基于FP-Tree的挖掘最大频繁项目集的新算法

杨青侠 何明祥 邱冬冬 聂宝军

山东科技大学信息科学与工程学院，山东 青岛 266000

基于FP-Tree的挖掘最大频繁项目集的新算法

杨青侠 何明祥 邱冬冬 聂宝军

山东科技大学信息科学与工程学院，山东 青岛 266000

引言

关联规则是由Agrawal等人首先提出的一个重要的数据挖掘研究课题[1]。而挖掘频繁项目集是关联规则挖掘的关键技术。在此基础上Agrawal等人于1993年首次提出为布尔关联规则挖掘频繁项集的Apriori算法。虽然，Apriori算法是数据挖掘中最重要的算法之一。但是它也存在着不足。Apriori算法为了挖掘频繁项目集，必须产生所有的候选项目集，候选项目集的数量很庞大。并且为了得到候选项目集的支持度，算法必须重复的扫描数据库来确定候选项目集的支持度。计算候选项目集的支持度是最耗时的工作。所以减小成本的最好手段就是降低候选项目集的数目和减少数据库的扫描次数。FP-Tree[2]存储结构就是为了解决这两个问题而被提出的。FP-Tree的构造只扫描两次数据库。第一次数据库扫描和Apriori相同，它导出频繁项（1-项集）的集合和支持度计数（频率）。第二次数据库扫描用于构建FP-Tree和保存重要信息。

最大频繁项目集中包含了所有的频繁项目集信息。所以对频繁项目集的挖掘就转化为对最大频繁项目集挖掘的问题。目前挖掘最大频繁项目集的算法有Max-Miner[3]，Pincer-Search[4]，DMFI[5]及DMFIA[6]等算法。其中DMFIA基于FP-Tree存储结构，虽然克服了先前的挖掘算法的不足，但仍然生产了过多的候选项目集。本文在研究大量算法的基础上，提出了一种基于FP-Tree的新的挖掘算法FP-GDMA。该算法采用自顶向下和自底向上的双向搜索策略有效减少了候选项目集的数目，提高了挖掘最大频繁项目集的效率。FP-GDMA算法通过能快速的剪枝掉不在最大候选项目集中的项目集，减少候选项目集的数目。并通过实验表明FP-GDMA算法优于DMFIA算法。

1 FP-GDMA算法

1.1 FP-Tree的构建

按以下步骤构建FP-Tree：

1）第一次扫描数据库D,D为要挖掘的事务数据库。导出频繁项的集合和支持度计数。创建一个顶头表L存放频繁项的信息。L的每一个表项有3个域组成：项目名itemname，项目名的支持度计数item-count，项目链头item-head，item-head为指向FP-Tree中与之具有相同item-name的首节点的指针。将导出的频繁项的集合按支持度计数的降序排列，一次存放到L的各表项中。

2)第二次扫描数据库D,创建FP-Tree。其中，FP-Tree中的每个节点有4个域组成：节点项目名node-name，节点的计数node-count，父节点指针node-parent，节点链node-link。其中，node-link为指向FP-Tree中拥有相同node-name值的下一个节点。首先，创建FP-Tree的根节点，用”root”标记。每个事务中的项按递减支持度计数排序。对D中每个事务Trans，执行：选择Trans中的频繁项，并按L中的次序排列。调用insert_tree([p|P],t)。该过程执行情况如下：如果t有一个子女n.node-name=p.node-name，则n.nodecount++，否则创建一个新节点n，则n.node-name=p.node-name,n.node-count等于1,连接到它的父节点T，且通过节点链结构将其链接到具有相同node-name的节点。只要P非空，就递归调用insert_ tree(P,n)。

1.2 FP-GDMA算法的思想

FP-GDMA算法通过自顶向下和自底向上相结合的搜索策略来快速的挖掘最大频繁项目集。该算法思想：1）自顶向下搜索FP-Tree的每一个分支，如果分支中的节点的n.node-count s,则继续搜索分支中的下一个节点，直到节点的n.node-count s或节点n为叶子节点。将该分支中的所有满足n.node-count s的节点项集作为最长的最大候选项集。2）如果n.node-parent还存在其他分支则重复1中的步骤。如果有更长的最大候选项集则更新。直到FP-Tree的每个分支搜索完毕,算法将得到一个最长的最大候选项集P和一个不在P中出现的项的集合Q。3）如果Q非空,对Q中的每一项利用项头表中的信息,得到以该项为后缀的路径。并利用交集的思想，将路径两两相交求交集。如果交集的count大于s，则为频繁项集。对Q中的项重复步骤3)最终可求得最大频繁项目集。

1.3 FP-GDMA算法的过程描述

输入：事务数据库D生成的FP-Tree，最小支持度计数阈值s，

输出：最大频繁项目集MFS

方法：

一次自顶向下的搜索FP-Tree得到一个最大长度的最大频繁项集候选P；//P必是频繁项集的前缀或是一个频繁项集

设Path数组中保存了以e为后缀的所有路径信息,PathC数组保存了对应于Path数组中的各路径的支持度计数。MaxF数组保存Path数组中的交集信息,MaxFC保存MaxF中各交集的支持度计数。

if MaxFC[i]≥s 并且MaxF[i]不是MFS中某项集的子集

例1 事务数据库D如下，minsup=0.5,求D的最大频繁项目集

事务数据库D

图1 事务数据库D的FP-Tree

首先构建事务数据库D的FP-Tree如图1,s=3。

根据FP-GDMA算法对例1中给出的事务数据库D，求最大频繁项目集的过程如下：自顶向下搜索FPTree得到P={f,c,a,m,p}，进一步求得Q={b},然后进入do-while循环。调用getMFS（FP-Tree，b）自底向上搜索FP-Tree，最大频繁项目集MFS={{f,b},{c,b}}。算法的最后判断P不是MFS的子集，则将P并入MFS，最终得到MFS={{f,c,a,m,p},{c,b},{f,b}}。

2 算法比较

实验环境为Windows XP Professional操作系统，CPU 1,59GHz和2GB的内存，用VC++6.0实现DMFIA和FP-GDMA算法。测试数据库采用mushroom。该数据库含有8124条记录。记录了蘑菇的23种属性。图2显示了DMFIA和FP-GDMA算法在不同最小支持度（分7档:25%，20%,15%，10%,5%,2%,1%）下的时间比较。由于FPGDMA产生的最大候选项目集的数目小于DFMIA，且执行时间比DMFIA短。故FPGDMA算法比DMFIA优越。

图2 DMFIA和FP-GDMA的挖掘对比

3 结语

本文以FP-Tree的存储结构为基础，提出了挖掘最大频繁项目集的FP-GDMA算法。FP-GDMA利用自顶向下和自底向上的双向搜索策略快速的挖掘最大频繁项目集。FP-GDMA算法采用了交集的方法克服了DMFIA算法产生大量最大候选项目集的缺点，提高了挖掘最大频繁项目集的效率。

[1]朱玉全,孙志辉,季小俊.基于频繁模式数的关联规则增量式更新算法.计算机学报，2003,26(1):91～96

[2]Han JW,Pei J,Yin YW.Mining frequent patterns without candidate generation.In:Weidong C, Jeffrey F,eds.Proc.of the ACM SIGMOD Conf.on Management of Data.Dallas:ACM Press,2000. 1～12.

[3]BAYARDO R.Efficiently Mining Long Patterns from Databases[A].HAAS LM,ed.Proceedings of the ACM SIGMOD International Conference on Mangement of Data[C].New York:ACM Press,1998:85～93

[4]L IN D I,KEDEM ZM.Princer-Search:A New Algorithm for Discovering the Maximum Frequent Set[A].SCHEK HJ,ed.Proceedings of the 6th European Conference on Extending Database Technology[C].Heide lberg:SpringerVerlag,1998:105～119

[5]惠亮,钱雪忠.关联规则中FP-Tree的最大频繁模式非检验挖掘算法.计算机应用,2010,30(7):1922～1925

[6]宋余庆,朱玉全,孙志辉,陈耿.基于FP-Tree的最大频繁项目集挖掘及更新算法.软件学报，2003,14(9):1586～1592

[7]吉根林,杨明,宋余庆,孙志辉.最大频繁项目集的快速更新.计算机学报,2005,28(1):128～135

[8]梅俊,郑刚.一种基于FP-Tree的最大频繁项目集挖掘算法.研究与发现,2009,315(9):33～36

[9]郑海明.基于FP-Tree最大频繁项集的FP-MFI算法研究，2008,293(10):37～39

[10]路松峰,卢正鼎.快速开采最大频繁项目集.软件学报,2001,12(2):293～297

A New Algorithm for Mining Maximum Frequent Itemsets Based on FP-Tree

Yang Qingxia He Mingxiang Qiu Dongdong Nie Baojun
College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao, China

挖掘最大频繁项目集是数据挖掘领域的一个重要的研究内容。Apriori算法作为一种挖掘频繁项目集的基本算法，其缺点是产生大量的候选项目集，算法的代价很大。本文在基于FP-Tree的基础上提出了挖掘最大频繁项目集的新算法FP-GDMA。该算法采用自顶向下和自底向上相结合的搜索策略有效减少了生产候选项目集的数目，有效提高了挖掘最大频繁项目集的效率。并通过实验比较FPGDMA与DMFIA算法。

最大频繁项目集;数据挖掘；FP-Tree;FPGDMA;DMFIA

Mining maximum frequent itemsets is an important research in data mining field.Apriori,as the basic algorithm for mining frequent itemsets,has drawbacks such as generating many candidate maximum frequent itemsets and tremendous cost .This paper proposes a new algorithm for mining maximum frequent itemsets named FP-GDMA based on FP-Tree. It uses the search strategy with combination of top-down and bottom-up,which effectively reduces the number of candidate frequent itemsets and effectively improves the efficiency for mining maximum frequent itemsets. The paper also compares FP-GDFM and DMFIA by experiment.

Maximum Frequent Itemsets; Data Mining; FPTree;FP-GDMA;DMFIA

10.3969/j.issn.1001-8972.2012.14.047

DOI：10.3969/j.issn.1001-8972.2012.14.089