基于遺傳算法改進的HMM聚類驗證方法研究

潘祥

摘 要：本文首先從NGSIM數據集中提取出自然行駛狀態下的加速度以及車頭時距的二維車輛運動數據。在K-means聚類分析后，為對聚類分析的準確性進行客觀評價，提出一種基于遺傳模型改進的HMM算法的車輛跟馳特性的驗證方法對該聚類方法的準確性進行驗證。實驗表明，該分類方法可以通過準確率來提供一種量化分類精度的標準以客觀的評價聚類方法的聚類精度。

關鍵詞：智能交通;車輛跟馳特性;遺傳算法;HMM

0 引言

近年來，交通領域發展迅猛，機動車駕駛人與機動車數量呈顯著增長的態勢，民用機動車保有量從2015年的16 284.45萬輛增長至2019年的25 387.2萬輛[1]，增幅近36%;機動車駕駛人從2015年的32 853.05萬人增至2018年的41 030.16萬人，增幅近20%。但于此統計中，追尾事故數量占到了總交通事故數量的50%，可見跟馳狀態下行車安全性是亟待研究的課題。

本文著重討論跟馳狀態下的聚類結果驗證問題。在聚類結果驗證方面，研究者俞立平通過對原始評價指標進行聚類，然后采用可行的多屬性評價方法進行評價并對評價結果進行二次聚類，最后根據評價結果聚類與原始指標聚類結果一致度的高低來選擇評價方法，優先選取聚類結果一致度最高的評價方法[2]。徐濤、謝繼文和楊國慶三位研究者通過選取分類簇的代表點并根據簇代表點及聚類算法的相似性定義度量聚類結果與外部數據的匹配程度后，根據匹配結果對聚類質量進行分析[3]。

聚類是一種無監督的學習方法，事先沒有任何先驗知識，因此需要一定的措施或方法對聚類結果進行有效性驗證及評價[4]。本文研究基于自然駕駛數據的車輛跟馳數據的聚類精度的驗證問題，提出一種基于遺傳算法改進HMM算法模型，通過模型輸出的車輛跟馳狀態系數的預測正確率以量化分析數據的聚類質量。

1 基本概念及理論

1.1 HMM聚類驗證算法

隱馬爾科夫模型是時間序列的概率模型，描述了由隱藏的狀態序列組成的一條馬爾科夫鏈和由其中的每一個狀態生成的觀測所構成的觀測序列。將該模型運用于跟馳狀態數據的聚類驗證中時，通過對固定步長的車頭時距數據以及加速度數據進行最大似然估計后，將獲得的跟馳狀態轉移矩陣和行駛狀態混淆矩陣視為分類簇特征的特征矩陣。

在獲得了分類簇特征的矩陣后，通過viterbi算法輸出相同步長的車頭時距預測序列以及車輛運動狀態預測序列。之后計算該預測序列的正確率，即可獲得量化評價值。

通常情況下，若分類簇分類越合理，則預測的正確率就會越高;相反，若分類不合理，則會出現多個車頭時距狀態概率相接近的情況，導致預測狀態序列出現較大的誤差。

1.2 HMM聚類驗證算法的改進

1.2.1 HMM聚類驗證算法存在的問題

1.1節所述的HMM聚類驗證算法中，在分類簇較少的情況下，若某個粗分類簇較大，則會出現大簇吃小簇的情況。即預測正確率無法反映出大簇分類較粗，未將數據特征進行細化分類的問題。由于HMM是基于定步長的車頭時距序列以及車輛運動狀態序列對分類簇的分類質量進行評估的。因此若步長較短，則易陷入局部最優;若步長較長，則會消耗大量硬件資源，僅可作為離線分析工具使用。因此，本文提出一種基于遺傳算法改進的HMM聚類驗證算法，克服HMM聚類驗證算法檢測失靈問題。

1.2.2 基于遺傳算法改進的HMM聚類驗證算法

遺傳算法是一種基于自然選擇、基因遺傳以及優勝劣汰的生物種群進化思想進行問題求解的啟發式優化算法。本次研究將通過遺傳算法對原有算法輸出的預測值進行優化，從而使得預測結果的可靠性更高。

在本研究的優化模型中，車頭時距狀態轉移矩陣、行駛狀態混淆矩陣的閾值隨機生成的m個數據進行浮點數編碼來作為遺傳算法的初始種群。

在適應度函數的選取上，跟馳數據分類簇以單個點距離簇中心的歐氏距離與簇內最大歐式距離的差值作為評價該數據在算法中的適應度。在車頭時距狀態轉移矩陣、行駛狀態混淆矩陣對應的隨機矩陣的適應度函數選取上，為克服局部最優問題，將m個步長的車頭時距狀態轉移矩陣和行駛狀態混淆矩陣的適應度函數進行擬合，以點到擬合曲線的距離作為評價各個矩陣適應度的標準。

基于遺傳算法優良的全局尋優能力，在搜尋行駛狀態混淆矩陣以及車頭時距狀態轉移矩陣的最優解時，優化了原有算法易陷入局部最優以及步長過長的問題，使得預測結果能更加準確的對聚類結果進行評價。

2 實驗對比分析

將5個駕駛員數據以50的定步長輸入到HMM模型以及改進HMM模型中，同時引用鄧恩指數對三個聚類結果進行客觀評價，鄧恩指數越大，該次聚類質量越高。評價結果如表1所示。

由表1可知，本文建立的基于遺傳算法改進的HMM跟馳特性狀態聚類結果量化評價算法符合客觀評價指標，改善了原有HMM算法存在的低K值下評價可靠性低的缺陷。通過該實驗證明了改進后的HMM模型相較于未改進的HMM模型更為優異。

3 結論

本文提出一種基于HMM的車輛跟馳特性聚類結果驗證方法，可對車輛跟馳數據的聚類分析結果進行量化評估，并通過遺傳算法對其易陷入局部最優以及對粗聚類評估失效的缺陷進行了改進。實驗結果表明，改進后的HMM算法可對粗聚類進行準確的評估，與其他聚類評估方法結果保持一致。

參考文獻：

[1]中國國家統計局，2019年年度數據[DB/OL].https：//data.stats.gov.cn/easyquery.htm？cn=C01，2019.

[2]俞立平.基于聚類分析的期刊多屬性評價方法選擇研究——聚類結果一致度篩選法[J].圖書情報工作，2018，62（21）：80-86.

[3]徐濤，謝繼文，楊國慶.一種基于層次聚類的機場噪聲數據挖掘方法[J].南京航空航天大學學報，2013，45（5）：715-721.

[4]Shtern M，Tzerpor V.Refining clustering evaluation using structure indicators[C]. International Confer-ence on Software Maintenance. Edmonton，Alberta Canada：ICSM，2009：297-305.