KMeans

K-means 算法

1. 从样本数据中随机抉择 $K$ 个样本作为初始聚类核心 $C=\{c_1,\cdots,c_K\}$；
2. 针对样本数据中的每一个样本 $x_i$，计算它到每一个聚类核心的间隔 $d(x_i,c_k)=||x_i-c_k||_2$，并将该样本分到间隔最小的聚类核心所对应的的类中；
3. 针对每一个类别 $Y_k$，从新计算它对应的聚类核心 $c_k=\frac{1}{|D_k|}\sum_{x\in D_{k}}$，其中 $D_k$ 示意属于第 $k$ 个簇的所有样本；
4. 反复步骤 2 和步骤 3，直到聚类核心的地位不再发生变化。

因而，对于 K -means 而言，最终心愿每一个簇的簇内平方和 (cluster sum of square，又称为 inertia) 最小 $\sum_{x\in D_k}||x-c_k||_2$，对所有簇的簇内平方和相加失去整体平方和 (total cluster sum of square，又称为 total inertia)$\sum_{k=1}^K\sum_{x\in D_k}||x-c_k||_2$。即心愿 簇内差别小，簇间差别大。

聚类核心的个数

K-means 算法聚类核心的个数是须要人为设定的，可采纳的做法是别离选定不同数目的聚类核心个数，运行 K -means 算法，比拟得分。

elbow method

elbow 办法失去的图像，横坐标为聚类核心的个数，纵坐标为掂量 K -means 算法的评估指标，个别为 total interia。失去的图像相似于肘关节，因而得名。抉择“拐点”对应的聚类核心数，作为最优的聚类核心数。

轮廓系数

轮廓系数 Silhouette coefficient 可能同时掂量

1. 样本与其本身所在的簇中的其余样本的类似度 a，应用样本与同一簇中所有其余点之间的均匀间隔来掂量；
2. 样本与其余簇中的样本的类似度 b，应用样本与下一个最近的簇中的所有点之间的均匀间隔来掂量。

依据“簇内差别小，簇间差别大”的需要，咱们心愿 b 尽可能大于 a。样本的轮廓系数为 $\frac{(b – a)}{max(a, b)}$。轮廓系数的取值为(-1,1)，值越靠近 1 示意样本与其所在的簇中的样本类似，与其它簇的样本不类似，如果轮廓系数为负，则表明样本与簇外的样本更类似。

但其实这两种办法都不是相对的，很多时候往往要联合业务剖析。

情景一

情景二

情景三

K-means 比拟适宜解决簇间没有重叠的聚类问题。

初始聚类核心的抉择

K-means 中的一个重要环节是如何抉择初始聚类核心，初始聚类核心的抉择影响到算法是否收敛到最优值以及收敛的速度。K-means 算法抉择初始聚类核心的形式是随机的，Arthur、David Sergei 和 Vassilvitskii 提出了 K -means++ 算法，K-means++ 对 K -means 做了改良，次要是对初始聚类核心的抉择形式做了改良，其基本思路是：不再应用随机初始化的形式抉择初始聚类核心，而是心愿初始聚类核心之间的互相间隔要尽可能的远。
具体的做法是，

1. 从样本数据中随机选取一个样本作为初始聚类核心 $c_1$；
2. 首先，计算每一个样本与以后 已有的聚类核心 的最短距离（即该样本到离他最近的聚类核心的间隔），记做 $D(x)$。接着计算每一个样本点被选为下一个初始聚类核心的概率 $\frac{D(x)^2}{\sum_{x^{‘}\in X}D(x^{‘})^2}$。最初，依照 轮盘法 选出下一个初始聚类核心；
3. 反复步骤 2，直到抉择出 $K$ 个初始聚类核心。之后依照 K -means 算法进行聚类。

scikit-learn 中，sklearn.cluster.KMeans的参数 init，用来抉择随机初始化(init=’random’) 和应用 Kmean++ 初始化(init=’k-means++’)。

参考

1. 比 elbow 办法更好的聚类评估指标
2. https://live.bilibili.com/125…