作者：张毅
1 引言
聚类是指在没有任何先验知识的情况下，根据数据特征的相似性将同类数据聚集在一起的过程，属于无监督分类的范畴。聚类的目标是使得同一类簇内对象的相似性尽可能大，不同类簇之间对象的相似性尽可能小。聚类作为一种重要的数据分析和挖掘手段，已被广泛应用于语音识别、字符识别、图像处理、信息安全、金融等领域。
迄今为止,国内外研究人员相继提出很多聚类算法，主要分为基于层次的聚类、基于划分的聚类、基于密度的聚类、基于网格的聚类、基于模型的聚类等。基于层次的聚类是指对样本集合进行合并或者分裂，直到满足某一个终止条件，代表算法有BIRCH算法、CURE算法。优点是能得到不同粒度的聚类结构，缺点是很难确定合并和分裂的准则。基于划分的聚类是指首先将所有数据粗略地划分为K个类，然后通过迭代算法使某个准则达到最优来对划分进行修正。代表算法有k-means算法、k中心点方法及其改进。优点是算法简单、速度快，缺点是K值需要事先指定，而且只能发现圆形类簇。基于密度的聚类算法是指根据数据对象的分布密度，将密度足够大的数据对象聚类在一起，样本空间被低密度区间划分开，代表算法有DBSCAN算法、OPTICS算法、DENCLUE算法。优点是可以发现任意形状的类簇。缺点是参数的设置对聚类结果影响较大。基于网格的聚类是指将数据空间量化为有限单元，构成一个可以聚类的网格结构，代表算法有STING算法、CLIQUE算法。优点是运算速度快，缺点是存在量化尺度问题。基于模型的聚类是指寻找给定数据与某种数据模型的最佳拟合，代表方法有COBWEB算法、AutoClass算法、SOM算法。
近年来随着人工智能、机器学习、模式识别、数据挖掘等领域的不断发展，又提出了许多新的聚类算法。为了解决样本点不仅仅只属于某一个类的问题，提出了模糊聚类，用模糊理论的方法对数据进行软划分。谱聚类是一种基于图论的聚类方法，通过计算数据之间相似矩阵的特征值和特征向量进行聚类。子空间聚类是针对高维数据空间出现的一种有效聚类方法，通过特征选择在不同的子空间上进行聚类。然而，在很多聚类方法中都需要提供聚类个数作为参数，目前还没有一个很好的办法可以保证获得准确的聚类数目，这一直是聚类分析中的一个难点。Frey提出一种利用亲密度传播进行聚类的方法。该方法无需事先指定聚类数目，能够快速、有效地处理大规模数据集，但对于比较松散的聚类结构就会得到较多的聚类数目。
2014年Alex Rodriguez和Alessandro Laio在Science上提出一种简洁的聚类算法。与以往的聚类算法相比，该方法能够处理任意形状的类簇，而且对数据变换有很好的顽健性。但该方法中聚类个数和聚类中心无法自动确定，需要手工选取，这无疑限制了算法的应用范围和领域。本文提出的基于局部密度的聚类算法，是对该算法的一种改进。在初步选取候选聚类中心的基础上，增加一个优化选取聚类中心的过程，使用基于密度连通的算法合并或剔除不正确的聚类中心，使用大密度最近邻方法确定样本类别。实验证明，该方法具有较好的聚类效果和性能，有效解决了聚类个数不确定的问题。
2聚类过程
2.1 算法思想
本文算法的核心思想是基于局部密度的概念，它表示与该点的距离在一定范围的点的个数，也就是说一个点附近点的个数越多，其局部密度越大。该算法认为聚类中心是由一些局部密度比较低的点围绕，并且这些点距离其他高局部密度的点的距离都比较大。为此定义两个量。
(1)局部密度pi
其中，dc>0为截断距离，需要用户确定。推荐做法是选择de，使得每个点的平均邻居数为总点数的1%~2%（假设为t）。为了将聚类算法扩展到异形类簇，本文使用高斯核函数来定义局部密度，既避免了不同的点具有相同局部密度的问题，又能识别异形类簇。
表示所有局部密度大于xi的点中，与xi距离最近的点xj与xi之间的距离。对于密度最大的点，δi=maxdij，表示与xi距离最大的数据点与xi之间的距离。
2.2确定类簇中心
类簇中心是指局部密度比较大，且距离其他较大局部密度的点的距离比较远的点。首先计算所有点的pi和δi，以p为横坐标，以δ为纵坐标形成决策图，选择pi和δi都比较大的点作为类簇的中心。为了定量确定类簇的中心点，定义yi=piδi，然后对{yi∣i=1，…，N}进行降序排序，选择yi大于某个阈值A的点为中心点。此时可能会存在两种特殊情况：第一种情况是一些p很大但占值很小的点会被选为中心点，这样可能会造成同一个类簇中有两个中心点存在，将本来属于同一个类簇的数据点分成两个不同的类簇；第二种情况是p很小，但6很大，这样会把部分异常点视为聚类的中心，本文的做法是对p和δ都设置各自的阈值，将大于阈值的点视为候选中心点。然后使用基于密度的连通性算法将候选中心点合并或剔除，具体算法如下。算法1 DCC(determing-clustering-center)
输入：X={x1,X2，…，XN}是需要聚类的数据点；Ⅳ是数据点个数；{plp2，…州为每个数据的局部密度；{δ1,δ2，…，δN}为每个样本点到高局部密度的最小距离。
输出：类簇中心点{Xm1，xm2,…，Xmk}。
2.3聚类
类簇中心确定以后，需要确定每个点划分给某个类簇的可靠性。本文使用大密度最近邻方法将每个点归类到局部密度比自己大的最近邻的簇。聚类算法如下。
算法2 LDC(local-density-clustering)
输入：X={x1,X2，…，XN}是需要聚类的数据点；N是数据点个数。
3评价指标
评价一个聚类算法的好坏一般基于这样的原则：簇中的成员尽可能地互相靠近，簇与簇之间的距离尽可能远。假设P={Pl，P2，…，Ps）为人工标注的分类结果，c={G1,C2，…，cm}为聚类算法的划分。本文采用以下评价指标。
(1 )purity：正确聚类的样本数占总样本数的比例
(2)R指数：表示C和P之间的相似程度
假设a表示两个点在C和P中均属于同一个簇的个数；6表示两个点在C中属于相同的簇，在P中属于不同簇的个数：c表示两个点在C中属于不同的簇，在P中属于相同簇的个数：d表示两个点在C、P中均属于不同簇的个数。R值越大说明G和P的吻合度越高，说明C的聚类效果越好。
4实验与结果分析
4.1 实验数据
UCI数据库是一个专门用于测试分类、聚类算法的国际通用标准测试数据库，包含Wine、Iris、Glass等数据集。其中Iris数据集包含3类，每一类代表一种类型的鸢尾花，每类有50个数据，共150个样本，在3个类簇中分布均匀，其中一类与另外两类线性可分，另外两类有部分重叠。Wine数据集包含178个样本，13个数值型属性，共分成3类，每类中样本数量不同。Glass数据集共有69个样本，包含3类，每类占总数据量的1/3。另外，Leuk72_3k也是比较常用的聚类测试数据集。
4.2类簇中心选择
算法首先根据局部密度和到高密度样本的距离来确定类簇中心，然后计算其他非中心样本与类簇中心的距离，从而决定样本归属。因此，算法中类簇中心点的选择不但决定着聚类的个数，还影响其他样本的类别归属。图l(a)为Iris数据样本经过多维尺度变换后样本的分布情况，图l(b)为y/l/=l，…，Ⅳ）从大到小排序后的结果。如果选择yi最大的2个样本作为类簇中心，则整个数据被分成2个类簇，如果选择yi值最大的前5个样本作为类簇中心，则样本被分成5个类簇。为了更合理地确定类簇中心，首先给Yi设置一个相对较小的阈值（本实验的阈值为6），使较多的样本点成为候选类簇中心，然后使用算法1对候选类簇中心进行合并，得到最优的类簇中心，图l(c)中菱形的点为候选类簇中心。图l(d)中菱形的点为合并后的类簇中心，样本的不同形状标示根据最优类簇中心聚类后的结果。
4.3 de对算法结果的影响
de的选择决定局部密度的大小，如果取得太大，pi的区分度不大，类簇中心不准确，如果取得太小，类簇中心的个数过多，会导致同一类簇的数据被划分为不同的类簇。为了
证明de的大小对实验结果的影响，本文针对不同的数据集，分别采用不同大小的de做实验，得出的实验结果如图2所示（t为de的值使得每个点的平均邻居数占所有点的比例）。
从图2中可以看出，不同数据集下，de对聚类结果的影响是不一样的。lris和Wine数据集都有最优的de。对于Iris数据集，当t>2%时，只能聚出2类，当t<l%时，虽然能聚出3类，但聚类的准确率在降低。Leuk72_3k和Glass数据集的聚类结果基本不受dc的影响。通过分析发现，Leuk72_3k数据集的类内样本点的距离远小于类间的距离。因此在不同的应用背景下，应该根据具体的问题选择合适的de参数。
4.4聚类结果对比
为了验证算法的有效性，将本文中算法与经典的K-means算法和DBSCAN算法进行实验对比，并用purity、R指数、F-measure来衡量算法的优劣性。表1为几种聚类算法在不同数据集上的实验结果比较。
从表1可以看出，本文算法相对于K-means、DBSCAN算法在各指标上均有较大的提升，说明该算法有较好的聚类效果和性能。
Alex提出的算法中，聚类个数以及类簇中心都通过人工方式选定，为了确定最优的聚簇类数，本文采用最优评价指标方法来确定聚类个数。在给定的数据集上，通过选择不同的类簇中心个数，对数据集进行不同的划分，并计算不同划分的评价指标，如图3所示。选择评价指标最好的聚类个数为最佳聚类个数。从图3中可以看出，4k2_far数据集的最优类簇个数为4，Iris数据集的最优类簇个数为3。
5结束语
针对基于局部密度的聚类算法无法自动选择类簇个数和类簇中心的问题，本文在该算法的基础上增加了一个优化选取聚类中心的过程，使用基于密度连通的算法合并或剔除不正确的聚类中心。与其他聚类算法相比，该方法具有较好的聚类效果和性能，并有效地解决了聚类个数不确定的问题。本文还验证了不同的截断距离对聚类结果的影响，实验证明在实际应用中应该根据具体的聚类问题选择合适的参数。
6摘要：聚类分析一直是机器学习和数据挖掘领域一个比较活跃而且极具挑战性的研究方向。Alex提出的基于局部密度的聚类算法是一种快速、有效的聚类方法，但该方法通过手工选取确定聚类个数和聚类中心。为此，对原算法进行改进，在初步选取候选聚类中心的基础上，使用基于密度连通的算法优化选取聚类中心，然后使用大密度最近邻方法确定样本类别。实验证明，该方法能有效解决聚类个数和聚类中心无法确定的问题，同时在聚类评价指标上显示出较好的聚类效果和性能。
下一篇:返回列表
