One of the main problems raising up in the frequent closed itemsets mining problem is the duplicate detection. In this paper we propose a general technique for promptly detecting and discarding duplicate closed itemsets, without the need of keeping in the main memory the whole set of closed patterns. Our approach can be exploited with substantial performance benefits by any algorithm that adopts a vertical representation of the dataset. We implemented our technique within a new depth-first closed itemsets mining algorithm. The experimental evaluation demonstrates that our algorithm outperforms other state of the art algorithms like CLOSET+ and FPCLOSE.
Frequent itemsets mining is the most important and demanding task in many data mining applications. To describe the mining problem we introduce the following notation. Let I = {a1, ..., aM } be a finite set of items, and D a finite set of transactions (the dataset), where each transaction t ∈ D is a list of distinct items t = {i0, i1, ..., iT }, ij ∈ I. A k-itemset is a sequence of k distinct items I = {i0, i1, ..., ik} | ij ∈ I, sorted on the basis of some total order relation between item literals. The number of transactions in the dataset including an itemset I is defined as the support of I (or supp(I)). Mining all the frequent itemsets from D requires to discover all the itemsets having support higher than (or equal to) a given threshold min supp.
The paper is organized as follows. In Sect. 2 we introduce closed itemsets and describe a framework for mining them. This framework is shared by all the algorithms surveyed in Sect. 3. In Sect. 4 we formalize the problem of duplicates and propose our technique. Section 5 proposes an implementation of our technique and discusses the experimental results obtained. Follow some concluding remarks. 2.
The concept of closed itemset is based on the two following functions f and g: f (T ) = {i ∈ I | ∀t ∈ T, i ∈ t} g(I) = {t ∈ D | ∀i ∈ I, i ∈ t} where T and I, T ⊆ D and I ⊆ I are, respectively, subsets of all the transactions and items occurring in dataset D. Function f returns the set of itemsets included in all the transactions in T , while function g returns the set of transactions supporting a given itemset I. Since the set of transaction g(I) can be represented by a list of transaction identifiers, we refer to g(I) as the tid-list of I. We can introduce the following definition: Definition 1 An itemset I is said to be closed if and only if c(I) = f (g(I)) = f ◦ g(I) = I where the composite function f ◦ g is called Galois operator or closure operator.
The closure operator defines a set of equivalence classes over the lattice of frequent itemsets: two itemsets belong to the same equivalence class iff they have the same closure, i.e. they are supported by the same set of transactions. We can also show that an itemset I is closed if no superset of I with the same support exists. Thus, a closed itemset is also the maximal itemset of an equivalence class. Mining all these maximal elements of each equivalence class corresponds to mine all the closed itemsets.
The algorithms for mining frequent closed itemsets adopt a strategy based on two main steps: Search space browsing, and Closure calculation. In fact, they browse the search space by traversing the lattice of frequent itemsets from an equivalence class to another, and they calculate the closure of the frequent itemsets visited in order to determine the maximal elements (closed itemsets) of the corresponding equivalence classes. Let us analyze in some depth these two phases.
Browsing the search space. The goal of an effective browsing strategy should be to devise a spanning tree over the lattice of frequent itemsets, visiting exactly a single itemset in each equivalence class. We could in fact mine all the closed itemsets by calculating the closure of just an itemset per equivalence class. Let us call the itemsets used to compute closures during the visit closure generators.
Some algorithms choose the minimal elements (or key patterns) of each equivalence class as closure generators. Key patterns form a lattice, and this lattice can be easily traversed with a simple apriori-like algorithm. Unfortunately, an equivalence class can have more than one minimal element leading to the same closed itemset. For example, the closed itemset {ABCD} of Fig. 1 may be mined twice, since it can be obtained as closure of the two minimal elements of its equivalence class {AD} and {CD}.
Other algorithms use instead a different technique that we call closure climbing. As soon as a generator is devised, its closure is computed, and new generators are built as supersets of the closed itemset discovered. Since closed itemsets are maximal elements, this strategy always guarantees to jump from an equivalence class to another. Unfortunately, it does not guarantee that the new generators belong to equivalence classes that were not previously visited.
Regardless of the strategy adopted, some kind of duplicate check has thus to be introduced. A naive approach to check for duplicates is to search for each generated closed itemset among all the ones mined so far. Indeed, in order to avoid to perform a lot of expensive closure operations, several algorithms exploit the following lemma: Lemma 1 Given two itemsets X and Y , if X ⊂ Y and supp(X) = supp(Y ) (i.e. |g(X)| = |g(Y )|), then c(X) = c(Y ).
Proof. If X ⊂ Y , then g(Y ) ⊆ g(X). Since |g(Y )| = |g(X)| then g(Y ) = g(X). g(X) = g(Y ) ⇒ f (g(X)) = f (g(Y )) ⇒ c(X) = c(Y ).
Therefore, given a generator X, if we find an already mined closed itemsets Y that set-includes X, AB 2
AC 2 A 2
TID and the supports of Y and X are identical, we can conclude that c(X) = c(Y ). Hence we can prune the generator X without actually calculating its closure. Also this duplicates checking strategy is however expensive, both in time and space. In time because we may need to search for the inclusion of each generator in a huge number of closed itemsets, in space because to perform it we need to keep all the closed itemsets in the main memory. To reduce such costs, closed sets can be stored in compact prefix tree structures, indexed by one or more levels of hashing.
Calculating Closures. To calculate the closure of an itemset X, we have to apply the Galois operator c. Applying c requires to intersect all the transactions of the dataset including X. Another way to calculate the closure is given by the following lemma: Lemma 2 Given an itemset X and an item i, if g(X) ⊆ g(i) ⇒ i ∈ c(X).
Proof. Since g(X ∪ i) = g(X) ∩ g(i), g(X) ⊆ g(i) ⇒ g(X ∪ i) = g(X). Therefore, if g(X ∪ i) = g(X) then f (g(X ∪ i)) = f (g(X)) ⇒ c(X ∪ i) = c(X) ⇒ i ∈ c(X).
From the above lemma, we know that if g(X) ⊆ g(i), then i ∈ c(X). Therefore, by performing this inclusion check for all the items in I not included in X, we can incrementally compute c(X). Note that, since the set g(i) can be represented by the tid-list associated with i, this suggests the adoption of a vertical format for the input dataset in order to efficiently implement the inclusion check: g(X) ⊆ g(i).
The closure calculation can be performed off-line or on-line. In the first case we firstly retrieve the complete set of generators, and then we calculate their closures. In the second case, as soon as a new generator is discovered, its closure is computed on-the-fly.
The algorithms that compute closures on-line are generally more efficient. This is because they can adopt the closure climbing strategy, according to which new generators are created recursively from closed itemsets. These generators are likely longer than key patterns, which are the minimal itemsets of the equivalence class and thus are the shorter possible generators. Obviously, the longer the generator is, the fewer checks (on further items to add) are needed to get its closure.
The first algorithm proposed for mining closed
itemsets was A-CLOSE [
The authors of FP-Growth [
FPCLOSE [
CHARM [
According to our classification, A-CLOSE exploits a key pattern browsing strategy and performs off-line closure calculations, while CHARM, CLOSET+ and FPCLOSE are different implementations of the same closure climbing strategy with incremental closure computation. that do not result order preserving according to the definition below.
Definition 2 A generator X = Y ∪ i, where Y is a closed itemset and i 6∈ Y , is said to be order preserving one iff i ≺ (c(X) \ X).
The following Theorem shows that, for any closed itemset Y , it is possible to find a sequence of order preserving generators in order to climb a sequence of closure itemsets and arrive at Y . The following Corollary states that this sequence is unique.
Theorem 1 For each closed itemset Y 6= c (∅), there exists a sequence of n (n ≥ 1) items i0 ≺ i1 ≺ ... ≺ in−1 such that generators of {gen0, gen1, . . . , genn−1} = {Y0∪i0, Y1∪i1, . . . , Yn−1∪in−1}
In this Section we discuss a particular visit of the lattice of frequent sets used by our algorithm to identify unique generators of each equivalence class, and compute all the closed patterns through the minimum number of closure calculations.
In our algorithm, we use closure climbing to browse the search space, find generators and compute their closure. As soon as a generator is found, its closure is computed, and new generators are built as supersets of the closed itemset discovered so far. So, each generator gen browsed by our algorithm can be generally represented as gen = Y ∪ i, where Y is a closed itemset, and i, i 6∈ Y is an item in I1.
Looking at Figure 1.(a), we can unfortunately discover multiple generators gen = Y ∪ i, whose closures produce an identical closed itemset. For example, we have four generators, {A}, {A, B}, {A, C} and {B, C}, whose closure is equal to the closed itemsets {A, B, C}. Note that all these generators have the form Y ∪ i, since they can be obtained by adding a single items to a smaller closed itemset, namely ∅, {B} and {C}.
The technique exploited by our algorithm to detect duplicate generators exploits a total lexicographic order relation ≺ between all the itemsets of our search space2. Since there exist a relation ≺ between each pair of k-itemsets, in order to avoid duplicate closed itemsets, we do not compute the closure of the generators 1 For each closed itemset Y 0 6= c (∅), it is straightforward to show that there must exists at least a generator having the form gen = Y ∪ i, where Y , Y ⊂ Y 0, is a closed itemset, i 6∈ Y , and Y 0 = c(gen). 2 This lexicographic order is induced by an order relation between single item literals, according to which each k-itemset I can be considered as a sorted set of k distinct items {i0, i1, ..., ik}. where the various geni are order preserving generators, with Y0 = c (∅), Yj+1 = c(Yj ∪ ij ) ∀j ∈ [0, n − 1] and Y = Yn.
Proof. First of all, we show that given a generic generator gen ⊆ Y , c(gen) ⊆ Y . More formally, if ∃Y 0 such that Y 0 is a closed itemset, and Y 0 ⊂ Y , and we extend Y 0 with an item i ∈ Y \ Y 0 to obtain gen = Y 0 ∪ i ⊆ Y , then ∀j ∈ c(gen), j ∈ Y .
Note that g(Y ) ⊆ g(gen) because gen ⊆ Y . Moreover, if j ∈ c(gen), then g(c(gen)) ⊆ g(j). Thus, since g(Y ) ⊆ g(gen), then g(Y ) ⊆ g(j) also holds, so that j ∈ c(Y ) too. So, if j 6∈ Y hold, Y would not be closed, and this is in contradiction with the hypothesis.
As regards the proof of the Theorem, we show it by constructing a sequence of closed itemsets and associated generators having the properties stated above.
We have that Y0 = c (∅). All the items in Y0 appear in every transaction of the dataset and therefore by definition of closure they must be included also in Y , i.e. Y0 ⊆ Y .
Since Y0 6= Y by definition, we choose i0 = min≺ (Y \ Y0), i.e. i0 is the smallest item in {Y \ Y0} with respect to the lexicographic order ≺, in order to create the first order preserving generator {Y0 ∪ i0}. Afterwards we calculate Y1 = c(Y0 ∪ i0) = c(gen0).
Once Y1 is found, if Y1 = Y we stop.
Otherwise we choose i1 = min≺ (Y \ Y1), where i0 ≺ i1 by construction, in order to build the next order preserving generator gen1 = Y1 ∪ i1 and we calculate Y2 = c(Y1 ∪ i1) = c(gen1).
Once Y2 is found, if Y2 = Y we stop, otherwise we iterate, by choosing i2 = min≺ (Y \ Y2), and so on.
Note that each generator genj = {Yj ∪ ij } is order preserving, because c({Yj ∪ ij }) = Yj+1 ⊆ Y and ij is {Yj+1 \ {Yj ∪ ij }}. the minimum item in {Y \Yj } by construction, i.e. ij ≺ Corollary 1 For each closed itemset Y the sequence of order preserving 6= c (∅), generators {gen0, gen1, . . . , genn} = {Y0 ∪ i0, Y1 ∪ i1, . . . , Yn ∪ in} as stated in Theorem 1 is unique.
Proof. Since all the items in Y0 appear in every transaction of the dataset, by definition of closure, they must be included also in Y , we have that Y0 = c (∅).
During the construction of the sequence of generators, suppose that we choose ij 6= min≺ (Y \ Yj ) to construct generator genj . Since genj and all the following generators must be order preserving, it should be impossible to obtain Y , since we can not consider anymore the item i = min≺ (Y \ Yj ) ∈ Y in any other generator or closure in order to respect the order preserving property.
Looking at Figure 1.(a), for each closed itemset we can easily identify those unique sequences of order preserving generators. For example, for the the closed itemset Y = {A, B, C, D}, we have Y0 = c(∅) = ∅, gen0 = ∅ ∪ A, Y1 = c(gen0) = {A, B, C}, gen1 = {A, B, C} ∪ D, and, finally, Y = c(gen1). Another example regards the closed itemset Y = {B, D}, where we have Y0 = c(∅) = ∅, gen0 = ∅ ∪ B, Y1 = c(gen0) = B, gen1 = B ∪ D, and, finally, Y = c(gen1).
In order to exploit the results of Theorem 1, we need a fast way to check whether a generator is order preserving.
Lemma 3 Let gen = Y ∪ i be a generator of a closed itemset where Y is a closed itemset and i 6∈ Y , and let pre-set(gen) = {j ≺ i | j 6∈ gen}. gen is not order preserving, iff ∃j ∈ pre-set(gen), such that g(gen) ⊆ g(j). Proof. If g(gen) ⊆ g(j), then j ∈ c(gen). Since, by hypothesis, j ≺ i, it is not true that i ≺ (c(gen) \ gen) because j ∈ (c(gen) \ gen).
The previous Lemma introduces the concept of pre-set(gen), where gen = {Y ∪ i} is a generator, and gives a way to check the order preserving property of gen by scanning all the g(j), for all j ∈ pre-set(gen).
We have thus contributed a deep study on the the problem of duplicates in mining frequent closed itemsets. By reformulating the duplicates problem as the problem of visiting the lattice of frequent itemsets, according to a total (lexicographic) order, we have moved the dependencies of the order preserving check from the set of closed itemsets already mined to the tid-lists associated with single items. This new technique is not resource demanding, because frequent closed itemsets need not to be stored in the main memory during the computation, and it is not time demanding, because the order preserving check is cheaper than searching the set of closed itemsets mined so far. Note that CLOSET+ needs the initial FP-tree as an additional requirement the current FP-tree in use, and morover does not use its upward checking tchnique with dense datasets. 5.
The pseudo-code of the recursive procedure DCI Closed() is shown in Algorithm 1. The procedure receives three parameters: a closed itemsets CLOSED SET, and two sets of items, i.e. the PRE SET and POST SET.
The procedure will output all the non-duplicate closed itemsets that properly contain CLOSED SET.
In particular, the goal of the procedure is to deeply explore each valid new generator obtained from CLOSED SET by extending it with all the element in POST SET.
Before calling procedure DCI Closed(), the dataset D is scanned to determine the frequent single items F1 ⊆ I, and to build the bitwise vertical dataset VD containing the various tid-list s g(i), ∀i ∈ F1.
The procedure is thus called by passing as arguments CLOSED SET = c(∅), PRE SET = ∅, and POST SET = F1 \ c(∅). Note that the itemset c(∅) contains, if any, the items that occur in all the transactions of the dataset D.
The procedure builds all the possible generators, by extending CLOSED SET with the various items in POST SET (lines 2–3). The infrequent and duplicate generators (i.e., the not order preserving ones) are however discarded as invalid (lines 4-5). Note that the items i ∈ P OST SET used to obtain those invalid generators will no longer be considered in the following recursive calls. Only the valid generators are then extended to compute their closure (lines 6–15). It is worth noting that each generator new gen ← CLOSED SET ∪ i is strictly extended according to the order preserving property, i.e. by using all items j ∈ POST SET such that i ≺ j (line 8). Note that all the items j, i ≺ j, which do not belong to c(new gen) are included in the new POST SET (line 12) and are used for the next recursive call. At the end of this process, a new closed set (CLOSED SETNew ← c(new gen)) is obtained (line 15). From this new closed set, new generators and corresponding closed sets can be build, by recursively calling the procedure DCI Closed() (line 16). Finally, it Algorithm 1 DCI-closed pseudocode 1: procedure DCI Closed(CLOSED SET, PRE SET, POST SET) for all i ∈ POST SET do new gen ← CLOSED SET ∪ i if supp(new gen) ≥ min supp then if is dup(new gen, PRE SET) = FALSE then
CLOSED SETNew ← new gen POST SETNew ← ∅ for all j ∈ POST SET, i ≺ j do if g(new gen) ⊆ g(j) then
CLOSED SETNew ← CLOSED SETNew ∪ j is worth to point out that, in order to force the lexicographic order of the visit, the two for all’s (line 2 and line 8) have to extract items from POST SET while respecting this order.
Before recursively calling the procedure, it is necessary to prepare the suitable PRE SET and POST SET to be passed to the new recursive call of the procedure.
Upon each recursive call to the procedure, the size of the new POST SET is monotonically decreased, while the new PRE SET’s size is instead increased.
As regards the composition of the new POST SET, assume that the closed set X =CLOSED SETnew passed to the procedure (line 16) has been obtained by computing the closure of a generator new gen = Y ∪ i (c(new gen)), where Y =CLOSED SET and i ∈ POST SET. The POST SETnew to be passed to the recursive call of the procedure is built as the set of all the items that follow i in the lexicographic order and that have not been already included in X. More formally, POST SETnew = {j ∈ F1 | i ≺ j and j 6∈ X}.
This condition allows the recursive call of the procedure to only build new generators X ∪ j, where i ≺ j (according to the hypotheses of Theorem 1.
The composition of the new PRE SET depends instead on the valid generators3 that precedes new gen = Y ∪ i in the lexicographic order. If all the generators were valid, it would simply be composed of all the items j that precede i in the lexicographic order, and j 6∈ X = c(new gen). In other words, the new PRE SET would be the complement set of X ∪ POST SETnew.
While the composition of POST SET guarantees that the various generators will be produced according to the lexicographic order ≺, the composition of PRE SET guarantees that duplicate generators will be pruned by function is dup().
Since we have shown that for each closed itemset Y exists one and only one sequence of order preserving generators and since our algorithm clearly explores every possible order preserving generator from every 3 The ones that have passed the frequency and duplicate tests.
. Try to create a new generator . new gen is frequent
. Duplication check . Compute closure of new gen
. Duplicate check . new gen is not order preserving!! closed itemset, we have that the algorithm is complete and does not produce any duplicate. 5.0.1. Some optimizations exploited in the algorithm. We adopted a large amount of optimizations to reduce the cost of the bitwise intersections, needed for the duplication and closure computations (line 10 and 34). For the sake of simplicity, these optimizations are not reported in the pseudo-code shown in Algorithm 1.
DCI-CLOSED inherits the internal representation of
our previous works DCI[
The D(i, j) bit is set to 1 if and only if the j -th transaction contains the i -th frequent single item. Row i of the matrix thus represent the tid-list of item i.
The columns of D are then reordered to profit of
data correlation. This is possible and highly worthwhile
when we mine dense datasets. As in [
This kind of representation fits with our framework, because the three main operations, i.e. support count, closure, and duplicates check, can be fastly performed with cheap bit-wise AND/OR operation.
Besides the DCI optimizations, specifically tailored for sparse and dense datasets, we exploited more specific techniques made possible by the depth-first visit of the lattice of itemsets.
In order to determine that the itemset X is closed, the tidlist g(X) must have been compared with all the g(j)’s, for all items j contained in the pre-list (postlist ) of X, i.e. the items that precede (follows) all items included in X according to a lexicographic order. The PRE SET must have been accessed for checking duplicate generators, and the POST SET for computing the closure. In particular, for all j ∈ PRE SET ∪ POST SET, we already know that g(X) * g(j), otherwise those items j must have been included in X.
Therefore, since g(X) must have already been compared with all the g(j), for all items j contained in the PRE SET (POST SET) of X, we may save some important information regarding each comparison between g(j) and g(X). Such information will be used to reduce the cost of the following use of g(j), when these tidlists g(j) will have to be exploited to look for further closed itemsets that include/extend X. In particular, even if, for all j, it is true that g(X) * g(j), we may know that some large portions of the bitwise tidlists g(X) are however strictly included in g(j). Let g(X)j be the portion of the bitwise tidlist g(X) strictly included in the corresponding portion of g(j), namely g(j). Hence, since g(X)j ⊆ g(j), it is straightforward to show that g(X ∪ Y )j ⊆ g(j) continues to hold, for all itemset Y used to extend X, because g(X ∪ Y ) ⊆ g(X) holds . So, when we extend X to obtain a new generator, we can limit the inclusion check of the various g(j) to the complementary portions of tid-lists g(j), thus strongly reducing the cost of them. 5.0.2. Dealing with sparse datasets. It is possible to show that in sparse datasets the number of closed itemsets is nearly equal to the number of frequent ones, so near that they are often the same. This means that the techniques for mining closed itemsets are of no use, because almost every duplicate checking or closure calculating procedure is likely to fail.
For this reason, in case of sparse datasets, we
preferred to exploit our frequent itemset mining algorithm
[
The main information needed to be kept in the main memory is the tid-list of each node in the current path along the lattice, and the tid-list of every frequent single item. In this way we are able to browse the search space intersecting nodes with single item tid-lists, and to discard duplicates checking the order preserving property.
The worst case of memory occupation happens when the number of generators and frequent single items is maximal: this occurs when c(∅) = ∅ and every itemset is frequent and closed. If N is the number of frequent single items, the deepest path has N nodes, and since one of this node is a single item, the total number of tid-lists to be kept in the main memory is 2N −1.
Since the length of a tid-list is equal to the number of FPCLOSE CLOSET+ DCI−CLOSED 40 35 30 20 15 10 5 100 45 40 35 25 20 15 70 65 60 55 50 45
40 103 102 .) cse ( e m it 101
Memory occupation on the connect dataset as a function of the minimum support threshold. (b-f ) Execution times of FPCLOSE, CLOSET+, and DCI-CLOSET as a function of the minimum support threshold on various publicly available datasets. transactions T in the dataset, the space complexity of our algorithm is
O ((2N − 1) × T ) . 5.1. Experimental results
We tested our implementation on a suite of
publicly available dense datasets (chess, connect, pumsb,
pumsb*), and compared the performances with those of
two well known state of the art algorithms: FPCLOSE
[
The experiments were conducted on a Windows XP PC equipped with a 2.8GHz Pentium IV and 512MB of RAM memory. The algorithms FPCLOSE and DCICLOSED were compiled with the gcc compiler available in the cygwin environment.
As shown in Fig. 2.(b-f), DCI-CLOSED outperforms both algorithms in all the tests conducted. CLOSET+ performs quite well on the connect dataset with low supports, but in any other case it is about two orders of magnitude slower. FPCLOSE is effective in pumsb*, where it is near to DCI-CLOSED, but it is at one order of magnitude slower in all the other tests.
In this paper we provide a deep study on the problem of mining frequent closed itemsets, formalizing a general framework fitting every mining algorithm. Use such framework we were able to analyse the problem of duplicates rising in this new mining problem.
We have proposed a technique for promptly detecting and discarding duplicates, without the need of keeping in the main memory the whole set of closed patterns, and we implemented this technique into a new algorithm which uses a vertical bitmap representation of the dataset.
The experimental evaluation demonstrated that our approach is very effective. The proposed implementation outperforms FPCLOSE and CLOSET+ in all the test conducted and requires orders of magnitude less memory.