蔡小路,曹 陽,董 蒲

(華南師范大學(xué) 計(jì)算機(jī)學(xué)院,廣州 510631)

隨著帶有定位模塊的智能終端使用量的增加,移動(dòng)對象位置數(shù)據(jù)的獲取變得越來越普遍.而軌跡數(shù)據(jù)能夠反映移動(dòng)對象的部分隱藏信息[1],通過識(shí)別軌跡中的隱藏信息加入語義信息,可以得到體積較小、質(zhì)量較高、便于理解的帶有語義信息的軌跡.將原始軌跡轉(zhuǎn)換為語義軌跡為目的地位置預(yù)測[2]、城市道路的規(guī)劃[3]、充電樁分布的規(guī)劃[4]、動(dòng)物習(xí)性的調(diào)查[5]等提供了解決方法.因此,對軌跡數(shù)據(jù)進(jìn)行語義轉(zhuǎn)換的需求將會(huì)變得越來越大.Alvares,Bogorny 等人[6]提出了一種將原始軌跡轉(zhuǎn)換為語義軌跡的模型,模型得到了廣泛的應(yīng)用[7-9].模型先將物體的移動(dòng)路徑切分為“停留點(diǎn)(stop)”和“移動(dòng)點(diǎn)(move)”兩部分,再將停留點(diǎn)與地理信息庫相匹配為停留點(diǎn)附上地理背景信息,然后將這些帶有地理信息的停留點(diǎn)按照時(shí)間先后順序排列后即為語義軌跡.因此,原始軌跡轉(zhuǎn)換為語義軌跡的關(guān)鍵是如何準(zhǔn)確識(shí)別出原始軌跡中的停留點(diǎn)或停留域.

目前關(guān)于軌跡停留點(diǎn)識(shí)別的算法大致可以兩大類:靜態(tài)方法和動(dòng)態(tài)方法[10].Alvares,Bogorny 等人[11]提出挖掘原始的軌跡數(shù)據(jù)中的語義信息是理解這些數(shù)據(jù)的前提,認(rèn)為?？奎c(diǎn)是軌跡集合中具有重要意義的子序列集合,將軌跡與預(yù)先定義好的重要位置的交集視為?？奎c(diǎn).靜態(tài)算法的主要缺點(diǎn)是用戶需要指定有意義的位置.因此,如果事先沒有定義一些有意義的特殊位置,靜態(tài)方法就無法識(shí)別出停留點(diǎn)信息[12].而動(dòng)態(tài)停留點(diǎn)識(shí)別方法則不需要事先知道停留點(diǎn)或停留域位置,也可以發(fā)現(xiàn)停留點(diǎn)位置.Ashbrook,Starner 等人[13]對傳統(tǒng)的K-Means算法進(jìn)行改進(jìn)來提取出軌跡中有意義的點(diǎn).方法要求首先選取一個(gè)初始中心點(diǎn)并定義覆蓋半徑,將中心點(diǎn)覆蓋半徑內(nèi)的點(diǎn)進(jìn)行標(biāo)記并計(jì)算這些點(diǎn)的均值點(diǎn).將均值點(diǎn)作為新的中心重復(fù)上述操作,直到中心點(diǎn)不再變化,將上述標(biāo)記的點(diǎn)視為一個(gè)停留域.然后從未被標(biāo)記的點(diǎn)中選擇一個(gè)初始中心點(diǎn)進(jìn)行新的停留域的篩選,直到所有點(diǎn)都被標(biāo)記.K-Means算法的K 值和初始中心點(diǎn)的選取是重要問題,選取不當(dāng)會(huì)導(dǎo)致最終的結(jié)果產(chǎn)生很大的誤差.Zhou,Frankowski 等人[14]提出了名為DJ-Cluster 的基于密度和連接的算法,算法核心思想是:計(jì)算每一個(gè)點(diǎn)的一定距離(EPS)內(nèi)的鄰域點(diǎn).當(dāng)點(diǎn)的數(shù)量小于MinPts 時(shí)將其標(biāo)記為噪聲.鄰域點(diǎn)數(shù)目大于MinPts 時(shí),鄰域不屬于任何一個(gè)已知停留點(diǎn)類時(shí)則將其標(biāo)記為一個(gè)新的停留點(diǎn)類,反之合并到所屬類中.基于密度聚類的停留點(diǎn)識(shí)別算法可以克服K-Means算法的缺陷,但是僅考慮了軌跡的空間特征而忽略了時(shí)序性.Hwang,Evans[15]提出了一種“自上而下”的光柵采樣方法,該方法采用預(yù)先定義的GPS 采集器進(jìn)行數(shù)據(jù)收集,將具有顯著區(qū)分值的光柵單元作為停留點(diǎn)進(jìn)行聚類.Palma,Bogorny[16]提出了CB-SMoT(基于聚類的停止和軌跡移動(dòng))算法來提取已知和未知的停留點(diǎn).CB-SMoT算法是一種考慮了時(shí)間和空間特征的基于密度的聚類算法,通過選取速度比速度閾值慢的點(diǎn)來生成停留點(diǎn).Zhao,Xu[17]指出[16]中估計(jì)參數(shù)Eps 適當(dāng)值的分位數(shù)函數(shù)并不能穩(wěn)定地確定參數(shù)的適當(dāng)閾值.因此提出了一種改進(jìn)的CB-SMoT算法,提出了一種計(jì)算EPS 參數(shù)的方法,但由于需要用戶區(qū)分低速部分和高速部分,計(jì)算起來仍然困難.Yan,Parent[18]在CB-SMoT 的基礎(chǔ)上加入最短停留時(shí)間參數(shù)來過濾掉“偽停留點(diǎn)”(例如,短期低速擁堵不應(yīng)是一個(gè)停留點(diǎn)).Lv,Chen[19]提出了一種層次聚類算法,首先從GPS 軌跡中提取訪問點(diǎn),然后對這些訪問點(diǎn)進(jìn)行聚類形成停留域.Chen,Ji[20]針對GPS 點(diǎn)的時(shí)間序列特性,提出了一種改進(jìn)的基于密度的聚類算法T-DBSCAN,并定義了兩個(gè)新的前提條件(單停留域內(nèi)的狀態(tài)連續(xù)性和停留點(diǎn)間的時(shí)間間斷性)作為調(diào)整聚類中軌跡點(diǎn)選擇的理論基礎(chǔ).Yang,Li[21]將Eps 坐標(biāo)系劃分為網(wǎng)格單元.通過遍歷數(shù)據(jù)集,每個(gè)數(shù)據(jù)點(diǎn)根據(jù)其經(jīng)度、緯度和時(shí)間分量被分配到相應(yīng)的網(wǎng)格單元.再計(jì)算每個(gè)網(wǎng)格單元內(nèi)的數(shù)據(jù)點(diǎn)數(shù)量,將網(wǎng)格點(diǎn)數(shù)大于MinPts 的單元標(biāo)記為核心網(wǎng)格單元.從核心網(wǎng)格單元出發(fā),采用廣度優(yōu)先遍歷策略搜索其相鄰的核心網(wǎng)格,并將最大的相鄰核心網(wǎng)格單元集標(biāo)記為停留點(diǎn)簇.

然而上述方法無法有效地分辨出移動(dòng)目標(biāo)是從建筑物穿過還是在建筑內(nèi)有過停留這一問題,也不能合理地設(shè)置時(shí)間閾值來聚類缺失記錄點(diǎn).當(dāng)移動(dòng)目標(biāo)于某一地理位置產(chǎn)生活動(dòng)時(shí),速度會(huì)低于整條軌跡的平均速度.針對這一物理特性和前文論述的研究缺陷,本文提出了一種改進(jìn)的停留點(diǎn)識(shí)別框架:先確定軌跡中的缺失子軌跡,再按缺失軌跡的平均速度對缺失軌跡進(jìn)行插值,然后采用基于速度的時(shí)空聚類方法來識(shí)別軌跡中的停留點(diǎn).

1 基于速度特征的軌跡停留點(diǎn)識(shí)別算法

1.1 軌跡預(yù)處理

由于移動(dòng)目標(biāo)物體會(huì)在不同的場景中移動(dòng),場景的不同導(dǎo)致采集到的軌跡數(shù)據(jù)特點(diǎn)也會(huì)不同.當(dāng)行人進(jìn)入建筑物內(nèi)時(shí),因?yàn)樾盘?hào)受到遮擋,無法收集到理想的數(shù)據(jù).用戶軌跡進(jìn)入建筑物可以分為兩種情況:在建筑物內(nèi)有停留和穿過建筑物.停留點(diǎn)識(shí)別算法應(yīng)正確地識(shí)別出前者而過濾掉后者.當(dāng)距離一定時(shí),停留時(shí)間越長,該軌跡段內(nèi)的按時(shí)記錄的點(diǎn)的密度越大;而對于穿過建筑物情景而言,用戶的移動(dòng)速度不存在劇烈變化.

因此針對前文描述的數(shù)據(jù)缺失或偏差等情況,采用插值法對缺失軌跡的記錄點(diǎn)進(jìn)行填充:將缺失軌跡前后兩端點(diǎn)的時(shí)間差作為缺失時(shí)間,兩點(diǎn)間的距離作為缺失軌跡的缺失距離.因?yàn)閱误w建筑范圍一般小于200×200 m2,且為了防止前條軌跡結(jié)束點(diǎn)與后一軌跡的起始點(diǎn)小于設(shè)定的缺失距離而導(dǎo)致兩條軌跡因?yàn)椴逯祵?dǎo)致合并造成最終的提取結(jié)果產(chǎn)生偏差,所以對缺失軌跡通過缺失時(shí)間的大小來進(jìn)行區(qū)別.當(dāng)缺失軌跡的缺失距離小于200 m,缺失時(shí)間小于2 小時(shí),缺失軌跡的前后兩條軌跡視為同一條軌跡.將缺失時(shí)間與軌跡記錄點(diǎn)時(shí)間間隔的比值視為缺失點(diǎn)的數(shù)目,將缺失距離按缺失數(shù)目等距插值填充,然后采用卡爾曼濾波器對填充后的整條軌跡進(jìn)行平滑處理得到最終的實(shí)驗(yàn)數(shù)據(jù)集.

1.2 停靠點(diǎn)識(shí)別算法

本文在ST-DBSCAN算法的基礎(chǔ)上提出了基于軌跡速度的密度聚類算法(V-DBSCAN,Velocity-Based DBSCAN).對于經(jīng)過預(yù)處理后的軌跡點(diǎn),采用以下步驟進(jìn)行處理:1)使用時(shí)間閾值和速度閾值對實(shí)際軌跡點(diǎn)進(jìn)行篩選,生成候選停留點(diǎn)鄰域.2)沿候選停留點(diǎn)鄰域的時(shí)間軸將其相鄰點(diǎn)數(shù)大于密度閾值的點(diǎn)進(jìn)行聚類,得到最終停留點(diǎn).具體算法見算法1.

?

如算法1 所示,算法首先根據(jù)軌跡點(diǎn)的加速度、相鄰軌跡速度范圍和速度持續(xù)時(shí)間等特征將軌跡切分成速度相近的子軌跡段,再依次對子軌跡進(jìn)行停留點(diǎn)識(shí)別.識(shí)別算法首先計(jì)算子軌跡點(diǎn)集合Traj 的半徑閾值Eps(算法詳情見算法2),再計(jì)算Traj 的整體平均速度(Mspeed).Traj 中所有點(diǎn)的初始狀態(tài)為未標(biāo)記狀態(tài),從起始記錄點(diǎn)開始,按記錄點(diǎn)時(shí)間順序依次對每一個(gè)點(diǎn)進(jìn)行篩選過濾.如果當(dāng)前點(diǎn)(pi)處于未標(biāo)記狀態(tài),則調(diào)用retrieve_neighbor 函數(shù),retrieve_neighbors 函數(shù)根據(jù)Eps、T 和Mspeed 三個(gè)條件閾值,從Traj 中篩選出pi的所有滿足條件的相鄰點(diǎn).如算法3 所示,函數(shù)依次根據(jù)時(shí)間、距離和速度三個(gè)條件篩選出pi半徑閾值(Eps)范圍內(nèi)速度小于Mspeed*e 且與pi的時(shí)間間隔小于時(shí)間閾值(T)的軌跡點(diǎn).結(jié)果集則是pi的候選停留點(diǎn)鄰域.若pi的候選停留點(diǎn)鄰域中軌跡點(diǎn)的數(shù)量小于minPs,將pi標(biāo)記為噪點(diǎn),反之則將pi與其鄰域用類ID 進(jìn)行標(biāo)記.然后再按時(shí)間順序迭代地對pi鄰域中未被標(biāo)記的點(diǎn)進(jìn)行篩選,直到Traj 中所有點(diǎn)都被標(biāo)記.

計(jì)算Traj 空間半徑閾值Eps的函數(shù)spatial_threshold 如算法2 所示.本方法是受文獻(xiàn)[22]提出的R N N-D B S C A N算法啟發(fā)而得出的,在R N NDBSCAN算法中通過計(jì)算每個(gè)目標(biāo)的k 最近鄰近點(diǎn),建立所有目標(biāo)的k 鄰近點(diǎn)索引表來進(jìn)行密度聚類.在spatial_ threshold 中,先求出每一個(gè)點(diǎn)與其他任一點(diǎn)的地球球面距離,篩選距離最短的k 個(gè)值放入all_kth_distances 中,再求得all_kth_distances 的平均值,返回均值.

?

從原始軌跡點(diǎn)中篩選候選停留點(diǎn)集的過程為:對連續(xù)的兩個(gè)時(shí)刻內(nèi)的運(yùn)動(dòng)狀態(tài)進(jìn)行判斷,當(dāng)pk與pi的時(shí)間差小于時(shí)間閾值T,則對兩點(diǎn)間的距離進(jìn)行判斷,若距離小于半徑閾值,且pk的速度小于速度閾值Mspeed*e (0＜e＜1),則將pk添加到pi的鄰域點(diǎn)集中,并計(jì)算下一點(diǎn)是否為pi的鄰域點(diǎn),直到所有點(diǎn)篩選完畢.具體方法如算法3 所示.

?

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

為了評估 V-DBSCAN算法的有效性,本章節(jié)將其與ST-DBSCAN算法[23]在提取的停留點(diǎn)的數(shù)目和準(zhǔn)確度方面進(jìn)行實(shí)驗(yàn)比較.實(shí)驗(yàn)數(shù)據(jù)集共兩組:第一組數(shù)據(jù)集為GeoLife 數(shù)據(jù)集中user ID=20 的用戶的所有軌跡數(shù)據(jù),采樣點(diǎn)間隔為5 s,共177 683 個(gè)記錄點(diǎn),用于驗(yàn)證算法的提取能力,下文稱數(shù)據(jù)一;第二組是志愿者收集的帶有停留點(diǎn)標(biāo)記的軌跡數(shù)據(jù),采樣時(shí)間間隔為2 s,共14 479 個(gè)記錄點(diǎn),用于驗(yàn)證提取到的停留點(diǎn)的準(zhǔn)確性,下文稱數(shù)據(jù)二;兩組數(shù)據(jù)集的屬性都相同,包有時(shí)間戳、經(jīng)緯度、海拔基本信息.軌跡數(shù)據(jù)基本信息如表1 所示.

表1 軌跡數(shù)據(jù)點(diǎn)基本信息表

2.1 參數(shù)設(shè)定

為了防止不恰當(dāng)?shù)膮?shù)設(shè)定造成最終結(jié)果的偏差,本節(jié)探索參數(shù)對結(jié)果的影響,并確定最終的對比實(shí)驗(yàn)的參數(shù).此處的實(shí)驗(yàn)數(shù)據(jù)集為另一志愿者室外步行狀態(tài)下的軌跡點(diǎn),時(shí)間間隔(t)為2 s,共12 797 個(gè)軌跡記錄點(diǎn).整條軌跡含26 個(gè)人工記錄的停留點(diǎn).

如表2 所示,經(jīng)過多輪實(shí)驗(yàn)探索得出:時(shí)間閾值設(shè)為30 倍的記錄點(diǎn)時(shí)間間隔(例如間隔2 s 記錄一個(gè)點(diǎn)的情況下,時(shí)間閾值設(shè)為60 s),密度閾值設(shè)為1.5 倍的時(shí)間閾值大小,即45 倍的記錄點(diǎn)時(shí)間間隔時(shí),提取出的停留點(diǎn)數(shù)最接近實(shí)際情況.

表2 參數(shù)對結(jié)果的影響

2.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)一測試兩種算法在相同時(shí)間、半徑閾值,各個(gè)密度閾值下,對軌跡中停留點(diǎn)的提取能力,采用數(shù)據(jù)一作為實(shí)驗(yàn)數(shù)據(jù)來進(jìn)行對比驗(yàn)證.時(shí)間閾值設(shè)為30 倍的記錄時(shí)間間隔,密度閾值設(shè)為記錄時(shí)間間隔的45 倍,密度閾值下為0.75 倍軌跡平均速度.從圖1 中可以看出相同的實(shí)驗(yàn)參數(shù)下,V-DBSCAN算法提取的停留點(diǎn)數(shù)都要大于ST-DBSCAN算法.這是因?yàn)槟繕?biāo)用戶在實(shí)際移動(dòng)中往往存在兩個(gè)或多個(gè)停留點(diǎn)相隔較近的情況,此種情景下停留點(diǎn)間的移動(dòng)點(diǎn)的數(shù)量會(huì)非常少.當(dāng)ST-DBSCAN算法的半徑閾值設(shè)置過大或密度閾值設(shè)置過小時(shí),就會(huì)將停留點(diǎn)間的移動(dòng)點(diǎn)也劃分到停留點(diǎn)中,導(dǎo)致相近的兩個(gè)或多個(gè)停留點(diǎn)被識(shí)別為一個(gè)停留點(diǎn).針對停留點(diǎn)間的移動(dòng)點(diǎn)的瞬時(shí)速度大于兩邊停留點(diǎn)的瞬時(shí)速度這一物理特征,V-DBSCAN算法對軌跡點(diǎn)速度進(jìn)行篩選,只有當(dāng)軌跡點(diǎn)的速度小于設(shè)置的速度閾值時(shí)才將該點(diǎn)進(jìn)行后續(xù)的篩選,因此可以對地理距離相隔較近的多個(gè)停留點(diǎn)進(jìn)行很好的劃分.因此在識(shí)別停留點(diǎn)的提取能力上V-DBSCAN算法要強(qiáng)于ST-DBSCAN算法.

圖1 停留點(diǎn)提取數(shù)量對比

實(shí)驗(yàn)二測試兩種算法對軌跡中停留點(diǎn)的提取能力,采用數(shù)據(jù)二作為實(shí)驗(yàn)數(shù)據(jù)來進(jìn)行對比驗(yàn)證(T=60 s,MinPts=90,e=0.75).兩者的對比實(shí)驗(yàn)結(jié)果如圖2 所示,其中黑色大圓點(diǎn)為V-DBSCAN算法的結(jié)果,白色小圓點(diǎn)為ST-DBSCAN算法的結(jié)果.

圖2 停留點(diǎn)準(zhǔn)確性對比

從圖2 中可以看出,當(dāng)僅考慮對停靠點(diǎn)的提取能力時(shí),V-DBSCAN 相對于ST-DBSCAN 提取出更多的?？奎c(diǎn),例如圖中A、B 兩點(diǎn).其中A、B 兩點(diǎn)的原始軌跡數(shù)據(jù)由于建筑物的遮擋而缺失,所以未改進(jìn)的STDBSCAN算法無法識(shí)別出這兩停留點(diǎn).因?yàn)閷τ赟TDBSCAN算法的時(shí)間閾值T 范圍內(nèi)可能存在多個(gè)停留點(diǎn),這是ST-DBSCAN算法參數(shù)不能基于軌跡特征來設(shè)定導(dǎo)致的缺陷.為此本文中提出了基于速度的密度聚類方法,在ST-DBSCAN算法的基礎(chǔ)上考慮軌跡點(diǎn)速度來提取停留點(diǎn),極大改善了ST-DBSCAN算法對停留點(diǎn)提取不完全的問題.

3 總結(jié)

本文針對空間軌跡停留點(diǎn)提取過程中的軌跡點(diǎn)缺失和半徑閾值難以確定等問題,提出了基于軌跡點(diǎn)速度的密度聚類算法.由于傳統(tǒng)的基于密度的聚類方法將軌跡的時(shí)間和空間兩個(gè)屬性分開來進(jìn)行考慮,忽略了兩者之間的聯(lián)系.V-DBSCAN 的設(shè)計(jì)是通過對一定范圍內(nèi)的缺失軌跡點(diǎn)進(jìn)行插值填充再根據(jù)速度和時(shí)間來篩選出軌跡中的停留點(diǎn).試驗(yàn)結(jié)果表明,相對于STDBSCAN,V-DBSCAN 一方面被證明具有更好的軌跡聚類能力.另一方面,V-DBSCAN 可以自動(dòng)計(jì)算出軌跡的Eps半徑距離,減少了人為設(shè)定參數(shù)的不確定性.但是,時(shí)間閾值和密度閾值仍然要人為設(shè)定.在后續(xù)的研究中會(huì)考慮本算法對多用戶的多條軌跡提取停靠點(diǎn)的處理能力,并根據(jù)不同用戶的?？奎c(diǎn)計(jì)算多個(gè)用戶間的用戶相似性.