K_means聚类算法研究

1、第30卷第1期Vol 30 No 1长春师范学院学报(自然科学版Journal of Changchun Normal Universi ty(Natural Science2011年2月Feb.2011K-means 聚类算法研究孙 庚1,冯艳红1,郭显久1,张春平2(1.大连海洋大学信息工程学院,辽宁大连 116023;2.黑龙江工程学院土木与建筑工程学院,黑龙江哈尔滨 150050摘 要K-means 算法作为聚类分析算法,已被广泛地应用到诸多领域。本文研究了K-means 算法的基本原理,并将其应用到高校学生入学信息分析中。高考学生入学的相关信息包含了大量重要的学习及其他方面的信息,对

2、这些数据信息进行分析和研究,有助于教师对不同类别的学生进行不同方式的教学,做到因材施教。首先对学生的入学信息数据进行预处理,然后使用K-means 算法,对学生信息进行分类评价;最后利用所获得的分类结果指导学生在大学期间的学习方向以及教师对学生的培养工作。关键词聚类;K-means;学生信息中图分类号TP27 文献标识码A 文章编号1008-178X(201101-0001-04收稿日期2010-11-01作者简介孙 庚(1979-,男,黑龙江齐齐哈尔人,大连海洋大学信息工程学院讲师,硕士,从事计算机应用研究。0 前言聚类是将物理或抽象对象的几何分成相似的对象类或簇的过程.使同一个簇中的对象之

3、间具有很高的相似度,不同簇中的对象高度相异.聚类分析已广泛地用于很多领域,例如在经济学的市场研究中帮助市场分析人员根据客户的购买模式发现不同的客户群,在生物学中根据基因或其他特性推导动物或植物的分类,聚类分析中的离群点检测可用于商业领域的信用卡欺诈检测和监控电子商务,聚类分析还可以用于WEB 文档的分类等其他应用领域1.在不同的应用领域和不同的学科中,很多聚类技术都得到了发展.常用的聚类方法有:划分发方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法2.作为数据挖掘的主要任务之一的聚类分析方法,应具有可伸缩性、处理不同类型属性、发现任意形状的簇、处理带噪声的数据、处理高维数据和处

4、理基于约束的聚类的能力3.本文主要研究划分方法中的K-means 聚类方法,并改进算法将其应用到实际领域.高校学生的入学信息承载了学生大量的重要的学习和其他方面的信息,给高等教育提供了信息帮助,做到因材施教,有的放矢,有利于培养多方面的人才.学生入学信息包括了学生此前的全部学习经历、奖惩经历、兴趣爱好、身体状况、个人阅历、参加的社会活动、所在地域等多方面的信息,通过充分地利用这些信息资源,深层次地挖掘每个学生的独立特性,进行分类,对不同类别进行分析,并采取恰当的教学、教育和培养方案,以达到更好地培养人才的目的.1 数据预处理1.1 学生入学信息分析及处理作为数据挖掘的主要技术之一,聚类分析成为

5、一种常用的分析数据的方法.主要处理大量的相关或不相关数据信息,以数据为研究对象.因此,我们应先分析学生信息.信息取自学生档案,信息内容零散、复杂,需要先进行整理,并对信息进行基本的处理,形成学生信息数据库,作为聚类分析的数据对象集.对缺失数据进行处理,采用忽略该条信息、人工填写、用均值填充等方法来处理.为尽量减少对聚类结果的影响,本文运用属性的均值填充方法处理缺失数据.接下来进行数据的标准化.由于数据对象包含不同的数据类型,不同的数据类型的度量方式和度量范围不同,对聚类结果有影响,所以为避免这种情况,在聚类分析之前对数据进行标准化处理.计算标准度量值,给定数据对象的变量f ,标准化处理方法如公

6、式(1所示.1z i f =x i f -m fs f.(1其中,z i f 为标准度量值,x i f 为变量f 的第i 个度量值,m f 为变量f 的均值,s f 为均值绝对值偏差,如公式(2所示.s f =1n(|x 1f -m f |+|x 2f -m f |+ +|x n f -m f |.(21.2 确定距离度量d (i,j =(x i 1-x j 12+(x i 2-x j 22+ +(x in -x jn 2.(3其中i =(x i 1,x i 2, ,x in ,i =(x i 1,x i 2, ,x in ,为任意两个数据对象.2 相异度分析2.1 数据对象 数据对象在聚类分

7、析中一般用数据矩阵表示,矩阵如下所示.x 11 x 1f x 1p x n 1x n fx n p.矩阵中有n 个数据对象,每个数据对象有p 个变量.数据对象矩阵无法直接应用于聚类分析,所以使用聚类算法之前将数据对象矩阵转换为相异度矩阵,转换算法根据数据对象间的相异度构造相异度矩阵,相异度矩阵如下所示.0 d (2,10 d (n,1d (n,2.其中,d (i,j 为数据对象之间的距离,即相异度,一般为非负值,两个对象越相似,值越接近0,否则值越大.2.2 相异度计算具体应用聚类分析解决实际问题时,数据对象的各变量类型不唯一,常见的有区间标度变量、二元变量、分类变量、序数变量和比例标度变量4

8、.由这几种类型中的一种或几种组合成实际的数据对象的类型.另外,在信息检索中的文本聚类,数据对象包含了大量的文字符号,一般用非传统度量的方式,采用非度量相异度进行聚类分析.本文中数据对象属于传统可度量变量,是包含几种类型的混合类型的变量,把不同类型的变量放在同一个相异度矩阵中.假设数据集合中包含p 个混合类型的变量,对象i 和j 之间的相异度d (i,j 定义如公式(4所示.d (i,j = pf =1 (f i j d (f i jp f =1 (f i j.(4其中, (f i j 的值为0或1,当数据对象i 或j 没有变量f 的值,或值为0,且变量f 是非对称二元变量,则 (f ij的值为

9、0,否则为1.d (f ij 的值为变量f 对i 和j 之间的相异度的贡献,其计算方法取决于数据对象的变量类型.如果变量f 是区间标度变量,d (f i j 的值如公式(5所示.d (f i j =|x i f -x jf |max h x hf -min h x h f.(5其中,h 遍历f 的所有非缺失对象.如果f 是二元或分类变量,d (f ij 的值如公式(6所示.d (f i j =0,x i f =x jf ;1,x i f x jf .(62如果f 是序数变量,计算秩r ij ,映射为z i j =r ij -1M f -1,M f为类别总数,将z i j 作为区间标度变量,计算

10、相异度d (f i j .如果f 是比例标度变量,可采用如下三种方法计算相异度.方法一:采用与处理区间标度变量相同的方法计算相异度,该方法产生的结果不准确,因为刻度可能扭曲.方法二:对比例标度变量进行对数变换,将变量f 的值x i f 变换为y i j =log (x i f ,把y ij 作为区间标度变量,计算相异度d ij .方法三:将变量f 当作连续的序数数据,计算r ij 和z i j ,将z ij 作为区间标度变量,计算相异度d (f i j .在本文的应用中,从学生入学信息数据库中抽取部分样本作为实验数据,进行研究,抽取的数据如表1所示,只列出3条记录,实际实验样本为1000名学生

11、的记录.表1 学生信息数据样例id 科别性别高考总分政治面貌身高爱好特长1理工男563党员178文学类2文史女459团员162智力类3管理男468其他181体育类3.1 基本K-means 聚类的算法描述输入:k :簇的数目D:数据对象的集合输出:k 个簇的集合算法:( 从D 中随机选取k 个数据对象作为簇的初始中心;( 根据簇中数据对象的均值,将每个数据对象重新分配到距离最近的簇;( 重新计算每个新簇中的对象的均值;( 如果准则函数收敛,则结束聚类分析,否则回到第二步.其中,准则函数一般采用平方误差准则,如公式(7所示.E = ki =1 p Ci|p -m i |2.(7其中,E 为所有数

12、据对象的平方误差和,p 为给定对象,m i 是簇C i 的均值.用平方误差准则使生成的k 个类尽可能地紧凑和独立.4 算法实现根据3.1的算法描述,并对计算机专业学生信息数据库系统的学生数据进行规范化,取样150条记录,借助于Matlab 软件,假设分为两类,聚类结果如图1所示.其中,三角符号和正方形符号各代表一类学生.从图1中看到,得到了较好的聚类结果.将聚类结果应用到实际中,可以对不同类别的学生进行不同方式的教育教学.3 图1 学生信息聚类结果5 结论聚类分析现已成为一个跨学科交叉的领域,被广泛应用于很多领域.在高校教育方面,聚类分析可以帮助教师发现学生中不同的特征组,采取因材施教的方法授

13、课.本文主要是利用了聚类分析中的K-means聚类算法对学生的入学信息进行分析,实现对学生的分组教学.由于K-means算法采用最小化平方误差函数作为评价函数,所以当聚类的结果簇是紧凑的,并且不存在离群点时,聚类效果很好.其计算复杂度是O(nkt,n为数据对象总数量,k是聚类的类别数,t是迭代的次数,从其时间复杂度上看,当处理大量数据时,其伸缩度和效率较好.但是,当存在离群点时,由于这些点对均值有很大的影响,导致聚类结果不准确;K-means聚类算法必须事先给出聚类的数目,即k的值;另外,只有均值可计算才行得通,对于某些应用,包含有分类属性,若无确切的均值定义,该方法无法实施.K-means算

14、法还可能出现终止于局部最优解的问题,有待进一步解决.参考文献1李路.基于二叉树算法实现Linux网络Socket流量控制与计费的设计J.沈阳大学学报,2008(1:4-6.2孙可,刘杰,王学颖.K均值聚类算法初始质心选择的改进J.沈阳师范大学学报:自然科学版,2009(4:448-450.3逄玉俊,柳明,李元.K均值聚类分析在过程改进中的应用J.华中科技大学学报:自然科学版,2009(S1:245-247.4司永胜,刘刚,高瑞.基于K-均值聚类的绿色苹果识别技术J.农业机械学报,2009(S1:100-104.5罗洎,王莹.基于K-均值聚类的中国存货景气指数设计研究J.经济研究导刊,2009(

15、26:10-12.6Jiawei Han,M icheline Kamber.数据挖掘概念与技术M.范明,孟小峰,译.北京:机械工业出版社,2006:256-266.Research on K-means Clustering AlgorithmSUN Geng1,FENG Yan-hong1,GUO Xian-jiu1,Z HANG Chun-ping2(1.School of Information Engineering,Dalian Ocean University,Dalian116023,China;2.School of Civil and Building Engineerin

16、g,Heilongjiang Institute of Technology,Harbin150050,China Abstract:As a kind of clustering analysis algorithm,K-means algorithm has widely been applied to various fields.In this paper,we research the basic principle of this algorithm and apply it to information analysis of senior school students.The

17、 in formation about senior school students entrance includes much important information about t study and other aspects.Ana lyzing and researching these data and information are helpful for universities to carry out c ollege education and realize indi vidualized instruction.Firstly,we preprocess the inf