k均值聚类中的em思想

《k均值聚类中的em思想》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、k均值聚类中的EM思想马丽娜（西安财经学院行知学院信息系，陕西西安710038）【摘　要】在无监督学习中，k均值聚类以其快速简单的特点得到了广泛的应用。EM算法是针对缺失数据的一种统计学习方法。然而，k均值和EM这两种不同领域的算法在思想上却有着一致的地方。本文分析了k均值中蕴含的EM思想，指出了k均值中样本隶属度更新和类中心更新与EM算法中的E步和M步的等价性。最后，利用R语言矩阵化运算的特点，介绍在如何在R语言中高效地实现k均值聚类算法。.jyqkpliedink-meansclusteringMALi-na(DepartmentofInformation

2、,XingzhiCollegeofXi’anUniversityofFinanceandEconomics,Xi’anShaanxi710038,China)【Abstract】Inunsupervisedlearning,k-meansclusteringisanyfieldsduetothefactthatitisverysimpleandfast.EMalgorithmisastatisticallearningapproachformissingdata.Althoughthesetethodsareappliedindifferentareas,th

3、eyaresimilarintermsofsomeideas.TheprincipleofEMimpliedink-meansclusteringisanalyzedinthispaper.Theequalitybeteans(theupdateofmembershipandtheupdateofprototypes)andtheEandMstepsinEMalgorithmsispointedout.【Keyeans;EMalgorithm;Clusteringanalysis简介：马丽娜（1986—），女，汉族，研究生，西安财经学院行知学院教师，研究方向为

4、应用概率统计。0　引言在数据分析中，根据数据集中有无某些已知类别的样本，可以分为监督学习和无监督学习两种。无监督学习是最常见的一种统计学习模式，又称为聚类分析，已经在文本挖掘[1]、遥感图像[2]、生物医学[3]、社交网络[4]、安全检测[5]等领域得到了广泛的应用。目前已经有许多成熟的聚类方法，像k均值聚类，支持向量机，层次聚类，基于密度的聚类等[6]。k均值算法以其简洁高效的特性，是最受关注的聚类方法之一。最大期望值算法(EM算法)，是针对缺失数据的一种统计学习理论，常常被用来求在含有不完整观测的数据集下的极大似然估计[7]。本文分析了k均值聚类和EM算法

5、思想上的相通之处，指出了两种方法迭代过程的等价性。1　相关理论知识1.1　k均值聚类k均值算法中的输入变量为类个数k和样本矩阵X。其中X中存有参与聚类的n个样本。算法的目标是将n个数据对象划分为k个类，以便使得所获得的k个子类满足：同一子类中的对象相似度较高；而不同子类中的对象相似度较小。k均值算法基本步骤如下：a）从n个样本中任意选择k个对象作为初始类中心；b）根据每个子类中样本的均值，计算每个对象与这些中心样本点的距离；并将每个样本分到这样一个子类，这个子类的中心是所有k个中心点离该样本最近的；c）重新计算每个子类的均值；d）当满足一定收敛条件(如类中心不

6、再变化)时，则算法终止；如果条件不满足则回到步骤b)。1.2　模糊k均值聚类模糊k均值聚类(FCM)是对传统k均值聚类的拓展。在FCM中，样本不再明确地属于或者不属于某一类，而是对各个子类有个0和1之间的隶属度。详细算法如下：a）从n个样本中任意选择k个对象作为初始类中心；b）计算每个对象与这些中心点的距离；并根据这些距离值计算样本对各单类的隶属度；c）根据样本的隶属度重新计算每个子类的均值(找出中心样本)；d）当满足一定收敛条件时，则算法终止；如果条件不满足则回到步骤b)。可以看出传统k均值其实是一种特殊的FCM，即限制了隶属度为0或1。1.3　改进模糊k均

7、值聚类传统的模糊k均值聚类对噪声点敏感。这是由于其对隶属度进行了概率归一化的限制，使得隶属度是相对的，而不是绝对的。比如，如果有两个点A和B，A和B均和两个类的距离相等。不同的是，A到两个类中心的距离较小，而B到两个类中心的距离很大。传统的模糊k均值不能区分这两种情况的不同，都会给A和B赋予0.5的各类隶属度。为此，目前有许多针对传统模糊k均值聚类的改进算法([8,9])，如噪声模糊k均值算法([10])。这种算法在原来的各个类的基础上，增加了噪声类。设定了一个距离阈值t，当样本到各个类中心的距离都大于t时，则将该样本归为噪声类，算法如下。a）初始化k个类中心

8、，设定噪声类阈值t；b）计算每个对象与