基于FP-矩阵的频繁项集挖掘算法.pdf

《基于FP-矩阵的频繁项集挖掘算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2011年8月中国制造业信息化第40卷第15期基于FP一矩阵的频繁项集挖掘算法刘芝怡，尹飞鸿(常州工学院计算机信息工程学院，江苏常州213002)摘要：针对频繁项集挖掘时间与空间效率低的问题，提出一种基于FP一矩阵的高效频繁项集挖掘算法。用此算法构造FP一矩阵压缩事务数据库，无需递归构造条件模式树，仅需3次扫描数据库即可生成所有频繁项集。最后的实验证明了该算法的有效性。关键词：数据挖掘；频繁项集；FP一矩阵中图分类号：TP311文献标识码：A文章编号：1672—1616(2011)15—0040一O4目前频繁项集挖掘已成为了数据挖掘领域中用了如下的分治策

2、略：首先，将提供频繁项集的数的一个基本问题，广泛应用于关联规则挖掘、搜索据库压缩成一棵频繁模式树(FP一树)，但仍然保引擎、web日志分析等领域。在挖掘频繁项集的留项集关联信息。然后，将这种压缩后的数据库分方法中，主要以Agrawal1993年提出的Apriori[-2]成一组条件数据库(一种特殊类型的投影数据库)，算法最具代表性。Apriori算法采用自底向上的思每个条件数据库关联一个频繁项，并分别挖掘每个想，利用已知的—l来生成，再扫描一次数据数据库。库来判断候选项集是否频繁。算法的主要时间消耗算法FP—Growth描述如下_6j：在删减候选项集以及

3、确定频繁项集上。其缺输入——事务数据库DB，最小支持度Min—点主要有：(1)需要多次扫描数据库，在挖掘海量数Supp。据时，数据库的扫描会相当耗时。(2)需要生成大输出——频繁模式的完全集。量的候选频繁项集，存储和计算这些频繁项集的支具体步骤：持度非常麻烦和耗时。之后许多学者依照此算法a．根据事务数据库DB构造FP一树：(1)扫描的缺点提出了许多改进算法，旨在减少数据库扫描DB一次，产生所有频繁l_项集及其支持度计数，的次数和增加执行效率，例如DHPE4J算法可以按其支持度降序排列插入到项头表。(2)gJ建FP一减少候选项集的产生，DICe5]算法可同

4、时扫描多个树的根节点，用“null”标记。对DB中的每个事务阶段，降低数据库的扫描次数。这些改进算法在一T做如下处理：(1)按项头表中次序排列T中的频定程度上提高了效率，但由于都未脱离Apriori算繁项目，设排序后的结果为[PIP]，其中P是第一法的框架，仍然无法克服Apriori方法一些固有的个项目，P是剩余项目的列表。(2)如果P非空，递缺陷，如可能产生大量的候选项集，需要反复扫描归调用insert—tree([PIP]，T)。过程insert～数据库。对此韩家烨等提出了一种本质上不同于tree([P『P]，T)的执行步骤为：如果T有子女NApri

5、ori的挖掘频繁模式的有效算法——FP一使得N．node—na?Tte=P，则N的计数增加l；否则(wth6。此算法利用FP一树存储数据库中的频集，只需扫描数据库2次，并且不需要产生候选创建一个新节点N，将其节点名称node—name、节项集，效率比Apriori算法要高一个数量级，但该算点记数sup—count分别设为P，1，由父节点指针node法在执行过程需递归构造基于内存的FP一树，因—parent链接到它的父节点，并通过节点链nodelink将其链接到同名节点。此会占用大量的内存空间，当数据库很大时，这将—成为算法的主要瓶颈。b．FP一树的挖掘通

6、过调用过程FP～Growth(FP—tree，nul1)实现。1FP—Growth算法FP—Growth算法刚好扫描2次事务数据库：FP—Growth算法是一种深度优先算法，它采第一次扫描生成频繁1一项集；第二次扫描构造收稿日期：2011—04—19作者简介：刘芝怡(1977一)，女，江苏常州人，常州工学院讲师，硕士，主要研究方向为数据库技术、计算机网络、数据挖掘。·计算技术·刘芝怡尹飞鸿基于FP一矩阵的频繁项集挖掘算法41FP～树。FP—Growth算法将发现长频繁模式的下面用一个例子来说明FP一矩阵的构造过问题转换成递归地发现一些短模式，然后连接后程

7、。表1是一个交易数据库，假设最小支持度为缀。它使用最不频繁的项作后缀，提供了很好的选60％，则对应的最小支持度计数为3次(5×60％：择性，大大降低了搜索开销。但是该算法也存在一3)。些缺点：(1)在挖掘频繁项集时，FP—Growth算法表1交易数据库示例需要递归地生成条件FP一树，并且每产生一个频繁模式就要生成一个条件FP一树。在支持度阈值较小的情况下，也要产生数以万计的频繁模式。动态地生成和释放这些大量的条件FP一树，将会消耗大量的时间和空间。(2)由较大的条件模式树构造较小的条件模式树需要扫描原有模式树2次，这也是非常浪费时间的。(3)FP一树和条

8、件FP一树第一次扫描原始数据库之后，对频繁1一项集需要自顶向下生成，而频繁模式的