基于节点表的FP-Growth算法改进
|
摘要
针对FP-Growth算法在构建FP-tree过程中需要对事务数据库扫描两次,同时在利用FP-tree挖掘频繁项集过程中产生大量条件模式基和条件模式树的问题,提出一种改进的FP-Growth算法。该算法只需扫描一次事务数据库,就能构建一棵无相同节点的新的FP-tree;弃用项头表,新增与新的FP-tree关联的节点表,将构建新的FP-tree过程中"多余"的项信息存入节点表;利用新的FP-tree和节点表挖掘频繁项集。实验结果表明了该算法的可行性和有效性,其提高了数据挖掘的效率。
Aiming at the problems that FP-Growth algorithm scans the transaction database twice for building the FP-tree and it generates a huge number of conditional pattern bases and conditional pattern trees when mining frequent itemsets,an improved FP-Growth algorithm was presented.A new FP-tree without the same node was built by only scanning the transaction database one time.In the process of building new FP-tree,the item head table was abandoned and an associated node table was added to store the redundant item information.The new FP-tree and a node table were used to mine frequent itemsets.Results of experiments show the feasibility and validity of the algorithm,and it improves the efficiency of data mining.
Aiming at the problems that FP-Growth algorithm scans the transaction database twice for building the FP-tree and it generates a huge number of conditional pattern bases and conditional pattern trees when mining frequent itemsets,an improved FP-Growth algorithm was presented.A new FP-tree without the same node was built by only scanning the transaction database one time.In the process of building new FP-tree,the item head table was abandoned and an associated node table was added to store the redundant item information.The new FP-tree and a node table were used to mine frequent itemsets.Results of experiments show the feasibility and validity of the algorithm,and it improves the efficiency of data mining.
引文
[1]LIU Shuai,YANG Yingjie,CHANG Dexian,et al.Improved fuzzy association rule and its mining algorithm[J].Computer Engineering and Design,2015,36(4):942-946(in Chinese).[刘帅,杨英杰,常德显,等.改进的模糊关联规则及其挖掘算法[J].计算机工程与设计,2015,36(4):942-946.]
[2]MI Yunlong,MI Chunqiao,LIU Wenqi.Research advance on related technology of massive data mining process[J].Journal of Frontiers of Computer Science and Technology,2015,9(6):641-659(in Chinese).[米允龙,米春桥,刘文奇.海量数据挖掘过程相关技术研究发展[J].计算机科学与探索,2015,9(6):641-659.]
[3]CHEN Xingshu,ZHANG Shuai,TONG Hao,et al.FP-Growth algorithm based on Boolean matrix and MapReduce[J].Journal of South China University of Technology(Natural Science Edition),2014,42(1):135-141(in Chinese).[陈兴蜀,张帅,童浩,等.基于布尔矩阵和MapReduce的FP-Growth算法[J].华南理工大学学报(自然科学版),2014,42(1):135-141.]
[4]SHEN Yan,ZHU Yuquan,LIU Chunhua.Incremental FP-Growth algorithm based on disk-resident 1-itemsets counting[J].Journal of Computer Research and Development,2015,52(3):569-578(in Chinese).[申彦,朱玉全,刘春华.基于磁盘存储1项集计数的增量FP-Growth算法[J].计算机研究与发展,2015,52(3):569-578.]
[5]SHI Liang,QIAN Xuezhong.Research and implementation of parallel FP-Growth algorithm based on Hadoop[J].Microelectro-nics&Computer,2015,32(4):150-154(in Chinese).[施亮,钱雪忠.基于Hadoop的并行FP-Growth算法的研究与实现[J].微电子学与计算机,2015,32(4):150-154.]
[6]Zhou Lijuan,Wang Xiang.Research of the FP-Growth algorithm based on cloud environments[J].Journal of Software,2014,9(3):676-683.
[7]ZHANG Zhigang,JI Genlin.Parallel algorithm for mining frequent item sets based on FP-Growth[J].Computer Enginee-ring and Applications,2014,50(2):103-106(in Chinese).[章志刚,吉根林.一种基于FP-Growth的频繁项目集并行挖掘算法[J].计算机工程与应用,2014,50(2):103-106.]
[8]YU Cuilan.A project FP-Growth-based algorithm for mining spatial co-location patterns[J].Science Technology and Engineering,2014,14(23):234-240(in Chinese).[余翠兰.一种基于投影FP-Growth的co-location模式挖掘算法[J].科学技术与工程,2014,14(23):234-240.]
[9]CHEN Zhiping,TAN Yihong,LI Xueyong,et al.Fast construction algorithm based on FP-tree[J].Journal of Computer Applications,2011,31(2):438-440(in Chinese).[陈治平,谭义红,李学勇,等.基于FP-tree的快速构建算法[J].计算机应用,2011,31(2):438-440.]
[10]WU Qian,LUO Jianxu.Improved search algorithm based on compressed FP-Tree[J].Computer Engineering and Design,2015,36(7):1771-1777(in Chinese).[吴倩,罗健旭.压缩FPTree的改进搜索算法[J].计算机工程与设计,2015,36(7):1771-1777.]
[11]LING Xuxiong,WANG Sheguo,LI Yang,et al.No-header-table FP-Growth algorithm[J].Journal of Computer Applications,2011,31(5):1391-1394(in Chinese).[凌绪雄,王社国,李洋,等.无项头表的FP-Growth算法[J].计算机应用,2011,31(5):1391-1394.]
[2]MI Yunlong,MI Chunqiao,LIU Wenqi.Research advance on related technology of massive data mining process[J].Journal of Frontiers of Computer Science and Technology,2015,9(6):641-659(in Chinese).[米允龙,米春桥,刘文奇.海量数据挖掘过程相关技术研究发展[J].计算机科学与探索,2015,9(6):641-659.]
[3]CHEN Xingshu,ZHANG Shuai,TONG Hao,et al.FP-Growth algorithm based on Boolean matrix and MapReduce[J].Journal of South China University of Technology(Natural Science Edition),2014,42(1):135-141(in Chinese).[陈兴蜀,张帅,童浩,等.基于布尔矩阵和MapReduce的FP-Growth算法[J].华南理工大学学报(自然科学版),2014,42(1):135-141.]
[4]SHEN Yan,ZHU Yuquan,LIU Chunhua.Incremental FP-Growth algorithm based on disk-resident 1-itemsets counting[J].Journal of Computer Research and Development,2015,52(3):569-578(in Chinese).[申彦,朱玉全,刘春华.基于磁盘存储1项集计数的增量FP-Growth算法[J].计算机研究与发展,2015,52(3):569-578.]
[5]SHI Liang,QIAN Xuezhong.Research and implementation of parallel FP-Growth algorithm based on Hadoop[J].Microelectro-nics&Computer,2015,32(4):150-154(in Chinese).[施亮,钱雪忠.基于Hadoop的并行FP-Growth算法的研究与实现[J].微电子学与计算机,2015,32(4):150-154.]
[6]Zhou Lijuan,Wang Xiang.Research of the FP-Growth algorithm based on cloud environments[J].Journal of Software,2014,9(3):676-683.
[7]ZHANG Zhigang,JI Genlin.Parallel algorithm for mining frequent item sets based on FP-Growth[J].Computer Enginee-ring and Applications,2014,50(2):103-106(in Chinese).[章志刚,吉根林.一种基于FP-Growth的频繁项目集并行挖掘算法[J].计算机工程与应用,2014,50(2):103-106.]
[8]YU Cuilan.A project FP-Growth-based algorithm for mining spatial co-location patterns[J].Science Technology and Engineering,2014,14(23):234-240(in Chinese).[余翠兰.一种基于投影FP-Growth的co-location模式挖掘算法[J].科学技术与工程,2014,14(23):234-240.]
[9]CHEN Zhiping,TAN Yihong,LI Xueyong,et al.Fast construction algorithm based on FP-tree[J].Journal of Computer Applications,2011,31(2):438-440(in Chinese).[陈治平,谭义红,李学勇,等.基于FP-tree的快速构建算法[J].计算机应用,2011,31(2):438-440.]
[10]WU Qian,LUO Jianxu.Improved search algorithm based on compressed FP-Tree[J].Computer Engineering and Design,2015,36(7):1771-1777(in Chinese).[吴倩,罗健旭.压缩FPTree的改进搜索算法[J].计算机工程与设计,2015,36(7):1771-1777.]
[11]LING Xuxiong,WANG Sheguo,LI Yang,et al.No-header-table FP-Growth algorithm[J].Journal of Computer Applications,2011,31(5):1391-1394(in Chinese).[凌绪雄,王社国,李洋,等.无项头表的FP-Growth算法[J].计算机应用,2011,31(5):1391-1394.]