基于QuickBundles算法的軌跡聚類方法

劉峰

摘? 要： 隨著衛(wèi)星定位傳感器的普及應用，形成了海量移動對象的軌跡數(shù)據(jù)。軌跡數(shù)據(jù)含有豐富的時空特征信息，通過對相關數(shù)據(jù)聚類處理，可以挖掘出移動對象的活動場景、位置等屬性信息。通過借鑒神經(jīng)成像學領域中的QuickBundles算法，介紹算法原理和實現(xiàn)，并基于此算法實現(xiàn)了一種軌跡聚類方法，通過使用實際GPS數(shù)據(jù)對此方法進行驗證，從對聚類結果的可視化展示表明，本方法能夠有效挖掘原始數(shù)據(jù)，完成對軌跡數(shù)據(jù)的聚類。

關鍵詞： 軌跡數(shù)據(jù)挖掘; 聚類; 可視化; 應用

中圖分類號：TP311.1? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2022）04-43-04

Trajectory clustering method based on QuickBundles algorithm

Liu Feng

（Jiangsu Automation Research Institute， Lianyungang， Jiangsu 222002， China）

Abstract： With the popularization of satellite positioning sensors， a large number of trajectory data of moving objects have been formed. The trajectory data contains rich spatio-temporal feature information. By clustering the relevant data， the attribute information such as activity scene and location of moving objects can be mined. By referring to the QuickBundles algorithm in the field of neuroimaging， the principle and implementation of the algorithm are introduced， and a trajectory clustering method is implemented based on this algorithm. This method is verified by using the actual GPS data. Through the visual display of the clustering results， this method can effectively mine the original data and complete the clustering of trajectory data.

Key words： trajectory data mining; clustering; visualization; application

0 引言

在互聯(lián)網(wǎng)高速發(fā)展的今天，無時無刻不在產(chǎn)生軌跡數(shù)據(jù)，海量的軌跡數(shù)據(jù)具有很大的研究價值，通過對于軌跡數(shù)據(jù)的聚類分析，能夠為交通路線優(yōu)化、船舶AIS導航[3]、路網(wǎng)預測[6]等提供很好的解決方案。

經(jīng)典的軌跡聚類算法有基于中心搜索的K-Means算法、基于密度的DBSCAN算法[2]以及基于層次的BIRCH算法等[8]，但是K-Means算法中需要選擇起始中心點和聚類的個數(shù)，并且不同的中心點的選取對最后的結果影響很大，而DBSCAN算法對均勻密度的樣本效果很好，但是對線性樣本則效果不佳。

大多數(shù)的聚類算法的時間復雜度為O（N2），其中N是需要進行聚類的軌跡數(shù)量，而本文則借鑒神經(jīng)成像學領域中，用于對磁共振成像中得到的白質纖維進行聚類所采用的QuickBundles算法[1]，把需要進行聚類的軌跡視為蛋白質纖維，然后在同一個聚類中合并相似度高的軌跡。

1 QuickBundles算法簡介

QuickBundles是一種非常的簡單和快速的算法，它可以在線性時間內(nèi)將N條軌跡進行聚類。在QB算法中，每個軌跡都被定義成固定長度的有序點序列，使用比較函數(shù)和合并來進行軌跡聚類。通過計算此條軌跡與當前存在的軌跡集群之間的距離，來判單是否需要將這條軌跡加入此集群，同時軌跡集群保存在一個根據(jù)需要擴展的列表中。與其他聚類算法不同，如k-Means或BIRCH，QB中沒有重新分配或更新階段，一旦一條軌跡被分配到一個集群，它就停留在那里，并且集群不會合并，QB的速度和效率正是源于這個思想。

1.1 軌跡距離度量

軌跡距離度量是整個軌跡聚類的基礎，這里我們使用了一個相當簡單的對稱距離函數(shù)，簡稱為最小平均直接翻轉距離（MDF），我們定義軌跡S=[S1，S2，…，SK]等價于兩條有序折線：S =[S1，S2，…，SK]和它的翻轉版本SF=（SK， SK?1，…，S1），在這種表示法下，直接距離、翻轉距離和MDF距離計算方式如下：

|x?y|表示兩個經(jīng)緯度點x和y之間的距離，直接距離d（s，t）是指兩條軌跡s和t對應點之間距離的均值。

不過只有當兩條軌跡具有相同的軌跡點數(shù)量時，才可以使用MDF距離進行計算。使用MD來計算兩點軌跡之間距離時，需要先通過簡單的線性插值算法，使得任意兩條軌跡具有相同的數(shù)量軌跡點，并且使得每條軌跡的所有段具有相等的長度。

因此對于包含K個點的兩條軌跡，MDF距離只需要進行2K點的距離計算。MDF距離是對兩條軌跡的相似度進行空間上的度量，顯然MDF距離是非負的，并且當且僅當兩條軌跡相同且對稱時，計算的MDF距離為零。

MDF距離的主要優(yōu)點是計算效率高，通過對兩條軌跡的直接距離和翻轉距離的計算，來對軌跡的相似度進行度量，可以非常輕松地解決從最簡單的平行軌跡到最復雜的發(fā)散軌跡的情況。

1.2 算法實現(xiàn)

QB算法在聚類節(jié)點中存儲關于軌跡聚類的信息，我們將軌跡從1到N進行編號，其中Si是代表第i條軌跡。聚類節(jié)點被定義為三元組c=（I，h，n），其中I是整數(shù)索引i=1到N的列表，n為該聚類中的軌跡數(shù)量，h為軌跡距離和。h是一個K×3矩陣，當一條軌跡被添加到一個聚類時，它可以在線更新，并且等于：

在算法的任何一步，我們都有M個clusters（集合）。選擇第一條軌跡S1并將其放在第一個clusters，C1←（{1}，S1，1）;此時M=1，對于每個剩余的軌跡，依次i=2，…，N：

i. 計算軌跡 Si與所有當前聚類 Ce 的質心軌跡Ve之間的MDF距離，其中e=1，…，M，這里定義群集節(jié)點的質心軌跡為V，其中V=h/n;

ii. 如果任何距離的值Me小于聚類閾值θ，將軌跡i添加到聚類e中，最小值為Me;Ce=（I，h，n），并更新Ce←（append（I，i），h+s，n+1）; 否則創(chuàng)建一個新的cluster CM+1←（[i]，si，1），M←M+1。

具體算法偽代碼如下：

輸入：T = {s，…，s，…，s}，θ

輸出：C = [c，…，c，…，c]

# 創(chuàng)建第一個聚類

c1 ← （[1]，s1，1）

C ← [c1]

M ← 1

for i = 2 to Ndo

t ← s

alld ←infinity（M） #距離緩沖區(qū)

flip ← zeros（M） #MDF檢查緩沖區(qū)

for k = 1 to M do

v ← c·h/c·n

d ← d（t，v）

f ← d（t，v）

# 計算MDF距離

if f < d then

d ← f

flipk← 1

end if

alldk← d

end for

m ← min（alld）

l ← argmin（alld）

if m < θ then

# 加入當前聚類

if flip is 1 then

cl·h ← c·h + tF

else

cl·h ← c·h + t

end if

cl·n ← cl·n + 1

append（cl·I，i）

else

# 創(chuàng)建新的聚類

c ← （[i]，t，1）

append（C，c）

M ← M+1

end if

end for

2 軌跡聚類方法實現(xiàn)

原始數(shù)據(jù)采用微軟亞洲研究院發(fā)布的GeoLife GPS Trajectories數(shù)據(jù)集，來進行軌跡聚類，考察用QB算法的運行效果，這里我們選擇Geolife Trajectories 1.3＼Data＼010＼Trajectory數(shù)據(jù)。

2.1 數(shù)據(jù)清理

首先我們需要對獲得的數(shù)據(jù)進行清理，GeoLife GPS Trajectories數(shù)據(jù)集里數(shù)據(jù)組織如圖1所示。

定義相關標簽，并讀取所有數(shù)據(jù)文件，將獲取到的GPS經(jīng)緯度點信息保存：

names=['lat'，'lng'，'zero'，'alt'，'days'，'date'，'time']

streams=[]

index=0

userdata='./Geolife Trajectories 1.3/Data/'+'010'+'/Trajectory/'

filelist=os.listdir（userdata）

for file in filelist：

df_list=[pd.read_csv（userdata+file，header=6，

names=names，index_col=False）]

df=pd.concat（df_list， ignore_index=True）

df.drop（['zero'，'alt'，'days'，'date'，'time']，axis=1，inplace=True）

df_min=df.iloc[：：， ：]

lat_lng_data=np.c_[df_min['lat'].values，df_min['lng'].values]

streams.append（lat_lng_data）

print（streams[0][0，0]， streams[0][0，1]）

聚類之前先繪制原始軌跡，這里采用gmplot包來進行軌跡點繪制：

#繪制原始軌跡

from gmplot import gmplot

gmap=gmplot.GoogleMapPlotter（streams[0][0，0]，

streams[0][0，1]，12）

color=randomcolor（）

for i in range（0， len（streams））：

gmap.plot（streams[i][：，0]，

streams[i][：，1]， color， edge_width=1）

gmap.draw（"normal_map.html"）

待處理的原始軌跡如圖2所示。

2.2 距離計算

我們現(xiàn)在可以從定義兩個GPS軌跡之間的距離函數(shù)開始，我們將使用大地坐標系計算公式來代替QuickBundle算法中的經(jīng)典歐幾里得距離計算公式，計算兩個經(jīng)緯度點之間的距離。

#距離計算

from math import radians， cos， sin， asin， sqrt

#公式計算兩點間距離（m）

def geodistance（lat1，lng1，lat2，lng2）：

lng1， lat1， lng2， lat2=map（radians， [float（lng1），

float（lat1）， float（lng2）， float（lat2）]） #經(jīng)緯度轉換成弧度

dlon=lng2-lng1

dlat=lat2-lat1

a=sin（dlat/2）**2 + cos（lat1）*cos（lat2）*sin（dlon/2）**2

distance=2*asin（sqrt（a））*6371*1000

#地球平均半徑，6371km

distance=round（distance/1000，3）

return distance

2.3 QB算法實現(xiàn)

我們計算了兩個軌跡之間的平均點的實際距離。這種計算距離的方法可以在且僅當兩個軌跡具有相同數(shù)量的點時使用，因此我們需要重新采樣所有軌跡，采樣點數(shù)量可以根據(jù)軌跡數(shù)據(jù)集里每條軌跡平均點數(shù)量來確定。使用上面我們定義的兩條軌跡之間的距離計算函數(shù)geodistance，這里我們就可以運行QuickBundle聚類算法進行軌跡聚類，聚類閾值θ可以根據(jù)需要聚類效果靈活選取。

#qb聚類

import geopy.distance

from dipy.segment.metric import Metric

from dipy.segment.metric import ResampleFeature

import numpy as np

from dipy.segment.clustering import QuickBundles

class GPSDistance（Metric）：

def __init__（self）：

super（GPSDistance， self）.__init__（feature=

ResampleFeature（nb_points=256））

def are_compatible（self， shape1， shape2）：

return len（shape1）==len（shape2）

def dist（self， v1， v2）：

x=[geodistance（p[0][0]， p[0][1]， p[1][0]， p[1][1]）

for p in list（zip（v1， v2））]

currD=np.mean（x）

return currD

THERSHOLD=10? ?#km

metric=GPSDistance（）

qb=QuickBundles（threshold=THERSHOLD， metric=metric）

clusters=qb.cluster（streams）

print（"Nb.clusters："， len（clusters））

2.4 聚類結果

如圖3所示，對θ分別選擇5、10、25、100得到的聚類結果，通過對軌跡結果的可視化展示[9]，可見，θ越大，得到的聚類數(shù)量越少，對軌跡壓縮效果也越高，同時損失的原始軌跡數(shù)據(jù)也越多。

3 結束語

本文借鑒了神經(jīng)成像學領域中的QuickBundles算法，提出一種應用該算法對海量軌跡點進行聚類的方法，同時采用微軟亞洲研究院發(fā)布的GeoLife GPS Trajectories數(shù)據(jù)集對聚類的方法進行驗證，通過對聚類結果的可視化分析，該方法能夠有效地對軌跡進行聚類，得到的結果和實際物體軌跡相符合。

參考文獻（References）：

[1] Garyfallidis Eleftherios，Brett Matthew，Correia MartaMorgado，Williams Guy B，Nimmo-Smith Ian. QuickBundles， a Method for Tractography Simplification[J]. Frontiers in neuroscience，2012，6

[2] 陳艷君.面向海量軌跡數(shù)據(jù)的聚類算法研究[D].北京交通大學，2015

[3] 肖瀟.基于AIS信息的船舶軌跡聚類模型研究[D].集美大學，2015

[4] 魏照坤.基于AIS的船舶軌跡聚類與應用[D].大連海事大學，2015

[5] 程智源.基于軌跡聚類的交通熱點分析[D].電子科技大學，2018

[6] 馮琦森.基于出租車軌跡的居民出行熱點路徑和區(qū)域挖掘[D].重慶大學，2016

[7] 甘波.基于海量物流軌跡數(shù)據(jù)的分析挖掘系統(tǒng)[D].武漢理工大學，2014

[8] 許佳捷，鄭凱，池明旻，等.軌跡大數(shù)據(jù)：數(shù)據(jù)、應用與技術現(xiàn)狀[J].通信學報，2015（12）：97?105

[9] 王祖超，袁曉如.軌跡數(shù)據(jù)可視分析研究.計算機輔助設計與圖形學學報，2015（1）：9?25