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

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

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

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