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