第24卷第5期 2007年5月计算机应用研究Application Resea心h of ComputersV01.24.No.5 Mav 2007基于聚类分析的K—means算法研究及应用爿:张建萍1,刘希玉2(1.山东师范大学信息科学与工程学院,山东济南250014;2.山东师范大学管理学院,山东济南250014摘要:通过对聚类分析及其算法的论述,从多个方面对这些算法性能进行比较,同时以儿童生长发育时期的数据为例通过聚类分析的软件和改进的K.means算法来进一步阐述聚类分析在数据挖掘中的实践应用。
关键词:数据挖掘;聚类分析;数据库;聚类算法中图分类号:TP311文献标志码:A 文章编号:1001—3695(200705—0166-03Application in Cluster’s Analysis Is Analyzed in Children DeVelopment PeriodZHANG Jian—pin91,UU Xi—yu。
(1.coz比伊矿,咖mo砌n 5c掂Me&E蟛袱^增,|s胁础增Ⅳo丌mf‰洫瑙毋,五n 帆5^a蒯D昭250014,吼i胁;2.cozz学矿讹加舻删眦, s^0n幽凡g舳丌Mf‰i孵璐匆,^加n乩。
砌。
昭250014,傩iMAbstract: nispaper passed cluster’s analysis and its algorithm corTectly,comparedthese algorithm perfbrnlances f}om a lotof respects,and explained that cluster analysis excavates the practice application of in datum further to come through software and impmved K—means aIgorithm,cIuster of analysis at the same time practise appIication.Key words:data mining; cluster analysis; database; cluster algorithm随着计算机硬件和软件技术的飞速发展,尤其是数据库技术的普及,人们面临着日益扩张的数据海洋,原来的数据分析工具已无法有效地为决策者提供决策支持所需要的相关知识, 从而形成一种独特的现象“丰富的数据,贫乏的知识”。
数据挖掘…又称为数据库中知识发现(Knowledge Discovery from Database,KDD,它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的复杂过程。
目的是在大量的数据中发现人们感兴趣的知识。
常用的数据挖掘技术包括关联分析、异类分析、分类与预测、聚类分析以及演化分析等。
由于数据库中收集了大量的数据,聚类分析已经成为数据挖掘领域的重要技术之一。
1问题的提出随着社会的发展和人们生活水平的提高,优育观念嵋一。
逐渐渗透到每个家庭,小儿的生长发育越来越引起家长们的重视。
中国每隔几年都要进行全国儿童营养调查,然而用手工计算的方法在大量的数据中分析出其中的特点和规律,显然是不现实的,也是不可行的。
为了有效地解决这个问题,数据挖掘技术——聚类分析发挥了巨大的作用。
在数据挖掘领域,聚类算法经常遇到一些问题如聚类初始点的选择H J、模糊因子的确定‘5o等,大部分均已得到解决。
现在的研究工作主要集中在为大型的数据库有效聚类分析寻找适当的方法、聚类算法对复杂分布数据和类别性数据聚类的有效性以及高维数据聚类技术等方面。
本文通过对聚类分析算法的分析并重点从聚类分析的软件工具和改进的K—means算法两个方面来论证聚类分析在儿童生长发育时期中的应用。
2聚类算法分析聚类∞1分析是直接比较各事物之间的性质,将性质相近的归为一类,将性质差别较大的归入不同的类。
在医学实践中也经常需要做分类工作,如根据病人的一系列症状、体征和生化检查的结果,判断病人所患疾病的类型;或对一系列检查方法及其结果,将之划分成某几种方法适合用于甲类病的检查, 另几种方法适合用于乙类病的检查,等等。
聚类分析被广泛研究了许多年。
基于聚类分析的工具已经被加入到许多统计分析软件包或系统中,如S—Plus、sPSS,以及SAS。
大体上,聚类算法¨o可以划分为如下几类:(1划分方法。
给定一个包含n个对象或数据行,划分方法将数据集划分为南个子集(划分。
其中每个子集均代表一个聚类(%≤n。
代表算法为K—means算法、K—medoids算法和 cLAm~Ns算法。
(2层次方法。
该方法就是通过分解所给定的数据对象集来创建一个层次。
它存在的缺陷就是在进行(组分解或合并之后无法回溯。
将循环再定位与层次方法结合起来使用常常是有效的,如BIRcH和CURE,就是基于这种组合方法设计的。
(3基于密度的方法。
只要临近区域的密度(对象或数据点的数目超过某个阈值,就继续聚类。
DBscAN是一个有代表性的基于密度的方法。
它根据一个密度阈值来控制簇的增长。
(4基于网格的方法。
基于网格方法将对象空间划分为有限数目的单元以形成网格结构。
其主要优点是它的处理速度很快,其处理时间独立于数据对象的数目,只与量化空间中每一维的单元数目有关。
STING就是一个典型的基于网格的收稿日期:2006—04—12;修返日期:2006—05—15基金项目:国家自然科学基金资助项目(6037405;“泰山学者”建设工程专项经费资助项目;山东省自然科学基金重大项目(Z2004G02;山东省中青年科学家奖励基金资助项目(03BS003作者简介:张建萍(1979一,女,山东滨州人,硕士研究生,主要研究方向为遗传算法、数据挖掘;刘希玉(1964・,男,山东济南人,教授,博导, 主要研究方向为信息管理、管理信息系统(MIs. 。
万方数据第5期张建萍等:基于聚类分析的K—means算法研究及应用・167・方法。
(5基于模型的方法。
该方法就是为每个聚类假设一个模型,然后再去发现符合相应模型的数据对象。
它根据标准统计方法并考虑到噪声或异常数据,可以自动确定聚类个数;因而它可以产生很鲁棒的聚类方法。
数据挖掘在不同领域对聚类算法提出了各自特殊的要求, 表1可以给聚类算法的研究和应用提供参考‘“。
表l聚类算法比较3儿童生长发育的分析聚类分析在数据挖掘中的应用主要有以下三个方面:(1聚类分析能作为一个独立的工具来获得数据的分布情况,观察每个簇的特点,集中对特定的某些簇作进一步的分析。
如:①聚类分析软件v1.2。
此软件主要用于血型、蛋白质多态、品种聚类等方面的统计分析,可自动进行杂合度、多态信息含量、遗传距离以及聚类的计算,并可自动画出聚类图。
② sPSs统计软件。
sPSs软件是一种专业的统计分析软件,用于数据的各种分析,从而最终为企、事业的科学决策服务。
其中采用聚类分析是理想的多变量统计技术,主要有分层聚类法和迭代聚类法。
本文通过一组儿童生长发育的数据运用SPsS工具进行分析,如表2所示。
表2儿童生长发育时期的数据月份数月平均增长率(% 月份数月平均增长率(% 运用SPSS工具调用K—means Cluster过程可完成由用户指定类别数的大样本资料的逐步聚类分析。
逐步聚类分析就是先把被聚对象进行初始分类,然后逐步调整,得到最终分类。
为研究儿童生长发育的分期,笔者对1253名1月一7岁儿童进行了抽样调查,分别对儿童的身高(cm、体重(蛞、胸围(cm和坐高(cm进行了测量。
资料作如下整理:先把1月 ~7岁划成19个月份段,分月份算出各指标的平均值,将第1月的各指标平均值与出生时的各指标平均值比较,求出月平均增长率(%,然后第2月起的各月份指标平均值均与前一月比较,求出月平均增长率(%(表2。
将儿童生长发育时期分为四期,所以聚类的类别数为4,从而确定四个儿童生长发育期的起止区间。
①激活数据管理窗口,定义变量名。
虽然月份分组不做分析变量,但为了更直观地了解聚类结果,也将之输入数据库。
②进行统计分析,在聚类方法上选择Iterateandclassify指定初始类别中心点,按K—means算法作迭代分类。
对聚类结果进行方差分析。
结果解释:首先系统根据用户的指定,按四类聚合确定初始聚类的各变量中心点,未经K—means算法迭代,其类别间距离并非最优;经迭代运算后类别问各变量中心值得到修正。
③对聚类结果的类别间距离进行方差分析。
方差分析表明,类别间距离差异的概率值均小于0.001,即聚类效果好。
这样,原有19类(即原有的19个月份分组聚合成四类,第一类含原有1类,第二类含原有1类,第三类含原有2类,第四类含原有15类。
具体结果系统以变量名qm一1存于原始数据库中。
在原始数据库(图1中,可清楚地看到聚类结果;参照专业知识,将儿童生长发育分期定为:第一期,出生后至满月,增长率最高;第二期,第2个月起至第3个月,增长率次之; 第三期,第3个月起至第8个月,增长率减缓; 第四期,第8个月后,增长率显著减缓。
图1逐步聚类分析的分类结果(2运用聚类分析软件可以很方便地对数据进行分析,利用分析的结果,在孩子生长发育时期合理安排好饮食,促进儿童健康快乐成长。
同时,聚类分析可以作为其他算法(如特征和分类等的预处理步骤,这些算法再在生成的簇上进行处理。
本文以改进的K—means算法归’为例来说明儿童生长发育时期的特征。
算法描述如下:算法:K.means。
划分的K—means算法基于簇中对象的平均值。
输入:簇的数目矗=4和输入n=19的表2的数据。
输出:四个簇,使平方误差准则最小。
方法:①任意选择四个对象作为初始簇的中心;②repeat;③根据簇中对象的平均值,将每个对象(重新赋给最类似的簇;④更新簇的平均值,即计算每个簇中对象的平均值;⑤until不再发生变化。
在本算法中要用到以下几个定义:定义1Dss‘1叫(DistancesquareSum是指数据库中所有对象的平方误差的总和,即印=∑:;。
∑。
以Ip—mi 2。
其中,p 是空间中的点,表示给定的数据对象;m。
是簇c。
的平均值(p坐吼mm mnm m nm胸仉n 吼啦 mm m髓㈨协撼篮篙㈣身mm mc;m m n mm慧篇篇臻撼㈣怒溜埝怒端㈣ L LL n.Z jl ; 0258万方数据・168・计算机应用研究 2007年和m;都是多维的。
定义2数据对象i与,的相异度为略2=∑。
酝屯2/∑。
瓠。
其中,d。
2是第%个值距离的平方,对每个变量根据其重要性赋予一个权重,运用加权的欧几里得距离Ⅲ1可以计算:咏2=%‰一謦l 2+职J如一&J 2+…+%I%一岛J 2其中,江(置。