Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 ２００８，４４（３５） ２０３ 基于粗糙集和支持向量机的高速公路事件检测 郭 倩，黄林 ＧＵＯ Ｑｉａｎ，ＨＵＡＮＧ Ｌｉｎ 西北农林科技大学信息工程学院，陕西杨凌７１２１００ Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎｏｒｔｈｗｅｓｔ Ａｇｒｉｃｕｌｔｕｒｅ ａｎｄ Ｆｏｒｅｓｔ Ｕｎｉｖｅｒｓｉｔｙ，Ｙａｎｇｌｉｎｇ，Ｓｈａａｎｘｉ ７１２１００，Ｃｈｉｎａ Ｅ—ｍａｌｌ：ｌｉａｎｇｑｉａｎ１９８４＠１２６．ｃｏｎ ＧＵＯ Ｑｉａｎ，ＨＵＡＮＧ Ｌｉｎ．Ｆｒｅｅｗａｙ ｉｎｃｉｄｅｎｔ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｒｏｕｇｈ Ｓｅｔｓ ａｎｄ Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅ．Ｃｏｍ－ ｐｕｒｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２００８，４４（３５）：２０３—２０５． Ａｂｓｔｒａｃｔ：Ａｇａｉｎｓｔ ｏｆ ｔｈｅ ｌｉｍｉｔａｔｉｏｎｓ ｏｆ ｃｕｒｒｅｎｔ ｅｘｐｒｅｓｓｗａｙ ｉｎｃｉｄｅｎｔ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ，ａ ｔｒａｆｉｆｃ ｉｎｃｉｄｅｎｔ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｒｏｕｇｈ Ｓｅｔｓ（ＲＳ）ｔｈｅｏｒｙ ａｎｄ Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅ（ＳＶＭ）ｉｓ ｐｒｏｐｏｓｅｄ．Ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｉｎｔｒｏｄｕｃｉｎｇ ｔｈｅ ｐｒｉｎｃｉｐｌｅ ｏｆ Ｒｏｕｇｈ Ｓｅｔｓ ｔｈｅｏｒｙ ａｎｄ Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅ，ｔｈｅ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｍｅｔｈｏｄ ｉｓ ｇｉｖｅｎ．Ｆｕｒｔｈｅｒ，ｖａｒｉｅｔｙ ｏｆ ａｌｇｏｒｉｔｈｍｓ ｓｉｍｕｌａｔｉｏｎ ａｎｄ ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｉｓ ｄｏｎｅ ｗｉｔｈ Ｍａｔｌａｂ．Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｆｒｅｅｗａｙ ｉｎｃｉｄｅｎｔ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ＲＳ ａｎｄ ＳＶＭ ｈａｓ ｓｕｃｈ ａｄｖａｎｔａｇｅｓ ａｓ ｈｉｇｈ ｄｅｔｅｃｔｉｏｎ ｒａｔｅ，ｆａｓｔ ｔｒａｉｎｉｎｇ ａｂｉｌｉｔｙ ａｎｄ ｇｏｏｄ ｇｅｎｅｒａｌｉｚａｔｉｏｎ．Ｉｔ ｉｓ ｆｏｕｎｄ ｔｏ ｂｅ ｐｏｔｅｎｔｉａｌｌｙ ａｐｐｌｉｃａｂｌｅ ｉｎ ｐｒａｃｔｉｃｅ． Ｋｅｙ ｗｏｒｄｓ：Ｒｏｕｇｈ Ｓｅｔｓ（ＲＳ）；Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅ（ＳＶＭ）；ｆｒｅｅｗａｙ；ｉｎｃｉｄｅｎｔ ｄｅｔｅｃｔｉｏｎ 摘要：针对目前高速公路事件检测算法存在的局限性，提出基于粗糙集理论和支持向量机的高速公路事件检测算法。在介绍粗 糙集理论和支持向量机原理的基础上，给出了检测算法的实现方法，并用Ｍａｔｌａｂ对多种算法进行了仿真和性能对比。仿真结果表 明，基于粗糙集理论和支持向量机的事件检测算法具有检测准确率高，训ＮＮ－Ｎ＃２，泛化能力好等优点，具有良好的应用前景。 关键词：粗糙集；支持向量机；高速公路；事件检测 ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２—８３３１．２００８．３５．０６１ 文章编号：１００２—８３３１（２００８）３５—０２０３—０３ 文献标识码：Ａ 中图分类￣＂：ＴＰ３９ ｌ引言 很好的学习泛化能力和分类性能日，但处理包含冗余信息的大 高速公路交通事件是指非周期性发生且使某段道路通行 量数据存在训练时间长、速度慢的缺点。粗糙集理论（Ｒｏｕｇｈ 能力下降的事件。高速公路交通事件的发生会严重影响交通安 Ｓｅｔｓ，ＲＳ）则可以对数据进行约简，在保持分类能力不变的条件 全与畅通，造成交通混乱及延误，而且容易引发二次事故。近年 下，删除其中不相关或不重要的冗余知识，获得数据的核心知 来，随着我国高速公路建设里程的增加和交通流量的增大，交 识 。将两算法充分融合，提高了ＳＶＭ处理速度，同时保持了 通事件也随之增多。据统计，近年来我国每年由高速公路交通 较好的分类效果。 事件造成的经济损失要达到３００亿元＿１Ｊ，因此对高速公路交通 事件的监控显得尤为重要。如何准确、快速地检测和确定事件 ２粗糙集和支持向量机 发生的时间、地点和性质是对交通事件进行控制的关键。 ２．１粗糙集基本原理 事件检测实质上是有事件交通模式和无事件交通模式的 粗糙集理论是一种处理模糊性与不确定性的软计算基础 分类问题。从２０世纪６０年代，人们已经开始了事件检测技术 理论，在保持分类能力不变的前提下，通过垂直约简，消除样本 的研究，目前，形成了多种自动检测算法，主要包括直接检测算 的冗余，通过属性约简，导出问题的决策或分类规则 。 法和间接检测算法两大类日。直接检测算法，主要通过视频和图 粗糙集理论把对象世界抽象为一个信息系统，表示为ｓ＝ 像处理的方法完成对目标的跟踪、识别及交通流检测，成本较 （ ，ｃｕＤ， 厂），其中ｕ表示对象的集合；Ｃ表示条件屙性集，Ｄ 高，且受气象条件影响较大；间接检测算法，主要根据事件对交 表示决策属性集，令Ａ＝ｃｕＤ；Ｖ表示所有属性可取值的集合， 通流的影响来检测事件的存在，成本低、简单易操作，但是存在 厂．ＵｘＡ— 是一个信息函数，该函数指定ｕ中每一个对象的属 检测率低，误报率高等问题。 性值，例￣ｎｆ（ｕ．，ａ）＝ 表示记录ｕ 在属性ａ上的取值为 针对目前高速公路事件检测算法存在的问题，提出了一种 粗糙集理论主要基于 中对象的不可区分关系的思想。 基于粗糙集理论和支持向量机的事件检测算法。支持向量机 某属性子集ＢＣ＿Ａ， ，Ｙ∈Ｕ为两个数据实体。如果有Ｖａ∈Ｂ， （Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅ，ＳＶＭ）算法基于统计学习理论，具有 ｆ（ｘ，。）＝厂（，，，。）那么仅仅根据属性集 提供的信息，无法将 作者简介：郭倩（１９８４一），女，硕士，主要研究领域为：基于网络的计算机应用；黄林（１９５１一），女，教授，主要研究领域为：基于网络的计算机应用。 收稿１３期：２００８—０７—２８ 修回１３期：２００８—０９—２６ ２０４ ２００８．４４（３５） ，Ｃｏｍｐｕ￣ｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 Ｙ区别开来，这时就称 ，Ｙ在属性集日上是不可分辨的，定 肋（Ｂ）＝｛（ ，Ｙ）Ｅ ＵｘＵ：Ｖ口∈曰 （ ，０）鼍厂（，，，０）ｌ （１） 义如下： ３基于粗糙集和支持向量机的高速公路事件检测算法 ３．１算法原理 运用粗糙集理论对交通流数据进行预处理，去掉样本数据 中的冗余属性，并消除噪声和冗余对象，然后以处理过的样本 数据作为支持向量机的输入，实现最终的决策分类。具体步骤 如下： 粗糙集理论对数据的分析主要基于“上近似集”和“下近似 集”两个重要的概念。设集合Ｘ Ｕ为域的任一子集， 是Ｕ上 的等价关系，其“上近似集”和“下近似集”分别定义如下： ＲＸ＝｛ｘ∈ ： ｋ ｎＸ≠ ） ＲＸ＝｛ｘ∈Ｕ：Ｍ Ｃ＿Ｘｌ （２） （３） —（１）把样本数据表示成决策表形式。决策表中每一行描述 个对象，每一列对应对象的一种属性。 是根据Ｒ判断可能属于 的Ｕ中的元素组成的集合； 是根据矗判断肯定属于 的ｕ中的元素组成的集合。集合 关于尺的近似质量定义为： ｃａｒｄ（Ｒ Ｘ） ＯｔＲ（ ）＝—— ｃａｒｄ（ＲＸ） （４） （２）连续屙陛离散化。将条件屙陛划分为若干个子区间，每 个区间用不同的代码如１，２…等表示，以此区间来代替原有实 值，从而使决策表泛化。 （３）决策表形成。采用量化后的条件属性和决策属性值形 成一张二维表格。 如果 （ ）：１，则 相对于 是精确的；否则， 相对于 Ｒ是粗糙的。 （４）对离散化的决策表进行约简。按照以下规则进行约简： 删除符合知识约简概念的属性列；删除表中的重复样本；对冲 突样本进行统计，保留相应数量最多的作为训练样本，去除其 中的冲突样本信息。根据约简得到决策表的核。 （５）支持向量机训练。选定支持向量机的核函数及其参数。 将粗糙集得到的样本作为支持向量机的训练集对支持向量机 进行训练。使用测试样本对支持向量机模型进行检验，若不能 达到预定要求，则重复步骤（２）一步骤（５）。 （６）事件检测。将采集到的交通流数据按照本文提出的算 法进行处理，然后输入到训练好的支持向量机进行分类，最终 得到是否为交通事件的结果。 在许多实际数据的分析中各属性之间可能存在着依赖性， 给定属性子集ＪＲ和Ｐ，如果舢（Ｐ） ，ⅣＤ（ ），则Ｒ依赖于Ｐ， 用严叫ｅ表示。消除这种依赖性，就可以在不影响分类的近似 质量时，以较小的属性集表达整个信息系统。 ２．２支持向量机分类原理 支持向量机产生于模式识别问题，原理就是要寻找—个满 足要求的分割平面，使训练集中的点距离该平面尽可能地远， 目标是构造—个函数将两类模式尽可能分开７－ ｏｌ。 在线陛可分的情况下，存在—个超平面使训练样本完全分 开，超平面可描述为： Ｗ・Ｘ＋ｂ＝０ （５） ３．２算法实现 采用Ｖｉｓｓｉｍ软件仿真高速公路的交通数据进行了算法实 现和性能测试。仿真以一段单向双车道的高速公路为模拟目标 路段，对不同交通条件下的交通流状况进行模拟，模拟数据为 各检测点的车流速度、占有率和流量等交通流参数。共获取 ５００组事件模拟数据和５００组正常交通模拟数据，将这些数据 混合后随机抽取其中的８００组作为训练样本，剩余的２００组作 为测试样本。 ３．２．１交通流数据的粗糙集预处理 其中 是输入向量， 是垂直于分类面的向量，ｂ为常数。最优 超平面应使两类样本的分类最小距离为最大，可以通过解二次 优化问题来获得： ａｉｒｎ咖（∞）＝— １ ｌ ｌｃｔＪ ｌｌ‘ （６） 满足约束条件： Ｙ．（Ｗ・ ＋６）≥１， Ｖｉ＝１，２，…，ｎ （７） 采用拉格朗日乘子法引入乘子求解该二次规划问题，可以 得到最优超平面分类函数： ）一ｇＨ［Ｘ置 ＋６］ … 对于线性不可分的情况，可以把样本 通过非线性映射 函数映射到—个高维的线性属性空间日，将分类问题转化到属 （８） 辆平均速度；车辆密度；路段是否为事件多发路段；天气状况； 是否在集会场所附近等１７个。决策属性Ｄ为交通事件标识。 将获取的交通数据表示成决策表形式。决策表的条件属性 Ｃ包括：下游ｔ时刻、ｔ－１时刻和￡一２时刻的交通流量；上游ｔ时 刻、卜１时刻和￡一２时刻的交通流量；下游 时刻、ｔ一１时刻和ｔ一 ２时刻的占有率；上游 时刻、ｔ一１时刻和 一２时刻的占有率；车 部分决策表属性数据如表２所示， 表示上￡游时刻交通流量， 性空间进行，如果选用适当的映射函数，输入空间的线性不可 日。表示上游ｔ时刻占有率。 分问题在属性空间将转化为线性可分问题。这种非线性映射函 表２部分决策表数据 数就是核函数Ｋ（Ｘ・Ｘ ｏ常用的核函数如表１所列。 表１常用核函数 因此可以得到输入空间的分类判别函数为： ｆ（ｘ）－ｓｇｎ［Ｌ ｏ １ ｔｌＹｉＫ（Ｘｉ＂Ｘ）＋６］ｊ （９） 有率属性中的０￣０．２，０．２～０．３，０．３～０．４，０．４～０．５，＞０．５，平均速度属 属性离散化，将条件属性划分 为若干个子区间，每个区间用不同的代码如１，２…等表示。交通 流量属性中的０－４００，４００～６００，６００～８００，８００—１０００，＞１０００，占 郭 倩，黄林：基于粗糙集和支持向量机的高速公路事件检测 ２００８，４４（３５） ２０５ 性中的＜１６．７，１６．７～２２．２，２２．２～２７．８，２７．８～３３．３，＞１２０；车辆密度属 表４检测结果对比 性中的０￣４００，４００—６００，６００～８００，８００～１ ０００，＞１ ０００分别用０、 １、２、３、４表示；而路段是否为事件多发路段；是否受天气状况 影响；是否在集会场所附近，是否为交通事件的属性值分别用 ０和１表示。表２中的部分决策表数据经过连续属性离散化处 理后如表３所示。 从表４可以看出，与神经网络和单纯的支持向量机相比，本 表３离散化的部分决策表数据 文提出的算法探测率和误报率都优于其它两种算法，同时算法 平均速度 车辆密度 天气状况 多发路段 集会场所 是否事件 检测速度也得到了提高。 ４结论 提出了一种基于粗糙集预处理的支持向量机高速公路事 件检测算法，利用粗糙集理论对样本数据进行约简，减少了表 达信息的属性个数，消除了冗余信息，使得到的数据更具代表 然后对决策表进行约简，首先根据公式（４）计算关于不同 性，构建的支持向量机分类模型，对处理后的样本数据进行了 属性集合的近似质量，如果去掉属性集合中的某个属性后，该 训练。从仿真结果可以看出，这种算法减小了支持向量机的训 屙『生集合的近似质量没有改变，那么就可以约简掉该属性。通 练负担，提高了检测速度和准确性，具有较好的应用价值。 过计算可以得出“车辆密度”依赖于“占有率”，去掉条件屙陛 “车辆密度”后获得的屙Ｉ生集的分类质量并没有下降，因此，可 以去掉“车辆密度”这一条件属性。其他条件屙Ｉ生相对于决策属 参考文献： 性都是不可缺少的；同时可以对决策表中的重复样本和冗余样 ［１１梁新荣，】刘智勇，孙德山，等基于支持向量机的高速公路事件检测阴． 本按照算法步骤（４）进行约简。 计算机工程与应用，２００６，４２（１４）：２１２—２１３． ３．２．２支持向量机模型建立 【２】王兆华，刘志强舰频检测技术在交通安全中的应用【Ｊ１．交通运输工 在对支持向量机进行训练之前，首先要选择判别函数（９） 程与信息学报，２００５（３）：１００—１０３． 中的核函数，表１中的高斯径向基核函数自身参数不多，有利 ［３］李国正，王猛．支持向量机导论【Ｍ】．北京：电子工业出版社，２００５． 于其他参数的确定，因此选用了此核函数。 是径向基核函数 ［４］谢川，倪世宏．基于粗糙集理论的飞行数据模式特征提取叨．计算机 工程，２００５，３１（６）：１６９—１７１． 的宽度参数，此参数直接影响着模型的推广能力，控制了核函 ［５】张文修．粗糙集理论与方法【Ｍ］ Ｅ京：科学出版社，２００１． 数的径向作用范围，用“试算法”进行搜寻，不断调整精度误差 【６］张敬磊，王晓原．交通事件检测算法研究进展［Ｊ】．武汉理工大学学 和宽度参数，可以提高支持向量机的测试精度，经多次尝试确 报：交通科学与工程，２００５，２９（２）：２１５—２１８． 定宽度参数取值为３。将经过粗糙集预处理的数据作为支持向 ［７】Ａｈｍｅｄ Ｓ Ａ，Ｃｏｏｋ Ａ Ｒ．Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｔｉｍｅｓ－ｓｅｒｉｅｓ ａｎａｌｙｓｉｓ ｔｅｅｈ－ 量机的输入向量，对支持向量机进行训练，然后输入测试样本 ｎｉｑｕｅｓ ｆｏｒ ｆｒｅｅｗａｙ ｉｎｃｉｄｅｎｔ［Ｊ］．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｒｅｓｅａｒｃｈ，１９８９（２）：１０３－ 对算法进行验证。 １１３． ３．３算法性能分析 ［８】张良春，夏利民，石华玮．基于模糊聚类支持向量机的高速公路事件 交通事件检测算法的评价指标包括：误报率、检测率和平 检测［Ｊ１．计算机工程与应用，２００７，４３（１７）：２０６—２０８． 均检测时间。在Ｍａｔｌａｂ环境下进行仿真实验，分别采用多层前 ［９ Ｃｏｒｔ９］ｓ Ｃ，Ｖａｐｎｉｋ Ｖ．Ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ， 向神经网络、ＳＶＭ和本文算法对同一组数据进行训练和检验， １９９５（２Ｏ）：２７３—２９７． 各算法的评价指标对比见表４。 ［１ ｏ］边肇祺，张学工．模式识别［Ｍ］．２版．北京：清华大学出／Ｉｇ￣￣，２０００． （上接１９９页） 版社，１９８１． ［１０】Ｔｓｕｍｏｔｏ Ｓ．Ｍｉｎｉｎｇ ｈｉｅｒａｒｃｈｉｃａｌ ｄｅｃｉｓｉｏｎ ｒｕｌｅｓ ｆｒｏｍ ｃｌｉｎｉｃａｌ ［１４］Ｔｓｕｍｏｔｏ Ｓ．Ｍｉｎｉｎｇ ｄｉａｇｎｏｓｔｉｃ ｒｕｌｅｓ ｆｒｏｍ ｃｌｉｎｉｃａｌ ｄａｔａｂａｓｅｓ ｕｓｉｎｇ ｄａｔａｂａｓｅｓ ｕｓｉｎｇ ｒｏｕｇｈ ｓｅｔｓ ａｎｄ ｍｅｄｉｃａｌ ｄｉａｇｎｏｓｔｉｃ ｍｏｄｅｌ［ＣＪ，， ｒｏｕｇｈ ｓｅｔｓ ａｎｄ ｍｅｄｉｃａｌ ｄｉａｇｎｏｓｔｉｃ ｍｏｄｅｌ￣］．Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ， ＬＮＣＳ ２４３１：Ｐｒｏｃｅ ｏｆ ｔｈｅ ６ｔｈ Ｅｕｒｏｐｅａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐｒｉｎｅｉ— ２００４，１６２：６５—８Ｏ． ｐｉｅｓ ｏｆ Ｄａｔａ Ｍｉｎｉｎｇ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ，２００２：４２３－４３４． ［１ １】Ｐａｗｌａｋ Ｚ．Ｒｏｕｇｈ ｓｅｔｓ：ｔｈｅｏｒｅｔｉｃａｌ ａｓｐｅｃｔｓ ｏｆ ｒｅａｓｏｎｉｎｇ ａｂｏｕｔ ｄａｔａ［Ｍ］． ［１５】陈文彬，王友赤．诊断学［Ｍ］．５版．北京：人民卫生出版社，２００２． Ｄｏｒｄｒｅｅｈｔ：Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ Ｐｕｂｌｉｓｈｅｒｓ，１９９１． 【１６】叶山东，朱禧星．临床糖尿病学［Ｍ】．安徽：安徽科学技术出版式社， 【１２】刘清．Ｒｏｕｇｈ集及Ｒｏｕｇｈ推理【Ｍ］．北京：科学出版社，２００１． ２０ｏ５． ［１３】左孝凌，李为箍，刘永才．离散数学［Ｍ】．上海：上海科学技术文献出 ［１７】欧阳钦．临床诊断学［Ｍ】．北京：人民卫生出版社，２００５．
