鄧 超 ,羅 澤 ,閻保平

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

1 概述

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

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

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

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

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

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。

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

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

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

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

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

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

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

圖1 青海斑頭雁時空軌跡

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

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

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

1) 找到a,b經(jīng)停地的空間交集,如果交集為空,返回NA,否則,得到經(jīng)停地交集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)。

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

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

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

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

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

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

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

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

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

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

構造列表LIST為空集；

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

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

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

將LIST中的元素按照時間排序,遍歷LIST,如果LIST中存在連續(xù)子序列滿足時間跨度大于等于thimco,則將子序列記為重要同現(xiàn)實例,將對應的實例加入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]滿足同現(xiàn)實例條件,則將(PA[1：k-2],PA[k-1],PB[k-1])加入LIST中；

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

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

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

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

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

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

4 實驗結果與分析

4.1 實驗數(shù)據(jù)

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

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

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

4.2 實驗結果

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

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

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

表2 分組基礎參數(shù)實驗結果

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

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

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

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

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

4.3 參數(shù)影響分析

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

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

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

5 結束語

本文通過分析青海湖斑頭雁的數(shù)據(jù)可知,該同現(xiàn)模式算法挖掘出的時空模式具有群體性和持續(xù)性的特點,并且研究了算法中各參數(shù)間的影響和關系。由于現(xiàn)有同現(xiàn)模式挖掘方法在是否同現(xiàn)的判斷上都采用了較武斷的閾值,使得同現(xiàn)判斷缺少對數(shù)據(jù)的容錯性,概率建模是加強容錯性的有效方法,如何直接對同現(xià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ù)據(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.