基于关联规则的数据挖掘Apriori算法的两种优化分析

张 超

（亳州学院 电子与信息工程系，安徽 亳州236800）

Apriori算法是关联规则挖掘技术的最基本算法［1］.目前关联规则的并行数据挖掘算法大都以Apriori算法为基础，它具有无可替代的独特地位，其效率的优化研究已成为广大学者关注的热点.Apriori算法本质主要包含两个方面问题，第一个是找出事务数据库中所有的频繁数据项集.第二个是如何生成强关联规则.两个方面相比较，第一方面的问题是算法的核心［2］.基于此，对算法进行优化，就应把重点放在找出频繁数据项集方面.

1 Apriori算法概述

1.1 原理

Apriori算法的核心思想是基于频繁项集理论的递归方法，采用逐层搜索的迭代方法挖掘出在目标事务数据库中所有频繁项集，直至找到最高阶频繁项集即止，最后通过对获得的频繁项集进行计算得到强关联规则［3-5］.其中，现设候选k-项集集合表示为Ck，频繁k-项集集合表示为Lk.经过一次扫描后，即可快捷得出L1.执行第k（k＞1）次扫描时，由Lk-1生成Ck.然后根据Ck继续进行扫描，对照每个元素的支持度，删减不符合者，最后即可求得Lk.依据此思路可依次求得Lk+1，Lk+2，Lk+3…….若某次计算Ck为空时，算法自然结束.

1.2 生成频繁项集的过程

Apriori算法的基本思想是基于频繁项集生成过程，使用递推方式推演出频繁项集，使用频繁项集Lk-1产生频繁项集Lk，其过程分为连接和剪枝两步［6］.Apriori算法生成频繁相集的第一步骤为连接步，即计算Lk由 Lk-1自身作连接得到 Ck.假若 Lk-1中含有项集 l1及 l2，li为（k-1）项集，规定 li［j］为 li的项，j为项的序号.对于 li，使得 li［1］＜li［2］＜…＜.对于 l1和 l2，假设 l1和 l2是可连接的，那么它们从第 1 个到第（k-2）个的项都应当分别对应相等.即（l1［1］=l2［1］）∩（l1［2］=l2［2］）∩…∩（l1［k-2］=l2［k-2］）∩（=l1［k-1］＜l2［k-1］）.其中 l1［k-1］＜l2［k-1］限定不产生重复现象，最后的结果项集可记作：（l1［1］，l1［2］，…，l1［k-1］，l1［k-2］）.

第二步骤为剪枝步，按照在给定的事务数据库D中，任意大项集的子集都是大项集，任意弱项集的超集都是弱项集［7］的性质，可以删除Ck中对应的支持度不满足的某个子集.

1.3 主要步骤

设min-sup表示最小支持度，则有以下步骤：（1）扫描数据，并生成C1；（2）根据min-sup的要求，由C1推导出 L1；（3）k＞1 时，按照（4）、（5）、（6）的次序重复执行；（4）对 Lk-1执行连接和剪枝操作，并得出 Ck；若Ck=Φ，执行（7），不然，执行（5）；（5）按照 min-sup 的要求，由候选 Ck推导出 Lk；（6）如 L≠Φ，k=k+1，执行（4）；否则执行（7）；（7）由min-sup的具体要求，基于频繁项集进一步推导出强关联规则.

2 Apriori算法的应用求解过程

一个大型购物中心的数据库事务包括T1、T2……T9，|D|=9.基于Apriori算法求D中频繁项集，Ti表示事务名，Pi表示商品名，Ci表示候选 i—项集集合，Li表示频繁项集， 规定 min-sup=2，T1={P1P2P5}、T2={P2P4}、T3={P2P3}、T4={P1P2P4}、T5={P1P3}、T6={P2P3}、T7={P1P3}、T8={P1P2P3P5}、T9={P1P2P3}.

具体求解过程如下：第一次C1→L1，按照min-sup=2的要求，对原数据库D进行扫描C1={{P1}{P2}{P3}{P4}{P5}}各项集的支持度分别为6、7、6、2、2.继而对C1扫描，不需要删除任何项目，求得L1=C1且支持度不变。

第二次求解C2→L2，在第一次求解出L1结果的基础上，进一步求得C2=L1∞L1。C2={{P1P2}{P1P3}{P1P4}{P1P5}{P2，P3}{P2，P4}{P2，P5}{P3，P4}{P3，P5}{P4，P5}}，在剪枝步中 C2无须删除.对其扫描后可求得 C2的各项支持度分别为 4、4、1、2、4、2、2、0、1、0. 结合支持度 min-sup=2 的要求， 删除不满足后三项要求者即可得到 L2。L2={{P1P2}{P1P3}{P1P4}{P1P5}{P2，P3}{P2，P4}{P2，P5}}，其中各项的支持度分别为 4、4、1、2、4、2、2.

第三次求解C3→L3，在第二次的结果的基础上，对L2进行自身连接得到C3，再由其对应的支持度数即可求得L3.步骤如下：

（1） 执行连接操作：C3=L2∞L2={{P1，P2}，{P1，P3}，{P1，P5}，{P2，P3}，{P2，P4}，{P2，P5}} ∞ {{P1，P2}，{P1，P3}，{P1，P5}，{P2，P3}，{P2，P4}，{P2，P5}}={{P1，P2，P3}，{P1，P2，P5}，{P1，P3，P5}，{P2，P3，P4}，{P2，P3，P5}，{P2，P4，P5}}.

（2）执行剪枝操作：根据有关性质，上步结果中的后4个均要删除.以{P1，P3，P5}为例，其对应的2项子集分别包括{P1，P3}、{P1，P5}、{P3，P5}.L2中存在{P1，P3}、{P1，P5}但不包括{P3，P5}，因而不是频繁的.剪枝后得到 C3={{P1，P2，P3}，{P1，P2，P5}}.

（3）结合统计支持度，C3的各元素均符合.即 L3={{P1，P2，P3}，{P1，P2，P5}}.

第四次扫描：求解 C4=L3∞L3，L3∞L3={{P1，P2，P3，P5}}，但其子集{P2，P3，P5}不属于 L3范畴，因此它不是频繁的，理应删除.至此求解全过程结束.

3 Apriori算法效率的优化

综上分析，进行推导Ck的连接操作通常要做大量繁杂的比较.但即便如此，却并不保证得到的一定为候选项集.这样一来，连接操作的有效性就比较差，往往在许多时候都是无效的.若能够去除无效的连接比较，简化剪枝步骤，而使执行连接之后得到的都归属于候选项集，那么算法效率将得到真正的优化提升.基于这种思路，笔者提出一种优化后的Apriori-A算法.

3.1 Apriori-A算法思想

首先，执行对 Lk-1扫描，并记录项集：{l1［1］}，{l1［1］，l1［2］}，…，{l1［1］，l1［2］，…，l1［k-2］，l1［k-1］}，{l2［1］}，{l2［1］，l2［2］}，…，{l2［1］，l2［2］，…，l2［k-2］，l2［k-1］}，{l3［1］}，….基于描述方便，令 li是一个 k 项集，li={li［1］，li［2］，…，li［k-1］，li［k］}，由算法性质可知，若 li归属于 Ck，那么 Lk-1应包含其以下的 k-1 个 k-1 项集.综上分析，进而得到规律：在扫描中，设项集{li［1］}，{li［1］，li［2］}的出现机会分别为 Q1和 Q2，那么必有 Q1≥k-1，Q2≥k-2.以此类推，项集{li［1］，li［2］，…，li［k-1］］}出现机会 Qk-1≥1.假定 Q1、Q2分别是{li［1］}，{li［1］，li［2］}的扫描次数，若 k-1＞Q1，则执行删除操作，即将 Lk-1中凡是以 li［1］开始的 k-1项集一律删除.假若 k-1≤Q1，则将 Q2与 k-2 进行比较.依此类推分析，假若 k-2＞Q2，把 Lk-1中凡是以项集{li［1］，li［2］}起头的全部删除，如果k-2≤Q2，就接着与后面的项集扫描次数继续比较.

这种优化的策略，实际上是以数字比较和删除操作为手段，进而实现了删除Lk-1中大量的无效项集.此优化算法的优点在于事先大大减少了冗余的连接，最后以连接操作生成k项集，只要通过一次比较操作即得出是否归属于Ck.该优化思想基于先删除后连接，以减少冗余的连接为前提条件，进而实现减少剪枝步中的判断量，最终实现提升数据挖掘效率的目的.

3.2 Apriori-A算法应用分析

例 1： L3={{O，P，Q}，{O，P，T}，{P，Q，R}，{P，Q，S}，{P，R，S}，{Q，R，S}，{Q，S，T}，{R，S，T}}.

基于Apriori-A算法，其删减操作过程见表1.执行得到结果={{P，Q，R}，{P，Q，S}}，然后执行它的自连接操作，最终得到{P，Q，R，S}的四项集.由于子集{Q，R，S}∈L3，所以 C4={P，Q，R，S}，通过验证，得出结论是完全正确.

表1 删减L3中项集的过程

本例中，如执行经典 Apriori算法，则首先执行连接操作，求得{O，P，Q，T}、{P，Q，R，S}两个项集.然后执行剪枝步骤，若在最坏的极端情况下，则要对{O，P，Q}、{O，P，T}、{O，Q，T}、{P，Q，T}、{P，Q，R}、{P，Q，S}、{P，R，S}、{Q，R，S}等8个项集都要判断其是否在L3范围之内.综上分析，在本优化算法中，只需执行连接操作求得相应的四项集，在后面的剪枝步骤中，再判断其子项集{Q，R，S}同L3有无归属关系成立即可.相比而言，优化后的Apriori-A算法效率明显地提升.

3.3 Apriori-B算法思想

通过深入分析和研究后，还可得知另一结论：判别一个项集是否归属于Lk，对Ck中的所有对象还需进一步明确其支持度计数.一般来说，用于关联规则挖掘的数据库的数据量都是非常庞大的.从先前分析来看，繁琐冗余的扫描则在很大程度上使得算法的效率大幅降低.试想，假如能够应用某种策略使得扫描次数大幅简略，则算法的优化就自然轻松实现.这样一来，问题的根源在于运用何种恰当的策略能够使得数据库的扫描大幅精简.

按照上述思路，现提出另一种优化策略.具体如下：引入一个C’K，在此集合中的任一对象标记成＜TID，{XK}＞，XK表示为潜在的频繁K—项集.C’K作如下特性的定义，数据库表示为D，事务表示为T，若k=l，C’K和D是一致的，其本质上可看作是用{I}代替了项目i.若K＞1，C’K中包含的对象同T保持完全相同，即可表示为：＜t.TID，{C∈C’K∣C⊂t}＞.归结到实际，就是先得到频繁 1-项集，并同步生成了 C’1.

从第二步起始，诸如此类，即可往复循环，直至不再有频繁项目集的生成.现假定第k步出现了循环，基于描述方便，分为两步说明.其一，先由第K-1步中得到LK-1，对其连接生成候选频繁K-项目集CK，并同步生成集合C’K，继续在C’K中搜索，即可统计出对应CK的支持度.究其根源是基于这一理论：如果一个事务不包含任何候选K-项集，则C’K中将没有这个事务的目录，所以C’K的目录数据必然小于数据库中事务的数据，特别是当k值很大时［8-10］.并且这种情况，极有可能因k值的增长，而呈现愈来明显的趋势.进而可以推知，当K值较大时，由于事务T基本上没什么候选项，所以任一目录同对应事务T相比，均要小于.同理，若当K值较小时，对于任一个T的候选K-项目集，C’K的一个目录就可以完全涵概，所以任一目录同对应事务T相比，均较大.

3.4 实例算法应用分析

例 2：有一数据库 D，包含 4 个事务表示为 T10、T20、T30、T40，support表示其支持度，T10={P1，P3，P4}，T20={P2，P3，P5}，T30={P1，P2，P3，P5}，T40={P2， P5}，最小支持度 min-sup=2.

按照经典的Aprior算法对数据库D进行扫描后得到C1，其中TSD分别包括{P1}、{P2}、{P3}、{P4}、{P5}五项，求解得到各自的support分别对应为2、3、3、1、3.由min-sup=2，在C1中继续扫描则需要删除{P4}，即求得L1的 4 项分别包括{P1}、{P2}、{P3}、{P5}.对 L1扫描后，可得到上述 4 项各自的 support分别对应为 2、3、3、3.继续求 C2=L1∞L1，其分别包括{P1P2}、{P1P3}、{P1P5}、{P2P3}、{P2P5}、{P3P5}等 6 项，对其扫描得到各自的 support分别对应为 1、2、1、2、3、2.由 min-sup=2，在 C2中继续扫描后需要删除{P1P2}、{P1P5}，剩余的即构成了 L2，其内在四项分别为{P1P3}、{P2P3}、{P2P5}、{P3P5}等 ，扫描后得到对应的支持度分别为 2、2、3、2.继续求解 C3=L2∞L2，求其结果仅包括{P2P3P5}，扫描后其支持度为2，符合min-sup要求，因此L3=C3，其结果也仅包括{P2P3P5}且支持度为2.

若执行优化的Apriori-B算法，其步骤可分为三步.第一步求解L1，对数据库D扫描得到C’1，其四个事务的构成分别为{P1}，{P3}，{P4}；{P2}，{P3}，{P5}；{P1}，{P2}，{P3}，{P5}；{P2}， {P5}等四项.对 C’1继续扫描可得到 L1，其四个事务的构成分别为{P1}、{P2}、{P3}、{P5}四项，对应 support分别为 2、3、3、3.

第二步求解 L2，先计算 C2=L1∞L1，其构成包括{P1P2}、{P1P3}、{P1P5}、{P2P3}、{P2P5}、{P3P5}等六项.对 C2扫描后可以得到C’2，其内在的四个事务的值分别为 {{P1P3}}、{{P2P3}{P2P5}{P3P5}}、{{P1P2}{P1P3}{P1P5}{P2P3}{P2P5}{P3P5}}、{{P2P5}}等四项.继续对C’2扫描，结合最小支持度min-sup=2的要求，即可求得L2的四项其分别为{P1P3}、{P2P3}、{P2P5}、{P3P5}，对应支持度分别是 2、2、3、2.

第三步求解 L3，首先计算 C3=L2∞L2，求得 C3仅包含一项{P2P3P5}，继续对 C3扫描可得到 C’3.C’3包含两个事务T20、T30，对应的构成值分别为{{P2P3P5}}、{{P2P3P5}}.以此类推，继续扫描 C’3即可求出 L3，只含有一个对象{P2P3P5}，且其支持度为2.

经对比分析后不难看出，应用Apriori-B算法仅仅是在第一步扫描对象是原数据库D，而在后续的第二和第三步中，扫描对象均为前一次所得到的候选数据库C’k.并且可知，若k值不断增大，同原数据库D相比而言，前者要远远小于后者.如此来看，采用Apriori-B算法，确实可减少I/O时间，可以大幅提升算法效率.

3.5 算法效率实验验证

以亳州学院教学评价系统数据进行挖掘为例，实验环境：Win7，eclipse，Java编程语言，计算机配置酷睿i5 3.0 GHz，内存4 G，硬盘1 T.算法运行时长对比分析见图1.经典Apriori如①，Apriori-A如②，Apriori-B如③.从图1的情况可观测到①的线条始终位于②、③之上.运用改进后的Apriori-A算法、Apriori-B算法在事务数相等的情况下运行时间较经典Apriori算法更短，效率更高.从事务数规模不断增大的趋势来看，算法效率改善的愈加明显，算法优化具有较强的应用意义.

图1 算法运行对比分析

4 结语

频繁数据项集的生成是关联规则挖掘的核心问题.Apriori—A算法思想是从删除无效连接，以减少冗余的连接为前提条件，进而实现了减少剪枝步中的判断量；Apriori—B算法则以候选事务数据库替代原数据库D，实现了大幅减少扫描次数.经定性分析和定量验证，两种优化策略均在特定案例可以使之效率有效提升.但两种优化算法依然存在较为繁琐的数据库扫描操作，算法效率仍有较大的提升空间.