用户地理位置的聚类算法实现—基于DBSCAN和Kmeans的混合算法

标签: 用户 地理位置 聚类 | 发表时间:2016-10-05 01:58 | 作者:jackaduma
出处:http://blog.csdn.net

1. 聚类算法简介

聚类的目标是使同一类对象的相似度尽可能地大;不同类对象之间的相似度尽可能地小。目前聚类的方法很多,根据基本思想的不同,大致可以将聚类算法分为五大类:层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。
以下实现主要选取了基于划分的Kmeans算法和基于密度的DBSCAN算法来处理

1.1 基于划分的Kmeans算法

一种典型的划分聚类算法,它用一个聚类的中心来代表一个簇,即在迭代过程中选择的聚点不一定是聚类中的一个点。其目的是使各个簇(共k个)中的数据点与所在簇质心的误差平方和SSE(Sum of Squared Error)达到最小,这也是评价K-means算法最后聚类效果的评价标准。
算法的详细原理可自行Google或Wiki。

1.2 基于密度的DBSCAN算法

一种典型的基于密度的聚类算法,该算法采用空间索引技术来搜索对象的邻域,引入了“核心对象”和“密度可达”等概念,从核心对象出发,把所有密度可达的对象组成一个簇。简单的说就是根据一个根据对象的密度不断扩展的过程的算法。一个对象O的密度可以用靠近O的对象数来判断。
在DBSCAN算法中将数据点分为一下三类:
核心点:在半径Eps内含有超过MinPts数目的点
边界点:在半径Eps内点的数量小于MinPts,但是落在核心点的邻域内
噪音点:既不是核心点也不是边界点的点
这里有两个量,一个是半径Eps,另一个是指定的数目MinPts。

2. 用户地理位置信息的的聚类实现

本实验用python实现,依赖numpy, pandas, sklearn, scipy等科学计算library。
数据来自收集得到的用户的地理位置信息,即经纬度数据的序列集。

  xy = numpy.array([[116.455788, 39.920767], [116.456065, 39.920965], [116.452312, 39.92304], [116.421385, 39.989539],
                      [116.455685, 39.92069], [116.455876, 39.920845], [116.455973, 39.920902], [116.455645, 39.920657],
                      [116.456022, 39.920934], [116.455685, 39.920691], [116.456023, 39.920671], [116.45596, 39.920864],
                      [116.455522, 39.920856], [116.455276, 39.920407], [116.455799, 39.920867],
                      [116.455349, 39.920425], [116.45511, 39.920377], [116.455318, 39.920442], [116.455298, 39.920474],
                      [116.455839, 39.920636], [116.455979, 39.921168], [116.454281, 39.920006], [116.45598, 39.920612],
                      [116.45388, 39.919584], [116.455474, 39.920737], [116.456009, 39.920641], [116.455439, 39.920574],
                      [116.455759, 39.920841], [116.455838, 39.920644], [116.455983, 39.920847],
                      [116.459803, 39.922041], [116.456029, 39.92088], [116.455539, 39.920603], [116.455989, 39.920851],
                      [116.455719, 39.920789], [116.45601, 39.92082], [116.456229, 39.920564], [116.455906, 39.920771],
                      [116.456248, 39.920868], [116.455805, 39.920544], [116.455896, 39.920758], [116.43692, 39.926767],
                      [116.454672, 39.92024], [116.454813, 39.917848], [116.381415, 40.00875], [116.422925, 39.980757],
                      [116.422849, 39.9808], [116.38107, 40.009217], [116.456078, 39.920747], [116.455242, 39.919515],
                      [116.455615, 39.920533], [116.422092, 39.991104], [116.454847, 39.917724],
                      [116.456686, 39.924316], [116.45575, 39.920642], [116.456713, 39.924413], [116.455846, 39.920828],
                      [116.422108, 39.991098], [116.422075, 39.991139], [118.775572, 31.97337], [118.776968, 31.97392],
                      [118.778187, 31.973121], [118.775695, 31.973254], [118.775302, 31.973807],
                      [118.776303, 31.973692], [118.777541, 31.973439], [118.776196, 31.973489],
                      [116.448944, 39.926799], [116.45487, 39.917804], [116.455762, 39.920645], [116.456146, 39.920441],
                      [116.455857, 39.920043], [116.455458, 39.920826], [116.455533, 39.920791],
                      [116.455426, 39.920896], [116.45566, 39.920811], [116.455696, 39.920621], [116.453667, 39.9259],
                      [116.466606, 39.886322], [116.455917, 39.92062]])

2.1 基于Kmeans的聚类实现

假设用户的地理位置信息通常是工作地点和家,因此选取k值为2,代码如下

  res, idx = kmeans2(numpy.array(zip(xy[:, 0], xy[:, 1], z)), 2, iter=20, minit='points')

实现输出结果
这里写图片描述
但是实际上用户并未在河北出现过,用户经常出现的地方除了北京的工作地方和家,还曾经在南京出差一段时间。所以将K值设定为3,再次运行

  res, idx = kmeans2(numpy.array(zip(xy[:, 0], xy[:, 1], z)), 3, iter=20, minit='points')

输出结果
这里写图片描述
这样就将南京的地理位置区分出来了。工作地方和出差地方已经非常贴合了,但是家的地方离实际距离还是差了不少距离。
其实已经可以看出来,由于用户的出现地点不可预知,因此 很难确定K值。并且 Kmeans聚合得到的结果取得是聚合簇的质心位置,并不是用户的实际地理位置,而且我选取的是相似度量是欧式距离,而不是经纬度计算的球面距离。因此得到的结果并不理想。

2.2 基于DBSCAN的聚类实现

DBSCAN算法的重点是选取的聚合半径参数和聚合所需指定的MinPts数目。
在此使用球面距离来衡量地理位置的距离,来作为聚合的半径参数。
如下实验,选取2公里作为密度聚合的半径参数,MinPts个数为5.

  def haversine(lonlat1, lonlat2):
    lat1, lon1 = lonlat1
    lat2, lon2 = lonlat2
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])

    dlon = lon2 - lon1
    dlat = lat2 - lat1
    a = sin(dlat / 2) ** 2 + cos(lat1) * cos(lat2) * sin(dlon / 2) ** 2
    c = 2 * asin(sqrt(a))
    r = 6371  # Radius of earth in kilometers. Use 3956 for miles
    return c * r


def clustering_by_dbscan():
    ......
    distance_matrix = squareform(pdist(X, (lambda u, v: haversine(u, v))))

    db = DBSCAN(eps=2, min_samples=5, metric='precomputed')  
    y_db = db.fit_predict(distance_matrix)
    X['cluster'] = y_db
    ......
    plt.scatter(X['lat'], X['lng'], c=X['cluster'])
    plt.show()
  输出如下

这里写图片描述

结果显示该用户的地理位置信息聚合簇为4块,在结果中分别用0.0,1.0,2.0,-1.0来标记。可以看出DBSCAN算法可以根据用户的活动半径,也就是设定的最小半径参数2公里,将用户的活动地理位置数据集合分为了4簇,而且每一簇 在空间上都是任意形状的,分类聚合的效果是不错的,但是得到的结果是一个个的簇,也就是一个个的地理点的集合,并不是一个“中心”。并且存在的 噪声点无法区分。

3.基于DBSCAN和Kmeans的混合算法实现

从上面的实验结果,Kmeans算法的关键的是 K值的选取,而我无法确定用户地理信息聚类的簇的个数,如果实际上的地理位置的分布过于分散,按照固定K值聚合,得到的质心的位置可能和实际位置相差甚远。而DBSCAN的算法,聚类结果不错,因为是按照设定的人的活动半径的密度可达来聚合的,但其结果是将数据集合分类,并不求出 中心点
因此我设计了一种基于DBSCAN和Kmeans的混合算法:先利用DBSCAN算法的密度可达特性将用户的地理位置数据集按照活动半径聚合成若干个簇,并且将每一簇的数据集作为新的输入,再利用Kmeans算法的迭代聚合求出 质心的位置,设定 K值为1
代码如下

  def clustering_by_dbscan_and_kmeans2():
    X = pd.DataFrame(
        {"lat": [39.920767, 39.920965, 39.92304, 39.989539, 39.92069, 39.920845, 39.920902, 39.920657, 39.920934,
                 39.920691, 39.920671, 39.920864, 39.920856, 39.920407, 39.920867, 39.920425, 39.920377, 39.920442,
                 39.920474, 39.920636, 39.921168, 39.920006, 39.920612, 39.919584, 39.920737, 39.920641, 39.920574,
                 39.920841, 39.920644, 39.920847, 39.922041, 39.92088, 39.920603, 39.920851, 39.920789, 39.92082,
                 39.920564, 39.920771, 39.920868, 39.920544, 39.920758, 39.926767, 39.92024, 39.917848, 40.00875,
                 39.980757, 39.9808, 40.009217, 39.920747, 39.919515, 39.920533, 39.991104, 39.917724, 39.924316,
                 39.920642, 39.924413, 39.920828, 39.991098, 39.991139, 31.97337, 31.97392, 31.973121, 31.973254,
                 31.973807, 31.973692, 31.973439, 31.973489, 39.926799, 39.917804, 39.920645, 39.920441, 39.920043,
                 39.920826, 39.920791, 39.920896, 39.920811, 39.920621, 39.9259, 39.886322, 39.92062],
         "lng": [116.455788, 116.456065, 116.452312, 116.421385, 116.455685, 116.455876, 116.455973, 116.455645,
                 116.456022, 116.455685, 116.456023, 116.45596, 116.455522, 116.455276, 116.455799, 116.455349,
                 116.45511, 116.455318, 116.455298, 116.455839, 116.455979, 116.454281, 116.45598, 116.45388,
                 116.455474, 116.456009, 116.455439, 116.455759, 116.455838, 116.455983, 116.459803, 116.456029,
                 116.455539, 116.455989, 116.455719, 116.45601, 116.456229, 116.455906, 116.456248, 116.455805,
                 116.455896, 116.43692, 116.454672, 116.454813, 116.381415, 116.422925, 116.422849, 116.38107,
                 116.456078, 116.455242, 116.455615, 116.422092, 116.454847, 116.456686, 116.45575, 116.456713,
                 116.455846, 116.422108, 116.422075, 118.775572, 118.776968, 118.778187, 118.775695, 118.775302,
                 118.776303, 118.777541, 118.776196, 116.448944, 116.45487, 116.455762, 116.456146, 116.455857,
                 116.455458, 116.455533, 116.455426, 116.45566, 116.455696, 116.453667, 116.466606, 116.455917]
         })
    distance_matrix = squareform(pdist(X, (lambda u, v: haversine(u, v))))

    db = DBSCAN(eps=2, min_samples=5, metric='precomputed')  
    y_db = db.fit_predict(distance_matrix)

    X['cluster'] = y_db

    results = {}
    for i in X.values:
        if i[2] not in results.keys():
            results[i[2]] = [[i[1], i[0]]]
        else:
            if results[i[2]]:
                results[i[2]].append([i[1], i[0]])
            else:
                results[i[2]] = [[i[1], i[0]]]
    print "DBSCAN output: ", len(results), results.keys()
    print "KMeans calc center as below: "
    for k in results.keys():
        xy = numpy.array(results[k])
        z = numpy.sin(xy[:, 1] - 0.2 * xy[:, 1])

        z = whiten(z)

        res, idx = kmeans2(numpy.array(zip(xy[:, 0], xy[:, 1], z)), 1, iter=20, minit='points')
        address_text = my_get_address_text_by_location(res[0][1], res[0][0])
        print res, address_text       

输出如下
这里写图片描述

其中”家“,”公司“,”出差“的位置信息已经非常贴合用户的实际信息了。
但是仍然存在的 噪声点的信息。这个暂时还没找到解决方案,下一步的思路是带入用户地理位置信息收集时候得到的附属信息如时间来辅助分析,希望可以有更好的结果。


作者:jackaduma 发表于2016/10/4 17:58:11 原文链接
阅读:19 评论:0 查看评论

相关 [用户 地理位置 聚类] 推荐:

用户地理位置的聚类算法实现—基于DBSCAN和Kmeans的混合算法

- - CSDN博客综合推荐文章
聚类的目标是使同一类对象的相似度尽可能地大;不同类对象之间的相似度尽可能地小. 目前聚类的方法很多,根据基本思想的不同,大致可以将聚类算法分为五大类:层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法. 以下实现主要选取了基于划分的Kmeans算法和基于密度的DBSCAN算法来处理.

谷歌将允许用户关闭地理位置追踪服务

- Woooon - cnBeta.COM
据国外媒体报道,谷歌周二表示,从今年晚些时候开始,谷歌将允许用户关闭地理位置追踪服务. 在此之前,欧盟隐私保护部门对科技公司收集用户地理位置信息的行为进行了调查. 谷歌全球隐私总顾问彼得・弗莱斯切(Peter Fleischer)周二通过博客表示,谷歌将允许全球Wi-Fi网络用户关闭地理位置服务.

HTML 5中地理位置api小结

- - ITeye博客
  HTML 5提供了地理位置等一系列API可以给用户使用,方便用户制作LBS的地理应用,首先在支持HTML 5的浏览器中,当开启API时,会询问是否用户同意使用api,否则不会开启的,保证安全. 1) 开启,判断是否浏览器支持LBS api.    上面的例子中,还在displayError方法中,捕捉了异常;.

聚类分析在用户分类中的应用

- - 人人都是产品经理
聚类分析属于探索性的数据分析方法. 通常,我们利用聚类分析将看似无序的对象进行分组、归类,以达到更好地理解研究对象的目的. 聚类结果要求 组内对象相似性较 高, 组间对象相似性较 低. 在用户研究中,很多问题可以借助聚类分析来解决,比如,网站的信息分类问题、网页的点击行为关联性问题以及用户分类问题等等.

基于地理位置的广告威力初现

- 小皮 - 爱范儿 · Beats of Bits
更精准的投放一直是广告公司的重要目标. 在这方面,拥有大量用户信息的移动运营商占据着得天独厚的优势. O2 几个月前在英国推出“你在这儿(You Are Here)”广告服务目前已经初显成效. O2 的“你在这儿”可以根据用户年龄、性别、当前所在位置、所处区域的气温投放短信/彩信广告. 厂商可以根据这些信息更有效地过滤出目标用户,实现精确投放.

地理位置技术将如何将改变服务业

- 彭全兵 - 互联网的那点事...
据国外媒体报道, 现场服务管理应用套件ServiceMax的首席执行官戴夫·约诺德(Dave Yarnold)今天发表署名文章,讨论地理位置技术在服务业中的应用,以下为全文摘要:. 面向消费者的地理位置服务如雨后春笋般冒出来,它们无处不在,比如Uber,它可以派一辆轿车到你的门口,速度比出租车快一倍,又比如应用程序Bizzy,它显示你的朋友们最近在哪里吃饭,并为你提供朋友们的推荐.

+1: 基于地理位置的活动交友应用

- 和谐牌河蟹 - Tech2IPO
你近期一定在被LBS、O2O、SOLOMO这些关键词反复轰炸,以几米、陌陌为代表的陌生人弹性社交应用,以幸会、在这儿为代表的活动交友应用,或许你并不了解这些关键词背后所代笔的产业变革,但它们的确为我们的生活带来了新的改变. “+1”这是一个好坏都特别明显的名称,很个性但也很容易被误认,这是生活中最常见的符号与字符,同时Google之前也推出了一款同名工具.

IP地理位置数据库 中国地区扩展版 120621

- - eMule Fans 电骡爱好者
这里的 IP地理位置数据库 中国地区扩展版,是 我们在webhosting.info的数据库基础上,进行了简体中文的汉化,并将 QQ IP 数据库(QQWry.Dat)纯真版中的中国地区详细IP数据库导入,而结合得到的. 更新时间2012年6月21日,版本号120621. IP to Country 数据库文件ip-to-country.csv,可用于Xtreme、MorphXT等许多支持IP2C功能的 eMule Mod软件.

【转载】HTML5 地理位置定位的原理及应用

- - HTML5研究小组
地理位置是HTML5 的重要特性之一,提供了确定用户位置的功能,借助这个特性东莞网站建设公司能够开发基于位置信息的应用. 下面 聚焦网络科技向大家介绍一下HTML5地理位置定位的基本原理及各个浏览器的数据精度情况. 在访问位置信息前,浏览器都会询问用户是否共享其位置信息,以 Chrome 浏览器为例,如果您允许 Chrome 浏览器与网站共享您的位置,Chrome 浏览器会向 Google 位置服务发送本地网络信息,估计您所在的位置.

HTML5开发:地理位置定位指南

- - HTML5研究小组
HTML5提供的最令人激动的特性之一. JavaScript代码,可以创建出能确定用户地理位置详细信息的Web应用,包括经纬度以及海拔等. 一些Web应用甚至能通过监控用户位置随时间的移动来提供导航功能,其中还综合了GoogleMaps API这样的地图系统. 和所有HTML5的功能一样,你还不能依赖浏览器提供支持.