Efficient Incremental Maintenance of Frequent Patterns with FP-Tree  

作　　者：Xiu-LiMa Yun-HaiTong Shi-WeiTang Dong-QingYang 

机构地区：[1]SchoolofElectronicsEngineeringandComputerScience,PekingUniversity,Beijing100871,P.R.China [2]NationalLaboratoryonMachinePerception,PekingUniversity,Beijing100871,P.R.China

出　　处：《Journal of Computer Science & Technology》2004年第6期876-884,共9页计算机科学技术学报（英文版）

基　　金：国家重点基础研究发展计划(973计划)

摘　　要：Mining frequent patterns has been studied popularly in data mining area. However, little work has been done on mining patterns when the database has an influx of fresh data constantly. In these dynamic scenarios, efficient maintenance of the discovered patterns is crucial. Most existing methods need to scan the entire database repeatedly, which is an obvious disadvantage. In this paper, an efficient incremental mining algorithm, Incremental-Mining (IM), is proposed for maintenance of the frequent patterns when incremental data come. Based on the frequent pattern tree (FP-tree) structure, IM gives a way to make the most of the things from the previous mining process, and requires scanning the original data once at most. Furthermore, IM can identify directly the differential set of frequent patterns, which may be more informative to users. Moreover, IM can deal with changing thresholds as well as changing data, thus provide a full maintenance scheme. IM has been implemented and the performance study shows it outperforms three other incremental algorithms: FUP, DB-tree and re-running frequent pattern growth (FP-growth). Keywords data mining - association rule mining - frequent pattern mining - incremental mining Supported by the National Basic Research 973 Program of China under Grant No.G1999032705.Xiu-Li Ma received the Ph.D. degree in computer science from Peking University in 2003. She is currently a postdoctoral researcher at National Lab on Machine Perception of Peking University. Her main research interests include data warehousing, data mining, intelligent online analysis, and sensor network.Yun-Hai Tong received the Ph.D. degree in computer software from Peking University in 2002. He is currently an assistant professor at School of Electronics Engineering and Computer Science of Peking University. His research interests include data warehousing, online analysis processing and data mining.Shi-Wei Tang received the B.S. degree in mathematics from Peking University in 1964. Now, he is a professor and Ph.D. suMining frequent patterns has been studied popularly in data mining area. However, little work has been done on mining patterns when the database has an influx of fresh data constantly. In these dynamic scenarios, efficient maintenance of the discovered patterns is crucial. Most existing methods need to scan the entire database repeatedly, which is an obvious disadvantage. In this paper, an efficient incremental mining algorithm, Incremental-Mining (IM), is proposed for maintenance of the frequent patterns when incremental data come. Based on the frequent pattern tree (FP-tree) structure, IM gives a way to make the most of the things from the previous mining process, and requires scanning the original data once at most. Furthermore, IM can identify directly the differential set of frequent patterns, which may be more informative to users. Moreover, IM can deal with changing thresholds as well as changing data, thus provide a full maintenance scheme. IM has been implemented and the performance study shows it outperforms three other incremental algorithms: FUP, DB-tree and re-running frequent pattern growth (FP-growth). Keywords data mining - association rule mining - frequent pattern mining - incremental mining Supported by the National Basic Research 973 Program of China under Grant No.G1999032705.Xiu-Li Ma received the Ph.D. degree in computer science from Peking University in 2003. She is currently a postdoctoral researcher at National Lab on Machine Perception of Peking University. Her main research interests include data warehousing, data mining, intelligent online analysis, and sensor network.Yun-Hai Tong received the Ph.D. degree in computer software from Peking University in 2002. He is currently an assistant professor at School of Electronics Engineering and Computer Science of Peking University. His research interests include data warehousing, online analysis processing and data mining.Shi-Wei Tang received the B.S. degree in mathematics from Peking University in 1964. Now, he is a professor and Ph.D. su

关 键 词：data mining association rule mining frequent pattern mining incremental mining 

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