基于k-means 的自然駕駛軌跡聚類研究

倪思齊 江浩斌 尹晨輝 沈青原

江蘇大學 汽車與交通工程學院 江蘇省鎮江市 212013

1 引言

inD 數據集包含了城市交叉口處大量的自然駕駛軌跡數據，為研究人類在交叉口處的駕駛特性提供了數據支撐。然而inD 數據集并沒有標注出車輛軌跡的轉向類型，例如左轉、右轉、直行等。為了進一步開展針對不同轉向類型的車輛軌跡擬合與軌跡預測研究，需要對數據集中車輛軌跡進行聚類。本文首先對inD 數據集中車輛軌跡的轉向類型進行了人工標注。其次，設置了不同的k-means參數進行軌跡聚類，并將聚類結果與人工標注結果做對比，通過聚類正確度指標分析了不同參數對聚類結果正確性的影響，并對參數進行了優化。最后采用優化后的參數對inD數據集中部分車輛軌跡進行了聚類。

2 車輛軌跡的人工標注

2.1 人工標注流程

為了評價車輛軌跡聚類結果的正確性，將數據集中車輛軌跡的類別進行了人工標注。inD 數據集共包括4 個城市交叉口場景，共32 個子數據集。本文選取了場景2（如圖1所示）中的4 個子數據集進行人工標注及軌跡聚類研究。由于本文只研究乘用車（car）軌跡特征，因此僅保留數據集中乘用車的軌跡。具體流程如下：

（1）剔除數據集中行人（pedestrian）、自行車（bicycle）與商用車（truck_bus）的軌跡。

（2）剔除靜止車輛與違章駕駛車輛的軌跡。

（3）將十字交叉口處的車道按逆時針順序依次標記（A 至J），如圖1 所示。根據車輛駛入、駛出車道，將轉向類型分為共計12類，如表1 所示。表中字母的順序表示車輛行駛方向，例如AB表示車輛從A車道駛入交叉口，并從B 車道駛出。

圖1 車道標記

（4）根據車輛ID 的橫、縱坐標，使用Matlab 畫出所選部分數據集中的車輛軌跡，比對圖1 中車輛駛入、駛出車道，在inD 子數據集文件中標入車輛軌跡的轉向類型。

2.2 分類與統計結果

該十字路口處的車輛軌跡統計結果如表1所示。由統計結果得知，AD 與FI 兩類直行軌跡占總軌跡數的59%，而CD、CG、CI、EB 與HB 的軌跡各自占比不足1%。

表1 車輛軌跡統計結果

續表1

3 k-means 超參數優化

3.1 性能參數

本文使用Matlab 中 的k-means 工具箱對車輛軌跡進行聚類。研究過程中發現，k-means 算法的中心初始化次數（Replicates）、距離度量標準（Distance）和中心初始化方法[1]（Start）對聚類結果有不同程度的影響。

在k-means 聚類過程中，多次選取初始中心點可以有效減少中心點位置選取的隨機性對聚類結果的影響。其中，Cluster 方法是在聚類初始階段，隨機挑選總樣本的10%作為子樣本，使用層次法聚類后再挑選由聚類生成的k 個簇中心作為初始質心，并開始聚類。uniform 方法則在所有樣本點中先任意挑選一個點，然后根據樣本點的分布范圍均勻生成k 個質心，再逐一選擇離這些質心距離最遠的點作為后繼質心，直至選取完畢。較cluster 而言，uniform 在一定程度上能夠降低樣本空間密度不一致對聚類中心初始化的影響。

k-means 距離度量標準中的歐氏距離（sqeuclidean）衡量的是空間各點的絕對距離，與樣本點所在位置的坐標直接相關；而余弦相似度（cosine）、衡量的是空間向量的夾角，更能體現樣本點在方向上的差異[1，2]。

3.2 超參數優化

本文采用控制變量法，在保持一個參數不變的前提下，研究另一參數的變化對k-means聚類正確度及程序運行時間的影響。其中，軌跡聚類正確度采用聚類外部評價指標[3，4]PI（純 度）、FI（F 值）、RI（Rand指數）與ARI（改進Rand 指數）來量化；其值越接近1，聚類正確度越高。

（1）控制距離度量使用sqeuclidean、中心初始化方法選擇uniform 不變，將中心初始化次數分別設置為10、40、70 與100。軌跡聚類效果及其正確度如圖2 和表2 所示，程序運行時間如圖3 所示。由圖2、圖3 及表2 可知，隨著中心初始化次數的增加，雖然程序運行時間有所增加，但是軌跡聚類正確度有一定提升。因此，選取100 作為中心初始化次數。

圖2 不同中心初始化次數下的車輛軌跡聚類效果

圖3 不同Replicates 值下的聚類時間

表2 不同中心初始化次數下的聚類正確度

（2）控制uniform 作為聚類的中心初始化方法不變，分別使用歐氏距離與余弦相似度對軌跡聚類4 次。各自的聚類效果、程序運行時間如圖4 與圖5 所示，聚類正確度如表3 的第二行與第三行所示。由圖4 及表3可知，采用歐氏距離時總體聚類效果較好，但余弦相似度對直行軌跡兩側的轉彎軌跡聚類效果較好。由于inD 數據集中直行軌跡數量的占比大于50%，其聚類正確度對總體聚類正確度的影響較大。又由圖5 得知，使用歐氏距離聚類的程序運行時間較短。綜合考慮后，使用歐氏距離作為k-means 中的距離度量，對車輛軌跡進行聚類。

圖4 不同距離度量標準下的車輛軌跡聚類效果

圖5 不同距離度量標準下的聚類時間

（3）控制歐氏距離作為聚類的距離度量標準不變，分別使用uniform 與cluster 對軌跡聚類4 次。結果顯示，使用uniform 聚類的程序運行平均時間為44.7s，小于使用cluster 聚類的程序運行平均時間47.1s。各自的程序運行時間、聚類效果與聚類正確度如圖6、圖7 與表3 的第三行與第四行所示。綜合考慮程序運行時間與聚類正確度，在保持歐氏距離作為距離度量不變的前提下，使用uniform 作為中心初始化方法。

圖6 不同中心初始化方法下的聚類時間

圖7 不同中心初始化方法下的車輛軌跡聚類效果

表3 不同參數的聚類正確度

4 研究結果

使用k-means 對inD 數據集進行軌跡聚類，優化后的參數為：中心初始化方法選擇uniform，距離度量方法選擇sqeuclidean，中心初始化次數設置為100。其它參數為：聚類中心為12。該參數設置下的聚類效果如圖8，結果顯示車輛直行軌跡與大部分轉彎軌跡的聚類正確度較高。聚類正確度分別為：PI=95.9%，FI=94.5%，RI=97.6%，ARI=93.8%。

圖8 優化后的聚類效果

5 結論

本文使用了k-means 對inD 數據集中十字交叉口處的部分車輛軌跡進行了聚類。根據人工標注的車輛軌跡轉向類型，使用控制變量法研究了k-means 在不同參數下的聚類正確度與程序運行效率，得出了較優的參數設置，并對車輛軌跡進行了聚類。該工作為后續進行基于轉向類型的車輛軌跡擬合與軌跡預測提供了便捷。同時，inD 數據集中部分轉向工況車輛軌跡數據量較少，聚類效果不是很理想，需要進一步改進k-means聚類方法以提高轉向工況下車輛軌跡的聚類正確度。