機器學習，特别是聚類算法，可以用來确定哪些地理區域經常被一個使用者通路和簽到而哪些區域不是。這樣的地理分析使多種服務成為可能，比如基于地理位置的推薦系統，先進的安全系統，或更通常來說，提供更個性化的使用者體驗。
在這篇文章中，我會确定對每個人來說特定的地理活動區域，讨論如何從大量的定位事件中（比如在餐廳或咖啡館的簽到）擷取使用者的活動區域來建構基于位置的服務。舉例來說，這種系統可以識别一個使用者經常外出吃晚飯的區域。
首先，我們需要選擇一種适用于定位資料的聚類算法，可以基于提供的資料點的局部密度确定使用者的活動區域。dbscan算法是一個不錯的選擇，因為它自下而上地選擇一個點并在一個給定的距離尋找更多的點。然後通過重複這個過程擴充尋找新的點來擴充類簇，直到無法再擴大為止。
這個算法可以通過兩個參數進行調試: ε，用來确定離給定的點多遠來搜尋；和minpoints，即為了類簇擴充，決定一個給定的點的鄰域附近最少有多少點。通過尋找鄰近點，本地類簇開始出現，各種形狀的類簇逐漸可以被識别(請參見圖1的簡化描述)。過于孤立的點和離其他點太遠的點則會被配置設定到一個特殊的異常值叢集。這些獨特的屬性使dbscan算法适合對地理定位事件進行聚類。
圖1：兩由dbscan算法(ε= 0.5和minpoints = 5)聚類得出的兩個類簇。一個是l型，另一個是圓形。互相靠近的點被配置設定到相同的類簇。黑色的孤立點被視為“異常點”。圖檔來自natalino busa。
在大多數實際應用中，機器學習系統必須處理數以百萬計的使用者和數十億的事件。是以，随着越來越多的使用者和事件被添加到系統中，一個精心設計的資料處理通道需要具備快速和可伸縮的特點。這就需要分布式計算。就我們的目标而言，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算法在多種語言和包裡都有實作。下面的代碼片段是基于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和機器學習的統一架構。這種擴充的資料管道對特定類别的事件将提供更準确的聚類結果。
spark産生的聚類分析結果可以儲存在一個資料存儲表中。一個api服務可以查詢該表，并确定一個新出現的地理位置點是否屬于已知的地區。api服務可以根據使用者場景觸發适當的行為。例如，它可以通過消息向使用者告警、發送通知或提供推薦。
我最初的實驗表明spark提供了堅實的基礎設施在大量的使用者和事件上來并行處理和分發機器學習算法。此外，spark通過在一個資料處理架構結合sql查詢和機器學習，加快了資料驅動系統的開發。
dbscan算法與spark的結合似乎是一種很有前途的方法，可以抽取準确的地理位置模式，并用于開發基于各種場景的資料驅動、基于位置的應用程式，例如個性化營銷、欺詐防範和内容過濾。
原文釋出時間為：2017-01-21
本文來自雲栖社群合作夥伴“大資料文摘”，了解相關資訊可以關注“bigdatadigest”微信公衆号