Maximal Pattern Mining Using Fast CP-Tree for Knowledge Discovery

Introduction

Extracting frequent and maximal item sets from transaction database is an important task to find interesting patterns for knowledge discovery. Among various data mining techniques, such as association rules, correlations, sequences, classification and clustering, the association rule mining is the one of popular problems. The association rule describe how often items or patterns appears together. Agrawal et al. (1994) has introduced the association rule mining and frequent item set problem and from then it has received attention from the researchers both in academia and industries. Among various algorithms, Apriori is the first technique, which uses candidate generation–and–test methodology to find frequent patterns. In Apriori, the frequent patterns are mined using “bottom up” approach, where frequent patterns of length ‘k’ candidate set is generated from the previously generated (k-1) candidate patterns. The counts of the candidates are accumulated by scanning the dataset. While the count of frequent pattern is less than the minimum support, it is pruned and the remaining set is used to find the next candidate set. The algorithm terminates while there is no further successful extension are available. To reduce the time for mining frequent patterns by pruning the candidate sets without scan the database is an important property called Anti-monotone property. This property has been used which is, if a set of length ‘k’ cannot pass a test, which implies that all its super sets of length (k+1) will eventually fail the same test. Similarly, the Apriori principle, is that “Any subset of frequent item set must be frequent” are followed. In order to find frequent patterns, Apriori requires multiple database scans and it requires a large amount of memory for handling the candidate patterns. This nature of problem has been dealt by Frequent-Pattern (FP) tree. In FP-tree (Han et al., 2004), the multiple scans of the large dataset is avoided by compressing the dataset into highly compact frequent descending tree structure and it is build with two scans. During first scan, the process collects the set of frequent items in which items are arranged in descending order based on its frequency of occurrence. In the second scan, the process builds the highly compact frequency-descending tree structure. The pattern growth approach is used for mining by avoiding the candidate generation-and-test approach, which requires a large memory space to mine frequent patterns. Even though FP-tree mines the frequent patterns efficiently, it does not support interactive and incremental mining. Tanbeer et al. (2008) have proposed the CP-tree, which supports interactive, incremental and data stream mining. CP-tree is build with only one scan by periodically reorganizing the prefix-tree in frequent-dependent item order after inserting some number of transactions into the prefix-tree using the previous item order. By reorganizing the tree repeatedly, the CP-tree can maintain as much prefix sharing as possible in a prefix-tree and provide better mining performance. However, this periodically restructuring consumes time for construction of prefix tree.

The mentioned algorithms can mine the frequent patterns efficiently, while mining all subsets for a large frequent item set of length ‘l’, then at most ‘2l‘ item sets are generated. Since, from the facts that “any subset of the frequent item set must be frequent” and “all frequent item sets are upward closed”, finding all ‘2l‘ subset lead to increase in mining time. This can be avoided through discovering the maximal frequent item set from the dataset. A frequent item set is maximal frequent item set if it has no superset that is frequent.

Hence, in this paper, the transactional dataset is scanned ones to capture the maximal frequent item set from the Maximal Fast CP-tree. Initially in our work, the tree is constructed based on user given item order. The supports of each item are retrieved from the constructed tree and sort those items in order based on its support. Using sorted items, the nodes in each branch of the constructed tree is dynamically rearranged to obtain the prefix tree and then the maximal item sets are mined from the prefix tree using FPmax algorithm. In additional, the proposed tree supports both incremental as well as interactive mining approaches.