Introduction

Frequent item set mining is one of the fundamental problems in data mining and has many applications such as association rule mining, inductive databases, and query expansion. From these applications, fast implementations of frequent itemset mining problems are needed. In this paper, we propose the second versions of LCM, LCMfreq and LCMmax, for enumerating closed, all and maximal frequent itemsets. LCM is an abbreviation of Linear time Closed item set Miner .

In FIMI03 [7], we proposed the first version of LCM, which is for enumerating frequent closed itemsets. LCM uses prefix preserving closure extension (ppc extension in short), which is an extension from a closed itemset to another closed itemset. The extension induces a search tree on the set of frequent closed itemsets, thereby we can completely enumerate closed itemsets without duplications. Generating a ppc extension needs no previously obtained closed itemset. Hence, the memory use of LCM does not depend on the number of frequent closed itemsets, even if there are many frequent closed itemsets.

The time complexity of LCM is theoretically bounded by a linear function in the number of frequent closed itemsets, while the existing algorithms are not. We further developed algorithms for the frequency counting, occurrence deliver and hybrid of diffsets. They reduce the practical computation time efficiently. Moreover, the framework of LCM is simple. Generating ppc extensions needs no sophisticated data structure such as binary trees. LCM is implemented with only arrays. Therefore, LCM is fast, and outperforms than other algorithms for some sparse datasets.

However, LCM does not have any routine for reducing the database, while many existing algorithms have. Thus, the performance of LCM is not good for dense datasets with large minimum supports, which involve many unnecessary items and transactions. At FIMI03, we also proposed modifications of LCM, LCMfreq and LCMmax, for enumerating all frequent itemsets and maximal frequent itemsets. Although they are fast for some instances, if LCM is not fast for an instance, they are also not fast for the instance. Existing maximal frequent itemset mining algorithms have efficient pruning methods to reduce the number of iterations, while LCMmax does not have. It is also a reason of the slowness of LCMmax.

This paper proposes the second version of LCM algorithms. We added database reduction to LCM, so that problems of dense datasets can be solved in short time. The second version of LCMmax includes a pruning method, thus the computation time is reduced when the number of maximal frequent itemsets is small. We further developed new algorithms for checking the maximality of a frequent itemset and for taking the closure of an itemset. We compare the performance of LCM algorithms and other algorithms submitted to FIMI03 by computational experiments. In many instances, LCM algorithms perform above other algorithms.

The organization of the paper is as follows. Section 2 introduces preliminaries. The main algorithms and practical techniques of LCM algorithms are described in Section 3. Section 4 shows the results of computational experiments, and Section 5 concludes the paper.

Preliminaries

Let I = {1, ..., n} be the set of items. A transaction database on I is a set T = {t 1 , . . . , t m } such that each t i is included in I. Each t i is called a transaction. We denote by ||T || the sum of sizes of all transactions in T , that is, the size of database T . A set P ⊆ I is called an itemset.

For itemset P , a transaction including P is called an occurrence of P . The denotation of P , denoted by T (P ) is the set of the occurrences of P . |T (P )| is called the frequency of P, and denoted by f rq(P ). For given constant θ, called a minimum support, itemset P is frequent if f rq(P ) ≥ θ. If a frequent itemset P is included in no other frequent itemset, P is called maximal. For any itemsets P and Q, T (P ∪ Q) = T (P )∩T (Q) holds, and if

P ⊆ Q then T (Q) ⊆ T (P ). An itemset P is called closed if no other itemset Q satisfies T (P ) = T (Q), P ⊆ Q.

Given set S ⊆ T of transactions, let I(S) be the set of items common to all transactions in S, i.e., I(S) = T ∈S T . Then, we define the closure of itemset P in T , denoted by clo(P ), by I(T (P ))(= t∈T (P ) t). For every pair of itemsets P and Q, the following properties hold [13,14].

(1) If P ⊆ Q, then clo(P ) ⊆ clo(Q). (2) If T (P ) = T (Q), then clo(P ) = clo(Q).

(3) clo(clo(P )) = clo(P ). ( 4) clo(P ) is the unique smallest closed itemset including P . (5) A itemset P is a closed itemset if and only if clo(P ) = P .

For itemset P and item i ∈ P , let P (i) = P ∩ {1, . . . , i} be the subset of P consisting only of elements no greater than i, called the i-prefix of P . An itemset Q is a closure extension of an itemset P if Q = clo(P ∪ {i}) holds for some i ∈ P . If Q is a closure extension of P , then Q ⊃ P, and f rq(Q) < f rq(P ). We call the item with the maximum index in P the tail of P , and denote by tail(P ).

Algorithms for Efficient Enumeration

In this section, we explain the techniques used in the second versions of LCM algorithms. We explain them one-by-one with comparing to the techniques used by the other algorithms, in the following subsections. The techniques used in the existing algorithms and the first version have citations to the previous papers.

Enumerating Frequent Itemsets

Any itemset included in a frequent itemset is itself frequent. Thereby, the property "frequent" is monotone. From this, we can construct any frequent itemset from the empty set by adding items one-byone without passing through any infrequent itemset. Roughly speaking, the existing algorithms are classified into two groups, and algorithms in both groups use this property.

The first group is so called apriori or level-by-level algorithms [1,2]. Let D k be the set of frequent itemsets of size k. Apriori algorithms start with D 0 , that is {∅}, and compute D k from D k−1 in the increasing order of k from k = 1. Any itemset in D k is obtained from an itemset of D k−1 by adding an item. Apriori algorithms add every item to each itemset of D k−1 , and choose frequent itemsets among them. If D k = ∅ holds for some k, then D k = ∅ holds for any k > k. Thus, apriori algorithms stop at such k. This is the scheme of apriori algorithms.

The other group is so called backtracking algorithms [3,18,19]. Backtracking algorithm is based on recursive calls. An iteration of a backtracking algorithm inputs a frequent itemset P , and generates itemsets by adding every items to P . Then, for each itemset being frequent among them, the iteration generates recursive calls with respect to it. To avoid duplications, an iteration of backtracking algorithms adds items with indices larger than the tail of P . We describe the framework of backtracking algorithms as follows.

ALGORITHM BackTracking (P :current solution) 1. Output P 2. For each e ∈ I, e > tail(P ) do 3.

If P ∪ {e} is frequent then call BackTracking (P ∪ {e})

An execution of backtracking algorithms gives a tree structure such that the vertices of the tree are iterations, and edges connect two iterations if one of the iteration calls the other. If an iteration I recursively calls another iteration I , then we say that I is the parent of I , and I is a child of I. For an iteration, the itemset received from the parent is called the current solution.

Apriori algorithms use much memory for storing D k in memory, while backtracking algorithms use less memory since they keep only the current solution. Backtracking algorithms need no computation for maintaining previously obtained itemsets, so the computation time of backtracking algorithms is generally short. However, apriori algorithms have advantages for the frequency counting.

LCM algorithms are based on backtracking algorithms, and use an efficient techniques for the frequency counting, which are occurrence deliver and anytime database reduction described below. Hence, LCM algorithms compute the frequency efficiently without keeping previously obtained itemsets in memory.

Maintaining Databases

In the existing studies, database reduction is said to be important to reduce the computation time. It is to reduce the input database as the following rules:

1. remove each item included in less than θ transactions 2. remove each item included in all transactions 3. merge the identical transactions into one.

Database reduction performs well when the minimum support is large, and many existing algorithms use it. LCM algorithms also use database reduction.

In the existing studies, the input databases are often stored and maintained by using FP-tree (frequent pattern tree), which is a version of prefix tree (trie) [9]. By using FP-tree, we can search specified transactions from the datasets efficiently. FP-tree compresses the common prefix, so we can decrease the memory use. In addition, FP-tree can detect the identical transactions, thus we can merge them into one. This merge accelerates the frequency counting. From these reasons, FP-trees are used in many algorithms and implementations.

Although FP-tree has many good advantages, we do not use it in the implementation of LCM, but use simple arrays. The main reason is that LCM does not have to search transactions in the database. The main operation of LCM is tracing the transactions in the the denotation of the current solution. Thus, we do not need to use sophisticated data structures for searching.

The other reason is the computation time for the initialization. If we use a standard binary tree for implementing FP-tree, the initialization of the input database takes O(||T || + |T | log |T |) time. for constructing FP-tree in memory. Compared to this, LCM detects the identical transactions and stores the database in memory within linear time of the database size. This is because that LCM uses radix sort for this task, which sorts the transactions in a lexicographic order in linear time. In general, the datasets of data mining problems have many transactions, and each transaction has few items. Thus, ||T || is usually smaller than |T | log |T |, and LCM has an advantage. The constant factors of the computation time of binary tree operations are relatively larger than that of array operations. LCM also has an advantage at this point. Again, we recall that LCM never search the transactions, so each operation required by LCM can be done in constant time.

FP-tree has an advantage in reducing the memory use. This memory reduction can also reduce the computation time of the frequency counting. To check the efficiency of the reduction, we checked the reduction ratio by FP-tree for some datasets examined in FIMI03. The result is shown in Table 1. Each cell shows the ratio of the number of items needed to be stored by arrays and FP-tree. Usually, the input database is reduced in each iteration, hence we sum up the numbers over all iterations to compute the ratio. In the results of our experiments, the ratio was not greater 3 in many instances. If |I| is small, |T | is large, and the dataset has a randomness, such as accidents, the ratio was up to 6. Generally, a binary tree uses memory three times as much as an array. Thus, the performance of FP-tree seems to be not quite good rather than an array in both memory use and computation time, for many datasets.

Hypercube Decomposition

LCM finds a number of frequent itemsets at once for reducing the computation time [18]. Since the itemsets obtained at once compose a hypercube in the itemset lattice, we call the technique hypercube decomposition. For a frequent itemset P , let H(P ) be the set of items e satisfying e > tail(P ) and T (P ) = T (P ∪ {e}). Then, for any Q ⊆ H(P ), T (P ∪ Q) = T (P ) holds, and P ∪ Q is frequent. LCMfreq uses this property. For two itemsets P and P ∪ Q, we say that P is between P and P ∪ Q if P ⊆ P ⊆ P ∪ Q. In the iteration with respect to P , we output all P between P and P ∪ H(P ). This saves about 2 |H(P )| times of the frequency counting.

To avoid duplications, we do not generate recursive calls with respect to items included in H(P ). Instead of generating these recursive calls, we output frequent itemsets including items of H(P ) in recursive calls with respect to items not included in H(P ). When the algorithm generates a recursive call with respect to e ∈ H(P ), we pass H(P ) to it. In the recursive call, we output all itemsets between P ∪ {e} and P ∪ {e} ∪ H(P ) ∪ H(P ∪ {e}). Since any itemset Q satisfies T (P ∪ Q ∪ H(P )) = T (P ∪ Q), the itemsets output in the recursive calls are frequent. We describe hypercube decomposition as follows.

ALGORITHM HypercubeDecomposition

(P :current solution, S:itemset) S := S ∪ H(P ) Output all itemsets including P and included in P ∪ S For each item e ∈ I \ (P ∪ S ), e > tail(P ) do If P ∪ {e} is frequent then call HypercubeDecomposition (P ∪ {e}, S ) End for

Frequency Counting

Generally, the most heavy part of the frequent itemset mining is the frequency counting, which is to count the number of transactions including a newly generated itemset. To reduce the computation time, existing algorithms uses down project. For an itemset P , down project computes its denotation T (P ) by using two subsets P 1 and P 2 of P . If P = P 1 ∪ P 2 , then T (P ) = T (P 1 )∩T (P 2 ). Under the condition that the items of P 1 and P 2 are sorted by their indices, the intersection can be computed in O(|T (P 1 )| + |T (P 2 )|) time. Down project uses this property, and computes the denotations quickly. Moreover, if |T (P 1 )| < θ or |T (P 2 )| < θ holds, we can see that P never be frequent. It also helps to reduce the computation time.

Apriori-type algorithms accelerates the frequency counting by finding a good pair P 1 and P 2 of subsets of P , such that |T (P 1 )| + |T (P 2 )| is small, or either P 1 or P 2 is infrequent. Backtracking algorithm adds an item e to the current solution P in each iteration, and compute its denotation. By using T ({e}), the computation time for the frequency counting is reduced to O( e>tail(P

) (|T (P )| + |T ({e})|)).

The bitmap method [5] is a technique for speeding up the computation of taking the intersection in down project. It uses a bitmap image (the characteristic vector) of the denotations. To take the intersection, we have to take O(|T |) time with bitmap. However, a 32bit CPU can take the intersection of 32bits at once, thus roughly speaking the computation time is reduced to 1/32. This method has a disadvantage for sparse datasets, and is not orthogonal to anytime database reduction described in the below. From the results of the experiments in FIMI 03, bitmap method seems to be not good for sparse large datasets.

LCM algorithms use another method for the frequency counting, called occurrence deliver [18,19]. Occurrence deliver computes the denotations of P ∪ {e} for e = tail(P ) + 1, ..., |I| at once by tracing transactions in T (P ). It use a bucket for each e to be added, and set them to empty set at the beginning. Then, for each transaction t ∈ T (P ), occurrence deliver inserts t to the bucket of e for each e ∈ t, e > tail(P ). After these insertions, the bucket of e is equal to T (P ∪ {e}). 2. For each transaction t ∈ T (P ) do 3.

For each item e ∈ t, e > tail(P ) do 4.

Insert t to Bucket[e] 5.

End for 6. End for 7. Output Bucket[e] for all e > tail(P ) Let F (P ) be the set of items e such that e > tail(P ) and P ∪ {e} is frequent. Apriori algorithms have possibility to find out in short time that P ∪ {e} is infrequent, thus, in the best case, their computation time can be reduced to O( e∈F (P ) |T (P ∪{e})|). If e>tail(P ),e ∈F (P ) |T (P ∪ {e})| is large, occurrence deliver will be slow.

To decrease e>tail(P ),e ∈F (P ) |T (P ∪ {e})|, LCM algorithms sort indices of items e in the increasing order of |T ({e})|. As we can see in Table 1, this sort reduces e>tail(P ),e ∈F (P ) |T (P ∪ {e})| to 1/4 of e>tail(P ) |T (P ∪ {e})| in many cases. Since apriori algorithms take much time to maintain previously obtained itemsets, the possibility of speeding up by apriori algorithms is not so large.

LCM algorithms further speeds up the frequency counting by iteratively reducing the database. Suppose that an iteration I of a backtracking algorithm receives a frequent itemset P from its parent. Then, in any descendant iteration of I, no item of indices smaller than tail(P ) is added. Hence, any such item can be removed from the database while the execution of the descendant iterations. Similarly, the transactions not including P never include the current solution of any descendant iteration, thus such transactions can be removed while the execution of the descendant iterations. Indeed, infrequent items can be removed, and the identical transactions can be merged.

According to this, LCM algorithms recursively reduce the database while the execution of recursive calls. Before the recursive call, LCM algorithms generate a reduced database according to the above discussion, and pass it to the recursive call. We call this technique anytime database reduction.

Anytime database reduction reduces the computation time of the iterations located at the lower levels of the recursion tree. In the recursion tree, many iterations are on the lower levels and few iterations are on the upper levels. Thus, anytime database reduction is expected to be efficient. In our experiments, anytime database reduction works quite well. The following table shows the efficiency of anytime database reduction. We sum up over all iterations the sizes of the database received from the parent, in both cases with anytime database reduction and without anytime database reduction. Each cell shows the sum. The reduction ratio is large especially if the dataset is dense and the minimum support is large.

Prefix Preserving Closure Extension

Many existing algorithms for mining closed itemsets are based on frequent itemset mining. That is, the algorithms enumerate frequent itemsets, and output those being closed. This approach is efficient when the number of frequent itemsets and the number of frequent closed itemsets differ not so much. However, if the difference between them is large, the algorithms generate many non-closed frequent itemsets, LCM uses prefix preserving closure extension (ppcextension in short) for generating closed itemsets [18,19]. For a closed itemset P , we define the closure tail clo tail(P ) by the item i of the minimum index satisfying clo(P (i)) = P . clo tail(P ) is always included in P . We say that P is a ppc extension of P if P = clo(P ∪ {e}) and P (e − 1) = P (e − 1) hold for an item e > clo tail(P ). Let P 0 be the itemset satisfying T (P ) = T . Any closed itemset P = P 0 is a ppc extension of another closed itemset P , and such P is unique for P . Moreover, the frequency of P is strictly larger than P , hence ppc extension induces a rooted tree on frequent closed itemsets. LCM starts from P 0 , and finds all frequent closed itemsets in a depth first manner by recursively generating ppc extensions. The proof of ppc extension algorithms are described in [18,19].

By ppc extension, the time complexity is bounded by a linear function in the number of frequent closed itemsets. Hence, the computation time of LCM never be super linear in the number of frequent closed itemsets.

Closure Operation

To enumerate closed itemsets, we have to check whether the current solution P is a closed itemset or not. In the existing studies, there are two methods for this task. The first method is to store in memory previously obtained itemsets which are currently maximal among itemsets having the identical denotation. In this method, we find frequent itemsets one-by-one, and store them in memory with removing itemsets included in another itemset having the identical denotation. After finding all frequent itemsets, only closed itemsets remain in memory. We call this storage method. The second method is to gener-ate the closure of P . By adding to P all items e such that f rq(P ) = f rq(P ∪ {e}), we can construct the closure of P . We call the second closure operation.

LCM uses closure operations for generating ppc extensions. Similar to the frequency counting, we use database reduction for closure operation. Suppose that the current solution is P , the reduced database is composed of transactions S 1 , ..., S h , and each S l is obtained from transactions T l 1 , ..., T l k of the original database. For each S l , we define the interior intersection In(S l ) by T ∈{T l 1 ,...,T l k } T . Here the closure of P is equal to S∈{S1,...,S h } In(S). Thus, by using interior intersections, we can efficiently construct the closure of P .

When we merge transactions to reduce the database, interior intersections can be updated efficiently, by taking the intersection of their interior intersections. In the same way as the frequency counting, we can remove infrequent items from the interior intersections for more reduction. The computation time for the closure operation in LCM depends on the size of database, but not on the number of previously obtained itemsets. Thus, storage method has advantages if the number of frequent closed itemsets is small. However, for the instances with a lot of frequent closed itemsets, which take long time to be solved, LCM has an advantage.

Enumerating Maximal Frequent Itemsets

Many existing algorithms for maximal frequent itemset enumeration are based on the enumeration of frequent itemsets. In breadth-first manner or depthfirst manner, they enumerate frequent itemsets and output maximal itemsets among them. To reduce the computation time, the algorithms prune the unnecessary itemsets and recursive calls. Similar to these algorithms, LCMmax enumerates closed itemsets by backtracking, and outputs maximal itemsets among them. It uses a pruning to cut off unnecessary branches of the recursion. The pruning is based on a re-ordering of the indices of items, in each iteration. We explain the re-ordering in the following.

Let us consider a backtracking algorithm for enumerating frequent itemsets. Let P be the current solution of an iteration of the algorithm. Suppose that P is a maximal frequent itemset including P . LCMmax puts new indices to items with indices larger than tail(P ) so that any item in P has an index larger than any item not in P . Note that this reordering of indices has no effect to the correctness of the algorithm.

Let e > tail(P ) be an item in P , and consider the recursive call with respect to P ∪ {e}. Any frequent itemset P found in the recursive call is included in P , since every item having an index larger than e is included in P , and the recursive call adds to P items only of indices larger than e. From this, we can see that by the re-ordering of indices, recursive calls with respect to items in P ∩ H generates no maximal frequent itemset other than P .

According to this, an iteration of LCMmax chooses an item e * ∈ H, and generates a recursive call with respect to P ∪ {e * } to obtain a maximal frequent itemset P . Then, re-orders the indices of items other than e * as the above, and generates recursive calls with respect to each e > tail(P ) not included in P ∪ {e * }. In this way, we save the computation time for finding P , and by finding a large itemset, increase the efficiency of this approach. In the following, we describe LCMmax. H := H \ {e} 11.

ALGORITHM

LCMmax (P ∪ {e}, H ) 12. End for

Checking Maximality

When LCMmax finds a frequent itemset P , it checks the current solution is maximal or not. We call this operation maximality check. Maximality check is a heavy task, thus many existing algorithms avoid it. They store in memory maximal itemsets among previously obtained frequent itemsets, and update them when they find a new itemset. When the algorithms terminate and obtain all frequent itemsets, only maximal frequent itemsets remain in memory. We call this storage method. If the number of maximal frequent itemsets is small, storage method is efficient. However, if the number is large, storage method needs much memory. When a frequent itemset is newly found, storage method checks whether the itemset is included in some itemsets in the memory or not. If the number of frequent itemsets is large, the operation takes long time.

To avoid the disadvantage of storage method, LCMmax operates maximality check. LCMmax checks the maximality by finding an item e such that P ∪ {e} is frequent. If and only if such e exists, P is not maximal. To operate this efficiently, we reduce the database. Let us consider an iteration of LCMmax with respect to a frequent itemset P . LCM algorithms reduce the database by anytime database reduction for the frequency counting. Suppose that the reduced database is composed of transactions S 1 , ..., S h , and each S l is obtained by merging transactions T l 1 , ..., T l k of the original database. Let H be the set of items to be added in the iteration. Suppose that we remove all items e from H such that P ∪ {e} is infrequent. Then, for any l, T l

1 ∩ H = T l 2 ∩ H =, ..., = T l k ∩ H holds. For an item e and a transaction S l , we define the weight w(e, S l ) by the number of transactions in T l 1 , ..., T l k including e. Here the frequency of P ∪{e} is S∈{S1,...,S h } w(e, S). Thus, by using the weights, we can efficiently check the maximality, in linear time of the size of the reduced database.

When we merge transactions to reduce the database, the weights can be updated easily. For each item e, we take the sum of w(e, S) over all transactions S to be merged. In the same way as frequency counting, we can remove infrequent items from the database for maximality checking, for more reduction.

The computation time for maximality check in LCMmax depends on the size of database, but not on the number of previously obtained itemsets. Thus, storage method has advantages if the number of maximal frequent itemsets is small, but for the instances with a lot of maximal frequent itemsets, which take long time to be solved, LCMmax has an advantage.

Computational Experiments

In this section, we show the results of our computational experiments. We implemented our three algorithms LCM, LCMfreq, and LCMmax. They are coded by ANSI C, and complied by gcc. The experiments were executed on a notebook PC, with AMD athron XP 1600+ of 224MB memory. The performance of LCM algorithms are compared with the algorithms which marked good score on FIMI 03: fpgrowth [8], afopt [11], MAFIA [5,6], kDCI [12], and PATRICIAMINE [16]. We note that kDCI and PA-TRICIAMINE are only for all frequent itemset mining. To reduce the time for experiments, we stop the execution when an algorithm takes more than 10 minute. The following figures show the results. We do not plot if the computation time is over 10 minutes, or abnormal terminations. The results are displayed in Figure 1 and 2. In each graph, the horizontal axis is the size of minimum supports, and the virtical axis is the CPU time written in a log scale.

From the performances of implementations, the instances were classified into three groups, in which the results are similar. Due to the space limitation, we show one instance as a representative for each group.

The first group is composed of BMS-WebView1, BMS-WebView2, BMS-POS, T10I4D100K, kosarak, and retail. These datasets have many items and transactions but are sparse. We call these datasets sparse datasets. We chosen BMS-WebView2 as the representative.

The second group is composed of datasets taken from UCI-Machine Learning Repository 1 , connect, chess, mushrooms, pumsb, and pumsb-star. These datasets have many transactions but few items. We call these datasets middle density datasets. As a representative, we show the result of chess.

The third group is accidents. It is different from any other dataset. It has huge number of transactions, but few items. Transactions includes many items, so the dataset is very dense. We call this dataset very dense dataset.

In almost instances and minimum supports, LCM algorithms perform well. When the minimum support is large, LCM algorithms are the fastest for all instances, because of the fast initialization. For all instances with any minimum support, LCM outperforms other closed itemset mining algorithms. This shows the efficiency of ppc extension.

For sparse datasets, LCM algorithms are the fastest, for any minimum support. The efficiency of FP-tree is not large, and occurrence deliver works efficiently. The performances of afopt and fp-growth are quite similar for these problems. They are the second bests, and 2 to 10 times slower than LCM algorithms. For enumerating frequent closed itemsets, they take much time when the number of closed itemsets is large. Although PATRICIAMINE is fast as much as fp-groth and afopt, it abnormally terminated for some instances. kDCI is slow when the number of frequent itemsets is large. MAFIA was the slowest for these instances, for any minimum support.

For middle density datasets, LCM is the fastest for all instances on closed itemset mining. On all and maximal frequent itemset mining, LCMfreq and LCMmax are the fastest for large minimum supports, for any dataset. For small minimum supports, for half instances LCMfreq and LCMmax are the fastest. For the other instances, the results are case by case: each algorithm won in some cases.

For accidents, LCM algorithms are the fastest when the minimum support is large. For small supports, LCM(closed) is the fastest, however LCMfreq and LCMmax are slower than fp-growth For this dataset, the efficiency of FP-tree is large, and the compression ratio is up to 6. Bitmap is also efficient from the density. Hence, the computation time for the frequency counting is short in the execution of existing implementations. However, by ppc extension, LCM has an advantage for closed itemset mining. hence LCM(closed) is the fastest.

1 http://www.ics.uci.edu/ mlearn/MLRepository.html

Conclusion

In this paper, we proposed a fast implementation of LCM for enumerating frequent closed itemsets, which is based on prefix preserving closure extension. We further gave implementations LCMfreq and LCMmax for enumerating all frequent itemsets and maximal frequent itemsets by modifying LCM. We show by computational experiments that our implements of LCM, LCMfreq and LCMmax perform above the other algorithms for many datasets, especially for sparse datasets. There is a possibility of speeding up LCM algorithms by developing more efficient maximality checking algorithms, or developing a hybrid of array and FP-tree like data structures.