滕巧爽，秘金鐘，孫尚宇

(1.遼寧工程技術(shù)大學(xué)，遼寧 阜新 123000； 2.中國測繪科學(xué)研究院，北京 100830)

?

支持語義信息挖掘的熱點(diǎn)路徑探測

滕巧爽1，秘金鐘2，孫尚宇1

(1.遼寧工程技術(shù)大學(xué)，遼寧 阜新 123000； 2.中國測繪科學(xué)研究院，北京 100830)

針對(duì)現(xiàn)有熱點(diǎn)路徑探測算法存在缺乏對(duì)軌跡語義信息進(jìn)行分析的問題，提出一種支持語義信息挖掘的熱點(diǎn)路徑探測算法：首先研究軌跡數(shù)據(jù)語義空間的建模方法，并據(jù)此構(gòu)建低維語義子空間來計(jì)算軌跡數(shù)據(jù)語義相似度，描述軌跡所屬移動(dòng)對(duì)象的社會(huì)角色的相似性，最后結(jié)合基于軌跡流與軌跡密度的傳統(tǒng)熱點(diǎn)路徑探測算法實(shí)現(xiàn)對(duì)不同社會(huì)角色對(duì)應(yīng)的熱點(diǎn)路徑的發(fā)現(xiàn)。結(jié)果表明，該算法能夠較好利用軌跡數(shù)據(jù)的時(shí)空和語義信息，有效識(shí)別出不同社會(huì)角色對(duì)應(yīng)的熱點(diǎn)路徑的聚類特征，為個(gè)性化的位置服務(wù)研究提供參考。

熱點(diǎn)路徑；軌跡流；軌跡密度；軌跡語義相似度；社會(huì)角色

0 引言

隨著移動(dòng)定位、無線通信等技術(shù)的不斷發(fā)展和普及，面向不同應(yīng)用領(lǐng)域的智能終端時(shí)刻都會(huì)產(chǎn)生大量的軌跡數(shù)據(jù)。這些數(shù)據(jù)中包含著豐富的信息，能夠用于發(fā)現(xiàn)交通狀況、移動(dòng)對(duì)象的出行規(guī)律等。因此，近年來與之相關(guān)的數(shù)據(jù)挖掘研究受到越來越多的關(guān)注，熱點(diǎn)路徑探測就是其中之一。熱點(diǎn)路徑是指多個(gè)移動(dòng)對(duì)象頻繁經(jīng)過的路徑[1]，反映了移動(dòng)對(duì)象的活動(dòng)規(guī)律及對(duì)某地理區(qū)域的關(guān)注程度[2]。從軌跡數(shù)據(jù)中發(fā)掘出熱點(diǎn)路徑，可為城市規(guī)劃、交通管理等領(lǐng)域提供決策支持[3-5]。

常用的熱點(diǎn)路徑探測方法主要包括以下幾種：軌跡聚類、移動(dòng)對(duì)象聚類、流量密度與連通性分析等。其中：軌跡聚類是依據(jù)相似度對(duì)軌跡進(jìn)行聚類分析，進(jìn)而發(fā)現(xiàn)熱點(diǎn)路徑；移動(dòng)對(duì)象聚類則是分析移動(dòng)對(duì)象的分布模式，將聚類中的軌跡認(rèn)定為熱點(diǎn)路徑；而流量密度與連通性分析通過計(jì)算相鄰路徑的密度可達(dá)性來確定熱點(diǎn)路徑。這些方法主要是對(duì)原始軌跡數(shù)據(jù)的數(shù)值特性、空間特性和時(shí)間特性進(jìn)行分析處理，而忽略了其語義特征，難以在探測熱點(diǎn)路徑的同時(shí)發(fā)掘其潛在語義信息。挖掘軌跡的時(shí)空和語義信息，可以發(fā)現(xiàn)其所屬移動(dòng)對(duì)象的社會(huì)角色特性，結(jié)合熱點(diǎn)路徑的探測算法，即可得到不同社會(huì)角色對(duì)應(yīng)的熱點(diǎn)路徑，進(jìn)而為不同移動(dòng)對(duì)象提供針對(duì)性的服務(wù)。

本文提出一種支持語義信息挖掘的熱點(diǎn)路徑探測算法，首先研究軌跡數(shù)據(jù)語義相似性的計(jì)算方法，進(jìn)而借鑒流量密度與連通性分析的方法實(shí)現(xiàn)對(duì)不同社會(huì)角色對(duì)應(yīng)的熱點(diǎn)路徑的空間分布探測。

1 理論基礎(chǔ)

定義2 軌跡[7]：1條軌跡TR={trid,p1,p2,…,pn}為1個(gè)按時(shí)間排列的點(diǎn)序列，其中trid表示該軌跡的唯一標(biāo)識(shí)符，pi=(xi,yi,ti)分別表示pi點(diǎn)的地理位置及采樣時(shí)間。

定義3 軌跡段[6]：1個(gè)軌跡段SubTR={trid,sid,pkpk+m}表示1條軌跡中落于相同路段上的連續(xù)軌跡點(diǎn)的集合，即pi.trid=pj.trid，pi.sid=pj.sid(?i,j:k≤i,j≤k+m)。如圖1所示，1條軌跡依照路段劃分為3個(gè)軌跡段SubTR1、SubTR2、SubTR3。

2 支持語義信息挖掘的熱點(diǎn)路徑探測

2.1 軌跡數(shù)據(jù)語義相似性度量

軌跡數(shù)據(jù)中包含豐富的時(shí)空和語義信息(如經(jīng)過的區(qū)域類型信息)，有助于從移動(dòng)對(duì)象的活動(dòng)規(guī)律中發(fā)現(xiàn)隱含的社會(huì)角色信息，如從軌跡中獲知移動(dòng)對(duì)象早上6:00—7:00出現(xiàn)在政府機(jī)關(guān)辦公室，則其社會(huì)角色傾向于是清潔人員，而早上8:00—12:00出現(xiàn)在政府機(jī)關(guān)辦公室的移動(dòng)對(duì)象則更可能是公務(wù)人員。挖掘軌跡的語義相似性可以發(fā)現(xiàn)軌跡間在空間、時(shí)間和語義維度上的鄰近程度[8],即2條軌跡在某時(shí)間段內(nèi)經(jīng)過同種類型區(qū)域的概率大小，概率越大，表明其相應(yīng)的社會(huì)角色越接近，便于軌跡依照其隱含的社會(huì)角色信息進(jìn)行聚類[9-11]。為探測不同社會(huì)角色對(duì)應(yīng)的熱點(diǎn)路徑，本文在獲取軌跡數(shù)據(jù)的語義信息后，首先采用奇異值分解(singular value decomposition，SVD)構(gòu)建軌跡數(shù)據(jù)的語義空間，然后通過軌跡數(shù)據(jù)的潛在語義信息的歐式距離度量其相似性。

2.1.1 軌跡數(shù)據(jù)語義信息獲取

本文所指的軌跡語義信息是指其經(jīng)過的區(qū)域類型信息，可以采用如下方法獲?。和ㄟ^調(diào)用百度應(yīng)用程序編程接口(application programming interface，API)獲取與軌跡點(diǎn)直線距離最短的地理標(biāo)簽，借鑒文獻(xiàn)[12]的方法，即使用語義代替詞并通過考慮關(guān)鍵候選詞的語義信息來提高關(guān)鍵詞提取性能的方法，來提取所得地理標(biāo)簽的關(guān)鍵詞，并按照?qǐng)D3所示的分級(jí)圖對(duì)其進(jìn)行分類，最終得到軌跡點(diǎn)所屬的區(qū)域類型，將其作為軌跡點(diǎn)的空間語義信息。

2.1.2 軌跡數(shù)據(jù)語義空間建模

面對(duì)海量軌跡數(shù)據(jù)，本文采用建立軌跡語義空間模型的方法進(jìn)行數(shù)據(jù)的存儲(chǔ)和分析，即統(tǒng)計(jì)某時(shí)間段內(nèi)每條軌跡經(jīng)過的區(qū)域類型及相應(yīng)的次數(shù)，并將其按照一定順序排列，來構(gòu)建軌跡語義特征矩陣。假設(shè)輸入n輛車的軌跡，每輛車的軌跡gj(1≤j≤n)占矩陣1列，每種區(qū)域類型vi(1≤i≤10)占矩陣1行，構(gòu)成1個(gè)10×n的軌跡語義特征矩陣X為

(1)

式中：矩陣元素xi,j(1≤i≤10,1≤j≤n)表示軌跡j在某時(shí)間段內(nèi)經(jīng)過區(qū)域類型i的次數(shù)。由于交通堵塞等原因，可能出現(xiàn)連續(xù)多個(gè)軌跡點(diǎn)的地理標(biāo)簽相同，顯然不能認(rèn)為是多次經(jīng)過，在統(tǒng)計(jì)時(shí)應(yīng)只計(jì)數(shù)1次。該方法將非結(jié)構(gòu)化的軌跡數(shù)據(jù)轉(zhuǎn)化為結(jié)構(gòu)化的數(shù)據(jù)矩陣進(jìn)行存儲(chǔ)，結(jié)合潛在語義分析，有望發(fā)現(xiàn)軌跡數(shù)據(jù)的語義相似度，為挖掘軌跡數(shù)據(jù)的社會(huì)角色特征提供支持。

2.1.3 軌跡數(shù)據(jù)語義相似度計(jì)算

為滿足大規(guī)模軌跡數(shù)據(jù)的處理需求，本文首先采用SVD去除軌跡語義特征矩陣X中的噪聲和冗余信息，生成低維潛在語義空間來描述元素間的語義結(jié)構(gòu)，在此基礎(chǔ)上選取歐氏距離計(jì)算兩兩軌跡間的相似程度并利用計(jì)算結(jié)果構(gòu)建軌跡相似度矩陣。上述方法可提高后續(xù)計(jì)算相連路段間的軌跡語義相似度的準(zhǔn)確性和運(yùn)算效率，降低探測不同社會(huì)角色對(duì)應(yīng)的熱點(diǎn)路徑的搜索時(shí)間。

根據(jù)SVD原理[13-14]，首先將軌跡語義特征矩陣X分解成3個(gè)矩陣U、Σ、VT，即

X=UΣVT。

(2)

式中：對(duì)角矩陣Σ=diag (σ1,σ2,σ3,…,σr)(r=rank (X))中包含了矩陣X的奇異值，并按照從大到小的順序排列；正交矩陣U=(u1,u2,u3,…,ur)和V=(v1,v2,v3,…,vr)的列向量分別為XXT和XTX的特征向量。

然后提取U與V中前k個(gè)列向量和Σ中前k個(gè)最大的奇異值，得到式(3)所示的降維矩陣Xk，其為原始矩陣X在秩為k條件下的最小二乘意義上的最優(yōu)近似，可反映原始矩陣的絕大部分信息，即

(3)

式中維數(shù)k的選取與奇異值的大小相關(guān)。若奇異值(σ1,σ2,…,σk)的平方和累積達(dá)到所有奇異值平方和的90 %，則認(rèn)為這個(gè)k值是合適的。

(4)

式中A [i]、B [i](i=1,2,…,k)分別表示軌跡A、B的潛在語義序列。整理所有計(jì)算結(jié)果最終可生成如下所示的對(duì)稱的軌跡相似度矩陣為

(5)

2.2 熱點(diǎn)路徑探測2.2.1 軌跡數(shù)據(jù)劃分

首先采用文獻(xiàn)[15]的算法在綜合考慮軌跡曲線與路徑曲線的相似性、路段幾何拓?fù)浜瓦B通性的基礎(chǔ)上進(jìn)行軌跡數(shù)據(jù)的地圖匹配，之后采用(trid,sid,x,y,t)的形式存儲(chǔ)軌跡點(diǎn)信息，并根據(jù)定義3將軌跡劃分成若干軌跡段。例如針對(duì)軌跡TRk={tridk,p1,p2,…,pn}，需從p1到pn依次檢查每2個(gè)連續(xù)軌跡點(diǎn)的sid，若pi.sid≠pi+1sid，則可使用2個(gè)軌跡點(diǎn)pi、pi+1所在路段的連接點(diǎn)對(duì)軌跡進(jìn)行劃分，重復(fù)該過程至每個(gè)軌跡段中軌跡點(diǎn)的sid均相同。

2.2.2 熱點(diǎn)路徑檢測算法

(6)

(7)

依據(jù)式(5)的軌跡相似度矩陣，即可計(jì)算2個(gè)相連路段Si、Sj間的軌跡語義相似度m，m的值越大，表示經(jīng)過2個(gè)路段的軌跡所對(duì)應(yīng)的社會(huì)角色越接近，計(jì)算方法為

(8)

探測不同社會(huì)角色對(duì)應(yīng)的熱點(diǎn)路徑時(shí)，可采用算法為：

1)衡量所有路段的“熱度”和經(jīng)過該路段的軌跡間的語義相似性，計(jì)算方法如式(9)所示，選擇獲得最大值的路段作為初始路段，即

(9)

2)評(píng)價(jià)初始路段與其指定一側(cè)鄰接路段間的軌跡語義相似度、連通性及鄰接路段的使用頻率，計(jì)算方法如式(10)所示，選取獲得最大值的路段作為初始路段的連接路段，即

F=wqq+wkk+wmm。

(10)

式中：權(quán)重wq、wk、wm為1/3；q、k、m分別表示軌跡流、軌跡密度和軌跡語義相似性。

3)重復(fù)使用式(10)，依次獲得上一次式(10)運(yùn)算結(jié)果的連接路段，直至式(10)計(jì)算結(jié)果為空，即沒有連接路段，至此獲得初始路段一側(cè)的連接路段集。

4)重復(fù)步驟2)和3)，獲得初始路段另一側(cè)的連接路段集，將初始路段和2側(cè)的連接路段集存儲(chǔ)于1個(gè)數(shù)據(jù)集中，并將其從原始路網(wǎng)數(shù)據(jù)集中剔除，不再參加其后的運(yùn)算。設(shè)置閾值C，當(dāng)經(jīng)過所得路段集的軌跡數(shù)目小于C時(shí)，則將其刪除。

5)重復(fù)步驟1)～4)，直至路網(wǎng)數(shù)據(jù)集為空，獲得若干熱點(diǎn)路段集。

采用以上算法獲取熱點(diǎn)路徑時(shí)，可能會(huì)出現(xiàn)如下問題：利用式(9)和式(10)選取初始路段及連接路段時(shí)，有若干路段對(duì)應(yīng)的計(jì)算結(jié)果相同且為最大值。針對(duì)初始路段的選擇問題，本文采用隨機(jī)選取的原則，即可任意選擇1個(gè)計(jì)算結(jié)果為最大值的路段作為初始路段。而面對(duì)連接路段的選擇問題，以圖4選取路段S的連接路段為例，本文遵守如下4條原則：

2)分別計(jì)算待選連接路段S1、S4另一側(cè)鄰接路段上的軌跡段數(shù)目，比較max(TrC(S2)、TrC(S3))與max(TrC(S5),TrC(S6))，選取最大值對(duì)應(yīng)的唯一待選連接路段，否則參照原則3)。

3)計(jì)算路段S與待選路段S1、S4間的軌跡語義相似度m (S,S1)和m (S,S4)，選取獲得最大值的唯一的連接路段，否則參照原則4)。

4)若前3條原則均無法確定，則可任意選擇1個(gè)待選連接路段作為最終結(jié)果。

3 實(shí)驗(yàn)與結(jié)果分析

本文使用微軟亞洲研究院收集的部分GPS軌跡數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集，該數(shù)據(jù)集包含13:00—17:00間經(jīng)過北京三環(huán)內(nèi)區(qū)域的60條GPS軌跡數(shù)據(jù)，共計(jì)240 281個(gè)軌跡點(diǎn)，其覆蓋的路網(wǎng)包含61 442個(gè)路段。

基于以上數(shù)據(jù)集，經(jīng)過軌跡數(shù)據(jù)的地圖匹配與劃分之后，首先采用上文所述的軌跡數(shù)據(jù)語義信息獲取方法得到軌跡點(diǎn)所屬的區(qū)域類型信息，即可根據(jù)式(1)所示方法構(gòu)建10×60的軌跡語義特征矩陣；其后對(duì)該矩陣運(yùn)用SVD分解成3個(gè)矩陣，并依據(jù)所得奇異值計(jì)算確定維數(shù)k為2，進(jìn)而生成降維語義空間；以此為基礎(chǔ)采用式(4)所示方法便可得到兩兩軌跡間的語義相似度，整理計(jì)算結(jié)果即可得到形如式(5)所示的60×60的軌跡相似度矩陣；在此基礎(chǔ)上采用上文所述的熱點(diǎn)路徑檢測算法，綜合考慮軌跡流、軌跡密度和軌跡語義相似性3種因子，最終探測到如圖5(a)所示的9條熱點(diǎn)路徑，每條熱點(diǎn)路徑均代表著一類社會(huì)角色在一定時(shí)空范圍內(nèi)經(jīng)常行駛的路線。其中實(shí)驗(yàn)閾值C設(shè)置為5，通過計(jì)算9條熱點(diǎn)路徑上的軌跡數(shù)目的平均值得到。

針對(duì)該數(shù)據(jù)集，在不考慮軌跡語義特征的情況下，采用流量密度與連通性分析最終獲得如圖5(b)所示的10條熱點(diǎn)路徑。通過對(duì)比圖5(a)和圖5(b)可知，2種方法探測到的熱點(diǎn)路徑大致相同，圖5(a)可認(rèn)為是基于軌跡的語義特征對(duì)圖5(b)進(jìn)行分析重組的結(jié)果，驗(yàn)證了本文算法的合理性。

4 結(jié)束語

本文在綜合考慮軌跡流、軌跡密度和軌跡語義相似性3種因子的基礎(chǔ)上，提出了一種支持語義信息挖掘的熱點(diǎn)路徑探測算法，實(shí)現(xiàn)了對(duì)不同社會(huì)角色對(duì)應(yīng)的熱點(diǎn)路徑的發(fā)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，該方法有效利用了軌跡數(shù)據(jù)的時(shí)空和語義特性，充分反映移動(dòng)對(duì)象的社會(huì)角色和運(yùn)動(dòng)模式。但是本實(shí)驗(yàn)的結(jié)果僅給出了1個(gè)時(shí)間段內(nèi)的若干條熱點(diǎn)路徑，并未對(duì)其他時(shí)間段內(nèi)的熱點(diǎn)路徑進(jìn)行分析，并且對(duì)熱點(diǎn)路徑的社會(huì)角色屬性挖掘得不夠深入，后續(xù)將展開進(jìn)一步研究。

[1] 鍛煉,李峙,胡寶清.時(shí)空約束下的熱點(diǎn)路徑空間分布檢測算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2014,35(3):861-866.

[2] 吳俊偉,朱云龍,庫濤,等.基于網(wǎng)格聚類的熱點(diǎn)路徑探測[J].吉林大學(xué)學(xué)報(bào)(工學(xué)版),2015,45(1):274-282.

[3] 曹政才,韓丁富,王永吉.面向城市交通網(wǎng)絡(luò)的一種新型動(dòng)態(tài)路徑尋優(yōu)方法[J].電子學(xué)報(bào),2012,40(10):2062-2067.

[4] 馬林兵,李鵬.基于子空間聚類算法的時(shí)空軌跡聚類[J].地理與地理信息科學(xué),2014,30(4):7-12.

[5]HUNGCC,PENGWC,LEEWC.Clusteringandaggregatingcluesoftrajectoriesforminingtrajectorypatternsandroutes[J].TheVLDBJournal, 2011, 24(2):169-192.

[6]HANB,LIUL,OMIECINSKIE.Road-networkawaretrajectoryclustering:integratinglocality,flowanddensity[J].IEEETransactionsonMobileComputing, 2015, 14(2): 416-429.

[7] 鄒永貴,萬建斌,夏英.基于路網(wǎng)的LBSN用戶移動(dòng)軌跡聚類挖掘方法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(8):2410-2414.

[8] 廖律超,蔣新華,鄒復(fù)民,等.一種支持軌跡大數(shù)據(jù)潛在語義相關(guān)性挖掘的譜聚類方法[J].電子學(xué)報(bào),2015,43(5):956-964.

[9] 馬宇馳,楊寧,謝琳,等.基于軌跡時(shí)空關(guān)聯(lián)語義和時(shí)態(tài)嫡的移動(dòng)對(duì)象社會(huì)角色發(fā)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展,2012,49(10):2153-2160.

[10]袁書寒,陳維斌,傅順開.位置服務(wù)社交網(wǎng)絡(luò)用戶行為相似性分析[J].計(jì)算機(jī)應(yīng)用,2012,32(2):322-325.

[11]LIJ,QINQ,XIEC,etal.Integrateduseofspatialandsemanticrelationshipsforextractingroadnetworksfromfloatingcardata[J].InternationalJournalofAppliedEarthObservationandGeo-information, 2012, 19(5): 238-247.

[12]方俊,郭雷,王曉東.基于語義的關(guān)鍵詞提取算法[J].計(jì)算機(jī)科學(xué),2008,35(6):148-151.

[13]劉云峰,齊歡,代建民.基于潛在語義空間維度特性的多層文檔聚類[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2005,45(增刊1):1783-1786.

[14]LANDAUERTK,DUMAISST.Latentsemanticanalysis[J].AnnualReviewofInformationScience&Technology, 2008, 3(11): 683-692.

[15]李清泉,黃練.基于GPS軌跡數(shù)據(jù)的地圖匹配算法[J].測繪學(xué)報(bào),2010,39(2):207-212.

Hot routes detection based on semantic information mining

TENGQiaoshuang1,BEIJinzhong2,SUNShangyu

(1.Liaoning Technical University, Fuxin, Laoning 123000, China;2.Chinese Academy of Surveying and Mapping, Beijing 100830, China)

Aiming at the problem that it is lack of the analysis on semantic information of trajectories in the existing algorithms of hot routes detection, the paper proposed a detection method supporting semantic information mining: firstly, the modeling method of semantic space of trajectory data was studied; secondly, the low-dimensional semantic subspace was constructed to compute the semantic similarity which describes the comparability of the social roles of the moving objects; finally, combined with the traditional hot routes detection algorithm based on trajectory flow and density, the discovery of hot routes corresponding to different social roles was realized.Result showed that the proposed method could make use of the spatial-temporal and semantics information of the trajectory data, and effectively identify the clustering characteristics of the hot routes corresponding to different social roles, which would provide a reference for related study on personalized location-based services.

hot routes; trajectory flow; trajectory density; trajectory semantic similarity; social roles

2016-08-16

國家863計(jì)劃項(xiàng)目(2015AA124001)；中國測繪科學(xué)研究院基本科研業(yè)務(wù)費(fèi)支持項(xiàng)目(7771604)；國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB0502105)。

滕巧爽(1990—)，女，遼寧沈陽人，博士研究生，研究方向?yàn)槲恢梅?wù)、數(shù)據(jù)挖掘。

滕巧爽，秘金鐘，孫尚宇.支持語義信息挖掘的熱點(diǎn)路徑探測[J].導(dǎo)航定位學(xué)報(bào),2017,5(2):27-31,37.(TENG Qiaoshuang,BEI Jinzhong,SUN Shangyu.Hot routes detection based on semantic information mining[J].Journal of Navigation and Positioning,2017,5(2):27-31,37.)

10.16547/j.cnki.10-1096.20170205.

P228

A

2095-4999(2017)02-0027-06