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

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

引 言

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

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

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

1 問題描述

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

根據(jù)以上特性，本文對移動群體的匯聚運(yùn)動行為進(jìn)行形式化。設(shè)移動對象集合ODB={o1,…,on}，時(shí)間區(qū)間T=〈t1,…,tm〉，其中移動對象o的軌跡定義為o.traj=〈(pt1,t1),…,(ptm,tm)〉，pti=(xti,yti)∈R2，ti∈T，o.pti為o在ti時(shí)刻的空間位置。在ti時(shí)刻所有對象的位置點(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ù)鄰域概念引申出另外兩個定義 ：(1)匯聚模式中心點(diǎn)pa的ε-鄰域，記作Nε(pa)；(2)以匯聚點(diǎn)pa為中心，以半徑r為距離閾值的鄰域，記作Nr(pa)。Nr(pa)是群體匯聚后的停留區(qū)域，而Nr(pa)是指移動對象從不同方向朝向匯聚點(diǎn)pa運(yùn)動的區(qū)域，如圖1所示。

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

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

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

定義5(匯聚群體) 給定移動對象集合ODB和時(shí)間閾值k1，在te時(shí)刻以pa為匯聚點(diǎn)參與匯聚的移動對象集合記作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 問題定義

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

1.3 總體框架

本文提出的移動對象匯聚模式挖掘的總體框架主要包括以下4個階段：

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

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

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

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

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

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

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

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

對于點(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簡要描述了這一過程。首先計(jì)算每個點(diǎn)的密度(行1～5)，然后計(jì)算每個點(diǎn)與密度更高點(diǎn)的距離(行6～10)，最后判斷每個點(diǎn)是否滿足閾值要求(行11～13)。算法時(shí)間復(fù)雜度為O(n2)，使用R樹索引后，時(shí)間復(fù)雜度為O(n·logn)。

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

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

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

輸入：移動對象集合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//如果每個分區(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í)刻匯聚模式

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

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

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

輸入：移動對象集合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)個時(shí)刻。本文實(shí)驗(yàn)所有程序采用Java語言編寫，運(yùn)行在CentOS 6.4操作系統(tǒng)上，硬件平臺的配置情況為2個6核Intel(R) Xeon(R) CPU，主頻為2.40 GHz，內(nèi)存為32 GB。

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

與本文研究最接近的工作是文獻(xiàn)[4]中提出的聚集模式及其算法，該算法是目前在聚集模式挖掘方面最新的研究成果，因而以此作為基準(zhǔn)測試方法。實(shí)驗(yàn)將從模式定義有效性和挖掘算法效率兩方面對匯聚模式和聚集模式進(jìn)行比較。在模式定義有效性方面，通過人工檢查的方式對模式挖掘的結(jié)果進(jìn)行分類，分析有效模式所占比例，比例越高說明模式挖掘效果越好。這里的有效模式是指移動群體的運(yùn)動中心區(qū)域在地理空間中與(Point of interest，POI)重合的模式。而算法效率的比較相對簡單，主要考慮不同數(shù)據(jù)量下的算法運(yùn)行時(shí)間，時(shí)間越短則效率越高。通過前文的分析可以發(fā)現(xiàn)，兩種模式最大的區(qū)別在于模式定義中是否考慮移動群體的運(yùn)動方向。本文實(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，聚集快照中移動對象的個數(shù)閾值mc=15，相鄰簇的豪斯多夫距離閾值δ=300 m，群體生命期閾值kc=10，參與者生命期閾值kp=5，參與者個數(shù)閾值mp=10。

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

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

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

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

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

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

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

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

3.4 算法效率

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

為了進(jìn)一步發(fā)現(xiàn)兩種挖掘算法性能差異的原因，本文實(shí)驗(yàn)將挖掘算法分為兩個階段，分別是預(yù)處理階段和模式挖掘階段。R樹索引僅在兩種模式的挖掘階段被使用。如圖6所示,首先可以發(fā)現(xiàn)隨著數(shù)據(jù)量的增加兩種算法各階段的執(zhí)行時(shí)間均隨之增加。在兩種模式的4個階段中，聚集模式的預(yù)處理階段最耗時(shí)，這是由于該階段需要進(jìn)行DBSCAN聚類計(jì)算，該計(jì)算的時(shí)間復(fù)雜度較高(具有索引支撐的DBSCAN時(shí)間復(fù)雜度為O(nlogn),否則為O(n2)。其次，發(fā)現(xiàn)聚集模式的TAD算法對于數(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ùn)動過程建模的時(shí)空軌跡匯聚模式。該模式定義可以有效地解決現(xiàn)有聚集模式和伴隨模式挖掘中無法避免的“停車場”問題。基于此模式定義設(shè)計(jì)并實(shí)現(xiàn)了匯聚模式挖掘算法CPM。該算法首先使用算法DPQ定位密度峰值點(diǎn)，并以此作為候選的匯聚中心區(qū)域,然后使用算法CGM識別單一時(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.