基于停留時間的語義行為模式挖掘

郭黎敏 高 需 武 斌 郭皓明 徐懷野 魏閆艷 王之欣 焉 麗 田 霂

1(北京工業(yè)大學(xué) 北京 100124)2(中國科學(xué)院軟件研究所 北京 100190)3 (中國科學(xué)院大學(xué) 北京 100049)(guolimin@bjut.edu.cn)

基于停留時間的語義行為模式挖掘

郭黎敏1高 需2,3武 斌2郭皓明2徐懷野2魏閆艷2王之欣2焉 麗2田 霂2

1(北京工業(yè)大學(xué) 北京 100124)2(中國科學(xué)院軟件研究所 北京 100190)3(中國科學(xué)院大學(xué) 北京 100049)(guolimin@bjut.edu.cn)

移動對象的語義行為模式挖掘是當前移動對象研究中關(guān)注的熱點，有益于諸多應(yīng)用場景，如朋友推薦系統(tǒng)、軌跡破案領(lǐng)域和個性化服務(wù)等.目前語義行為模式挖掘方法沒有考慮移動對象在停留點的停留時間，不能準確地分辨出移動對象之間的不同行為模式.為了解決上述問題，提出了一種基于停留時間的語義行為模式挖掘(discovering common behavior using staying duration on semantic trajectory, DSTra)方法，首先挖掘每個移動對象的頻繁語義行為模式，然后定義語義行為模式之間的相似性度量方法，最后采用層次聚類的方法對移動對象進行聚類，找出具有相似行為模式的移動對象群體.實驗結(jié)果表明：該方法不僅具有合理性和有效性，同時還具有較高的準確率和較好的效率.

語義軌跡；停留時間；語義行為模式；模式相似度；移動對象聚類

隨著移動便攜設(shè)備的廣泛普及以及無線通信技術(shù)和全球定位技術(shù)的飛速發(fā)展，移動對象可以方便地獲取其位置信息并對移動軌跡進行存儲管理.移動軌跡本身的價值使得各種基于位置的服務(wù)越來越受到國內(nèi)外研究學(xué)者的關(guān)注，移動對象的軌跡模式挖掘是其中最受關(guān)注的熱點問題之一.本文研究了移動對象的語義行為模式挖掘方法，即在移動對象語義軌跡的基礎(chǔ)上，找出具有相似行為模式的移動對象群體.

事實上，移動對象軌跡記錄了人們在現(xiàn)實世界中的活動，而這些活動在一定程度上反映了其生活方式或行為習(xí)慣，因此通過對軌跡數(shù)據(jù)進行分析，挖掘出移動對象的行為模式，發(fā)現(xiàn)移動對象之間相關(guān)性具有重要的研究價值與廣泛的應(yīng)用領(lǐng)域.如在朋友推薦系統(tǒng)中，通過用戶分享的軌跡數(shù)據(jù)，發(fā)現(xiàn)用戶的生活方式、興趣愛好等，推薦趣味相投的朋友；在軌跡破案領(lǐng)域，分析犯罪行為遺留的軌跡信息，結(jié)合對嫌疑人的關(guān)聯(lián)分析，查找案件的同伙關(guān)系人，并發(fā)現(xiàn)嫌疑人的移動模式及其規(guī)律，預(yù)測其發(fā)展走向，協(xié)助案件偵破；在個性化服務(wù)中，幫助服務(wù)供應(yīng)商了解用戶的生活規(guī)律，預(yù)測用戶的行駛路徑，實現(xiàn)商品或路徑推薦.可以說，移動對象的軌跡模式挖掘技術(shù)已經(jīng)得到了人們?nèi)找鎻V泛的重視.

移動對象的軌跡模式挖掘可以分為兩大類：基于地理信息的軌跡模式挖掘和基于語義信息的軌跡模式挖掘.其中，前者主要關(guān)注軌跡的位置特征，如軌跡形狀、行駛方向、速度等；后者則主要關(guān)注軌跡的語義信息.在基于地理信息的軌跡模式挖掘方法中，位置越靠近并且形狀越相似的軌跡被認為越相似.如圖1所示，僅從軌跡的位置特征考慮，MO1與MO2最相似，因為MO1與MO2的軌跡距離最接近并且形狀最相似.然而，基于地理位置的相似性度量缺乏語義信息，并不能挖掘移動對象的移動模式.在基于語義信息的軌跡模式挖掘方法中，語義軌跡對移動對象行駛路徑中的地理位置標注上了語義信息，圖1中語義層的軌跡是地理層中的移動軌跡對應(yīng)的語義軌跡.然而，現(xiàn)有的基于語義信息的軌跡模式挖掘方法沒有考慮移動對象在每個停留點的停留時間.例如，在圖1中MO1和MO3具有相同的移動模式：家→飯店→公司→飯店，但是實際上MO1與MO3并不相似，因為MO1在飯店工作，去公司送外賣后再返回飯店，而MO3在飯店吃完早餐后去公司上班，并再次返回飯店吃午飯.因此，現(xiàn)有的基于語義的方法不能準確地分辨出移動對象之間不同的生活方式.

Fig. 1 Geographic and semantic trajectories圖1 地理信息軌跡和語義信息軌跡

Fig. 2 User behaviors with staying durations圖2 基于停留時間的語義行為模式挖掘

通過上述分析可以看出，在軌跡模式挖掘技術(shù)方面，目前缺乏一種能夠處理移動對象停留時間的高準確性的軌跡模式挖掘方法.為了解決上述問題，本文提出了一種基于停留時間的語義行為模式挖掘(discovering common behavior using staying duration on semantic trajectory, DSTra)方法.DSTra具備2種優(yōu)勢：1)能夠提高不同語義行為模式之間的區(qū)分度；2)能夠發(fā)現(xiàn)具有相似生活方式或行為習(xí)慣的移動對象群體.在圖2中，如果考慮每個停留點的停留時間，就能容易地區(qū)分出圖1中MO1與MO3具有不同的行為模式.由于MO1與MO3在公司和飯店的不同停留時間體現(xiàn)了其不同的意圖，因此可以分辨出MO1與MO3具有不同的行為模式.由此可以從圖2中挖掘出語義行為模式 (家,10)→(飯店,1)→(公司,4)→(飯店,1.5)，并逐步找出具有相似行為模式的移動對象聚類{MO3,MO4}.

DSTra的基本思路是：在一系列移動對象的語義軌跡集合中，1)挖掘出每個移動對象的基于停留時間的頻繁語義行為模式；2)基于停留時間給出了語義行為模式之間的相似性度量方法；3)通過模式之間的相似性，采用層次聚類的方法對移動對象聚類，每一個聚類代表具有一系列相似語義行為模式的移動對象集合，也就是具有相似生活方式、行為習(xí)慣的移動對象集合.歸納總結(jié)本文的主要貢獻有5點：

1) 定義了基于停留時間的語義行為模式；

2) 提出了一種基于停留時間的語義行為模式挖掘算法；

3) 提出了一種基于停留時間的語義行為模式相似性度量方法；

4) 提出了一種基于模式相似性的移動對象聚類算法；

5) 驗證了DSTra方法在挖掘語義行為模式時的有效性、高準確性及高效性.

1 相關(guān)工作

本節(jié)首先介紹了軌跡相似性度量方法，然后概述了現(xiàn)有的軌跡模式挖掘技術(shù).

軌跡相似性度量方法主要分為兩大類：基于地理信息的相似性度量和基于語義信息的相似性度量.

基于地理信息的相似性度量關(guān)注的是軌跡的位置特征，早期的研究主要是基于歐氏距離的度量方法，其中最具代表性的有DTW[1]，EDR[2]，LCSS[3].此外，針對軌跡模式之間的相似性度量也進行了相關(guān)的研究[4-7]，文獻[4]研究了基于線索的軌跡相似性.文獻[5]提出了3種距離度量方法；基于語義信息的相似性度量主要關(guān)注的是軌跡的語義特征，文獻[8-11]對語義軌跡進行了研究，語義軌跡被定義為一系列時空位置與相應(yīng)停留點的集合，如此不僅能抽取位置信息還能挖掘語義信息.另外，研究學(xué)者在語義軌跡相似性領(lǐng)域也進行了相關(guān)的討論和研究[12-16].這些文獻中，首先將軌跡轉(zhuǎn)換為語義軌跡，然后通過移動對象之間的相似性進行用戶推薦.文獻[15]依據(jù)用戶之間軌跡模式的相似性定義用戶之間的相似性.文獻[13-14]通過層次樹狀結(jié)構(gòu)計算相似性.文獻[16]結(jié)合了位置及語義特征預(yù)測用戶未來的位置.

基于地理信息的相似性度量方法只能處理軌跡的位置信息，而基于語義信息的相似性度量方法不能處理軌跡中的停留時間，因此現(xiàn)有的相似性度量方法不能解決基于停留時間的軌跡相似性問題.

現(xiàn)有的軌跡模式挖掘方法可以分為2大類：軌跡模式挖掘和軌跡聚類.

軌跡模式挖掘研究的是移動對象的運動模式，早期的研究主要關(guān)注的是軌跡的時空屬性[17-20]，其基本思想是通過序列模式挖掘找出頻繁軌跡模式.由于這些方法沒有考慮停留時間對軌跡模式的影響，因此不能有效地區(qū)分不同的軌跡模式.

軌跡聚類的目標在于挖掘具有相同運動模式的移動對象集合[21-26].除此之外，另一類研究的目標在于找出移動對象集合的公共路徑，文獻[5]將每條軌跡劃分為一系列子軌跡，然后基于距離函數(shù)進行聚類.文獻[27]在軌跡劃分和聚類的過程中同時考慮了時間和空間因素.

上述軌跡模式挖掘方法從移動對象的個體或群體的角度出發(fā)進行研究，但是既不能挖掘移動對象的公共行為模式，也不能處理語義軌跡.為了解決上述問題，本文提出了一種基于停留時間的語義行為模式挖掘方法.

2 問題定義

本節(jié)以語義軌跡為基礎(chǔ)，首先給出了語義行為模式的相關(guān)問題定義，然后介紹了DSTra方法的系統(tǒng)架構(gòu).

為便于敘述，表1給出了本文的符號描述表.

定義1. 語義點.語義點A定義為

A=(A,t)，

其中，A是移動對象的停留點，t是移動對象在A的停留時間.

定義2. 語義軌跡.語義軌跡S是一組移動對象語義點的有序序列，定義為

.

不失一般性，我們使用字母表示移動對象的停留點，表2為某一移動對象的語義軌跡集合實例.

Table 2 An Example of Semantic Trajectory Dataset

定義3. 語義軌跡等價.給定停留閾值δt，語義軌跡S1與S2等價定義為S1?S2，當且僅當滿足條件：

其中，條件2對相應(yīng)2個語義點之間的停留時間進行了約束，即停留時間比例差受限于δt.

定義4. 語義行為模式.語義行為模式P是一組相似語義軌跡的共同模式，定義為

為了更好地描述語義行為模式挖掘，我們定義了語義行為模式與語義軌跡之間的匹配關(guān)系.

定義5. 模式匹配.給定語義行為模式P和語義軌跡S，S匹配P定義為SP，當且僅當S存在子序列SP，使得SP?P.

移動對象的行為語義提取即從語義軌跡集合中挖掘出頻繁語義行為模式.

以表2為例，假設(shè)δt=0.5，fmin=0.5，依據(jù)定義6，{(a,10),(b,0.5),(c,4),(b,1.5)}是一個語義行為模式.然而任意形如{(a,10),(b,t),(c,4),(b,1.5)}(t∈[0.5,1])的行為模式都滿足條件.因此，我們采用平均停留時間來表示行為模式中的停留時間.

問題描述：給定語義軌跡集合D、最小支持度fmin和停留閾值δt，移動對象的語義行為模式挖掘步驟如下：1)依據(jù)fmin和δt，從D中進行行為語義提取，找出所有語義行為模式的集合P；2)度量P中模式之間的相似度；3)在相似度的基礎(chǔ)上，依據(jù)移動對象的相似生活方式、行為習(xí)慣等進行聚類.

由此，我們提出了一種語義行為模式的挖掘方法——基于停留時間的語義行為模式挖掘DSTra.DSTra的系統(tǒng)結(jié)構(gòu)如圖3所示，可以分為3部分：1)語義行為模式挖掘(semantic trajectory pattern mining，STPM)；2)模式相似性度量(pattern similarity， P-Similarity)；3)基于模式相似性的移動對象聚類(similarity-based user clustering， SU-Clustering).

Fig. 3 System overview of DSTra圖3 DSTra的系統(tǒng)結(jié)構(gòu)

圖3中，1)提出了基于停留時間的語義行為模式挖掘算法，并對每個移動對象進行了行為語義抽取；2)設(shè)計了基于時間權(quán)重的語義行為模式相似度度量方法；3)在模式相似性的基礎(chǔ)上，采用剪枝策略進行層次聚類，找出所有具有相似行為模式的移動對象群體.

3 基于停留時間的語義行為模式挖掘算法

本節(jié)首先給出了相關(guān)數(shù)據(jù)結(jié)構(gòu)，然后詳細介紹了語義行為模式挖掘算法STPM.

在語義行為模式挖掘之前，首先要將原始軌跡轉(zhuǎn)換為語義軌跡，相關(guān)研究較為豐富[7]，鑒于篇幅所限，在此處不再詳述;然后針對每一個移動對象，提取其主要的語義行為模式集合.

在PrefixSpan算法的基礎(chǔ)上，我們提出了基于停留時間的語義行為模式挖掘算法STPM.STPM與PrefixSpan的不同之處在于投影數(shù)據(jù)庫的構(gòu)建，對于α，PrefixSpan中α-投影數(shù)據(jù)庫是由第1次出現(xiàn)的α為前綴的子序列構(gòu)成，而STPM中并不總以第1次出現(xiàn)的α為前綴.我們采用類似文獻[28]中的數(shù)據(jù)結(jié)構(gòu)來構(gòu)建α-投影數(shù)據(jù)庫.

tuple=sid,pos,t,proj，

其中,sid是語義軌跡在D中的標識號；pos是α中最后一個停留點在語義軌跡中的位置；t是在α中最后一個停留點的停留時間；proj是pos位置上以α為前綴的子序列.

表3為表2中語義軌跡集合的b-投影數(shù)據(jù)庫.

Table 3 b -projected Database

STPM算法的偽代碼如算法1所示.STPM是深度優(yōu)先遞歸算法，遞歸地擴展語義行為模式，以及試探其是否滿足頻繁語義行為模式的條件，并通過不斷構(gòu)建投影數(shù)據(jù)庫有效降低支持度及停留時間計算的時間復(fù)雜度.

算法1. STPM算法.

輸入：語義軌跡集合D、最小支持度fmin、停留閾值δt、語義行為模式P；

輸出：頻繁語義行為模式集合P.

②S1←Frequent(LD(P))；

③ forβinS1do

⑤P′←P⊕β;*P后擴展β*

⑥ LD(P)←?；

⑧ fortpin LD(P) do

⑨S←D(tp.sid)；

R=[tp′.t,tp′.t1-δt].

函數(shù)ValidSet()最終返回LD(P′)中停留時間在R范圍內(nèi)的項集M.

函數(shù)GeneratePattern()最終返回語義行為模式P′=P⊕(β,tβ).

在表3中，假設(shè)δt=0.5，tp′=3,4,1.5,?，則等價停留時間R=[1.5,3]，等價項集M={3,4,1.5,?,4,6,1.5,?}，停留點b的平均停留時間tb=(1.5+1.5)2=1.5.

4 語義行為模式相似性

本節(jié)介紹了語義行為模式之間的相似性度量方法.

從直覺上來說，語義行為模式之間的相似性與其之間的公共子串相關(guān)，因此我們采用公共子串來度量模式之間的相似性.

定義8. 最長公共子串.給定2個語義行為模式P1和P2，P1與P2的最長公共子串LCS滿足條件：

1)LCSP1∧LCSP2；

為了突出停留時間對語義行為模式的影響，我們給出了時間權(quán)值的定義.

定義9. 時間權(quán)值.給定語義行為模式P1，P2及其最長公共子串LCS，對于Ai∈LCS，Ai的時間權(quán)值定義為

定義10. 語義行為模式相似度.給定語義行為模式P1，P2及其最長公共子串LCS，P1與P2之間的相似度定義為

其中Ai∈LCS.

假設(shè)δt=0.5，給定2個語義行為模式P={(a,10),(b,1),(c,4)} 和Q={(a,10),(b,0.5),(d,0.5),(c,4)}，那么P與Q的最長公共子串為LCS(P,Q)=(a,10),(b,0.75),(c,4).表4給出了LCS的時間權(quán)值，因此P，Q之間的相似度為Sim(P,Q)=(13+14)×(1+0.5+1)=1.46.

Table 4 An Example of Time-Weight

動態(tài)規(guī)劃是尋找最長公共子串最有效的方法，動態(tài)規(guī)劃方法采用二維數(shù)組標識中間計算結(jié)果，避免了重復(fù)計算而提高了效率.我們修改了文獻[29]中的算法，采用矩陣SM保存最長公共子串計算過程中語義行為模式之間的時間權(quán)值.給定語義行為模式P，Q，SM[i,j]的計算公式定義為

SM[i,j]=

(1)

算法2. P-Similarity算法.

輸入：語義行為模式P和Q、停留閾值δt；

輸出：相似度Sim.

① fori=0 to |P| do

②SM[i,0].count←0,SM[i,0].t←0；

③ end for

④ forj=0 to |Q| do

⑤SM[0,j].count←0,SM[0,j].t←0；

⑥ end for

⑦ fori=1 to |P| do

⑧ forj=1 to |Q| do

⑨ ifPi?Qjw.r.tδtthen

⑩SM[i,j].count←SM[i-1,j-1]+wi j；

P(a，10)(b，1)(c，4)Q(0，0)(0，0)(0，0)(0，0)(a，10)(0，0)↖(1，10)←(1，10)←(1，10)(b，0．5)(0，0)↑(1，10)↖(1．5，0．75)←(1．5，0．75)(d，0．5)(0，0)↑(1，10)↑(1．5，0．75)←(1．5，0．75)(c，4)(0，0)↑(1，10)↑(1．5，0．75)↖(2．5，4)

Fig. 4 An example of P-Similarity
圖4 P-Similarity算法實例

5 基于模式相似性的移動對象聚類

本節(jié)介紹了如何在語義行為模式相似性的基礎(chǔ)上找出具有相似行為模式的移動對象集合，并提出了基于模式相似性的移動對象聚類算法SU-Clustering，然后在此基礎(chǔ)上介紹了SU-Clustering的優(yōu)化算法.

由于基于密度的聚類算法可能引入噪聲點，因此我們采用了層次聚類的方法.為了保證移動對象聚類的有效性，限定同一聚類中語義行為模式之間的最長公共子串長度不能小于長度閾值δlen.

算法3. SU-Clustering算法.

輸出：移動對象聚類集合MO.

①MO←?；

② fori=1 ton-1 do

③ forj=i+1 tondo

⑤Sim[i,j],Lcs[i,j]←P-Similarity(ci.P,cj.P)；

⑥ end for

⑦ end for

⑩FindSimPattern(Sim,Lcs,δlen)；

算法3中行⑧，函數(shù)FindSimPattern()返回滿足一對最相似聚類cp，cq的條件：

2)cp.U∩cq.U=?.

假設(shè)語義行為模式個數(shù)為n，語義行為模式的平均長度為m，迭代次數(shù)為n1，那么初始化矩陣Sim和矩陣Lcs的時間復(fù)雜度為O(n2m2)，層次聚類的時間復(fù)雜度為O(n1nm2).因為n1

在每次迭代過程中，函數(shù)Adjust()需要調(diào)用n次函數(shù)P-Similarity()以更新矩陣Sim和矩陣Lcs，而這將帶來較大的時間開銷.為了避免不必要的計算，我們給出了剪枝策略性質(zhì)1.

性質(zhì)1. 假設(shè)給定語義行為模式P和Q，P與Q的最長公共子串長度的邊界值等于P，Q之間等價的語義點個數(shù)，記作LCS-Boundary(P,Q).

利用性質(zhì)1，我們能通過剪枝策略對函數(shù)Adjust()進行優(yōu)化，優(yōu)化后Adjust()算法如算法4:

算法4. Adjust算法.

輸入：相似度矩陣Sim，最長公共子串矩陣Lcs，語義行為模式cp,cq,cnew，長度閾值δlen.

② 從Sim和Lcs中刪除第p行和第q列；

④ fori=1 ton-1 do

⑤ ifLCS-Boundary(cnew.P,ci.P)≥δlenthen

⑥Sim[n,i],Lcs[n,i]←P-Similarity(cnew.P,ci.P)；

⑦ end if

⑧ end for

⑨ return

假設(shè)語義行為模式個數(shù)為n，語義行為模式的平均長度為m，那么算法4的時間復(fù)雜度為O(nm2).雖然在最壞的情況下，算法4不能優(yōu)化Adjust()算法，但在實驗中我們發(fā)現(xiàn)優(yōu)化后的聚類算法能大約提高50%的效率，因此剪枝策略可以有效地減少不必要的計算代價，提高效率.

6 實驗結(jié)果與分析

本節(jié)實現(xiàn)了DSTra實驗系統(tǒng)，并在真實數(shù)據(jù)集和模擬數(shù)據(jù)集的基礎(chǔ)上，對語義行為模式的有效性、準確性以及效率進行了一系列實驗驗證.

實驗所用的真實數(shù)據(jù)集來自GeoLife[30-32]，GeoLife數(shù)據(jù)集是由微軟亞洲研究院182名志愿者采集的9 462條GPS軌跡構(gòu)成.實驗所用的模擬數(shù)據(jù)由機器產(chǎn)生，我們模擬了一系列移動對象，并依據(jù)每個移動對象的行為習(xí)慣對其生成了一系列語義軌跡.為了真實模擬移動對象的語義軌跡，我們使用了2個參數(shù)控制移動對象的行為習(xí)慣：Npc和Pr.具體來說，我們將語義行為模式共分為Npc種類型，每一類語義行為模式描述移動對象的一類行為習(xí)慣或生活方式.對于每個移動對象，其中Pr比例的語義軌跡隨機生成，剩下的語義軌跡依據(jù)Npc中的一部分行為模式生成.據(jù)此模擬的數(shù)據(jù)既具有一定的行為習(xí)慣又具有一定的靈活性，能較真實地還原移動對象的軌跡.

實驗程序用C++編寫，編譯工具為GCC 4.4.6，優(yōu)化選項為-O2.實驗硬件平臺處理器為Intel?Xeon?CPU E5-2630，主頻為2.3 GHz，內(nèi)存大小為4 GB；軟件平臺為CentOS release 6.2(Final).我們將從3個方面來分析DSTra的性能：1)語義行為模式挖掘的有效性；2)語義行為模式挖掘的準確率；3)語義行為模式挖掘的效率.表5給出了實驗中的主要參數(shù).

Table 5 Experiment Settings

6.1 有效性驗證

本節(jié)在真實數(shù)據(jù)集GeoLife的基礎(chǔ)上驗證了語義行為模式的有效性.

由于GeoLife數(shù)據(jù)集中的軌跡為GPS軌跡數(shù)據(jù)，因此不能在DSTra中直接使用，需要進行預(yù)處理.我們在處理中結(jié)合北京市POI數(shù)據(jù)庫，首先從GeoLife數(shù)據(jù)集中挖掘出家、公司、超市、游覽地、商場、車站、學(xué)校、公園、飯店幾類具有代表性的訪問點；然后以此為依據(jù)，將GPS軌跡轉(zhuǎn)換為相應(yīng)的語義軌跡；最后選擇了周末節(jié)假日的語義軌跡以發(fā)現(xiàn)更有趣的生活方式.

為了顯示停留時間對語義行為模式的影響，我們統(tǒng)計了語義軌跡中每個訪問點的停留時間(假設(shè)志愿者關(guān)閉采集器后都在家中)，并忽略了無法統(tǒng)計停留時間的語義軌跡.圖5是115號志愿者(簡稱115號)的語義行為模式在Google Map中的展示.參數(shù)設(shè)置為：fmin=0.1，δt=0.2.

Fig. 5 Semantic trajectory patterns of No.115圖5 115號語義行為模式

圖5(a)(b)是從115號的語義軌跡中抽取出的語義行為模式.可以看出，圖5(a)(b)的軌跡位置并不相似，基于地理位置信息的軌跡模式挖掘方法不能發(fā)現(xiàn)用戶的生活方式，而DSTra方法能有效地挖掘出語義行為模式(家,7.5 h)→(游覽地,2.5 h)→(家,11 h)，表示115號有周末出去游的生活習(xí)慣.

圖6是73號志愿者(簡稱73號)的語義行為模式在Google Map中的展示.參數(shù)設(shè)置為：fmin=0.1，δt=0.2.

Fig. 6 Semantic trajectory patterns of No.73圖6 73號語義行為模式

圖6是從73號的語義軌跡中抽取中的語義行為模式，即(游覽地，5.5 h)→(家,11 h).可以看出，DSTra方法可以準確地區(qū)分出115號與73號2種不同的生活方式，其中115號偏向周末小游一趟，73號則偏向周末外出暢游，而沒有考慮停留時間的軌跡模式挖掘方法卻不能分辨出其中差別.由此，根據(jù)用戶相似的生活習(xí)慣，DSTra可以將用戶進行聚類，同一聚類內(nèi)的用戶具有相似生活方式或行為習(xí)慣.

6.2 準確性驗證

本節(jié)模擬了100個移動對象，并依據(jù)每個移動對象的行為習(xí)慣各生成了1 000條語義軌跡，其中20%條語義軌跡隨機生成，80%條語義軌跡依據(jù)20種行為習(xí)慣生成.為了更好地評估語義行為模式挖掘的準確率，我們給出了準確率的定義：

其中,ξcorrect是正確的語義行為模式個數(shù)，ξall是所有的語義行為模式個數(shù).圖7是準確率與最小支持度fmin以及停留閾值δt的關(guān)系，參數(shù)設(shè)置為：Nmo=100，Ntrj=1 000，Lpattern=6，Npc=20，Pr=0.2.

圖7(a)顯示隨著最小支持度的增加，語義行為模式的準確率也隨之增加，這是因為隨著最小支持度的增加，挖掘出的語義行為模式更主流，相應(yīng)地錯誤的模式也就隨之減少，準確率增加.圖7(b)顯示語義行為模式的準確率隨著停留閾值的增加而逐漸減少，由于停留閾值增加會導(dǎo)致不同模式的區(qū)分度降低，從而導(dǎo)致準確率下降.

Fig. 7 Precision evaluation圖7 準確性評估

6.3 效率驗證

本節(jié)在模擬數(shù)據(jù)集的基礎(chǔ)上驗證了SU-Clustering及其優(yōu)化算法Optimized-SUC的執(zhí)行效率.圖8是SU-Clustering與Optimized-SUC算法的效率評估，圖8(a)中停留閾值δt=0.2，圖8(b)中模式平均長度Lpattern=6，其他參數(shù)設(shè)置為：Nmo=100，Ntrj=1 000，fmin=0.2，δlen=3.

Fig. 8 Runtime evaluation圖8 效率評估

圖8(a)為執(zhí)行時間與模式平均長度的關(guān)系，隨著模式平均長度的增加，SU-Clustering和Optimized-SUC的執(zhí)行時間都逐漸增加，這是由于隨著模式平均長度的增加，算法中最耗時的最長公共子串匹配的計算復(fù)雜度增加，從而導(dǎo)致效率下降.與此相似，圖8(b)中SU-Clustering和Optimized-SUC的效率也隨著停留閾值的增加而下降，因為最長公共子串匹配的時間復(fù)雜度也隨著停留閾值增加而增加.除此之外，圖8(a)(b)都顯示，算法Optimized-SUC的性能明顯優(yōu)于算法SU-Clustering，充分表明Optimized-SUC中的剪枝策略具有顯著的效果.

實驗結(jié)果顯示，本文提出的語義行為模式挖掘方法不僅具有合理性和有效性，同時還具有較高的準確率和較好的挖掘效率.

7 結(jié) 論

本文提出了一種語義行為模式挖掘方法，能夠挖掘出具有相似行為習(xí)慣或生活方式的移動對象群體.為了提高不同語義行為模式之間的區(qū)分度，本文引入了停留時間的概念，并在此基礎(chǔ)上提出了一種基于停留時間的語義行為模式挖掘方法DSTra.DSTra挖掘框架分為3部分:語義行為模式挖掘、模式相似性度量、基于模式相似性的移動對象聚類.DSTra方法具有廣泛的應(yīng)用前景.如在朋友推薦系統(tǒng)中，根據(jù)用戶提供的日常行為軌跡，挖掘出每個用戶的語義行為模式，利用模式相似性度量方法計算語義行為模式之間的相似性，最后基于模式相似性對用戶進行聚類，發(fā)現(xiàn)具有相似生活方式或行為習(xí)慣的用戶，并將聚類內(nèi)的用戶相互進行推薦.實驗結(jié)果表明，DSTra方法不僅具有合理性和有效性，還能夠準確并且有效地挖掘出語義行為模式.

[1]Keogh E J. Exact indexing of dynamic time warping[C]Proc of VLDB’02. San Francisco: Morgan Kaufman, 2002: 406-417

[2]Chen L, Ozsu M, Oria V. Robust and fast similarity search for moving object trajectories[C]Proc of ACM SIGMOD’05. New York: ACM, 2005: 491-502

[3]Vlachos M, Hadjieleftheriou M, Gunopulos D, et al. Indexing multidimensional time-series[J]. VLDB Journal, 2006, 15(1): 1-20

[4]Hung C C, Peng W C, Lee W C. Clustering and aggregating clues of trajectories for mining trajectory patterns and routes[J]. VLDB Journal, 2015, 24(2): 169-192

[5]Lee J G, Han Jiawei, Whang K Y. Trajectory clustering: A partition-and-group framework[C]Proc of ACM SIGMOD’07. New York: ACM, 2007: 593-604

[6]Li Quannan, Zheng Yu, Xie Xing, et al. Mining user similarity based on location history[C]Proc of Sigspatial GIS’08. New York: ACM, 2008

[7]Zheng Yu, Zhang Lizhu, Ma Zhengxin, et al. Recommending friends and locations based on individual location history[J]. ACM Trans on the Web, 2011, 5(1): 1-44

[8]Parent C, Spaccapietra S, Renso C, et al. Semantic trajectories modeling and analysis[J]. ACM Computing Surveys, 2013, 45(4): No.42

[9]Yan Zhixian, Chakraborty D, Parent C, et al. SeMiTri: A framework for semantic annotation of heterogeneous trajectories[C]Proc of EDBT’11. New York: ACM, 2011: 259-270

[10]Spaccapietra S, Parent C. Adding meaning to your steps[C]Proc of ER’11. Berlin: Springer, 2011: 13-31

[11]Alvares L O, Bogorny V, Kuijpers B, et al. Towards semantic trajectory knowledge discovery[EBOL]. 2007[2015-06-21]. https:uhdspace.uhasselt.bedspacebitstream194218321towards.pdf

[12]Liu Hechen, Schneider M. Similarity measurement of moving object trajectories[C]Proc of IWGS’12. New York: ACM, 2012: 19-22

[13]Zheng Yu, Zhang Lizhu, Xie Xing, et al. Mining interesting locations and travel sequences from GPS trajectories[C]Proc of WWW’09. New York: ACM, 2009: 791-800

[14]Zheng Yu, Xie Xing. Learning travel recommendations from user-generated GPS traces[J]. ACM Trans on Intelligent Systems and Technology, 2011, 2(1): No.2

[15]Ying J J C, Lu E H C, Lee W C, et al. Mining user similarity from semantic trajectories[C]Proc of LBSN’10. New York: ACM, 2010: 19-26

[16]Ying J C, Chen H S, Lin K W, et al. Semantic trajectory-based high utility item recommendation system[J]. Expert Systems with Applications, 2014, 41: 4762-4776

[17]Zhu Feixiang. Mining ship spatial trajectory patterns from AIS database for maritime surveillance[C]Proc of ICEMMS’11. Piscataway, NJ: IEEE, 2011: 772-775

[18]Smouse P E, Focardi S, Moorcroft P R, et al. Stochastic modeling of animal movement[J]. Philosophical Trans of the Royal Society of London-Series B: Biological Sciences, 2010, 365(1550): 2201-2211

[19]Li Zhenhui, Ji Ming, Lee J G, et al. MoveMine: Mining moving object databases[C]Proc of ACM SIGMOD’10. New York: ACM, 2010: 1203-1206

[20]Tsai H P, Yang D N, Chen M S. Mining group movement patterns for tracking moving objects efficiently[J]. IEEE Trans on Knowledge and Data Engineering, 2011, 23(2): 266-281

[21]Zheng Kai, Zheng Yu, Yuan N J. On discovery of gathering patterns from trajectories[C]Proc of ICDE’13. Piscataway, NJ: IEEE, 2013: 242-253

[22]Guo Limin, Huang Guangyan, Ding Zhiming. Efficient detection of emergency event from moving object data streams[C]Proc of DASFAA’14. Berlin: Springer, 2014: 422-437

[23]Jeung Hoyoung, Shen Hengtao, Zhou Xiaofang. Convoy queries in spatio-temporal databases[C]Proc of ICDE’08. Piscataway, NJ: IEEE, 2008: 1457-1459

[24]Al-Naymat G, Chawla S, Gudmundsson J. Dimensionality reduction for long duration and complex spatio-temporal queries[C]Proc of SAC’07. New York: ACM, 2007: 393-397

[25]Li Zhenhui, Ding Bolin, Han Jiawei, et al. Swarm: Mining relaxed temporal moving object clusters[J]. Proceedings of the VLDB Endowment, 2010, 3(1): 723-734

[26]Tang L A, Zheng Yu. On discovery of traveling companions from streaming trajectories[C]Proc of ICDE’12. Piscataway, NJ: IEEE, 2012: 186-197

[27]Wu H R, Yeh M Y, Chen M S. Profiling moving objects by dividing and clustering trajectories spatiotemporally[C]Proc of TKDE’12. Piscataway, NJ: IEEE, 2012: 2615-2628

[28]Srikant R, Agrawal R. Mining sequential patterns: Generalizations and performance improvements[C]Proc of the 5th Int Conf on Extending Database Technology. Piscataway, NJ: IEEE, 1996: 3-17

[29]Bergroth L, Hakonen H, Raita T. A survey of longest common subsequence algorithms[C]Proc of SPIRE’00. Piscataway, NJ: IEEE, 2000: 39-48

[30]Zheng Yu, Zhang Lizhu, Xie Xing, et al. Mining interesting locations and travel sequences from GPS trajectories[C]Proc of Int Conf on World Wild Web (WWW 2009). New York: ACM, 2009: 791-800

[31]Zheng Yu, Li Quannan, Chen Yukun, et al. Understanding mobility based on GPS data[C]Proc of ACM Conf on Ubiquitous Computing(UbiComp 2008). New York: ACM, 2008: 312-321

[32]Zheng Yu, Xie Xing, Ma Weiying. GeoLife: A collaborative social networking service among user, location and trajectory[J]. IEEE Data Engineering Bulletin, 2010, 33(2): 32-40

Guo Limin, born in 1984. PhD and lecturer in Beijing University of Technology. Her main research interests include database research and implementation, spatial-temporal data mining, storage, query and analysis of big data, etc.

Gao Xu, born in 1980. PhD candidate and lecturer in the Institute of Software, Chinese Academy of Sciences. His main research interests include database and knowledge base systems, and spatial-temporal database.

Wu Bin, born in 1982. PhD and research fellow in the Institute of Software, Chinese Academy of Sciences. His main research interests include massive data management and multidimensional data analysis.

Guo Haoming, born in 1978. PhD and senior engineer in the Institute of Software, Chinese Academy of Sciences. His main research interests include massive data management and multidimensional data analysis.

Xu Huaiye, born in 1987. Master and engineer in the Institute of Software, Chinese Academy of Sciences. His main research interests include massive data management and multidimensional data analysis.

Wei Yanyan, born in 1990. Master and assistant engineer in the Institute of Software, Chinese Academy of Sciences. Her main research interests include massive data management and multidimensional data analysis.

Wang Zhixin, born in 1989. Master and assistant engineer in the Institute of Software, Chinese Academy of Sciences. Her main research interests include massive data management and multidimensional data analysis.

Yan Li, born in 1990. Master and assistant engineer in the Institute of Software, Chinese Academy of Sciences. Her main research interests include networked control system.

Tian Mu, born in 1989. Master and assistant engineer in the Institute of Software, Chinese Academy of Sciences. His main research interest includes networked control system.

Discovering Common Behavior Using Staying Duration on Semantic Trajectory

Guo Limin1, Gao Xu2,3, Wu Bin2, Guo Haoming2, Xu Huaiye2, Wei Yanyan2, Wang Zhixin2, Yan Li2, and Tian Mu2

1(BeijingUniversityofTechnology,Beijing100124)2(InstituteofSoftware,ChineseAcademyofSciences,Beijing100190)3(UniversityofChineseAcademyofSciences,Beijing100049)

With the advancement of mobile computing technology and the widespread use of GPS-enabled mobile devices, research on semantic trajectories has attracted a lot of attentions in recent years, and the semantic trajectory pattern mining is one of the most important issues. Most existing methods discover the similar behavior of moving objects through the analysis of sequences of stops. However, these methods have not considered the duration of staying on a stop which affects the accuracy to distinguish different behavior patterns. In order to solve the problem, this paper proposes a novel approach for discovering common behavior using staying duration on semantic trajectory (DSTra) which can easily differentiate trajectory patterns. DSTra can be used to detect the group that has similar lifestyle, habit or behavior patterns. Semantic trajectory patterns of each moving object are mined firstly. Then, the time-weight based pattern similarity measurement is designed. After that, a hierarchical clustering method with pruning strategy is proposed, where each cluster represents the common behavior patterns from moving objects. Finally, experiments on both real-world dataset and synthetic dataset demonstrate the effectiveness, precision and efficiency of DSTra.

semantic trajectory; staying duration; semantic trajectory pattern; pattern similarity; moving object clustering

2015-09-01；

2016-11-04

國家自然科學(xué)基金項目(61402449,91546111,91646201)；中國科學(xué)院重點部署項目(KGZD-EW-102-3-3)；北京市教委重點項目(KZ201610005009)；北京工業(yè)大學(xué)“17內(nèi)涵發(fā)展定額——引進人才科研啟動費” This work was supported by the National Natural Science Foundation of China (61402449, 91546111, 91646201), the Key Deployment Project of the Chinese Academy of Sciences (KGZD-EW-102-3-3), the Key Project of Beijing Municipal Education Commission (KZ201610005009), and the Connotation Development 2017—Introducing the Talents Scientific Research Foundation of Beijing University of Technology.

TP311