一種基于時序的層次軌跡聚類算法

冷泳林， 魯富宇

(渤海大學 a.信息科學與技術學院; b.教務處，遼寧 錦州 121000)

一種基于時序的層次軌跡聚類算法

冷泳林a， 魯富宇b

(渤海大學 a.信息科學與技術學院; b.教務處，遼寧 錦州 121000)

聚類相似的運動軌跡，獲取對象主要運動特征是軌跡路徑聚類的目標之一。本文針對軌跡路徑數據量大、傳統整體軌跡聚類算法效率低等問題，提出了一種基于時序的層次軌跡聚類算法(hierarchical trajectory clustering algorithm based on time series,HTCTS)。算法首先將完整的軌跡數據按一定的時間間隔進行分割，然后對分割的子路徑分別聚類，最后在對聚類子集進行二次聚類，生成最終的聚類結果。實驗結果表明：HTCTS算法在聚類效率和聚類質量上高于整體軌跡聚類算法。

軌跡聚類；軌跡路徑；相似性；AP算法

目前，物聯網技術日趨成熟，他由物聯網采集的數據無處不在。 軌跡數據就是其中一種重要的數據，其來源非常廣泛，如動物移動路徑、車輛運行路線、用戶購買路線等等。 這些軌跡數據通常包括活動的時間、速度、位置等基礎信息。通過對這些軌跡數據的分析，可以獲取移動對象個體或群體運動的模式，如超市用戶習慣路線圖，鳥類遷徙時間、路線，道路交通情況等，輔助研究者和管理者做出決策分析[1-3]。

軌跡聚類是一種有效的分析軌跡數據的方法。 針對不同的軌跡數據，人們研究了大量軌跡聚類算法。如Caffney等提出的基于模型的軌跡聚類算法[4-7]。Lee等提出的TRACLUS，一種執行在全部子軌跡集合上的基于密度的聚類算法[7]。Ahmed Kharrat 等提出的NETSCAN，一種在路網空間下的基于密度的軌跡聚類方法。NETSCAN先是根據移動對象經過的道路計算出繁忙路徑，然后根據用戶設置的密度參數對子軌跡進行聚類[8]。Xia Ying等[9]提出了一種在路網約束下綜合考慮時間和空間約束的軌跡相似性度量方法，并應用于軌跡聚類。

由于采集的軌跡數據量越來越龐大，傳統的聚類算法不能有效地聚類大規模的軌跡數據。本文提出了一種基于時序的層次軌跡聚類算法(HTCTS)。 算法首先將一個完整的軌跡數據按一定的時間間隔進行分割，然后對每一個時間間隔內的數據分別進行聚類，形成聚類子集。最后在對聚類子集進行二次聚類，生成相應的聚類結果。

1 相關概念

1.1 軌跡聚類

1.2 AP聚類算法

仿射傳播(affinity propagation,AP)聚類通過計算N個數據點間的相似度進行聚類。這N個數據點間的相似度可以用一個N×N的矩陣S表示。不同于其它聚類算法，AP聚類不需要指定聚類中心，在聚類的過程中，AP聚類算法將所有的數據點都作為潛在的聚類中心(exemplar)，第k個數據點能否成為聚類中心的評判標準是判斷該點在矩陣對角線上對應的值S(k，k)，S(k，k)的值越大，k點成為聚類中心的可能性就越大， 這個值又稱為參考度p(preference)。AP聚類的數目受p的影響。初始時，如果認為每個數據點都有可能成為聚類中心，則令p取相同的值，如果p取輸入相似度的均值，則產生的聚類數目為中等，如果取最小值，則聚類產生的數目也較少[10]。

AP聚類算法通過迭代的過程在數據點間傳遞兩種類型的消息，它們分別是吸引度(responsibility)和歸屬度(availability)。這兩類消息分別對應吸引度矩陣R和歸屬度矩陣A。其中R(i，k)表示從數據點i發送到候選聚類中心k的數值消息， 反映了數據點k是否適合作為數據點i的聚類中心。而A(i，k)表示從候選聚類中心k發送到數據點i的數值消息，反映了數據點i是否選擇k作為其聚類中心。R(i，k)與A(i，k)越大，則數據點k作為聚類中心的可能性就越大，i點越容易選擇k點作為聚類中心。

AP聚類通過迭代過程不斷更新吸引度矩陣和歸屬度矩陣，直到產生k個高質量的exemplar。吸引度矩陣的更新是用歸屬度矩陣A和相似度S實現，如式(1)所示：

(1)

歸屬度矩陣的更新用吸引度矩陣實現，如式(2)所示。

(2)

2 基于時序的層次軌跡聚類算法

2.1 算法概述

本文提出了一種基于時序的軌跡聚類算法。因為不同時段軌跡路徑之間的關聯程度要遠遠小于間隔內軌跡路徑之間的關聯，所以算法首先將一個完整的軌跡數據按一定的時間進行分割。然后對每一個時間間隔內的數據分別利用AP聚類算法進行聚類，生成相應的聚類子集。為實現軌跡數據的整體聚類，算法對聚類子集進行二次AP聚類，最后生成相應的聚類結果。

2.2 相似性度量

計算對象間的相似性是聚類算法的基礎，本文聚類算法涉及兩種相似性的度量。一種是兩條子軌跡的相似性度量，另一種是兩個子聚類集合之間的相似性度量。

2.2.1 軌跡線段相似性度量

文獻[11]認為兩條子軌跡之間的相似性由中心點相似性(simicenter)、角度相似性(simiθ)和平行相似性(simiparallel)3部分構成，見式(3)。其中，L1、L2分別對應2個子軌跡，L1表示較長的子軌跡，L2表示較短的子軌跡。

simi(L1,L2)=simicenter(L1,L2)+

(3)

子軌跡中心點相似性用歐幾里得距離進行計算，其中和分別對應兩條子軌跡的中心點。

(4)

在子軌跡角度相似性計算中，用θ表示兩條子軌跡間較小的交叉角。由于本文不考慮子軌跡的方向性，因此θ的取值滿足0°≤θ≤180°。式(5)給出了子軌跡角度相似性的計算方法。

(5)

(6)

(7)

則兩條子軌跡的并行相似性為para1和para2的最小值，如式(8)所示。

simiparallel(L1,L2)=min(para1,para2)

(8)

2.2.2 代表子軌跡

采用元組TL={N,LScenter,LSθ,LSlength}來描述子軌跡聚類后每個聚類子集合的信息，其中N代表聚類中子軌跡的數目，LScenter,LSθ,LSlength分別表示所有子軌跡中心點、角度和長度總和。

(9)

(10)

圖1 代表子軌跡

2.3 HTCTS算法

給定軌跡路徑集合TR和時間間隔參數t，HTCTS算法的步驟如下：

步驟1 根據給定的時間間隔分割軌跡路徑集合TR，將軌跡路徑集合中的軌跡路徑簡化成子軌跡集合。

步驟2 依據式(3)計算每一個時間間隔內子軌跡的相似性，并應用AP聚類生成聚類子集。

步驟3 計算每一個聚類子集的代表子軌跡。

步驟4 計算代表子軌跡間相似性。

步驟5 應用AP聚類算法聚類代表子軌跡。

步驟6 將相應的聚類子集分配到所屬代表子軌跡所在聚類。

步驟7 輸出聚類結果C。

3 實驗

為了驗證HTCTS算法的性能，設置實驗的運行環境是Windows XP professional操作系統， 硬件配置包括Intel Xeon 2.00GHz、2GB內存、500G硬盤。HTCTS算法的編寫采用 C++ 語言和gcc編譯器，軌跡數據存儲在SQL Server 2000。實驗數據集來自微軟亞洲研究院領導的一個Geolife項目*http://research.microsoft.com/en-us/projects/urbancomputing/.。數據集中包括了2007年4月到2012年8月之間的182個用戶的軌跡數據。本文隨機從數據集中選擇了100個用戶在1天之間的軌跡數據進行實驗。實驗從聚類時間和聚類數目2個角度進行衡量。本文的聚類時間包含路徑分割、路徑簡化、相似度計算和2次聚類。每次實驗重復5次，聚類時間為5次的平均值。由于AP聚類自動發現聚類中心，并分配節點到相應的聚類，因此聚類數目無法確定，但通過聚類數目，可以判斷算法發現有效路徑的能力。如果聚類集合子軌跡數目低于某一閾值，則認為這些子軌跡是噪音數據，由其產生的路徑不具有普遍性。

3.1 聚類質量評價

實驗按一定時間間隔將軌跡數據進行分割， 然后對分割軌跡數據采用HTCTS算法進行聚類。 表1列出了不同時間間隔軌跡路徑聚類時間和聚類數目。從實驗結果分析， 聚類時間間隔對聚類效率影響不大。如將軌跡路徑按1 h時間間隔劃分時，聚類時間為2.67 s。而當時間間隔縮小至0.5 h，聚類時間只增加了0.16 s。其原因在于短時間間隔內的子軌跡數目低于長時間間隔子軌跡數目， 相應的每次聚類子軌跡之間相似性計算量和聚類子軌跡規模都下降。雖然聚類次數增加，但由于每次聚類數據量遠小于長時間間隔的數據量，因此迭代次數也低于長時間間隔的聚類迭代次數，因此時間變化不明顯。

本實驗中統計的聚類數目只選擇子軌跡數目高于一定閾值的聚類結果，本文設定為20。其余低于閾值的聚類結果被視為噪音區，即不是所有用戶共同擁有的特征。聚類數目實驗結果表明：時間間隔的設置將影響聚類數目的變化，由于AP聚類不需要指定聚類數目，算法在迭代的過程中會逐步發現聚類中心。當時間間隔長時，有一些比較稀疏的軌跡段被列為噪音區，因此聚類數目低于短時間間隔的聚類數目。

表1 HTCTS軌跡路徑聚類質量

3.2 同類算法的對比

本文將HTCTS同TRACLUS和DBSCAN聚類算法相比。從圖2可以看出：HTCTS在聚類軌跡路徑時具有更好的運行效率，且聚類數目也多余其它算法。其主要原因在于HTCTS通過時間分割將軌跡路徑劃分成子集進行聚類，由于各時間間隔的軌跡路徑關聯性不大，因此這種分割并沒有影響聚類質量，但時間效率卻得到了提升。

圖2 不同算法之間性能比較

4 結束語

隨著物聯網技術在各個領域的廣泛應用，通過手機、GPS等可用設備可以獲取大量可用的軌跡數據，分析這些數據可以獲取巨大的商業價值，也可以輔助社會管理者做出重要決策。如本文通過聚類用戶的活動數據，可以發現這些用戶頻繁活動的路徑、不同時間重點活動區域等信息，進而總結一類人群在一個時間段內(如工作日)的工作模式和社會規律，為商業、交通提供有價值信息，更好地提高社會管理質量和服務水平。

傳統軌跡聚類算法大都針對完整的軌跡路徑進行，針對整體軌跡路徑數據量大、聚類效率低、一定時間間隔內軌跡路徑關聯性更大等原因，本文提出了一種基于時序的層次軌跡聚類算法(HTCTS)。HTCTS將軌跡路徑進行2種分割：第一種是為實現分塊聚類而進行的時間分割；第二種是為確定聚類對象而進行的子軌跡分割。HTCTS接著采用二次聚類方式對軌跡路徑進行聚類，其中，第1次是聚類每個時間間隔內的子軌跡；第2次是對子軌跡聚類結果進行整體聚類。實驗驗證了不同時間間隔對聚類結果的影響，并且將HTCTS算法同整體軌跡聚類算法進行對比。結果表明：HTCTS的聚類效率和聚類質量有很大的提高。

[1] ZHENG Y,ZHOU X F.Computing with spatial trajectories[M].Berlin:Springer,2011.

[2] 袁冠,夏士雄,張磊,等.基于結構相似度的軌跡聚類算法[J].通信學報,2011,32(9):103-110.

YUAN Guan,XIA Shixiong,ZHANG Lei,et al.Trajectory clustering algorithm based on structural similarity[J].Journal on Communications,2011,32(9):103-110.

[3] 曲冰潔.基于物聯網技術的煤礦智能物流的支撐器件與技術態勢[J].電子元件與材料,2014,33(5):103-104.

QU Bingjie.Supporting Device and Technology Situation of Frozen Coal Mine Intelligent Logistics Networking Technology Based on [J].Electronic Components and Materials,2014,33(5):103-104.

[4] GAFFNEY S and SMYTH P.Trajectory clustering with mixtures of regression models[C]//proceedings of the 5th International Conference on Knowledge Discovery and Data Mining.USA:[s.n],1999:63-72.

[5] CADEZ I V,GAFFNEY S,and SMYTH P.A general probabilistic framework for clustering individuals and objects[C]//proceedings of the 6th International Conference on Knowledge Discovery and Data Mining.USA:[s.n],2000:140-149.

[6] GAFFNEY S J,ROBERTSON A W,SMYTH P,et al.Probabilistic clustering of extratropical cyclones using regression mixture models[J].Climate Dynamics,2007,29(4):423-440.

[7] LEE J G,HAN J,WHANG K Y.Trajectory clustering:a partition-and-group framework[C]//ACM SIGMOD International Conference on Management of Data.USA:[s.n],2007:593-604.

[8] KHARRAT A,POPA I S,ZEITOUNI K,et al.Clustering Algorithm for Network Constraint Trajectories[C]//Headway in Spatial Data Handling,International Symposium on Spatial Data Handling.USA:[s.n],2008:631-647.

[9] XIA Y,WANG G Y,ZHANG X et al.Research of spatio-temporal similarity measure on network constrained trajectory data[J].International Journal of Computational Intelligence Systems,2010,4(5):491-498.

[10]FREY B J,DUECK D.Clustering by passing messages between data points[ J].Science,2007,315(5814):972-976.

[11]LI Z,LEE J G,LI X,et al.Incremental clustering for trajectories[C]//International Conference on Database Systems for Advanced Applications.USA:[s.n],2010:32-46.

(責任編輯 劉 舸)

A Hierarchical Trajectory Clustering Algorithm Based on Time Series

LENG Yong-lina， LU Fu-yub

( a.College of Information Science and Technology; b.Office of Academic Affairs, Bohai University, Jinzhou 121000, China)

Clustering movement trajectories to get the motion feature of object are one of the goals of the trajectory clustering. Aiming at the large scale trajectory data, to address the low efficiency of clustering, this paper proposes a hierarchical trajectory clustering algorithm based on time series (HTCTS). The algorithm first divides trajectory data by time interval, and then respectively clusters the sub paths. Finally, for all cluster subset, HTCTS executes cluster algorithm again to produce the final clustering results. The experimental results show that HTCTS algorithm in clustering efficiency and quality is superior to the trajectory clustering algorithms which cluster the whole dataset directly.

trajectory clustering; trajectory path; similarity; AP clustering

2016-11-10 基金項目：遼寧省社科基金資助項目(L14AGL002,L13AGL002);遼寧省教育科學規劃十三五項目(JG16DB009)；遼寧省社科聯2015年度合作項目(lslgslhl-020)

冷泳林(1978—)，女，遼寧營口人，碩士，副教授，主要從事數據挖掘、數據存儲與索引研究，E-mail:lengyonglin@qq.com；魯富宇(1980—)，男，碩士，主要從事數據挖掘研究。

冷泳林， 魯富宇.一種基于時序的層次軌跡聚類算法[J].重慶理工大學學報(自然科學)，2017(3):123-127.

format：LENG Yong-lin， LU Fu-yu.A Hierarchical Trajectory Clustering Algorithm Based on Time Series [J].Journal of Chongqing University of Technology(Natural Science)，2017(3):123-127.

10.3969/j.issn.1674-8425(z).2017.03.018

TP311

A

1674-8425(2017)03-0123-05