基于加權(quán)矢量場(chǎng)的軌跡層次聚類*

陳 琳， 王 蒙

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500)

基于加權(quán)矢量場(chǎng)的軌跡層次聚類*

陳 琳， 王 蒙

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500)

傳統(tǒng)的軌跡聚類方法存在定義軌跡相似度難度大，聚類過程中容易忽略軌跡細(xì)節(jié)等問題?；谑噶繄?chǎng)的軌跡聚類(VFC)在保持軌跡原始運(yùn)動(dòng)特征的基礎(chǔ)上，利用矢量場(chǎng)的幾何結(jié)構(gòu)可以很好地度量軌跡相似度。引入加權(quán)擬合方法，降低噪聲對(duì)聚類的影響，以解決VFC魯棒性較差問題。采用層次聚類動(dòng)態(tài)地決定聚類類別數(shù)，以解決聚類類別數(shù)不能自適應(yīng)的問題，提高聚類有效性。采用亞特蘭大颶風(fēng)數(shù)據(jù)作為實(shí)驗(yàn)原始軌跡數(shù)據(jù)，分別使用經(jīng)典矢量場(chǎng)的軌跡聚類，k-means聚類，k-mediods聚類以及提出的方法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明了加權(quán)擬合矢量場(chǎng)的層次聚類算法的有效性。

軌跡； 矢量場(chǎng)聚類； 加權(quán)擬合； 層次聚類

0 引 言

軌跡是對(duì)一個(gè)移動(dòng)對(duì)象位置和時(shí)間的記錄序列。作為一種重要的時(shí)空對(duì)象數(shù)據(jù)類型和信息源，軌跡的應(yīng)用范圍涵蓋了人類行為、交通物流、應(yīng)急疏散管理和動(dòng)物習(xí)性等諸多方面。生態(tài)學(xué)家通過學(xué)習(xí)動(dòng)物的運(yùn)動(dòng)，來獲取動(dòng)物種群的增長(zhǎng)，遷徙模式[1]。氣象學(xué)家通過軌跡數(shù)據(jù)來幫助預(yù)測(cè)風(fēng)暴的路徑[2]。

目前，軌跡聚類的方法主要包括兩類，一類是將軌跡嵌入到一個(gè)度量空間中，定義軌跡的相似度概念，使用基于軌跡點(diǎn)的聚類。Lee J G等人[3]提出關(guān)于軌跡聚類的新的分割與群組的框架，將一條軌跡劃分成不同的段，然后將相似的段聚到一類中。Gudmundsson J等人[4]將多個(gè)領(lǐng)域的軌跡數(shù)據(jù)嵌入運(yùn)動(dòng)空間進(jìn)行概念建模,該方法的缺點(diǎn)是，定義軌跡相似度難度大，容易忽略軌跡中細(xì)節(jié)的部分。另一類是基于模型的方法,Wei J等人[5]擴(kuò)展和并行化回歸模型對(duì)大量軌跡進(jìn)行聚類。Gaffney S J等人[6]采用曲線混合模型對(duì)經(jīng)緯度空間的冬季溫帶氣旋進(jìn)行概率聚類。這種方法模型適應(yīng)性不強(qiáng)，軌跡數(shù)據(jù)不同需要的聚類模型不同。

基于矢量場(chǎng)軌跡聚類(VFC)方法，可以有效地解決上述定義軌跡相似度難度大，容易忽略軌跡中細(xì)節(jié)部分和算法適應(yīng)性不強(qiáng)等問題。VFC算法利用軌跡的幾何結(jié)構(gòu)來自動(dòng)編碼軌跡特征，從而度量軌跡相似度，很好地保留軌跡原有特征。Ferreira N等人[7]通過VFC算法，研究臺(tái)風(fēng)運(yùn)動(dòng)與GPS行人追蹤等。Brillinger D R等人[8]利用VFC算法研究動(dòng)物的運(yùn)動(dòng)規(guī)律。Camargo S J[9]利用VFC算法研究臺(tái)風(fēng)的活動(dòng)規(guī)律。文獻(xiàn)[7～9]存在聚類類別不能自適應(yīng)，沒有考慮采集軌跡過程中的量測(cè)噪聲，算法魯棒性差等問題。

針對(duì)上述VFC算法中聚類類別數(shù)不能自適應(yīng)的問題，本文提出了層次聚類的方法。將矢量場(chǎng)作為聚類依據(jù)，通過設(shè)置閾值使算法自動(dòng)對(duì)軌跡進(jìn)行分類。針對(duì)算法魯棒性差，易受噪聲干擾的問題，提出加權(quán)擬合矢量場(chǎng)的方法。給噪聲數(shù)據(jù)分配較小的權(quán)重，減小噪聲數(shù)據(jù)對(duì)矢量場(chǎng)擬合的影響。通過實(shí)驗(yàn)對(duì)基于加權(quán)矢量場(chǎng)的軌跡層次聚類(WVFHC)進(jìn)行驗(yàn)證，效果較好。

1 基于加權(quán)矢量場(chǎng)的軌跡層次聚類算法

1.1 數(shù)據(jù)預(yù)處理

點(diǎn)bsj(x,y)為軌跡Ti上一坐標(biāo)點(diǎn)，點(diǎn)Q11(x11,y11),Q12(x12,y12),Q21(x21,y21),Q22(x22,y22)為bsj(x，y)周圍最近的4個(gè)坐標(biāo)點(diǎn)如圖1(a)。定義dx=x-[x],dy=y-[y]，則點(diǎn)Q11(x11,y11)，Q12(x12,y12)，Q21(x21,y21)，Q22(x22,y22)可以通過bsj(x,y)表示

Q11(x11,y11)=bsj(x,y)·dx·(1-dy)

(1)

Q21(x21,y21)=bsj(x,y)·dx·dy

(2)

Q22(x22,y22)=bsj(x,y)·(1-dx)·dy

(3)

Q12(x12,y12)=bsj(x,y)·(1-dx)·(1-dy)

(4)

圖1 雙線性插值和拉普拉斯貝特拉米算子

1.2 軌跡數(shù)據(jù)矢量場(chǎng)擬合

假設(shè)對(duì)于一組軌跡數(shù)據(jù)α={T1,T2,…,Tn}存在一組平滑的矢量場(chǎng)Xj來解釋這組軌跡中的移動(dòng)規(guī)律,即需要找到矢量場(chǎng)Xj與類別集合Φ∶α→{1,2,…,k}來解釋該組軌跡的移動(dòng)規(guī)律。

如圖1(b)所示采用拉普拉斯貝特拉米算子L作為平滑矩陣對(duì)矢量場(chǎng)進(jìn)行平滑

(5)

則該組軌跡的移動(dòng)規(guī)律可以表示為

(6)

式中L為拉普拉斯余切矩陣；Xj為擬合之后的矢量場(chǎng)。

用矩陣的形式表示并進(jìn)行最小二乘擬合，定義能量函數(shù)E，則式(6)可化簡(jiǎn)為求E=‖LX‖2+‖CX-b‖2的最小值,其中，C為網(wǎng)格數(shù)據(jù)，b為原始軌跡數(shù)據(jù)。

1.3 軌跡數(shù)據(jù)加權(quán)矢量場(chǎng)擬合

在軌跡數(shù)據(jù)采集過程中設(shè)備誤差可能會(huì)生成存在噪聲的軌跡數(shù)據(jù)，若直接運(yùn)算，可能對(duì)聚類結(jié)果產(chǎn)生影響,進(jìn)行加權(quán)擬合，會(huì)降低噪聲對(duì)聚類結(jié)果的影響。加權(quán)矢量場(chǎng)擬合的核心部分為權(quán)值的確定，權(quán)值通過調(diào)諧常數(shù)cH與局部估計(jì)噪聲偏差σ共同確定[10，11]。其中

σ=1.482 6 med|ri-medri|

(7)

式中 ri為第i個(gè)數(shù)據(jù)點(diǎn)的殘差。

(8)

式中cH為調(diào)諧常數(shù)，取固定值1.345;wH,i為權(quán)重矩陣。

通過迭代更新權(quán)值矩陣wH,i，定義停止準(zhǔn)則F(l)來停止迭代過程

(9)

式中l(wèi)為當(dāng)前迭代過程。當(dāng)?shù)趌次迭代過程與第l-1次迭代過程的差值小于0.001時(shí)，迭代收斂，即

|F(l)-F(l-1)|<0.001，l=1,2,…

(10)

對(duì)能量函數(shù)E中的擬合部分進(jìn)行加權(quán),即

E=‖LX‖2+‖W(CX-b)‖2

(11)

X=(LTL+CTWTWC)CTWTWb

(12)

式中W為權(quán)重矩陣。

1.4 矢量場(chǎng)層次聚類

VFC算法聚類類別數(shù)需提前設(shè)定，適應(yīng)性較差。使用層次聚類，通過設(shè)置閾值動(dòng)態(tài)地決定聚類類別數(shù)，提高算法的適應(yīng)性。

WVFHC算法步驟如下：

1)輸入：軌跡數(shù)據(jù)α={T1,T2,…,Tn},th;

2)初始化：根據(jù)1.1節(jié)將軌跡數(shù)據(jù)映射到網(wǎng)格Ci上，i=1;

3)根據(jù)式(12)由Ci得到Xi;

4)i=i+1;

5)若i

6)采用層次聚類方法，根據(jù)聚類閾值th對(duì)V聚類得到M類，Φj={Φj,j=1,2,3,…,M}(M不固定)，且{Xi,i∈Φj};

7)分別輸出聚類后的矢量場(chǎng)Yj。

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)設(shè)計(jì)與評(píng)價(jià)指標(biāo)

用文獻(xiàn)[7]中的颶風(fēng)數(shù)據(jù)以及人造數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)。用颶風(fēng)數(shù)據(jù)進(jìn)行了VFC算法，k-means[12～14]算法，k-medoids[15]算法以及VFHC算法實(shí)驗(yàn)。用人造數(shù)據(jù)進(jìn)行了VFHC算法與WVFHC算法實(shí)驗(yàn)。

采用4種性能評(píng)價(jià)指標(biāo)[16]：RS(R-Squares)[17，18],CH指數(shù)(Calinski-Harabaszindex)[19],DB指數(shù)(Davies-Bouldinindex)[20]與修正的HubertГ統(tǒng)計(jì)(ModifiedHubertΓstatistic)[21]。QCH，QRS，QГ值越高聚類結(jié)果越準(zhǔn)確,QDB值越小聚類結(jié)果越準(zhǔn)確。

2.2 實(shí)驗(yàn)結(jié)果與分析

2.2.1 真實(shí)數(shù)據(jù)集

利用文獻(xiàn)[7]中的颶風(fēng)數(shù)據(jù)作為真實(shí)數(shù)據(jù)集，包含1 415條軌跡。

設(shè)置不同的閾值，得到不同的聚類類別數(shù)，結(jié)果如表1所示,NC為聚類類別數(shù)。圖2(a)～(d)為評(píng)價(jià)指標(biāo)折線圖，可以看出:在閾值為“1.5”時(shí)，QDB發(fā)生異常變化，其他指標(biāo)沒有出現(xiàn)異常，所以閾值為“2.5”，“2”與“1.8”時(shí)，聚類效果較好，對(duì)應(yīng)的類別數(shù)分別為“4”，“5”與“6”。

圖2(e)～(h)為4種算法評(píng)價(jià)指標(biāo)直方圖，可以看出:在聚類類別數(shù)為“4”，“5”，“6”時(shí)。VFHC算法的聚類效果更好。因?yàn)樵诰垲愵悇e數(shù)較小時(shí)，k-means算法,k-medoids算法與VFC算法固定了聚類類別數(shù)，使每一類中的軌跡數(shù)據(jù)方差變大，所以聚類效果較差。VFHC算法通過閾值獲取聚類類別，每一類中的軌跡數(shù)據(jù)相似度更高，所以聚類效果更好。圖4為VFHC算法在閾值為2.5時(shí)各類別的矢量場(chǎng)圖。

圖2 實(shí)驗(yàn)結(jié)果

圖3 實(shí)驗(yàn)數(shù)據(jù)

圖4 閾值為2.5時(shí)各類的矢量場(chǎng)圖

閾值評(píng)價(jià)指標(biāo)QCHQDBQRSQГ2．5(NC=4)7．64×1050．00280．0888851．97782(NC=5)9．54×1050．00170．010971．90081．8(NC=6)1．18×1060．03180．16595．81991．5(NC=7)1．35×106183．50470．21123．18881．3(NC=9)1．57×106108．77830．2102183．1176

2.2.2 人造數(shù)據(jù)集

從颶風(fēng)數(shù)據(jù)中隨機(jī)選取142條軌跡，加入噪聲得到人造數(shù)據(jù)集。原始軌跡數(shù)據(jù)與噪聲軌跡數(shù)據(jù)如圖3(b)，圖3(c)所示。將人造數(shù)據(jù)替換原來的軌跡數(shù)據(jù)作為人造數(shù)據(jù)集。采用加權(quán)擬合與不加權(quán)擬合得到矢量場(chǎng)，進(jìn)行層次聚類。

圖2(i)～(l)為評(píng)價(jià)指標(biāo)直方圖，可以看出，WVFHC算法的聚類效果好。因?yàn)榧尤朐肼暫螅琕FHC算法將異常數(shù)據(jù)作為正常數(shù)據(jù)進(jìn)行矢量場(chǎng)擬合，影響聚類結(jié)果。而WVFHC算法通過給異常數(shù)據(jù)分配較小的權(quán)重，降低異常數(shù)據(jù)的影響，所以聚類效果較好。

3 結(jié) 論

本文提出WVFHC方法，對(duì)真實(shí)軌跡數(shù)據(jù)與人造軌跡數(shù)據(jù)進(jìn)行聚類。VFHC方法能夠解決VFC算法聚類類別數(shù)不能自適應(yīng)的問題。通過與k-means算法，k-medoids算法，VFC算法的實(shí)驗(yàn)對(duì)比得出，在聚類類別較小時(shí)效果較好，但在聚類類別較大時(shí)效果較差。通過WVFHC方法對(duì)人造軌跡數(shù)據(jù)進(jìn)行聚類，能夠降低噪聲的干擾，增強(qiáng)算法的魯棒性。通過與VFHC算法的對(duì)比得出，WVFHC算法效果更好。在今后的研究中，研究重點(diǎn)為改進(jìn)WVFHC算法，增強(qiáng)算法的適應(yīng)性。

[1] Grundy E,Jones M W,Laramee R S,et al.Visualisation of sensor data from animal movement[J].Computer Graphics Forum,2009,28(3):815-822.

[2] Camargo S J,Robertson A W,Gaffney S J,et al.Cluster analysis of typhoon tracks[J].Journal of Climate,2007,20(14):3654-3676.

[3] Lee J G,Han J,Whang K Y.Trajectory clustering:A partition-and-group framework[C]∥Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data,ACM,2007:593-604.

[4] Gudmundsson J,Laube P,Wolle T.Computational movement analysis[M].Berlin Heidelberg：Springer,2012:423-438.

[5] Wei J,Wang C,Yu H,et al.A sketch-based interface for classi-fying and visualizing vector fields[C]∥2010 IEEE Pacific Visua-lization (PacificVis)Symposium,IEEE,2010:129-136.

[6] Gaffney S,Smyth P.Trajectory clustering with mixtures of regression models[C]∥Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,ACM,1999:63-72.

[7] Ferreira N,Klosowski J T,Scheidegger C E,et al.Vector fieldk-means:Clustering trajectories by fitting multiple vector field-s[C]∥Computer Graphics Forum,2013:201-210.

[8] Brillinger D R,Preisler H K,Ager A A,et al.An exploratory data analysis(EDA)of the paths of moving animals[J].Journal of Statistical Planning and Inference,2004,122(1):43-63.

[9] Camargo S J,Robertson A W,Gaffney S J,et al.Cluster analysis of typhoon tracks—Part II:Large-scale circulation and ENSO[J].Journal of Climate,2007,20(14):3654-3676.

[10] Meer P,Mintz D,Rosenfeld A,et al.Robust regression methods for computer vision:A review[J].International Journal of Computer Vision,1991,6(1):59-70.

[11] 嚴(yán)筱永,錢煥延,施衛(wèi)娟,等.一種利用統(tǒng)計(jì)中值的加權(quán)定位算法[J].傳感器與微系統(tǒng),2011,30(8):120-123.

[12] MacQueen J B.On the asymptotic behavior ofk-means[R].Los Angeles:Western Management Science Inst,Univ of California at Los Angeles,1965.

[13] 王聯(lián)國(guó),韓曉慧,宋 磊.基于改進(jìn)混合蛙跳-K均值聚類算法的無(wú)功電壓控制分區(qū)[J].傳感器與微系統(tǒng),2013,32(6):18-21.

[14] 張乙竹,周禮爭(zhēng),唐 瑞,等.基于k-means聚類點(diǎn)密度的WSNs加權(quán)質(zhì)心定位算法[J].傳感器與微系統(tǒng),2015,34(7):125-127.

[15] Kaufman L,Rousseeuw P.Clustering by means of medoids[M].Amsterdam:North-Holland Publisher,1987.

[16] Liu Y,Li Z,Xiong H,et al.Understanding of internal clustering validation measures[C]∥2010 IEEE 10th International Confe-rence on Data Mining(ICDM),IEEE,2010:911-916.

[17] Sharma S.Applied multivariate techniques[M].New York:John Wiley & Sons Inc,1995.

[18] Halkidi M,Batistakis Y,Vazirgiannis M.On clustering validation techniques[J].Journal of Intelligent Information Systems,2001,17(2):107-145.

[19] Caliński T,Harabasz J.A dendrite method for cluster analy-sis[J].Communications in Statistics-theory and Methods,1974,3(1):1-27.

[20] Davies D L,Bouldin D W.A cluster separation measure[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1979(2):224-227.

[21] Hubert L,Arabie P.Comparing partitions[J].Journal of classification,1985,2(1):193-218.

王 蒙(1985-)，博士，講師，主要從事計(jì)算機(jī)視覺、圖像處理、機(jī)器學(xué)習(xí)，以及語(yǔ)音識(shí)別方向研究工作,E—amil:vicong@live.com。

Trajectory hierarchical clustering based on weighted vector field*

CHEN Lin, WANG Meng

(School of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)

It is hard to define similarity of trajectories and trends to ignore details of trajectories using a traditional trajectory clustering method.Vector field based clustering methods keep the inherent features of movements and measures similarities of trajectories with the geometric structure information derived from it.Weighted fitting scheme is introduced to weaken the effects of noises and increase the robustness of clustering.A hierarchical approach is employed to automatically determine the number of class solving the problem that traditional methods cannot be self-adaptive to clustering,thus improving the effectiveness of our method.Experiments of traditional vector field clustering,k-means clustering andk-mediods clustering as well as the proposed method are conducted on the Atlanta Hurricane dataset,and the result shows the effectiveness of the hierarchical clustering algorithm based on weighted vector field.

trajectory; vector field clustering; weighted fitting; hierarchical clustering

2016—06—08

國(guó)家自然科學(xué)基金地區(qū)基金資助項(xiàng)目(61563025)；云南省教育廳科學(xué)研究基金資助項(xiàng)目(2015Z047)

10.13873/J.1000—9787(2017)06—0010—04

TP 311

A

1000—9787(2017)06—0010—04

陳 琳(1992-)，男，碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)視覺、模式識(shí)別。