1、AUTO TIME 181 TRAFFIC AND SAFETY|交通与安全基于 k-means 的自然驾驶轨迹聚类研究倪思齐江浩斌尹晨辉沈青原江苏大学汽车与交通工程学院 江苏省镇江市 212013摘 要：使用 k-means 聚类方法对 Intersection Drone Dataset（inD）自然驾驶数据集中的部分车辆轨迹进行了聚类分析。首先，根据车辆的驶入、驶出车道，对轨迹数据的转向类型进行了人工标注，为评价轨迹聚类算法的正确度奠定基础。其次，根据 k-means 聚类正确度与程序运行效率，分析并优化了聚类算法参数。最后，采用优化参数后的 k-means 对车辆轨迹进行了聚类，结果显
2、示轨迹聚类正确度达到 95.4%。关键词：轨迹聚类k-means参数优化1引言inD 数据集包含了城市交叉口处大量的自然驾驶轨迹数据，为研究人类在交叉口处的驾驶特性提供了数据支撑。然而 inD 数据集并没有标注出车辆轨迹的转向类型，例如左转、右转、直行等。为了进一步开展针对不同转向类型的车辆轨迹拟合与轨迹预测研究，需要对数据集中车辆轨迹进行聚类。本文首先对 inD 数据集中车辆轨迹的转向类型进行了人工标注。其次，设置了不同的 k-means参数进行轨迹聚类，并将聚类结果与人工标注结果做对比，通过聚类正确度指标分析了不同参数对聚类结果正确性的影响，并对参数进行了优化。最后采用优化后的参数对 in
3、D数据集中部分车辆轨迹进行了聚类。2车辆轨迹的人工标注2.1人工标注流程为了评价车辆轨迹聚类结果的正确性，将数据集中车辆轨迹的类别进行了人工标注。inD 数据集共包括 4 个城市交叉口场景，共32 个子数据集。本文选取了场景 2（如图 1所示）中的 4 个子数据集进行人工标注及轨迹聚类研究。由于本文只研究乘用车（car）轨迹特征，因此仅保留数据集中乘用车的轨迹。具体流程如下：（1）剔除数据集中行人（pedestrian）、自行车（bicycle）与商用车（truck_bus）的轨迹。（2）剔除静止车辆与违章驾驶车辆的轨迹。（3）将十字交叉口处的车道按逆时针顺序依次标记（A 至 J），如图 1
4、所示。根据车辆驶入、驶出车道，将转向类型分为共计12类，如表 1 所示。表中字母的顺序表示车辆行驶方向，例如AB表示车辆从A车道驶入交叉口，并从 B 车道驶出。图 1车道标记（4）根据车辆 ID 的横、纵坐标，使用Matlab 画出所选部分数据集中的车辆轨迹，比对图 1 中车辆驶入、驶出车道，在 inD 子数据集文件中标入车辆轨迹的转向类型。2.2分类与统计结果该十字路口处的车辆轨迹统计结果如表 1所示。由统计结果得知，AD 与 FI 两类直行轨迹占总轨迹数的 59%，而 CD、CG、CI、EB 与 HB 的轨迹各自占比不足 1%。分类ABADCDCGCIEB数量32096614占比(%)0.
5、427.10.80.80.10.5表 1车辆轨迹统计结果分类FGFIHIHBHDJG数量852464937666占比(%)11.031.96.30.49.88.5续表 13k-means 超参数优化3.1性能参数本 文 使 用 Matlab 中 的 k-means 工具箱对车辆轨迹进行聚类。研究过程中Natural Driving Trajectory Clustering based on K-meansNi SiqiJiang HaobinYin ChenhuiShen QingyuanAbstract：The k-means clustering method is used to cl
6、uster a part of vehicle trajectories in the Intersection Drone Dataset(inD)-a naturalistic driving dataset.Firstly,according to the entry and exit of the vehicle,the maneuver type of the trajectory data is manually labeled,which lays a foundation for evaluating the correctness of the trajectory clus
7、tering algorithm.Secondly,according to the accuracy and efficiency of k-means clustering,the parameters of the clustering algorithm are analyzed and optimized.Finally,the vehicle trajectories are clustered by k-means after parameter optimization,and the results show that the accuracy of trajectory c
8、lustering reaches up to 95.4%.Key words：trajectory clustering,k-means,parameter optimization182 AUTO TIMETRAFFIC AND SAFETY|交通与安全发 现，k-means 算 法 的 中 心 初 始 化 次 数（Replicates）、距离度量标准（Distance）和中心初始化方法1（Start）对聚类结果有不同程度的影响。在 k-means 聚类过程中，多次选取初始中心点可以有效减少中心点位置选取的随机性对聚类结果的影响。其中，Cluster 方法是在聚类初始阶段，随机挑选总样本的
9、 10%作为子样本，使用层次法聚类后再挑选由聚类生成的 k 个簇中心作为初始质心，并开始聚类。uniform 方法则在所有样本点中先任意挑选一个点，然后根据样本点的分布范围均匀生成 k 个质心，再逐一选择离这些质心距离最远的点作为后继质心，直至选取完毕。较 cluster 而言，uniform 在一定程度上能够降低样本空间密度不一致对聚类中心初始化的影响。k-means 距离度量标准中的欧氏距离（sqeuclidean）衡量的是空间各点的绝对距离，与样本点所在位置的坐标直接相关；而余弦相似度（cosine）、衡量的是空间向量的夹角，更能体现样本点在方向上的差异1,2。3.2超参数优化本文采用控
10、制变量法，在保持一个参数不变的前提下，研究另一参数的变化对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 可知，随着中心初始化次数的增加，虽然程序运行时间有所增加，但是轨迹聚类正确
11、度有一定提升。因此，选取 100 作为中心初始化次数。评价指标(%)PIFIRIARIReplicates1096.593.194.597.84096.293.795.197.67096.494.295.297.910096.494.395.598.2表 2不同中心初始化次数下的聚类正确度（2）控制 uniform 作为聚类的中心初始化方法不变，分别使用欧氏距离与余弦相似度对轨迹聚类 4 次。各自的聚类效果、程序图 3不同 Replicates 值下的聚类时间Replicates484644424038360204060中心初始化次数80100程序运行时间(s)图 2不同中心初始化次数下的车辆
12、轨迹聚类效果（c）Replicates=70 （d）Replicates=100（a）Replicates=10 （b）Replicates=400000-10-10-10-10-20-20-20-20-30-30-30-30-40-40-40-40-50-50-50-50-60-60-60-60303030304040404050505050606060607070707080808080（a）欧氏距离 （b）余弦相似度图 4不同距离度量标准下的车辆轨迹聚类效果00-10-10-20-20-30-30-40-40-50-50-60-60303040405050606070708080AUTO
13、 TIME 183 TRAFFIC AND SAFETY|交通与安全运行时间如图 4 与图 5 所示，聚类正确度如表 3 的第二行与第三行所示。由图 4 及表 3可知，采用欧氏距离时总体聚类效果较好，但余弦相似度对直行轨迹两侧的转弯轨迹聚类效果较好。由于 inD 数据集中直行轨迹数量的占比大于 50%，其聚类正确度对总体聚类正确度的影响较大。又由图 5 得知，使用欧氏距离聚类的程序运行时间较短。综合考虑后，使用欧氏距离作为 k-means 中的距离度量，对车辆轨迹进行聚类。（3）控制欧氏距离作为聚类的距离度量标准不变，分别使用 uniform 与 cluster 对轨迹聚类 4 次。结果显示，
14、使用 uniform 聚类的程序运行平均时间为 44.7s，小于使用cluster 聚类的程序运行平均时间 47.1s。各自的程序运行时间、聚类效果与聚类正确度如图 6、图 7 与表 3 的第三行与第四行所示。综合考虑程序运行时间与聚类正确度，在保持欧氏距离作为距离度量不变的前提下，使用uniform 作为中心初始化方法。评价指标(%)PIFIRIARI距离度量欧氏距离95.994.597.693.8余弦相似度93.867.491.361.7初始化方法uniform95.994.597.693.8cluster95.784.993.683.2表 3不同参数的聚类正确度4研究结果使用 k-mea
15、ns 对 inD 数据集进行轨迹聚类，优化后的参数为：中心初始化方法选择uniform，距离度量方法选择 sqeuclidean，中心初始化次数设置为 100。其它参数为：聚类中心为 12。该参数设置下的聚类效果如图 8，结果显示车辆直行轨迹与大部分转弯轨迹的聚类正确度较高。聚类正确度分别为：PI=95.9%，FI=94.5%，RI=97.6%，ARI=93.8%。5结论本文使用了 k-means 对 inD 数据集中十字交叉口处的部分车辆轨迹进行了聚类。根据人工标注的车辆轨迹转向类型，使用控 作者简介倪思齐：（2000.01），男，汉族，上海人，江苏大学车辆工程专业本科生。江浩斌：（1969
16、.10），男，汉族，江苏启东人，江苏大学车辆工程学科教授、博士生导师。尹晨辉：（1993.09），男，汉族，江苏盐城人，江苏大学车辆工程专业博士生。沈青原：（1995.12），男，汉族，江苏镇江人，江苏大学车辆工程专业博士生。图 5不同距离度量标准下的聚类时间图 6不同中心初始化方法下的聚类时间程序运行时间(s)uniformcluster40424446485052012聚类次数345程序运行时间(s)sqeuclideancosine7065554535012聚类次数345605040图 8优化后的聚类效果0-10-20-30-40-50-60304050607080图 7不同中心初始化方法下的车辆轨迹聚类效果（a）uniform （b）cluster00-10-10-20-20-30-30-40-40-50-50-60-60303040405050606070708080制变量法研究了 k-means 在不同参数下的聚类正确度与程序运行效率，得出了较优的参数设置，并对车辆轨迹进行了聚类。该工作为后续进行基于转向类型的车辆轨迹拟合与轨迹预测提供了便捷。同时，inD 数据集中部分转向
