专栏首页Urlteam使用python-sklearn-机器学习框架针对140W个点进行kmeans基于密度聚类划分

使用python-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值评定聚类效果

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

from sklearn.cluster import KMeans
from sklearn.externals import joblib
import numpy
import matplotlib.pyplot as plt

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

# -*- coding: utf-8 -*-
from sklearn.cluster import KMeans
from sklearn.externals import joblib
import numpy
import time
import matplotlib.pyplot as plt
 
if __name__ == '__main__':
    ## step 1: 加载数据
    print "step 1: load data..."
    dataSet = []
    fileIn = open('./data.txt')
    for line in fileIn.readlines():
        lineArr = line.strip().split(' ')
        dataSet.append([float(lineArr[0]), float(lineArr[1])])
 
    #设定不同k值以运算
    for k in range(2,10):
        clf = KMeans(n_clusters=k) #设定k  !!!!!!!!!!这里就是调用KMeans算法
        s = clf.fit(dataSet) #加载数据集合
        numSamples = len(dataSet) 
        centroids = clf.labels_
        print centroids,type(centroids) #显示中心点
        print clf.inertia_  #显示聚类效果
        mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
        #画出所有样例点 属于同一分类的绘制同样的颜色
        for i in xrange(numSamples):
            #markIndex = int(clusterAssment[i, 0])
            plt.plot(dataSet[i][0], dataSet[i][1], mark[clf.labels_[i]]) #mark[markIndex])
        mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
        # 画出质点,用特殊图型
        centroids =  clf.cluster_centers_
        for i in range(k):
            plt.plot(centroids[i][0], centroids[i][1], mark[i], markersize = 12)
            #print centroids[i, 0], centroids[i, 1]
        plt.show()

效果截图如下:

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

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

# -*- coding: utf-8 -*-
from sklearn.cluster import KMeans
from sklearn.externals import joblib
import numpy ,time
import matplotlib.pyplot as plt
from sklearn.cluster import MeanShift, estimate_bandwidth
import numpy as np
 
if __name__ == '__main__':
    ## step 1: 加载数据
    print "step 1: load data..."
 
    dataSet = []
    fileIn = open('./data.txt')
    for line in fileIn.readlines():
        lineArr = line.strip().split(' ')
        dataSet.append([float(lineArr[0]), float(lineArr[1])])
 
    numSamples = len(dataSet)
    X = np.array(dataSet) #列表类型转换成array数组类型
 
    bandwidth = estimate_bandwidth(X, quantile=0.2, n_samples=500)
    clf = MeanShift(bandwidth=bandwidth, bin_seeding=True,cluster_all=True).fit(X)
 
    centroids = clf.labels_
    print centroids,type(centroids) #显示每一个点的聚类归属
    # 计算其自动生成的k,并将聚类数量小于3的排除
    arr_flag = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    for i in clf.labels_:
        arr_flag[i]+=1
    k = 0
    for i in arr_flag:
        if(i > 3):
            k +=1
    print k
 
    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    #画出所有样例点 属于同一分类的绘制同样的颜色
    for i in xrange(numSamples):
        plt.plot(dataSet[i][0], dataSet[i][1], mark[clf.labels_[i]]) #mark[markIndex])
    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
    # 画出质点,用特殊图型
    centroids =  clf.cluster_centers_
    for i in range(k):
        plt.plot(centroids[i][0], centroids[i][1], mark[i], markersize = 12)
    print centroids #显示中心点坐标
    plt.show()

运行截图如下:

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

关于项目最后

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

总计运算时间约半小时。其实聚类耗时少,测试时时间主要消耗在绘图上。

原创文章,转载请注明: 转载自URl-team

本文链接地址: 使用python-sklearn-机器学习框架针对140W个点进行kmeans基于密度聚类划分

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • STL 算法部分 原创入门教程

    库为  Algorithm 算法库  Functional函数式编程       Numeric  基础性的数值算法

    十四君
  • acm比赛刷题小技巧

    2.有时候int型不够用,可以用long long或__int64型(两个下划线__)。

    十四君
  • 百度语音识别api使用python进行调用

    百度语音现在是比较方便的接口,具体说明请看官方文档,本文分两个部分,先是使用python实现录音,然后再使用百度语音api进行识别上传。

    十四君
  • 谱聚类、Chameleon聚类、PCCA、SOM、Affinity Propagation

    层次聚类和K-means聚类,可以说是聚类算法里面最基本的两种方法(wiki的cluster analysis页面都把它们排前两位)。这次要探讨的,则是两个相...

    机器学习AI算法工程
  • 聚类算法之——k-means,k-means++,Minibatch kmeans

    可以说这也符合我们的直觉:聚类中心当然是互相离得越远越好。这个改进虽然直观简单,但是却非常得有效。

    种花家的奋斗兔
  • 四种聚类方法之比较

    聚类分析是一种重要的人类行为,早在孩提时代,一个人就通过不断改进下意识中的聚类模式来学会如何区分猫狗、动物植物。目前在许多领域都得到了广泛的研究和成功的应用,如...

    统计学家
  • 转载 | Python AI 教学│k-means聚类算法及应用

    假如有这样一种情况,在一天你想去某个城市旅游,这个城市里你想去的有70个地方,现在你只有每一个地方的地址,这个地址列表很长,有70个位置。事先肯定要做好攻略,你...

    短短的路走走停停
  • Python AI 教学│k-means聚类算法及应用

    假如有这样一种情况,在一天你想去某个城市旅游,这个城市里你想去的有70个地方,现在你只有每一个地方的地址,这个地址列表很长,有70个位置。事先肯定要做好攻略,你...

    用户1621951
  • 数据挖掘从入门到放弃(六):K-means 聚类

    所谓物以类聚-人以群分,“类”指的是具有相似性的集合,聚类是指将数据集划分为若干类,使得各个类之内的数据最为相似,而各个类之间的数据相似度差别尽可能的大。聚类分...

    数据社
  • 当我们拿到数据进行建模时, 如何选择更合适的算法?

    2.其次,看数据特征的数据类型,然后做一些初步的数据统计,比如是否数据均衡,大致的数据分布是怎样的(不同类别的分布)

    公众号guangcity

扫码关注云+社区

领取腾讯云代金券