當我們想要利用智能手機或智能手環等個人裝置生成的GPS資料時,G PS軌迹聚類是一種常見的分析。
在本文中,我們将介紹一種在Python中執行GPS軌迹聚類的快速簡便方法。這裡的主要目标是建立包含“相似”軌迹的聚類。例如,我們希望将每天從工作到家的路徑放在同一個聚類中。
本文分為兩個主要部分。首先,我們将描述聚類算法。在第二部分中,我們将展示如何在Python中使用和自定義算法。
神經圖像算法與GPS軌迹聚類
在本文中,我們使用了一種用于neuromaging的聚類算法,而不是像K-Means或DBSCAN那樣使用經典的聚類算法。
QuickBundles (QB)是一種簡單的聚類算法,用于磁共振成像中對應用tractography算法得到的白質纖維進行聚類。
隻需檢視下圖,我們就可以看到大腦中的白質纖維看起來像GPS軌迹。
應用tractography算法獲得的白質纖維的執行個體
主要思想是将每個GPS軌迹視為白質纖維,然後在同一個聚類中合并“相似”軌迹。在本文的其餘部分,我們将假設GPS Trajectory = White Matter Fiber。
有了這個假設,我們就可以使用原始論文中提供的算法描述:算法如下進行。在算法的任何一步,我們都有 M個clusters。選擇第一個streamline s1并将其放在第一個cluster c1 ←({1},s1,1); 此時M = 1。對于每個剩餘的streamlines,依次 i = 2 ,. 。。,N:
(i)計算streamline si與所有目前聚類 ce 的質心streamline ve之間的距離 , e = 1 ,. 。。,M,其中v動态定義為v = h/n;
(ii)如果任何距離的值me小于聚類門檻值θ,,将streamlined i添加到聚類e,最小值為me; ce =(I,h,n),并更新 ce ←(append(I, i), h + s, n + 1); 否則建立一個新的cluster cM + 1 ←([i],si,1),M←M + 1.
在下圖中,我們展示了算法如何根據給定的門檻值合并公共質心中的不同streamlines 的示例。
QuickBundle質心具有不同的門檻值
門檻值是THE要選擇的參數,以優化聚類算法的行為。如果你想要“大”軌迹,你可以設定門檻值的高值。否則,如果您想要小聚類,則需要較低的值。
該論文的作者提供了所提出方法的Python實作。該算法作為dipy庫的一部分提供,而算法的文檔可在此處獲得(http://nipy.org/dipy/examples_built/segment_quickbundles.html#)。
GPS軌迹聚類
我們使用的資料集來自微軟亞洲研究院釋出的GeoLife GPS Trajectories資料集,可在此處獲得(https://www.microsoft.com/en-us/download/details.aspx?id=52367)。該資料集文檔:https://yidatao.github.io/2016-12-23/geolife-dbscan/。
在開始執行聚類之前,讓我們使用gmplot繪制谷歌地圖上的所有軌迹。
資料集中的GPS軌迹
我們現在可以從定義兩個GPS軌迹(streamlines)之間的距離函數開始。我們将使用GeoPy庫中定義的GPS距離,而不是使用QuickBundle中提供的經典歐幾裡得距離。
我們計算了兩個軌迹之間的平均點的GPS距離。這種計算距離的方法可以在且僅當兩個軌迹具有相同數量的點時使用,這就是為什麼我們使用ResampleFeature類重新采樣所有軌迹的原因。
一旦定義了兩條軌迹之間的距離,就可以運作QuickBundle聚類算法。
用于運作軌迹聚類的代碼
然後,我們可以像以前一樣使用gmplot繪制谷歌地圖上不同聚類中包含的軌迹。
使用gmplot聚類圖
這裡是my_map.html的結果,用于繪制不同的聚類
Cluster #0
Cluster #2
Cluster #30
結論
在本文中,我們描述了一種簡單快速的方法來執行GPS資料的軌迹聚類。目标是使用QuickBundles實作的,QuickBundles是一種應用于神經成像的聚類算法。
該算法的主要限制與門檻值參數的調整有關。但是,作為資料分析中的所有内容,需要根據所需的群集類型選擇此參數。