K-Means原理总结

K-Means!

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

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

k-means

过程描述:如上图所示生成的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.可能会因为初始点随机的不好,会收敛到一个奇怪的结果。如下图。


聚类成奇怪的结果
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 总结一些聚类评估方法 和Silhouette。 聚类的效果咱们要有一个指标来评估它聚的到底好不好。 1.第一个...
    325620576492阅读 1,945评论 0 0
  • 散伙饭上,我喝到酩酊大醉,据说那天晚上我从上车回学校就开始哭,直到下车睡醒,还坐在路边死活不肯走耍赖,抱着树吐到干...
    小白不爱吃骨头阅读 249评论 0 0
  • 射手恋爱的三个阶段 文章里包含射手的冷淡期是怎么回事? 第一阶段:热情期 (觉得你哪都好,优点的光芒盖住缺点之时)...
    射手座研究室阅读 40,878评论 5 33
  • 在网络时代,能让人读好几遍的东西,不是很多。 近日,网上看了一篇微小说,被小说中的父亲,戳中了泪点,重复读了。 不...
    宽哥说阅读 416评论 0 0
  • 腾哥 衣服 早起给腾穿了一件新衣服,临出门才发现这衣服上有根绳子,还挺长。于是我跟他商量把绳子剪了。腾果然不同意,...
    疼福妈阅读 272评论 0 0