For a transaction database, a frequent itemset is an itemset included in at least a speci ed number of transactions. A frequent itemset P is maximal if P is included in no other frequent itemset, and closed if P is included in no other itemset included in the exactly same transactions as P . The problems of nding these frequent itemsets are fundamental in data mining, and from the applications, fast implementations for solving the problems are needed. In this paper, we propose e cient algorithms LCM (Linear time Closed itemset Miner), LCMfreq and LCMmax for these problems. We show the e ciency of our algorithms by computational experiments compared with existing algorithms.
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[
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 di sets. They reduce the practical computation time e ciently. 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 modi cations 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 e cient 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. 2
Let I = f1; :::; ng be the set of items. A transaction database on I is a set T = ft1; : : : ; tmg such that each ti is included in I. Each ti is called a transaction. We denote by jjT jj 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 . jT (P )j 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 satis es 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) =
TT 2S T . Then, we de ne the closure of itemset P
in T , denoted by clo(P ), by I(T (P ))(= Tt2T (P ) t).
For every pair of itemsets P and Q, the following
properties hold[
(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 2 P , let P (i) = P \ f1; : : : ; ig be the subset of P consisting only of elements no greater than i, called the i-pre x of P . An itemset Q is a closure extension of an itemset P if Q = clo(P [ fig) holds for some i 62 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 ). 3
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 new techniques used in the second version are: 3.2. new database reduction (reduce the frequency counting cost) 3.6. database reduction for fast checking closedness 3.8. database reduction for fast checking maximality 3.7. new pruning algorithm for backtracking-based maximal frequent itemset mining.
The techniques also used in the rst versions are: 3.4. occurrence deliver (compute frequency in linear time) 3.5. ppc extension (generates closed itemsets with neither memory nor duplication) 3.3. hypercube decomposition (fast enumeration by grouping frequent itemsets by equivalence class).
The techniques used in the existing algorithms and the rst version have citations to the previous papers. 3.1
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 classied into two groups, and algorithms in both groups use this property.
The rst group is so called apriori or level-by-level algorithms [1, 2]. Let Dk be the set of frequent itemsets of size k. Apriori algorithms start with D0, that is f;g, and compute Dk from Dk 1 in the increasing order of k from k = 1. Any itemset in Dk is obtained from an itemset of Dk 1 by adding an item. Apriori algorithms add every item to each itemset of Dk 1, and choose frequent itemsets among them. If Dk = ; holds for some k, then Dk0 = ; holds for any k0 > k. Thus, apriori algorithms stop at such k. This is the scheme of apriori algorithms.
The other group is so called backtracking
algorithms[
ALGORITHM BackTracking (P :current solution) 1. Output P 2. For each e 2 I; e > tail(P ) do 3. If P [ feg is frequent then
call BackTracking (P [ feg)
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 0, then we say that I is the parent of I0, and I0 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 Dk 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 e cient techniques for the frequency counting, which are occurrence deliver and anytime database reduction described below. Hence, LCM algorithms compute the frequency e ciently without keeping previously obtained itemsets in memory. 3.2
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 pre x tree
(trie) [
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(jjT jj + jT j log jT j) 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, jjT jj is usually smaller than jT j log jT j, 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 e ciency 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 jIj is small, jT j 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. 3.3
LCM nds a number of frequent itemsets at once for
reducing the computation time[
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 62 H(P ); we pass H(P ) to it. In the recursive call, we output all itemsets between P [ feg and P [ feg [ H(P ) [ H(P [ feg). Since any itemset Q satis es 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) S0 := S [ H(P ) Output all itemsets including P
and included in P [ S0 For each item e 2 I n (P [ S0), e > tail(P ) do If P [ feg is frequent then
call HypercubeDecomposition (P [ feg; S0) End for 3.4
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 P1 and P2 of P . If P = P1 [ P2, then T (P ) = T (P1)\T (P2). Under the condition that the items of P1 and P2 are sorted by their indices, the intersection can be computed in O(jT (P1)j + jT (P2)j) time. Down project uses this property, and computes the denotations quickly. Moreover, if jT (P1)j < or jT (P2)j < 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 nding a good pair P1 and P2 of subsets of P , such that jT (P1)j + jT (P2)j is small, or either P1 or P2 is infrequent. Backtracking algorithm adds an item e to the current solution P in each iteration, and compute its denotation. By using T (feg), the computation time for the frequency counting is reduced to O(Pe>tail(P )(jT (P )j + jT (feg)j)).
The bitmap method[
LCM algorithms use another method for the
frequency counting, called occurrence deliver[
ALGORITHM OccurrenceDeliver
(T:database, P :itemset) 1. Set Bucket[e] := ; for each item e > tail(P ) 6.01
1
Let F (P ) be the set of items e such that e > tail(P ) and P [ feg is frequent. Apriori algorithms have possibility to nd out in short time that P [ feg is infrequent, thus, in the best case, their computation time can be reduced to O(Pe2F (P ) jT (P [feg)j). If Pe>tail(P );e62F (P ) jT (P [ feg)j is large, occurrence deliver will be slow.
To decrease Pe>tail(P );e62F (P ) jT (P [ feg)j; LCM algorithms sort indices of items e in the increasing order of jT (feg)j. As we can see in Table 1, this sort reduces Pe>tail(P );e62F (P ) jT (P [ feg)j to 1/4 of Pe>tail(P ) jT (P [ feg)j 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 e cient. In our experiments, anytime database reduction works quite well. The following table shows the e ciency 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. 3.5
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 e cient when the number of frequent itemsets and the number of frequent closed itemsets di er not so much. However, if the di erence between them is large, the algorithms generate many non-closed frequent itemsets, thus they will be not e cient. Many pruning methods have been developed for speeding up, however they are not complete. Thus, the computation time is not bounded by a linear function in the number of frequent closed itemsets. There is a possibility of over linear increase of computation time in the number of output.
LCM uses pre x preserving closure extension
(ppcextension in short) for generating closed itemsets[
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. 3.6
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 rst method is to store in memory previously obtained itemsets which are currently maximal among itemsets having the identical denotation. In this method, we nd frequent itemsets one-by-one, and store them in memory with removing itemsets included in another itemset having the identical denotation. After nding all frequent itemsets, only closed itemsets remain in memory. We call this storage method. The second method is to generate the closure of P . By adding to P all items e such that f rq(P ) = f rq(P [ feg), 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 S1; :::; Sh, and each Sl is obtained from transactions T1l; :::; Tkl of the original database. For each Sl, we de ne the interior intersection In(Sl) by TT 2fT1l;:::;Tklg T . Here the closure of P is equal to TS2fS1;:::;Shg In(S). Thus, by using interior intersections, we can e ciently construct the closure of P .
When we merge transactions to reduce the database, interior intersections can be updated e ciently, 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. 3.7
Many existing algorithms for maximal frequent itemset enumeration are based on the enumeration of frequent itemsets. In breadth- rst manner or depthrst 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 o 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 0 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 0 has an index larger than any item not in P 0. Note that this reordering of indices has no e ect to the correctness of the algorithm.
Let e > tail(P ) be an item in P 0, and consider the recursive call with respect to P [ feg. Any frequent itemset P^ found in the recursive call is included in P 0, since every item having an index larger than e is included in P 0, 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 0 \ H generates no maximal frequent itemset other than P 0.
According to this, an iteration of LCMmax chooses an item e 2 H, and generates a recursive call with respect to P [ fe g to obtain a maximal frequent itemset P 0. 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 0 [ fe g. In this way, we save the computation time for nding P 0, and by nding a large itemset, increase the e ciency of this approach. In the following, we describe LCMmax.
ALGORITHM LCMmax (P :itemset, H:items to be added) 1. H0 := the set of items e in H s.t. P [ feg is frequent 2. If H0 = ; then 3. If P [ feg is infrequent for any e then output P ; return 4. End if 5. End if 6. Choose an item e 2 H0 ; H0 := H0 n fe g 7. LCMmax (P [ feg, H0) 8. P 0 := frequent itemset of the maximum size found in the recursive call in 7 9. For each item e 2 H n P 0 do 10. H0 := H0 n feg 11. LCMmax (P [ feg, H0) 12. End for 3.8
When LCMmax nds 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 nd 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 e cient. 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 nding an item e such that P [ feg is frequent. If and only if such e exists, P is not maximal. To operate this e ciently, 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 S1; :::; Sh, and each Sl is obtained by merging transactions T1l; :::; Tkl 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 [ feg is infrequent. Then, for any l; T1l \ H = T2l \ H =; :::; = Tkl \ H holds. For an item e and a transaction Sl, we de ne the weight w(e; Sl) by the number of transactions in T1l; :::; Tkl including e. Here the frequency of P [feg is PS2fS1;:::;Shg w(e; S). Thus, by using the weights, we can e ciently 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. BBBMMMSSS--W-WWeebebVbVVieieiweww--2-2-2-a-alalll BBBMMMSSS--W-WWeebebVbVVieieiweww--2-2-2-c-clcololsosesededd afaofapoftpo_tpa_tla_llal ll afopt_all fpfgpf_gpa_gla_llal ll fpg_all lclmcm_a_lal ll lcm_all mafia_all mafia_all dci_all dci_all patriciamine_all 10100 ) c e s ( e m it u p c 100 10 1 afaofapoftpo_tpc_tlc_olcsolesodesded fpfgpf_gpc_glc_olcsolesodesded lclmcm_c_lcolsoesded mafia_closed
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[
From the performances of implementations, the instances were classi ed 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 rst 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 10100 10
1 )c 10 e s ( e m it u p 1 c
0.1 0.101
9090 100 )c 10 e s ( e m it u p 1 c 0.1 1000 )c 100 e s ( e 10 m it u p 10 c afaofpotp_ta_lal ll afopt_all fpfgp_ga_lal ll fpg_all lcm_all lcm_all mafia_all mafia_all dci_all dci_all patriciamine_all afopt_maximal fpg_maximal lcm_maximal mafia_maximal afaofpotp_tc_lcolsoesded fpfgp_gc_lcolsoesded lcm_closed mafia_closed 8800 7700 6600 5500 4400 30 20 90 8800 7070 60 60 50 5040 4300 230 mmininssuupp((%%)) chess-maximal 90 80 70 40 30 20 60
50 minsup (%) aaccccidideenntsts--cclolosseedd 11 9090 8800 7700 6600 5500 4400 3300 20 10 mmininssuupp((%%)) accidents-maximal 80 7700 6060 50 50 40 4030 3200 120 80 70 60 50 40 30 20 10 0.1 1000 )c 100 e s ( e 10 m it u p 10 c
1000 )c 100 e s ( e m it u p 10 c afopt_closed fpg_closed lcm_closed mafia_closed minsup (%) aaccccidideenntsts--aalll afaofpotp_ta_lal ll afopt_all fpfgp_ga_lal ll fpg_all lcm_all lcm_all mafia_all mafia_all dci_all dci_all patriciamine_all afopt_maximal fpg_maximal lcm_maximal mafia_maximal from UCI-Machine Learning Repository1, 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 di erent 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 e ciency of ppc extension.
For sparse datasets, LCM algorithms are the fastest, for any minimum support. The e ciency of FP-tree is not large, and occurrence deliver works efciently. 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 e ciency of FP-tree is large, and the compression ratio is up to 6. Bitmap is also e cient 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.
1http://www.ics.uci.edu/ mlearn/MLRepository.html
In this paper, we proposed a fast implementation of LCM for enumerating frequent closed itemsets, which is based on pre x 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 e cient maximality checking algorithms, or developing a hybrid of array and FP-tree like data structures.
This research is supported by joint-research funds of National Institute of Informatics.
[1] R. Agrawal and R. Srikant, \Fast Algorithms for Mining Association Rules in Large Databases," In Proceedings of VLDB '94, pp. 487{499, 1994. [2] R. Agrawal, H. Mannila, R. Srikant, H. Toivonen and A. I. Verkamo, \Fast Discovery of Association Rules," In Advances in Knowledge Discovery and Data Mining, MIT Press, pp. 307{328, 1996. [3] R. J. Bayardo Jr., \E ciently Mining Long Patterns from Databases", In Proc. SIGMOD'98, pp. 85{93, 1998. [4] E. Boros, V. Gurvich, L. Khachiyan, and K. Makino, \On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets," STACS 2002, pp. 133-141, 2002.