首页 > 代码库 > 聚类分析之K-meas算法

聚类分析之K-meas算法

K-means算法

一般情况,聚类算法可以划分为以下几类:划分方法(partitioning method)、层次方法(hierarchical methods)、基于密度的方法(density-based methods)、基于网格的方法(grid-based methods)、基于模型的方法(model-based methods.k-means算法属于划分方法中的一种。 K-means算法是将样本聚类成k个簇(cluster),具体算法描述如下:


K是我们事先给定的聚类数,clip_image012[6]代表样例i与k个类中距离最近的那个类,clip_image012[7]的值是1到k中的一个。质心clip_image014[6]代表我们对属于同一个类的样本中心点的猜测,拿星团模型来解释就是要将所有的星星聚成k个星团,首先随机选取k个宇宙中的点(或者k个星星)作为k个星团的质心,然后第一步对于每一个星星计算其到k个质心中每一个的距离,然后选取距离最近的那个星团作为clip_image012[8],这样经过第一步每一个星星都有了所属的星团;第二步对于每一个星团,重新计算它的质心clip_image014[7](对里面所有的星星坐标求平均)。重复迭代第一步和第二步直到质心不变或者变化很小。

K-means算法的整个流程:首先从聚类对象中随机选出K个对象作为类簇的质心(当然了,初始参数的K代表聚类结果的类簇数),对剩余的每个对象,根据它们分别到这个K个质心的距离,将它们指定到最相似的簇(因为K-means是利用距离来量化相似度的,所以我们这里可以理解为是“将它们指定到离最近最近距离的质心所属类簇”)。然后重新计算质心位置。以上过程不断反复,直到准则函数收敛为止。

K-means的优点和不足:能处理大型数据集,结果簇相当紧凑,并且簇和簇之间明显分离。但是

1)该算法必须事先给定类簇数和质点,簇数和质点的初始值设定往往会对聚类的算法影响较大。

2 ) 通常会在获得一个局部最优值时停止,

3 ) 并且只适合对数值型数据聚类,

4) 只适用于聚类结果为凸形的数据集,K-means方法不适合发现非凸面形状的类簇,或者大小差别很大的簇。

5) 噪音和孤立点数据敏感,少量的该类数据对质点的计算会产生极大的影响。

关于K-means的代码实现网上有很多,可自行查阅。

聚类分析之K-meas算法