朱 毅，祁雪婷，趙玉帥

（鹽城工業(yè)職業(yè)技術學院，江蘇 鹽城 224000）

在軌跡聚類研究的發(fā)展歷程中，對海量對象運動規(guī)律的發(fā)掘始終是重要的探討課題之一。2005年，Kalni等[1]提出了基于一種密度的移動聚類思想，這種聚類思想主要可以被闡述如下：對于聚類中的每個數(shù)據(jù)點，給定范圍（ε），在該范圍中至少有一定數(shù)量（Minpts）的點。這類移動對象聚類模式也被Jeung等[2]稱作Convoy模式。Convoy模式定義：K個連續(xù)時間段內存在超過某數(shù)目且共同移動的對象集合。本文中實驗采用北京交通的數(shù)據(jù)集，此數(shù)據(jù)集主要由城市地圖數(shù)據(jù)庫、道路ID數(shù)據(jù)庫、節(jié)點ID數(shù)據(jù)庫以及軌跡數(shù)據(jù)庫構成。

1 實驗流程

本次實驗基于數(shù)據(jù)總量龐大的特性，采用道格拉斯-普克算法（Douglas-Peucker）[3]對連續(xù)坐標進行測量，然后對相鄰時間戳的數(shù)據(jù)進行了進一步填充以保證數(shù)據(jù)的平滑性。在對數(shù)據(jù)噪點清除和切分之后，本實驗采用了3種聚類算法（MC1、MC2、CMC）對處理后的數(shù)據(jù)進行Convoy模式的聚類，并且對這3種聚類算法進行了效率、質量的對比[4]。

2 軌跡聚類算法實現(xiàn)

2.1 軌跡壓縮

在軌跡壓縮部分，本實驗采用了時間同步歐氏距離（Time Synchronized Euclidian Distance）和DK算法來簡化軌跡數(shù)據(jù)。時間同步歐氏距離能夠從軌跡算法中產生近似軌跡[5]，而DK算法則能通過垂向距離對數(shù)據(jù)進行壓縮[3]。本次實驗基于這兩種方法將測試數(shù)據(jù)中單個時間戳中缺失的數(shù)據(jù)進行了補全，然后通過DK算法對整體軌跡數(shù)據(jù)進行了壓縮。即使數(shù)據(jù)經(jīng)過算法進行了壓縮，也需要對各個時段內所有坐標點進行統(tǒng)計之后才能聚類。為了提升聚類算法的性能，本次實驗中采用了網(wǎng)格（Grid）數(shù)據(jù)結構[6]。網(wǎng)格數(shù)據(jù)結構將地圖數(shù)據(jù)均分成若干小的網(wǎng)格并建立索引，單個網(wǎng)格的計算需要與其周圍8個網(wǎng)格同步。

2.2 時間切片聚類過程

經(jīng)過對軌跡數(shù)據(jù)進行預處理與壓縮，我們得到了單個時間段內平滑的軌跡數(shù)據(jù)集?；诖藬?shù)據(jù)集，本實驗實現(xiàn)了基于DBSCAN算法的移動聚類算法（MC1、MC2、CMC）對數(shù)據(jù)進行聚類。MC1[1]算法對數(shù)據(jù)進行直接移動聚類，此算法的運行機制是：遍歷所有時間切片，對單個時間切片進行DBSCAN聚類后，對所有時間切片進行移動聚類集合的創(chuàng)建，要求移動聚類集合中相同的單個數(shù)據(jù)點至少在一段時間內持續(xù)存在于該集合中。

本實驗中實施的另一種算法是MC2[1]，本算法在MC1算法的基礎上對移動聚類進行并集的創(chuàng)建和數(shù)據(jù)的連接。該算法指定聚類移動的擴展條件并對兩個移動聚類之間進行相似性檢查。當兩個連續(xù)的時間戳具有較大或相等的閾值百分比時，該聚類可以被認為是有效的移動聚類。閾值的定義為，式中，Ct和Ct-1代表時間戳在t和t-1的聚類。

為了與MC2算法進行比較，本實驗實現(xiàn)了另一種基于相似性檢查的聚類算法，稱為CMC[2]。該算法使用不同時間戳聚類之間的交集數(shù)量代替閾值θ作為驗證條件，并將驗證周期擴大到k個時間戳，以增強輸出的特征。這種算法對移動聚類的生命周期處理類似于MC2，但判定條件改為|Ct∩Ct-1|≥m，即兩個連續(xù)時間戳中交叉點數(shù)量需要大于m個，并且持續(xù)k個時間戳。

3 軌跡聚類算法比較與分析

3.1 算法效率對比

（1）距離計算方式選擇：由于單個時間切片的聚類需要進行地圖中坐標點與坐標點之間的距離計算，并且數(shù)據(jù)中也提供了整個城市的節(jié)點ID和鏈接位置。我們基于這些節(jié)點ID構建了一個有向加權圖，并且使用迪杰斯特拉算法、基于Grid結構優(yōu)化的迪杰斯特拉算法以及時間同步歐氏距離算法對節(jié)點進行了路徑計算。實驗顯示，Dijkstra算法運行時間遠超歐式距離算法，因此本次實驗中采用歐氏距離算法為計算距離的唯一算法。

（2）空間數(shù)據(jù)結構效率對比：對于空間結構數(shù)據(jù)的使用，為了驗證Grid結構是否適合軌跡數(shù)據(jù)挖掘。該實驗采用MC1進行了使用Grid結構和不使用Grid結構之間的對比，通過時間戳來進行結構算法的時間復雜度計算。實驗表明，當數(shù)據(jù)量提升至巨量水準時，使用Grid結構插入與搜索的時間復雜度遠好于不使用Grid結構。

（3）移動聚類算法效率對比：本次實驗對移動聚類算法MC1、MC2和CMC的算法效率進行了分析，以上述算法在整個聚類過程中隨著時間切片數(shù)量上升產生的時間成本作為效率參考。DBSCAN算法的參數(shù)：范圍（ε）=400、最小數(shù)量（MinPts）=5。移動聚類算法參數(shù)：MC1閾值θ=0.5、MC2閾值θ=0.333、CMC交叉點個數(shù)m=3。實驗結果表明，3種移動聚類在算法時間成本上效率相近，CMC算法效率略好于其余兩種算法。

圖1 聚類算法的時間復雜度對比

3.2 算法實現(xiàn)成果

為對比不同軌跡精度和聚類算法精度，實驗抽取更有代表性的特征時間戳用于聚類展示。首次進行切片的時間是3月1日中午12時的交通數(shù)據(jù)，采用此時間段的原因是午間交通流量高。數(shù)據(jù)經(jīng)過移動聚類得到如圖2所示結果，地圖背景以網(wǎng)格形式展示。

圖2 MC1（左）MC2（中）CMC（右）的聚類結果

由以上3幅圖像上的點所構成的簇就是算法獲得的移動聚類，本實驗在3幅聚類圖像的基礎上，通過觀察隨時間戳不斷運動的結果生成圖像來觀察數(shù)據(jù)聚類情況。就觀察聚類生成的范圍與精度，MC2是三種算法中適用情況最廣的一類。而CMC算法則更適合需求高精度移動聚類的實驗需求，如婚禮車隊、游行等情況。因此根據(jù)獲得的移動聚類圖像，本實驗總結如下：①MC1、MC2、CMC的算法的準確性存在差異，且由于算法中確定閾值，在閾值較高時MC2和CMC會有一些沒有被識別為移動聚類的點聚類。②對于通用的情況，MC2能較好地分割出有更大范圍的簇；而對于數(shù)據(jù)稀疏的情況，MC1能更方便輕易地將其分割成若干更小的簇。③CMC聚類算法的精度較高，但它定義的聚類數(shù)目比MC1和MC2要少。

3.3 算法參數(shù)對算法效果的影響

3.3.1 半徑Radius與聚類密度指標Minpts的影響

基于算法效率以及準確性，本實驗選取MC2算法作為參考對象，更改半徑（Radius）并觀察結果。我們檢驗了兩個極值，即改變半徑值為非常大（1 000米）和非常?。?00米）來觀察結果。通過檢驗，得出以下結論：①在半徑僅為100米的情況下，即使軌跡總數(shù)非常大，也只能確定非常小數(shù)量的移動聚類。但是當軌跡總數(shù)量很大時，僅能識別出少量移動聚類。顯然，這樣做效果欠佳。②若半徑值太大，則大部分軌跡點都會歸為一個大的聚類。這樣就會造成聚類效果變差。

在本次試驗中，我們發(fā)現(xiàn)Minpts個數(shù)對對比之后的效果也有一定的影響。但由于此參數(shù)造成的影響在密集的軌跡數(shù)據(jù)中對聚類結果影響并不明顯。所以本實驗減少半徑參數(shù)到100米并觀察。結果表明Minpts個數(shù)的增加會使算法聚類得更嚴格，也會使得聚類被定義得更少。

3.3.2 聚類判斷閾值影響

由于MC2的移動聚類驗證機制與CMC不同，本實驗采用這兩種算法進行聚類判斷閾值影響的驗證。

（1）MC2的實驗：本實驗首先根據(jù)公式對閾值θ進行了調整，其取值范圍為0.5～0.8。經(jīng)實驗表明，提高算法閾值θ對結果沒有很大的影響。當改變量不大時，算法得出的聚類個數(shù)與結果幾乎相同，并且當θ值增加到一定的閾值時聚類結果會收斂，實驗中得出的聚類內部點個數(shù)也會非常少，算法的可用性就會降低。

（2）CMC的實驗：基于前面給出的閾值判定公式|Ct∩Ct-1|≥m，我們可以通過更改m值的大小來操縱閾值。本實驗觀察了CMC算法在m=3以及m=5的狀態(tài)下，移動聚類生成的精度與數(shù)量。實驗表明：m與聚類大小成正相關，且會導致聚類精度降低。選擇m值對于CMC算法的可用性影響較大，需要謹慎判斷。

4 結束語

本實驗采用一系列算法對北京交通軌跡數(shù)據(jù)進行處理，對軌跡聚類進行了實現(xiàn)與分析。實現(xiàn)了以MC1、MC2和CMC為算法的移動聚類，并對其進行比較。總之，該實驗許多方法在多數(shù)場景下適用性不強，本次實驗的算法較為同質化，可發(fā)掘更具有前瞻性的聚類模式?！?/p>