王雅楠，李博涵,2,3+，張 潮，鄭 偉，李俊潔，秦小麟,2

1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016

2.江蘇省軟件新技術(shù)與產(chǎn)業(yè)協(xié)同創(chuàng)新中心，南京 210016

3.江蘇易圖地理信息科技股份有限公司，江蘇 揚(yáng)州 225000

4.成都航空職業(yè)技術(shù)學(xué)院，成都 610100

1 引言

隨著室內(nèi)定位技術(shù)[1]的發(fā)展，室內(nèi)移動(dòng)對(duì)象數(shù)據(jù)管理[2]逐漸成為熱門研究領(lǐng)域，尤其在緊急救援、安全預(yù)防以及定位導(dǎo)航等領(lǐng)域具有廣泛的應(yīng)用前景。移動(dòng)對(duì)象軌跡分析作為位置服務(wù)的重要基礎(chǔ)，通過(guò)對(duì)用戶位置數(shù)據(jù)和其移動(dòng)軌跡數(shù)據(jù)進(jìn)行深層次的提取和分析研究，可以有效地挖掘出用戶的行為偏好及異常等重要信息，這對(duì)異常軌跡檢測(cè)、社交推薦[3]、智能交通等應(yīng)用都有著重要的作用。

移動(dòng)軌跡相似性度量是移動(dòng)軌跡分析領(lǐng)域里的一個(gè)重要部分，指的是找到一種合適的軌跡距離計(jì)算方法來(lái)度量?jī)蓷l移動(dòng)軌跡之間的相似程度，包括軌跡形狀、空間距離、軌跡時(shí)間等。移動(dòng)軌跡相似性度量在基于位置服務(wù)中有許多重要的實(shí)際應(yīng)用，例如通過(guò)計(jì)算用戶移動(dòng)軌跡的相似性，聚集相似軌跡[4]，找到相似用戶，從而在社交網(wǎng)絡(luò)上進(jìn)行朋友推薦等。

目前針對(duì)移動(dòng)對(duì)象軌跡相似性度量的研究多基于室外空間，對(duì)室內(nèi)空間的研究較少。由于室內(nèi)空間和室外空間的結(jié)構(gòu)不同，移動(dòng)對(duì)象定位方式不同，移動(dòng)軌跡維度不同等因素，已有基于室外空間移動(dòng)軌跡查詢研究不能直接應(yīng)用于室內(nèi)空間。然而，有數(shù)據(jù)統(tǒng)計(jì)表明人們活動(dòng)的區(qū)域和時(shí)間約80%處于室內(nèi)環(huán)境，如：辦公樓、商場(chǎng)、地鐵站、機(jī)場(chǎng)等。在室內(nèi)環(huán)境下移動(dòng)對(duì)象軌跡相似性查詢有眾多的應(yīng)用場(chǎng)景。例如商家可以通過(guò)對(duì)大量用戶移動(dòng)軌跡相似性分析挖掘出用戶行為偏好，為商業(yè)決策及資源分配提供依據(jù)；在室內(nèi)公共區(qū)域，工作人員可以通過(guò)軌跡相似性度量來(lái)找出異常軌跡，從而預(yù)防車站、機(jī)場(chǎng)等人流密集地區(qū)犯罪事件的發(fā)生；室內(nèi)設(shè)計(jì)工作者可以通過(guò)對(duì)大量軌跡進(jìn)行相似性分析得到用戶行為模式等信息，從而更好地進(jìn)行結(jié)構(gòu)設(shè)計(jì)等。對(duì)于軌跡相似性度量的研究中，多以空間距離為主要研究對(duì)象，時(shí)間和位置語(yǔ)義的相似性僅僅作為考慮因素甚至直接忽略。然而，在室內(nèi)環(huán)境下，時(shí)間和位置語(yǔ)義卻占有重要角色。本文結(jié)合室內(nèi)移動(dòng)軌跡的特點(diǎn)，提出一種新的適用于室內(nèi)空間的移動(dòng)軌跡相似性度量方法IMTSM（indoor-space moving-object trajectory similarity measurement），將空間、時(shí)間和位置語(yǔ)義這三種主要影響因素分別度量，從而更好地適應(yīng)不同需求。

本文的主要貢獻(xiàn)如下：

（1）結(jié)合室內(nèi)空間結(jié)構(gòu)，定義一種新的三維軌跡特征點(diǎn)發(fā)現(xiàn)算法，在保證軌跡信息完整的前提下將冗雜的軌跡數(shù)據(jù)進(jìn)行重構(gòu)，有效降低了計(jì)算復(fù)雜度。

（2）將移動(dòng)對(duì)象軌跡時(shí)空距離計(jì)算由二維空間擴(kuò)展到三維空間，利用軌跡投影提出室內(nèi)軌跡空間距離算法，并根據(jù)室內(nèi)軌跡相對(duì)較短的特性，獨(dú)立計(jì)算軌跡時(shí)間距離，得到室內(nèi)軌跡時(shí)空相似度。

（3）設(shè)計(jì)室內(nèi)位置語(yǔ)義分析樹(shù)（LSR_Tree）結(jié)構(gòu)來(lái)描述位置之間的語(yǔ)義關(guān)系，通過(guò)自底向上查詢并改進(jìn)動(dòng)態(tài)時(shí)間規(guī)整算法，將文本的絕對(duì)性比較巧妙地轉(zhuǎn)換為語(yǔ)義關(guān)系度計(jì)算，并給出位置語(yǔ)義距離提取算法，有效減少了將軌跡位置語(yǔ)義序列作為文本序列比較的誤差，最后通過(guò)數(shù)據(jù)標(biāo)準(zhǔn)化處理將不同數(shù)量級(jí)的差異數(shù)據(jù)進(jìn)行歸一，得到室內(nèi)移動(dòng)對(duì)象軌跡綜合相似度。

2 相關(guān)工作

目前，對(duì)于移動(dòng)對(duì)象軌跡相似度的計(jì)算多集中于室外空間或路網(wǎng)空間[5-6]中。室外空間中的經(jīng)典距離度量方法歐氏距離[7]最先被應(yīng)用于計(jì)算移動(dòng)軌跡序列的相似度。先通過(guò)對(duì)坐標(biāo)點(diǎn)計(jì)算得到歐氏距離，再加權(quán)平均得到整條軌跡的相似度，該方法思想易于理解，計(jì)算簡(jiǎn)單，但對(duì)于軌跡長(zhǎng)度有嚴(yán)格要求，實(shí)際應(yīng)用范圍有限。DTW（dynamic time warping distance）[8]動(dòng)態(tài)時(shí)間規(guī)整方法解決了位置點(diǎn)與采集時(shí)刻不對(duì)應(yīng)的問(wèn)題，通過(guò)歷史坐標(biāo)點(diǎn)值來(lái)實(shí)現(xiàn)兩條軌跡的局部時(shí)間轉(zhuǎn)換，可以計(jì)算長(zhǎng)度不同的軌跡，但這種方法必須要求軌跡距離計(jì)算能夠適應(yīng)時(shí)間維度的拉伸。Vlachos等人[9]所提出的基于最長(zhǎng)公共子序列LCSS（longest common subsequence）的度量方法，解決了對(duì)于軌跡長(zhǎng)度的限制，將軌跡分割成片段并判定不同段的相似程度，對(duì)軌跡噪點(diǎn)的影響有所改善。該方法經(jīng)驗(yàn)證表明其效果明顯優(yōu)于歐式距離以及經(jīng)典方法DTW。Lin等人[10]通過(guò)定義One Way Distance距離函數(shù)來(lái)度量移動(dòng)軌跡空間形狀的相似度。這些方法都只考慮了軌跡在空間及形狀的相似度，并未考慮時(shí)間因素對(duì)軌跡相似性的影響。

Pelekis等人提出了一種針對(duì)室外空間的時(shí)空相似性度量方法，并給出LIP（locality in-between polylines）[11]算法，將兩條軌跡交疊所圍成的多個(gè)小區(qū)域面積作為計(jì)算空間相似度的依據(jù)，同時(shí)將小區(qū)域最大時(shí)間與兩條軌跡的時(shí)間和的比值作為時(shí)間相似度的考量，在綜合考慮時(shí)間和空間的影響因素下得到最終相似度。Skoumas等人[12]將軌跡看成是多條線段的組合，在兩條軌跡相對(duì)應(yīng)的時(shí)間段內(nèi)，對(duì)空間中水平距離和垂直距離進(jìn)行計(jì)算，得到軌跡時(shí)空相似度。

除了利用時(shí)空距離和軌跡形狀的相似性來(lái)度量軌跡相似度的方法外，還有位置語(yǔ)義這一因素對(duì)移動(dòng)軌跡相似性度量有著重要影響。Ying等人[13]首先在軌跡相似度計(jì)算中加入了位置語(yǔ)義信息，分別將語(yǔ)義位置標(biāo)簽加入軌跡單元，再改進(jìn)LCSS方法計(jì)算兩條軌跡的位置語(yǔ)義相似度，但此方法僅僅將位置語(yǔ)義形式化，適合在特定場(chǎng)景下應(yīng)用。Wang等人[14]利用歐氏距離結(jié)合編輯距離的方法，克服了僅把位置當(dāng)作字符的缺陷，但此方法并不適用室內(nèi)空間。

室內(nèi)空間與室外空間的特征有顯著的不同，室內(nèi)軌跡為三維軌跡，以上用于室外空間的軌跡相似度量方法并不能直接應(yīng)用于室內(nèi)空間，因此出現(xiàn)了少量關(guān)于室內(nèi)軌跡相似性度量的研究工作。Kang等人[15]在2009年首先提出一種基于LCSS的方法用于室內(nèi)軌跡相似度的計(jì)算，將軌跡相似度用軌跡在同一位置的停留時(shí)間代替，該方法思想簡(jiǎn)單，但對(duì)于軌跡的計(jì)算相對(duì)粗略，且對(duì)于語(yǔ)義位置信息僅用字符代替，很難得到實(shí)際的應(yīng)用。Jin等人[16]設(shè)計(jì)了SIT（similarity indoor trajectory）算法，他們認(rèn)為相比于地理位置所表示的坐標(biāo)信息，位置的語(yǔ)義信息更有利用價(jià)值。SIT算法給出了室內(nèi)分層移動(dòng)模式的概念，并基于最長(zhǎng)公共子序列算法LCSS度量位置語(yǔ)義信息之間的相似度，從而獲得用戶對(duì)位置的偏好程度。但LCSS主要用于計(jì)算兩個(gè)字符串之間最大公共子序列，然而對(duì)于移動(dòng)對(duì)象軌跡的位置語(yǔ)義序列，不同語(yǔ)境可能產(chǎn)生不同語(yǔ)義，將位置語(yǔ)義序列作為字符串進(jìn)行絕對(duì)性比較會(huì)出現(xiàn)計(jì)算誤差。

3 基礎(chǔ)知識(shí)

3.1 問(wèn)題描述

室內(nèi)空間由于房間、走廊、樓梯等因素的限制，使得歐式距離、路網(wǎng)距離等不再適用，必須重新定義符合室內(nèi)空間約束的三維軌跡空間距離度量方法。而且，在室內(nèi)空間中，移動(dòng)軌跡的時(shí)間距離和位置語(yǔ)義距離對(duì)軌跡相似性度量有重要影響。如圖1所示，移動(dòng)軌跡T和R的空間形狀走向極為相似，但考慮到時(shí)間屬性，便不能再認(rèn)為是相似軌跡。

Fig.1 Moving trajectory time distance profile圖1 移動(dòng)軌跡時(shí)間距離圖

傳統(tǒng)的軌跡分析研究中多將語(yǔ)義信息符號(hào)化，但在室內(nèi)環(huán)境中，位置語(yǔ)義信息應(yīng)用需求較高，例如在大型機(jī)場(chǎng)中，人們通常的描述為“我在登機(jī)口”而不是“我在位置A”，因此空間形狀相似的軌跡在位置語(yǔ)義的角度可能出現(xiàn)很大的差異。有時(shí)用戶的查詢需要會(huì)有所側(cè)重，例如查詢某一時(shí)間段的相似軌跡，那么時(shí)間相似度就相對(duì)重要。本文將空間、時(shí)間、位置語(yǔ)義分別度量，用戶可以根據(jù)自己的需要對(duì)其中一個(gè)或多個(gè)方面著重度量，以更好地適應(yīng)不同需求。

3.2 形式化定義

室內(nèi)環(huán)境中，移動(dòng)對(duì)象的位置信息通常通過(guò)室內(nèi)部署的傳感器來(lái)獲取，因此可以使用傳感器序列標(biāo)號(hào)來(lái)表示室內(nèi)移動(dòng)對(duì)象軌跡。

定義1（室內(nèi)定位記錄）一個(gè)室內(nèi)移動(dòng)對(duì)象的位置記錄可以由一個(gè)四元組表示，表示為：

其中，objectID表示移動(dòng)對(duì)象，readerID表示傳感器標(biāo)號(hào)，label表示此處位置語(yǔ)義標(biāo)簽，ts表示移動(dòng)對(duì)象進(jìn)入傳感器范圍的時(shí)刻，te表示移動(dòng)對(duì)象離開(kāi)傳感器范圍的時(shí)刻。

定義2（室內(nèi)移動(dòng)對(duì)象軌跡）由室內(nèi)定位記錄序列構(gòu)成室內(nèi)移動(dòng)對(duì)象軌跡，表示為：

4 室內(nèi)移動(dòng)軌跡相似性度量

4.1 軌跡重構(gòu)

移動(dòng)軌跡數(shù)據(jù)是由一系列的離散的記錄點(diǎn)組成，采樣點(diǎn)個(gè)數(shù)越多，軌跡的完整性和精度越高，但是存儲(chǔ)和計(jì)算的代價(jià)也越高。提取軌跡特征點(diǎn)是移動(dòng)軌跡分析經(jīng)常采用的策略，即提取軌跡中具有典型特征或是軌跡變化幅度較大的特征點(diǎn)重新構(gòu)建軌跡。本文結(jié)合室內(nèi)空間的特點(diǎn)，定義一種新的算法TRS（trajectory restructure）提取軌跡特征點(diǎn)重構(gòu)軌跡，對(duì)冗雜的移動(dòng)軌跡進(jìn)行壓縮，保證了在軌跡信息完整的前提下減少軌跡的數(shù)據(jù)量和簡(jiǎn)化軌跡相似性計(jì)算的復(fù)雜度。

定義3（軌跡特征點(diǎn)）TR={p1,p2,…,pn}為一條室內(nèi)移動(dòng)對(duì)象軌跡，其軌跡特征點(diǎn)表示為：

其中，ω為角度偏移閾值，d為位置偏移距離閾值，對(duì)于軌跡TR中任意采樣點(diǎn)pi，記Dpi為pi的位置偏移距離，Dθpi為pi的角度偏移距離。若采樣點(diǎn)位置語(yǔ)義標(biāo)簽pi.label=“l(fā)ift”，或Dpi>d，或Dθpi>ω，則pi定義為一個(gè)特征點(diǎn)ci，軌跡的開(kāi)始點(diǎn)和結(jié)束點(diǎn)自動(dòng)歸為特征點(diǎn)。

如圖2所示，假設(shè)pc是一個(gè)特征點(diǎn)，pc+1是下一個(gè)特征點(diǎn)，則定義pcpc+1為標(biāo)記向量，并隨著特征點(diǎn)的增加而后移。假設(shè)pi到標(biāo)記向量pcpc+1的最小歐式距離為位置偏移距離Dpi，若向量pcpi和pipc+1夾角α以及向量pc+1pi和pc+1pc夾角β均為銳角或存在直角，則最小距離為pi到標(biāo)記向量pcpc+1的垂線段d1；若α和β中有鈍角存在，則最小距離為：

Fig.2 Sketch of trajectory characteristic points threshold圖2 軌跡特征點(diǎn)閾值示意圖

同時(shí)，軌跡的轉(zhuǎn)向角反映了軌跡的運(yùn)動(dòng)趨勢(shì)，pcpc+1為標(biāo)記向量，若pi為軌跡下一個(gè)采樣點(diǎn)，此處向量pcpc+1與向量pc+1pi的夾角為θ，則角度偏移距離Dθpi為：

算法1軌跡重構(gòu)算法TRS

輸入：室內(nèi)移動(dòng)軌跡T，角度偏移閾值ω，距離偏移閾值d。

輸出：由特征點(diǎn)集合組成的重構(gòu)軌跡R。

4.2 空間距離

目前，已有的對(duì)于軌跡空間距離的計(jì)算方法大多數(shù)基于歐式空間或者網(wǎng)格空間，對(duì)于室內(nèi)環(huán)境下的研究較少。LIP[11]算法在室外軌跡時(shí)空相似度方面取得很好的效果，本文針對(duì)室內(nèi)復(fù)雜三維空間，將其所提出的距離函數(shù)作了改進(jìn)，提出一種新的適用于室內(nèi)軌跡空間距離度量算法SIP（spatial locality inbetween polygon of indoor）。對(duì)于每一條移動(dòng)軌跡，根據(jù)特征點(diǎn)提取算法可以獲得以特征點(diǎn)表示的位置集合C={c1,c2,…,cs}。特征點(diǎn)序列中，每?jī)蓚€(gè)相鄰的特征點(diǎn)按到達(dá)時(shí)間的先后組成一條軌跡段L，由此該條軌跡便可以表示為多個(gè)3D線段組成的有向序列。如圖3所示：假設(shè)軌跡線段表示為T={L1,L2,…,Lm}，R={L1,L2,…,Ln}，軌跡T′為軌跡T在軌跡R所在二維平面的投影軌跡，記軌跡相交點(diǎn)為I={I1,I2,…,Iq}。

Fig.3 Trajectory space projection圖3 軌跡空間投影示意圖

定義4（高度距離）假設(shè)投影后軌跡T′與軌跡R相交點(diǎn)個(gè)數(shù)為k，當(dāng)k>1時(shí)，定義其高度距離hi(0≤i＜k)為投影后相鄰相交點(diǎn)之間軌跡所圍成的封閉多邊形內(nèi)投影高度平均值；當(dāng)k≤1時(shí)，定義高度距離hi(0≤i＜k)為整條軌跡投影高度平均值。

定義5（相交面積）假設(shè)投影后軌跡T′與軌跡R相交點(diǎn)個(gè)數(shù)為k，當(dāng)k>1時(shí)，定義軌跡相交面積Areai(0≤i＜k)為投影后相鄰相交點(diǎn)之間軌跡所圍成的封閉多邊形的面積；當(dāng)k≤1時(shí)，定義軌跡相交面積Areai(0≤i＜k)為軌跡T′與軌跡R的首尾端點(diǎn)所圍成封閉多邊形面積，即相交面積取為最大值。

定義6（權(quán)重系數(shù)）當(dāng)k>1時(shí)，定義lengthT和lengthR分別表示移動(dòng)軌跡T和R的軌跡長(zhǎng)度，即軌跡特征點(diǎn)個(gè)數(shù)。lengthT(Ii,Ii+1)和lengthR(Ii,Ii+1)分別表示封閉多邊形Areai(0≤i＜k)內(nèi)移動(dòng)軌跡T和R的軌跡長(zhǎng)度，則權(quán)重系數(shù)的計(jì)算公式為：

其中，0≤i＜k；當(dāng)k≤1時(shí)，軌跡投影后不相交或只有一個(gè)相交點(diǎn)，封閉多邊形不存在，ωi取為最大值1。

定義7（空間距離）定義移動(dòng)軌跡T和R的空間相似度Dspace為：

其中，0≤i＜k。

算法2空間相似距離算法SIP

輸入：室內(nèi)移動(dòng)軌跡T和R。

輸出：軌跡T和R的空間距離。

4.3 時(shí)間距離

文獻(xiàn)[11-12]中考慮到時(shí)間距離對(duì)軌跡相似度的影響，將其融入到空間距離計(jì)算之中，取得一定的成果，但這種方式更適用于軌跡長(zhǎng)度較長(zhǎng)的環(huán)境中。在室內(nèi)空間，軌跡相對(duì)較短，容易做到將整條軌跡的時(shí)間作為度量單元，若將空間和時(shí)間的度量分開(kāi)計(jì)算，能夠在一定程度上提高計(jì)算效率。

如圖4所示，假設(shè)軌跡T和R在軌跡開(kāi)始點(diǎn)和結(jié)束點(diǎn)的時(shí)間段內(nèi)無(wú)時(shí)間交集，則時(shí)間距離為第一段軌跡開(kāi)始點(diǎn)與第二段軌跡結(jié)束點(diǎn)差值的絕對(duì)值。否則，時(shí)間距離為第一段軌跡開(kāi)始點(diǎn)到第二段軌跡結(jié)束點(diǎn)時(shí)間差值減去兩條軌跡相交區(qū)域時(shí)間段，如式（8）所示：

Fig.4 Trajectory time distance圖4 軌跡時(shí)間距離

4.4 位置語(yǔ)義距離

由于移動(dòng)軌跡的位置語(yǔ)義序列所代表的含義是根據(jù)其所在場(chǎng)景定義的，傳統(tǒng)應(yīng)用字符串序列比較來(lái)衡量軌跡位置語(yǔ)義序列相似性的方法精確度較低。本文利用位置語(yǔ)義之間的相互關(guān)系來(lái)計(jì)算位置語(yǔ)義距離，其中葉子節(jié)點(diǎn)表示室內(nèi)空間中實(shí)際位置所對(duì)應(yīng)的語(yǔ)義屬性，即位置語(yǔ)義標(biāo)簽。如圖5所示的位置語(yǔ)義分析樹(shù)結(jié)構(gòu)LSR_Tree，非葉子節(jié)點(diǎn)表示下層節(jié)點(diǎn)所屬位置類別，其所在層次越高，所代表的位置范圍就越大，位置語(yǔ)義相似度就越小。反之，則相似度越大。在LSR_Tree結(jié)構(gòu)中，通過(guò)兩個(gè)軌跡特征點(diǎn)所訪問(wèn)的葉子節(jié)點(diǎn)，尋找到其最小公共父親節(jié)點(diǎn)，并定義公共父親節(jié)點(diǎn)所在層次高度與LSR_Tree高度之比為特征點(diǎn)之間的位置語(yǔ)義距離。根據(jù)語(yǔ)義位置分析樹(shù)，提出位置語(yǔ)義距離提取算法LSE（location semantic extract），并改進(jìn)DTW函數(shù)，使其適用于室內(nèi)軌跡位置語(yǔ)義的相似性度量。

假設(shè)由特征點(diǎn)表示的移動(dòng)軌跡T={T1,T2,…,Tm},R={R1,R2,…,Rn}，m和n分別為軌跡T和R的特征點(diǎn)個(gè)數(shù)，即軌跡長(zhǎng)度。這里改進(jìn)動(dòng)態(tài)時(shí)間規(guī)整算法DTW后得到位置語(yǔ)義距離函數(shù)：

Fig.5 Location semantic analysis LSR_Tree圖5 位置語(yǔ)義分析樹(shù)LSR_Tree

其中，Ti為軌跡T中某一時(shí)刻的特征點(diǎn)，Rj為軌跡R中某一時(shí)刻的特征點(diǎn)，0＜i＜m,0＜j＜n。特征點(diǎn)Ti與Rj之間的距離dist(Ti,Rj)為位置語(yǔ)義分析樹(shù)中最小公共父節(jié)點(diǎn)高度與樹(shù)高度的比值。

位置語(yǔ)義距離計(jì)算公式：

公式中前一部分引用動(dòng)態(tài)時(shí)間規(guī)整DTW的方法度量?jī)蓷l軌跡的位置語(yǔ)義距離，但此方法未考慮到軌跡長(zhǎng)度的差異，公式后一部分引入軌跡長(zhǎng)度比值，解決軌跡長(zhǎng)度不相等的情況。若兩條軌跡T和R是完全相同的，那么distTR(T,R)為零，公式計(jì)算結(jié)果為1，即軌跡完全相似。

算法3位置語(yǔ)義距離算法LSE

輸入：兩條室內(nèi)移動(dòng)軌跡T、R以及語(yǔ)義位置分析樹(shù)LSR_Tree。

輸出：軌跡T、R的位置語(yǔ)義相似度。

4.5 室內(nèi)移動(dòng)對(duì)象軌跡相似度

在得到軌跡空間、時(shí)間和位置語(yǔ)義距離三方面的度量結(jié)果后，根據(jù)用戶需求的不同，按不同比例綜合三個(gè)因素即可得到整條軌跡的時(shí)空語(yǔ)義相似度?？紤]到不同單位和數(shù)量級(jí)，采用極差標(biāo)準(zhǔn)化（min-max normalization）方法將差異數(shù)據(jù)進(jìn)行統(tǒng)一。將原始數(shù)據(jù)進(jìn)行線性變換，設(shè)maxA和minA分別為屬性集合A的最大值和最小值，將A的一個(gè)原始值x通過(guò)min-max標(biāo)準(zhǔn)化映射成為區(qū)間[0,1]之間的數(shù)值x′，公式如下：

假設(shè)經(jīng)過(guò)標(biāo)準(zhǔn)化后的空間距離為D′space，時(shí)間距離為D′time，語(yǔ)義距離為D′sem，給出總的室內(nèi)空間移動(dòng)軌跡相似度計(jì)算公式：

其中，δ、η和λ為用戶用來(lái)調(diào)節(jié)各個(gè)影響因素的所占比重，δ+η+λ=1。

5 實(shí)驗(yàn)及分析

5.1 實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)的硬件環(huán)境為Intel?CoreTMi7-2670QM 2.20 GHz CPU，4 GB內(nèi)存，軟件環(huán)境為Windows 7操作系統(tǒng)和Visual Studio 2010開(kāi)發(fā)環(huán)境。由于目前無(wú)法獲得真實(shí)的室內(nèi)移動(dòng)對(duì)象軌跡數(shù)據(jù)集，本文采用隨機(jī)數(shù)據(jù)生成器進(jìn)行仿真模擬實(shí)驗(yàn)，模擬應(yīng)用場(chǎng)景為室內(nèi)大型機(jī)場(chǎng)，人員流動(dòng)視為移動(dòng)對(duì)象。

軌跡數(shù)據(jù)信息如表1所示，實(shí)驗(yàn)設(shè)置6組實(shí)驗(yàn)數(shù)據(jù)，移動(dòng)對(duì)象個(gè)數(shù)分別為150、300、600、1 200、2 400、4 800，所生成軌跡數(shù)目分別為1 000、2 000、5 000、10 000、20 000、40 000條，每條軌跡平均包含約30個(gè)位置記錄。

Table 1 Data of indoor moving object trajectory表1 室內(nèi)移動(dòng)對(duì)象軌跡數(shù)據(jù)表

5.2 軌跡重構(gòu)有效性

軌跡重構(gòu)需要最大程度保留原始軌跡的特性同時(shí)節(jié)省算法執(zhí)行開(kāi)銷。本實(shí)驗(yàn)采用經(jīng)典Top-K查詢算法NRA（random access algorithm）[17]取Top-10條相似軌跡相似值并計(jì)算其平均值，如圖6所示，將原軌跡IMTSM-NC與重構(gòu)軌跡IMTSM在同一場(chǎng)景下進(jìn)行軌跡相似性度量對(duì)比實(shí)驗(yàn)。軌跡數(shù)目與Top-10相似軌跡相似值均值呈同趨勢(shì)增長(zhǎng)，且原軌跡數(shù)據(jù)與重構(gòu)軌跡數(shù)據(jù)的軌跡相似值平均值非常接近，差值均小于0.5%，在軌跡數(shù)目達(dá)10 000條時(shí)兩種軌跡數(shù)據(jù)的相似值均值重合，因此相對(duì)于原始軌跡IMTSM-NC，重構(gòu)軌跡IMTSM對(duì)軌跡相似性計(jì)算的改變非常小，說(shuō)明本文所提出的軌跡重構(gòu)算法可以很好地保留原始軌跡特征。

Fig.6 Similarity contrast of reconstruct trajectories and original trajectories圖6 重構(gòu)軌跡與原軌跡相似性對(duì)比

圖7為原始軌跡IMTSM-NC與重構(gòu)軌跡IMTSM在算法執(zhí)行時(shí)間方面的對(duì)比實(shí)驗(yàn)，在軌跡數(shù)目小于5 000條時(shí)，兩種軌跡數(shù)據(jù)的執(zhí)行時(shí)間差距較小，隨著軌跡數(shù)目的增長(zhǎng)，重構(gòu)軌跡IMTSM的算法執(zhí)行時(shí)間明顯小于原始軌跡IMTSM-NC，且軌跡數(shù)目越大，算法執(zhí)行的時(shí)間差越大，說(shuō)明本文所提出的軌跡重構(gòu)方法可以有效提高室內(nèi)軌跡相似性算法執(zhí)行效率。

Fig.7 Algorithm execution time contrast圖7 算法執(zhí)行時(shí)間對(duì)比

5.3 用戶參數(shù)對(duì)軌跡相似性的影響

式（12）中，參數(shù)δ、η和λ分別為用戶對(duì)空間、時(shí)間和位置語(yǔ)義在IMTSM算法中設(shè)置的權(quán)重。本實(shí)驗(yàn)取軌跡數(shù)目為20 000條時(shí)Top-10條相似軌跡，計(jì)算其平均相似值，并分別對(duì)用戶參數(shù)極端分布情況和均勻分布情況進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)結(jié)果如表2所示。

Table 2 User parameter ratio extreme and uniform表2 用戶參數(shù)比極端分布與均勻分布

其中算法執(zhí)行時(shí)間在用戶參數(shù)為極端分布和均勻分布兩種情況下均為3.1 s，說(shuō)明用戶參數(shù)分布對(duì)IMTSM算法的執(zhí)行效率沒(méi)有影響。而Top-10條相似軌跡的平均相似值在用戶參數(shù)均勻分布時(shí)略高，這是因?yàn)橛脩魶](méi)有對(duì)哪一種影響因素特殊考慮時(shí)相似軌跡的選擇范圍較大。相對(duì)于用戶參數(shù)均勻分布的情況，軌跡相似值在極端分布時(shí)的變動(dòng)幅度可以說(shuō)明空間、時(shí)間和位置語(yǔ)義三種因素對(duì)IMTSM算法的影響程度。如表2所示，空間權(quán)重δ極端大時(shí)，變動(dòng)幅度為0.03，時(shí)間權(quán)重η極端大時(shí)，變動(dòng)幅度為0.04，位置語(yǔ)義權(quán)重λ極端大時(shí)，變動(dòng)幅度為0.09，說(shuō)明對(duì)于室內(nèi)移動(dòng)對(duì)象軌跡相似性計(jì)算，位置語(yǔ)義因素影響最大，其次是時(shí)間因素和空間因素。因此，結(jié)合用戶的不同需求，通過(guò)設(shè)定相應(yīng)的參數(shù)分布，獨(dú)立計(jì)算其位置語(yǔ)義相似度，時(shí)間相似度和空間相似度可以更為有效地計(jì)算出不同需求下的室內(nèi)移動(dòng)對(duì)象軌跡相似性。

5.4 室內(nèi)軌跡相似性度量算法有效性

LIP算法[11]是當(dāng)前較為流行的軌跡時(shí)空相似性度量算法之一，SIT算法[16]為目前最新的可用于室內(nèi)軌跡相似性度量的算法。本實(shí)驗(yàn)采用LIP算法和SIT算法與本文所提算法IMTSM進(jìn)行對(duì)比實(shí)驗(yàn)，在相同軌跡數(shù)據(jù)集、相同查詢軌跡、相同用戶參數(shù)分布情況下，取Top-10條相似軌跡相似值并計(jì)算其平均值。

Fig.8 Indoor trajectory similarity algorithm contrast圖8 室內(nèi)軌跡相似性算法對(duì)比

如圖8所示，是相同場(chǎng)景下三種算法的軌跡相似度計(jì)算對(duì)比實(shí)驗(yàn)結(jié)果，當(dāng)軌跡數(shù)目小于2 000條時(shí)，三種算法的軌跡相似值較為接近，當(dāng)軌跡數(shù)目超過(guò)20 000條時(shí)，IMTSM算法產(chǎn)生明顯優(yōu)勢(shì)，且隨著軌跡數(shù)目的不斷增加，優(yōu)勢(shì)越明顯。這是因?yàn)長(zhǎng)IP算法雖然在軌跡時(shí)空相似性計(jì)算方面取得很好的成果，但其算法更適合應(yīng)用于室外空間。首先LIP算法采用二維軌跡距離計(jì)算，而室內(nèi)環(huán)境下多為三維軌跡；其次，LIP算法并未加入位置語(yǔ)義相似度的考量，在室內(nèi)環(huán)境下度量準(zhǔn)確性較低。另外，SIT算法設(shè)計(jì)了語(yǔ)義分層模式擴(kuò)充位置語(yǔ)義距離計(jì)算，其度量準(zhǔn)確性也高于LIP，相比于LIP算法更適合室內(nèi)環(huán)境。然而，SIT算法未考慮軌跡時(shí)間距離，并且仍然基于最長(zhǎng)公共子序列LCSS算法計(jì)算位置語(yǔ)義相似度，而LCSS主要用于計(jì)算兩個(gè)字符串之間的最大公共子序列，基于LCSS算法計(jì)算移動(dòng)對(duì)象軌跡中的位置語(yǔ)義序列，將字符等同性作為相似依據(jù)，忽略了位置語(yǔ)義序列與字符串序列的不同。

IMTSM算法將時(shí)間因素從軌跡時(shí)空距離中提取進(jìn)行獨(dú)立計(jì)算，利用軌跡投影相交面積設(shè)計(jì)了室內(nèi)軌跡空間距離算法，并且基于位置語(yǔ)義分析樹(shù)直接提取位置語(yǔ)義距離。相比于SIT算法，IMTSM算法增加了軌跡相似性影響因素，減少了語(yǔ)義模式分析過(guò)程，避免了文本相似計(jì)算所帶來(lái)的誤差，可以更加精確地查詢室內(nèi)相似軌跡。

如圖9所示，取Top-10條相似軌跡并將其抽象化，（a）為原始查詢軌跡，（b）為IMTSM算法所得Top-10條相似軌跡，（c）為SIT算法所得Top-10條相似軌跡。從圖中可以看出，采用IMTSM算法得到的相似軌跡與SIT算法相比更為接近原始查詢軌跡，而且SIT算法得到的相似軌跡中明顯存在軌跡偏離及中斷的情況。因此，采用IMTSM算法所得到的軌跡相似性要高于SIT算法，說(shuō)明所提出的IMTSM算法能夠更好地應(yīng)用于查詢室內(nèi)相似移動(dòng)對(duì)象軌跡。

Fig.9 Top-10 similar indoor trajectories圖9 Top-10相似室內(nèi)軌跡

6 結(jié)束語(yǔ)

隨著室內(nèi)位置服務(wù)的多元化發(fā)展，室內(nèi)移動(dòng)對(duì)象軌跡相似性查詢具有重要的研究?jī)r(jià)值。本文給出了一種適用于室內(nèi)空間的移動(dòng)對(duì)象軌跡相似性度量方法IMTSM，并對(duì)其進(jìn)行了相關(guān)闡述。根據(jù)室內(nèi)空間特點(diǎn)，提出將時(shí)間距離獨(dú)立計(jì)算并給出新的時(shí)空距離計(jì)算方法，設(shè)計(jì)位置語(yǔ)義分析樹(shù)結(jié)構(gòu)并基于此給出語(yǔ)義位置距離提取算法，很好地解決了文本絕對(duì)性比較直接應(yīng)用于軌跡相似性計(jì)算不夠精確和代價(jià)過(guò)高的問(wèn)題。最后，通過(guò)實(shí)驗(yàn)對(duì)IMTSM方法的準(zhǔn)確性和有效性進(jìn)行了驗(yàn)證。下一步研究的重點(diǎn)主要集中在結(jié)合室內(nèi)空間索引技術(shù)實(shí)現(xiàn)高效的室內(nèi)相似軌跡查詢。