王齊童,王 鵬,趙郁亮,2,汪 衛(wèi)

(1.復旦大學 計算機科學技術學院,上海 201203; 2.公安部第三研究所,上海 200031)

0 概述

衛(wèi)星導航和無線通信等技術的廣泛應用產(chǎn)生了大量位置信息數(shù)據(jù),使得路徑導航、社交網(wǎng)絡地點推薦等基于位置的服務(Location Based Service,LBS)成為研究熱點[1]。移動對象的軌跡相似性是時空數(shù)據(jù)挖掘的重要問題,對相似性的研究可以只考慮空間特征,如野生動物的遷徙軌跡分析、車輛軌跡分析,也可以同時考慮時間和空間2個維度的特征,如本文研究的移動對象伴隨模式挖掘問題[2-3]。

移動對象的伴隨模式挖掘是指找到在給定時間段內(nèi)經(jīng)常同時出現(xiàn)在某些地點的對象集合,該技術在智慧城市與城市安全、基于地理位置的用戶行為分析中有廣闊的應用場景:在城市道路監(jiān)控攝像頭捕捉到的車輛過路信息數(shù)據(jù)集中挖掘伴隨車輛,有利于公安隊伍尋找團伙犯罪的嫌疑車輛;在手機基站接入信息數(shù)據(jù)集中挖掘伴隨人群,有利于移動運營商分析用戶的時空特性,協(xié)助基站的規(guī)劃與建設;在社交網(wǎng)絡地點簽到數(shù)據(jù)集中挖掘伴隨用戶,可以協(xié)助社交軟件進行好友、興趣點等多維度的推薦,也可以提供拼團服務。

在上述移動對象的伴隨模式挖掘應用中,對象(車輛、人群、用戶等)在時間維度上密集地連續(xù)分布,但在空間維度上則是離散分布(道路攝像頭、手機基站、商鋪等),這與傳統(tǒng)的野生動物遷徙軌跡分析等軌跡相似性分析應用中對象時空信息由安裝的GPS傳感器定期傳輸,也即時間離散、空間連續(xù)的特點完全不同。此外,上述應用中數(shù)據(jù)量大且中間結果冗余度高,對此,傳統(tǒng)方法是在每個離散的時刻進行空間聚類,再計算兩個或多個對象被聚集到同一聚類中的次數(shù),與給定閾值進行比較。而本文研究的移動對象伴隨模式挖掘問題的數(shù)據(jù)量超過了傳統(tǒng)方法能夠處理的范圍。以北京市道路監(jiān)控攝像真實數(shù)據(jù)集為例,每天的捕捉到的不同車輛數(shù)約200萬,車輛的相遇次數(shù)逾2億,但其中超過99%的相遇都是冗余結果,這兩個特點給移動對象的伴隨模式挖掘帶來了挑戰(zhàn)。

本文面向時空數(shù)據(jù)相似性挖掘中時間連續(xù)、空間離散的新型應用場景，定義并形式化移動對象伴隨模式挖掘問題。針對移動對象時間連續(xù)、空間離散的特點，設計基于單位步長滑動窗口的算法框架，并采用貪心選擇策略[4]消除滑動窗口之間的重疊，利用Apriori性質(zhì)[5]生成多個對象的伴隨模式；針對移動對象時空局部性的特點，設計基于摘要信息的細粒度剪枝方法，并根據(jù)不同強度的時間和空間局部性提出4種摘要信息提取策略。本文將這兩種剪枝策略層疊使用到算法的基本框架中，以提高對移動對象伴隨模式挖掘問題的求解效率。

1 相關研究

大量學者針對移動對象軌跡相似性挖掘進行了研究,方向主要是空間維度的軌跡聚類[6]和時空2個維度的移動對象聚類[7-8]。

對于不同的移動對象時空聚類應用場景,先后有Flock[9-10]、Convoy[11]、Swarm[12-13]、Gathering[14-15]等問題被提出并研究。這四種移動對象聚類模式的基本算法框架均為在每個時間片上分別進行空間聚類,判斷2個或多個對象是否滿足定義的方法,是計算其位于同一聚類的時間片數(shù)量是否超過給定閾值,主要優(yōu)化方法則是利用相鄰時間片之間聚類的相似性。在基本框架上,Flock以距離半徑來確定空間是否接近,并要求位于同一聚類中的時間片是相鄰的。Convoy用基于密度的聚類方法來獲得空間上的相似性,同樣要求時間上的相鄰性。Swarm定義相似模式可以在一定時間閾值內(nèi)間隔性出現(xiàn),聚類方法也是基于密度的聚類。Gathering定義相似模式的對象集合中的對象可以是動態(tài)變化的,例如在游行中會有人隨時進入和離開。但上述4種問題定義均是在時間離散、空間連續(xù)的背景或假設下進行的,且對象的數(shù)量少,這與本文研究的應用場景中時間連續(xù)、空間離散、對象量大、中間結果冗余度高的特點是不一致的,直接使用除了會因為時間分割而帶來漏解的問題,也會由于大量冗余中間結果嚴重影響性能。

在近期其他相關的工作中:文獻[16]從子圖搜索的角度研究了移動軌跡相似性的問題,但并未考慮軌跡的時間特性;文獻[17]與本文研究的問題背景相似,采用了基于Apache Spark[18]的分布式計算流程,但未能解決大量冗余中間結果的問題。文獻[19]采用了基于Apache MapReduce[20]框架設計的分布式Swarm挖掘算法,但同樣未解決大量冗余中間結果的問題。文獻[21]提出的Episode與本文的問題定義類似,但要求模式中的對象在時間上保持順序。

2 問題定義

本文研究的移動對象伴隨模式挖掘問題,針對的是在給定時間段內(nèi)經(jīng)常出現(xiàn)在同一地點的對象集合。為明確出現(xiàn)在同一地點的含義,首先定義相遇的概念,然后為精確計數(shù)對象集合出現(xiàn)在同一地點的次數(shù)定義最大有效相遇集合的概念,其大小即對象集合出現(xiàn)在同一地點的次數(shù)。將計數(shù)對象限制為有效相遇是為了消除對某對象某一次出現(xiàn)的重復計數(shù)。下面將分別對以上概念和移動對象伴隨模式挖掘的問題加以形式化說明。

定義1(k-相遇) 給定時間長度閾值εt和記錄集合R={r1,r2,…,rk},若?r1,r2∈R,ri={oi,li,ti},rj={oj,lj,tj}滿足oi≠oj、li=lj、|ti-tj|≤εt這3個條件時,稱R為一次k-相遇,記為e。

不失一般性,在此假設?r1,r2∈e,如果i≤j,則ti≤tj。因此?r1,r2∈R,|ti-tj|≤εt等價于tk-t1≤εt。稱t1為相遇e的開始時間,tk為相遇e的結束時間。

定義2(有效相遇集合) 給定時間長度閾值εt和對象集合O,滿足以下2個條件的相遇集合E={e1,e2,…,ek}被稱為對象集合O的有效相遇集合,也記為E(O):1)?ei∈E,{oi,j|ri,j={oi,j,li,j,ti,j}∈ei}=O;2) ?ei≠ej∈E,ti,1>tj,k∨tj,1>ti,k。

第2個條件要求在同一個集合中的相遇在時間上是不重疊的,稱為非重疊性。一個對象集合O會有多種不同的有效相遇集合E(O),把最大的有效相遇集合記為EL(O),指O中對象相遇的最多次數(shù)。

定義3(伴隨關系) 給定時間長度閾值εt和頻率閾值εe,對象集合O滿足伴隨關系當且僅當|O|≥2且|EL(O)|≥εe。

將所有滿足伴隨關系的對象集合記為C,所有滿足伴隨關系的大小為k的伴隨關系集合記為Ck。由于滿足伴隨關系的對象集合會具有冗余性(例如滿足伴隨關系的對象集合的非平凡子集都滿足伴隨關系),因此本文進一步給出閉合伴隨關系的定義:

定義4(閉合伴隨關系) 對象集合O滿足閉合伴隨關系當且僅當?O′∈{Oi||EL(Oi)|=|EL(Oi)|},O?O′。

對象集合O滿足閉合伴隨關系,即O的所有超集的最大有效相遇集合都小于O的最大有效相遇集合。移動對象的伴隨模式挖掘問題是在給定數(shù)據(jù)集合中找出所有閉合伴隨關系,移動對象伴隨模式挖掘定義為:給定時間長度閾值εt和頻率閾值εe,返回數(shù)據(jù)集RRec中所有滿足閉合伴隨關系的對象集合。下文以圖1所示的記錄為例對移動對象伴隨模式挖掘問題和相關定義進行說明。

圖1 記錄樣例Fig.1 Example of records

圖1中的每一個元組代表了一條記錄,l1行t1列的元組o1(r1)代表對象o1在t1時刻位于位置l1,也即記錄r1,r1={o1,l1,t1}。不失通用性,本文假設時間等間隔分布,間隔長度為1,即?i,j,|ti-tj|=|i-j|。給定長度閾值εt=4和頻率閾值εe=2,在表1中分別給出定義1～定義4的樣例。

表1 定義1～定義4樣例Table1 Examples of definition 1 to definition 4

表1中的樣例基于圖1中的記錄。在滿足εt的[t1,t4]內(nèi),o1出現(xiàn)了2次,o2和o3各出現(xiàn)了1次,因此,有2個3-相遇(e4與e7)和5個2-相遇(e1、e2、e3、e4、e5、e6)。生成相遇之后,按照非重疊性的要求構造有效相遇集合,共得到19個有效相遇集合(包括11個大小為1的集合),并從中選擇最大有效相遇集合。當候選的最大有效相遇集合不止一個時,任取一個即可以滿足定義要求。所有的最大有效相遇集合均大于等于εe,因此,得到4個滿足伴隨關系的對象集合,其中C4為滿足閉合伴隨關系的對象集合。

表1的樣例也體現(xiàn)了移動對象伴隨模式挖掘問題的大量冗余的中間結果這一特點與挑戰(zhàn)。在表1提供的樣例中,雖然只有1個滿足閉合伴隨關系的對象集合,但需要檢查11個相遇、19個有效相遇集合和4個滿足伴隨關系的對象集合,其中只有2個相遇、1個有效相遇集合與查詢到的滿足閉合伴隨關系的對象集合相關。

3 基于滑動窗口的寬度優(yōu)先搜索算法

本文設計基于滑動窗口的寬度優(yōu)先搜索算法框架,采用Apriori 剪枝策略挑選候選對象集合、縮減搜索空間,利用貪心策略直接選擇具有非重疊性的最大有效相遇集合。由于中間結果的冗余性是移動對象伴隨模式挖掘的難點,因此額外設計針對2-相遇的剪枝過程。

本文算法設計的基本思路是首先生成滿足伴隨關系的大小為k的對象集合,再利用Apriori性質(zhì)來選擇大小為k+1的候選對象集合。在生成滿足伴隨關系的大小為k+1的對象集合時,分別檢查每個地點按時間排序的每個記錄rj,生成長度為[tj-εt,tj]的滑動窗口,窗口中每組(對象不同的)k條記錄均可與rj組成相遇,通過每次有新記錄rj加入的方式來消除滑動窗口之間的重疊,也便于通過選擇最早結束相遇的貪心策略直接生成最大有效相遇集合。

3.1 Apriori 性質(zhì)

獲得滿足伴隨關系的大小為k的對象集合后,本文利用Apriori性質(zhì)來選擇大小為k+1的候選對象集合。Apriori性質(zhì)的形式化定義見定理1。

定理1(Apriori性質(zhì)[22])對Oi?Oj,有|EL(Oi)|≤|EL(Oj)|。

Apriori性質(zhì)說明,如果一個對象集合的任意子集不滿足伴隨關系,則此對象集合不滿足伴隨關系。因此,可以得到剪枝函數(shù)如下:

其中,P(O)=false指O不能通過Apriori性質(zhì)來判斷是否可以剪枝。

3.2 最大相遇集合貪心選擇策略

為在保證非重疊性的同時直接選擇最大有效相遇集合,本文設計選擇最早結束相遇的貪心選擇策略。

定義5(最早結束) 給定相遇集合E,如果一個相遇ei∈E滿足?ej∈E,ti,k≤tj,k,稱ei是E中最早結束的相遇,此處ei={ri,1,ri,2,…,ri,k},ej={rj,1,rj,2,…,rj,k}。

對當前相遇ei是否最早結束的判斷基于與ei有相同對象的所有相遇集合。為獲取最早結束的相遇,對所有相遇按結束時間進行檢查。對于對象集合O,每次獲得尚未加入到最大有效相遇集合的相遇ei,檢查ei開始時間是否長于已加入到最大有效相遇集合中相遇的結束時間的最大值,若滿足則將ei加入到O的最大相遇集合中,否則拋棄ei,繼續(xù)檢查下一個相遇,這樣通過一次掃描即獲得所有對象集合的最大有效相遇集合。

3.3 閉合性檢查

生成Ck+1后,對Ck進行閉合性檢查。如果O∈Ck的超集均不滿足伴隨關系,則O已閉合。閉合函數(shù)定義如下:

3.4 算法基本框架

算法1提供了包含Apriori剪枝、貪心選擇策略和閉合性檢查的基于滑動窗口的閉合伴隨關系挖掘算法基本框架的偽代碼。

算法1基于滑動窗口的閉合伴隨關系挖掘算法

輸入εt,εe,RRec

輸出所有滿足閉合伴隨關系的對象集合CC

1.k=1,初始化C1

2.while Ck≠? do

3.C′k+1=Apriori_Generate(Ck)

4.過濾不在C′k+1中對象的記錄

5.for li∈LLoc

6.for rj∈Sorted(Rec(li))

7.Greedy_Choose({rk|tk∈[tj-εt,tj]})

8.更新C′k+1

9.過濾C′k+1,得到Ck+1

10.Close_Check(Ck,Ck+1)

11.更新CC

12.k=k+1

13.return CC

對于Ck,k=1時用所有出現(xiàn)次數(shù)大于等于εe的對象初始化Ck,k≠1時用Apriori性質(zhì)進行初始化。算法1第5行的過濾可以減少需要檢查的記錄的數(shù)量,也可以減少需要檢查的相遇數(shù)量,第8行對大小為k+1的未檢查相遇中結束時間最早的相遇進行檢查,并對候選集合C′k+1進行更新。檢查過所有相遇之后,對頻率進行過濾,并挑選閉合伴隨關系,開始下一次迭代。假設所有的相遇數(shù)量為|NE|,該算法的復雜度即為|NE|。該算法不僅能夠有效地生成所有的閉合伴隨模式集合,而且可以通過貪心策略進行優(yōu)化,篩除不能組成最大有效相遇集合的相遇。

基于算法1的基本框架,可給出如圖2所示的算法流程。算法在從小到大的寬度優(yōu)先搜索過程中,分別對每個地點、每個滑動窗口的每個相遇進行檢查,檢查的主要內(nèi)容為是否滿足貪心條件,添加的剪枝操作也在此處進行,同時在生成候選伴隨模式集合和閉合伴隨模式集合的過程中會進行閉合性檢查。

圖2 算法1流程Fig.2 Procedure of algorithm 1

4 2-相遇剪枝算法

在算法1中C1生成C2時,由于C1是所有對象的集合,只能根據(jù)每個對象在數(shù)據(jù)集中出現(xiàn)的總次數(shù)進行剪枝,而不能利用任何時空信息(時空信息只在考慮相遇時有用),因此Apriori性質(zhì)對C2候選集的剪枝效果是最差的,2-相遇具有最高的偽命中率,需要針對2-相遇設計專用的剪枝算法。2-相遇剪枝是指對大小為2的對象集合和相遇集合的剪枝操作,在算法1中用于替代由C1生成C2的過程。添加剪枝操作后的算法框架如圖3所示。

圖3 加入剪枝操作后的算法流程Fig.3 Procedure of algorithm after adding pruning operations

本文提出的2-相遇剪枝算法是結合了基于哈希的迭代過濾和基于摘要信息的過濾的兩層剪枝算法,剪枝的過程隨著2-相遇的搜索同時進行?；诠５牡^濾即PCY算法[19],其針對具有相同哈希值的一組對象集合進行剪枝;基于摘要信息的過濾則利用了對象的時空局部性特點求解對象集合的相遇上界進行細粒度的剪枝。

因為基于哈希的迭代過濾和基于摘要信息的過濾分別使用了不同的原理與信息進行剪枝,所以可以結合這兩種方法來增強剪枝效果。

4.1 基于哈希的迭代過濾

基于哈希的迭代過濾是將2-相遇對應的對象集合散列到一個哈希空間上,每一個分桶用來計數(shù)擁有對應哈希值的2-相遇個數(shù)。如果某個計數(shù)值小于εe,則說明對應該哈希值的所有對象集合的總2-相遇個數(shù)小于εe,他們都是可被剪枝掉的冗余對象集合和冗余相遇集合。在進行一輪剪枝之后,可以對未能剪枝掉的對象集合進行第2輪散列、計數(shù)與剪枝,此時由于第一輪被剪枝掉的對象和記錄已不再計數(shù),因此迭代可以提供更好的剪枝效果。

以下為基于哈希的迭代過濾的形式化定義:任意一個2-相遇ei={ri1=(oi1,li1,ti1),ri2=(oi2,li2,ti2)},不失通用性,使oi1

PH(ei)=H[h(oi1,oi2)]<εe

Mj=|{ei|h(oi1,oi2)=j}|

若PH(ei)=true,則ei對應的對象集合Oi不能滿足伴隨關系,因為與ei哈希值相同的相遇總數(shù)小于εe。

對于多層的哈希索引,剪枝公式為:

PH(ei)=

基于滑動窗口的算法2用于生成哈希表H。其中,第4行代碼確定當前滑動窗口范圍[rj.t-εt,rj.t],第5行掃描當前窗口的所有2-相遇,增加對應哈希值的計數(shù)。算法2的復雜度同樣為|NE|,但由于該算法不存儲每個相遇的具體信息,在線性的算法復雜度基礎上具有非常小的常數(shù),因此效率較高。

算法2哈希表H生成算法

輸入εt,εe,RRec,NH

輸出H=[H1,H2,…,HNH]

1.for n ∈ [1,NH]

2.for li∈LLoc

3.for rj∈Sorted(Rec(li))

4.for rk∈Sorted(Rec(li)) and rk.t≤rj.t∧rk.t+εt≥rj.t

5.for n ′∈[1,n)

6.If H′n[h′n(oi1,oi2)]≥εe

7.Hn[hn(oi1,oi2)]+=1

8.return H

在算法2中,可以用額外的哈希表記錄單個對象能組成的2-相遇數(shù),從而對記錄進行篩選,從而在生成不同層次的哈希表H過程中減少需要比較的記錄數(shù)量。

4.2 基于摘要信息的剪枝方法

基于摘要信息的過濾計算2個對象能夠相遇的次數(shù)上界,能夠充分利用對象的時空信息。在每個位置l,對象oi和oj有效相遇次數(shù)的上界是oi和oj出現(xiàn)在l的較小值,對所有位置的上界加和可得到全局上界B。若B<εe,則oi和oj有效相遇次數(shù)小于εe,是可以被剪枝掉的冗余值。進一步可以考慮應用場景中不同的時空特性,通過改變“位置”的粒度,對位置進行聚類或者按時間分割,可以調(diào)節(jié)計算復雜度與剪枝率之間的權衡。

下面給出基于摘要信息的剪枝的形式化定義。對對象oi,摘要信息S(oi)是記錄其在每個位置出現(xiàn)次數(shù)的字典結構,形式化定義如下:

S={S(oi)|oi∈OObj}

S(oi)=[(L1,ai,1),(L2,ai,2),…,(LNL,ai,NL)]

ai,j=|{rk|rk=(ok,lk,tk),ok=oi,lk=Lj}|

對于對象集合Oi={oi1,oi2},通過摘要信息S可以計算得到Oi的最大有效相遇集合的上界為:

其中,min{ai1,k,ai2,k}是oi1和oi2在地點Lk的最大有效相遇次數(shù)的上界,加和之后得到oi1和oi2的最大有效相遇次數(shù)的上界,可以利用此上界進行剪枝:

PS(ei)=B({oi1,oi2})<εe

對于不同的時間長度閾值εt和頻率閾值εe,摘要信息S可以復用,不需要重復計算。

在基于摘要信息剪枝的基礎上,本文提出2種優(yōu)化方法:

1)充分利用應用場景的時空特性,改變“位置”的粒度,如將L1、L2與L3組合成分組G1,作為統(tǒng)計摘要信息和計算上界的基本單元,如果|LLoc|很大且S是稀疏的,分組策略可以降低內(nèi)存消耗,提高算法效率,本文針對不同的應用場景分析特點,提出2種不同的分組策略。

2)提前停止,即如果部分地點的上界和已滿足一定條件,則不需要繼續(xù)計算完整的全局上界。

4.2.1 生成摘要信息的分組策略

首先給出基于分組G={G1,G2,…,GNG}的摘要信息和上界如下:

S(oi)=[(G1,ai,1),(G2,ai,2),…,(GNG,ai,NG)]

ai,j=|{rk|rk=(ok,lk,tk),ok=oi,lk∈Gj}|

本文提出4種不同的分組策略,其中最常用的分組策略是一個位置作為一個組,稱為單地點分組策略。單地點分組策略在2種情況下會失效。第1種情況是|LLoc|很大,上界B的計算消耗了主要的時間。第2種情況是位置Lj是一個非常頻繁的位置,即|RRec(Lj)|很大,很多對象在Lj的出現(xiàn)次數(shù)都臨近εe,導致上界B松弛,非常容易達到εe。

針對|LLoc|很大的情況,最直接的方法是將位置按記錄數(shù)量均勻分組,稱為隨機分組策略。如果可以從記錄中提取連通性信息,也可以將位置基于連通性進行聚類,按照聚類結果進行分組,稱為聚類分組策略。在社交網(wǎng)絡中,連通性通常對應興趣點之間的用戶轉(zhuǎn)移。對連通性可做如下處理:以位置為頂點初始化構造一張圖,對于ri、rj,不妨設ti≤tj,如果oi=oj,li≠lj且tj-ti≤εt,則將li與lj之間邊的權重加1,滿足上述條件隱含著oi在εt時間內(nèi)從li移動到了lj,說明li與lj之間很有可能是連通的,權重的大小也能體現(xiàn)li與lj之間通路的頻繁使用程度,可以用圖上的頂點聚類方法對位置進行聚類,在本文實驗中采用層次聚類。

社交網(wǎng)絡中的伴隨模式挖掘通常具有|LLoc|很大的特征,因為通常網(wǎng)絡中的POI的數(shù)量比較大,文獻[23]中使用的Foursquare數(shù)據(jù)集在過濾了少于10個用戶訪問的POI之后有105個POI,而且POI用戶訪問的稀疏性是非常高的,所以對POI進行分組可以在不影響過濾效果的同時顯著縮短計算時間。在進行分組和聚類時可以考慮POI的類別或城市功能區(qū)的特點,從而進一步利用數(shù)據(jù)的空間特性。

針對RRec(Lj)很大的情況,可進一步將RRec(Lj)按時間等分為子記錄集合,構成分割分組策略。例如,按時間排序的Lj位置的記錄集合RRec(Lj)=[ri,1,ri,2,…,ri,10]可以被劃分成RRec(Gj,1)=[ri,1,ri,2,…,ri,5]和RRec(Gj,2)=[ri,6,ri,7,…,ri,10]。需要注意的是ri,5和ri,6有可能會組成相遇,因此,需要對劃分的集合保留一定重疊以保證上界成立。

城市道路監(jiān)控車輛數(shù)據(jù)集和手機基站接入信息數(shù)據(jù)集通常具有RRec(Lj)很大的特征,因為監(jiān)控攝像頭和手機基站都可以被動捕捉附近對象的信息。由于車輛和手機的使用者數(shù)量都是非常大的,而且不同用戶的交通行為通常具有一定的時間規(guī)律,例如很多車輛只會在早晚高峰出現(xiàn),工作日和周末的出現(xiàn)特征不同,因此,分割之后可以顯著降低每個組上界的B,從而提高剪枝率。在進行分割時可以充分考慮數(shù)據(jù)集的規(guī)律性,如按照早晚高峰和非高峰時段、工作日和周末進行劃分,從而進一步利用數(shù)據(jù)的時間特性。

在實際使用中也可以堆疊不同的摘要信息進行多層的摘要信息過濾。例如可以采用聚類分組策略和劃分分組策略結合的方法,對于數(shù)據(jù)量小的地點進行聚類,對數(shù)據(jù)量大的地點進行劃分,利用聚類分組策略計算速度快、分割分組策略上界更緊的性質(zhì)來平衡運算速度和過濾效果。

4.2.2 提前停止

可以使用由前i個分組計算得到的部分上界Bi進行剪枝,定義如下:

在上式中,加號右側(cè)是未檢查的分組2個對象各自的出現(xiàn)總次數(shù)的最小值,可以在檢查每個地點時通過減去當前地點的出現(xiàn)次數(shù)來進行更新。部分上界Bi(Oj)具有?i∈[1,NG],Bi(Oj)≥B(Oj)的性質(zhì),因此,如果在計算B(Oj)的過程中發(fā)現(xiàn)某部分上界Bi(Oj)<εe,則B(Oj)<εe,Oj可以被剪枝掉,形式化定義如下:

4.3 兩層剪枝算法偽代碼

算法3給出了2-相遇剪枝算法的偽代碼。算法的框架與算法1基本一致,只是在第7行考察是否要貪心地將當前相遇加入到候選集合中前,先后進行了基于哈希的剪枝和基于摘要信息的剪枝以縮減候選集合。

算法32-相遇剪枝算法

輸入εt,εe,RRec,NMR,NMC,S

輸出C2

1.過濾掉出現(xiàn)次數(shù)少于εe的對象

2.調(diào)用算法2生成H

3.k=1,初始化C1

4.for li∈LLoc

5.for rj∈Sorted(RRec(li))

6.for rk∈Sorted(RRec(li)) and rk.t≤rj.t∧rk.t+εt≥rj.t

7.If not PH({rj,rk})∧not PS({rj,rk})

8.貪心選擇{rj,rk}

9.更新C2

10.Return C2

5 實驗結果與分析

實驗在單臺機器進行,處理器為Intel Core i5-3570 3.4 GHz,內(nèi)存大小為16 GB,操作系統(tǒng)為64位Windows 8.1,JDK版本為1.8.0_152。

實驗在國內(nèi)某市道路車輛監(jiān)控車牌識別真實數(shù)據(jù)集上進行,相關統(tǒng)計信息見表2,由于實驗前已對數(shù)據(jù)進行了清洗和隱私處理,因此表中的時間為采集數(shù)據(jù)的持續(xù)時間,對象數(shù)量即不同的車輛數(shù),地點數(shù)量即不同的監(jiān)測點數(shù)量。在實驗過程中,由于基本算法和其他對比方法[12-13,19]均不含有任何剪枝操作,需要的內(nèi)存空間超過系統(tǒng)內(nèi)存上限,估計運行時間比實驗中報告的各最差時間慢至少1個數(shù)量級(×10),因此在以下部分不單獨報告基本算法和其他對比方法的運行時間,與基本算法和其他對比方法的比較通過剪枝率來體現(xiàn)。

表2 測試數(shù)據(jù)的統(tǒng)計信息Table 2 Statistics information of test data

基于哈希的迭代過濾算法生成了兩層哈希表。生成多層哈希表雖然會進一步提高剪枝率,但由于增加了生成哈希表的初始化時間和額外一次哈希檢查的時間,運行時間反而會有一定程度減少。實驗中報告的所有運行時間均為5次實驗的平均值。

5.1 數(shù)據(jù)集規(guī)模對算法性能的影響

圖4給出了各算法在不同大小數(shù)據(jù)集上的運行時間,圖5給出了各算法在不同大小數(shù)據(jù)集上的剪枝率,圖6給出了兩層剪枝算法在不同大小數(shù)據(jù)集上各步驟的運行時間,圖7給出了各算法運行在不同大小數(shù)據(jù)上通過過濾的相遇中真實相遇的比例,其中真實相遇指最終組成伴隨模式的相遇,即對應伴隨模式的最大有效相遇集合。實驗中使用的哈希表單層的長度為150 000 000,相遇時間閾值εt=180,相遇次數(shù)閾值εe標記在圖中。相遇次數(shù)閾值εe的選擇方法是使算法找到的伴隨模式數(shù)量大致相同且均不超過1 000,方便在后續(xù)尋找犯罪團伙的嫌疑車輛等應用中的人工參與。

圖4 不同數(shù)據(jù)集規(guī)模下的運行時間Fig.4 Running time under different sizes of dataset

圖5 不同數(shù)據(jù)集規(guī)模下的剪枝率Fig.5 Pruning rate under different sizes of dataset

圖6 不同數(shù)據(jù)集規(guī)模下兩層剪枝算法各步驟的運行時間Fig.6 Running time of each step of two-layer pruningalgorithm under different sizes of dataset

圖7 不同數(shù)據(jù)集規(guī)模下的真實相遇比例Fig.7 True encounter ratio under different sizes of dataset

從圖4和圖5可以看出,算法在不同規(guī)模的數(shù)據(jù)集上都能夠有效地運行,且本文提出的兩層剪枝算法具有最低的剪枝率,剪枝率均小于1%。剪枝率的計算方法是通過過濾的相遇個數(shù)除以總的相遇個數(shù)。總相遇個數(shù)是在按照相遇次數(shù)閾值對記錄進行過濾之后計算出的,過濾的方法是檢查每個記錄對應的對象在整個數(shù)據(jù)集中出現(xiàn)的總次數(shù)是否小于相遇次數(shù)閾值,如果小于相遇次數(shù)閾值則將該條記錄從數(shù)據(jù)集中刪除。除在15 d的數(shù)據(jù)集上以外,兩層剪枝算法都具有最短的運行時間。在7 d和15 d的數(shù)據(jù)集上僅利用摘要信息的剪枝方法與其他2種方法的剪枝率相差最小,由于僅利用摘要信息的剪枝方法不需要對不同的參數(shù)進行初始化,因此在15 d的數(shù)據(jù)集上反而具有最短的運行時間。

圖5顯示了兩層剪枝算法各個步驟的運行時間,基于哈希的迭代過濾算法也具有類似的特性。其中:初始化步驟是指初始化哈希表;過濾步驟是指進一步對通過剪枝過濾的對象集合進行檢查,找到真實的伴隨模式;生成步驟是指從大小為2的伴隨模式生成更大的伴隨模式的過程。從圖5中可以看出,初始化過程占據(jù)了多數(shù)運行時間。此外,隨著數(shù)據(jù)集的增大,生成過程所用的時間也逐漸增加。

圖7顯示了通過剪枝過濾的相遇中真實相遇的比例,可以看出兩層剪枝算法中真實相遇比例是最高的,均超過了50%。

5.2 摘要信息分組策略對算法性能的影響

圖8和圖9顯示了不同的摘要信息分組策略下算法的運行時間和剪枝率。實驗是在7 d的數(shù)據(jù)集下運行的,相遇時間閾值εt=180,相遇次數(shù)閾值εe=38,哈希表單層的長度為100 000 000。后綴 O 指單地點分組策略,S 指分割分組策略,G200指分為200組的隨機分組策略,C200指分為200組的聚類分組策略。從圖8可以看出,兩層剪枝算法運行時間最短。在兩層剪枝算法中使用聚類分組策略可達到最短的運行時間,因為在兩層剪枝算法的剪枝率都很高的情況下,聚類分組策略的計算代價較小。在不同分組策略的橫向比較中,組數(shù)越多剪枝率越高。聚類分組策略由于可以利用空間局部性,效果比隨機分組策略好。通過圖8與圖9的比較也可以看出,運行時間與剪枝率成正比,剪枝率越高,運行時間越短。

圖8 摘要信息分組策略對運行時間的影響Fig.8 Influence of summary information groupingstrategies on running times

圖9 不同摘要信息分組策略下的剪枝率Fig.9 Pruning rate under different summary informationgrouping strategies

5.3 相遇次數(shù)閾值對算法性能的影響

圖10～圖13顯示了不同相遇次數(shù)閾值下算法的運行時間和剪枝率。實驗是在7 d的數(shù)據(jù)集下運行的,相遇時間閾值εt=180,哈希表單層的長度為100 00 000。

圖10 相遇次數(shù)閾值對運行時間的影響Fig.10 Influence of thresholds of encounter time on running times

圖11 不同相遇次數(shù)閾值下兩層剪枝算法各步驟的運行時間Fig.11 Running time of each step of two-layer pruningalgorihm under different thresholds of encounter time

圖12 不同相遇次數(shù)閾值下的剪枝率Fig.12 Pruning rate under different thresholds ofencounter time

圖13 不同相遇次數(shù)閾值下的真實相遇比例Fig.13 True encounter ratio under different thresholds ofencounter time

從圖10可以看出,除最高的42次相遇次數(shù)閾值之外,兩層剪枝算法都具有最短的運行時間。當相遇次數(shù)閾值為42時,由于比較高的相遇次數(shù)閾值使得候選對象集合減少、剪枝率提高,且基于摘要信息的剪枝算法不需要初始化時間,基于摘要信息的剪枝算法運行時間最短。從圖11可以看出,隨著相遇次數(shù)閾值的提高,初始化時間逐漸穩(wěn)定,且占據(jù)了兩層剪枝算法多數(shù)的運行時間。從圖12可以看出,兩層剪枝算法和基于哈希的剪枝算法的剪枝率隨相遇次數(shù)閾值提高而有所下降,主要是因為隨著相遇次數(shù)閾值的提高,候選對象集合的數(shù)量有所下降。而對基于摘要信息的剪枝算法而言,剪枝率隨相遇次數(shù)先降后升,主要是由于在相遇次數(shù)閾值提高時,基于摘要信息的剪枝算法的剪枝效果更為明顯。從圖13可以看出,兩層剪枝算法仍具有最好的剪枝效果,真實相遇比例基本穩(wěn)定在50%以上。

5.4 相遇時間閾值對算法性能的影響

圖14～圖17對在不同相遇時間閾值下算法的運行時間和剪枝率進行了介紹。實驗是在7 d的數(shù)據(jù)集下運行的,相遇次數(shù)閾值εe=30,哈希表單層的長度為100 000 000。

圖14 不同相遇時間閾值下的運行時間Fig.14 Running time under different thresholds ofencounter time

圖15 不同相遇時間閾值下兩層剪枝算法各步驟的運行時間Fig.15 Running time of each step of two-layer pruningalgorithm under different thresholds of encounter time

圖16 不同相遇時間閾值下的剪枝率Fig.16 Pruning rates under different thresholds ofencounter time

圖17 不同相遇時間閾值下的真實相遇比例Fig.17 True encounter ratio under different thresholds ofencounter time

從圖14可以看出,除最低的90 s相遇時間閾值之外,兩層剪枝算法都具有最短的運行時間。在最低的相遇時間閾值時基于摘要信息的剪枝算法具有最短的運行時間的原因與圖10中相遇次數(shù)閾值為42的情況類似,都是因為候選對象集合的數(shù)量較少,而基于摘要信息的剪枝算法不需要初始化時間,因此整體運行時間較短。圖15中各個步驟的運行時間比例也體現(xiàn)出,隨著相遇時間閾值的提高,剪枝步驟所占據(jù)的時間逐漸提高。從圖16和圖17中可以看出,在不同相遇時間閾值下,兩層剪枝算法具有最高的剪枝率,且通過兩層剪枝算法過濾后的相遇中真實相遇比例也最高。

6 結束語

公安犯罪團伙嫌疑車輛分析、基于地點的社交網(wǎng)絡用戶推薦等應用具有時間連續(xù)、空間離散、時空相關、數(shù)據(jù)量大的特點,針對此類場景中的移動對象相似性挖掘需求,本文研究移動對象的伴隨模式挖掘問題,構建基于Apriori框架和貪心選擇的算法框架,提出一種結合基于哈希迭代剪枝和摘要信息剪枝的兩層剪枝算法,以解決中間結果過多的問題,提高挖掘效率?；谡鎸崝?shù)據(jù)的實驗結果表明,本文算法可以穩(wěn)定去除99%以上的中間數(shù)據(jù)。為進一步提高算法的可擴展性,后續(xù)將基于Apache Spark[20]等分布式計算平臺實現(xiàn)算法及相應的剪枝策略,以應對分布式情景帶來的挑戰(zhàn)。