GTK:A Hybrid-Search Algorithm of Top-Rank-k Frequent Patterns Based on Greedy Strategy  

作　　者：Yuhang Long Wensheng Tang Bo Yang Xinyu Wang Hua Ma Hang Shi Xueyu Cheng 

机构地区：[1]Hunan Provincial Key Laboratory of Intelligent Computing and Language Information Processing,Hunan Normal University,Changsha,410081,China [2]College of Information Science and Engineering,Hunan University,Changsha,410082,China [3]Clayton State University,Morrow,GA 30260,USA

出　　处：《Computers, Materials & Continua》2020年第6期1445-1469,共25页计算机、材料和连续体（英文）

基　　金：This research was supported in part by the Hunan Province’s Strategic and Emerging Industrial Projects under Grant 2018GK4035;in part by the Hunan Province’s Changsha Zhuzhou Xiangtan National Independent Innovation Demonstration Zone projects under Grant 2017XK2058;in part by the National Natural Science Foundation of China under Grant 61602171;in part by the Scientific Research Fund of Hunan Provincial Education Department under Grant 17C0960 and 18B037.

摘　　要：Currently,the top-rank-k has been widely applied to mine frequent patterns with a rank not exceeding k.In the existing algorithms,although a level-wise-search could fully mine the target patterns,it usually leads to the delay of high rank patterns generation,resulting in the slow growth of the support threshold and the mining efficiency.Aiming at this problem,a greedy-strategy-based top-rank-k frequent patterns hybrid mining algorithm(GTK)is proposed in this paper.In this algorithm,top-rank-k patterns are stored in a static doubly linked list called RSL,and the patterns are divided into short patterns and long patterns.The short patterns generated by a rank-first-search always joins the two patterns of the highest rank in RSL that have not yet been joined.On the basis of the short patterns satisfying specific conditions,the long patterns are extracted through level-wise-search.To reduce redundancy,GTK improves the generation method of subsume index and designs the new pruning strategies of candidates.This algorithm also takes the use of reasonable pruning strategies to reduce the amount of computation to improve the computational speed.Real datasets and synthetic datasets are adopted in experiments to evaluate the proposed algorithm.The experimental results show the obvious advantages in both time efficiency and space efficiency of GTK.

关 键 词：Top-rank-k frequent patterns greedy strategy hybrid-search 

分 类 号：TN9[电子电信—信息与通信工程]