用 sklearn 对 140W 个点进行 kmeans 基于密度聚类划分

任务需求:现有140w个某地区的ip和经纬度的对应表,根据每个ip的/24块进行初步划分,再在每个区域越100-200个点进行细致聚类划分由于k值未知,采用密度的Mean Shift聚类方式。

0#目录:

  • 原理部分
  • 框架资源
  • 实践操作
  • 效果展示

 

1#原理部分

关于kmeans纯代码实现可以移步之前的一篇

机器学习-聚类算法-k-均值聚类-python详解

 

在文中已经对代码做了详细的注释。

介绍

K-means算法是是最经典的聚类算法之一,它的优美简单、快速高效被广泛使用。它是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。

图示

步骤

  1. 从N个点随机选取K个点作为质心
  2. 对剩余的每个点测量其到每个质心的距离,并把它归到最近的质心的类
  3. 重新计算已经得到的各个类的质心
  4. 迭代2~3步直至新的质心与原质心相等或小于指定阈值,算法结束

优点

  1. k-平均算法是解决聚类问题的一种经典算法,算法简单、快速。
  2. 对处理大数据集,该算法是相对可伸缩的和高效率的,因为它的复杂度大约是O(nkt),其中n是所有对象的数目,k是簇的数目,t是迭代的次数。通常k<<n。这个算法经常以局部最优结束。
  3. 算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的,而簇与簇之间区别明显时,它的聚类效果很好。

缺点

  1. K 是事先给定的,这个 K 值的选定是非常难以估计的;
  2. 对初值敏感,对于不同的初始值,可能会导致不同的聚类结果。一旦初始值选择的不好,可能无法得到有效的聚类结果;
  3. 该算法需要不断地进行样本分类调整,不断地计算调整后的新的聚类中心,因此当数据量非常大时,算法的时间开销是非常大的。
  4. 不适合于发现非凸面形状的簇,或者大小差别很大的簇;
  5. 对于”噪声”和孤立点数据敏感,少量的该类数据能够对平均值产生极大影响。

关于K值的确定主要在于判定聚合程度:提供几篇论文注意,这些论文仅仅是提供思路,不要去自己写出来,内容有点扯

快速查找最优初始聚类数K的改进K_means算法   Kmeans聚类分析算法中一个新的确定聚类个数有效性的指标_李双虎.pdf   简单有效的确定聚类数目算法_张忠平.pdf

 

2#框架资源

本次基于密度的kmeans算法使用的是 scikit-learn 框架。

官网:http://scikit-learn.org/stable/index.html

聚类算法汇总:http://scikit-learn.org/stable/modules/clustering.html

KMeans算法 : http://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_assumptions.html#sphx-glr-auto-examples-cluster-plot-kmeans-assumptions-py

MeanShift算法: http://scikit-learn.org/stable/modules/generated/sklearn.cluster.MeanShift.html#sklearn.cluster.MeanShift

meanShift 测试demo:http://scikit-learn.org/stable/auto_examples/cluster/plot_mean_shift.html#sphx-glr-auto-examples-cluster-plot-mean-shift-py

安装框架环境:http://scikit-learn.org/stable/install.html

测试数据集合下载:data  数据比较小,百来个经纬度的点

 

3#实践操作

3.1:运用 Kmeans  使用2-6作为k值评定聚类效果

。请先下载上文中的数据集合,和测试代码放在同一目录下,确保下列运作环境已经安装完成:

 完整运行代码:请结合官方文档,可以理解运行的参数和返回值

 

效果截图如下:

2016-10-21-10-53-29%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be 2016-10-21-10-53-13%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be 2016-10-21-10-53-02%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be 2016-10-21-10-52-53%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be

 

3.1:使用MeanShift自动生成k值删除游离点

注意此部分中数据集合需要转换为np.array类型。


 

运行截图如下:

2016-10-21-11-12-23%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be 2016-10-21-11-14-52%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be

其中第一部分是每一个点在聚类之后所属的类的标识,可以看出最高有7,说明该集合最多聚集了8个类,显示的数值为5则是聚类中类数目大于3的有5个。

关于项目最后

140w个经纬数据,按照ip/24分类,分出19660个24块,对每一个24块聚类,将分类结果和游离点标记,重新写回数据库,项目完结。

总计运算时间约半小时。其实聚类耗时少,测试时时间主要消耗在绘图上。曾经直接将10000个点一起聚类,但是在大的距离尺度下,密度的衡量值就变化了,导致10000个点只分出10个类别,导致精度不和要求所以拆分块之后再聚类。

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

1 3 收藏 5 评论

关于作者:路易十四

少年程序猿,从事数据采集挖掘方面:个人博客,www.urlteam.org,邮箱:a83533774@gmail.com主要技能树:python,爬虫,linux,web前端,ACM,骑行。 个人主页 · 我的文章 · 9 ·   

相关文章

可能感兴趣的话题



直接登录
最新评论
  • 请问您在文中最后说的24块是什么意思呢?Ip是什么意思呢?   按照您的说法,如果一共3万个经纬度数据似乎也是要分块的意思?不过不太明白是怎么分块的?

    • 路易十四 数据挖掘 03/27

      我这里的ip就是ip地址的意思,我这里的数据是ip地址以及对应位置信息,24块就是ip最后aaa.bbb.ccc.ddd。只要是同一个abc就是一个24块。

      • listener   03/29

        我有64万行数据,也就是说不能一次性全处理完?要分块么?具体是怎么分块的呢,不是太懂,能麻烦说一下吗

         

        • 路易十四 数据挖掘 03/29

          。。。。ip格式为aaa.bbb.ccc.ddd 吧abc相同的作为同一组即可。一次处理一组,导入data.txt 的为经纬度。类似如下,空格隔开。每次聚类都会以这一组进行聚类(之所以要分组是因为一次几十万的点一起聚类的话效果不好。)

          114.224025 22.405946
          114.224025 22.405946
          114.206792 22.419722
          114.186303 22.434767
          114.224025 22.405946

  • 大耐   04/19

    请问,mark为什么没有用啊,在我这里?

跳到底部
返回顶部