劉峰

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

關(guān)鍵詞： 軌跡數(shù)據(jù)挖掘; 聚類; 可視化; 應(yīng)用

中圖分類號(hào)：TP311.1? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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ā)展的今天，無時(shí)無刻不在產(chǎn)生軌跡數(shù)據(jù)，海量的軌跡數(shù)據(jù)具有很大的研究?jī)r(jià)值，通過對(duì)于軌跡數(shù)據(jù)的聚類分析，能夠?yàn)榻煌肪€優(yōu)化、船舶AIS導(dǎo)航[3]、路網(wǎng)預(yù)測(cè)[6]等提供很好的解決方案。

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

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

1 QuickBundles算法簡(jiǎn)介

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

1.1 軌跡距離度量

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

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

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

因此對(duì)于包含K個(gè)點(diǎn)的兩條軌跡，MDF距離只需要進(jìn)行2K點(diǎn)的距離計(jì)算。MDF距離是對(duì)兩條軌跡的相似度進(jìn)行空間上的度量，顯然MDF距離是非負(fù)的，并且當(dāng)且僅當(dāng)兩條軌跡相同且對(duì)稱時(shí)，計(jì)算的MDF距離為零。

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

1.2 算法實(shí)現(xiàn)

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

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

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

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

具體算法偽代碼如下：

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

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

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

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）

# 計(jì)算MDF距離

if f < d then

d ← f

flipk← 1

end if

alldk← d

end for

m ← min（alld）

l ← argmin（alld）

if m < θ then

# 加入當(dāng)前聚類

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 軌跡聚類方法實(shí)現(xiàn)

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

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

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

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

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包來進(jìn)行軌跡點(diǎn)繪制：

#繪制原始軌跡

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 距離計(jì)算

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

#距離計(jì)算

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

#公式計(jì)算兩點(diǎn)間距離（m）

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

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

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

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算法實(shí)現(xiàn)

我們計(jì)算了兩個(gè)軌跡之間的平均點(diǎn)的實(shí)際距離。這種計(jì)算距離的方法可以在且僅當(dāng)兩個(gè)軌跡具有相同數(shù)量的點(diǎn)時(shí)使用，因此我們需要重新采樣所有軌跡，采樣點(diǎn)數(shù)量可以根據(jù)軌跡數(shù)據(jù)集里每條軌跡平均點(diǎn)數(shù)量來確定。使用上面我們定義的兩條軌跡之間的距離計(jì)算函數(shù)geodistance，這里我們就可以運(yùn)行QuickBundle聚類算法進(jìn)行軌跡聚類，聚類閾值θ可以根據(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 聚類結(jié)果

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)（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].北京交通大學(xué)，2015

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

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

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

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

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

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

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