开发者社区> 小旋风柴进> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

用Spark和DBSCAN对地理定位数据进行聚类

简介:
+关注继续查看


0?wx_fmt=png

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

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

使用DBSCAN聚类算法

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

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

640?wx_fmt=jpeg


图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)。

640?wx_fmt=jpeg


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

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

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

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

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

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

结论

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

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

原文发布时间为:2017-01-21


本文来自云栖社区合作伙伴“大数据文摘”,了解相关信息可以关注“BigDataDigest”微信公众号

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Spark Streaming 数据清理机制
大家刚开始用Spark Streaming时,心里肯定嘀咕,对于一个7*24小时运行的数据,cache住的RDD,broadcast 系统会帮忙自己清理掉么?还是说必须自己做清理?如果系统帮忙清理的话,机制是啥?
2770 0
【Spark Summit East 2017】Spark中的容错:从生产实践中获取的经验
本讲义出自Jose Soltren在Spark Summit East 2017上的演讲,主要介绍了Spark容错中的螺母和螺栓,他首先简述了Spark中的各种容错机制,然后讨论了YARN上的Spark、调度与资源分配,在演讲中还对于一些用户案例进行了探讨研究并给出了一些需要的工具,最后分享了未来Spark中容错未来的发展方向比如调度器和检查点的变化。
1930 0
【Spark Summit East 2017】从容器化Spark负载中获取的经验
本讲义出自Tom Phelan在Spark Summit East 2017上的演讲,Tom Phelan探讨了如何实现高可用性的分布式大数据应用和数据中心主机,并分享了学到的经验教训,并对于如何在一个可靠的、可伸缩的、高性能的环境将大数据应用程序容器化给出了一些提示。
1838 0
【Spark Summit EU 2016】使用Java Agent扩展Spark
本讲义出自Jaroslav Bachorik与Adrian Popescu在Spark Summit EU上的演讲,主要介绍了Spark缓存中出现的关于when, what, where的挑战问题以及应对这一挑战使用RDDs的解决算法。
2246 0
【Spark Summit EU 2016】没人会把Spark放在容器里
本讲义出自Jorg Schad在Spark Summit EU上的演讲,主要介绍了基于Mesos的开源的数据中心操作系统DC/OS,DC/OS可以用于处理容器和大数据。Jorg Schad还介绍了容器技术的相关内容,从容器技术的设计理念到容器技术与虚拟机技术的区别,以及容器技术控制组、命名空间等相关技术细节,在最后还讨论了Java与容器的关联。
1773 0
【Spark Summit EU 2016】TPC-DS基准测试下的Spark SQL2.0使用体验
本讲义出自Berni Schiefer在Spark Summit EU上的演讲,目前而言Spark SQL发展演进的速度非常迅猛,但是大多数情况下还是部署在传统的Hadoop集群上,为了尝试将Spark SQL使用在专为Spark设置的集群上,Berni Schiefer使用了最新版本的Spark SQL应对企业级标准的工作负载。
4223 0
【Spark Summit EU 2016】经验分享:将SparkR用于生产环境下的数据科学应用中
本讲义出自Heiko Korndorf在Spark Summit EU 2016上的演讲,主要分享了R语言以及现实场景下使用R语言进行数据分析的应用案例,并且将引领大家使用SparkR扩展R语言应用,并介绍了SparkR1.X和2.X架构,并介绍了这两个版本的SparkR分别如何获取。
2006 0
【Spark Summit EU 2016】瑞士电信:对于集体移动性的理解
本讲义出自Francois Garillot and Mohamed Kafsi在Spark Summit EU上的演讲,主要介绍了瑞士电信通过对于用户的集体移动大数据进行分析得到的理解。
1877 0
【Spark Summit EU 2016】60 TB+数据规模的Spark产品用例
本讲义出自Sital Kedia在Spark Summit EU上的演讲,主要介绍了60 TB+数据规模的Spark产品用例,他在开始时首先介绍了实体排序的用例,然后介绍之前使用Hive进行的实现以及现在使用Spark的实现方式,并对于两种实现方式进行了对比。
3511 0
文章
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
基于Spark的面向十亿级别特征的 大规模机器学习
立即下载
深度学习的迁移模型
立即下载
基于Spark的大规模机器学习在微博的应用
立即下载