基于Apriori算法的公安交管业务异常数据研判模型

基于Apriori算法的公安交管业务异常数据研判模型

陈跃1陈有贤2杨友磊1杨灿3

陈跃1陈有贤2杨友磊1杨灿3

1安徽科力信息产业有限责任公司安徽合肥230088;2安徽畅通行交通信息服务有限公司安徽合肥230088;3北京航空航天大学合肥创新研究院安徽合肥230000

摘要：针对公安交管业务异常数据人工评估效率低、覆盖范围小、难以为业务开展提供有效指导等突出应用问题，研究基于Apriori算法的公安交管综合业务相关性研判模型，为公安交管业务异常数据分析研判的常态化开展提供有效的技术保障，有效增强公安交管核心业务数据质量。

关键词：公安交管业务异常数据；关联规则；Apriori算法

1引言

随着信息化建设的逐步推进，公安交管业务的信息化程度不断提高，同时也积累了大规模的公安工作数据和社会信息。如何将庞大的信息转换为公安交管工作所需要的？公安交管业务异常数据研判成为我国各地公安交管业务工作中非常重要的组成部分，是各级公安部门准确有效的开展业务工作的依据。交管业务异常数据研判能够为决策者和组织机构提供有关目标车辆及其周围环境的知识。在传统的信息环境下，公安交管机关的分析工作主要是对异常数据进行分析、综合、评价，最终形成综述报告、述评报告、研究报告等多种形式的过程。交管业务异常数据研判可以进一步发掘交通事故、设备故障等问题。

数据挖掘等分析技术在交管业务异常数据研判中的应用已经成为国内外研究的重要课题。数据挖掘能够从大量结构化和非结构化的数据中提取有用的信息和知识[1]。中科院计算机研究所的智能信息处理重点实验室研制开发的多策略数据挖掘平台MSMiner系统[2]，此系统集成了关联规则挖掘算法；复旦大学研制开发的ARMiner系统，该系统采用的关联规则挖掘算法是基于Apriori的改进算法。国内数据挖掘技术在公安业务的应用还是一个比较年轻的领域，目前主要集中在情报分析方面，比如北京东方金指开发的一套适合公安刑侦部门使用的信息系统、神州数码开发的北京市公安局刑侦信息管理系统等。李晓冰应用Apriori算法对诈骗案件内部属性之间存在的关系进行挖掘,实现了从大量诈骗案件信息中获取潜在的、有用的情报信息。汤毅平使用Apriori算法对犯罪人员的数据进行关联规则分析，寻找重新犯罪的潜在规律。

2关联规则基本概念

数据挖掘中一个最基本、最重要的问题就是关联规则的挖掘。下面就关联规则涉及的基本概念加以解释。

（1）置信度

假设数据库Z中在包含项目集合A的记录中有X%的记录,也同时包含了项目集合B，则X%就是关联规则A→B的置信度(confidence)。置信度是表示以前件为真时，后件也为真的可能性有多大。

（2）支持度

假设数据库U中有V%的记录是既包括了项目集合A同时也包括项目集合B，那么V%就是关联规则A→B的支持度(Support)。支持度是表示在所有的事项记录里出现项目集合A和项目集合B的并集的概率有多高。

用数学形式表述关联规则分析：

假设K={K1，K2，…，Km}是项目集合，数据库事项的集合F表示的数据是目标相关的，当中每一个事项H是项的集合，使得H⊆K。HKF作为每一个事项的标识符号。设项集为X，事项W包含X当且仅当X⊆W。关联规则X→Y，其中X⊂K，Y⊂K，且X∩Y=∅。规则X→Y在事项集F中成立，支持度为A，置信度为B，则：支持度(X→Y)=P(X⋃Y)，表示在数据库F中至少有A%的记录包含X⋃Y；置信度(X→Y)=P(Y|X)，表示在数据库F中包含的X记录中至少有B%的记录同时也包含了Y。

（3）强关联规则

强关联规则的定义是置信度大于客户设定的最小置信度(min_conf)，支持度也大于客户设定的最小支持度(min_sup)的关联规则。对强关联规则进行挖掘是数据挖掘的主要任务。

（4）频繁项集

项集是项的集合。如果项集K的支持度大于等于客户给定的最小支持度阀值，则K为频繁项集。

3Apriori算法

1993年，R.Agrawal和R.Srikant提出了Apriori算法。Apriori算法是数据挖掘领域重要的十大算法之一。此算法采用逐层搜索形式的迭代方法，通过对数据库的多次扫描来发现所有的频繁项集。对数据库进行扫描，首先找出频繁项集1的集合，把该集合记为K1，用K1来找频繁项集2的集合，记为K2，再用K2来找K3，一直下去，直到找不到新的频繁项集为止。每一层K被找出来，都必须对数据库扫描一次。

生成的关联规则：

（1）每一个频繁项集K，可以生成K的全部非空子集。

（2）对于K的每一个非空子集X，假如，那么“X→(K-X)”就是输出规则。K-X表示在项集K中去掉S子集的项集。

4Apriori算法在公安交管业务异常数据研判中的应用

4.1基于Apriori算法的异常业务数据研判模型构建技术解决方案

Apriori算法是挖掘数据之间关联性有效方法，通过Apriori算法可找到交管业务数据之间的关联规则，进而通过关联规则可对异常业务数据进行研判。根据已有的交管数据完成研判模型的训练，最终向训练好的模型中传入实时交管业务数据，判断是否出现异常业务数据。

4.2用于公安交管业务数据的Apriori算法及优化

公安交管业务信息系统中存有大量交通违法违规记录，在拟定的Apriori算法下对大量的违法违规行为案例记录进行分析，从而发现违法违规行为的规律、趋势，了解不同违法违规行为之间的关联。

在交通违法违规案件中有如下几种关系：

人与人的关系：交通肇事人与被害人的关系；交通肇事车辆与同行人的关系、与同案犯的关系；等等。

人与事的关系：交通肇事人与发生在案件整个过程之中的一些事件的关系，该交通肇事人对事件的影响等。

人与物的关系：交通肇事人与涉案相关物证（肇事车辆、道路设施及其他相关物）的关系，需要弄清楚物属关系，物品在案件中所起到的作用等等。

事与物的关系：案件事实与物证的关系。

由于公安机关的交管业务所具有的特殊性，已有的Apriori算法没办法最大限度地适应公安机关交管业务分析的新趋势，有以下不足之处：

（1）Apriori算法对新增加的项目敏感度低。交通违法违规行为的记录不断地变化，常规的违法违规行为逐渐发生的同时，新型违法违规行为也逐渐增加，增加或减少项目之间的关联一有更新就会生成新关联规则。但已有的Apriori算法没有注意此问题，当要计算集合支持度时，把数据库全部的违法违规行为记录都列为基数，就算增加了新项目，也无法发现最新的频繁项集，就无法生成最新的关联规则，不适应关联规则挖掘的要求。也就是说，在对公安交管信息的分析实践应用中，不可能及时、敏锐的发现新型的违法违规行为。

（2）Apriori算法没有考虑数据库中不同的项集的重要性是不同的，这样会致使那些虽然出现的频率少但具有重要价值的项集被忽略不计了。实践当中应用Apriori算法对公安交管信息进行分析时，就往往忽略了那些交通事故情节特别严重、社会危害性特别大的肇事行为。

本文立足提高新型交通违法违规行为的敏感度和注重发现性质严重的违法违规行为，提出了两种用于优化Apriori算法的方法，希望能满足公安交管信息分析的实际需要和适应新趋势发展的要求。

优化方法一：

对频繁项集算法的优化，既要考虑公安交管部门对信息中的新事项的敏感性的需求又要考虑怎样提高数据挖掘的效率。数据库是按时间的先后顺序不停地累积数据，在新的算法中也把按时间的先后顺序对数据进行划分，新的关联规则的产生不再考虑以前的所有数据集，而是依据在一个期间内新增加的数据集合和以前生成的频繁项目集，不断地更新频繁项目集。这样，空间上不再储存之前发现的数据集，时间上也不再对数据库中已有的数据集进行扫描，极大节约了频繁项目集的发现时间，大大提高了挖掘关联规则的效率。

优化方法二：

本方法先引入参数i（1<i<∞）。数据库的规模是越来越庞大，但事项的增加比较平稳，扫描整个数据集的时间比只扫描支持度不小于最小支持度/i的频繁项目集的时间长的多，所以在找出频繁项集的过程中，只保存支持度不小于最小支持度/i的频繁项目集和新增的数据集，这样就极大地提高了发现频繁项目集的效率。假设现有数据库中的数据集为K，新增数据集为k，整个数据库为（K+k），思路：假设利用Apriori算法取得数据集K的支持度不小于最小支持度/i的频繁项目集T’（K），T’(K)里项目集支持度Count和项目集总数Countall。假如有项集K1和K2，项集1在K1是频繁项集，在K2不是频繁项集，那么1.Countall=（|K1|）。假如项集1在K1和K2都是频繁项集，那么1.Countall=（|K1|+|K2|）。新增了数据集k之后的思路：

（a）依靠新数据集k和T’(K)获得支持度不小于最小支持度/i的频繁项集，增加入(K+k)的支持度不小于最小支持度/i的频繁项集T’(K+k)中。项集1，E∊T’(K)，E.Supportort=(1.Count(k)+1.Count(K))/(1.Countall|K|+|k|)，支持度E.Support≥最小支持度/i的项集1增至（K+k）的频繁项集T’(K+k)。

（b）应用Apriori算法找出新数据集k的支持度不小于最小支持度/i的频繁项集T’（K），k中项集E为E.Supportort=1.Count(k)/|k|。

（c）项集E，E∊T’(K)且E∉T’(K+k)，就将E增值T’(K+k)。

（d）再用Apriori算法在支持度不小于最小支持度/i的频繁项集T’(K+k)中获取支持度不小于最小支持度的频繁项集T（K+k）。

5结束语

本文针对公安交管业务异常数据人工评估效率低、覆盖范围小、难以为业务开展提供有效指导等突出应用问题，研究基于Apriori算法的公安交管综合业务相关性研判模型，分析了已有的Apriori算法在公安交管异常数据综合研判方面的不足之处，并提出了优化方法，为公安交管业务异常数据分析研判的常态化开展提供有效的技术保障，增强公安交管核心业务数据质量。

参考文献:

[1]潘华,项同德.数据仓库与数据挖掘原理、工具及应用[M].北京:中国电力出版社,2007.

[2]秦亮曦,史忠植,刘少辉,等.多策略数据挖掘平台MSMiner的元数据管理[J].计算机应用,2003,z2:34-36.