Nicolas Pasquier

Yves Bastide
email: bastide@libd1.univ-bpclermont.fr

Lot Lakhal {pasquier Ra K Taouil
email: taouil@libd1.univ-bpclermont.fr

Pruning Closed Itemset Lattices for Association Rules

Keywords: extraction de connaissances, r gles d'association, treillis, algorithmes data mining, knowledge discovery, association rules, lattices, algorithms

R sum

La d couverte des r gles d'association est l'un des principaux probl mes de l'extraction de connaissances dans les bases de donn es. De nombreux algorithmes e caces ont t propos s, dont les plus remarquables sont Apriori, l'algorithme de Mannila, Partition, Sampling et DIC. Ces derniers sont tous bas s sur la m thode de recherche de Apriori: l' lagage du treillis des parties (treillis des itemsets). Dans cet article, nous proposons un algorithme e cace bas sur une nouvelle m thode de recherche: l' lagage du treillis des ferm s (treillis des itemsets ferm s). Ce treillis qui est un sous-ordre du treillis des parties est troitement li au treillis de concepts de Wille dans son analyse formelle de concepts. Nous avons compar exp rimentalement Close une version optimis e de Apriori et les r sultats obtenus montrent la grande e cacit de Close dans le traitement des donn es denses et/ou corr l es telles que les donn es de rescensement (cas di cile). Nous avons galement pu observer que Close donne des temps de r ponse corrects dans le traitement des bases de donn es de ventes.

Introduction

One of the most important task in data mining is the discovery of association rules rst introduced in 1]. The aim of the association rule discovery is to identify relationships between items in very large databases. For example, given a market basket database, it would be interesting for decision support to know the fact that 80% of customers who bought cereals and sugar also bought milk. In a census database, we should discover that 60% of persons who worked last year earned less than the average income, or in a medical database, that 70% of patients who have sti nesses and fever also have headaches. Agrawal's statement of the problem of discovering association rules in market basket databases is the following 1, 2]. Let I = {i 1 ; i 2 ; : : : ; i m } be a set of m literals called items. Let the database D = {t 1 ; t 2 ; : : : ; t n } be a set of n transactions, each one consisting of a set of items I from I and associated with a unique identi er called its TID. I is called a k-itemset, where k is the size of I. A transaction t 2 D is said to contain an itemset I if I t. The support of an itemset I is the percentage of transactions in D containing I: support(I) = ft 2 D j I tg = ft 2 Dg. An association rule is a conditional implication among itemsets, I ) I 0 , where itemsets I; I 0 I and I \ I 0 = ;. The con dence of an association rule r : I ) I 0 is the conditional probability that a transaction contains I 0 , given that it contains I: confidence(r) = support(I I 0 ) = support(I). The support of r is de ned as: support(r) = support(I I 0 ).

The problem of mining association rules in a database D is then traditionally de ned as follows.

Given user de ned thresholds for the permissible minimum support and con dence, nd all the association rules that hold with more than the given minsupport and mincon dence. This problem can be broken into two subproblems 1]:

1. Finding all frequent itemsets in D, i.e. itemsets with support greater or equal to minsupport.

Frequent itemsets are also called large itemsets.

2. For each frequent itemset I 1 found, generating all association rules I 2 ) I 1 I 2 | I 2 I 1 , with con dence greater or equal to mincon dence. The second subproblem can be solved in main memory in a straightforward manner once all frequent itemsets and their support are known. Hence, the problem of mining association rules is reduced to the problem of nding frequent itemsets. Many algorithms have been proposed in the literature 2, [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF][START_REF] Mannila | Methods and problems in data mining[END_REF][START_REF] Godin | Incremental concept formation algorithms based on Galois (concept) lattices[END_REF][START_REF] Mueller | Fast sequential and parallel algorithms for association rules mining: A comparison[END_REF]12,[START_REF] Savasere | An e cient algorithm for mining association rules in larges databases[END_REF]. Although they are very di erent from each other, they are all based on the Apriori mining method 2]: pruning of the subset lattice for nding frequent itemsets. This relies on the basic properties that all subsets of a frequent itemset are frequent and that all supersets of an infrequent itemset are infrequent. Algorithms based on this approach perform very well for weakly correlated data such as market basket data. However perfomances drastically decrease for correlated data such as census data. In this paper, we propose a new e cient algorithm called Close for mining association rules in very large databases. Close is based on the pruning of the closed itemset lattice which is a sub-order of the subset lattice, thus much smaller. Such a structure is closely related to Wille's concept lattice in formal concept analysis [START_REF] Chen | Data mining: An overview from a database perspective[END_REF][START_REF] Toivonen | Sampling large databases for association rules[END_REF][START_REF] Wille | Restructuring lattices theory: an approach based on hierarchies of concepts[END_REF]. We show that this structure can be used as a formal framework for discovering association rules given the basic properties that all sub-closed itemsets of a frequent closed itemset are frequent, that all sup-closed itemsets of an infrequent closed itemset are infrequent and that the set of maximal frequent itemsets is identical to the set of maximal frequent closed itemsets. Empirical evaluations comparing Close to an optimized version of Apriori showed that Close performs reasonably well for weakly correlated data and performs very well for correlated data. The rest of the paper is organized as follows. Section 2 reviews related work and exhibits the contribution of the paper. In Section 3, we de ne the semantics of association rules based on the Galois connection operators. In Section 4, we describe the Close algorithm. Section 5 gives experimental results on synthetic data1 and census data using the PUMS le for Kansas USA2 and Section 6 concludes the paper. In this section, we rst present the subset lattice based approach for mining association rules. Then, we introduce the use of the closed itemset lattice as a formal framework in data mining and we brie y describe the Close mining method.

TID

Items 1 A C D 2 B C E 3 A B C E 4 B E 5 A B C E

A Common Approach for Mining Association Rules

Finding all frequent itemsets is a nontrivial problem because the number of possible frequent itemsets is exponential in the size of the set of items I of the database. Given kIk = m, there are possibly 2 m frequent itemsets, which form a lattice of subsets over I with height equal to m. Consider the example transaction database D given in Figure 1. The lattice of subsets associated with D is represented in Figure 2. This lattice contains 32 itemsets and its height is 6. However, depending on the data and the minsupport value, only a small fraction of the whole lattice space is frequent. For instance, assuming that minsupport is 2 (40%), only 15 itemsets of D are frequent.

A naive approach consists of testing the support of every itemset in the lattice, which can be done in a single pass over the database. Clearly, this approach is impractical for large values of m. In the following, we describe the Apriori mining method used by all existing algorithms for nding frequent itemsets. The notation is given in Table 1. Each element of this set has two elds: i) itemset and ii) support count.

L k Set of frequent k-itemsets (itemsets with minimum support).

Each element of this set has two elds: i) itemset and ii) support count.

Algorithm Apriori

In the Apriori algorithm, items are sorted in lexicographic order. The pseudo-code of the Apriori frequent itemset discovery is given in Algorithm 1. Frequent itemsets are computed iteratively, in the ascending order of their size. The process takes k iterations, where k is the size of the largest frequent itemsets. For each iteration i k, the database is scanned once and all frequent itemsets of size i are computed. The rst iteration computes the set L 1 of frequent 1-itemsets. A subsequent iteration i consists of two phases. First, a set C i of candidate i-itemsets is created by joining the frequent (i 1)-itemsets in L i 1 found in the previous iteration. This phase is realized by the Apriori-Gen function described below. Next, the database is scanned for determining the support of the candidates in C i and the frequent i-itemsets are extracted from the candidates.

This process is repeated until no more candidate can be generated.

1) L 1 = {Large 1-itemsets};

2) for ( k=2; L k 1 6 = ;; k++ ) do begin

3) C k = Apriori-Gen(L k 1 ); // Generates candidates k-itemsets 4)
forall transactions t 2 D do begin Apriori-Gen Candidate Generation The function takes as argument the set L i 1 of frequent (i 1)-itemsets. It returns the set C i of candidate i-itemsets, which is a superset of the set of all frequent i-itemsets. Two frequent itemsets of size i 1 with the same rst i 2 items are joined, generating a new candidate itemset of size i: insert into C i select p.item 1 , p.item 2 , : : :, p.item i 1 , q.item i 1 from L i 1 p; L i 1 q where p.item 1 = q.item 1 , : : : , p.item i 2 = q.item i 2 , p.item i 1 < q.item i 1 ; Then, the candidate set C i produced is pruned by removing every candidate i-itemset c such that some (i 1)-subset of c is not in L i 1 : forall candidate itemsets c 2 C i do begin forall (i 1)-subsets s of c do begin if (s = 2 L i 1 ) then delete c from C i ; Example Figure 3 shows the execution of Apriori for a minimum support of 2 (40%) on the database D. This process takes four iterations, computing four sets of candidates and frequent itemsets and performing four database passes. The frequent itemsets found are outlined in the itemset lattice given in Figure 2 The algorithms based on this approach take k database passes to generate all frequent itemsets, where k is strongly linked to the height of the itemset lattice (generaly the size of the maximal frequent itemsets). Recent algorithms like Partition, Sampling and DIC have attempted to improve the search e ciency by reducing the number of database passes. However, the e ciency of algorithms does not rely only on the I/O cost they incur (number of database passes), but the CPU overhead they involve can a ect their performances.

Closed Itemset Lattices

In this section, we de ne data mining context, Galois connection, closed itemset and closed itemset lattice. Interested readers should consult 5] for further details on the order and lattice theory. (1) I 1 I 2 =) g(I 1 ) g(

I 2 ) (1') O 1 O 2 =) f(O 1 ) f(O 2 ) (2) I g f(I) (2') O f g(O) (3) g f(g f(I)) = g f(I) (3') f g(f g(O)) = f g(O) (4) I 1 I 2 =) g f(I 1 ) g f(I 2 ) (4') O 1 O 2 =) f g(O 1 ) f g(O 2 ) (5) f g(g(I)) = g(I) (5') g f(f(O)) = f(O) (6)
O g(I) () I f(O) Closed Itemset Let C I be a set of items from D. C is a closed itemset i g f(C) = C. The smallest (minimal) closed itemset containing an itemset I is obtained by applying g f to I.

Closed Itemset Lattice Let C be the set of closed itemsets derived from D using the Galois connection. The pair L C = (C; ) is a complete lattice called closed itemset lattice. Having a lattice structure implies two properties: i) A partial order on the lattice elements such that, for every elements C

1 ; C 2 2 L C ; C 1 C 2 , i C 1 C 2 4 .
ii) All subsets of L C have one upper bound, the Join element, and one lower bound, the Meet element. Below, we give the de nitions of the Join and Meet elements extracted from Wille's basic theorem on concept lattices 5, 14]. For all S L C :

Join (S) = g f( C2S C); Meet (S) = \ C2S C

The Close Mining Method

The Close algorithm is fundamentally di erent from existing algorithms, since it is based on the pruning of the closed itemset lattice for nding frequent itemsets. A closed itemset is a maximal set of items common to a set of objects. For example, in the database D, the itemset fB; C; Eg is a closed itemset since it is the maximal set of items common to the objects f2; 3; 4g. fB; C; Eg is called a frequent closed itemset for minsupport = 2 as support(fB; C; Eg) = kf2; 3; 4gk = 3 minsupport. In a basket database, this means that 60% of customers (3 customers on a total of 5) purchase at most the items B; C; E. The itemset fB; Cg is not a closed itemset since it is not a maximal grouping of items common to some objects: all customers purchasing the items B and C also purchase the item E. The closed itemset lattice of a nite relation (the database) is isomorphic to the concept lattice 14, 15], also called Galois lattice 7]. Figure 1 Using the closed itemset lattice, which is a sub-order of the subset lattice, for nding frequent itemsets can improve the e ciency of the association rule discovery. Indeed, the proportion of itemsets that are closed and frequent is much smaller than the proportion of frequent itemsets. By minimizing the search space, we reduce both the number of database passes and the CPU overhead incurred by the generation of frequent itemsets. Indeed, the size of the itemset lattice is exponential in the size of the set of items, kL S k = 2 kIk . Although in the worst case, the closed itemset lattice may grow exponentially, the growth is linear with respect to kDk when it exists an upper bound K on the object size (kok). Then, the size of the closed itemset lattice is kL C k 2 K kDk. Moreover, experimental applications and theoretical results based on a uniform distribution hypothesis showed that the average growth factor is far less than the 2 K bound.

Actually, we can observe that kL C k kDk, where is the mean value for kok 7]. Using the closed itemset lattice framework we can deduce the following properties (see Section 3): i) All subsets of a frequent itemset are frequent. ii) All supersets of an infrequent itemset are infrequent. iii) All sub-closed itemsets5 of a frequent closed itemset are frequent. iv) All sup-closed itemsets 6 of an infrequent closed itemset are infrequent. v) The set of maximal frequent itemsets is identical to the set of maximal frequent closed itemsets.

vi) The support of a frequent itemset I which is not closed is equal to the support of the smallest frequent closed itemset containing I. Based on these properties, Close generates all association rules from a database D through three successive phases:

1. Discovering all frequent closed itemsets in D, i.e. itemsets that are closed and have support greater or equal to minsupport.

2. Deriving all frequent itemsets from the frequent closed itemsets found in phase 1. This phase consists in generating all subsets of the maximal frequent closed itemsets and deriving their support from the frequent closed itemset supports .

3. For each frequent itemset I found in phase 2, generating all association rules that can be derived from I and have con dence greater or equal to mincon dence.

The rst phase is the more computationally intensive part of the algorithm. After this phase, no more database access is necessary and the second and third phases can be solved easily in main memory in a straightforward manner. Indeed, the rst phase has given us all information needed for the next two, particularly the support of the frequent closed itemsets used to determinate the support of the frequent itemsets without any database access.

Semantics of Association Rules

In this section, we propose new semantics for association rules using the Galois connection (f; g).

We rst de ne frequent itemsets, frequent closed itemsets and their properties, in a data mining context D = (O; I; R). Then, we de ne association rules and valid association rules using frequent closed itemsets.

Frequent Itemsets

Itemset Support Let I I be a set of items from D. The support count of the itemset I in D is: support(I) = kg(I)k kOk

Frequent Itemsets The itemset I is said to be frequent if the support of I in D is at least minsupport. We de ne the set L of frequent itemsets in D as: L = fI I j support(I) minsupportg

Maximal Frequent Itemsets Let L be the set of frequent itemsets. We de ne the set M of maximal frequent itemsets as: M = fI 2 L j @I 0 2 L; I I 0 g Property 1: All subsets of a frequent itemset are frequent (intuitive in 2]). Proof: Let I; I 0 I, I 2 L and I 0 I. According to Property (1) of the Galois connection: I 0 I =) g(I 0 ) g(I) =) support(I 0 ) support(I) minsupport. So, we get: I 0 2 L. Property 2: All supersets of an infrequent itemset are infrequent (intuitive in 2]). Proof: Let I; I 0 I, I 0 = 2 L and I 0 I. According to Property (1) of the Galois connection:

I I 0 =) g(I) g(I 0 ) =) support(I) support(I 0 ) minsupport. So, we get: I = 2 L.

Frequent Closed Itemsets

Frequent Closed Itemsets The closed itemset C is said to be frequent if the support of C in D is at least minsupport. We de ne the set FC of all frequent closed itemsets in D as: FC = fC I j C = g f(C) and support(C) minsupportg Maximal Frequent Closed Itemsets Let FC be the set of all frequent closed itemsets. We Proof: It su ces to demonstrate that 8I 2 M, I is closed, i.e. I = g f(I). Let I 2 M be a maximal frequent itemset. By de nition, 8I 0 I, I 0 is not frequent, i.e. I 0 = 2 M.

According to Property (2) of the Galois connection I g f(I) and, since I is maximal and support(g f(I)) = support(I) minsupport, we can conclude I = g f(I). I is a maximal frequent closed itemset. Since all maximal frequent itemsets are also a maximal frequent closed itemsets, we get: M = MC.

Association Rules

Association Rules An association rule is an implication between itemsets of the form I ) I 0 where I; I 0 I and I \ I 0 = ;. The itemset I is called the antecedent of the rule, and the itemset I 0 is called the consequent. Below, we de ne the support and con dence of an association rule using the Galois connection applications f and g. The support and con dence of an association rule r : I ) I 0 are: support(r) = kg(I I 0 )k kOk ; confidence(r) = support(I I 0 ) support(I) = kg(I I 0 )k kg(I)k

Valid Association Rules The task of mining association rules consists in generating all valid association rules, i.e. association rules with support and con dence greater or equal to the minsupport and mincon dence thresholds. Let AR be the set of valid association rules in D. We de ne AR using the set MC of maximal frequent closed itemsets as: AR(D; minsupport; minconfidence) = fr : I 2 ) I 1 I 2 ; I 2 I 1 j I 1 2 L = C2MC 2 C and confidence(r) minconfidenceg

Algorithm Close

In Section 4.1 we describe our discovery of the frequent closed itemsets. In Section 4.2 we give our method for deriving frequent itemsets from the frequent closed itemsets. In Section 4.3 we present an e cient algorithm for nding valid association rules using frequent itemsets. This algorithm is adapted from the one described in 2].

Discovering Frequent Closed Itemsets

As in the Apriori algorithm, items are sorted in lexicographic order. The pseudo-code for discovering frequent closed itemsets is given in Algorithm 2. For each iteration, the algorithm constructs a set of candidate frequent closed itemsets, determines the frequent closed itemsets using the minsupport threshold and then computes the generator itemsets that will be used during the next iteration for constructing the set of candidate frequent closed itemsets. In each iteration, one pass over the database is necessary, for constructing the set of candidate frequent closed itemsets (closures of generators). support Support of the frequent closed itemset: support = count(closure). The rst operation of the algorithm (step 1) initializes the set of generator itemsets in FCC 1 with the items present in the data mining context, i.e. elements of the set I, needing no database pass.

Set

Each of the following iterations consists of three phases. First, the closure function is applied to each generator in FCC i , determining the candidate frequent closed itemsets and their support.

The closure function Gen-Closure used for this purpose is described in Section 4.1.1. Next, the set of candidate closed itemsets obtained is pruned: the closed itemsets with su cient support 1) generators in FCC 1 = {1-itemsets};

2) for ( i=1; FCC i .generator6 = ;; i++ ) do begin We can conclude that S = S 0 , thus g f(I) = H.

Using Proposition 1, only one database pass is necessary for computing the closures of the generators of an iteration i, and their support. The function works as follows. For each object o in D, we create the set G o containing all generators in FCC i that are subsets of the object itemset f(fog) (step 2). Then, for each generator p in G o , we update the associated closed itemset p.closure (step 3 to 7). If the object o is the rst one containing the generator, p.closure is empty and we assign to it the object itemset (step 4). Otherwise, the intersection between p.closure and the object itemset gives us the new p.closure (step 5). Then, we increment the closed itemset support p.support (step 6). At the end of the function, we have for each generator p in FCC i , the closed itemset p.closure corresponding to the intersection of all objects containing p and its associated support count p.support corresponding to the number of objects containing p.closure (support count of the generator and its closure are equal according to Property 5).

Gen-Generator Function

The function Gen-Generator takes as argument the set of frequent closed itemsets FC i . Based on Proposition 2, it returns the set FCC i+1 containing all generator (i + 1)-itemsets that will be The function rst generates all potential generator (i + 1)-itemsets using generator i-itemsets in FC i .

Then, based on Proposition 3, the potential generators produced that will lead to useless computing (infrequent closed itemsets) or redundancies (frequent closed itemsets already produced) are deleted from FCC i+1 .

Proposition 2: Let I 1 ; I 2 be two generator itemsets. We have: g f(I 1 I 2 ) = g f(g f(I 1 ) g f(I 2 ))

Proof: Let I 1 and I 2 be two itemsets. According to Property (2) of the Galois connection: I 1 g f(I 1 ) and I 2 g f(I 2 ) =) I 1 I 2 g f(I 1 ) g f(I 2 ) =) g f(I 1 I 2 ) g f(g f(I 1 ) g f(I 2 ))

(1)

Obviously, I 1 I 1 I 2 and I 2 I 1 I 2 . So g f(I 1 ) g f(I 1 I 2 ) and g f(I 2 ) g f(I 1 I 2 ).

According to Property (3) of the Galois connection:

g f(g f(I 1 ) g f(I 2 )) g f(g f(I 1 I 2 )) =) g f(g f(I 1 ) g f(I 2 )) g f(I 1 I 2 ) (2) From (1) and (2), we can conclude g f(I 1 I 2 ) = g f(g f(I 1 ) g f(I 2 )).

Proposition 3: Let I be a generator i-itemset and S = fs 1 ; s 2 ; : : : ; s j g a set of (i 1)-subsets of I where S s2S s = I. If 9s a 2 S such as I g f(s a ), then g f(I) = g f(s a ). Proof: Let I be an i-itemset and s a 2 S, an (i 1)-subset of I.

I g f(s a ) =) g f(I) g f(g f(s a )) =) g f(I) g f(s a ) (1) s a 2 S =) s a I =) g f(s a ) g f(I) (2)
From (1) and (2), we deduce g f(I) = g f(s a ).

The function Gen-Generator works as follows. We rst apply the combinatorial phase of Apriori-Gen 2] to the set of generators in FC i giving us a set of new potential generators: two generators of size i in FC i with the same rst i 1 items are joined, producing a new potential generator of size i + 1.

1) insert into FCC i+1 .generator 2) select p.item 1 , p.item 2 , : : :, p.item i , q.item i 3) from FC i .generator p, FC i .generator q 4) where p.item 1 = q.item 1 , : : : , p.item i 1 = q.item i 1 , p.item i < q.item i ; Then, we prune the resulting set using two strategies. First, like in Apriori-Gen, for all potential generator p created we test the presence of all its i-subsets in FC i .generator. Indeed, if one of them is absent from FC i and according to Property 2 we deduce that p is not frequent and we can remove it from FCC i+1 . Let's take an example. Suppose that the set of candidate frequent closed itemsets FC 2 contains the generator itemsets AB; AC with respective closures ABC; ACD all frequent. The Gen-Generator 5) forall generators p 2 FCC i+1 .generator do begin [START_REF] Davey | Introduction to Lattices and Order[END_REF] forall i-subsets s of p do begin [START_REF] Ganter | Finding all closed sets: A general approach[END_REF] if ( s = 2 FC i .generator ) then 8)

delete p from FCC i+1 .generator; 9) end 10) end function will create ABC = AB AC as a new potential generator in FCC 3 . The rst pruning strategy will remove ABC from FCC 3 since BC = 2 FC 2 .generator as it is infrequent.

The second pruning strategy is as follows. For each potential generator p in FCC i+1 , we test if the closure of one of its i-subsets s is a superset of p. In that case, the closure of p will be equal to the closure of s (see Proposition 3), so we can remove p from FCC i+1 . Let's give another example. Suppose that the set of frequent closed itemsets FC 2 contains generators AB; AC; BC with respective closures AB; ABC; BC all frequent. The Gen-Generator function will create ABC = AB AC as a new potential generator in FCC 3 . The second prune step will remove ABC from FCC 3 since ABC closure(AC). Indeed, we can deduce that closure(ABC) = closure(AC) and the computation of the closure of ABC is useless.

Subset Function

Candidate frequent closed itemsets are stored in a pre x-tree structure to quickly nd all generators associated with an object. Our structure is derived from the one proposed in 10]. Figure 5 shows the Pre x-tree structure for the set FCC 2 given in Figure 6 Each edge in the tree is labeled with an item. A generator itemset is represented as a path in the tree, starting from the root node. The closure of a generator is stored in the leaf (terminal node) of the path representing it. Each node contains a pointer to a sibling node, a hash-table towards the children of the node and, if the node is a leaf, a pointer to the closure of the generator represented. For a node representing an i-itemset c, a sibling node represents another i-itemset with the same rst i 1 items and a hash collision on the i th item. For performance reasons, if the size of such a linked list exceeds a given threshold, instead of adding a new sibling node, the size of the hash-table of the parent node is doubled and the i th nodes are rebalanced. 0 1 0 0 1 1 0 10 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

B C 3 {B,C,E} 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 1 0 10 1 A B 2 {A,B,C,E}
Pointer to sibling

Hash-table

Pointer to closure Closure Support Item Figure 5: Pre x-tree of the set FCC 2 in Figure 6 The subset function takes as arguments a set of generators G and an itemset c. It determines which generators p 2 G are subsets of the itemset c. The function starts from the root node and hashes successively on each item of the itemset c down through the tree. Having reached a node by hashing on item i, we hash on each item that comes after i in c and recursively apply this procedure to the node in the corresponding bucket of the hash-table. At the root node, we hash on every item in c. When we are at a leaf, we add the reference to the generator to the answer set.

Example and Correctness

Figure 6 shows the execution of the algorithm on the data mining context D given in Figure 1. We assume that minsupport is 2 (40%). Step 1 initializes the set of generators in FCC 1 with the list of items in D. Calling Gen-Closure at step 3 gives for every generator p the candidate closed itemset p.closure and its support count p.support. In step 4 through 7 we generate FC 1 by pruning FCC 1 according to minsupport. In step 9 we produce the generators in FCC 2 by applying the function Gen-Generator to FC 1 . As we can see in Figure 6, calling Gen-Generator with FC 1 produces two new generators: AB and BC. Generators A and C in FC 1 do not give a new generator AC since the closure of A is AC and the closure of C is C. Obviously C AC, so the generator A C is deleted by the second pruning step of the function Gen-Generator.

Calling Gen-Closure with FCC 2 produces the closures of the generators in FCC 2 and their support. After the pruning of the candidate closed itemsets, FCC 2 and FC 2 are identical since all candidate closed itemsets in FCC 2 are frequent. The set of generators in FCC 3 constructed by calling Gen-Generator with FC 2 is empty as no generator in FC 2 have the same rst item, and the algorithm terminates. We can observe that the number of database passes is reduced by half compared to the execution of Apriori on the same example. Correctness We must ensure that all frequent closed itemsets have been produced. Starting with the set of items in the data mining context and making successive closures of the unions of closed itemsets found in the previous iteration gives the complete closed itemset lattice, based on the Join operator of Wille's basic theorem on concept lattices (see section 2.2). According to Proposition 2, working on generator itemsets is identical to working on their closures. The method we use for creating the generators (similar to the one in Apriori-Gen) is an e cient union method. This method yields all possible unions, avoiding redundancies, given the lexicographic order among items. The two pruning steps of the set of generators avoid useless computations by removing infrequent generators and generators which closure was already found (Proposition 3).

Scan

Deriving Frequent Itemsets

The pseudo-code for deriving frequent itemsets is given in Algorithm 4. It uses as its input the set of frequent closed itemsets FC = S i FC i and gives the set of frequent itemsets L = S k L k as the output. In step 1 through 5, we put each frequent closed itemset c from FC in the set of frequent itemset L kck corresponding to the size of c, and we determine the size k of the largest frequent itemsets. Then, during step 6 to 15 we construct all sets L i , starting from L k down to L 1 . In each iteration, we complete the set L i 1 using the itemsets in L i . For each i-itemset c in L i , we generate all (i 1)-subsets of c. All subsets that are not present in L i 1 are added to the end of L i 1 with support value equal to the support of c. This process takes place until L 1 has been completed.

1) k = 0;

2) forall frequent closed itemsets c 2 FC do begin forall (i 1)-subsets s of c do begin [START_REF] Mannila | Methods and problems in data mining[END_REF] if ( s = 2 L i 1 ) then begin

L i 1 = L i 1 fsg; // Put s at the end of L i 1

end 15) end 16) Answer = S i=k i=1 L i ; Algorithm 4: Deriving frequent itemsets Example Figure 7 shows the execution of the algorithm using as input the sets FC 1 and FC 2 given in Figure 6. The rst phase of the algorithm simply splits frequent closed itemsets of FC 1 and FC 2 in sets L 1 to L 4 according to their size, and determines that k = 4. During the rst iteration of the loop (step 6 to 15), the closed itemset ABCE in L 4 is examined and generates ABC, ABE and ACE in L 3 with the same support value as ABCE. The closed itemset BCE is not generated since it is already present in L 3 . During the second iteration, we rst examine the closed itemset BCE, generating BC in L 2 with support = 3. If we had rst examined the itemset ABC, we would have generated BC in L 2 with support = 2 which is incorrect. At the end of the second iteration, L 2 is complete. The third iteration generates L 1 and ends the algorithm.

Correctness The correctness of the algorithm for deriving frequent itemsets relies on Properties 5 and 6, and on the fact that we rst examine closed i-itemsets in L i during the (i 1)-subset generation. For an iteration i, let c be a frequent closed i-itemset in L i and s an (i 1)-subset of c. If s is a closed itemset then it has already been inserted in L i 1 during the rst phase of the algorithm (step 1 to 5). If s is not a closed itemset, then according to Property 5 it is correct to insert s in L i 1 with the same support value as c. Now, consider that s is not a closed (i 1)-itemset and we are completing L i 2 . The support of s is equal to the support of c which is the smallest closed itemset containing s. Let s 0 be a (i 2)-subset of s. If s 0 is not a closed itemset and has not already been generated in L i 2 , then, given Proposition 3, its support is equal to the support of the smallest closed itemset containing s 0 which is c. Hence it is correct to insert s 0 in L i 2 with the support value of s. Since the set of maximal frequent itemsets is the same as the set of maximal frequent closed itemsets (see Property 6), the set L k is complete, where k is the size of the largest frequent itemsets (obviously all maximal frequent itemsets). Given the properties that all subsets of a frequent itemset are frequent and all supersets of an infrequent itemset are infrequent, by generating all subsets of the maximal frequent closed itemsets we generate all frequent itemsets, and the result is correct.

Generating Valid Association Rules

The problem of generating valid association rules can be solved in a straightforward manner once all frequent itemsets and their support are known. In this section, we describe an adapted version of Apriori rule generation algorithm 2] (implemented for our experiments). For every frequent itemset I 1 we derive all subsets I 2 of I 1 and we compute the ratio support(I 1 )=support(I 2 ). If the result is at least mincon dence, then the rule I 2 )(I 1 I 2 ) is generated. The support of any subset I 3 of I 2 being greater or equal to the support of I 2 , the con dence of the rule I 3 )(I 1 I 3 ) is necessarily less than the con dence of the rule I 2 )(I 1 I 2 ). Hence, if the rule I 2 )(I 1 I 2 ) does not hold, neither will the rule I 3 )(I 1 I 3 ). Conversely, if the rule (I 1 I 2 ) )I 2 holds, then all rules of the form (I 1 I 3 ) )I 3 also hold. For example, if the rule A)BC holds, then the rules AB )C and AC )B also hold.

Using this property for e ciently generating valid association rules, the algorithm works as follows.

For every frequent itemset I 1 , all rules with one item in the consequent that have a con dence at least equal to mincon dence are generated. We then create all consequents with 2 items that are possible in a rule generated from I 1 . This generation is performed by applying the Apriori-Gen function given in Section 2.1 to the set of one item consequents found in the rst step. Next the set of rules with 2 items in the consequent generated is pruned with respect to mincon dence. The 2 items consequents of the rules that hold are used for generating consequents with 3 items, etc. The pseudo-code is given in Algorithm 5.

Example Figure 8 gives the result of the frequent itemset discovery for the data mining context D, assuming that minsupport is 3 (60%). In Figure 9 we show the valid association rule generation for mincon dence = 0.5 (50%) using the previous result.

1) forall frequent k-itemsets l k 2 L k | k 2 do begin

2)

H 1 = { itemsets of size 1 that are subsets of l k };

3)

forall h 1 2 H 1 do begin 4)

con dence = support(l k )/support(l k h 1 ); // Con dence of r : (l k -h 1 ) )h 1 5)

if ( con dence mincon dence ) then

Experimental Results

We implemented the Apriori and Close algorithms in C++ on several Unix platforms, to assess their relative performances. Both used the same data structure (as described in Section 4.1.3) that improves Apriori e ciency. Our experiments were realized on a 43P240 bi-processor IBM Power-PC running AIX 4.1.5 with a CPU clock rate of 166 MHz, 1GB of main memory and a 9GB disk. Only one processor was used since the application was single-threaded. The test program was allowed a maximum of 128MB. We did not implement swapping; also, the system bu ers were not ushed between each database pass of the algorithms. In Section 1, we describe the datasets used for the experiments. We then compare relative performances of the two algorithms in Section 2.

Test Data

The algorithms were tested on two types of datasets: synthetic data, which mimic market basket data, and census data, which belong to the domain of statistical databases. For generating the synthetic dataset, we used the program described in 2]. This dataset, called T10I4D100K, contains 100,000 objects for an average object size of 10 items and an average size of the maximal potentially frequent itemsets of 4. The census data were extracted from the Kansas 1990 PUMS le (Public Use Microdata Samples), in the same way as 3] for the PUMS le of Washington (unavailable through Internet at the time of the experiments). Unlike in 3] though, we did not put an upper bound on the support, as this distorts each algorithm's results in di erent ways. We therefore took smaller datasets containing the rst 10,000 persons. Dataset C20D10K contains 20 attributes (20 items per object and 386 total items), and C73D10K, 73 attributes (73 items per object and 2178 total items).

Relative Performance of Apriori and Close

Synthetic Data

We used the same values for minsupport as the ones used in 2], ranging from 2% to 0.25%. The gure beside shows the execution times of Apriori and Close on the dataset T10I4D100K. We can observe that Apriori performs better than Close on these data. The reason is that, in such datasets, data are weakly correlated and sparse; furthermore, nearly all frequent itemsets are closed. For an identical number of database passes, Close performs more operations to compute the closure of the generators. Response times remain however acceptable: two minutes and a half for the longest execution.

Census Data

Experiments were conducted on the two census datasets using di erent minsupport ranges to get meaningful response times and to accommodate with the memory space limit. Results for the C20D10K and C73D10K datasets are plotted on Figure 11 and Figure 12 respectively. Close always signi cantly outperforms Apriori, for execution times as well as number of database passes. Here, contrarily to the experiments on synthetic data, the di erences between the execution times can be counted in hours. It should furthermore be noted that Apriori could not be run for minsupport lower than 3% on C20D10K and lower than 70% on C73D10K as it exceeds the memory limit. Census datasets are typical of statistical databases: highly correlated and dense data. Many items being extremely popular, this leads to a huge number of frequent itemsets.

Scale up on Census Data

We nally examined how Apriori and Close behave as the object size is increased in census data. The number of objects was xed to 10,000 and the minsupport level was set to 10%. The object size varied from 10 (281 total items) up to 24 (408 total items). Apriori could not be run for higher object sizes. Results are shown in Figure 13. We can see here that, as expected, Close outperforms Apriori both in execution times and in memory space requirements.

Conclusion

We presented a new algorithm, called Close, for mining association rules in large databases. Close is based on the pruning of the closed itemset lattice, unlike existing algorithms that are all based on the pruning of the itemset lattice. As the number of itemsets and the height of the closed itemset lattice of a database are much smaller than those of the itemset lattice, Close can reduce both the number of database passes and the CPU overhead incurred by the frequent itemset search. We conducted performance evaluations to compare Close to an optimized version of Apriori using pre x-tree, which corresponds to the basic approach for nding association rules by pruning the itemset lattice. Experiments were carried out using two types of databases: synthetic data (often used as a benchmark for mining market basket data) and census data (a real-life statistical database application). Experimental results showed that Close is less e cient, but gives nonetheless acceptable response times, for mining synthetic data. On the contrary, Close clearly outperforms Apriori in the case of census data, in particular for large problems (that are more signi cant of real-life datasets). The number of database passes is reduced from a quarter to a half in comparison with the number of passes Apriori needs. Moreover, in all the cases, Close was able to discover association rules for low minsupport values that Apriori cannot treat because of its memory space requirements. Close is particularly well suited to statistical database applications that are considered as di cult problems.

In addition to the discovery of association rules, our algorithm has another important feature: Close gives an e cient computing of the Dedekind-MacNeille completion of an order 5], which is the smallest lattice associated with an order and is isomorphic to the closed itemset

Figure 1 :

 1 Figure 1: The transaction database D 2 Related Work and Contribution

Figure 2 :

 2 Figure 2: Itemset lattice of D

  gives the closed itemset lattice of D with frequent closed itemsets for minsupport = 2 outlined.

Figure 4 :

 4 Figure 4: Closed itemset lattice of D 4 C 1 is a sub-closed itemset of C 2 and C 2 is a sup-closed itemset of C 1

  de ne the set MC of maximal frequent closed itemsets as: MC = fC 2 FC j @C 0 2 FC; C C 0 g Property 3: All sub-closed itemsets of a frequent closed itemset are frequent. Proof: Derived from Property 1. Property 4: All sup-closed itemsets of an infrequent closed itemset are infrequent. Proof: Derived from Property 2. Property 5: The support of an itemset I is equal to the support of the smallest closed itemset containing I. Proof: Let I I be an itemset. The support of I in D is: support(I) = kg(I)k kOk Now, we consider g f(I), the closure of I. Since g(I) is closed and by consequence f g(g(I))= g(I) (according to Property (5) of the Galois connection), we have: support(g f(I)) = kg(g f(I))k kOk = kf g(g(I))k kOk = kg(I)k kOk = support(I) Property 6: The set of maximal frequent itemsets M is identical to the set of maximal frequent closed itemsets MC.

  Gen-Closure(F CC i ); // Produces closures of generators (see Section 4.1FC = S j=i 1 j=1 (F C j .closure,F C j .support); Algorithm 2: Algorithm Close value are inserted in the set of frequent closed itemsets FC i . Finally, the generators of the set FCC i+1 are determined by applying the function Gen-Generator (described in Section 4.1.2) to the generators of the frequent closed itemsets in FC i . This process takes place until FCC i+1 is empty. Then, all frequent closed itemsets have been produced and their supports are known.4.1.1 Gen-Closure FunctionThe closure function Gen-Closure takes as argument the set of generator itemsets in FCC i . It updates FCC i with, for each generator p, the closed itemset p.closure and its support count p.support obtained by applying the closure operator g f to p. Algorithm 3 gives the pseudo-code of the function. The method used for computing closed itemsets is based on Proposition 1. Proposition 1: The closed itemset g f(I) corresponding to the closure by g f of the itemset I is the intersection of all objects in the database that contain I : g f(I) = \ o2O ff(fog) j I f(fog)g Proof: We de ne H = T o2S f(fog) where S = fo 2 O j I f(fog)g. We have g f(I) = f(g(I)) = T o2g(I) f(fog) = T o2S 0 f(fog) where S 0 = fo 2 O j o 2 g(I)g. Let's show that S 0 = S: I f(fog) () o 2 g(I) o 2 g(I) () I f(g(I)) f(fog)

  Subset(F CC i .generator,f(fog)); // Generators subsets of f({o}) (Section 4.1.closure = ; ) then p.closure = f(fog); 5) else p.closure = p.closure \f(fog); = S { c 2 FCC i | c.closure 6 = ; }; Algorithm 3: Function Gen-Closure used during iteration i + 1 for constructing the set of candidate frequent closed itemsets.

Figure 7 :

 7 Figure 7: Deriving frequent itemsets for minsupport = 2 (40%)

Figure 9 :

 9 Figure 9: Generating valid association rules for minsupport=3 (60%) and mincon dence=0.5 (50%)

Figure 10 :

 10 Figure 10: Performance of Apriori and Close on synthetic data

Figure 11 :Figure 12 :Figure 13 :

 111213 Figure 13: Scale-up properties of Apriori and Close on census data

Table 1 :

 1 Notation

  .

	Scan D !	C1 Itemset Support {A} 3 {B} 4 {C} 4 {D} 1 {E} 4	Pruning of Infrequent itemsets !	L1 Itemset Support {A} 3 {B} 4 {C} 4 {E} 4
	Scan D !	C2 Itemset Support {AB} 2 {AC} 3 {AE} 2 {BC} 3 {BE} 4 {CE} 3	Pruning of Infrequent itemsets !	L2 Itemset Support {AB} 2 {AC} 3 {AE} 2 {BC} 3 {BE} 4 {CE} 3
	Scan D !	C3 Itemset Support {ABC} 2 {ABE} 2 {ACE} 2 {BCE} 3	Pruning of Infrequent itemsets !	L3 Itemset Support {ABC} 2 {ABE} 2 {ACE} 2 {BCE} 3
	Scan D !	C4 Itemset Support {ABCE} 2	Pruning of Infrequent itemsets !	L4 Itemset Support {ABCE} 2
	Figure 3: Discovering frequent itemsets with Apriori for minsupport = 2(40%)

  Field Contains FCC i generator A generator itemset of size i. closure Candidate closed itemset produced by the closure of generator: closure = g f(generator). support Support count of the closed itemset: support = count(closure). FC i generator Generator of the frequent closed itemset. closure Frequent closed itemset (closed itemset with support greater or equal to minsupport).

Table 2 :

 2 Notation

http://www.almaden.ibm.com/cs/quest/syndata.html

ftp://ftp2.cc.ukans.edu/pub/ippr/census/pums/pums90ks.zip

Here, we use the following notation: g f(I) = f(g(I)) and f g(O) = g(f(O)).

Closed subsets of a closed itemset.

Closed supersets of a closed itemset.


Nicolas Pasquier
email: fpasquier@libd1.univ-bpclermont.fr

Yves Bastide
email: bastide@libd1.univ-bpclermont.fr

Ra K Taouil
email: taouil@libd1.univ-bpclermont.fr

Lot Lakhal
email: lakhalg@libd1.univ-bpclermont.fr

Discovering Frequent Closed Itemsets for Association Rules

In this paper, we address the problem of nding frequent itemsets in a database. Using the closed itemset lattice framework, we show that this problem can be reduced to the problem of nding frequent closed itemsets. Based on this statement, we can construct e cient data mining algorithms by limiting the search space to the closed itemset lattice rather than the subset lattice. Moreover, we show that the set of all frequent closed itemsets su ces to determine a reduced set of association rules, thus addressing another important data mining problem: limiting the number of rules produced without information loss. We propose a new algorithm, called A-Close, using a closure mechanism to nd frequent closed itemsets. We realized experiments to compare our approach to the commonly used frequent itemset search approach. Those experiments showed that our approach is very valuable for dense and/or correlated data that represent an important part of existing databases.

Introduction

The discovery of association rules was rst introduced in 1]. This task consists in determining relationships between sets of items in very large databases.

Agrawal's statement of this problem is the following 1, 2]. Let I = fi 1 ; i 2 ; : : : ; i m g be a set of m items. Let the database D = ft 1 ; t 2 ; : : : ; t n g be a set of n transactions, each one identi ed by its unique TID. Each transaction t consists of a set of items I from I. If kIk = k, then I is called a k-itemset. An itemset I is contained in a transaction t 2 D if I t. The support of an itemset I is the percentage of transactions in D containing I. Association rules are of the form r : I 1 c ! I 2 , with I 1 ; I 2 I and I 1 \ I 2 = ;. Each association rule r has a support de ned as support(r) = support(I 1 I 2 ) and a con dence c de ned as confidence(r) = support(I 1 I 2 ) = support(I 1 ). Given the user de ned minimum support minsup and minimum con dence minconf thresholds, the problem of mining association rules can be divided into two sub-problems 1]:

1. Find all frequent itemsets in D, i.e. itemsets with support greater or equal to minsup.

2. For each frequent itemset I 1 found, generate all association rules I 2 c ! I 1 I 2 where I 2 I 1 , with con dence c greater or equal to minconf. Once all frequent itemsets and their support are known, the association rule generation is straightforward. Hence, the problem of mining association rules is reduced to the problem of determining frequent itemsets and their support.

Recent works demonstrated that the frequent itemset discovery is also the key stage in the search for episodes from sequences and in nding keys or inclusion as well as functional dependencies from a relation 12]. All existing algorithms use one of the two following approach: a levelwise 12] bottom-up search 2, 5, 13, [START_REF] Savasere | An e cient algorithm for mining association rules in larges databases[END_REF][START_REF] Toivonen | Sampling large databases for association rules[END_REF] or a simultaneous bottom-up and top-down search [START_REF] Bayardo | E ciently mining long patterns from databases[END_REF][START_REF] Lin | Pincer-search: A new algorithm for discovering the maximum frequent set[END_REF][START_REF] Zaki | New algorithms for fast discovery of association rules[END_REF]. Although they are dissimilar, all those algorithms explore the subset lattice (itemset lattice) for nding frequent itemsets: they all use the basic properties that all subsets of a frequent itemset are frequent and that all supersets of an infrequent itemset are infrequent in order to prune elements of the itemset lattice.

In this paper, we propose a new e cient algorithm, called A-Close, for nding frequent closed itemsets and their support in a database. Using a closure mechanism based on the Galois connection, we de ne the closed itemset lattice which is a sub-order of the itemset lattice, thus often much smaller. This lattice is closely related to the Galois lattice 4, 7] also called concept lattice 19]. The closed itemset lattice can be used as a formal framework for discovering frequent itemsets given the basic properties that the support of an itemset I is equal to the support of its closure and that the set of maximal frequent itemsets is identical to the set of maximal frequent closed itemsets. Then, once A-Close has discovered all frequent closed itemsets and their support, we can directly determine the frequent itemsets and their support. Hence, we reduce the problem of mining association rules to the problem of determining frequent closed itemsets and their support.

Using the set of frequent closed itemsets, we can also directly generate a reduced set of association rules without having to determine all frequent itemsets, thus lowering the algorithm computation cost. Moreover, since there can be thousands of association rules holding in a database, reducing the number of rules produced without information loss is an important problem for the understandability of the result 18]. Empirical evaluations comparing A-Close to an optimized version of Apriori showed that they give nearly always equivalent results for weakly correlated data (such as synthetic data) and that A-Close clearly outperforms Apriori for correlated data (such as statistical or text data).

The rest of the paper is organized as follows. In Section 2, we present the closed itemset lattice. In Section 3, we propose a new model for association rules based on the Galois connection and we characterize a reduced set of association rules. In Section 4, we describe the A-Close algorithm. Section 5 gives experimental results on synthetic data1 and census data using the PUMS le for Kansas USA 2 and Section 6 concludes the paper.

Closed Itemset Lattices

In this section, we de ne data mining context, Galois connection, Galois closure operators, closed itemsets and closed itemset lattice. Interested readers should read 4, 7, 19] for further details on order and lattice theory.

De nition 1 (Data mining context). A data mining context 3 (1)

I 1 I 2 ) g(I 1 ) g(I 2 ) (1') O 1 O 2 ) f(O 1 ) f(O 2 ) (2) O g(I) () I f(O)
De nition 3 (Galois closure operators). The operators h = f g in 2 I and h 0 = g f in 2 O are Galois closure operators 4 . Given the Galois connection (f; g), De nition 5 (Closed itemset lattice). Let C be the set of closed itemsets derived from D using the Galois closure operator h. The pair L C = (C; ) is a complete lattice called closed itemset lattice. The lattice structure implies two properties: i) There exists a partial order on the lattice elements such that, for every ele- 5 . ii) All subsets of L C have one greatest lower bound, the Join element, and one lowest upper bound, the Meet element. 3 By extension, we call database a data mining context afterwards.

ments C 1 ; C 2 2 L C , C 1 C 2 , i C 1 C 2
Below, we give the de nitions of the Join and Meet elements extracted from the basic theorem on Galois (concept) lattices [START_REF] Birkho | Lattices theory[END_REF][START_REF] Davey | Introduction to Lattices and Order[END_REF][START_REF] Wille | Concept lattices and conceptual knowledge systems[END_REF]. For all S L C :

Join (S) = h( C2S C); Meet (S) = \ C2S C OID Items 1 A C D 2 B C E 3 A B C E 4 B E 5 A B C E ABCDE ABCE AC BE C ACD BCE Ø
Fig. 1. The data mining context D and its associated closed itemset lattice.

Association Rule Model

In this section, we de ne frequent and maximal frequent itemsets and closed itemsets using the Galois connection. We then de ne association rules and valid association rules, and we characterise a reduced set of valid association rules in a data mining context D.

Frequent Itemsets

De nition 6 (Itemset support). Let I I be a set of items from D. The support count of the itemset I in D is: support(I) = kg(I)k kOk De nition 7 (Frequent itemsets). The itemset I is said to be frequent if the support of I in D is at least minsup. The set L of frequent itemsets in D is: L = fI I j support(I) minsupg De nition 8 (Maximal frequent itemsets). Let L be the set of frequent itemsets. We de ne the set M of maximal frequent itemsets in D as: M = fI 2 L j 6 9I 0 2 L; I I 0 g Property 1. All subsets of a frequent itemset are frequent (intuitive in 2]).

Proof. Let I; I 0 I, I 2 L and I 0 I. According to Property (1) of the Galois connection: I 0 I =) g(I 0 ) g(I) =) support(I 0 ) support(I) minsup.

So, we get: I 0 2 L. Since all maximal frequent itemsets are also maximal frequent closed itemsets, we get: M = MC.

Association Rule Semantics De nition 11 (Association rules

). An association rule is an implication between itemsets of the form I 1 c

!I 2 where I 1 ; I 2 I and I 1 \ I 2 = ;. Below, we de ne the support and con dence c of an association rule r : I 1 c ! I 2 using the Galois connection: support(r) = kg(I 1 I 2 )k kOk ; confidence(r) = support(I 1 I 2 ) support(I 1 ) = kg(I 1 I 2 )k kg(I 1 )k De nition 12 (Valid association rules). A valid association rules is an association rules with support and con dence greater or equal to the minsup and minconf thresholds respectively. We de ne the set AR of valid association rules in D using the set MC of maximal frequent closed itemsets as: AR(D; minsup, minconf) = fr : I 2 c

! I 1 I 2 ; I 2 I 1 j I 1 2 L = C2MC 2 C and confidence(r) minconfg

Reduced Set of Association Rules

Let I 1 ; I 2 I and I 1 \ I 2 = ;. An association rule r : I 1 c ! I 2 is an exact association rule if c = 1. Then, r is noted r : I 1 ) I 2 . An association rule r : I 1 c ! I 2 where c < 1 is called an approximate association rule. Let D be a data mining context.

De nition 13 (Pseudo-closed itemsets). An itemset I I from D is a pseudo-closed itemset i h(I) 6 = I and 8I 0 I such as I 0 is a pseudo-closed itemset, we have h(I 0 ) I.

Theorem 1 (Exact association rules basis 8]). Let P be the set of pseudoclosed itemsets and R the set of exact association rules in D. The set E = fr : I 1 )h(I 1 ) I 1 j I 1 2 Pg is a basis for all exact association rules. 8r 0 2 R where con dence(r 0 ) = 1 minconf we have E j = r 0 . Corollary 1 (Exact valid association rules basis). Let FP be the set of frequent pseudo-closed itemsets in D. The set BE = fr : I 1 )h(I 1 ) I 1 j I 1 2 FPg is a basis for all exact valid association rules. 8r 0 2 AR where con dence(r 0 ) = 1 we have BE j = r 0 . Theorem 2 (Reduced set of approximate association rules 11]). Let C be the set of closed itemsets and R the set of approximate association rules in D. The set A = fr : I 1 c !I 2 I 1 j I 2 I 1 ^I1 ; I 2 2 Cg is a correct reduced set for all approximate association rules. 8r 0 2 R where minconf con dence(r 0 ) < 1 we have A j = r 0 . Corollary 2 (Reduced set of approximate valid association rules). Let FC be the set of frequent closed itemsets in D. The set BA = fr : I 1 c ! I 2 I 1 j I 2 I 1 ^I1 ; I 2 2 FCg is a correct reduced set for all approximate valid assocition rules. 8r 0 2 AR where con dence(r 0 ) 1 we have BA j = r 0 .

A-Close Algorithm

In this section, we present our algorithm for nding frequent closed itemsets and their supports in a database. Section 4.1 describes its principle. In Section 4.2 to 4.5, we give the pseudo-close of the algorithm and the sub-functions it uses. Section 4.6 provides an example and the proof of the algorithm correctness.

A-Close Principle

A closed itemset is a maximal set of items common to a set of objects. For example, in the database D in Figure 1, the itemset BCE is a closed itemset since it is the maximal set of items common to the objects f2; 3; 5g. BCE is called a frequent closed itemset for minsup = 2 as support(BCE) = kf2; 3; 5gk = 3 minsup. In a basket database, this means that 60% of customers (3 customers on a total of 5) purchase at most the items B; C and E. The itemset BC is not a closed itemset since it is not a maximal group of items common to some objects: all customers purchasing the items B and C also purchase the item E.

The closed itemset lattice of a nite relation (the database) is dually isomorphic to the Galois lattice 4, 7], also called concept lattice 19].

Based on the closed itemset lattice properties (Section 2 and 3), using the result of A-Close we can generate all frequent itemsets from a database D through the two following phases:

1. Discover all frequent closed itemsets in D, i.e. itemsets that are closed and have support greater or equal to minsup. 2. Derive all frequent itemsets from the frequent closed itemsets found in phase 1.

That is generate all subsets of the maximal frequent closed itemsets and derive their support from the frequent closed itemset supports. A di erent algorithm for nding frequent closed itemsets and algorithms for deriving frequent itemsets and generating valid association rules are presented in 15].

Using the result of A-Close, we can directly generate the reduced set of valid association rules de ned in Section 3.4 instead of determining all frequent itemsets. The procedure is the following:

1. Discover all frequent closed itemsets in D.

2. Determine the exact valid association rule basis: determine the pseudo-closed itemsets in D and then generate all rules r : I 1 ) I 2 I 1 j I 1 I 2 where I 2 is a frequent closed itemset and I 1 is a frequent pseudo-closed itemset.

3. Construct the reduced set of approximate valid association rules: generate all rules of the form: r : I 1 c ! I 2 I 1 j I 1 I 2 where I 1 and I 2 are frequent closed itemsets. In the two cases, the rst phase is the most computationally intensive part. After this phase, no more database pass is necessary and the later phases can be solved easily in a straightforward manner. Indeed, the rst phase has given us all information needed by the next ones.

A-Close discovers the frequent closed itemsets as follows. Based on the closed itemset properties, it determines a set of generators that will give us all frequent closed itemsets by application of the Galois closure operator h. An itemset p is a generator of a closed itemset c if it is one of the smallest itemsets (there can be more than one) that will determine c using the Galois closure operator: h(p) = c.

For instance, in the database D (Figure 1), BC and CE are generators of the closed itemset BCE. The itemsets B, C and E are not generators of BCE since h(C) = C and h(B) = h(E) = BE. The itemset BCE is not a generator of itself since it includes BC and CE: BCE is not one of the smallest itemsets for which closure is BCE.

The algorithm constructs the set of generators in a levelwise manner: (i+1)generators 6 are created using i-generators in G i . Then, their support is counted and the useless generators are pruned. According to their supports and the supports of their i-subsets in G i , infrequent generators and generators that have the same closure as one of their subsets are deleted from G i+1 . In the previous example, the support of the generator BCE is the same as the support of generators BC and CE since they have the same closure (Property 3). Once all frequent useful generators are found, their closures are determined, giving us the set of all frequent closed itemsets. For reducing the cost of the closure computation when possible, we introduce the following optimization. We determine the rst iteration of the algorithm for which a (i+1)-generator was pruned because it had the same closure as one of its i-subsets. In all iterations preceding the i th one, the generators created are closed and their closure computation is useless. Hence, we can limit the closure computation to generators of size greater or equal to i. For this purpose, the level variable indicates the rst iteration for which a generator was pruned by this pruning strategy.

Discovering Frequent Closed Itemsets

As in the Apriori algorithm, items are sorted in lexicographic order. The pseudocode for discovering frequent closed itemsets is given in Algorithm 1. The notation is given in Table 1. In each of the iterations that construct the candidate generators, one pass over the database is necessary in order to count the support of the candidate generators. At the end of the algorithm, one more pass is needed for determining the closures of generators that are not closed. If all generators are closed, this pass is not made.

First, the algorithm determines the set G 1 of frequent 1-generators and their support (step 1 to 5). Then, the level variable is set to 0 (step 6). In each of the following iterations (step 7 to 9), the AC-Generator function (Section 4.4) is applied to the set of generators G i , determining the candidate (i+1)-generators and their support in G i+1 (step 8). This process takes place until G i is empty.

Finally, closures of all generators produced are determined (step 10 to 14). Using the level variable, we construct two sets of generators. The set G which contains generators p for which size is less than level 1, and so that are closed (p = h(p)). 6 A generator of size i is called an i-generator.

Set Field Contains

Gi generator A generator of size i.

support Support count of the generator: support = count(generator) G; G 0 generator A generator of size i.

closure Closure of the generator: closure = h(generator). support Support count of the generator and its closure: support = count(closure) = count(generator) (Property 3). FC closure Frequent closed itemset (closed itemset with support minsup).

support Support count of the frequent closed itemset.

Table 1. Notation

The set G 0 which contains generators for which size is at least level 1, among which some are not closed, and so for which closure computation is necessary.

The closures of generators in G 0 are determined by applying the AC-Generator function (Section 4.4) to G 0 (step 15). Then, all frequent closed itemsets have been produced and their support is known (see Theorem 3).

Algorithm 1 A-Close algorithm 1) generators in G1 f1-itemsetsg;

2) G1 Support-Count(G1);

3) forall generators p 2 G1 do begin The Subset function quickly determines which generators are contained in an object 7 , i.e. generators that are subsets of f(fog). For this purpose, generators are stored in a pre x-tree structure derived from the one proposed in 14].

AC-Generator Function

The function takes the set G i of frequent as argument. Based on Lemma 1 and 2, it returns the set G i+1 of frequent (i+1)-generators. The pseudocode of the function is given in Algorithm 3. Lemma 1. Let I 1 ; I 2 be two itemsets. We have: h(I 1 I 2 ) = h(h(I 1 ) h(I 2 ))

Proof. Let I 1 and I 2 be two itemsets. According to the extension property of the Galois closure operators: I 1 h(I 1 ) and I 2 h(I 2 ) =) I 1 I 2 h(I 1 ) h(I 2 ) =) h(I 1 I 2 ) h(h(I 1 ) h(I 2 ))

Obviously, I 1 I 1 I 2 and I 2 I 1 I 2 . So h(I 1 ) h(I 1 I 2 ) and h(I 2 ) h(I 1 I 2 ). According to the idempotency property of the Galois closure operators: h(h(I 1 ) h(I 2 )) h(h(I 1 I 2 )) =) h(h(I 1 ) h(I 2 )) h(I 1 I 2 )

(

From ( 1) and ( 2), we conclude that h(I 1 I 2 ) = h(h(I 1 ) h(I 2 )).

Lemma 2. Let I 1 be an itemset and I 2 a subset of I 1 where support(I 1 ) = support(I 2 ). Then we have h(I 1 ) = h(I 2 ) and 8I 3 I, h(I 1 I 3 ) = h(I 2 I 3 ).

Proof. Let I 1 ; I 2 be two itemsets where I 2 I 1 and support(I 1 ) = support(I 2 ).

Then, we have that kg(I 1 )k = kg(I 2 )k and we deduce that g(I 1 ) = g(I 2 ). From this, we conclude f(g(I 1 )) = f(g(I 2 )) =) h(I 1 ) = h(I 2 ). Let I 3 I be an itemset. Then according to Lemma 1:

h(I 1 I 3 ) = h(h(I 1 ) h(I 3 )) = h(h(I 2 ) h(I 3 )) = h(I 2 I 3 ) 7 We say that an itemset I is contained in object o if o is related to all items i 2 I. Corollary 3. Let I be an i-generator and S = fs 1 ; s 2 ; : : : ; s j g a set of (i 1)subsets of I where S s2S s = I. If 9s 2 S such as support(s) = support(I), then h(I) = h(s).

Proof. Derived from Lemma 2.

The AC-Generator function works as follows. We rst apply the combinatorial phase of Apriori-Gen 2] to the set of generators G i in order to obtain a set of candidate (i+1)-generators: two generators of size i in G i with the same rst i 1 items are joined, producing a new potential generator of size i + 1 (step 1 to 4). Then, the potential generators produced that will lead to useless computations (infrequent closed itemsets) or redundancies (frequent closed itemsets already produced) are pruned from G i+1 as follows.

First, like in Apriori-Gen, G i+1 is pruned by removing every candidate (i+1)generator c such that some i-subset of c is not in G i (step 8 and 9). Using this strategy, we prune two kinds of itemsets: rst, all supersets of infrequent generators (that are also infrequent according to Property 2); second, all generators that have the same support as one of their subset and therefore have the same closure (see Theorem 3). Let's take an example. Suppose that the set of frequent closed itemsets G 2 contains the generators AB; AC. The AC-Generator function will create ABC = AB AC as a new potential generator in G 3 and the rst pruning will remove ABC since BC = 2 G 2 .

Next, the supports of the remaining candidate generators in G i+1 are determined and, based on Property 2, those with support less than minsup are deleted from G i+1 (step 7).

The third pruning strategy works as follows. For each candidate generator c in G i+1 , we test if the support of one of its i-subsets s is equal to the support of c. In that case, the closure of c will be equal to the closure of s (see Corollary 3), so we remove c from G i+1 (step 10 to 13). Let's give another example. Suppose that the nal set of generators G 2 contains frequent generators AB; AC; BC and their respective supports 3; 2; 3. The AC-Generator function will create ABC = AB AC as a new potential generator in G 3 and suppose it determines its support is 2. The third prune step will remove ABC from G 3 since support(ABC) = support(AC). Indeed, we deduce that closure(ABC) = closure(AC) and the computation of the closure of ABC is useless. For the optimization of the generator closure computation in Algorithm 1, we determine the iteration at which the second prune suppressed a generator (variable level).

AC-Closure Function

The AC-Closure function takes the set of frequent generators G, for which closures must be determined, as argument. It updates G with, for each generator p 2 G, the closed itemset p.closure obtained by applying the closure operator h to p. Algorithm 4 gives the pseudo-code of the function. The method used to compute closures is based on Proposition 1.

Algorithm 3 AC-Generator function 1) insert into Gi+1

2) select p.item1, p.item2, : : : , p.itemi, q.itemi 3) from Gi p, Gi q 4) where p.item1 = q.item1, : : : , p.itemi 1 = q.itemi 1, p.itemi < q.itemi; 5) forall candidate generators c 2 Gi+1 do begin [START_REF] Chen | Data mining: An overview from a database perspective[END_REF] forall i-subsets s of c do begin [START_REF] Davey | Introduction to Lattices and Order[END_REF] if (s = 2 Gi) then delete c from Gi+1; 8) end 9) end 10) Gi+1 Support-Count(Gi+1); 11) forall candidate generators c 2 Gi+1 do begin [START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF] if (support(c) < minsup) then delete c from Gi+1; // Pruning infrequent 13) else do begin [START_REF] Mueller | Fast sequential and parallel algorithms for association rules mining: A comparison[END_REF] forall i-subsets s of c do begin [START_REF] Pasquier | Pruning closed itemset lattices for association rules[END_REF] if (support(s) = support(c)) then begin Proof. We de ne H = T o2S f(fog) where S = fo 2 O j I f(fog)g. We have h(I) = f(g(I)) = T o2g(I) f(fog) = T o2S 0 f(fog) where S 0 = fo 2 O j o 2 g(I)g.

Let's show that S 0 = S:

I f(fog) () o 2 g(I) o 2 g(I) () I f(g(I)) f(fog)
We conclude that S = S 0 , thus h(I) = H.

Using Proposition 1, only one database pass is necessary to compute the closures of the generators. The function works as follows. For each object o in D, the set G o is created (step 2). G o contains all generators in G that are subsets of the object itemset f(fog). Then, for each generator p in G o , the associated closed itemset p.closure is updated (step 3 to 6). If the object o is the rst one containing the generator, p.closure is empty and the object itemset f(fog) is assigned to it (step 4). Otherwise, the intersection between p.closure and the object itemset gives the new p.closure (step 5). At the end, the function returns else p.closure p.closure \ f(fog); 6) end 7) end 8) Answer S fp 2 G j 6 9p 0 2 G; closure(p 0 )=closure(p)g; for each generator p in G, the closed itemset p.closure corresponding to the intersection of all objects containing p.

Example and Correctness

Figure 2 gives the execution of A-Close for a minimum support of 2 (40%) on the data mining context D given in Figure 1. First, the algorithm determines the set G 1 of 1-generators and their support (step 1 and 2), and the infrequent generator D is deleted form G 1 (step 3 to 5). Then, generators in G 2 are determined by applying the AC-Generator function to G 1 (step 8): the 2-generators are created by union of generators in G 1 , their support is determined and the three pruning strategies are applied. Generators AC and BE are pruned since support(AC) = support(A) and support(BE) = support(B), and the level variable is set to 2.

Calling AC-Generator with G 2 produces 3-generators in G 3 . The only generator created in G 3 is ABE since only AB and AE have the same rst item. The three pruning strategies are applied and the second one removes ABE form G 3 as BE = 2 G 2 . Then, G 3 is empty and the iterative construction of sets G i terminates (the loop in step 7 to 9 stops).

The sets G and G 0 are constructed using the level variable (step 10 and 11): G is empty and G 0 contains generators from G 1 and G 2 . The closure function AC-Closure is applied to G 0 and the closures of all generators in G 0 are determined (step 15). Finally, duplicates closures are removed from G 0 by AC-Closure and the result is returned to the set FC which therefore contains AC,BE,C,ABCE and BCE, that are all frequent closed itemsets in D. Lemma 3. For p I such as kpk > 1, if p = 2 G kpk and support(p) minsup then 9s 1 ; s 2 I, s 1 s 2 p and ks 1 k = ks 2 k 1 such as h(s 1 ) = h(s 2 ) and s 1 2 G ks1 k . Proof. We show this using a recurrence. For kpk = 2, we have p = s 2 and 9s 1 2 G 1 j s 1 s 2 and support(s 1 ) = support(s 2 ) =) h(s 1 ) = h(s 2 ) (Lemma 3 is obvious). Then, supposing that Lemma 3 is true for kpk = i, let's show that it is true for kpk = i + 1. Let p I j kpk = i + 1 and p = 2 G kpk . There are two possible cases:

(1) 9p 0 p j kp 0 k = i and p 0 = 2 G kp 0 k (2) 9p 0 p j kp 0 k = i and p 0 If (1) then according to the recurrence hypothesis, 9s 1 s 2 p 0 p such as h(s 1 ) = h(s 2 ) and s 1 2 G ks1 k . If (2) then we identify s 1 to p 0 and s 2 to p. Results on Synthetic Data Figure 3 shows the execution times of Apriori and A-Close on the datasets T10I4D100K and T20I6D100K. We can observe that both algorithms always give similar results except for executions with minsup = 0.5% and 0.33% on T20I6D100. This similitude comes from the fact that data are weakly correlated and sparse in such datasets. Hence, the sets of generators in A-Close and frequent itemsets in Apriori are identical, and the closure mechanism does not help in jumping iterations. In the two cases where Apriori outperforms A-Close, there was in the 4 th iteration a generator that has been pruned because it had the same support as one of its subsets. As a consequence, A-Close determined closures of all generators with size greater or equal than 3.

Results on Census Data Experiments were conducted on the two census datasets using di erent minsup ranges to get meaningful response times and to accommodate with the memory space limit. Results for the C20D10K and C73D10K datasets are plotted on Figure 4 and 5 respectively. A-Close always signi cantly outperforms Apriori, for execution times as well as number of database passes. Here, contrarily to the experiments on synthetic data, the di erences between execution times can be measured in minutes for C20D10K and in hours for

Scale up Properties on Census Data We nally examined how Apriori and

A-Close behave as the object size is increased in census data. The number of objects was xed to 10,000 and the minsup level was set to 10%. The object size varied from 10 (281 total items) up to 24 (408 total items). Apriori could not be run for higher object sizes. Results are shown in Figure 6. We can see here that, the scale up properties of A-Close are far better than those of Apriori.

Conclusion

We presented a new algorithm, called A-Close, for discovering frequent closed itemsets in large databases. This algorithm is based on the pruning of the closed itemset lattice instead of the itemset lattice, which is the commonly used approach. This lattice being a sub-order of the itemset lattice, for many datasets, the number of itemsets considered will be signi cantly reduced. Given the set of frequent closed itemsets and their support, we showed that we can either deduce all frequent itemsets, or construct a reduced set of valid association rules needless the search for frequent itemsets.

We realized experiments in order to compare our approach to the itemset lattice exploration approach. We implemented A-Close and an optimized version of Apriori using pre x-trees. The choice of Apriori leads form the fact that, in practice, it remains one of the most general and powerful algorithms. Those experiments showed that A-Close is very e cient for mining dense and/or correlated data (such as statistical data): on such datasets, the number of itemsets considered and the number of database passes made are signi cantly reduced Fig. 6. Scale-up properties of Apriori and A-Close on census data compared to those Apriori needs. They also showed that A-Close leads to equivalent performances of the two algorithms for weakly correlated data (such as synthetic data) in which many generators are closed. This leads from the adaptive characteristic of A-Close that consists in determining the rst iteration for which it is necessary to compute closures of generators. Such a way, we avoid A-Close many useless closure computations.

We think these results are very interesting since dense and/or correlated data represent an important part of all existing data, and since mining such data is considered as very di cult. Statistical, text, biological and medical data are examples of such correlated data. Supermarket data are weakly correlated and quite sparse, but experimental results showed that mining such data is considerably less di cult than mining correlated data. In the rst case, executions take some minutes at most whereas in the second case, executions sometimes take several hours.

Moreover, A-Close gives an e cient unsupervised classi cation technic: the closed itemset lattice of an order is dually isomorphic to the Dedekind-MacNeille completion of an order 7], which is the smallest lattice associated with an order. The closest work is Ganter's algorithm 9] which works only in main memory. This feature is very interesting since unsupervised classi cation is another important problem in data mining 6] and in machine learning.

  is a triple D = (O; I; R). O and I are nite sets of objects and items respectively. R O I is a binary relation between objects and items. Each couple (o; i) 2 R denotes the fact that the object o 2 O is related to the item i 2 I. De nition 2 (Galois connection). Let D = (O; I; R) be a data mining context. For O O and I I, we de ne: f(O):

  the following properties hold for all I; I 1 ; I 2 I and O; O 1 ; O 2 O 4, 7, 19]: Extension : (3) I h(I) (3') O h 0 (O) Idempotency : (4) h(h(I)) = h(I) (4') h 0 (h 0 (O)) = h 0 (O) Monotonicity : (5) I 1 I 2 ) h(I 1 ) h(I 2 ) (5') O 1 O 2 ) h 0 (O 1 ) h 0 (O 2 ) De nition 4 (Closed itemsets). An itemset C I from D is a closed itemset i h(C) = C. The smallest (minimal) closed itemset containing an itemset I is obtained by applying h to I. We call h(I) the closure of I.

Property 2 .

 2 All supersets of an infrequent itemset are infrequent (intuitive in 2]). Proof. Let I; I 0 I, I 0 = 2 L and I 0 I. According to Property (1) of the Galois connection: I I 0 =) g(I) g(I 0 ) =) support(I) support(I 0 ) minsup. So, we get: I = 2 L.

  Proof. Let I I be an itemset. The support of I in D is: support(I) = kg(I)k kOk Now, we consider h(I), the closure of I. Let's show that h 0 (g(I)) = g(I). We have g(I) h(g(I)) (extension property of the Galois closure) and I h(I) )g(h(I)) g(I) (Property (1) of the Galois connection). We deduce that h 0 (g(I))= g(I), and therefore we have: support(h(I)) = kg(h(I))k kOk = kh 0 (g(I))k kOk = kg(I)k kOk = support(I) Property 4. The set of maximal frequent itemsets M is identical to the set of maximal frequent closed itemsets MC. Proof. It su ces to demonstrate that 8I 2 M, I is closed, i.e. I = h(I). Let I 2 M be a maximal frequent itemset. According to Property (3) of the Galois connection I h(I) and, since I is maximal and support(h(I)) = support(I) minsup, we conclude that I = h(I). I is a maximal frequent closed itemset.

Proposition 1 .

 1 = 0) then level i; // Iteration number of the rst prune 18The closed itemset h(I) corresponding to the closure by h of the itemset I is the intersection of all objects in the database that contain I: h(I) = \ o2O ff(fog) j I f(fog)g

Fig. 2 .

 2 Fig. 2. A-Close frequent closed itemset discovery for minsup = 2 (40%)

Fig. 4 .Fig. 5 .

 45 Fig. 4. Performance of Apriori and A-Close on census data C20D10K

  Rg f(O) associates with O the items common to all objects o 2 O and g(I) associates with I the objects related to all items i 2 I. The couple of applications (f; g) is a Galois connection between the power set of O (i.e. 2 O ) and the power set of I (i.e. 2 I ). The following properties hold for all I; I 1 ; I 2 I and O; O 1 ; O 2 O:

	2 O ! 2 I f(O)=fi 2 I j 8o 2 O; (o; i) 2 Rg	g(I): 2 I ! 2 O g(I)=fo 2 O j 8i 2 I; (o; i) 2

Table 2 .

 2 Theorem 3. The A-Close algorithm generates all frequent closed itemsets.Proof. Using a recurrence, we show that 8p I j support(p) minsup we have h(p) 2 FC. We rst demonstrate the property for the 1-itemsets: 8p I where kpk = 1, if support(p) minsup then p 2 G 1 ) h(p) 2 FC. Let's suppose that 8p I such as kpk = i we have h(p) 2 FC. We then demonstrate that 8p I where kpk = i + 1 we have h(p) 2 FC. If p 2 G kpk then h(p) 2 FC. Data We used two kinds of datasets: synthetic data, that simulate market basket data, and census data, that are typical statistical data. The synthetic datasets were generated using the program described in 2]. The census data were extracted from the Kansas 1990 PUMS le (Public Use Microdata Samples), in the same way as 5] for the PUMS le of Washington (unavailable through Internet at the time of the experiments). Unlike in 5] though, we did not put an upper bound on the support, as this distorts each algorithm results in di erent ways. We therefore took smaller datasets containing the rst 10,000 persons. Notation

	Else, if p =

Test

  Performance of Apriori and A-Close on synthetic data C73D10K. It should furthermore be noted that Apriori could not be run for minsup lower than 3% on C20D10K and lower than 70% on C73D10K as it exceeds the memory limit. Census datasets are typical of statistical databases: highly correlated and dense data. Many items being extremely popular, this leads to a huge number of frequent itemsets from which few are closed.

						800
				A-Close						A-Close
				Apriori						Apriori
						700
						600
	Time (seconds)				Time (seconds)	400 500
						300
						200
						100
						0
	1.5%	1%	0.75%	0.5%	0.33%	2%	1.5%	1%	0.75%	0.5%	0.33%
	Minimum support						Minimum support
	Execution times on T10I4D100K		Execution times on T20I6D100K
	Fig. 3.

http://www.almaden.ibm.com/cs/quest/syndata.html

ftp://ftp2.cc.ukans.edu/pub/ippbr/census/pums/pums90ks.zip

Here, we use the following notation: f g(I) = f(g(I)) and g f(O) = g(f(O)).

C1 is a sub-closed itemset of C2 and C2 is a sup-closed itemset of C1.

G kpk and according to Lemma

3, we have: 9s 1 s 2 p j s 1 2 G ks1 k and h(s 1 ) = h(s 2 ). Now h(p) = h(s 2 p s 2 ) = h(s 1 p s 2 ) and ks 1 p s 2 k = i, therefore in conformity with the recurrence hypothesis we conclude that h(s 1 p s 2 ) 2 FC and so h(p) 2 FC.