k均值聚类中的EM思想.docx

1均值聚类中的思想马丽娜西安财经学院行知学院信息系陕西西安摘要在无监督学习中均值聚类以其快速简单的特点得到了广泛的应用算法是针对缺失数据的一种统计学习方法然而均值和这两种不同领域的算法在思想上却有着一致的地方本文分析了均值中蕴含的思想指出了均值中样本隶属度更新和类中心更新与算法中的步和步的等价性最后利用语言矩阵化运算的特点介绍在如何在语言中高效地实现均值聚类算法关键词均值算法聚类分析2作者简介马丽娜女汉族研究生西安财经学院行知学院教师研究方向为应用概率统计引言在数据分析中根据数据集中有无某些已知类别的样本可以分为监督学习和无监督学习两种无监督学习是最常见的一种统计学习模式又称为聚类分析已经在文本挖掘遥感图像生物医学社交网络安全检测等领域得到了广泛的应用目前已经有许多成熟的聚类方法像均值聚类支持向量机层次聚类基于密度的聚类等均值算法以其简洁高效的特性是最受关注的聚类方法之一最大期望值算法算法是针对缺失数据的一种统计学习理论常常被用来求在含有不完整观测的数据集下的极大似然估计本文分析了均值聚类和算法思想上的相通之处指出了两种方法迭代过程的等价性相关理论知识均值聚类均值算法中的输入变量为类个数和样本矩阵其中中存有参与聚类的个样本算法的目标是将个数据对象划分为个类以3便使得所获得的个子类满足同一子类中的对象相似度较高而不同子类中的对象相似度较小均值算法基本步骤如下从个样本中任意选择个对象作为初始类中心根据每个子类中样本的均值计算每个对象与这些中心样本点的距离并将每个样本分到这样一个子类这个子类的中心是所有个中心点离该样本最近的重新计算每个子类的均值当满足一定收敛条件如类中心不再变化时则算法终止如果条件不满足则回到步骤模糊均值聚类模糊均值聚类是对传统均值聚类的拓展在中样本不再明确地属于或者不属于某一类而是对各个子类有个和之间的隶属度详细算法如下从个样本中任意选择个对象作为初始类中心计算每个对象与这些中心点的距离并根据这些距离值计算样本对各单类的隶属度根据样本的隶属度重新计算每个子类的均值找出中心样本当满足一定收敛条件时则算法终止如果条件不满足则回到步骤可以看出传统均值其实是一种特殊的即限制了隶属度为或改进模糊均值聚类4传统的模糊均值聚类对噪声点敏感这是由于其对隶属度进行了概率归一化的限制使得隶属度是相对的而不是绝对的比如如果有两个点和和均和两个类的距离相等不同的是到两个类中心的距离较小而到两个类中心的距离很大传统的模糊均值不能区分这两种情况的不同都会给和赋予的各类隶属度为此目前有许多针对传统模糊均值聚类的改进算法如噪声模糊均值算法这种算法在原来的各个类的基础上增加了噪声类设定了一个距离阈值当样本到各个类中心的距离都大于时则将该样本归为噪声类算法如下初始化个类中心设定噪声类阈值计算每个对象与这些类中心点的距离并根据这些距离值和阈值计算样本对各单类和噪声类的隶属度根据样本的隶属度重新计算每个子类的均值找出中心样本当满足一定收敛条件时则算法终止如果条件不满足则回到步骤算法在统计计算中模型中常用来计算在带有不完全观测的数据集下参数的最大似然估计为了方便起见我们将数据集分为两部分可直接观测部分和不可观测隐藏部分算法同样经过两个步骤交替进行计算步利用对隐藏变量的当前估计值在观测下的条件期望计算完全对数似然函数5步最大化在步上求得的似然函数来计算参数的值在步上找到的参数估计值将被用于下一个步计算中这个过程不断交替进行直到算法收敛均值和迭代过程的等价性算法的迭代过程类似于爬山的过程在步为基于完全数据的对数观测似然函数确定一个下界函数然后在步极大化这个下界函数接下来就是一个循环往复的过程在算法刚开始的时候给定初始点进行步观测似然函数值并没有提升它只是找到了一个下界函数并且这个函数和对数观测似然函数在初始点的值相等在极大化之后我们再计算期望这时的步才会提升观测似然函数值步是对不可观测的隐藏变量进行猜测这种猜测是在观测样本的基础上进行的即在观测样本和现有参数下求条件期望如果以观测样本和现有的参数为猜测依据那么期望就是最靠谱的猜测所谓的靠谱就是说在现行的参数下目标函数和猜测函数的值相等而且猜测函数在参数为其他值时也不会超过对应的目标函数步保证了这种猜测是目标函数的下界所以步求得的极大值依然没有超过目标函数的最大值在步求得极大值后参数进行了更新所以也要将猜测根据新的参数进行更新可以说下一次迭代的步提升了上一次迭代步的值而这种提升的原因有两点基于上一次步猜测函数的值小于目标函数在进行新的步之后目标函数和新的猜测函数值相同而新的猜测函数同样是目标函数的下界6再来看一下均值的更新过程均值通过更新两种变量来极小化目标函数类中心和隶属度隶属度即类别标签相当于不可观测的隐藏变量而类中心是可观测的在已知观测变量的条件下首先猜样本属于哪一类易知通过将样本分到最近的中心所在的类就可以实现目标函数在现有观测条件下的极小化所谓的条件期望在这里其实就是根据各类几何中心确定类标签或隶属度接下来就要通过极小化的方法来确定类中心因此类中心的更新过程相当于中的步而隶属度更新的过程相当于中的步对于均值聚类来讲刚开始并不知道每个样本对应的隐藏变量即其类别标签刚开始的时候可以对类标签进行一个随机初始化然后在类别已知的情况下极大化目标函数接下来发现会有更好的类标签的指定办法如此往复直到目标函数收敛所以聚类的目标函数相当于中观测对数似然函数的角色对于传统均值聚类来讲隐藏类别的指定方法比较特殊属于非此及彼的硬指派而对于模糊均值聚类类别的指派办法是依赖隶属度的以上的讨论不限于传统均值聚类对其各种改进算法如噪声均值聚类同样适用均值聚类的实现语言是当前最为流利的一种统计分析语言它包含一套完整的数据处理计算和制图软件系统现在已经有成熟的包集成了聚类算法包含均值聚类比如包其中函数提供了均值和模糊均值聚类的功能但是这个函数并没有利用矩阵化7运算的特点这就降低了程序的执行效率语言作为一种解释型编译语言显式循环比较慢是其一个很大的缺点虽然已经有系列的函数来避免显式循环但是在很多情况下还是不能满足需求其实语言的一个显著的优点是支持矩阵化运算如果能用矩阵运算来代替显式循环将会大大提高程序的效率比如在隶属度确定时利用矩阵化运算的思想可以通过矩阵乘积来实现假设样本距离矩阵为则隶属度的计算过程为计算的倒数的次方其中为模糊化因子计算结果记为用除以和维全矩阵的矩阵乘积经过上述两个步骤就得到了各个样本的隶属度同样的可以设计更新样本中心时的矩阵化方法记隶属度矩阵为中心更新算法如下计算的次方和样本矩阵的矩阵乘积计算的次方和维全矩阵的矩阵乘积其中为样本的个数为样本的维数将上面两个步骤得到的矩阵向量相除得到中心矩阵噪声均值聚类算法的隶属度更新可类似进行计算的倒数的次方同样将计算结果记为用除以与维全矩阵的矩阵乘积和的倒数的次方的和增加的噪声类对各个类中心的计算无影响所以中心的更新过程和上8面模糊均值聚类是完全一样的有了隶属度和中心更新的主程序不同均值聚类均可依下流程进行初始化个类中心指定需要的附加参数依如上介绍的隶属度更新算法计算矩阵依如上介绍的中心确定算法计算矩阵判断算法收敛条件如不满足收敛条件返回如满足则算法结束算法的收敛条件可以根据需要设计可以为相邻两次迭代目标函数的值变化不大或相邻两次迭代确定的类中心完全相同为了显示矩阵化后的程序的优势我们以数据集为例用和本文设计的算法分别执行模糊均值聚类将实验以不同的随机初始点重复进行次比较系统运行的时间结果如表所示从上表可以看出矩阵化运算可以使程序的运行时间大大缩短这就极大地提高了算法的效率尤其在海量数据的时代更具有实际应用价值结论本文讨论了均值聚类中包含的思想并指出了两个算法在迭代过程中的等价性均值中样本隶属度更新和类中心更新分别与算法中的步和步的等价两个不同领域的方法在思想上是相通的同时介绍了如何基于矩阵化运算进行均值聚类的程序设计并用9数值实例证明了矩阵化算法可以使程序的执行效率大大提高参考文献任江涛孙婧昊施潇潇等一种用于文本聚类的改进的均值算法计算机应用王易循赵勋杰基于均值聚类分割彩色图像算法的改进计算机应用与软件王兴伟沈兰荪基于改进的均值聚类和数学形态学的彩色眼科图像病灶分割中国生物医学工程学报杨建新周献中葛银茂基于拉普拉斯图谱和均值的多社团发现方法计算机工程胡艳维秦拯张忠志基于模拟退火与均值聚类的入侵检测算法计算机科学汤效琴戴汝源数据挖掘中聚类分析的技术方法微计算机信息王爱平张功营刘方算法研究与应用计算机技术与发展傅德胜周辰基于密度的改进均值算法及实现计算机应用孔锐张国宣施泽生等基于核的均值聚类计算机工程谢志伟王志明基于上下文约束的噪声模糊聚类算法计算机工程与应用10责任编辑汤静