蔡小路,曹 陽,董 蒲

(華南師范大學 計算機學院,廣州 510631)

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

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

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

1 基于速度特征的軌跡停留點識別算法

1.1 軌跡預處理

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

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

1.2 停靠點識別算法

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

?

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

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

?

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

?

2 實驗分析

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

表1 軌跡數(shù)據點基本信息表

2.1 參數(shù)設定

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

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

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

2.2 實驗結果

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

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

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

圖2 停留點準確性對比

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

3 總結

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