Improved canonical-order tree algorithm based on restructure

doi:10.11772/j.issn.1001-9081.2018061328

Abstract

Abstract: In order to solve the problems such as too many nodes and low compressibility in the tree structure constructed by CANonical-order tree (CAN-tree) algorithm, an improved CAN-tree algorithm based on restructure was proposed. Firstly, a tree structure was constructed directly with canonical-order, which scans the database only once in the frequent itemset mining algorithm. Then, in order to get a tree structure with high compressibility, a pruning operation was used with support in desending order to restructure the tree. Finally, frequent itemsets were mined out for the reconstructed tree structure. The experimental results show that compared with original CAN-tree algorithm, the number of nodes constructed by the improved CAN-tree algorithm is reduced to less than 20%,and the execution efficiency is improved by 4 to 6 times. The proposed algorithm shortens the execution time of the frequent itemset mining algorithm and effectively compresses the tree structure in it.

Key words: frequent itemset, frequent itemset header table, restructure, pruning, minimum support

摘要： 针对自然排序树（CAN-tree）算法构建的树结构节点个数过多、压缩性不高等问题，提出一种基于重构的改进CAN-tree算法。首先，使用自然排序法直接构建树结构，将频繁项集挖掘算法实现中数据库扫描次数减少至1；然后，对构建的树结构以支持度降序方式结合剪枝操作实现树结构的重构，得到高压缩性的树结构；最后，对重构的树结构进行频繁项集挖掘。实验结果表明，基于重构的改进CAN-tree算法所构建的树结构节点个数减少至原来的20%以下，执行效率提高了4至6倍，在频繁项集挖掘中有效地压缩了树结构，缩短了算法的执行时间。

关键词: 频繁项集, 频繁项集头表, 重构, 剪枝, 最小支持度

CLC Number:

TP301.6

DU Yuan, ZHANG Shiwei. Improved canonical-order tree algorithm based on restructure[J]. Journal of Computer Applications, 2019, 39(2): 441-445.

杜媛, 张世伟. 基于重构的改进自然排序树算法[J]. 计算机应用, 2019, 39(2): 441-445.

References

[1] AGRAWL R, IMIELINSKI T, SWAMI A. Mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. New York:ACM, 1993:207-216.
[2] HAN J, PEI J, YIN Y. Mining frequent patterns without candidate generation[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York:ACM 2000:1-12.
[3] DING Z, WEI Q, DING X. An improved FP-growth algorithm based on Compound single linked list[C]//Proceedings of the 2009 Second International Conference on Information and Computing Science. Washington, DC:IEEE Computer Society, 2009, 1:351-353.
[4] HAO J, XU H. An improved algorithm for frequency itemsets mining[C]//Proceedings of the 2017 Fifth International Conference on Advanced Cloud and Big Data. Washington, DC:IEEE Computer Society, 2017:314-317.
[5] 李也白,唐辉,张淳,等. 基于改进的FP-tree的频繁模式挖掘算法[J]. 计算机应用,2011,31(1):101-103.(LI Y B, TANG H, ZHANG C, el al. Frequent pattern mining algorithm based on improve FP-tree[J]. Journal of Computer Applications, 2011, 31(1):101-103.)
[6] 李校林,杜托,刘彪.基于B-list的快速频繁模式挖掘算法[J].计算机应用,2017,37(8):2357-2361,2367. (LI X L,DU T,LIU B. Fast algorithm for mining frequent patterns based on B-list[J]. Journal of Computer Applications, 2017, 37(8):2357-2361, 2367.)
[7] 马丽生,姚光顺,杨传健.基于改进的FP-tree最大频繁项目集挖掘算法[J].计算机应用,2012,32(2):326-329.(MA L S, YAO G S, YANG C J. Mining algorithm for maximal frequent itemsets based on improved FP-tree[J]. Journal of Computer Applications, 2012, 32(2):326-329.)
[8] 宁慧,王素红,催立刚,等. 基于改进的FP-tree最大频繁模式挖掘算法[J]. 应用科技,2016,43(2):37-43.(NING H, WANG S H, CUI L G, et al. An algorithm for mining maximal frequent patterns based on improved FP-tree[J]. Applied Science and Technology,2016,43(2):37-43.)
[9] 赵阳,吴廖丹. 一种自底向上的最大频繁项集挖掘方法[J]. 计算机技术与发展,2017,27(8):57-60.(ZHAO Y,WU L D. A bottom-up method for mining maximum frequent itemsets[J]. Computer Technology and Development, 2017, 27(8):57-60.)
[10] LI H, WANG Y, ZHAN D, el al. PFP:parallel FP-growth for query recommendation[C]//Proceedings of the 2008 ACM Conference on Recommender Systems. New York:ACM, 2008:107-114.
[11] WEI X, MA Y, ZHANG F, el al. Incremental FP-Growth mining strategy for dynamic threshold value and database based on MapReduce[C]//Proceedings of the 2014 IEEE 18th International Conference on Computer Supported Cooperative Wori in Design. Piscataway, NJ:IEEE, 2014:271-276.
[12] LEUNG C K-S, KHAN Q I, HOQUE T. CANTree:a tree structure for efficient incremental mining of frequent patterns[C]//Proceedings of the Fifth IEEE International Conference on Data Mining. Washington, DC:IEEE Computer Society, 2005:274-281.
[13] 邹力鹍,张其善. 基于CAN-树的高效关联规则增量挖掘算法[J]. 计算机工程,2008,34(3):29-31.(ZOU L K, ZHANG Q S. Efficient incremental association rules mining algorithm based on CAN-tree[J]. Computer Engineering, 2008, 34(3):29-31.)
[14] 陈刚,闫英战,刘秉权. 一种基于CAN-tree快速构建算法[J]. 微电子学与计算机,2014,31(1):76-82.(CHEN G, YAN Y Z, LIU B Q. A fast construction algorithm based on CAN-tree[J]. Microelectronics & Computer, 2014, 32(1):76-82.)
[15] TAN P M, STEINBACH M, KUMAR V. 数据挖掘导论(完整版)[M]. 范明,等译. 北京:人民邮电出版社,2017:225-228.(TAN P M, STEINBACH M, KUMAR V. Writing Introduction to Data Mining[M]. FAN M, translated. Beijing:Post & Telecom Press, 2017:225-228.)