K-均值算法聚类数的确定
0 引言
聚类分析：近几年来，聚类作为数据挖掘的主要方法之一，越来越引起人们的关注。聚类的输入是一组未分类的数据，而且事先也不知道要分成几类，它通过分析数据，根据一定的分类准则，合理划分数据，从而确定每个数据点所属的类别。当预先不知道类型数目，或者用参数估计和非参数估计难以分辨不同类型的类概率密度函数时，就需要采用聚类分析。有些聚类分析算法可以自动地确定类的个数K，也可以给定K作为算法的终止条件。若没有给定K，如何确定K，这是聚类分析中的一个关键问题。现有的聚类算法大致可以分为：划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法[1，2，3]。 K-均值聚类分析法：K-均值聚类算法是一种已知聚类个数的聚类算法。指定类个数为K，对样本集合进行聚类，聚类的结果有K个聚类中心来表达，基于给定的聚类目标函数（或者说是聚类效果判别准则），算法采用迭代更新的方法，每一次迭代过程都是向目标函数值减少的方向进行，最终的聚类结果使目标函数值取得极小值，达到较优的聚类效果[4]。 K-均值算法的缺点：
1）K-均值算法聚类数K需要预先给定。
2）算法对初始值的选取依赖性极大。不同的初始值，结果
往往得到不同的局部极小值。
3）K-均值算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当类的个数非常大时，算法的时间开销是非常大的。
4）由于将均值点作为聚类中心进行新一轮计算，远离数据密集区的孤立点和噪声点会导致聚类中心偏离真正的数据密集区，所以K-均值算法对噪声点和孤立点很明感。 5）K-均值算法一般只能发现球状簇。
K-均值聚类法的执行时间过度依赖K的取值，但是在实际问题中并不容易确定K值[5，6，7，8]，尤其是在样本数较多每个样本的维数又较大的情况下。那么要想得到合理的聚类效果K就不能随机，而是应由一定的方法来确定，在这种情况下如何选取K值，这是聚类分析中的一个很值得人们探讨的问题。本文通过对现有几种初始点选择及初始分类方法的改进，总结出几种可用于确定合理聚类数K的方法。 2 K-均值算法聚类数确定的方法
下面主要介绍几种常用的聚类类数的确定方法。聚类初始点选取及初始分类方法[4]，如：经验法、密度法、逐个归类法；确定最优聚类数的方法，如爬山法；本文提出的新方法：递推法。 2.1 经验法
这是K-均值方法原始方案中用于确定聚类数的方法。根据问题的性质，由人凭经验来指定类别数。
2.2 密度法
“密度”法选择凝聚点，最终的聚点数即为欲分类数K。这里的“密度”是具有统计性质的样本密度。先规定一个正数d1，再以每一样本点为球心，以d1为半径，并将落入球中的样本数（不包括球心处样本）定义为这样本的“密度”。选择具有最大密度的样本点作为第一凝聚点，并考察它与第二大密度样本点间的距离，若距离大或等于规定正值d2，就把第二大密度点看作第二凝聚点；若小于d2，则继续选择第三大密度的样本点作考察。用此方法按样本密度由大到小的顺序考察下去，在每次考察中若发现所考察的点与所有已选定的凝聚点间的距离都大于d2，便将此点定为新的凝聚点，否则便不作为凝聚点再选密度仅次于它的点作为考察点，直到所有样本点考察完毕。 2.3 逐个归类法
一种选择了凝聚点又确定了初始划分的方法，其凝聚点数即为类数K。首先规定一个阈值d。然后选w1={y1}，计算样本y2与y1的距离D（y2，y1），如其小于d，则归入w1否则建立新的类别w2={y2}。当轮到样本ye时，已有了K类即，w1，w2，w3，……，wK，而每类中第一个划入类的样本点分别为y11，y12，y13，……，y1K，则计算i=1，…，K，若D（y1i，ye）>d对所有的i＝1，…，K都成立，则建立新类={ye}。否则将ye归入与y11，y12，…，y1K距离最近的类别中。 2.4 爬山法――最优聚类数的逻辑判定法
在类别数未知情况下使用K-均值算法时，可以假设类别数是逐步增加的，例如对K＝1，2，3，……分别使用该算法。显然准则函数JK是随K的增加而单调地减少的。如果样本集的合理聚类数为K类，当类别数继续增大时，相当于将聚类很好的类别又分成子类，则JK值虽然继续减少但会呈现平缓趋势，如果作一条JK值随K变化的曲线，如下图所示，则其拐点对应的类别数就比较接近于最优聚类数。下图表示c＝4是较合适的聚类数。 3 递推法
从低级聚类划分问题的解中确定高级聚类划分的凝聚点，最终的凝聚点数即为欲分类数K。对样本集整体首先看作一个聚类，计算样本集总均值为凝聚点，并设定一个常数d，然后找与凝聚点相距最远的样本点，若凝聚点与最远点的距离大于等于d ，那么该最远的点便成为新的凝聚点，依此类推，则K聚类划分问题的凝聚点就是K-1聚类凝聚点再加上离最近的凝聚点最远的点（当然这个最近距离要大于d）。当最近凝聚点与那最远点的距离有小于d的时候结束递推[9，10]。 4 实验 4.1 实验结果
为了检测本文中几种算法的有效性，通过三个程序用Glass数据集、Iris数据集和Wine数据集分别对密度法、递推法及逐个归类法进行了测试，实验结果令人满意。其中密度法参数d1，
递推法d，及逐个归类法d都是随即输入的，不同参数可能对应不同的K值。经过反复输入参数进行测试，找到了Glass数据集聚类数为6时，Iris数据集聚类数为3时，Wine数据集聚类数为3时的各个参数值。实验结果如下表： 实验中参数依次如下： 密度法：1.40、0.45、60； 递推法：4.50、2.0、400； 逐个归类法：5.0、2.5、380。 4.2 分析比较
4.2.1 经验法与爬山法
经验法的优点和缺点都是显而易见。优点在于方便、快捷、高效，而缺点就在于应用的范围有限，在样本数据量较大、维数较多时很难确定K值，而且聚类效果难于保证；爬山法是一种最优聚类数的逻辑判定方法，是在类别数未知情况下使用的。但另人遗憾的是，并非所有的情况都能在图中找到这样的转折点A。当无明显的转折点时，这种确定最佳分类数目的方法将失效。 4.2.2 新方法与现有方法的比较
密度法中d1若太小，聚类数K就会太大，若太大，则聚类数K又会太小，故d1的选择应适当。d2值一般大于d1，常取d2=2d1。密度法能够在通过对样本值的计算来确定一个较合理的聚类数，是目前比较通用的确定初始凝聚点的方法，但它的计算量较大，尤其是在样本点数较大时，其计算就尤为复杂。与递推
法和爬山法相比，它的参数多了一个，从而又增加了确定合理聚类数的难度；递推法是笔者在初始凝聚点选择方法的基础之上改进而来的，计算量也较大，需要事先确定常数d，但较密度还是要简单一些，更容易理解，也更为高效；逐个归类法是一种既可确定类数K又可确定初始划分的方法，与以上两种方法比较就显得更为简单方便，每个样本只需被访问一次即可得到初始分类，从而得到分类数K。 5 结论
K-均值聚类算法作为使用较为广泛的一种聚类算法，本身的一个重要问题就是在聚类前必须先确定聚类的数目K ，本文在总结前人知识的基础上提出了多种确定K值的方法，并通过理论分析和实验验证等方法对其进行了分析总结，希望能为后来的读者起到一定的参考作用。
K-均值算法聚类数的确定-精选文档
