K—means聚类算法的实例教学研究

王丽娟　郝志峰　蔡瑞初　温雯　刘添添

摘要：针对数据挖掘课程理论知识多、讲解抽象难懂的教学实际，重点研究数据挖掘课程的经典算法K-means聚类算法的实例教学策略，以提高学生对数据挖掘算法的学习兴趣，加强实际应用能力。研究内容包括选择实例、讲解实例、扩展实例和教学评价4部分。选择合适的实例提升学生学习兴趣；讲解实例使得学生掌握基本的K-means算法；扩展实例增强学生实际应用K-means算法的能力；最后教学评价进一步完善教学质量和效果。

关键词：数据挖掘；实例教学；K-means

0 引言

随着沃尔玛超市发布的啤酒和尿布营销规则，数据挖掘（Data mining）逐步进入人们的日常生活，并且在生产和消费等各个领域都发挥着重要的指导作用。由于数据挖掘的重要作用，各个高校纷纷开设本科生以及研究生的数据挖掘课程。

数据挖掘是研究如何从大量数据中挖掘隐藏于其中的知识或者信息的科学。数据挖掘通常借助计算机科学、统计、在线分析处理、情报检索、机器学习、专家系统和模式识别等诸多技术来实现上述目标。该课程涉及大量数学和统计模型，较为抽象，而且具有很强的时效性，知识更新换代快。本科生或者研究生在学习这门课程的时候，概念较多，算法抽象，难以入门，更难于应用算法求解实际问题。为了获取较好的课堂教学效果，数据挖掘课程采用实例教学策略教学。

实例教学策略通过工具软件仿真建模，演示数据挖掘算法的具体运行过程，使得学生自己纳入数据挖掘算法学习、开发和研究过程。数据挖掘课程的实例教学策略包括选择实例、讲解实例、扩展实例和教学评价4个部分，如图1所示。

以K-means聚类算法实例作为数据挖掘实例教学的研究对象。具体讲解7个仿真数据的聚类问题；通过Matlab软件仿真K-means算法执行过程，使得学生了解K-means算法及其设计策略；扩展实例重点分析K-means算法中参数设置，使得学生真正掌握该算法，求解实际的聚类问题；教学评价进一步促进教师改进教学的不足，提升教学质量。

1 K-means聚类算法理论基础

聚类的思想在日常生活中广泛应用，如：物以类聚，人以群分。聚类是根据相似度形成数据的划分，使得同一类对象属于相同的类，而不同的对象位于不同的类。相似性度量是聚类算法的核心问题。常用的相似性度量如欧氏距离和夹角余弦等。K-means算法是一种基于欧氏距离的分割聚类算法。

K-means算法的基本思想：依据聚类个数C形成数据的C个划分，计算每个划分的类心，更新数据的类别为当前所属划分，不断迭代调整聚类及其类心，直至所有数据的类属不再改变为止。聚类个数c与K-means中的K对应表示聚类个数。

设数据集X={X₁，X₂，…，X_n}为待聚类的对象集，每个对象Ⅸ（1≤j≤n）由s个属性组成，记作X_j={X_j，…，X_js），其中x_jk是对象X_j的第k维属性值。第i类数据的中心定义为v_i，其中vi的任一属性值通过该类数据相应特征的平均值计算得到，即（1）式中：|v_i|为第i个聚类v_i所包含的数据个数。第i个聚类中心v_i与第j个数据点X_j的欧氏距离定义为（2）

根据式（2），将数据点划分到距离最近的数据类。重复计算类心v_i和数据类属，不断地迭代，调整聚类。当聚类目标函数的变化值达到指定的阈值，即聚类不再改变或者发生较小的改变，算法可以停止，获得聚类结果。聚类目标函数定义为（3）式中：d_ij为第i个聚类中心v_i与第h个数据点X_j的欧氏距离。目标函数J反映所有数据到其所属类心的距离之和。如果和较小，则表示数据靠近其所属类心，聚类内聚性好，聚类效果好；否则，表示每类数据比较分散，内聚性差，聚类效果差。

K-means算法描述如下：

（1）初始化：确定聚类个数C，随机选取C个数据作为聚类中心v_i。

（2）更新聚类：计算所有数据到C个中心v_i的距离，对每个数据选取与其最近的类心，将该数据归人该类。

（3）更新聚类中心：根据每个数据的类属，将同一类数据的特征值平均得到更新的聚类中心。

（4）迭代：计算该划分的对应的目标函数，的值，重复（2）～（4），直至J的值不变化或者J变化值达到指定的较小的阈值。

2 K-means聚类算法的实例教学

K-means算法采用了梯度下降和期望最大化等数学模型，算法较为复杂抽象。单纯根据上面的分析，学生无法形成直观的印象，因此，K-means算法需用实例教学策略。实例教学策略能够通过Matlab软件直观呈现7个仿真数据的K-means算法聚类过程，将抽象的算法具象呈现，从而降低算法的难度，提升学生学习兴趣。例1介绍了基本的K-means算法，属于实例讲解。但是在实际应用中，数据存在噪声、异常和缺失等情况，数据聚类结果较为复杂，因此，需要具体研究算法的参数，增强算法的健壮性。例2和例3分别讨论了聚类类数变化和类心变化的实例拓展过程。

2.1 实例选择

实际的聚类问题如文本聚类和图像聚类问题。文本聚类指计算机自动根据文本的语义，将文本分为政治、经济、军事、体育等类别。图像聚类是指计算机根据图片的颜色、纹理或轮廓自动识别图片的类型，分成海滩图片、森林图片、街道图片、日出日落照片等类型。无论文本信息还是图片信息均需要转换成每个实例的若干特征描述，即每个实例形成一个空间坐标点。聚类的过程就是根据空间点距离的远近，形成数据的划分，使得相似的数据（彼此靠近的数据）分成一类，不相似的数据（距离较远的数据）位于不同类。

由于课堂讲述的时间有限，因此将实例规模限定为7个2维仿真数据，如表1所示，数据初始分布如图2（a）所示。7个仿真数据的聚类过程如下所示。

2.2 实例讲解

本节重点介绍如何通过K-means算法聚类表1所示的7个仿真数据的聚类过程。

例1：初始化：设7个数据分成C=2类，随机选取（X₃，X₂）作为2个类心，用红色+号标记。

第1次聚类：根据图2（a）中的类心，计算每个数据到类心的距离如表2所示，从中选取距离较近的类心作为当前该数据的类属。第1次迭代后得到聚类为{X₁X₃X₆}{X₂X₄X₅X₇}，如图2（b）中2个圆圈所示，目标函数J=17.9。

更新第1次聚类的类心：根据图2（b）中数据分布重新计算2类的类心得到图2（b）中2个新的红色加号。

第2次聚类：根据图2（b）中的新类心，第2次迭代计算每个数据到类心的距离，如表3所示，选择最近的类心作为当前类属，得到聚类为{X₁X₃}{X₂X₄X₆X₇}，如图2（c）中2个圆圈所示，目标函数J=16.60降低。

更新第2次聚类的类心：根据图2（c）中数据分布重新计算2类的类心得到图2（c）中2个新的红色加号。

第3次聚类，如图2（d）所示，目标函数的值J=16.60，前后2次误差为0，聚类无改变，算法结束。

通过以上实例的讲解，学习到K-means算法的过程：根据初始数据类划分，更新每类的类心；根据更新的类心，更新数据类划分，重复上述过程，直到数据划分不改变或者仅有较小的改变结束聚类过程。

2.3 拓展实例

K-means算法的参数包括两方面，分别是：①聚类个数C不同，聚类结果是否相同？②初始聚类中心不同，聚类结果是否不同？如果聚类中心不正确，是否能得到正确的聚类结果？针对上述2个问题，通过2组实例数据分析K-means聚类算法的性能。

例2：设7个2维数据如表1所示。初始状态数据分布如图3（a）所示。聚类过程如下：

（1）初始化：设7个数据分成C=2类，随机选取X₁和X₇作为2个类心，用红色+号标记。

（2）第1次聚类：根据图3（a）中的类心，计算每个数据到类心的距离如表4所示，从中选取距离较近的类心作为当前该数据的类属。第1次迭代后得到聚类为：{X₁X₂X₃X₄}{X₅X₆X₇}，如图3（b）中2个圆圈所示，目标函数J=12.60。

（3）更新第1次聚类的类心：根据图3（b）中数据分布重新计算2类的类心得到图3（b）中2个新的红色加号。

（4）第2次聚类如图3（c）所示，目标函数的值J=12.60，前后2次误差为0，聚类无改变，算法结束。

上述实例说明：无论初始聚类中心如何设置，迭代过程会不断修正，使其收敛到一个局部最优的聚类结果。但是，初始聚类中心不同，聚类结果不同。作为初始聚类中心比更合适，因为前者最终聚类目标函数比后者低，聚类结果更合理。

接下来，研究聚类类数对聚类结果的影响，设计实验对比不同聚类类数的聚类结果。

例3：设7个2维数据如表1所示。初始状态数据分布如图4（a）所示。聚类过程如下：

（1）初始化：设7个数据分成C=3类，随机选取{X₃X₄₇}作为3个初始聚类中心，用红色+号标记。

（2）第1次聚类：根据图4（a）中的类心，计算每个数据到类心的距离如表5所示，从中选取距离较近的类心作为当前该数据的类属。第1次迭代后得到聚类为{X₁X₃}{X₂X₄}{X₅X₆X₇），如图4（b）中3个圆圈所示，目标函数，/=7.99。

（3）更新第1次聚类的类心：根据图4（b）中数据分布重新计算2类的类心得到图4（b）中2个新的红色加号。

（4）第2次聚类如图4（c）所示，目标函数的值J=7.99，前后2次误差为0，聚类无改变，算法结束。

上述实例说明：初始聚类类数C不同，聚类结果不同。C=3作为初始聚类类数比C=2更合适，因为前者最终聚类目标函数比后者低，聚类结果更合理。可以根据先验知识或者专家经验确定初始的聚类类数的范围，在此范围内多次运行聚类算法，从中选择最合适的聚类类数及其聚类结果作为最终的聚类结果。

2.4 教学评价

实例教学策略所选择的仿真问题和仿真数据来源于实际问题，可以极大调动学生学习兴趣。实例教学策略通过Matlab软件仿真将抽象的聚类过程具象呈现在学生面前，降低了算法学习的难度，易于学习。实例拓展分析了实际问题所遇到的参数设置，可以提升学生在实际中应用K-means算法求解的操作能力。

设计问卷对比研究传统教学策略和实例教学策略2种教学方法学生喜欢程度。问卷包括A～E共5个等级及其对应分值，分别是：非常枯燥（-2分）、比较枯燥（-1分）、一般（0分）、比较有趣（1分）和非常有趣（2分）。本次调查分传统教学法和实例教学策略两部分内容，分别发放问卷50份，回收问卷48份，回收率96%，问卷有效率为100%。传统教学策略的投票结果如表6所示；实例教学策略的投票结果如表7所示。调查结果显示：学生更喜欢通过实例教学策略学习数据挖掘课程，实例教学策略的综合得分远远高出传统教学策略的得分。

3 结语

K-means聚类算法采用了期望最大化和梯度下降等数学方法，迭代求解数据聚类，其求解过程抽象复杂，不易于在有限课时范围内开展大规模的理论分析，学生学习较为困难。实例教学策略能够深入浅出、形象具体地展现K-means聚类的方方面面，加深学生对于算法的理解，为学生进一步应用算法解决实际问题奠定基础，具有较好的教学效果。未来将深入研究数据挖掘课程中其他算法的实例教学策略。

（见习编辑：张勋）