An efficient frequent pattern mining algorithm using a highly compressed prefix tree

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

1. Introduction

Frequent itemset or frequent pattern (FI) mining is employed in data mining and knowledge discovery tasks such as spanning classification [1], clustering [2], decision support and regular pattern mining [3]. It has also been applied to many different types real-world databases containing medical clinical data [4], web data [5], customer data [6], library records [7], and so forth.

Apriori [8] and FP-growth [9] are two fundamental algorithms for mining FIs. Apriori requires multiple database scans and consumes substantial memory. In contrast, FP-growth uses a prefix tree structure based on a pattern growth approach that avoids candidate generation and significantly improves performance. Therefore, FP-growth is more commonly applied to mining tasks.

Many extended algorithms based on FP-growth have been proposed to accomplish various mining tasks. FI-mining algorithms also exist for uncertain data, such as Tube-trees [10] and UF-streaming+ [11]. The following techniques are based on mining weighted frequent patterns. WIP [12] and IWS [13] are algorithms that mine weighted interesting patterns, and IWI Miner [14] is applied in mining infrequent weighted patterns. Because it is challenging for a data analyst to specify the appropriate minimum support, a top-k mining approach has been proposed that efficiently retrieves a set of top-k frequent patterns without requiring a minimum support parameter; these algorithms include FCPminer [15] and BTK [16]. Because each item is different and should not be treated identically among transaction datasets, FPME [17] was proposed to mine FI in these transaction datasets. These algorithms all rely on the tree structure of the FP-growth algorithm. Therefore, reducing the complexity of the FP-growth algorithm would greatly improve the efficiency of these algorithms.

The FP-tree in FP-growth consists of a prefix tree and a header table. As a result, FP-growth scans the database only twice. The first scan identifies all the frequent items and counts their support. Then, during the second scan, the algorithm inserts the frequent transaction items identified into the FP-tree.

Table 1
A transaction dataset

Tid	Items	Tid	Items	Tid	Items
1	a b c d	6	b	11	a
2	b d	7	a d	12	b c d
3	a c d	8	a b c	13	a b
4	c	9	c d	14	a b d
5	b c	10	d	15	a c

Example 1. Let the minimum support threshold be 2. Figure 1 illustrates the FP-tree for the transaction dataset in Table 1. As shown in Fig. 1, there are 15 nodes in the FP-tree.

Figure 1.

FP-tree for the dataset in Table 1.

After constructing the FP-tree, FP-growth constructs a conditional pattern base and a conditional FP-tree for each item in the header table. This procedure is then applied recursively to each conditional FP-tree until the conditional FP-tree contains only one path. Subsequently, the FIs are obtained after forming all the possible combinations of the nodes in the single paths.

It is easy to see that the major cost of FP-growth is constructing the conditional FP-trees. Therefore, FP-growth efficiency is determined by the total number of recursions [18]. A smaller number of recursive calls means that the mining process will finish early and involve constructing fewer conditional trees. However, the number of recursive calls is determined by prefix sharing among patterns and the number of nodes in the tree. When there is more prefix sharing and fewer nodes in the tree, the tree is more likely to have a single path.

In this paper, we propose a novel compact tree structure named the highly compressed FP-tree (HCFP-tree) to increase prefix sharing. The implementation of HCFP-growth that utilizes HCFP-tree for frequent pattern mining has the following advantages: (1) HCFP-growth is faster than the existing algorithms because it effectively reduces the number of recursive calls and generates fewer conditional trees. (2) HCFP-growth uses relatively less memory because the number of nodes in the HCFP-tree is much smaller than that in FP-tree. (3) By reusing the HeaderTable, the number of nodes in HCFP-tree could be further reduced.

The remainder of this paper is organized as follows. Section 2 reviews the related work with respect to HCFP-tree and HCFP-growth. Section 3 employs examples to demonstrate the HCFP-growth algorithm. The experimental results are presented in Section 4. Finally, conclusions are drawn in Section 5.

2. Related work

Many algorithms have been proposed to improve the mining speed of the FP-growth algorithm such as DiffNodesets [19], IFP-growth [20], LP-growth [21], FP-growth+ [22], FDM [23], PrePost+ [24], NSFI [25], and CT-PRO [26].

IFP-growth utilizes a new tree structure named FP-tree+ that adds an address table and does not eliminate the infrequent nodes. Therefore, IFP-growth may increase the cost of tree traversal despite reducing the number of conditional FP-trees in sparse datasets. LP-growth applies a linear structure called Liner Prefix Node that speeds up tree traversal by reducing the number of pointers between nodes. However, LP-growth can perform poorly when the average number of child nodes exceeds 3. FP-growth+ mines frequent patterns by recursively traversing the global FP-tree; therefore, its mining efficiency is low when the global FP-tree has a large number of nodes. FDM switches between the FP-tree and DIFFset-list mining techniques according to the conditional pattern base.

Although the above algorithms can improve the mining speed, they do not efficiently decrease the total number of recursive calls and the number of nodes in the prefix-tree.

Other nonrecursive algorithms, such as CT-PRO, BISC [18], nonordfp [27], NSFI and PrePost ${}^{+}$ , avoid constructing the conditional FP-trees recursively. However, these algorithms lose the advantage of being able to prune branches during tree construction. Because nonordfp does not restore frequent items, it did not have high levels of prefix sharing. NSFI and PrePost ${}^{+}$ generate the N-lists when constructing the PPC-tree (which is similar to an FP-tree), and they recursively execute N-list intersection when producing all the frequent itemsets. Therefore, they require relatively more memory and perform poorly on sparse datasets with many items but few sharing prefixes.

In CT-PRO, the authors suggested a compressed FP-tree named CFP-tree. Each node of a CFP-tree has a count array in which each array entry registers the count of transactions matched with the item subset in the path from the root of subtree to that node. Therefore, a CFP-tree maintains more prefix sharing than does an FP-tree. A CFP-tree is formed by the leftmost branch of an FP-tree and has fewer nodes than an FP-tree.

Figure 2.

CFP-tree for the dataset shown in Table 1.

Example 2. In Fig. 1, a cut (a virtual line in the lattice) has been drawn to separate the nodes. All the branches on the left side of cut form the CFP-tree, as shown in Fig. 2. In this example, there are 7 nodes in the CFP-tree – 8 fewer than the number of nodes in the FP-tree.

The CT-PRO algorithm applies a CFP-tree to mine FIs without recursive calls; however, it requires large amounts of memory. Meanwhile, to mine longer FIs, CT-PRO requires a procedure called RecMine. When the paths contain many infrequent items, the cost of RecMine may cause CT-PROs performance to be poorer than that of FP-growth. Thus, it is necessary to improve the performance of CT-PRO.

As shown in Fig. 2, we found a cut in the CFP-tree. The branches on the right-hand side of the cut can be compressed further, while those on the left-hand side can form a new compressed tree-based data structure, which we refer to as HCFP-tree. The HCFP-tree structure and the HCFP-growth algorithm, which applies HCFP-trees to frequent patterns mining, are described in the next section.

3. Frequent pattern mining using compressed prefix tree

Our FI mining method involves two main steps. First, HCFP-growth constructs an HCFP-tree by scanning the dataset. Then, it extracts FIs by recursively traversing the HCFP-tree and constructing conditional HCFP-trees. This section first defines several key FI-mining terms before introducing HCFP-tree and describing the HCFP-growth algorithm in detail.

3.1 HCFP-tree: A highly compressed FP-tree structure

Let $I={\{}i_{1},i_{2},\ldots,i_{n}{\}}$ be a set of items and $DB={\{}T_{1},\ldots,T_{m}{\}}$ be a transaction database, where each transaction $T_{j}(1\leqslant j\leqslant m)$ in $D B$ involves a unique set of items and $\textit{TID}_{j}$ – a unique identifier.

An item subset $P={\{}i_{b},\ldots,i_{e}{\}}\subseteq I$ , where $1\leqslant b<e\leqslant n$ , is called a pattern (or an itemset). $P$ ’s absolute support is defined as the number of transactions containing $P$ in $D B$ , denoted $\textit{Sup}(P)$ . The relative support $\textit{sup}(P)$ is then defined as follows:

$\displaystyle\textit{sup}(P)=\frac{\textit{Sup}(P)}{\left|{DB}\right|}$ (1)

where 0 $\leqslant\textit{sup}(P)\leqslant$ 1. Given a minimum support threshold (minsup) $\xi$ , a pattern $P$ is considered to be frequent when $\textit{sup}(P)\geqslant\xi$ .

First, to make the generation of conditional transactions from HCPT-Tree more convenient, each item in each transaction is mapped to its corresponding item index.

Definition 1. Item index: This is the item number listed in decreasing order of support.

As mentioned in Section 2, HCFP-tree aims to maximize prefix sharing and is defined as follows.

Definition 2. HCFP-tree includes following structures:

It comprises a HeaderTable and the body of the tree.

The tree’s root represents the index of the item with the highest support.

Each tree node is a compressed prefix node (CPN) that stores the index. Each CPN comprises an item index, path count, a pointer to the next node with the same item index, pointers to the parent CPN and CPN’s next sibling, a child pointer, and a pointer to the path count node (PCN).

Definition 3. The HeaderTable contains all FIs sorted in the descending order of support. Each HeaderTable entry comprises an item index, item name, support, and node links.

Next, to compress the right branches in the CFP-tree, we introduce the concept of the first-start item index (FSI).

Definition 4. First-start item index: Let $F={\{}f_{1},f_{2},\ldots,f_{n}{\}}$ be an indexed set of the FIs stored in the descending order of support in a given transaction. If $f_{1}$ is equal to 1, then $\textit{FSI}=f_{2}$ . Otherwise, $\textit{FSI}=f_{1}$ .

Transactions can thus be divided into two types, where the first type has FSIs equal to the index of their first item, while this is not true for the second type. Each CPN uses PCN to increase prefix sharing.

Definition 5. Path Count Node (PCN). A PCN consists of four fields: level-id, firstcount, secondcount, and next-link, in which level-id registers the FSI of transactions, firstcount registers the number of occurrences of the first type of transactions that are represented by the index set in the path from the CPN at level level-id to the CPN to which the PCN is attached, secondcount counts the second type of transactions, and next-link is linked to the next PCN.

Compared to a CFP-tree, an HCFP-tree has the following major differences:

The CFP-PRO algorithm utilizes the CFP-tree to mine FIs nonrecursively, while HCFP-tree is proposed to mine FIs recursively.

Each node in a CFP-tree boasts a count array in which many entries may be empty. In contrast, HCFP-tree creates PCNs for each node independently, and connects them by pointers; therefore, an HCFP-tree requires less memory than a CFP-tree.

The count array of nodes in CFP-tree counts only one type of transactions, while the PCN of a node in HCFP-tree can count two types of transactions. Therefore, the HCFP-tree can improve prefix sharing compared to the CFP-tree.

3.2 HCFP-tree construction

First, the algorithm scans the dataset $D$ to calculate the item supports and identify FIs. Then, it generates the HeaderTable and constructs the leftmost branch of the tree, generating a CPN for each FI index as the root of that index’s subtree. It then sets the path count values of all nodes in the leftmost branch to 0.

Then, $D$ is scanned again to construct the HCFP-tree. First, each item in each transaction is mapped to the index and sorted in descending support order. Second, the FSI of each transaction is calculated. When the first index in the transaction is 1, the FSI is equal to the second index and the path count of the root is increased by 1. Otherwise, FSI is equal to the first index. Subsequently, HCFP-growth performs item insertion starting from the HeaderTable [FSI]. In addition, the node in the leftmost branch pointed to by the HeaderTable [FSI] becomes the current node, and its PCN is updated. Then, the next index in the transaction is inserted. The algorithm checks whether the current node has a child node whose index matches the inserted index. If such a child node exists, the algorithm regards it as the current node and updates its PCN. Otherwise, the algorithm creates a new child node and updates its PCN. After generating a new child node, it becomes the current node. Subsequently, the algorithm continues to insert the remaining items. In the Update PCN process, HCFP-growth increases the path count of the current node by 1. If the current node has one PCN whose level-id matches the FSI, the HCFP-growth algorithm increases the firstcount or secondcount of the PCN according to the FSI value; otherwise, it creates a new PCN attached to it.

The HCFP-tree construction process is depicted in the following example.

Figure 3.

An HCFP-tree state: inserting the first transaction.

Figure 4.

An HCFP-tree state: inserting the second transaction.

Example 3. The transaction database is shown in Table 1. After initializing the leftmost branch of the HCFP-tree, the index sets are inserted. In the first transaction, after mapping {a, b, c, d} to their indexes, the result is {1, 2, 3, 4}. Because the first item index is 1, its FSI is 2. Thereafter, the index set of the first transaction are inserted into HCFP-tree starting from CPN (2:0). The index set shares a prefix with the leftmost branch in the tree. Thus, the path count is increased by 1, generating a new PCN, {2, 0, 1, null} for each CPN in the branch. Figure 3 shows the state of HCFP-tree after inserting the first transaction.

Figure 5.

An HCFP-tree state: inserting all transactions.

Next, the index set of the second transaction is inserted, where the mapped index set is {2, 4}. Because the FSI of the second index set is 2, the path count of CPN (2:1) is increased by 1 and its corresponding PCN is updated to {2, 1, 1, null}. Subsequently, index ‘4’ is inserted into the tree. However, there is no index ‘4’ in the child node of CPN (2:2); therefore, a new CPN (4:1) is created whose new PCN is {2, 1, 0, null}, as shown in Fig. 4. Then, the remaining index sets can be inserted into HCFP-tree. Figure 5 shows the HCFP-tree after inserting all the transactions.

3.3 HCFP-tree analysis

Because both the HCFP-tree and FP-tree employ an ordered tree structure and a recursive mining FI process, we compare HCFP-tree and FP-tree regarding the following three steps: node generation, transaction insertion, and tree traversal.

Definition 6. Compression Efficiency of Nodes (CEN). Let $\alpha$ and $\beta$ be the total number of nodes in HCFP-tree and FP-tree, respectively. The CEN is defined as

$\displaystyle\textit{CEN}=\frac{\beta-\alpha}{\beta}$ (2)

In HCFP-tree, each newly generated CPN can be seen (approximately) as a combination of a new FP-Tree node and PCN.

Property 1. Let $t_{1}$ be the running time for the FP-tree to generate a new node and store the corresponding item information in it, and let $t_{2}$ be the running time needed when HCFP-tree creates a new PCN and stores corresponding information in it. Accordingly, HCFP-tree needs $t_{1}+t_{2}$ to create a CPN and should satisfy $t_{2}/t_{1}=0.5$ .

Rationale: Each node in the FP-tree consists of 2 integer domains and 4 pointers: item-name, count, node-link, parent pointer, child pointer, and sibling pointer. An HCFP-tree PCN consists of 3 integer values and 1 pointer: level-id, firstcount, secondcount, and next-link. The integer values can be accessed directly. However, we must confirm whether the pointer has been stored before accessing it. Therefore, accessing an integer value requires only one task, while accessing a pointer requires two tasks. In the FP-tree, generating a new node requires ten tasks, and in the HCFP-tree, creating a new PCN requires five tasks. Assuming that $\nu$ is the memory-access time, we therefore obtain $t_{1}=(10\times\nu)$ and $t_{2}=(5\times\nu)$ . Consequently, it is true that $t_{2}/t_{1}=0.5$ .

Property 2. In the transaction insertion phase, HCFP-tree is faster than FP-tree if the CEN is greater than 50%.

Rationale: Let $e$ be the number of transactions in the dataset and $f$ be the average number of items in the transaction. Therefore, the total number of items in the dataset is $e\times f$ . Consequently, the total insertion time of FP-tree for all transactions, $s_{1}$ , is denoted as follows:

$\displaystyle s_{1}=e\times f\times t_{1}$ (3)

For HCFP-tree, approximately $\textit{CEN}\times e\times f$ items are compressed. Accordingly, $(1-\textit{CEN})\times e\times f$ new CPNs and $\textit{CEN}\times e\times f$ new PCNs must be created. Thus, the total insertion time of HCFP-tree for all transactions, $s_{2}$ , is denoted as follows:

$\displaystyle s_{2}=(1-\textit{CEN})\times e\times f\times(t_{1}+t_{2})+% \textit{CEN}\times e\times f\times t_{2}$ (4)

The relation $s_{1}>s_{2}$ is equivalent to

$\displaystyle e\times f\times t_{1}>(1-\textit{CEN})\times e\times f\times(t_{% 1}+t_{2})+\textit{CEN}\times e\times f\times t_{2}$ (5)

And the solution is

$\displaystyle\textit{CEN}>t2/t1=0.5$ (6)

Therefore, in the transaction insertion phase, HCFP-tree achieves better performance than FP-tree if the CEN is greater than 50%.

Property 3. For tree traversal, HCFP-tree is faster than FP-tree when the CEN is greater than 50%.

Rationale: Given item $i$ in the header table, by following the node link starting at $i$ , there are $m$ branches that contain item $i$ . Let the average number of nodes in each path from $i$ to the root be $n$ . Accordingly, the time to search the FP-tree, $w_{1}$ , is denoted as follows.

$\displaystyle w_{1}=m\times n\times\nu$ (7)

In an HCFP-tree, when all branches with item $i$ are visited, the total number of nodes found is $(1-\textit{CEN})\times m\times n$ , and the average number of PCNs attached to the node is 1/(2CEN). Therefore, the total time to search an HCFP-tree, $w_{2}$ , can be defined as follows:

$\displaystyle w_{2}=\nu\times\left((1-\textit{CEN})\times m\times n\times\left% ({1+\frac{1}{2\textit{CEN}}}\right)\right)$ (8)

The relation, $w_{1}>w_{2}$ can be denoted as

$\displaystyle m\times n\times\nu>\nu\times\left({({1-\textit{CEN}})\times m% \times n\times\left({1+\frac{1}{2\textit{CEN}}}\right)}\right)$ (9)

and the solution is

$\displaystyle\textit{CEN}>0.5$ (10)

Property 3 is important, because it shows that HCFP-tree is more efficient than FP-tree when the CEN is greater than 50%.

To further reduce the number of nodes in an HCFP-tree, we propose a technique of reusing the HeaderTable.

3.4 Reusing the HeaderTable

Section 3.2 demonstrated how to construct an HCFP-tree, which first constructs the Header Table and the leftmost branch of the HCFP-tree. Because both the HeaderTable and the leftmost branch of the HCFP-tree contain all the frequent items, the HeaderTable can be reused to take the place of the leftmost branch of the HCFP-tree.

Figure 6.

HCFP-tree construction algorithm.

Figure 7.

The procedure of InsertHCFPTree.

To accomplish this task, two fields are added to each entry in HeaderTable: path count and a pointer to a PCN. When a transaction is inserted in to the tree, HCFP-growth performs item insertion starting from HeaderTable [FSI], and then, HeaderTable [FSI] becomes the current node. If there a HeaderTable node exists that is adjacent to the current node and matches the next index of the transaction, the current node is set to that node. Otherwise, the algorithm confirms whether the current node has one child node whose index matches the inserted index. When such a child node exists, the algorithm regards that child node as the current node. Otherwise, the algorithm creates a new child node.

Figure 8.

The procedure of UpdatePCN.

Figure 9.

An HCFP-tree reusing the HeaderTable.

Figures 6–8 show the pseudocode for constructing the HCFP-tree.

Figure 9 shows a HCFP-tree that reuses the HeaderTable for the database shown in Table 1. The number of nodes in the HCFP-tree is reduced by 4.

In Section 4.3, the experimental results show that the technique of reusing the HeaderTable achieves outstanding performance for sparse datasets (such as Retail) that contain a large number of items.

After constructing the HCFP-Tree, HCFP-Growth starts mining FIs from it.

3.5 Mining frequent patterns

HCFP-growth traverses an HCFP-tree in a bottom-up strategy and creates conditional HCFP-trees recursively. Initially, the presented algorithm starts with the least frequent item index in the HeaderTable and then searches the nodes based on that item index’s node links. The algorithm visits the nodes in the path from each linked node to a root by following parent pointer and counts their support values. HCFP-growth terminates the path-searching operation when the parent node is the root; these item indexes of the nodes in the path form a transaction substring. Assume that the number of items indexed in the path is $n$ ; its transaction substring $T S$ is denoted as $TS={\{}i_{1},i_{2},\ldots i_{n}{\}}$ .

If a single path cannot be derived from a node $a_{i}$ , the algorithm generates conditional transactions according to its PCNs. Let $\textit{PCN}_{i}={\{}L,C_{1},C_{2},N{\}}$ and the item index of the first visited node be $l$ . When $C_{1}>$ 0, a new conditional transaction $CT_{i1}$ can be obtained whose support is $C_{1}$ . $CT_{i1}$ is defined as follows:

$\displaystyle CT_{i1}={\{}i_{x},\ldots i_{y}|:C_{1}{\}}L\leqslant i_{x}<i_{y}<% l,i_{x}\subseteq TS\textit{ and }i_{y}\subseteq TS$ (11)

Otherwise, when $C_{2}>$ 0, a new conditional transaction $CT_{i2}$ can be obtained as follows:

$\displaystyle CT_{i2}={\{}1,i_{x},\ldots i_{y}|:C_{2}{\}}L\leqslant i_{x}<i_{y% }<l,i_{x}\subseteq TS\textit{ and }i_{y}\subseteq TS$ (12)

According to these conditional transactions, the algorithm creates a conditional pattern base. Subsequently, each conditional transaction is sorted in descending order of support and infrequent items are eliminated. Then, based on the sorted conditional pattern base, the algorithm generates a new conditional HCFP-tree. HCFP-growth will construct conditional HCFP-trees recursively until each node in HeaderTable of the conditional HCFP-tree derives a single path.

When $a_{i}$ already follows a single-path, the algorithm generates all the combinations of the item indexes. Let $a_{i}$ contain $m$ PCNs denoted as follows:

$\displaystyle\textit{PCN}\text{s}:{\{}\textit{PCN}_{1}=(L,C_{1},C_{2},N),% \ldots,\textit{PCN}_{\text{m}}=(L,C_{1},C_{2},N){\}}$ (13)

For any combination of the item indexes, $P$ is denoted as $P={\{}i_{x},\ldots i_{y}{\}},1\leqslant x<y\leqslant n,i_{x}\subseteq TS$ and $i_{y}\subseteq TS$ . The support of $p$ is denoted by

$\displaystyle\textit{support}_{p}=\left\{{{\begin{array}[]{ll}\mathop{\sum}% \limits_{\textit{PCN}_{j}.L<i_{x}}\textit{PCN}_{j}.c_{2}&\text{if }\,i_{x}=1\\ \mathop{\sum}\limits_{\textit{PCN}_{j}.L\leqslant i_{x}}(\textit{PCN}_{j}.c_{1% }+\textit{PCN}_{j}.c_{2})&\text{if }\,i_{x}\neq 1\\ \end{array}}}\right.$ (14)

All the item index combinations are mapped to patterns. Finally, the set of FIs is generated by combining the patterns and the prefix itemset.

Figure 10.

The conditional HCFP-tree of index 4.

Example 4. The HCFP-tree is shown in Fig. 9. Let minsup be 2, HCFP-growth starts from the least frequent item (index: 4, item: d) in the header table, and index ‘4’ derives an FI ( $d:8$ ). By traversing the node-links of index ‘4’, two nodes with index ‘4’ are found. Thus, there are two paths starting from index ‘4’ in the tree, and two transaction substrings can be obtained: {3, 2, 1} and {2, 1}, respectively. In the first path, the PCNs of index ‘4’ are: {2, 1, 1}, {3, 1, 1}, and {4, 1, 1}. Because the level-id of the first PCN is 2, the conditional transaction should be generated from index ‘2’ to index ‘3’. Meanwhile, because the secondcount of the first PCN is 1, the index 1 should be inserted. Thus, the conditional transactions obtained are as follows: {3, 2, 1 $|$ :1}, {3, 2 $|$ :1}. Similarly, conditional transactions can be obtained from the other PCNs: {3, 1 $|$ :1}, {3 $|$ :1}, and {1 $|$ :1}, respectively. In the second path, the PCN of index ‘4’ is: {2, 1, 1}, and the conditional transactions obtained are {2 $|$ :1} and {2, 1 $|$ :1}. These conditional transactions form the conditional pattern base of index ‘4’. Additionally, HCFP-growth constructs a conditional HCFP-tree for index ‘4’. Figure 10 shows the conditional HCFP-tree for index ‘4’, in which each node derives only a single path. Consequently, their sets of FIs can be generated directly, e.g., {a d:4}, {b d:4}, {a b d:2}, {c d:4}, {a c d:2}, and {b c d:2}.

For node ‘3’ in Fig. 9, the algorithm derives an FI (c: 8) and a single path {3, 2, 1}. Thus, its PCNs can be accessed and its set of FIs can be generated: {c b a: 2}, {c b: 4}, and {c a: 4}. Similarly, nodes ‘2’ and ‘1’ drive their sets of FIs: {b a: 4}, {b: 8}, and {a: 8}.

The following Property 4 shows why HCFP-growth is advantageous.

Property 4. The number of recursive calls in HCFP-growth is lower than that in FP-growth.

Rationale: Both FP-growth and HCFP-growth algorithm use a recursive mining method that continues until the conditional tree contains only one path. HCFP-growth utilizes a highly compressed tree structure. For the same transaction dataset, HCFP-tree supports more prefix sharing and generates fewer nodes does than a corresponding FP-tree. Therefore, HCFP-tree forms a single-path earlier than FP-tree. Thus, the number of recursions in HCFP-growth is smaller than the number of recursions in FP-growth.

Based on the above analysis, the proposed HCFP-growth algorithm is shown in Fig. 11. HCFP-growth selects each item index with $i$ starting from the bottom of the HeaderTable, and checks whether the node with the current index follows only one path (lines 1–3). When that is the case, the algorithm generates FIs by combining all the indexes in the path with the prefix (lines 3–6). Subsequently, the algorithm calculates the FI support based on the PCNs of the current node. Otherwise, the indexes in the paths from the nodes with the current index to the first node of the HeaderTable are stored in $T S$ (lines 9 and 10). Then, the algorithm generates conditional patterns from $T S$ according to the PCNs of the nodes (lines 12–33). Next, a conditional HCFP-tree is created to implement the procedure Construct_HCFP-tree (line 34). Finally, the algorithm calls HCFP-growth recursively to obtain all the FIs (line 37).

Figure 11.

HCFP-growth algorithm.

4. Performance evaluation

To evaluate HCFP-growth, we compare it with other state-of-the-art algorithms based on three criteria: running time, memory consumption, and scalability. Experiments are also performed to observe the number of recursive calls and nodes in the conditional trees to demonstrate the compression efficiency of HCFP-tree.

4.1 Experimental environment and datasets

All the experiments are executed on a computer with a 2.16 GHz Intel processor with 2 GB of memory and a Windows 7 OS. In this study, HCFP-growth is compared with FP-growth, CT-PRO, LP-growth, NSFI, and MAFIA [28]. All these algorithms were implemented in C++ and compiled with Microsoft Visual Studio 2010. Several real datasets were employed to evaluate the performance of the algorithms; the characteristics of these datasets are presented in Table 2. Pumsb is provided by http://archive.ics.uci.edu/ml/index.html, and the other datasets were acquired from http://fimi.cs.helsinki.fi/data. These datasets can be divided into two categories: dense datasets, in which many similar transactions exist and the number of unique items in each transaction is relatively small, and sparse datasets, which are the opposite of a dense dataset: they include many FIs when minsup is small. Here, Chess, Connect, and Pumsb are dense datasets, while Retail, Mushroom, and Accidents are sparse datasets.

Table 2
Real datasets

Datasets	#Items	Avg. length	Transactions
Chess	75	37	3,196
Retail	16,469	10.3	88,162
Connect	129	43	67,557
Mushroom	119	23	8,124
Pumsb	2,133	50.5	49,046
Accidents	468	33.8	340,183

Table 3

Datasets for scalability test

Datasets	T	I	L	Items	Transactions(k)
T10I4D1000K	10	4	2000	1000	1000
T10I4D2000K	10	4	2000	1000	2000
T10I4D3000K	10	4	2000	1000	3000
T10I4D4000K	10	4	2000	1000	4000
T10I4D5000K	10	4	2000	1000	5000
T100N10000	10	4	1000	1000	1000
T200N10000	10	4	2000	2000	1000
T300N10000	10	4	3000	3000	1000
T400N10000	10	4	4000	4000	1000

Table 3 presents the parameters of synthetic datasets for scalability tests. These datasets are generated by the IBM data generator acquired from http://www.almaden.ibm.com/software/projects/hdb/resources. shtml. The first part of Table 3 lists the datasets utilized to test the scalability of the compared algorithms as the transaction size changes. In these datasets, the number of transactions ranges from 1000 K to 5000 K. The second part of Table 3 lists the datasets used to evaluate the scalability of the compared algorithms as the number of items increases from 1,000 to 4,000. In Table 3, $|$ T $|$ represents the number of items in the dataset, $|$ I $|$ represents the average length of the maximal patterns, and $|$ L $|$ represents the number of FIs.

4.2 Compressed efficiency of HCFP-tree

When CEN is greater than 50%, HCFP-tree executes faster than does FP-growth, as discussed in Section 3.2. HCFP-growth requires fewer recursive calls and conditional HCFP-trees than does FP-growth, according to Property 4. To support these analyses, experiments are performed to compare the number of nodes required by HCFP-growth and FP-growth. Figure 12 shows the experimental results of the number of nodes resulting from six datasets. These results show that HCFP-growth requires a smaller number of nodes for all the datasets compared to the number of nodes required by FP-growth.

Notably, the CEN is the highest in the Connect dataset, while the CEN is the lowest in Retail. When minsup is 60% in Connect, HCFP-growth requires only 40.36% of the number of nodes required by FP-growth, and the CEN is 59.64%. For the Retail dataset, the number of nodes required by HCFP-growth is still 13.1% less than that required by FP-growth. Next, experiments are performed to compare the number of recursive calls made in HCFP-growth and FP-growth.

Figure 12.

The number of nodes in HCFP-growth and FP-growth on various datasets at various support thresholds.

Figure 13.

The number of recursive calls in HCFP-growth compared to FP-growth on various datasets at various support threshold.

Figure 13 shows results of the number of recursive calls for the various datasets. A conditional tree is constructed during a recursive call. From the experimental results, the number of conditional trees created by HCFP-growth for all the datasets is smaller than the number of trees created by FP-growth. This is especially apparent when minsup is 60% and HCFP-growth creates 33,923 trees for the Connect dataset – only 27.22% of the number of trees created by FP-growth. Even for Retail, the number of conditional trees created by HCFP-growth is still 21% smaller than the number created by FP-growth.

From these results, it can be concluded that HCFP-growth reduces the cost of conditional tree construction, and outperforms FP-growth in most cases even when the CEN is less than 50%.

4.3 Runtime analysis

Figure 14 shows the runtimes with various minsup values on the real datasets in Table 2. To improve the mining performance, MAFIA utilizes a vertical bitmap that may increase both runtime and memory consumption. Therefore, MAFIA performs the worst in most cases, especially on sparse datasets such as Retail (in Fig. 14b, the MAFIA result is not included because the runtime is too high to plot).

CT-PRO achieves outstanding runtime performance when minsup is low due to its compressed FP-tree data structure. Nevertheless, the CT-PRO algorithm requires large amounts of memory when processing all the datasets, and its runtime is longer than that of HCFP-growth when minsup is large.

Particularly, in Fig. 14c and d when the threshold was greater than 70% for the Connect, 65% for the Pumsb and 10% for the Mushroom, the CT-PRO algorithm’s performance is only slightly better than that of the MAFIA algorithm.

Figure 14.

Runtime test.

FP-growth’s mining time exceeds that of LP-growth on all the datasets except Retail. For example, in Pumsb, when minsup is 60%, the execution time of the FP-growth algorithm is 485 seconds. However, for the same minsup, LP-growth requires only 475 seconds. LP-growth’s performance improvement occurs because it uses an LP-tree, which reduces the number of pointers between nodes.

However, LP-tree may degenerate into FP-tree when sparse datasets have large amounts of items. For example, Retail has 16,469 items; thus, LP-growth exhibits poor performance on Retail, as shown in Fig. 14b.

NSFI recursively executed the N-list intersection procedure instead of constructing conditional trees. Therefore, NSFI shows excellent runtime performance on the dense datasets. However, when there are many items but little prefix sharing in the sparse datasets, NSFI’s efficiency is poor because it must construct many N-lists.

Overall, HCFP-growth achieves the best performance on almost all the datasets. The reason is that when minsup is below 90% for Connect, the CEN is greater than 50%. Although when minsup is less than 80% for Pumsb, 90% for Chess, 70% for Accidents, and 30% for Mushroom, and the CENs are not greater than 50%, HCFP-growth still executes faster than the others because it reduces the cost of creating conditional trees. Notably, the CEN on Retail is only 13.1%. However, Retail has many items; consequently, the presented algorithm maintains good performance on Retail by reusing the HeaderTable.

4.4 Memory consumption

In this section, we study the memory consumption of the compared algorithms on the datasets listed in Table 2.

Figure 15.

Memory tests.

CT-PRO and MAFIA consume more memory than the other algorithms in almost all cases. As shown in Fig. 15, when minsup is 90% for Connect, 30% for Mushroom, and 80% for Accidents, CT-PRO has relatively good memory efficiency. However, as minsup increases, CT-PRO’s memory consumption increases dramatically. In contrast, MAFIA’s memory usage remains constant regardless of the minsup value. Notably, in Fig. 15f, with a threshold below 40% for the Accidents dataset, MAFIA boasts outstanding memory efficiency.

In addition to the prefix tree, NSFI must also construct N-lists; therefore, it consumes more memory, especially on sparse datasets. LP-growth consumes relatively less memory although its memory usage is still higher than that of HCFP-growth. FP-growth’s memory consumption is similar to that of our algorithm in almost all cases.

Even though HCFP-growth does not always use smallest amount of memory, as shown in Fig. 15b and f, it still uses less memory in these cases than do some of the existing algorithms, such as NSFI and CT-PRO. In addition, the proposed algorithm achieves the best experimental results regarding memory in many cases. In particular, in Fig. 15a and c–e, HCFP-growth outperforms the compared algorithms on the Connect, Mushroom, Pumsb and Chess datasets in all cases.

Figure 16.

Scalability test.

4.5 Scalability

Figure 16 shows the results of the scalability experiments by varying the number of items and transactions in the synthetic datasets listed in Table 3. Notably, MAFIA and CT-PRO perform the worst, because they have the highest memory requirements.

FP-growth exhibits outstanding scalability in these experiments as the number of transactions increases, but its performance falls as the numbers of items increase, as shown in Fig. 16c and d.

Based on its linear structure, LP-growth enjoys better memory scalability performance than FP-growth; through its runtime scalability does not. NSFI shows better scalability than MAFIA, FP-growth and CT-PRO, but its memory consumption increases faster than HCFP-growth. The presented algorithm boasts the best runtime performances in the scalability experiments as shown in Fig. 16a and c. As the number of items and transactions increase, the runtime of HCFP-growth increases slightly due to its highly compressed tree structure. Consequently, as the number of items and transactions increase, there is a slight increase in the number of nodes in HCFP-tree. HCFP-growth does not show the best memory scalability, however, its memory scalability is still better than that of MAFIA, NSFI and CT-PRO, as shown in Fig. 16d. In summary, HCFP-growth exhibits the best runtime and relatively better memory scalability compared to the other tested algorithms as the numbers of items and transactions increase.

4.6 Conclusion

In this study, a novel highly compressed tree structure (HCFP-tree) and an efficient FI-mining algorithm (HCFP-growth) are proposed. By using a new data structure called PCN, an HCFP-tree supports more prefix sharing and considerably reduces the number of nodes in the tree. The major advantage of the HCFP-growth is that it reduces the number of recursive calls by adopting the highly compressed HCFP-tree structure. Therefore, HCFP-growth markedly improves the FI-mining performance because it generates fewer conditional trees compared to FP-growth. The experimental results show that HCFP-growth executes faster than do the other algorithms and that its memory consumption is the smallest in many cases and is comparable to those of existing algorithms in other cases. The methods and strategies presented in this paper can be extended to other types of patterns mining such as weighted pattern mining, sequential pattern mining, subgraph mining, and so on. Further study along these directions could provide significant academic value.

Footnotes

Acknowledgments

This research was supported in part by the National Science and Technology Major Project of the Ministry of Science and Technology of China under grant 2018ZX10715003, the National Key R&D Program of China under grant 2017YFC1703900, the Sichuan Science and Technology Program under grants 2018GZ0192 and 2018SZ0065, and the National Natural Science Foundation of China (NSFC) under grant 81803851.

References

Liu

Hsu

and Ma

, Integrating classification and association rule mining, in: Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, 1998.

Agrawal

Gehrke

Gunopulos

and Raghavan

, Automatic subspace clustering of high dimensional data, Data Mining & Knowledge Discovery11 (2005), 5–33.

Ruggieri

, Frequent regular itemset mining, in: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, Dc, Usa, July, 2010, pp. 263–272.

Nahar

Imam

Tickle

K.S.

and Chen

Y.-P.P.

, Association rule mining to detect factors which contribute to heart disease in males and females, Expert Systems with Applications40 (2013), 1086–1093.

H.-F.

, A sliding window method for finding top-k path traversal patterns over streaming Web click-sequences, Expert Systems with Applications36 (2009), 4382–4386.

Weng

C.-H.

, Revenue prediction by mining frequent itemsets with customer analysis, Engineering Applications of Artificial Intelligence63 (2017), 85–97.

Chen

Y.C.

Peng

W.C.

and Lee

S.Y.

, CEMiner – An Efficient Algorithm for Mining Closed Patterns from Time Interval-Based Data, in: IEEE International Conference on Data Mining, 2011, pp. 121–130.

Agrawal

and Srikant

, Fast algorithms for mining association rules in large databases, in: Proceedings of the 20th International Conference on Very Large Data Bases, Sep 12–15, 1994, Santiago, Chile, 1994, pp. 487–487.

Jiawei

Jian

and Yiwen

, Mining frequent patterns without candidate generation, Sigmod Record29 (2000), 1–12.

10.

Leung

C.K.S.

and MacKinnon

R.K.

, Fast Algorithms for Frequent Itemset Mining from Uncertain Data, in: 2014 IEEE International Conference on Data Mining, 2014, pp. 893–898.

11.

Leung

K.S.

Hao

and Jiang

, Constrained frequent itemset mining from uncertain data streams, in: IEEE International Conference on Data Engineering Workshops, 2010, pp. 120–127.

12.

Yun

and Leggett

J.J.

, WIP: Mining Weighted Interesting Patterns with a strong weight and/or support affinity, in: Siam International Conference on Data Mining, April 20–22, 2006, Bethesda, Md, Usa, 2006, pp. 3477–3499.

13.

Nguyen

and Pedrycz

, An efficient algorithm for mining frequent weighted itemsets using interval word segments, Applied Intelligence45 (2016), 1–13.

14.

Cagliero

and Garza

, Infrequent weighted itemset mining using frequent pattern growth, IEEE Transactions on Knowledge & Data Engineering26 (2014), 903–915.

15.

Wang

Zong

and Gao

, Mining Top-K Frequent Closed Patterns from Gene Expression Data, in: IEEE International Conference on Data Mining Workshop, 2014, pp. 732–739.

16.

Dam

T.-L.

Fournier-Viger

and Duong

Q.-H.

, An efficient algorithm for mining top-rank-k frequent patterns, Applied Intelligence45 (2016), 96–111.

17.

Gan

Lin

J.C.-W.

Fournier-Viger

Chao

H.-C.

and Zhan

, Mining of frequent patterns with multiple minimum supports, Engineering Applications of Artificial Intelligence60 (2017), 83–96.

18.

Chen

and Xiao

, BISC: a bitmap itemset support counting approach for efficient frequent itemset mining, Acm Transactions on Knowledge Discovery from Data4 (2010), 1–37.

19.

Deng

Z.H.

, DiffNodesets: an efficient structure for fast mining frequent itemsets, Computer Science41 (2015), 214–223.

20.

Lin

K.C.

Liao

I.E.

and Chen

Z.S.

, An improved frequent pattern growth method for mining association rules, Expert Systems with Applications38 (2011), 5154–5161.

21.

Pyun

Yun

and Ryu

K.H.

, Efficient frequent pattern mining based on Linear Prefix tree, Knowledge-Based Systems55 (2014), 125–139.

22.

Alghyaline

Hsieh

J.W.

and Lai

J.Z.C.

, Efficiently mining frequent itemsets in transactional databases, Journal of Marine Science & Technology24 (2016), 184–191.

23.

Gatuha

and Jiang

, Smart frequent itemsets mining algorithm based on FP-tree and DIFFset data structures, Turkish Journal of Electrical Engineering & Computer Sciences25 (2017), 2096–2107.

24.

Deng

Z.H.

and Lv

S.L.

, PrePost +: An efficient N-lists-based algorithm for mining frequent itemsets via Children-Parent Equivalence pruning, Expert Systems with Applications42 (2015), 5424–5432.

25.

Coenen

and Hong

T.-P.

, Mining frequent itemsets using the N-list and subsume concepts, International Journal of Machine Learning and Cybernetics7 (2016), 253–265.

26.

Giri

S.Y.

and P

G.R.

, CT-PRO: A Bottom-Up Non Recursive Frequent Itemset Mining Algorithm Using Compressed FP-Tree Data Structure, in: Fimi ’04, Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations, Brighton, Uk, November, 2004.

27.

Rácz

, nonordfp: An FP-growth variation without rebuilding the FP-tree, in: Fimi ’04, Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations, Brighton, Uk, November, 2008.

28.

Burdick

Calimlim

and Gehrke

, Mafia: A maximal frequent itemset algorithm for transactional databases, in: Data Engineering, 2001. Proceedings. 17th International Conference on, 2001, pp. 443–452.