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

冷泳林， 魯富宇

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

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

冷泳林a， 魯富宇b

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

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

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

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

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

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

1 相關概念

1.1 軌跡聚類

1.2 AP聚類算法

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

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

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

(1)

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

(2)

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

2.1 算法概述

本文提出了一種基于時序的軌跡聚類算法。因為不同時段軌跡路徑之間的關聯(lián)程度要遠遠小于間隔內軌跡路徑之間的關聯(lián)，所以算法首先將一個完整的軌跡數(shù)據(jù)按一定的時間進行分割。然后對每一個時間間隔內的數(shù)據(jù)分別利用AP聚類算法進行聚類，生成相應的聚類子集。為實現(xiàn)軌跡數(shù)據(jù)的整體聚類，算法對聚類子集進行二次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代表聚類中子軌跡的數(shù)目，LScenter,LSθ,LSlength分別表示所有子軌跡中心點、角度和長度總和。

(9)

(10)

圖1 代表子軌跡

2.3 HTCTS算法

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

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

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

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

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

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

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

步驟7 輸出聚類結果C。

3 實驗

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

3.1 聚類質量評價

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

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

表1 HTCTS軌跡路徑聚類質量

3.2 同類算法的對比

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

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

4 結束語

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

傳統(tǒng)軌跡聚類算法大都針對完整的軌跡路徑進行，針對整體軌跡路徑數(shù)據(jù)量大、聚類效率低、一定時間間隔內軌跡路徑關聯(lián)性更大等原因，本文提出了一種基于時序的層次軌跡聚類算法(HTCTS)。HTCTS將軌跡路徑進行2種分割：第一種是為實現(xiàn)分塊聚類而進行的時間分割；第二種是為確定聚類對象而進行的子軌跡分割。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] 曲冰潔.基于物聯(lián)網(wǎng)技術的煤礦智能物流的支撐器件與技術態(tài)勢[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);遼寧省教育科學規(guī)劃十三五項目(JG16DB009)；遼寧省社科聯(lián)2015年度合作項目(lslgslhl-020)

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

冷泳林， 魯富宇.一種基于時序的層次軌跡聚類算法[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