劉 文 凱，唐 建 波，蔡 建 南，熊 強 強，劉 啟 亮

(中南大學地球科學與信息物理學院地理信息系，湖南 長沙 410083)

面向城市交通應用的移動對象聚類算法比較研究

劉 文 凱，唐 建 波，蔡 建 南，熊 強 強，劉 啟 亮

(中南大學地球科學與信息物理學院地理信息系，湖南 長沙 410083)

移動對象聚類方法已被廣泛應用于城市交通系統(tǒng)中移動對象的動態(tài)聚類模式挖掘，然而，當前對于現(xiàn)有移動對象聚類算法在城市交通中的實際效果尚缺乏客觀的分析與評價。為此，該文選取4種具有代表性的移動對象聚類算法(Swarm模式、Convoy模式、Platoon模式、Moving Cluster模式)，針對北京市出租車移動數(shù)據(jù)中的擁堵現(xiàn)象挖掘進行實驗分析與比較：1)定義模式數(shù)量、模式生存期及模式運動距離等指標定量評價和比較現(xiàn)有算法挖掘擁堵現(xiàn)象的能力；2)采用不同的對象數(shù)目閾值和時間閾值等參數(shù)閾值進行測試，分析算法閾值對移動對象聚類結(jié)果的影響。實驗結(jié)果表明， 4種模式中的Convoy模式挖掘虛假擁堵現(xiàn)象的概率最低，挖掘擁堵現(xiàn)象的能力最強。4種移動對象聚類方法對閾值的設置均比較敏感，時間連續(xù)性約束對聚類結(jié)果有著顯著影響。最后，對現(xiàn)有算法在城市交通應用中的適用性給出了相關建議。

移動對象；聚類分析；GPS軌跡

近年來，隨著移動通訊技術與GPS定位技術的不斷發(fā)展，已經(jīng)獲取了海量的移動對象位置數(shù)據(jù)，如城市車輛位置數(shù)據(jù)、颶風軌跡數(shù)據(jù)、動物遷徙數(shù)據(jù)及人類活動位置數(shù)據(jù)等[1-3]。這些移動對象位置數(shù)據(jù)庫中通常包含一些彼此空間鄰近且共同移動的對象集合，即移動對象聚集模式[4]。分析這類移動對象聚集模式對于研究地理現(xiàn)象的發(fā)展變化機理具有重要的價值，且已經(jīng)廣泛應用于城市交通與安全、天氣預測、動物遷移分析等領域[5-9]。尤其在城市交通領域，移動對象聚集模式可以直接用于發(fā)現(xiàn)和預測城市系統(tǒng)中的擁堵現(xiàn)象[10]，進而服務于城市路況分析、熱點區(qū)域挖掘和導航線路規(guī)劃[11-13]。當前，在城市交通領域，國內(nèi)外學者雖然已針對移動對象聚集模式挖掘開展了初步研究，并在空間聚類算法的基礎上發(fā)展了一系列移動對象聚類算法，但對這些算法的實際應用效果尚缺乏客觀分析與評價。為此，本文首先對移動對象聚集模式挖掘算法進行分析和歸納，進而采用北京市出租車GPS軌跡數(shù)據(jù)對4種具有代表性的移動對象聚類算法的特點與實際應用效果進行對比和分析，以期為實際應用提供指導。

1 移動對象聚類算法

移動對象聚類旨在發(fā)現(xiàn)共同運動(滿足空間鄰近)一定時間的移動對象集合。定義一個移動對象聚集模式需要考慮兩方面約束：1)對象存在約束，移動對象是否始終存在于聚集模式中；2)時間連續(xù)約束，移動對象的空間鄰近性是否在每個時間點上都滿足。依據(jù)這兩類約束，本文將現(xiàn)有移動對象聚集模式分為兩類(表1)：對象不變模式與對象可變模式。

表1 現(xiàn)有移動對象聚類模式對比

1.1 對象不變模式聚類算法

Jeung等[14]提出了移動對象聚集模式的Convoy模式。Convoy模式定義為一定數(shù)目且共同運動至少K個連續(xù)時間段的移動對象集合。挖掘Convoy模式時，首先在每個時間快照上采用空間聚類算法(如DBSCAN算法[15])分析空間聚集模式，將第一個時間快照的聚類結(jié)果作為候選Convoy模式集。進而，將下一個時間快照的空間聚類結(jié)果與候選Convoy模式集進行比對，并將共同移動對象數(shù)目大于給定閾值的聚類結(jié)果與候選Convoy模式集對應聚類結(jié)果合并，生成新的候選Convoy模式集。遍歷所有時間快照之后，檢索候選Convoy模式集中存在時間大于給定時間閾值的候選Convoy模式，將其視為一個Convoy模式。如圖1所示，t0、t1、t2、t3為4個時間快照，在這4個時間快照中共有a、b、c、d、e 5個移動對象，每個時間快照上發(fā)現(xiàn)的空間聚集模式如圖中虛線區(qū)域所示。在t0中，a、b、c、d、e同屬于一個聚集模式；在t1中，b、c、d同屬于一個聚集模式；在t2中，a、b、c、d、e同屬于一個聚集模式；在t3中，b、c、d、e同屬于一個聚集模式。給定移動對象數(shù)目閾值2，存在時間閾值2，則b、c、d這3個移動對象組成一個Convoy模式(實線所示)。另有學者提出的Flock模式[16]可以視為Convoy模式的一種特例，F(xiàn)lock模式要求每個時間切片上的空間聚集模式均包含在固定大小的圓形區(qū)域中，而Convoy模式對空間聚集模式的形狀沒有約束。

Li等[17]在Convoy模式的基礎上，放寬對時間連續(xù)性的約束，進一步提出了Swarm模式。Swarm模式定義為一定數(shù)目且共同運動至少K個時間段的移動對象集合(K不需要連續(xù))。Swarm模式挖掘算法首先在每個時間快照上發(fā)現(xiàn)空間聚集模式，然后建立對象集搜索空間，采用深度優(yōu)先順序遍歷該搜索空間的每一個節(jié)點，如果節(jié)點符合Swarm的定義規(guī)則，則該節(jié)點可視為一個Swarm模式。如圖2所示，在t0、t1、t2、t34個時間快照中共有a、b、c、d、e 5個移動對象，每個時間快照上發(fā)現(xiàn)的空間聚集模式如圖中實線區(qū)域所示。在t0中，a、b、c、d、e同屬于一個聚集模式；在t1中，b、c、d同屬于一個聚集模式；在t2中，a、b、c、d、e同屬于一個聚集模式；在t3中，b、c、d、e同屬于一個聚集模式。給定移動對象數(shù)目閾值2，存在時間閾值2，則圖中可發(fā)現(xiàn)3個Swarm模式，{(a,b,c,d,e),(t0,t2)}、{(b,c,d ),(t0,t1,t2,t3)}和{(b,c,d,e),(t0,t2,t3)}。同一個移動對象可以屬于多個Swarm模式，且Swarm模式中的移動對象可在不連續(xù)的時間快照上出現(xiàn)在同一個聚集模式中。

Li等[18]定義了一種時間約束介于Convoy模式和Swarm模式之間的Platoon模式。Platoon模式定義為一定數(shù)目且共同運動至少K個時間段的移動對象集合，K個時間段可在全局不連續(xù)，但至少包含n個連續(xù)的局部時間段。挖掘Platoon模式時，首先在每個時間快照上采用空間聚類算法(如DBSCAN算法[15])發(fā)現(xiàn)空間聚集模式，進而依據(jù)空間聚類算法結(jié)果建立對象空間迭代樹，通過深度優(yōu)先順序遍歷該樹，若樹的節(jié)點能夠滿足Platoon模式的定義規(guī)則，那么該節(jié)點可識別為一個Platoon模式。如圖3所示，在t0、t1、t2、t34個時間快照中共有a、b、c、d、e 5個移動對象，每個時間快照上發(fā)現(xiàn)的空間聚集模式如圖中實線區(qū)域所示。在t0中，a、b、c、d、e同屬于一個聚集模式；在t1中，b、c、d同屬于一個聚集模式；在t2中，a、b、c、d、e同屬于一個聚集模式；在t3中，b、c、d、e同屬于一個聚集模式。給定移動對象數(shù)目閾值4，全局存在時間閾值3，局部存在時間閾值2，那么在圖中只有一個Platoon模式，即{(b,c,d,e),(t0,t2,t3)}。可見，在該Platoon模式中，時間快照(t0,t2,t3)在整體上并不連續(xù)，但包含t2，t3這兩個連續(xù)的局部時間快照。

1.2 對象可變模式聚類算法

與對象不變模式相比，在對象可變模式中，依然要求移動對象在空間上的鄰近性與時間上的連續(xù)性，但允許移動對象聚類模式中的成員發(fā)生變化。對象可變移動對象集聚模式挖掘具體可采用兩種策略：

(1)時空分治的策略。Kalnis等[4]從時空分治的角度發(fā)展了挖掘Moving Cluster模式的方法，其首先在每個時間快照上采用空間聚類算法(如DBSCAN算法[15])聚類發(fā)現(xiàn)空間聚集模式，然后計算連續(xù)時間快照中不同聚集模式的Jaccard相似性系數(shù)，如果Jaccard相似性系數(shù)超過給定閾值，那么兩個相鄰時間快照中不同的聚集模式便組成了一個Moving Cluster模式。如圖4a所示，采用DBSCAN算法[15]在每個時間快照上發(fā)現(xiàn)空間聚集模式，在t0、t1、t23個時間快照上，共有C1、C2、C3 3個聚集模式(如實線圓所示)，在C1中包含a、b、c、d、e 5個移動對象，在C2中包含b、c、d 3個移動對象，在C3中包含a、b、c、d、e 5個移動對象。聚集模式C1和C2的Jaccard相似性系數(shù)為0.6，C2和C3的Jaccard相似性系數(shù)為0.6，若設置的Jaccard相似性系數(shù)閾值為0.6，則在時間快照t0、t1、t2中只有一個Moving Cluster{C1,C2,C3}。國內(nèi)外學者亦對Moving Cluster模式挖掘中的效率提高以及空間聚類合并等問題開展了諸多改進工作[12]。

(2)動態(tài)維護的策略。在每一個時間快照上進行聚類會耗費大量的時間[19]，為解決該問題，Li 等在BIRCH算法[20]的基礎上提出了Moving Micro-cluster算法：首先在初始階段采用空間聚類方法(如K-means[21])對移動對象進行聚類，在得到的聚類結(jié)構基礎上持續(xù)探測該聚集模式的最小外包矩形是否超過給定閾值，同時處理碰撞和分離事件，并進一步采用動態(tài)數(shù)據(jù)結(jié)構(KDS)[22]減少查找邊界點的時間。如圖4b所示，5個移動對象在不同時間快照上聚類結(jié)構的外包矩形如實線框所示，從t1時刻起，盡管空間聚類結(jié)構中的成員發(fā)生了分離(如對象a)與匯入(如對象e)，但一直滿足最小外包矩形閾值，因此被識別為一個移動聚類結(jié)構。Jensen等[23]進一步發(fā)現(xiàn)上述策略在碰撞和分離事件的探測過程中浪費大量時間，通過綜合移動對象當前和未來位置定義相似性度量指標，評估移動聚集模式的分裂和合并，進而提高算法效率。

圖4 對象可變模式簡例

分析當前的移動對象聚類方法：1)對象不變的方法有利于對移動對象個體的移動聚集模式進行挖掘，然而Convoy模式中對時間連續(xù)性約束過于嚴格，可能遺漏部分移動聚集模式，但是一些放松時間連續(xù)性約束的方法(如Swarm)亦容易發(fā)現(xiàn)一些虛假的移動聚集模式；2)對象可變的方法雖然實際操作較為容易，但是對移動對象個體的運動模式反映不足(不同時間快照上簇內(nèi)成員的變化可能較大)。

2 實驗設計與分析

本文采用2012年12月1日北京市12 409輛出租車移動對象數(shù)據(jù)(圖5)對上述4種代表性方法(Swarm、Platoon、Convoy和Moving Cluster挖掘算法)挖掘交通擁堵的能力進行對比分析。每個移動對象包含9種屬性信息：車輛標識、觸發(fā)事件、運營狀態(tài)、GPS記錄時間、經(jīng)度、緯度、速度、方向和GPS狀態(tài)。雖然出租車從絕對數(shù)量上在城市機動車保有量中所占的比例并不高，然而相較于私家車等其他車輛，同時考慮到其運營時間的持續(xù)性，其在城市道路交通中所占比例相當可觀，利用出租車的運行信息間接地估計城市道路的擁堵狀況是可行的[13,24,25]。

本文設置時間粒度為1 min，僅選取經(jīng)緯度信息進行實驗。實驗中，選擇擁堵高發(fā)的3個上下班時間段(即7:00-10:00，11:00-14:00，17:00-20:00)對4種方法進行測試，并從兩方面對現(xiàn)有的移動對象聚集模式算法進行對比分析：1)挖掘出的模式數(shù)量、模式生存期及模式運動距離等差異；2)不同的閾值設置得到的聚類結(jié)果差異。

圖5 出租車移動對象數(shù)據(jù)示例

上述移動對象聚類算法均需首先提取每個時間快照上的空間聚集模式，由于DBSCAN算法[15]能夠有效發(fā)現(xiàn)不同形狀的空間聚集模式，因此實驗中選取該算法提取移動對象中的空間聚集模式，算法的空間半徑參數(shù)(Eps)默認設置為 100 m，最小包含點參數(shù)(Minpts)設置為3。對于Swarm模式、Convoy模式以及Platoon模式，將對象數(shù)目閾值均設置為3，前兩種模式的生存期閾值設為3 min，Platoon模式全局生存期閾值設置為3 min，局部生存期閾值設置為2 min。Moving Cluster 模式中Jaccard系數(shù)閾值設置為0.8。為了方便表達，本文將時間段7:00-10:00表示為時間段1，11:00-14:00表示為時間段2，17:00-20:00表示為時間段3。

2.1 聚類結(jié)果對比分析

上述4種移動對象聚類算法在3個時間段內(nèi)發(fā)現(xiàn)的移動對象聚集模式數(shù)目如圖6所示?？梢园l(fā)現(xiàn)，在任一時間段，Swarm模式數(shù)量最多，與其他3種算法發(fā)現(xiàn)的移動對象聚集模式數(shù)量差別較大，Platoon模式與Moving Cluster模式數(shù)量相當，Convoy模式數(shù)量最少。4種移動對象聚集模式在時間段17:00-20:00的數(shù)量最多，在11:00-14:00的數(shù)量次之，在7:00-10:00的數(shù)量最少，這與日常生活中的晚高峰較早、中高峰交通更擁堵現(xiàn)象相一致。

移動對象聚集模式的生存期及運動距離的對比結(jié)果如圖7所示。模式生存期代表某一時間段內(nèi)所有該模式生存時間的平均值，模式運動距離代表某一時間段內(nèi)該模式所有對象共同運動距離的平均值。擁堵模式大致應該滿足模式運動距離短且生存期長這兩方面條件(表征了車輛移動緩慢的特點)。從圖7可以看出：1)Swarm模式與Platoon模式均表現(xiàn)出模式生存期長且運動距離長的特點，可以推斷二者發(fā)現(xiàn)虛假擁堵現(xiàn)象的概率較大；2)Moving Cluster模式表現(xiàn)出模式生存期短且運動距離短的特點，這可能是由于該模式對于時間連續(xù)性沒有約束，導致發(fā)現(xiàn)了較多無意義的小簇；3)Convoy模式最為符合交通擁堵模式運動距離短且生存期長的特點，可以推斷其發(fā)現(xiàn)真正交通擁堵的能力較強。

2.2 聚類參數(shù)影響分析

為探究不同的閾值設置對移動對象聚類算法結(jié)果的影響，以時間段3為例進行實驗分析。為了測試單個閾值的設置對聚類結(jié)果的影響，實驗時每次僅改變一個測試閾值，而保證其他閾值為默認值。首先對Swarm模式、Platoon模式和Convoy模式挖掘中的兩個關鍵閾值(對象數(shù)目閾值和時間閾值)進行分析，實驗結(jié)果如圖8所示?？梢园l(fā)現(xiàn)，隨著對象數(shù)目閾值的增大，移動對象聚類模式的數(shù)量隨之迅速減少，但在對象數(shù)目閾值超過6后，聚類模式數(shù)目變化不大；隨著時間閾值的增大，Swarm模式和Platoon模式的數(shù)量迅速減少，但時間閾值對Convoy模式的影響最小。

進而，對影響Moving Cluster模式挖掘的關鍵閾值(DBSCAN算法的最小包含點數(shù)(Minpts)與Jaccard相似性系數(shù)閾值)進行分析，實驗結(jié)果如圖9所示?？梢园l(fā)現(xiàn)，隨著Minpts增大，得到的Moving Cluster模式數(shù)目隨之減少，當Minpts從3增大到5時，Moving Cluster模式的數(shù)目減少速度最快；隨著Jaccard相似系數(shù)閾值的增大，發(fā)現(xiàn)Moving Cluster模式的數(shù)目隨之減少， Jaccard相似系數(shù)閾值超過0.7后，Moving Cluster模式的數(shù)目變化不大。上述參數(shù)變化規(guī)律亦可以為實際應用中閾值設置提供一定的參考。

2.3 實驗結(jié)果分析與討論

依據(jù)上述實驗結(jié)果，對文中4種方法的性能與適用性進行分析和總結(jié)：1)Swarm模式數(shù)目最多的主要原因在于其對時間連續(xù)性的約束過于寬松，導致發(fā)現(xiàn)的模式中包含較多的非擁堵現(xiàn)象，亦是Swarm模式運動距離與生存期長的主要原因；伴隨著時間連續(xù)性約束越來越嚴格(Platoon和Convoy模式)，模式的數(shù)量、運動距離、生存期均減少?？梢?，模式的時間連續(xù)性約束對移動對象聚集模式挖掘的影響最為顯著。2)對于Moving cluster模式，雖然其對移動對象在聚類模式中的時間閾值沒有約束，但是其限定了相鄰兩個時間切片間連續(xù)性的約束與相鄰時間切片間的相似性約束，Moving Cluster的數(shù)量僅比Convoy模式稍多。由于Moving Cluster的時間連續(xù)約束比Convoy模式更寬松，發(fā)現(xiàn)了更多細碎的移動模式，故該模式的運動距離與生存期比Convoy模式更短。3)由于Convoy模式對移動對象聚集模式定義的約束最為嚴格，其對參數(shù)閾值的敏感性相對較低，而其他幾種算法均對閾值較為敏感。Convoy模式最為符合擁堵模式生存期長且運動距離短的特點，在實際中發(fā)現(xiàn)真正交通擁堵的能力較強。但是，在實際中如何依據(jù)應用需求與應用目的選擇聚類參數(shù)依然是一個必須要重視的問題。4)上述4種算法發(fā)現(xiàn)交通擁堵時，僅考慮了時間切片上的聚集性與時間的連續(xù)性，而沒有顧及車輛的運行距離與運行速度，這也是發(fā)現(xiàn)虛假移動對象聚集模式的一個重要原因，如圖10所示，上述移動對象雖然一起運動了一定時間，但是相鄰時間的模式運動距離較長，并沒有產(chǎn)生相鄰時間切片上空間鄰近性的聚集現(xiàn)象。此外，當前算法大多僅在歐式空間研究移動對象的聚集模式，而忽視了路網(wǎng)對移動對象的約束，因此需要進一步研究路網(wǎng)約束對移動對象聚集模式挖掘的影響[26,27]。

圖8 不同參數(shù)對Convoy,Swarm和Platoon模式挖掘影響

圖9 不同參數(shù)對Moving Cluster挖掘結(jié)果影響

圖10 現(xiàn)有移動對象聚類算法發(fā)現(xiàn)的非擁堵模式

3 結(jié)論與討論

本文對現(xiàn)有4種代表性的移動對象聚集模式挖掘算法在城市交通中的應用效果進行了對比研究，并采用北京市出租車移動數(shù)據(jù)，從模式數(shù)量、模式生存期及模式運動距離等方面對現(xiàn)有方法發(fā)現(xiàn)移動對象交通擁堵的實際效果進行了實驗分析，同時對比了不同閾值對聚類結(jié)果的影響。結(jié)果發(fā)現(xiàn)：1)時間連續(xù)性約束對于移動對象聚集模式挖掘具有顯著影響，直接影響模式數(shù)量、模式生存期及模式運動距離；2)雖然現(xiàn)有算法均有發(fā)現(xiàn)虛假擁堵的問題，但對于時間連續(xù)性約束較嚴格的方法(如Convoy和Moving Cluster)而言，發(fā)現(xiàn)虛假擁堵的概率相對較低；3)現(xiàn)有方法對參數(shù)閾值較為敏感，尚缺乏較為通用、客觀的閾值設置方法。

本研究尚存在兩方面的不足：1)沒有對算法的效率進行分析，在分析交通大數(shù)據(jù)時，算法的效率亦是必須考慮的問題；2)僅采用出租車移動對象數(shù)據(jù)進行分析，而不同類型的移動對象聚集模式的特征與性質(zhì)可能存在差異，亦有算法的偏向性。進一步的研究工作將側(cè)重于以下兩方面：1)移動對象全生命周期聚集模式挖掘，如區(qū)分城市交通擁堵中的4個過程(開始、發(fā)展、擁堵、衰退)，如何發(fā)現(xiàn)這一過程對于城市交通規(guī)劃具有重要意義；2)路網(wǎng)約束下的移動對象聚集模式挖掘模型構建。

[1] 李婷,裴韜,袁燁城,等.人類活動軌跡的分類、模式和應用研究綜述[J].地理科學進展,2014,33(7):938-948.

[2] 譚祥爽,王靜,宋現(xiàn)鋒,等.基于浮動車數(shù)據(jù)的路口探測方法[J].地理與地理信息科學,2015,31(5):34-38.

[3] 楊偉,艾廷華.基于眾源軌跡數(shù)據(jù)的道路中心線提取[J].地理與地理信息科學,2016,32(3):1-7.

[4] KALNIS P,MAMOULIS N,BAKIRAS S.On discovering moving clusters in spatio-temporal data[A].Proceedings of the 9th International Conference on Advances in Spatial and Temporal Databases[C].Berlin,Germany,2005.364-381.

[5] PEI T,WANG W,ZHANG H,et al.Density-based clustering for data containing two types of points[J].International Journal of Geographical Information Science,2015,29(2):1-19.

[6] ROSSWOG J,GHOSE K.Detecting and tracking coordinated groups in dense,systematically moving,crowds[A].SIAM International Conference on Data Mining[C].2012.

[7] WANG Y,LUO Z,TAKEKAWA J,et al.A new method for discovering behavior patterns among animal movements[J].International Journal of Geographical Information Science,2015,30(5):929-947.

[8] LI Z H,HAN J W,JI M,et al.MoveMine:Mining moving object data for discovery of animal movement patterns[J].ACM Transactions on Intelligent Systems & Technology,2011,2(4):135-136.

[9] TRIPATHI P K,DEBNATH M,ELMASRI R.Extracting dense regions from hurricane trajectory data[A].The Workshop on Managing & Mining Enriched Geo-Spatial Data[C].New York,USA,2014.1-6.

[10] 魯小丫,宋志豪,徐柱,等.利用實時路況數(shù)據(jù)聚類方法檢測城市交通擁堵點[J].地球信息科學學報,2012,14(6):775-780.

[11] KUIJPERS B,OTHMAN W.Modeling uncertainty of moving objects on road networks via space-time prisms[J].International Journal of Geographical Information Science,2009,23(9):1095-1117.

[12] 張峻銘,李靜林,王尚廣,等.基于時空圖的移動對象聚集模式挖掘方法[J].軟件學報,2016,27(2):348-362.

[13] LIU S,LIU Y,NI L M,et al.Towards mobility-based clustering[A].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York,USA,2010.919-928.

[14] JEUNG H,YIU M L,ZHOU X,et al.Discovery of Convoys in trajectory databases[J].Computer Science,2010,1(1):1068-1080.

[15] ESTER M,KRIEGEL H P,SANDER J,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[A].Proceedings of KDD-96(C)[C].1996,96(34):226-231.

[16] LAUBE P,IMFELD S.Analyzing relative motion within groups of trackable moving point objects[A].International Conference on Geographic Information Science[C].Berlin Germany,2002.132-144.

[17] LI Z,DING B,HAN J,et al.Swarm:Mining relaxed temporal moving object clusters[A].Proceedings of the Vldb Endowment[C].2010,3(1):723-734.

[18] LI Y,BAILEY J,KULIK L.Efficient mining of platoon patterns in trajectory databases[J].Data and Knowledge Engineering,2015,100:167-187.

[19] LI Y,HAN J,YANG J.Clustering moving objects[A].Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York,USA,2004.617-622.

[20] ZHANG T,RAMAKRISHNAN R,LIVNY M.BIRCH:An efficient data clustering method for very large databases[A].Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data[C].New York,USA,1996.103-114.

[21] MACQUEEN J.Some methods for classification and analysis of multivariate observations[A].Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability[C].1967.281-297.

[22] BASCH J,GUIBAS L J,HERSHBERGER J.Data structures for mobile data[J].Journal of Algorithms,1999,31(1):1-28.

[23] JENSEN C S,LIN D,OOI B C.Continuous clustering of moving objects[J].IEEE Transactions on Knowledge and Data Engineering,2007,19(9):1161-1174.

[24] 張俊濤,李志勇,張浩,等.利用出租車軌跡數(shù)據(jù)估計城市道路擁堵狀況[J].測繪工程,2016,25(9):68-72.

[25] 趙天天,張晶,王彥兵.基于實時路況數(shù)據(jù)的原發(fā)性交通擁堵點判別——以北京市二環(huán)以內(nèi)為例[J].地理與地理信息科學,2015,31(3):104-107.

[26] CHEN J,MENG X.Clustering analysis of moving objects[A].Moving Objects Management[C].Berlin,Germany,2010.151-171.

[27] 翟丹潤,馬駿.基于道路網(wǎng)絡的移動對象的聚類算法研究[J].河南大學學報(自然科學版),2011,41(1):95-97.

Algorithm Comparison for Clustering of Moving Objects in Traffic System

LIU Wen-kai,TANG Jian-bo,CAI Jian-nan,XIONG Qiang-qiang,LIU Qi-liang

(DepartmentofGeo-informatics,SchoolofGeosciencesandInfo-physics,CentralSouthUniversity,Changsha410083,China)

Existing location-acquisition technologies such as Global Positioning Systems and Wireless Sensor Networks have generated large amounts of moving object data.Discovery of clustering patterns from moving objects is useful for the study of wildlife migration,the prediction of travel time and the prediction of anomalies in traffic systems.Currently,clustering of moving objects has played a key role in spatio-temporal data mining,and a series of moving objects clustering algorithms have been proposed based on the spatial clustering algorithms.Although the application of moving objects clustering in traffic systems has attracted more attentions in recent years,an objective evaluation of existing moving objects clustering algorithms is still lacking.On that account,a comparative analysis of four typical moving objects clustering algorithms (Convoy,Swarm,Platoon and Moving Cluster) is presented in this study.The GPS (Global Position System) trajectories dataset in Beijing is used to test the performance of different algorithms.The performance of these algorithms is evaluated based on the number of patterns,the lifetime of patterns and the moving distances of patterns.The experimental results show that the clustering results are seriously affected by the time continuous constraint,and the method designed for discovering Convoy pattern is the most effective for the discovery of traffic congest.The effect of clustering parameters on these four algorithms is also analyzed.

moving objects;clustering analysis;GPS trajectories

2016-09-16；

2016-10-24

國家自然科學基金項目(41601410)；資源與環(huán)境信息系統(tǒng)國家重點實驗室開放基金；國家級大學生自由探索項目(201610533401)

劉文凱(1993-)，男，碩士研究生，主要研究方向為時空動態(tài)目標聚類分析。E-mail:wenkai.liu@csu.edu.cn

10.3969/j.issn.1672-0504.2016.06.012

TP311.13；U491.1

A

1672-0504(2016)06-0069-06