多种关联规则挖掘算法的研究与分析

程险峰

（长春市公安局交通警察支队，长春 130000）

数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，则称之为关联，关联可以分为简单关联、时序关联、因果关联。关联分析的目的是从大型数据中找出隐藏的属性之间存在的关联和规律。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。

自Agrawal等人首次提出了挖掘顾客交易数据库中项集间的关联规则问题以来，研究人员对原有的算法进行了大量研究和进一步优化，例如，提出了随机采样、并行等思想，使得挖掘规则算法的效率和伸缩性都有了提高，并且推广了关联规则的应用范围。

1 传统的关联规则挖掘算法

1.1 Apriori算法

Apriori算法最初是由 Agrawal等人提出的，Apriori算法是一种经典的规则挖掘算法，通过挖掘布尔关联规则频繁项集挖掘数据。其基本原理如下：

（1）通过事物数据库得到大一项集L1。若L1为非空的，则由L1产生长度为2的候选项集合C2；

（2）对事务数据库中的每一个事务 t，求出 t在C2中的全部子集Ct，对于Ct中的每一个长度为2的候选项集c进行加1操作。

（3）完成一次事务数据库的扫描，筛选出C2中满足最小支持度的项集组成了长度为2的频繁项集合。

（4）重复以上步骤，处理新得到的频繁项集合，直到不再产生频繁项集合为止。Apriori算法的缺点是扫描事务数据库次数过多、在频繁项长度变大的情况下，运算时间显着增加、不能直接用于关系数据库的关联规则挖掘、不适于海量数据环境下的关联规则挖掘。

1.2 基于划分的算法

A.Savasere等人提出的Partition算法和S.Brin等人提出的DIC算法均属于基于划分的算法。这些算法为了节省访问外部存储器I/O的开销，将整个数据集划分为数据块，然后将这些数据块存放在内存中进行处理。与 Apriori算法相比，数据集划分算法高度并行并且候选项目集数量比较大，是各种并行关联规则和分布式关联规则挖掘算法的基础。该算法先把每个分块数据分别分配给某一个处理器生成频集，产生频集的每个循环结束以后，处理器之间通过通信产生全局的候选k-项集，算法的执行时间主要取决于该通信过程，这也是算法的主要瓶颈；另一个瓶颈即每个独立的处理器生成频集所消耗的时间。

1.3 FP-树频集算法

频繁项集挖掘算法 FP-树算法的基本原理是通过两次扫描数据库，将数据信息存到一种高度压缩的数据结构 FP-树里，避免生成候选项集，缩小了搜索空间，减少了数据模式匹配的开销，进而有效地避免了多次扫描数据库和生成大量候选项集所造成的时间、空间上的浪费。但由于 FP-树算法没有充分考虑层次数据的自身特点，在查找频繁项集的过程中，计算了大量的无用项集。使得该算法不能根据层次数据的特点去除关联规则的冗余，从而产生大量冗余关联规则。

2 几种关联规则挖掘算法的改进

基于 FP-树频集算法的改进算法，针对层次结构数据的内在特征，研究高效的去冗余多层关联规则挖掘算法。通过采取聚类的方法，对已有的评价关联规则的支持度和可信度（两个常用的客观性指标），增加一个相关的业务参数，达到对树的进一步划分，不断减小频繁项集挖掘时需要扫描的数据库，进而提高挖掘效率，以便挖掘出收益较高、值得关注的业务。

基于遗传算法的思想改进 Apriori算法，只需要对数据库进行一次扫描，便可以给定一个映射，实现据库到矩阵的映射，以下均可通过在矩阵上的运算来完成所有对数据库的扫描。将某个生物种群对环境的适应性问题转化为求解关联规则最长频繁项集的问题，生物种群的进化过程即为优化问题的求解过程，生物种群的个体即为优化变量。基于遗传算法改进Apriori算法的基本思想：

（1）进行二进制或十进制编码；

（2）根据实际要求，选取遗传算法的适应度函数，并由适应度函数求出频繁 1-项集，进行交叉、变异运算进化该组项集；

（3）进行选择运算产生下一代频繁项集，反复迭代运算若干代，直至最终满足遗传算法的终止条件，此时得到一组最长频繁项集。

3 改进算法分析

（一）基于 FP-树频集算法的改进算法以大型的商业交易为例，每次商业交易都有层次结构树的特征，对整个交易树利用特定的业务参数进行分类，通过自顶向下方式（下层分类是在上层分类结果基础上进行的），依次对各层子树（第1层根节点除外）进行分类。分类过程主要分为以下几个步骤：

（1）对于交易树的第i层，若第i-1层中每个分类交易子树的层数是第2层，则考察整个交易子树；

（2）对于交易树的第i-1层，若其中1-项集不是频繁项集的子树，则将其从交易数据库中删除且不纳入后续分类；

（3）对于交易树的第i-1层，若每棵待分类的交易子树，则计算所有子树两两之间的业务参数。

由于包含这两棵交易子树的2-项集(subtree-i，subtree-j)表示的是这两类交易在事务数据库中同时出现的频率，值越大，则这两类交易子树参数相关性程度可能会越高，按每一层上交易子树之间的业务参数相关程度，根据层次连接聚类算法的方法，就可以得到该层上各交易子树之间相互独立(或说弱利润相关)的分类，然后依此对上层交易数据库进一步进行划分，使得生成k-项集时须扫描的数据库变得越来越小，以此达到提高生成频繁项集和关联规则的效率。因此该改进算法适用于大型的金融交易之中，比如银行交易、大型企业交易等。

表1 算法参数Tab.1 Parameters of algorithm

（二）应用遗传算法的思想改进Apriori算法，应用此算法进行求解，算法参数见表1。

在算法中还随机产生了一组具有2000个事务、30个项的数据。

表2显示了在不同支持度下所得到的最大频繁项集的个数、消耗时间和循环次数。相对于原始的Apriori算法改进后的算法节省了时间，提高了效率。

表2 实验运行结果Tab.2 Result of experiment

4 结论

根据理论以及实验结果分析，改进算法相比与传统的算法，调高了效率，且节省了时间，在实际应用中有一定的可行性，根据不同算法的不同特点，可以应用到相应的领域中去。

［1］冯洁，陶宏才.典型关联规则挖掘算法的分析与比较［J］.计算机技术与发展，2007，17（3）：121-124.

［2］陈沛玲.决策树分类算法研究［D］.中南大学，2007.

［3］Perner P.Recent advances in data mining［J］.Engineering Appli-cations of Artificial Intelligence，2006，19（4）：361-362.

［4］刘建.商务智能中关联规则挖掘算法的研究及应用［D］.长春理工大学，2009.