DMFUCP:大規(guī)模軌跡數(shù)據(jù)通用伴隨模式分布式挖掘框架

張敬偉 劉紹建 楊 青 周 婭

1(廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué)) 廣西桂林 541004)

2(廣西自動(dòng)檢測(cè)技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué)) 廣西桂林 541004)

具有定位功能的移動(dòng)設(shè)備的普及使用，軌跡數(shù)據(jù)呈現(xiàn)爆炸式增長(zhǎng)，例如日本大阪的ATC購(gòu)物中心[1]在2012年10月28日的1天內(nèi)能記錄下4 000萬(wàn)以上的軌跡點(diǎn)；T-Drive[2]中超過(guò)33 000輛出租車在3個(gè)月內(nèi)生成了7.9億以上的軌跡點(diǎn)，平均采樣時(shí)間為3.1分鐘/點(diǎn).軌跡數(shù)據(jù)多為時(shí)空序列，被攜帶有定位裝置的移動(dòng)對(duì)象不斷以固定的頻率產(chǎn)生，蘊(yùn)含著豐富的價(jià)值.在大規(guī)模的軌跡中提取出通用伴隨模式具有重要的意義，為上層的服務(wù)提供了諸多可能.通用伴隨模式挖掘可用于改善城市交通狀況，通過(guò)發(fā)現(xiàn)通用伴隨模式可以預(yù)測(cè)某一時(shí)間段內(nèi)某段道路是否會(huì)發(fā)生交通擁堵，從而提前疏導(dǎo)交通以避免交通擁堵；處于相同通用伴隨模式的一組群體往往具有某些相似的特征，通過(guò)對(duì)這些相似的特征進(jìn)行挖掘可以提高社會(huì)推薦服務(wù)；通用伴隨模式挖掘在事件調(diào)查方面也具有廣泛運(yùn)用場(chǎng)景，通過(guò)挖掘的通用伴隨模式為尋找事件發(fā)生的可能原因提供支持.

伴隨模式是指在某一范圍內(nèi)一定數(shù)量的運(yùn)動(dòng)對(duì)象在某一時(shí)間段內(nèi)伴隨運(yùn)動(dòng)，它具有時(shí)間性和空間性.軌跡數(shù)據(jù)中挖掘伴隨模式的方法從實(shí)現(xiàn)方案上可分為分布式與單機(jī)2類.分布式方案分為數(shù)據(jù)處理、數(shù)據(jù)分區(qū)和軌跡挖掘3個(gè)階段，單機(jī)方案可分為數(shù)據(jù)處理和軌跡挖掘2個(gè)階段.

現(xiàn)有的研究大多關(guān)注于如何在軌跡數(shù)據(jù)中快速地挖掘出伴隨模式，將整個(gè)挖掘任務(wù)的重點(diǎn)放在軌跡挖掘階段，對(duì)數(shù)據(jù)處理階段則采用基于歐氏距離的密度聚類或圓盤聚類.但在現(xiàn)實(shí)生活與實(shí)踐運(yùn)用中，挖掘出對(duì)象間運(yùn)動(dòng)方向相似的比運(yùn)動(dòng)方向差異大的軌跡更具有實(shí)際意義，對(duì)基于歐氏距離的聚類方法形成了挑戰(zhàn).如圖1所示，采用歐氏距離的聚類方法會(huì)將(o1,t3)，(o2,t3)聚為一類，但在現(xiàn)實(shí)生活中將(o2,t3)，(o3,t3)聚為一類更具有意義，因?yàn)楹芸赡軐?duì)象o1與對(duì)象o2在岔路口處選擇了不同的路，而o3與o2選擇了相同的路.亟需一種新的距離度量方式，能實(shí)現(xiàn)在擴(kuò)大對(duì)象運(yùn)動(dòng)方向上的橫向聚類半徑的同時(shí)縮小縱向聚類半徑.

Fig. 1 Unreasonable clustering圖1 不合理聚類

伴隨模式挖掘中的聚類具有時(shí)間相關(guān)性，對(duì)象在某一時(shí)刻的聚類情況與它的上一時(shí)刻和下一時(shí)刻的聚類情況會(huì)對(duì)挖掘結(jié)果產(chǎn)生影響.由于聚類起始點(diǎn)是隨機(jī)選取的，每個(gè)軌跡點(diǎn)也只能被歸為一個(gè)簇，所以在聚類過(guò)程中會(huì)產(chǎn)生一定數(shù)量可同時(shí)歸為不同簇的邊界點(diǎn)，現(xiàn)有的工作單純地按照對(duì)象被訪問的順序進(jìn)行劃分，影響了伴隨模式挖掘的質(zhì)量.怎樣合理地劃分邊界點(diǎn)對(duì)聚類算法形成了挑戰(zhàn).如圖2所示，對(duì)象o2和對(duì)象o3為核心點(diǎn)，對(duì)象o1為邊界點(diǎn)，對(duì)象o1可同時(shí)處于對(duì)象o2與o3所屬的簇，怎樣合理地劃分o1對(duì)于伴隨模式挖掘具有重要意義.

如圖3所示，不同的顏色灰度表示不同的伴隨模式，在現(xiàn)實(shí)生活中會(huì)存在這樣一種現(xiàn)象，大量的軌跡會(huì)集中式地經(jīng)過(guò)一些公共場(chǎng)所，如超市、加油站等，需要伴隨模式挖掘算法去積極地識(shí)別它.GCMP(general co-movement pattern)將這種現(xiàn)象定義為松散連接，通過(guò)設(shè)置參數(shù)G來(lái)避免它，處理效果不好.現(xiàn)實(shí)生活中它很可能是一種正常現(xiàn)象，因?yàn)榘殡S模式具有時(shí)間性，所以對(duì)象o2與對(duì)象o3很可能處于2種不同的伴隨狀態(tài).現(xiàn)有的方法并不能去挖掘和區(qū)分它們，同時(shí)挖掘具有松散連接現(xiàn)象的伴隨模式需要掃描整個(gè)軌跡，對(duì)伴隨模式挖掘算法的性能提出了挑戰(zhàn).

Fig. 2 Cluster boundary points圖2 聚類邊界點(diǎn)

Fig. 3 Loose connections圖3 松散連接

針對(duì)挑戰(zhàn)，本文工作的主要貢獻(xiàn)分為3個(gè)方面：

1) 在數(shù)據(jù)處理階段基于DBSCAN(density-based spatial clustering of applications with noise)提出了DBSCANCD(DBSCAN based on cosine distance between two points)算法和TCB(time-dependent clustering balance)算法，DBSCANCD算法通過(guò)使用CDAP(cosine distance of the angle between two points)對(duì)軌跡點(diǎn)進(jìn)行密度聚類，可以有效地?cái)U(kuò)大相似于對(duì)象運(yùn)動(dòng)方向上的軌跡點(diǎn)發(fā)現(xiàn)，同時(shí)減少與對(duì)象運(yùn)動(dòng)方向差異大的軌跡點(diǎn)發(fā)現(xiàn).TCB算法以密度聚類結(jié)果作為輸入，根據(jù)每一快照下的每個(gè)邊界點(diǎn)形成一個(gè)邊界點(diǎn)劃分集合，通過(guò)計(jì)算集合成員間的相似度，對(duì)邊界點(diǎn)進(jìn)行合理劃分.聚類平衡算法采用貪心策略的思想，每次計(jì)算盡最大可能劃分更多邊界點(diǎn)，以取得局部最優(yōu)解.

2) 在挖掘階段提出了GSPR(Gsegment pruning and repartitioning)算法和SAE(segmented apriori enumerator)算法，通過(guò)對(duì)分區(qū)數(shù)據(jù)進(jìn)行G分段剪枝和重劃分來(lái)有效地挖掘具有松散連接現(xiàn)象的通用伴隨模式，同時(shí)保證SAE算法的性能.

3) 基于DBSCANCD，TCB，GSPR，SAE這4個(gè)算法提出了DMFUCP.DMFUCP利用負(fù)載均衡及合適的Map和Reduce方式降低了Spark進(jìn)行分布式調(diào)度的壓力.使用2個(gè)真實(shí)的軌跡數(shù)據(jù)集對(duì)部署在Spark上的DMFUCP進(jìn)行了大量實(shí)驗(yàn)，本文所提出的DMFUCP在保證性能的同時(shí)，具有更強(qiáng)的通用伴隨模式發(fā)現(xiàn)能力.

1 相關(guān)工作

近年來(lái)，軌跡數(shù)據(jù)的伴隨模式挖掘已被廣泛研究.隨著軌跡數(shù)據(jù)的規(guī)模不斷增長(zhǎng)，如何快速、有效地從大規(guī)模軌跡數(shù)據(jù)中挖掘伴隨模式為科學(xué)研究提供了動(dòng)力.本節(jié)將主要圍繞伴隨模式的時(shí)間戳約束展開總結(jié)分析.

1.1 Flock和Convoy

Flock模式起初是被Laube等人[3-4]提出，只考慮單一時(shí)刻移動(dòng)對(duì)象的行為特征，要求在某時(shí)刻至少有m個(gè)移動(dòng)對(duì)象在同一區(qū)域內(nèi)，并且移動(dòng)方向相同，該定義不能很好地適應(yīng)實(shí)際應(yīng)用；Gudmundsson等人[5-6]對(duì)Flock模式提出了新的定義，即Flock模型，并形式化為flock(m,k,r)；Jeung等人[7]發(fā)現(xiàn)已有的方法不能準(zhǔn)確地檢索出Convoy模式，在現(xiàn)有的基礎(chǔ)上采用著名的過(guò)濾-細(xì)化框架開發(fā)了3種有效的Convoy發(fā)現(xiàn)算法，并使用線性簡(jiǎn)化方法[8]近似模擬原始軌跡，在數(shù)據(jù)庫(kù)查詢中發(fā)現(xiàn)Convoy模式；Orakzai等人[9]發(fā)現(xiàn)傳統(tǒng)的Convoy挖掘方法需要對(duì)每個(gè)快照進(jìn)行DBSCAN聚類，在大數(shù)據(jù)集上消耗的時(shí)間成本過(guò)大，于是提出了k/2-hop算法來(lái)高效地挖掘Convoy模式；Calders等人[10]提出了一種分布式挖掘算法DCM(distributed convoy mining)來(lái)發(fā)現(xiàn)Convoy模式，DCM算法基于分而治之策略且獨(dú)立于任何數(shù)據(jù)處理框架，Calders等人還在Hadoop上實(shí)現(xiàn)了基于DCM算法的DCMMR框架.

Flock模型預(yù)先定義了區(qū)域形狀和群體大小，不能很好地適應(yīng)實(shí)際.為了解決在伴隨模式挖掘中對(duì)移動(dòng)對(duì)象群體大小和形狀的限制，Convoy模型采用密度聚類來(lái)挖掘任意形狀的軌跡，從而避免受預(yù)先定義的空間閾值限定.Flock和Convoy模式要求每個(gè)檢測(cè)到的聚類組的所有快照都連續(xù).

1.2 Group，Platoon，GCMP

Wang等人[11]提出了AGP(apriori-like algorithm for mining valid group patterns)和VG-growth(a valid group graph)算法來(lái)挖掘由距離閾值和最小持續(xù)時(shí)間確定的Group模式，并發(fā)現(xiàn)AGP和VG-growth[12]算法的性能較低，后研究發(fā)現(xiàn)在伴隨模式挖掘前對(duì)原始軌跡數(shù)據(jù)進(jìn)行摘要可以大幅度地提升AGP和VG-growth算法的性能；Bailey等人[13]提出了一種Platoon挖掘算法PlatoonMiner，使用頻繁連續(xù)剪枝、對(duì)象剪枝、子集剪枝和通用前綴剪枝方法來(lái)減少搜索空間；由于現(xiàn)有的工作對(duì)伴隨模式的定義種類繁多，F(xiàn)an等人[14]提出了GCMP模式，并給出了TRPM(temporal replication and parallel mining)和SPARE(star partitioning and apriori enumerator)兩個(gè)算法來(lái)挖掘GCMP模式，GCMP模式包含了4個(gè)可調(diào)參數(shù)M，K，L，G.通過(guò)對(duì)4個(gè)參數(shù)的調(diào)節(jié)可以將GCMP變換為Flock，Convoy，Group，Platoon等不同模式.同時(shí)，TRPM和SPARE這2個(gè)算法被部署在基于內(nèi)存計(jì)算的Spark分布式平臺(tái)上.Group，Platoon，GCMP模式使用了折中的時(shí)間戳約束方案，即局部連續(xù).

1.3 Swarm和Traveling companion

Li等人[15]設(shè)計(jì)了ObjectGrowth算法來(lái)有效地檢索封閉的Swarm模式，ObjectGrowth算法中使用了2種有效的剪枝策略減少搜索空間，并提出了一種新的閉包檢查規(guī)則，用于動(dòng)態(tài)檢索封閉的Swarm.相對(duì)于Flock和Convoy模式，Swarm允許在一定時(shí)間內(nèi)，移動(dòng)對(duì)象在任意形狀區(qū)域內(nèi)一起移動(dòng)而時(shí)間不要求連續(xù).由于在Convoy和Swarm模式挖掘過(guò)程中需要將整個(gè)軌跡加載到內(nèi)存中，Zheng等人[16-17]提出了Traveling companion模式，使用一種traveling buddy的數(shù)據(jù)結(jié)構(gòu)來(lái)不斷地從進(jìn)入系統(tǒng)的軌跡中找到Convoy和Swarm模式.Traveling companion更像是一種在線的Convoy和Swarm模式檢測(cè)方式.Swarm和Traveling companion模式不要求時(shí)間戳連續(xù).

1.4 Gathering

為了檢測(cè)某些事件，如慶祝和游行這類運(yùn)動(dòng)對(duì)象會(huì)頻繁地加入和離開的事件，Zheng等人[18-19]提出了Gathering模型.Gathering模型用于檢測(cè)事件時(shí)還要求檢測(cè)到的事件的幾何屬性相對(duì)穩(wěn)定，如位置和形狀.

2 問題定義

本節(jié)給出一些參數(shù)和基本術(shù)語(yǔ)，如表1所示：

Table 1 Symbol Definition List表1 符號(hào)定義列表

本文主要研究的是怎樣有效地在大規(guī)模軌跡數(shù)據(jù)中挖掘伴隨模式，伴隨模式具體定義：

定義1.通用伴隨模式(universal companion pattern, UCP).給定對(duì)象集O={o1,o2,…,on}，聚類簇集C={c1,c2,…,cn}，(oi,ti,i)∈ci，通用伴隨模式UC={Os,TUs}，其中Os?O,TUs=ti,tj,…,tn,i

UCP具有5個(gè)約束，其中第1個(gè)約束包含距離和方向2個(gè)基本約束，即需要在方向參與計(jì)算得出的距離滿足要求的1組軌跡才具有構(gòu)成通用伴隨模式的基本條件，第2～5個(gè)約束通過(guò)參數(shù)的形式進(jìn)行調(diào)節(jié)以適應(yīng)不同條件下的伴隨模式.例如G=1時(shí)UCP轉(zhuǎn)變?yōu)镃onvoy和Flock，這使得UCP能更好地適應(yīng)現(xiàn)實(shí)生活.與已有的研究不同，本文的參數(shù)G還將用于GSPR算法中的長(zhǎng)軌跡分割.

Fig. 4 Distributed clustering and cluster balance framework圖4 分布式聚類及聚類平衡框架

下面給出一個(gè)實(shí)例來(lái)理解UCP.當(dāng)G=2，K=3，M=3，L=2時(shí)，給定一個(gè)UCP為UC={Os,TUs}，TUs=(1,2,4,5,9,10,11,18)，Os=(1,2,4,5)，聚類簇集C={(Os,1,1),(Os,2,3),(Os,4,7),(Os,5,10),(Os,9,2),(Os,10,4),(Os,11,6),(Os,18,8)}，根據(jù)定義1及參數(shù)G可以得到2個(gè)符合條件的UCP，分別為UC1={Os,(1,2,4,5)}，UC2={Os,(9,10,11)}.

定義2.相鄰軌跡點(diǎn)線段(adjacent trajectory point line segment, ATPS).給定軌跡P=p1,p2,…,pn，其中pn=(xn,yn,tn)，xn為pn的經(jīng)度，yn為pn的緯度，tn為pn的時(shí)間戳，ATPS表示為pS(i)=T[pi:pi+1]，當(dāng)且僅當(dāng)pi+1-pi≤Δt.

定義3.ATPS方向向量，即pVector.給定軌跡T=p1,p2,…,pn，則pVector表示在以0經(jīng)度線和0緯度線構(gòu)成的二維坐標(biāo)中運(yùn)動(dòng)對(duì)象在相鄰時(shí)刻的運(yùn)動(dòng)向量，軌跡T在時(shí)刻i的pVector表示為

pV(Ti)=(xi+1-xi,yi+1-yi).

(1)

(2)

3 分布式聚類及聚類平衡框架

聚類操作對(duì)于軌跡數(shù)據(jù)的模式挖掘具有十分重要的作用，但聚類操作也占據(jù)了模式挖掘整個(gè)過(guò)程的大量時(shí)間.隨著軌跡數(shù)據(jù)規(guī)模的快速增長(zhǎng)，基于單機(jī)模式的挖掘框架很難直接擴(kuò)展.現(xiàn)有的解決方式通常采用分布式方案，分布式可以將互不影響的各個(gè)任務(wù)并行執(zhí)行，從而達(dá)到成倍的速度提升.軌跡數(shù)據(jù)的UCP挖掘具有時(shí)間相關(guān)性，分布式挖掘UCP，首先需要對(duì)每個(gè)快照下的所有對(duì)象進(jìn)行聚類操作，在現(xiàn)實(shí)生活中，整個(gè)軌跡數(shù)據(jù)集往往具有成千上萬(wàn)的快照數(shù)，甚至更多，并且快照數(shù)和數(shù)據(jù)量隨時(shí)間在不斷地增長(zhǎng)，對(duì)這些數(shù)據(jù)進(jìn)行聚類所需要的時(shí)間十分龐大.分析發(fā)現(xiàn)，每個(gè)快照下的軌跡聚類操作互不影響，采用分布式聚類可以為整個(gè)模式挖掘任務(wù)節(jié)省大量時(shí)間.圖4顯示了本文提出的軌跡數(shù)據(jù)分布式聚類及聚類平衡的基本框架，整個(gè)框架包含Map和Reduce這2個(gè)階段.圖4顯示了輸入的原始軌跡、DBSCANCD算法聚類后的結(jié)果、TCB重劃分邊界點(diǎn)后的結(jié)果.

3.1 DBSCANCD算法

現(xiàn)有的大部分研究均采用基于歐氏距離的DBSCAN算法，DBSCAN算法并不考慮對(duì)象的運(yùn)動(dòng)方向，只考慮距離這一單一維度，使大量無(wú)實(shí)際意義的軌跡點(diǎn)被聚類.DBSCANCD是一種基于密度聚類的算法，它同時(shí)考慮了對(duì)象運(yùn)動(dòng)方向和距離2個(gè)維度，并且引入了可調(diào)參數(shù)σ，參數(shù)σ主要受城市道路的彎曲角度和城市道路岔路口角度2個(gè)因素影響.

DBSCANCD使用了考慮運(yùn)動(dòng)方向和距離2個(gè)維度的CDAP度量方式，下面給出了CDAP距離的定義及計(jì)算方式：

(3)

(4)

Fig. 5 The relationship between CDAP and Euclidean distance圖5 CDAP距離與歐氏距離的關(guān)系

DBSCANCD算法可以發(fā)現(xiàn)任意形狀的聚類區(qū)域，與DBSCAN算法不同，DBSCANCD算法的單一聚類區(qū)域不再是圓形，而是一個(gè)近似橢圓的扁平狀區(qū)域.當(dāng)σ=0.5時(shí)，圖6顯示了歐氏距離與CDAP距離在單一聚類區(qū)域上的差異，可以發(fā)現(xiàn)，CDAP距離所形成的聚類區(qū)域更為扁平，單一聚類區(qū)域更加偏向于對(duì)象的運(yùn)動(dòng)方向.

Fig. 6 Comparison between Euclidean distance and CDAP single cluster area圖6 歐氏距離與CDAP距離單一聚類區(qū)域?qū)Ρ?/p>

定義6.聚類邊界點(diǎn)(boundary point).給定對(duì)象集O=o1,o2,…,on，聚類簇集C=c1,c2,…,cn，其中(oi,ti,i)∈ci，?ok∈ci,?ok∈ck，則ok為聚類邊界點(diǎn).

算法1.DBSCANCD算法.

輸入：軌跡數(shù)據(jù)集合Si、聚類半徑ePs、最小簇基數(shù)minPts、向量夾角閾值angle；

輸出：聚類結(jié)果集cluster、邊界點(diǎn)集BPSet.

①cluster←0，BPSet←?，CI←1；

②CrDis←ePs/angle；

③ forsjinSi

④ ifsj沒被訪問

⑤sj←Visited；

⑥C←DCDAP(sj,Si)；

⑦C′←C.filter(0≤distance≤ePs)；

⑧ if |C′|≥minPts

⑨C′←C′-sj；

⑩cluster(j)←CI；

ePs)；

算法1中，步驟①②對(duì)聚類結(jié)果集、邊界點(diǎn)集、CDAP的臨界值和簇號(hào)進(jìn)行了初始化；步驟⑥⑦根據(jù)定義5進(jìn)行了2點(diǎn)間的CDAP距離計(jì)算，并根據(jù)ePs參數(shù)對(duì)計(jì)算結(jié)果進(jìn)行篩選；步驟～對(duì)C′進(jìn)行了廣度優(yōu)先遍歷，找出與sj屬于同一簇的所有對(duì)象；步驟將滿足|W′|≥minPts的所有W′成員添加到C′，以更新C′；步驟～得到了邊界點(diǎn)e，并添加到BPSet集中.

3.2 TCB算法

在對(duì)軌跡數(shù)據(jù)進(jìn)行密度聚類時(shí)，聚類算法通常會(huì)從所有對(duì)象集中隨意挑選一個(gè)對(duì)象作為聚類的起始點(diǎn)，不斷地遍歷對(duì)象集中沒有被訪問過(guò)的對(duì)象.現(xiàn)有的聚類算法遵照先后順序?qū)γ恳粋€(gè)符合要求的軌跡點(diǎn)進(jìn)行聚類，并將其歸入某一簇中，然后將被歸入簇中的點(diǎn)從對(duì)象集中刪除.但對(duì)象集中往往存在一些這樣的對(duì)象，它們可以同時(shí)滿足超過(guò)2個(gè)簇的聚類條件，即定義6中的聚類邊界點(diǎn).軌跡數(shù)據(jù)的UCP挖掘具有時(shí)間相關(guān)性，對(duì)象在相鄰時(shí)刻的聚類情況與它當(dāng)前的聚類情況存在聯(lián)系.單純的按照先后順序?qū)吔琰c(diǎn)進(jìn)行劃分存在合理性問題.

定義7.邊界點(diǎn)生成集(boundary point generating set).給定邊界點(diǎn)i，邊界點(diǎn)i同時(shí)滿足聚類條件的聚類簇集C，|C|≥2，ck,cn∈C，i的邊界點(diǎn)生成集BPC(i)可表示為

(5)

定義8.集合間相似度集(similarity set between sets).給定邊界點(diǎn)i的邊界點(diǎn)生成集BPC(i)，BPC(i)的集合間相似度集SBS(BPC(i))為

(6)

(7)

定義9.最大集合間相似度(maximum similarity between sets).給定邊界點(diǎn)i的邊界點(diǎn)生成集BPC(i)，BPC(i)的集合間相似度集SBS(BPC(i))，BPC(i)的最大集合間相似度MSBS(BPC(i))為

MSBS(BPC(i))=max(SBS(BPC(i))).

(8)

TCB算法很好地改善了邊界點(diǎn)合理劃分問題，與現(xiàn)有的單純按照對(duì)象訪問順序劃分聚類邊界點(diǎn)相比，TCB算法通過(guò)計(jì)算邊界點(diǎn)i的BPC(i)的MSBS(BPC(i))值來(lái)確定i被劃分到哪個(gè)簇更為合理.為了防止當(dāng)前時(shí)刻和相鄰時(shí)刻邊界點(diǎn)i所屬的簇中包含其他邊界點(diǎn)而導(dǎo)致BPC(i)被遞歸計(jì)算，同時(shí)考慮到邊界點(diǎn)i在相鄰時(shí)刻均為邊界點(diǎn)的情況，TCB算法采用貪心策略的思想，在處理邊界點(diǎn)i的劃分問題時(shí)，如果邊界點(diǎn)i在相鄰時(shí)刻同為邊界點(diǎn)，則將相鄰時(shí)刻邊界點(diǎn)i同時(shí)滿足的簇的所有成員添加到BPC(i)，如果邊界點(diǎn)i的當(dāng)前時(shí)刻和相鄰時(shí)刻存在其他邊界點(diǎn)，則將它們僅在當(dāng)前計(jì)算中視為非邊界點(diǎn).采用貪心策略的TCB算法可以減少邊界點(diǎn)處理的次數(shù)，同時(shí)獲得一個(gè)邊界點(diǎn)合理劃分的局部最優(yōu)解.

算法2.TCB算法.

輸入：所有快照下的聚類結(jié)果集CR、邊界點(diǎn)集CP、最小簇的基數(shù)minPt；

輸出：平衡聚類結(jié)果集CB.

①S←0；

②CB←CR；

③ if |CP|<1

④ 輸出CB；

⑤ end if

⑥ whileCP≠0

⑦q←CP的第1個(gè)元素；

⑧CP←CP-q；

⑨M←SBS(BPC(q))；

⑩ ifM中的成員不相等

4 分布式UCP挖掘框架

在大規(guī)模軌跡數(shù)據(jù)中挖掘滿足要求的UCP是一項(xiàng)十分耗時(shí)的任務(wù)，軌跡數(shù)據(jù)中往往具有成千上萬(wàn)的運(yùn)動(dòng)對(duì)象，為了挖掘UCP就不得不遍歷所有的對(duì)象.在成都Taxi數(shù)據(jù)集中，包含120 000以上條長(zhǎng)軌跡和19 000多個(gè)快照，如果通過(guò)直接遍歷它們挖掘UCP，即使采用各種剪枝技術(shù)，挖掘UCP所花費(fèi)的時(shí)間也是十分龐大的.隨著信息時(shí)代的不斷發(fā)展，計(jì)算資源也取得了快速增長(zhǎng).分析發(fā)現(xiàn)，對(duì)每個(gè)運(yùn)動(dòng)對(duì)象進(jìn)行UCP挖掘可以同時(shí)進(jìn)行而不產(chǎn)生干擾，只需為挖掘任務(wù)分配更多的計(jì)算資源便可實(shí)現(xiàn)性能的成倍增長(zhǎng).將UCP進(jìn)行分布式挖掘可以實(shí)現(xiàn)挖掘任務(wù)的并行執(zhí)行，如圖7所示，本文設(shè)計(jì)了一種高效的分布式UCP挖掘框架，實(shí)現(xiàn)了挖掘性能的提升，框架包含Map和Reduce這2階段.圖7顯示了已分區(qū)的數(shù)據(jù)、GSPR算法的切分、剪枝和重劃分的過(guò)程、SAE算法的挖掘過(guò)程.

Fig. 7 Distributed companion pattern mining framework圖7 分布式伴隨模式挖掘框架

4.1 GSPR算法

軌跡數(shù)據(jù)中存在大量的松散連接現(xiàn)象，表現(xiàn)為對(duì)象在2次形成聚類現(xiàn)象之間相隔了相當(dāng)長(zhǎng)的一段時(shí)間.為了高效地挖掘處于松散連接狀態(tài)下不同的UCP，本文設(shè)計(jì)了GSPR算法，GSPR算法使用自定義參數(shù)G實(shí)現(xiàn)對(duì)存在松散連接現(xiàn)象的長(zhǎng)軌跡的切分，并為屬于同一條長(zhǎng)軌跡的每個(gè)分段添加一個(gè)相同的標(biāo)記以避免重劃分過(guò)程的重復(fù)計(jì)算.GSPR算法使用自定義參數(shù)K對(duì)每一個(gè)分段進(jìn)行初步剪枝，在完成初步剪枝后，使用自定義參數(shù)L和K同時(shí)對(duì)分段進(jìn)行剪枝，在剪枝完成后將對(duì)每個(gè)分段進(jìn)行重劃分.最終，大量的長(zhǎng)軌跡將被劃分成一個(gè)包含相互獨(dú)立的子軌跡群，下面給出子軌跡群的具體定義.

算法3.GSPR算法.

輸入：星型分區(qū)數(shù)據(jù)Star，G，M，K，L；

輸出：相互獨(dú)立的STG集STGS.

① forSrinStar

② if |Sr中的所有時(shí)間點(diǎn)|≥K

③S←使用G劃分Sr中的時(shí)間點(diǎn)；

④ forsiinS

⑤ if |si|≥K

⑥N←(Sr.O,si,label)；

⑦ end if

⑧ end for

⑨ end if

⑩S←?；

nj.label

算法3中，步驟②使用K對(duì)星型分區(qū)的每條長(zhǎng)軌跡進(jìn)行首次過(guò)濾；步驟④～⑨首先使用參數(shù)G對(duì)長(zhǎng)軌跡進(jìn)行分割，并對(duì)分割后的各個(gè)分段使用K進(jìn)行二次過(guò)濾，最后給每條長(zhǎng)軌跡的每個(gè)分段添加相同的標(biāo)記；步驟～使用參數(shù)L和K進(jìn)行剪枝，并得到了候選的子軌跡群W；步驟～使用參數(shù)M對(duì)候選的子軌跡群W進(jìn)行過(guò)濾，最終得到有效的子軌跡群并添加進(jìn)STGS.

4.2 SAE算法

SAE算法將GSPR算法輸出的STGS作為輸入，STGS中的每一個(gè)STG都相互獨(dú)立，為了充分利用計(jì)算機(jī)的多線程特性，本文將SAE算法中加入多線程特性，以提高從STGS中挖掘UCP的效率.一條長(zhǎng)軌跡往往攜帶著諸多的運(yùn)動(dòng)信息，它可能與不同的或相同的長(zhǎng)軌跡集合在不同的時(shí)刻形成伴隨狀態(tài)，雖然現(xiàn)有的方法采用前向閉包檢測(cè)能有效地提高挖掘任務(wù)的時(shí)間效率，但也導(dǎo)致了長(zhǎng)軌跡的部分伴隨信息丟失.SAE算法與現(xiàn)有挖掘算法一樣，對(duì)每一個(gè)線程中的挖掘任務(wù)進(jìn)行前向閉包檢測(cè)，從而提前結(jié)束挖掘任務(wù).但與現(xiàn)有方法不同的是，SAE算法不會(huì)錯(cuò)過(guò)長(zhǎng)軌跡的伴隨信息，SAE算法的輸入STGS能保證伴隨信息的不流失，同時(shí)提高SAE算法對(duì)UCP的挖掘效率.

算法4.SAE算法.

輸入：星型分區(qū)數(shù)據(jù)Star，G，M，K，L；

輸出：通用伴隨模式UP.

①STGS←FGSPR(Star,G,M,K)；

②UP←STGSMap(C′→UCPMinning(C′))；

③ 輸出UP.

函數(shù)UCPMinning(C′):

① whileC′≠?

②Ou←C′.O的并集；

③Ti←C′.T的交集；

④ if ?|Ti[m:n]|≥L并且∑(|Ti[m:n]|)≥K并且|Ou|≥M

⑤UP′←(Ou,Ti)；

⑥ break；

⑦ end if

⑧ forciinC′

⑨ forcjinC′

⑩temp←ci.T∩cj.T；

|temp|≥K

算法4中，步驟①調(diào)用了GSPR算法獲得了子軌跡群集STGS；步驟②SAE算法對(duì)STGS結(jié)果進(jìn)行了Map，即SAE開啟了多線程；步驟④定義了一個(gè)UCPMinning函數(shù)，輸入為子軌跡群集，輸出為UCP；步驟⑥～對(duì)UCP的候選集進(jìn)行前向閉包檢測(cè)，如果(Ou,Ti)為UCP，則提前終止當(dāng)前線程并輸出結(jié)果；步驟～是SAE算法通過(guò)遍歷子軌跡群來(lái)持續(xù)更新候選集CA.

5 實(shí)驗(yàn)及分析

5.1 實(shí)驗(yàn)信息

5.1.1 環(huán)境設(shè)置

實(shí)驗(yàn)采用4臺(tái)Dell服務(wù)器，每臺(tái)服務(wù)器擁有128 GB RAM、56個(gè)CPU內(nèi)核(Intel?Xeon?Gold 5117 CPU @2.00 GHz). 4臺(tái)服務(wù)器上一共部署了26個(gè)節(jié)點(diǎn)，其中包括25個(gè)子節(jié)點(diǎn)和1個(gè)主節(jié)點(diǎn).主節(jié)點(diǎn)擁有32 GB RAM、16個(gè)CPU內(nèi)核和1.5 TB ROM，每個(gè)子節(jié)點(diǎn)擁有18 GB RAM、8個(gè)CPU內(nèi)核和0.5 TB ROM.集群系統(tǒng)采用Centos7，Java虛擬機(jī)版本為JDK 1.8，分布式平臺(tái)采用Spark2.3.0，以Yarn的方式搭建在Hadoop 3.1上，集群的統(tǒng)一部署和可視化采用Apache ambari 2.7，整個(gè)UCP挖掘方案使用Scala語(yǔ)言在IDEA 2019.1中實(shí)現(xiàn)，并通過(guò)Maven3.6.0進(jìn)行打包上傳到Spark集群.

5.1.2 數(shù)據(jù)集

本文使用了2個(gè)真實(shí)的軌跡數(shù)據(jù)集.

1) GeoLife[20-22].該數(shù)據(jù)集保存了182名用戶在2008-04—2012-08的旅行記錄.對(duì)于每個(gè)用戶，定期收集GPS信息.

2) Taxi.該數(shù)據(jù)集是成都市14 795輛出租車超過(guò)3億條GPS記錄，時(shí)間從2014-08-03—2014-08-12，其中忽略了00∶00∶00—05∶59∶59這一時(shí)間段的數(shù)據(jù).

5.1.3 預(yù)處理

預(yù)處理中，本文將運(yùn)動(dòng)對(duì)象的原始編號(hào)進(jìn)行了重新編號(hào)，使編號(hào)連續(xù)并由1開始.同時(shí)本文使用了固定頻率(GeoLife數(shù)據(jù)集為5 s，Taxi數(shù)據(jù)集為30 s)對(duì)2個(gè)真實(shí)數(shù)據(jù)集進(jìn)行了處理，使用線性插值對(duì)缺失數(shù)據(jù)進(jìn)行填充，同時(shí)剔除了小于固定頻率的多余數(shù)據(jù).在使用DBSCANCD與DBSCAN聚類算法時(shí)，本文根據(jù)數(shù)據(jù)集的不同設(shè)置了不同的ePs(聚類半徑)和minPts(最小簇基數(shù))值，GeoLife采用ePs=30，minPts=8，angle=0.5，Taxi采用ePs=25，minPts=8，angle=0.5.表2顯示了本文對(duì)2個(gè)真實(shí)數(shù)據(jù)集預(yù)處理后的結(jié)果.

Table 2 Data Preprocessing表2 數(shù)據(jù)預(yù)處理

5.1.4 參數(shù)設(shè)置

為了全面評(píng)估DMFUCP挖掘框架對(duì)UCP的發(fā)現(xiàn)能力及挖掘框架的性能，本文對(duì)設(shè)置的各個(gè)參數(shù)進(jìn)行了實(shí)驗(yàn).表3列出了所有需要評(píng)估的參數(shù).

Table 3 Parameters and Default Values表3 參數(shù)及默認(rèn)值

5.2 實(shí)驗(yàn)對(duì)比及分析

由于DMFUCP挖掘框架涉及多個(gè)算法，為了便于觀察，本文在以下實(shí)驗(yàn)對(duì)比與分析中為挖掘框架所使用到的算法進(jìn)行了簡(jiǎn)化表示，具體如表4所示.

為了更好地比較表4中挖掘框架在挖掘階段的性能，本文給出了挖掘性能的計(jì)算：

(9)

Table 4 Simplified Representation表4 方案簡(jiǎn)化表示

Fig. 8 Evaluation of UCP discovery capability by DMFUCP圖8 DMFUCP對(duì)UCP發(fā)現(xiàn)能力評(píng)估

5.2.1 DMFUCP的UCP發(fā)現(xiàn)能力評(píng)估

圖8顯示了DMFUCP的UCP發(fā)現(xiàn)能力在2個(gè)數(shù)據(jù)集上的評(píng)估結(jié)果.

圖8(a)(b)表示隨著M的變化UCP發(fā)現(xiàn)能力的變化.GeoLife中不同的M對(duì)方案的發(fā)現(xiàn)能力改變相較于Taxi并不明顯，那是因?yàn)镚eoLife的數(shù)據(jù)比較稀疏，M的變化并不會(huì)對(duì)發(fā)現(xiàn)能力產(chǎn)生大的變化.

圖8(c)(d)表示隨著K的變化UCP發(fā)現(xiàn)能力的變化.GeoLife中發(fā)現(xiàn)能力在不同的K值下表現(xiàn)穩(wěn)定，而Taxi則對(duì)不同K值表現(xiàn)的十分敏感，因?yàn)門axi中的長(zhǎng)軌跡包含的快照數(shù)要普遍低于GeoLife中長(zhǎng)軌跡的快照數(shù).

圖8(e)(f)表示隨著L的變化UCP發(fā)現(xiàn)能力的變化.在2個(gè)數(shù)據(jù)集中不同的L值并未對(duì)UCP發(fā)現(xiàn)能力產(chǎn)生太大變化，因?yàn)樵?個(gè)數(shù)據(jù)集中長(zhǎng)軌跡的完整度都很高，線性插值補(bǔ)全也起到了作用.

圖8(g)(h)表示隨著G的變化UCP發(fā)現(xiàn)能力的變化.在GeoLife中采用GSPR算法比Taxi表現(xiàn)更好，GeoLife中會(huì)對(duì)UCP發(fā)現(xiàn)能力有2～3倍的提升，而Taxi中會(huì)有1～2倍的提升，因?yàn)镚eoLife中長(zhǎng)軌跡更長(zhǎng)且存在大量的松散連接現(xiàn)象.

5.2.2 DMFUCP的Platoon與Swarm發(fā)現(xiàn)能力評(píng)估

圖9表示隨著M，K，L的變化Platoon與Swarm發(fā)現(xiàn)能力的變化.采用DCTAE比DAE的Platoon與Swarm發(fā)現(xiàn)能力更好，因?yàn)镈CTAE擴(kuò)大了對(duì)象運(yùn)動(dòng)方向上的對(duì)象發(fā)現(xiàn).不同的M，K，L的變化在Taxi上表現(xiàn)得更加明顯，且DCTAE相對(duì)于DAE對(duì)Platoon與Swarm發(fā)現(xiàn)能力保持在1.7倍左右，因?yàn)門axi中存在的邊界點(diǎn)多于GeoLife.

5.2.3 DMFUCP性能評(píng)估

圖10(a)(b)顯示了DAE，DCTAE，DGS，DCTGS

Fig. 9 The evaluation of Platoon and Swarm’s discovery capability by DMFUCP圖9 DMFUCP對(duì)Platoon和Swarm發(fā)現(xiàn)能力評(píng)估

Fig. 10 TS evaluation of DMFUCP圖10 DMFUCP的TS評(píng)估

在默認(rèn)取值的狀態(tài)下對(duì)GeoLife與Taxi中的UCP發(fā)現(xiàn)性能.DCTGS和DCTAE的TS均高于基準(zhǔn)框架DAE，因?yàn)樗鼈儼l(fā)現(xiàn)UCP數(shù)量的提升要大于時(shí)間消耗的提升.Taxi中DGS的TS略低于DAE，因?yàn)門axi中存在的松散連接現(xiàn)象并不多，這導(dǎo)致DGS發(fā)現(xiàn)UCP數(shù)量的提升要小于時(shí)間消耗的提升.

6 總 結(jié)

本文主要圍繞在保證挖掘框架性能的同時(shí)提高對(duì)UCP的發(fā)現(xiàn)能力，因此，基于DBSCANCD，TCB，GSPR，SAE這4個(gè)算法提出了DMFUCP挖掘框架來(lái)達(dá)到本文的目標(biāo)，DBSCANCD與TCB分別通過(guò)擴(kuò)大有意義點(diǎn)的發(fā)現(xiàn)和合理劃分聚類邊界點(diǎn)來(lái)提高通用伴隨模式挖掘輸入數(shù)據(jù)的質(zhì)量，GSPR算法通過(guò)G對(duì)通用伴隨模式挖掘的輸入進(jìn)行分割和重劃分，在過(guò)濾無(wú)用信息的同時(shí)提高挖掘算法對(duì)UCP的發(fā)現(xiàn)能力，SAE算法則使用多線程和前向閉包使挖掘過(guò)程的時(shí)間消耗大大降低.實(shí)驗(yàn)結(jié)果證明DMFUCP挖掘框架在UCP的發(fā)現(xiàn)能力和TS上均得到了提升.下一步工作將應(yīng)用DMFUCP挖掘框架處理軌跡數(shù)據(jù)流，提升從軌跡數(shù)據(jù)流中發(fā)現(xiàn)UCP的能力和性能.

作者貢獻(xiàn)聲明：張敬偉負(fù)責(zé)提出研究選題、組織建議模型論證分析、優(yōu)化論文；劉紹建負(fù)責(zé)細(xì)化算法、設(shè)計(jì)實(shí)驗(yàn)并開展實(shí)驗(yàn)分析；楊青負(fù)責(zé)調(diào)研整理文獻(xiàn)、模型驗(yàn)證優(yōu)化和設(shè)計(jì)論文框架；周婭負(fù)責(zé)修訂和完善論文.