1、1基于格的快速频繁项集挖掘算法基金项目：国家自然科学基金资助项目（61072121） ；湖南省自然科学基金资助项目（12JJ2035） ；“中央高校基本科研业务费”资助项目 作者简介：刘彩苹（1978-） ，女，湖南邵阳人，湖南大学教师，博士 江西 抚州 344000；3.湖南大学 电气与信息工程学院，湖南 长沙410082） 摘要：随着数据库规模的增加或支持度阈值的减少，频繁模式的数量将以指数形式增长，FPgrowth 算法运行的时空效率将大为降低本文提出一种基于格的快速频繁项集挖掘算法 LFPgrowth，算法利用等价关系将原来的搜索空间（格）划分成若干个较小的子空间（子格） ，通过子格间
2、的迭代分解，将对网格 P（I）的频繁项集挖掘转化为对多个子格的并集进行的约束频繁项集挖掘实验结果和理论分析表明，在挖掘大型数据库时，LFPgrowth 算法的时间和空间性能均优于 FPgrowth 算法 关键词：数据挖掘；FP 树；频繁项集；格 中图分类号：TP31113 文献标识码：A 频繁项集挖掘是数据挖掘中的一类重要挖掘问题，广泛应用于关联规则挖掘、相关性分析、入侵检测、序列挖掘、分类分析、聚类分析、Web 挖掘、XML 挖掘等诸多数据挖掘任务长期以来， 人们对频繁模式的2挖掘进行了大量深入的研究工作 Han 等人提出了一种比 Apriori 算法快一个数量级的 FPgrowth 算法随
3、后，各国的研究者们提出了许多其他改进算法，如 Koh 等人提出的基于树的高效频繁项集挖掘算法，李也白等人用一种辅助存储结构提高了查询的效率，Nguyen 利用矩阵提出的频繁项集挖掘算法，郭宇红等人提出的反向频繁项集挖掘算法，Zeng 等人提出了加权关联规则挖掘算法 Jalan 提出了一种非递归频繁项集挖掘算法Adnan 提出一种自适应的频繁项集挖掘算法赵强利提出一种快速选择性集成算法范明提出一种不生成条件 FP 树的算法谭军提出了一种单遍扫描频繁模式算法 FPgrowth 算法开辟了有效挖掘频繁模式的新途径然而，它的时间和空间效率还不足够高，仍需改进 FPgrowth 算法的主要问题是建树过程
4、中必须将提供频繁项集的数据全部压缩到一棵频繁模式树（或 FP 树） ，在挖掘时，由长度为 1 的频繁模式（初始后缀模式）开始，递归的构造条件 FP 树进行挖掘，在建树和挖掘过程中都需要占用大量的内存当数据库很大，或者数据库中的频繁 1 项集的数目很大时，运行速度将大为降低；更有甚者，可能由于无法构造基于内存的 FP 树，该算法将不能有效地工作 本文结合大型数据库本身的特性，在分析 FPgrowth 算法的基础上，提出了一种基于格的大型数据库频繁模式挖掘算法 LFPgrowth 实验和分析表明，在挖掘大型数据库时，LFPgrowth 算法具有较好的时间和空间效率 1 基本概念和问题的描述 3为方
5、便讨论，以事务数据库为背景设为所有项目的集合，为事务数据库， 其中每个事务有一个惟一的标识 TID 表 1 中的事务数据库是本文的示例数据库该数据库中事务已经按照各项的支持度计数递增地将各事务中的项重新排列 在事务数据库中挖掘频繁项集的问题可以描述为：给定事务数据库D 和最小支持度阈值 minsup ，挖掘所有的频繁项集 由定理 3 得到以下结论，对网格 P（I）的频繁项集挖掘转化为对多个子网格的并集进行的约束频繁项集的挖掘，不会影响频繁项集完全集的正确输出 22 算法步骤 实现 LFPgrowth 算法的关键是子格（子搜索空间）所对应的事务的迭加，如果复制所有的子格对应的事务进行迭加，时间和
6、空间的效率会非常低为此，可以借鉴 Christian Borgelt 教授在研究 Recursive elimination 算法时提出的事务链表（transaction list array）来实现迭加 事务链表是由一组单向数据链表组成，每一个单向数据链记录一个子格 P（k）所对应的事务集（以下简称为 P（k）事务集）的信息，每一个单向数据链都包括一个计数器（support counter）和一个指针计数器的值表示 P（k）事务集的总数，指针则用于保存 P（k）事务集的关联信息将所有单向数据链表按 P（k）处理的顺序排列，便组成了事务链表样例数据库的事务链表组如图 3 所示 当数据库为海量数
7、据库时，可将它分解迭加成多个 P（k）进行挖掘，4而当某个 P（k）对应的事务很多，依然无法在内存中构造 Fp 树时，挖掘就难以顺利进行根据定理 5 可知 P（k）是格，因此我们可将 P（k）再次进行迭加分解，如果分解后扩展子格依然无法在内存中构造 Fp 树时，就再继续分解直到可以在内存中构造扩展子格的 Fp 树为止 3 实验结果和分析 31 实验结果 本节对 LFPgrowth 算法和 FPgrowth 算法进行比较，程序代码均用Visual C+实现实验在 Petium28G，内存 512M，硬盘 80G 的 PC 机上运行实验结果如图 5图 7 所示 图 5 是采用 accidents
8、数据库进行实验，该数据库大小为 336 M，是比利时国家统计院提供的 1991-2000 年期间 Flanders 地区的交通事故数据库由图 5 可知，当最小支持度大于等于 05%时，FPgrowth 算法的运行速度比 LFPgrowth 算法略快但是，当最小支持度小于 05%时，LFPgrowth算法的运行速度比 FPgrowth 算法快而且随着支持度的减少，差别越明显 图 6 是采用 bio_train 数据库进行实验，该数据库是 KDD Cup 2004所提供的关于蛋白质同源性的训练数据库该数据库有 145 751 行，每行包含有 1 个块号、1 个试验号和 74 个特征值图 6 是在事
9、务数据库大小为664 M 条件下，最小支持度从 3%减少到 005%的两种算法运行时间的比较，由图 6 可知，当最小支持度等于 3%时，FPgrowth 算法的运行速度比LFPgrowth 算法快但是，当最小支持度小于等于 1%时，LFPgrowth 算法的运行速度比 FPgrowth 算法快而且随着支持度的减少，差别越大 32实验结果分析 5FPgrowth 算法要将事务数据库中所有产生频繁项集的数据压缩到一棵 FP 树中，该树中存储的关联信息从建树开始到挖掘完毕都完整地保存在内存里，挖掘时又通过递归创建条件 FPtree 生成频繁模式，条件FPtree 个数等于频繁模式数，所以建树挖掘的时
10、间和空间开销都很大，尤其是随着数据库规模的增加或支持度阈值的减少而导致频繁模式的数量以指数形式增长时， FPgrowth 算法无法构造基于内存的 FP 树，从而导致挖掘失败而 LFPgrowth 算法虽然多次迭加子格，但它是在扩展格中构造 FPtree，规模比原始的 FPtree 要小，而且挖掘过程比 FPgrowth 算法简单，时间消耗远小于 FPgrowth 算法 本文算法不仅时间效率明显优于 FPgrowth 算法，而且空间效率也明显优于 FPgrowth 算法因为，LFPgrowth 算法构建的是基于扩展格的 FP 树，其规模远远小于在整体事务数据库上构建的 FP 树，而且由以上运行时
11、间效率实验和分析已表明，LFPgrowth 可以在更小的支持度阀度水平上运行，而 FPgrowth 算法常因耗尽物理内存而无法运行 4 结论 提出了一种基于格的快速频繁项集挖掘算法 LFPgrowth 这种算法不仅减少了对内存的需求，也较大地提高了挖掘效率，尤其适合挖掘大型数据库的频繁项集本文的实验结果很好地证明了这一点 今后的工作在于进一步的研究如何精简事务数据链表组的结构，进一步提高现有算法的效率，减少对内存的需求同时考虑可将本文格迭加分解的策略和已有的各种分布式频繁模式挖掘算法结合起来，设计新的基于分布式数据库的频繁模式挖掘算法 6参考文献 1HAN J， PEI J， YIN Y Mi
12、ning frequent patterns without candidate generationC/Proceedings of the ACM SIGMOD International Conference on Management of Data New York： ACM Press， 2000：1-12 2KOH J L， TU Y L A treebased approach for efficiently mining approximate frequent itemsetsC/Proceedings of the Fourth International Confere
13、nce on Research Challenges in Information Science （RCIS） Nice， France： 2010： 1349-1357 3李也白，唐辉，张淳，等基于改进的 FPtree 的频繁模式挖掘算法J计算机应用， 2011， 31（1）：101-103. LI Yebai， TANG Hui， ZHANG Chun，et al Frequent pattern mining algorithm based on improved FPtreeJ Journal of Computer Applications， 2011， 31（1）：101-103
14、. （In Chinese） 4NGUYEN T T An improved algorithm for frequent patterns mining problemC/Proceedings of the International Symposium on Computer Communication Control and AtomationTainan，2010：503-507. 5郭宇红， 童云海， 唐世渭基于 FPTree 的反向频繁项集挖掘J软件学报， 2008，19（2）：338-350 GUO Yuhong， TONG Yunhai， TANG Shiwei Invers
15、e frequent itemset mining based on FPtreeJJournal of Software， 72008，19（2）：338-350 （In Chinese） 6ZENG B， JIANG X L， ZHAO W The improvement of weighted association rules arithmetic based on FPtreeC/Proceedings of the 3rd International Conference on Advanced Computer Theory and Engineering Chengdu，201
16、0：549-552. 7JALAN S， SRIVASTAVA A， SHARMA G KA nonrecursive approach for FPtree based frequent pattern generationC/2009 IEEE Student Conference on Research and Development （SCOReD） UPM Serdang，2009：160-163. 8ADNAN M， ALHAJJ R A bounded and adaptive memorybased approach to mine frequent patterns from
17、 very large databasesJ IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2011，41（1）： 154-172. 9赵强利，蒋艳凰，徐明 基于 FPTree 的快速选择性集成算法J 软件学报，2011，22（4）：709-720. ZHAO Qiangli， JIANG Yanhuang， XU Ming Fast ensemble pruning algorithm based on FPtreeJ Journal of Software，2011，22（4）：709-72
18、0（In Chinese） 10范明，李川在 FP 树中挖掘频繁模式而不生成条件 FP 树J计算机研究与发展，2003，40（8）： 1216-1222 FAN Ming， LI ChuanMining frequent patterns in an FPtree without conditional FPtree generationJJournal of Computer 8Research and Development， 2003， 40（8）： 1216-1222 （In Chinese） 11谭军，卜英勇，杨勃一种单遍扫描频繁模式树结构J计算机工程，2010，36（14）：32-33. TAN Jun，BU Yingyong，YANG Bo Singlepass frequent pattern tree structureJComputer Engineering， 2010， 36（14）： 32-33（In Chinese） 12郭耀煌，刘家诚，刘常青， 等 格序决策M 上海：上海科学技术出版社， 2003.
