A new algorithm for fast mining frequent itemsets using N-lists

查看全文 作　　者：DENG [1]ZhiHong;WANG [1]ZhongHui;JIANG [1]JiaJian

机构地区：[1]Key Laboratory of Machine Perception(Ministry of Education),School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China

出　　处：《Science China(Information Sciences)》索引2012年第55卷第9期,共23页

基　　金：supported by National Natural Science Foundation of China (Grant No. 61170091);National High Technology Research and Development Program of China (863 Program) (Grant No. 2009AA-01Z136) 摘　　要：Mining frequent itemsets has emerged as a fundamental problem in data mining and plays an essential role in many important data mining tasks.In this paper,we propose a novel vertical data representation called N-list,which originates from an FP-tree-like coding prefix tree called PPC-tree that stores crucial information about frequent itemsets.Based on the N-list data structure,we develop an efficient mining algorithm,PrePost,for mining all frequent itemsets.Efficiency of PrePost is achieved by the following three reasons.First,N-list is compact since transactions with common prefixes share the same nodes of the PPC-tree.Second,the counting of itemsets' supports is transformed into the intersection of N-lists and the complexity of intersecting two N-lists can be reduced to O(m + n) by an efficient strategy,where m and n are the cardinalities of the two N-lists respectively.Third,PrePost can directly find frequent itemsets without generating candidate itemsets in some cases by making use of the single path property of N-list.We have experimentally evaluated PrePost against four state-of-the-art algorithms for mining frequent itemsets on a variety of real and synthetic datasets.The experimental results show that the PrePost algorithm is the fastest in most cases.Even though the algorithm consumes more memory when the datasets are sparse,it is still the fastest one. 关键词：频繁项集数据挖掘挖掘算法实验评价候选项目集数据表示 FP-树数据结构

相关文献

参考文献（31）
引证文献（25）
耦合文献（0）

参考文献(31)

引证文献(25)

互联网出版许可证新出网证(渝)字10号全国400电话 - 免长途话费

A new algorithm for fast mining frequent itemsets using N-lists

参考文献(31)

引证文献(25)

用户提示