基于改进Apriori算法的水政数据关联规则分析研究

陈潇潇+++蔡迎归

摘 要：数据挖掘中的关联规则挖掘能够发现大量数据中项集之间潜在的关联，运用关联分析方法对水事违法案件数据进行挖掘分析，从而总结出水政执法队伍在监察过程中存在的问题，以期提高水政执法能力和水平，有效地预防、遏制涉水违法现象。

关键词：改进Apriori算法 水政 关联规则

中图分类号：TP311 文献标识码：A 文章编号：1672-3791（2017）09（c）-0202-02

随着互联网以及计算机相关技术的飞速发展，政务信息化的不断推进，水政执法部门积累了海量的水事违法案件数据，而目前对于这些数据的使用多限于统计、查询等传统方式，其潜在的使用价值还远没能得到充分的挖掘和实用，对于隐藏在这些数据后的规律、产生的原因往往无法得知，从而不能有针对性地对水政监察管理中已存在的问题进行相应的变革。传统的处理数据方式，已经难以适应于日益增长的数据规模，“信息爆炸”但“知识贫乏”，已成为一个现实问题。

由此，应用数据挖掘中的关联规则对水政数据进行分析，通过对所采集到的水事违法案件数据进行预处理、数据挖掘等步骤，从中总结出水政执法队伍在监察过程中存在的问题，以期提高水政执法能力和水平，有效地预防、遏制涉水违法现象。

1 关联规则Apriori算法

Apriori算法是最经典的关联规则挖掘算法，是由Agrawal首次提出的，是基于计算候选集的递推方法，其思想是利用已知的高频数据集推导其他高频数据项集，是一种宽度优先算法。该算法的主要工作在于寻找频繁项集，它利用了频繁项集的向下封闭性（即频繁项集的子集必须是频繁项集），k-项集用于探索（k+1）-项集。Apriori通过K次扫描数据库来发掘频繁K项集，大量的时间浪费在IO上，并且以数据库中各项目的重要程度相同以及各项目分布均匀为前提，容易忽略概率小但重要性高的项目。

2 Apriori算法的改进

本文从候选项目集的支持度计算过程和小候选项目集的规模两个方面对原Apriori算法进行优化。

2.1 候选项目集的支持度计算过程

在整个事务数据库中，如果想要求得一条事务项的集合，可以将该事务项分解为单一的元素项，对单一元素项的集合在取交集的结果即是。根据这一定理，对Ck的计数工作，不需要再去频繁的扫描数据库，而是根据候选项集的集合可以分解为其项集元素在数据库中的集合的交集这一规则，利用已经生成的候选项集C1来推导得到。这样，在计算支持度的计数的过程中，只扫描一遍数据库，时间开销会低于原算法。

2.2 缩小候选项目集的规模

在生成频繁k-1项集后，对整个候选集进行检查裁剪，判断LK-1包含的项集数是否小于其项集的维度。若小于，则不能生成k项候选集的，算法即可终止。在候选集LK-1中的项集Ii和Ij连接生成X时，对于X的每一个项集元素同样进行检查，若项集元素个数小于候选集的维度，则该项集元素不会出现在生成k维的候选项目集中，可以删除掉以减小候选集的规模。

通过上述两个方面的优化，可以生成一个完整的基于支持度计数工作和候选项目集规则优化的改进方案， 从而使算法效率有较大的提高。

3 Apriori算法在水政数据分析中的应用

3.1 水事违法案件信息的预处理

在水政监察管理系统的案件信息中，去除重复数据，挑选出科学的、安全、适用于数据挖掘应用的属性数据进行数据清洗。对于原始数据中某些属性为空缺值的记录，尽量补充缺失属性。如用身份证件号码填补年龄、籍贯的空缺、案件类型的空缺可以通过分析其他属性获得。数据清洗后，对某些原来没有的属性按需要进行生成，通过泛化、属性离散化处理将数据转换以构成一个适合数据挖掘的描述形式。如将案件类型泛化处理，取河道案、水工程案、水资源案、水土保持案和其他类案件五大类；年龄由出生日期转化生成，并概化为少年（17岁以下）、青年（18～40岁）、中年（41～65岁）、老年（66岁以上）四个年龄段；将发案时间离散化处理为上午、下午、夜间、深夜；发案季节由发案时间转化，离散化处理为春（3～5月）、夏（6～8月）、秋（9～11月）、冬（12～2月）；发案地点划分成对应水政监察总队所管辖的几个地区；经济损失泛化划分为一般、较大、严重、重大；职业泛化为无业、事业、企业、个体四大类；文化程度泛化为小学及以下、初中、高职中专、专（本）科、硕士及以上五类；户籍略去县市、街道等细节信息，简化为各个省份名称。

3.2 改进Apriori算法对水事违法案件信息进行关联规则挖掘

数据做好预处理工作之后，根据造成经济损失的不同程度，进行项目属性权值的设置，如水事违法案件中造成重大经济损失的案件，其重要和危害程度明显要高于其他案件，但它的发生概率通常较小而容易被忽略，需要增大其属性权值。然后通过已经由程序实现的优化算法，找出相关属性之间的强关联规则，如案件类型、发案地点、发案时间段、发案季节、经济损失、违法人员年龄段、职业、文化程度以及戶籍等属性之间的强关联规则，并对结果进行解释评估，为水政执法部门制定重要决策，合理部署水政执法工作提供宏观决策依据。

4 实验结果及分析

以经过预处理后的水事违法案件信息作为数据源进行仿真实验，案件信息记录5400条，运用经典关联规则Apriori算法和改进后的Apriori算法，通过设置不同的事务数量、不同的支持度、不同的项目个数，统计两种算法的运行时间和生成强关联规则数量，对比分析算法的性能和效率。实验测试采用Matlab语言编写程序，在Matlab平台下进行调试，CPU采用的Intel（R）i3-3217U，内存4G，操作系统为64位Windows7。挖掘结果得出了采用同样最小支持度对于不同事务记录条数进行比较时，两种算法在执行时间的区别。从实验结果来看，改进的Apriori算法实现了预期的目标，与同类算法相比，改算法具有挖掘结果准确、速度快、运算量小、时间短、空间利用率高等特点。同时，也反映了这两种算法的最小支持度与时间的关系：最小支持度最高，所需要的时间越多；对于不同的最小支持度，改进的Apriori算法所需时间比经典Apriori算法所需要的时间短。通过以上分析，综合关联规则挖掘结果，得到如下结论，水事违法案件虽然类型多情况复杂，但是违法人员结构极其类似，年龄趋于两极化，青少年和老年居多，而且文化素质低，特别是无业人员在违法人员中所占比重较大。水土保持案和水资源案较多的在A1地区，在A2地区夜间多发盗窃设备的水工程案

5 结语

本文详细说明了关联规则算法Apriori在水事违法案件信息挖掘中的应用过程：首先简述了关联规则基本概念和Apriori算法原理；其次提出了一个完整的基于支持度计数工作和候选项目集规则优化的改进方案，从而使算法效率有较大的提高；最后以经过预处理后的水事违法案件信息作为数据源进行仿真实验，对关联规则挖掘结果进行分析，从而提高水政执法能力和水平，有效地预防、遏制涉水违法现象。

参考文献

[1] 苗苗苗，王玉英.基于矩阵压缩的Apriori算法改进的研究[J].计算机工程与应用，2013，49（1）：159-162.

[2] 付沙，周航军.关联规则挖掘Apriori算法的研究与改进[J].微电子学与计算机，2013，30（9）：110-114.endprint