一種高效的移動(dòng)對(duì)象伴隨模式挖掘算法

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

(1.復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,上海 201203; 2.公安部第三研究所,上海 200031)

0 概述

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

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

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

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

1 相關(guān)研究

大量學(xué)者針對(duì)移動(dòng)對(duì)象軌跡相似性挖掘進(jìn)行了研究,方向主要是空間維度的軌跡聚類(lèi)[6]和時(shí)空2個(gè)維度的移動(dòng)對(duì)象聚類(lèi)[7-8]。

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

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

2 問(wèn)題定義

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

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

不失一般性,在此假設(shè)?r1,r2∈e,如果i≤j,則ti≤tj。因此?r1,r2∈R,|ti-tj|≤εt等價(jià)于tk-t1≤εt。稱(chēng)t1為相遇e的開(kāi)始時(shí)間,tk為相遇e的結(jié)束時(shí)間。

定義2(有效相遇集合) 給定時(shí)間長(zhǎng)度閾值εt和對(duì)象集合O,滿足以下2個(gè)條件的相遇集合E={e1,e2,…,ek}被稱(chēng)為對(duì)象集合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個(gè)條件要求在同一個(gè)集合中的相遇在時(shí)間上是不重疊的,稱(chēng)為非重疊性。一個(gè)對(duì)象集合O會(huì)有多種不同的有效相遇集合E(O),把最大的有效相遇集合記為EL(O),指O中對(duì)象相遇的最多次數(shù)。

定義3(伴隨關(guān)系) 給定時(shí)間長(zhǎng)度閾值εt和頻率閾值εe,對(duì)象集合O滿足伴隨關(guān)系當(dāng)且僅當(dāng)|O|≥2且|EL(O)|≥εe。

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

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

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

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

圖1中的每一個(gè)元組代表了一條記錄,l1行t1列的元組o1(r1)代表對(duì)象o1在t1時(shí)刻位于位置l1,也即記錄r1,r1={o1,l1,t1}。不失通用性,本文假設(shè)時(shí)間等間隔分布,間隔長(zhǎng)度為1,即?i,j,|ti-tj|=|i-j|。給定長(zhǎng)度閾值ε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個(gè)3-相遇(e4與e7)和5個(gè)2-相遇(e1、e2、e3、e4、e5、e6)。生成相遇之后,按照非重疊性的要求構(gòu)造有效相遇集合,共得到19個(gè)有效相遇集合(包括11個(gè)大小為1的集合),并從中選擇最大有效相遇集合。當(dāng)候選的最大有效相遇集合不止一個(gè)時(shí),任取一個(gè)即可以滿足定義要求。所有的最大有效相遇集合均大于等于εe,因此,得到4個(gè)滿足伴隨關(guān)系的對(duì)象集合,其中C4為滿足閉合伴隨關(guān)系的對(duì)象集合。

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

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

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

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

3.1 Apriori 性質(zhì)

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

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

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

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

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

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

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

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

3.3 閉合性檢查

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

3.4 算法基本框架

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

算法1基于滑動(dòng)窗口的閉合伴隨關(guān)系挖掘算法

輸入εt,εe,RRec

輸出所有滿足閉合伴隨關(guān)系的對(duì)象集合CC

1.k=1,初始化C1

2.while Ck≠? do

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

4.過(guò)濾不在C′k+1中對(duì)象的記錄

5.for li∈LLoc

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

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

8.更新C′k+1

9.過(guò)濾C′k+1,得到Ck+1

10.Close_Check(Ck,Ck+1)

11.更新CC

12.k=k+1

13.return CC

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

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

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

4 2-相遇剪枝算法

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

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

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

因?yàn)榛诠５牡^(guò)濾和基于摘要信息的過(guò)濾分別使用了不同的原理與信息進(jìn)行剪枝,所以可以結(jié)合這兩種方法來(lái)增強(qiáng)剪枝效果。

4.1 基于哈希的迭代過(guò)濾

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

以下為基于哈希的迭代過(guò)濾的形式化定義:任意一個(gè)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對(duì)應(yīng)的對(duì)象集合Oi不能滿足伴隨關(guān)系,因?yàn)榕cei哈希值相同的相遇總數(shù)小于εe。

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

PH(ei)=

基于滑動(dòng)窗口的算法2用于生成哈希表H。其中,第4行代碼確定當(dāng)前滑動(dòng)窗口范圍[rj.t-εt,rj.t],第5行掃描當(dāng)前窗口的所有2-相遇,增加對(duì)應(yīng)哈希值的計(jì)數(shù)。算法2的復(fù)雜度同樣為|NE|,但由于該算法不存儲(chǔ)每個(gè)相遇的具體信息,在線性的算法復(fù)雜度基礎(chǔ)上具有非常小的常數(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中,可以用額外的哈希表記錄單個(gè)對(duì)象能組成的2-相遇數(shù),從而對(duì)記錄進(jìn)行篩選,從而在生成不同層次的哈希表H過(guò)程中減少需要比較的記錄數(shù)量。

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

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

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

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}|

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

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

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

對(duì)于不同的時(shí)間長(zhǎng)度閾值εt和頻率閾值εe,摘要信息S可以復(fù)用,不需要重復(fù)計(jì)算。

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

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

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

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種不同的分組策略,其中最常用的分組策略是一個(gè)位置作為一個(gè)組,稱(chēng)為單地點(diǎn)分組策略。單地點(diǎn)分組策略在2種情況下會(huì)失效。第1種情況是|LLoc|很大,上界B的計(jì)算消耗了主要的時(shí)間。第2種情況是位置Lj是一個(gè)非常頻繁的位置,即|RRec(Lj)|很大,很多對(duì)象在Lj的出現(xiàn)次數(shù)都臨近εe,導(dǎo)致上界B松弛,非常容易達(dá)到εe。

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

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

針對(duì)RRec(Lj)很大的情況,可進(jìn)一步將RRec(Lj)按時(shí)間等分為子記錄集合,構(gòu)成分割分組策略。例如,按時(shí)間排序的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有可能會(huì)組成相遇,因此,需要對(duì)劃分的集合保留一定重疊以保證上界成立。

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

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

4.2.2 提前停止

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

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

4.3 兩層剪枝算法偽代碼

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

算法32-相遇剪枝算法

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

輸出C2

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

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 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

圖8和圖9顯示了不同的摘要信息分組策略下算法的運(yùn)行時(shí)間和剪枝率。實(shí)驗(yàn)是在7 d的數(shù)據(jù)集下運(yùn)行的,相遇時(shí)間閾值εt=180,相遇次數(shù)閾值εe=38,哈希表單層的長(zhǎng)度為100 000 000。后綴 O 指單地點(diǎn)分組策略,S 指分割分組策略,G200指分為200組的隨機(jī)分組策略,C200指分為200組的聚類(lèi)分組策略。從圖8可以看出,兩層剪枝算法運(yùn)行時(shí)間最短。在兩層剪枝算法中使用聚類(lèi)分組策略可達(dá)到最短的運(yùn)行時(shí)間,因?yàn)樵趦蓪蛹糁λ惴ǖ募糁β识己芨叩那闆r下,聚類(lèi)分組策略的計(jì)算代價(jià)較小。在不同分組策略的橫向比較中,組數(shù)越多剪枝率越高。聚類(lèi)分組策略由于可以利用空間局部性,效果比隨機(jī)分組策略好。通過(guò)圖8與圖9的比較也可以看出,運(yùn)行時(shí)間與剪枝率成正比,剪枝率越高,運(yùn)行時(shí)間越短。

圖8 摘要信息分組策略對(duì)運(yùn)行時(shí)間的影響Fig.8 Influence of summary information groupingstrategies on running times

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

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

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

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

圖11 不同相遇次數(shù)閾值下兩層剪枝算法各步驟的運(yùn)行時(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ù)閾值下的真實(shí)相遇比例Fig.13 True encounter ratio under different thresholds ofencounter time

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

5.4 相遇時(shí)間閾值對(duì)算法性能的影響

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

圖14 不同相遇時(shí)間閾值下的運(yùn)行時(shí)間Fig.14 Running time under different thresholds ofencounter time

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

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

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

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

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

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