Nowadays basic algorithms such as Apriori and Eclat often are conceived as mere textbook examples without much practical applicability: in practice more sophisticated algorithms with better performance have to be used. We would like to challenge that point of view by showing that a carefully assembled implementation of Eclat outperforms the best algorithms known in the field, at least for dense datasets. For that we view Eclat as a basic algorithm and a bundle of optional algorithmic features that are taken partly from other algorithms like lcm and Apriori, partly new ones. We evaluate the performance impact of these different features and report about results of experiments that support our claim of the competitiveness of Eclat.
Algorithms for mining frequent itemsets often are presented in a monolithic way and labeled with a fancy name for marketing. Careful inspection often reveals similarities with other mining algorithms that allow the transfer from a smart solution of a specific (detail) problem in one algorithm to another one. We would like to go one step further and view such mining algorithms as a basic algorithm and a bundle of algorithmic features.
Basically, there are only two large families of mining
algorithms, Apriori [
In this paper, we would like to challenge that point of view by presenting an Eclat algorithm that for dense datasets outperforms all its more sophisticated competitors.
We will start with a formal outline of Eclat algorithm
in section 2. In section 3 we investigate several
algorithmic features of Eclat, partly gathered from other algorithms
as lcm, fpgrowth, and Apriori, partly new ones, review their
usefulness in Eclat and shortly discuss their possible
performance impact along with possible reasons thereof. In
section 4 we present an empirical evaluation of that impact as
well as a comparison with the competitor algorithms from
FIMI 03 mentioned above. – We will stick to Eclat. See
[
Let us fix notations for the frequent itemset mining problem in the rest of this section. Let A be a set, called set of items or alphabet. Any subset X ∈ P(A) of A is called an itemset. Let T ⊆ P (A) be a multiset of itemsets, called transaction database, and its elements T ∈ T called transactions. For a given itemset X ∈ P(A), the set of transactions that contain X
T (X) := {T ∈ T | X ⊆ T } is called (transaction) cover of X in T and its cardinality sup(X) := |T (X)|
T (absolute) support of X in T . An (all) frequent itemset mining task is specified by a dataset T and a lower bound minsup ∈ N on support, called minimum support, and asks for enumerating all itemsets with support at least minsup, called frequent or (frequent) patterns.
An itemset X is called closed, if
X = \ T (X) i.e., if any super-itemset of X has lower support. 2. Basic Eclat Algorithm
Most frequent itemset mining algorithms as Apriori [
For an itemset X ∈ P(A) an itemset Y ∈ P(A) with X ⊂ Y and X < Y is called an extension of X. An extension Y of X with Y = X ∪ {y} (and thus y > max X) is called an 1-item-extension of X. The extension relation organizes all itemsets in a tree, called extension tree or search tree.
Eclat starts with the empty prefix and the itemtransaction incidence matrix C∅, shortly called incidence matrix in the following, and stored sparsely as list of item covers: C∅ := {(x, T ({x})) | x ∈ A}. The incidence matrix is filtered to only contain frequent items by freq(C) := {(x, Tx) | (x, Tx) ∈ C, |Tx| ≥ minsup}. that represent frequent 1-item-extensions of the prefix. For any prefix p ∈ P(A) and incidence matrix C of frequent 1item-extensions of p one can compute the incidence matrix Cx of 1-item-extensions of p ∪ {x} by intersection rows:
Cx := {(y, Tx ∩ Ty) | (y, Ty) ∈ C, y > x} where (x, Tx) ∈ C is the row representing p ∪ {x}. Cx has to be filtered to get all frequent 1-item-extensions of p ∪ {x} and then this procedure is recursively iterated until the resulting incidence matrix Cx is empty, signaling that there are no further frequent 1-item-extensions of the prefix. See alg. 1 for an exact description of the Eclat algorithm.
The formal description of the Eclat algorithm in the last section allows us to point to several algorithmic features that this algorithm may have. These sometimes are described as implementation details, sometimes as extensions of Eclat, and sometimes as new algorithms.
Algorithm 1 Basic Eclat algorithm. input: alphabet A with ordering ≤ , multiset T ⊆ P (A) of sets of items, minimum support value minsup ∈ N. output: set F of frequent itemsets and their support counts.
F := {(∅, |T |)}.
C∅ := {(x, T ({x})) | x ∈ A}.
C∅0 := freq(C∅) := {(x, Tx) | |(Txx, |T≥x) m∈inCs∅u,p}.
F := {∅}. addFrequentSupersets(∅, C0 ).
∅ function addFrequentSupersets(): input: frequent itemset p ∈ P(A) called prefix, incidence matrix C of frequent 1-item-extensions of p. output: add all frequent extensions of p to global variable F . for (x, Tx) ∈ C do q := p ∪ {x}.
Cq := {(y, Tx ∩ Ty) | (y, Ty) ∈ C, y > x}.
Cq0 := freq(Cq) := {(y, Ty) | (y, Ty) ∈ Cq, |Ty| ≥ minsup}. if Cq0 6= ∅ then
addFrequentSupersets(q, Cq0 ). end if
F := F ∪ {(q, |Tx|)}.
end for
Before the first incidence matrix C∅ is built, it is
usually beneficial 1) to remove infrequent items from the
transactions, 2) to recode the items in the transaction database
s.t. they are sorted in a specific order, and 3) to sort the
transaction in that order. As implementations usually use
the natural order on item codes, item recoding affects the
order in which candidates are checked. There are several
recodings used in the literature and in existing
implementations of Eclat and other algorithms as Apriori (see e.g.,
[
One of the major early improvements of Eclat algorithms
has been the replacement of item covers in incidence
matrices by their relative complement in its superpattern, so
called diffsets, see [
Dx := {(y, Tx \ Ty) | (y, Ty) ∈ C, y > x} From an incidence matrix D of item defects and one of its 1-item-extensions (x, Tx) ∈ D of its prefix we can derive the incidence matrix Dx of item defects of this extension by
Dx := {(y, Ty \ Tx) | (y, Ty) ∈ D, y > x} If we expand first by x and then by y in the second step, we loose transactions that not contain y unless we have lost them before as they did not contain x.
Defects computed from covers may have at most size maxdefp := |T (p)| − minsup, those computed recursively from other defects at most size maxdefp∪{x} := maxdefp −|T x| 1-item-extensions exceeding that maximal defect are removed by a filter step: freq(D) := {(x, Tx) | (x, Tx) ∈ C, |Tx| ≤ maxdef}.
Computing intersections of covers or set differences for defects are computationally equivalent complex tasks. Thus, the usage of defects can improve performance only by leading to smaller incidence matrices. For dense datasets where covers overlap considerably, intersection reduces the size of the incidence matrix only slowly, while defects cut down considerably. On the other side, for sparse data using defects may deteriorate the performance. – Common items in covers also can be removed by omitting equisupport extensions (see section 3.5).
While there is an efficient transition from covers to defects as given by the formula above, the reverse transition from defects to covers seems hard to perform efficiently as all defects on the path to the root of the search tree would have to be accumulated.
Regardless which type of incidence matrix is used, it can
be stored as sparse matrix (i.e., as list of lists as discussed
so far) or as dense (bit)matrix (used e.g, by [
A third alternative for keeping track of item-transaction
incidences is not to store item covers as a set of incident
transaction IDs per 1-item-extension, but to store all
transactions T (p) that contain a given prefix p in a trie (plus
some index structure, known as frequent pattern tree and
first used in fp-growth; see [
For both incidence matrices, covers and defects, two different ways of computing the operator that derives an incidence matrix from a given incidence matrix recursively, i.e., intersection and set difference, respectively, can be chosen. The straightforward way is to implement both operators as set operators operating on the sets of transaction IDs.
Alternatively, intersection and difference of several sets
Ty, y > x of transactions by another set Tx of transactions
also can be computed in parallel using the original
transaction database by counting in IDs of matching transactions
(called occurrence deliver in [
0 Similar, to compute Ty0 := Tx \ Ty for several y > x one computes ∀T ∈ Tx∀y 6∈ T : Ty0 := Ty ∪ {T }.
0 3.4. Initial Incidence Matrix
Basic Eclat first builds the incidence matrix C∅ of single item covers as initial incidence matrix and then recursively derives incidence matrices Cp of covers of increasing prefixes p or Dp of defects.
Obviously, one also can start with D∅, the matrix of item cover complements. This seems only useful for very dense datasets as it basically inverts the encoding of item occurrence and non-occurrence (dualization).
It seems more interesting to start already with incidence matrices for 1-item-prefixes, i.e., not to use Eclat computation schemes for the computation of frequent pairs, but count them directly from the transaction data. For Apriori this is a standard procedure. The cover incidence matrix Cx = {(y, Ty)} for an frequent item x, i.e., Ty = T ({x}) ∩ T ({y}), is computed as follows:
∀T ∈ T : if x ∈ T : ∀y ∈ T, y > x : Ty := Ty ∪ {T }. The test for x ∈ T looks worse than it is in practice: if transactions are sorted, items x are processed in increasing order, and deleted from the transaction database after computation of Cx, then if x is contained in a transaction T it has to be its first item.
Similarly, a defect incidence matrix Dx = {(y, Ty)} for a frequent item x, i.e., Ty = T ({x}) \ T ({y}), can be computed directly from the transaction database by ∀T ∈ T : if x ∈ T : ∀y 6∈ T, y > x : Ty := Ty ∪ {T }.
If Cx or Dx is computed directly from the transaction database, then it has to be filtered afterwards to remove infrequent extensions. An additional pass over T in advance can count pair frequencies for all x, y in parallel, so that unnecessary creation of covers or defects of infrequent extensions can be avoided. 3.5. Omission of Equisupport Extensions
Whenever an extension x has the same support as its prefix p, it is contained in the closure T T (p) of the prefix. That means that one can add any such equisupport extension to any extension of p without changing its support; thus, one can omit to explicitly check its extensions. Equisupport extensions can be filtered out and kept in a separate list E for the active branch: whenever an itemset X is output, all its 2|E| supersets X0 ⊆ X ∪ E are also output.
Omission of equisupport extensions is extremely cheap to implement as it can be included in the filtering step that has to check support values anyway. For dense datasets with many equisupport extensions, the number of candidates that have to be checked and accordingly the runtime can be reduced drastically. 3.6. Interleaving Incidence Matrix Computation and Filtering
When the intersection Tx ∩ Ty of two sets of transaction IDs is computed, we are interested in the result of this computation only if it is at least of size minsup, as otherwise it is filtered out in the next step. As the sets of transactions are sorted, intersections are computed by iterating over the lists of transaction IDs and comparing items. Once one of the tails of the lists to intersect is shorter than minsup minus the length of the intersection so far, we can stop and drop that candidate, as it never can become frequent. – For set difference of maximal length maxdef a completely analogous procedure can be used. 3.7. Omission of Final Incidence Matrix Derivation
Finally, once the incidence matrix has only two rows, the result of the next incidence matrix derivation will be an incidence matrix with a single row. As this is only checked for frequency, but its items are not used any further, we can omit to generate the list of transaction IDs and just count its length. 3.8. IO
So far we have investigated features that are specific to
Eclat and the frequent itemset mining problem. Though
these specific algorithmic features are what should be of
primary interest, we noticed in our experiments, that
often different IO mechanism dominate runtime behavior. At
least three output schemes are implemented in several of
the algorithms available: IO using C++ streams, IO using
printf, and IO using handcrafted rendering of integer
itemsets to a char buffer and writing that buffer to files using
low-level fwrite (for the latter see e.g., the
implementation of lcm, [
By evaluating different features of Eclat we wanted to answer two questions: 1. What features will make Eclat run fastest? Especially, what is its marginal runtime improvement of each feature in a sophisticated Eclat implementation? 2. Is Eclat competitive compared with more complex algorithms?
To answer the question about the runtime improvement of the different features, we implemented a modular version of Eclat in C++ (basically mostly plain C) that allows the flexible inclusion or exclusion of different algorithmic features. At the time of writing the following features are implemented: the incidence structure types covers and diffsets (COV, DIFF), transaction recoding (none, decreasing, increasing; NREC, RECDEC, RECINC), omission of equisupport extensions (NEE), interleaving incidence matrix computation and filtering (IFILT), and omission of final incidence matrix (NFIN). As initial incidence matrix alway covers of frequent 1-itemsets (C∅) was used.
To measure the marginal runtime improvement of a feature we configured a sophisticated Eclat algorithm with all features turned on (SOPH:= DIFF, RECINC, NEE+, IFILT+, NFIN+) and additionally for each feature an Eclat algorithm derived from SOPH by omitting this feature (SOPH-DIFF, SOPH-RECINC (decreasing encoding), SOPH-REC (no recoding at all), SOPH-NEE+, SOPHIFILT+, SOPH-NFIN+).
We used several of the data sets and mining
tasks that have been used in the FIMI-03 workshop
([
A sample from the results of these experiments can be seen in fig. 1 (the remaining charts can be found at http://www.informatik.uni-freiburg.de/cgnm/papers/fimi04). One can see some common behavior across datasets and mining tasks: • For dense mining tasks like accidents, chess, etc.
SOPH is the best configuration. • For sparse mining tasks like retail, T20I10N1KP5KC0-25D200K etc. SOPH-diff is the best configuration, i.e., using defects harms performance here – both effects are rather distinct. • Recoding is important and shows a huge variety w.r.t. runtime: compare e.g., decreasing and no encoding for connect: the natural encoding is not much worse than decreasing encoding, but the curve for increasing encoding shows what harm the wrong encoding can do: note that the natural encoding is close to optimal only by mere chance and could be anywhere between increasing and decreasing! • Omitting equisupport extensions also shows a clear benefit for most mining tasks, with exception for mushroom. • Compared with other features, the impact of the features IFILT and NFIN is neglectible.
To answer the second question about competitiveness of
Eclat compared with more advanced frequent pattern
mining algorithms we have chosen the four best-performing
algorithms from the FIMI-03 workshop: patricia, kdci, lcm,
and fpgrowth* (see [
Again, a sample from the results of these experiments can be seen in fig. 2 (the remaining charts also can be found at http://www.informatik.uni-freiburg.de/cgnm/papers/fimi04). For several datasets (chess, connect, mushroom, pumsb, and – not shown – pumsbstar), Eclat-SOPH is faster than all other algorithms. For some datasets it is faster for high minimum support values, but beaten by fpgrowth* when support values get smaller (accidents, T30I15N1KP5KC0-25D200K) and for some datasets its performance is really poor (retail, T20I10N1KP5KC0-25D200K, and – not shown – kosarak and T10I5N1KP5KC0.25D200K). We can draw two conclusions from this observations: 1) at least for dense datasets, Eclat-SOPH is faster than all its competitors, 2) for sparse datasets, Eclat-SOPH is not suitable. Recalling our discussion on the potential of using defects instead of covers and on starting with frequent 2-itemsets instead of with frequent 1-itemsets, the latter conclusion is not very surprising.
There are at least four more features we do not have investigated yet: using tries to store the transaction covers, the method to compute the initial incidence matrix, pruning, and memory management. Our further research will try to address questions about the impact of these features.
This update of optimization for dense datasets has to be complemented with research in performance drivers for sparse datasets. As can be seen from our results, Eclat seems not suited well for that task. Though using covers instead of defects improves performance, it still is not competitive with other algorithms in the field.
Furthermore, results for dense datasets will have to be compared with that of the next generation of mining algorithms we expect as outcome of FIMI’04 and eventually new features of these algorithms have to be integrated in Eclat. We expect both, that Eclat is clearly beaten at FIMI’04 as well that it will be not too hard to identify the relevant features and integrate them in Eclat. eclat−SOPH eclat−SOPH−diff eclat−SOPH−nee eclat−SOPH−rec eclat−SOPH−recinc eclat−SOPH−ifilt eclat−SOPH−nfin ● 0.8 eclat−SOPH eclat−SOPH−diff eclat−SOPH−nee eclat−SOPH−rec eclat−SOPH−recinc eclat−SOPH−ifilt eclat−SOPH−nfin 0.4 0.6 minimum support 0.10 0.15 minimum support 10^0.5 10^0.0 10^−0.5 ● ●
● ● ● ● ●
pumsb ●● ●● ● ●● ●● ● ● ●● 0.2 10^−1.0 10^1.5 ] s [ e m it n u r10^1.0 10^0.5 10^0.0 10^2.0 ● ● 0.002 0.004 0.006 minimum support 0.008 0.010 0.01 0.04
0.05 0.02 0.03 minimum support chess 0.3 0.4 0.5
0.6 0.7 minimum support 0.9 0.6 0.7
0.8 minimum support retail ●
●● ● ● eclat−SOPH eclat−SOPH−diff eclat−SOPH−nee eclat−SOPH−rec eclat−SOPH−recinc eclat−SOPH−ifilt eclat−SOPH−nfin ● 0.8 eclat−SOPH eclat−SOPH−diff eclat−SOPH−nee eclat−SOPH−rec eclat−SOPH−recinc eclat−SOPH−ifilt eclat−SOPH−nfin ● ● ● ● ● 0.9 10^0.5 chess 0.4 0.6 minimum support pumsb 0.2 0.8 0.3 0.4 0.8 0.9 0.6 patricia kdci lcm fpgrowthpp eclat−lst ● ● 0.7
0.8 minimum support
0.9 retail patricia kdci lcm fpgrowthpp eclat−lst 10^3 10^2 ] s [ e m it n u r 10^1 10^0 10^1.0 10^0.5 10^−0.5 10^−1.0 10^2.0 10^1.5 ] s [ e m i tn10^1.0 u r 10^0.5 patricia kdci lcm fpgrowthpp eclat−lst patricia kdci lcm fpgrowthpp eclat−lst patricia kdci lcm fpgrowthpp eclat−lst ● ● ● 10^2 10^1 ] s [ e im10^0 t n u r 10^−1 10^−2 10^2.0 10^1.5 10^1.0 ] s [ e m it run10^0.5 10^0.0 10^−0.5 10^2.0 10^1.5 10^1.0 ] s [ e m it n ru10^0.5 10^0.0 10^−0.5 0.05 0.10 0.15 minimum support 0.20 0.6 0.7
0.8 minimum support 0.9 0.0002 0.0004 0.0006 minimum support 0.0008 0.0010 10^0.5 10^0.0 patricia kdci lcm fpgrowthpp eclat−lst ● 10^1.5