一种基于FP树的挖掘关联规则的增量更新算法  

A FP-Tree Based Incremental Updating Algorithm for Mining Association Rules

作　　者：易彤[1] 徐宝文[1] 吴方君[1] 

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

出　　处：《计算机学报》2004年第5期703-710,共8页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(G1999032701);高等学校博士学科点专项科研基金(20020286004);教育部跨世纪优秀人才培养计划基金;江苏省计算机信息处理技术重点实验室开放基金资助

摘　　要：挖掘关联规则是数据挖掘领域的一个重要研究方向 .人们已经提出了许多用于高效地发现大规模数据库中关联规则的算法 ,但对关联规则维护问题的研究却比较少 .该文在FP树的基础上 ,引入支持度函数的概念 ,对FP树进行改造 ,提出了一种关于挖掘关联规则的增量更新算法IFP growth .该算法既考虑了数据集中数据的增加 ,同时又考虑了数据集中数据的减少等情况下关联规则的维护问题 ,并且还可以把增量更新的 5种情形简化为 3种情形 .使用本算法来挖掘关联规则可以避免生成大量的候选项目集 ,而且非常高效 .Association rules mining is an important research topic in data mining area, which has been successfully applied to commercial domains. For this reason, many approaches have been proposed to mine association rules, but little work was done on their maintenance. This paper puts forward an incremental updating algorithm on the basis of FP-tree. Firstly the concept of support function is introduced. Then an incremental updating model is presented, which contains the construction of IFP-tree and IFP-tree growth algorithm. The model considers not only adding new data into the database but also reducing old data from the database. Furthermore, it can predigest five cases to three cases. Finally, some nontrivial experiments have been conducted. The results show that IFP-growth algorithm is powerful and efficient, suitable for mining association rules, as well as for some other purposes. Additionally, a small example is presented to illustrate how to define the support function Z and how to develop IFP-tree.

关 键 词：FP树 挖掘关联规则 增量更新算法 IFP—growth 数据挖掘 置信度 支持度 

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