K―means聚类算法的实例教学研究.docVIP

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={X1，X2，…，Xn}为待聚类的对象集，每个对象Ⅸ（1≤j≤n）由s个属性组成，记作Xj={Xj，…，Xjs），其中xjk是对象Xj的第k维属性值。第i类数据的中心定义为vi，其中vi的任一属性值通过该类数据相应特征的平均值计算得到，即（1）式中：|vi|为第i个聚类vi所包含的数据个数。第i个聚类中心vi与第j个数据点Xj的欧氏距离定义为（2） 　　根据式（2），将数据点划分到距离最近的数据类。重复计算类心vi和数据类属，不断地迭代，调整聚类。当聚类目标函数的变化值达到指定的阈值，即聚类不再改变或者发生较小的改变，算法可以停止，获得聚类结果。聚类目标函数定义为（3）式中：dij为第i个聚类中心vi与第h个数据点Xj的欧氏距离。目标函数J反映所有数据到其所属类心的距离之和。如果和较小，则表示数据靠近其所属类心，聚类内聚性好，聚类效果好；否则，表示每类数据比较分散，内聚性差，聚类效果差。 　　K-means算法描述如下： 　　（1）初始化：确定聚类个数C，随机选取C个数据作为聚类中心vi。 　　（2）更新聚类：计算所有数据到C个中心vi的距离，对每个数据选取与其最近的类心，将该数据归人该类。 　　（3）更新聚类中心：根据每个数据的类属，将同一类数据的特征值平均得到更新的聚类中心。 　　（4）迭代：计算该划分的对应的目标函数，的值，重复（2）～（4），直至J的值不变化或者J变化值达到指定的较小的阈值。 　　2 K-means聚类算法的实例教学 　　K-means算法采用了梯度下降和期望最大化等数学模型，算法较为复杂抽象。单纯根据上面的分析，学生无法形成直观的印象，因此，K-means算法需用实例教学策略。实例教学策略能够通过Matlab软件直观呈现7个仿真数据的K-means算法聚类过程，将抽象的算法具象呈现，从而降低算法的难度，提升学生学习兴趣。例1介绍了基本的K-means算法，属于实例讲解。但是在实际应用中，数据存在噪声、异常和缺失等情况，数据聚类结果较为复杂，