一种基于频繁模式树的最大频繁项目集挖掘算法  

Algorithm Based on FP-tree for Mining Frequent Closed Itemsets

作　　者：任永功[1] 张亮[1] 付玉[1] 

机构地区：[1]辽宁师范大学计算机与信息技术学院,辽宁大连116029

出　　处：《小型微型计算机系统》2010年第2期317-321,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60603047)资助;辽宁省科技计划项目(2008216014)资助;大连市优秀青年科技人才基金项目(2008J23JH026)资助;教育部留学回国人员科研启动基金资助项目

摘　　要：目前提出的频繁项目集挖掘算法大多基于Apriori算法思想,这类算法会产生巨大的候选集并且重复扫描数据库.针对这一问题,给出一种基于频繁模式树的最大频繁项目集挖掘算法FP-MFIA,该算法利用频繁模式树对最大频繁项目集进行检索,通过位图建树的方法有效的减少了扫描数据库的次数,从而节省了CPU的执行时间.另外,此算法运用独特的最大频繁项目集判断策略,同时运用投影技术进行超集检测,提高了遍历的效率,实验结果表明该算法是快速有效的.Most mining algorithms of frequent Itemsets are based on Apriori. However,these algorithms make huge candidate itemsets and scan large database repeatedly. In order to solve this problem,in this paper a new depth-first search algorithm called FP-MFIA based on FP-tree（frequent pattern tree） for mining maximal frequent Itemsets is proposed. This algorithm makes use of bitmap to cut down the frequency of scanning the database,which saves executing time. In addition,FP-MFIA adopts efficient strategies to distinguish maximal frequent itemsets and a new superset checking method based on projection of the maximal frequent itemsets,which can reduce the cost of accessing the tree. The experiments show that FP-MFIA is more efficient and fast.

关 键 词：频繁项目集 最大频繁项目集 频繁模式树 深度优先搜索 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]