Chapitre 3
L'algorithme PRINCE
3.1 Introduction
L'utilisation des regles d'association est un domaine en
pleine expansion. En effet, de nos jours, l'exploitation des regles
d'association dépasse le cadre du panier de la ménagere,
introduit par Agrawal et al. en 1993 [1], pour s'intéresser a plusieurs
autres domaines tels que l'aide a planification commerciale [42], l'aide a la
recherche médicale [20], l'analyse des images, de données
spatiales, géographiques, etc [54]. Cependant, l'extraction des regles
d'association a partir des itemsets fréquents génere un nombre
généralement tres élevé de regles même pour
des contextes de tailles raisonnables (quelques milliers d'objets) [67]. Ainsi,
l'exploitation et la visualisation de ces regles devient de loin une
tâche facile pour l'utilisateur. Pour pallier cet inconvénient,
l'approche basée sur l'extraction des itemsets fermés
fréquents propose d'extraire, sans perte d'information, un sous-ensemble
de regles, a partir duquel nous pouvons retrouver toutes les autres regles
(redondantes) [5, 56, 67]. Ainsi, les bases génériques formant
les regles d'association informatives [4, 5] ont été introduites
pour obtenir des ensembles de regles informatives et pour présenter a
l'utilisateur les regles les plus pertinentes sans perte d'information. Un
survol critique des algorithmes, basés sur l'extraction des itemsets
fermés, montre que ces algorithmes ont failli a leurs objectifs [9]. En
effet, l'obtention des bases génériques de regles
nécessite l'extraction de trois composantes, a savoir les itemsets
fermés fréquents, leurs générateurs minimaux
associés ainsi que la relation d'ordre partiel sous-jacente. Cette
relation d'ordre partiel est une condition sine qua non pour l'obtention des
regles d'association génériques approximatives [9]. Les
générateurs minimaux permettent d'obtenir les regles les plus
informatives pour l'utilisateur. Les notions d'ordre partiel et de
générateur mi-
nimal sont donc primordiales. Cependant, la quasi-totalite des
algorithmes reposant sur cette approche, cad celle de l'extraction des itemsets
fermes frequents, se sont focalises sur l'extraction de la premiere composante,
cad les itemsets fermes frequents, en negligeant les deux dernieres
composantes. Seuls les algorithmes adoptant la strategie "Generer-ettester"
font mieux en permettant aussi l'extraction des generateurs minimaux, sans se
soucier de la construction de la relation d'ordre partiel.
Dans ce chapitre, nous allons introduire un nouvel algorithme,
appele PRINCE, pour l'extraction des itemsets fermes frequents, leurs
generateurs minimaux respectifs ainsi que la determination de la relation
d'ordre partiel. A cet effet, PRINCE construit une structure partiellement
ordonnee appelee treillis des generateurs minimaux [7]. La principale
originalite de l'algorithme PRINCE reside dans le fait que cette relation
d'ordre est maintenue entre les generateurs minimaux et non plus entre les
itemsets fermes. Ainsi, les bases generiques de regles sont obtenues par un
simple balayage de la structure partiellement ordonnee sans avoir a calculer
les fermetures.
Dans ce chapitre, nous commencons par decrire les etapes
constituant l'algorithme PRINCE ainsi que la structure de donnees qu'il
utilise. Ensuite, nous montrons sa validite, sa terminaison ainsi que sa
completude. Enfin, nous cloturons la presentation de notre algorithme par une
etude de sa complexite theorique.
|
