Extraction des bases génériques informatives de règles sans calcul de fermetures

sommaire suivant

ECOLE DOCTORALE EN INFORMATIQUE

F

MEMOIRE DE MASTERE

présenté en vue de l'obtention du
Diplome de Mastere en In formatique

par

Tarek HAMROUNI

Maitrise en Informatique, FS de Tunis)

Extraction des bases génériques

informatives de règles sans calcul

de fermetures

soutenu le 14 juillet 2005, devant le jury d'examen

MM. Habib OUNELLI Président

Mohamed Mohsen GAMMOUDI Membre

Yahya SLIMANI Directeur du memoire

Sadok BEN YAHIA Invite

Dedicaces

Ce travail est dedie a mes Maitres, rues parents et ma famille.

Qu'ils trouvent ici le Mmoignage de ma gratitude et de mon
respect.

REMERCIEMENTS

C'est avec un grand plaisir, que j'exprime ici ma reconnaissance a tous ceux qui m'ont apporté leur aide scientifique, matérielle ou morale pour mener a terme ce travail.

A Mr. Habib Ounelli, Maitre de Conférences a la Faculté des Sciences de Tunis, pour avoir accepté de présider le jury de ce Mastère. Je le remercie pour l'attention avec laquelle il a lu et évalué ce mémoire.

A Mr. Mohamed Mohsen Gammoudi, Maitre Assistant a la Faculté des Sciences de Tunis, pour avoir accepté de participer au jury de ce Mastère. Je le remercie pour l'attention avec laquelle il a lu et évalué ce mémoire.

A Mr. Yahya Slimani, Maitre de Conférences a la Faculté des Sciences de Tunis, pour ses orientations, ses conseils et ses suggestions. J'ai spécialement apprécié son esprit critique et sa rigueur scientifique. Qu'il trouve ici l'expression de mon respect.

A Mr. Sadok Ben Yahia, Maitre Assistant a la Faculté des Sciences de Tunis, qui m'a aidé dans ce travail et en a rendu possible la réalisation. J'ai particulièrement apprécié ses qualités humaines indéniables, sa disponibilité et ses conseils de bon aloi. Qu'il trouve ici l'expression de ma gratitude.

Je souhaite aussi exprimer toute ma reconnaissance envers Mr. Yves Bastide, Professeur adjoint a l'Ensar de Rennes, qui s'est montré toujours disponible a répondre a mes questions et pour avoir mis a ma disposition les codes sources des algorithmes CLOSE, A-CLOSE et TITANIC utilisés dans le cadre de ce travail.

Je tiens également a remercier Mlle Yosr Slama, Assistante a la Faculté des Sciences de Tunis, pour son aide a l'élaboration de l'étude théorique de la complexité de l'algorithme proposé.

Je remercie les membres de l'URPAH de la Faculte des Sciences de Tunis de m'avoir accueilli au sein de leur unite et fait beneficier de leurs experiences.

Mes remerciements vont aussi a tous ceux qui, non cites ici, m'ont soutenu tout le long de ce travail.

Résumé: Durant ces dernières ann'ees, les quantit'es de donn'ees collect'ees, dans divers domaines d'application de l'informatique, deviennent de plus en plus importantes. Ces quantit'es ont suscit'e le besoin d'analyse et d'interpr'etation afin d'en extraire des connaissances utiles. Ce m'emoire s'int'eresse a` la technique d'extraction de règles associatives, une des techniques les plus utilis'ees dans le domaine de la fouille de donn'ees. La première approche permettant la g'en'eration de règles associatives s'est bas'ee sur l'extraction des itemsets fr'equents. Cependant, cette approche souffre de deux problèmes majeurs, a` savoir le coüt de l'extraction des itemsets fr'equents, qui sont n'ecessaires a` la g'en'eration de règles associatives, et la g'en'eration d'un nombre important de règles associatives, dont un bon pourcentage est redondant. Pour rem'edier a` ces problèmes, une nouvelle approche bas'ee sur la d'ecouverte des itemsets ferm'es fr'equents en utilisant les treillis de Galois, issus de l'analyse formelle de concepts, a 'et'e propos'ee. Toutefois, les algorithmes relatifs a` cette nouvelle approche se sont focalis'es sur la r'esolution du premier problème, sans se soucier de la construction de la relation d'ordre partiel li'ee a` un treillis de Galois. Cette relation est une condition sine qua non pour l'extraction, sans perte d'information, d'un sous-ensemble de règles associatives, appel'e base g'en'erique. Dans ce cadre, nous avons propos'e un nouvel algorithme appel'e PRINCE pour la g'en'eration de bases g'en'eriques de règles associatives. Cet algorithme effectue une exploration par niveau de l'espace de recherche. Sa principale originalit'e est qu'il est le seul a` construire la relation d'ordre partiel dans l'objectif d'extraire les bases g'en'eriques de règles. Pour r'eduire le coüt de cette construction, la relation d'ordre partiel est maintenue entre l'ensemble des g'en'erateurs minimaux des itemsets ferm'es fr'equents et non plus entre les itemsets ferm'es fr'equents. Une structure, appel'ee treillis des générateurs minimaux, est alors construite a` partir de laquelle la d'erivation des bases g'en'eriques devient imm'ediate. Les exp'erimentations que nous avons r'ealis'ees sur diff'erents contextes d'extraction ont montr'e l'efficacit'e de l'algorithme propos'e, comparativement a` des algorithmes de r'ef'erence tels que CLOSE, A-CLOSE et TITANIC.

Mots-clés: Fouille de donn'ees, Analyse formelle de concepts, Itemsets (ferm'es) fr'equents, Treillis de Galois, Treillis des générateurs minimaux, Règles associatives, Base générique de règles.

Abstract: In the last few years, the amount of collected data, in various computer science applications, becomes increasingly significant. These large volumes of data pointed out the need to analyze them in order to extract useful hidden knowledge. This Master thesis focusses on the association rule extraction, one of the most popular knowledge extraction technique. The first approach to extract association rules, uses the notion of frequent itemsets. However, this approach suffers from two major problems, namely the cost of extracting frequent itemsets and the high number of extracted association rules, among which many are redundant. Thus, a new approach based on Galois lattice uses the notion of frequent closed itemsets instead the frequent ones. However, algorithms related to this new approach have only resolved the first problem and have avoid the problem of construction of the order relation associated to a Galois lattice. This partial order relation is a sine qua non condition to obtain a subset of all association rules, without information loss, called generic basis. For this purpose, we proposed a new algorithm called PRINCE that performs a level-wise browsing of the search space. Its main originality is that it is the only one which constructs the partial order in order to extract generic bases. In order to reduce the cost of this construction, the partial order is maintained between frequent minimal generators and not between frequent closed itemsets. A structure called minimal generator lattice is then built, from which the derivation of the generic association rules becomes straightforward. Several experimentations of our algorithm have showed the efficiency of the proposed algorithm, comparatively to well-known algorithms like CLOSE, A-CLOSE and TITANIC.

Key-words: Data mining, Formal concept analysis, Galois lattice, Frequent (closed) itemsets, Minimal generator lattice, Association rules, Generic rule basis.

Table des matières

4 Ètude experimentale 65

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2 Environnement d'expérimentation . . . . . . . . . . . . . . . . . . . . . . . 66

4.2.1 Environnement materiel et logiciel . . . . . . . . . . . . . . . . . . . 66

4.2.2 Description des executables . . . . . . . . . . . . . . . . . . . . . . 66

4.2.3 Bases de test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.3 Optimisations et evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.4 Effets de la variation de la mesure minconf . . . . . . . . . . . . . . . . . . 74
4.5 Comparaisons des coits des étapes de PRINCE . . . . . . . . . . . . . . . . 75

4.5.1 Bases benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

4.5.2 Bases "pire des cas" . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.6 Performances de PRINCE vs. CLOSE, A-CLOSE et TITANIC . . . . . . . . . 83

4.6.1 Bases benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.6.2 Bases "pire des cas" . . . . . . . . . . . . . . . . . . . . . . . . . . 90

4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

Conclusion generale 93

Table des figures

1.1 Exemple de contexte formel . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Join - Meet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3 Join-irréductible - Meet-irréductible . . . . . . . . . . . . . . . . . . . . . . 12

3.1 Contexte d'extraction 1C . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.2 Construction du treillis des generateurs minimaux et le treillis d'Iceberg

associés au contexte d'extraction 1C pour minsup2. . . . . . . . . . . . . . 56 3.3 Gauche : La base générique de regles exactes BG. Droite : La réduction

transitive des regles approximatives RI. . . . . . . . . . . . . . . . . . . . . 56
3.4 Exemple d'un trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.1 Exemple d'une base "pire des cas" avec n4 . . . . . . . . . . . . . . . . . 68 4.2 La structure Itemset-Trie (Gauche) et la structure IT-BDT (Droite)

associées au contexte d'extraction de la Figure 3.1 . . . . . . . . . . . . . . 70 4.3 Effet de l'utilisation d'une représentation compacte de la base sur les per-

formances de PRINCE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.4 Effet de l'exécution de la procédure GEN-ORDRE sur les performances de

PRINCE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.5 Effet de l'utilisation des 2-itemsets fréquents non générateurs minimaux

sur les performances de PRINCE . . . . . . . . . . . . . . . . . . . . . . . . 73 4.6 Effet de l'utilisation des listes prohibées sur les performances de PRINCE . 74 4.7 Effet de la variation de minconf sur les performances de PRINCE . . . . . . 75 4.8 Temps d'exécution des étapes constituant PRINCE pour les bases denses . . 77 4.9 Temps d'exécution des étapes constituant PRINCE pour les bases éparses . 82 4.10 Temps d'exécution des étapes constituant PRINCE pour les bases "pire des

cas" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.11 Les performances de PRINCE vs. CLOSE, A-CLOSE et TITANIC pour les

bases denses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.12 Les performances de PRINCE vs. CLOSE, A-CLOSE et TITANIC pour les

bases éparses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.13 Test de mise a l'échelle de PRINCE vs. CLOSE, A-CLOSE et TITANIC pour

les bases "pire des cas" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

Liste des tableaux

Liste des algorithmes

Introduction générale

Il est chaque jour plus facile de collecter des donnees mais notre capacite a en extraire des informations a forte valeur ajoutee reste limitee [16]. Ainsi, l'attention des entreprises s'est progressivement detournee des systemes operationnels, vitaux mais sans valeur ajoutee concurrentielle reelle. Elle s'est alors portee sur des systemes decisionnels, sans apport direct en matiere de productivite mais qui contribuent veritablement a la differenciation strategique de l'entreprise [42]. Afin d'exploiter ces masses importantes de donnees stockees dans les systemes decisionnels, la fouille de donnees se propose de donner les outils et/ou techniques necessaires pour l'extraction de cette connaissance. La fouille de donnees (ou Data mining) est le domaine de recherche au sein duquel cooperent statisticiens, specialistes en bases de donnees et en intelligence artificielle, ou encore chercheurs en conception d'interfaces homme-machine [16]. Les informations extraites, suite a l'application d'un processus de fouille de donnees, peuvent prendre plusieurs formes, telles que les regles d'association, les arbres de decisions, les reseaux de neurones, etc [24, 42].

Dans ce memoire, nous allons nous interesser, en particulier, a la technique d'extraction de regles d'association. Cette technique a ete introduite par Agrawal et al. en 1993 [1]. En 1994, Agrawal et al. ont propose un des premiers algorithmes, appele APRIORI [2], pour l'extraction des regles d'association a partir de bases de donnees des grandes surfaces commerciales. Cet algorithme adoptait une strategie d'exploration par niveau de l'espace de recherche, appelee "Generer-et-tester". Ainsi, le probleme d'extraction des regles d'association est alors decompose en deux sous-problemes [2] :

1. Extraction des ensembles d'items (ou itemsets) interessants (ou frequents) pour l'utilisateur, cad presentant une frequence d'apparition superieure ou egale a un certain seuil minimal fixe par l'utilisateur.

Motivations

L'approche d'extraction des regles d'association -- basee sur la decouverte des itemsets frequents -- souffre de deux problemes majeurs, a savoir le coUt de l'extraction des itemsets frequents et surtout la generation d'un tres grand nombre de regles, et ce meme pour de petites bases de donnees.

Pour pallier ces inconvenients, une nouvelle approche basee sur l'extraction des itemsets fermes frequents [48] est apparue. Cette approche est issue des fondements mathematiques de l'analyse formelle de concepts introduite par Wille en 1982 [66]. Cette nouvelle approche propose deux alternatives seduisantes :

1. Une reduction du coUt de l'extraction des itemsets frequents.

2. Une selection d'un sous-ensemble de toutes les regles d'association, a partir duquel le reste des regles pourrait etre derive sans perte d'information. Ce sous-ensemble de regles d'association est communement appele base generi que.

Cependant, pour extraire ces bases generiques de regles, il faut prealablement decouvrir trois composantes primordiales, a savoir [9] :

1. Les itemsets fermes frequents ;

2. La liste des generateurs minimaux associes a chaque itemset ferme frequent ;

3. La relation d'ordre entre les itemsets fermes frequents.

Un survol critique des algorithmes, bases sur l'extraction des itemsets fermes frequents, montre que les algorithmes existants dans la litterature ont failli a leurs objectifs [9]. En effet, la quasi-totalite de ces algorithmes se sont focalises sur l'extraction de la premiere composante, cad les itemsets fermes frequents, en oubliant les deux dernieres. Seuls les algorithmes adoptant la strategie "Generer-et-tester" font mieux en permettant aussi l'extraction des generateurs minimaux, sans se soucier de la construction de la relation d'ordre partiel. Par consequent, les algorithmes existants n'ont pas reussi a generer les bases generiques de regles d'association.

Pour remedier aux insuffisances enumerees, nous proposons, dans ce memoire, un nouvel algorithme, appele PRINCE, permettant l'extraction des itemsets fermes frequents, leurs generateurs minimaux associes ainsi que les bases generiques de regles d'association. A cet effet, l'algorithme propose permet la construction de l'ordre partiel. L'algorithme PRINCE effectue une exploration par niveau de l'espace de recherche. Sa principale originalite est qu'il est le seul a construire la relation d'ordre partiel dans l'objectif d'extraire les bases

generiques de regles. Pour reduire le coUt de cette construction, la relation d'ordre partiel est maintenue entre l'ensemble des generateurs minimaux des itemsets fermes frequents et non plus entre les itemsets fermes frequents. Ceci evite le coUt du calcul des fermetures des itemsets. Une fois la structure partiellement ordonnee construite, l'extraction des bases generiques devient immediate.

Structure du memoire

Les resultats de nos travaux de recherche sont synthetises dans ce memoire qui est compose de quatre chapitres.

Le premier chapitre introduit la technique d'extraction des regles d'association ainsi que les fondements mathematiques de l'analyse formelle de concepts. Il definit egalement la connexion de ces fondements avec le processus d'extraction des bases generiques de regles d'association.

Le deuxieme chapitre presente des algorithmes d'extraction des itemsets fermes frequents. Ensuite, il presente une etude comparative critique de ces algorithmes selon des criteres que nous introduisons.

Le troisieme chapitre est consacre a la presentation de l'algorithme que nous proposons pour l'extraction des trois composantes permettant la derivation des bases generiques de regles d'association. La presentation des differentes etapes de l'algorithme PRINCE est donnee. La demonstration de la validite, la completude et la terminaison ainsi que l'etude de la complexite theorique de l'algorithme PRINCE seront aussi presentees.

Le quatrieme chapitre presente les experimentations effectuees sur l'algorithme PRINCE. Ces experimentations sont divisees en deux parties. La premiere partie s'interesse a l'analyse de quelques optimisations apportees a notre algorithme ainsi qu'a l'analyse de ses caracteristiques. La deuxieme partie compare les performances de l'algorithme PRINCE a celles des algorithmes CLOSE, A-CLOSE et TITANIC.