挖掘最大频繁模式的新方法  

A New Algorithm for Mining Maximal Frequent Patterns

作　　者：刘君强[1] 孙晓莹[1] 王勋[1] 潘云鹤[2] 

机构地区：[1]浙江工商大学计算机信息工程学院,杭州310035 [2]浙江大学计算机科学与技术学院,杭州310027

出　　处：《计算机学报》2004年第10期1328-1334,共7页Chinese Journal of Computers

基　　金：浙江省自然科学基金 (60 2 14 0 );国家"八六三"高技术研究发展计划项目基金 (2 0 0 2AA12 10 64 );浙江省教育厅科技计划基金 (2 0 0 2 0 63 5 )资助

摘　　要：由于其内在的计算复杂性 ,挖掘密集型数据集的频繁模式完全集非常困难 ,解决方案之一是挖掘最大频繁模式集 .该文在频繁模式完全集挖掘算法OpportuneProject基础上 ,提出了挖掘最大频繁模式的新算法MOP .它采用宽度与深度优先相结合的混合搜索策略 ,能恰当地选择不同的支持集表示和投影方法 ,将闭合性剪裁和一般性剪裁相结合 ,并适时前窥 ,实现搜索与剪裁效率最优化 .实验表明 ,MOP效率是MaxMiner的 2～ 8倍 ,比MAFIA高 2个数量级以上 .Because of the inherent computational complexity, mining the complete set of frequent patterns remains to be a difficult task. Mining maximal frequent patterns is an alternative to address the problem. In this paper, a new algorithm, MOP, for mining maximal frequent patterns is proposed based on the Opportune Project algorithm proposed by the author in the previous study. MOP employs a breadth first and depth first combined hybrid search strategy to discover the frequent patterns, chooses different representations and projecting methods for transaction subsets in accordance with the features of the subsets, and integrates pruning methods based on closure checking and general subsumption checking. MOP also looks ahead opportunistically to discover maximal frequent patterns as early as possible. Both the search and pruning efficiency of MOP are maximized. Comparative experiments on real world and artificial datasets show that MOP outperforms MaxMiner by a factor of two to eight, and is more than two orders of magnitude efficient than MAFIA.

关 键 词：知识发现 数据挖掘 最大频繁模式 关联规则 混合搜索策略 完全集挖掘算法 MOP 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]