一種時空軌跡群體運動移動簇模式的排序算法

張玉潔，吉根林，趙 斌，張書亮

1 (南京師范大學 計算機科學與技術學院, 南京 210023)

2 (南京師范大學 地理科學學院, 南京 210023)

1 引 言

隨著移動對象軌跡數據量的快速增長，軌跡數據的分析挖掘需求明顯增強.通過挖掘軌跡數據，可以發現大量時空軌跡模式.群體運動移動簇模式是時空軌跡模式的重要組成部分，其挖掘算法能夠挖掘出軌跡大數據中有價值的信息，從而用于分析移動對象群體的運動趨勢和運動規律[1].群體運動移動簇模式挖掘算法通常會產生大量挖掘結果且這些結果的質量參差不齊，如何從大量挖掘結果中找出有價值的、重要的結果，涉及到模式的排序問題.

群體運動移動簇模式(簡稱移動簇模式)是指移動對象群體在一定的時間間隔內一起移動所形成的簇序列，表現出空間相近、時間相關的特性.目前，群體運動移動簇模式主要包括成群模式(Flock)[2,3]、護航模式(Convoy)[4]、蜂群模式(Swarm)[5]、匯聚模式(Convergence)[6]、聚合模式(Gathering)[7,8]等.雖然以上模式的定義各不相同，挖掘結果的表現形式也互有差異，但是它們都面臨一個共同問題，即挖掘結果的數量龐大而且質量參差不齊.造成該問題的主要原因有兩方面.一方面，由于移動對象產生的時空軌跡數據量規模龐大且移動簇模式挖掘算法本身存在的參數敏感性問題，會導致移動簇模式挖掘算法產生大量結果.另一方面，在這些結果中，有部分結果雖然滿足模式定義，但是在現實生活中并無應用價值.例如，很多車輛在一段時間內聚集在交叉路口等待紅燈，這種情況雖然滿足移動簇模式的定義，但是用戶并不能從這些結果中獲取有用的信息.綜上所述，我們希望能夠對移動簇模式挖掘算法挖掘出的大量結果進行排序，從而挑選出更有意義的結果，幫助用戶利用這些結果進行交通規劃、事件分析以及商業決策.

現有的研究工作中，關于時空軌跡模式挖掘結果的排序問題并不多.2011年，Zhijun Yin等人[9]提出軌跡模式排序方法，但是該方法只針對頻繁模式的挖掘結果進行排序，并不適用于群體運動移動簇模式.目前，仍然沒有針對群體運動移動簇模式挖掘結果進行排序的研究工作.究其原因，是由于群體運動移動簇模式挖掘結果所包含的屬性各不相同，很難找到一種傳統的排序方法來對所有群體運動移動簇模式進行排序.

對于群體運動移動簇模式排序問題而言，最簡單的方法就是按照移動簇的持續時間或對象規模來進行排序.這種方法雖然簡單，但存在很大缺陷.例如交管部門通常對一些熱門區域(商業圈、車站、機場等)發生的事件更感興趣，然而這些區域的移動簇并不一定具有較長的持續時間或者較大的對象規模，如果使用上述方法對這樣的移動簇進行排序，則它們并不一定能被排在前面.因此，需要找到一個更有效的排序方法，幫助用戶找出與重要地理位置相關的移動簇.

通過對移動簇模式挖掘結果進行分析，可以利用移動簇中所包含的時空屬性對模式挖掘出的大量移動簇進行排序.然而，對移動簇進行排序面臨如下兩個方面的挑戰.首先，如何利用空間屬性對移動簇進行排序是一大難點.對于時間屬性，可以利用移動簇持續時間的長短來說明移動簇的重要性，而空間屬性由于只包含地理位置的信息，并沒有可量化的元素用于比較.因此如何從空間屬性中找到可用于比較的元素是一大挑戰；其次，對于排序問題而言，人們最關心的就是排序結果是否有效.如何找到一個基準排序結果，并利用該基準結果對排序方法進行合理的有效性評價也是一個挑戰.

本文提出了一種基于"移動簇-興趣點"的圖模型，該圖模型結合移動簇的空間屬性和興趣點兩個重要因素，對移動簇進行建模.相應地，基于"移動簇-興趣點"模型提出基于重啟式隨機游走的群體運動移動簇模式排序算法RWR-Ranking，對移動簇的空間屬性進行度量進而給出重要性排序.此外，將時空屬性結合，對RWR-Ranking算法進行改進，提出基于帶權重的重啟式隨機游走的群體運動移動簇模式排序算法WRWR-Ranking來對移動簇進行排序.最后，在實驗部分，利用可靠的外部資源(大眾點評網站游客的評分和推薦指數)作為基準排序結果，用排序方法中常用的一些評價指標P@N、MAP、NDCG[10-12]對實驗所得結果進行有效性評價，驗證了本文方法在群體運動移動簇排序方面的優勢.

2 問題定義

為了提高本文方法的適用性，給出群體運動移動簇模式挖掘結果的統一表現形式.以群體運動方向相同的蜂群模式和群體運動方向不同的聚合模式為例來抽象出移動簇的形式化定義.下面給出移動簇的形式化表示：

定義1.(移動簇Moving Cluster)給定群體運動移動簇模式的挖掘結果，即一系列移動簇的集合MC={mc1,mc2,mc3,…,mck}，每個移動簇mci={O,T,|O|,|T|,P}，其中：

1) 對象集O={o1,o2,o3,…,om}，表示移動簇所包含的對象集合；其中，oj為第j個對象；

2) 時間集T={t1,t2,t3,…,tn}，表示移動簇所包含的時間序列；其中，tj為第j個時間戳；

3) 對象規模|O|，表示對象集O中對象個數；

4) 持續時間|T|，表示時間集T中時間戳的個數；

5) 移動簇中心點集P={pt1,pt2,pt3,…,ptn}，其中，ptj對應移動簇在tj時刻的中心點，即簇中所有點的質心.mci.P表示移動簇mci的中心點集.

圖1 移動簇mc示例Fig.1 An example of moving cluster

圖1為一個移動簇的示例.該移動簇中O={o1,o2,o3,o4,o5,o6}，T={t1,t2,t3}，|O|=6，|T|=3，P={pt1,pt2,pt3}.

定義2.(興趣點)POI(Point of Interest)泛指一切可以抽象為點的地理對象，尤其是一些與人們生活密切相關的地理實體，如學校、銀行、餐館、加油站、醫院、超市、景區等.興趣點主要用于對事物和事件的地址進行描述.

定義3.(移動簇的重要性)移動簇的重要性主要體現在兩方面：

1) 移動簇的持續時間越長，該移動簇越重要；

2) 移動簇的中心點附近POI越多，該移動簇越重要；

定義4.(移動簇模式排序)給定群體運動移動簇模式的挖掘結果集MC，群體運動移動簇模式排序對移動簇集合MC中所包含的移動簇進行重要性排序，并以重要性得分降序輸出.

3 算法設計

3.1 重啟式隨機游走模型(RWR)

重啟式隨機游走模型(Random Walk with Restart，RWR)[13]用于度量圖上頂點間的相似度[14-16].其主要思想是從圖中某個頂點出發，沿著圖中的邊隨機游走.在任意點上，以一定的概率隨機選擇與該頂點相鄰的邊，沿著邊移動到下一個頂點，或以一定的概率直接回到出發點.經過有限次的隨機游走過程，圖中每個頂點的概率值達到平穩狀態，再次迭代也不會改變圖中的概率分布.此時，圖中每個點的概率值可以看作該頂點與出發點的相似度.

RWR的數學表達式[13]為：

p(t+1)=(1-α)·M·p(t)+α·q

(1)

其中，p(t)、p(t+1)和q是列向量.p(t)表示第t步圖中的頂點概率分布，pi(t)表示第t步到達頂點i的概率.列向量q為重啟動向量，表示初始狀態，qi表示初始狀態下粒子在頂點i的概率.列向量q中設置目標用戶頂點值為1，其余為0.M是轉移概率矩陣，它的元素Mi,j表示當前頂點i下一步到達頂點j的轉移概率.α為直接回到出發頂點的概率即重啟概率.概率分布使用公式(1)計算.它在圖的隨機游走過程中被執行，重復迭代，直到前后兩次p的一范數‖p‖1=∑|pi| 差值小于給定的閾值ε，則認為p收斂，得到出發頂點到圖中其他頂點的穩定概率分布.

3.2 "移動簇-興趣點"圖模型

由于移動簇模式挖掘出的移動簇包含空間屬性且該屬性與地理空間中的興趣點有著不可分割的聯系，因此本文提出結合移動簇的空間屬性和興趣點兩個重要因素的圖模型"移動簇-興趣點".由于圖的特殊結構，使得可以將不同的因素考慮進來，挖掘出因素之間的關聯[17].本文采用"移動簇-興趣點"圖模型對移動簇和興趣點之間的聯系進行建模.

"移動簇-興趣點"模型基于二分圖G=(V,E)，其中V={MC∪POI},它是二分圖中結點的有窮非空集合；MC結點集代表移動簇模式挖掘算法所挖掘出結果中的所有移動簇的集合，POI結點集代表該挖掘算法所使用數據集中的興趣點的集合.邊集E={(mc,poi) |mc∈MC,poi∈POI}是移動簇和興趣點之間關系的有窮集合.令eij∈E表示移動簇mci到興趣點poij的一條邊.對于每一個移動簇mci，其空間屬性中包含一個中心點或多個中心點的序列.對于中心點序列中的每一個點，我們找到興趣點集合POI中與該點距離小于閾值γ的所有興趣點，并認為這些興趣點與移動簇mci之間有聯系，在二分圖中移動簇與興趣點之間存在一條邊.

如圖2所示，圖中左側每個結點代表一個移動簇，右側每個結點代表一個興趣點.移動簇mc1與興趣點poi1、poi2、poi3之間均存在一條邊，這說明移動簇mc1的中心點序列中的點與興趣點poi1、poi2、poi3之間的距離小于閾值γ.

圖2 MC-POI二分圖示例Fig.2 An example of bipartite graph MC-POI

二分圖G={MC∪POI,E}被存儲在矩陣M中.M中的元素Mij可以定義為如下形式，其中eij表示圖中移動簇mci與興趣點poij相連的邊.

(2)

算法1簡要描述了"移動簇-興趣點"二分圖的矩陣構建算法.首先初始化矩陣M(第1-3行)，接著對于任意移動簇mci∈MC，獲取該移動簇的中心點序列mci.P.對于中心點序列中的每一個點pk∈mci.P，得到其鄰域半徑γ內的興趣點集POIpk(第4-6行).興趣點集POIpk中的每一個點poij，認為其與移動簇mci有聯系，把矩陣對應元素Mij賦值為1(第7-8行).最后返回構建好的"移動簇-興趣點"二分圖的矩陣M(第9行).

算法1."移動簇-興趣點"二分圖的矩陣構建算法CreateMBGraph

輸入：移動簇的集合MC，興趣點的集合POI，距離閾值γ

輸出：矩陣M

1.for(i=1;i≤|MC|;i++)

2. for (j=1;j≤|POI|;j++)

3.Mij=0

4.foreachmci∈MCdo

5.foreachpk∈mci.Pdo

6. POIpk=getPOI(pk,POI,γ)

7.foreachpoij∈POIpk

8.Mij=1

9.return M

3.3 基于RWR的群體運動移動簇模式排序算法

利用3.2節中構造的 "移動簇-興趣點"圖模型來對移動簇進行重要性排序.對群體運動移動簇模式挖掘出的移動簇進行重要性排序問題可以轉換為圖中頂點的重要性計算問題，每個頂點的概率值代表該頂點的重要性，概率值越大說明該頂點越重要.對于圖中頂點的重要性，本文提出如下假設：

1)如果一個移動簇的中心點被很多重要的poi覆蓋，則認為該移動簇是重要的.

2)如果一個poi覆蓋很多重要移動簇的中心點，則認為該poi是重要的.

利用重啟式隨機游走算法得到圖中每個點的穩定的概率分布，按概率值對所有點進行降序排列，概率值越高說明該點越重要.排在前面的移動簇即為用戶感興趣的結果.

對群體運動移動簇模式挖掘出的所有移動簇集合MC={mc1,…,mcn}，利用3.2節中的"移動簇-興趣點"圖模型構建二分圖，二分圖存儲在矩陣M中.

使用M構建鄰接矩陣M′：

(3)

算法2簡要描述了對移動簇的排序過程.首先利用移動簇的中心點和興趣點之間的關系建立MC-POI二部圖，生成矩陣M(第1行)，然后利用公式(3)構造方陣M′，并對M′進行行歸一化處理(第2-4行)，接著初始化列向量p和q中的元素，最后利用公式(1)進行迭代計算，直到滿足迭代的終止條件，得到排序結果即列向量p(第5-10行).此時P中還包含POI的重要性排序結果，對P中元素進行篩選，得到移動簇的重要性排序結果(第11-12行).

算法2. 基于RWR的群體運動移動簇模式排序算法(RWR-Ranking)

輸入：移動簇的集合MC，重啟概率α，興趣點的集合POI，停止迭代過程的參數ε，距離閾值γ

輸出：移動簇排序序列Q

1.M=CreateMBGraph(MC,POI,γ)

// 調用算法1

2.MT=TransposeMatrix(M)

3.M′=CreateSquareMatrix(M,MT)

4.對M′進行行歸一化處理

5.for(i=1;i≤|MC|+|POI|;i++)

7.t=0

8.while‖p(t+1)‖1-‖p(t)‖1>εdo

9.p(t+1)=(1-α)·M′·p(t)+α·q

10.t++

11.Q=DeletePOI(p)

12.return Q

3.4 基于WRWR的群體運動移動簇模式排序

上述方法將重啟式隨機游走模型應用于群體運動移動簇模式的排序問題，利用移動簇的空間屬性和POI之間的聯系構建"移動簇-興趣點"圖模型，對所有移動簇進行重要性排序.但是進一步分析，移動簇所處的地理位置固然重要，移動簇的持續時間也在一定程度上反映了該移動簇的重要性.因此，考慮將時間屬性加入進來，對移動簇進行時空屬性的綜合排序.基于以上考慮，本文提出基于帶權重的重啟式隨機游走(Weighted Random Walk with Restart，WRWR)的群體運動移動簇模式排序算法WRWR-Ranking，將時間屬性作為邊上的權重來重新構建二部圖.假設一個移動簇它在某個POI附近停留的時間越長，其在二部圖的邊上所占的權重就越大，在隨機游走的過程中，轉移概率也越大.

對于任意給定的起始節點vj，定義從節點vj到vi的轉移概率P(vi│vj)如(4)：

(4)

其中，P(vi│vj)的計算依賴于相關的有向邊及其屬性，而對于邊eij∈E，轉移概率P(vi│vj)主要由邊上時間屬性決定.本節將介紹將時間屬性作為權重的WRWR-Ranking方法.

在上節介紹的RWR-Ranking方法中，二部圖中所有邊上的權重是一樣的，即都為1.而考慮時間因素后，將每一個移動簇在興趣點附近的停留時間作為權重賦值給與該移動簇有關聯的興趣點所連成的邊.對于移動簇mc1來說，由于其中心點序列中的點覆蓋了poi1、poi2、poi3三個興趣點，獲取移動簇mc1在poi1、poi2、poi3三個興趣點附近停留的時間t11,t12,t13，并分別作為權重賦值給mc1-poi1，mc1-poi2，mc1-poi3三條邊.二部圖構建過程如圖3所示.

圖3 WRWR-Ranking方法的二部圖構建示例Fig.3 Example of constructing a bipartitegraph of WRWR-Ranking

二部圖所對應的矩陣表示形式如下，其中w(eij)代表邊eij上的權重：

(5)

(6)

仍然用3.2中使用的方法構建鄰接矩陣，然后用公式(1)來進行迭代計算.

由于考慮時間因素后，僅需要改變鄰接矩陣的構造方法，其余步驟和算法2相同.因此，這里只介紹帶權重的二分圖的矩陣構造方法.對于移動簇mci中心點集中的點pk，如果其與興趣點poij之間的距離dist(pk,poij)≤γ，則獲取移動簇mci在興趣點poij附近的停留時間，并將停留時間作為權重賦值給移動簇mci與興趣點poij相連的邊eij.相應地，矩陣對應位置上的元素值為w(eij).

4 實驗與分析

4.1 實驗設置

為了說明本文方法的適用性，選取群體運動移動簇模式相關工作中的聚合模式和蜂群模式進行實驗.以上兩種模式分別為數據庫頂級會議關于聚集運動模式和伴隨運動模式方面較近的研究工作.由于蜂群模式完全放松對時間的要求，因此挖掘結果中噪聲較多，對排序方法的要求也更高，通過蜂群模式可以更好的驗證本文方法的有效性.

使用兩個真實的GPS軌跡數據集分別實現文獻[7]中的聚合模式挖掘算法TAD和文獻[5]中的蜂群模式挖掘算法ObjectGrowth.數據集一(HKT)為香港海洋公園2014年7月6日至7月10日五天中每天上午10點至晚上8點的游客移動軌跡數據，數據集二(BJT)為北京市13617輛出租車在2012年11月2日至11月8日的GPS數據.實驗參數如表1所示.其中，eps表示聚類DBSCAN鄰域半徑閾值，pts表示鄰域密度閾值，kc表示群體生命周期，mc表示移動對象群體規模閾值，kp表示移動簇中參與者生命周期閾值，mp表示移動簇中參與者數量閾值.

表1 聚合模式和蜂群模式實驗參數Table 1 Experiment parameter of gathering and swarm

算法TAD和ObjectGrowth輸出結果即為聚合移動簇和蜂群移動簇的集合，移動簇集合中移動簇的個數統計如表2所示.使用本文方法分別對其進行排序.

對于北京市出租車數據集，其對應的北京市POI數據集是公開的1.對于香港海洋公園數據集，本文認為一個游樂項目代表一個POI，因此使用海洋公園中所有游樂項目構成POI集合.

由于目前移動對象群體運動移動簇模式排序算法尚未報道，因此本文方法無法與其他方法進行比較，為了說明本文方法的有效性，首先對兩個移動簇的集合進行單屬性排序，即只按照移動簇的持續時間從大到小對其進行排序.然后將單屬性排序結果與RWR-Ranking方法、WRWR-Ranking方法所得結果進行比較.

1http://download.csdn.net/download/zhaoguangxu/7602575

4.2 評價指標

使用信息檢索中常用的對于檢索結果的評價指標P@N、MAP、NDCG@N[18]來衡量排序結果的好壞.以下分別介紹這三個評價指標：

1)P@N：前N篇檢索結果中相關文檔的比例，對于網絡搜索引擎而言，由于大部分用戶比較多地只查看前一至兩頁的檢索結果，因此提高前十條或者前二十條檢索結果中相關文檔的比例顯得尤為重要.因此，P@5、P@10和P@20的分值能比較真實地反映網絡搜索引擎在實際生活檢索場景中的檢索性能.

2)MAP(Mean Average Precision)：對所有查詢的平均正確率求平均.每個主題的平均準確率是每次查詢平均準確率的平均值，主集合的平均準確率是每個主題的平均準確率的平均值.MAP指標可以反映檢索系統在全部相關文檔上的性能.檢索出的相關文檔越靠前，MAP值就可能越高.

表2 排序算法輸入數據Table 2 Input data of ranking algorithm

3)NDCG(Normalized Discounted Cumulative Gain)：衡量搜索引擎質量指標，利用NDCG進行評價時，每個文檔的相關性劃分不再是相關和不相關兩種，而是具有相關度級別，比如0，1，2，3.級別越高，相關度越高.在檢索結果中，相關度級別越高的文檔越多，NDCG值就越高.同時，相關度級別越高的文檔越靠前NDCG值越高.

4.3 BJT數據集實驗分析

對于BJT數據集，選取工作日早高峰(7:00-9:30)、周末白天(8:00-18:00)、周末夜晚(18:00-22:00)三個容易產生聚合事件的時間段進行實驗.對獲得的聚合移動簇的集合分別使用單屬性排序、RWR-Ranking、WRWR-Ranking三個方法進行排序.由于北京市特殊的城市布局，本文直接使用北京市的地理特性來輔助說明排序結果的有效性.

表3 北京市出租車數據聚合移動簇發現結果Table 3 Results of discovering gathering moving cluster for Beijing Taxi Data

對于工作日早高峰的排序結果，選取單屬性排序和WRWR-Ranking方法所得結果中排名前25聚合移動簇，發現后者所得到的前25個移動簇中，有2個移動簇的中心點位于三環以內，且都位于中央商務區(Central Business District，CBD).位于四環和五環以內的分別有3個和7個移動簇.而相比之下，用單屬性排序方法，并不能找到位于三環和四環的移動簇.這也就間接說明WRWR-Ranking方法的有效性.除此之外，本文還比較了周末白天和周末夜晚的實驗結果，所得結論與上文一致.具體數據如表3所示.

4.4 HKT數據集實驗分析

4.4.1 可視化分析

以香港海洋公園2014年7月7日產生的聚合移動簇為例，分析單屬性和WRWR-Ranking方法的排序結果.如圖4所示，圖中圖釘表示一個移動簇的中心.觀察發現單屬性排序排在前面的移動簇發生的地點都集中在海洋劇場周圍.海洋劇場作為一個每天定時開放的表演場地，有固定的開放時間和表演時間，且表演持續時間較長，因此這樣的地方較容易發生聚合事件.對于以上用戶已知的容易發生聚合事件的地點，用戶對該地點產生的移動簇的興趣度較低.而WRWR-Ranking方法的排序結果，不僅能夠發現人們經驗常識里容易發生聚合事件的地點，該方法還能發現諸如水母萬花筒、尋鯊探秘、登山纜車這樣的游樂項目附近發生的重要事件.這些項目都是網友推薦指數較高的項目，這說明了本文方法與現實生活中實際場景相吻合.而單屬性排序并沒有找出發生在這些項目附近的聚合事件.

4.4.2 基準排序結果

對于HKT數據集而言，可以進一步借助基準排序結果來定量分析三種排序方法的好壞.在本文中，使用可靠的外部資源作為基準結果對上述排序方法進行有效性評價.我們統計了大眾點評網站游客對于香港海洋公園內每個游樂項目的評論數以及評分，然后基于評論數量對園內游樂項目進行排序，評論數越多則該游樂項目排名越靠前.這里的評論數量認為是該游樂項目的熱度及受歡迎程度.

4.4.3 評價指標分析

對于HKT數據集5天中每天的聚合移動簇和蜂群移動簇，以基準排序結果為參照，對三種排序結果進行有效性評價.選用的評價指標為P@15、MAP以及NDCG@25.圖5為兩種模式的排序結果得到的各項評價指標得分.

Time字段表示單屬性排序的結果，RWR字段表示使用重啟式隨機游走模型的排序結果，WRWR字段表示帶時間權重的重啟式隨機游走模型的排序結果.以聚合模式為例，比較RWR-Ranking方法和單屬性排序方法，發現RWR-Ranking方法優于單屬性排序方法，P@15、MAP和NDCG@25分別提高17.2%、110.4%和14.4%.對于本文提出的WRWR-Ranking和RWR-Ranking方法，發現相比RWR-Ranking方法，WRWR-Ranking方法P@15、MAP和NDCG@25分別提高了35%、11.4%和41.8%.由此，可得出對于群體運動移動簇模式的排序問題而言，WRWR-Ranking方法優于RWR-Ranking方法，RWR-Ranking方法優于單屬性排序方法.此外，發現蜂群模式在7月9日和10日使用RWR-Ranking和WRWR-Ranking方法NDCG@25得分相同.究其原因是在計算NDCG@25時，為每個POI指定一個相關度級別，有很多POI相關度級別是一致的.因此，雖然排序結果不同，但如果對應位置上POI的相關度級別一致，NDCG@25得分就相同.進一步比較圖5中(e)和(f)可以看出聚合模式WR-Ranking方法排序結果優于蜂群模式.其原因在于蜂群模式完全放松對時間的要求，導致其挖掘結果中包含很多噪聲，為排序增加難度.但分析蜂群模式的三項評價指標得分.仍然可以得出WRWR-Ranking方法優于單屬性排序且不遜于RWR-Ranking方法的結論.

綜上所述，對于群體運動移動簇模式排序問題，WRWR-Ranking方法優于RWR-Ranking方法，RWR-Ranking方法優于單屬性排序方法.這表明本文排序方法是有效的.對于單屬性排序而言，它所得到的結果較為片面、偶然性較強且排序的結果不穩定.RWR-Ranking方法雖然利用移動簇中心點和POI之間的聯系，得到每個移動簇的重要性排名，但是該方法只考慮了空間因素而忽略了時間屬性.WRWR-Ranking方法將時空因素綜合考慮，得到較為全面、穩定的排名，對于用戶有著較高的參考價值.

(a) 移動簇可視化結果 (b) 單屬性排序Top-10的移動簇 (c) WRWR排序Top-10的移動簇

圖5 評價指標得分統計Fig.5 Score statistics of evaluating index

5 結束語

本文針對移動對象群體運動移動簇模式的重要性，提出一種時空軌跡群體運動移動簇模式的排序算法.利用移動簇的時空屬性，將重啟式隨機游走模型應用于移動簇的排序問題，幫助用戶從大量結果中篩選出其感興趣的少數結果.提出群體運動移動簇模式排序算法RWR-Ranking，結合移動簇的空間屬性和POI之間的聯系，利用重啟式隨機游走模型對移動簇進行重要性排序.此外，考慮將時空因素相結合，對RWR-Ranking算法進行改進， 提出WRWR-Ranking算法.最后，基于真實的實驗驗證了本文提出的RWR-Ranking方法和WRWR-Ranking方法在群體運動移動簇模式排序方面明顯優于只考慮時間因素的單屬性排序方法.其中，WRWR-Ranking方法能夠幫助用戶找出更多潛在的重要移動簇.