支持語義信息挖掘的熱點路徑探測

滕巧爽，秘金鐘，孫尚宇

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

?

支持語義信息挖掘的熱點路徑探測

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

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

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

熱點路徑；軌跡流；軌跡密度；軌跡語義相似度；社會角色

0 引言

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

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

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

1 理論基礎(chǔ)

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

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

2 支持語義信息挖掘的熱點路徑探測

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

軌跡數(shù)據(jù)中包含豐富的時空和語義信息(如經(jīng)過的區(qū)域類型信息)，有助于從移動對象的活動規(guī)律中發(fā)現(xiàn)隱含的社會角色信息，如從軌跡中獲知移動對象早上6:00—7:00出現(xiàn)在政府機關(guān)辦公室，則其社會角色傾向于是清潔人員，而早上8:00—12:00出現(xiàn)在政府機關(guān)辦公室的移動對象則更可能是公務(wù)人員。挖掘軌跡的語義相似性可以發(fā)現(xiàn)軌跡間在空間、時間和語義維度上的鄰近程度[8],即2條軌跡在某時間段內(nèi)經(jīng)過同種類型區(qū)域的概率大小，概率越大，表明其相應(yīng)的社會角色越接近，便于軌跡依照其隱含的社會角色信息進行聚類[9-11]。為探測不同社會角色對應(yīng)的熱點路徑，本文在獲取軌跡數(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)獲取與軌跡點直線距離最短的地理標簽，借鑒文獻[12]的方法，即使用語義代替詞并通過考慮關(guān)鍵候選詞的語義信息來提高關(guān)鍵詞提取性能的方法，來提取所得地理標簽的關(guān)鍵詞，并按照圖3所示的分級圖對其進行分類，最終得到軌跡點所屬的區(qū)域類型，將其作為軌跡點的空間語義信息。

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

面對海量軌跡數(shù)據(jù)，本文采用建立軌跡語義空間模型的方法進行數(shù)據(jù)的存儲和分析，即統(tǒng)計某時間段內(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個10×n的軌跡語義特征矩陣X為

(1)

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

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

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

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

X=UΣVT。

(2)

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

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

(3)

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

(4)

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

(5)

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

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

2.2.2 熱點路徑檢測算法

(6)

(7)

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

(8)

探測不同社會角色對應(yīng)的熱點路徑時，可采用算法為：

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

(9)

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

F=wqq+wkk+wmm。

(10)

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

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

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

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

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

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

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

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

3 實驗與結(jié)果分析

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

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

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

4 結(jié)束語

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

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

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

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

[4] 馬林兵,李鵬.基于子空間聚類算法的時空軌跡聚類[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用戶移動軌跡聚類挖掘方法[J].計算機應(yīng)用研究,2013,30(8):2410-2414.

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

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

[10]袁書寒,陳維斌,傅順開.位置服務(wù)社交網(wǎng)絡(luò)用戶行為相似性分析[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].計算機科學(xué),2008,35(6):148-151.

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

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

[15]李清泉,黃練.基于GPS軌跡數(shù)據(jù)的地圖匹配算法[J].測繪學(xué)報,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計劃項目(2015AA124001)；中國測繪科學(xué)研究院基本科研業(yè)務(wù)費支持項目(7771604)；國家重點研發(fā)計劃項目(2016YFB0502105)。

滕巧爽(1990—)，女，遼寧沈陽人，博士研究生，研究方向為位置服務(wù)、數(shù)據(jù)挖掘。

滕巧爽，秘金鐘，孫尚宇.支持語義信息挖掘的熱點路徑探測[J].導(dǎo)航定位學(xué)報,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