Les techniques de fouille de données et ses limites

1.4 Principales techniques de fouille de données

Plusieurs techniques ont été élaborées pour la recherche de connaissances utiles à partir de données, les toutes premières sont simples et issues, dans la majorité, de la statistique et de l’analyse de données. Cependant il a été vite constaté que les méthodes statistiques classiques sont souvent limitées, car on ne peut étudier simultanément que quelques variables (1 à 2) (Besse, 2005).

En effet, dès que le modèle à découvrir est complexe et met en œuvre plusieurs variables d’autres méthodes doivent alors être utilisées, on fait recours donc à d’autres techniques et algorithmes sophistiqués. Présentons dans les points suivants une sélection de ces méthodes.

1.4.1 Techniques statistiques et probabilistes

1.4.1.1 La régression linéaire simple, multiple et logistique

La régression simple est la méthode la plus aisée. Elle consiste à analyser la corrélation entre deux variables x et y quantitatives, en approchant cette dépendance par une droite. Ce modèle s’écrit donc : y=ax+b, y est appelée variable expliquée et x variable explicative. Pour un ensemble de points (observations) dans l’espace R2, on cherche à tracer la droite regroupant le plus possible de points (xi, yi). La solution des moindres carrés due à GAUSS est la plus connue (Gardarin, 1999).

La régression linéaire multiple est l’outil statistique le plus habituellement mis en œuvre pour l’étude de données multidimensionnelles. Il constitue la généralisation de la régression simple. Dans ce modèle, on suppose que la variable y est corrélée à un ensemble de variables x1, x2,…, xp, et s’écrit donc : y=b0+b1x1+b2x2+…+bpxp. La solution est alors Y’, la projection de Y sur le sous espace w (de degré p+1) engendré par 1, x1,…, xp. (Saporta, 1990)

La régression logistique, quant à elle, est une extension de la régression linéaire pour la modélisation d’une variable qualitative (binaire) z à deux modalités : 0 ou 1 : succès ou échec, présence ou absence de maladie, panne d’un équipement, faillite d’une entreprise, bon ou mauvais client. Il est clair qu’on ne peut appliquer directement les modèles précédents. Une solution consiste à expliquer non pas la variable mais une probabilité d’apparition, i.e P= Pr (z=0) et 1-P=Pr (z=1) ou une transformation de celle-ci par l’introduction d’une fonction réelle monotone g opérant de [0,1] dans R. La fonction LogIt est la plus préférée (Besse, 2005) :

g (p)=LogIt(p)=Ln p/1-p , g-1(x)=ex/1+ex.

Les tests statistiques sont des techniques largement utilisées pour expliquer la dépendance entre variables. Ce sont des mécanismes qui permettent de trancher entre deux hypothèses (H0 et H1) au vu des résultats d’un échantillon. Parmi les plus utilisés on cite le test de KHI2 (χ2) et le test de Kolmogrov-Smirnov (KS) (Saporta, 1990).

L’ACP est une méthode descriptive permettant de visualiser l’information contenue dans un tableau de n*p éléments (matrice), ou n est le nombre d’individus et p le nombre de variables. Elle consiste à projeter le nuage des individus sur un sous-espace w de dimension q<

1.4.1.4 Les réseaux bayésiens (RB)

Basés sur les travaux de thomas Bayes au 18 siècle, les RB utilise les probabilités conditionnelles pour prédire le futur (probabilité à posteriori) à partir du passé (expérience). Ils sont modélisés par un graphe étiqueté orienté et sans circuit, dont les nœuds représentent des valeurs possibles de variables et les arcs les dépendances conditionnelles entres variables.

Tout nœud étant valué par la probabilité de la variable qu’il représente et tout arc par la probabilité conditionnelle de la cible si la source est réalisé (Gardarin, 1999), (Lauria, 2003). Rappelons que la formule générale de bayes est la suivante où A et Bi étant des hypothèses :

P(Bi/A) =P(A/Bi).P(Bi)/∑k P(A/Bk).P(Bk).

Les RB sont utilisés dans les taches de classification. Néanmoins, Il ne sont pas parfaitement acceptés pour deux raisons : le premier à trait au caractère subjectif de la mesure de probabilité, surtout en l’absence de données d’observations (pour les probabilités à priori), le deuxième concerne le problème de la mise à l’échelle (nombre important de variables) (Lauria, 2003).

1.4.2 Les réseaux de neurones (RN)

Les RN sont des systèmes qui tentent de simuler les mécanismes de traitement de l’information ayant lieu dans le cerveau humain (Freeman et al., 1991). Ils sont constitué d’un ensemble de neurones formels interconnectés et évoluant dans le temps par interactions réciproques. Pour décrire un tel réseau, il nous faut donc décrire : le comportement de chaque neurone et l’interaction entre neurones. Nous retiendrons la définition formelle suivante (Wenzek, 1993) : Un RN est défini à partir :

• * d’un ensemble I de N éléments appelés neurones, ou cellules, ou encore unités,
• * d’un sous-ensemble Q de l’ensemble R des réels codant les différents états accessibles par un neurone,
• * d’une fonction f de R dans Q,
• * d’un graphe (I, G) décrivant les connexions entre les neurones,
• * d’un réel wij, pour chaque couple (i, j) de G,
• * d’un ensemble d’entrées E,
• * et d’une fonction i de E dans R, pour chaque élément i de I.

Un réseau de neurones construit à partir de ces données, est alors un système dont la réponse à une entrée e de E est un vecteur S de Rn vérifiant pour toute cellule i :

si f ( j wij . s j i (e)) j tel que (i, j) G

Sont appelés, respectivement, synapses et coefficients synaptiques, les éléments (i,j) de G et les réels wij, la fonction i est qualifiée de seuil lorsqu’elle est constante sur E, la fonction f est appelée fonction de seuillage ou d’activation.

Une des caractéristiques la plus importante des réseaux de neurones est leur capacité à apprendre, l’apprentissage1 va permettre au réseau de modifier sa structure interne pour s’adapter à son environnement.

En effet, nous n’avons pas besoin d’une formulation rigoureuse d’un problème donné pour le résoudre, tout ce dont nous avons besoin est une collection d’exemples représentatifs de la fonction désirée, ensuite le réseau s’adapte pour reproduire les sorties souhaitées quand un exemple d’entrée est présenté. Cette propriété d’adaptation offre également aux RN, à l’opposé aux méthodes algorithmiques traditionnelles, la capacité à traiter des données bruitées ou incomplètes (Bourret et al., 1991).

Les RN sont utilisés, en fouille de données, pour la classification, la segmentation, l’estimation et la prédiction (Gilleron et al., 2000). Notons toutefois, qu’outre les temps de calcul importants qu’ils entraînent, les RN sont considérés comme des boites noires, dont les règles de fonctionnement sont inconnues, et sont de ce fait incapable d’expliquer les résultats qu’ils fournissent (Besse, 2005).

1 C’est la méthode d’ajustement des poids du réseau, elle peut être choisie dans une gamme variée d’algorithmes, dont voici les plus connus : La règle de Hebb, La règle de Widrow-Hoff, La règle delta, l’algorithme de rétropropagation de l’erreur, apprentissage compétitif (Cf. (Bourret et al, 1991) ou (Freeman et al., 1991))

1.4.3 K-means

Cette technique célèbre de segmentation hiérarchique partitionne de manière itérative les données en K groupes ou clusters fixés au départ. Voici son algorithme (Gardarin, 1999)

3. Algorithme des K-means

1.4.4 Les plus proches voisins (PPV, kNN)

L’algorithme des plus proches voisins (PPV, Nearest neighbor NN en anglais) (Gilleron et al., 2000) est un algorithme dédié à la classification et peut être étendu à l’estimation. Contrairement à d’autres algorithmes de classification, le kPPV ne nécessite pas d’étape d’apprentissage, il est appelé aussi algorithme de « raisonnement à partir de cas », car la décision d’assignation de la classe est basée sur le ou les cas similaires déjà résolus.

Le modèle dans les kPPV est constitué de l’échantillon de données en entrée, de la fonction de distance et de celle de choix de la classe en fonction des classes des voisins les plus proches.

4. L’algorithme des kPPV

La décision d’attribution de la classe à un nouvel exemple est basée sur la recherche de cas similaires les plus proches. Ce choix peut être fait parmi trois solutions :

Prendre la classe du cas le plus proche (1-NN), fonctionne très bien pour des problèmes simples.

Vote majoritaire : prendre la classe majoritaire.

Vote majoritaire pondérée : chaque classe est pondérée, le poids de la classe c (o) de l’objet o est inversement proportionnel à la distance entre o’ objet à classer et o.

Le nombre K de voisins est souvent fixe et égale au nombre d’attributs plus 1, mais il peut être déterminé aussi par test ou par validation croisée.

1.4.5 Arbres de décision (Decision tree)

Les arbres de décision sont des arbres permettant de classer des objets en sous classes par divisions hiérarchiques, dans lequel un nœud représente une sous classe du nœud parent et un arc un prédicat de placement des objets de la classe parent dans la sous classe. Pour le classement d’un enregistrement il suffit de descendre dans l’arbre selon les réponses aux différents tests pour cet enregistrement. Nous pouvons donc associé à un arbre de décision une traduction immédiate en terme de règles de décisions exhaustives et mutuellement exclusives (Gardarin, 1999).

La génération des arbres de décision se fait à partir d’un échantillon d’apprentissage en deux phases : construction de l’arbre par divisions récursives puis élagage de l’arbre depuis les feuilles afin de réduire sa taille. La construction consiste à déterminer une séquence de nœuds, un nœud est défini par le choix d’un attribut de test et d’une division qui induit une partition en classes. La définition d’un critère de sélection de la meilleure division, d’une règle de terminaison (décider qu’un nœud est terminal), et d’affectation de classe sont donc nécessaires (Besse, 2005).

Pour le choix d’une division, différentes mesures (fonctions) ont été proposées dans la littérature, nous nous limitons à deux (Gardarin, 1999),(Gilleron et al., 2000) : la fonction Gini adoptée dans l’algorithme CART développé par Breiman en 1984, et la fonction Entropie utilisée dan l’algorithme C4.5 de Quinlan (1984 puis 1993)

Soit P un ensemble de données à partitionner, appelons Pi la fréquence relative de la classe i dans P.

L’entropie sert à détecter l’attribut le plus discriminant. Elle est donnée par la formule ci-après :

L’indice de Gini est le suivant :

Quelle que soit la mesure adoptée, nous choisissons le test qui fournit le degré de désordre espéré minimum. L’algorithme d’apprentissage pour les arbres de décision est le suivant (Gilleron et al., 2000) :

Données : un échantillon S de m enregistrement classés (x,c(x)) Initialisation :

arbre vide ;

nœud courant :racine; échantillon courant :S Répéter

Décider si le nœud courant est terminal //attributs epuisés,seuils

//atteints

Si le nœud courant est terminal alors

Etiquetter le nœud courant par une feuille

// classe majoritaire

Sinon sélectionner un test et créer un sous arbre //Gini,entropie

Fsi

Nœud courant : un nœud non encore étudié ;

Echantillon courant : échantillon atteignant le nœud courant

Jusqua production d’un arbre de décision

Elaguer l’arbre de décision obtenu

Sortie : arbre de décision élaguer

5. Algorithme d’apprentissage pour les arbres de décision

1.4.6 Le classificateur naïf de Bayes

Soit un échantillon S d’enregistrements avec x1,…, xn attributs descriptifs. Nous souhaitons connaître la classe C d’un élément X, en se basant sur les probabilités à posteriori de Bayes. L’idée est d’affecter à X la classe C tel que P(C/X) soit maximale (Lauria, 2003) : P(C/X)=P(X/C)*P(C)/P(X),

P(X) étant constante pour toutes les classes, nous cherchons donc à maximiser P(X/C)*P(C). P(C) sera estimée, pour toutes les classes, par la proportion d’éléments de la classe C dans S. La difficulté est comment pouvons nous calculer P(X/C). Le classificateur naïf de Bayes part de l’hypothèse de l’indépendance des attributs xi, cela revient à faire la simplification suivante :

P(X/C)=P(x1,…,xn/C)=P(x1/C)*P(x2/C)….P(xn/C)

P(xi/C) est estimée comme la fréquence relative des instances possédant la valeur xi (pour le ieme attribut) dans la classe C.

Cette méthode est simple à mettre en œuvre, et bien quelle soit basée sur une hypothèse fausse en général (l’indépendance des attributs), elle donne cependant de bons résultats dans des problèmes réels (Gilleron et al., 2000).

1.4.7 Algorithme Apriori de recherche de règles associatives

Dans cet algorithme, un ensemble d’objets (produits) ayant un support supérieur à MinSup est qualifié de fréquent. Le problème est de trouver les ensembles fréquents de taille K (K-ensemble fréquent).

L’algorithme procède en deux étapes : recherche de K-ensembles fréquents (support>MinSup) puis construction des règles à partir des K-ensembles fréquents trouvés (une règle est retenue si et seulement si confiance >MinConf).

Ce travail est effectué en plusieurs passes : une première pour générer les 1-ensembles fréquents, dans la Kieme passe la génération des K-ensembles fréquents est faite à partir des (k-1)-ensembles fréquents en utilisant une procédure Apriori-Gen. Le processus s’arrête lorsque il est impossible de générer des ensembles fréquents de taille supérieure.

L1 ={1-itemsets fréquents}; for (k=2; Lk-1≠ φ; k++) do Ck =apriori_gen(Lk-1); forall instances t de T do Ct =subset(Ck,t);

forall candidats c de Ct do

c.count++;

Lk ={c de Ck / c.count ≥ MINSUP }

L=UiLi;

6. L’algorithme Apriori

{Jointure Lk-1*Lk-1;k-2 éléments communs}

insert into Ck;

select p.item1, p.item2,…, p.itemk-1, q.itemk-1 from Lk-1p, Lk-1q

where p.item1=q.item1,…, p.itemk-2=q.itemk-2,p.itemk-1< q.itemk-1 forall itemsets c de Ck do

forall (k-1)-itemsets s appartenant c do if s n’appartient pas a LK-1 then

delete c from Ck;

7. La procédure Apriori_gen.

L’algorithme à priori donne des résultats clairs et simples à interpréter, il peut être étendu par l‘introduction du temps dans les règles (un client ayant acheté un produit A est susceptible d’acheter le produit B dans deux ans), cependant il est coûteux en temps de calcul, c’est pourquoi d’autres améliorations à cet algorithme ont été proposées (Gardarin, 1999).

1.4.8 Autres techniques

La fouille de données est un domaine de recherche qui a suscité beaucoup de travaux, nous avons présenté sommairement les techniques les plus connus et implémentés dans les outils de fouille. Pour clôturer cette section, nous signalons que d’autres techniques et même plusieurs variantes des techniques présentées sont utilisées. Nous les citons sans les détailler. Il s’agit notamment des algorithmes génétiques introduits par Holland en 1975, des support vector machines (SVP) proposé par Vapnik en 1995 (Besse, 2005) et des ensembles approximatifs (Rough sets) (Grzymala-Busse, 2003).

1.5 Limites de la fouille de données et sujets ouverts

La fouille de données est un domaine de recherche pluridisciplinaire, englobant moult de spécialités, où il est question d’extraire à partir de gros volumes de données de l’information pertinente et utile pour l’utilisateur.

Une multitude d’algorithmes et de méthodes ont été proposés pour atteindre cet objectif. Cependant il faut dire que la fouille de données n’est pas le remède miracle à toutes les questions posées en analyse de l’information et de son exploitation dans le processus de prise de décision.

Les limitations de la fouille de données sont liées beaucoup plus aux personnels et aux données à traiter qu’à la technologie utilisée. Ainsi pour réussir un projet de fouille de données, il est nécessaire de disposer du personnel qualifié prenant à la fois la gestion et la structuration de l’analyse, puis, et du fait que la fouille de données ne donne pas l’intérêt des motifs extraits, l’interprétation des résultats obtenus.

D’un autre coté, et suivant (Seifert, 2004), même si la fouille de données est utilisée pour identifier des liaisons et des corrélations entre variables, il est incapable de montrer des relations de causes. Les autres inconvénients sont ceux liés au coût souvent élevé de la plupart des projets de fouille, aux difficultés de traitement des données bruitées ou erronées, et à la question de la protection et le partage des données personnelles.

Enfin, et en dépit des travaux réalisés dans ce domaine, le futur de la fouille de données reste promoteur et plusieurs sujets et directions de recherche demeurent ouverts (Zaïane, 1999),(Hsu, 2003). Il s’agit notamment des préoccupations ayant trait à :

•  l’amélioration des interfaces des outils de fouille de données, aussi bien dans le volet interrogation que celui de la présentation des résultats,
•  d’apporter des solutions aux limites des algorithmes actuels, spécialement en terme de complexité et de performances,
•  de veiller au respect du principe de protection des données privées dans les systèmes de fouille,
•  de concevoir de nouveaux environnements permettant la fouille de données dispersées géographiquement et/ou hétérogènes, et
•  d’investir de nouveaux types de données tels que : les données multimédia, les données spatiales, les séries temporelles, et récemment le Web. .