基于有序FP-tree的最大频繁项集挖掘算法
2016-06-30李少华吕志旺车德勇
李少华，吕志旺，车德勇，周 宁
(1.东北电力大学能源与动力工程学院，吉林 吉林 132012；2.东北电力大学信息工程学院，吉林 吉林 132012)
基于有序FP-tree的最大频繁项集挖掘算法
李少华1，吕志旺2，车德勇1，周宁2
(1.东北电力大学能源与动力工程学院，吉林 吉林 132012；2.东北电力大学信息工程学院，吉林 吉林 132012)
[摘要]通过分析有序FP-tree与MFI之间的关联关系，提出一种高效的MFI挖掘算法(MMFI)，使其在挖掘过程中不但避免了条件频繁模式树的构建，也省略了超集检测的过程.提出了两种预剪枝策略，该策略能够有效地缩短算法执行的时间复杂度.结合理论分析和实验数据发现MMFI算法比传统算法快速、合理.
[关键词]数据挖掘；FP-tree；最大频繁项集；关联规则
0引言
R.Agrawal和R.Srikant[1]提出了为布尔型关联规则挖掘频繁项集的Apriori算法.随后J.Han[2]将所要挖掘的事务数据库DB转化为FP-tree 结构，并设计了FP-Growth算法.FP-Growth和Apriori都是用于发现事务数据库中的全部频繁项，造成了算法的执行过程耗时较长.因此提出将挖掘频繁项集的问题转化为挖掘MFI.一方面是由于MFI集合中包括了所有的频繁项；另一方面由于MFI的数量远远低于频繁项的数量.然而，目前对于MFI的挖掘过程普遍存在以下问题：(1)需要递归构建条件模式树，增加了算法的时间复杂度；(2)算法对每次求出的频繁项需要检测其是否为MFI(超集检测).在项集数量较大、事务条数较多的情况下，以上2个问题的耗时会占整个挖掘过程的绝大部分时间，因此降低了算法的执行效率.
本文通过对文献[3]提出的有序FP-tree的结构进行了改进，总结并分析出了该树型结构的相关性质.提出了一种新的MFI挖掘算法——MMFI (mining maximal frequent itemset)算法.有序FP-tree作为对传统FP-tree结构的一种改进，使得MMFI算法在挖掘MFI的过程中既能够避免超集检测，也无须建立条件模式树.
1相关知识
1.1FP-tree结构
FP-tree是J.Han[2]等人提出的一种树型结构，用于存储事物数据库中满足最小支持度的频繁项集，且该树型结构仍保留各项集间的关联关系.项集在该树型结构体现为任意节点到根节点的节点集合，同时在各节点中存储对应项集的支持度数.
为便于对树的遍历需创建头表，头表用于存储频繁项和支持度计数，将树中相同的频繁项用指针链从左到右依次链接在一起，其中链头指针存储在头表中.下面给出了构建FP-tree的例子，表1列出了事务数据库以及满足min_sup2的频繁项，图1为事务数据库DB对应的FP-tree.
图1 事务数据库DB对应的FP-tree
TID事务数据库频繁项1a,c,fc,a2c,gc3a,c,ec,a,e4c,d,kc,d5a,c,d,oc,d,a6a,e,pa,e7c,d,e,hc,d,e8b,c,d,e,nc,d,e,b9d,e,td,e10a,b,d,md,a,b11a,c,d,qc,d,a
1.2MFI挖掘算法的现状
当前已经比较成熟的MFI挖掘算法主要有MaxMiner[4]、DMFIA[5]、MAFIA[6]和FP-Max[7]等.由Bayardo等人提出的MaxMiner算法运用“look-ahead”的超集剪枝策略，在一定程度上有效地压缩了算法的搜索空间，但是在生成无用候选项集和多次遍历数据库的过程中影响了算法的执行效率；Burdick等提出的MAFIA算法结合纵向位图与动态重排序技术进行空间剪枝，算法性能较好，但也需要多次扫描事务数据库；宋余庆等人通过对MaxMiner算法进行了改进，提出DMFIA算法，只需扫描数据库2次且没有产生条件模式基，但是也会产生大量的频繁项集候选项.
基于FP-tree的FP-Max算法需多次递归建立条件模式树，当挖掘对象为稠密型数据时会产生大量的冗余递归过程，耗费大量存储空间.近年来，国内学者对FP-Max和DMFIA算法进行了改进，提出了BDRFI[8]和NCFP-Max[9]等算法.BDRFI算法通过建立数字频繁模式树以提高超集检验效率，同时采用自下而上的搜索策略，但算法也会生成大量的候选项集.NCFP-Max算法虽然能够避免超集检测，但是在避免递归生成条件模式树的过程中需对所有路径求其交集，耗时较长.
综上所述，目前的MFI挖掘算法普遍存在以下问题：(1)多次遍历数据库；(2)递归建立条件模式树；(3)超集检测.
2MMFI算法
MMFI算法是通过沿有序FP-tree头表中的节点链对树中的节点进行遍历以挖掘事务数据库DB中隐藏的MFI.在挖掘的过程中既不用递归的构建条件频繁模式树，也避免了将求出的项集进行超集监测的过程.
2.1有序FP-tree
MMFI算法依据MFI的任何真子集都不是利用MFI的基本性质对有序FP-tree进行挖掘，使得在算法执行过程中仅生成MFI.为实现MMFI算法需要建立有序FP-tree，其具体的构建过程已经被提出[3].
图2表示由表1中满足min_sup2的项构成的有序FP-tree.同时在该树型结构头表中添加了一个num域，用于记录各频繁项位于FP-tree中的层次(最左侧节点).
图2 有序FP-tree
2.2有序FP-tree的性质
设Ipi表示从任意非根节点pi到根节点的所有节点组成的集合，则有序FP-tree具有2种性质.
性质1设pi和pj为有序FP-tree对应头表中2个频繁项且pi在pj的下方，那么Ipi可能为Ipj的超集，但一定不是Ipj的子集.
证明在头表中所有频繁项从上到下依据支持度按递减顺序排列，若pi和pj同时出现在有序FP-tree的一个分支上，且在头表中pi位于pj下方，则pi必为pj的子孙节点，因此性质1成立.证毕.
性质2设
证明设〈p1，p2，…，pi〉是有序FP-tree中的一个MFI，根据文献[3]中有序FP-tree的构建过程可知，节点p1一定是树根的最左侧孩子，同理节点p2一定是节点p1的最左侧孩子，如此进行下去，节点pi必是节点pi-1的最左侧孩子，因此〈p1，p2，…，pi〉一定是FP-tree的最左边的分枝.证毕.
结合上文对有序FP-tree性质的分析，以pi为后缀的MFI必然是下面情形之一：
(1)Ipi可能是最大频繁项集；
(2)pi右侧的兄弟节点中存在pj且满足Ipj⊂Ipi，则Ipj可能是MFI；
(3)在兄弟链表中存在节点pi，pj，…，pk，且Ipi，Ipj，…，Ipk互不包含，则Ipi，Ipj，…，Ipk的最大化交集为MFI.
2.3预剪枝策略
基于有序FP-tree的MMFI算法的基本思想采用自下而上依次处理头表中各个节点所指节点链，同一层节点链沿FP-tree从左到右的顺序进行遍历.为提高算法的挖掘效率，结合有序FP-tree的性质，采取预剪枝策略.
(1)当头表中任意节点p的num域的值等于该节点在头表中的层次且为p.count≥min_sup时，算法终止.
(2)对于树中任意非根节点p，其tag域初始值为T；定义p.tag=T表示Ip可能为MFI，p.tag=f表示Ip肯定不是MFI.如果Ip为MFI，那么Ip的任何子集都不可能是MFI，因此可将Ip中所有节点的tag域标记为f.当遍历的节点满足p.tag=f时可以直接跳过，从而避免超集检测的过程.
2.4MMFI算法及流程
结合本文提出的有序FP-tree的性质以及最大频繁项可能出现的情况，从头表最底端节点指针域所指节点链开始挖掘.
(1)如果support(p)≥min_sup则Ip是MFI，将Ip存入MFS(最大频繁项集集合)后分2种情况分别处理：
(A)如果节点p是节点链的首节点且所在头表的层次等于num域的值，则Ip为剩余所有项的最大频繁项(由性质2可知)，算法结束并输出MFS；
(b)否则将该节点的所有祖先节点标记为不可挖掘，并沿链表向右侧搜索Ip的子集，并标记为不可挖掘.
(2)若support(p) (A)若在节点链右侧有pj满足Ipj为Ip的子集，则执行Ipj.count=Ip.count+Ipj.count. (b)若节点链右侧有pj且Ipj不是Ip的子集；令Ipk=IpIpj，如果Ipk非空，按照有序FP-tree的构造规则将Ipk添加到兄弟链表中.其count域的值为Ipk.count=Ip.count+Ipj.count. 结合以上分析，MMFI算法伪代码执行过程具体如下： (1)输入：事务数据库DB和min_sup (2)输出：MFS (3)for(p=tb_pos;tb_pos≥0;tab_pos--){ (4)p=tb[tb_pos].node_link (5)if(p.count>min_sup&&tb[tb_pos].num==tb_pos) (6){输出MFS;算法结束;} else{ (7)while(p≠null){ (8)if(p.tag==T){//Ip可能是MFI (9)if(p.count≥min_sup)//Ip是MFI (10){Ip路径上所有节点tag域为F; (11)while(节点链右侧tag=T的节点) (12)if(Ipj⊂Ip){ (13)令Ipj所有节点tag=F; (14)Ip添加到MFS;} } else{//Ip不是MFI (15)搜索节点链右侧tag=T的节点; (16)if(Ipj⊂Ip){ (17)令Ip所有节点tag=F; (18)pj.count+=p.count;} else (19){Ipk=Ip∩Ipj; (20)Ipk.count=Ip.count+Ipj.count; (21)将Ipk添加到兄弟链表中;} } } else{//Ip及其子集都不是MFI (22)while(向右侧搜索tag=T的节点){ (23)if(Ipi⊂Ip) (24)将pi及其祖先节点tag标记为F; (25)p=p→next;} } } }. 2.5MMFI算法实例 MMFI算法的挖掘过程(见图3)：首先沿项头表b节点所指节点链开始遍历，由于{c，d，e，b:1}和{d，A，b:1}均不满足最小支持度且互不包含，取其最大化交集{d，b:2}满足支持数，因此以b为后缀的MFI为{d，b:2}. 当沿节点e所指节点链遍历时，项集{c，d，e:2}满足最小支持数，又由于{A，e:1}是{c，A，e:1}的子集故转移支持数生成{A，e:2}，因此以e为后缀的MFI为{c，d，e:2}、{A，e，:2}. 当沿节点A所指节点链遍历时，由于链表num域的值等于节点A在头表中的层次且该节点满足最小支持数，故以A为后缀的MFI为{c，d，A:2}，算法结束. 综上图3所隐藏的最大频繁项集集合MFS={{d，b:2}，{c，d，e:2}，{A，e:2}，{c，d，A:2}}. 3算法性能分析 为验证MMFI算法的可行性，通过实验数据将其与FP-max算法进行对比分析.实验测试环境：CPU为T4200 2.0 GHz，操作系统为Win7，内存为2 GB的PC机.通过Java语言实现了FP-max 和MMFI算法，实验对象为由文献[10]提供的国际象棋数据(chess.dat)和蘑菇数据(mushroom.dat)2个密集型数据集. 图3和4分别表示2种算法在mushroom(含有8 124个事务)和chess.dat(含有3 196个事务)数据集上采用不同支持度时的性能对比结果.实验表明，在挖掘MFI时MMFI的挖掘效率优于FP-max算法. 图3 mushroom数据集 图4 chess数据集 4结束语 频繁项集的获取是发现事务间关联规则的前提和关键，将挖掘频繁项集转化为挖掘MFI能够降低算法的时间复杂度.相对于传统基于FP-tree的挖掘算法，MMFI算法不但避免了递归建立条件频繁模式树和超集检测的步骤，所提出的预剪枝策略也提高了算法执行的效率.同时，MMFI算法需要在同一层节点链上进行多次循环遍历，在一定程度上增加了算法的复杂程度，这也是MMFI算法需要进一步解决的问题. [参考文献] [1]AGRAWAL R，IMIELINSKI T，SWAMI A.Mining association rules between sets of items in large databases[C]// Proceedings of the ACM SIGMOD inter-national conference management of date，Washington：ACM，1993:207-216. [2]HAN J，PEI J.Mining frequent patterns without candidate generation[C]// Proceeding of the ACM SIGMOD International Conference on Management of Data，Dallas：ACM，2000，29:1-12. [3]陈晨，鞠时光.基于改进FP-tree的最大频繁项集挖掘算法[J].计算机工程与设计，2008，24：6236-6239. [4]BAYARDO J，ROBERTO J.Efficiently mining long patterns from databases[C]// Proceeding of 1998 ACM SIG-MOD International Conference on Management of Data，New York：ACM，1998:85-93. [5]宋余庆，朱玉全，孙志挥，等.基于FP-Tree的最大频繁项目集挖掘及更新算法[J].软件学报，2003(9):1586-1592. [6]BURDICK D，CALIMLIM M.MAFIA：a maximal frequent itemset algorithm[J].IEEE Transactions on Knowledge and Data Engineering，2005(11)：1490-1504. [7]GRAHNE G，ZHU J.High performance mining of maximal frequent itemsets[EB/OL].(2014-07-06)[2015-07-20].http://www.docin.com/p-773109811.html. [8]钱雪忠，惠亮.关联规则中基于降维的最大频繁模式挖掘算法[J].计算机应用，2011，31(5):1339-1343. [9]赵志刚，王芳.基于OWSFP-Tree的最大频繁项目集挖掘算法[J].计算机工程与设计，2013，34(5):1687-1690. [10]BART GOETHALS.Frequent itemset mining implementations repository [DB/OL].(2004-09-03)[2015-07-20].http://fimi.ua.ac.be. (责任编辑：石绍庆) Algorithm for mining maximal frequent itemset based on ordered FP-tree LI Shao-hua1，LÜ Zhi-wang2，CHE De-yong1，ZHOU Ning2 (1.Institute for Energy and Power Engineering，Northeast Dianli University，Jilin 132012，China；2.Institute for Information Engineering，Northeast Dianli University，Jilin 132012，China) Abstract:A new algorithm MMFI (mining maximalfrequent itemset)for efficiently mining maximal frequent itemset is proposed through analyzing the relationship of the ordered FP-tree and MFI.In the algorithm neither constructing conditional frequent pattern tree nor superset checking is needed.Also proposed two pre-pruning strategies can effectively reduce the time of the algorithm executed.It is proved by theoretical analysis and experimental comparison that the algorithm is fast and reasonable. Keywords:data mining；FP-tree；maximal frequent itemsets；association rules [文章编号]1000-1832(2016)02-0065-05 [收稿日期]2015-08-11 [基金项目]吉林省科技发展计划项目(20140307022GX). [作者简介]李少华(1957—)，男，教授，博士研究生导师，主要从事数据挖掘、信息融合，数字电站系统等研究. [中图分类号]TP 311[学科代码] [文献标志码]A [DOI]10.16163/j.cnki.22-1123/n.2016.02.015
