第10.5节 Kmeans++聚类算法
各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！
10.5 -means++聚类算法 10.5.1 算法原理 10.5.2 计算示例 10.5.3 从零实现-means++聚类算法 10.5.4 小结 引用
10.5 -means++聚类算法
在前面几节内容中，笔者介绍了什么是聚类算法，并且还介绍了聚类算法中应用最为广泛的-means聚类算法。从-means聚类算法的原理可知，-means在正式聚类之前首先需要完成的就是初始化个簇中心。同时，也正是因为这个原因使-means聚类算法存在着一个巨大的缺陷——收敛情况严重依赖于簇中心的初始化状况。试想一下，如果在初始化过程中很不巧地将个（或大多数）簇中心都初始化到同一个簇中，则在这种情况下-means聚类算法很大程度上都不会收敛到全局最优解。也就是说，当簇中心初始化的位置不合适时，聚类结果将会出现严重错误。
如图10-4所示的聚类过程仍旧是通过-means聚类算法在10.2节中所用到的人造数据集上得到的聚类结果。只不过不同的是在进行聚类时人为地将3个簇中心初始化到同一个簇中了。在图10-4中，iter=0表示未开始聚类前根据每个样本的真实簇标签所展示的结果，其中蓝色、绿色和橙色分别表示3个簇的分布情况，而3个黑色圆点为初始化的簇中心。从图10-4中可以发现，-means在进行完第10次迭代后，将最上面的1个簇划分为了2个簇，将下面的2个簇划分成了1个簇。同时，当进行完第30次迭代后，可以发现算法已经开始收敛，但后续簇中心却没有发生任何变化，因此最终的结果仍旧是将上面1个簇分为2个簇，将下面的2个簇划分为1个簇。
通过上面这个例子可以知道，初始簇中心的位置会严重影响-means聚类算法的最终结果。对于这种情况，该怎样在最大程度上避免？此时就要轮到-means++算法登场了。
10.5.1 算法原理
-means++[1]仅从名字也可以看出它是-means聚类算法的改进版。不过，它又在哪些地方对-means进行了改进呢？一言以蔽之，-means++算法仅仅在初始化簇中心的方式上做了改进，其他地方同-means聚类算法一样。将-means++在初始化簇中心时的方法总结成一句话就是：逐个选取k个簇中心，并且离其他簇中心越远的样本点越有可能被选为下一个簇中心。其具体做法如下：
(1) 从数据集中随机（均匀分布）选取一个样本点作为第1个初始聚类中心。
(2) 接着计算每个样本点与当前已有聚类中心之间的最短距离，并用表示，然后计算每个样本点被选为下一个聚类中心的概率，并选择最大概率值所对应的样本点作为下一个簇中心。
(3) 重复第(2)步，直到选择出k个聚类中心。
从式(10.7)可以看出，整个选择过程是先计算每个样本到各个簇的最小距离，然后选择所有最小距离中的最大距离，即先求最小化再求最大化，有点类似于SVM中的思想。同时，在实际计算时并不用计算这个概率，因为分母为一个常数。只需计算这个距离，即距离现有簇中心越远的样本点，越可能被选为下一个簇中心。
10.5.2 计算示例
在上面的内容中，笔者已经介绍了-means++聚类算法在初始化簇中心时的具体步骤。不过,为了能够使读者理解得更加清楚，下面笔者就通过一个例子来实际演示一下簇中心的选择过程。
图10-5显示了一个人为制作的模拟数据集。可以很明显地看出该数据集一共包含3个簇，这就意味着在聚类之前需要初始化3个簇中心。现在假设-means++算法第1步选择的是将7号样本点(1,2)作为第1个初始聚类中心，那么在进行第2个簇中心的查找时就需要计算所有样本点到7号样本点的距离。
根据计算可得到7号样本点到其他所有样本点的距离，如表10-1所示。
从表10-1中的结果可以看出，离7号样本点最远的是2号和12号样本点（当然从图10-5中也可以看出），因此-means++就会选择2号（也可以是12号）样本点为下一个聚类中心。接着，再次重复步骤(2)又可以得到如表10-2所示的结果。
从表10-2中的结果可以看出，同时离2号和7号样本点最远的是12号样本点，所以-means++算法选择的下一个簇中心为12号样本点。进一步，可以得到如图10-6所示的可视化结果。
为你认可的知识付费，欢迎订阅本专栏阅读更多优质内容！
从图10-6可以看出，-means++算法在每次选择簇中心时，离当前已有簇中心越远的样本点越可能被选中，即作为下一个簇中心，从而避免所有簇中心出现在同一个簇中的情况。