陳 琳， 王 蒙

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

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

陳 琳， 王 蒙

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

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

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

0 引 言

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

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

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

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

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

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

點bsj(x,y)為軌跡Ti上一坐標點，點Q11(x11,y11),Q12(x12,y12),Q21(x21,y21),Q22(x22,y22)為bsj(x，y)周圍最近的4個坐標點如圖1(a)。定義dx=x-[x],dy=y-[y]，則點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ù)矢量場擬合

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

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

(5)

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

(6)

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

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

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

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

σ=1.482 6 med|ri-medri|

(7)

式中 ri為第i個數(shù)據(jù)點的殘差。

(8)

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

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

(9)

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

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

(10)

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

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

(11)

X=(LTL+CTWTWC)CTWTWb

(12)

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

1.4 矢量場層次聚類

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

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對V聚類得到M類，Φj={Φj,j=1,2,3,…,M}(M不固定)，且{Xi,i∈Φj};

7)分別輸出聚類后的矢量場Yj。

2 實驗結(jié)果與分析

2.1 實驗設計與評價指標

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

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

2.2 實驗結(jié)果與分析

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

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

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

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

圖2 實驗結(jié)果

圖3 實驗數(shù)據(jù)

圖4 閾值為2.5時各類的矢量場圖

閾值評價指標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ù)集

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

圖2(i)～(l)為評價指標直方圖，可以看出，WVFHC算法的聚類效果好。因為加入噪聲后，VFHC算法將異常數(shù)據(jù)作為正常數(shù)據(jù)進行矢量場擬合，影響聚類結(jié)果。而WVFHC算法通過給異常數(shù)據(jù)分配較小的權(quán)重，降低異常數(shù)據(jù)的影響，所以聚類效果較好。

3 結(jié) 論

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

[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] 嚴筱永,錢煥延,施衛(wèi)娟,等.一種利用統(tǒng)計中值的加權(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)國,韓曉慧,宋 磊.基于改進混合蛙跳-K均值聚類算法的無功電壓控制分區(qū)[J].傳感器與微系統(tǒng),2013,32(6):18-21.

[14] 張乙竹,周禮爭,唐 瑞,等.基于k-means聚類點密度的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-)，博士，講師，主要從事計算機視覺、圖像處理、機器學習，以及語音識別方向研究工作,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

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

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

TP 311

A

1000—9787(2017)06—0010—04

陳 琳(1992-)，男，碩士研究生，主要研究方向為計算機視覺、模式識別。