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

论文摘要

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

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景与意义
• 1.2 带障碍约束的空间聚类国内外研究现状与发展趋势
• 1.2.1 国内外研究现状
• 1.2.2 研究发展趋势
• 1.3 粒子群优化技术国内外研究现状与发展趋势
• 1.3.1 国内外研究现状
• 1.3.2 研究发展趋势
• 1.4 本文的主要研究内容及组织结构
• 第2章 带障碍约束的空间聚类分析
• 2.1 聚类概述
• 2.2 空间聚类概述
• 2.3 带障碍约束的空间聚类概述
• 2.3.1 带障碍约束的空间聚类的提出
• 2.3.2 带障碍约束的空间聚类的相关概念
• 2.4 带障碍约束的空间障碍距离算法概述
• 2.4.1 障碍距离分析方法
• 2.4.2 障碍距离方法比较
• 2.5 本章小结
• 第3章 基于粒子群的障碍路径优化分析
• 3.1 粒子群优化算法概述
• 3.1.1 粒子群算法的基本思想
• 3.1.2 粒子群算法的参数改进
• 3.1.3 粒子群算法的优化过程
• 3.2 基于粒子群的障碍距离优化
• 3.2.1 障碍距离的定义
• 3.2.2 障碍距离的约简算法
• 3.2.3 基于粒子群的障碍距离算法
• 3.3 本章小结
• 第4章 基于粒子群优化的带障碍约束DBSCAN空间距离分析
• 4.1 带障碍约束的DBSCAN空间聚类算法
• 4.1.1 传统DBSCAN算法概述
• 4.1.2 带障碍约束DBSCAN算法概述
• 4.1.3 带障碍约束DBSCAN改进算法
• 4.2 基于粒子群优化的空间聚类算法—PSODBSCAN
• 4.2.1 PSODBSCAN算法思想
• 4.2.2 PSODBSCAN算法实现
• 4.2.3 PSODBSCAN算法复杂度分析
• 4.3 本章小结
• 第5章 实验与结果分析
• 5.1 障碍距离优化算法实验
• 5.1.1 实验环境与方案
• 5.1.2 算法正确性验证
• 5.1.3 算法结果比较
• 5.2 PSODBSCAN空间聚类实验
• 5.2.1 实验环境与方案
• 5.2.2 聚类质量验证
• 5.2.3 算法效率分析
• 5.3 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文和取得的科研成果
• 致谢