882
技術社區[雲棲]
用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的結合似乎是一種很有前途的方法，可以抽取準確的地理位置模式，並用於開發基於各種場景的數據驅動、基於位置的應用程序，例如個性化營銷、欺詐防範和內容過濾。
原文發布時間為：2017-01-21
本文來自雲棲社區合作夥伴“大數據文摘”，了解相關信息可以關注“BigDataDigest”微信公眾號
最後更新：2017-05-25 09:02:35