基于改进FP-树的最大模式挖掘算法  

Mining Maximal Frequent Patterns Based on Improved FP-tree

作　　者：孟祥萍[1] 王华金[2] 王贤勇[2] 任纪川[2] 鞠传香[2] 

机构地区：[1]长春工程学院电气工程系,长春130012 [2]东北电力学院信息工程系,吉林132012

出　　处：《计算机工程与应用》2005年第14期179-181,228,共4页Computer Engineering and Applications

基　　金：吉林省教育厅科研基金资助项目(编号:0230)

摘　　要：频繁模式挖掘是数据挖掘领域中的一个非常重要的分支,但是由于其内在的计算复杂性,挖掘密集型数据的频繁模式完全集非常困难而且数量往往大得惊人,难以理解和应用。最大频繁模式(最大模式)压缩隐含了所有的频繁模式,存储所占用的空间远远小于完全集,因而最大模式挖掘具有十分重要的意义。该文改进了传统的FP-树结构并提出了一种有效的基于改进FP-树的最大模式挖掘算法IFP-M ax;通过引入后缀子树的概念,算法在挖掘过程中不用生成最大频繁模式候选集,从而大大提高了算法的时间效率和空间可伸缩性。实验表明,IFP-M ax的挖掘速度比M AFIA和GenM ax大约快一个数量级。Mining frequent patterns is an important part of data mining,however,because of the inherent complexity,mining complete set of frequent patterns from dense database could be impractical,and its quantity is usually very large,it is hard to understand and make use of them.Maximal frequent patterns contain and compress all frequent patterns,and its memory for saving is much smaller than that of complete patterns,thus it is greatly valuable to mine maximal frequent patterns.In this paper,the structure of a traditional FP-tree is improved and an efficient algorithm for mining maximal frequent patterns based on improved FP-tree,called IFP-Max,is proposed;By introducing the concept of postfix sub-tree,this algorithm needn't generate the candidate of maximal frequent patterns in mining process,therefore greatly improves the mining efficiency in time and space scalability.Experimental results show that IFP-Max is about an order of magnitude faster than MAFIA and GenMax.

关 键 词：数据挖掘 关联规则 最大频繁模式 改进FP-树 

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