基于遗传算法改进的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.