k-means++算法：针对K-means算法缺点的针对性改进版本
在上一篇中我们对k-means算法进行了简单地介绍，明确了k-means算法的优缺点，本章我们将介绍k-means算法的改进版本——k-means++算法，该算法是为解决k-means分类结果会受到初始点的选取而存在区别而提出的。
k-means++算法仅对k-means算法的初始点选择部分进行改进，改进后算法的初始质心选择思路为：
- 初始聚类中心之间的相互距离要尽可能的远；
- 假设已经选取了n个初始聚类中心（n < k），则在选取第 n+1 个聚类中心时，距离当前 n 个聚类中心越远的点会有更高的概率被选为第 n+1 个聚类中心
k-means++算法的步骤如下：
- 随机选择一个样本作为第一个聚类中心 c1;
- 计算每个样本与当前已有聚类中心的最短距离（即与最近一个聚类中心的距离），用 D（x）表示，这个值越大，表示被选取作为聚类中心的概率就越大；
k-means聚类算法的两个难点：
- 确定 k 值得大小
k 值的确定
样本聚类误差平方和，核心指标是SSE(Sum of the squared errors, 误差平方和)
其中，K是聚类数量，p是样本， 是第 k 个聚类的中心点，K越大，SSE越小，说明样本聚合程度越高。
当 k小于真实聚类数时，由于 k 的增大会大幅度增加每个簇的聚类程度，故SSE的下降幅度会增大，而当 k 到达真实聚类数时，再增加 k 所得到的聚类程度回报会迅速变小，所以 SSE 的下降幅度会骤减，然后随着 k 值得继续增大而趋于平缓，这个最先趋于平缓的点就是合适的 K 值。
2. 如何选择 k 个初始聚类中心
初始类簇中心点的确定
（1）选择批次距离尽可能远的 k 个点
首先，随机选择一个点作为第一个类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点，以此类推，直至选出 k 个初始类簇中心点。
（2）选用层次聚类或者Canopy算法进行初始聚类，然后利用这些类簇的中心点作为 k-means算法初始类簇中心点
参考：