基于集成聚類的交叉口車輛行駛路徑提取方法

尹 卓 許 甜 陳陽舟 盧佳程

1(北京工業大學北京市交通工程重點實驗室 北京 100124)2(中交第一公路勘察設計研究院有限公司 陜西 西安 710075)3(北京工業大學人工智能與自動化學院 北京 100124)

0 引 言

軌跡數據的聚類是監控場景中目標行為分析的一項具有挑戰性的基礎工作。針對交叉口場景而言，車輛的行駛軌跡聚類對于交叉口的安全評估具有重要的意義。例如，基于車輛行駛軌跡聚類提出不同行駛路徑，可用于分析車輛事故的碰撞方式，評估事故發生的風險程度等。交叉口的車輛軌跡數據通常來自交通監控視頻中車輛的識別與跟蹤。雖然交叉口車輛的運動行為受到交通規則的限制，具有很強的規律性，但是基于機器學習的車輛軌跡聚類卻面臨著很大的挑戰性。首先，交叉口場景非常容易發生遮擋，導致軌跡不連續的現象發生；其次，對于軌跡聚類而言，由于監控場景視野的緣故，聚類與聚類之間的區別不明顯，使得在相似位置具有相似特性的軌跡可能對應于不同的聚類[1]，甚至兩個聚類的軌跡數據會存在重疊的現象；最后，交叉口的車輛常常出現的停止行為使軌跡存在大量的停止點，從而導致軌跡的冗余現象。針對交叉口場景設計車輛軌跡聚類算法，并在此基礎上獲取穩定的場景路徑信息已成為具有挑戰性的研究熱點。

各種監控場景下路徑提取的基礎是運動目標的軌跡聚類，軌跡聚類主要分為三種方式。第一種聚類方式為基于軌跡的空間相似性。早期的代表性工作由Morris等[2-3]和Zhang等[4]完成，他們將軌跡聚類問題轉化為時間序列聚類問題，并使用序列相似性距離度量(如LCSS距離等)計算軌跡之間的距離。基于軌跡相似度，采用各種聚類算法對軌跡進行聚類。例如，Morris等[3]針對DTW和LCSS等距離度量應用于模糊C-means聚類算法的效果進行了實驗對比，總結了相關算法的特點與優勢。Kim等[5]針對城市級別的GPS軌跡數據進行分析，使用DBSCAN聚類算法對軌跡進行聚類。他們采用LCSS距離來評估軌跡的相似性，然后借助DBSCAN中的核心點的定義，提出了聚類代表(CRS)提取算法，并在聚類代表的基礎上合并相似的軌跡聚類。基于比較的聚類算法往往能夠取得較好的效果[3]，但是其缺點是時間與空間復雜度較高。Lee等[6]基于最小描述長度原則(MDL)設計了軌跡分段算法。他們對軌跡先根據關鍵點進行分段，再對分段軌跡進行聚類。由于分段軌跡的距離度量采用了針對線段的朝向角度以及垂直距離與平行歐式距離度量，該算法本質上也是基于距離的聚類方式。

第二種聚類方式主要基于統計特征。早期的代表性工作中，Li等[7]提出采用軌跡距離直方圖(TDH)對軌跡進行描述，其中軌跡點的轉向角被投射到了方向直方圖中，因此形成了對軌跡方向的統計特征表示；Anjum等[8]拓展了相關的特征，提出了軌跡數據的一系列統計特征，并使用Mean-shift算法對軌跡進行了聚類。基于統計特征的軌跡數據聚類往往能夠以較低的時間復雜度獲得較為穩定而優良的聚類效果，但是軌跡的統計特征忽略了軌跡數據的時空相關性，因此聚類效果往往不如基于相似度的軌跡聚類效果。

第三種聚類方式是在軌跡建模之后再利用模型對軌跡進行分析。文獻[9]使用高斯混合模型與隱馬爾可夫模型對軌跡進行建模，然后對軌跡進行聚類。文獻[10]則利用狄利克雷過程對軌跡進行分類與聚類，算法可以被拓展到實時方式，但是這種聚類方式的缺點在于其效果通常受到模型參數初值的影響。

在上述針對監控場景的車輛軌跡聚類方法中，缺乏對基于空間軌跡相似度比較的方法與基于統計特征的軌跡聚類方法進行集成，以發揮各自的優勢。因此，為了獲取更具魯棒性的聚類結果，獲取場景的路徑信息，本文提出基于集成聚類的交叉口路徑信息挖掘方法，通過融合不同聚類方式獲取交叉口場景的路徑信息。首先，對基于軌跡統計特征的聚類方法與基于距離度量的聚類方法進行集成，獲得了更具魯棒性的軌跡聚類結果；其次，針對軌跡相似度矩陣引入拉普拉斯中心性[11]，并對每一個聚類的聚類原型進行提取，消除了噪聲軌跡對聚類原型提取的影響；最后，引入深度優先搜索算法對聚類原型相似度鄰接矩陣的連通子圖進行搜索，合并冗余的聚類，生成場景的路徑信息。使用獲取的路徑信息，可以進一步對軌跡進行分類或者異常檢測等。

1 相關概念與數據預處理

圖1 軌跡數據網格化實例，深色區域被標定為停止區域

(1)

2 軌跡特征提取與距離度量

2.1 軌跡數據的直方圖描述

如圖2所示，軌跡的方向角度被分為了8份，每一個網格上的角度被分配到了統計圖上。

圖2 軌跡數據角度直方圖

對于pij而言，若(m-1)Δα≤aij

(2)

便可以得到軌跡方向落在第Im區間內的頻率，并且得到一個長度為α的一個軌跡方向向量。

2.2 軌跡形狀特征

(3)

而軌跡的復雜度定義為：

(4)

式中：ci取值在0到1的范圍內。不同于文獻[3]，這里軌跡的復雜度計算使用了壓縮后的軌跡的復雜度計算。文獻[3]采用原始軌跡對軌跡復雜度進行計算，但是在存在大量停止點的情況下，利用原始軌跡計算移動總距離會受到冗余的停止點的影響，因此此處采用網格軌跡計算車輛行駛的距離，可以防止停止點對于計算的干擾。

前面從軌跡的朝向和形狀兩個角度給出了軌跡的特征提取方法，還提取了軌跡的以下特征：軌跡的起點與終點坐標[xi1,yi1]與[xiTi,yiTi]，軌跡x與y坐標的分布特征[μix,σix]與[μiy,σiy]等。由于這里使用的都是完整的軌跡，自然軌跡的起點與終點對于軌跡聚類的判別有一定的幫助，不同起點與終點的軌跡對應于不同的運動模式。

2.3 軌跡相似度

(1) 邊界條件：路徑的起點位于(pi1,pj1)，終點位于(piTi,pjTj)。

(2) 漸進性條件：路徑上的每一個軌跡點滿足條件：pi1≤…≤pik≤…≤piTi，pj1≤…≤pjl≤…≤pjTj。

(3) 步長條件：當位于(pik,pjl)點時，路徑的下一步坐標在{(pi(k+1),pjl),(pik,pj(l+1)),(pi(k+1),pj(l+1))}集合內。這意味著每次路徑只能沿著時間順序移動一步。

條件(3)可以被放松為移動多步[14]，這通常意味著DTW對于噪聲的軌跡點具有更強的魯棒性。假設這里存在一條累積損失值最小的路徑f*，而DTW距離被定義為：

DTW(Traji,Trajj)=sum(f*)

(5)

即DTW距離的值為滿足三個條件的累積損失值最小的一條路徑的累積損失值。

圖3為數據集中兩條軌跡的損失矩陣的熱力圖。顏色越深，則兩個坐標點之間的歐式距離越近。而最優的DTW距離的值為滿足前面條件的累積損失最小的一條路徑對應的累積損失值，也就是白色的路徑。類似于DTW距離的度量方式還有LCSS距離、Frechet距離、編輯距離等。

圖3 DTW距離在損失矩陣中的最優路徑

3 路徑提取算法

3.1 軌跡的集成聚類策略

現有的一系列研究中，對于交叉口場景的軌跡聚類可以粗略地分為基于統計特征聚類[7-8，14]的軌跡聚類方法與基于比較的軌跡聚類方法[5-6，9]，這些方法有各自的優缺點。為了提升聚類的魯棒性，獲取更高質量的聚類，本節采用兩類方法融合的集成聚類策略，即對基于特征的聚類與基于軌跡相似度的聚類進行了集成。

記聯合相關矩陣為S，矩陣的元素為：

(6)

式中：

(7)

可以看出，聯合相關矩陣元素的取值范圍在0到1之間，其生成過程如圖5所示。

圖5 聯合相關矩陣生成

(8)

式中：

(9)

(10)

(11)

(12)

權重wn的定義為：

wn=ECI(clsn(Traji))

(13)

基于軌跡相似性的聚類采用譜聚類方法進行。譜聚類[15]是一種基于圖的聚類算法，其思想是基于結點的相似度構建鄰接矩陣與拉普拉斯矩陣，然后優化基于拉普拉斯矩陣的損失函數[15]。以DTW距離為例，首先構建軌跡數據的鄰接矩陣A：

Aij=e-DTW(Traji,Trajj)/2ζ2

(14)

針對軌跡特征的聚類，本文采用層次聚類算法。其優點在于對于非凸聚類也能取得優異的結果，缺點是時間復雜度較高。當進行特征聚類時，軌跡形狀特征與軌跡方向直方圖(TDH)描述的特征被組合以后進行聚類。其中，軌跡的形狀特征需要進行Min-Max歸一化后，才能送入到聚類算法中進行聚類。例如，對于第i條軌跡的復雜度di表示為：

(15)

在進行歸一化以后，就可以對歸一化以后的特征進行聚類，從而獲取特征聚類的結果。

獲取了加權聯合相關矩陣之后，任意一種聚類算法都可以被用來對集成以后的結果進行聚類。本文仍然采用譜聚類對軌跡集成結果進行聚類，其中加權聯合相關矩陣作為譜聚類的鄰接矩陣。最后一步采用譜聚類，一方面是因為譜聚類能夠應對非凸聚類問題，另一方面，Liu等[20]提出的針對聯合相關矩陣的譜聚類通過特征編碼的方式將問題轉換為加權K-means聚類問題，從而在保證同等質量的前提下降低了時間復雜度。在完成最后一步的譜聚類后，可以獲得Nc個軌跡聚類。

3.2 獲取聚類原型

在集成聚類之后，訓練數據中的每一條軌跡都將擁有聚類標簽，但是這些軌跡聚類的數目與實際路徑的數目不一致。主要原因在于在不同場景中，并不知道真實的路徑個數Nr，只能保證指定的聚類數目Nc>>Nr，即聚類可能存在冗余。為此，需要對聚類后的軌跡進行進一步處理，以獲得場景中實際的路徑數目Nr。

軌跡聚類的合并分為兩步:(1) 針對每一個聚類的軌跡，提取該軌跡的聚類原型，聚類原型為該聚類中最具有代表性的軌跡。(2) 利用聚類原型將相似的聚類合并，從而得到場景的路徑信息。

在聚類原型提取中，一般選取同一聚類的平均軌跡作為聚類的代表，即聚類原型。軌跡的平均需要將聚類內的軌跡進行插值得到等長軌跡才能進行。Morris等[9]借助插值的策略提取了平均軌跡，并基于平均軌跡間的DTW距離對聚類進行了合并。以平均軌跡作為聚類原型會帶來兩個問題：(1) 聚類不可避免地會包含少量的噪聲軌跡或是分類錯誤的軌跡，若是該聚類樣本數目比較小，則會對平均軌跡的質量產生較大的影響；(2) 平均法對軌跡的平移，伸縮變換不具有魯棒性。Paparrizos等[16]討論了針對時間序列聚類中的聚類中心提取問題，提出若是對時間序列進行時間方向的平移或是伸縮變換，則平均的時間序列將不具有穩定性，這里針對軌跡也是一樣的效果。針對這些問題，本文引入圖的拉普拉斯能量的思想[11]，對聚類原型進行提取。

圖G的拉普拉斯能量：給定圖G的鄰接矩陣A和度矩陣D，計算拉普拉斯矩陣L=D-A，則圖G的拉普拉斯能量定義為：

(16)

式中：λ1,λ2,…,λM是拉普拉斯矩陣的特征值。

圖G的節點vi的拉普拉斯中心性：給定圖G，刪除連接節點vi的所有邊之后的圖記為Gi，則給定節點vi∈G的拉普拉斯中心性hi定義為：

(17)

3.3 路徑生成

Kij=I(Edit(Pi,Pj)≥ηe)

(18)

式中：I(·)代表指示函數；Edit(Pi,Pj)代表編輯距離[22]。采用編輯距離是因為編輯距離能夠被很好地歸一化到0到1的區間，方便ηe的取值。在獲取矩陣K之后，使用深度優先搜索對連通子圖進行搜索，屬于同一子圖的聚類將被合并在一起，并重新根據軌跡屬于路徑的情況提取聚類原型。本文ηe的取值為0.9，代表聚類原型之間至少有90%的點匹配時，才將二者進行合并，這也意味著給定嚴格的合并條件能取得魯棒的效果。

4 實驗分析

4.1 實驗環境與數據集

針對所提出的方法，采用西安市2個交叉口的軌跡數據進行實驗分析。實驗環境為Ubuntu 18.04 LTS系統，處理器為Intel Xeon(R) E3-1230v3，內存20 GB，軟件平臺使用到了基于Python的Anaconda集成環境。數據集的相關特性如表1所示。

表1 兩個軌跡數據集基本信息

圖6與圖7顯示了兩個場景中提取的路徑，可以看出場景具有非常復雜的運動模式。其中數據集JYGY采集于早高峰8點到9點左右，場景擁有24條路徑；HJDS數據集包含28條路徑。實驗的評估標準采用的是V-measure[17]。V-measure是一種基于熵的聚類質量度量，取值范圍在0到1之間。并且使用V-measure需要預先知道樣本的聚類標簽與真實類標簽，V-measure值越高越好。

圖6 JYGY數據集路徑(24條路徑)

圖7 HJDS數據集路徑(28條路徑)

4.2 軌跡集成聚類效果

針對軌跡數據集成聚類的效果進行實驗。首先對數據集分別進行基于特征的聚類與基于距離度量的聚類，從而生成一系列的基聚類。每個方法聚類的數目從30個一直到50個，所以生成的基聚類的組數N=40。這樣保證了各個聚類的數目Nc大于場景潛在的路徑數目Nr。在獲得基聚類之后，利用所有獲得的基聚類，參照式(12)構建了加權聯合相關矩陣，并運用譜聚類對其進行聚類，獲取了集成聚類的類標簽。對于集成聚類而言，其聚類的數目從30個變化到50個，方便與之前的結果進行對比。并且針對基于距離度量的聚類算法與基于特征的聚類算法也進行了集成，用以驗證集成聚類的效果并非只受到單一聚類方式集成的影響。

圖8是聚類數目從30變化到50的時候，各組方法的V-measure分數的變化情況。可以看出，單獨使用結合DTW距離的譜聚類時，其聚類效果并不穩定，隨著聚類個數的變化聚類分數發生波動，這主要是由于對于鄰接矩陣的高斯核參數調整不當造成的。但是對其進行集成聚類之后，其聚類效果與穩定性都有大幅的提升，這也說明聚類集成能夠提升聚類質量。就聚類分數而言，軌跡的特征工程配合層次聚類的方法取得的結果最為穩定，隨著聚類數目的變化，其V-measure分數沒有發生太大的波動。但是事實上該方法在設計損失函數時，沒有對聚類包含的樣本數目進行約束，因此容易受到噪聲的影響從而切分出單條軌跡作為聚類，并且由于前者的原因，基聚類之間的差異性也較低，導致集成結果不明顯。對于兩種方法結合的集成聚類算法，在聚類效果上與基于特征的集成結果類似，但是其集成后分數的穩定性高，并在部分指定聚類數目下超越了之前的所有方法。

(a) JYGY數據集聚類結果

(b) HJDS數據集聚類結果圖8 兩個數據集的聚類結果

集成聚類對低質量聚類的加入也具有較高的魯棒性。圖9是通過調整超參數，降低譜聚類分數之后得到的集成的結果。可以看到在譜聚類結果的質量較低的情況下，集成的結果仍然保持了非常高的準確性，表明二者結合的集成策略具有較高的精度與魯棒性。

圖9 HJDS數據集聚類融合低質聚類的結果

4.3 路徑生成實驗

在獲取了軌跡的各個聚類之后，對各個聚類的聚類原型進行了提取。這里已經獲取了聚類的標簽，因此可以依據聚類標簽對實現進行譜聚類的鄰接矩陣A進行分解為子圖的鄰接矩陣，并按照式(17)，計算子圖每一結點的拉普拉斯中心性，選取中心性最高的軌跡作為聚類的聚類原型。

圖10與圖11分別為兩個場景下的任意5個軌跡聚類與其聚類原型。聚類原型通常為聚類最具代表性的軌跡，例如聚類的平均軌跡。若將每一條聚類中的軌跡視為圖中的一個節點，則聚類原型理應與聚類中其他節點之間的連接的權值之和低，一般來說，這樣的節點應當位于聚類的中心。由圖10與圖11可以看出，算法很好地找到了每一個聚類的中心，并抵御了噪聲軌跡的干擾。

圖10 JYGY數據集中的5個聚類與其聚類原型

圖11 HJDS數據集中的5個聚類原型

在獲取了各個軌跡聚類的聚類原型之后，便可以進行聚類原型的合并以獲得場景的路徑信息。為了對比集成方法對于場景路徑獲取的有效性，我們通過實驗對比了各個方法聚類合并的效果。具體而言，定義命中率(HR)與冗余率(RR)：

(19)

(20)

式(19)中:Nr代表場景實際路徑的數目，Nc代表聚類原型的數目，Nh代表Nc中能夠與場景實際路徑匹配的聚類原型的個數。判斷是否匹配的方式為對比合并以后的路徑與真實路徑的編輯距離是否小于預設閾值，這里閾值被設定為0.9以確保試驗結果的可靠性。HR∈[0,1]越高越好，RR代表合并以后剩余的或是缺失路徑的比率，越接近0越好。

表2是設定不同數據集、聚類方法與聚類數目的條件下，路徑合并后的命中率與冗余率情況。其中集成聚類字樣代表路徑的提取方式為先進行集成聚類，從集成聚類的結果中提取聚類原型，然后進行聚類合并的操作，以下簡稱為集成方式；帶有特征聚類或是距離字樣的聚類方式和前述相似，只是獲取聚類的手段是之前提到的基于特征的聚類和基于距離度量的聚類方式，以下分別簡稱為距離方式與特征方式。

表2 不同聚類數目，不同數據集下的路徑提取命中率(HR)/冗余率(RR)

從結果上來看，就路徑提取的命中率而言，集成方式與距離方式具有相似的命中率；而特征方式V-measure的分數較高，但是由于忽略了軌跡的時序特性，導致對于路徑的提取效果不論是命中率還是冗余率都不如前兩種方式。而在JYGY數據集上，經典方式提取的命中率高于集成方式，但是冗余率遠高于集成方式，若是考慮低冗余和高命中的話，本文的集成聚類具有較強的優勢。

5 結 語

本文提出了一種基于集成聚類的交叉口路徑信息挖掘方法。利用基于距離度量的譜聚類算法與基于特征的層次聚類算法的集成，對軌跡進行聚類；針對軌跡的相似性鄰接矩陣，引入了拉普拉斯中心性的思想提取了聚類的中心結點。在多個數據集實驗中，本文提出的聚類方法具有較強的魯棒性與較高的精度。在提取路徑的實驗中，在不降低命中率前提下本文方法具有較低的冗余率。但是，其在時間復雜度方面有待進一步改進。