Yves Bastide

Rafik Taouil

Nicolas Pasquier

Gerd Stumme

Lotfi Lakhal

Mining Frequent Patterns with Counting Inference

In this paper, we propose the algorithm PASCAL which introduces a novel optimization of the well-known algorithm Apriori. This optimization is based on a new strategy called pattern counting inference that relies on the concept of key patterns. We show that the support of frequent non-key patterns can be inferred from frequent key patterns without accessing the database. Experiments comparing PAS-CAL to the three algorithms Apriori, Close and Max-Miner, show that PASCAL is among the most efficient algorithms for mining frequent patterns.

INTRODUCTION

Knowledge discovery in databases (KDD) is defined as the non-trivial extraction of valld~ implicit, potentially useful and ultimately understandable information in large databases [START_REF] Has | Data Mining: Concepts and Techniques[END_REF]. For several years, a wide range of applications in various domains have benefited from KDD techniques and many work has been conducted on this topic. The problem of mining frequent patterns arose first as a sub-problem of mining association rules [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], but it then turned out to be present in a variety of problems [START_REF] Has | Mining frequent patterns without candidate generation[END_REF]: mining sequential patterns [START_REF] Agrawal | Mining sequential patterns[END_REF], episodes [START_REF] Mannila | Discovery of frequent episodes in event sequences[END_REF], association rules [START_REF] Srikant | Fast algorithms for mining association rules in large databases[END_REF], correlations [8; 23], multi-dimensional patterns [13; 14], maximal patterns [7; 26; 15], closed patterns [24; 20; 19; 21]. Since the complexity of this problem is exponential in the size of the binary database input relation and since this relation has to be scanned several times during the process, efficient algorithms for mining frequent patterns are required.

Related work

Three approaches have been proposed for mining frequent patterns. The first is traversing iteratively the set of all *LIMOS, universit~ Blaise Pascal, complexe scientifique des C6zeanx, 24 av. des Landais, 63177 Aubi~re Cedex, France tINRIA Lorraine, 54506 Vandceuvre-l~s-Nancy Cedex, France $I3S (CNRS UPRESA 6070) -uuiversit~ de Nice, 06903 Sophia Antipolis, France §Institut fiir Angewandte Informatik und Formale Beschreibungsverfahren, Universit~it Karlsruhe (TH), D-76128 Karlsruhe, Germany ¶LIM (CNRS FRE 2246) -universit6 de la M~diterran~e, 13288 Marseille Cedex 09, France patterns in a levelwise manner. During each iteration corresponding to a level, a set of candidate patterns is created by joining the frequent patterns discovered during the previous iteration, the supports of all candidate patterns are counted and infrequent ones are discarded. The most prominent algorithm based on this approach is the Apriori algorithm [START_REF] Srikant | Fast algorithms for mining association rules in large databases[END_REF].

A variety of modifications of this algorithm arose [9; 17; 22; 25] in order to improve different effciency aspects. However, all of these algorithms have to determine the supports of all frequent patterns and of some infrequent ones in the database.

The second approach is based on the extraction of maximal 1 frequent patterns, from which all supersets are infrequent and all subsets are frequent. This approach combines a levelwise bottom-up traversal with a top-down traversai in order to quickly find the maximal frequent patterns. Then, all frequent patterns are derived from these ones and one last database scan is carried on to count their support. The most prominent algorithm using this approach is Max-Miner [START_REF] Bayardo | Efficiently mining long patterns from databases[END_REF]. Experimental results have shown that this approach is particularly effcient for extracting maximal frequent patterns, but when applied to extracting all frequent patterns performances drastically decrease because of the cost of the last scan which requires roughly an inclusion test between each frequent pattern and each object of the database. As for the first approach, algorithms based on this approach have to extract the supports of all frequent patterns from the database. The third approach, represented by the Close algorithm [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF], is based on the theoretical framework introduced in [START_REF] Pasquier | Pruning closed itemset lattices for association rules[END_REF] that uses the closure of the Galois connection [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. In this approach, the frequent closed patterns (and their support) are extracted from the database in a levelwise manner. A closed pattern is the greatest pattern common to a set of objects of the database; and each non-closed pattern has the same properties (i.e. the same set of objects containing it and thus the same support) as its closure, the smallest closed pattern containing it. Then, all frequent patterns as well as their support are derived from the frequent closed patterns and their support without accessing the database. Hence not all patterns are considered during the most expensive part of the algorithm (counting the supports of the patterns) and the search space is drastically reduced, especially for strongly correlated data. Experiments have shown that this approach is much more efficient than the two previous ones on such data.

t'Maximal' means 'maximal with respect to set inclusion'.

Contribution

We present the PASCAL 2 algorithm, introducing a novel, effective and simple optimization of the Apriori algorithm.

This optimization is based on pattern counting inference that relies on the new concept of key patterns. A key pattern is a minimal pattern of an equivalence class gathering all patterns that have the same objects s. The pattern counting inference allows to determine the supports of some frequent and infrequent patterns (the key patterns) in the database only. The supports of all other frequent patterns are derived from the frequent key patterns. This allows to reduce, at each database pass, the number of patterns considered, and, even more important, to reduce the number of passes in total. This optimization is valid since key patterns have a property that is compatible with the original Apriori (deterministic) heuristic; we show that all subsets of a key pattern are key patterns and all supersets of a non-key pattern are non-key patterns. Then, the counting inference is performed in a levelwise manner: If a candidate pattern of size k which support has to be determined is a non-key pattern, then its support is equal to the minimal support among the patterns of size k-1 that axe its subsets. In comparison to most other modifications of Apriori~ this induces a minimal impact on the understandability and simplicity of implementation of the algorithm. The important difference is to determine as much support counts as possible without accessing the database by information gathered in previous passes. As shown by the experiments, the efficiency gain is up to one order of magnitude on correlated data.

Organization of the paper

In the next section, we recall the problem of mining frequent patterns. The essential notions and definitions of key patterns and pattern counting inference are given in Section 3. The PASCAL algorithm is described in Section 4 and experimental results for comparing its efficiency to those of Apriori, Max-Miner and Close are presented in Section 5. Section 6 concludes the paper. Let f be the function which assigns to each pattern P C P the set of all objects that include this pattern:

STATEMENT OF THE PROBLEM

f(P) = {o E O ] o includes P}.
The support of a pattern P is given by: sup(P) = card(f(P))/card(O). For a given threshold minsup E [0,1], a pattern P is called frequent pattern if sup(P) > minsup.

The task of mining frequent patterns consists in determining all frequent patterns together with their supports for a given threshold minsup.

2The French mathematician Blaise Pascal (*Clermont-Ferrand 1623, t 1662 Paris) invented an early computing device. 3A similar notion of equivalence classes was also recently proposed by R. Bayardo and R. Agrawal [START_REF] Bayardo | Mining the most interesting rules[END_REF] to characterize "a-maximal" rules (i.e., association rules with maximal antecedent).

PATTERN COUNTING INFERENCE

In this section, we give the theoretical basis of the new PAS-CAL algorithm. This basis provides at the same time the proof of correctness of the algorithm. In Section 4, these theorems will be turned into pseudo-code. Like Apriori, PASCAL will traverse the powerset of P levelwise: At the k th iteration, the algorithm generates first all candidate k-patterns.

Definition 1. A k-pattern P is a subset of P such that card(P) = k. A candidate k-pattern is a k-pattern where all its proper sub-patterns are frequent.

Given the set of candidate k-patterns, one database pass is used to determine their support. Infrequent patterns are then pruned. This approach works because of the wellknown fact that a pattern cannot be frequent if it has an infrequent sub-pattern.

Key Patterns

Our approach is based on the observation that frequent pub terns can be considered as "equivalent" if they are included in exactly the same objects. We describe this fact by the following equivalence relation 0 on the frequent patterns.

Definition 2. Given two patterns P, Q c_ P, let P 0 Q if and only if f(P) = f(Q). The set of patterns which are equivalent to a pattern P is given by [P] = {Q c ~l POQ}.

In the case of patterns P and Q with POQ, both patterns obviously have the same support: LEMMA 1. Let P and Q be two patterns.

(i) P0 Q ~ sup(F) = sup(Q) (ii) PC_QAsup(P)=sup(Q) ==#. P0Q PROOF. (i) P0Q ~ f(P)= f(Q) ~ sup(P)= card(f(P) )/card(O) = card(f(Q) )/card(O) = sup(Q).
(ii) Since P c_ Q and f is monotonous decreasing, we

have f(P) ~ f(Q). sup(P) = sup(Q) is equivalent to card(f (P)) = card(f(Q))
which implies with the former

I(P) = f(Q) and

thus POQ. []

Hence if we knew the relation 0 in advance, we would need to count the support of only one pattern in each equivalence class. Of course this is not the case; but we can construct it step by step 4. Thus, we will (in general) need to determine the support of more than one pattern in each class, but not of all of them. If we already have determined the support of a pattern P in the database and encounter later a pattern Q E [P], then we need not access the database for it because we know that sup(Q) = sup(F).

The first patterns of an equivalence class that we reach using a levelwise approach are exactly the minimal s patterns in the class:

Counting Inference

In the algorithm, we apply the pruning strategy to both candidate patterns and candidate key patterns. This is justified by the following theorem: THEOREM 2. (i) lf Q is a frequent key pattern and P C Q, then P is also a frequent key pattern. (ii) If P is not a frequent key pattern and P C_ Q, then Q is not a frequent key pattern either, e PROOF. We will first prove a more general statement of this theorem with no hypothesis on the support.

(ii) Let P and Q be two patterns with P C Q and P not being a key pattern. Then there exists pr E rain[P] with pr C P. We need to show that f(Q) = f(Q\(p\pr)).

We can rewrite f(Q) as f((Q \ (P \ P')) t9 (P \ P')), or f(Q\(P\P'!)f3f(P\I~). We know that .f(P') C f(e\P'), because f(P ) ----l(P) and f is a decreasing function z, so

f(Q) D f(Q \ (P \ p')) N f(P'). This formula is equivalent to f(Q) .D f((Q \ (P \ p')) t9 P'). Since naturally P' c_ (Q \ (p \ P')), it follows that f(Q) D f(Q \ (p \ P'))
. The opposite inequality is obvious. Hence, Q is not minimal in Pin mathematical terms, (i) and (ii) state that the set of frequent key patterns is an order ideal (or down-set) of (2 v, _C). ZThat is, P1 C P2 =~ f(P2) C f(P1).

[Q] and thus by definition not a key pattern. (i) is a direct logical consequence of (ii).

When taking the support into account, it is sufficient to notice that all subsets of a frequent pattern are frequent patterns, so the proof remains valid. [] The algorithm determines, at each iteration, the key patterns among the candidate key patterns by using (ii) of the following theorem: THEOREM 3. Let P be a frequent pattern. (i) Let p e P. Then P e[P \ {p}] iff sup(P) = sup(P \ {p}).

(ii) P is a key pattern iffsup(P) ~ minpep(sup(P\ {p})).

PROOF. (i)

The 'if' part follows from Lemma 1 (ii). The 'only if' part is obvious. (ii)

From (i) we deduce that P is a key pattern itf sup(P) ~ sup(P \ ~p}), for all p E P. Since sup is a monotonous decreasing function, this is equivalent to (ii). [] As all candidate key patterns are also candidate patterns, when generating all candidate patterns for the next level we can at the same time determine the candidate key patterns among them. If we reach a candidate k-pattern which is not a candidate key pattern, then we already passed along at least one of the key patterns in its equivalence class in an earlier iteration. Hence we already know its support. Using the following theorem, we determine this support without accessing the database: THEOREM 4. If Pia a non-key pattern, then sup(P) ----~i~(sup(e \ {p})). PROOF. "<" follows from the fact that sup is a monotonous decreasing function. "~": If P is not a key pattern then exists p E P with POP\{p}. Hence sup(P) --sup(P \

{P}) ~ minqep(sup(P\ {q}). []

Thus the database pass needs to count the supports of the candidate key patterns only. Knowing this, we can summarize PASCAL as follows: It works exactly as Apriori, but counts only those supports in the database pass which cannot be derived from supports already computed. We can thus, on each level, restrict the expensive count in the database to some of the-c.andidates. Better yet, from some level on, all candidate pattern may be known to be non-key patterns. Then all remaining frequent patterns and their support can be derived without accessing the database any more. In the worst case (i. e.~ in weakly correlated data), all candidate patterns are also candidate key patterns. The algorithm behaves then exactly as Apriori, with no significant overhead.

THE PASCAL ALGORITHM

In this section, we transform the theorems from the last section into an algorithm. The pseudo-code is given in Algorithm 1. A list of notations is provided in Table 1. We assume that P is linearly ordered, e.g., • = (1,..., n}. This will be used in PASCAL-GEN. The algorithm starts with the empty set, which always has a support of 1 and which is (by definition) a key pattern (step 2) 9o ~ {~};

19)

94 ~ 9h U {c}; [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF] end; 21) end; 22) return U/c 9k-1 and 2). In step 3, frequent 1-patterns are determined. They are marked as key patterns unless their support is 1 (steps 4--0). The main loop is similar to the one in Aprieri (steps 7 to 21). First, PASCAL-GEN is called to compute the candidate patterns. The support of key ones is determined via a database pass (steps 10-14). The 'subset' function (step 11) is the same as in Apriori: it returns all the candidate patterns included in the object o. Candidate patterns are stored in a data structure allowing fast retrieval, like the hash-tree in Apriori [START_REF] Srikant | Fast algorithms for mining association rules in large databases[END_REF]. In our implementation, we used a trie with hash nodes [START_REF] Pasquier | Pruning closed itemset lattices for association rules[END_REF]. Then (steps 15-20) the ~traditional' pruning is done. At the same time, for all remaining candidate key patterns, it is determined whether they are key or net (step 17 and 18). The way that PASCAL-GEN operates is basically known from the generator function Apriori-Gen which was introduced in [START_REF] Srikant | Fast algorithms for mining association rules in large databases[END_REF]. When called at the kth iteration, it uses as input the set of frequent (k -1)-patterns 94-1. Its output is the set of candidate k-patterns. Additionally to Apriori-Gen's join Algorithm 2 PASCAL-GEN Input: 9k-l, the set of frequent (k-1)-patterns p with their support p. sup and the p.key flag.

Output: CA, the set of candidate k-patterns c each with the flag c.key, the value c.pred_sup, and the support c. sup if c is not a key pattern.

1) insert into CA select p.iteml, p.item2, ..., p.item~_l, q.itemk-i from 9~-1 p, 9u-1 q where p.iteml = q.iteml, ..., p.itemk-2 = q.itemk-2, p.item~_l < q.itemk-1; 2) forall c E CA do begin 3) c.key +-true; c.pred_sup ~--t-oo; 4) retail (k -1)-subsets s of c do begin and prune steps, PASCAL-GEN makes the new candidates inherit the fact of being or not a candidate key pattern (step 9) by using Theorem 2; and it determines at the same time the support of all non-key candidate patterns (step 12) by using Theorem 4.

Running example.

We illustrate the PASCAL algorithm on the following dataset for minsup = 2/5:

ID Items 1 A C D F 2 B C E F 3 A B C E F 4 B E F 5 A B C E F
The algorithm performs first one database pass to count the support of the 1-patterns.

EXPERIMENTAL EVALUATION

We evaluated PASCAL against the algorithms Apriori, Close, and Max-Miner. Max-Miner was extended to retrieve the frequent patterns with their support by a pass over the databases; the two phases are shown in the tables below s. PASCAL, Apriori, Close and this final step to Max-Miner all shared the same data structures and general organization. Optimizations such as special handling of pass two or items reordering were disabled. Experiments were conducted on a PC Pentium 3 600MHz with 512MiB of RAM. Characteristics of the datasets used are given in Table 2. These datasets are the C20D10K and C73D10K census datasets from the PUMS sample file e, the T25110D10K and T25120D100K 10 synthetic dataset that mimics market basket data, and the MUSHROOMS .1 dataset describing mushrooms characteristics [START_REF] Bay | The UCI KDD Archive[END_REF]. In all experiments, we attempted to choose significant minimum support threshold values. Related work have shown that the behavior of algorithms for extracting frequent patterns depends mainly on the dataset characteristics. Weakly correlated data, such as synthetic data, constitute easy cases for the extraction since few patterns are frequent. For such data, all algorithms give acceptable response times as we can observe in Section 5.1 in which experimental results obtained for the T2016D100K, T25110D10K and T25120D100K datasets are presented. On the contrary, correlated data constitute fax more diificult cases for the extraction due to the important proportion of patterns that are frequent among all patterns. Such data represent a huge part of real-life dataset% and differences between extraction times obtained widely vary depending on the algorithm used. Experimental results obtained for the C20D10K, C73D10K and MUSHROOMS datasets, that are made up of correlated data, are given in Section 5.2.

Weakly correlated data

The T2016D100K, T25110D10K and T25120D100K synthetic datasets are constructed according to the properties of market basket data that are typical weakly correlated data. In these datasets, the number of frequent patterns is small compared to the total number of patterns and, in most cases, nearly all the frequent patterns are also key patterns.

Response times for the T2016D10OK dataset are presented numerically in Table 3

Correlated data

Response times obtained from the C20D10K and C73D10K census datasets are given numerically in Tables 6 and7, and graphically in Figures 5 and6. Results for the MUSHROOMS dataset are presented in Table 8 and Figure 7. In these three datasets, constituted of correlated data, the proportion of patterns that are frequent is important but few of them are also key patterns. Hence, using pattern counting inference, PASCAL has to perform much fewer support counts than the Apriori and the Max-Miner algorithms.

CONCLUSION

We presented PASCAL, a novel optimization of the Apriori algorithm for fast discovery of frequent patterns. PASCAL is both effective and easy to implement or to integrate in existing implementations based on the Apriori approach. This optimization uses pattern counting inference, using the key patterns in equivalence classes to reduce the number of patterns counted and database passes. We conducted performance evaluations to compare the efficiency of PASCAL with those of Apriori, Max-Miner and Close. The results showed that PASCAL gives response times equivalent to those of Apriori and Max-Miner when extracting all frequent patterns and their support from weakly correlated data, and that it is the most efficient among the four algorithms when data are dense or correlated.

Frequent key patterns are also used for simplifying rule generation, as they can be seen as the left hand sides of minimal non-redundant association rules [START_REF] Bastide | Mining minimal non-redundant rules using frequent closed itemsets[END_REF].

Figure 1 :

 1 Figure 1: Example lattice of frequent patterns

3 )

 3 91 <--(frequent 1-patterns}; 4) forall p E 91 do begin 5) p.pred sup ~--1; p.key ~ (p. sup ~ 1); 6) end; 7) for (k ~-2; 9~-1 ~ 0; k -I--I-) do begin 8) C/c ~ PASCAL-GEN(9~-i); 9) if 3(C E C~ where c.key ~-true) sup >_ minsup then begin 17) if c.key and c. sup = c.pred_sup then 18) c.key ~-false;

Figure 2 :Figure 3 :

 23 Figure 2: Experimental results for T2016D100K

Figure 4 :

 4 Figure 4: Experimental results for T25110D10K

Figure 5 :

 5 Figure 5: Experimental results for C20D10K

Table I :

 I Notations used in PASCAL

	k	is the counter which indicates the current it-
		eration. In the kth iteration, all frequent k-
		patterns and all key patterns among them are
		determined.
	9~ contains after the kth iteration all frequent k-
		patterns P together with their support P. sup,
		and a boolean variable P.key indicating if P is
		a (candidate) key pattern.
	CA stores the candidate k-patterns together with
		their support (if known)~ the boolean variable
		P.keyl and a counter P.pred_sup which stores
		the minimum of the supports of all (k -1)-
		sub-patterns of P.
	Algorithm 1 PASCAL
	1) 0. sup ~ 1; 0.key ~--true;

  The candidate pattern {D} is pruned because it is infrequent. As ~F) has the same support as the empty set, .{F} is marked as a non-key pattern:At the third iteration, it turns out in PASCAL-GEN that each newly generated candidate pattern contains at least one subpattern which is not a key pattern. Hence all new candidate patterns are not candidate key pattern, and all their supports are determined directly in PASCAL-GEN. From there on, the database will not be accessed any more.

	C2	pred sup key sup	:P2 sup key
	{AB} {AC} {AE} {AF} {Be} {BE} {BF} {cE} {CF}	3/5 3/5 415 3/5 415 4/5 4/5 415 4/5	t t t f 3/5 ? ? ? t ? t ? f 4/5 t ? f 4/5	{AB} 2/5 t {AG} 3/5 f {AE} 2/5 t {AF} 3/5 f {Be} 3/5 t {BE} 4/5 f {BF} 4/5 f {cE} 315 t {CF} 4/5 f
	{EF}	4/5	f 4/5	{EF} 4/5 f
	Cs	pred_sup key sup	Ps	sup key
	{ABF} {ABe} {ABE} {ACE} {ACF} {AEF}	2/5 2/5 2/5 2/5 3/5 2/5	f 2/5 f 2/5 f 2/5 f 3/5 f 3/5 f 2/5	{ABF} 2/5 f {ABe} 2/5 f {ABE} 2/5 f {ACE} 2/5 f {ACF} 3/5 f {AEF} 2/5 f
	{BEE} {BCF} {BEE} {CEF}		3/5 3/5 4/5 3/5	f 3/5 f 3/5 f 4/5 f 3/5	{BCE} 3/5 f {BCF} 3/5 f {BEF} 4/5 f {CEF} 3/5 f
	In the fourth and fifth iteration, all supports are determined
	directly in PASCAL-GEN. In the sixth iteration, PASCAL-
	GEN generates no new candidate patterns, thus no frequent
	6-patterns are computed and the algorithm stops:
	C4	pred_sup key sup	P4	sup key
	{ABCE} 2/5	f 2/5	{ABCE} 2/5 f
	{ABCF}	2/5	f 2/5	{ABCF} 2/5 f
	{ABEF}	2/5	f 2/5	{ABEF} 2/5 f
	{ACEF}	2/5	f 3/5	{ACEF} 2/5 f
	{BEEF}		3/5	f 3/5	{BEEF} 3/5 f
	C5		pred_snp key sup	'P5	sup key
	{ABCEF}	2/5	f 2/5	{ABCEF} 2/5 f
	Hence PASCAL needs two database passes in which the al-gorithm counts the supports of 6 + 6 = 12 patterns. Apri-ori would have needed five database passes for counting the supports of 6 + 10 + 10 + 5 + 1 = 32 patterns for the same dataset. All other current algorithms (with the only excep-tion of Close) may need less than five passes, but they all	~Pl sup key {A} 3/5 t {S} 4/5 t {c} 4/5 t {E} 4/5 t ~F) 1 f
	have to perform the 32 counts.

At the next iteration, all candidate 2-patterns are created and stored in C2. At the same time, the support of all patterns containing ~F} as a sub-pattern is computed. Then a database pass is performed to determine the supports of the remaining six candidate patterns: SIGKDD Explorations.

ACM SIGKDD~ December 2000. Volume 2, Issue 2 -page 69

Table 2 :

 2 Datasets

	Name	# of objects Avg. size # of items
	T2016D100K	100,000	20	1,000
	T25110DIOK	10,000	25	1,000
	T25120D100K	100,000	25	10,000
	C20D10K	10,000	20	386
	C?3D10K	10,000	73	2,178
	MUSH~.OOMS	8,416	23	128

Table 3 :

 3 Response times for T2016Di00K

	200	'		' Pascai o Apriori ---~--
					Close -"'9--.
				Max_Miner + ._ ~<.)z"
	150
					/
	100
	50
	a	I	,	I	,
		0.75		0.5	0.25
		Minimum Support (%)

Table 5 :

 5 Response times for T25110DIOK

	1.00	3,300	3.24	3.62	6.67 0.63	1.05
	0.75	17,583	5.17	6.95	9.38 1.09	3.83
	0.50	331,280	17.82 41.06 26.43 2.76 35.53
	0.25	2,270,573	70.37	187.92	86.08	6.99	154.89

Table 4 :

 4 Response times for T25120DI00KResults for the T25120DI00K dataset are presented numerically in Table4and graphically in Figure3. For this dataset, nearly all frequent patterns are key patterns, and results are similar to those obtained for the T2016D100K dataset: PAS-CAL and Apriori give identical response times and suffer a slight performance loss over Max-Miner while Close is the worst performer.

	In Table 5 and Figure 4, execution times for the T25110D10K
	dataset are presented. In this dataset, the proportion of fre-
	quent patterns that are not key patterns is much more im-
	portant than for the T25120D100K dataset. For the 1.00
	and 0.75 minsup thresholds, Max-Miner performs better
	than Apriori and PASCAL that themselves perform better
	than Close. For the lower 0.50 and 0.25 minsup thresholds,
	PASCAL becomes the best performer and is slightly better

than Close whereas they both clearly outperform Apriori and Max-Miner: When the proportion of frequent patterns that are not key is significant~ the mechanism used by PAS-CAL (resp. Close) to consider only key (resp. closed) patterns enables to reduce considerably the number of support counts performed.

Table 6 :

 6 The same observation stands for the Close algorithm, that uses the closure mechanism to reduce the number of support counts, and both PASCAL and Close are an order of magnitude faster than Apriori and Max-Miner. Differences between the execution times of PASCAL and Close and those of Apriori and Max-Miner can be counted in tens of minutes for C20D10K and MUSHROOMS and in hours for C73D10K. Moreover, pattern counting inference and closure mechanism allow to reduce the number of passes on the datasets since the supports of all candidate patterns of some iteration are all deduced from the supports of key, or closed, patterns of previous iterations. On C73D10K with minsup = 60%, for instance, PASCAL and Close both make 13 passes while the largest frequent patterns are of size 19. For this dataset and this threshold value, frequent patterns could not be derived from the maximal frequent patterns extracted with Max-Miner since we did not implement memory management for this phase and it required in this case more memory space than available. Response times for C20D10K

	Sup.	# freq. Pascal Apriori Close Max-Miner +
	20.0	20,239	9.44	57.15 14.36 0.17	77.40
	15.0	36,359 12.31	85.35 18.99 0.26 113.22
	10.0	89,883 19.29 164.81 29.58 0.34 201.33
	7.5	153,163 23.53 232.40 36.02 0.35 268.80
	5.0	352,611 33.06 395.32 50.46 0.48 428.65
	2.5 1,160,363 55.33 754.64 78.63 0.81 775.56
	Sup. ~ freq.	Pascal	Apriori	Close	Max-Miner +
	80 109,159 177.49 3,661.27 241.91 0.87 3,717.99
	75 235,271 392.80 7,653.58 549.27 1.06 7,730.36
	70 572,087 786.49 17,465.10 1,112.42 2.28 17,618.40
	60 4,355,543 3,972.10 109,204.00 5,604.91 7.72	(*)
	(*) Not enough memory.

Table 7 :

 7 Response times for C73D10K

	Sup.	# freq. Pascal	Apriori Close	Max-Miner +
	20.0	53,337	6.48	115.82 9.63 0.31	134.31
	15.0	99,079	9.81	190.94 14.57 0.50	218.93
	10.0	600,817 23.12 724.35 29.83 0.89	745.72
	7.5	936,247 32.08 1,023.24 41.05 1.25 1,035.48
	5.0 4,140,453 97.12 2,763.42 98.81 1.99 2,752.05

Table 8 :

 8 Response times for MUSHROOMS

ACKNOWLEDGEMENTS

We would like to thank Robexto Bayardo, who provided us with the implementation of Max-Miner used in the tests and commented on an earlier version of this work.

Minimum Support (%)


Nicolas Pasquier
email: pasquier@libd2.univ-bpclermont.fr

Extraction de Bases pour les Règles d'Association à partir des Itemsets Fermés Fréquents

Keywords: Extraction de connaissances Knowledge discovery in databases, data mining, closure operator of the Galois connection, frequent closed itemsets, minimal non-redundant association rules, bases for association rules, algorithms

Le problème de l'utilité et de la pertinence des règles d'association extraites est primordial car, dans la plupart des cas, les jeux de données réels conduisent à plusieurs milliers voire plusieurs millions de règles d'association dont la mesure de confiance est élevée, et parmi lesquelles se trouvent de nombreuses règles redondantes. Utilisant la sémantique basée sur la fermeture de la connexion de Galois, des bases pour les règles d'association, qui sont des ensembles générateurs pour toutes les règles d'association ainsi que leurs supports et leurs confiances, sont définies. Ces bases sont constituées des règles d'association non redondantes d'antécédents minimaux et de conséquences maximales et sont définies à partir des itemsets fermés fréquents et leurs générateurs extraits par les algorithmes Close et A-Close. Des algorithmes efficaces de génération des bases à partir de ces derniers sont présentés et les résultats des expérimentations menées sur des bases de données réelles montrent l'efficacité des algorithmes et l'utilité des bases proposées.

Introduction

L'extraction dcie règles d'association a pour but de découvrir des relations significatives entre attributs binaires extraits des bases de données. Un exemple de règle d'association extraite d'une base de données de ventes de supermarché est : « céréales ∧ sucre → lait (support 7%, confiance 50%) ». Cette règle indique que les clients qui achètent des céréales et du sucre ont également tendance à acheter du lait. La mesure de support définit la portée de la règle, c'est à dire la proportion de clients qui ont acheté les trois articles, et la mesure de confiance définit la précision de la règle, c'est à dire la proportion de clients qui ont acheté du lait parmi ceux qui ont acheté des céréales et du sucre. L'extraction de règles d'association consiste à extraire les règles dont le support et la confiance sont au moins égaux à des seuils minimaux de support et de confiance définis par l'utilisateur. Les règles d'association ont été utilisées avec succès dans de nombreux domaines, parmi lesquels l'aide à la planification commerciale, l'aide au diagnostic et en recherche médicale, l'amélioration des processus de télécommunications, l'organisation et l'accès aux sites Internet, et l'analyse d'images, de données spatiales, de données géographiques et de données statistiques.

L'extraction de règles d'association est un processus itératif et interactif constitué de plusieurs phases allant de la sélection et la préparation des données jusqu'a l'interprétation des résultats, en passant par la phase de recherche des connaissances : le data mining [START_REF]Advances in Knowledge Discovery and Data Mining[END_REF]. La plupart des approches proposées pour l'extraction des itemsets fréquents reposent sur les quatre phases suivantes :

Préparation des données Cette phase consiste à sélectionner les données (attributs et objets) de

Extraction des ensembles fréquents d'attributs

Cette phase consiste à extraire du contexte tous les ensembles d'attributs binaires l ⊆ A A, appelés itemsets, qui sont fréquents dans le contexte B B. Un itemset l est fréquent si son support, qui correspond au nombre d'objets du contexte qui « contiennent » l, est supérieur ou égal au seuil minimal de support minsupport défini par l'utilisateur. L'ensemble des itemsets fréquents dans le contexte est noté F. Le problème de l'extraction des itemsets fréquents est de complexité exponentielle dans la taille m de l'ensemble d'items puisque le nombre d'itemsets fréquents potentiels est 2 m . Ces itemsets forment un treillis dont la représentation sous forme de diagramme de Hasse pour le contexte D D est présentée dans la Figure 1. De plus, des balayages du contexte doivent être réalisés lors de cette phase, et il est donc nécessaire de développer des méthodes efficaces d'exploration de cet espace de recherche exponentiel.

Génération des règles d'association

Durant cette phase, les itemsets fréquents extraits durant la phase précédente sont utilisés afin de générer les règles d'association qui sont des implications entre deux itemsets fréquents l 1 , l 2 ∈ F tels que l 1 ⊂ l 2 , de la forme r : l 1 → (l 2 \ l 1 ). Afin de limiter l'extraction aux règles d'association les plus informatives, seules celles qui possèdent une confiance supérieure ou égale au seuil minimal minconfiance défini par l'utilisateur sont générées. La confiance d'une règle r : l 1 → (l 2 \ l 1 ) est définie comme la proportion d'objets contenant la conséquence (l 2 \ l 1 ) de r parmi ceux qui contiennent l'antécédent l 1 de r. Cette valeur est égale au rapport entre le support de l'itemset l 2 et le support de l'itemset l 1 .

Interprétation des résultats Cette phase consiste en la visualisation par l'utilisateur des règles d'association extraites du contexte et leur interprétation afin d'en déduire des connaissances utiles pour l'amélioration de l'activité concernée. Le nombre important de règles d'association extraites en général impose le développement d'outils de classification des règles, de sélection par l'utilisateur de sous-ensembles de règles, et de leur visualisation sous une forme intelligible. De

Algorithmes d'extraction des itemsets fréquents

Algorithmes d'extraction des itemsets fréquents maximaux

Ces algorithmes sont basés sur la propriété que les itemsets fréquents maximaux, c'est à dire les itemsets dont tous les sur-ensembles sont infréquents, forment une bordure au dessous de laquelle tous les itemsets sont fréquents. L'extraction des itemsets fréquents maximaux est réalisée par une exploration itérative du treillis des itemsets fréquents, en « avancant » de un niveaux du bas vers le haut et de un ou plusieurs niveaux du haut vers le bas lors de chaque itération. À partir des itemsets fréquents maximaux, tous les itemsets fréquents sont dérivés et leurs supports sont déterminés en réalisant un balayage du contexte. Quatre algorithmes basés sur cette approche ont été proposés, ce sont les algorithmes Pincer-Search [START_REF] Lin | Pincer-Search : A new algorithm for discovering the maximum frequent set[END_REF]

Algorithmes d'extraction des itemsets fermés fréquents

Les itemsets fermés fréquents [START_REF] Pasquier | Data mining : algorithmes d'extraction et de réduction des règles d'association dans les bases de données[END_REF][START_REF] Pasquier | Pruning closed itemset lattices for association rules[END_REF] L'algorithme commence par initialiser l'ensemble FFC 1 des 1-générateurs avec la liste des 1itemsets du contexte et exécute ensuite un ensemble d'itérations. Durant chaque itération k :

• La fermeture de tous les k-générateurs ainsi que leur support sont calculés. La détermination des fermetures des générateurs est basée sur la propriété que la fermeture d'un itemset l est égale à l'intersection de tous les objets du contexte contenant l dont le décompte fournit le support du générateur qui est identique au support de sa fermeture. Un seul balayage du contexte est donc nécessaire pour déterminer les fermetures et les supports de tous les kgénérateurs.

• Tous les k-générateurs fréquents, dont le support est supérieur ou égal au seuil minimal de support minsupport, ainsi que leur fermeture et leur support sont insérés dans l'ensemble FF k des itemsets fermés fréquents identifiés durant l'itération k.

• L'ensemble des (k+1)-générateurs candidats (utilisés durant l'itération suivante) est construit, en joignant les k-générateurs fréquents de l'ensemble FF k comme suit (procédure Gen-Generator) : L'ensemble FFC 1 est initialisé avec la liste des 1-itemsets du contexte D D. La procédure Gen-Closure génère les fermetures des 1-générateurs, qui sont les itemsets fermés fréquents potentiels, et leurs supports dans FFC 1 . Les groupes candidats de FFC 1 qui sont fréquents sont insérés dans l'ensemble FF 1 . La première phase de la procédure Gen-Generator appliquée à l'ensemble FF 1 génère six nouveaux 2-générateurs candidats : {AB}, {AC}, {AE}, {BC}, {BE} et {CE} dans FFC 2 . Les 2-générateurs {AC} et {BE} sont supprimés de FFC 2 par la troisième phase de la procédure Gen-Generator car nous avons {AC} ⊆ γ({A}) et {BE} ⊆ γ({B}). La procédure Gen-Closure calcule ensuite les fermetures et les supports des 2-générateurs restant dans FFC 2 et les ensembles FF 2 et FFC 2 sont identiques car tous les itemsets fermés de FFC 2 sont fréquents. L'application de la procédure Gen-Generator à l'ensemble FF 2 génère le 3générateur {ABE} qui est supprimé car le 2-générateur {BE} n'appartient pas à FF 2 et l'algorithme s'arrête.

Problème de la pertinence et de l'utilité des règles d'association extraites

Le problème de la pertinence et de l'utilité est lié au nombre de règles d'association extraites qui est en général très important et à la présence d'une forte proportion de règles redondantes, c'est à dire de règles convoyant la même information, parmi celles-ci. Si le problème de la visualisation d'un nombre relativement important de règles peut être simplifié par l'utilisation de systèmes de visualisation tels que le système Rule Visualizer proposé par Klemettinen et al. [START_REF] Klemettinen | Finding interesting rules from large sets of discovered association rules[END_REF], le problème de la suppression des règles d'association redondantes nécessite d'autres solutions. De plus, les règles d'association redondantes représentant pour certains type de données la majorité des règles extraites, leur suppression permet de réduire considérablement le nombre de règles à gérer lors de la visualisation.

Exemple 1 Afin d'illustrer le problème des règles d'association redondantes, neuf règles d'association extraites du jeu de données Mushrooms décrivant les caractéristiques de 8 416 champignons sont présentées ci-dessous. Ces neuf règles possèdent un support et une confiance identiques de 51% et 54% respectivement :

1) lamelles libres → comestible 2) lamelles libres → comestible, voile partiel 3) lamelles libres → comestible, voile blanc 4) lamelles libres → comestible, voile partiel, voile blanc 5) lamelles libres, voile partiel → comestible 6) lamelles libres, voile partiel → comestible, voile blanc 7) lamelles libres, voile blanc → comestible 8) lamelles libres, voile blanc → comestible, voile partiel 9) lamelles libres, voile partiel, voile blanc → comestible Il est évident que les règles 1 à 3 et 5 à 9 sont redondantes par rapport à la règle 4 puisque, du point de vue de l'utilisateur, ces 8 règles n'apportent aucune information supplémentaire par rapport à la règle 4 qui est la plus générale. Afin d'améliorer la pertinence et l'utilité des règles extraites, il est souhaitable que seule cette dernière règle soit extraite et présentée à l'utilisateur.

Dans la suite, deux types de règles d'association sont distingués :

• Les règles d'association exactes dont la confiance est égale à 1 (100\%) qui sont vérifiées dans tous les objets du contexte.

• Les règles d'association approximatives dont la confiance est inférieure à 1 qui sont vérifiées dans une proportion d'objets du contexte égale à leur confiance.

La solution proposée dans cet article consiste à générer des bases, également appelées couvertures réduites, pour les règles d'association qui sont des ensembles de taille réduite ne contenant aucune règle redondante. Le but est de limiter l'extraction aux règles d'association les plus informatives, c'est-à-dire les plus générales et, éventuellement, dont les mesures de précision sont les plus élevées parmi toutes les règles valides, du point de vue de l'utilisateur.

État de l'art

Plusieurs méthodes permettant de réduire le nombre de règles d'association extraites, ou bien de sélectionner un sous-ensembles de règles, ont été proposées. Nous présentons un état de l'art non exhaustif de ces méthodes dans la suite.

Règles d'association généralisées

Les règles d'association généralisées sont définies en utilisant une taxonomie des items du contexte : ce sont des règles d'association entre ensembles d'items pouvant appartenir à différents niveaux de la taxonomie. Par exemple, la règle généralisée « r 1 : lait → sucre » est appelée sur-règle des deux règles « r 2 : lait entier → sucre » et « r 3 : lait écrémé → sucre » car les items « lait entier » et « lait écrémé » sont des descendants de l'item « lait ». Dans [START_REF] Han | Discovery of multiple-level association rules from large databases[END_REF][START_REF] Srikant | Mining generalized association rules[END_REF], les auteurs proposent de générer seulement la sur-règle r 1 si son support est supérieur à la somme des supports de r 2 et r 3 et sa confiance est supérieure aux confiances de r 2 et r 3 . Cette méthode nécessite la création d'une taxonomie des items et ne permet pas de supprimer les règles d'association redondantes. De plus, elle ne permet pas de réduire significativement le nombre de règles extraites dans le cas de données denses ou corrélées.

Utilisation d'autres mesures statistiques L'utilisation d'autres mesures statistiques que la confiance pour déterminer la précision des règles d'association a fait l'objet de nombreuses études [BMS97, PS91, SBM98]. Parmi ces mesures, nous retenons les deux mesures suivantes qui fournissent les résultats les plus intéressants. La mesure de conviction permet de mesurer pour chaque règle la déviation de la dépendance entre la probabilité d'occurrence de l'antécédent et la probabilité de non occurrence de la conséquence dans les objets. La mesure du χ 2 spécifie le degré de dépendance entre les items d'un itemset en comparant la distribution réelle de leur occurrence avec la distribution attendue de leur occurrence sous l'assomption d'une complète indépendance et d'une distribution normale. L'utilisation de ces mesures entraîne des problèmes de performances car le calcul de leurs valeurs nécessite des temps d'exécution importants. Templates Les templates [START_REF] Klemettinen | Finding interesting rules from large sets of discovered association rules[END_REF] sont des expressions booléennes permettant de sélectionner un sous-ensemble de l'ensemble des règles d'assocation valides. Ce sous-ensemble est construit en conservant les règles d'association valides qui vérifient les critères spécifiés par les templates parmi cet ensemble. Un template spécifie des contraintes d'occurrence ou de non occurrence des items dans l'antécédent et la conséquence des règles. Cette méthode de traitement a posteriori des règles extraites ne permet pas de supprimer les règles redondantes, mais peut faciliter la visualisation de l'ensemble des règles extraites en visualisant les règles par groupes, chaque groupe correspondant à un ensemble de templates.

Mesures de déviation

Contraintes sur les items

Les contraintes sur les items [BAG99, NLHP98, SVA97] sont des expressions portant sur l'antécédent et la conséquence des règles, définies par l'utilisateur, qui spécifient la forme des règles d'association à extraire. Ces contraintes sont utilisées lors de la phase d'extraction des itemsets fréquents afin de limiter l'espace de recherche de cette phase aux itemsets permettant de générer les règles vérifiant les contraintes. Elles sont prises en compte lors de la génération des itemsets candidats afin de considérer seulement les candidats permettant de générer des règles satisfaisant les contraintes. Toutefois, cette approche ne permet pas d'éliminer les règles redondantes et ne fournit qu'un résultat partiel, tous les items du contexte n'étant pas considérés.

Bases pour les règles d'implication La définition de bases pour les règles d'implication entre deux ensembles d'attributs binaires a été étudiée essentiellement dans les domaines de l'analyse de données et de l'analyse formelle de concepts. L'adaptation de la base de Duquenne-Guigues [DG86, GW99] pour les implications (globales), et la base de Luxenburger [START_REF] Luxenburger | Implications partielles dans un contexte[END_REF] pour les implications partielles2 dans le cadre de l'extraction de règles d'association exactes et approximatives est présentée dans [START_REF] Pasquier | Data mining : algorithmes d'extraction et de réduction des règles d'association dans les bases de données[END_REF][START_REF] Pasquier | Closed set based discovery of small covers for association rules[END_REF]. Les bases obtenues sont des réductions de l'ensemble des règles d'association qui minimisent autant que faire se peut le nombre de règles générées, sans tenir compte du support des règles. Cela signifie que les antécédents et les conséquences de toutes les règles d'association peuvent être déduits de l'union de ces bases, mais pas leurs supports.

Contribution

Utilisant la sémantique pour le problème de l'extraction de règles d'association basée sur la fermeture de la connexion de Galois [START_REF] Pasquier | Data mining : algorithmes d'extraction et de réduction des règles d'association dans les bases de données[END_REF], des bases pour les règles d'association sont caractérisées. Ces bases, qui sont la base générique pour les règles d'association exactes et la base informative pour les règles d'association approximatives, sont définies à partir des itemsets fermés fréquents et leurs générateurs. Ce sont des ensembles de taille réduite qui minimisent le nombre de règles d'association générées tout en maximisant la quantité et la qualité des informations convoyées. Elles permettent :

• La génération des règles d'association non redondantes les plus informatives seulement, c'est à dire des règles les plus utiles et pertinentes : celles qui ont un antécédent (partie gauche) minimal et une conséquence (partie droite) maximale. Les règles redondantes représentent pour certains jeux de données la majorité des règles extraites, plus particulièrement dans le cas de jeux de données denses ou corrélées pour lesquels le nombre total de règles valides est très important.

• La présentation à l'utilisateur d'un ensemble de règles couvrant tous les attributs de la base de données, c'est-à-dire contenant des règles dont l'union des conséquences est égale à l'union des conséquences de toutes les règles d'association valides dans le contexte. En effet, il est nécessaire de ne pas limiter la recherche à un seul sous-ensemble des attributs de la base de données car les règles « surprenantes » pour l'utilisateur constituent des informations utiles qu'il est nécessaire de considérer [Hec96, PSM94, ST96].

• L'extraction d'un ensemble de règles ne représentant aucune perte d'information, c'est à dire véhiculant toutes les informations convoyées par l'ensemble des règles d'association valides. Il est possible de déduire de manière efficace, sans accès au jeu de données, toutes les règles d'association valides ainsi que leurs supports et leurs confiances à partir des règles d'association de ces bases.

L'union de ces deux bases constitue donc un ensemble générateur minimal non redondant pour toutes les règles d'association valides, leurs supports et leurs confiances.

Bases pour les règles d'association

Base générique pour les règles d'association exactes

Les règles d'association exactes, de la forme r : l 1 → (l 2 \ l 1 ), sont des règles entre deux itemsets fréquents l 1 et l 2 dont les fermetures sont identiques : γ(l 1 ) = γ(l 2 ) [START_REF] Pasquier | Data mining : algorithmes d'extraction et de réduction des règles d'association dans les bases de données[END_REF]. En effet, de γ(l 1 ) = γ(l 2 ) nous déduisons que l 1 ⊂ l 2 et support(l 1 ) = support(l 2 ), et donc confiance(r) = 1. Puisque l'itemset maximal parmi ces itemsets (qui possèdent le même support) est l'itemset γ(l 2 ) (évident) , tous les sur-ensembles stricts de l 1 qui sont des sous-ensembles de γ(l 2 ) possèdent le même support, et les règles entre deux de ces itemsets sont des règles exactes.

Soit l'ensemble G γ(l2) des générateurs de l'itemset fermé fréquent γ(l 2 ). Par définition, les itemsets minimaux qui sont des sur-ensembles stricts de l 1 et des sous-ensembles de γ(l 2 ) sont les générateurs g ∈ G γ(l2) . Nous en concluons que les règles de la forme g → (γ(l 2 ) \ g) entre les générateurs g ∈ G γ(l2) et l'itemset fermé fréquent γ(l2) sont les règles d'antécédents minimaux et de conséquences maximales parmi les règles entre les sur-ensembles stricts de l 1 et les sousensemble de γ(l 2 ). La généralisation de cette propriété à l'ensemble des itemsets fermés fréquents définit la base générique constituée de toutes les règles d'association exactes non redondantes, selon la Définition 1, d'antécédents minimaux et de conséquences maximales. Soit l'ensemble FF des itemsets fermés fréquents extraits du contexte et pour chaque itemset fermé fréquent f l'ensemble G f des générateurs de f. La base générique pour les règles d'association exactes est :

BG = {r : g → (f \ g) | f ∈ FF ∧ g ∈ G f ∧ g ≠ f}.
La condition g ≠ f est nécessaire car les règles entre un générateur g d'un itemset fermé fréquent f tel que g = f sont de la forme g → ∅ et n'appartiennent pas à l'ensemble des règles d'association valides (règles non informatives).

Exemple 2 La base générique pour les règles d'association exactes extraite du contexte D D pour minsupport = 2/6 est présentée dans la Table 2. Cette base ne représente aucune perte d'information : toutes les règles d'association exactes valides dans le contexte peuvent être déduites ainsi que leurs supports (et leurs confiances qui sont égales à 1) à partir des règles de la base générique [START_REF] Pasquier | Data mining : algorithmes d'extraction et de réduction des règles d'association dans les bases de données[END_REF].

Générateur

Base informative pour les règles d'association approximatives

Les règles d'association approximatives, de la forme l 1 → (l 2 \ l 1 ), sont des règles entre deux itemsets fréquents l 1 et l 2 tel que la fermeture de l 1 est un sous-ensemble de la fermeture de l 2 : γ (l 1 ) ⊂ γ(l 2 ) [START_REF] Pasquier | Data mining : algorithmes d'extraction et de réduction des règles d'association dans les bases de données[END_REF]. Les règles d'association approximatives non redondantes d'antécédent l 1 minimal et de conséquence (l 2 \ l 1 ) maximale sont déduites de cette caractérisation.

Soit l'itemset fermé fréquent f 1 qui est la fermeture de l 1 et le générateur unique g 1 de f 1 tels que

g 1 ⊆ l 1 ⊆ f 1 . Soit l'
BI = {r : g → (f \ g) | f ∈ FF ∧ g ∈ G ∧ γ(g) ⊂ f}.
La base informative ne représente aucune perte d'information car toutes les règles d'association approximatives valides dans le contexte peuvent être déduites ainsi que leurs supports et leurs confiances à partir des règles qui la constituent [START_REF] Pasquier | Data mining : algorithmes d'extraction et de réduction des règles d'association dans les bases de données[END_REF].

De la définition de la base informative il est possible de déduire la réduction transitive de celle-ci qui constitue elle-même une base pour les règles d'association approximatives. Les règles transitives de la base informative sont de la forme r : g → (f \ g) pour un itemset fermé fréquent f et un générateur fréquent g tels que γ(g) ⊂ f et γ(g) n'est pas un prédécesseur immédiat de f :

∃ f' ∈ FF tel que γ(g) ⊂ f' ⊂ f, noté γ(g)  f.

Définition 4 (Réduction transitive de la base informative [Pas00])

Soit l'ensemble FF des itemsets fermés fréquents et l'ensemble G de leurs générateurs extraits du contexte. La réduction transitive de la base informative pour les règles d'association approximatives est :

RI = {r : g → (f \ g) | f ∈ FF ∧ g ∈ G ∧ γ(g)  f}.
Il est possible de déduire toutes les règles d'association de la base informative ainsi que leurs supports et leurs confiances, et donc toutes les règles approximatives valides, à partir des règles de la réduction transitive [START_REF] Pasquier | Data mining : algorithmes d'extraction et de réduction des règles d'association dans les bases de données[END_REF]. Cette réduction permet de diminuer le nombre de règles extraites en conservant les règles dont la confiance est la plus élevée puisque les règles transitives possèdent par construction des confiances inférieures aux règles non transitives.

Exemple 3

La réduction transitive de la base informative extraite du contexte D D pour minsupport = 2/6 et minconfiance = 2/6 est présentée dans la Table 3

Algorithmes de génération des bases

Base générique pour les règles d'association exactes

Le pseudo-code de l'algorithme Gen-BG [Pas00] de construction de la base générique pour les règles d'association exactes à partir de l'ensemble des itemsets fermés fréquents et de leurs générateurs est présenté dans l'Algorithme 1. Les notations utilisées sont présentées dans la Table 4.

L'algorithme commence par initialiser l'ensemble BG avec l'ensemble vide (ligne 1). Chaque ensemble FF k de k-groupes fréquents est ensuite examiné successivement (lignes 2 à 6). Pour chaque k-générateur g ∈ FF k de l'itemset fermé fréquent γ(g) pour lequel g est différent de se fermeture γ(g) (lignes 3 à 5), la règle r : g → (γ(g) \ g), dont le support est égal au support de g et γ(g), est insérée dans BG (ligne 4). L'algorithme retourne finalement l'ensemble BG qui contient toutes les règles exactes informatives entre un générateur et sa fermeture (ligne 7).

FF k Ensemble de k-groupes fréquents des k-générateurs. Chaque élément de cet ensemble possède trois champs : générateur, fermé et support.

BG Ensemble des règles d'association exactes de la base générique.

Table 4 : Notations utilisées dans l'algorithme Gen-BG.

Entrée Ensembles FF k des k-groupes fréquents des k-générateurs; Sortie : Ensemble BG des règles d'association exactes de la base de générique; 1) BG ← ∅;

2) pour chaque ensemble FF k faire 3) pour chaque k-générateur g ∈ FF k tel que g ≠ γ(g) faire 4)

BG ← BG ∪ {(r : g → (γ(g) \ g), γ(g).support)}; 5) fin pour 6) fin pour 7) retourner BG; Algorithme 1 :Génération de la base générique avec Gen-BG.

Réduction transitive de la base informative pour les règles d'association approximatives

Le pseudo-code de l'algorithme Gen-RI [Pas00] de construction de la réduction transitive de la base informative pour les règles d'association approximatives à partir de l'ensemble des itemsets fermés fréquents et de leurs générateurs est présenté dans l'Algorithme 2. Les notations utilisées sont présentées dans la Table 5.

L'algorithme commence par initialiser l'ensemble RI avec l'ensemble vide (ligne 1). Chaque ensemble FF k de k-groupes fréquents est ensuite examiné successivement dans l'ordre des valeurs de k croissantes (lignes 2 à 14). Pour chaque k-générateur g ∈ FF k de l'itemset fermé fréquent γ(g) (lignes 3 à 18), l'ensemble Succ g des successeurs de la fermeture de γ(g) est initialisé avec l'ensemble vide (ligne 4) et les ensembles S j des j-itemsets fermés fréquents qui sont des sur-ensembles de γ(g) pour |γ(g)| < j ≤ µ sont constuits (lignes 5 à 7). Les ensembles S j sont ensuite considérés dans l'ordre croissant des valeurs de j (lignes 8 à 17). Pour chaque itemset f ∈ S j dont aucun successeur immédiat de γ(g) dans Succ g n'est un sous-ensemble (ligne 10), f est inséré dans Succ g (ligne 11) et la confiance de la règle r : g → (f \ g) est calculée (ligne 12). Si la confiance de r est supérieure ou égale au seuil minimal de confiance minconfiance, la règle r est insérée dans RI (lignes 13 à 15). Lorsque tous les générateurs de taille inférieure à µ ont été considérés, l'algorithme retourne l'ensemble RI (ligne 20).

FF k

Ensemble de k-groupes fréquents des k-générateurs. Chaque élément de cet ensemble possède trois champs : générateur, fermé et support.

Succ g Ensemble des itemsets fermés fréquents qui sont des successeurs immédiats de la fermeture du générateur g considéré.

RI

Ensemble des règles d'association approximatives de la réduction transitive de la base informative.

Figure 1 :

 1 Figure 1 : Diagramme de Hasse représentant le treillis des itemsets.

  Les algorithmes d'extraction des itemsets fréquents par niveaux considèrent un ensemble d'itemsets d'une taille donnée lors de chaque itération, c'est à dire un ensemble d'itemsets d'un « niveau » du treillis des itemsets. Ces algorithmes se basent sur les propriétés suivantes afin de limiter le nombre d'itemsets candidats considérés, en les générant à partir des itemsets fréquents de l'itération précédente : tous les sur-ensembles d'un itemset infréquents sont infréquents et tous les sous-ensembles d'un itemset fréquent sont fréquents [AS94, MTV94]. Parmi ceux-ci nous pouvons citer les algorithmes Apriori [AS94] et OCD [MTV94] qui réalisent un nombre de balayages du contexte égal à la taille des plus longs itemsets fréquents, l'algorithme Partition [SON95] qui autorise la parallélisation du processus d'extraction, et l'algorithme DIC [BMUT97] qui réduit le nombre de balayages du contexte en considérant les itemsets de plusieurs tailles différentes lors de chaque itération. Les algorithmes Partition et DIC entraînent un coût supplémentaire en temps CPU par rapport aux algorithmes Apriori et OCD dû à l'augmentation du nombre d'itemsets candidats testés.

Figure 3 :

 3 Figure 3 : Extraction des itemsets fermés fréquents dans le contexte D D avec Close pour minsupport = 2/6.

  Les mesures de déviation sont des mesures de distance entre règles d'association définies en fonction de leurs supports et leurs confiances. Ces mesures peuvent être utilisées afin d'identifier les règles d'association fortement semblables, caractérisées par une faible distance entre elles, et ensuite regrouper ou supprimer certaines de ces règles [BAG99, TKR+95]. Cette méthode entraîne une perte d'information et nécessite des traitements supplémentaires de comparaison des règles extraites deux à deux. Une autre utilisation consiste à identifier les règles d'association inattendues pour l'utilisateur qui apportent donc une connaissance importante car nouvelle [Hec96, PSM94, ST96]. Les connaissances de l'utilisateur sont représentées en utilisant des modèles probabilistes auxquels sont confrontées les règles d'association extraites. La déviation d'une règle correspond à la différence entre la valeur attendue pour la règle dans le modèle probabiliste et la valeur réelle pour la règle dans le contexte. Cette méthode nécessite la définition par l'utilisateur de ces connaissances, ce qui dans de nombreux cas se révèle très complexe, et les temps des calculs des mesures de déviation sont très importants car ils requièrent de très nombreuses opérations.

Définition 3 (

 3 Base générique pour les règles d'association exactes [Pas00])

  la base de données utiles à l'extraction des règles d'association et transformer ces données en un contexte d'extraction. Ce contexte, ou jeu de données, est un triplet B identifié par son OID, et cinq items est représenté dans la Table 1. Ce contexte est utilisée comme support pour les exemples dans la suite de l'article. Cette phase est nécessaire afin qu'il soit possible d'appliquer les algorithmes d'extraction des règles d'association sur des données de natures différentes provenant de sources différentes, de concentrer la recherche sur les données utiles pour l'application et de minimiser les temps d'extraction.

		B=(O O, A A, R R) dans lequel
	O O est un ensemble d'objets, A A est un ensemble d'attributs, également appelés items, et R R est une
	relation binaire entre O O et A A. Un contexte d'extraction de règles d'association D D constitué de six
	objets, chacun OID	items
	1	A C D
	2	B C E
	3	A B C E
	4	B E
	5	A B C E
	6	B C E
	Table 1: Contexte d'extraction de règles d'association D D.

  été proposés dans le système Rule Visualizer[START_REF] Klemettinen | Finding interesting rules from large sets of discovered association rules[END_REF], qui utilise des templates de sélection des règles et permet de les visualiser sous forme textuelle ou bien sous forme de graphes dirigés.Les connaissances de l'utilisateur concernant le domaine d'application sont nécessaires lors des phases de pré-traitement, afin d'assister la sélection et la préparation des données, et de posttraitement, pour l'interprétation et l'évaluation des règles extraites. En fonction de l'évaluation des règles extraites, les paramètres utilisés lors des précédentes phases (critères de sélection et préparation des données et seuils minimaux de support et de confiance) peuvent être modifiés avant d'effectuer à nouveau l'extraction des règles d'association, ceci afin d'améliorer la qualité du résultat.Deux problèmes majeurs pour l'utilisation de l'extraction des règles d'association ont donné lieu à de nombreuses recherches : le problème des temps d'extraction des règles d'association à partir du jeu de données et le problème de la pertinence et de l'utilité des règles d'association extraites. Ces deux problèmes et les solutions proposées dans la littérature sont présentés dans les

	tels outils ont
					{ABCDE}
		{ABCE}	{ABCD}	{ABDE}	{ACDE}	{BCDE}
	{ABC}	{ABE}	{ACE}	{BCE}	{ABD}	{ACD}	{BCD}	{ADE}	{BDE}	{CDE}
	{AB}	{AC}	{AE}	{BE}	{BC}	{CE}	{AD}	{CD}	{BD}	{DE}
			{A}	{B}	{C}	{E}	{D}
					Ø

Paragraphes 2 et 3. Les nouvelles bases pour les règles d'association sont définies dans le Paragraphe 4. Les algorithmes permettant l'extraction efficace de ces bases sont présentés dans le Paragraphe 5. Les résultats des expérimentations, qui montrent l'efficacité des algorithmes et l'utilité de la génération de ces bases, sont présentés dans le Paragraphe 6. La conclusion et les perspectives de travaux ultérieurs font l'objet du Paragraphe 7. 2 Problème du temps d'extraction des règles d'association Les temps de réponse de l'extraction des règles d'association dépendent principalement des temps d'extraction des itemsets fréquents car plusieurs balayages du contexte doivent être réalisés en comptant pour chaque itemset fréquent potentiel le nombre d'objets du contexte dans lesquels il est contenu. Le nombre d'itemsets à considérer (2 |A| |A| ) et la taille des jeux de données (contexte d'extraction) étant importants (de plusieurs dizaines de milliers à plusieurs millions d'objets et de plusieurs centaines à plusieurs milliers d'items) des algorithmes permettant de minimiser le nombre d'itemsets candidats (itemsets potentiellement fréquents) considérés et le nombre de balayages du contexte ont été proposés.

et leurs supports. Tous les itemsets fréquents et leurs supports, et donc toutes les règles d'association ainsi que leurs supports et leurs confiances, peuvent donc être déduits efficacement, sans accéder au jeu de données, à partir des itemsets fermés fréquents et leurs supports. Cette propriété découle du fait que le support d'un itemset fréquent est égal au support de sa fermeture et que les itemsets fréquents maximaux sont des itemsets

  sont définis en utilisant la fermeture de la connexion de Galois d'une relation binaire finie[START_REF] Davey | Introduction to lattices and order[END_REF][START_REF] Ganter | Formal Concept Analysis : Mathematical foundations[END_REF]. Ces itemsets sont les itemsets fréquents qui sont fermés selon l'opérateur de fermeture γ de la connexion de Galois qui est la composition de l'application ϕ, qui associe à un ensemble O ⊆ O O les items communs à tous les objets o ∈ O, et de l'application ψ, qui associe à un itemset l ⊆ I I les objets en relation avec tous les items i ∈ l. L'opérateur γ = ϕ o ψ associe à un itemset l l'ensemble maximal d'items communs à tous les objets contenant l, c'est-à-dire l'intersection de ces objets.

	générateurs fréquents extraits durant l'itération précédente. L'algorithme Close + [Pas00] permet
	d'identifier les itemsets fermés fréquents et leurs générateurs parmi les itemsets fréquents, sans
	accéder au jeu de données.
	Figure 2 : Diagramme de Hasse représentant le treillis des itemsets fermés.
	Par exemple, dans le
	contexte D D, l'itemset {BCE} est un itemset fermé car il est l'ensemble maximal d'items communs
	aux objets {2, 3, 5, 6}. L'itemset {BC} n'est pas un itemset fermé car il n'est pas un ensemble
	maximal d'items communs à certains objets : tous les objets contenant les items B and C (les
	objets 2, 3, 5 et 6) contiennent également l'item E. Dans la cas d'une base de données de ventes,
	cela signifie que les clients achètent au plus les articles B, C et E, et que tous les clients qui
	achètent les articles B et C achètent également l'article E. Les itemsets fermés fréquents, selon
	cet opérateur de fermeture, constituent un ensemble générateur non redondant minimal pour tous
	les itemsets fréquents fermés
	fréquents maximaux [Pas00, PBTL98]. Les itemsets fermés fréquents forment un treillis dont la
	taille est bornée par la taille du treillis des itemsets fréquents 2 |A A| . Toutefois, en pratique, la taille
	de ce treillis est en moyenne bien inférieure à la taille du treillis des itemsets [GM94]. Le
	diagramme de Hasse représentant le treillis des itemsets fermés associé au contexte D D est
	représenté dans la Figure 2.
	Dans [Pas00, PBTL99b], les générateurs des itemsets fermés sont définis : les générateurs d'un itemset fermé f sont les itemsets minimaux g dont la fermeture est égale à f : γ(g) = f. Les générateurs de l'itemset fermé {BCE} sont les itemsets {BC} et {CE} car les itemsets {BE} et
	{C} sont fermés et la fermeture des itemsets {B} et {E} est {BE}. Les algorithmes Close [Pas00,
	PBTL99a] et A-Close [Pas00, PBTL99b] sont des algorithmes d'extraction des itemsets fermés
	fréquents par niveaux : ils considèrent un ensemble de générateurs candidats d'une taille donnée,
	et déterminent leurs supports et leurs fermetures en réalisant un balayage du contexte lors de
	chaque itération. Les fermetures (fréquentes) des générateurs fréquents sont les itemsets fermés
	fréquents extraits lors de l'itération. Les générateurs candidats sont construits en combinants les

Algorithme Close d'extraction des itemsets fermés fréquents L

  'algorithme Close, proposé en 1998, est un algorithme itératif d'extraction des itemsets fermés fréquents qui parcourt l'ensemble des générateurs des itemsets fermés fréquents par niveaux. Durant chaque itération k de l'algorithme, un ensemble FFC k de k-générateurs candidats est considéré. Chaque élément de cet ensemble est constitué de trois éléments : le k-générateur candidat, sa fermeture, qui est un itemset fermé candidat, et leur support. À la fin de l'itération k, l'algorithme stocke un ensemble FF k contenant les k-générateurs fréquents, leurs fermetures, qui sont des itemsets fermés fréquents, et leurs supports.

  Les (k+1)-générateurs candidats sont créés en joignant les k-générateurs de FF k qui possèdent les mêmes k-1 premiers items. Les 3-générateurs {ABC} et {ABD} par exemple seront joints afin de créer le 4-générateur candidat {ABCD}. 2. Les (k+1)-générateurs candidats dont on sait qu'ils sont soit infréquents, soit non minimaux sont ensuite supprimés. Ces générateurs sont identifiés par l'absence d'un de leurs sous-ensembles de taille k parmi les k-générateurs fréquents de FF k . 3. La troisième phase permet de supprimer parmi ces générateurs ceux dont la fermeture a déjà été calculée. Un tel générateur est identifié car il est inclus dans la fermeture d'un kgénérateur fréquent de FF k dont il est un sur-ensemble. Les itérations cessent lorsque aucun nouveau générateur candidat ne peut être créé et l'algorihtme s'arrête alors. L'algorithme A-Close, développé afin d'améliorer l'efficacité de l'extraction dans le cas de données faiblement corrélées, ne calcule pas les fermetures des générateurs candidats durant les itérations, mais lors d'un ultime balayage réalisé après la fin de ces itérations.

	{ACD} {AC} {C} 1. FFC 1	{ABCDE}	{BE} {ABCE} {BCE}	FF 1
	Balayage	Générateur {A}	Fermé {AC}	Support Ø 3/6	Suppression	Générateur {A}	Fermé Support {AC} 3/6
	de D D	{B}	{BE}	5/6	des itemsets	{B}	{BE}	5/6
	→	{C}	{C}	5/6	infréquents	{C}	{C}	5/6
		{D}	{ACD}	1/6	→
		{E}	{BE}	5/6		{E}	{BE}	5/6
			FFC 2				FF 2
		Générateur	Fermé	Support		Générateur	Fermé Support
	Balayage	{AB}	{ABCE}	2/6	Suppression	{AB}	{ABCE}	2/6
	de D D	{AE}	{ABCE}	2/6	des itemsets	{AE}	{ABCE}	2/6
	→	{BC}	{BCE}	4/6	infréquents	{BC}	{BCE}	4/6
		{CE}	{BCE}	4/6	→	{CE}	{BCE}	4/6

Exemple 4 La Figure 3 représente l'exécution de l'algorithme Close au contexte d'extraction D D pour un seuil minimal de support de 2/6.

  Une règle d'association est une règle d'implication entre deux itemsets à laquelle sont associées la mesure de support, qui définit la portée de la règle, et la mesure de confiance, qui définit la précision de la règle dans le contexte d'extraction. Le support et la confiance indiquent l'utilité et la pertinence de la règle et doivent donc être pris en considération lors de la définition des règles d'association redondantes. Une règle d'association r : l 1 → l 2 de support s et de confiance c est notée r : l 1 → l 2 . Une règle d'association r ∈ E est redondante si la règle r peut être déduite ainsi que son support s et sa confiance c de l'ensemble E \ r. Soit un ensemble E de règles d'association. Une règle r :l 1 → l 2 \in E est redondante si et seulement si E \ {r : l 1 → l 2 } \models r:l 1 → l 2 .Comme nous l'avons vu dans l'Exemple 1, il est souhaitable que seules les règles d'association non redondantes minimales, qui sont les règles les plus utiles et les plus pertinentes, soient

	Définition 1 (Règles d'association redondantes [Pas00])

extraites et présentées à l'utilisateur. Une règle d'association est redondante si elle convoie la même information ou une information moins générale que l'information convoyée par une autre règle de même utilité et de même pertinence. Une règle d'association r est non redondante minimale s'il n'existe pas une autre règle d'association r' possédant le même support et la même confiance, dont l'antécédent est un sous-ensemble de l'antécédent de r et la conséquence est un sur-ensemble de la conséquence de r.

Définition 2 (Règles d'association non redondantes minimales [Pas00])

Soit l'ensemble AR des règles d'association extraites du contexte. Une règle d'association r : l 1 → l 2 ∈ AR est non redondante minimale s'il n'existe pas de règle d'association r' : l' 1 → l' 2 ∈ AR telle que support(r) = support(r'), confiance(r) = confiance(r'), l' 1 ⊆ l 1 et l 2 ⊆ l' 2 .

À partir de cette définition, les règles d'association exactes non redondantes minimales sont définies dans le Paragraphe 4.1 et les règles d'association approximatives non redondantes minimales sont définies dans le Paragraphe 4.2. Ces règles constituent la base générique pour les règles d'association exactes et la base informative pour les règles d'association approximatives respectivement, et sont générées à partir des itemsets fermés fréquents et leurs générateurs.

Table 2 :

 2 Base générique extraite du contexte D D.

		Fermeture	Règle exacte	Support
	{A} {B}	{AC} {BE}	A → C B → E	3/6 5/6
	{C}	{C}
	{E}	{BE}	E → B	5/6
	{AB}	{ABCE}	AB → CE	2/6
	{AE}	{ABCE}	AE → BC	2/6
	{BC}	{BCE}	BC → E	4/6
	{CE}	{BCE}	CE → B	4/6

Base informative pour les règles approximatives [Pas00])

  itemset fermé fréquent f 2 qui est la fermeture de l 2 et le générateur unique g 2 de f 2 tels que g 2 ⊆ l 2 ⊆ f 2 . La règle g 1 → (f 2 \ g 1 ) entre le générateur g 1 et l'itemset fermé fréquent f 2 est la règle non redondante d'antécédent minimal et de conséquence maximale parmi les règles entre un itemset de l'intervalle [g 1 , f 1 ] 3 et un itemset de l'intervalle [g 2 , f 2 ]. En effet, le générateur g 1 est l'itemset minimal dont la fermeture est f 1 , ce qui signifie que l'antécédent g 1 de cette règle est minimal, et la conséquence (f 2 \ g 1 ) est maximale puisque f 2 est l'itemset maximal de l'intervalle [g 2 , f 2 ]. La généralisation de cette propriété à l'ensemble des règles entre deux itemsets l 1 et l 2 définit la base informative qui est donc constituée de toutes les règles d'association approximatives non redondantes selon la Définition 1 d'antécédents minimaux et de conséquences maximales. Soit l'ensemble FF des itemsets fermés fréquents et l'ensemble G de leurs générateurs extraits du contexte. La base informative pour les règles d'association approximatives est :

	Définition 3 (

Table 3 :

 3 . Réduction transitive de la base informative extraite du contexte D. D.

	Générateur Fermeture Sur-ensemble	Règle	Support	Confiance
			fermé	approximative
	{A} {B}	{AC} {BE}	{ABCE} {BCE}	A → BCE B → CE	2/6 4/6	2/3 4/5
	{B}	{BE}	{ABCE}
	{C}	{C}	{AC}	C → A	3/6	3/5
	{C}	{C}	{BCE}	C → BE	4/6	4/5
	{C}	{C}	{ABCE}
	{E}	{BE}	{BCE}	E → BC	4/6	4/5
	{E}	{BE}	{ABCE}
	{AB}	{ABCE}
	{AE}	{ABCE}
	{BC}	{BCE}	{ABCE}	BC → AE	2/6	2/4
	{CE}	{BCE}	{ABCE}	CE → AB	2/6	2/4

Table 5 :

 5 Notations utilisées dans l'algorithme Gen-RI. Génération de la réduction transitive de la base informative avec Gen-RI.Les algorithmes ont été implémentés en C++ et les expérimentations ont été réalisées sur un PC Pentium II possédant une vitesse d'horloge de 350 Mhz et 128 Megaoctets de mémoire, fonctionnant sous le système d'exploitation Linux. Un fichier de mémoire virtuelle d'une taille de 128 Megaoctets a été utilisé, portant à 256 Megaoctets l'espace mémoire total utilisable par les programmes. Nous avons utilisé les quatre jeux de données suivants lors de ces expérimentations :• T20I6D100K 4 , constitué de données synthétiques construites selon les propriétés des données de ventes, qui contient 100 000 objets d'une taille moyenne de 20 items pour une taille moyenne des itemsets fréquents maximaux potentiels de 6 items. • Mushrooms 5 décrivant les caractéristiques de champignons. Il est constitué de 8 416 objets d'une taille moyenne de 23 attributs (23 items par objets et 127 items au total) correspondant aux caractéristiques des champignons. • C20D10K et C73D10K 6 qui sont des échantillons du fichier Public Use Microdata Samples contenant des données du recensement du Kansas effectué en 1990. Ils sont constitués des 10 000 objets correspondant aux 10 000 premières personnes recensées, chaque objet contenant 20 attributs (20 items par objets et 386 items au total) pour C20D10K et 73 attributs (73 items par objets et 2 178 items au total) pour C73D10K. Les temps de réponse présentés dans le Paragraphe 6.1 correspondent aux temps d'extraction des itemsets fréquents et de génération de toutes les règles d'association valides pour Apriori et aux temps d'extraction des itemsets fermés fréquents et de génération de la base générique et de la réduction de la base informative pour les algorithmes Close et A-Close.

	Sortie : Ensemble RI des règles d'association approximatives de la réduction transitive
		de la base de informative;
	1) RI ← ∅;
	2) pour (k ← 1; k ≤ µ-1; k++) faire
	3)	pour chaque k-générateur g ∈ FF k faire
	4)	Succ g ← ∅;
	5)	pour (j = |γ(g)|; j ≤ µ; j++) faire
	6)	S j ← {f ∈ FF | f ⊃ γ(g) ∧ | f | = j};
	7)	fin pour
	8)	pour (j = |γ(g)|; j ≤ µ; j++) faire
	9)	pour chaque itemset fermé fréquent f ∈ S j faire
	10)	si ( ∃ s ∈ Succ g | s ⊂ f ) alors faire
	11)	Succ g ← Succ g ∪ f;
	12)	r.confiance ← f.support / g.support;
	13)	si r.confiance ≥ minconfiance
	14)	alors RI ← RI ∪ {(r : g → (f \ g), r.confiance, g.support};
	15)	finsi
	16)	fin pour
	17)	fin pour
	18)	fin pour
	19) fin pour
	20) retourner RI;
		Algorithme 2 :

Entrée : Ensembles FF k des k-groupes fréquents des k-générateurs; seuil minimal de confiance minconfiance;

Temps d'extraction des règles d'association

  Pour T20I6D100K, les temps de réponse de Apriori et A-Close sont identiques et inférieurs à ceux de Close pour les seuils de support de 2 % à 0,75 %. Les données de ventes étant éparses et faiblement corrélées, pour ces exécutions tous les itemsets fréquents sont des itemsets fermés fréquents (le treillis des itemsets fermés est identique au treillis des itemsets), ce qui correspond au pire des cas pour Close qui réalise plus d'opérations que Apriori et A-Close afin de déterminer les fermetures des générateurs. L'algorithme A-Close ne calcule pas les fermetures des générateurs dans cette situation et fournit donc des temps de réponse identiques à Apriori. Ceci n'est plus le cas pour les seuils de support de 0,5 % à 0,25 % pour lesquels certains itemsets (générateurs) ne sont pas fermés et où les temps de réponse de A-Close rejoignent ceux de Close.Malgré ces différences, les temps d'exécution des trois algorithmes, qui varient de quelques secondes à quelques minutes, restent acceptables dans tous les cas. Pour Mushrooms, C20D10K et C73D10K les temps d'exécution de Close et A-Close sont très inférieurs à ceux de Apriori. Ces résultats s'expliquent par les caractéristiques des données de ces jeux qui sont corrélées et denses. En conséquence, le nombre d'itemsets fréquents est important et la proportion d'itemsets fermés fréquents parmi ces derniers est faible. L'espace de recherche des algorithmes Close et A-Close (le treillis des itemsets fermés) est de taille très inférieure à l'espace de recherche de l'algorithme Apriori (le treillis des itemsets). Contrairement aux temps de réponses obtenus pour T20I6D100K, les différences des temps de réponse entre Close et Apriori se mesurent en minutes ou en dizaines de minutes pour Mushrooms et C20D10K, et en dizaines de minutes ou en heures pour C73D10K. De plus, Apriori et A-Close n'ont pu être exécutés sur le jeu Mushrooms pour des seuils de support inférieurs à 7,5 % car ils dépassent alors la limite de 256 Mégaoctets correspondant à la quantité maximale de mémoire utilisable par les programmes. Pour la même raison, Apriori et A-Close n'ont pu être exécutés pour des seuils de support inférieurs à 65 % sur le jeu C73D10K.

	Les temps d'extraction des règles d'association avec Apriori et des bases pour les règles T20I6D100K Mushrooms
	d'association avec Close et A-Close pour les jeux de données T20I6D100K, Mushrooms,
	C20D10K et C73D10K sont présentés dans la Figure 4. Le seuil minconfiance a été fixé à 0,5 %
	pour T20I6D100K, 30 % pour Mushrooms et C20D10K, et 80 % pour C73D10K.
	C20D10K	C73D10K

Figure 4 :Temps d'extraction des règles d'association.

6.

2 Nombre de règles d'association exactes extraites

  Le nombre total de règles d'association exactes valides et le nombre de règles dans la base de Duquenne-Guigues sont présentés dans la Table4. Aucune règle d'association exacte n'est extraite du jeu T10I4D100K car pour ce seuil de support, tous les itemsets fréquents sont des itemsets fermés fréquents : ils possèdent tous des supports différents et sont donc eux-mêmes leur propre générateur unique. En conséquence, il n'existe aucune règle de la forme l 1 → (l 2 \ l 1 ) entre deux itemsets fréquents l 1 et l 2 dont les fermetures sont identiques : γ(l 1 ) = γ(l 2 ) qui sont les règles d'association exactes valides dans le contexte.Pour les trois autres jeux de données, constitués de données denses et corrélées, le nombre total de règles exactes valides varie de plus de 2 000 à plus de 52 000, ce qui est considérable et rend difficile la découverte de relations intéressantes dans ces ensembles. La base de Duquenne-Guigues représente une réduction importante du nombre de règles exactes extraites mais représente également une perte d'information importante. La base générique de taille supérieure, mais acceptable, ne représente aucune perte d'information et apporte donc une connaissance complète, pertinente et facilement utilisable du point de vue de l'utilisateur.

	Jeu de données Minsupport	Règles	Base de	Base générique
			exactes	Duquenne-Guigues
	T10I4D100K	0,5 %	0	0	0
	Mushrooms	30 %	7 476	69	543
	C20D10K	50 %	2 277	11	457
	C73D10K	90 %	52 035	15	1 369

Table 5 :

 5 Nombre de règles d'association exactes extraites.

6.

3 Nombre de règles d'association approximatives extraites

  Le nombre total de règles d'association approximatives valides et le nombre de règles dans la réduction transitive de la base de Luxenburger et la réduction transitive de la base informative sont présentés dans la Table6. Le nombre total de règles d'association approximatives valides est pour les quatre jeux de données très important puisqu'il varie de près de 20 000 règles pour T20I6D100K à plus de 2 000 000 de règles pour C73D10K. Il est donc indispensable de réduire l'ensemble des règles extraites afin de le rendre utilisable. Pour T20I6D100K, les deux bases sont de taille identique et représentent une division par un facteur de 5 environ du nombre de règles approximatives extraites. Pour Mushrooms, C20D10K et C73D10K, le nombre total de règles d'association approximatives valides est bien plus important que pour les données synthétiques car ces données étant denses et corrélées, le nombre d'itemsets fréquents est bien plus élevé et il en est donc de même pour le nombre de règles approximatives valides. La proportion d'itemsets fermés fréquents parmi les itemsets fréquents étant faible, ces deux bases pour les règles approximatives de tailles sensiblement équivalentes permettent de réduire considérablement (par un facteur variant de 40 à 500) le nombre de règles extraites.L'examen des règles extraites dans chacune des deux bases par rapport a l'ensemble des règles valides a permis de vérifier qu'aucune de ces bases ne contient de règles redondantes. Considérant l'exemple présenté dans le Paragraphe 1 concernant les neuf règles approximatives extraites du jeu de données Mushrooms, seule la règle 4 est générée parmi ces neuf règles dans les bases. En effet, les itemsets {lamelles libres} et {lamelles libres, comestible, voile partiel, voile blanc} sont deux itemsets fermés fréquents dont le premier est un prédécesseur immédiat du second, la règle 4 appartient donc à la réduction transitive de la base de Luxenburger. Ces deux itemsets sont les seuls itemsets fermés fréquents de l'intervalle [∅, {lamelles libres, comestible, voile partiel, voile blanc}]. De plus, l'itemset fermé fréquent {lamelles libres} étant lui-même son seul et unique générateur, la règle 4 appartient également à la réduction transitive de la base informative et est donc bien la règle non redondante d'antécédent minimal et de conséquence maximale parmi ces neuf règles.

	Jeu de données Minconfiance	Règles	Réduction base	Réduction
			approximatives	de Luxemburger	base informative
	T10I4D100K	70 %	20 419	4 004	4 004
	(0,5 %)	30 %	22 952	4 519	4 519
	Mushrooms	70 %	37 671	968	1 221
	(30 %)	30 %	71 412	1 260	1 578
	C20D10K	70 %	89 601	1 948	1 957
	(50 %)	30 %	116 791	1 948	1 957
	C73D10K	90 %	2 053 896	4 089	5 718
	(90 %)	80 %	2 053 936	4 089	5 718

Table 6 :

 6 Nombre de règles d'association approximatives extraites.Dans cet article, le problème de l'utilité et de la pertinence des règles d'association extraites est traité en utilisant la sémantique basée sur la fermeture de la connexion de Galois. Utilisant les itemsets fermés fréquents et leurs générateurs extraits par les algorithmes Close, A-Close et Close + , la base générique pour les règles d'association exactes et la réduction transitive de la base informative pour les règles d'association approximatives sont définies. L'union de ces bases fournit un ensemble générateur non redondant pour toutes les règles d'association valides, leurs supports et leurs confiances. Elle est constituée des règles d'association non redondantes minimales (d'antécédent minimal et de conséquence maximale) et ne représente aucune perte d'information du point de vue de l'utilisateur : ce sont les règles d'association les plus utiles et les plus pertinentes. Toutes les informations convoyées par l'ensemble des règles d'association valides sont également convoyées par l'union de ces deux bases. Deux algorithmes de génération de la base générique et de la réduction transitive de la base informative à partir des itemsets fermés fréquents et leurs générateurs, sont également présentés. Ces bases présentent également un fort intérêt pour :• La visualisation des règles extraites car le nombre réduit de règles dans ces bases ainsi que la distinction des règles exactes et des règles approximatives facilitent la présentation des règles à l'utilisateur. De plus, l'absence de règles redondantes dans les bases et la génération des règles non redondantes minimales seulement présentent un intérêt important du point de vue de l'utilisateur[START_REF] Klemettinen | Finding interesting rules from large sets of discovered association rules[END_REF].• L'identification des règles d'association non redondantes minimales parmi l'ensemble des règles d'association valides extraites, à partir de la Définition 2. Il est ainsi possible d'étendre une implémentation existante d'extraction des règles d'association ou bien d'intégrer cette méthode dans le système de visualisation afin de présenter les règles d'association non redondantes minimales à l'utilisateur. Des algorithmes permettant d'identifier les itemsets fermés fréquents et leurs générateurs parmi les itemsets fréquents, et donc permettant de générer les règles d'association minimales non-redondantes à partir du résultat d'une implémentation existante, sont décrits dans [Pas00]. • L'analyse de données et l'analyse formelle de concepts car elles ne représentent aucune perte d'information par rapport à l'ensemble des règles d'implication valides et sont constituées des règles les plus utiles et les plus pertinentes. La Définition 2 des règles non redondantes minimales étant également valide dans le cadre des règles d'implications globales et partielles entre ensembles d'attributs binaires, les Définitions 3 de la base générique et 4 de la base informative sont également valides pour les règles d'implications globales et partielles respectivement. Les perspectives de travaux ultérieurs concernent l'étude des diverses techniques d'implémentation et structures de données afin d'améliorer les processus d'extraction de connaissances dans les bases de données selon leurs propriétés et les différents types de données [Bas00]; le développement d'un algorithme efficace d'extraction des ensembles fréquents de littéraux spécifiant l'occurrence ou la non occurrence d'un item dans l'ensemble [Bas00]. Ces itemsets permettent la génération de règles d'association avec négation des occurrences des items et l'amélioration de la mesure de la précision des règles approximatives en utilisant des mesures statistiques autres que la confiance telles que la conviction.L'extraction des ensembles fréquents de tels littéraux pose des problèmes plus importants en termes de temps d'exécution et d'espace mémoire que l'extraction des itemsets fréquents, deux littéraux devant être considérés pour chaque item.

7 Conclusion et perpectives

Les règles d'implication partielles sont également appelées règles d'implication avec quelques contre-exemples ou règles d'implication valides dans un sous-contexte. Les règles d'implication globales sont des règles d'association exactes, et les règles d'implication partielles sont des règles d'association approximatives, avec une mesure de support associée.

L'intervalle [g1, f1] contient tous les sur-ensembles de g1 qui sont des sous-ensembles de f1.

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

ftp://ftp.ics.uci.edu/~cmerz/mldb.tar.Z

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


Rafik Taouil
email: taouil@libd2.univ-bpclermont.fr

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

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

Lotfi Lakhal
email: lakhalg@libd2.univ-bpclermont.fr

Mining Bases for Association Rules Using Closed Sets

We address the problem of the usefulness and the relevance of the set of discovered association rules. Using the frequent closed itemset groundwork, we propose to generate bases for association rules, that are non-redundant generating sets for all association rules.

Introduction

Association rules are conditional implications between frequent itemsets. The problem of the usefulness and the relevance of the set of discovered association rules is related to the huge number of rules extracted and the presence of many redundancies among these rules for many datasets. We address this important problem using the Galois connection framework and we show that we can generate bases for association rules using the frequent closed itemsets extracted by the Close [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF] or the A-Close [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF] algorithms.

Galois connection framework

The association rule extraction is performed from a data mining context that is a triplet D = (O; I; R), where O and I are finite sets of objects and items respectively, and R O I is a binary relation. Each couple (o; i) 2 R denotes the fact that the object o 2 O is related to the item i 2 I. The closure operator h of the Galois connection [START_REF] Ganter | Formal Concept Analysis: Mathematical foundations[END_REF] is the composition of the application f , that associates with O O the items common to all objects o 2 O, and the application g, that associates with an itemset I I the objects related to all items i 2 I . The closure operator h = f g associates with I the maximal set of items common to all the objects containing I , i.e. the intersection of these objects. Using this closure operator, we define the frequent closed itemsets that constitute a minimal non-redundant generating set for all frequent itemsets and their support, and thus for all association rules, their support and their confidence. This property comes from the fact that the support of a frequent itemset is equal to the support of its closure and that the maximal frequent itemsets are maximal frequent closed itemsets [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF][START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF].

Definition 1 (Frequent closed itemsets) A frequent itemset I is a frequent closed itemset iff h(I ) = I . The smallest (minimal) closed itemset containing an itemset

I is h(I ), i.e.
the closure of I . We denote F C the set of frequent closed itemsets in D.

Bases for association rules

We adapt the Duquenne-Guigues basis for global implications [START_REF] Duquenne | Famille minimale d'implications informatives résultant d'un tableau de données binaires[END_REF][START_REF] Ganter | Formal Concept Analysis: Mathematical foundations[END_REF] and the Luxenburger basis for partial implications [START_REF] Luxenburger | Implications partielles dans un contexte[END_REF] to the exact association rules (100% confidence rules) and the approximate association rules respectively.

Theorem 1 (Duquenne-Guigues basis)

A frequent pseudo-closed itemset is a frequent itemset that is not closed and that contains the closures of all its subsets that are frequent pseudo-closed itemsets. Let F P be the set of frequent pseudo-closed itemsets in D. The Duquenne-Guigues basis for exact association rules contains all rules of the form I 1 ! (I 2 n I 1 ) for I 1 2 F P , I 2 2 F C and h(I 1 ) = I 2 .

Theorem 2 (Luxenburger basis) The Luxenburger basis for approximate association rules contains all rules of the form I 1 ! (I 2 nI 1 ) for I 1 ; I 2 2 F C and I 1 I 2 . The transitive reduction of this basis, i.e. for I 1 I 2 and @I 3 2 F C such as I 1 I 3 I 2 , is also a basis for all approximate association rules.

All approximate association rules, their support and their confidence can be deduced from the Luxenburger basis, or its reduction, and all exact association rules can be deduced from the Duquenne-Guigues basis. They are minimal non redundant sets of association rules.