论文部分内容阅读
聚类是一个无监督分类技术,根据数据元素间的相似关系,将数据划分到不同的团簇中。通过分析聚类结果,观察不同团簇的分布规律,能够发现数据背后隐藏的规律。随着社会信息化的发展,聚类分析在社会生活中发挥着越来越重要的作用,已广泛应用于社会多个领域。数据规模的快速增长和多样化,提出适应能力更强的聚类算法成为当前急需解决的问题。基于密度的聚类算法能适用于任意形状数据的聚类,具有较强抗噪声能力,成为近年来聚类算法研究的方向。密度峰值聚类算法(Clustering by fast search and find of density peak,CFSFDP)是Alex Rodriguez提出的基于密度的聚类算法。该算法思想简单、聚类效果好、时间效率高,在一些数据集上获得了不错的聚类效果,但该算法依然存在一些不足:(1)CFSFDP算法基于假设:中心结点被密度比它小的结点包围,中心结点到比它密度大的结点距离较远。该假设认为同一团簇中只有一个密度峰值,当团簇中有多个密度峰值时,该算法容易将一个团簇错误划分为多个团簇,不适用于团簇中有多个密度峰值的数据集。(2)截断距离是CFSFDP算法中的唯一参数,截断距离的大小决定结点的密度。算法中提供了截断距离的计算方法,实验证明该计算方法不适用于形状复杂的数据集。(3)为了识别噪声结点,CFSFDP算法定义了边界区域,边界区域中的结点邻域内包含其他团簇结点。该算法找到边界区域中局部密度最大的结点,将该结点的密度设定为筛选噪声结点的阈值,密度大于阈值的结点是团簇结点,密度小于阈值的结点是噪声结点,该噪声识别方法准确率不高。针对CFSFDP算法的不足,提出了基于传递距离的密度峰值聚类算法(PBCFSFDP)和自动识别噪声的PB-CFSFDP算法(APB-CFSFDP)。PB-CFSFDP算法解决了CFSFDP算法的不足,APB-CFSFDP算法在PB-CFSFDP基础上实现了噪声自动识别。为了能更好地评价聚类效果,本文基于传递距离提出了一组聚类算法评价指标,该指标能很好评价不同形状数据集。本文的主要研究内容如下:1.提出新的聚类评价指标传统的紧密性、间隔性和戴维森堡丁指数评价指标,结点间的距离为空间直线距离,使得指标不适用于非凸数据集。本文提出了基于传递距离的紧密性(PBCP)、间隔性(PBSP)和戴维森堡丁指数(PBDBI)指标,能较好的适用于凸数据集和非凸数据集。在PBDBI基础上,提出新的聚类效果评价指标PBCI,该指标综合考虑了基于传递距离的紧密性、间隔性和噪声识别因素,可以评价具有噪声识别能力的聚类算法的聚类效果。2.提出PB-CFSFDP算法(1)提出了基于传递距离的相似度计算方法,以结点间的传递距离取代空间直线距离,缩短了密度峰值间的距离,使同一团簇中最多有一个中心结点,解决了CFSFDP算法误将一个有多个密度峰值的团簇划分为多个团簇的问题。(2)提出新的截断距离计算方法,截断距离值等于数据集构成的最小生成树中第L短边值。实验证明,L在较大范围内都有不错的聚类效果,截断距离有较高鲁棒性。(3)提出一种基于决策图的噪声识别方法,决策图以结点局部密度为横坐标,结点的k近邻距离为纵坐标。画出所有结点在决策图中的分布,选出密度小且k近邻距离较大的结点作为噪声结点。实验证明,该方法能够较准确识别噪声结点。3.提出APB-CFSFDP算法PB-CFSFDP在不同形状数据集上取得较好的聚类效果,但该算法噪声识别过程需要手动选择噪声结点,算法执行效率不高。本文基于PBCI指标和PB-CFSFDP算法提出了APB-CFSFDP算法。本文将PB-CFSFDP和APB-CFSFDP算法与K-means、DBSCAN、CFSFDP算法进行对比,实验证明,PB-CFSFDP和APB-CFSFDP算法在数据适用性、参数的鲁棒性、噪声识别准确性都优于对比算法。APB-CFSFDP算法在PB-CFSFDP算法基础上实现了噪声自动识别,提高了算法聚类效果和执行效率。