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

方敏佳，劉漫丹

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

0 引 言

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

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

1 相關(guān)工作

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

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

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

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

2 用戶時(shí)空軌跡提取

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

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

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

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

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

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

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

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

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

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

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

3 軌跡時(shí)空相似性度量模型

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

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

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

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

(1)

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

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

圖2 軌跡時(shí)空相似性度量流程

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

3.1 時(shí)間相似性計(jì)算

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

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

(2)

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

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

(3)

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

(4)

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

(5)

(6)

3.2 空間相似性計(jì)算

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

對(duì)于用戶ui和用戶uj，其時(shí)空軌跡序列分別為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序列的長(zhǎng)度分別占兩條軌跡長(zhǎng)度比例的平均值決定

(7)

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

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

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

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

(8)

(9)

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

舉例說(shuō)明上述過(guò)程，例如存在兩條軌跡為

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對(duì)于軌跡R2的最短時(shí)間距離計(jì)算結(jié)果如圖3所示，所以軌跡R2屬于軌跡R1的最短時(shí)間距離子序列為SR1→2:{A,C,D}，該子序列在軌跡R2中對(duì)應(yīng)位置順序?yàn)閧2,3,4}。

圖3 最短時(shí)間距離子序列

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

(10)

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

(11)

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

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

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

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

3.3 時(shí)空軌跡的窗口劃分

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

length(w)=|ts-te|

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

volume(w)=|ls-le|

每個(gè)滑動(dòng)窗口的長(zhǎng)度和體積大小受到上限的約束

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

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

圖4 并行滑動(dòng)時(shí)間窗

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

假設(shè)存在某校園用戶ui和uj，定義兩用戶某段時(shí)間內(nèi)通過(guò)校園無(wú)線網(wǎng)絡(luò)產(chǎn)生的總軌跡為Ti和Tj，通過(guò)并行滑動(dòng)時(shí)間窗獲得n個(gè)窗口內(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之間的用戶相似性可通過(guò)軌跡段的時(shí)空相似性獲得，表達(dá)式為UCor(ui,uj)

(12)

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

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

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

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

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

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

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

圖5 3名用戶某日軌跡點(diǎn)分布情況

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

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

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

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

(13)

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

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

(14)

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

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

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

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

4.3 運(yùn)行時(shí)間比較

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

圖7 不同模型運(yùn)行時(shí)間比較/s

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

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