張敬偉 劉紹建 楊 青 周 婭

1(廣西可信軟件重點實驗室(桂林電子科技大學(xué)) 廣西桂林 541004)

2(廣西自動檢測技術(shù)與儀器重點實驗室(桂林電子科技大學(xué)) 廣西桂林 541004)

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

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

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

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

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

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

Fig. 2 Cluster boundary points圖2 聚類邊界點

Fig. 3 Loose connections圖3 松散連接

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

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算法通過使用CDAP(cosine distance of the angle between two points)對軌跡點進行密度聚類，可以有效地擴大相似于對象運動方向上的軌跡點發(fā)現(xiàn)，同時減少與對象運動方向差異大的軌跡點發(fā)現(xiàn).TCB算法以密度聚類結(jié)果作為輸入，根據(jù)每一快照下的每個邊界點形成一個邊界點劃分集合，通過計算集合成員間的相似度，對邊界點進行合理劃分.聚類平衡算法采用貪心策略的思想，每次計算盡最大可能劃分更多邊界點，以取得局部最優(yōu)解.

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

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

1 相關(guān)工作

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

1.1 Flock和Convoy

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

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

1.2 Group，Platoon，GCMP

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

1.3 Swarm和Traveling companion

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

1.4 Gathering

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

2 問題定義

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

Table 1 Symbol Definition List表1 符號定義列表

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

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

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

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

下面給出一個實例來理解UCP.當G=2，K=3，M=3，L=2時，給定一個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個符合條件的UCP，分別為UC1={Os,(1,2,4,5)}，UC2={Os,(9,10,11)}.

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

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

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

(1)

(2)

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

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

3.1 DBSCANCD算法

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

DBSCANCD使用了考慮運動方向和距離2個維度的CDAP度量方式，下面給出了CDAP距離的定義及計算方式：

(3)

(4)

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

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

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

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

算法1.DBSCANCD算法.

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

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

3.2 TCB算法

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

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

(5)

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

(6)

(7)

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

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

(8)

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

算法2.TCB算法.

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

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

①S←0；

②CB←CR；

③ if |CP|<1

④ 輸出CB；

⑤ end if

⑥ whileCP≠0

⑦q←CP的第1個元素；

⑧CP←CP-q；

⑨M←SBS(BPC(q))；

⑩ ifM中的成員不相等

4 分布式UCP挖掘框架

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

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

4.1 GSPR算法

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

算法3.GSPR算法.

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

輸出：相互獨立的STG集STGS.

① forSrinStar

② if |Sr中的所有時間點|≥K

③S←使用G劃分Sr中的時間點；

④ forsiinS

⑤ if |si|≥K

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

⑦ end if

⑧ end for

⑨ end if

⑩S←?；

nj.label

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

4.2 SAE算法

SAE算法將GSPR算法輸出的STGS作為輸入，STGS中的每一個STG都相互獨立，為了充分利用計算機的多線程特性，本文將SAE算法中加入多線程特性，以提高從STGS中挖掘UCP的效率.一條長軌跡往往攜帶著諸多的運動信息，它可能與不同的或相同的長軌跡集合在不同的時刻形成伴隨狀態(tài)，雖然現(xiàn)有的方法采用前向閉包檢測能有效地提高挖掘任務(wù)的時間效率，但也導(dǎo)致了長軌跡的部分伴隨信息丟失.SAE算法與現(xiàn)有挖掘算法一樣，對每一個線程中的挖掘任務(wù)進行前向閉包檢測，從而提前結(jié)束挖掘任務(wù).但與現(xiàn)有方法不同的是，SAE算法不會錯過長軌跡的伴隨信息，SAE算法的輸入STGS能保證伴隨信息的不流失，同時提高SAE算法對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算法對STGS結(jié)果進行了Map，即SAE開啟了多線程；步驟④定義了一個UCPMinning函數(shù)，輸入為子軌跡群集，輸出為UCP；步驟⑥～對UCP的候選集進行前向閉包檢測，如果(Ou,Ti)為UCP，則提前終止當前線程并輸出結(jié)果；步驟～是SAE算法通過遍歷子軌跡群來持續(xù)更新候選集CA.

5 實驗及分析

5.1 實驗信息

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

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

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

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

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

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

5.1.3 預(yù)處理

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

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

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

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

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

5.2 實驗對比及分析

由于DMFUCP挖掘框架涉及多個算法，為了便于觀察，本文在以下實驗對比與分析中為挖掘框架所使用到的算法進行了簡化表示，具體如表4所示.

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

(9)

Table 4 Simplified Representation表4 方案簡化表示

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

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

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

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

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

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

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

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

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

5.2.3 DMFUCP性能評估

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

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

Fig. 10 TS evaluation of DMFUCP圖10 DMFUCP的TS評估

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

6 總 結(jié)

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

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