K-Means（二）初始质心的选择

回顾：

通过第一讲，我们已经知道了关于最优k值的选择，可以用SSE（组内差）和轮廓系数。

K值的选择

        1.先验知识

        2.SSE

        3.轮廓系数

---

现在介绍一下初始质心的选择：

        1.随机选择

        选择初始质心，我们可以用最基本的随机方法，但是这种方法会导致一个局部最优解问题。即，将一个比较大的簇分裂，同时将两个较小的簇进行合并。

        由于K-Means算法具有不稳定性，初始质心选择不同，结果也不同。所以解决局部最优的方法，其一可以多次运行算法，选择具有最小SSE值的那组作为最终解。这种方法通过多次运行，通过尝试，来解决随机选择初始质心问题。

        不过可以通过以下其他方法来寻找比较好的初始质心。

        2.层次聚类

        通过层次聚类，划分k个层次，计算出每个簇对应的质心作为K-Means算法的初始质心。这种方法可以很好地解决初始质心指派不合理的问题。但是也有局限性。

        3.K-Means++

        K-Means++算法是基本算法的改进版，其区别就在于初始质心的选择。

        该算法第一个质心是随机选择的，接下来的质心基于样本点与最近质心的距离，距离越大越可能被选为下一个质心，直到选择完k个质心。

        该方法有效地解决了关于初始质心的选取问题，目前已经成为了一种硬聚类算法的标准。但是该方法无法解决离群点问题。

        4.基于最近邻密度

        该方法通过检测样本点的样本密度和与之前质心的分散度来决定下一个质心。