基于布朗橋模型的重要同現模式挖掘

鄧 超 ,羅 澤 ,閻保平

(1.中國科學院計算機網絡信息中心,北京 100190；2.中國科學院大學,北京 100049)

1 概述

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

同現模式挖掘就是發現在時間和空間上共同出現的時空對象,比如,兩只鳥在飛行過程中在同一時間同一地點出現。重要同現模式挖掘就是發現那些在某區域內同時出現并持續足夠長時間的時空對象,重要同現模式不僅包括了同現,還限定了同現必須持續一定長的時間,比如,某幾個人可能在一起開會,他們會同時出現在會議室并持續一定時間,或者某些動物群體性的遷徙過程中一起出現在某個區域,并停留了很長時間。

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

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

現有的同現模式挖掘只關注了同現的瞬時性,而沒有關注同現的持續性?；诟怕式５慕浲５胤治鲫P注點也只在單一的對象上,而沒有去挖掘群體性的模式。本文提出重要同現模式挖掘,將同現模式挖掘和經停地分析結合起來,挖掘出具有群體性和持續性特點的時空模式。

2 概念定義及問題描述

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

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

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

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

3 重要同現模式挖掘算法

重要同現模式挖掘算法具體如下：

(1) 利用布朗橋為每條軌跡建模,并求得軌跡對應的經停地。

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

圖1 青海斑頭雁時空軌跡

(2) 找到2 個對象相交經停地中的重要軌跡。

由于布朗橋建模得到的概率分布沒有時間信息,經停地區域中可能包含多條軌跡片段,因此要找出經停地中的重要軌跡。重要軌跡是指滿足重要同現要求的對象的連續時空點集合。解決的整體思路是先找到不同對象的共同經停地,然后,再在這個共同經停地內尋找停留時間足夠長的對象各自的軌跡,而這些軌跡就是重要軌跡。

算法1求a,b的相交經停地的重要軌跡

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

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

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

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

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

經過算法1,就找到滿足重要條件,并且在同一個空間區域的軌跡,從而過濾掉了大量不需要做同現實例挖掘的采樣點。

由于每個軌跡建模后得到的經停地區域都包含了對應的軌跡所在的位置點,因此重要軌跡必然存在于經停地區域中。此外,同一個對象軌跡的2 條子軌跡也可能存在于同一個經停地中,因此,該算法重新掃描了2 個對象的軌跡,從而保證了經停地中發現的重要軌跡都是原軌跡中的連續采樣點。

由于空間交集是數學計算,則求交集部分只需要O(1)復雜度,而找重要軌跡的過程分別需要O(n)的時間復雜度,n是軌跡對應的采樣點數目。

(3) 利用2 個對象的重要軌跡,找到重要同現實例。

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

算法2尋找N個對象的同現模式

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

2) 對a的每一個重要軌跡TRi(a)：

對b的每一個重要軌跡TRj(b)：

如果TRi(a)和TRj(b)的時間跨度沒有重疊,則進入下一個循環；

構造列表LIST為空集；

對TR(a)中的每個時空點Pa：

對TR(b)中的每個時空點Pb：

如果Pa和Pb滿足同現實例條件,將(Pa,Pb)加入LIST中,其中,Pa和Pb在對象標記上滿足特定的偏序關系；

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

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

4)k=3～N：

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

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

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

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

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

經過算法2,就得到了最終的各長度的重要同現實例。

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

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

4 實驗結果與分析

4.1 實驗數據

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

表1 青海湖斑頭雁采樣數據

為滿足實驗的精度需求,在原始數據中選擇使用誤差小于1 000 m 的數據,13 只斑頭雁滿足要求的數據記錄數共22 589 條,為方便距離的計算,將經緯度轉換成了坐標。

4.2 實驗結果

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

圖2 長度為2 的重要同現實例在地圖上的位置

使用多組參數組合進行實驗,通過多組參數的實驗,分析不同參數值對實驗結果的影響。首先定義了一個參照的參數標準,并列出該組參數情況下的實驗結果,如表2 所示。

表2 分組基礎參數實驗結果

各參數對挖掘出的同現實例數的影響如圖3～圖6 所示。

圖3 同現長度閾值dtco對重要同現實例數的影響

圖4 同現時間閾值thco對重要同現實例數的影響

圖5 概率密度比例rate 對重要同現實例數的影響

圖6 持續時間thimco對重要同現實例數的影響

4.3 參數影響分析

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

重要同現持續時間thimco決定了一個同現實例集合能不能構成一個重要同現實例,thimco設定的越大,說明對重要性要求越高,越難找到合適的重要同現。算法中在重要軌跡發現和重要同現判斷中都使用了該參數,如果該參數比較嚴格,可能導致dtco和thco的影響力下降,因為該參數也直接決定了同現實例發現所需的候選時空點集合。

概率密度比例rate決定了預先找到的經停地的大小,rate值設置的越大,說明對經停地需要的密度分布越大,那么找到的經停地就越小和越少。在使用該參數時,要考慮到thimco的影響,如果rate選擇的太小,導致找到的經停地太小,那么在經停地內就可能不會出現持續時間超過thimco的軌跡,導致找不到重要同現；如果rate取得太大,會使得找到的時空點太多,達不到限制區域和減少冗余計算的目的。

5 結束語

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

[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]劉大有,陳慧靈,齊 紅,等.時空數據挖掘研究進展[J].計算機研究與發展,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.