基于FP－growth的改进算法-论文.pdf

《基于FP－growth的改进算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《工业控制计算机}2015年第28卷第5期1O5基于FP—growth的改进算法OptimizationofFP-growthAlgorithm郑志成姜昌金(东南大学自动化学院，江苏南京210096)摘要介绍了目前关联规则挖掘中效率较高的FP-growth算法，并对FP-growth算法中存在的几点不足进行了相应的改进。改进后的算法从时间性能和空间性能两方面都得到了很大的提升。关键词：数据挖掘，FP—growth，频繁闭项集AbstractThispaperdescribestheFP-growth

2、algorithm-oneofthemosteficientalgorithmamongalltheassociationrulealgo·rithms．andmakesupforseveraldeficienciesexistinFP—growthalgorithmTheoptimizedalgorithmimprovetheeficiencyofthealgorithmintimeaswellasspace．Keywords：datamining，FP—growth，frequentclosed

3、itemsets关联规则挖掘是数据挖掘中最常用的方法之一¨1]，它最早表1事物数据集D表2FP—tree的定义是Agrawal等人在1993年时提出的，主要是用来描述事务数TIDItemset节点名据库中各数据项之间的关系。关联性挖掘方法可以分为两大类：1"1f，a，c，d，g，i1到选节点子路Count径数T2b，a，c，f，1，m，o产生候选集候选模式的方法和不产生候选集候选模式的方法。前父节点ParentT3b，f，h，j首孩子节点firstchild一种方法有Apriori等算法，而后一种有

4、FP—growth等算法_2]。前T4f，b，c，k，P，q兄弟节点nextsibling一种由于它需要多次扫描数据库，可能会产生庞大的候选集，而T5同名节点后一种方法则是构建一颗FP—tree树来存放数据库中的主要信2)定义一个根(nul1)结点，表3优化后事务数据集息，只需要扫描两次数据库即可，而且不需要产生候选集，相比然后第二次扫描事务数据集，TID优化后项集ID于Apriori算法，无论在时间性能还是空间性能上都有了很大的对事务数据集中的每条事务进Tlf，c，a，m提升。本文对FP—grow

5、th进行了分析和研究，并对其存在的几行优化，首先丢掉L头表中未T2f．c，a．b，mT3f，b点不足进行了改进。出现过的非频繁项，然后将保T4f，c，b，P1相关的概念留的频繁项按照L头表中次序T5t，c．a，m，pl={a，b，C，d，e，f，g，h，i，j，k，I，m，n，o，P，qJ是一项目全集，(即按递减支持度计数)排序，包含k个项的项目集称为k一项集]，D={T1，T2，T3，T4，T5}是一从根结点开始构建FP-tree，相同的前缀的路径可以共用，构造事物数据库，在D中包含项集Y的个数称

6、为项集Y的支持度的FP—tree树如图1所示。sup(Y)，给定一个最小支持度min_sup，对于sup(Y)大于等于min_sup的Y称为频繁项集。对于一个项集Y来说，如果它是频繁的，而且不存在这样一个项集Y：Y是Y的超集且sup(Y)=sup(Y)。我们就称项集Y为频繁闭项集]。2FP—growth算法2．1基本思想及算法描述FP—growth算法是在大型数据库中挖掘频繁项集的一个有效的算法[3]。该算法在挖掘频繁项集时不需要产生候选集。算法的基本过程如下：首先，设定一个最小支持度，扫描一遍事物

7、数据库，确定每个项集的支持度，将支持度小于最小支持度的项集舍弃，将剩下的项集按支持度递减排序。然后第二次扫描事物数据库，生成FP—tree，挖掘FP—tree生成项的条件模式基[a]，构造条件FP—tree，在条件FP—tree中递归挖掘。2．2算法实现2．2．1FP—tree的构造图1初始的全局FP—tree1)设定最小支持度为2，扫描给定的事务数据集，得到频繁2．2．2FP—tree的挖掘1一项集，记录其支持数，删除小于最小支持度的非频繁项集，并基本思想是对频繁项头表中的每一项生成其条件模式基，

8、将剩下的频繁项集按照支持数递减排序，生成频繁项头表L=并利用fp-tree的生成方法建立每一项的条件模式树，在此基{(f：5)，(c：4)，(a：3)，(b：3)，(m：3)，(p：2)}。106基于FP-growth的改进算法础上，递归调用自己，产生频繁项集(每个频繁项集都取支持度支持度小于该频繁闭项集的组，只需要查找支持度相同的组即最小的，当只有单路径时结束)。可，如果没有被包含，就插入进该组中。同一组的组成员之间的过程：顺序同全局频繁项头表中的顺序相同。输入：一