EM算法与K-Means算法比较VIP免费

2007年第9期计算机与现代化JISUANJIYUXIANDAIHUA总第145期文章编号：】006-2475(2007)09．0012_03EM算法与K。Means算法比较黄颖，李伟(江西理工大学信息工程学院．江西赣州341000)摘要：聚类是广泛应用的基本数据挖掘方法之一．它按照数据的相似性和差异性特数据分为若干簇，并使得同簇的尽量相似，不同蔟的尽量相异。目前存在大量的聚类算法．本文但考察了划分方法中的两个常用算法：EM算法和K-MearIs算法，并重点剖析了EM算珐．对实验结果进行了分析。最后对算法进行了总结与讨论。关键词：最类；K—Me鲫s算法；EM算法中图分类号：仰3016文献标识码：AComparisonofEMandK-Mea啮Algoritl腑sHUANGYing，UWei(Facuhyof111⋯natmE“91眦e矗“g，Jia。嶝iuniversi‘yofscience阴dTechnology，Ganzllou341000，china)Abst强ct：Clustedng拓0neofb蚰icdataminingf0邢3，ildjvidesdatatoma“ycIu肚ersacc甜di工lgtotIlesiIIlil面可肌ddis8imil“-tybe¨een暗佗data．AI以theda吨inoneclu咖a工emo她siⅡm吐山an口山e毋．1herearem8卿clu卧e五“gdg瞄山瑚，恤epa”oIllyintroduc朗twDcoInmonclusted“gB190血hm8：EMalgo订thmandK-Mean8algodthm，emph艚izesEMa190dtIIln，arId8tlast，discussesthe耽81lltofthealgodthⅡ1anddrBwsaconclusion．Keyword5：cluste^”g：K-Meansalgod【llm；EMalgodthmO引言聚类(clustering)是数据挖掘最常用的方法之一，它是计算机对数据进行自动组织的方法。它按照数据的相似性和差异性将数据分为若干组，并使得同组的尽量相似，不同组的尽量相异。聚类是一种无监督学习，完全南计算机自动进行而不需要人工干预。目前存在大量的聚类算法。算法的选择取决于数据的类型、聚类的目的和应用。，大体上，主要的聚类算法可以划分为如下几类：划分方法(panitioningmethod)、层次的方法Lhierarchicalmechod)、基于密度的方法(density-b*edmetllod)、基于网格的方法(酣d-basedmet}Iod)和基于模型的方法(model-basedmethod)。本文考察了划分方法中的两个常用算法：K—Mean8算法和EM算法。lK-Means算法K-Means算法是最著名与最常用的划分方法。K—Means以k为参数，把n个对象分为k个簇，以使簇内具有较高的相似度，而簇间的相似度较低。相似度的计算根据一个簇中对象的平均值(被看作簇的重心)来进行。K—Means算法的处理流程如下。首先，随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象，根据其与各个簇中心的距离，把它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。通常，采用平方误差准则，其定义如下：E=∑；。l∑Ⅲ。Ip—m。I2这里的E是数据库中所有对象的平方误差的总和，p是空间中的点，表示给定的数据对象，m是簇c．的平均值(p和m；都是多维的)。这个准则试图使生成的结果簇尽可能地紧凑和独立。这个算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的，而簇与簇之间的区别明显时．它的效果好。对处理大数据集，该算法是相对可伸缩和高效率的，因为它的复杂度是0(nkt)，其中，n是所有对象的数目，k是簇的数目，t是迭代的收稿日期：2006．09．04作者简介：黄颖(1981一)．女．江西万载人，江西理工大学信息工程学院硕士研究生，研究方向：数据仓库与数据挖掘；李伟(1980．)，男，江西赣州人，讲师，硕士研究生，研究方向：遗传算法，演化硬件。万方数据2007年第9期黄颖等：EM算法与K-Me蚰s算法比较13次数。通常地，k<