机器学习实践:用 Spark 和 DBSCAN 对地理定位数据进行聚类

【新智元导读】数据专家 Natalino Busa 在本文中讨论了如何从大量的定位事件中获取用户的活动区域来构建基于位置的服务。他经过论证得出,DBSCAN算法与Spark的结合似乎是一种很有前途的方法,可以抽取准确的地理位置模式,并用于开发基于各种场景的数据驱动、基于位置的应用程序,例如个性化营销、欺诈防范和内容过滤。

机器学习,特别是聚类算法,可以用来确定哪些地理区域经常被一个用户访问和签到而哪些区域不是。这样的地理分析使多种服务成为可能,比如基于地理位置的推荐系统,先进的安全系统,或更通常来说,提供更个性化的用户体验。

在这篇文章中,我会确定对每个人来说特定的地理活动区域,讨论如何从大量的定位事件中(比如在餐厅或咖啡馆的签到)获取用户的活动区域来构建基于位置的服务。举例来说,这种系统可以识别一个用户经常外出吃晚饭的区域。

使用DBSCAN聚类算法

首先,我们需要选择一种适用于定位数据的聚类算法,可以基于提供的数据点的局部密度确定用户的活动区域。DBSCAN 算法是一个不错的选择,因为它自下而上地选择一个点并在一个给定的距离寻找更多的点。然后通过重复这个过程扩展寻找新的点来扩展类簇,直到无法再扩大为止。

这个算法可以通过两个参数进行调试:ε(用来确定离给定的点多远来搜索)和 minPoints(为了类簇扩展,决定一个给定的点的邻域附近最少有多少点)。通过寻找邻近点,本地类簇开始出现,各种形状的类簇逐渐可以被识别(请参见图1的简化描述)。过于孤立的点和离其他点太远的点则会被分配到一个特殊的异常值集群。这些独特的属性使DBSCAN算法适合对地理定位事件进行聚类。

图1:两由DBSCAN算法(ε= 0.5和minPoints = 5)聚类得出的两个类簇。一个是L型,另一个是圆形。互相靠近的点被分配到相同的类簇。黑色的孤立点被视为“异常点”。图片来自Natalino Busa。

在Spark里使用PairRDDs

在大多数实际应用中,机器学习系统必须处理数以百万计的用户和数十亿的事件。因此,随着越来越多的用户和事件被添加到系统中,一个精心设计的数据处理通道需要具备快速和可伸缩的特点。这就需要分布式计算。就我们的目标而言,Spark作为一个分布式处理引擎,是一个很好的选择,因为它提供了能够在多机器上并行执行许多基于地理定位的聚类任务的计算框架。

在Spark里,用户地理定位数据可以使用称为PairRDD的对象来建模。PairRDD是一个分布式的元组集合(键,值),根据关键字段被划分到多个机器。特别是对于地理定位数据,我们选择的键是用户标识符,值是给定用户的所有签到的聚合列表。

地理定位数据放置在一个n×2的矩阵中,其中第一列表示经度,第二列表示纬度。参见下面的例子,这是Spark数据类型中的PairRDD集合,以及元祖的一个例子:

org.apache.spark.rdd.RDD[(Long, breeze.linalg.DenseMatrix[Double])]

(15474, DenseMatrix( 40.8379525833 -73.70209875

40.6997066969 -73.8085234165

40.7484436586 -73.9857316017

40.750613794 -73.993434906 ))

DBSCAN在 Spark 中并发运行

DBSCAN算法在多种语言和包里都有实现。下面的代码片段是基于DBSCAN 在GitHub上的scala nlp /nak 库中的实现。

假设给定用户经常访问城市的三个区域,一个区域是经常参加酒宴和聚会的,另一个是经常来舒适放松的,还有一个是和朋友一起吃晚餐的。如果这些区域位于城市的不同部分,下面的代码通过查看每个事件的位置将其分到不同类簇。在这段代码中,我们寻找距离约100米的范围内的事件(约 0.001度),如果至少有三个点互相接近,我们便开始进行聚类。

import breeze.numerics._

import nak.cluster._

import nak.cluster.GDBSCAN._

def dbscan(v : breeze.linalg.DenseMatrix[Double]) = {

val gdbscan = new GDBSCAN(

DBSCAN.getNeighbours(epsilon = 0.001, distance = Kmeans.euclideanDistance),

DBSCAN.isCorePoint(minPoints = 3)

)

val clusters = gdbscan cluster v

}

然后,我们将用Spark对整个用户集合来并行dbscan算法。 这个操作作为Spark的PairRDD功能的一部分已经可以使用了,它叫做mapValues:

val clustersRdd = checkinsRdd.mapValues(dbscan(_))

简而言之,定位数据的聚类在Spark中可以这样实现,将位置的原始PairRDD转换到一个新的PairRDD,其中元组的键值分别代表用户的ID,和其对应的定位类簇。一旦定位数据被聚类完毕,它可以进一步概括总结,比如确定每个类簇的边界框或轮廓

图2显示了从一个使用Gowalla(用户在特定地点签到分享他们的位置的社交网站)的匿名用户的定位数据中提取的一个示例类簇。图中是佛罗里达地图,特别是开普科勒尔地区,签到的地方会有一个带颜色的点。

事件根据其发生的地理位置被聚类。例如在 Estero Bay (暗橙色圆点)漫步、在机场的聚集活动(棕色点)和森尼贝尔岛的聚集活动(绿点)属于不同的聚类(ε设定为3公里,minPoints设置为3)。

图2:从用户的佛罗里达开普科勒尔区域的Gowalla数据集中提取聚类的例子。注意点集合的密度与聚类正确匹配,异常值标记为孤立的黑点。图片来自Natalino Busa。地图重叠:OpenStreet地图。

进一步增强地理定位数据分析

这一分析是围绕地理坐标进行的,但可以很容易地扩展到其他事件属性上,如签到时间、场地类型(餐厅、体育馆、博物馆)或用户的状态。聚类算法还可以将用户社交网络中朋友所生成的事件考虑进来,从而得以应用于一个更大的上下文。

Spark为SQL数据处理提供了一个模块,可用于在运行聚类算法之前运行查询来过滤和收集事件。通过这种方式,数据处理通道可以在Spark上完整地实现SQL和机器学习的统一框架。这种扩展的数据管道对特定类别的事件将提供更准确的聚类结果。

创建一个基于位置的API 服务

Spark 产生的聚类分析结果可以保存在一个数据存储表中。一个API服务可以查询该表,并确定一个新出现的地理位置点是否属于已知的地区。API服务可以根据用户场景触发适当的行为。例如,它可以通过消息向用户告警、发送通知或提供推荐。

结论

我最初的实验表明 Spark 提供了坚实的基础设施在大量的用户和事件上来并行处理和分发机器学习算法。此外,Spark通过在一个数据处理框架结合SQL查询和机器学习,加快了数据驱动系统的开发。

DBSCAN算法与Spark的结合似乎是一种很有前途的方法,可以抽取准确的地理位置模式,并用于开发基于各种场景的数据驱动、基于位置的应用程序,例如个性化营销、欺诈防范和内容过滤。

原文发布于微信公众号 - 新智元(AI_era)

原文发表时间:2017-01-23

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

【零一】#操作教程贴#从0开始,教你如何做数据分析#中阶#第八篇

大家好,我是零一。第一次用手机写文章,哈。在车上的时间看了一本书,余下的时间,我想应该可以写一篇文章。图片等到了地儿了,再用电脑补上。 我的公众微信号是sta...

22050
来自专栏前端儿

无线网络覆盖

我们的乐乐同学对于网络可算得上是情有独钟,他有一个计划,那就是用无线网覆盖郑州大学。

16710
来自专栏图形学与OpenGL

计算机图形学课程设计内容及要求

目标:以图形学算法为目标,深入研究。继而策划、设计并实现一个能够表现计算机图形学算法原理的或完整过程的演示系统,并能从某些方面作出评价和改进意见。通过完成一个完...

14260
来自专栏人工智能头条

用机器学习怎样鉴别不可描述的网站

前两天教师节,人工智能头条的某个精神股东粉群里,大家纷纷向当年为我们启蒙、给我们带来快乐的老师们表达感激之情。

17820
来自专栏机器学习算法原理与实践

英文文本挖掘预处理流程总结

    在中文文本挖掘预处理流程总结中,我们总结了中文文本挖掘的预处理流程,这里我们再对英文文本挖掘的预处理流程做一个总结。

16520
来自专栏数据结构与算法

各种读入方式速度比较

以前写过一篇比较scanf与cin的博客,但是那篇博客存在很多bug,测速也很不规范。 今天我收集了一下众大佬的读入优化,来做个比较 特别鸣谢:my,zyh,h...

33640
来自专栏奇点大数据

神器Pytorch(1)

话说,自从我自己入坑深度学习以来,也是用了不少的框架,什么Tensorflow、Chainer、Theano、Caffe、Torch等等。鉴于赶时髦以及对谷歌老...

47150
来自专栏目标检测和深度学习

资源 | Texture:一个优雅的开源学术论文书写工具

机器之心整理 作者:思源 近日,Substance 在 GitHub 上开源了一个用于结构文本的文字处理工具 Texture,他们表示该工具像 LaTeX 一样...

403100
来自专栏大数据

用R语言进行文本挖掘和主题建模

我们每天都会遇到各种各样的文本数据 - 但大部分是非结构化的,并不是全部都是有价值的。请继续阅读以了解文本挖掘如何提供帮助。

43810
来自专栏携程技术中心

干货 | 去哪儿酒店算法服务平台

作者简介 张中原,2011年加入去哪儿网,先后从事交易系统、酒店数据、公司基础平台与组件、存储和监控等相关工作,曾长期担任应届生技术培训和指导。 最近几年时间,...

458100

扫码关注云+社区

领取腾讯云代金券