夏 英,楊 雪,張 旭,裴海英

(重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400065)

0 引 言

隨著城鎮(zhèn)化和信息化建設(shè)的不斷推進(jìn)，人們?cè)谑覂?nèi)空間的活動(dòng)更加頻繁和豐富，由于非視距傳播、多徑傳播等因素的影響，傳統(tǒng)的GPS定位技術(shù)已不能提供高質(zhì)量的室內(nèi)位置服務(wù)[1]，但無(wú)線射頻識(shí)別(radio frequency identification,RFID)、藍(lán)牙、WiFi等室內(nèi)定位技術(shù)的發(fā)展，使人們?cè)谑覂?nèi)的軌跡信息可以被及時(shí)、準(zhǔn)確地獲取。聚類作為一種重要的軌跡分析方法，旨在將有相似行為的移動(dòng)軌跡劃分成在同一個(gè)簇中，是室內(nèi)熱點(diǎn)分析、移動(dòng)模式分析、空間布局優(yōu)化、個(gè)性化路線推薦等信息服務(wù)的基礎(chǔ)。

由于室內(nèi)環(huán)境在空間結(jié)構(gòu)、定位技術(shù)、距離度量、位置語(yǔ)義等方面的特殊性，室內(nèi)軌跡聚類分析具有一定的挑戰(zhàn)，但也取得了一系列成果。文獻(xiàn)[2]基于室內(nèi)指紋定位采集的數(shù)據(jù)，提出一種k-medians算法，該算法根據(jù)對(duì)數(shù)高斯距離度量標(biāo)準(zhǔn)選擇各簇的中心點(diǎn)，以各簇的某個(gè)子集為搜索范圍，找到數(shù)據(jù)的近似中值進(jìn)行聚類。文獻(xiàn)[3]針對(duì)室內(nèi)移動(dòng)軌跡提出了時(shí)空偏移的概念，使用動(dòng)態(tài)時(shí)間歸整(dynamic time warping,DTW)算法評(píng)價(jià)軌跡相似性時(shí)引入空間衰減因子，并在此基礎(chǔ)上建立時(shí)空?qǐng)D進(jìn)行軌跡聚類。文獻(xiàn)[4]以室內(nèi)RFID軌跡的時(shí)間維度和當(dāng)前軌跡點(diǎn)的下一個(gè)位置為特征劃分軌跡子簇，直到子簇中的軌跡長(zhǎng)度滿足閾值MAX_DEPTH，并結(jié)合(ordering points to identify the clustering structure,OPTICS)算法的聚類規(guī)則，剔除軌跡中的噪音數(shù)據(jù)。文獻(xiàn)[5]提出改進(jìn)的凝聚型層次聚類(agglomerative nesting,AGNES)算法，計(jì)算軌跡位置的曼哈頓距離，并考慮室內(nèi)軌跡的時(shí)間、距離屬性和空間拓?fù)潢P(guān)系，使得聚簇更加精確。文獻(xiàn)[6]將移動(dòng)對(duì)象的空間位置軌跡轉(zhuǎn)化成語(yǔ)義軌跡，并提取代表移動(dòng)對(duì)象運(yùn)動(dòng)行為的停留位置序列，對(duì)具有相似行為的軌跡進(jìn)行全鏈接層次聚類，同時(shí)挖掘出每個(gè)聚類的地理模式集。

目前RFID定位技術(shù)在商業(yè)服務(wù)、公共安全等諸多領(lǐng)域得到了廣泛應(yīng)用，它是一種結(jié)合自動(dòng)識(shí)別功能的短距離通信技術(shù)，通常由讀寫器、電子標(biāo)簽和數(shù)據(jù)管理系統(tǒng)組成，利用固定的閱讀器讀取進(jìn)入其感應(yīng)范圍內(nèi)的移動(dòng)標(biāo)簽信息，從而識(shí)別并定位移動(dòng)對(duì)象，具有成本低、應(yīng)用簡(jiǎn)便、易于集成等優(yōu)點(diǎn)[7]。本文為了提高室內(nèi)軌跡聚類的準(zhǔn)確性和效率，結(jié)合室內(nèi)空間結(jié)構(gòu)和RFID位置記錄特征，提出一種基于RFID位置語(yǔ)義的室內(nèi)移動(dòng)軌跡聚類方法(indoor trajectory clustering based on RFID location semantics，ITCRLS)。該方法首先通過檢測(cè)室內(nèi)軌跡特征點(diǎn)來(lái)簡(jiǎn)化軌跡，然后從軌跡空間相似度和語(yǔ)義相似度2個(gè)方面綜合度量軌跡相似性，最后對(duì)相似軌跡進(jìn)行層次聚類。

1 相關(guān)定義

結(jié)合室內(nèi)空間結(jié)構(gòu)及移動(dòng)對(duì)象的室內(nèi)運(yùn)動(dòng)行為，對(duì)相關(guān)概念做如下定義。

定義1(室內(nèi)空間要素[8])室內(nèi)空間是三維的，由樓棟、樓層、房間、墻體、門窗、通道等多種要素組成。其中，室內(nèi)通道描述了樓層內(nèi)和樓層間用于連接的公用空間，反映樓層內(nèi)多要素之間和樓層間的可達(dá)關(guān)系，如走廊、電梯、樓梯等。

定義2(室內(nèi)位置)移動(dòng)對(duì)象的室內(nèi)位置pi采用三維坐標(biāo)表示，即，x，y為平面坐標(biāo)中的相對(duì)位置，floor為移動(dòng)對(duì)象所在樓層。

定義3(RFID位置記錄[8])RFID閱讀器固定部署在室內(nèi)空間，當(dāng)攜帶電子標(biāo)簽的移動(dòng)對(duì)象進(jìn)入其覆蓋范圍時(shí)將產(chǎn)生位置記錄。RFID位置記錄為，表示閱讀器readerID在ts時(shí)刻檢測(cè)到帶有標(biāo)簽tagID的對(duì)象進(jìn)入其感應(yīng)范圍，并在te時(shí)刻離開。

定義4(室內(nèi)停留位置)移動(dòng)對(duì)象在位置pi的停留時(shí)間pi.staytime可根據(jù)RFID閱讀器檢測(cè)到的到達(dá)時(shí)間ts和離開時(shí)間te計(jì)算，若超過預(yù)先設(shè)定的時(shí)間閾值δt，則pi可視作室內(nèi)停留位置。

定義5(移動(dòng)軌跡)某移動(dòng)對(duì)象的室內(nèi)位置序列，即TR={|(pi·te

定義6(室內(nèi)語(yǔ)義軌跡)通過RFID閱讀器所在位置的語(yǔ)義信息，可確定pi的語(yǔ)義標(biāo)簽labeli。通過在移動(dòng)軌跡基礎(chǔ)上增加各位置的語(yǔ)義標(biāo)簽形成室內(nèi)語(yǔ)義軌跡，即TRS={,…,}。

定義7(位置語(yǔ)義相關(guān)度)已知室內(nèi)位置pi和pj的語(yǔ)義標(biāo)簽，則pi和pj的位置語(yǔ)義相關(guān)度為loc_E(pi,pj)，具體取值可由應(yīng)用者自行定義。比如，若2個(gè)位置語(yǔ)義標(biāo)簽完全相同(如均為樓梯)則取值為1，若屬于同一類型(如不同品牌的運(yùn)動(dòng)類服裝店)則取值為0.5，完全不同則取值為0。

定義9(特征點(diǎn))當(dāng)室內(nèi)位置pi滿足以下任意一個(gè)條件時(shí)可記為語(yǔ)義軌跡TRS的一個(gè)特征點(diǎn)。

1)pi是TRS的初始位置或者結(jié)束位置；

2)pi位于室內(nèi)通道內(nèi)；

3)角度偏移Api大于閾值θ；

4)pi是室內(nèi)停留位置，體現(xiàn)了移動(dòng)對(duì)象對(duì)該位置的關(guān)注程度[10]。

定義10(相似度線性表)存儲(chǔ)室內(nèi)語(yǔ)義軌跡簇間相似度的有限序列，即線性表Ltable={x1,x2,…,xn}，其中，每個(gè)元素xi=，表示簇cr與簇cs的相似度值為ε。

2 軌跡相似性度量

軌跡相似性度量即選擇合適的算法衡量多條軌跡之間的相似程度，是實(shí)現(xiàn)軌跡聚類的基礎(chǔ)。為了在保持軌跡特征的前提下提高軌跡相似度的計(jì)算效率，首先根據(jù)定義9提取軌跡中的特征點(diǎn)，然后計(jì)算軌跡空間相似度，再結(jié)合移動(dòng)對(duì)象的到達(dá)時(shí)間和停留時(shí)間計(jì)算軌跡語(yǔ)義相似度，并將兩者進(jìn)行加權(quán)求和。將此方法命名為ITSM(indoor trajectory similarity measurement)。

假設(shè)2條室內(nèi)語(yǔ)義軌跡分別為trs1和trs2，其軌跡相似度計(jì)算為

Sim(trs1,trs2)=α*spaSim(trs1,trs2)+

(1-α)*semSim(trs1,trs2)

(1)

(1)式中：spaSim(trs1,trs2)表示軌跡的空間相似度；semSim(trs1,trs2)表示軌跡的語(yǔ)義相似度；α為影響權(quán)重。當(dāng)α取值為0.5時(shí)，表示空間距離和語(yǔ)義2個(gè)因素在軌跡相似性度量時(shí)的影響程度一致。

2.1 空間相似性度量

每條軌跡鄰接的2個(gè)特征點(diǎn)可以構(gòu)成線段，由此室內(nèi)軌跡便可以表示為多個(gè)線段構(gòu)成的有序序列。本文引入文獻(xiàn)[11]提出的二維線段相似性度量算法，并定義室內(nèi)空間距離函數(shù)，使其適用于室內(nèi)三維空間。

假設(shè)在室內(nèi)空間中有2條軌跡線段Li={si,ei}和Lj={sj,ej}，Li位于平面，Lj’={sj’,ej’}為L(zhǎng)j在平面上的投影，如圖1所示。2條線段的室內(nèi)距離由4部分構(gòu)成，即垂直距離、水平距離、高度距離和角度距離[11]。

2)水平距離：d‖=(L‖1,L‖2)

3)高度距離：dh=h

其中，dh可根據(jù)軌跡線段所在的樓層差計(jì)算，計(jì)算室內(nèi)軌跡線段間的距離函數(shù)為：dist(Li,Lj)=ω⊥×d⊥+ω‖×d‖+ωh×dh+ωθ×dθ，函數(shù)中ω⊥,ω‖,ωh,ωθ4個(gè)參數(shù)可根據(jù)真實(shí)室內(nèi)場(chǎng)景取值。本文中將參數(shù)設(shè)置為等值，該函數(shù)考慮了線段的長(zhǎng)度和方向，能夠準(zhǔn)確反映線段間的差異。

圖1 線段的室內(nèi)距離圖示Fig.1 Illustration of the indoor distance between line segments

實(shí)數(shù)代價(jià)編輯距離(edit distance on real sequence，EDR)是計(jì)算軌跡相似度的經(jīng)典方法。本文結(jié)合RFID位置記錄的數(shù)據(jù)特征，采用改進(jìn)的EDR方法計(jì)算軌跡相似度，如(2)式所示。該方法既適用于采樣間隔不等、長(zhǎng)度不一致的軌跡數(shù)據(jù)，又對(duì)由于傳感器故障引起的軌跡噪聲有較好的魯棒性。

DisTR(tra1,tra2)=

(2)

(2)式計(jì)算了2條軌跡tra1和tra2的室內(nèi)距離DisTR(tra1,tra2)。假設(shè)軌跡經(jīng)過特征點(diǎn)檢測(cè)后的長(zhǎng)度分別為|tra1|和|tra2|，tra(i)表示軌跡tra的第i個(gè)線段，Rest(tra)表示tra移除第一個(gè)線段后的軌跡。由于分析長(zhǎng)度變化范圍較大的軌跡時(shí)，容易使長(zhǎng)軌跡之間的距離遠(yuǎn)大于短軌跡之間的距離，這對(duì)于發(fā)現(xiàn)具有相似移動(dòng)行為的軌跡是不合理的，因此需要對(duì)室內(nèi)距離DisTR(tra1,tra2)進(jìn)行歸一化，并通過(3)式得到2個(gè)軌跡的空間相似度。軌跡間的室內(nèi)距離越小，其相似度越高。

(3)

2.2 語(yǔ)義相似性度量

室內(nèi)軌跡中引入位置語(yǔ)義標(biāo)簽[12]，能夠更全面地反映用戶的室內(nèi)運(yùn)動(dòng)模式。通過RFID位置記錄和室內(nèi)停留位置分析，可以得到室內(nèi)語(yǔ)義軌跡并反映出移動(dòng)對(duì)象到達(dá)某位置的時(shí)間和停留時(shí)間。如果2個(gè)移動(dòng)對(duì)象在相近的時(shí)間范圍內(nèi)產(chǎn)生了相似的室內(nèi)語(yǔ)義軌跡，則2條軌跡具有較高的語(yǔ)義相似度。因此，考慮基于移動(dòng)對(duì)象到達(dá)時(shí)間和停留時(shí)間進(jìn)行室內(nèi)軌跡的語(yǔ)義相似性分析。

語(yǔ)義行為模式之間的相似性與其之間的公共子序列相關(guān)，該子序列的長(zhǎng)度代表了語(yǔ)義軌跡間的相似程度。室內(nèi)語(yǔ)義軌跡不僅有語(yǔ)義標(biāo)簽的信息，還具有同樣重要的時(shí)間信息。因此，本文基于最長(zhǎng)公共子序列(longest common subsequence，LCSS)的方法做了改進(jìn)，將室內(nèi)語(yǔ)義軌跡的到達(dá)時(shí)間和停留時(shí)間考慮到相似度計(jì)算中。假設(shè)a和b分別為2條室內(nèi)語(yǔ)義軌跡，它們基于時(shí)間信息的最長(zhǎng)公共子序列的長(zhǎng)度記作ISLCSS(a,b)，其計(jì)算公式為

ISLCSS(a,b)=

(4)

(4)式中：|a|表示軌跡的語(yǔ)義位置數(shù)；Rest(a)表示序列a移除第一個(gè)語(yǔ)義位置；ai是第i個(gè)語(yǔ)義位置；TFai,bj(ts,staytime)是一個(gè)時(shí)間因子，由位置ai和bj的到達(dá)時(shí)間ts和停留時(shí)間staytime計(jì)算，如(5)式所示，其中，系數(shù)λ取值為0.5，表示到達(dá)時(shí)間和停留時(shí)間對(duì)于ISLCSS值計(jì)算的影響程度相同。可以看出當(dāng)軌跡位置在語(yǔ)義、到達(dá)時(shí)間和停留時(shí)間都相等時(shí)，TFai,bj(ts,staytime)值為1，表示該語(yǔ)義位置為2條軌跡的公共位置。

TFai,bj(ts,staytime)=λ×

(5)

在(4)式的基礎(chǔ)上，通過ISLCSS值與較小的軌跡長(zhǎng)度的比值計(jì)算軌跡的語(yǔ)義相似性，即

(6)

(6)式中，semSim(a,b)取值為[0,1]，其值越大表示2條軌跡在語(yǔ)義方面越相似。

2.3 軌跡相似度計(jì)算的有效性分析

ITSM算法的有效性分析主要分為空間相似性分析和語(yǔ)義相似性分析。隨機(jī)選取Q條移動(dòng)軌跡作為查詢軌跡，對(duì)于每條查詢軌跡q采用top-k(k=5,10,20,30)的方式篩選出與其相似度最高的軌跡集合，記為R={r1,r2,…,rk}。

2.3.1 空間相似性分析

采用空間距離度量方法計(jì)算返回的k條軌跡與查詢軌跡的平均室內(nèi)距離。平均距離越小表示返回軌跡與查詢軌跡在空間距離上越接近，算法在空間相似度計(jì)算方面的表現(xiàn)越好。計(jì)算公式為

(7)

2.3.2 語(yǔ)義相似性分析

CG(cumulative gain)[13]方法常用于信息檢索領(lǐng)域，用于評(píng)價(jià)檢索結(jié)果的相關(guān)性。采用該方法計(jì)算每條返回軌跡與查詢軌跡的語(yǔ)義相關(guān)度，即

(8)

(8)式中，loc_E(rj,qj)用于計(jì)算2條軌跡第j個(gè)位置語(yǔ)義的相關(guān)度。軌跡間的語(yǔ)義相關(guān)度Sem_rel(r,q)需要進(jìn)行歸一化處理，最后取k條返回軌跡與查詢軌跡的語(yǔ)義相關(guān)度的平均值，取值為[0,1]，其值越高，表示返回軌跡與查詢軌跡在語(yǔ)義上越接近，算法的語(yǔ)義相似度計(jì)算效果越好。

3 軌跡聚類

層次聚類算法可排除噪聲點(diǎn)的干擾，適用于形狀不規(guī)則、規(guī)模差異大的室內(nèi)軌跡。完成室內(nèi)軌跡特征點(diǎn)檢測(cè)和軌跡相似性度量之后，即可對(duì)具有相似運(yùn)動(dòng)模式的用戶進(jìn)行層次聚類。

3.1 改進(jìn)算法描述

常見的凝聚型層次聚類算法(如AGNES)先將每條軌跡看做單獨(dú)的簇，計(jì)算簇之間的距離并存儲(chǔ)在矩陣中，選擇距離最近的2個(gè)簇進(jìn)行聚類操作，再更新矩陣重復(fù)上述步驟，直到滿足終止條件。為了減少計(jì)算復(fù)雜度，ITCRLS算法根據(jù)定義10將語(yǔ)義軌跡簇間的相似度以三元組的方式存儲(chǔ)在線性表Ltable中，若ε大于預(yù)先設(shè)定的相似度閾值threshold，則將對(duì)應(yīng)的簇cr與簇cs合并為一個(gè)簇，對(duì)線性表中的所有相似度滿足條件的簇進(jìn)行該操作，直到簇之間的最大相似度小于threshold。ITCRLS算法描述如下。

算法1ITCRLS算法。

輸入：室內(nèi)語(yǔ)義軌跡集TR={tra1,tra2,…,tran}，簇間相似度閾值threshold；

輸出：室內(nèi)軌跡簇集TC={TC1,TC2,…,TCn}；

步驟：

1.TC←TR//初始化每條軌跡為一個(gè)簇

2.maxsim←0//maxsim初始化

3.fori←1ton

4.forj←i+1ton

5.ε←CalTrackSimilarity(TCi,TCj)

6.cr←TCiandcs←TCj

7.Ltable←//保存相似度值ε

8.endfor

9.endfor

10.do{

11.fork←1to|Ltable|//線性表長(zhǎng)度為|Ltable|

12.if(Ltablek.ε>threshold)do

13.Ltablek.cr←Ltablek.cr∪

Ltablek.cs//合并簇

14.deleteLtablek.csthenupdateLtable

15.endif

16.if(Ltablek.ε>maxsim)then

17.maxsim←Ltablek.ε

18.endif

19. }whilemaxsim>threshold//聚類終止條件

20.returnTC

算法中函數(shù)CalTrackSimilarity(TCi,TCj)用于計(jì)算簇TCi和簇TCj的相似度，參數(shù)maxsim用于保存相似度的最大值。計(jì)算2個(gè)簇之間的相似度時(shí)，若每個(gè)簇為一個(gè)軌跡集，為了消除異常值對(duì)聚類的干擾，簇間相似度計(jì)算將采用average-linkage思想[14]，即計(jì)算簇間兩兩軌跡的相似度并取其中值。假設(shè)對(duì)n條室內(nèi)語(yǔ)義軌跡聚類，ITCRLS算法每次聚類操作完成了多個(gè)簇的合并，而不僅僅選擇相似度最大的2個(gè)簇進(jìn)行聚類，若平均每次合并t個(gè)簇，共聚類次數(shù)為n/t，其時(shí)間復(fù)雜度為Ο(n2/t)。

3.2 軌跡聚類質(zhì)量評(píng)價(jià)指標(biāo)

聚類過程中將利用(1)式計(jì)算軌跡間的相似度，其值大于設(shè)定閾值則為相似軌跡，應(yīng)歸為一簇。為了反映聚類效果，本文選取精確度(precision)、召回率(recall)和F-measure作為聚類質(zhì)量評(píng)價(jià)指標(biāo)。準(zhǔn)確率和召回率根據(jù)TP，F(xiàn)P和FN計(jì)算[15]，即precision=TP/(TP+FP)，recall=TP/(TP+FN)，其中，TP表示同簇中的相似軌跡數(shù)，F(xiàn)P表示同簇中的非相似軌跡數(shù)，F(xiàn)N表示未正確聚類的相似軌跡數(shù)。F-measure是precision和racall的加權(quán)調(diào)和平均值，計(jì)算如(9)式所示，其取值為[0,1]。

(9)

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集

本文采用的實(shí)驗(yàn)環(huán)境為2.30 GHz CPU，8.0 GB內(nèi)存，Windows7操作系統(tǒng)，java語(yǔ)言，Eclipse環(huán)境。實(shí)驗(yàn)數(shù)據(jù)集使用室內(nèi)移動(dòng)軌跡生成工具IndoorSTG[16-17]模擬生成，模擬的室內(nèi)環(huán)境來(lái)源于真實(shí)商場(chǎng)，共6層樓，94個(gè)室內(nèi)要素。原始數(shù)據(jù)格式為(ID,Read_ID,Move_ID,EnterTime,LeaveTime)，表示移動(dòng)對(duì)象Move_ID在EnterTime時(shí)刻進(jìn)入閱讀器Read_ID的感應(yīng)范圍，LeaveTime時(shí)刻離開。實(shí)驗(yàn)分別模擬了50，250，500，1 000個(gè)移動(dòng)對(duì)象在20天之內(nèi)產(chǎn)生的RFID移動(dòng)軌跡數(shù)據(jù)，軌跡數(shù)目分別為1 000，5 000，10 000以及20 000條，并對(duì)原始軌跡進(jìn)行了語(yǔ)義擴(kuò)充和室內(nèi)空間位置的標(biāo)注。

4.2 實(shí)驗(yàn)結(jié)果對(duì)比

1)為了驗(yàn)證軌跡相似度計(jì)算的有效性，將ITSM算法與文獻(xiàn)[9]同樣計(jì)算室內(nèi)語(yǔ)義軌跡相似度的SIT_SSCP,LSCC_indoor DTW_indoor算法進(jìn)行對(duì)比，設(shè)參數(shù)α為0.5，停留時(shí)間閾值δt為10 min，角度偏移閾值θ為45°，實(shí)驗(yàn)隨機(jī)選取100條移動(dòng)軌跡作為查詢軌跡。

ITSM算法與對(duì)比算法在室內(nèi)空間距離和語(yǔ)義相關(guān)性的分析結(jié)果分別如圖2、圖3所示。

從圖2中可以看出，ITSM方法的平均室內(nèi)空間距離明顯小于傳統(tǒng)算法，說明返回的相似軌跡在空間距離上與查詢軌跡更接近，這是因?yàn)镮TSM充分考慮了室內(nèi)空間特征并計(jì)算軌跡間的室內(nèi)距離。同時(shí)隨著返回軌跡數(shù)量的增加，ITSM也能表現(xiàn)出較好的優(yōu)勢(shì)，因?yàn)槎x的空間距離函數(shù)采用了改進(jìn)的EDR方法，減少了軌跡中異常位置點(diǎn)的影響。從圖3中可以看出，ITSM的軌跡語(yǔ)義相關(guān)度高于對(duì)比算法。ITSM算法描述了軌跡位置間的語(yǔ)義關(guān)系，并考慮了移動(dòng)對(duì)象的停留時(shí)間和到達(dá)時(shí)間，使得查詢結(jié)果更精確。

圖2 平均室內(nèi)空間距離對(duì)比Fig.2 Comparison of average indoor spatial distance

圖3 軌跡語(yǔ)義相關(guān)度對(duì)比Fig.3 Comparison of trajectory semantic relevancy

2)為了分析室內(nèi)軌跡聚類質(zhì)量，將ITCRLS算法與文獻(xiàn)[5]中基于室內(nèi)環(huán)境的improved_ANGES算法進(jìn)行對(duì)比，設(shè)簇間相似度閾值threshold為0.7，α取值為0.5，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 聚類算法的性能對(duì)比Fig.4 Comparison of clustering algorithm performance

由圖4可見，ITCRLS算法的精確度、召回率和F-measure指標(biāo)均高于對(duì)比算法。improved_ANGES算法采用曼哈頓距離處理符號(hào)化軌跡數(shù)據(jù)，并需要預(yù)先設(shè)定聚類的簇?cái)?shù)，而ITCRLS算法通過分析軌跡的語(yǔ)義相似性能夠獲得更好的聚類效果。

此外，圖5表明ITCRLS算法在運(yùn)行時(shí)間方面也得到了較大改善。這是因?yàn)镮TCRLS算法通過特征點(diǎn)檢測(cè)簡(jiǎn)化了原始軌跡，并采用線性表存儲(chǔ)軌跡相似度，從而降低了計(jì)算復(fù)雜度。而improved_ANGES算法采用相似矩陣存儲(chǔ)數(shù)據(jù)，需要消耗更多的存儲(chǔ)空間和計(jì)算時(shí)間。

圖5 聚類運(yùn)行時(shí)間對(duì)比Fig.5 Comparison of clustering runtime

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

室內(nèi)軌跡聚類有利于發(fā)現(xiàn)室內(nèi)熱點(diǎn)和用戶移動(dòng)模式。本文通過分析室內(nèi)空間結(jié)構(gòu)及RFID位置語(yǔ)義特征，提出了一種室內(nèi)移動(dòng)軌跡聚類方法。該方法首先通過軌跡特征點(diǎn)檢測(cè)簡(jiǎn)化原始軌跡，減小后續(xù)的計(jì)算復(fù)雜度。其次，綜合考慮室內(nèi)軌跡在空間特征、到達(dá)時(shí)間和停留時(shí)間等位置語(yǔ)義，可以提高軌跡相似度計(jì)算的準(zhǔn)確性。在此基礎(chǔ)上采用改進(jìn)的層次聚類方法對(duì)移動(dòng)軌跡進(jìn)行聚類。實(shí)驗(yàn)結(jié)果表明，該方法能有效評(píng)價(jià)室內(nèi)軌跡的相似性，提高了聚類質(zhì)量和效率。

參考文獻(xiàn)：

[1] 夏英，王磊，劉兆宏.基于無(wú)線局域網(wǎng)接收信號(hào)強(qiáng)度分析的混合室內(nèi)定位方法[J].重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版,2012, 24(2): 217-221.

XIA Ying, WANG Lei, LIU Zhaohong. Hybrid indoor positioning method based on WLAN RSS analysis[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2012, 24(2): 217-221.

[2] CAMPOS R S, LOVISOLO L, CAMPOS M L R D. Wi-Fi multi-floor indoor positioning considering architectural aspects and controlled computational complexity[J]. Expert Systems with Applications, 2014, 41(14): 6211-6223.

[3] HUNG C C, PENG W C, LEE W C. Clustering and aggregating clues of trajectories for mining trajectory patterns and routes[J].The VLDB Journal,2015,24(2):169-192.

[4] WU Y, SHEN H, SHENG Q Z. A cloud-friendly RFID trajectory clustering algorithm in uncertain environments[J]. IEEE Transactions on Parallel & Distributed Systems, 2015, 26(8): 2075-2088.

[5] HUANG W Q, DING C, WANG S Y. An efficient clustering mining algorithm for indoor moving target trajectory based on the improved AGNES[C]//Proceedings of the 2015 IEEE Trustcom.Washington:IEEE,2015:1318-1323.

[6] 黃健斌,張盼盼,皇甫學(xué)軍,等.融合語(yǔ)義特征的移動(dòng)對(duì)象軌跡預(yù)測(cè)方法[J].計(jì)算機(jī)研究與發(fā)展, 2014, 51(1): 76-87.

HUANG Jianbin, ZHANG Panpan, Huang Fuxuejun, et al. A trajectory approach for mobile objects by combining semantic features[J]. Journal of Computer Research and Development, 2014, 51(1): 76-87.

[7] 王斌,何佳佳,孔祥吉.一種新型寬帶圓極化UHF RFID讀寫天線[J].重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版,2015, 27(5): 620-625.

WANG Bin, HE Jiajia, KONG Xiangji. Novel circular polarization planar broadband antenna for UHF RFID applications[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition，2015, 27(5): 620-625.

[8] 金培權(quán),汪娜,張曉翔,等.面向室內(nèi)空間的移動(dòng)對(duì)象數(shù)據(jù)管理[J].計(jì)算機(jī)學(xué)報(bào),2015,38(9): 1777-1795.

JIN Peiquan, WANG Na, ZHANG Xiaoxiang, et al. Moving object data management for indoor spaces[J]. Journal of Computers, 2015,38(9): 1777-1795.

[9] JIN P,CUI T,WANG Q,et al.Effective similarity search on indoor moving-object trajectories[M].Berlin:Database Systems for Advanced Applications,2016:181-197.

[10] 夏英,溫海平,張旭.基于軌跡聚類的熱點(diǎn)分析方法[J].重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版,2011, 23(5): 602-606.

XIA Ying, WEN Haiping, ZHANG Xu. Hot route analysis method based on trajectory clustering[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2011, 23(5): 602-606.

[11] SKOUMAS G, SKOUTAS D, VLACHAKI A. Efficient identification and approximation of k-nearest moving neighbors [C]//ACM Sigspatial International Conference on Advances in Geographic Information Systems. New York: ACM, 2013: 264-273.

[12] XU Y, LI G, XUE C, et al. Affinity-based human mobility pattern for improved region function discovering[J]. Journal of China Universities of Posts and Tele- communications, 2016, 23(1): 60-67.

[13] MANNING C D, RAGHAVAN P. An introduction to information retrieval[J]. Journal of the American Society For Information Science & Technology, 2008, 43(3): 824-825.

[14] FOUEDJIO F. A hierarchical clustering method for multivariate geostatistical data[J]. Spatial Statistics, 2016, 18(17): 179-198.

[15] YEH C C, YANG M S. Evaluation measures for cluster ensembles based on a fuzzy generalized Rand index[J]. Applied Soft Computing, 2017, 57(9): 225-234.

[16] HUANG C, JIN P, WANG H, et al. IndoorSTG: A Flexible Tool to Generate Trajectory Data for Indoor Moving Objects[C]//IEEE International Conference on Mobile Data Management. Washington: IEEE, 2013: 341-343.

[17] JIN P, DU J, HUANG C, et al. Detecting Hotspots from Trajectory Data in Indoor Space[C]//International Conference on Database Systems for Advanced Applications. Berlin: Springer International Publishing, 2015: 209-225.