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

顾 鹏

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

1 引言

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

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

FP-Growth算法之所以高效，是因为采用特殊的数据结构将事务数据库压缩存储到内存中，避免了重复扫描事务数据库带来的性能瓶颈。学者们也采用了其他的数据结构来对事务数据库进行压缩存储，并在此特殊的数据结构上挖掘频繁项集。文献［3］提出用十字链表来压缩存储数据结构，文献［7］首先将事务数据库转化为关系矩阵，并使用正交链表对该矩阵进行存储，从而可以通过对链表节点集合进行操作实现频繁项目集的挖掘。……