一种基于FP-tree的频繁项集增量更新算法  

Efficient algorithm for incremental updating of frequent itemsets based on FP-tree

作　　者：廖仁全[1] 王利华[2] 邱江涛[3] 

机构地区：[1]西南财经大学教务处,成都610074 [2]攀枝花学院电气信息与工程学院,四川攀枝花617000 [3]四川大学计算机学院,成都610064

出　　处：《计算机工程与应用》2007年第4期176-178,233,共4页Computer Engineering and Applications

摘　　要：针对频繁项集增量更新的问题,提出算法FIU。该算法将保存了数据库事务的FP-tree存储在磁盘上,当挖掘新支持度阈值的频繁项集时,只需从磁盘上读入FP-tree,再挖掘新支持度阈值下的频繁项集。当新增数据库事务记录后,首先建立新项目表,然后根据新项目表建立新增事务记录的FP-tree,读入存储在磁盘上的FP-tree,抽取出所有的事务记录,再插入到新FP-tree中,从而得到增量更新后的FP-tree。最后在增量更新后的FP-tree上挖掘频繁项集。实验证明,FIU算法执行时间不随数据库大小变化,与其他算法相比有较好的性能。Incremental updating of frequent itemsets in a database includes three problems.An algorithm FIU is proposed for the three problems.Firstly,FP-tree which save transaction recorders of database is materialized on disk.Secondly,when frequent itemsets need be found with new support threshold,only work is to read FP-tree to memory from disk,then travel the tree to find itemsets under new support threshold.Thirdly,when new data insert into database,a new item table of database need be build, then a new FP-tree is built based on the new item table.All transaction records,which were saved in FP-tree on disk,are acquired,then insert into the new FP-tree.Finally,updated frequent itemsets may be found in the FP-tree.

关 键 词：数据挖掘 关联规则 频繁项集 增量更新 

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