原理

K-Means算法属于基于划分的聚类算法,对N维欧氏空间中的点进行聚类,是一种最简单的无监督学习方法。它通过迭代来实现,其基本思想是:每次确定K个类别中心,然后将各个结点归属到与之距离最近的中心点所在的Cluster,然后将类别中心更新为属于各Cluster的所有样本的均值,反复迭代,直至类别中心不再发生变化或变化小于某阈值。

算法描述

(1)随机生成c个类的初始中心;
(2)在第k次迭代中,对任意一个样本,求其到c各中心的距离,将该样本归到距离最短的那个中心所在的类;
(3)利用均值等方法更新该类的中心值;
(4)对于所有的C个聚类中心,如果利用(2)(3)的迭代法更新后,值保持不变,则迭代结束;否则继续迭代。

不同的初始化k值和中心点的选择有可能引起不同的聚类结果

聚类数k的选取评价方法

1、事前的数据分析,选取合适的k值

2、手肘法

手肘法的核心指标是SSE(误差平方和)。取名的原因是拟合曲线形状和手肘形状相似。

手肘法的核心思想是:随着聚类数k的增大,样本划分会更加精细,每个簇的聚合程度会逐渐提高,那么误差平方和SSE自然会逐渐变小。并且,当k小于真实聚类数时,由于k的增大会大幅增加每个簇的聚合程度,故SSE的下降幅度会很大,而当k到达真实聚类数时,再增加k所得到的聚合程度回报会迅速变小,所以SSE的下降幅度会骤减,然后随着k值的继续增大而趋于平缓,也就是说SSE和k的关系图是一个手肘的形状,而这个肘部对应的k值就是数据的真实聚类数。当然,这也是该方法被称为手肘法的原因。

3、轮廓系数法

轮廓系数的公式为 s = (a-b)/max(a,b)。其中a为当前样本点x与同簇的其他样本的平均距离,称为凝聚度,b为x与最近簇中所有样本的平均距离,称为分离度。顾名思义,最近簇为除了同簇的最近的簇。

求出所有样本的轮廓系数后再求平均值就得到了平均轮廓系数。平均轮廓系数的取值范围为[-1,1],且簇内样本的距离越近,簇间样本距离越远,平均轮廓系数越大,聚类效果越好。

随机点的选取评价方法

1、事前的数据分析,选取合适中心点

2、随机化选择

第一个簇心A随机找;第二个簇心B要找距离A最远的,是因为簇心之间要相距远一些,如果很近的话,很容易当作一类,影响聚类效果;第三个簇心C也是同样的,它得离A、B远一些;如此类推。

时间复杂度

k-means算法的时间复杂度为:
O(mnkd),m为迭代次数。n为数据集中数据样本数量,k为聚类个数,d为数据的维数。