基于相对密度的聚类算法.pdf

维普资讯 计算机科学2007Vo1．34No．2 基于相对密度的聚类算法 ) 刘青宝 邓 苏 张维明 (国防科学技术大学信息系统与管理学院 长沙410073) 摘 要 基于密度的聚类算法因其抗噪声能力强和能发现任意形状的簇等优点，在聚类分析中被广泛采用，本文提出 的基于相对密度的聚类算法，在继承上述优点的基础上。有效地解决了基于密度的聚类结果对参数值过于敏感、参数 值难以设置以厦高密度簇完全被相连的低密度簇所包含等问题。 关键词 聚类，K近邻，聚类参数，相对密度 RelativeDensity-basedClusteringAlgorithm LIUQing-Bao DENGSu ZHANGWeiMing (CollegeofInformationSystem andManagement，NationalUniversityofDefenseTechnology，Changsha410073) Abstract Withstrongabilityofdiscoveryarbitraryshapeclustersandhandlingnoise，densitybasedclusteringisoneof primarymethodsfordatamining．Thispaperprovidesaclusteringalgorithm basedonrelativedensity，whichefficiently resolvestheseproblem ofbeingverysensitivetOtheuser-definedparametersandtOOdifficultforuserstodeterminethe parameters． Keywords Clustering，。K—nearestneighbors。Clusteringparameter，Relativedensity 聚类分析是一种重要的人类行为，已经广泛地应用在许 SCAN算法。它将具有高密度的区域划分为类。DBSCAN算 多领域，包括模式识别、数据分析、图像处理，以及市场研究。 法依赖两个参数实现聚类；对象的邻域半径 e和e邻域内的 目前在文献中存在大量聚类分析算法，它们多数侧重于如何 最少对象数MinPts。DBSCAN通过检查数据集中每个点的 提高算法效率，而往往忽视了算法的有效性问题。聚类算法 ￡邻域来寻找聚类；如果一个点P的 ￡邻域包含多于MinPts 的有效性问题主要表现在三个方面：其一，聚类算法大多要求 个点，则创建一个以P为核心对象的新类。然后，DBSCAN 用户输入一定的参数，例如希望产生的簇的数 目，而这些参数 反复寻找从这些核心对象直接密度可达的对象，当没有新点 通常难以确定，特别是针埘高维空间中稀疏分布的实际应用 可被添加到任意类时，聚类过程结束，那些不属于任何类的点 数据集，用户几乎无法给出合适的算法参数，因此非专业用户 被标志为噪声 AN可以在有噪声的情况下中发现任 需要与数据分析专家密切配合才能保证获得理想的聚类结 意形状的类，但是它留给用户决定的参数难以确定，而且它对 果。导致算法的使用极为不便 ；其二，聚类结果对于输入的参 参数值非常敏感，设置的细微不同即可能导致差别较大的聚 数值过于敏感 ，往往参数值的一些轻微变化却产生聚类结果 类结果_2]。如图 l所示，当所选的MinPts较大，￡较小的时 的很大差异；其三，对于高维的实际应用数据集其数据分布往 候 ，就会把A、B两个类全部判别成孤立点。 往是稀疏的、杂乱的，很难为算法选择全局的参数进行准确的 聚类分析，使得聚类的质量难以保证。本文提出了基于相对 密度的聚类算法，在继承了基于密度的聚类算法具有抗噪声 能力强、能发现任意形状的簇等优点的基础上 ，有效地解决了 ⑦ ③ 基于密度的聚类结果对参数值过于敏感、参数值难以设置等