基于時(shí)空軌跡的移動(dòng)對(duì)象匯聚模式挖掘算法

張逸凡 趙 斌 孫鴻艷 談 超 吉根林

(南京師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 南京，210023)

引 言

衛(wèi)星定位和移動(dòng)互聯(lián)技術(shù)的日趨成熟催生了海量的時(shí)空軌跡數(shù)據(jù)。它們真實(shí)記錄了移動(dòng)對(duì)象的運(yùn)動(dòng)行為特征，包括位置、時(shí)間、方向和速度等屬性。采集并分析移動(dòng)對(duì)象群體(簡(jiǎn)稱群體)的軌跡數(shù)據(jù)，可以有效地揭示群體運(yùn)動(dòng)的行為規(guī)律和常見模式。所以時(shí)空軌跡的群體模式挖掘是一個(gè)具有理論意義和應(yīng)用價(jià)值的研究課題。通常，時(shí)空軌跡模式分為共現(xiàn)模式、伴隨模式、聚集模式、頻繁模式和異常模式等[1,2]。本文主要研究時(shí)空軌跡的聚集模式挖掘問題。2005年，由Laube等首次提出了定義移動(dòng)對(duì)象運(yùn)動(dòng)模式的REMO模型[3]，其中定義了基于時(shí)空維度的聚集模式，即Aggregation模式。該模式規(guī)定在單個(gè)時(shí)間片中存在足夠多的面向同一圓形區(qū)域運(yùn)動(dòng)的移動(dòng)對(duì)象，且運(yùn)動(dòng)的方向向量都與該圓形區(qū)域相交，最終通過計(jì)算各方向向量延長(zhǎng)線的交點(diǎn)來(lái)識(shí)別聚集模式。2013年，鄭凱等提出了聚集模式Gathering[4,5]，并總結(jié)了聚集模式的5種特征，分別是規(guī)模性、密集性、持久性、靜態(tài)性、專一性。Gathering模式由至少個(gè)連續(xù)時(shí)刻的密集快照構(gòu)成，同時(shí)要求至少個(gè)參與者(Participator)必須在不低于個(gè)密集快照(可以不連續(xù))中出現(xiàn)。Gathering模式的優(yōu)點(diǎn)是放松了參與者必須在連續(xù)密集快照中出現(xiàn)的要求，在保證足夠參與性的同時(shí)也兼顧了每個(gè)時(shí)刻的對(duì)象密集性，這更適合實(shí)際的應(yīng)用場(chǎng)景。2015年，鄭宇等研究基于STG圖 (Spatio-temporal graph)的聚集模式。他們通過分析人群的移動(dòng)行為發(fā)現(xiàn)城市中的黑洞模式[6]。該研究與眾不同之處在于研究拓?fù)浣Y(jié)構(gòu)上的聚集模式問題。時(shí)空軌跡的伴隨模式研究在建模方法上與聚集模式的比較接近。伴隨模式是指群體在時(shí)間維度上連續(xù)出現(xiàn)，在空間維度上密集存在。典型的研究工作主要有Flock[7-9],Moving cluster[10],Convoy[11,12],Swarm[13]以及Traveling companions[14]等伴隨模式。Flock模式是指群體在連續(xù)的k個(gè)時(shí)刻中都在空間中維持圓形的聚集形狀，并且這些時(shí)刻的聚集共享一定數(shù)量的移動(dòng)對(duì)象。Convoy模式放松了群體的聚集形狀必須為圓形的要求，采用了密度相連的方式識(shí)別伴隨運(yùn)動(dòng)的群體。Swarm模式考慮到部分移動(dòng)對(duì)象在某些時(shí)刻可能臨時(shí)離開，然后又重回聚集群體。因而，在時(shí)間維度上放松為k個(gè)非連續(xù)的時(shí)刻要求。而Traveling companions模式則在處理方式采用在線處理的方式從時(shí)空軌跡流中挖掘伴隨模式。不難發(fā)現(xiàn)，早期伴隨模式的研究方法被借鑒到后續(xù)聚集模式研究中。例如，聚集模式的定義依然沿用了伴隨模式定義的基本思路。經(jīng)過分析可以發(fā)現(xiàn)，雖然聚集模式和伴隨模式在群體形狀、密度以及時(shí)間連續(xù)性方面各有不同，但是它們都是基于多時(shí)刻的共現(xiàn)模式所構(gòu)成。這種建模方法的優(yōu)點(diǎn)是可以從空間位置關(guān)系上準(zhǔn)確識(shí)別“在一起”的群體，從而滿足模式中“聚集存在”的需要，但是缺點(diǎn)也十分明顯。由于缺乏群體在運(yùn)動(dòng)形態(tài)上的判斷，因而無(wú)法避免“停車場(chǎng)”問題的出現(xiàn)。“停車場(chǎng)”問題是指聚集在一起的群體在連續(xù)時(shí)刻內(nèi)不發(fā)生空間位置的改變，如同停車場(chǎng)一樣。雖然處于“停車場(chǎng)”中的群體在連續(xù)時(shí)刻內(nèi)都在空間鄰域中聚集存在，但顯然與聚集模式和伴隨模式的基本思想不符合。

為了解決“停車場(chǎng)”問題對(duì)聚集模式挖掘的干擾，本文提出了兼顧群體運(yùn)動(dòng)方向的聚集模式挖掘問題,也就是對(duì)群體運(yùn)動(dòng)過程進(jìn)行建模，識(shí)別持續(xù)朝向中心區(qū)域聚集的群體匯聚模式，簡(jiǎn)稱匯聚模式。與傳統(tǒng)的聚集模式相比，匯聚模式挖掘中增加了對(duì)群體運(yùn)動(dòng)形態(tài)的甄別，提高了識(shí)別群體聚集行為的準(zhǔn)確性，但也為算法設(shè)計(jì)增加了難度，主要表現(xiàn)在如下兩方面：(1)匯聚模式的定義。已有的聚集模式和伴隨模式都是基于群體的“共現(xiàn)”思想來(lái)設(shè)計(jì)并定義的。但是在匯聚模式中只有群體聚集到中心區(qū)域時(shí)才會(huì)表現(xiàn)出共現(xiàn)模式，在此之前無(wú)法采用共現(xiàn)模式的挖掘算法跟蹤并識(shí)別移動(dòng)群體。所以，本文提出的匯聚模式無(wú)法完全采用共現(xiàn)模式進(jìn)行定義。(2)群體運(yùn)動(dòng)形態(tài)具有復(fù)雜性。在現(xiàn)實(shí)應(yīng)用場(chǎng)景中，群體的運(yùn)動(dòng)形態(tài)具有多樣性。例如，有向心運(yùn)動(dòng)的群體，有隨機(jī)運(yùn)動(dòng)的群體，也有靜止不動(dòng)的群體。多種類型群體在空間維度上相互重合交織，這為匯聚模式識(shí)別增加了難度。

為了應(yīng)對(duì)上述挑戰(zhàn)，本文提出的匯聚模式針對(duì)移動(dòng)群體的聚集過程進(jìn)行建模。在模式定義中引入運(yùn)動(dòng)方向，從群體運(yùn)動(dòng)形態(tài)出發(fā)進(jìn)行設(shè)計(jì)。這樣可以有效識(shí)別向心運(yùn)動(dòng)的群體，而不受其他運(yùn)動(dòng)類型移動(dòng)對(duì)象的干擾?；诖怂悸?本文設(shè)計(jì)并實(shí)現(xiàn)了匯聚模式的挖掘算法。該算法從匯聚模式的匯聚中心點(diǎn)出發(fā)，首先使用基于密度的聚類算法定位高密度點(diǎn)，并以此作為候選匯聚的中心點(diǎn),然后根據(jù)候選匯聚中心點(diǎn)鄰域中的移動(dòng)群體的運(yùn)動(dòng)形態(tài)識(shí)別向心匯聚模式。最后在連續(xù)時(shí)刻上，挖掘移動(dòng)群體的匯聚模式。

1 問題描述

分析現(xiàn)實(shí)中的匯聚運(yùn)動(dòng)行為可以總結(jié)出如下3個(gè)特性：(1)規(guī)模性。移動(dòng)群體在數(shù)量上應(yīng)該具有規(guī)模性；(2)持續(xù)性。在時(shí)間維度上，群體匯聚行為應(yīng)該持續(xù)一段時(shí)間，形成穩(wěn)定的群體運(yùn)動(dòng)形態(tài)；(3)方向性。在空間維度上，移動(dòng)群體從不同方向朝向同一中心區(qū)域匯聚。

根據(jù)以上特性，本文對(duì)移動(dòng)群體的匯聚運(yùn)動(dòng)行為進(jìn)行形式化。設(shè)移動(dòng)對(duì)象集合ODB={o1,…,on}，時(shí)間區(qū)間T=〈t1,…,tm〉，其中移動(dòng)對(duì)象o的軌跡定義為o.traj=〈(pt1,t1),…,(ptm,tm)〉，pti=(xti,yti)∈R2，ti∈T，o.pti為o在ti時(shí)刻的空間位置。在ti時(shí)刻所有對(duì)象的位置點(diǎn)集合定義為Sti={o.pti|o∈ODB}。

1.1 相關(guān)定義

定義1(鄰域) 給定距離閾值ε和點(diǎn)集S，點(diǎn)p的ε-鄰域定義為Nε(p)={q∈S|D(p,q)≤ε}，其中D(·)表示兩點(diǎn)間的歐氏距離。

根據(jù)鄰域概念引申出另外兩個(gè)定義 ：(1)匯聚模式中心點(diǎn)pa的ε-鄰域，記作Nε(pa)；(2)以匯聚點(diǎn)pa為中心，以半徑r為距離閾值的鄰域，記作Nr(pa)。Nr(pa)是群體匯聚后的停留區(qū)域，而Nr(pa)是指移動(dòng)對(duì)象從不同方向朝向匯聚點(diǎn)pa運(yùn)動(dòng)的區(qū)域，如圖1所示。

圖1 匯聚模式中的P點(diǎn)鄰域 Fig．1 Neighborhood of node P of converging pattern

定義2(鄰域快照) 給定移動(dòng)對(duì)象集合ODB和距離閾值ε，點(diǎn)p在t時(shí)刻的ε-鄰域定義為Nε(p,t)={q∈St|D(p,q)≤ε}。

圖2 匯聚模式方向區(qū)域 Fig．2 Direction regions of converging pattern

定義5(匯聚群體) 給定移動(dòng)對(duì)象集合ODB和時(shí)間閾值k1，在te時(shí)刻以pa為匯聚點(diǎn)參與匯聚的移動(dòng)對(duì)象集合記作Ate，必須滿足以下要求:

(1)Ate?ODB；

(2)設(shè)[te-k1,te]?T，?o∈Ate，滿足o.pte∈N∈(pa,te)，且o.pte-k1?Nr(pa,te-k1)。

1.2 問題定義

給定移動(dòng)對(duì)象集合ODB，匯聚區(qū)域半徑r，方向區(qū)域同向點(diǎn)集的閾值s，時(shí)間閾值k1和k2，時(shí)空軌跡匯聚模式挖掘是在時(shí)間區(qū)間T范圍內(nèi)發(fā)現(xiàn)所有的匯聚模式G。

1.3 總體框架

本文提出的移動(dòng)對(duì)象匯聚模式挖掘的總體框架主要包括以下4個(gè)階段：

(1)數(shù)據(jù)預(yù)處理。真實(shí)的GPS軌跡長(zhǎng)度往往不等，采樣率各不相同。預(yù)處理階段的主要任務(wù)是采用線性插值的方法將不等長(zhǎng)的軌跡基于相同的時(shí)間序列T進(jìn)行“對(duì)齊”。

(2)定位候選的匯聚中心區(qū)域。匯聚模式的中心區(qū)域往往具有高密度的特點(diǎn)，因而通過識(shí)別密度峰值區(qū)域可以確定候選的匯聚中心區(qū)域。

(3)識(shí)別匯聚模式。在階段2的基礎(chǔ)上，分析匯聚中心區(qū)域中的移動(dòng)群體在歷史時(shí)間區(qū)間中的運(yùn)動(dòng)形態(tài)，進(jìn)而識(shí)別匯聚模式及其中心區(qū)域。

(4)展示匯聚模式。通過可視化技術(shù)展示時(shí)空軌跡的匯聚模式，包括匯聚模式的移動(dòng)對(duì)象、匯聚區(qū)域及其中心和匯聚模式的生命周期。

2 算法設(shè)計(jì)

基于匯聚模式定義，本文提出了匯聚模式挖掘算法CPM。該算法包含定位密度峰值點(diǎn)、識(shí)別單時(shí)刻匯聚群體和挖掘匯聚模式3個(gè)階段。由于算法在每個(gè)時(shí)刻都要進(jìn)行多次區(qū)域搜索，因此對(duì)每個(gè)時(shí)刻建立R樹索引。不作說明，下文算法中涉及到區(qū)域搜索的步驟，均使用R樹索引提升效率。

2.1 定位密度峰值點(diǎn)

通常，密度峰值點(diǎn)具有以下兩個(gè)特點(diǎn)：(1)密度峰值點(diǎn)的密度大于其鄰域中其他點(diǎn)的密度；(2)密度峰值點(diǎn)與密度更高的點(diǎn)之間的距離相對(duì)較大。根據(jù)這兩個(gè)特點(diǎn)，Rodriguez等提出了基于密度峰值的聚類算法[15]。

對(duì)于點(diǎn)pi，分別計(jì)算其密度ρi和距離δi，即

(1)

(2)

式中:dij表示pi與pj的距離;dc為搜索半徑，當(dāng)dij-dc< 0時(shí)，f(dij-dc) = 1，否則f(dij-dc) = 0。δi表示pi距離密度更大的點(diǎn)的最小距離。特別地，當(dāng)ρi為最大時(shí)，δi=maxj(dij)。

如果ρi大于密度閾值ρ，δi大于距離閾值δ，則pi為密度峰值點(diǎn)。算法1簡(jiǎn)要描述了這一過程。首先計(jì)算每個(gè)點(diǎn)的密度(行1～5)，然后計(jì)算每個(gè)點(diǎn)與密度更高點(diǎn)的距離(行6～10)，最后判斷每個(gè)點(diǎn)是否滿足閾值要求(行11～13)。算法時(shí)間復(fù)雜度為O(n2)，使用R樹索引后，時(shí)間復(fù)雜度為O(n·logn)。

算法1密度峰值點(diǎn)查找算法(Density peak query,DPQ)

輸入：移動(dòng)對(duì)象點(diǎn)集S，搜索半徑dc，密度閾值ρ，距離閾值δ

輸出：密度峰值點(diǎn)集合P

1.for each pointpi∈S

2.ρi←0;//密度初始化為0

3. for each pointpj∈S

4. if(dij

5.ρi←ρi+1;//密度更新

6.for each pointpi∈S

7.δi←max (dij);

8. for each pointpj∈S

9. if(ρj>ρi)

10.δi←min(δi,dij);//計(jì)算pi距離密度更大的點(diǎn)的最小距離

11.for each pointpi∈S

12. if(ρi>ρa(bǔ)ndδi>δ)

13.P←P∪p;//輸出滿足閾值ρ,δ的點(diǎn)

14.returnP

2.2 挖掘單時(shí)刻向心匯聚群體

算法1簡(jiǎn)要描述了單時(shí)刻向心匯聚群體的挖掘過程。這里，O′表示候選匯聚中心鄰域中的移動(dòng)對(duì)象集合。對(duì)于時(shí)刻te，首先找到候選匯聚模式對(duì)應(yīng)的匯聚中心以外的點(diǎn)集(行2～4)，然后計(jì)算這些點(diǎn)集的密度峰值點(diǎn)，并將其作為候選向心匯聚中心(行5)，最后根據(jù)向心匯聚群體的定義判斷每個(gè)候選向心匯聚在該時(shí)刻是否滿足定義要求(行6～18)。如果滿足要求，則更新其持續(xù)時(shí)間(行13)。如果不滿足要求且該候選向心匯聚的持續(xù)時(shí)間滿足閾值k2，則輸出為閉合匯集模式(行16)。

算法2單時(shí)刻匯聚群體挖掘算法(Converging group mining,CGM)

輸入：移動(dòng)對(duì)象集合ODB，候選匯聚模式C，半徑閾值ε,γ，同向點(diǎn)集的閾值s，時(shí)刻te，時(shí)間閾值k1,k2

輸出：當(dāng)前時(shí)刻匯聚模式R

1.C′←Φ,O′←Φ,R←Φ;

2.for each c∈C

3.O′←O′∪{o|o∈Nε(c.center)};

4.Ste←{o.pte|o∈(ODB-O′)};

5.C←C∪{c|c(pa)∈DPQ(Ste);//計(jì)算當(dāng)前密度峰值點(diǎn)，并將其作為候選向心匯聚中心

6.for eachc∈Cdo

7. if(c. is Converge = false)

8. continue;

9. flag←true;

10.for eachti∈[te-k1+1,te-1] do

12. flag←false;

13. break;

14.if(flag = true) then//如果每個(gè)分區(qū)的點(diǎn)集規(guī)模滿足閾值s，則為匯聚

15.c.updateTime;//更新候選匯聚模式時(shí)間

16.C′←C′∪c;

17. else if(c.lifetime≥k2)

18.R←R∪c;

19. else

20.C.remove(c);//從候選匯聚模式中刪除閉合匯集模式

21.returnR;

2.3 挖掘連續(xù)時(shí)刻匯聚模式

向心匯聚反映了移動(dòng)對(duì)象從四周向中心匯聚的運(yùn)動(dòng)形態(tài)，是一個(gè)匯聚的過程。如果只是單時(shí)刻或者持續(xù)時(shí)間很短的向心匯聚則不能形成一個(gè)大規(guī)模群體事件，這樣的匯聚模式也是沒有意義的。而當(dāng)匯聚模式持續(xù)了較長(zhǎng)的一段時(shí)間，匯聚中心的規(guī)模會(huì)越來(lái)越大，直到達(dá)到一個(gè)峰值后，再趨于穩(wěn)定，然后又慢慢消失,這個(gè)過程恰恰反映了一個(gè)大規(guī)模群體事件從產(chǎn)生到消失的過程。根據(jù)匯聚模式的時(shí)間連續(xù)性，算法按時(shí)間推進(jìn)，使用單時(shí)刻匯聚模式挖掘算法CGM計(jì)算每個(gè)時(shí)刻的閉合匯聚模式，同時(shí)計(jì)算當(dāng)前時(shí)刻的候選匯聚模式并更新候選匯聚模式集合。

算法3簡(jiǎn)要描述了這一過程。R表示匯聚模式集合，C表示當(dāng)前候選匯聚模式集合。算法迭代地調(diào)用單時(shí)刻匯聚模式挖掘算法CGM，并更新當(dāng)前候選集合C(行2～4)，最后輸出所有匯聚模式R。

算法3匯聚模式挖掘算法(Converging patterns mining,CPM)

輸入：移動(dòng)對(duì)象集合ODB，半徑閾值∈、γ，同向點(diǎn)集的閾值s，時(shí)間閾值k1,k2，時(shí)間域T

輸出：匯聚模式集合R

1.R←Φ,C←Φ;

2.for eachte∈T(in ascending order)

3.R←R∪CGM(ODB,C,∈,γ,s,te,k1,k2);

4.C.update;

5.returnR;

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證匯聚模式及其算法的有效性和高效性，本文采用真實(shí)的GPS軌跡數(shù)據(jù)(http://www.ccf.org.cn/sites/ccf/dashuju.jsp?contentId=2756825351305#大賽賽題)進(jìn)行實(shí)驗(yàn)。該數(shù)據(jù)集是北京市12 408輛出租車在2012年11月的GPS數(shù)據(jù)。本文實(shí)驗(yàn)選取了其中11月1日全天的GPS數(shù)據(jù)，共12 408條軌跡，大小為1.8 GB。經(jīng)過軌跡預(yù)處理后，出租車軌跡的時(shí)間區(qū)間以分鐘為單位，共1440(24×60)個(gè)時(shí)刻。本文實(shí)驗(yàn)所有程序采用Java語(yǔ)言編寫，運(yùn)行在CentOS 6.4操作系統(tǒng)上，硬件平臺(tái)的配置情況為2個(gè)6核Intel(R) Xeon(R) CPU，主頻為2.40 GHz，內(nèi)存為32 GB。

3.2 實(shí)驗(yàn)評(píng)價(jià)

與本文研究最接近的工作是文獻(xiàn)[4]中提出的聚集模式及其算法，該算法是目前在聚集模式挖掘方面最新的研究成果，因而以此作為基準(zhǔn)測(cè)試方法。實(shí)驗(yàn)將從模式定義有效性和挖掘算法效率兩方面對(duì)匯聚模式和聚集模式進(jìn)行比較。在模式定義有效性方面，通過人工檢查的方式對(duì)模式挖掘的結(jié)果進(jìn)行分類，分析有效模式所占比例，比例越高說明模式挖掘效果越好。這里的有效模式是指移動(dòng)群體的運(yùn)動(dòng)中心區(qū)域在地理空間中與(Point of interest，POI)重合的模式。而算法效率的比較相對(duì)簡(jiǎn)單，主要考慮不同數(shù)據(jù)量下的算法運(yùn)行時(shí)間，時(shí)間越短則效率越高。通過前文的分析可以發(fā)現(xiàn)，兩種模式最大的區(qū)別在于模式定義中是否考慮移動(dòng)群體的運(yùn)動(dòng)方向。本文實(shí)驗(yàn)將證明考慮方向性的匯聚模式比聚集模式在挖掘效果和算法效率兩方面表現(xiàn)得更出色。

3.3 挖掘算法有效性

在分析兩種模式的有效性之前，先介紹實(shí)驗(yàn)參數(shù)的設(shè)置情況。匯聚模式的參數(shù)設(shè)置為：匯聚中心區(qū)域定位算法的距離閾值dc=1 000 m，密度閾值ρ=20，峰值點(diǎn)間的距離閾值δ=1 500 m，半徑閾值ε=800 m，r=5 000 m，方向區(qū)域同向點(diǎn)集閾值s=5，時(shí)間閾值k1=20，k2=5。

聚集模式的參數(shù)設(shè)置為：DBSCAN數(shù)量閾值m=5，半徑閾值ε=200 m，聚集快照中移動(dòng)對(duì)象的個(gè)數(shù)閾值mc=15，相鄰簇的豪斯多夫距離閾值δ=300 m，群體生命期閾值kc=10，參與者生命期閾值kp=5，參與者個(gè)數(shù)閾值mp=10。

首先通過可視化技術(shù)在地圖上展示兩種模式的挖掘結(jié)果，即地理空間中的分布情況?？梢悦黠@發(fā)現(xiàn)聚集模式在數(shù)量上多于匯聚模式，兩者空間分布差異性較大。匯聚模式主要集中在北京市三環(huán)以內(nèi)人流量較多的地方；而聚集模式分布較為廣泛，不局限在城市的中心區(qū)域，如圖3所示。

圖3 模式挖掘結(jié)果可視化Fig．3 Visualization of mining pattern

為了能夠量化評(píng)估模式挖掘的有效性，結(jié)合群體運(yùn)動(dòng)的地理位置對(duì)挖掘結(jié)果進(jìn)行分類，劃分成3種類型：路口聚集、停車場(chǎng)聚集和POI聚集。其中，路口聚集是指移動(dòng)群體在道路路口的停留；停車場(chǎng)聚集表明移動(dòng)群體在某個(gè)固定區(qū)域長(zhǎng)時(shí)間滯留，移動(dòng)群體本身變動(dòng)較少；POI聚集是指地理空間中人們感興趣的位置，如體育場(chǎng)、交通樞紐和娛樂場(chǎng)所等。不難發(fā)現(xiàn)，只有POI聚集可以體現(xiàn)模式挖掘的有效性。

按照上述分類，作者將2016年11月1日一天中兩種模式挖掘算法的結(jié)果統(tǒng)計(jì)在表1中。可以發(fā)現(xiàn)，聚集模式發(fā)現(xiàn)了326個(gè)結(jié)果，遠(yuǎn)遠(yuǎn)多于匯聚模式的40個(gè)結(jié)果。但是73.3%的結(jié)果都屬于停車場(chǎng)聚集。經(jīng)過分析發(fā)現(xiàn)，大量出租車停留在交通樞紐的停車場(chǎng)，或者下午集中停留在出租車?？奎c(diǎn)，這些位置大多是路邊。而POI聚集一共28個(gè)，占8.6%。這樣的結(jié)果說明聚集模式的挖掘質(zhì)量不高，有效的聚集比例較低。另一方面，匯聚模式中POI聚集共33個(gè)，占82.5%，在絕對(duì)數(shù)量上超過聚集模式，并且匯聚模式挖掘算法的質(zhì)量較高，可以發(fā)現(xiàn)更多有意義的模式。

表1 2012年11月1日北京市的匯聚模式和聚集模式挖掘情況

圖4 匯聚模式和聚集模式挖掘結(jié)果的交集 Fig．4 Intersection of converging and gathering

針對(duì)同一份軌跡數(shù)據(jù)，兩種模式挖掘結(jié)果中存在4個(gè)相同的POI聚集結(jié)果。按照發(fā)生地點(diǎn)、時(shí)間和規(guī)模的不同展現(xiàn)在圖4中。矩形框的粗細(xì)代表群體模式的規(guī)模大小，長(zhǎng)短表示群體模式持續(xù)的時(shí)間。通過分析可以發(fā)現(xiàn)以下結(jié)果：(1)這4個(gè)相同的POI聚集主要發(fā)生在交通樞紐；(2)匯聚模式出現(xiàn)的時(shí)刻主要為早晚高峰，也就是交通樞紐最繁忙的時(shí)間段，但是有一半的聚集模式發(fā)生的時(shí)間段在凌晨，主要是交通樞紐的停車區(qū)域;(3)從群體模式規(guī)模上來(lái)看，匯聚模式普遍大于聚集模式。

之所以有這樣的差異，和兩種模式的定義有關(guān)。聚集模式主要考慮各個(gè)時(shí)刻移動(dòng)群體的聚集狀態(tài)，而不考慮聚集的運(yùn)動(dòng)過程及方向，這就出現(xiàn)了聚集模式無(wú)法解決的“停車場(chǎng)”問題。移動(dòng)群體在早晚高峰期的交通路口減速慢行或者等待紅綠燈時(shí)，被識(shí)別成一個(gè)密集區(qū)域。按照聚集模式定義，持續(xù)一段時(shí)間這樣的群體聚集行為被識(shí)別為聚集模式。而匯聚模式關(guān)注于聚集形成的運(yùn)動(dòng)過程，很自然地類似“停車場(chǎng)”這樣的模式都被過濾掉，所以最終的挖掘結(jié)果質(zhì)量比較高。

3.4 算法效率

本節(jié)將比較兩種模式挖掘算法的執(zhí)行效率。 分別比較1 000條、2 000條、3 000條、4 000條和5 000條軌跡數(shù)據(jù)的測(cè)試結(jié)果。如圖5所示，同樣數(shù)據(jù)量情況下匯聚模式挖掘算法CPM比聚集模式挖掘算法TAD[4]效率更高，并且十分明顯。因而，在算法整體運(yùn)行時(shí)間上CPM算法優(yōu)勢(shì)明顯。

為了進(jìn)一步發(fā)現(xiàn)兩種挖掘算法性能差異的原因，本文實(shí)驗(yàn)將挖掘算法分為兩個(gè)階段，分別是預(yù)處理階段和模式挖掘階段。R樹索引僅在兩種模式的挖掘階段被使用。如圖6所示,首先可以發(fā)現(xiàn)隨著數(shù)據(jù)量的增加兩種算法各階段的執(zhí)行時(shí)間均隨之增加。在兩種模式的4個(gè)階段中，聚集模式的預(yù)處理階段最耗時(shí)，這是由于該階段需要進(jìn)行DBSCAN聚類計(jì)算，該計(jì)算的時(shí)間復(fù)雜度較高(具有索引支撐的DBSCAN時(shí)間復(fù)雜度為O(nlogn),否則為O(n2)。其次，發(fā)現(xiàn)聚集模式的TAD算法對(duì)于數(shù)據(jù)集的增加比較敏感。這主要是TAD算法中包含了較為耗時(shí)的豪斯多夫距離計(jì)算，時(shí)間復(fù)雜度為O(mn)。所以，在聚集模式挖掘中采用了聚類算法和豪斯多夫距離計(jì)算兩種耗時(shí)的計(jì)算步驟，這是影響挖掘算法效率的主要因素。

圖5 不同數(shù)據(jù)量的算法效率比較 圖6 不同數(shù)據(jù)量的算法各階段效率比較Fig．5 Performance comparison of algorithms under data size Fig.6 Performance comparison of stages under data size

4 結(jié)束語(yǔ)

本文提出了一種基于群體運(yùn)動(dòng)過程建模的時(shí)空軌跡匯聚模式。該模式定義可以有效地解決現(xiàn)有聚集模式和伴隨模式挖掘中無(wú)法避免的“停車場(chǎng)”問題?；诖四Ｊ蕉x設(shè)計(jì)并實(shí)現(xiàn)了匯聚模式挖掘算法CPM。該算法首先使用算法DPQ定位密度峰值點(diǎn)，并以此作為候選的匯聚中心區(qū)域,然后使用算法CGM識(shí)別單一時(shí)刻的向心匯聚群體。最后將CGM算法應(yīng)用到連續(xù)時(shí)間片上，挖掘出所有滿足規(guī)模性和持續(xù)性要求的匯聚模式。為了驗(yàn)證本文提出的匯聚模式及其算法的優(yōu)越性，本文以真實(shí)的軌跡數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)表明本文提出的匯聚模式及其算法在挖掘效果和算法效率兩方面都明顯優(yōu)于現(xiàn)有的聚集模式的挖掘方法。

參考文獻(xiàn):

[1] Zheng Y. Trajectory data mining: An overview[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2015, 6(3): 1-29,41.

[2] 吉根林, 趙斌. 時(shí)空軌跡大數(shù)據(jù)模式挖掘研究進(jìn)展[J]. 數(shù)據(jù)采集與處理, 2015, 30(1): 47-58.

Ji Genlin, Zhao Bin. Research progress in pattern mining for big spatio-temporal trajectories[J].Journal of Data Acquision and Processing,2015,30(1):47-58.

[3] Laube P, Marc V K, Stephan I. Finding REMO-detecting relative motion patterns in geospatial lifelines [M]. Berlin: Springer, 2005: 201-215.

[4] Zheng K, Zheng Y, Yuan N J, et al. On discovery of gathering patterns from trajectories[C]// IEEE 29th International Conference on Data Engineering. Brisbane, Australia:[s.n], 2013: 242-253.

[5] Zheng K, Zheng Y, Yuan N J, et al. Online discovery of gathering patterns over trajectories[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 8(26): 1974-1988.

[6] Hong L, Zheng Y, Yung D, et al. Detecting urban black holes based on human mobility data[C]//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. Bellevue, WA, USA:[s.n], 2015, 35:1-10.

[7] Benkert M, Gudmundsson J, Hübner F, et al. Reporting flock patterns[C]//European Symposium on Algorithms. Zurich, Switzerland:[s.n], 2006: 660-671.

[8] Vieira M R, Bakalov P, Tsotras V J. On-line discovery of flock patterns in spatio-temporal data[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference On Advances In Geographic Information Systems. Seattle, Washington, USA:[s.n], 2009: 286-295.

[9] Gudmundsson J, Kreveld M J. Computing longest duration flocks in trajectory data[C]//Proceedings of the 14th Annual ACM International Symposium on Advances In Geographic Information Systems. Arlington, Virginia, USA:[s.n], 2006: 35-42.

[10] Kalnis P, Mamoulis N, Bakiras S. On discovering moving clusters in spatio-temporal data[C]//International Symposium on Spatial and Temporal Databases. Angra dos Reis, Brazil:[s.n], 2005: 364-381.

[11] Jeung H, Yiu M L, Zhou X, et al. Discovery of convoys in trajectory databases[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 1068-1080.

[12] Jeung H, Shen H T, Zhou X. Convoy queries in spatio-temporal databases[C]//2008 IEEE 24th International Conference on Data Engineering. Cancun, Mexico:[s.n], 2008: 1457-1459.

[13] Li Z H, Ding B L, Han J W, et al. Swarm: Mining relaxed temporal moving object clusters[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2): 723-734.

[14] Tang L A, Zheng Y, Yuan J, et al. On discovery of traveling companions from streaming trajectories[C]//2012 IEEE 28th International Conference on Data Engineering. Washington D C, USA:IEEE, 2012: 186-197.

[15] Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.