Efficient Algorithms for Mining Frequent Patterns from Sparse and Dense Databases

1.1 Contributions

Most databases consist of both sparse and dense data portions that can only be detected during the mining process. Applying single mining strategy for FPM will omit this feature and result in unstable performance on different data types. In this article, we present a novel approach for FPM and two algorithms, FEM and DFEM, based on this approach that can self-adapt to data characteristics. The main contributions of our study include:

1. The recognition of various characteristics of databases and the fact that this characteristics may change during the mining process is an original idea. The new approach presented in this article detects the data characteristics at various stages of the mining process and selects one of the two mining algorithms suitable for each subset of the data remaining to be mined on the fly. Two algorithms, FEM and DFEM, derived from the proposed approach are discussed.

2. Effective optimization techniques are introduced for the implementation of our mining approach to further the mining process, reduce the memory usage, and the I/O cost.

3. The efficiency of our approach is demonstrated in both execution time and memory usage via the benchmark of our algorithms (FEM and DFEM) with six other FPM algorithms including Apriori [1], Eclat [34], FP-growth [13], FP-growth* [11], FP-array [18], AIM2 [25]. We also analyze the reasons for the performance merit of our approach.

2.1 Problem Statement

The FPM problem can be stated as follows: let I= {i₁, i₂, …, i_n} be the set of all distinct items in the transactional database D. The count of an itemset x (a set of items) is the number of occurrences of x in D and the support of x is the percentage of transactions containing x. A k-itemset x, which consists of k items from I, is frequent if the support of x is at least minsup, where minsup is a user-specified minimum support threshold. Given a database D and a minsup, the problem statement is to find the complete set of frequent itemsets (or frequent patterns) in D. In this article, we use the terms “pattern” and “itemset” as well as “database” and “data set” interchangeably.

For example, given the data set in Table 2 and minsup= 20%, the frequent 1-itemsets include a, b, c, d, and e, whereas f is infrequent because its support is only 11%. Similarly, ab, ac, ad, ae, bc, bd, cd, ce, and de are frequent 2-itemsets, and abc, abd, ace, and ade are the frequent 3-itemset.

FPM is an important part of many data mining tasks, especially in association rule mining (ARM) [3], a problem of finding all strong association rules with the form: X → Y ∣ X, Y ⊂ I and X ∩ Y= ∅, whose support and confidence satisfy a minimum support threshold (minsup) and a minimum confidence threshold (minconf). The confidence of a rule is the percentage of transactions in D that contain X also contain Y. An example of such a rule might be that 60% of customers who purchase flour also buy sugar with a confidence 80%. ARM consists of two steps. The first step is finding all frequent itemsets that are computationally intensive and is the focus of our research. The second step is generating strong association rules from the frequent itemsets.

2.2 Frequent Pattern Mining Approaches

Mining frequent patterns is nontrivial because of its exponential search space and its large amount of data. Many algorithms have been developed to do this mining on large databases, and they typically perform efficiently on either sparse or dense databases but not both [1, 3–5, 9, 11, 13, 15, 22–25, 34].

Apriori [1] was the first sequential algorithm that sharply cuts down the search space to make this mining task feasible. Some variants of Apriori include direct hashing and pruning (DHP) [21], sampling technique [27], dynamic itemset counting (DIC) [7], BitApriori [9], and Hybrid search-based ARM [10]. Because of the breath-first strategy with multiple I/O scanning times and candidate generate-and-test approach, Apriori-like methods usually suffer from large computational time and memory usage.

Eclat-like algorithms load all data of the frequent items into memory, present them in vertical format, and apply the depth-first strategy to search for all frequent patterns. These algorithms run significantly faster than Apriori-like ones because they require at most two database scans and reduce memory usage sharply. Eclat and their variants have been shown to be the better choice for long patterns and/or dense databases [9, 24, 25, 33].

FP-growth is known as one of the most efficient FPM algorithms [13]. It compresses the data of the frequent items into an FP-tree in memory and recursively mines all frequent patterns from this data structure without candidate generation requirement. Because of its efficiency, this algorithm is used in large-scale applications such as Google’s query recommendation [17]. FP-growth* [11], H-mine [22], nonordfp [23], FP-growth with database partition projection [20] are some improvements of FP-growth. Although FP-growth has shown to outperform previously developed methods including Eclat and Apriori [4, 11, 13, 22, 23], it has been shown not to perform as well as Eclat-like algorithms [9, 24, 25] for dense databases or mining with low minimum support.

Recently, a new algorithm named FP-array has been proposed [18]. This algorithm inherits the mining features of FP-growth and presents data as arrays for cache optimization. FP-array was shown to achieve a significant performance improvement compared with FP-growth [13], nonordfp [23], and AIM2 [25].

3.1 Data Structures

FPM is a memory intensive task whose data presentation and manipulation have a huge impact on mining performance. In our mining approach, we apply two main data structures including FP-tree and Bit Vector for the mining task.

FP-tree is a prefix tree that compacts all sets of ordered frequent items from database into memory. This tree consists of a header table storing the frequent items with their count, a root node, and a set of prefix subtrees. Each node of the tree includes an item name, a count indicating the number of transactions that contain all items in the path from the root node to the current node, and a link to its parent node. Each linked list starting from the header table links all nodes of the same frequent item. If two itemsets share a common prefix, the shared part can be merged as long as the count properly reflects the frequency of each itemset in the database. Figure 1 illustrates an FP-tree constructed from the data set in Table 2, where a pair <x:y> indicates item name and its count.

Figure 1

FP-Tree Constructed from the Database in Table 2.

Bit Vector is used to store data in memory using the vertical format. This data structure includes item name, count, and vector of binary bits associated with an item or an itemset. The i^th bit of this vector indicates if the i^th transaction in the database contains that item or itemset (1: exist, 0: does not exist). For example, the data set in Table 2 can be presented in five bit vectors as in Figure 2. The bit vector of the item f is removed because this item is infrequent. This structure does not only save memory but also enables low-cost bitwise operations for computations.

Figure 2

Bit Vectors Constructed from the Data Set in in Table 2.

3.2 The Proposed Approach

Studying many real databases and their characteristics, we observed that most consist of a group of items occurring much more frequently than the others. During the mining process, the items in this group create data subsets whose characteristic is dense, whereas the less frequent items create subsets that are sparse. Our approach is combining two mining strategies: (1) the first one, which is applied for sparse data subsets, presents data as FP-tree and uses the divide-and-conquer approach to generate frequent patterns; (2) the second strategy, which is used to mine the dense data portions, stores data into Bit Vectors and performs ANDing bitwise operation on pairs of vectors to specify the frequent patterns. It has been shown that the first mining strategy works better on sparse data [11, 13, 22, 23] and the second one is more suitable for dense one [9, 24, 25, 34]. The proposed approach detects the characteristic of each data subset (not whole database) and applies a suitable one for these data dynamically. Based on this approach, we develop two new algorithms, FEM and DFEM, which are presented in Sections 4 and 5. In general, our mining method includes three main subtasks as shown in Figure 3:

Figure 3

Mining Model of the Proposed Approach.

FP-tree construction: the database is scanned for the first time to find the frequent items and create the header table. A second database scan is conducted to get frequent items of each transaction. Then, these items are sorted and inserted in the FP-tree in frequency-descending order. During the top-down traversal of the tree construction, if a node presenting an item exists, its count will be incremented by one. Otherwise, a new node is added to the FP-tree.

MineFPTree generates frequent patterns by concatenating the suffix pattern of the previous step with each item x of the input FP-tree. Then, it constructs a child FP-tree called conditional FP-tree for every item x using a data set called conditional pattern base. This data set is extracted from the input FP-tree and consists of sets of frequent items co-occurring with the suffix pattern. The new tree is then used as the input of this recursive mining task. This mining approach explores data in the horizontal format and does not require generating a large number of candidate patterns. Hence, it performs well on sparse databases. However, unlike the related works [11, 13, 22, 23] that perform mining on FP-tree only, MineFPTreecan switch to the second mining strategy when it detects the current data subset is dense. In this case, the data subset is converted into bit vectors and MineBitVector is invoked. A weight vector w whose elements indicate the frequency of sets in the conditional pattern base is added as the input of MineBitVector.

MineBitVector generates frequent patterns by concatenating the suffix pattern with each item of the input bit vector. It then joins pairs of bit vectors using logical AND operation and computes their support using the weight vector to specify new frequent patterns. The resulting bit vectors are used as the input of MineBitVector to find longer frequent patterns. The mining process continues in a recursive manner until all frequent patterns are found. For dense data, this mining strategy is better than MineFPTree because the number of frequent patterns, which is usually found in dense data, make is suitable for the candidate generation and test approach of MineBitVector.

Figure 4 illustrates an example. The conditional pattern base of item d, extracted from the FP-tree in Figure 1, consists of the four sets {a:2, b:2}, {a:1, c:1}, {a:1}, and {b:1, c:1} in which {a, b} occurs twice (Figure 4A). This base is equivalent to the data set represented in Figure 4B. If MineFPTree is selected, the conditional FP-tree of item d is constructed as in Figure 4C. Otherwise, the bit vectors a, b, c, and the weight vector w (Figure 4D and E) are created instead to be used by MineBitVector.

Figure 4

Illustration of FP-Tree and Bit Vector Construction. A: Conditional pattern base of item d; B: Dataset equivalent to the conditional base of item d; C: Conditional FP-tree of item d; D: Bit Vectors; E: Weight vector.

3.3 Switching between Two Mining Strategies

Effective determination of how and when to switch between the two mining strategies is key in our approach to perform efficiently on different types of databases. During the mining process of MineFPTree, a very large number of child FP-trees are constructed from the parent tree. A FP-tree is organized in such a way that the nodes of the most frequent items are closer to the top. The newly generated trees are much smaller than their parents because the less frequent items whose nodes are at bottom of the parent trees are removed. The size of a conditional pattern base, which is used to construct a new FP-tree, also reduces to a level where it contains mostly the most frequent items. In these cases, the conditional pattern base has the characteristic of a dense data set. Therefore, only small conditional pattern bases are considered for transforming into bit vectors and weight vector. The size of a conditional pattern base is specified by the number of sets in that base that is similar to the number of transactions in a data set. If this size is less than or equal to a threshold K, bit vectors and a weight vector are constructed and the mining switches to MineBitVector.

4.1 Algorithmic Descriptions

FEM uses the method described in Section 3 and includes three subalgorithms: FEM (Figure 5), MineFPTree (Figure 6), and MineBitVector (Figure 7). FEM first constructs the FP-tree from the database and then calls MineFPTree to start searching for frequent patterns and dynamically switch to MineBitVector if appropriate. In FEM, a fixed value of threshold K is used to decide whether MineFPTree or MineBitVector is applied during the mining process. Our experimental results show that selecting a good value of K for FEM is data-specific and depends on the user-specified minimum support threshold (minsup). For FEM to perform well on many databases, we suggest K = 128 (line 3). K can be adjusted to obtain better performance for a specific database application. An in-depth analysis on a range of values for K is presented in Section 4.2.

Figure 5

FEM Algorithm.

Figure 6

MineFPTree Algorithm.

Figure 7

MineBitVector Algorithm.

4.2 Selection of Threshold K

We further investigate the impact of varying values of K of different databases in this section. Selecting a good value of K also depends on the minimum support specified by the user. This raises the question of how to select a good value of K without testing all possible values? To answer this question, we conducted an experiment from which we suggest a good default value of K for FEM. In this experiment, we measure the performance of FEM on eight real data sets for varying values of K. The eight data sets selected for these test cases consist of a mix of four dense, three sparse, and one moderate to represent a variety of database characteristics. The detailed characteristics of these data sets are presented in Table 4. Values of K were selected in the range of 0–256 as multiples of 32 so that the maximum size of transaction ID (TID) bit vectors are also multiples of 32 (4 bytes) for better memory utilization. The running time of FEM for values of K for each data set are presented in Figure 8.

Figure 8

Running Time of FEM with Different Values of K.

As the results show, FEM performs better with K in the 32–128 range for seven of the data sets. For the Kosarak data set, FEM with a value of K in the 128–256 range performs best. This result reflects the excecution time with the selected minsup values. Based on extensive tests not presented here, we observe that when minsup varies, the range of K for each data set to produce best performance also changes, but it remains within the overall range of 0–256. For this reason, we recommend K = 128 as a default value for good performance on various databases and different minsup values. For K = 128, the maximum size of a Bit Vector is 128 bits (16 bytes). This is smaller than or equal to the size of just one node of FP-tree, which needs at least 16 bytes for item name (4 bytes), count (4 bytes), a link to parent node (4 bytes), and a link to the next node of its linked list (4 bytes). The total memory size of all Bit Vectors is therefore not greater than the number of items in the conditional pattern base multiplied by 16 bytes. This data structure requires much less memory space than an equivalent conditional FP-tree does. Furthermore, the bitwise operations on Bit Vector will perform faster than creating and manipulating FP-trees.

5.1 Computing Dynamic Value of K

FEM performs well for many databases using a value of K = 128. However, in some cases, the best performance is not reached with this fixed selection. The second column in Table 3 shows the running time of FEM for Kosarak data set with different values of K and minsup = 0.07%. As can be seen, for K = 224, the running time of FEM is 871 s, significantly faster than its running time of 1206 s for K = 128. This execution time difference becomes significantly larger when the minimum support threshold (minsup) is set to lower levels as required by many applications such as query recommendation for web search engine [17]. In this case, it is important to find the best possible value of K dynamically as the program runs on a specific database with the required minsups to gain near-optimal performance.

In Table 3, when K increases, the number of frequent patterns found solely by the MineFPTree task reduces because more mining workload is shifted to the MineBitVector task. Let {K₀, K₁, …, K_n} be the set of all values of K, where K_i = K_i–1 + 32; P_i is the number of frequent patterns generated by the MineFPTree task when K_i is applied; and R_i is the ratio indicating the difference between P_i and P_i–1. R_i is computed as R_i = P_i–1/P_i, i = 1, …, n.

Our intensive empirical study indicates that good mining performance is achieved with K_i that satisfies: Ri < 2 ∍ (∃Rj < 2, ∀j > i). In other words, FEM will perform best (near optimal) at the smallest K_i, where increasing K does not result in a sharp drop in the number of frequent patterns found by the MineFPTreetask. In the example in Table 3, the K_i that satisfies this condition is 224, and its runtime is 871 s. Although this result is promising, the challenge is that this K_i can only be specified when the mining process completes and all P_i and R_i have been computed. We have developed a practical method to predict a value of K that is close to or equal to the best K_i. The predicted value is based on all P_i’s estimated dynamically at runtime as described in UpdateK algorithm in Figure 9. In this algorithm, K is the global threshold initialized to zero, N is the number of different threshold values, K_i, that are being considered (default value N=9), Step is the distance between K_i and K_i–₁ (default value Step=32); and P[N] is an array whose the ith element stores the number of frequent patterns P_i estimated from all conditional pattern bases of the MineFPTree task. The elements of P[N] are initialized to zero and are regularly updated using the UpdateK algorithm everytime a new conditional pattern base is processed. K is then updated with a new value newKif newK satisfies the condition stated above. In Figure 9, NewPatterns indicates the number of new frequent patterns and is equal to the number of items in C (conditional pattern base); Size is the size of the C.

Figure 9

UpdateK Algorithm.

5.2 Algorithmic Description

DFEM uses UpdateK algorithm (Figure 9) to dynamically select the value of K at runtime and using it to adapt its mining behaviors to the characteristics of processed data better than FEM. DFEM consists of four sub algorithms: DFEM (Figure 10), UpdateK (Figure 9), MineFPTree* (Figure 11), and MineBitVector (Figure 6). MineBitVector of DFEM is similar to the one of FEM, shown in Figure 6.

Figure 10

DFEM Algorithm.

Figure 11

MineFPTree* Algorithm.

DFEM algorithm builds the FP-tree, initializes the variables used by UpdateK and invokes the MineFPTree*. The variables in lines 3–6 must be declared in a scope that UpdateK can access and update.

The MineFPTree* algorithm is similar to MineFPTree with the exception of the extra steps needed to regularly update K (lines 4–5 and lines 11–13 in Figure 10).

7.1 Experimental Setup

7.2 Time Comparison

The execution time of eight algorithms on eight data sets with various minsup are presented in Figure 12. The experimental results show that FEM and DFEM run stably and outperform the others in almost all cases, whereas the other algorithms behave differently for different data sets. Apriori runs slowest on eight data sets, but it does better than FP-growth* and FP-array for two dense data sets, Chess and Mushroom. For Retail, the sparse data set, Apriori has longer execution time compared with FEM, DFEM, and FP-growth but runs faster than the others. Eclat performs better than the others except AIM2, FEM, and DFEM on the dense data sets. However, for the sparse data sets such as Retail and Kosarak, Eclat runs slower than most of the others. Compared with Eclat, three algorithms, FP-growth, FP-growth*, and FP-array, run faster for the dense data sets but slower for the sparse ones. AIM2, a variant of Eclat, performs well for some dense and sparse data sets but worse for the other ones.

Figure 12

Execution Time of FEM, DFEM, and Other Algorithms.

Based on the execution time in this experiment, we found that FEM and DFEM run faster than Apriori – the most popular used FPM method – from 3.4 to 5555.6 times. In comparison to Eclat and AIM2 whose mining approach use vertical data format, our algorithms run faster from 1.02 to 45.3 times. Our algorithms performed 1.2 to 23.4 times better than FP-growth, FP-growth*, and FP-array, which are among the best methods for FPM. This experiment demonstrates the efficiency performance of FEM and DFEM for both sparse and dense data.

7.3 Memory Usage Comparison

To evaluate the memory usage efficiency of FEM and DFEM, we measured their peak memory usage in comparison to the other six algorithms for the eight data sets using the memusage command of Linux. Table 5 shows the memory usage (megabytes) of all algorithms for the test cases with low minimum supports so that the result can reflect the large difference in memory usage among the algorithms. As in Table 5, FEM and DFEM consume much less memory than Apriori in every case. Their memory requirements are closer to the average memory usage of Eclat and FP-growth in most cases. For the Accidents and Connect data set, our algorithms use less memory than both Eclat and FP-growth. For the Chess data set, FEM and DFEM need more memory because our implementation includes some additional buffers to enhance the performance. However, these buffers have fixed size and do not require much memory. Compared with FP-growth*, FEM and DFEM require more memory for the dense data sets but less memory for the sparse ones. In contrast, compared with FP-array, the memory usage of FEM and DFEM is smaller for the dense data sets but larger for the sparse ones. The memory usage of AIM2 is smallest in most cases. However, the memory usage of AIM2 for Webdocs, where memory optimization is critical due to its large memory requirements, AIM2 uses a significantly lager memory than the others do.

To sum up, the two experiments in Sections 7.2 and 7.3 show that FEM and DFEM not only significantly improve the mining performance and outperform other existing “efficient” algorithms for both sparse and dense data sets, they also compare well in memory requirements. Their memory consumption is much less than Apriori and FP-growth and is, on average, at par with the other algorithms. These results demonstrate the efficiency and efficacy of our algorithms. DFEM performs better than FEM, especially when minsup is low. Therefore, for mining application that requires low minsup, DFEM is a better choice.

7.4 Performance Impact of the Two Mining Strategies

To study the performance merit of our mining approach, we measured the mining time of DFEM in three separated cases: (1) using MineFPTree* only, (2) using MineBitVector only, and (3) using both MineFPTree* and MineBitVector, i.e., our approach. The results for DFEM on both dense and sparse data (Figure 13) show that it outperforms the other methods where single mining strategy was used. This is explained by the contribution of dynamic combination of the two strategies, MineFPTree and MineBitVector, to the mining task where each handles data portions it can perform best.

Figure 13

Execution Time of Using Single Mining Strategy vs. Using Both.

7.5 Analyzing the Self-adaptive Capability of Our Mining Approach to Data Characteristics

To understand the self-adaptive capability of our mining to data characteristics, we measured the time of MineBitVector and MineFPTree* in DFEM separately to observe the level that each mining strategy contributes to the overall performance for different databases and for various minsup input values.

Figure 14 shows the time distribution of MineBitVector and MineFPTree* for eight databases whose data characteristics range from very sparse to very dense. The results show that our approach automatically distributes the mining workload to its two mining strategies based on data characteristics. MineBitVector, which is more suitable for dense data, has been utilized mostly for the dense data sets like Chess, Connect, Mushroom, and Pumsb (85–99% of total mining time). The time percentage of this strategy reduces when the data are sparse. MineFPTree* is increasingly used for sparse data sets like Retail, Kosarak, and Webdocs (33–90% of total mining time). For the sparse portions of the data sets, MineFPTree* is a better choice because its mining approach does not require generating the very large number of infrequent candidate patterns.

Figure 14

Time Distribution of Two Mining Strategies in DFEM.

The ability to self-adapt to data characteristics shows not only for different databases but also for different minsup values for a given database. This is demonstrated by the time distribution of MineFPTree* and MineBitVector as minsup varies. Figure 15 presents the time distribution for Accident data set with various minsup values. The results show the lower minsup, the more mining workload and time were handled by MineBitVector. For the smaller values of minsup, a large number of frequent patterns are generated because more patterns satisfy the condition to be frequent. This situation is similar to mining on dense database. Our mining approach, therefore, automatically detects this feature and adjust its mining behavior to have more mining workload handled by MineBitVector and help improve the overall performance.

Figure 15

Time Distribution of Two Mining Strategies in DFEM for Accidents Dataset with Different minsup Input Values.