用Spark/DBSCAN做地理定位数据聚类

问题导读：
1、如何利用机器学习对用户事件进行分类？
2、如何利用Spark/DBSCAN进行数据聚类？



机器学习，特别是聚类算法，可以用来确定哪些地理区域被一个给定的用户经常访问和“入住”而哪些区域不是。这样的地理分析使范围广泛的服务成为可能，从基于位置的推荐系统到先进的安全系统，并提供更个性化的用户体验。

在这篇文章中，我将确定特定的地理区域，从个人到每个用户，看看如何从众多的定位请求中通过获取用户的地理区域来构建基于位置的服务，如在餐馆或咖啡馆的签到。举例来说,系统可以识别一个既定的用户常常吃饭郊游的区域。


使用DBSCAN聚类算法

首先,我们需要选择一种有效的地理数据聚类算法，可以基于提供的数据点的局部密度确定用户的地理位置。DBSCAN算法是一个很好的选择,因为它是通过选择一个点自下而上运行的，会在一个给定的距离寻找更多的点。然后通过重复这个过程扩展寻找新的集群点，直到无法再扩大为止。

这个算法可以调用两个参数:ε，决定寻找一个给定的点附近的多远的点，还有minPoints，决定多少分应该出现在一个给定的点的邻域，以保持给定集群扩展。通过寻找邻近点，本地集群开始出现，各种形状的集群出现了(请参见图1的简化描述)。过于孤立的点和离其他点太远的点被分配到一个特殊的异常值集群。这些识别属性使DBSCAN算法适合集群定位事件。


图1.两个集群显示集群与DBSCAN算法(ε= 0.5和minPoints = 5)。一个是L型，另一个是圆形。接近彼此的点被分配到相同的集群。黑色的孤立点被视为“异常点”。图片来自Natalino Busa。

在Spark里使用PairRDDs

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

在Spark里可以模拟用户定位数据使用对象称为PairRDD。PairRDD是一个分布式的元组集合(键，值)划分到多个机器根据关键字段。特别是对于定位数据，我们选择的关键是用户标识符，和给定用户传递的“签到”聚合列表。

定位数据安排在一个n除以2矩阵，其中第一列表示经度，第二列表示纬度。见下面的一个PairRDD收集的spark数据类型和元组的案例：

[mw_shl_code=applescript,true]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 ))[/mw_shl_code]

DBSCAN和Spark并行

DBSCAN算法可以兼容多种语言和包。下面在GitHub上的代码片段，基于DBSCAN 的，在scala库中实现nlp /nal。

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

[mw_shl_code=applescript,true]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
}[/mw_shl_code]

然后，我们将用Spark来并行dbscan功能以便于进行完整的用户收集。    这个操作作为Spark的PairRDD功能的一部分已经可以使用了，它叫做mapValues：
[mw_shl_code=applescript,true]val clustersRdd = checkinsRdd.mapValues(dbscan(_))[/mw_shl_code]

简而言之，集群定位数据可以在Spark中实现，通过将位置的原始PairRDD转换到一个新的PairRDD，键值的元组代表用户的ID，分别为每个用户定位集群。一旦定位数据被分组到集群，它可以通过确定每个集群的边界框或轮廓进一步总结实例。

图2显示了从一个使用Gowalla,社交网站的匿名用户提取一个示例集群，用户通过在特定地点签到分享他们的位置。图中是佛罗里达地图，特别是Cape Coral的面积，签到的地方会有小色点。



根据事件发生的地理位置我们获得了集群。所以,例如,漫步在Estero Bay  (暗橙色圆点),在机场的场馆(棕色点),和在森尼贝尔岛的场馆(绿点)属于单独的集群(ε设定为3公里，minPoints设置为3)。


图2。集群的一个例子，一个用户使用Gowalla的数据集，佛罗里达Cape Coral区域。注意正确密度的点集合映射到集群，异常值标记为孤立的黑点。图片来自Natalino Busa。地图上色:OpenStreet地图。


进一步增强定位数据分析

这个分析是围绕地理坐标进行的，但可以很容易地扩展到其他属性，如签到时间、场地类型(餐厅、体育馆、博物馆)或用户的地位。聚类算法还可以应用于一个更大的背景，包括用户社交网络的朋友发生的事件。

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

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

Spark产生的聚类分析结果可以保存在数据存储表。一个可以使用API服务查询的表，并在用户提交地点时，确定它属于已知的地区。API服务可以根据使用案例触发一些提示。例如,它可以告知用户警报,通知,或建议。

结论

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

DBSCAN算法结合Spark似乎是一种很有前途的方法，用以提取准确的地理模式，并且能够运用在开发数据驱动、基于位置的应用程序等各种不同领域，如个性化营销、欺诈防范和内容过滤。


来源：http://dataunion.org/22423.html

oh my god