k均值(k-means)是聚类算法的一种,聚类分析是根据在数据中发现的描述对象及其关系的信息,将数据对象分组。其目标是,组内的对象相互之间是相似的,而不同组中的对象是不同的。组内的相似性越大,组间差别越大,聚类就越好。
举个例子,在二维平面上有几百个点,在笛卡儿坐标系中有(x,y)坐标,把它们点到纸上,问题是如何把它们分成不同组,每个组里点彼此之前都比较相近,而离其它组的成员又比较远。下面介绍的k均值就能干这种事。
基本k均值
基本k均值思想很简单,首先,选择k个初始质心,其中k是用户指定的参数,即所期望的簇的个数。每个点被指派到最近的质心,而指派到一个质心的点集为一个簇。然后根据指派到簇的点,更新每个簇的质心。重复指派和更新步骤,直到簇不发生变化,或等价的,直到质心不发生变化。
伪代码:
1:指派点到最近的质心。为了将点指派到最近的质心,我们需要邻近性度量来量化所考虑的数据的“最近”的概念。判断两项的相似度,在上篇文章里已经提到过,可以选择一个合适的算法。通常,对欧式空间里的点适用欧几里德距离,对文档用余弦相似性
选择k个点作为初始质心。
repeat
将每个点指派到最近的质心,形成k个簇
重新计算每个簇的质心
util 质心不发生变化
2:质心和目标函数。因为在计算k均值的过程中要迭代计算每个簇的质心,我们用均值来当作一个簇的质心,例如第一个簇有点(1,2) (1,1),(2,1),那么我们就用 ( (1 + 1 + 2) / 3, (2 + 1 + 1) /3 )作为质心(相当于各维数据相加,然后除以这组的点数)。而目标函数是我们用来计算产生n个组的算法效果:当我们产生n个组后,计算每个组的所有点的中心点(各维数据相加,然后除以这组的点数),我们称这个点为质心,然后计算每个组中每个点到这个质心的距离,把这个距离相加得到一个组内的距离之和Sum_1,再把每个组这种距离之后相加,即Sum_1 + Sum_2 + … Sum_n,得到这个总距离和就可以判定这次分组质量的好坏,显然,这个值越小越好。
列下k均值常用的邻近度,质心和目标函数的选择:
- 邻近度函数:曼哈顿距离。质心:中位数。目标函数:最小化对象到其簇质心的距离和
- 邻近度函数:平方欧几里德距离。质心:均值。目标函数:最小化对象到其簇质心的距离的平方和
- 邻近度函数:余弦。质心:均值。最大化对象与其质心的余弦相似度和
- 邻近度函数:Bregman 散度。质心:均值。目标函数:最小化对象到其簇质心的Bregman散度和
选择适当的初始质心是基本k均值的关键步骤。常见的方法是随机地选取初始质心,但是簇地质量会比较差。一个方法是多次运行,每次适用一组不同的随机初始质心,然后选取具有最小目标函数和的簇集。但是这样也只是取得多次运行中较好的,仍然非常依赖开始时质心的位置。
在我的测试数据中,随机产生了100个点,其中每10点给它们一个范围,例如第一组点的横坐标和纵坐标都在10~20之间随机,第二组点的都在40~50之间随机,这样就人为产生了10个簇点。然后适用基本k均值算法,指定k=10,得到的10个簇。如此运行50次。我们期望的结果是分成10个簇后,每个簇有10个点,和我们想的数据相符。但是即使运行50次,得到的也是非常不均匀的,有的簇点有20~30个,有的簇的点只有2,3个,甚至产生了空簇,这说明本来应该在这个簇的点被划到了其它簇。可见对于初始点的指定还是很重要的。
而k均值的变种---二分k均值则对初始化问题不大敏感。
二分k均值
基本思想是:为了得到k个簇,将所有点的集合分裂成两个簇,从这些簇中选取一个继续分裂,如此下去,直到产生k个簇。
伪代码:
初始化簇表,使之包含由所有的点组成的簇。
repeat
从簇表中取出一个簇。
{对选定的簇进行多次二分试验}
for i=1 to 试验次数 do
使用基本k均值,二分选定的簇。
endfor
从二分试验中选择具有最小误差的两个簇。
将这两个簇添加到簇表中。
until 簇表中包含k个簇
比如要分成5个组,第一次分裂产生2个组,然后从这2个组中选一个目标函数产生的误差比较大的,分裂这个组产生2个,这样加上开始那1个就有3个组了,然后再从这3个组里选一个分裂,产生4个组,重复此过程,产生5个组。这算是一中基本求精的思想。二分k均值不太受初始化的困扰,因为它执行了多次二分试验并选取具有最小误差的试验结果,还因为每步只有两个质心。
同样是上面的那组数据,当我使用二分k均值算法时,产生的10个簇正好每个都是10个点,就是和我们预想的簇一样,非常均匀。
优点与缺点
k均值简单并且可以用于各种数据类型,它相当有效,尽管常常多次运行。然后k均值并不适合所有的数据类型。它不能处理非球形簇,不同尺寸和不同密度的簇。对包含离群点(噪声点)的数据进行聚类时,k均值也有问题。
基本k均值和二分k均值的代码,由于比较长就不贴了,通过看上面的伪代码,理解了其思想,代码还是比较容易写出来的。
分享到:
相关推荐
K均值聚类算法首先是聚类算法。K均值算法是一种简单的迭代型聚类算法,采用距离作为相似性指标,从而发现给定数据集中的K个类,且每个类的中心是根据类中所有值的均值得到,每个类用聚类中心来描述。它将相似的对象...
这是先实现k均值算法,再在这个基础上实现约束种子k均值算法。k均值算法有直接调用接口实现,有用代码一步一步实现,训练数据清晰,每一个函数都有解释,是一个学习k均值算法很好的资源。
k均值matlabk均值matlabk均值matlabk均值matlabk均值matlabk均值matlabk均值matlabk均值matlab
用C++实现模式识别中K均值聚类。算法优点: 1、算法采用平均值初始化聚类中心,这样可以更加接近最后的结果,减少迭代次数。 2、算法采用精度为0.000001,使运行结果更为精确。 3、算法对其它数据适应良好。 4、算法...
k-means(k均值)算法的python代码实现,可以显示聚类效果与聚类的迭代次数,初学者使用更方便。
k均值聚类的扩展,带核函数的k均值聚类以及多核k均值聚类
K均值算法的简介
本程序为MATLAB程序,适用于用k均值聚类法对数据分类,有数据为例,下载即可使用,可根据自己需要进行修改,效果较好
k均值的matlab代码,生成一批模式,类别数和各的中心点样本可控之后采用改进 K-均值 算法进行聚类,分析结果。本实验采用 MATLAB 编
K均值算法流程图 visio画的 写代码必备
针对现有留一校验法存在剔除异常样本耗时长、误判的缺陷,提出一种K均值改进留一校验法,并将其用于煤质分析中异常样本的检测与剔除。该方法首先利用K均值聚类法对样本进行聚类,得到可疑样本;然后将可疑样本作为验证集...
C语言写的K均值聚类算法,常规款。算法写成类的形式,封装了接口,方便使用。
基于K均值聚类RBF网络程序与实现,有实例
matlab实现K均值分类算法 分类为5 开始的聚类中心为前五个像素 武大遥感学院模式识别作业
模式识别大作业K均值算法matlab平台实现,内有iris数据用于测试一起其他相关资料。
资源名:模式识别_动态聚类_k均值算法_matlab_画图分析_k-means_Clustering 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者...
k均值聚类是最著名的划分聚类算法,由于简洁和效率使得他成为所有聚类算法中最广泛使用的。
k均值聚类是最著名的划分聚类算法,由于简洁和效率使得他成为所有聚类算法中最广泛使用的。给定一个数据点集合和需要的聚类数目k,k由用户指定,k均值算法根据某个距离函数反复把数据分入k个聚类中。
模式识别中k均值聚类的程序及数据:包括初始中心点的选择、新中心点的选择,距离的定义等
利用K均值进行图像分割有图有真相 程序好使