基于遺傳算法改進(jìn)的HMM聚類驗證方法研究

潘祥

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

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

0 引言

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

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

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

1 基本概念及理論

1.1 HMM聚類驗證算法

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

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

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

1.2 HMM聚類驗證算法的改進(jìn)

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

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

1.2.2 基于遺傳算法改進(jìn)的HMM聚類驗證算法

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

在本研究的優(yōu)化模型中，車頭時距狀態(tài)轉(zhuǎn)移矩陣、行駛狀態(tài)混淆矩陣的閾值隨機(jī)生成的m個數(shù)據(jù)進(jìn)行浮點數(shù)編碼來作為遺傳算法的初始種群。

在適應(yīng)度函數(shù)的選取上，跟馳數(shù)據(jù)分類簇以單個點距離簇中心的歐氏距離與簇內(nèi)最大歐式距離的差值作為評價該數(shù)據(jù)在算法中的適應(yīng)度。在車頭時距狀態(tài)轉(zhuǎn)移矩陣、行駛狀態(tài)混淆矩陣對應(yīng)的隨機(jī)矩陣的適應(yīng)度函數(shù)選取上，為克服局部最優(yōu)問題，將m個步長的車頭時距狀態(tài)轉(zhuǎn)移矩陣和行駛狀態(tài)混淆矩陣的適應(yīng)度函數(shù)進(jìn)行擬合，以點到擬合曲線的距離作為評價各個矩陣適應(yīng)度的標(biāo)準(zhǔn)。

基于遺傳算法優(yōu)良的全局尋優(yōu)能力，在搜尋行駛狀態(tài)混淆矩陣以及車頭時距狀態(tài)轉(zhuǎn)移矩陣的最優(yōu)解時，優(yōu)化了原有算法易陷入局部最優(yōu)以及步長過長的問題，使得預(yù)測結(jié)果能更加準(zhǔn)確的對聚類結(jié)果進(jìn)行評價。

2 實驗對比分析

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

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

3 結(jié)論

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

參考文獻(xiàn)：

[1]中國國家統(tǒng)計局，2019年年度數(shù)據(jù)[DB/OL].https：//data.stats.gov.cn/easyquery.htm？cn=C01，2019.

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

[3]徐濤，謝繼文，楊國慶.一種基于層次聚類的機(jī)場噪聲數(shù)據(jù)挖掘方法[J].南京航空航天大學(xué)學(xué)報，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.