基于改进K-Medoids的组合聚类算法及异常值检测研究

贺 玉 海， 周 庆 琨， 程 埮 晟， 王 勤 鹏*

( 1.武汉理工大学 船海与能源动力工程学院， 湖北 武汉 430063；2.武汉理工大学 船舶动力工程技术交通行业重点实验室， 湖北 武汉 430063；3.武汉理工大学 船舶与海洋工程动力系统国家工程实验室电控分实验室， 湖北 武汉 430063 )

0 引 言

随着社会经济与科技的快速发展，国民生活质量正在不断提高．汽车保有量的快速增长，虽然给人们带来了出行上的便利，但也给城市带来了日益严重的交通拥堵以及环境污染等问题．近年来，伴随着人工智能(AI)、机器视觉、物联(车辆)网、5G等大数据采集与传输技术的日益完善，可以对大量车辆行驶自然轨迹数据进行分析[1]，挖掘特征参数，帮助人们理解轨迹数据中隐含的规律与趋势，给城市道路交通管理与规划提供指导，对于缓解城市交通拥堵发挥了重要作用[2]．

聚类是挖掘轨迹数据最常用的手段之一[3-5]，轨迹聚类可以较为精确地识别目标轨迹的行为方式，并对于异常的噪声轨迹进行识别与剔除[6]．轨迹聚类一方面可以为研究如潮汐交通的内在规律提供帮助，为大车流的规划、控制提供决策性指导[7]；另一方面，对于无人驾驶汽车来说，异常轨迹的识别也可以降低事故发生的概率，提高安全性[8]．郝美薇等[9]提出一种改进的基于密度的K-Means算法．该算法基于轨迹数据增加轨迹数据关键点密度权值和分布密度选取高密度的轨迹数据点作为初始聚类中心进行K-Means聚类．张玉西等[10]提出一种改进主成分分析和基于密度的改进K-Means聚类组合方法，消除了K-Means算法对初始聚类中心的敏感性及噪声点的干扰．何月等[11]采用了一种基于网格的聚类算法，通过对出租车GPS轨迹数据进行处理和聚类分析，最后得到了出租车轨迹热力图并确定了出租车的运营规律．郭景华等[12]通过马尔可夫链蒙特卡罗模拟预测未来时刻的车辆状态，有效解决了不能准确表征前车人类驾驶员驾驶车辆随机运动的问题．

轨迹的相似性度量是轨迹聚类方法的基础，冯琦森[13]与Zheng等[14]基于最长公共子序列的轨迹相似度测量方法，并结合DBSCAN(density-based spatial clustering of application with noise)算法设计了一种可以识别居民出行热点路线的出租车轨迹数据聚类算法．马占宇[15]通过计算轨迹间的双向距离，提高了相似性计算的准确性，使其适用于从不等长的轨迹数据中提取热点．

异常轨迹检测作为轨迹聚类的目标，切实应用于日常的交通运输规划、智能汽车避障等场景．蒋恩源等[16]利用三帧差法、最小二乘法、自适应分段直线拟合算法等通过结合轨迹转向和速度变化率两个参数建立车辆异常行为检测模型．朱宪飞[17]基于FCM轨迹聚类算法并通过卷积神经网络学习，建立了异常轨迹识别模型．浩欢飞[18]在无监督轨迹模型上引入了增量式EM算法，提出一种增量式轨迹模型，并将该模型应用到车辆轨迹的异常识别上．

虽然研究人员提出并改进了多种聚类算法，并实现了较好效果，但值得注意的是，目前所采用的大部分轨迹数据集是高速公路等直道数据集，轨迹形状较为单一，针对城市十字交叉路口以及环形交叉路口等的轨迹聚类研究相对较少，相关聚类算法与异常值检测方法对于城市交叉路口轨迹数据集的兼容性较差．为了解决这个问题，本文提出一种基于K-Medoids算法与DBSCAN算法的组合聚类算法，通过模拟十字交叉路口数据集的训练，得到一个交叉路口的最佳聚类模型，再用全景相机所采集的真实环形交叉路口的轨迹数据集加以验证，从而为实现车辆监管、轨迹异常识别、缓解交通拥堵等应用提供理论指导．

1 轨迹相似度分析

轨迹相似度函数作为聚类算法的底层函数，可为聚类算法服务，相似度系数与轨迹间的某种距离度量密不可分．通常情况下，采用轨迹距离函数来代替相似度系数函数，也可获得较好的聚类效果．选择合理的轨迹距离函数，对于后面聚类算法的效率与准确性至关重要．一方面，轨迹距离函数的适用性会影响数据的完备性，使数据样本间的差别不够明显，导致聚类簇数不足；另一方面，轨迹距离函数的选择还会影响到聚类算法的索引结构，进而影响聚类效率．

因此，本文从时、空两个维度入手，首先通过“时间戳”将轨迹点集按照时间顺序排列并存储为元胞形式；然后根据Hausdorff距离对形状敏感的特点，求得形状差异较大的城市交叉路口车辆轨迹距离，从而得到轨迹间相似度系数；最后实现轨迹聚类的目标．

Hausdorff距离是描述两组实数点集之间相似程度的一种量度，假设有两组集合A=(a1a2

…ap)，B=(b1b2…bq)，则这两个点集合之间的Hausdorff距离H(A，B)定义为

(1)

或

H(A，B)=max{h(A，B)，h(B，A)}

(2)

其中

(3)

(4)

由式(1)、(2)可知，Hausdorff距离是一种极大极小函数，具有方向性，或是说存在不对称性，即h(A，B)≠h(B，A)，所以将h(A，B)称为单向Hausdorff距离，将H(A，B)称为双向Hausdorff距离．下文若无特殊说明，Hausdorff距离均指的是双向Hausdorff距离H(A，B)．

简而言之，Hausdorff距离是从一个集合到另一个集合中最近点的最大距离，这种距离的度量方式克服了最近距离算法(closest-pair distance，CPD)在相对位置改变时距离也会受到影响的缺点．因此，这种算法对形状敏感而被广泛应用于计算机的视觉识别．考虑到非完全直线道路(十字交叉路口、环形交叉路口等)上车辆轨迹形状差异很大，使用Hausdorff距离可以有效地识别不同方向的车辆并提供相似度系数．该算法的时间复杂度是O(p，q)，其中p和q分别为集合A和集合B中点的个数．所以，如果一条轨迹中存在较多点则会线性增加该算法的时间复杂度，降低运算效率．

2 聚类算法分析

由于轨迹聚类分析的数据集规模往往十分庞大，选择合适的聚类算法至关重要．DBSCAN算法是一种典型的基于密度的聚类算法，它将簇定义为密度相连的点的最大集合，能够把具有足够密的区域划分为簇，并可以在有噪声的空间数据集中发现任意形状的簇．因此该算法聚类速度快，异常值识别准确，但存在参数难以控制的缺点．K-Medoids算法仅需输入一个参数，但算法存在随机性．因此将两者以参数传递的方式相结合，提出一种组合聚类算法，可以较好地达到聚类与异常轨迹检测的目的．

2.1 K-Medoids算法

设在m维欧式空间中有n个点所构成的数据点集X=(X1X2…Xn)，其中Xi=(xi1xi2…xim)，i=1，2，…，n．在这个空间中的某个范围内选取k个中心位置Vi(i=1，2，…，k)，使这n个点到各自所在簇的中心位置的某种距离度量最小，这是一种基于优化思想的目标函数，一般可定义如下：

(5)

K-Medoids算法用簇的中位数计算使离群噪声点对于聚类的影响减小，避免较小簇的形成，鲁棒性高．但中心点的寻找采取了轮换的思想，需要遍历所有的点，时间复杂度大，为O(n2kt)，其中n是所有数据点的数目，k是簇的数目，t是迭代的次数．K-Medoids算法通常使用贪婪优化过程来实现：

(1)初始化簇中心点V1，V2，…，Vk

(2)重复以下步骤直到函数收敛

①确定簇

(6)

②更新簇的中心点

(7)

Ck={i|Di，V[k]≤Di，V[λ]}

(8)

(9)

2.2 实验分析

本文使用LISA(Laboratory for Intelligent and Safe Automobiles，UC San Diego Datasets)轨迹数据集为基准轨迹聚类算法提供数据[19]．

如图1所示，该数据集包含6个不同场景：3条模拟公路、1条真实公路、1个模拟十字路口和1个类似环形交叉路口．前期使用模拟数据集进行训练，后期使用多个摄像头收集的真实轨迹数据加以验证．

图1 环形交叉路口K-Medoids轨迹聚类Fig.1 K-Medoids clustering trajectory at roundabout intersection

该场景有5个出入口，中间是一个圆形障碍物，是一个类似环形交叉路口的场景．考虑到出入量的不同，忽略了行走人数较少的行走方案以及折返回头等规模较小的簇，所以这种场景的聚类是在k=12时进行的．并且通过后续的实验表明：在极端情况下(聚类超过10 000次)，k=12存在一个轮廓系数高达0.76的聚类结果，这表明，若想追求最佳聚类效果，可以选择k=12并反复训练模型，保存最佳的一个．结果表明，该方法能较好地对轨迹进行聚类，且各簇间的差别较大，符合人们的认知习惯，效果较好．但是在图像右侧，算法陷入了局部最优解，这与此部分轨迹质量低、噪声点多以及k值的选取有直接联系．

图2 十字交叉路口K-Medoids轨迹聚类Fig.2 K-Medoids clustering trajectory at four-exit intersection

3 聚类效果分析

为了能够更科学地评估聚类效果，本文引入轮廓系数S(silhouette coefficient)作为评价指标．它将聚类效果分为凝聚度与分离度两个方面进行评价，可以用来评价不同聚类算法对同一原始数据的聚类效果，也可以评价运行环境对于聚类效果的影响，是一种评估聚类算法效果的科学客观的手段，在现实生产应用中存在着重要的指导价值．

3.1 单点轮廓系数

首先，对于簇中的每个样本，分别计算它的轮廓系数，对于其中的一个样本i来说，其轮廓系数为

(10)

(11)

(12)

式中：i代表簇Cn中的对象，凝聚度a(i)代表i与Cn中剩余对象的均值，分离度b(i)代表i与Cm中其他点的平均距离，S(i)代表轮廓系数．

所有样本的轮廓系数的均值称为聚类效果的轮廓系数，定义为S，是该聚类是否合理、有效的一种度量．聚类效果轮廓系数的取值在[-1，1]，值越大，说明同类样本相距越近，不同样本相距越远，则聚类效果越好．

3.2 DBSCAN算法

DBSCAN算法对参数很敏感但却不易控制选择，略微改变参数就有可能得出完全不同的聚类效果，而参数的选择目前无规律可循，只能靠反复实验确定．聚类半径愈大，聚类的簇数就越少；最少点越多，识别出的噪声点就越多．

3.3 异常轨迹的分析

在模拟场景中使用DBSCAN算法对不同参数聚类效果进行模拟，图3为环形交叉路口的聚类效果，其中图3(a)、(b)取簇数为5，图3(c)取簇数为6．表1为在环形交叉路口场景中使用DBSCAN 算法与K-Medoids算法于不同参数条件下聚类效果的比较．

(a) 簇数为5，聚类半径为150

表1 DBSCAN与K-Medoids参数对比Tab.1 Comparison of DBSCAN and K-Medoids parameters

由于K-Medoids算法每次聚类时会在n个样本点中任意选取k个点作为中心点，结果具有一定偏差．因此，具体操作流程如下：

(1)在总体n个样本点中任意选取k个点作为中心点．

(2)按照与中心点就近原则，将剩余的n-k个点分配到当前最佳中心点的类中．

(3)对于第i个类中除对应中心点外的所有其他点，按顺序计算当前簇中所有其他点到该中心点的距离之和，选取最小距离时对应的点作为新的中心点．

(4)重复(2)、(3)的过程，直到所有的中心点不再发生变化或已达到设定的最大迭代次数．

(5)最终确定k个类．

本场景中，通过K-Medoids算法传递的函数可知，簇数应为4或5．从图3与表1看出，当簇数为5(图3(a)、(b))时，聚类的效果较好，异常检测较为准确，异常轨迹基本聚集在右侧；而当簇数为6(图3(c))时，轮廓系数直线下降，使得聚类效果大幅下降．

在十字交叉路口模拟场景下，使用DBSCAN算法进行模拟，观察其异常轨迹如图4所示．

从图4可以看出，轨迹异常的主要原因是异常变道，一方面是因为轨迹数据点较少，导致连接数据点形成折线；另一方面转向异常轨迹较少，说明该模拟数据集对转向轨迹部分模拟较为谨慎，异常值较少．

图4 十字交叉路口异常轨迹检测Fig.4 Four-exit intersection abnormal trajectory detection

4 聚类算法的改进

4.1 K-Medoids的改进

根据K-Medoids算法的特点，聚类初始需要对随机种子进行选择，容易导致每次的运行训练结果大不相同．所以，统一以1 000次聚类为基准，测试不同值下的聚类效果．以轮廓系数为判断依据，分别记录K-Means与K-Medoids的最大轮廓系数与1 000次平均轮廓系数，见表2、3．最大轮廓系数代表了这种算法的最好聚类效果，平均轮廓系数则表达了聚类效果的总体水平．

表2 K-Means轮廓系数Tab.2 K-Means silhouette coefficient

通过对比表2与表3的轮廓系数可知，K-Medoids算法的聚类效果普遍优于K-Means算法．同时由表3可知，随着k值的提高，最大轮廓系数基本保持在0.7左右，但是，平均轮廓系数却在降低，说明初始随机种子越多，聚类效果越不稳定，容易陷入局部最优解，造成聚类效果下降．综合考虑时间复杂度以及运算成本，当k在9～11时，既节约了计算成本，同时也可以取得较好较稳定的聚类效果．值得一提的是，在极端情况下(聚类超过10 000次)，k=12存在一个轮廓系数高达0.76的聚类结果，这表明若想追求最佳聚类效果，可以选择k=12并反复训练模型，保存最佳的一个．

表3 K-Medoids轮廓系数Tab.3 K-Medoids silhouette coefficient

4.2 DBSCAN算法的改进

与K-Means及K-Medoids算法不同，DBSCAN 算法具有较好的稳定性，实验的可重复性高，所以在获取轮廓系数的时候，并没有进行过多次的聚类，其轮廓系数如表4所示．

表4 DBSCAN轮廓系数Tab.4 DBSCAN silhouette coefficient

关于DBSCAN轮廓系数各种参数的调整需要注意的是：簇数与聚类半径参数直接相关，但并不意味着改变聚类半径参数一定会改变簇数，同时两者之间大致呈负相关，但绝非标准负相关；基于预处理后的轨迹数据，通过Alteryx软件计算轨迹的标准差，筛选出比标准差大的轨迹点记为噪声点，最少点参数的修改只影响最终噪声点的识别与剔除，通过软件计算得出噪声点所占比例小于1%，所以对于轮廓系数的影响可以忽略不计，故本数据未更改最少点参数，但为了数据的完整性记录下来；同一参数与原始数据多次实验，轮廓系数差别在1×10-5量级上，故不记录平均轮廓系数，以最大轮廓系数代替．

结果表明，DBSCAN算法的聚类效果普遍优于K-Means与K-Medoids算法，且聚类速度更快，轮廓系数随着聚类半径的增大先增后降，最佳聚类效果应当出现在聚类半径为450～500时，这时聚类的簇数为12或13，与K-Means和K-Medoids最佳聚类效果簇数相符．两者相互验证，证明了前期假定的簇数为12是正确的．

综上所述，由于K-Medoids算法参数少，使用K-Medoids算法可以确定最佳聚类簇数，再将最佳聚类簇数传递给DBSCAN算法，使其可以确定自身的相关参数，从而达到精确聚类并识别异常轨迹的目的．

5 结 论

(1)针对交叉路口轨迹形状差异大、交叉点类型多、轨迹异常等特点，提出了一种基于K-Medoids 和DBSCAN算法相结合的聚类算法．分别使用模拟数据集和真实交通数据集进行训练．最后，根据轮廓系数评价聚类效果．结果表明，K-Medoids算法由于自身的局限性，在聚类速度上比DBSCAN算法慢，但它仍然是目前可用的最快的聚类算法之一，最佳聚类效果更好．K-Medoids算法具有随机性，需要大量重复训练才能得到最佳模型，而DBSCAN算法则更稳定．K-Medoids只需要为集群指定一个k值，该方法为DBSCAN算法提供了参数参考，进而得到高轮廓系数的模型参数．实验结果表明，两者的有机结合可以获得更好的聚类效果和异常轨迹识别效果．

(2)面对海量数据，K-Medoids算法的运算时间随着数据量的增加而线性增加．因此，在处理大量数据时，聚类效率不容忽视；如果样本集的密度不均匀，且聚类间距相差很大，DBSCAN算法的聚类质量较差，这就需要对数据进行一定的规范化．同时，该算法对高维数据的聚类效果不是很好．对于三维数据，应进行降维变换或使用相应的高维相似度系数函数．

(3)对于轨迹异常检测，需要提高DBSCAN算法检测局部异常的准确性．这些异常状态表现为由于设备测量误差导致的轨道曲率异常，但整个轨道仍在正常车道上．

(4)对于动态轨迹聚类，需要在轨迹完全驱动之前预测聚类结果，这就需要对静态轨迹进行分段聚类，并对每个类别进行可能性分析．动态预测在实际无人驾驶中具有较高的实用价值和研究价值，本实验可为后续的动态预测提供一些基础数据．