一种基于链表的改进Apriori算法∗

顾 鹏

（南京理工大学计算机工程与科学学院 南京 210094）

1 引言

随着大数据时代的到来，关联规则挖掘日益受到人们的重视，且在银行、保险、电商、零售等行业的应用也越来越广泛。作为关联规则挖掘的经典算法，Apriori算法受到了广泛的关注和研究。同时，利用Apriori算法挖掘频繁模式也是构建商务智能系统前期数据预处理和特征提取的重要技术手段之一。经典的Apriori算法需要多次扫描事务数据库，候选-N项集通过频繁-N-1项集的连接产生，生成大量候选集，进行了大量的无用计算，尤其在项目数较多的情况下，这种情况更加明显。

针对Apriori算法的性能瓶颈问题，人们开展大量的研究对Apriori算法进行改进，以提高其效率。较有名的是FP-Growth算法［17］，该算法采用树和链表的混合结构，只需扫描两次事务数据库，且无需产生候选项集，但算法的局限性体现在频繁的构造条件模式基，对于大规模数据集来讲，FP-Growth算法所构建的FP-Tree会非常庞大，可能无法存储于内存之中。

FP-Growth算法之所以高效，是因为采用特殊的数据结构将事务数据库压缩存储到内存中，避免了重复扫描事务数据库带来的性能瓶颈。学者们也采用了其他的数据结构来对事务数据库进行压缩存储，并在此特殊的数据结构上挖掘频繁项集。文献［3］提出用十字链表来压缩存储数据结构，文献［7］首先将事务数据库转化为关系矩阵，并使用正交链表对该矩阵进行存储，从而可以通过对链表节点集合进行操作实现频繁项目集的挖掘。文献［8～9］同样采用特殊的方法压缩事务数据库，并通过各自特殊的方法挖掘频繁项集。图作为经典的数据结构，也被许多学者用到频繁项集的挖掘中。文献［6］将事务数据库压缩为一个有向图进行存储，有向图顶点为项，边为事务编号集合，通过对该图的遍历来搜索频繁项集，与之不同是，文献［1］采用以事务为顶点，项为边的无向图来存储事务数据库，在挖掘频繁-K项集时，混合Apriori算法和基于图的频繁项集挖掘算法，在K较小时用Apriori算法，在K较大时用图挖掘算法。文献［4］分别用布尔矩阵（生成矩阵）和图两种结构来进行频繁项集挖掘。文献［2］采用PPC-Tree和N-list的数据结构，对项进行pre-order和post-order编码，极大压缩了事务数据库，提高了算法的效率，文献［15］混合利用Apriori算法和FP-Growth算法来挖掘频繁项集。也有利用特殊的方法挖掘频繁项集，以改进Apriori算法的效率，文献［14］根据事务数据库中事务的长度进行倒序排列，从最长的事务开始，求频繁项集。

上述对Apriori算法的改进，均不同程度的提高了挖掘频繁项集的效率，但算法采用的数据结构过于复杂，对事物数据库的压缩有限，对项集的支持度计数仍是采用循环或搜索统计的方法。本文在总结现有研究的基础上提出了一种基于链表的改进的Apriori算法。该算法首先扫描事务数据库计算频繁-1项集并采用链表进行压缩存储，然后在频繁-N项集（N≥1）的基础上利用高效的位运算对链表进行合并操作生成频繁N+1项集，并对频繁N+1项集（N≥1）的产生过程进行了优化，提高了Apriori算法的效率。

2 IABL（An improved Apriori algo⁃rithm based on linked list）算法

2.1 算法描述

IABL算法首先扫描事务数据库计算频繁-1项集，并采用链表以垂直数据结构的形式将频繁-1项集存储在内存中，然后对频繁-1项集链表中的节点进行两两合并生成频繁-2项集链表。为节约内存，保存频繁-1项集的Itemi和其支持度计数后，删除频繁-1项集链表，然后按相同的方法生成频繁-N项集（N≥2），直到新生成的频繁-N项集链表长度小于N，算法结束。具体步骤如下。

步骤1：加载数据，生成频繁-1项集L1。扫描事务数据库D，统计每个项目的支持度计数，获得L1并采用如图1所示的链表结构进行存储。该链表包含两种节点，Item节点和Tid节点。其中Item节点组成ILink链表，包含三个域，next指向下一个Item节点，如无则为Null，TLink域指向由Tid节点组成的链表，ID域存储该Item节点包含项目的ID号；Tid节点中包含两个域，rno存储该项集在事务数据库中出现的行序号，另一个为指向下一个Tid节点的next域，若无则为Null。TLink链表的长度，即所包含Tid节点的个数，为该项集的支持度计数。

步骤2：根据步骤1中生成的ILink链表，对IL⁃ink链表中的Item节点进行两两合并，生成新的Item节点，如果该节点的支持度计数满足最小支持度计数，则将该节点添加到新的ILink中，否则丢弃。新的ILink中的所有节点均为频繁-2项集。在节点合并时，一个节点只与其之后的节点合并，具体合并时，对于待合并的两个节点Item1和Item2，合并生成一个新的Item节点NewItem，NewI⁃tem.ID=Item1.ID∪ Item2.ID，NewItem.TLink=Item1.TLink∩Item2.TLink。然后删除频繁-1项集的IL⁃ink链表，保存频繁2项集的ILink中各个Item节点的ID和支持度计数信息得到L2。

步骤3：重复步骤2直到ILink的长度小于N为止。但在Item节点的两两合并过程中，需要增加以下判断以减少不必要的计算。

1）判断新生成的ID是否属于N项集令║ID║为ID所表示的项集中所包含的项目的个数，如果║ID║≠N，进行下两个节点的合并，否则进行下一步。

2）根据新生成的ID在ILink中查找是否已存在具有相同ID的节点，如果存在，则进行下两个节点的合并，否则进行下一步。

3）判断ID所表示的项集的所有长度为N-1的子集是否为频繁集，如是则进行下一步，进行下两个Item节点的合并。

2.2 算法分析

接下来采用表1所示样本事务数据库，对本文所提出的算法进行具体的描述，并对算法性能进行简要的分析。设最小支持度计数为2。

表1 样本事务数据库

1）根据IABL算法步骤1，扫描事务数据库，计算频繁-1项集L1，构建L1的ILink链表，L1=｛B，C，D，A，E｝，其支持度计数分别为：5，4，4，3，3。结果如图2所示。

图2 L1的ILink

2）按步骤2，对1）生成的ILink中各Item节点进行两两合并，由满足条件（支持度计数不小于最小支持度）的新生成的Item节点构成L2的ILink，其结果如图3所示。根据L2的ILink结果，可得到L2=｛BC，BD，BA，BE，CA，CD，CE，DA｝，其支持度计数分别为4，3，3，3，3，2，2，2。

图3 L2的ILink

3）按步骤3，对步骤2中生成的ILink进行两两节点的合并，结果如图4所示。根据L3的ILink，L3=｛BCD，BCA，BCE，BDA，CDA｝，其支持度计数均为2。同样地，可得到L4的ILink，其结果如图5所示。可得到L4=｛BCDA｝，其支持度计数为：2。因此时IL⁃ink中Item节点的个数少于4个，算法结束。

图4 L3的ILink

根据上述采用表1的样本事务数据库对算法的具体描述可以看出：

图5 L4的ILink

1）本算法采用链表结构对事务数据库进行一次扫描后存储到内存中，避免了多次扫描事务数据库带来的频繁I/O操作，解决了Apriori算法的性能瓶颈问题，同时本算法采用的用嵌套链表存储事务数据库的方法，客观上对事务数据库信息进行了压缩，数据量越大越稀疏压缩效果越明显。

2）在频繁项集的迭代生成过程中，LN的生成，包括项集支持度计数的计算只与LN-1相关，方便计算的同时整体上减少了内存开销。

3）算法采用链表结构存储事务数据库信息，在生成频繁项集的过程中只进行两个Item节点的合并操作，方法简单，实现容易，但克服了经典Apriori算法的瓶颈，提高了频繁项集挖掘的效率。

为了提高算法的运行效率，可将高效的位运算运用到两个Item节点的合并过程中，包括其ID域和Tid链表的合并（实际上是两个Tid链表求交集），具体方法如下：

1）ID域的合并。首先对L1中的所有项进行编码，用与L1中项的个数相同长度的二进制位对L1中的每个项进行编码。如在上面的示例中，L1=｛B，C，A，E｝，则我们可以用4位二进制位来对L1中的每个项进行编码，具体为：B=1000，C=0100，A=0010，E=0001，在ID域的合并过程中则直接对其编码进行或运算，如B∪ C=1000|0100=1100。

2）Tid链表的合并。类似地，如对于图3中Item节点B的Tid域可以表示为：11111，C的Tid域可表示为：11101，对节点B和C的Tid域进行合并操作，计算11111&11101即可。支持度计数的计算只需求11101中“1”的个数即可。

3）需要注意的是，如果L1中的项的个数较多，或者事务数据库中事务的数目较多时，可以采用链表等方式来处理。如事务数较多，可将事务划分为若干块，每块设置编号，在块内依然用二进制串表示，以便可以用高效的位运算来进行两个Item节点的合并。

3 实验分析

为对IABL算法的性能进行验证，采用Java编程语言将该算法与FP-Growth算法的性能进行了实验对比分析。实验环境为华硕X556UB笔记本电脑一台，配置如下：CPU Intel（R）Core（TM）i7-6500 2.5GHz；8G内存；64位windows 10操作系统，数据集共6组，详情如表2所示。

表2 实验数据集详细信息表

表2中T40I10D100K.dat、T10I4D100K.dat两个数据集为采用IBM Quest Market-Basket Synthetic Data Generator生成的数据集，其余的数据集为真实数据集。在上述实验条件下，分别用实现的两种算法在6组数据上进行了实验，具体实验结果如图6～图11所示。通过实验结果数据综合分析，可以得出如下结论。

1）总体上，IABL算法性能明显高于FP-Growth算法。从所示各图可以看出，对于相同的数据集，在相同的最小支持度时，IABL算法的执行时间明显低于FP-Growth算法的运行时间。

图6 chess数据集

图7 pumsb数据集

图8 mushroom数据集

图9 kosarak数据集

图10 T40I10D100K数据集

图11 T10I4D100K数据集

2）对同一数据集，随着最小支持度的降低，IABL算法和FP-Growth算法在同一最小支持度下的运行时间差距更大。如图6所示，当最小支持度为95%时，IABL算法与FP-Growth算法各自运行时间所表示的点在图上几乎重合，但当最小支持度降低到90%时，我们可以清楚地从图上看到差距，而当最小支持度降低到85%时，这种差距更明显。对同一数据集而言，最小支持度越小，所得到的频繁-1项集也就越多，意味着有更多的项参与到之后的频繁-2项集以及频繁-N项集的计算中，计算的复杂度也会相应的增加。这也说明IABL算法在查找频繁项集的计算中效率要高于FP-Growth算法。

3）IABL算法在低密度数据集上的性能表现相较于FP-Growth算法优势更加突出。如图6～图11所示三个数据集，其特点就是数据密度低，数据量大。如kosarak.dat数据集，项目总数为41270，而平均事务长度只有8，事务总数却达到990000。根据算法的实现原理，以图4～6所示的两种算法在T10I4D100K数据集上运行结果对比为例，对其原因进行分析。

当最小支持度为10%时，数据集中满足最小支持度的项的个数为0，算法运行时间的差距较小，产生差距的原因在于对数据的读取和计算频繁-1项集上。

当最小支持度降为4%时，频繁-1项集的数目为26，而频繁-2项集的数目为0。FP-Growth算法的运行过程为：根据得到的频繁-1项集开始第二次扫描事务数据库构建FP-Tree［4］，然后根据构建的FP-Tree调用FP-growth（Tree，α）挖掘出所有频繁项集。IABL算法的运行过程为：扫描事务数据库得到频繁-1项集并构建ILink链表，然后对TidLink链表采用位运算的形式进行两两合并，并计算其支持度计数，确定频繁-2项集，频繁-2项集为空，算法结束。由于FP-Growth算法需要扫描两次事务数据库，而IABL算法只需扫描一次事务数据库，同时构建FP-Tree和之后的挖掘频繁模式也比IABL算法计算更复杂，效率更低。实验结果也很好地验证了这点，在最小支持度为4%时，在T10I4D100K数据集上，FP-Growth算法的运行时间为1968ms，而在同等的条件下，IABL算法的运行时间为422ms，是FP-Growth算法的21.44%。

当最小支持度为1%时，频繁-1项集的数目是375，频繁-2项集的数目为9，频繁-3项集的数目为1。为了挖掘出所有满足最小支持度的频繁项集，FP-Growth算法需要对查找出的375个频繁项构建庞大的FP-Tree，并在此基础上展开对树的搜索查找出所有的频繁项集，这将是繁重的工作，必将耗费大量时间。而IABL算法基于查找出的375个频繁项构建的ILink链表，一方面对数据进行了充分的压缩，另一方面采用位运算迭代计算频繁-2项集和频繁-3项集，计算量相对较小，位运算的速度也比搜索操作的速度更快，从而整个算法的执行效率也就更高。实验结果显示，在最小支持度为1%时，在T10I4D100K数据集上，FP-Growth算法的执行时间为37546ms，IABL算法的执行时间为4947ms，是FP-Growth算法的13.18%。

4）综合图6～11及上述1）～3）的分析，相对于FP-Growth算法而言，由于采用特殊的ILink链表结构对预先计算出的频繁-1项集进行了压缩存储，整个算法在挖掘频繁项集的过程中只需扫描一遍事务数据库，采用高效的位运算挖掘频繁-N项集以及计算其相应的支持度计数，IABL算法性能明显优于FP-Growth算法，在数据密度低的数据集上这种优势更加明显，其效率也更高。

4 结语

本文在研究总结现有关联规则挖掘算法的基础上，提出并实现了一种基于链表的改进Apriori算法，该算法使用嵌套链表对事务数据库和前一频繁项集LN-1进行存储，并对经典Apriori算法的连接、剪枝和验证过程基于嵌套链表的存储结构进行了优化，并采用多个数据集对本文所提出的算法与经典的FP-Growth算法的运行结果进行对比分析，证明了本文提出的算法的可行性与正确性。通过实验的对比分析，本文所提出的算法具有更好的性能。虽然算法能处理较大量的数据集，但内存空间毕竟有限，在今后的研究中将基于分布式和并行计算对算法进行改进，以适应更广泛的应用需求。