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

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

江蘇大學(xué) 汽車與交通工程學(xué)院 江蘇省鎮(zhèn)江市 212013

1 引言

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

2 車輛軌跡的人工標(biāo)注

2.1 人工標(biāo)注流程

為了評(píng)價(jià)車輛軌跡聚類結(jié)果的正確性，將數(shù)據(jù)集中車輛軌跡的類別進(jìn)行了人工標(biāo)注。inD 數(shù)據(jù)集共包括4 個(gè)城市交叉口場(chǎng)景，共32 個(gè)子數(shù)據(jù)集。本文選取了場(chǎng)景2（如圖1所示）中的4 個(gè)子數(shù)據(jù)集進(jìn)行人工標(biāo)注及軌跡聚類研究。由于本文只研究乘用車（car）軌跡特征，因此僅保留數(shù)據(jù)集中乘用車的軌跡。具體流程如下：

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

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

（3）將十字交叉口處的車道按逆時(shí)針順序依次標(biāo)記（A 至J），如圖1 所示。根據(jù)車輛駛?cè)?、駛出車道，將轉(zhuǎn)向類型分為共計(jì)12類，如表1 所示。表中字母的順序表示車輛行駛方向，例如AB表示車輛從A車道駛?cè)虢徊婵冢腂 車道駛出。

圖1 車道標(biāo)記

（4）根據(jù)車輛ID 的橫、縱坐標(biāo)，使用Matlab 畫出所選部分?jǐn)?shù)據(jù)集中的車輛軌跡，比對(duì)圖1 中車輛駛?cè)?、駛出車道，在inD 子數(shù)據(jù)集文件中標(biāo)入車輛軌跡的轉(zhuǎn)向類型。

2.2 分類與統(tǒng)計(jì)結(jié)果

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

表1 車輛軌跡統(tǒng)計(jì)結(jié)果

續(xù)表1

3 k-means 超參數(shù)優(yōu)化

3.1 性能參數(shù)

本文使用Matlab 中 的k-means 工具箱對(duì)車輛軌跡進(jìn)行聚類。研究過程中發(fā)現(xiàn)，k-means 算法的中心初始化次數(shù)（Replicates）、距離度量標(biāo)準(zhǔn)（Distance）和中心初始化方法[1]（Start）對(duì)聚類結(jié)果有不同程度的影響。

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

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

3.2 超參數(shù)優(yōu)化

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

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

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

圖3 不同Replicates 值下的聚類時(shí)間

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

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

圖4 不同距離度量標(biāo)準(zhǔn)下的車輛軌跡聚類效果

圖5 不同距離度量標(biāo)準(zhǔn)下的聚類時(shí)間

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

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

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

表3 不同參數(shù)的聚類正確度

4 研究結(jié)果

使用k-means 對(duì)inD 數(shù)據(jù)集進(jìn)行軌跡聚類，優(yōu)化后的參數(shù)為：中心初始化方法選擇uniform，距離度量方法選擇sqeuclidean，中心初始化次數(shù)設(shè)置為100。其它參數(shù)為：聚類中心為12。該參數(shù)設(shè)置下的聚類效果如圖8，結(jié)果顯示車輛直行軌跡與大部分轉(zhuǎn)彎軌跡的聚類正確度較高。聚類正確度分別為：PI=95.9%，F(xiàn)I=94.5%，RI=97.6%，ARI=93.8%。

圖8 優(yōu)化后的聚類效果

5 結(jié)論

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