一种基于前缀广义表的关联规则增量式更新算法  

An Incremental Updating Algorithm Based on Prefix General List for Association Rules

作　　者：杨明[1] 孙志挥[1] 

机构地区：[1]东南大学计算机科学与工程系,南京210096

出　　处：《计算机学报》2003年第10期1318-1325,共8页Chinese Journal of Computers

基　　金：国家自然科学基金 ( 79970 0 92 )资助

摘　　要：关联规则挖掘是数据挖掘研究的一个重要方面 ,关联规则的高效维护算法研究是当前研究的热点 .传统更新算法与Apriori算法框架一致 ,要多遍扫描数据库并产生大量的候选项目集 .为此 ,该文对FP tree进行了改进 ,引入了前缀广义表———PG List,并提出了基于PG List的关联规则挖掘 (MARBPGL)与增量式更新算法(IUABPGL) .算法MARBPGL仅须扫描数据库两遍 ,算法IUABPGL在最坏的情况下仅须扫描原数据库一遍 ,扫描新增数据库两遍 ,且两个算法均无须生成候选项目集 ,避免了产生“知识的组合爆炸” ,提高了挖掘和维护的效率 .理论分析和实验结果表明该文提出的算法是有效可行的 .Finding association rules is a major aspect of data mining research. Efficient maintenance of discovered association rules is the key problem. Conventional maintenance algorithms employ same framework as Apriori. However, candidate set generation is still costly, and the algorithms need repeatedly scan the database, especially when there exist prolific patterns and /or long patterns. In this paper, we improve the structure of FP-tree and propose prefix general List——PG-List, and introduce mining and incremental updating algorithms of association rules based on PG-List——MARBPGL and IUABPGL. MARBPGL only scans transaction database twice; in worse case, IUABPGL only scans original transaction database once, scans incremental transaction database twice; both MARBPGL and IUABPGL need not generate candidate itemsets. Therefore, the two algorithms proposed avoid producing combinatorial explosion problem of knowledge and improve efficiently mining and maintenance of association rules. Theory analysis and experimental results show the feasibility and effectiveness of the two algorithms.

关 键 词：关联规则 增量式更新算法 前缀广义表 数据挖掘 频繁模式树 数据库 APRIORI算法 

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