专栏首页IT技术小咖《Python网络爬虫与数据挖掘小课堂》——part3

《Python网络爬虫与数据挖掘小课堂》——part3

基于Python的K-Means聚类数据分析

摘要:在数据挖掘中,K-Means算法是一种 cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。


来源于维基百科,自由的百科全书的解释:

k-平均算法源于信号处理中的一种向量量化方法,现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-平均聚类的目的是:把n个点(可以是样本的一次观察或一个实例)划分到k个聚类中,使得每个点都属于离他最近的均值(此即聚类中心)对应的聚类,以之作为聚类的标准。这个问题将归结为一个把数据空间划分为Voronoi cells的问题。


在数据挖掘中,K-Means算法是一种cluster analysis的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。

问题

K-Means算法主要解决的问题如下图所示。我们可以看到,在图的左边有一些点,我们用肉眼可以看出来有四个点群,但是我们怎么通过计算机程序找出这几个点群来呢?于是就出现了我们的K-Means算法。

算法概要

这个算法其实很简单,如下图所示:

从上图中,我们可以看到,A,B,C,D,E是五个在图中点。而灰色的点是我们的种子点,也就是我们用来找点群的点。有两个种子点,所以K=2。

然后,K-Means的算法如下:

  1. 随机在图中取K(这里K=2)个种子点。
  2. 然后对图中的所有点求到这K个种子点的距离,假如点Pi离种子点Si最近,那么Pi属于Si点群。(上图中,我们可以看到A,B属于上面的种子点,C,D,E属于下面中部的种子点)
  3. 接下来,我们要移动种子点到属于他的“点群”的中心。(见图上的第三步)
  4. 然后重复第2)和第3)步,直到,种子点没有移动(我们可以看到图中的第四步上面的种子点聚合了A,B,C,下面的种子点聚合了D,E)。

这个算法很简单,但是有些细节我要提一下,求距离的公式我不说了,大家有初中毕业水平的人都应该知道怎么算的。我重点想说一下"求点群中心的算法"。

求点群中心的算法

一般来说,求点群中心点的算法你可以很简的使用各个点的X/Y坐标的平均值。不过,我这里想告诉大家另三个求中心点的的公式:

1)Minkowski Distance公式——λ可以随意取值,可以是负数,也可以是正数,或是无穷大。

2)Euclidean Distance公式——也就是第一个公式λ=2的情况

3)CityBlock Distance公式——也就是第一个公式λ=1的情况

这三个公式的求中心点有一些不一样的地方,我们看下图(对于第一个λ在0-1之间)。

上面这几个图的大意是他们是怎么个逼近中心的,第一个图以星形的方式,第二个图以同心圆的方式,第三个图以菱形的方式。

本文分享自微信公众号 - IT技术小咖(IT-arch),作者:giserway

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • REST微服务的分布式事务实现-使用Spring Cloud的fallback模式

    Fallback是Spring Cloud Netflix框架套件中的Hystrix使用的,用于在出错时候进行的应急措施,我们可以用它来实现在出错的时候来进行回...

    IT技术小咖
  • 前端之 CSS 知识点回顾

    <p>标签内的文字的颜色是red,优先级相等的时候与文件中样式定义的先后顺序有关,即是后面的覆盖前面的,与在class定义中的先后关系无关。

    IT技术小咖
  • 基于GIS的合肥市BRT和Metro的交通可达性研究-part4

    看完《基于GIS的合肥市BRT和Metro的交通可达性研究》part1、part2、part3……系列文章,紧接着往下看......

    IT技术小咖
  • 视频 | 硅谷深度学习网红传授超参数优化宝典

    AI 研习社按:今天为大家带来硅谷深度学习网红 Siraj 在人工智能在线大会 AI WITH THE BEST(AIWTB)上的演讲,雷锋字幕组独家译制。本次...

    AI研习社
  • 数据挖掘:K-Means 算法

    最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问...

    机器学习AI算法工程
  • AlphaGo背后的秘密——深度增强学习(DRL)前沿算法解析

    用户1737318
  • 洗牌算法及 random 中 shuffle 方法和 sample 方法浅析

    游戏开始的时候需要随机布雷。扫雷的高级是 16 × 30 的网格,一共有 99 个雷。如果从 0 开始给所有网格做标记,那么布雷的问题就成了从 480 个数中随...

    丹枫无迹
  • 纸牌游戏中的洗牌是如何实现的?

    对于算法书买了一本又一本却没一本读完超过 10%,Leetcode 刷题从来没坚持超过 3 天的我来说,算法能力真的是渣渣。但是,今天决定写一篇跟算法有关的文章...

    数据森麟
  • EDA算法探究--20世纪10个影响最大的算法在EDA领域的应用

    21世纪初,科研人员总结了上个世纪对工业界影响最大的10个算法,其中大多数算法都在EDA领域有重要应用。我们今天来看一下,这10大算法,你在大学期间学过哪些?在...

    网络交换FPGA
  • 不懂算法,还想进大厂?做梦吧

    拿到题目后就开始想着怎么写代码,结果写了大半天,发现越写越乱,最后就写不下去了,又或者是,看到题目后,一脸懵逼,完全不知道怎么下手。

    Java团长

扫码关注云+社区

领取腾讯云代金券