任柏寒, 丁雪梅, 孫士龍

(1. 吉林建筑科技學院 交通工程學院, 長春 130114； 2. 白山市互聯(lián)網(wǎng)信息中心 輿情科, 吉林 白山 134300)

0 引 言

隨著社會生活水平的發(fā)展, 汽車保有量不斷攀升, 造成道路資源服務(wù)增長與車輛增長之間嚴重失衡, 從而使交通擁堵等交通問題變得越來越嚴重。而隨著信息化的發(fā)展, 使實時記錄車輛的軌跡信息變?yōu)榭赡? 為解決交通問題提供了新的契機。例如可以利用手機基站位置、 公交數(shù)據(jù)形成的交通軌跡數(shù)據(jù), 分析城市職住關(guān)系和通勤出行[1-2]、 個體活動規(guī)律[3]和城市空間結(jié)構(gòu)[4]等。

聚類是一種將數(shù)據(jù)歸類劃分的技術(shù)方法[5], 可以廣泛應(yīng)用于交通數(shù)據(jù)處理等方面。陳繼東等[6]將道路網(wǎng)絡(luò)的邊和結(jié)點信息作為特征數(shù)據(jù)對象進行聚類。袁冠等[7]根據(jù)轉(zhuǎn)角分割得到軌跡段, 然后計算軌跡段結(jié)構(gòu)相似系數(shù), 完成軌跡聚類。王金鳳等[8]基于道路網(wǎng)絡(luò)的移動對象聚類算法 MOBORN(Moving Objects Based on Road Network), 考慮了不同時刻對象的移動速度、 方向和位置參數(shù), 在此基礎(chǔ)上計算網(wǎng)絡(luò)距離和不同時刻的空間相似度, 確定時空相似系數(shù), 當移動對象間的時空相似系數(shù)達到給定閾值時, 將其分到同一類。Won等[9]提出一種計算運動物體之間軌跡相似性的方法, 將運動物體軌跡間的相似性定義為兩個軌跡間非重疊部分長度與兩個軌跡的總長度之比。該計算方法僅考慮了軌跡間的空間相似性, 并未考慮兩軌跡之間的時間相似性。Chen等[10]基于Hausdorff距離思想, 根據(jù)路網(wǎng)中路段距離計算兩軌跡之間的距離, 雖在計算軌跡間空間方面上更有效, 但該方法未考慮軌跡間的時間信息。Hwang等[11]首先通過過濾階段在道路路網(wǎng)中發(fā)現(xiàn)路網(wǎng)距離, 然后根據(jù)時間距離細化前一階段對數(shù)據(jù)進行預處理, 然后進行軌跡聚類從而發(fā)現(xiàn)相似的軌跡。Chang等[12]利用道路網(wǎng)中移動物體軌跡之間的時間相似性和空間相似性的均值和乘積度量軌跡間的時空相似性。Abraham等[13]找出并根據(jù)軌跡中的興趣位置點和時間點, 計算出移動對象軌跡間的時空相似性。

基于以往的研究可得知軌跡相似性不僅依賴于形狀, 而且還依賴于時間。為實現(xiàn)區(qū)域車輛軌跡聚類, 筆者通過分析交叉口車輛軌跡時空信息并計算時空相似系數(shù), 由于文中的車輛數(shù)據(jù)有較多的空值, 部分信息丟失或不完全, 這屬于稀疏數(shù)據(jù), 所以采用譜聚類將相似的數(shù)據(jù)聚集在一個類簇中, 繼而可視化展示車輛軌跡在環(huán)形交叉口區(qū)域一段時間內(nèi)的軌跡聚類情況。根據(jù)聚類情況繼而發(fā)現(xiàn)車輛軌跡之間共同特征, 從而為實現(xiàn)車輛管控、 軌跡異常檢測、 交通擁堵的發(fā)現(xiàn)等應(yīng)用奠定基礎(chǔ)。

1 時空相似系數(shù)

軌跡相似系數(shù)是聚類的基礎(chǔ), 通過相似系數(shù)確定軌跡之間的關(guān)系, 再利用軌跡相似系數(shù)對軌跡進行聚類。因此, 筆者從時間維度和空間維度兩方面入手, 利用杰卡德相似系數(shù)(Jaccard Similarity Coefficient)計算兩條軌跡上的時間相似系數(shù)； 以兩條軌跡上的車輛在任意相同時間點上的平均距離為標準獲取兩條軌跡的距離, 繼而用高斯過程求出距離相似系數(shù)。然后用時間相似系數(shù)乘以距離相似系數(shù)求得兩條軌跡間的時空相似系數(shù), 以實現(xiàn)軌跡聚類。

1.1 時間相似系數(shù)

結(jié)合在環(huán)形交叉口區(qū)域經(jīng)緯度范圍, 定義任意在區(qū)域內(nèi)的車輛k的軌跡如下

(1)

(2)

根據(jù)式(2)可得到環(huán)形交叉口區(qū)域任意兩車輛軌跡之間的時間相似系數(shù)

(3)

1.2 距離相似系數(shù)

根據(jù)環(huán)形交叉口區(qū)域兩車輛軌跡所處的時間交集段, 以采樣時間間隔Δt劃分軌跡子段, 計算各個劃分軌跡子段的距離。然后求得時間交集段各個劃分軌跡子段的距離的平均值, 作為計算的軌跡距離, 再采用高斯過程轉(zhuǎn)化得到環(huán)形交叉口區(qū)域兩車輛軌跡的距離相似系數(shù)。

1.2.1 軌跡子段距離

通過假設(shè)環(huán)形交叉口區(qū)域兩車輛軌跡在采樣時間間隔Δt內(nèi), 兩車輛的速度穩(wěn)定, 不發(fā)生突變, 即認為兩車輛在采樣時間間隔Δt內(nèi)勻速運行。采樣時間間隔Δt內(nèi)兩車輛的軌跡子段分別記為L1:p(1)→p(1)′, L2:p(2)→p(2)′, 相對運動軌跡記為ΔL: Δp→Δp′, 其中Δp=p(2)-p(1); Δp′=p(2)′-p(1)′。令d=Δp+α(Δp′-Δp), 其中d為相對運動軌跡ΔL上的位置點,α的范圍是： 0≤α≤1。綜上, 軌跡子段L1,L2的距離如下

(4)

令α=(Δp′-Δp)T(Δp′-Δp),b=2ΔpT(Δp′-Δp),c=ΔpTΔp, 可得到dist(L1,L2)如下所示

(5)

1.2.2 軌跡距離

截取軌跡L(k1),L(k2)時間交集段的兩車輛的軌跡L′(k1),L′(k2)如下

(6)

(7)

通過式(7)可計算出任意時間交集段的兩車輛的軌跡距離如下

(8)

1.2.3 距離相似系數(shù)

利用高斯過程計算出兩軌跡距離的相似系數(shù)

(9)

其中σ為高斯過程標準參數(shù)。

1.3 時空相似度系數(shù)

將時間相似系數(shù)矩陣與距離相似系數(shù)矩陣進行Hadamard乘積運算, 表示對應(yīng)位置元素相乘。求得軌跡相似系數(shù)矩陣

S=T⊙G

(10)

2 基于譜聚類的軌跡聚類

譜聚類算法在聚類過程中只需要數(shù)據(jù)之間的相似度矩陣, 因此可以有效處理稀疏數(shù)據(jù)聚類的情況。同時譜聚類算法使用了降維處理, 對高維數(shù)據(jù)進行聚類時, 其復雜程度優(yōu)于傳統(tǒng)聚類算法。故選取了譜聚類算法進行軌跡聚類。聚類算法步驟如下：

1) 計算時空相似系數(shù)矩陣S的每行元素值之和構(gòu)成對角度矩陣D;

2) 計算拉普拉斯矩陣

S′=D-S

(11)

3) 采用

Lsym=D-1/2S′D-1/2

(12)

得到對稱標準化拉普拉斯矩陣Lsym;

4) 計算矩陣Lsym的前k個最大特征值, 并從大到小組成向量g∈Rk×1, 相應(yīng)的特征向量排成矩陣U∈Rm×k, 其中U的第i列為第i大特征值對應(yīng)的特征向量；

5) 根據(jù)K-means聚類算法將矩陣U的行向量聚成k類, 所聚類結(jié)果即為譜聚類結(jié)果。

3 實例驗證

3.1 數(shù)據(jù)預處理

由于觀測數(shù)據(jù)中包含系統(tǒng)噪聲和干擾, 故采用卡爾曼濾波(Kalman Filtering)方法對數(shù)據(jù)進行降噪處理。該方法通過輸入輸出觀測數(shù)據(jù), 在不確定性變化中尋求一種平衡, 對系統(tǒng)狀態(tài)進行最優(yōu)估計?？柭鼮V波方法的處理過程可分為預測模塊和更新模塊。

3.1.1 預測模塊

預測模塊主要通過當前時刻與上一時刻的關(guān)系, 實現(xiàn)對狀態(tài)的預測并且構(gòu)建狀態(tài)預測誤差的協(xié)方差矩陣。

1) 根據(jù)狀態(tài)轉(zhuǎn)移矩陣、 控制矩陣及上一時刻的狀態(tài)矩陣si對當前時刻狀態(tài)矩陣si+1的預測估計, 得到當前時刻狀態(tài)矩陣的估計值

(13)

(14)

其中Q為預測模型本身帶來的噪聲。

3.1.2 更新模塊

1) 根據(jù)預測狀態(tài)協(xié)方差矩陣P和觀測量的協(xié)方差矩陣W確定卡爾曼增益矩陣

(15)

式(15)中,λ為測量結(jié)果不信任指數(shù), 該值越高表示對相應(yīng)時刻的測量結(jié)果越不可信。根據(jù)車輛在短時間內(nèi)速度不會突變。確定不信任指數(shù)λ的計算如下

(16)

(17)

其中Zi∈R2×1為GPS實際觀測的車輛軌跡狀態(tài)矩陣。

(18)

圖1 在交叉口坐標平面中車輛軌跡數(shù)據(jù)預處理結(jié)果展示

3.1.3 數(shù)據(jù)預處理結(jié)果展示

以采集到的一條車輛軌跡的交叉口坐標數(shù)據(jù)為例, 進行了數(shù)據(jù)預處理, 處理結(jié)果如圖1所示。

3.2 相似度計算結(jié)果

為了避免雜亂的軌跡影響繪圖效果, 從數(shù)據(jù)庫中選取8條軌跡展示聚類效果。為檢驗聚類效果, 在環(huán)形交叉口中每個進口的軌跡數(shù)據(jù)中選取了不同數(shù)量的車輛軌跡, 其軌跡的方向如表1所示。

表1 車輛軌跡編號及其圖示

計算得到的時間相似系數(shù)矩陣

(19)

計算得到的距離相似系數(shù)矩陣

(20)

得到的時間相似系數(shù)矩陣imagesc如圖2所示。距離相似系數(shù)矩陣imagesc如圖3所示。根據(jù)式(11)得到標準化的拉普拉斯矩陣

(21)

可以得出如圖4所示的標準化的拉普拉斯矩陣imagesc圖。

圖2 時間相似系數(shù)矩陣imagesc圖 圖3 距離相似系數(shù)矩陣imagesc圖 圖4 標準化的拉普拉斯矩陣imagesc圖

圖5 聚類結(jié)果

4 聚類結(jié)果及結(jié)論

通過軌跡聚類得到的聚類效果如圖5所示。

Mou等[14]指出軌跡聚類的有效性評價需要更加深入研究, 故筆者只對聚類得到的可視化圖進行闡述。由圖5可以直觀看出, 可以將交叉口進口道的車輛軌跡聚類一起, 以區(qū)分不同交叉口進口道的軌跡。筆者所提出的基于GPS數(shù)據(jù)的車輛軌跡聚類算法具有一定的可行性, 為交通數(shù)據(jù)挖掘提供了一定的基礎(chǔ)。

5 結(jié) 語

筆者考慮環(huán)形交叉口車輛運行軌跡時間上和空間上的相似性, 構(gòu)建了時空相似系數(shù), 以此作為主要指標提出了車輛軌跡的譜聚類方法。通過法國克雷泰伊一環(huán)形交叉口GPS數(shù)據(jù)驗證, 筆者提出的方法能有效確定車輛進出交叉口路線、 環(huán)島交織段, 為避免車輛沖突科學渠化設(shè)計環(huán)形交叉口提供了重要依據(jù)。