基于前缀项集的Apriori算法改进

于守健 周羿阳

(东华大学计算机学院 上海 201600)

基于前缀项集的Apriori算法改进

于守健 周羿阳

(东华大学计算机学院 上海 201600)

关联规则的挖掘是数据挖掘中一个重要内容，主要目的是找到事务数据库中的有趣的模式。Apriori算法是关联规则挖掘的最经典算法之一，但是它本身存在着效率上的瓶颈。在深入了解Apriori算法前提下，提出基于前缀项集的候选集存储结构，并利用哈希表在快速查找上的优势，大大提高了经典Apriori算法在连接步骤和剪枝步骤中的效率。实验证明改进后的Apriori算法在一定支持度下比经典Apriori算法有着更大的效率优势，并且支持度越小时提升效率越大。

数据挖掘 Apriori算法 前缀项集 关联规则 哈希表

0 引 言

随着计算机技术在各个行业的迅猛发展，各行业所产生的数据也越来越多，但是如何在这些海量数据中获取有价值的信息也成了一个新的问题。数据挖掘，即数据知识发现，正是在这个大背景下应运而生。数据挖掘[1]是从大量的数据中挖掘出隐含的、未知的、用户可能感兴趣的知识和规则。关联规则是数据挖掘中的一个重要内容，它最先由Agrawal等提出[2]，主要解决的是顾客交易事务库中项集之间的关联规则问题。隔年，Agrawal等人又提出了计算关联规则的最经典的算法，即Apriori算法[3]，它是由k-项集来推断(k+1)-项集并通过剪枝来获得k-项集的算法。但是由于Apriori算法在计算候选集中的计算瓶颈问题，近年来也出现了针对不同方面的的算法改进方式。Zhang等[4]提出了基于分类的改进的Apriori算法，在效率上有一定程度的提升。Jia等[5]从事务数据库划分和动态项集统计的角度对经典Apriori算法进行改进。Liu等[6]在研究煤炭隐患数据时提出了数据库矩阵化的方法来进一步提升算法效率。Wang等[7]提出一种优化的方法来减少对事务库重复搜索的次数，从而达到提高效率的目的。Vaithiyanathan等[8]针对事务数据库中相同兴趣的关系对其进行压缩的方法来改进算法效率。Lin[9]提出基于MapReduce计算模型的Apriori算法以提高大量数据的候选集生成效率。Zhang等[10]是从要分析的数据，即医疗数据的特征出发，提出一种针对该数据特点的改进Apriori算法。

上述提到的改进算法大多是通过减少对事务数据库遍历的次数来提高算法的效率，但是这些算法并没有针对Apriori算法的两个重要步骤，即连接和剪枝步骤进行改进。本文将针对经典Apriori算法的这两个重要步骤，即连接步骤和剪枝步骤，采用一种新的基于前缀项集的存储方式，并利用哈希表快速查找的特征来提高改进算法在两个步骤中的查找效率。本文首先介绍经典Apriori算法以及其不足之处，再具体介绍算法的改进之处，最后介绍在具体数据集上经典Apriori算法与改进Apriori算法的效率比较。

1 Apriori算法

1.1 Apriori 算法介绍

Apriori算法是一种经典的挖掘关联规则的频繁项集算法，其基本思想是使用逐层迭代方法，先求得k-项集，再由k-项集去探索(k+1)-项集。Apriori算法利用频繁项集性质的先验知识，首先找出频繁1-项集的集合，记作L1。用L1得到2-项集的集合L2，再用L2得到L3，直至不能找到频繁k-项集。Apriori算法的主要包括下面3个步骤：

(1) 连接步骤：连接k-频繁项集生成(k+1)-候选项集，记作Ck+1。连接的条件是2个k-项集的前(k-1)项相等且它们的第k项不相等。记li[j]为li中的第j项，则条件为：

l1[1]=l2[1]∧l1[2]=l2[2]∧…∧l1[k-1]=l2[k-1]∧l1[k]≠l2[k]其中l1和l2是k-项集集合Lk的子集，l1[k]≠l2[k]是确保不产生重复的k-项集。由l1和l2连接产生的结果项集为：

{l1[1],l1[2],l1[3],…,l1[k],l2[k]}

(2) 剪枝步骤：从候选项集Ck+1中挑选出真实频繁项集Lk+1。因为候选项集Ck+1是真实频繁项集Lk+1的超集。根据Apriori性质：频繁k-项集的任意子集必定也是频繁的，即频繁k-项集的任意(k-1)-项集也必定是频繁的。利用此性质查找是否Ck+1的k-项子集是否都在Lk中，如果不成立，则将该候选(k+1)-项集从Ck+1中删除。

(3) 计数步骤：扫描数据库，累加(k+1)-候选集在数据库中出现的次数。再根据给定的最小支持度阈值生成(k+1)-项集。

1.2 Apriori算法的不足

Apriori是挖掘关联规则的最经典算法之一，但是也存在着效率不高的问题。Apriori算法的时间消耗主要在以下3个方面：

(1) 在连接步骤，利用k-项集连接产生(k+1)-候选项集时，判断连接条件时比较次数太多。假设Lk中有m个k-项集，则连接步骤需要进行比较的时间复杂度为O(k×m2)。

(3) 在计数步骤中，对Ck+1中候选项集的支持度计数中，需要扫描次数据库|Ck+1|。

上述即经典Apriori算法的时间消耗的主要三个方面，在引言中提到的改进的算法也主要是针对其中的第三个步骤，即计数步骤作出改进以提升效率，本文将针对其中的前两个步骤，即连接步骤和剪枝步骤的计算瓶颈，提出一种基于前缀项集的改进Apriori算法。

2 Apriori算法改进

2.1 算法改进思想

在1.2节中已经分析了传统Apriori算法的不足之处，所以对其改进也着重在1.2节中提到的3个步骤中。由于Apriori算法中记录中的各项均已经是按字典排序的，因此由Apriori算法生成的候选项集也是有序的。

(1) 基于前缀项集的存储方式

在新提出的基于前缀项集的改进算法中，我们引入一种新的存储项集的方法——基于前缀项集的存储方法。对于每个项集我们修改其保存方式：对于Lk中各k-项集我们采用类似Map结构的Hash表来保存，其中key为k-项集的前(k-1)-项内容，value为k-项集的第k项内容。再将LK中所有项集保存在一个Map中，对于具有相同key，即相同前(k-1)-项内容的k-项集，则该key对应的value值为其value，即第k-项内容的并集。

例如：数据库如表1所示，设最小支持度为2。

表1 事务表TD

传统的Apriori算法扫描数据库，得到每个项在数据库中出现的次数，并得到1-项集及计数，再基于1-项集迭代产生满足最小支持度的2-项集及计数。下面是传统的Apriori算法得到的内容如表2所示。

表2 传统存储方式

利用基于前缀项集的保存方式如表3所示。

表3 基于前缀项集存储方式

表3中，因为1-项集只有一个项，所以其前缀内容设为NULL；在上表中还可以清楚地看到若前缀的长度为n，则其代表的项集长度则为(n+1)，因为value中记录的是该项集的最后一个项的内容。

(2) 基于前缀项集的连接步骤

在基于前缀项集存储方式的建立后，在连接步骤进行k-项集间的连接操作时，则只要对相同前缀-key的value中任意两个项进行合并，再加上该前缀-key即可成为新的(k+1)-项候选项集。例如，对表3中的2-项集进行连接，前缀-key为A对应的value集中连接操作可得到{{B,C},{B,D},{C,D}}，前缀-key为B对应的value集中连接操作可得到{{C,D},{C,E},{D,E}}。

(3) 基于前缀项集的剪枝步骤

由1.1节中对传统剪枝步骤的介绍可以知道，(k+1)-候选项集是由LK中的两个k-项集连接得到，并且如果(k+1)-候选项集的某个k-项子集不在Lk中时，该(k+1)-候选项即从Ck+1中移除。下面提出一个定理：

定理1 如果由两个k-项集、，连接产生的(k+1)-项集的k-项子集不在Lk中，则该k-项子集中必然同时包含l1[k]，l2[k]。

证明：l1、l2连接后得到的(k+1)-项候选集为{l1[1],l1[2],l1[3],…,l1[k],l2[k]}。

如果该(k+1)-项候选集的k-项子集不同时包含l1[k]，l2[k]，则可能的情况只有l1[1]、l1[2]，l1[3]…,l1[k]、l1[1]，l1[2]，l1[3]，…，l2[k]}即、l1、l2。而l1、l2属于Lk，所以若k-项子集不属于Lk，则k-项子集中必同时包含l1[k]，l2[k]。

由定理1可知，在进行剪枝过程中只需考虑(k+1)-项候选集中同时包含用于连接的两个k-项集尾项的可能的k-项子集即可。针对表3中的例子，遍历可能出错的2-项子集可以得到如表4所示。

表4 剪枝过程

如表4中所示，只有{{B,C},{B,E}}是可能的2-项候选子集，再加上其对应的前缀-key，得到{{A,B,C},{A,B,E}}，即得剪枝后的3-项候选子集C3。

得到(k+1)-项候选集后，再遍历原始数据库，执行计数步骤，即找出满足最小支持度的k-项集，针对表3中例子，可以知道{{A,B,C},{A,B,E}}都满足最小支持度，所以将他们加入到基于前缀项集存储中，如表5所示。

表5 3-项集存储方式

2.2 算法实现

完整的算法可描述为：

输入：事务数据库D，最小支持度min_sup

输出：频繁项集L

1) L1=D的1-项集

2) Map map;

3) 将L1导入map中，key为null，value为L1中项的并集

4) for(k=2;Lk-1φ;k++){

5) Ck=pre_apriori_gen(map,k-2);

6) 对Ck中每个项集计数，Lk={c∈Ck|c.count>min_sup}

7) }

8) Return ;

procedurepre_apriori_gen(map:Map;k:int)

1) for each key in map{

2) if(key.length()==k){

3) c:=key与(value中任意两个值)的有序组合;

4) if(map.containsKey(c[0:k])){

5) If(c的任意(k+1)子集存在于map的(key,value)中){

6) 将c加入Ck;

7) }

8) }

9) else continue；

10) }

11) Return Ck

3 实验结果与分析

实验采用的数据是瑞金医院的糖尿病临床处方数据共120 000行，数据中记录的是每次就诊的处方药品编号。本实验运行机器配置为Intel Core i5 2.7 GHz处理器，8 GB 1866 MHz LPDDR3 内存。

实验从两方面来对经典Apriori算法和基于前缀项集的Apriori算法来进行效率上的比较：一方面是当测试总数固定时不同的支持度下的算法运行效率的比较，另一方面是当支持度固定后不同的测试总数下算法的运行效率的比较。

实验1结果如下图所示。

图1 不同支持度下的运行时间比较

图1描述的是两种算法在测试样本总数一定，共12万条数据时，不同的最小支持度下运行的时间比较。从图1中可以看到，当支持度越小时改进的Apriori算法比经典Apriori算法的效率优势越明显。从图中还可以看出当支持度达到一定值时，由于达到支持度要求的频繁项集数很少，所以此时改进算法的效率优势一般。

表6 不同支持度下时间及时间减少率

表6显示了经典Apriori算法和改进Apriori算法在不同支持度下的具体运行时间以及后者相对前者的减少率。

实验2结果如图2所示。

图2 相同支持度不同测试总数下的运行时间比较

图2描述的是两种算法在不同测试总数，但支持度都为测试总数的2%时运行时间的比较。从图2可以看出，在相同支持度下测试总数越大，算法的运行时间越长，并且改进的Apriori算法相比经典Apriori算法在效率上有着稳定的提升效果。

表7介绍了两种算法在相同支持率但测试总数不同的情况下运行的时间比较，可以看出在支持度为测试总数2%时，改进Apriori算法在效率上明显高于经典Apriori算法，并且效率的提升率稳定在70%左右。

表7 不用测试总数下时间及时间减少率

续表7

实验表明，基于前缀项集的Apriori算法是有效可行的。

4 结 语

本文在对经典Apriori算法的深入研究基础上，指出了该算法在连接、剪枝步骤中的一些局限，并提出了基于前缀项集的数据存储方式以及在该存储方式上的算法改进，使得在连接步骤和剪枝步骤的运行时间得到很大程度的减少。最后在支持度和测试总数两个维度上的实验结果也证明了算法的可行性。

[1] Han J,Kamber M,Pei J.Data mining:Concepts and techniques[J].3rd ed.San Francisco:Morgan Kaufmann Publishers,2001.

[2] Agrawal R,Imieliński T,Swami A.Miningassociationrules between setsof items inlarge databases[C]//Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data,1993:207-216.

[3] Agrawal R,Srikant R.Fast algorithms for mining association rules in large databases[C]//Proceedings of the 20th International Conference on Very Large Data Bases,1994:487-499.

[4] Zhang C S,Li Y.Extension of local association rules mining algorithm based on apriori algorithm[C]//Software Engineering and Service Science (ICSESS),2014 5th IEEE International Conference on.IEEE,2014:340-343.

[5] Jia Y,Xia G,Fan H,et al.An Improved Apriori Algorithm Based on Association Analysis[C]//2012 Third International Conference on Networking and Distributed Computing,2012:208-211.

[6] Liu S,Peng L.Analysis of Coal Mine Hidden Danger Correlation Based on Improved A Priori Algorithm[C]//Intelligent Systems Design and Engineering Applications,2013 Fourth International Conference on.IEEE,2013:112-116.

[7] Wang P,An C,Wang L.An improved algorithm for Mining Association Rule in relational database[C]//Machine Learning and Cybernetics (ICMLC),2014 International Conference on.IEEE,2014,1:247-252.

[8] Vaithiyanathan V,Rajeswari K,Phalnikar R,et al.Improved apriori algorithm based on selection criterion[C]//Computational Intelligence & Computing Research (ICCIC),2012 IEEE International Conference on.IEEE,2012:1-4.

[9] Lin X.MR-Apriori:Association Rules algorithm based on MapReduce[C]//Software Engineering and Service Science (ICSESS),2014 5th IEEE International Conference on.IEEE,2014:141-144.

[10] Zhang W,Ma D,Yao W.Medical Diagnosis Data Mining Based on Improved Apriori Algorithm[J].Journal of Networks,2014,9(5):1339-1345.

[11] Han J,Pei J,Yin Y.Mining Frequent Patterns without Candidate Generation[C]//Proceedings of ACM SIGMOD International Conference on Management of Data,2000:1-12.

THE IMPROVEMENT OF APRIORI ALGORITHM BASED ON PREFIXED-ITEMSET

Yu Shoujian Zhou Yiyang

(CollegeofComputerScienceandTechnology,DonghuaUniversity,Shanghai201600,China)

The mining of association rule is an important method for discovering interesting relations between variables in large databases.Apriori algorithm is one of the most classical algorithms of association rules,but it has bottleneck in efficiency.Thus,a candidate item set storage structure based on prefixed-item set is proposed with the help of the quick search of hash map,and the efficiency of classical Apriori algorithm in connecting and pruning step has been improved greatly.The experiments show that the improved Apriori algorithm does better in efficiency than the classical Apriori algorithm in certain degree’s support,and the smaller support,the better efficiency.

Data mining Apriori algorithm Prefixed-itemset Association rules Hash map

2015-10-21。于守健，副教授，主研领域：Web服务，企业应用集成，数据库与数据仓库。周羿阳，硕士。

TP3

A

10.3969/j.issn.1000-386x.2017.02.052