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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 相關工作

本節首先介紹了軌跡相似性度量方法，然后概述了現有的軌跡模式挖掘技術.

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

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

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

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

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

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

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

2 問題定義

本節以語義軌跡為基礎，首先給出了語義行為模式的相關問題定義，然后介紹了DSTra方法的系統架構.

為便于敘述，表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對相應2個語義點之間的停留時間進行了約束，即停留時間比例差受限于δt.

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

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

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

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

以表2為例，假設δt=0.5，fmin=0.5，依據定義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)依據fmin和δt，從D中進行行為語義提取，找出所有語義行為模式的集合P；2)度量P中模式之間的相似度；3)在相似度的基礎上，依據移動對象的相似生活方式、行為習慣等進行聚類.

由此，我們提出了一種語義行為模式的挖掘方法——基于停留時間的語義行為模式挖掘DSTra.DSTra的系統結構如圖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的系統結構

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

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

本節首先給出了相關數據結構，然后詳細介紹了語義行為模式挖掘算法STPM.

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

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

tuple=sid,pos,t,proj，

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

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

Table 3 b -projected Database

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

算法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].

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

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

在表3中，假設δ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 語義行為模式相似性

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

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

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

1)LCSP1∧LCSP2；

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

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

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

其中Ai∈LCS.

假設δ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的時間權值，因此P，Q之間的相似度為Sim(P,Q)=(13+14)×(1+0.5+1)=1.46.

Table 4 An Example of Time-Weight

動態規劃是尋找最長公共子串最有效的方法，動態規劃方法采用二維數組標識中間計算結果，避免了重復計算而提高了效率.我們修改了文獻[29]中的算法，采用矩陣SM保存最長公共子串計算過程中語義行為模式之間的時間權值.給定語義行為模式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 基于模式相似性的移動對象聚類

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

由于基于密度的聚類算法可能引入噪聲點，因此我們采用了層次聚類的方法.為了保證移動對象聚類的有效性，限定同一聚類中語義行為模式之間的最長公共子串長度不能小于長度閾值δ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中行⑧，函數FindSimPattern()返回滿足一對最相似聚類cp，cq的條件：

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

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

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

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

利用性質1，我們能通過剪枝策略對函數Adjust()進行優化，優化后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

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

6 實驗結果與分析

本節實現了DSTra實驗系統，并在真實數據集和模擬數據集的基礎上，對語義行為模式的有效性、準確性以及效率進行了一系列實驗驗證.

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

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

Table 5 Experiment Settings

6.1 有效性驗證

本節在真實數據集GeoLife的基礎上驗證了語義行為模式的有效性.

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

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

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

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

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

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

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

6.2 準確性驗證

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

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

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

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

6.3 效率驗證

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

Fig. 8 Runtime evaluation圖8 效率評估

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

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

7 結 論

本文提出了一種語義行為模式挖掘方法，能夠挖掘出具有相似行為習慣或生活方式的移動對象群體.為了提高不同語義行為模式之間的區分度，本文引入了停留時間的概念，并在此基礎上提出了一種基于停留時間的語義行為模式挖掘方法DSTra.DSTra挖掘框架分為3部分:語義行為模式挖掘、模式相似性度量、基于模式相似性的移動對象聚類.DSTra方法具有廣泛的應用前景.如在朋友推薦系統中，根據用戶提供的日常行為軌跡，挖掘出每個用戶的語義行為模式，利用模式相似性度量方法計算語義行為模式之間的相似性，最后基于模式相似性對用戶進行聚類，發現具有相似生活方式或行為習慣的用戶，并將聚類內的用戶相互進行推薦.實驗結果表明，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

國家自然科學基金項目(61402449,91546111,91646201)；中國科學院重點部署項目(KGZD-EW-102-3-3)；北京市教委重點項目(KZ201610005009)；北京工業大學“17內涵發展定額——引進人才科研啟動費” 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