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

滕巧爽，秘金鐘，孫尚宇

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

?

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

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

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

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

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

0 引言

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

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

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

1 理論基礎

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

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

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

2.1 軌跡數據語義相似性度量

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

2.1.1 軌跡數據語義信息獲取

本文所指的軌跡語義信息是指其經過的區域類型信息，可以采用如下方法獲取：通過調用百度應用程序編程接口(application programming interface，API)獲取與軌跡點直線距離最短的地理標簽，借鑒文獻[12]的方法，即使用語義代替詞并通過考慮關鍵候選詞的語義信息來提高關鍵詞提取性能的方法，來提取所得地理標簽的關鍵詞，并按照圖3所示的分級圖對其進行分類，最終得到軌跡點所屬的區域類型，將其作為軌跡點的空間語義信息。

2.1.2 軌跡數據語義空間建模

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

(1)

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

2.1.3 軌跡數據語義相似度計算

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

根據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條件下的最小二乘意義上的最優近似，可反映原始矩陣的絕大部分信息，即

(3)

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

(4)

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

(5)

2.2 熱點路徑探測2.2.1 軌跡數據劃分

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

2.2.2 熱點路徑檢測算法

(6)

(7)

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

(8)

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

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

(9)

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

F=wqq+wkk+wmm。

(10)

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

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

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

5)重復步驟1)～4)，直至路網數據集為空，獲得若干熱點路段集。

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

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

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

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

3 實驗與結果分析

本文使用微軟亞洲研究院收集的部分GPS軌跡數據作為實驗數據集，該數據集包含13:00—17:00間經過北京三環內區域的60條GPS軌跡數據，共計240 281個軌跡點，其覆蓋的路網包含61 442個路段。

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

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

4 結束語

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

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

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

[3] 曹政才,韓丁富,王永吉.面向城市交通網絡的一種新型動態路徑尋優方法[J].電子學報,2012,40(10):2062-2067.

[4] 馬林兵,李鵬.基于子空間聚類算法的時空軌跡聚類[J].地理與地理信息科學,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] 鄒永貴,萬建斌,夏英.基于路網的LBSN用戶移動軌跡聚類挖掘方法[J].計算機應用研究,2013,30(8):2410-2414.

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

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

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

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

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

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

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

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

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

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