Introduction

It is widely known that frequent itemset based algorithms suffer from the generation of a very large number of frequent itemsets and hence association rules. Thus, this prohibitive generation reduces not only efficiency but also effectiveness of the mined knowledge. In fact, users have to perform tedious rummage within an overwhelming large number of mined association rules [1]. In this context, the approach based on the extraction of frequent closed itemsets [2] presented a clear promise to reduce the frequent itemset extraction cost and mainly to offer, to users, irreducible nuclei of association rules that are commonly known as "generic bases" of association rules. This approach, relying on the Formal Concept Analysis mathematical background [3], proposes to reduce the search space by detecting intrinsic structural properties. Therefore, the problem of mining association rules might be reformulated, under the (frequent) closed itemsets discovery point of view, as follows [4]:

1. Discover both distinct "closure systems", i.e., sets of sets which are closed under the intersection operator, namely the set of closed itemsets and the set of minimal generators. Also, the upper cover (Cov u ) of each closed itemset should be available. 2. From all discovered information during the first step, i.e., both closure systems and the upper cover sets, derive generic bases of association rules (from which all remaining association rules can be derived).

The essential report after an overview of the state of the art of frequent closed itemset based algorithms (e.g., [1,2,[5][6][7][8][9]) can be summarized in what follows:

1. These algorithms mainly concentrate on the first task, i.e., reducing the computation time of the frequent itemset extraction step. Their performances are interesting on dense contexts. However, they present modest performances on sparse contexts. Indeed, computing itemset closures in this type of contexts is heavily handicapping on these algorithm performances, since frequent closed itemset search space tends to overlap that of frequent itemsets. 2. The frequent closed itemset based algorithms neglect the second task, i.e., extracting generic association rule bases. Indeed, none of them accepted to maintain the order covering the relationship between frequent closed itemsets.

In this paper, we propose a new algorithm, called Prince, aiming to extract generic bases of association rules. Prince performs a level-wise browsing of the search space. Its main originality is that it is the only one who accepted to bear the cost of building the partial order. Interestingly enough, to amortize this prohibitive cost, the partial order is maintained between frequent minimal generators and no more between frequent closed itemsets. The obtained partially ordered structure is called minimal generator lattice [10], in which each equivalence class is reduced to the corresponding set of frequent minimal generators. Hence, itemset closures are not computed but derived when Prince performs a simple sweeping of the minimal generator lattice to derive generic bases of association rules. Practical performances of the Prince algorithm have been compared to those of well known level-wise browsing algorithms, i.e., Close [2], A-Close [5], and Titanic [6]. Our experiments were carried out on benchmark datasets (dense and sparse) and on "worst case" datasets. Obtained results are very encouraging: although our algorithm performs the partial order construction task, it largely outperforms Close, A-Close, and Titanic algorithms. In addition to the "worst case" datasets and due to space limit, we report our results only on two benchmark datasets, frequently used for evaluating data mining algorithms.

It is important to note that omitting to compare Prince performances to those of more recent algorithms, e.g., LCM [8], DCI-Closed [9], is argued by two reasons:

1. Close, A-Close and Titanic algorithms determine at least the "key" information provided by the frequent minimal generator set. 2. Following our claim that stressing on fast enumeration of frequent closed itemsets will not be of any interest nor presents any added-value knowledge for end-users, since not all required information is extracted.

The remainder of the paper is organized as follows. Section 2 sketches the generic association rule basis extraction problem. Section 3 is dedicated to the presentation of Prince algorithm. Experimental results showing the utility of the proposed approach are reported in section 4. The conclusion and future work are presented in section 5.

Generic association rule basis extraction

Since the apparition of the approach based on the extraction of frequent closed itemsets [2], several generic association rule bases were introduced among which those of Bastide et al. [11] and which are defined as follows:

1. The generic basis for exact association rules is defined as follows:

Definition 1. Let FCI K be the set of frequent closed itemsets extracted from the extraction context K. For each entry f in FCI K , let MG f be the set of its minimal generators. The generic basis for exact association rules GB is given by: GB = {R:

g ⇒ (f -g) | f ∈ FCI K and g ∈ MG f and g = f (1) }.

2. The transitive reduction of the informative basis [11], which is a basis for all approximate association rules, is defined as follows (2) : Definition 2. Let FMG K be the set of frequent minimal generators extracted from the extraction context K. The transitive reduction RI is given by: RI = {R | R: g ⇒ (f -g) | f ∈ FCI K and g ∈ FMG K and g ≺ f (3) and Conf(R) ≥ minconf }.

In the remainder of the paper, we will refer to the generic association rules formed by the couple (GB, RI). This couple is informative, sound and lossless [11,12] and the association rules forming it are referred as informative association rules. Thus, given an Iceberg Galois lattice -in which each frequent closed itemset is decorated by its list of minimal generators -the derivation of these association rules can be performed straightforwardly. Indeed, approximate generic association rules represent "inter-node" implications, assorted with the confidence measure, between two adjacent comparable equivalence classes, i.e., from a frequent closed itemset to another frequent closed itemset immediately covering it. For example, referring to the Iceberg Galois lattice depicted by ⇒ ADEF is generated from both equivalence classes topped respectively by the frequent closed itemsets "CE" and "ACDEF". Inversely, exact generic association rules are "intra-node" implications, with a confidence equal to 1, extracted from each node in the partially ordered structure. For example, from the closed itemset "ACDEFG", three exact generic association rules are obtained: AG⇒CDEF, DG⇒ACEF and FG⇒ACDE.

A B C D E F G 1 × × × × × × 2 × × × × × × 3 × × × 4 × × × × 5 × × × × × × ({∅};

Prince algorithm

In order to palliate the frequent closed itemset based algorithm insufficiencies, i.e., the cost of the closure computation as well as neglecting the partial order construction, we will introduce a new algorithm called Prince. Prince highly reduces the cost of closure computation and generates the partially ordered structure, which makes it able to extract straightforwardly generic association rule bases without coupling it with another algorithm. Prince takes as input an extraction context K where the items are sorted by lexicographic order, the minimum threshold of support minsup and the minimum threshold of confidence minconf. It outputs the list of frequent closed itemsets and their associated minimal generators as well as the informative association rules formed by the couple (GB, RI). Thus, Prince operates in three successive steps: (i) Minimal generator determination (ii) Partial order construction (iii) Generic association rule basis extraction.

Minimal generator determination

Following the "Test-and-generate" technique, Prince traverses the search space by level to determine the set of frequent minimal generators FMG K sorted by decreasing support values. FMG K is then considered as divided into several subsets. Each subset represents a given support. Thus, each time that a frequent minimal generator is determined, it is added to the subset representing its support. Prince also keeps track of the negative border of minimal generators GBd − (4) [13]. In the second step, the set of frequent minimal generators will serve as a backbone to construct the minimal generator lattice. As shown by the following property, the union of FMG K and GBd − will be used, in the second step, as a concise lossless representation of frequent itemsets:

Property 1. [13] Let X be an itemset. If ∃ Z ∈ GBd − and Z ⊆ X then X is infrequent. Otherwise, X is frequent and Supp(X) = min {Supp(g) | g ∈ FMG K and g ⊆ X}.

Prince uses, in this step, the same pruning strategies introduced in Titanic namely minsup, the ideal order of the frequent minimal generator set and the estimated support. A trie is used to store the minimal generator set in order to speed-up the extraction of information that will be later of use. The path from the root to each node represents a minimal generator.

Partial order construction

In this step, the frequent minimal generator set FMG K will form a minimal generator lattice, and this without any access to the extraction context. The main idea is how to construct the partial order without computing itemset closures, i.e., how guessing the subsumption relation by only comparing minimal generators? To achieve this goal, the list of immediate successors (5) of each equivalence class will be updated in an iterative way. The processing of the frequent minimal generator set is done according to the order imposed in the first step (i.e., by decreasing support values). Each frequent minimal generator g of size k (k ≥ 1) is introduced into the minimal generator lattice by comparing it to the immediate successors of its (k-1)-subsets (6) . This is based on the isotony property of the closure operator [14]. Indeed, let g 1 , a (k-1)-itemset, be one of the subsets of g, g 1 ⊂ g ⇒ g 1 ⊂ g . Thus, the equivalence class to which belongs g is a successor (not necessarily an immediate one) of the equivalence class to which belongs g 1 . While comparing g to the immediate successor list of g 1 , noted L, two cases are to be distinguished. If L is empty then g is added to L. Otherwise, g is compared to the elements already belonging to L (cf. Proposition 1). The imposed order in the first step allows to distinguish only two cases sketched by Proposition 1 by replacing the frequent minimal generators X and Y by respectively g and one of the elements of L.

Proposition 1. [15] Let X, Y ∈ FMG K , C X and C Y their respective equiva- lence classes: a. If Supp(X) = Supp(Y ) = Supp(X ∪ Y ) then X and Y belong to the same equivalence class. b. If Supp(X) < Supp(Y ) and Supp(X) = Supp(X ∪ Y ) then C X (resp. C Y ) is a successor (resp. predecessor) of C Y (resp. C X ). The computation of the support of (X ∪ Y ) is performed in a direct manner if (X ∪ Y ) belongs to FMG K ∪ GBd − . C X and C Y are then incomparable.

Otherwise, Property 1 is applied. The support computation stops then as soon as we find a minimal generator that is included in (X ∪ Y ) and has a support strictly lower than that of X and that of Y . C X and C Y are then incomparable.

During these comparisons and to avoid redundant closure computations, Prince introduces two complementary functions. These functions make it possible to maintain the concept of equivalence class throughout processing. To this end, each equivalence class C will be characterized by a representative itemset, which is the first frequent minimal generator introduced into the minimal generator lattice. Both functions are described below:

1. Manage-Equiv-Class: This function is used if a frequent minimal generator, say g, is compared to the representative itemset of its equivalence class, say R. The Manage-Equiv-Class function replaces all occurrences of g by R in the immediate successor lists in which g was added. Then, comparisons to carry out with g will be made with R. Thus, for each equivalence class, only its representative itemset appears in the lists of immediate successors.

2.

Representative: This function makes it possible to find, for each frequent minimal generator g, the representative R of its equivalence class in order to complete the immediate successor list of C g . This allows to manage only one immediate successor list for all frequent minimal generators belonging to the same equivalence class.

The pseudo-code of the second step is given by the Gen-Order procedure (Algorithm 1). Each entry, say g, in FMG K is composed by the following fields: (i) support: the support of g (ii) direct-subsets: the list of (k-1)-subsets of g (iii) immediate-succs: the list of immediate successors of g. At the end of the execution of the Gen-Order procedure, g.immediate-succs is empty if g is not the representative itemset of its equivalence class or if g belongs to a maximal equivalence class, i.e., not subsumed by any equivalence class. Otherwise, this list will contain only representative frequent minimal generators.

Algorithm 1 Gen-Order

Require: -FMG K . Ensure: -The elements of FMG K partially ordered in the form of a minimal generator lattice. 1: for all (g ∈ FMG K ) do 2:

for all (g 1 ∈ g.direct-subsets) do 3: R = Representative(g 1 ); 4:

for all (g 2 ∈ R.immediate-succs) do 5:

if (g.support = g 2 .support = Supp(g ∪ g 2 )) then 6:

Manage-Equiv-Class(g,g

Generic association rule basis extraction

In this step, Prince extracts the valid informative association rules. For this purpose and using Proposition 2, Prince finds the frequent closed itemset corresponding to each equivalence class. Proposition 2. [15] Let f and f 1 be two closed itemsets such that f covers f 1 in the Galois lattice L CK . Let MG f be the set of minimal generators of f . The closed itemset f can be composed as follows:

f = ∪{g|g ∈ MG f } ∪ f 1 .

The traversal of the minimal generator lattice is carried out in an ascending manner from the equivalence class whose frequent minimal generator is the empty set (7) (denoted C ∅ ) to the non subsumed equivalence class(es). If the closure of the empty set is not null, the exact generic association rule between the empty set and its closure is then extracted. Having the partial ordered structure built, Prince extracts the valid approximate generic association rules between the empty set and the frequent closed itemsets of the upper cover of C ∅ . These closures are found, by applying Proposition 2, using the minimal generators of each equivalence class and the closure of the empty set. Equivalence classes forming the upper cover of C ∅ are stored which makes it possible to apply the same process to them. By the same manner, Prince treats higher levels of the minimal generator lattice until reaching the maximal equivalence class(es).

The pseudo-code of this step is given by the procedure Gen-GRB (Algorithm 2). We use the same notations of the procedure Gen-Order to which we add the field FCI to each element of FMG K . Thus, for each frequent minimal generator g, this field allows to store the frequent closed itemset corresponding to C g if g is its representative. In the Gen-GRB procedure, L 1 indicates the list of equivalence classes from which are extracted the valid informative association rules. By L 2 , we note the list of equivalence classes which cover those forming L 1 (8) .

Example 1. Let us consider the extraction context K given by Figure 1 (Left) for minsup=2 and minconf =0.5. The first step allows the determination of the empty set closure, the sorted set FMG K and the negative border of minimal generators GBd − . Thus, ∅ =E, FMG K = {(∅,5), (C,4), (D,4), (A,3), (B,3), (F,3), (G,3), (CD,3), (AG,2), (BC,2), (BD,2), (DG,2), (FG,2)} and GBd − ={(AB,1), (BF,1), (BG,1), (BCD,1)}. During the second step, Prince processes the element of FMG K by comparing each frequent minimal generator g, of size k (k ≥ 1), with the immediate successor lists of its (k-1)-subsets. end for 20:

L 1 = L 2 ; 21: L 2 = ∅; 22: end while list. By comparing A to C, A.support < C.support and A.support = Supp(AC) and C A is then a successor of C C . A is added to C.immediate-succs without any comparison since this list is still empty. A is also added to D.immediate-succs since A.support < D.support and A.support = Supp(AD). At this moment of processing, we have ∅.immediate-succs = {C,D} and B is added to this list since C B is incomparable with C C (BC is a minimal generator) and C D (BD is also a minimal generator). F is then introduced into the minimal generator lattice by comparing it with the immediate successor list of its unique 0subset, i.e., the empty set. By comparing F to C, F.support < C.support and F.support = Supp(CF) and then C F is a successor of C C . F is then compared to C.immediate-succs which contains A. F.support = A.support = Supp(AF) and thus F ∈ C A whose A is the representative one. The Manage-Equiv-Class function is then applied by replacing occurrences of F, in the immediate successor lists, by A (in this case, there is no occurrence) and by continuing comparisons with A instead of F (in this case, there are no more comparisons to do with F). G is then compared to ∅.immediate-succs equal to {C,B,D}. C G is a successor of C C since G.support < C.support and G.support = Supp(CG). After comparing G with C.immediate-succs which only contains A, G is added to C.immediate-succs since C G is incomparable with C A (AG is a minimal generator). By comparing G to D (resp. B), C G is incomparable with C D (resp. C B ) since DG (resp. BG) is a minimal generator. Then, CD is compared to the immediate successor lists of its 1-subsets, i.e., C and D. C C has C A and C G as immediate successors. By comparing CD and A, CD is affected to C A since CD.support = A.support = Supp(ACD). The Manage-Equiv-Class function is then applied. In particular, comparisons to carry out with CD will be made with A. A is then compared to the immediate successor list of the second 1-subset of CD, i.e., D. However, D.immediate-succs contains only A and the comparison process stops. It is the same for the remainder of FMG K . Having the minimal generator lattice built (cf. Figure 1 (Center)), an ascending sweeping is carried out from C ∅ . As ∅ =E, the exact generic association rule ∅ ⇒ E is then extracted. ∅.immediate-succs={C,D,B}. The frequent closed itemset associated to C C is then found and is equal to CE. The approximate generic association rule ∅ ⇒ CE, of a support equal to 4 and a confidence equal to 0.8, will be extracted. It is the same for C D and C B . Using the same process and from C C , C D and C B , the traversal of the minimal generator lattice is performed in an ascending way until extracting all valid informative association rules. The resulting generic association rule bases are sketched by Figure 2.

Exact generic association rulesR 1 : ∅ ⇒ E R 8 : G ⇒ CE R 2 : C ⇒ E R 9 : BC ⇒ E R 3 : D ⇒ E R 10 : BD ⇒ E R 4 : B ⇒ E R 11 : AG ⇒ CDEF R 5 : A ⇒ CDEF R 12 : DG ⇒ ACEF R 6 : F ⇒ ACDE R 13 : FG ⇒ ACDE R 7 : CD ⇒ AEF

Correctness and Computational cost

In this section, we prove the correctness of Prince algorithm and we evaluate its computational cost in the worst case.

Theorem 1. (correctness)

The Prince algorithm extracts all frequent minimal generators and derives all frequent closed itemsets and all valid informative association rules.

Proof. During the first step, a minimal generator candidate c is pruned only if its estimate support is equal to its actual support or if it does not verify the ideal order of minimal generators. Otherwise, c is a minimal generator and by comparing its actual support to minsup, Prince algorithm adds it to the frequent minimal generator set FMG K or to the negative border of minimal generators GBd − . Thus, at the end of the first step of Prince, all frequent minimal generators are extracted in addition to the negative border of minimal generators.

During the second step, Prince takes care to introduce all frequent minimal generators into the minimal generator lattice. Indeed, a frequent minimal generator g is compared to the immediate successor list of all its (k-1)-subsets. The Representative function allows to find the representative itemset of the equivalence class of a (k-1)-subset of g. Once the representative found, the used Proposition 1 treats both possible cases. The Manage-Equiv-Class function is used only if g is compared to the representative of C g . At the end of this step, the minimal generator lattice is completely built.

During the third step, all equivalence classes are taken in consideration when deriving frequent closed itemsets and valid informative association rules. Indeed, each equivalence class C, except C ∅ , has at least one immediate predecessor. Hence, the representative of C belongs at least to one immediate successor list of another equivalence class, say C 1 . When treating C 1 , the frequent closed itemset of C is derived and C is added to the equivalence class list from which valid informative association rules will be derived in the next iteration. Thus, at the end of this step, all frequent closed itemsets and all valid informative association rules are derived. Proof. The worst case is obtained when each extracted frequent itemset is a frequent closed minimal generator. Thus, the frequent itemset lattice strictly overlaps both the Iceberg Galois lattice and the minimal generator lattice. The number of frequent closed minimal generators is then equal to 2 n . We consider that each transaction contains the n distinct items.

During the first step, Prince performs two main tasks. The first task consists in candidate support computations and is of order O(m × 2 n ). The second task consists in trying to prune non-minimal generator candidates and it is done in the order of O(n 2 ×2 n ). The cost of the first step is then of order O((n 2 +m)×2 n ).

During the second step, and for each frequent minimal generator g of size k, Prince performs, in the worst case, O(k × (n − k)) comparisons ((k × (n − k)) will be over-estimated by n 2 ). Indeed, the number of its (k-1)-subset is equal to k. Each (k-1)-subset g 1 has, in the worst case, (n − k) immediate successors when comparing g with g 1 .immediate-succs. Each comparison is performed by making the union of g with an element of g 1 .immediate-succs. The union cost is O(n). The search of the support of the itemset, result of this union, costs O(n) since it is a minimal generator. The cost of the second step is then

O((n + n) × n 2 × 2 n ), i.e., O(n 3 × 2 n ).

During the third step, and for each equivalence class C, Prince performs two main tasks. The first task consists in deriving the corresponding frequent closed itemset f . This is carried out by performing the union of the set of frequent minimal generators of f , containing only one element, and a frequent closed itemset f 1 , which is an immediate predecessor of f . The first task then costs O(n). The second task consists in deriving valid informative association rules. As each frequent minimal generator is also closed, there is no exact generic association rules. However, by fixing minconf to 0, there are k approximate generic association rules, for an equivalence class whose frequent closed minimal generator is of size k. To derive each approximate generic association rule, Prince performs the difference between the frequent closed itemset f and the corresponding premise and this costs O(n). The second task then costs O(k × n) (k will be over-estimated by n). Hence, the cost of the third step is O((n

+ n 2 ) × 2 n ), i.e., O(n 2 × 2 n ).

Thus, in the worst case, the time complexity of Prince is the sum of costs of its three steps and is of order O((

n 3 + m) × 2 n ).

It is important to mention that although Prince constructs the partial order, its running time remains of the same order of magnitude as that of algorithms dedicated to the extraction of frequent closed itemsets [17].

Experimental results

In this section, we shed light on Prince performances vs those of Close, A-Close and Titanic algorithms. Prince was implemented in the C language using gcc version 3.3.1. All experiments were carried out on a PC with a 2.4 GHz Pentium IV and 512 MB of main memory (with 2 GB of Swap) and running S.u.s.e Linux 9.0.

In all our experiments, all times reported are real times, including system and user times, into benchmark datasets (dense and sparse (9) ) and "worst case" datasets. Figure 3 (Left) summarizes the characteristics of benchmark datasets. The definition of a "worst case" context is given as follows:

Definition 3. A "worst case" context is a context K = (O, A,

R) where O represents a finite set of objects (or transactions) of size (n+1), A is a finite set of attributes (or items) of size n and R is a binary (incidence) relation (i.e., R ⊆ O × A). Each object, among the first n ones, is verified by (n-1) distinct attributes. The last object is verified by all attributes. Each attribute is checked by n distinct objects.

Thus, in a "worst case" dataset, each closed itemset is equal to its (minimal) generator. Hence, from a "worst case" dataset of dimension equal to (n+1)×n, 2 n frequent closed itemsets can be extracted when minsup is fixed to 1 transaction. Figure 3 (Right) presents an example of a "worst case" dataset for n=4. Figure 4 shows execution times of Prince (10) algorithm compared to those of Close, A-Close and Titanic algorithms.

i1 i2 i3 i4 1 × × × 2 × × × 3 × × × 4 × × × 5 × × × ×

-Mushroom: In the case of Mushroom dataset, Prince performances are better than those of Close, A-Close and Titanic for all minsup values, given the important role played by equivalence class management functions. Indeed, for a value of minsup equal to 0.1%, the number of frequent minimal generators (equal to 360,166) is almost to 2.2 times the number of frequent closed itemsets (equal to 164,117). Titanic performances decrease in a significant way due to the extension attempts carried out for each frequent minimal generator. Indeed, for minsup = 0.1%, 116 items, among 119, are frequent and the maximum size of a frequent minimal generator is only equal to 10 items.

-T40I10D100K: Prince performances for this dataset are largely better than those of Close, A-Close and Titanic for all minsup values. Thus, Close and A-Close are handicapped by a large average transaction size (40 items). In the same way, Titanic performances regress considerably for the same reasons previously evoked. The comparison cost for a frequent minimal generator, in the case of Prince, being definitely more reduced than the intersection operations performed in Close and A-Close and the extension attempts elaborated in Titanic, explains the big gap between Prince performances and those of remaining algorithms.

-"Worst case" datasets: For these experiments, minsup was fixed to 1 transaction. We tested 26 datasets showing the variation of n from 1 to 26. The execution times of the four algorithms began to be distinguishable only starting from the value of n equal to 15. The Prince algorithm performances remain better than those of Close, A-Close and Titanic algorithms. Close and Titanic executions stop for n=24 for lack of memory space. It is the same for A-Close for n=25 and Prince for n=26. It is important to mention that the partial order construction requires to store much more information than needed when aiming only to extract frequent closed itemsets. Thus, the use of only one trie to store information about all minimal generators instead of several tries, as in Close, A-Close and Titanic algorithms (11) , is an attempt aiming to reduce the memory need of Prince algorithm.

Conclusion

In this paper, we proposed a new algorithm, called Prince, for an efficient extraction of frequent closed itemsets and their respective minimal generators as well as the generic association rule bases. To this end, Prince builds the partial order contrary to the existing algorithms. A main characteristic of Prince algorithm is that it relies only on minimal generators to build the underlying partial order. Carried out experiments outlined that Prince largely outperforms existing "Test-and-generate" algorithms of the literature for both benchmark and "worst case" contexts. In the near future, we plan to tackle two issues. Firstly, we plan to study the possibility of integrating the work of Calders et al. [18] in the first step of Prince. Indeed, this work can be applied to any set verifying the property of ideal order such as the set of frequent minimal generators in our case. Secondly, we propose to add constraints [19], so that the number of generic association rules will be reduced while keeping the most interesting for the user.