基于校園無線網(wǎng)絡(luò)的時空軌跡相似性度量

方敏佳，劉漫丹

(華東理工大學(xué) 信息科學(xué)與工程學(xué)院，上海 200237)

0 引 言

目前，全國各大高校正相繼推進校園信息化建設(shè)，實現(xiàn)了校園無線網(wǎng)絡(luò)全覆蓋，為學(xué)生在校園區(qū)域內(nèi)上網(wǎng)提供了便利[1-3]。校園無線網(wǎng)絡(luò)不僅記錄下了學(xué)生的大量上網(wǎng)數(shù)據(jù)，還通過無線網(wǎng)絡(luò)接入點的位置實時反映出了學(xué)生的位置信息，這為開展以校園無線網(wǎng)絡(luò)為背景的時空軌跡挖掘工作提供了可能。

針對時空軌跡挖掘的研究內(nèi)容主要包括軌跡聚類、軌跡分類、頻繁序列分析、軌跡模式挖掘、軌跡數(shù)據(jù)可視化等方面[4]。軌跡相似性計算是進行各類時空軌跡挖掘研究的基礎(chǔ)工作，相似性計算結(jié)果的準(zhǔn)確性將會對后續(xù)挖掘工作產(chǎn)生極大影響，因此根據(jù)不同軌跡特點和應(yīng)用場景選擇合適的相似性度量模型顯得尤為重要。目前的時空軌跡相似性度量研究大多是基于全球定位系統(tǒng)(global positioning system，GPS)獲得的時空軌跡數(shù)據(jù)，軌跡點之間時間間隔穩(wěn)定，地理位置信息詳細(xì)。然而，校園無線網(wǎng)絡(luò)中的時空軌跡數(shù)據(jù)是通過用戶登錄無線網(wǎng)絡(luò)接入點(access point，AP)獲得的，軌跡數(shù)據(jù)具有時間間隔不穩(wěn)定、地理位置信息重復(fù)冗余等特點。因此目前已有的軌跡相似性度量方法并不能很好適用于該場景。此外，目前已有的相關(guān)研究中，通常只關(guān)注了時空軌跡時間或者空間某一方面數(shù)據(jù)特征信息，或者只是將另一方面的數(shù)據(jù)作為約束條件，并沒有將兩者很好地進行結(jié)合。針對以上問題，本文提出了一種基于最短時間距離子序列的時空軌跡相似性度量模型。該模型同時考慮了時空軌跡的時間相似性和空間相似性，以建筑物編號表示軌跡點地理位置信息，在空間相似性度量模型中引入連續(xù)因子以強化軌跡序列特征，消除冗余軌跡數(shù)據(jù)帶來的影響。另外，在計算過程中利用并行時間滑動時間窗對用戶軌跡進行劃分以提高計算效率。

1 相關(guān)工作

經(jīng)典軌跡相似性度量方法通常利用位置距離來表征軌跡相似性，例如歐氏距離(Euclidean distance)、動態(tài)時間規(guī)整(dynamic time warping，DTW)、編輯距離(edit distance，ED)、弗雷歇距離度量(Fréchet distance)、豪斯多夫距離(Hausdorff distance)等[5]。最長公共子序列(longest common subsequences，LCSS)也是一種研究者常用的經(jīng)典軌跡相似性度量方法，該方法是從軌跡序列的角度分析軌跡相似性?；诮?jīng)典軌跡相似性度量方法，研究者們開展了大量相關(guān)改進工作。王培等[6]針對經(jīng)典Hausdorff距離容易受空間目標(biāo)局部分布影響的缺陷,在進行時空軌跡相似性度量時改為求單位時間內(nèi)最大最小距離的平均值距離；張曉濱等[7]則為Hausdorff距離引入時間約束，以彌補只著重關(guān)注于位置信息的不足。Zheng Zhang等[8]通過限制兩條軌跡點的連接總數(shù)以減少傳統(tǒng)DTW方法中產(chǎn)生的不合理連接，提高算法魯棒性。

由于時空軌跡數(shù)據(jù)的來源非常廣泛，軌跡相似性度量方法需要根據(jù)應(yīng)用場景和軌跡數(shù)據(jù)的自身特點進行優(yōu)化調(diào)整。王雅楠等[9]結(jié)合空間、時間、位置語義的影響將相似性轉(zhuǎn)化為位置語義關(guān)系的計算，提出了一種適用于室內(nèi)的軌跡相似性度量方法。Mei Yeen Choong等[10]結(jié)合k均值和模糊c均值(FCM)聚類算法，并基于LCSS的相似度函數(shù)進行車輛流量分析。Mengke Yang等[11]提出了一個基于長期軌跡數(shù)據(jù)挖掘個體相似性的框架，在計算相似性時結(jié)合了個體訪問重要地點的時空和語義屬性。為了減少海量車輛數(shù)據(jù)的計算量，裴劍等[12]運用Ramer-Douglas-Peucker算法先對單條軌跡進行輪廓抽取，并在此基礎(chǔ)上提出基于LCSS的軌跡相似性算法。周永[13]基于社交網(wǎng)絡(luò)的簽到數(shù)據(jù)對用戶的簽到興趣點進行不同尺度和維度的劃分，然后采用類似包圍盒的思想進行相似度的計算。

無線網(wǎng)絡(luò)也是軌跡相似性的重要數(shù)據(jù)來源和應(yīng)用場景之一。利用無線網(wǎng)絡(luò)獲取的時空軌跡數(shù)據(jù)具有鮮明的數(shù)據(jù)特點，移動對象通常會位于某一限定區(qū)域，例如大型室內(nèi)場所、學(xué)校、社區(qū)等，可以較穩(wěn)定的反映出移動對象在一段較長時間內(nèi)的周期性行為記錄和行為偏好，缺點是軌跡數(shù)據(jù)量大、噪聲干擾信息多、空間范圍小。另外與利用GPS獲取時空軌跡數(shù)據(jù)不同的是，無線網(wǎng)絡(luò)并無法準(zhǔn)確獲取移動對象的實時地理位置信息，而是利用移動對象連接某個AP點從側(cè)面反映出其位置信息。因此，上文中利用GPS獲取軌跡點具體地理位置信息(經(jīng)緯度)和地理軌跡圖形進行軌跡相似性度量的方法并無法在無線網(wǎng)絡(luò)數(shù)據(jù)場景下直接使用。針對上述問題，趙振邦[14]通過構(gòu)建層次圖來為每個用戶的歷史軌跡建模，將用戶軌跡映射為層次圖的一個子圖，通過比較不同子圖之間的相似性進行相似性度量。Fengzi Wang等[15]基于LCSS的思想結(jié)合軌跡點語義特征提出語義軌跡相似度量算法，并用于社會關(guān)系挖掘。Bonan Wang[16]建立基于地點相遇時間的決策樹模型，計算出地點的相似性以得到用戶間的相似性。但是上述這些方法僅僅是關(guān)注了軌跡時間或者空間某一方面數(shù)據(jù)特征信息，并沒有將兩者很好地進行結(jié)合。

在充分分析基于校園無線網(wǎng)絡(luò)的時空軌跡數(shù)據(jù)特點后，本文建立綜合時間序列與空間信息的軌跡相似性度量模型。時間序列方面，改進了文獻[17]中的基于DTW思想的相遇時間距離模型，優(yōu)化時間距離參數(shù)；從空間信息角度，提出了最短時間距離公共子序列的概念，在傳統(tǒng)LCSS法的基礎(chǔ)上利用最短時間距離剔除冗余數(shù)據(jù)，最大可能保留利用空間信息特征。在計算時參考文獻[18]中軌跡連續(xù)性的表達方式引入連續(xù)因子，以體現(xiàn)連續(xù)性特征對軌跡空間位置信息的影響。針對軌跡序列數(shù)據(jù)多、時間跨度大的特點，本文進一步利用并行滑動時間窗口對軌跡進行劃分，大大提高了軌跡相似性度量的計算速度。此外，本文提出的方法可以得出軌跡之間相似性的量化結(jié)果，從而反映出用戶之間的相似性度量結(jié)果，擁有具體的量化數(shù)據(jù)結(jié)果更利于后續(xù)進行社區(qū)發(fā)現(xiàn)、用戶關(guān)系挖掘等用戶行為研究。

2 用戶時空軌跡提取

用戶在使用移動設(shè)備時會主動或被動地記錄大量歷史位置信息，將信息進行提取便形成時空軌跡。時空軌跡是一條位于多維空間的曲線，由一系列時空軌跡點構(gòu)成，代表了用戶在時空環(huán)境下的個體移動過程和行為歷史。每個時空軌跡點均包含空間位置信息和時間信息，此外還可能包含移動方向、移動速度、連接設(shè)備以及用戶的各類社會交互信息[19]。基于無線網(wǎng)絡(luò)的時空軌跡序列是用戶利用各類移動設(shè)備登錄AP點產(chǎn)生的。假設(shè)某用戶在校園中的真實移動路徑如圖1中所示，則該用戶的移動設(shè)備連接行為會在無線網(wǎng)絡(luò)中留下時空序列R

圖1 基于校園無線網(wǎng)絡(luò)的時空軌跡序列生成過程

R∶{(AP6,t1),(AP6,t2),(AP7,t3),(AP8,t4), (AP3,t5),(AP3,t6),(AP4,t7)，(AP5,t8)}

其中，t1,t2,…,t8是連接行為發(fā)生的時間。

無線網(wǎng)絡(luò)的AP點一般均安裝部署在建筑樓內(nèi)，可以將AP點與建筑樓進行關(guān)聯(lián)映射。建筑樓一般具有功能型的語義信息，能夠為軌跡分析帶來更多的特征信息，提高人們對軌跡含義的解讀能力。時空軌跡序列R可以被表示為

R∶{(B4,t1),(B4,t2),(B4,t3),(B4,t4),(B2,t5), (B2,t6),(B2,t7)，(B3,t8)}

根據(jù)上文中對時空軌跡生成原理的介紹，可以定義整個校園無線網(wǎng)絡(luò)中的N個用戶的集合為

U={u1,u2,…,ui,…uN}

定義用戶ui的軌跡序列集為

Ri={ri,1,ri,2,…ri,x,…ri,Ki}

其中，1≤x≤Ki，Ki為用戶ui軌跡序列中行為記錄總數(shù)，序列中的元素ri,x為軌跡記錄點，其為二元組 (li,x,ti,x)，li,x是發(fā)生行為記錄的地點，ti,x則是發(fā)生行為記錄的時間。

3 軌跡時空相似性度量模型

時空軌跡具有時間和空間兩個維度的屬性特征，且時間特征和空間特征是相互約束但又相互獨立的。通常在研究相似性時，相似結(jié)果的值都會被定義在0至1之間。同樣，本文定義任意兩個軌跡序列之間的時間相似性TCor(Ri,Rj) 和空間相似性SCor(Ri,Rj) 變化范圍均在0至1之間

TCor(Ri,Rj)∈[0,1]
SCor(Ri,Rj)∈[0,1]

根據(jù)時間特征和空間特征之間的關(guān)系，定義任意兩軌跡的時空相似性為

TSCor(Ri,Rj)=TCor(Ri,Rj)×SCor(Ri,Rj)

(1)

通過對上式進行分析可以發(fā)現(xiàn)，任意兩軌跡的時空相似性的變化范圍仍然在0至1之間，當(dāng)時間或空間任意特征的相似性為零時，則兩軌跡的時空相似性為零。

本文提出的時空軌跡相似性度量模型根據(jù)上述思想從時間和空間角度進行相似性計算，時間相似性采用最短時間距離(shortest time distance，STD)模型，空間相似性采用基于LCSS的最短時間距離子序列(shortest time distance subsequences，STDSS)模型。為了提高度量模型的運算效率，軌跡相似性計算前先并行滑動窗口對用戶軌跡進行軌跡劃分，獲得對應(yīng)時間范圍內(nèi)的n組軌跡段，然后依次對每組軌跡段進行相似性計算，匯總得到軌跡整體相似性，即用戶之間的相似性度量結(jié)果。以計算用戶ui和用戶uj之間的軌跡相似性為例，具體度量流程如圖2所示。

圖2 軌跡時空相似性度量流程

下文將分別從時間相似性計算、空間相似性計算和窗口劃分3個部分進行詳細(xì)論述。

3.1 時間相似性計算

在實際生活中，兩個用戶前往同一地點區(qū)域并登陸校園無線網(wǎng)絡(luò)，則會產(chǎn)生地點區(qū)域相同且時間間隔較小的軌跡點。從軌跡的時間屬性角度分析，兩個軌跡點之間的關(guān)聯(lián)性與行為記錄的時間距離有關(guān)，當(dāng)時間距離較小時，關(guān)聯(lián)性較高，隨著時間距離的增大，關(guān)聯(lián)性隨時間距離的增大急劇衰減[17]。

對任意兩個軌跡記錄點ri,x和rj,y進行匹配計算：若li,x≠lj,y，表示兩個用戶并未出現(xiàn)在同一地點區(qū)域，則ri,x和rj,y之間不存在關(guān)聯(lián)性；若li,x=lj,y，表示兩個用戶出現(xiàn)在同一地點區(qū)域，存在關(guān)聯(lián)性。根據(jù)行為記錄關(guān)聯(lián)性隨時間變化的規(guī)律，定義軌跡記錄點ri,x和rj,y的時間距離Dis(ri,x,rj,y) 為

(2)

對于用戶ui和用戶uj，其時空軌跡序列分別為Ri={ri,1,ri,2,…ri,x,…ri,Ki} 和Rj={rj,1,rj,2,…rj,y,…rj,Kj}。對于軌跡序列Ri中的軌跡點ri,x，尋找軌跡Rj中所有軌跡點中與軌跡點rj,y時間距離最小的值，即最短時間距離STD，記為STD(ri,x,Rj)，表達式為

STD(ri,x,Rj)=minDis(ri,x,rj,y),?y∈Kj

(3)

基于DTW算法的思想可以認(rèn)為，軌跡Ri對于軌跡Rj之間的關(guān)聯(lián)性可以近似為Ri軌跡序列中所有軌跡點與Rj軌跡序列中對應(yīng)STD匹配點的關(guān)聯(lián)性總和，定義表達式為

(4)

從上式可以發(fā)現(xiàn)，STD相似性度量模型具有明顯方向性，可以得出軌跡Rj對于軌跡Ri的關(guān)聯(lián)性如式(5)所示，兩軌跡之間基于STD模型得到時間序列相似性結(jié)果如式(6)所示

(5)

(6)

3.2 空間相似性計算

最長公共子序列(LCSS)算法是常用的從軌跡序列角度分析軌跡相似性的度量方法。軌跡序列的子序列是指，不改變序列的順序，從序列中去掉任意的元素而獲得新的序列。LCSS算法就是尋找兩個給定序列的公共子序列中最長的子序列，該子序列在兩個序列中以相同的順序出現(xiàn)，但是不要求是連續(xù)的?？梢哉J(rèn)為最長公共子序列的長度越長，給定的兩個序列相似程度越高。該方法較好反映出了時空軌跡的空間特征，因此本文考慮選擇利用LCSS進行軌跡空間相似性計算。

對于用戶ui和用戶uj，其時空軌跡序列分別為Ri={ri,1,ri,2,…ri,x,…ri,Ki} 和Rj={rj,1,rj,2,…rj,y,…rj,Kj}。求取其LCSS序列Rθ

Rθ={rθ,1,rθ,2,…,rθ,z,…,rθ,Kθ}

軌跡Ri和軌跡Rj的空間相似性可以采用LCSS序列的長度分別占兩條軌跡長度比例的平均值決定

(7)

利用LCSS模型求取時空軌跡的空間相似性時雖然能夠體現(xiàn)出軌跡之間的重疊程度但是卻無法體現(xiàn)出軌跡的連續(xù)性特征。例如，假設(shè)有

軌跡A：{餐廳→教學(xué)樓1→教學(xué)樓3→操場}
軌跡B：{餐廳→教學(xué)樓1→教學(xué)樓3→超市}
軌跡C：{餐廳→教學(xué)樓1→圖書館→教學(xué)樓3}

軌跡A分別與軌跡B、軌跡C求取LCSS的長度均為3，但是明顯可以發(fā)現(xiàn)軌跡B與軌跡A出現(xiàn)了相同的移動模式，即可以認(rèn)為軌跡A與軌跡B的相似程度比軌跡C要更高。由于校園用戶的生活移動軌跡主要圍繞寢室和教學(xué)區(qū)展開，因此基于校園無線網(wǎng)絡(luò)的數(shù)據(jù)集中會更容易出現(xiàn)大量重復(fù)易混淆的軌跡點，這使得僅僅依靠LCSS來衡量軌跡的空間相似性不夠合理?；谛@無線網(wǎng)絡(luò)數(shù)據(jù)的特點，本文提出了一種基于最短時間距離子序列STDSS的用戶軌跡相似性度量模型，參考文獻[18]中軌跡連續(xù)性的表達方式在LCSS基礎(chǔ)上引入連續(xù)因子，增加軌跡空間相似性的度量能力。

假設(shè)有兩條軌跡Ri和Rj，將軌跡Ri中每個軌跡點根據(jù)式(3)對軌跡Rj求取最短時間距離，軌跡Rj中對應(yīng)的最短時間距離點構(gòu)成的子序列稱為軌跡Rj屬于軌跡Ri的最短時間距離子序列，記為SRi→j。同時還可以確定最短時間距離子序列SRi→j在軌跡Rj中的位置順序分布，以確定地點連續(xù)因子γ。定義連續(xù)因子表達式

(8)

(9)

式中：γi→j表示SRi→j的連續(xù)因子，|SRi→j| 為SRi→j的序列長度，Kj為軌跡Rj的軌跡長度，u表示SRi→j序列中第z個序列點對應(yīng)軌跡Rj中的順序位置數(shù)，v表示SRi→j序列中第z-1個序列點對應(yīng)軌跡Rj中的順序位置數(shù)。

舉例說明上述過程，例如存在兩條軌跡為

R1={(A,8:20),(A,8:25),(C,10:55),
(D,11:12),(B,11:39)}
R2={(A,7:50),(E,8:18),(C,10:37),(D,11:05),
(D,11:23)(A,12:28)}

軌跡R1對于軌跡R2的最短時間距離計算結(jié)果如圖3所示，所以軌跡R2屬于軌跡R1的最短時間距離子序列為SR1→2:{A,C,D}，該子序列在軌跡R2中對應(yīng)位置順序為{2,3,4}。

圖3 最短時間距離子序列

軌跡連續(xù)因子的求取過程不具有對稱性，可以定義兩條軌跡之間的連續(xù)因子γi,j的表達式為

(10)

基于此，將式(7)進行修正，得到軌跡Ri和軌跡Rj基于STDSS的空間相似性計算結(jié)果為

(11)

至此，根據(jù)時間特征和空間特征之間的關(guān)系，本文中共提到了3種時空軌跡相似性度量模型：

(1)最短時間距離模型(STD模型)。該模型僅利用STD算法提取軌跡序列的時間特征進行計算，忽略空間相似性部分。

(2)最長公共子序列時空度量模型(STD-LCSS模型)。該模型結(jié)合了STD算法和LCSS算法同時從時間和空間角度對軌跡序列進行計算。

(3)最短時間距離子序列時空度量模型(STD-STDSS模型)。該模型是本文提出的優(yōu)化模型，結(jié)合了STD算法和STDSS算法，針對校園用戶的軌跡數(shù)據(jù)特征從時間和空間角度對軌跡序列進行計算。

3.3 時空軌跡的窗口劃分

在實際應(yīng)用過程中，用戶在校園無線網(wǎng)絡(luò)中的軌跡序列長度通?？缍确浅４螅@對進行軌跡相似性度量帶來了一定的困難。而且，用戶的軌跡序列通常呈現(xiàn)一種周期性變化，為了得到更準(zhǔn)確的度量結(jié)果、提高運行速度，本文采用并行滑動時間窗口將兩名用戶完整的時空軌跡同時進行劃分，分別計算對應(yīng)窗口內(nèi)軌跡段的時空相似性再進行匯總平均處理。定義符號w=(ls,le,ts,te) 來表示某一用戶軌跡在某段連續(xù)時間中產(chǎn)生的用戶軌跡序列段，其中l(wèi)s和le分別表示時間窗內(nèi)該軌跡的起止軌跡地點編號，ts和te分別表示時間窗的起止時間。起止時間之間的時間間隔定義為時間窗的長度，即

length(w)=|ts-te|

時間窗內(nèi)包含軌跡序列的軌跡點數(shù)定義為時間窗的體積，即

volume(w)=|ls-le|

每個滑動窗口的長度和體積大小受到上限的約束

其中，lengthmax和volumemax分別表示最大窗口寬度和體積。

首先對兩軌跡的起始軌跡點進行分析，選擇時間參數(shù)較小的軌跡點作為時間窗的起始軌跡點，對應(yīng)時間參數(shù)為滑動窗口的起始時間。窗口結(jié)束時間由兩個約束的上限同時決定，若窗口內(nèi)兩用戶的軌跡段同時滿足時間和體積的約束上限，這將窗口標(biāo)識為有效窗口。剩下的軌跡序列以相同的規(guī)則依次重復(fù)劃分下去，便可得到兩用戶的滑動窗口序列。圖4為并行滑動窗口的實現(xiàn)原理。

圖4 并行滑動時間窗

并行滑動窗口提取出的軌跡段能夠同時通過時間跨度和窗口內(nèi)的軌跡點數(shù)目進行大小調(diào)整，較好地適應(yīng)兩個用戶的軌跡點分布變化，平衡各個窗口內(nèi)的軌跡點數(shù)量。該窗口滑動方法可以提取出位于相同時間范圍內(nèi)的軌跡段，將其對應(yīng)進行時空相似性度量更具合理性。

假設(shè)存在某校園用戶ui和uj，定義兩用戶某段時間內(nèi)通過校園無線網(wǎng)絡(luò)產(chǎn)生的總軌跡為Ti和Tj，通過并行滑動時間窗獲得n個窗口內(nèi)的軌跡段序列集合為

Ti={Ri,1,Ri,2,…,Ri,x,…,Ri,n}
Tj={Rj,1,Rj,2,…,Rj,x,…,Rj,n}

其中，n為軌跡劃分的總窗口數(shù)。

結(jié)合上文的式(1)、式(6)和式(11)定義用戶ui和uj之間的用戶相似性可通過軌跡段的時空相似性獲得，表達式為UCor(ui,uj)

(12)

4 實驗分析

本文抽取某高校無線網(wǎng)絡(luò)的真實登錄記錄作為實驗數(shù)據(jù)集。該數(shù)據(jù)集時間跨度為30天，被統(tǒng)計用戶共377名，涵蓋全校區(qū)域范圍的21個地點編號。該軌跡數(shù)據(jù)是由電子設(shè)備(如手機、筆記本電腦)接入無線局域網(wǎng)絡(luò)的接入點獲取的用戶位置信息組成，因此在進行用戶軌跡相似性計算之前，需要對數(shù)據(jù)集進行清洗，剔除重復(fù)和錯誤的數(shù)據(jù)。此外，還需對地點相同的數(shù)據(jù)點進行適當(dāng)合并，減少密集軌跡點。本文在實際實驗中，選擇將時間間隔在5分鐘內(nèi)的相同地點的軌跡點進行合并，將兩軌跡點動作時間的平均值作為合并后軌跡點的時間。將用戶的軌跡點時間表示為數(shù)值形式，將24小時映射至區(qū)間[0,1]，因此30天時間跨度應(yīng)為區(qū)間[0,30]。表1中記錄了完成數(shù)據(jù)預(yù)處理后數(shù)據(jù)集的數(shù)據(jù)格式。

表1 數(shù)據(jù)集軌跡序列

為驗證最短時間距離模型(STD模型)、最長公共子序列時空度量模型(STD-LCSS模型)，以及本文提出的最短時間距離子序列時空度量模型(STD-STDSS模型)3種軌跡相似性度量模型的特點以及STD-STDSS模型的優(yōu)越性，將從局部軌跡段、數(shù)據(jù)集整體效果和運行時間3個方面進行分析。

4.1 局部軌跡段相似性結(jié)果

從數(shù)據(jù)集中提取出3名用戶某天的軌跡序列見表2，其軌跡點在一天內(nèi)的分布情況如圖5所示，利用文中3種軌跡相似性度量方法分別計算出用戶1與用戶2之間的相似性和用戶1與用戶3之間的相似性見表3。

表2 3名用戶某天內(nèi)軌跡序列

圖5 3名用戶某日軌跡點分布情況

表3 不同相似性度量算法結(jié)果對比

從圖5軌跡點的分布中可以發(fā)現(xiàn)，用戶2與用戶3的軌跡序列中，用戶2的行為軌跡序列明顯與用戶1更為相似，但是STD模型卻得出了相反的實驗結(jié)果。STD-LCSS模型和STD-STDSS模型得出的計算結(jié)果更加具有合理性，并且STD-STDSS模型能夠更明顯區(qū)分出軌跡序列的差別。用戶3的軌跡模式是校園無線網(wǎng)絡(luò)數(shù)據(jù)集中經(jīng)常出現(xiàn)的一種軌跡類型，用戶的行為數(shù)據(jù)為大量重復(fù)的地點且通常為宿舍樓，這樣容易對相似性度量的結(jié)果產(chǎn)生干擾，STD-STDSS模型則可以過濾這樣的干擾信息，提高局部軌跡段計算的準(zhǔn)確性。

4.2 整體軌跡數(shù)據(jù)集相似性結(jié)果

對整體軌跡數(shù)據(jù)集進行實驗分析時，為更好地驗證不同模型之間計算結(jié)果的有效性，需要將計算結(jié)果先進行歸一化處理，得到任意兩用戶之間的關(guān)聯(lián)性Urelation(ui,uj)

(13)

式中：UCormin和UCormax分別為整個數(shù)據(jù)集中任意兩用戶軌跡序列相似性計算值的最小值和最大值。

采用用戶關(guān)聯(lián)性有效性指標(biāo)AFR(θ) (accuracy of fin-ding relationship)進行分析對比[17]。其含義為所有滿足Urelation(ui,uj)≥θ的用戶對和uj中含有相同用戶標(biāo)簽(例如學(xué)院專業(yè)班級)的用戶對所占的比例，表達式為

(14)

式中：θ為用戶關(guān)聯(lián)性閾值，有0≤θ≤1，|Urelation(ui,uj)≥θ| 為滿足閾值范圍的用戶對總數(shù)，|Urelation(ui,uj)≥θ且ui與uj存在相同用戶標(biāo)簽|為滿足閾值范圍且含有相同用戶標(biāo)簽的用戶對總數(shù)。通過對閾值的設(shè)置，可以分析不同度量方法下用戶關(guān)聯(lián)性的分布與變化情況。表4和圖6分別記錄了3種模型的AFR(θ) 隨θ變化的數(shù)值和曲線。

表4 不同模型下AFR(θ)隨θ變化情況

圖6 不同模型下AFR(θ)隨θ變化的曲線

從表4和圖6中可以看出AFR(θ) 會隨著閾值θ增大而增大，在相同θ的情況下，STD-STDSS模型的結(jié)果準(zhǔn)確性最高，且準(zhǔn)確率較早達到了100%。在AFR(θ) 隨閾值θ增長的過程中，前兩種模型在θ=0.5附近均出現(xiàn)了準(zhǔn)確率波動的現(xiàn)象，但是STD-STDSS模型則未出現(xiàn)這樣的狀況。

4.3 運行時間比較

對整體數(shù)據(jù)集通過20次仿真實驗求取運行時間平均值后發(fā)現(xiàn)，采用并行滑動窗口對軌跡進行先劃分再進行用戶相似性計算可以明顯提高算法的運行時間。結(jié)合軌跡時空特征的算法比僅考慮軌跡時間序列的算法運行時間會有些許增加，但是可以提高度量結(jié)果的準(zhǔn)確性，因此所需運行時間增長在可接受范圍內(nèi)。圖7為未進行滑窗處理直接利用STD模型進行相似性度量與經(jīng)過滑窗處理后再進行度量的3種模型所需運行時間的比較。

圖7 不同模型運行時間比較/s

5 結(jié)束語

相似性度量是軌跡數(shù)據(jù)挖掘中的關(guān)鍵性步驟，也決定了后續(xù)推廣應(yīng)用成果是否可靠。針對目前相關(guān)軌跡相似性度量方法不能較好地應(yīng)用于校園無線網(wǎng)絡(luò)場景的問題，本文提出了最短時間距離子序列時空度量模型(STD-STDSS模型)。該模型基于校園無線網(wǎng)絡(luò)的數(shù)據(jù)特點和應(yīng)用場景，同時結(jié)合軌跡時間序列與空間信息，度量用戶時空軌跡序列之間的相似程度，以反映校園無線網(wǎng)絡(luò)用戶之間的關(guān)聯(lián)性。該模型利用最短時間距離(STD)求取軌跡的時間相似性，利用最短時間距離子序列(STDSS)的概念求取軌跡的空間信息相似性。STDSS模型能夠在剔除干擾數(shù)據(jù)的同時保留軌跡空間信息的順序特征，提高軌跡空間相似性度量的準(zhǔn)確性。最后，文中利用真實的校園無線網(wǎng)絡(luò)數(shù)據(jù)集對算法進行了實驗驗證，實驗結(jié)果表明，基于最短時間距離子序列(STD-STDSS)的軌跡時空相似性度量模型的計算結(jié)果在局部和整體都具有較好的準(zhǔn)確性，在基于校園無線網(wǎng)絡(luò)的應(yīng)用場景下有較好的實際效果。