用Spark/DBSCAN做地理定位數據聚類

本文為數盟原創譯文，歡迎轉載，注明出處“數盟社區”即可

如何利用機器學習和分布式計算來對用戶事件進行分類

作者：Natalino Busa

機器學習，特別是聚類算法，可以用來確定哪些地理區域被一個給定的用戶經常訪問和“入住”而哪些區域不是。這樣的地理分析使范圍廣泛的服務成為可能，從基于位置的推薦系統到先進的安全系統，并提供更個性化的用戶體驗。

在這篇文章中，我將確定特定的地理區域，和個人向每個用戶，看看如何從眾多的定位請求，通過獲取用戶的地理區域來構建基于位置的服務，如在餐館或咖啡館的簽到。舉例來說,系統可以識別一個既定的用戶常常吃飯郊游的區域。

使用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數據類型和元組的案例：

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

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算法可以兼容多種語言和包。下面在GitHub上的代碼片段，基于DBSCAN 的，在scala庫中實現nlp /nal。

假設給定用戶經常訪問城市的三個區域，一個經常來參加酒宴和聚會，另一個經常來舒適放松，還有一個和朋友一起吃晚餐。如果這些區域位于城市的不同部分,下面的代碼通過觀察每個位置將不同集群的事件區分。在這段代碼中,我們尋找距離約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
}

importbreeze.numerics._
importnak.cluster._
importnak.cluster.GDBSCAN._
 
defdbscan(v : breeze.linalg.DenseMatrix[Double]) = {
  valgdbscan = new GDBSCAN(
    DBSCAN.getNeighbours(epsilon = 0.001, distance = Kmeans.euclideanDistance),
    DBSCAN.isCorePoint(minPoints = 3)
  )
  valclusters = gdbscancluster v
}

然后，我們將用Spark來并行dbscan功能以便于進行完整的用戶收集。    這個操作作為Spark的PairRDD功能的一部分已經可以使用了，它叫做mapValues：

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

valclustersRdd = checkinsRdd.mapValues(dbscan(_))

簡而言之，集群定位數據可以在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似乎是一種很有前途的方法，用以提取準確的地理模式，并且能夠運用在開發數據驅動、基于位置的應用程序等各種不同領域，如個性化營銷、欺詐防范和內容過濾。

原文鏈接： https://www.oreilly.com/ideas/clustering-geolocated-data-using-spark-and-dbscan?推ter=@bigdata