基于临时表的Apriori改进算法

摘要  Apriori算法在关联规则领域有很大的影响力，然而由于需要过于频繁的扫描数据库及较大的空间消耗，仍然有需要改进的地方。通过对Apriori算法进行深入研究，本文提出了基于临时表的Apriori改进算法，通过比较分析，获得了较好的效率和性能。关键词  关联规则  Apriori算法  频繁项集  临时表 0  引言数据挖掘（Data Mining)是数据库知识发现KDD(Knowledge Discovery in Database)的核心,是指从数据库中提取潜在的、有用的、最终可理解的知识的过程。关联规则算法则是数据挖掘的一个重要研究方向,其侧重于确定数据库中不同领域间的联系,找出满足给定支持度和可信度的多个域之间的相互关系[4]。简单的说，关联规则就是给定一组项目Item和一个记录集合，通过分析记录集合，推导出 Item 间的相关性。1  Apriori算法介绍1.1 Apriori算法基本思想Apriori算法是发现关联规则领域的经典算法。该算法将发现关联规则的过程分为两个步骤：第一步通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；第二步利用频繁项集构造出满足用户最小信任度的规则[5]。具体做法就是：首先找出频繁1-项集，记为L₁；然后利用L₁来产生候选项集C₂，对C₂中的项进行判定挖掘出L₂，即频繁2-项集；不断如此循环下去直到无法发现更多的频繁k-项集为止。每挖掘一层L_k就需要扫描整个数据库一遍。1.2 Apriori算法描述Apriori利用层次循环发现频繁项集，算法如下：输入：交易数据库D，最小支持阈值min-sup输出：D中的频繁项集L然后利用 Apriori性质删除那些子集为非频繁项集的候选项集，一旦产生所有候选，就要扫描数据库，对于数据库中的每个交易利用subset 函数来帮助发现该交易记录的所有（已成为候选项集）的子集，由此累计每个候选项集的支持频度。最终满足最小支持频度的候选项集组成了频繁项集 L。然而,像这样产生候选集的开销极大,特别是频繁集很长或最小支持度非常小时。例如,当有10⁴个频繁1-项集时,Apriori算法就会产生多于10⁷个的候选2-项集。针对Apriori算法的瓶颈，本文提出了一种基于临时表的改进算法。2  基于临时表的Apriori改进算法2.1 基本思想基于临时表的Apriori改进算法利用了以下两个事实：(1)    对于已知规模的事务数据库D，任意一个项集I的出现频繁度与规模小于|I|的事务无关。所以在第|I|次扫描数据库D时，可以删除规模小于|I|的事务记录。(2)    k­-候选项集中不包含任何(k-1)-项集的项集一定不是频繁项集，因此k次扫描时可以将这样的事务记录立即删除，从而减少了下次需要扫描的记录数。用临时表来完成频繁项集的选择。首先把(k-1)-项集中的第一个项集添加进临时表中；然后把最后一项不同的其它项集添加进临时表，生成k-项集，其频繁度，若频繁度大于最小频繁度，则生成该频繁项并保存，否则删除。依此循环，直至生成所有的频繁项。2.2 改进算法的描述输入：事务数据库D；最小支持度阈值min_sup输出：D的频繁项集L变量说明：    Ck：k-候选项集    Lk：k-频繁项集    Dk：第k次扫描后的数据库L1 = {large 1-itemsets};  //D中的1-项集 3 改进前后的分析比较为便于算法的比较,选取[6]中Apriori算法使用的AllElectronics某分店的事务数据库中的数据进行算法模拟,如表1所示。

TID	项的列表
T100	I1,I2,I5
T200	I2,I4
T300	I2,I3
T400	I1,I2,I4
T500	I1,I3
T600	I2,I3
T700	I1,I3
T800	I1,I2,I3,I5
T900	I1,I2,I3

表1  假定min_sup=2,Apriori算法执行过程:(1)    算法第一次扫描数据库，确定1-项集及各元素的覆盖频度。如图1所示：  (2)    利用L₁⊕L₁来产生候选2-项集C₂，由C₂确定频繁2-项集。如图2所示：                 
 (3) 利用L₂⊕L₂进行连接操作，获得候选3-项集C₃，为{(I1,I2,I3),(I1,I2,I5),(I1,I3,I5),(I2,I3,I5),(I2,I4,I5)}。根据Apriori“一个频繁项集的所有子集也是频繁的”的性质，可以确定后四个项集不可能是频繁的，因此可以删除它们，从而减少了扫描次数。结果如图3所示：                     图3(4)  利用L₃⊕L₃进行连接操作得到C₄，根据Apriori性质可知C₄=Φ。算法至此结束。由此可见，Apriori算法每次扫描都要彻底扫描整个数据库D，而改进后的算法及时的将不符合要求的项集删除，从而减少了下次扫描数据库的记录数；Apriori算法进行连接操作时需生成完整的项集，而使用临时表则只需将最后一个不同的项进行连接，从而节省了大量的存储空间。算法比较结果如下表所示：表2说明：表2中数据库规模是指数据库中的记录数，空间耗费是指生成的候选项集所占的空间。从表2可以看到，在扫描规模上，Apriori每次需要对所有的事务数据库进行扫描，而基于临时表的改进算法在第二趟数据扫描后，数据中二元组 T200，T300，T500，T600，T700被删除，第三次的扫描量减至4。在空间耗费上，第一次对 5 个单项进行判断每一个单项占一位空间，需要的空间耗费为 5。第二次进行 JOIN 运算时，需要（C14+C13+C12+C11）×2=10×2=20 个单元空间，第三次进行 JOIN 运算，需要（C13+C12+C11）×3=18个单元空间。临时表压缩算法采用了逐个动态生成频繁项，依次所需空间均为 1。 4.结束语    本文在对Apriori挖掘算法的深入研究基础上，提出了基于临时表的改进算法。通过分析比较，在减少扫描数据库中记录数量和进行连接操作所需空间耗费上，取得了较好的效果。与 Apriori相比，基于临时表的改进算法在数据规模及空间耗费上均占有优势，随数据规模的增大，这种优势将更加明显。 文献：1 R Agrawal,R Wrikant. Fast Algorithms for Mining Association Rules in Large Databases. Proc,20^th int’l Conf.Very large databases.1994：478~4992 Margarent H.Dunham. Data Mining Introductory and Advanced Topics. Southern Mehodist University.20033 Brin S, Motwani R. Dynamic Itemset Counting and Implication Rules for Market Basket Data. In: Proc. Of the 1997 ACM_SIGMOD Int’1 Conf, On the Management of Data. New York: ACM Press, 1997 4 陈江平,傅仲良,徐志红.一种Apriori的改进算法.武汉大学学报(信息版),2003,2.5 李雄飞，李军.数据挖掘与知识发现.北京：高等出版社，2003.6 韩家炜.数据挖掘概念与技术.北京:机械出版社,20017 Savasere A,Ong B, Mitbander B. An efficient algorithm for mining association rules in large databases[A]. In Proc 1995, Int Conf Very Large Databases(VLDB’95)[C].19958 Bayardo R J, Agrawal R. Mining the Most Interesting Rules[c]. Processing of the 5^th International Conference on knowledge Discovery and Data Mining. San Diego: ACMPress, 1999:145-154