一種時空軌跡群體運(yùn)動移動簇模式的排序算法

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

1 (南京師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 南京 210023)

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

1 引 言

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

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

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

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

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

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

2 問題定義

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

定義1.(移動簇Moving Cluster)給定群體運(yùn)動移動簇模式的挖掘結(jié)果，即一系列移動簇的集合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) 對象規(guī)模|O|，表示對象集O中對象個數(shù)；

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

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

圖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.(興趣點(diǎn))POI(Point of Interest)泛指一切可以抽象為點(diǎn)的地理對象，尤其是一些與人們生活密切相關(guān)的地理實(shí)體，如學(xué)校、銀行、餐館、加油站、醫(yī)院、超市、景區(qū)等.興趣點(diǎn)主要用于對事物和事件的地址進(jìn)行描述.

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

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

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

定義4.(移動簇模式排序)給定群體運(yùn)動移動簇模式的挖掘結(jié)果集MC，群體運(yùn)動移動簇模式排序?qū)σ苿哟丶螹C中所包含的移動簇進(jìn)行重要性排序，并以重要性得分降序輸出.

3 算法設(shè)計(jì)

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

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

RWR的數(shù)學(xué)表達(dá)式[13]為：

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

(1)

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

3.2 "移動簇-興趣點(diǎn)"圖模型

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

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

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

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

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

(2)

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

算法1."移動簇-興趣點(diǎn)"二分圖的矩陣構(gòu)建算法CreateMBGraph

輸入：移動簇的集合MC，興趣點(diǎn)的集合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的群體運(yùn)動移動簇模式排序算法

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

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

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

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

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

使用M構(gòu)建鄰接矩陣M′：

(3)

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

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

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

輸出：移動簇排序序列Q

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

// 調(diào)用算法1

2.MT=TransposeMatrix(M)

3.M′=CreateSquareMatrix(M,MT)

4.對M′進(jìn)行行歸一化處理

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的群體運(yùn)動移動簇模式排序

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

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

(4)

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

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

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

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

(5)

(6)

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

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

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)置

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

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

表1 聚合模式和蜂群模式實(shí)驗(yàn)參數(shù)Table 1 Experiment parameter of gathering and swarm

算法TAD和ObjectGrowth輸出結(jié)果即為聚合移動簇和蜂群移動簇的集合，移動簇集合中移動簇的個數(shù)統(tǒng)計(jì)如表2所示.使用本文方法分別對其進(jìn)行排序.

對于北京市出租車數(shù)據(jù)集，其對應(yīng)的北京市POI數(shù)據(jù)集是公開的1.對于香港海洋公園數(shù)據(jù)集，本文認(rèn)為一個游樂項(xiàng)目代表一個POI，因此使用海洋公園中所有游樂項(xiàng)目構(gòu)成POI集合.

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

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

4.2 評價指標(biāo)

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

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

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

表2 排序算法輸入數(shù)據(jù)Table 2 Input data of ranking algorithm

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

4.3 BJT數(shù)據(jù)集實(shí)驗(yàn)分析

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

表3 北京市出租車數(shù)據(jù)聚合移動簇發(fā)現(xiàn)結(jié)果Table 3 Results of discovering gathering moving cluster for Beijing Taxi Data

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

4.4 HKT數(shù)據(jù)集實(shí)驗(yàn)分析

4.4.1 可視化分析

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

4.4.2 基準(zhǔn)排序結(jié)果

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

4.4.3 評價指標(biāo)分析

對于HKT數(shù)據(jù)集5天中每天的聚合移動簇和蜂群移動簇，以基準(zhǔn)排序結(jié)果為參照，對三種排序結(jié)果進(jìn)行有效性評價.選用的評價指標(biāo)為P@15、MAP以及NDCG@25.圖5為兩種模式的排序結(jié)果得到的各項(xiàng)評價指標(biāo)得分.

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

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

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

圖5 評價指標(biāo)得分統(tǒng)計(jì)Fig.5 Score statistics of evaluating index

5 結(jié)束語

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