基于K均值算法增强初始中心的研究

杨黎明　屈晓旭

【摘 要】随着数据库技术以及数据库管理系统的迅速发展，人们积累的数据越来越多。聚类（clustering） 作为数据挖掘三大领域（关联规则，聚类，分类）之一被广泛应用[1]。K-均值算法属于聚类中最普遍快速方法，常采用误差平方和准则函数作为聚类准则。但K均值算法不能保证标准的全局最小值，这导致对初始质心的高敏感度。本文提出通过消除初始质心的随机选择来提高算法性能。本文提出增强的初始质心的K均值算法，由于对应用数据集进行加权平均，消除了初始值的随机选择，减少了迭代步数，降低了计算复杂度。

【关键词】聚类；K均值；误差平方和准则

0 引言

K均值算法是一种常用的聚类技术，由于其简单性、快速的数学计算和记忆效率深受学者欢迎。K均值算法通过迭代对一组对象进行聚类，使得同一组中的对象比其他组中的对象更相似[2]。K均值算法是一种聚类算法，它将数据集分为K个非空、非重叠和非从属的簇。本文提出一种“增强初始质心”的K均值算法，主要思想是修改选择初始质心的方法。在传统的K均值算法中，初始质心是随机选择的聚类点。而增强的方法是使用加权平均值作为质心选择。本研究的主要目的是消除初始质心的随机选择，因为它导致不太可靠的结果，并提高聚类效率。新方法在选择初始质心之前，计算每个属性的每个点的加权平均值。本研究将原始K均值算法和增强初始质心的K均值算法，应用于对学生的考试成绩评价，在可靠性和迭代次数方面比较了它们的性能。

1 传统K均值算法

1967年，J.B.MacQueen提出了一种简单、快速、高效的用来处理数据聚类问题的K均值算法。K均值算法主要思想是将数据集合划分为K个类簇。首先随机选取K个点作为初始聚类中心，然后计算数据集合中各个数据对象到各聚类中心距离，按照每个数据对象距离最近的原则归到对应的类中；新的分类中心形成后，重新计算得到新的K个点作为每个类新的中心，重新计算各个数据对象与新的中心的距离，再次按照距离最近的原则归整新的类[3]。此过程一直循环，倘若相邻两次的聚类中心不再发生任何变化，说明数据对象归类结束。

式中，K表示类簇个数，S表示簇Ci的数据对象，mi表示簇ci的中心（均值）。||s-mi||2可计算出数据对象到所属类中心的距离。

K均值算法不能保证标准的全局最小值，这导致对初始质心的高敏感度。本文提出通过消除初始质心的随机选择来提高算法性能。K均值聚类算法的聚类结果很大程度上取决于随机选择的初始质心的可靠性。

在数学中，二维区域的质心或几何中心是形状中所有点的算术平均位置。随机初始选择不是基于任何计算或算法，因此会导致不适当的结果。

下面进行实例应用计算，假设我们有4名学生，每个学生有两个属性（平时成绩，考试成绩）。学生1（100，100），学生2（200，100），学生3（400，300），学生4（500，400）。我们的目标是根据这两个特征将这些学生分成K=2（通过和未通过的学生）的聚类，以确定四名学生的學业成绩。在这个例子中，平时测试成绩满分是500，书面考试成绩满分是400。

在K均值算法的原始方法中，随着初始质心的随机选择，我们假设学生1的质心1为（100，100），质心2为（200，100）。下面使用欧几里德距离公式对每个学生的质心1进行样本计算。

基于最小距离的对象聚类的结果是：

组1为学生1

组2为学生2、3、4。

基于新成员的每组的计算新质心是：

组1仅具有一个成员，质心保留在质心1=（100，100）中。

组2有三个成员，因此，质心是三个成员之间的平均坐标：质心2=（200+400+500）/3，（100+300+400）/3 =（366.67，266.67）。

第二次迭代后，聚类结果为：

组1=学生1和2

组2=学生3和4

以下表格是重复K均值算法原始方法的主要步骤的结果：

（1）确定质心/质心

（2）使用欧几里得距离计算物体中心距离

（3）对象聚类。

用新成员，计算另一个质心群：质心1=（100+200）/2，（100+100）/2=（150，100），质心2=（400+500）/2，（300+400）/2=（450，350）。

质心1的样本计算=（150，100）

质心2的样本计算=（450，350）

三次迭代后的最后分组如下所示。

可以看出，传统K均值算法随机选择初始质心导致了三次迭代。

3 增强初始中心K均值算法

3.1 主要步骤

3.1.1 初始化

给定簇的数量K，增强初始质心意味着给予对象属性更准确的加权平均值。计算得到的最高和最低加权平均值作为创建初始分簇的初始质心。初始分簇使用计算的初始质心，将对象划分为K个群集。分簇和收敛步骤则相似于传统的K均值算法。

3.1.2 分簇

分配步骤：使用欧几里德距离计算聚类，如果数据当前不在具有最接近原型的簇中，则将其重新分配给距离其最近的簇；

更新步骤：如果发生重新分配，则更新簇，并使用当前聚类重新计算质心；

3.1.3 重复迭代，直到产生收敛

由于质心是数据集中指示相等权重的所有点的平均位置，因此加权平均值是指定数据集中点的实际权重，其中最高加权平均和最低加权平均值用X，Y来表示。该算法结果表明组间重叠被最小化，并且分离更明显。增强质心的K均值算法应用数据集的加权平均值，能够清楚地分离数据集，并且具有较少的迭代次数。它不仅消除了初始质心的随机选择，而且减少了用于聚类的欧氏距离计算。endprint

3.2 实例验证

加权平均值是按权重大小进行分配的平均值，以下是加权平均数S的公式：

s=∑wx/∑w（3）

将K均值算法的同样应用在学生成绩问题中，确定列中的最高点。

对于属性X（平时测验），其最高点（即最高成绩）是500。根据给定的权重得到每个点的加权平均值，权重将等于给定属性的最高点。

X[1]=100*500/1200=41.67

X[2]=200*500/1200=83.33

X[3]=400*500/1200=166.66

X[4]=500*500/1200=208.33

对于属性Y（书面考试），其最高点是400。Y的每个点的加权平均值为：

X[1]=100*400/900=44.44

X[2]=100*400/900=44.44

Y[1]=300*400/900=133.33

Y[2]=400*400/900=177.78

X=41.57和Y=44.44，这是通过加权平均获得的两个初始质心。因此，初始质心是质心1=（100，100），质心2 =（500，400）。通过欧几里德距离的公式来计算群集中心到每个对象之间的距离。

迭代1：使用欧几里德距离知道质心1（100，100）之间的距离的样本计算如下所示：

质心1的样本计算=（100，100）

质心2=（500，400）物体的欧氏距离的样本计算如下所示：

质心2的样本计算=（500，400）

使用欧几里德的第一次迭代的初始结果如下表所示。

质心1（100，100）=（0.00，100.00，360.55，500.00）之间的距离。 质心2（500 400）=（500，424.26，141.42，0.00）之间的距离。 基于计算，对象聚类是检查对象到两个质心的最小距离的过程。

初步计算后，增强型K均值组1的迭代1已经有2名成员，1名和2名学生，与第2组相同， 只有一名成员，第2组有3名成员。

在新方法中，由于组1和组2各有2个成员，因此我们必须计算对象分簇的新质心。

迭代2：新質心1将为（100 + 200）/ 2（100 + 100）2 =（150，100）

物体与质心1的新计算距离为（50，50，320.15.460.97）。

质心1的样本计算=（150，100）

新质心2将为（400 + 500）/，（300 + 400）/ 2 =（450，350）。

质心2=（430.11，353.55，70.71，70.71）物体距离的样本计算如下所示：

质心2的样本计算=（450，350）

比较原始的K均值算法和迭代，修改的K均值算法已达到稳定，不需要更多的迭代。与以前的K均值算法相比，迭代次数减少了。基于增强初始质心的K均值算法获得的初始质心如表所示。

使用增强初始质心的K均值算法进行聚类的最终结果如下所示。

4 小结

增强的初始质心的K均值算法，由于对应用数据集进行加权平均，消除了初始值的随机选择，减少了迭代步数，降低了计算复杂度。K均值必须预先输入K值作为输入参数，因为不适当的K选择可能产生不准确的分类结果，这是我们下一步研究的方向，着力解决该问题。

【参考文献】

[1]J Han J，Kamber M.范明，孟小峰，等译：数据挖掘概念与技术.第一版.北京：机械工业出版社.2006，185-217.

[2]T.Kanungo，D.M Mount，N.S.Netanyahu，etal.An efficient K-means clusteringalgorithm：analysis and implementation.IEEE Transactions on Pattern Ana1ysis and Machine Intelligence，2002， 24（7）：881-892.

[3]万小军，杨建武，陈晓鸥.文档聚类中 K-means 算法的一种改进算法.计算机工程，2003，29（2）：102-103，157.

[4]周娟.基于最大最小距离法的多中心聚类算法研究[D].庆：重庆大学汁算机系统结构，2006.endprint