Question

K-Means原理总结

Answer 1

    K-means是聚类中的一个经典方法。其中的原理和思想实在是巧妙到爆炸💥。接下来让我来给大家展示来自1967年的算法的智慧。

问题引出：如下图所示，我们想要自动的聚类，肉眼一看是5类。那么我们随机生成5个点，它们最终将会成为聚类后每个类的中心点。由于是随机初始化的5个点，所以它们的位置刚开始大概率不在每个类的中心点上，不过没关系，我们可以慢慢调整。

过程描述：如上图所示生成的5个点，它们最终会成为每个类的中心点，此时此刻，每个点有着自己的领域范围。比如最上面的那个点1，它想要成为一个类的中心点，这个类此时此刻都包含哪些点呢，答案当然是到它的距离比到其他中心点距离更近的所有样本点。那么接下来，哪些点符合条件呢?由于每个中心点它都想要控制尽可能多的点，并且得合理。那最上面那个中心点1想要控制位于它自己下面的一些样本点，会有哪些中心点在跟它竞争呢? 答案是中间左右两个点2和3，注意最下面两个中心点4和5参与不到竞争了。所以我们做出两条垂直平分线a,b。a是连线点1，2的垂直平分线，b是连线点1，3的垂直平分线。垂直平分线有什么性质啊? 位于线上的点到两端的距离相等，位于线一侧的点到该侧端点距离更小。所以！位于垂直平分线a,b上面的所有样本点暂时归中心点的领域，注意此时点1并未是该领域样本点的中心，我们应该更新点1的位置，把它挪到领域的中心。因为三角形三条边的垂直平分线会交于一点（先画出两条交于一点，再从该点向另一个边做垂线，证明该垂线与边的交点为中点即可）所以5个中心点互相竞争划分领域会呈现出如上并不杂乱的界限。我们更新5个中心点的位置，再次重新竞争领域，再更新位置。。。直到中心点的位置不动了，聚类完毕。

        原理中一直贯穿着中心的概念，这就是means的含义。接下来我们来分析一下K-means的优缺点。

            1.对分布类似球型的数据效果很好。为什么？试想长条带状的末端有一小簇。

.............................................           。

.............................................           。

如果刚开始随机的中心点一左一右刚刚好，开始竞争，显然...这些右侧的..离。。。的中心点更近，按规则应该归它领域，然后再更新。这样就不符合人的直觉了。

            2.收敛的很快，中心点更新个几次后就不咋动了。

            3.相对高效并且易估计复杂度O(k·t·n)，t是迭代次数一般几次就可以完成，k是中心点个数，簇的个数，不会很大。n是数据点的个数，可能会很大。

        1.K值不好估计，不能预先去判断。

        2.可能会因为初始点随机的不好，会收敛到一个奇怪的结果。如下图。