一种基于频繁模式树的约束最大频繁项目集挖掘及其更新算法  

An Algorithm and Its Updating Algorithm Based on Frequent Pattern Tree for Mining Constrained Maximum Frequent Itemsets

作　　者：宋余庆[1] 朱玉全[2] 孙志挥[1] 杨鹤标[2] 

机构地区：[1]东南大学计算机科学与工程系,南京210096 [2]江苏大学计算机科学与通信工程学院,镇江212013

出　　处：《计算机研究与发展》2005年第5期777-783,共7页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(70371015);教育部高等学校博士学科点专项科研基金项目(20040286009)

摘　　要：目前已提出了许多快速的关联规则挖掘算法,实际上用户只关心部分关联规则,如他们仅想知道包含指定项目的规则.当这些约束被用于数据预处理或将它结合到数据挖掘算法中去时,可以显著减少算法的执行时间.为此,考虑了一类包含或不包含某些项目的布尔表达式约束条件,提出了一种快速的基于FPtree的约束最大频繁项目集挖掘算法CMFIMA,并对其更新问题进行了研究,提出了一种增量式更新约束最大频繁项目集挖掘算法CMFIUA.The problem of discovering association rules has received considerable research attention and several fast algorithms for mining association rules have been developed In practice, users are often interested in a subset of association rules For example, they may only want rules that contain some specific items Applying such constraints as a pre-processing stepor integrating them into the mining algorithm can dramatically reduce the execution time The problem of integrating constraints, that are Boolean expressions over the presence or absence of items, into the maximum frequent itemsets discovery algorithm is considered An integrated algorithm and its updating algorithm for mining maximum frequent itemsets with item constraints are presented and their tradeoff is discussed which is based on a novel frequent pattern tree (FP-tree) structure that is an extended prefix-tree structure for storing compressed and crucial information about frequent patterns

关 键 词：关联规则 项约束 最大频繁项目集 频繁模式树 增量式更新 

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