一种基于事务树的快速频繁项集挖掘与更新算法  

A Fast Algorithm Based on Trans-Tree for Mining and Updating Frequent Itemsets

作　　者：阮幼林[1] 李庆华[1] 杨世达[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机科学》2005年第2期210-212,共3页Computer Science

基　　金：国家自然科学基金(60273075)

摘　　要：挖掘频繁项集是数据挖掘研究中的关键问题。基于FP-Tree的挖掘及其更新算法无需生成候选项目集因而效率明显高于Apriori类算法,但FP-Tree结构存在动态维护复杂、必须两次扫描数据库等缺点。因此,本文提出一种基于事务树Trans-Tree的新算法。该算法通过引入一种新结构—事务树Trans-Tree来压缩存放数据的相关信息且易于更新,挖掘算法只需对数据库扫描一次,而且更新算法只需对新增数据扫描一次,无需扫描原始数据,从而大大提高了频繁项集的挖掘和维护效率。Mining frequent patterns is a key problem in data mining research. Although mining based on FP-Tree achieves better performance and efficiency than Apriori-like algorithms because of avoiding costly candidate genera- tion,it still have problems such as update of FP-Tree and require two scans of the database. Therefore,this paper proposes a new method that designs a new structure called Trans-Tree,which stores all of the information in a highly compact form and updates easily. Thus,mining requires only one scan of the database and updating Trans-Tree needs one scan of the new data only without scanning the existing data.

关 键 词：事务 频繁项集 新算法 扫描 挖掘算法 数据库 数据挖掘 更新 选项 动态维护 

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