基于粒子群优化的带障碍约束DBSCAN算法研究

摘要

空间数据挖掘是现代研究领域中一个非常活跃的研究课题,空间数据挖掘已经广泛应用于遥感系统、全球定位系统和地理信息系统,在国民经济和国防建设方面发挥着越来越大的作用。空间聚类分析作为数据挖掘中一项重要的挖掘任务和挖掘方法,能够发现密集和稀疏的空间数据关系,并且在聚类过程中充分考虑了现实障碍物的存在,具有广阔的应用前景和实际价值。
　　 DBSCAN算法是一种重要的基于密度的高效聚类方法,适用于任意形状和大小的几何图形的聚类,可以自动确定形成的簇的数目,有效地将簇和环境噪声相分离。DBSCAN具有聚类速度快,能够处理复杂数据对象等优点,然而由于参数选择和参数计算的方法不同,算法的执行结果和执行效果则相差很大。目前,已经有许多学者致力于研究有效的DBSCAN参数选择方法,从而使它能够适应更加实际和复杂的数据挖掘问题中。
　　 粒子群优化算法作为一种新颖的群集智能算法,在诞生后的10年多时间里,其算法结构和性能改善一直是研究者们关注的热点。粒子群优化算法是基于群集智能理论的关键优化算法,通过群体中粒子间在合作与竞争的过程中产生群体智能,并利用此群体智能指导整个迭代搜索过程。
　　 本文首先介绍了聚类和空间聚类的原理,并针对其中基于密度的DBSCAN聚类算法的优缺点进行了深入的分析。然后,根据粒子群优化算法的迭代搜索策略,并借助移动机器人路径规划方法的动态避障思想,提出了一种新的基于粒子群优化算法的障碍约束条件下DBSCAN空间聚类算法-PSODBSCAN。该算法在DBSCAN算法的基础上引入了障碍模型,对数据进行坐标初始化处理,将聚类对象的空间二维坐标编码简化为一维,然后利用粒子群优化算法进行迭代搜索,从而获得数据对象之间的最短障碍路径和最小障碍距离,最后,PSODBSCAN根据粒子群优化算法求得的障碍距离,将数据对象按照DBSCAN聚类算法进行空间聚类,并通过Matlab进行仿真实验和正确性验证。通过理论分析和实验表明,该算法可以得到高质量的聚类结果,在处理空间约束时更具有合理性和准确性。