基于FP-tree的支持度计数优化策略

赵 阳，白 凡

(江南计算技术研究所，江苏 无锡 214083)

基于FP-tree的支持度计数优化策略

赵 阳，白 凡

(江南计算技术研究所，江苏 无锡 214083)

关联规则挖掘过程中，频繁项集的挖掘是最关键的步骤。最大频繁项集是最常用的频繁项集简化表示。基于FP-tree的最大频繁项集挖掘算法多数都需要自底向上地搜索FP-tree来计算项集的支持度。而已有的支持度计算方法在计算当前项集的支持度时没有考虑已完成的支持度计算过程所获得的信息，因而造成了不必要的开销。针对该问题，提出了基于FP-tree的支持度计数优化策略(Support Count Optimization Method on FP-tree,SCOM)，在付出很小的额外空间代价的条件下，充分利用已完成的支持度计数过程中获取的路径对项集的支持信息和项集之间的关系进行搜索剪枝，并设计实验将该策略应用到DMFIA算法上。实验结果表明，应用该策略的最大频繁项集挖掘算法DMFIA获得了较大的性能提升。SCOM对基于FP-tree的支持度计数进行优化，因此能够应用到所有利用FP-tree进行支持度计数的算法之中。

关联规则挖掘；FP-tree；最大频繁项集；支持度计数；搜索剪枝

0 引 言

关联规则的概念是由Agrawal等提出的[1-2],反映了大量数据中项目集之间有趣的关联或相关关系。频繁项集挖掘是关联规则挖掘中最关键的一步。实践中，由事务数据集产生的频繁项集的数量可能非常大，因此，从中识别出可以推导出其他所有频繁项集的、较小的、具有代表性的项集是有用的。由于最大频繁项目集中已经隐含了所有频繁项目集,所以可把发现频繁项目集的问题转化为发现最大频繁项目集的问题。另外,某些数据挖掘应用仅需发现最大频繁项目集,而不必发现所有的频繁项目集,因而发现最大频繁项目集对数据挖掘具有重大意义[3]。

频繁模式树(Frequent Patten tree,FP-tree)是由Han等提出的对于事务数据集的一种压缩存储方式[4]。基于FP-tree的算法可以避免Apriori系列算法需要多次读取事务数据集而造成的额外开销。目前，基于FP-tree的最大频繁项集挖掘算法主要有FP-Max[5]，DMFIA[3]，IDMFIA[6]，FPMFI[7]，BDRFIA[8]，等等。FP-Max与FP-growth类似，通过递归构建FP-tree的方式挖掘频繁项集，用超级检验的方法保证最终结果是最大频繁项集。DMFIA是一种自顶向下的最大频繁项集挖掘算法，与FP-Max相比，其无需递归生成FP-tree，对于最大频繁项集维度较大的数据效果较好；IDMFIA是在DMFIA基础上提出的双向搜索算法，充分利用了低维项集信息进行剪枝，扩大了算法的适用数据范围；FPMFIA使用基于投影的方法减少了超集检测的时间；BDRFI则改进FP-tree为DFP-tree(Digital Frequent Patten tree，数字频繁模式树)，运用多种预测剪枝策略，快速降低候选项集维度，减少了超级检测的时间。调研中还发现各文献对于“自顶向下”和“自底向上”的项集空间搜索的定义较为混乱[9-11]，因此文中的“自顶向下”的项集空间搜索特指从高维项集到低维项集的搜索。

上述基于FP-tree的最大频繁项集挖掘算法中多数都需要通过遍历FP-tree或其子树来计算项集的支持数，以避免多次扫描数据库或递归生成条件FP-tree。但是在项集支持度计数的过程中，没有充分利用在计算之前的项集支持度时所获得的信息，因而造成了不必要的检索开销。针对该问题，提出了基于FP-tree的支持度计数优化策略(Support Count Optimization Method on FP-tree,SCOM)。根据集合的性质，在搜索FP-tree计算项集的支持度时，记录路径对项集的支持信息，以达到减少搜索路径数的目的；并以DMFIA算法为例，应用该策略对算法进行改进，并设计实验进行验证。

1 相关知识

1.1相关定义和性质

设I={i1,i2,…,im}是由m个项组成的集合，D是由一组事务组成的事务数据集且D中事务都由I中的项组成。给定项集X⊆I,X在D中的支持数是指D中包含X的事务数，X在D中的支持度是指X的支持数占D中所有事务数的百分比。

定义1：对于项集X⊆I,若X在D中的支持度sX大于等于给定的最小支持度s,则称项集X为事务数据集D在最小支持度s下的频繁项集；反之，则称项集X为事务数据集D在最小支持度s下的非频繁项集。

定义2：对于项集X⊆I,给定最小支持度s,若X的所有超集都是非频繁项集，则称项集X为事务数据集D在最小支持度s下的最大频繁项集。

设R={n1,n2,…,nm}为由事务数据集D生成的FP-tree中的一条路径，所有项集和路径都是按照支持度降序排列的。

性质1：对于项集X,若X⊆R,则∀Y⊆X,Y⊆R且∀R'⊇R,X⊆R'；若X⊄R,则∀Y⊇X,Y⊄R且∀R'⊆R,X⊄R'。

证明：根据集合的性质容易得证。

对于项集X,Y⊆X且Y的最后一项为ei，R'为R的以ei结尾的前缀子路径。

性质2：若X⊆R,则必有Y⊆R'；若Y⊄R',则必有X⊄R。

证明：若X⊆R,由于所有项集和路径都是按照支持度降序排列的，则对于X的以ei为结尾的前缀子集X',必有X'⊆R'，而Y⊆X'，故Y⊆R',同理可证若Y⊄R',则必有X⊄R,证毕。

1.2FP-tree与DMFIA

FP-tree是一种输入数据的压缩表示法，它通过逐个读入事务，并把每个事物映射到FP-tree中的一条路径来构造。由于不同的事物可能会有若干个相同的项，因此它们的路径可能部分重叠。路径相互重叠越多，使用FP树结构获得的压缩效果越好。如果FP-tree足够小，能够存放在内存之中，就可以直接从这个内存中的结构提取频繁项集，而不必重复扫描存放在硬盘上的数据。

在FP-tree中，每个节点由4个域组成[12]:节点名称item-name、节点计数item-count、节点链item-link(用于指向树中具有相同item-name的下一个节点)，及父节点指针item-parent。同时为方便树的遍历，FP-tree还包含一个频繁项头表Htable，它由两个域组成:项目名称item-name和指向FP-tree中具有相同item-name的首节点指针head of node-link。

为了获得较好的压缩效果，通常需要将事务中的项按照支持度降序排列，尽管这样得到的FP-tree并不一定是最小的[13]。通过两次扫描数据集来构造FP-tree：

(1)第一次扫描数据集，确定每个项的支持度计数，丢弃非频繁项；按照支持度降序构建频繁项头表Headers，创建FP-tree的根节点，标记为“null”；

(2)第二次扫描数据集，对于每个事务Trans，根据项的支持度降序排列。令当前节点为根节点，顺序遍历Trans中的项，若当前节点包含与该项同名的子节点，则该子节点计数加1，当前节点变为该子节点；否则，创建当前节点的新的子节点，item-name=当前项的名称，item-count=1，item-parent指向当前节点，Headers中同名链表的尾节点的item-link指向该子节点。直到遍历完数据集中所有的事务，FP-tree构建完成。

文献[9]提出了FP-tree的一种改进—数字频繁模式树(DFP-tree)，用频繁项降序排列后的序号代替名称，有利于提高超集检测的效率。

DMFIA采用FP-tree的存储结构和自顶向下的搜索策略。它采用双重循环的方式挖掘最大频繁项集，外层循环是在MFCS非空状态下进行，内层循环以自底向上的方式进行处理，若MFCS中项集的支持度大于等于最小支持度阈值，则将该项集加入到最大频繁项集(Maximum Frequent Sets，MFS)中;对非频繁项集，通过循环每次删除该项集中的一个项来产生新的候选项集，对于新的候选项集需要判断在MFS和MFCS中是否存在超集，若不存在则将其加入MFCS中，否则将其删除。

2 SCOM

2.1主要思想

SCOM策略的主要思想是：在搜索FP-tree计算候选项集的支持度时，记录各个相关路径的支持状态；当通过该项集生成新的候选项集时，根据性质1、2将旧的项集的路径支持信息传递给新的候选项集，这样在计算新的候选项集的支持度时就可以剪除不必要的路径与候选项集的匹配。SCOM策略理论上适用于所有的DMFIA同类算法。

2.2算法步骤

为了让SCOM策略能够较好地发挥优势，需要为FP-tree的每一个节点增加一个域item_num，用来记录该节点在Headers中同名链表的序号，也就是在计算以该项结尾的候选项集的支持度时检索的路径序号；为每一个候选项集X增加一个二进制向量标记(binary vector)用以表示路径对X的支持情况，记为X.bv。X.bv(i)表示X.bv的第i位，X.bv(i)=0表示路径i不支持X,X.bv(i)=1表示路径i支持X。

DMFIA同类算法计算最大频繁项集的过程大致可分为如下几个步骤：

(1)初始化候选项集集合；

(2)选取部分候选项集，计算支持度；

(3)将最大频繁项集加入到结果集；

(4)通过非最大频繁项集候选项集生成新的候选项集，通过“超级检测”等策略筛选后，代替步骤(2)中候选项集加入到候选项集集合；

(5)重复步骤(2)～(4)直到候选项集集合为空。

SCOM策略主要体现在支持度计算(步骤(2))和新的候选项集生成(步骤(4))之中。支持度计算过程如下：

ProcedureComputeCount(FP-tree,Headers,m)

/*Headers为频繁项头表，m为待计算的最后一项为i的候选项集*/

begin

搜索项目头表Htable的项目名称域item-name,假设Htable[q1].item-name=i;

根据Htable[q1].head找到FP-tree中节点名称为i的节点n1,n2,…,nh;

根据n1,n2,…,nh及其前缀节点的父节点指针域，找到包含i的所有路径P1,P2,…,Ph;

for(j=1;j≤h;j++) do begin

ifm.bv的第j位为1 then//项集空间搜索方向为“自顶向下”时

m支持数增加ndj.node-count，continue;//性质1

/*

ifm.bv的第j位为0 then//项集空间搜索方向为“自底向上”时

continue;//性质2

*/

if路径Pj包含m,then//

m的支持数增加ndj.node-count;

m.bv的第j位置1

end

end

对每个非最大频繁项集候选项集m,设M'是由m生成的新的候选项集，则应用SCOM策略的算法如下：

begin

for allm'∈M'do begin

ifm'与m的最后一项相同，then

m'.bv=m.bv;

else

ComputeBV(FP-tree,m,m');//由性质2根据路径的包含关系计算路径支持信息

end

end

ProcedureComputeBV(FP-tree,Headers,m,m')

/*由性质2根据已计算过路径支持信息的m计算新的候选项集m'的路径支持信息，I(0)表示全0的二进制向量，|m.bv|表示m.bv的长度*/

/*针对“自顶向下”的项集空间搜索*/

begin

m'.bv=I(0);

fori=0 to |m.bv| do begin

ifm.bv(i)=0 then continue;

由Headers找到item_name=m末项名称的第i个节点Ni;

ifNi存在item_name=m'末项名称的祖先节点Nj,Nj.item_num=jthen

m'.bv(j)=1;

end

/*针对“自底向上”的项集空间搜索*/

begin

m'.bv=I(1);

fori=0 to |m.bv| do begin

ifm.bv(i)=1 then continue;

由Headers找到item_name=m末项名称的第i个节点Ni；

ifNi存在item_name=m'末项名称的子孙节点Nj,Nj.item_num=jthen

m'.bv(j)=0

end

2.3算法实例

举例说明该策略的优化过程。图1为一棵数字频繁模式树。

图1 数字频繁模式树

设X={2,3,5}为已经计算过支持度的候选项集，则X.bv=(1,0)；Y1={2,5}，Y2={2,3}为“自顶向下”的项集空间搜索算法生成的新候选项集，Y3={2,3,5,6}为根据自底向上搜索算法生成的新候选项集，根据SCOM策略能够快速得出Y1.bv=X.bv=(1,0)，由ComputeBV得Y2.bv=(1,0)，Y3.bv=(1,0,1)，则在计算Y1、Y2的支持度时，只需搜索item_name=6的第二条路径，在计算Y3的支持度时，只需搜索第一条路径与第三条路径。

3 实验结果

为了验证SCOM策略的实际优化效果，在8 G RAM，Intel Core i5-2430 M CPU 2.40 GHz，Windows7操作系统上用Java实现了DMFIA原算法和应用了SCOM策略的DMFIA算法SCOM-DMFIA。实验采用的测试数据集为mushroom，包含有8 124条记录，记录平均长度为23，共有115个蘑菇属性。图2为在不同最小支持度下(分为5%，10%，15%，20%，25%五档)两种算法的执行时间对比结果。

图2 mushroom数据集上两种算法的执行时间对比

从图2可以看出，应用了SCOM策略的DMFIA算法的整体运行时间明显少于原算法。为了进一步说明SCOM策略通过优化支持度计数进而提高最大频繁项集挖掘算法整体性能的过程，实验中还监测了两种算法用于支持度计数的时间开销，如图3所示。

图3 mushroom数据集上两种算法用于支持度计数的时间对比

从图3中可以看出，SCOM明显降低了DMFIA算法用于支持度计数的时间。

以上实验结果说明，SCOM策略的确能在基于FP-tree的支持度计数过程中减少搜索路径，降低时间开销，进而提高整个最大频繁项集挖掘算法的效率。

4 结束语

文中提出的基于FP-tree的支持度计数优化策略—SCOM，通过记录支持度计算过程中路径对项集的支持情况，依据相关性质在支持度计算中搜索FP-tree时避免不必要的搜索路径，以达到搜索优化的目的。实验结果表明，该策略有效提高了最大频繁项集挖掘算法DMFIA的运行效率，并且可以推广应用到DMFIA的同类算法中。下一步的工作中将进一步探究SCOM在其他种类频繁项集挖掘算法中的适用性。

[1] Agrawal R， Imielinski T，Swami A． Mining association rules between sets of items in large database[C]//Proceedings of 1993 ACM SIGMOD conference on management of data．New York:ACM，1993:207-216．

[2] Han J, Kamber M. Data mining:concepts and techniques[M].Beijing:High Education Press,2001.

[3] 宋余庆，朱玉全，孙志挥，等．基于FP-tree的最大频繁项目集挖掘及更新算法[J]．软件学报，2003，14(9):1586-1592．

[4] Han J，Pei J，Yin Y．Mining frequent patterns without candidate generation[C]//Proceedings of the 2000 ACM-SIGMOD international conference on management of data．New York:ACM，2000:1-12．

[5] Grahne G，Zhu J．High performance mining of maximal frequent itemset[EB/OL]．[2014-07-06]．http://www．docin．com/p-773109811．html．[6] 吉根林，杨 明，宋余庆，等．最大频繁项目集的快速更新[J]．计算机学报，2005，28(1):128-135．

[7] 颜跃进，李舟军，陈火旺．基于FP-Tree有效挖掘最大频繁项集[J]．软件学报，2005，16(2)：215-222．

[8] 钱雪忠，惠 亮．关联规则中基于降维的最大频繁模式挖掘算法[J]．计算机应用，2011，31(5):1339-1343．

[9] 颜跃进,李舟军,陈火旺.一种挖掘最大频繁项集的深度优先算法[J].计算机研究与发展,2005,42(3):462-467.

[10] 陈 晨,鞠时光.基于改进FP-tree的最大频繁项集挖掘算法[J].计算机工程与设计,2008,29(24):6236-6239.

[11] 王黎明,赵 辉.基于FP树的全局最大频繁项集挖掘算法[J].计算机研究与发展,2007,44(3):445-451.

[12] 付冬梅，王志强．基于FP-tree和约束概念格的关联规则挖掘算法及应用研究[J]．计算机应用研究，2014，31(4):1013-1015．

[13] Tan Pangning．数据挖掘导论：英文[M].北京：人民邮电出版社，2006.

SupportCountOptimizationMethodBasedonFP-tree

ZHAO Yang，BAI Fan

(Jiangnan Institute of Computer Technology，Wuxi 214083，China)

In the association rules mining,mining frequent itemsets is the most critical step.Maximum frequent itemsets is the most common simplified representation of frequent itemsets.Maximum frequent itemsets mining algorithms based on FP-tree are most needed to search the FP-tree bottom-up to count the support of the itemsets,but they have not considered the information obtained by completed support counting while counting the current itemset,resulting in unnecessary overhead.To solve it,Support Count Optimization Method on FP-tree,called SCOM for short,is proposed.With a small additional space cost,it can make full use of the information that whether a path supports a itemset and the relation between the itemsets to prune the search.Experimental results show that the maximum frequent itemsets mining algorithm applied obtains a performance boost with SCOM which optimizes the support count based on FP-tree,so it can be applied to all algorithms that use FP-tree to count support.

association rules mining;FP-tree;maximum frequent itemsets;support count;search prune

TP311

A

1673-629X(2017)10-0030-04

2016-11-14

2017-03-16 < class="emphasis_bold">网络出版时间

时间：2017-07-11

国家科技重点专项“核高基”(2015ZX01040-201)

赵 阳(1991-)，男，硕士研究生，研究方向为数据挖掘、文本分析及可视化；导师：刘镇江，高级工程师，研究方向为数据挖掘、信息处理、数据可视化。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1457.090.html

10.3969/j.issn.1673-629X.2017.10.007