基于布朗橋模型的重要同現(xiàn)模式挖掘

鄧 超 ,羅 澤 ,閻保平

(1.中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心,北京 100190；2.中國科學(xué)院大學(xué),北京 100049)

1 概述

隨著傳感器網(wǎng)絡(luò)、全球定位系統(tǒng)(Global Positioning System,GPS)、手持移動(dòng)設(shè)備和射頻識(shí)別(Radio Frequency Identification,RFID)等設(shè)備的普遍應(yīng)用,大量的移動(dòng)對(duì)象數(shù)據(jù)被積累下來[1-2]。在此背景下,針對(duì)歷史軌跡數(shù)據(jù)挖掘技術(shù)的研究成為當(dāng)前研究的熱點(diǎn),時(shí)空模式發(fā)現(xiàn)是主要的研究方向之一,包括時(shí)空頻繁模式挖掘、時(shí)空同現(xiàn)模式挖掘和時(shí)空關(guān)聯(lián)模式挖掘[3]。然而,在時(shí)空數(shù)據(jù)挖掘的眾多模式中,同現(xiàn)模式的挖掘占有重要地位。

同現(xiàn)模式挖掘就是發(fā)現(xiàn)在時(shí)間和空間上共同出現(xiàn)的時(shí)空對(duì)象,比如,兩只鳥在飛行過程中在同一時(shí)間同一地點(diǎn)出現(xiàn)。重要同現(xiàn)模式挖掘就是發(fā)現(xiàn)那些在某區(qū)域內(nèi)同時(shí)出現(xiàn)并持續(xù)足夠長時(shí)間的時(shí)空對(duì)象,重要同現(xiàn)模式不僅包括了同現(xiàn),還限定了同現(xiàn)必須持續(xù)一定長的時(shí)間,比如,某幾個(gè)人可能在一起開會(huì),他們會(huì)同時(shí)出現(xiàn)在會(huì)議室并持續(xù)一定時(shí)間,或者某些動(dòng)物群體性的遷徙過程中一起出現(xiàn)在某個(gè)區(qū)域,并停留了很長時(shí)間。

同現(xiàn)模式挖掘的研究已經(jīng)有了比較長的歷史。文獻(xiàn)[4]提出空間數(shù)據(jù)的頻繁同現(xiàn)鄰居挖掘,使用同現(xiàn)位置的對(duì)象數(shù)量作為支持量來衡量同現(xiàn)位置的重要程度。文獻(xiàn)[5-6]提出一種基于Apriori 算法的同現(xiàn)模式挖掘算法框架,使用參與率來取代支持量,這使得同現(xiàn)評(píng)價(jià)指標(biāo)更有統(tǒng)計(jì)意義。此外,還有基于聚類方法的同現(xiàn)模式挖掘[7-9]。文獻(xiàn)[10]提出基于密度的同現(xiàn)模式挖掘,該算法通過將對(duì)象分區(qū),優(yōu)先處理密集分區(qū)的樣本,減少了Apriori 算法連接次數(shù),提升了效率,但該算法沒有考慮時(shí)間信息。

基于概率建模的方法一直是時(shí)空數(shù)據(jù)挖掘的重要方式,在經(jīng)停地挖掘中也有重要應(yīng)用。文獻(xiàn)[11]提出基于核方法的經(jīng)停地分布建模算法。文獻(xiàn)[12]提出使用布朗橋模型來為時(shí)空對(duì)象的移動(dòng)數(shù)據(jù)建模,并應(yīng)用于經(jīng)停地挖掘中。文獻(xiàn)[13]在該算法的基礎(chǔ)上進(jìn)行改進(jìn),提出能夠容錯(cuò)的針對(duì)時(shí)空對(duì)象軌跡數(shù)據(jù)的布朗橋建模。利用概率建模分析經(jīng)停地的好處是可以通過概率密度來增加對(duì)離散采樣點(diǎn)數(shù)據(jù)的魯棒性,減少因?yàn)閿?shù)據(jù)采樣間隔時(shí)間過長或者采樣不完整所帶來的誤差。

現(xiàn)有的同現(xiàn)模式挖掘只關(guān)注了同現(xiàn)的瞬時(shí)性,而沒有關(guān)注同現(xiàn)的持續(xù)性?；诟怕式５慕?jīng)停地分析關(guān)注點(diǎn)也只在單一的對(duì)象上,而沒有去挖掘群體性的模式。本文提出重要同現(xiàn)模式挖掘,將同現(xiàn)模式挖掘和經(jīng)停地分析結(jié)合起來,挖掘出具有群體性和持續(xù)性特點(diǎn)的時(shí)空模式。

2 概念定義及問題描述

首先介紹文中用到的符號(hào)定義：時(shí)空對(duì)象采用小寫字母a,b,…表示；時(shí)空點(diǎn)由大寫字母P表示,P={x,y,timestamp},即P由二維空間的點(diǎn)對(duì)(x,y)以及時(shí)間維度的采樣時(shí)間戳timestamp所確定,P(a,τ)表示對(duì)象a在時(shí)刻τ所處的位置；軌跡TR由某個(gè)對(duì)象的一系列時(shí)空點(diǎn)P組成,并按時(shí)間排序,對(duì)象a的軌跡TR(a)={P(a,τ1),P(a,τ2),…,P(a,τn)},其中,τ1≤τ2≤…≤τn。

同現(xiàn)實(shí)例：一個(gè)長度為N的同現(xiàn)實(shí)例由來自N個(gè)不同對(duì)象的N個(gè)時(shí)空點(diǎn)組成(每個(gè)對(duì)象一個(gè)時(shí)空點(diǎn)),并滿足條件：(1)任意2 個(gè)時(shí)空點(diǎn)之間的時(shí)間間隔必須小于一個(gè)時(shí)間閾值thco；(2)任意2 個(gè)時(shí)空點(diǎn)間的空間距離不得大于一個(gè)長度閾值dtco。

重要同現(xiàn)實(shí)例：長度為N的重要同現(xiàn)實(shí)例來自N個(gè)對(duì)象的若干個(gè)同現(xiàn)實(shí)例組成的集合,該集合滿足條件：(1)集合中的每個(gè)同現(xiàn)實(shí)例都是一個(gè)長度為N的同現(xiàn)實(shí)例；(2)集合中所有同現(xiàn)實(shí)例在時(shí)間上連續(xù),并且首尾的時(shí)間跨度大于一個(gè)時(shí)間閾值thimco。該集合中的每一組同現(xiàn)實(shí)例都是一個(gè)重要同現(xiàn)實(shí)例。

重要同現(xiàn)實(shí)例代表著重要的時(shí)空移動(dòng)模式,例如,鳥群在遷徙過程中集體在某個(gè)區(qū)域棲息了一段時(shí)間,則他們的群體棲息行為可以通過重要同現(xiàn)模式來描述,在鳥群發(fā)生禽流感時(shí),通過采樣數(shù)據(jù),利用挖掘方法得到的群體棲息地,將是發(fā)現(xiàn)流感傳播途徑的重點(diǎn)關(guān)注區(qū)域。本文需要解決的問題是：給定N個(gè)移動(dòng)對(duì)象的空間軌跡采樣數(shù)據(jù),挖掘任意長度的重要同現(xiàn)實(shí)例。

3 重要同現(xiàn)模式挖掘算法

重要同現(xiàn)模式挖掘算法具體如下：

(1) 利用布朗橋?yàn)槊織l軌跡建模,并求得軌跡對(duì)應(yīng)的經(jīng)停地。

每個(gè)移動(dòng)對(duì)象都有各自的一條軌跡,利用布朗橋?yàn)閷?duì)象軌跡對(duì)應(yīng)的概率分布建模,建模方法采用容錯(cuò)的布朗橋模型[13],然后利用該分布得到該時(shí)空對(duì)象的經(jīng)停地,這里需要定義一個(gè)概率閾值rate,將軌跡的分布概率大于rate的部分,作為經(jīng)停地。圖1(矩形表示軌跡的起點(diǎn)位置,三角形表示軌跡的結(jié)束位置)展示了一只斑頭雁的時(shí)空軌跡圖和利用布朗橋模型得到的經(jīng)停地。

圖1 青海斑頭雁時(shí)空軌跡

(2) 找到2 個(gè)對(duì)象相交經(jīng)停地中的重要軌跡。

由于布朗橋建模得到的概率分布沒有時(shí)間信息,經(jīng)停地區(qū)域中可能包含多條軌跡片段,因此要找出經(jīng)停地中的重要軌跡。重要軌跡是指滿足重要同現(xiàn)要求的對(duì)象的連續(xù)時(shí)空點(diǎn)集合。解決的整體思路是先找到不同對(duì)象的共同經(jīng)停地,然后,再在這個(gè)共同經(jīng)停地內(nèi)尋找停留時(shí)間足夠長的對(duì)象各自的軌跡,而這些軌跡就是重要軌跡。

算法1求a,b的相交經(jīng)停地的重要軌跡

1) 找到a,b經(jīng)停地的空間交集,如果交集為空,返回NA,否則,得到經(jīng)停地交集STOPOVER,進(jìn)行第2)步；

2) 定義a,b的重要軌跡集合SET(a),SET(b)；

3) 按時(shí)間順序遍歷TR(a)在STOPOVER中的時(shí)空點(diǎn),如果找到一條軌跡片段TRi(a)滿足TRi(a)的終點(diǎn)時(shí)間τn和起點(diǎn)時(shí)間τ0的時(shí)間差τn-τ0≥thimco,則將該條軌跡加入到SET(a)中；

4) 按時(shí)間順序遍歷TR(b)在STOPOVER中的時(shí)空點(diǎn),如果找到一條軌跡片段TRi(b)滿足TRi(b)的終點(diǎn)時(shí)間τn和起點(diǎn)時(shí)間τ0的時(shí)間差τn-τ0≥thimco,則將該條軌跡加入到SET(b)中；

5) 如果SET(a)為空集或者SET(b)為空集,則返回空集,否則返回SET(a)和SET(b)。

經(jīng)過算法1,就找到滿足重要條件,并且在同一個(gè)空間區(qū)域的軌跡,從而過濾掉了大量不需要做同現(xiàn)實(shí)例挖掘的采樣點(diǎn)。

由于每個(gè)軌跡建模后得到的經(jīng)停地區(qū)域都包含了對(duì)應(yīng)的軌跡所在的位置點(diǎn),因此重要軌跡必然存在于經(jīng)停地區(qū)域中。此外,同一個(gè)對(duì)象軌跡的2 條子軌跡也可能存在于同一個(gè)經(jīng)停地中,因此,該算法重新掃描了2 個(gè)對(duì)象的軌跡,從而保證了經(jīng)停地中發(fā)現(xiàn)的重要軌跡都是原軌跡中的連續(xù)采樣點(diǎn)。

由于空間交集是數(shù)學(xué)計(jì)算,則求交集部分只需要O(1)復(fù)雜度,而找重要軌跡的過程分別需要O(n)的時(shí)間復(fù)雜度,n是軌跡對(duì)應(yīng)的采樣點(diǎn)數(shù)目。

(3) 利用2 個(gè)對(duì)象的重要軌跡,找到重要同現(xiàn)實(shí)例。

用類似Apriori 的算法[5-6]來發(fā)現(xiàn)同現(xiàn)實(shí)例,從長度為2 的同現(xiàn)實(shí)例開始,依次連接,長度為N+1的同現(xiàn)實(shí)例可以由長度為N的同現(xiàn)實(shí)例連接得到,同現(xiàn)實(shí)例的判斷按照定義判斷。方式如下：

算法2尋找N個(gè)對(duì)象的同現(xiàn)模式

1) 定義集合SET(2)為空集；

2) 對(duì)a的每一個(gè)重要軌跡TRi(a)：

對(duì)b的每一個(gè)重要軌跡TRj(b)：

如果TRi(a)和TRj(b)的時(shí)間跨度沒有重疊,則進(jìn)入下一個(gè)循環(huán)；

構(gòu)造列表LIST為空集；

對(duì)TR(a)中的每個(gè)時(shí)空點(diǎn)Pa：

對(duì)TR(b)中的每個(gè)時(shí)空點(diǎn)Pb：

如果Pa和Pb滿足同現(xiàn)實(shí)例條件,將(Pa,Pb)加入LIST中,其中,Pa和Pb在對(duì)象標(biāo)記上滿足特定的偏序關(guān)系；

將LIST中的元素按照時(shí)間排序,遍歷LIST,如果LIST中存在連續(xù)子序列滿足時(shí)間跨度大于等于thimco,則將子序列記為重要同現(xiàn)實(shí)例,將對(duì)應(yīng)的實(shí)例加入SEST(2)中；

3) 如果SET(2)為空集,返回空集,否則,進(jìn)入第4)步；

4)k=3～N：

定義SET(k)為空集,LIST為空集；

對(duì)SET(K-1)中的任意2 個(gè)元素PA,PB,如果對(duì)應(yīng)的前k-2 個(gè)對(duì)象相同,即PA[1：k-2]=PB[1：k-2],并且最末2 個(gè)對(duì)象PA[k-1]和PB[k-1]滿足同現(xiàn)實(shí)例條件,則將(PA[1：k-2],PA[k-1],PB[k-1])加入LIST中；

將LIST4 中的元素按照時(shí)間排序,遍歷LIST,如果LIST中存在連續(xù)子序列滿足時(shí)間跨度大于等于thimco,則將子序列記為重要同現(xiàn)實(shí)例,加入SEST(k)中；

如果SET(k)為空集,記錄下sk=k,停止循環(huán)；

5) 返回SET(2),SET(3),…,SET(sk)。

經(jīng)過算法2,就得到了最終的各長度的重要同現(xiàn)實(shí)例。

從Apriori 算法思路可知,采用自底向上的計(jì)算方法,能夠完全計(jì)算出所有長度的重要同現(xiàn)實(shí)例。因?yàn)?若(PA[1：k-2],PA[k-1])和(PA[1：k-2],PB[k-1])不是重要同現(xiàn)實(shí)例,則(PA[1：k-2],PA[k-1],PB[k-1])肯定不滿足同現(xiàn)條件,反之,若(PA[1：k-2],PA[k-1],PB[k-1])是重要同現(xiàn)實(shí)例,則(PA[1：k-2],PA[k-1])和(PA[1：k-2],PB[k-1])也必然滿足重要同現(xiàn)條件。所以,該算法能夠保證挖掘結(jié)果的完備性和正確性。

雖然該算法基于Apriori 思路,但是計(jì)算復(fù)雜度不同于傳統(tǒng)的Apriori 算法,在連接時(shí),該算法并不需要掃描所有采樣點(diǎn),同時(shí),判斷連個(gè)點(diǎn)是否滿足同現(xiàn)條件時(shí),也只需要做歐氏距離計(jì)算和時(shí)間差計(jì)算,這部分的開銷為O(1),而每次一排序需要時(shí)間復(fù)雜度是O(nlogn),因此,該部分算法總體時(shí)間復(fù)雜度不超過O(knlogn),k是需要計(jì)算的重要同現(xiàn)實(shí)例的長度,n是采樣點(diǎn)個(gè)數(shù)。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

為驗(yàn)證算法的可行性,將算法應(yīng)用在來自青海湖的13 只斑頭雁從2007 年3 月-2008 年3 月的時(shí)空采樣數(shù)據(jù)上。這些斑頭雁被綁定了一個(gè)太陽能充電的便攜式遙感設(shè)備,包括一個(gè)傳輸終端和一個(gè)微波遙測(cè)終端,可以同時(shí)通過Argos 衛(wèi)星和GPS 接收器進(jìn)行定位。采樣收集到的數(shù)據(jù)格式如表1 所示。

表1 青海湖斑頭雁采樣數(shù)據(jù)

為滿足實(shí)驗(yàn)的精度需求,在原始數(shù)據(jù)中選擇使用誤差小于1 000 m 的數(shù)據(jù),13 只斑頭雁滿足要求的數(shù)據(jù)記錄數(shù)共22 589 條,為方便距離的計(jì)算,將經(jīng)緯度轉(zhuǎn)換成了坐標(biāo)。

4.2 實(shí)驗(yàn)結(jié)果

通過對(duì)13 只斑頭雁的數(shù)據(jù)實(shí)驗(yàn)發(fā)現(xiàn)斑頭雁遷徙中的群體移動(dòng)特點(diǎn),這些斑頭雁在青海湖和西藏之間長途遷徙。青海湖區(qū)域、鄂陵湖和扎陵湖區(qū)域是遷徙的出發(fā)區(qū)域,大多數(shù)重要同現(xiàn)模式集中在這2 個(gè)區(qū)域。遷徙的終點(diǎn)主要在錯(cuò)鄂湖區(qū)域。除此之外,實(shí)驗(yàn)還發(fā)現(xiàn)在扎木錯(cuò)區(qū)域的重要同現(xiàn)模式,這說明這些斑頭雁在遷徙過程中也在這些區(qū)域有過群體性的停留。實(shí)驗(yàn)發(fā)現(xiàn),對(duì)于鳥類分析學(xué)家研究鳥類的遷徙模式非常有用,例如這些珍稀動(dòng)物中出現(xiàn)了傳染病,則這些群體性的停留地和停留時(shí)間就應(yīng)當(dāng)重點(diǎn)關(guān)注。圖2展示了一組長度為2 的重要同現(xiàn)實(shí)例在地圖上的位置,該重要同現(xiàn)實(shí)例出現(xiàn)在青海湖西北側(cè)(維度37.125°,經(jīng)度99.731°),時(shí)間在2007 年5 月11 日。

圖2 長度為2 的重要同現(xiàn)實(shí)例在地圖上的位置

使用多組參數(shù)組合進(jìn)行實(shí)驗(yàn),通過多組參數(shù)的實(shí)驗(yàn),分析不同參數(shù)值對(duì)實(shí)驗(yàn)結(jié)果的影響。首先定義了一個(gè)參照的參數(shù)標(biāo)準(zhǔn),并列出該組參數(shù)情況下的實(shí)驗(yàn)結(jié)果,如表2 所示。

表2 分組基礎(chǔ)參數(shù)實(shí)驗(yàn)結(jié)果

各參數(shù)對(duì)挖掘出的同現(xiàn)實(shí)例數(shù)的影響如圖3～圖6 所示。

圖3 同現(xiàn)長度閾值dtco對(duì)重要同現(xiàn)實(shí)例數(shù)的影響

圖4 同現(xiàn)時(shí)間閾值thco對(duì)重要同現(xiàn)實(shí)例數(shù)的影響

圖5 概率密度比例rate 對(duì)重要同現(xiàn)實(shí)例數(shù)的影響

圖6 持續(xù)時(shí)間thimco對(duì)重要同現(xiàn)實(shí)例數(shù)的影響

4.3 參數(shù)影響分析

dtco,thco決定了2 個(gè)不同的時(shí)空點(diǎn)是否是一個(gè)同現(xiàn)實(shí)例,dtco和thco設(shè)定的越大,說明同現(xiàn)條件越寬松,能夠找到的同現(xiàn)實(shí)例越多,使得重要同現(xiàn)出現(xiàn)的可能增加。

重要同現(xiàn)持續(xù)時(shí)間thimco決定了一個(gè)同現(xiàn)實(shí)例集合能不能構(gòu)成一個(gè)重要同現(xiàn)實(shí)例,thimco設(shè)定的越大,說明對(duì)重要性要求越高,越難找到合適的重要同現(xiàn)。算法中在重要軌跡發(fā)現(xiàn)和重要同現(xiàn)判斷中都使用了該參數(shù),如果該參數(shù)比較嚴(yán)格,可能導(dǎo)致dtco和thco的影響力下降,因?yàn)樵搮?shù)也直接決定了同現(xiàn)實(shí)例發(fā)現(xiàn)所需的候選時(shí)空點(diǎn)集合。

概率密度比例rate決定了預(yù)先找到的經(jīng)停地的大小,rate值設(shè)置的越大,說明對(duì)經(jīng)停地需要的密度分布越大,那么找到的經(jīng)停地就越小和越少。在使用該參數(shù)時(shí),要考慮到thimco的影響,如果rate選擇的太小,導(dǎo)致找到的經(jīng)停地太小,那么在經(jīng)停地內(nèi)就可能不會(huì)出現(xiàn)持續(xù)時(shí)間超過thimco的軌跡,導(dǎo)致找不到重要同現(xiàn)；如果rate取得太大,會(huì)使得找到的時(shí)空點(diǎn)太多,達(dá)不到限制區(qū)域和減少冗余計(jì)算的目的。

5 結(jié)束語

本文通過分析青海湖斑頭雁的數(shù)據(jù)可知,該同現(xiàn)模式算法挖掘出的時(shí)空模式具有群體性和持續(xù)性的特點(diǎn),并且研究了算法中各參數(shù)間的影響和關(guān)系。由于現(xiàn)有同現(xiàn)模式挖掘方法在是否同現(xiàn)的判斷上都采用了較武斷的閾值,使得同現(xiàn)判斷缺少對(duì)數(shù)據(jù)的容錯(cuò)性,概率建模是加強(qiáng)容錯(cuò)性的有效方法,如何直接對(duì)同現(xiàn)進(jìn)行概率建模是下一步研究的方向。

[1]Antunes C M,Oliveira A L.Temporal Data Mining：An Overview [C]//Proceedings of KDD Workshop on Temporal Data Mining.New York,USA：ACM Press,2001：1-13.

[2]Miller H J,Han Jiawei.Geographic Data Mining and Knowledge Discovery [M].Boca Raton,USA：CRC Press,2009.

[3]劉大有,陳慧靈,齊 紅,等.時(shí)空數(shù)據(jù)挖掘研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展,2013,50(2)：225-239.

[4]Morimoto Y.Mining Frequent Neighboring Class Sets in Spatial Databases[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA：ACM Press,2001：353-358.

[5]Huang Yan,Xiong Hui,Shekhar S,et al.Mining Confident Co-location Rules Without a Support Threshold[C]//Proceedings of the 18th ACM Symposium on Applied Computing.New York,USA：ACM Press,2003：497-501.

[6]Shekhar S,Huang Yan.Discovering Spatial Co-location Patterns：A Summary of Results[C]//Proceedings of the 7th International Symposium on Spatial and Temporal Databases.Berlin,Germany：Springer,2001：236-256.

[7]Estivill-Castro V,Lee I.Data Mining Techniques for Autonomous Exploration of Large Volumes of Georeferenced Crime Data [C]//Proceedings of the 6th International Conference on Geocomputation.New York,USA：[s.n.],2001：24-26.

[8]Estivill-Castrol V,Murray A T.Discovering Associations in Spatial Data——An Efficient Method Based Approach[C]//Proceedings of the 2nd Pacific-Asia Conference on Knowledge Discovery and Data Mining.Berlin,Germany：Springer,1998：110-121.

[9]Huang Yan,Zhang Pusheng.On the Relationships Between Clustering and Spatial Co-location Pattern Mining [J].International Journal on Artificial Intelligence Tools,2008,17(1)：55-70.

[10]Xiao Xiangye,Xie Xing,Luo Qiong,et al.Density Based Co-location Pattern Discovery[C]//Proceedings of the 16th International Conference on Advances in Geographic Information Systems.New York,USA：ACM Press,2008：29-34.

[11]Worton B J.Kernel Methods for Estimating the Utilization Distribution in Home-range Studies [J].Ecology,1989,70(1)：164-168.

[12]Billiard F.Estimating the Home Range of An Animal：A Brownian Bridge Approach [D].Chapel Hill,USA：University of North Carolina,1991.

[13]Horne J S,Garton E O,Krone S M,et al.Analyzing Animal Movements Using Brownian Bridges [ J].Ecology,2007,88(9)：2354-2363.