基于k-mediods及其改进算法的非法营运车辆识别

帅　丹　蓝章礼　李益才

(重庆交通大学信息科学与工程学院　重庆 400074)



基于k-mediods及其改进算法的非法营运车辆识别

帅丹蓝章礼李益才

(重庆交通大学信息科学与工程学院重庆 400074)

摘要为从大量社会车辆中识别出疑似非法营运的车辆，提高交通管理部门行政执法的目的性和针对性，维护道路运输市场秩序，消除交通安全隐患。结合RFID车辆信息数据提出了基于k-mediods的非法营运车辆识别算法，并针对k-mediods算法缺点进行了基于距离贡献率和算法偶然性的2种改进。非法营运车辆识别的实现，首先需要提取出车辆RFID数据，并对其进行预处理，进而得到车辆运行行为数据，再利用PCA处理得到车辆运行特征数据，最后通过k-mediods算法聚类分析识别出非法营运车辆。实验结果表明，算法流程清晰，能够有效地识别出非法营运车辆。同时通过对算法进行改进，提高了算法稳定性和对非法营运车辆的正确识别数量，降低了错误识别数量。

关键词k-mediods距离贡献率偶然性RFID

0引言

相对滞后的公共交通满足不了群众日益增长的出行需求，这就为实载率高、方便灵活、具有成本优势的非法营运车辆的存在提供了肥沃的土壤，但由于非法营运车辆的巨大危害性，打击和规范非法营运车辆是交通行政执法的重中之重[1,2]。因此如何有效地从大量的社会车辆中识别出疑似非法营运车辆，对提高交通管理部门行政执法的目的性和针对性，维护道路运输市场秩序，消除交通安全隐患具有重要意义。

RFID(无线射频识别)技术作为一种新兴的车辆监控技术，因其识别速度高，精确性能好，成本低廉，正在被广泛地应用于物流、交通、医疗、商品防伪等诸多领域[3-6]。RFID装置能够采集到的数据包括时间、地点以及RFID卡中所含信息如车辆牌照号、车辆类型等，能够很好地满足对各类车辆的监控和数据采集功能。

数据挖掘中聚类分析在城市交通、道路安全、事故分析、交通违规违法行为分析等方面得到较为深入的研究和广泛的应用[7-10]。文献[11]提出了一种混合蛙跳算法与模糊C均值相结合的聚类算法，用于城市交通流数据的聚类分析；文献[12]提出灰色定权聚类对区域内高等级公路进行聚类；文献[13] 采用快速DBSCAN算法对铁路异物侵限检测；文献[14]采用主成分分析方法实现了疲劳驾驶行为特征提取，对疲劳驾驶进行了分析；文献[15]针对车辆行驶过程中的GPS设备采集提供的车辆行驶位置和速度等数据，根据超速情况划分和确定重点监控车辆和实现对该车技术状况和驾驶人情况信息的查询。但是利用聚类分析算法分析RFID数据，识别车辆运行规律和识别非法营运车辆的研究还比较少见。

本文结合车辆RFID数据，运用数据挖掘中的经典聚类分析算法k-mediods对非法营运车辆进行识别，首先将从RFID获取的车辆运行信息存入数据库，并通过提取特征数据等对数据进行预处理得到车辆运行的行为数据，再利用PCA(主成分分析)处理得到车辆运行特征数据，最后通过k-mediods聚类分析算法对特征数据进行分析识别非法营运车辆。同时，针对k-mediods的各成分对相似性贡献率相同和偶然性比较大的问题，结合RFID车辆数据特点，对算法缺点分别做了改进，提高了非法营运车辆的正确识别数量、降低了错误识别数量。

1基于k-mediods算法的非法营运车辆识别

1.1非法营运车辆识别系统流程

非法营运车辆识别系统流程如图1所示。

图1　非法营运车辆识别系统流程

先将车辆运行信息存储于车辆信息数据库；再对存放车辆信息的数据库进行预处理，包括：分析并提取车辆运行的行为数据，建立数据仓库并定时更新；然后对数据仓库中的车辆运行行为数据进行PCA处理；接着利用k-mediods算法进行聚类分析，最后得到车辆分类识别结果中非法营运车辆信息并将其存入数据库。若运行的车辆信息在非法营运车辆信息数据库中，则此车被判定为非法营运车辆；反之被判定为合法车辆。

其中，分析的车辆信息为RFID采集的数据，包括车牌号码、车辆通过地点、车辆通过时间；提取的行为特征数据包括车牌号码、通过时间间隔、平均通过时长、时间间隔方差、通过频次、高峰时期通过占比等相关信息；PCA处理之后得到6维车辆运行特征数据和每一维数据贡献率；k-mediods聚类算法分析输出基于RFID的车辆数据分类结果；数据仓库更新比较耗时，因此频率可设定为一周一次，时间定为凌晨车少的时间点。

1.2算法流程

RFID数据的k-mediods算法流程如图2所示。

图2　RFID数据的k-mediods算法流程图

算法输入：包含n个对象的车辆运行信息，结果簇的个数k。

算法输出：k个簇的集合，使得所有对象与其最近中心点的相异度总和最小方法。

其步骤描述为：

1) 从数据库中获取聚类分析车辆的数据信息O(n)，需要聚类的个数k；

2) 随机选择k个对象作为初始中心点；

3) 将剩余对象分配到临近中心的簇，并计算此时的目标函数oldE；

4) 随机产生一个代替原中心的对象Orand；

5) 依次利用Orand代替原始的k个对象；

5.1) 初始化即将替代的簇中心下标i=0；

5.2) 判断是否遍历完所有簇中心，若遍历完则转向步骤6),否则转向下一步5.3)；

5.3) 将剩余对象分配到临近中心的簇，计算目标函数newE；

5.4) 计算此时代价函数S=newE-oldE；

5.5) 判断S是否小于0，若小于0则转向步骤5.7)，否则转向下一步5.6)；

5.6) 下标i=i+1，转向5.2);

5.7) 记录此时下标j=i，并用Orand代替Oj，转向步骤5.3);

6) 结束。

算法其他说明：

a) 输入的n个对象的车辆信息，包含车牌号、已知的车辆类型以及经过PCA处理之后的车辆运行特征数据，同时对这些特征数据进行了归一化处理，归一化处理公式如下：

(1)

其中，norci(p)表示第i个对象在第p维特征数据经过归一化处理的结果；c表示车辆信息的对象；ci(p)表示第i个对象在第p维特征数据值；min(c(p))表示所有车辆信息中的第p维特征数据值的最小值；max(c(p))表示所有车辆信息中的第p维特征数据值的最大值。

b) 输入的结果簇k为经验值，其确定方法在本文不做讨论。

c) 目标函数E的公式如下：

(2)

其中j表示聚类分析后簇的序号，范围为：1到k；i为对象序号，范围为：1到n；cj表示第j个簇的中心；xi表示第i个对象；dist表示求cj与xi欧式距离。其中dist(cj,xi)的公式如下：

(3)

其中cj(p)表示cj的第p个运行特征数据，m表示对象共有多少特征数据。

式(1)的意义为：分别将属于第j个簇中心的对象xi与所在簇中心cj之间的距离的平方依次相加，表示聚类分析后簇内部数据的差异性，在一定范围内，目标函数E越小，聚类分析效果越好。

d) 代价函数公式如下：

S=newE-oldE

(4)

其中newE表示利用随机对象替换原簇中心之后的目标函数值，oldE表示原对象的目标函数值。若S<0，则可以替换原簇中心；反之，则不能替换原簇中心。

2k-mediods算法在车辆RFID数据应用的改进

k-mediods算法是一种使目标函数下降最快的方法，属于启发式搜索算法，能从n个对象中找出以k个中心点为代表的一个局部优化划分聚类。与k-means算法比较，k-mediods算法解决了k-means算法本身的缺陷：对初始值依赖过大的问题和对噪声点、离群点敏感型问题[16,17]。但是仍存在以下缺点：

a) k-mediods算法利用欧式距离表征其相似性，数据的每个属性对距离的贡献都一样，这样不能体现出属性的重要程度，因此无法达到良好的聚类效果。

b) 在算法中仅仅是随机指定一个非代表对象Orandom来依次替换代表对象Oj，虽然在时间复杂度比较小，运行时间也比较小，但是偶然性太大，不能达到良好的聚类效果。

因此针对以上2个缺点，结合车辆RFID数据特点对算法进行了2种改进。

2.1改进一：基于距离贡献率的改进

由k-mediods算法的缺点a)，其使用欧式距离度量相似性的过程中，每个属性对距离贡献率一样。因此提出以下改进，在非法营运车辆识别系统中经过PCA分析和处理之后，由于对象每一维对数据的影响不同，故根据其重要程度为每一维乘以其权值wp，其中：

(5)

RFID数据经过PCA处理之后，每一维特征数据的重要程度不一样，第一维的数据占了很大的比重，其对数据分析而言是最重要的，第二维次之，剩余维依次减小。这样改进可以增加最主要的成分对计算相似度的贡献率，适合处理基于车辆RFID数据。因此，将式(3)中的欧式距离改进为式(6)：

(6)

与式(3)相比，考虑了每一维车辆运行特征数据的重要程度对距离的影响，将权值wp乘上相应运行特征数据值与簇中心的欧式距离。

2.2改进二：基于偶然性的改进

由于k-mediods算法的缺点b)，其算法偶然性太大，因此提出以下改进，在算法中仅仅是随机指定一个非代表性对象Orandom来依次替换代表对象Oj，修改为依次用所有的非代表性对象Oi(i=1,2,…,n)来替代Oj，再依次计算代价函数。

这样改进可以排除随机指定非代表性对象的偶然性，得到在每一轮换的过程中使得目标函数值最小的替换对象，即最优替换对象。在非法营运车辆识别系统中后台处理使得系统对时间的敏感度不高，因此，此改进适合处理基于车辆RFID数据。

3结果分析

在Win7环境下，使用VC++平台实现本文提出的基于k-mediods算法及其改进的非法营运车辆识别系统。通过车辆RFID的数据实验数据中排除了出租车的干扰后共1762辆车，包含：公交车57辆、长途车40辆、社会车1635辆、非法营运车30辆。在对基于车辆RFID数据进行分类和处理时，关心的结果是非法营运车辆正确识别数量、误识别数量，因此实验结果重点分析和对比非法营运车辆正确识别数量和误识别数量。实验结果曲线均是经过15次车辆运行数据得出的平均值，簇数目k取值从1到30。

3.1k-mediods算法结果分析

主要分析用最原始的k-mediods来分析经过标准化，但没有经过处理的车辆RFID数据运行特征数据，实验结果如图3所示。

图3　非法营运车辆识别、误识别数量曲线图

根据非法车辆识别数量、非法车辆曲线图可以分析得出最佳k值为14，此时的正确识别数量平均值为29.93辆，错误识别数量为2.13辆。再进一步分析效果相对较好的一段曲线k从10到18之间所有实验结果。如表1所示。

表1　提取监控视频关键帧实验结果表

表1中i为实验次数，k为相应的簇个数，N为正确识别数目。从15次实验的非法车辆正确识别数量来看，其偶然性太大，比如在k=11的时候，有2次识别的非法营运车数量为0辆，1次识别的非法营运车数量为26辆，12次识别的非法营运车数量为30辆。因此需要对算法进行改进以更好地适应本系统中车辆RFID数据。

3.2基于距离贡献率改进前后结果对比与分析

主要分析借助于改进一算法对标准化的数据乘以相应权值之后的改进k-mediods改进算法时间复杂度虽然比原来算法有所提高，但本算法在分析非法营运车辆的应用中是后台运行，不需要考虑算法的运行时间，其识别率的实验结果如图4所示。

图4　算法改进一之后的非法车辆识别、误识别数量曲线

根据非法车辆识别数量和非法车辆曲线图，经分析可以得出最佳k值为10，此时的正确识别出来平均值为30辆，错误识别数量为0.4辆。虽然还是有误识别的车辆，但是与对车辆RFID运行特征数据利用k-mediods算法进行改进以前的识别结果相比：非法车辆正确识别数量明显增加，此时可以完全识别，同时误识别数量明显减少，验证了算法改进一的合理性。

3.3基于偶然性改进前后结果对比与分析

主要分析在算法改进一的基础上再对算法进行改进二，对标准化的数据乘以相应权值之后，利用所有非对象点替换随机点的k-mediods算法时间复杂度虽然比原来算法高，但本算法在分析非法营运车辆的应用中是后台运行，不需要考虑算法的运行时间，其识别率的实验结果如图5所示。

图5　算法改进二之后的非法车辆识别、误识别数量曲线

根据非法车辆识别数量和非法车辆曲线图，经分析可以得出最佳k值为18、19，此时的正确识别数量平均值均为30辆，错误识别数量均为0辆。与对车辆RFID运行特征数据利用改进一之后的k-mediods算法的识别结果相比：全部正确识别非法营运车辆，并且误识别数量有明显减少。其中k从3到19的正确识别数量均为30辆，而最大的误识别率也只有2辆，因此算法稳定性明显提高，降低了偶然性带来的影响，验证了算法改进二的合理性。

3.4算法改进实验结果前后对比

算法经过改进前后，其在最佳k值的情况下，非法营运车辆正确、错误识别平均数量对比如表2所示。

表2　算法改进前后实验结果对比表

由表2可得：原始k-mediods算法能够识别出非法营运车辆。经过基于距离贡献率的算法改进之后，非法营运车辆正确识别数量达到30，即可以完全识别出非法营运车辆；错误识别数量也有明显下降。再经过基于偶然性的算法改进之后，在最佳k值得情况下，也可以完全识别出非法营运车辆，同时错误识别非法营运车辆的数量降低为0。由此也可以得原始算法的合理性和算法改进的合理性。

4结语

本文结合车辆RFID数据，利用k-mediods聚类分析算法对非法营运车辆进行识别，同时，针对k-mediods算法的缺点进行了基于距离贡献率和偶然性的改进。实验结果表明，能够有效地识别出非法营运车辆，经过改进之后，提高了算法稳定性和非法营运车辆的正确识别数量、降低了错误识别数量。但算法中的聚类数量k值凭经验得出，在以后研究中，将进一步完善算法，使得算法能够结合自动训练合适的k值范围。

参考文献

[1] 郭譞.涉非法营运车辆案件的情况分析[J].法制与经济,2014(3):100-102.

[2] 祁巍巍.非法营运车辆的监管及其对策研究[D].华东理工大学,2012.

[3] 付华伟,何小敏,许亮,等.基于RFID和遗传算法的实时炸药仓储优化操作[J].计算机工程与科学,2014,36(2):286-291.

[4] 郑方伟,周明天,张宇威.RFID自助收银研究和设计[J].微电子学与计算机,2011,28(3):186-189.

[5] 王德玉,张霖言,刘紫熠.RFID技术在电力企业中的应用及前景[J].天津电力技术,2014(2):78-80.

[6] Malakar B,Roy B K.Survey of RFID applications in railway industry[C]//Automation,Control,Energy and Systems (ACES),2014 First International Conference on.IEEE,2014:1-6.

[7] 张昀,周涑,任海军,等.数据挖掘在电力负荷坏数据智能辨识与修正中的应用[J].重庆大学学报ISTIC EI,2013,36(2):73-78.

[8] 张成叔.数据挖掘中关联规则挖掘方法的研究及应用[J].软件,2013,34(9):138.

[9] Fan X D.Clustering Analysis Based on Data Mining Applications[J].Applied Mechanics and Materials,2013:1026-1029.

[10] Stutz C,Runkler T A.Classification and prediction of road traffic using application-specific fuzzy clustering[J].Fuzzy Systems,IEEE Transactions on,2002,10(3):297-308.

[11] 杨祖元,徐姣,罗兵,等.基于SFLA-FCM聚类的城市交通状态判别研究[J].计算机应用研究,2010(5):1743-1745.

[12] 许洪国,刘兆惠,王超.道路安全等级定权聚类评价模型及因素辨析[J].交通运输工程学报,2007,7(2):94-98.

[13] 郭保青,朱力强,史红梅.基于快速DBSCAN聚类的铁路异物侵限检测算法[J].仪器仪表学报,2012,33(2):241-247.

[14] 毛吉吉,初秀民,严新平,等.汽车驾驶员驾驶疲劳监测技术研究进展[J].中国安全科学学报,2005,15(3):108-112.

[15] 丁博.基于数据挖掘的车辆运行状态监控技术应用研究[D].北京交通大学,2011.

[16] 孙胜,王元珍.基于核的自适应k-Medoid聚类[J].计算机工程与设计,2009(3):674-675.

[17] Park H S,Jun C H.A simple and fast algorithm for K-medoids clustering[J].Expert Systems with Applications,2009,36(2):3336-3341.

[18] 姚丽娟,罗可,孟颖.一种新的k-medoids聚类算法[J].计算机工程与应用,2013,49(19):153-157.

RECOGNISING ILLEGAL OPERATION VEHICLES BASED ON K-MEDIODS AND ITS IMPROVED ALGORITHM

Shuai DanLan ZhangliLi Yicai

(SchoolofInformationScienceandEngineering,ChongqingJiaotongUniversity,Chongqing400074,China)

AbstractIn order to recognise the vehicles to be suspected operating illegally from a large number of social vehicles, improve the purposive intention and pertinence of the traffic administration in administrative enforcement, maintain the market order of road transportation and eliminate the hidden traffic safety hazard, we proposed the k-mediods-based illegal operation vehicles recognition algorithm in combination with RFID vehicle information data. In light of the shortcomings of k-mediods algorithm, we made two improvements on it, the distance contribution rate-based and the algorithm contingency-based respectively. To implement the illegal operation vehicles recognition, firstly it needs to extract vehicles’ RFID data, and carries out pretreatment on them, and then obtains the behaviour data of vehicles operation; secondly, it acquires the characteristics data of vehicles operation by means of PCA processing; finally, it recognises the illegal operation vehicles by k-mediods-based clustering analysis. Experimental results show that the algorithm has a clear flow, it can recognise the illegal operation vehicles effectively, meanwhile it can improve the stability of the algorithm by improving it, and in turn raises the numbers of correct recognition of the illegal operation vehicles, and decreases the numbers of wrong recognition as well.

Keywordsk-mediodsDistance contribution rateContingencyRFID

收稿日期：2014-12-11。重庆市教委科学技术研究项目(KJ1304 21)。帅丹，硕士生，主研领域：交通信息化。蓝章礼，教授。李益才，副教授。

中图分类号TP391

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.038