基于afopt-tree的最大频繁项集挖掘(20180524132040)

《基于afopt-tree的最大频繁项集挖掘(20180524132040)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、后来人们陆续提出了一些技术对Apriori算法进行了改进，但作为作为广度优先策略的频繁项集挖掘算法，任然无法避免产生候选项集和对于数据库的多次扫描。因此，后来深度优先策略的挖掘算法逐渐成为频繁项集挖掘的主流算法，FP-Growth算法就是其中最具代表性的算法。2、EP-Growth算法利用FP-Growth算法进行频繁项集挖掘的算法思想主要分为两步：首先要根据事物数据集创建一棵压缩的条件模式树FP-Tree。FP-Tree屮的每一个结点都对疲一个项.树中每-条从根结点到某个子孙结点的路径表示一个项集。每个结

2、点都记录了从根节点到该结点项集的支持度，并且每个结点还有指向其前驱结点和相同结点的指针域。然后再递归的调用EP-Growth算法进行频繁项集的挖掘。构造FP-Trcc的算法过程如下所示：(1)扫描事物数据集D，产生频繁1项集集合F及其计数，并将获得的项集按其计数的降序进行排列，生成FP-Tree的头表Header。(2)创建FP-Tree的根节点T=null，并再次扫描事物数据集D，对事物数据集(3)D中的每一项数据，根据头表中获得的频繁1项集集合删除其中的非频繁项，然后按照(1)中所获得头表顺序进行排序，

3、假定所得的结果为［p

4、P］，其中P为频繁项目的首项，P则为其剩余项目，递归调用过程insert-tree(［p

5、P］，T)。其中insert-tree(［p

6、P］，T)的过程如下：如果T中有子女结点N使得N.name=p,则将结点N的计数加1;若不存在，则建立一个新的结点N,其中N.name=p,N.count=l,并将N结点的父指针域指向其前驱结点T,将N结点的结点链指向与其相同的结点。对于表2-1屮的事务数据集，在最小支持度min_sup为3时，所创建的FP-Tree如图2-2所不。频繁模式树FP-tr

7、ee构造完成以后，就可以利用FP-Growth算法对其进行相应的关联规则挖掘。FP-Growth算法主耍步骤如下：输入：频繁模式树FP-tree，最小支持度min_sup，事务数据集D输出：D屮的所有频繁项集FP-Growth(T,h)(1)IFT中只包含唯一路径P(2)对P屮所有结点的每个组合(记为夕)(1)生成频繁项目集An/?，其支持度等于当中结点的最小支持度(2)ELSE对FP-tree头表中的每个元素％do(3)生成频繁模式夕其中/?.S叩=6ZrSUp(4)构造0的条件模式基的集合并创建条件模式

8、子树(5)IFFP-tree0(6)递归调用FP-Growth(FP-tree^h)FP-Growth算法将数据集中与关联规则挖掘相关的信息压缩保存在了FP-tree中，只需要扫描W次数据库，避免了产生候选项集的问题，减少了算法的I/O消耗；并且算法利用递归的方式将频繁项集的挖掘转化为对一些较短的频繁项集再加上其后缀的挖掘过程，具有良好的选择性，提升丫算法的运行效率。相比Apriori及其改进算法，FP-Growth算法的性能有了巨大的提高。但是当最小支持度较小，或者当数据集中的长数据项较多时，算法在运行过

9、程中会产生大量的条件模式子树，产生巨大的系统开销，并且影响算法的运行效率。2.3最大频繁项集挖掘2.3.1频繁项集的分类传统的频繁项集挖掘算法获取的是事务数据集屮所有的频繁项集，即完全频繁项集。但是随着信息产业尤其是互联网行业的不断发展，人们需要处理的信息越来越多，而数据挖掘所需要处理的数据集也越来越大，获取信息中所有的关联知识变得越来越困难，并且在通常情况下也没有必耍;所以，人们提出了频繁闭项集和最大频繁项集的概念，来简化关联规则挖掘所获取的关联信息频繁闭项集和最大频繁项集的具体定义如下：定义4当且仅当：

10、(1)sup(C)>min_sup；(2)对于任意的频繁项集X都有当CczX则sup(C)〉sup(Y)，称C为事物数据集D上的频繁闭项集。定义5当且仅当：(1)sup(A/)>min_sup；(2)对于事物数据库中的任意项集X都有当McX则sup(X)

11、集，当支持度较小时，频繁闭项集的规模也非常庞大,因此自从1998年提出最大频繁项集的概念以后，最大频繁项集的挖掘也越来越受到人们的关注。最大频繁项集挖掘算法中，最具影响力的算法就是Grahne等人提出的FP-max算法心FP-max算法是一种基于FP-tree的深度优先搜索的最人频繁项集挖掘算法。在算法对条件模式树进行遍历时，不仅保存了遍历结点在搜索空间树中的路径信息，同时也对遍历过的结点的条件模式基，即搜索空间