数据挖掘三大经典算法在交通领域的应用综述

引 言

近几年，随着我国经济的快速发展，交通基础设施建设规模不断扩大，为了有效监控和管理各类交通基础设施，提高道路运营和服务水平，特综合了先进的信息技术、数据通信技术、电子传感技术、控制技术及计算机技术，设计了能够对大范围交通设施进行实时、准确、高效管理的综合交通管理系统——智能运输系统（Intelligent Transportation System， ITS），该系统逐渐受到了世界各国交通研究者的高度重视 [1]。

智能运输系统的一个显著特点是以交通信息的收集、处理、发布、交换、分析、利用为主线，为交通参与者提供多样服务。在上述各环节中，交通信息的收集是基础工作，与交通服务水平的质量紧密相关，因此各国研究者对交通信息收集技术展开了大量研究 [2]。一般而言，交通信息的收集方式主要分为两种，即利用人工方式进行交通数据调查，如交通问卷调查 ；基于交通检测设备由计算机自动完成数据收集， 常见的技术包括利用微波车检器、超声波车检器、感应线圈、视频车检器等交通检测设备收集交通流量、速度和占有率等数据指标。随着这些交通检测技术的日益升级以及国家对智能交通的大力倡导，我国各地区的交通管理部门已经积累了大量历史交通数据，如何对这些数据进行有效分析和利用，以进一步改善整个道路系统的服务水平，成为当前交通研究领域一项有价值的课题。在此背景下，能够从海量数据中挖掘出有用规律和模式的数据挖掘技术便成为研究者手中的利器。

本文首先对数据挖掘技术中的三大经典算法进行原理描述，在此基础上，对这些算法近些年在交通领域中的热门应用进行综述和总结性分析。

1 数据挖掘三大经典算法概述

1.1 C4.5算法

C4.5 算法是数据挖掘学科中用于机器自动分类的一种决策树学习算法，其基本思想是基于信息熵理论和树状分类规则构建样本属性与样本类别之间的映射关系[3-4]。C4.5 算法的前身是由著名机器学习专家 Quinlan 在 1986 年提出的 ID3 算法[5]，采用递归分治的方式进行决策树的迭代构建。在构建过程中依据最优划分属性的属性值将当前层的样本集划分为若干子集。ID3 算法基于信息熵理论选择当前样本集中具有最大信息增益的属性作为最优划分属性。然而，这种做法容易导致最优划分属性的选择偏向于取值较多的属性，为此， Quinlan 又在 1993 年提出了 ID3 的改进算法——C4.5 算法。与前者不同，C4.5 算法采用信息增益率确定最优划分属性， 以显著改进算法的泛化性能。此外，C4.5 算法还能够对连续型属性及属性值空缺的情况进行处理，并且在树剪枝方面也采用了较为成熟的策略。图 1 所示为利用 C4.5 决策树算法进行分类决策的过程示例。图中描述的样本具有 3 个属性，包括天气（Outlook）、空气湿度（Humidity）、是否有风（Windy），以及1个决策类别（是否去打高尔夫）。

注 ：最左边的一条分类决策规则是 ：如果晴天且空气湿度不大于 75，则可以去打高尔夫

                                                                                                       图1 基于 C4.5 决策树算法进行分类决策

1.2 K-Means算法

K-Means算法 [6] 是一种无监督学习算法，是数据挖掘学科中常用的聚类技术之一。它通过对样本内部分布特征进行归纳和描述（采用“类内相似性最大，类间相似性最小”的归类原则），将样本集自动划分成指定的 k个类别。该算法最显著的特点是无需人工提前标定样本类别。基本思想 ：从样本集中随机选择 k 个样本，每个样本代表一个类中心。对剩余每个样本，根据其与各类中心之间的距离，将它指派到距离最相近的类中，然后计算各类新的类中心。不断重复上述过程， 直至聚类函数收敛。聚类函数见式（1）：

式中 ：E是数据集中所有样本的平方误差和 ；p是给定的样本向量 ；mi是类 Ci的中心（均值）向量。K-Means算法简单，计算复杂度低，可扩展性强，得到了众多研究者的青睐。然而， 它本质上是一种贪心算法，可能会收敛到“局部最优”，而且对初始中心点的选择较为敏感。此外，初始参数 k需要人工设定。图 2所示为利用 K-Means算法进行聚类的示意图。

1.3 SVM算法

SVM（Support Vector Machine，SVM）算法 [7] 属于有监督学习算法范畴，是一种机器自动分类算法。该算法通过寻求结构化风险最小提高学习机的泛化能力，实现经验风险和置信范围最小化，实现在统计样本量较少的情况下依然能获得良好分类性能的目的。SVM 算法对复杂的非线性决策边界的建模准确度极高，且不容易出现“过拟合”现象。缺点是训练时间较长，因此适合小样本分类问题。图 3 描述了利用SVM 算法对样本进行分类的过程。

2 数据挖掘三大经典算法在交通领域的应用

2.1 C4.5算法在交通中的应用

ZHANG 等人 [8-9] 采用 C4.5 算法对交通冲突数据进行了建模分析，并利用所构建的决策树对造成交通冲突的各种影响因素、种类和碰撞程度以及受影响人群进行了细分，进而归纳分析出导致各种交通冲突的主要影响因素及其对应的冲突程度和受影响人群的特性。Park 等人 [10] 提出了一种基于 C4.5算法的路线航策略，并将其应用于个人车载导航系统，取得了良好的效果。Griffin 和 Huang[11] 基于收集的 GPS 数据对交通出行目的进行了分类和决策，所构建的模型基于 C4.5 决策树算法。他们的实验结果显示，C4.5 决策树算法的分类效果很好，且最终得到的分类规则具有较强的可解释性，容易理解。徐磊和方源敏 [12] 对 C4.5 算法进行了改进，并基于改进的模型对交通拥堵和各种影响因素之间的内在关系进行了挖掘分析，获取的规则对于城市交通管理和疏导具有很强的指导意义。徐春荣 [13] 研究了 C4.5 算法在交通拥堵分类中的可行性和有效性，考虑到 C4.5 算法的时间复杂度较高，在算法学习过程中引入了基于实例的规则进行提速。改进后的模型不仅能以很高的精度分类交通拥堵程度，而且大大降低了分类所花费的时间开销。赵明 [14] 通过分析天气、时间段、特殊路况、道路设施质量及节假日等影响因素，构建了基于 C4.5 算法的预测模型，对未来的交通拥堵程度进行预测。他们的实验结果表明，基于 C4.5 算法的预测模型在交通拥堵预警应用中具有显著的优势和可靠性。

通过上述分析可以看出，C4.5 算法在交通领域主要应用于交通的分类决策。由于 C4.5 算法基于信息熵理论，具有坚实的理论基础，因此具有出色的分类性能，并且最终导出的分类规则具有较强的可解释性，使其在交通影响因素分析研究领域具有显著优势。

2.2 K-Means算法在交通中的应用

Bocarejo 和Díaz 对哥伦比亚首都波哥大的交通事故数据进行了研究，并利用 K-Means 算法进行了聚类分析。研究结果表明，基于 K-Means 的聚类分析方法能够有效找出隐藏在事故数据中的规律和模式。他们找出的一个有趣模式是，在波哥大市区发生的致命交通事故主要分为两种类型，一类是公交车与行人相互冲突 ；另一类是公交车与摩托车相互冲突。因此，他们建议从道路运营和安全管理角度对这两类事故进行重点监控，并制定相应的预警政策。Raiwani 和 Baluni 对印度乌塔拉坎德邦的交通事故数据进行了 K-Means 聚类，分析的数据指标包括交通事故发生的具体地点、所属区域、发生时间以及交通事故中受伤或死亡人员的姓名、年龄、性别、家庭地址。聚类结果显示出一些有趣的关联模式，例如，在该城市的哪几个地区更易发生交通事故，事故中人员受伤程度与性别之间是否存在内在关联等。Deb Nath 等人利用改进的K-Means 算法对道路行程时间指标进行了预测。他们的研究表明，相较于连续滑动平均方法（SMA）、链式平均方法（CA）及朴素贝叶斯分类方法（NBC），改进的 K-Means 算法具有更加显著的预测效果。Pankaj 和 Patil 在交通标志识别（Traffic Sign Recognition，TSR）系统中采用 K-Means 算法进行交通标志图像分割，显著改善了交通标志的识别效果。闰明月基于K-means 算法对城市交通客流量数据进行了分析，得到了一些有用的结论，为城市交通规律分析、城市规划与交通政策的制定提供了依据。高勃等人采用 K-means 算法对北京地铁路网重要度进行了聚类分析。研究发现，在不同时间段，北京地铁车站和区间在路网中的重要度是动态变化的，路网中车站（区间）的重要度异质性也随时间而改变。他们构建的聚类模型能够较好地从历史数据中挖掘出北京地铁路网的规律模式。沈吟东等学者基于大量 GPS 运营数据，创新性地将K-means聚类算法应用于公交运营时段划分，并结合十堰市和海口市公交的数据案例，验证了所提出模型的可行性和有效性。

综上所述，当需要对数据样本进行归类但又没有可用的人工标定训练数据时，以 K-means 为代表的聚类分析算法便成为最佳选择。K-means 算法通过数据的内部分布特征迭代进行相似度计算，可以自动对数据集进行归类。在交通研究领域， 交通检测数据由于数量巨大、标定成本过高等原因导致在大部分应用中都没有事先标定类别的训练样本，因此，K-means 聚类算法就有了用武之地。

2.3 SVM算法在交通中的应用

Borkar 和Malik 通过布设在路侧的传声器收集车辆的音频数据，并基于这些数据估计交通密度状态。他们利用各种核函数 SVM 分类器对收集到的数据进行学习和分类。最终， 数据样本被分成 3 类（Low，Medium，Heavy），分别对应交通密度低（自由流）、交通密度中等（畅通）、交通密度很大（拥堵） 三种状态。实验结果表明，基于二次核函数的 SVM 分类器可以获得 96.67% 的分类精度，而基于多项式核函数的 SVM 分类器分类准确率高达 98.33%。Alioua 等人基于 SVM 人脸检测技术提取车辆驾驶者的脸部特征，并根据眼睛和鼻子的特征信息判断驾驶者是否处于疲劳驾驶状态。采用这种方法得到的识别率达 94%。一些研究者设计了基于 SVM 算法的分类器对由车辆摄像头捕捉的交通标志符号图像进行识别和归类， 研究显示，利用 SVM 算法在复杂决策边界情形下的高精度分类性能，可以有效对在非理性条件下（复杂道路条件、雨雾天气、有遮挡物等）的交通标志进行准确辨认和识别。此外， 还有一些学者利用 SVM算法对交通流短时预测课题展开了研究，并取得了不错的效果。

SVM 算法是一种有坚实理论基础的小样本学习方法，从本质上看，它避开了从归纳到演绎的传统过程，实现了从训练样本到分类样本的“转导推理”，大大简化了机器学习和数据挖掘领域的分类和回归问题。因此，SVM 算法在交通事件自动检测、交通状态判别及短时交通流预测等方面均有成功的应用。需要说明的是，SVM 是借助二次规划来求解支持向量， 而求解二次规划涉及高阶矩阵的计算，此时矩阵的存储和计算将耗费大量的计算机资源，因此 SVM 算法对大规模训练样本难以实施。

3 结 语

本文简要概述了 C4.5，K-Means 和 SVM 三大经典数据挖掘算法的基本原理，并对这三种算法在交通领域的有效应用进行了综述，以期对研究者充分发掘它们在解决交通问题中的潜力提供有益借鉴。在未来的研究工作中，笔者将进一步研究和探讨这些算法的原理及其在交通领域的应用。