Conclusion générale
La fouille de donnees est un domaine qui est apparu suite a un
besoin incessant exprime par les entreprises. Ce besoin consiste en l'analyse
des flux de donnees qui s'accumulent quotidiennement dans leurs bases de
donnees. Partant du fait que l'analyse de ces donnees est une solution cle pour
toute entreprise voulant tirer profit des masses d'informations stockees, la
fouille des donnees s'est vite integree dans differents domaines [42]. La
fouille de donnees englobe plusieurs techniques, dont l'extraction des regles
d'association. Ainsi, l'approche basee sur l'extraction des itemsets fermes
frequents [48], issue de l'analyse formelle de concepts [66], presentait une
promesse claire de reduire, sans perte d'information, la liste de toutes les
regles d'association extraites d'un contexte. Ceci donnait la possibilite de
presenter un ensemble minimal de regles a l'utilisateur afin de lui permettre
de mieux les visualiser et les exploiter. Une etude critique nous a permis de
constater que les algorithmes dediees a cette approche ont failli a cette
promesse. En effet, ils ne font qu'extraire les itemsets fermes frequents et au
plus leurs generateurs minimaux associes sans se soucier de la relation d'ordre
partiel.
Afin de satisfaire la promesse apportee par l'approche basee
sur l'extraction des itemsets fermes frequents, nous avons introduit un nouvel
algorithme, appele PRINCE, permettant d'extraire les composantes suivantes :
1. Les itemsets fermes frequents ;
2. Les generateurs minimaux associes aux itemsets fermes
frequents ;
3. La relation d'ordre sous-jacente.
La principale originalite de l'algorithme introduit est qu'il
construit une structure partiellement ordonnee, appelee treillis des
générateurs minimaux. Cette structure maintient la relation
d'ordre partiel entre les generateurs minimaux frequents et non plus entre les
itemsets fermes frequents. Une fois cette structure construite, la generation
des bases generiques de regles d'association devient immediate. En effet, un
parcours ascendant permet de deriver les regles generiques sans avoir a
calculer les fermetures. L'etude de la
complexité théorique de l'algorithme PRINCE nous
a montré que sa complexité au pire des cas est linéaire en
fonction du nombre d'itemsets fermés fréquents 2'. Cependant,
cette complexité théorique reste de même ordre de grandeur
que celle des algorithmes dédiés a l'extraction des itemsets
fermés fréquents. L'étude expérimentale, que nous
avons menée, a porté sur deux parties. La première partie
a consisté a tester l'effet des optimisations apportées a
l'algorithme PRINCE et a analyser ses caractéristiques. La
deuxième partie s'est intéressée a comparer les
performances de notre algorithme comparées a celles des algorithmes
CLOSE, A-CLOSE et TITANIC. Cette deuxième partie des
expérimentations a montré que l'algorithme PRINCE est plus
performant que les algorithmes CLOSE, A-CLOSE et TITANIC sur les bases
benchmark et les bases "pire des cas". En effet, PRINCE est en moyenne 33
(resp. 45 et 32) fois plus rapide que CLOSE (resp. A-CLOSE et TITANIC) et la
différence atteint 160 (resp. 403 et 538) fois.
Bien que les résultats obtenus sont encourageants,
plusieurs perspectives de travaux futurs peuvent être envisagées
pour l'amélioration des performances de l'algorithme PRINCE. Ces
perspectives sont comme suit :
G L'étude de la possibilité d'intégrer la
notion d'itemsets non-dérivables fréquents [18] dans la
première étape de PRINCE, cad Détermination des
générateurs minimaux. En effet, cette notion s'applique a tout
ensemble vérifiant la propriété d'idéal d'ordre tel
que l'ensemble des générateurs minimaux dans notre cas. Elle
permet d'estimer, moyennant l'application d'un système
d'inéquations, le support minimal (lower bound) et le support
maximal (upper bound) que peut avoir un candidat c. Si ces deux
supports sont égaux, il n'y a nul besoin d'ajouter c parmi les
candidats auxquels un accès au contexte d'extraction est
nécessaire pour calculer leurs supports car le support réel
de c est égal a son support minimal (égal a son support
maximal). Ainsi, cette intégration devrait réduire le nombre de
candidats lors de l'étape, parfois cofiteuse, du calcul du support des
candidats. Il serait alors intéressant de voir si malgré le cofit
induit par l'application du système d'inéquations pour chaque
candidat, l'intégration de ces travaux permettent de réduire le
cofit du calcul du support.
Un remplacement du stockage de la bordure négative des
générateurs minimaux GBd-, utilisée
lors de la deuxième étape de PRINCE, par le stockage d'un
sous-ensemble de GBd-, appelée bordure
négative des générateurs minimaux infréquents et
notée IDFreeGBd- [39]. En effet, dans [39], l'auteur
montre que l'union de l'ensemble des générateurs minimaux
fréquents GMFK et de IDFreeGBd- est une
représentation concise de l'ensemble des itemsets fréquents. Ce
stockage présente un avantage,
a savoir de reduire l'espace de recherche lors de la recherche
d'un support dans la deuxieme etape. Cependant, il presente aussi une
contrainte, a savoir le coUt de la determination de
IDFreeGBd- [39]. L'elaboration d'une version de PRINCE
utilisant IDFreeGBd- au lieu de GBd-
parait interessante a tester.
La reduction d'avantage du nombre de regles generiques
extraites et ceci moyennant deux pistes possibles :
1. Utilisation d'autres contraintes autres que le seuil minimum
de confiance, minconf [15].
2. Restriction de l'extraction des bases generiques
informatives aux generateurs minimaux frequents formant une representation
succincte des generateurs minimaux [22]. Cette representation est de taille
inferieure a celle de l'ensemble des generateurs minimaux frequents
GMFK et permet ainsi de reduire le nombre de regles informatives. Il
serait alors interessant d'etudier les proprietes des nouvelles bases obtenues
ainsi que de trouver un systeme axiomatique permettant de retrouver toutes les
regles formant les bases generiques informatives.
| 