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

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

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

1 引 言

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

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

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

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

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

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

2 問題定義

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

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

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

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

3) 對(duì)象規(guī)模|O|，表示對(duì)象集O中對(duì)象個(gè)數(shù)；

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

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

圖1 移動(dòng)簇mc示例Fig.1 An example of moving cluster

圖1為一個(gè)移動(dòng)簇的示例.該移動(dòng)簇中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)的地理對(duì)象，尤其是一些與人們生活密切相關(guān)的地理實(shí)體，如學(xué)校、銀行、餐館、加油站、醫(yī)院、超市、景區(qū)等.興趣點(diǎn)主要用于對(duì)事物和事件的地址進(jìn)行描述.

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

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

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

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

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

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

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

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

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

如圖2所示，圖中左側(cè)每個(gè)結(jié)點(diǎn)代表一個(gè)移動(dòng)簇，右側(cè)每個(gè)結(jié)點(diǎn)代表一個(gè)興趣點(diǎn).移動(dòng)簇mc1與興趣點(diǎn)poi1、poi2、poi3之間均存在一條邊，這說明移動(dòng)簇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}被存儲(chǔ)在矩陣M中.M中的元素Mij可以定義為如下形式，其中eij表示圖中移動(dòng)簇mci與興趣點(diǎn)poij相連的邊.

(2)

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

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

輸入：移動(dòng)簇的集合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)動(dòng)移動(dòng)簇模式排序算法

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

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

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

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

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

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

(3)

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

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

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

輸出：移動(dòng)簇排序序列Q

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

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

2.MT=TransposeMatrix(M)

3.M′=CreateSquareMatrix(M,MT)

4.對(duì)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)動(dòng)移動(dòng)簇模式排序

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

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

(4)

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

在上節(jié)介紹的RWR-Ranking方法中，二部圖中所有邊上的權(quán)重是一樣的，即都為1.而考慮時(shí)間因素后，將每一個(gè)移動(dòng)簇在興趣點(diǎn)附近的停留時(shí)間作為權(quán)重賦值給與該移動(dòng)簇有關(guān)聯(lián)的興趣點(diǎn)所連成的邊.對(duì)于移動(dòng)簇mc1來說，由于其中心點(diǎn)序列中的點(diǎn)覆蓋了poi1、poi2、poi3三個(gè)興趣點(diǎn)，獲取移動(dòng)簇mc1在poi1、poi2、poi3三個(gè)興趣點(diǎn)附近停留的時(shí)間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

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

(5)

(6)

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

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

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

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

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

使用兩個(gè)真實(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)的游客移動(dòng)軌跡數(shù)據(jù)，數(shù)據(jù)集二(BJT)為北京市13617輛出租車在2012年11月2日至11月8日的GPS數(shù)據(jù).實(shí)驗(yàn)參數(shù)如表1所示.其中，eps表示聚類DBSCAN鄰域半徑閾值，pts表示鄰域密度閾值，kc表示群體生命周期，mc表示移動(dòng)對(duì)象群體規(guī)模閾值，kp表示移動(dòng)簇中參與者生命周期閾值，mp表示移動(dòng)簇中參與者數(shù)量閾值.

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

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

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

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

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

4.2 評(píng)價(jià)指標(biāo)

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

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

2)MAP(Mean Average Precision)：對(duì)所有查詢的平均正確率求平均.每個(gè)主題的平均準(zhǔn)確率是每次查詢平均準(zhǔn)確率的平均值，主集合的平均準(zhǔn)確率是每個(gè)主題的平均準(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)行評(píng)價(jià)時(shí)，每個(gè)文檔的相關(guān)性劃分不再是相關(guān)和不相關(guān)兩種，而是具有相關(guān)度級(jí)別，比如0，1，2，3.級(jí)別越高，相關(guān)度越高.在檢索結(jié)果中，相關(guān)度級(jí)別越高的文檔越多，NDCG值就越高.同時(shí)，相關(guān)度級(jí)別越高的文檔越靠前NDCG值越高.

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

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

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

對(duì)于工作日早高峰的排序結(jié)果，選取單屬性排序和WRWR-Ranking方法所得結(jié)果中排名前25聚合移動(dòng)簇，發(fā)現(xiàn)后者所得到的前25個(gè)移動(dòng)簇中，有2個(gè)移動(dòng)簇的中心點(diǎn)位于三環(huán)以內(nèi)，且都位于中央商務(wù)區(qū)(Central Business District，CBD).位于四環(huán)和五環(huán)以內(nèi)的分別有3個(gè)和7個(gè)移動(dòng)簇.而相比之下，用單屬性排序方法，并不能找到位于三環(huán)和四環(huán)的移動(dòng)簇.這也就間接說明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)生的聚合移動(dòng)簇為例，分析單屬性和WRWR-Ranking方法的排序結(jié)果.如圖4所示，圖中圖釘表示一個(gè)移動(dòng)簇的中心.觀察發(fā)現(xiàn)單屬性排序排在前面的移動(dòng)簇發(fā)生的地點(diǎn)都集中在海洋劇場周圍.海洋劇場作為一個(gè)每天定時(shí)開放的表演場地，有固定的開放時(shí)間和表演時(shí)間，且表演持續(xù)時(shí)間較長，因此這樣的地方較容易發(fā)生聚合事件.對(duì)于以上用戶已知的容易發(fā)生聚合事件的地點(diǎn)，用戶對(duì)該地點(diǎn)產(chǎn)生的移動(dòng)簇的興趣度較低.而WRWR-Ranking方法的排序結(jié)果，不僅能夠發(fā)現(xiàn)人們經(jīng)驗(yàn)常識(shí)里容易發(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é)果

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

4.4.3 評(píng)價(jià)指標(biāo)分析

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

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

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

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

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

5 結(jié)束語

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