EM算法与K_Means算法比较VIP免费

©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net计算机与现代化2007年第9期JISUANJIYUXIANDAIHUA总第145期文章编号:100622475(2007)0920012203收稿日期:2006209204作者简介:黄颖(19812),女,江西万载人,江西理工大学信息工程学院硕士研究生,研究方向:数据仓库与数据挖掘;李伟(19802),男,江西赣州人,讲师,硕士研究生,研究方向:遗传算法,演化硬件。EM算法与K2Means算法比较黄颖,李伟(江西理工大学信息工程学院,江西赣州341000)摘要:聚类是广泛应用的基本数据挖掘方法之一,它按照数据的相似性和差异性将数据分为若干簇,并使得同簇的尽量相似,不同簇的尽量相异。目前存在大量的聚类算法,本文仅考察了划分方法中的两个常用算法:EM算法和K2Means算法,并重点剖析了EM算法,对实验结果进行了分析。最后对算法进行了总结与讨论。关键词:聚类;K2Means算法;EM算法中图分类号:TP301.6文献标识码:AComparisonofEMandK2MeansAlgorithmsHUANGYing,LIWei(FacultyofInformationEngineering,JiangxiUniversityofScienceandTechnology,Ganzhou341000,China)Abstract:Clusteringisoneofbasicdataminingforms,itdividesdatatomanyclustersaccordingtothesimilarityanddissimilari2tybetweenthedata.Andthedatainoneclusteraremoresimilarthanothers.Therearemanyclusteringalgorithms,thispaperonlyintroducestwocommonclusteringalgorithms:EMalgorithmandK2Meansalgorithm,emphasizesEMalgorithm,andatlast,discussestheresultofthealgorithmanddrawsaconclusion.Keywords:clustering;K2Meansalgorithm;EMalgorithm0引言聚类(clustering)是数据挖掘最常用的方法之一,它是计算机对数据进行自动组织的方法。它按照数据的相似性和差异性将数据分为若干组,并使得同组的尽量相似,不同组的尽量相异。聚类是一种无监督学习,完全由计算机自动进行而不需要人工干预。目前存在大量的聚类算法。算法的选择取决于数据的类型、聚类的目的和应用。大体上,主要的聚类算法可以划分为如下几类:划分方法(partitioningmethod)、层次的方法(hierarchicalmethod)、基于密度的方法(density2basedmethod)、基于网格的方法(grid2basedmethod)和基于模型的方法(model2basedmethod)。本文考察了划分方法中的两个常用算法:K2Means算法和EM算法。1K2Means算法K2Means算法是最著名与最常用的划分方法。K2Means以k为参数,把n个对象分为k个簇,以使簇内具有较高的相似度,而簇间的相似度较低。相似度的计算根据一个簇中对象的平均值(被看作簇的重心)来进行。K2Means算法的处理流程如下。首先,随机地选择k个对象,每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象,根据其与各个簇中心的距离,把它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复,直到准则函数收敛。通常,采用平方误差准则,其定义如下:E=∑ki=1∑p∈Ci|p-mi|2这里的E是数据库中所有对象的平方误差的总和,p是空间中的点,表示给定的数据对象,m是簇Ci的平均值(p和mi都是多维的)。这个准则试图使生成的结果簇尽可能地紧凑和独立。这个算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的,而簇与簇之间的区别明显时,它的效果好。对处理大数据集,该算法是相对可伸缩和高效率的,因为它的复杂度是O(nkt),其中,n是所有对象的数目,k是簇的数目,t是迭代的©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net2007年第9期黄颖等:EM算法与K2Means算法比较13次数。通常地,k<