新智元启动新一轮大招聘：COO、执行总编、主编、高级编译、主笔、运营总监、客户经理、咨询总监、行政助理等 9 大岗位全面开放。

　　简历投递：j[email protected]

　　HR 微信：13552313024

　　新智元为COO和执行总编提供最高超百万的年薪激励；为骨干员工提供最完整的培训体系、高于业界平均水平的工资和奖金。

　　加盟新智元，与人工智能业界领袖携手改变世界。

　　【新智元导读】数据专家 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(_))