Affiliations: Knowledge and Data Engineering Laboratory of Chinese Medicine, School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan, China
Correspondence:
[*]
Corresponding author: Yongguo Liu, Knowledge and Data Engineering Laboratory of Chinese Medicine, School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan 610054, China. E-mail: liuyg_cn@163.com.
Abstract: The identification of frequent patterns plays a key role in mining association rules. FP-growth is a fundamental algorithm for frequent pattern mining. It employs a prefix tree structure (FP-Tree) and a recursive mining process to discover frequent patterns. However, the performance of FP-growth is closely related to the total number of recursive calls, which leads to poor performance when multiple conditional FP-trees are required to be constructed. This paper proposes highly compressed FP-tree (HCFP-tree). This increases prefix sharing and reduces the number of nodes in the prefix tree. Based on HCFP-tree, we design a new algorithm called HCFP-growth. This algorithm greatly reduces the number of recursive calls required to mine full frequent patterns. Experiments conducted on various types of datasets demonstrate that HCFP-growth is always among the fastest algorithms. It also consumes the least memory in many cases, and its memory consumption is comparable to that of existing algorithms in other cases.
Keywords: Data mining, association rule, frequent pattern mining
