改進(jìn)DBSCAN 算法在校園軌跡數(shù)據(jù)相似性的應(yīng)用①

張瑛璽, 王法玉

(天津理工大學(xué), 天津 300384)

在早期對校園用戶的移動性研究中多數(shù)是基于校園用戶的上網(wǎng)日志, 研究者主要關(guān)注的是用戶的上網(wǎng)習(xí)慣及無線網(wǎng)絡(luò)的使用情況, 如用戶的在線時長、用戶的在線頻率、系統(tǒng)當(dāng)前的在線人數(shù)等. 現(xiàn)在越來越多的研究人員開始關(guān)注用戶在無線網(wǎng)絡(luò)下的軌跡變化規(guī)律. 例如文獻(xiàn)[1]中作者使用無向加權(quán)的單模網(wǎng)絡(luò)統(tǒng)計兩個用戶WiFi 接入點時間軌跡矢量變化. 學(xué)生作為一個重要群體, 面臨各種各樣的問題, 有學(xué)業(yè)上的焦慮問題, 戀愛狀態(tài)問題, 人際交往的問題[2]. 有時學(xué)生不愿意說出來, 需要老師和學(xué)校多加注意, 及時關(guān)注心理狀況. 從人際交往學(xué)和心理學(xué)分析, 良好的交際行為營造出的輕松舒適的氛圍, 能夠促進(jìn)學(xué)生學(xué)習(xí)進(jìn)步. 所以,老師可以通過無線數(shù)據(jù)狀態(tài), 科學(xué)判斷學(xué)生的社交狀態(tài), 依據(jù)判斷結(jié)果, 發(fā)現(xiàn)有疑似孤僻的學(xué)生, 則需要排查和教育輔導(dǎo). 從而為高校的學(xué)生日常教育提供據(jù)支撐.

目前, 已經(jīng)有部分學(xué)者對此類問題進(jìn)行研究, 文獻(xiàn)[3]中作者使用Hausdorff 距離進(jìn)行時空軌跡相似度測量,但是這種距離方式只能從點數(shù)據(jù)集合上判斷相似度,對移動物體整體度量分析效果不佳. 文獻(xiàn)[4]使用校園卡數(shù)據(jù)進(jìn)行軌跡模式挖掘, 但是校園卡使用地點有限,時間上有間隔, 時效性較差. 文獻(xiàn)[5]采用K-means 對時空數(shù)據(jù)進(jìn)行聚類, K-means 算法最終得到的可能是局部優(yōu)化, 在非凸數(shù)據(jù)集或者類別規(guī)模太大的數(shù)據(jù)上聚類效果不好. 以上方法因為在相似性度量時對時間維度的依賴程度不同, 所以不同程度地影響聚類效果.還有, 聚類算法的核心是相似度度量公式的使用, 除常用的Minkowski 距離、向量內(nèi)積、曼哈頓距離公式,還有文獻(xiàn)[6]改進(jìn)版的MinKovDM, 實際場景中要根據(jù)語義結(jié)構(gòu)復(fù)雜度和數(shù)據(jù)性質(zhì)選取合適的公式進(jìn)行軌跡匹配. 文獻(xiàn)[7]提出最短時間距離子序列模型, 運用連續(xù)因子求空間相似性, 采用并行滑動時間進(jìn)行時間相似性度量. 文獻(xiàn)[8]中闡述DBSCAN 和K-mans 算法在軌跡數(shù)據(jù)中的優(yōu)缺點以及對移動對象聚類效果進(jìn)行分類對比, 為本文的寫作提供思路.

針對上述問題, 為了減少軌跡間偏差和兼容移動對象的移動模式, 更好地匹配軌跡模式, 增強度量方法的時間魯棒性, 采用Hausdorff 距離和Frechet 距離相結(jié)合的距離公式, 不僅從整體上提升相似性度量效果,而且能夠保持軌跡整體形狀. 因為DBSCAN 算法適合任意形狀, 對異常點有較好的魯棒性, 相對于其他算法更適合查找異常點, 所以采用DBSCAN 進(jìn)行聚類.聚類之后為了更加清楚的判斷聚類效果, 采用FineBI 軟件進(jìn)行可視化展示.

1 模型方法

1.1 WiFi 數(shù)據(jù)的處理

WiFi 是一個高頻無線電信號, 通過一個無線路由器可以發(fā)送出去. 其電波覆蓋的有效范圍可以通過設(shè)備連接. WiFi 定位, 也就是通過移動終端和無線網(wǎng)絡(luò)接入的信號交互來實現(xiàn)對移動終端的精準(zhǔn)定位.無線AP(wireless access point) 是WiFi 技術(shù)的一種, 利用無線技術(shù)實現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)的傳輸. 目前, 高校圖書館、食堂、宿舍、教學(xué)樓都安裝了一定數(shù)量的AP 設(shè)備, 基本實現(xiàn)了全覆蓋. 本文所使用的原始數(shù)據(jù)根據(jù)RESTful 接口定時獲取的. RESTful 接口是HTTP 接口的實現(xiàn)方式之一. 接入控制器收集到數(shù)據(jù)后, 每一種數(shù)據(jù)資源都存入一條唯一的URL 中. 因此使用RESTful 接口的GET方法可以從AC 獲取用戶使用無線網(wǎng)絡(luò)的數(shù)據(jù).智能手機在WiFi 功能打開的狀態(tài)下, 如果檢測到已經(jīng)連接過的AP, 會自動連接. 而且, 無線AP 具有漫游功能, 保證學(xué)生移動過程中跨AP 連接WiFi 信號的連續(xù)性. 需要的原始數(shù)據(jù)如表1.

表1 原始數(shù)據(jù)

1.2 軌跡數(shù)據(jù)的時空距離

基于距離的相似度度量方法有很多, 包括歐氏距離和余弦距離、Hausdorff 距離、Minkowski 距離、Chebyshev 距離. Hausdorff 距離是用來測量離散點的鄰接度, 而運動軌跡是矢量空間中有序的序列點集, 即使兩個序列有很小的Hausdorff 距離, 也并不能表示軌跡間相似度高.

本文加入空間和時間維度, 更加合理地計算相似度. 通過對比分析, 同時使用Frechet 距離公式, 以函數(shù)的形式定義曲線的距離, 從序列整體全局到局部細(xì)節(jié)分級進(jìn)行度量, 避免Hausdorf 距離分析只從點數(shù)據(jù)集合距離上判斷各軌跡間相近度的缺陷, 整體態(tài)勢越相近, 相似度越高.

計算方法如下:

定義1. 軌跡點, 帶時間的軌跡點P=(t,d,loc), 其中t表示用戶停留在該軌跡點的時間點,d表示用戶停留在該軌跡的時間長,loc表示用戶停留的軌跡點位置.

定義 2. 一條軌跡Tr定義為按時序組成的一組坐標(biāo)點序列, 該序列由定義1 的軌跡點組成. 設(shè)Tr=p1→p2→p3···→pn, 其中p1,t＜pi+1,t, 按時間先后排序.

設(shè)有兩條軌跡Li和Lj,si、ei、sj、ej分別表示Li和Lj的開始點和結(jié)束點, 由Lj兩端點向Li兩端點做垂直投影, 得到ps和pe, 空間距離如圖1 所示.

圖1 軌跡距離

Li和Lj垂直距離如下:

考慮到時間距離和空間距離之間有數(shù)量級之間的差別, 使用z-score 函數(shù)進(jìn)行標(biāo)準(zhǔn)化. 例如對變量h進(jìn)行標(biāo)準(zhǔn)化.

1)絕對值偏差的平均值的計算:

1.3 基于Frechet 的 DBSCAN 時空聚類算法

DBSCAN 算法, 作為最具有代表性的基于密度的聚類算法, 可以將高密度數(shù)據(jù)進(jìn)行聚類, 最好是在存在“噪聲”的目標(biāo)對象里尋找所有可能的形狀的簇[10], 這樣的聚類結(jié)果可篩選出異常軌跡.在傳統(tǒng)的算法基礎(chǔ)上, 增加時間和空間維度, 能夠更加有效的提升聚類效果. 參數(shù)Eps反映了不同軌跡聚成一個類需滿足的最低相似程度范圍, 而MinPts刻畫了不同軌跡聚成一個類需滿足的最少數(shù)量. 如圖2 所示.

圖2 DBSCAN 核心概念示意圖

應(yīng)用到實際的軌跡聚類的算法中, 算法的時間復(fù)雜度主要在鄰域的計算中, 可以通過使用索引的方法降低時間復(fù)雜度, 因此加入路網(wǎng)思想.

根據(jù)路網(wǎng)的思想, 首先根據(jù)定義好的n×n的網(wǎng)格空間, 在每一格空間進(jìn)行序列的標(biāo)注, 統(tǒng)計每條軌跡經(jīng)過的網(wǎng)格. 計算軌跡段的領(lǐng)域時, 先以該軌跡中心點所在的網(wǎng)格為中心, 向5×5 的區(qū)域擴(kuò)展, 只判斷所在25宮格區(qū)域內(nèi)的軌跡, 減少搜索時間.

下面對DBSCAN 算法的具體步驟介紹如下:

(1)由軌跡Tr中任意一個未被訪問的p軌跡點作為核心點開始, 在Tr中以宮格法搜索ε 鄰域的軌跡點q,即Nε(p)={q∈Tr|dist(p,q)≤Eps},dist(p,q)可由式(11)得到. 如果ε 領(lǐng)域里有足夠的點|Nε(p)|≥MinPts, 則認(rèn)為這是一個新的簇C, 否則認(rèn)為該軌跡點為邊界點或噪聲點.

(2)對p點進(jìn)行擴(kuò)充, 尋找從該點出發(fā)的所有密度相連的軌跡點, 遍歷每一個密度相連的軌跡點領(lǐng)域內(nèi)所有核心點, 尋找和這些核心點密度相連的點, 直到?jīng)]有可擴(kuò)充的點為止.

(3)找到除p以外尚未處理的核心點, 重復(fù)第一步,對該核心點進(jìn)行擴(kuò)充直到軌跡數(shù)據(jù)集中沒有新的核心點為止.

偽代碼如下:

算法1. 改進(jìn)的DBSCAN 算法輸入: 軌跡數(shù)據(jù)集 , 半徑 , 最少軌跡數(shù)量輸出: 所有到達(dá)密度要求的軌跡簇Tr Eps MinPts(1)起初將軌跡數(shù)據(jù)集 中的所有軌跡點對象標(biāo)記為未處理狀態(tài)Tr p Tr(2) for 數(shù)據(jù)集 中每個坐標(biāo)點對象 do(3) if p 已經(jīng)歸入某個簇或標(biāo)記為噪聲 then(4) continue;(5) else p Eps Nε(p)(6) 用宮格法檢查坐標(biāo)點對象 的 鄰域 ;MinPts(7) if Nε(p)包含的對象小于 then p(8) 標(biāo)記對象 為邊界點或噪聲點(9) else p p(10)標(biāo)記 為核心點, 建立新簇C, 并將 鄰域內(nèi)所有點加入C Nε(p) q(11) for 中所有尚未處理的軌跡點對象 do Eps Nε(q) Nε(q) MinPts Nε(q)(12) 檢查其 鄰域 , 若 包含至少 個對象, 則將中未歸入任何一個簇的坐標(biāo)點對象加入C;(13) end for(14) end if(15) end if(16) end for

1.4 特征軌跡提取

軌跡的運動特征指一些能夠反映運動物體特征的指標(biāo). 比如軌跡速率、方向角和角速度等數(shù)據(jù)的均值、最值、中位值等[11]. 下面對聚類后的簇進(jìn)行特征軌跡提取.

主要思想: 用一條垂直于類別中所有線段的平均向量(軌跡本質(zhì)是一種向量, 向量的長度為線段的長度, 求出所有的向量和, 再單位化, 得到的結(jié)果即為平均向量)的直線掃描各條子軌跡, 計算該線段在軌跡開始點和結(jié)束點分別有多少個交點, 將交點個數(shù)與設(shè)置的Leastlns比較, 如果小于該值則繼續(xù)掃描, 否則計算所有交點的中心點并存儲在向量中, 最后生成的軌跡點向量為特征軌跡.

假設(shè)每一個簇內(nèi)所有軌跡段的向量集合w={w1,w2,···,wn} , 設(shè)|w|表示集合內(nèi)所有向量的和的長度.

步驟如下:

(1)對一個簇中所有向量求平均向量如下:

(2)把整個簇內(nèi)的向量按平均向量旋轉(zhuǎn), 向量旋轉(zhuǎn)的示例圖如圖3 所示.

圖3 向量旋轉(zhuǎn)示意

(4)把步驟(3)生成的點旋轉(zhuǎn)回原來的角度, 連接成一條軌跡, 這條軌跡就是特征軌跡, 如圖4 所示.

圖4 掃描示例

(5)對所有的軌跡簇重復(fù)上述4 個步驟.

1.5 相似度度量

軌跡序列也是一種帶時間空間屬性的序列, 下面對提取出的特征軌跡進(jìn)行相似性度量.

最長公共子序列(LCSS)算法是常用的從軌跡序列角度研究軌跡相似度的算法. 軌跡序列的子序列是指, 不改變該序列的順序, 從序列中去掉某些元素獲得新的序列, 該序列在兩個序列中以相同的順序出現(xiàn), 不一定要連續(xù)[12].

公共子序列: 比如給定的序列X和Y, 序列Z是X的子序列, 同時也是Y的序列, 則Z是X和Y的公共子序列.

LCSS 是最長的公共子序列, 最長公共子序列的長度越長, 給定的兩個序列相似度越高.相似性計算公式:

改進(jìn)的算法可以更好的體現(xiàn)出軌跡之間的重疊程度, 通過增加的相似度指數(shù)直觀的判斷軌跡相似性.

2 實驗結(jié)果及分析

2.1 數(shù)據(jù)集介紹和實驗設(shè)置

采集8 周無線數(shù)據(jù)作為數(shù)據(jù)源, 根據(jù)原始數(shù)據(jù)參數(shù)處理成軌跡數(shù)據(jù).

采集時間為2020.9.1-2020.10.31, AP 數(shù)量: 318 個,學(xué)生數(shù)量: 13 568 名.

改進(jìn)的DBSCAN 算法參數(shù)設(shè)置:Eps= 1 km,MinPts=10.

2.2 數(shù)據(jù)篩選和預(yù)處理

提取實驗數(shù)據(jù)集中的用戶移動軌跡的信息, 形成定義1 的基于用戶軌跡的向量數(shù)據(jù), 從而根據(jù)軌跡向量聚類之后提取特征軌跡進(jìn)行相似值計算. 但是, 由于本校無線用戶群體大, 終端多樣性等特征, 還有Frechet計算方法對噪聲敏感[13], 為了降低向量相似性的計算的復(fù)雜度, 減小聚類結(jié)果的偏差. 進(jìn)行了二次去噪的過程, 對篩選規(guī)則做了定義, 并使用基于使用頻率和在線時長的方法對用戶進(jìn)行了過濾.

2.3 聚類結(jié)果分析

新提出的算法考慮了時間空間因素, 還有采用Frechet 距離測量, 比傳統(tǒng)的DBSCAN 算法運行時間長. 雖然提高了聚類效果的準(zhǔn)確性, 聚類開銷變大, 但是運行時間的增長在可接受的范圍內(nèi).

下面選取某一天上午9 點到12 點部分同學(xué)數(shù)據(jù).在保護(hù)隱私的條件下進(jìn)行實驗.

通過在運行時間, 特征軌跡的相似性對比效果兩個方面進(jìn)行分析, 驗證本文所提出的改進(jìn)的算法的優(yōu)越性, 同時發(fā)現(xiàn)不足之處, 為后續(xù)的研究提供方向.

FinBI 可以實現(xiàn)Windows 系統(tǒng)類似的圖形化系統(tǒng)界面[14]來設(shè)計ETL 轉(zhuǎn)換過程, 所以用FinBI 展示, 軌跡粗細(xì)表示人數(shù)多少. 如圖5 所示.

圖5 軌跡聚類

之后根據(jù)第1.4 節(jié)中方法進(jìn)行軌跡提取, 如圖6.

圖6 特征軌跡提取

對整體數(shù)據(jù)集通過20 次實驗求取運行時間平均值和其他3 種常見的模型對比, 如圖7. 和傳統(tǒng)的DBSCAN算法比較, 時間變長是因為增加了時間和空間的復(fù)雜度, 但是提升了相似度度量的效果, 所以增長的時間在可接受的范圍內(nèi). 同時驗證了Hausdoff 在軌跡距離測量的效果不如Frechet 距離. DBSCAN 算法同K-means算法比較, 前者更適合時空軌跡這種形狀不規(guī)則序列之間的聚類應(yīng)用.

圖7 運行時間對比圖

2.4 用戶相似性分析

學(xué)生無線用戶可以根據(jù)在網(wǎng)絡(luò)信息中心注冊的信息, 判斷學(xué)生專業(yè)、年級、宿舍信息. 根據(jù)實驗結(jié)果圖可以得出, 本次數(shù)據(jù)大多為1-5 號公寓樓學(xué)生. 開學(xué)前兩個月, 同學(xué)們學(xué)習(xí)積極性比較高, 去往圖書館、學(xué)院樓、教學(xué)樓同學(xué)較多, 符合學(xué)生活動特點.

同公寓的學(xué)生大部分是同專業(yè)、同班級, 行為趨同性更高, 算法聚類可視化結(jié)果也表明了算法的正確性. 但是有部分同學(xué)行為軌跡差異大, 會選擇較遠(yuǎn)的路線繞行.

提取出特征軌跡, 將改進(jìn)的相似性度量方法和STD(最短時間距離模型, 根據(jù)模型中時間單位進(jìn)行軌跡提取)、OWD (單向距離法, 基于兩條軌跡圍成的面積大小判斷相似性. 面積越大, 說明軌跡之間距離較遠(yuǎn), 相似度就低; 相反, 若圍成的面積為0, 則說明兩條軌跡重合, 相似度最高)、MBR (最小邊界矩形法, 在設(shè)定的圖形內(nèi)通過求最小外接矩形和設(shè)定密度閾值進(jìn)行聚類)進(jìn)行實驗對比, 見表2.

表2 不同相似性方法結(jié)果對比

S im值根據(jù)式(15) 得出, 比值越高, 相似度越高.前兩列比值用來評價相似值區(qū)分度, 指數(shù)越高區(qū)分度越明顯. 經(jīng)過實驗可以得出, 軌跡a和軌跡c相似度更高, OWD 的相似性效果最差, STD 和MBR 實驗結(jié)果比較相近, LCSS 能夠更有效的區(qū)分軌跡間差別. 在軌跡時空相似性的應(yīng)用上效果更好. 相似性值低表示和其他同學(xué)共同軌跡較少, 有可能經(jīng)常一個人進(jìn)行各項活動, 或者是不善交際或者交友障礙, 所以較孤僻. 采取該類學(xué)生多日的軌跡數(shù)據(jù)進(jìn)行聚類分析, 如果軌跡相似性總是較低, 輔導(dǎo)員可以進(jìn)行排查尋訪了解學(xué)生心理動態(tài).

3 結(jié)束語

為了準(zhǔn)確地分析校園無線網(wǎng)絡(luò)數(shù)據(jù)中隱藏的社交關(guān)系親密度, 本文提出了改進(jìn)DBSCAN 時空聚類算法,運用LCSS 算法進(jìn)行軌跡間相似性度量. 該方法基于校園WiFi 的數(shù)據(jù)特點和特有的應(yīng)用場所, 結(jié)合時間空間信息, 整理出軌跡數(shù)據(jù), 通過改進(jìn)的DBSCAN 時空算法進(jìn)行聚類, 在聚類結(jié)果簇中提取出特征軌跡, 計算特征軌跡間相似值, 進(jìn)一步推測學(xué)生之間的社交關(guān)系,若發(fā)現(xiàn)可能孤僻的學(xué)生, 老師需要進(jìn)行排查和教育輔導(dǎo).聚類算法還可以應(yīng)用在停留活動區(qū)域人流量分析、出行距離統(tǒng)計分析、無線網(wǎng)絡(luò)吞吐量和在線時長聚類分析, 為制定人性化、智能化決策提供數(shù)據(jù)支撐. 最后,運用高校的真實數(shù)據(jù)進(jìn)行實驗驗證, 實驗結(jié)果表明, 改進(jìn)的DBSCAN 算法能夠提升聚類效果, 相似性度量效果更好, 在校園無線網(wǎng)絡(luò)的實際環(huán)境中有較好的效果,但是在DBSCAN 算法中增加時間和空間的維度, 運行時間還是不太理想, 將在以后的研究中改進(jìn)和完善.