基于聚类分析的Kmeans算法研究及应用概要.docx
《基于聚类分析的Kmeans算法研究及应用概要.docx》由会员分享，可在线阅读，更多相关《基于聚类分析的Kmeans算法研究及应用概要.docx（17页珍藏版）》请在冰点文库上搜索。
基于聚类分析的Kmeans算法研究及应用概要
第24卷第5期2007年5月
计算机应用研究
ApplicationResea心hofComputers
V01.24.No.5Mav2007
基于聚类分析的K—means算法研究及应用爿:
张建萍1,刘希玉2
（1.山东师范大学信息科学与工程学院,山东济南250014;2.山东师范大学管理学院,山东济南250014
摘要:
通过对聚类分析及其算法的论述,从多个方面对这些算法性能进行比较,同时以儿童生长发育时期的数据为例通过聚类分析的软件和改进的K.means算法来进一步阐述聚类分析在数据挖掘中的实践应用。
关键词:
数据挖掘;聚类分析;数据库;聚类算法
中图分类号:
TP311文献标志码:
A文章编号:
1001—3695（200705—0166-03
ApplicationinCluster’sAnalysisIsAnalyzedinChildrenDeVelopmentPeriod
ZHANGJian—pin91,UUXi—yu。
（1.coz比伊矿,咖mo砌n5c掂Me&E蟛袱^增,|s胁础增Ⅳo丌mf‰洫瑙毋,五n帆5^a蒯D昭250014,吼i胁;2.cozz学矿讹加舻删眦,s^0n幽凡g舳丌Mf‰i孵璐匆,^加n乩。
砌。
昭250014,傩iM
Abstract:
nis
paperpassedcluster’sanalysisanditsalgorithmcorTectly,compared
thesealgorithmperfbrnlancesf}omalot
ofrespects,andexplainedthatclusteranalysisexcavatesthepracticeapplicationofindatumfurthertocomethroughsoftwareandimpmvedK—meansaIgorithm,cIusterofanalysisatthesametimepractiseappIication.
Keywords:
datamining;clusteranalysis;database;clusteralgorithm
随着计算机硬件和软件技术的飞速发展,尤其是数据库技
术的普及,人们面临着日益扩张的数据海洋,原来的数据分析工具已无法有效地为决策者提供决策支持所需要的相关知识,从而形成一种独特的现象“丰富的数据,贫乏的知识”。
数据挖掘…又称为数据库中知识发现（KnowledgeDiscoveryfromDatabase,KDD,它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的复杂过程。
目的是在大量的数据中发现人们感兴趣的知识。
常用的数据挖掘技术包括关联分析、异类分析、分类与预测、聚类分析以及演化分析等。
由于数据库中收集了大量的数据,聚类分析已经成为数据挖掘领域的重要技术之一。
1问题的提出
随着社会的发展和人们生活水平的提高,优育观念嵋一。
逐渐渗透到每个家庭,小儿的生长发育越来越引起家长们的重视。
中国每隔几年都要进行全国儿童营养调查,然而用手工计算的方法在大量的数据中分析出其中的特点和规律,显然是不现实的,也是不可行的。
为了有效地解决这个问题,数据挖掘技术——聚类分析发挥了巨大的作用。
在数据挖掘领域,聚类算法经常遇到一些问题如聚类初始点的选择HJ、模糊因子的确定‘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—meansCluster过程可完成由用户指
定类别数的大样本资料的逐步聚类分析。
逐步聚类分析就是先
把被聚对象进行初始分类,然后逐步调整,得到最终分类。
为研究儿童生长发育的分期,笔者对1253名1月一7岁儿童进行了抽样调查,分别对儿童的身高（cm、体重（蛞、胸围（cm和坐高（cm进行了测量。
资料作如下整理:
先把1月~7岁划成19个月份段,分月份算出各指标的平均值,将第1月的各指标平均值与出生时的各指标平均值比较,求出月平均增长率（%,然后第2月起的各月份指标平均值均与前一月比较,求出月平均增长率（%（表2。
将儿童生长发育时期分为四期,所以聚类的类别数为4,从而确定四个儿童生长发育期的起止区间。
①激活数据管理窗口,定义变量名。
虽然月份分组不做分析变量,但为了更直观地了解聚类结果,也将之输入数据库。
②进行统计分析,在聚类方法上选择Iterate
and
classify指
定初始类别中心点,按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不再发生变化。
在本算法中要用到以下几个定义:
定义1
Dss‘1叫（Distance
square
Sum是指数据库中所有
对象的平方误差的总和,即印=∑:
;。
∑。
以Ip—mi2。
其中,p是空间中的点,表示给定的数据对象;m。
是簇c。
的平均值（p
坐吼m
mm
n
mmn
m
胸仉n吼啦m
mm
髓㈨协撼篮篙㈣
身m
mm
c;mmnm
m
慧篇篇臻撼㈣怒溜埝怒端㈣L
L
Ln
.
Zj
l;0
25
8
万方数据
・168・计算机应用研究2007年
和m;都是多维的。
定义2数据对象i与,的相异度为略2=∑。
酝屯2/∑。
瓠。
其中,d。
。
2是第%个值距离的平方,对每个变量根据其重要性赋予一个权重,运用加权的欧几里得距离Ⅲ1可以计算:
咏2=%‰一謦l2+职J如一&J2+…+%I%一岛J2其中,江（置。
%,…,瓦、j=（x『l’&,…,%是两个p维的数据对象。
6:
。
是值为O—l的权重,它决定第七个值的重要性。
Dss是判别K-means聚类结果的重要指标。
通过%,试图找到使Dss函数值最小的划分,一般实际可达到局部最优,即算法最终要使Dss最小化,采用这种方法是试图使生成的结果簇尽可能紧凑和独立。
基于K—means算法同样可得到图l所示的结果。
（3聚类分析也可以进行孤立点的分析。
经常存在一些数据对象,它们不符合数据的一般模型,这些数据对象被称为孤立点。
孤立点的分析有着广泛的应用¨L”1,如欺诈检测即探询不寻常的信用卡使用或电信服务;此外,它在市场分析中可用于确定极低或极高收入的客户的消费行为、或者在医疗分析中用于发现对多种治疗方式的不寻常的反应。
4结束语
本文通过改进的K—means算法和聚类分析工具sPss来对儿童生长发育期进行分析。
在科技发展的今天,随着信息化产业的不断发展,大量的数据迫切需要强有力的数据分析工具的出现,从而导致了数据挖掘的蓬勃发展,而聚类分析已经成为数据挖掘领域一个非常活跃的研究课题。
用户当然希望聚类的结果是可解释的、可理解的和可应用的。
如何选择聚类方法和正确地使用聚类算法也是很重要的,而目前所使用的聚类算法均存在某方面的缺陷,也没有统一的标准,因此如何使聚类算法成为像sQL语言那样统一、标准的语言,还有待于计算机工作者的努力。
参考文献:
[1]朱明.数据挖掘[M].舍肥:
中国科学技术大学出版社,2002:
5—6.[2]卫生部关于八省（自治区婴幼儿营养健康状况调查报告[R]。
北京:
新华出版社,2005:
1.3.
[3]杭燕.体育幼儿园现代体育课程模式的探索（上[J].学前教育文荟。
2000（6:
10-12.
[4]GONzALEzT.clusteringtominimi2ea11dmaximuminter℃lu8terdi争tance[J].TheoreticaIc伽puterscie眦e,1985,38（2—3:
293—306.
[5]PALNR,BEzDEKJc.0nclustervalidityforthefuz2yc-meaIlsmodel[J],mEETra嘲c廿onsonFuzzySystems,1995,3（3:
370一
379.
[6]邵峰晶,于忠清.数据挖掘的原理与算法[M].北京:
中国水利水电出版社.2003.
[7]HANJiawei,KAMBERM.Dataminingconceptsandtechniques[M].范明,孟小峰,等译.北京:
机械工业出版社.
[8]马庆国.管理统计[M].北京:
科学出版社,2002:
3-120.
[9]wIsHARTD.K.meansclusteringwithoutlierdetection:
the25thAn—nualCorlferenceoftheGe珊aJlclassificationSociety[C].Munich:
UniversityofMunich,200l:
14—16.
[10]左子叶,朱扬勇.基于数据挖掘聚类技术的信用评分评级[J].计算机应用与软件,2004,21（4:
1—3,101.
[11]何彬彬,方涛,郭达志.基于不确定性的空间聚类[J].计算机科学,2004,31（11:
196—198.
[12]钱锋,徐麟文.知识发现中的聚类分析及其应用（J].杭州师范学院学报:
自然科学版,200l（2:
34—37.
[13]许向东,张全寿.数据仓库与数据挖掘的应用[J].计算机系统应用.1998（4:
20—24.
（上接第162页⑤各种功能资源配置信息。
插件描述文件plu一百n.xml集中描述了插件的基本信息（如插件的名字、类型、实现类的类名:
组合和依赖关系等。
5结束语
ACT—Ps解决了可配置和可扩展发布订阅通信的一些初步问题,并在实际数据交换系统中进行了配置和扩展实现,为一般的发布订阅中间件系统的建立提供了参考。
目前可配置发布订阅系统的研究仍然是一个新的领域,后续的工作是进一步深入研究设计模型之间的语义冲突和发布订阅系统安全控制问题。
参考文献:
[1]cuGOLAG,NrITrOED,FuGGETTAA.TheJEDIevent—basedinfra—stmcturea11dits印plicationtothedevelopmentoftheOPSSWFMS
[J].磁EETran鼢c廿ononsoft、忸reEngin船ring,2001,27（9:
827—850.
[2]EUGSTERPT,FELLERP,GuERRA0uIR.%emaIIy‰esofpub—lish/subsc曲e[J].ACMCompu廿嘴Surveys,2003,35（2:
114一131.[3]sOuzACRB,BAsAVESWARASD,REDMILESDF.Usingeventnotificationserversto
support印pljcationawareness:
IntemationalconferenceonsoftwareEn百neeringandApplications[c].NewYork:
IEEEpress,2002:
521—526.
[4]F玎_ZPA豫ICKG,KAPLANs,MANSFIELDT.Supponjngpublica-vailabilityaIldaccessibilitywithelvin:
experiencesandrenections[J].ComputerSupponedco叩e髓tiveWork,2002,ll（3:
447—474.[5]IBMCorporation.Gryphon:
publish/subsc曲eoverpublicnetworks『R].Yorktown:
IBM7rJWatsonResearchCenter,2001.
[6]cARzANIGAA,ROsENBLUMDS,写驴0LFAL.Des迳口andev出ua-tionofawide-areaeventnotificationservice『J].ACMTnInsac戗。
璐onComputerSystems,2001,19（3:
332—383.
[7]BARRETTDJ,cLARKELA,TARRPL,e￡。
z.Afhmeworkfore.vent-basedsoftw盯eintegration[J]‘AcMTran鼢ctio璐帆SoftWa心EngineeringandMethodology,1996,5（4:
378—421.
[8]cARzANIGAA,ROSENBLUMDS,w0LFAL.DesignaIldevalua—tionofawide吨reaeventnoti6cationservicefJ].ACMTransactiononComputerSysten坞,200l,19（3:
332—383.
[9]cARzANIGAA,R0sENBLuMDs,w0LFAL.challengesfordi争tributedeventservices:
scalabilityvs.expressiveness:
pmc.0fEDD’99[c].NewYork:
IEEE
Press,1999:
72—77. 万方数据
基于聚类分析的K-means算法研究及应用
作者:
张建萍,刘希玉,ZHANGJian-ping,LIUXi-yu
作者单位:
张建萍,ZHANGJian-ping（山东师范大学,信息科学与工程学院,山东,济南,250014,刘希玉,LIUXi-yu（山东师范大学,管理学院,山东,济南,250014刊名:
计算机应用研究
英文刊名:
APPLICATIONRESEARCHOFCOMPUTERS年,卷（期:
2007,24（5被引用次数:
12次
参考文献（13条1.朱明数据挖掘2002
2.卫生部关于八省（自治区婴幼儿营养健康状况调查报告20053.杭燕体育幼儿园现代体育课程模式的探索（上2000（06
4.GONZALEZTClusteringtominimizeandmaximuminterclusterdistance1985（2-35.PALNR.BEZDEKJCOnclustervalidityforthefuzzyc-meansmodel1995（036.邵峰晶.于忠清数据挖掘的原理与算法2003
7.HANJiawei.KAMBERM.范明.孟小峰Dataminingconceptsandtechniques8.马庆国管理统计2002
9.WISHARTDK-meansclusteringwithoutlierdetection2001
10.左子叶.朱扬勇基于数据挖掘聚类技术的信用评分评级[期刊论文]-计算机应用与软件2004（0411.何彬彬.方涛.郭达志基于不确定性的空间聚类[期刊论文]-计算机科学2004（1112.钱锋.徐麟文知识发现中的聚类分析及其应用2001（0213.许向东.张全寿数据仓库与数据挖掘的应用1998（04
相似文献（10条
1.学位论文许存兴聚类分析在数据挖掘中的应用2004
聚类分析是数据挖掘方法中的一个重要的方法.该文首先对数据挖掘进行了简要的描述;其次、着重对数据挖掘中的聚类分析法进行讨论;最后、以一个超市的商品销售为例,用数据挖掘中的聚类分析法进行了挖掘.因此,该文从研究数据挖掘的算法角度出发,从三个方面对数据挖掘进行了论述:
一、数据挖掘的概述通过对数据挖掘的概念、方法、过程、特点、作用及其与统计学关系的描述,使我们对数据挖掘有一个整体的了解.二、聚类分析在数据挖掘中的应用在这部分首先介绍了统计学中的聚类分析基础知识,即距离与相似系数和聚类的特征与聚类间的距离.其次,介绍了具体的聚类分析方法,包括分层聚类法（最短距离法、最长距离法和中间距离法、分割聚类算法（PAM算法、CLARA算法、基于密度的方法、基于网格的方法和基于模型的方法.三、数据挖掘在超市中的应用在这部分以某一超市为例,以数据挖掘的过程为线索,对这个超市的销售数据用聚类分析法中的层次法进行了数据挖掘;其次,对数据挖掘的结果进行了描述;最后,分析了数据挖掘的结果.
2.期刊论文陈学进.CHENXue-jin数据挖掘中聚类分析的研究-计算机技术与发展2006,16（9
聚类分析是由若干个模式组成的,它在数据挖掘中的地位越来越重要.文中阐述了数据挖掘中聚类分析的概念、方法及应用,并通过引用一个用客户交易数据统计出每个客户的交易情况的例子,根据客户行为进行聚类.通过数据挖掘聚类分析,可以及时了解经营状况、资金情况、利润情况、客户群分布等重要的信息.对客户状态、交易行为、自然属性和其他信息进行综合分析,细分客户群,确定核心客户.采用不同的聚类方法,对于相同的记录集合可能有不同的划分结果对其进行关联分析,可为协助各种有效的方案,开展针对性的服务.
3.学位论文席景科数据挖掘中聚类分析的研究与实现2003
该文首先概述了数据挖掘的概念、分类和数据挖掘过程;其次,介绍了聚类分析的定义,对聚类分析算法进行了系统地归纳和总结,并简要介绍了每一种代表性算法的实现思想及其优点和不足;然后,重点讨论了k-prototypes算法——一种能对数值型和分类型混合属性数据集进行聚类的算法,在此基础上,提出了基于k-prototypes算法的改进算法,并使用实验室数据集对改进算法进行了测试,证明新算法是有效的;最后,根据目前的研究状况,提出了聚类分析技术需要进一步的研究方向.
4.学位论文周东华数据挖掘中聚类分析的研究与应用2006
数据挖掘是目前信息领域和数据库技术的前沿研究课题,被公认为是最具发展前景的关键技术之一。
数据挖掘涉及到统计学、人工智能（特
升级会员 