11.5 Kmeans++聚类算法#
在前面几节内容中，我们介绍了什么是聚类算法，并且还介绍了聚类算法中应用最为广泛的Kmeans聚类算法。从Kmeans聚类算法的原理可知，Kmeans在正式聚类之前首先需要完成的就是初始化K个簇中心。同时，也正是因为这个原因使Kmeans聚类算法存在着一个巨大的缺陷——收敛情况严重依赖于簇中心的初始化状况。试想一下，如果在初始化过程中很不巧地将K个（或大多数）簇中心都初始化到同一个簇中，则在这种情况下Kmeans聚类算法很大程度上都不会收敛到全局最优解。也就是说，当簇中心初始化的位置不合适时，聚类结果将会出现严重错误。在本节内容中我们将介绍一种基于Kmeans聚类算法改进而来的Kmeans++聚类算法，其学习路线如图11-6所示。
11.5.1 Kmeans++算法思想#
如图11-7所示的聚类过程仍旧是通过Kmeans聚类算法在11.2节中所用到的人造数据集上得到的聚类结果。只不过不同的是在进行聚类时人为地将3个簇中心初始化到同一个簇中了。在图11-7中，iter=0表示未开始聚类前根据每个样本的真实簇标签所展示的结果，其中蓝色、绿色和橙色分别表示3个簇的分布情况，而3个黑色圆点为初始化的簇中心。从图11-7中可以发现，Kmeans在进行完第10次迭代后，将最上面的1个簇划分为了2个簇，将下面的2个簇划分成了1个簇。同时，当进行完第30次迭代后，可以发现算法已经开始收敛，但后续簇中心却没有发生任何变化，因此最终的结果仍旧是将上面1个簇分为2个簇，将下面的2个簇划分为1个簇。
通过上面这个例子可以知道，初始簇中心的位置会严重影响Kmeans聚类算法的最终结果。对于这种情况，该怎样在最大程度上避免呢？此时就要轮到Kmeans++算法出场了。
从整体上看Kmeans++聚类算法同Kmeans聚类算法一致，唯一的区别在于初始簇中心的选择上。在Kmeans++聚类算法中，对于初始簇中心的选择是逐一进行的，并且每次在选择当前簇中心时都会选择离已有簇中心尽可能远的样本的作为簇中心，以此来避免所有簇中心出现在同一个簇中的情况。同时，在sklearn中只需要在实例化时指定对应的初始化方法，即KMeans(n_clusters=K,init='k-means++')，便可使用Kmeans++聚类算法，使用示例这里就不再赘述。
11.5.2 Kmeans++算法原理#
Kmeans++[1]仅从名字也可以看出它是Kmeans聚类算法的改进版。一言以蔽之，Kmeans++算法仅仅在初始化簇中心的方式上做了改进，其他地方同Kmeans聚类算法一样。将Kmeans++在初始化簇中心时的方法总结成一句话就是： 逐个选取K个簇中心，并且离其他簇中心越远的样本点越有可能被选为下一个簇中心。其具体做法如下：
(1) 从数据集$X$中随机（均匀分布）选取一个样本点作为第1个初始聚类中心$c_1$。
(2) 接着计算每个样本点$x\in X$与当前已有聚类中心之间的最短距离，并用$D(x)$表示，然后计算每个样本点${{x}^{\prime }}\in X$被选为下一个聚类中心的概率，并选择最大概率值所对应的样本点作为下一个簇中心$c_i$。
$$ {{c}_{i}}=\underset{{{x}^{\prime }}}{\mathop{\arg \max }}\,\frac{D{{({{x}^{\prime }})}^{2}}}{\sum\limits_{x\in X}{D}{{(x)}^{2}}}\tag{11-6} $$