基于校園無線網絡的時空軌跡相似性度量

方敏佳，劉漫丹

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

0 引 言

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

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

1 相關工作

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

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

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

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

2 用戶時空軌跡提取

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

圖1 基于校園無線網絡的時空軌跡序列生成過程

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

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

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

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

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

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

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

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

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

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

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

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

根據時間特征和空間特征之間的關系，定義任意兩軌跡的時空相似性為

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

(1)

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

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

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

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

3.1 時間相似性計算

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

對任意兩個軌跡記錄點ri,x和rj,y進行匹配計算：若li,x≠lj,y，表示兩個用戶并未出現在同一地點區域，則ri,x和rj,y之間不存在關聯性；若li,x=lj,y，表示兩個用戶出現在同一地點區域，存在關聯性。根據行為記錄關聯性隨時間變化的規律，定義軌跡記錄點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算法的思想可以認為，軌跡Ri對于軌跡Rj之間的關聯性可以近似為Ri軌跡序列中所有軌跡點與Rj軌跡序列中對應STD匹配點的關聯性總和，定義表達式為

(4)

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

(5)

(6)

3.2 空間相似性計算

最長公共子序列(LCSS)算法是常用的從軌跡序列角度分析軌跡相似性的度量方法。軌跡序列的子序列是指，不改變序列的順序，從序列中去掉任意的元素而獲得新的序列。LCSS算法就是尋找兩個給定序列的公共子序列中最長的子序列，該子序列在兩個序列中以相同的順序出現，但是不要求是連續的?？梢哉J為最長公共子序列的長度越長，給定的兩個序列相似程度越高。該方法較好反映出了時空軌跡的空間特征，因此本文考慮選擇利用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模型求取時空軌跡的空間相似性時雖然能夠體現出軌跡之間的重疊程度但是卻無法體現出軌跡的連續性特征。例如，假設有

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

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

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

(8)

(9)

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

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

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的最短時間距離計算結果如圖3所示，所以軌跡R2屬于軌跡R1的最短時間距離子序列為SR1→2:{A,C,D}，該子序列在軌跡R2中對應位置順序為{2,3,4}。

圖3 最短時間距離子序列

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

(10)

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

(11)

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

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

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

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

3.3 時空軌跡的窗口劃分

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

length(w)=|ts-te|

時間窗內包含軌跡序列的軌跡點數定義為時間窗的體積，即

volume(w)=|ls-le|

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

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

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

圖4 并行滑動時間窗

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

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

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

其中，n為軌跡劃分的總窗口數。

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

(12)

4 實驗分析

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

表1 數據集軌跡序列

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

4.1 局部軌跡段相似性結果

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

表2 3名用戶某天內軌跡序列

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

表3 不同相似性度量算法結果對比

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

4.2 整體軌跡數據集相似性結果

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

(13)

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

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

(14)

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

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

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

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

4.3 運行時間比較

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

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

5 結束語

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