I.5 Les méthodes de fouille de
données
La fouille de données n'est ni un outil, ni une
technique, c'est plutôt une science encapsulant des méthodes dont
le but est d'extraire des connaissances à partir de données assez
structurées. Chaque méthode vise un objectif, i.e. une
tâche, qui n'est réalisable par une seule méthode, mais
plus tôt par un ensemble de méthodes complémentaires,
chacune choisie en fonction du domaine d'application, du type des
données à analyser, et du type des connaissances que nous voulons
extraire.
Une tâche correspond donc à l'objectif du
Data Miner, ainsi par exemple la classification d'objets, à partir de
plusieurs caractéristiques connues, est une tâche de fouille de
données. Les tâches peuvent être catégorisées
de plusieurs façons. D'ailleurs, il n'existe pas de taxonomie standard
dans la littérature. Fayyad et al divisent les tâches en deux
[Fayyad et al., 1996] : les tâches descriptives et les tâches
prédictives. D'autres, les divisent en méthodes symboliques et
numériques, supervisées ou non supervisées et par
renforcement. D'autres auteurs encore, divisent les tâches de fouille de
données en sept types [Goebel et Gruenland, 1999]: la prédiction,
la régression, la classification, le groupement, l'analyse de liens, les
modèles de visualisation et l'analyse exploratoire de
données.
Comme Il n'existe pas de taxonomie standard nous avons
donc choisi de décrire les trois approches qui reviennent souvent dans
la littérature et de présenter ensuite une catégorisation
la plus adaptée.
1ere approche (description,
prédiction)
Une distinction est faite selon l'objectif. On a alors
les méthodes descriptives (caractérisation, discrimination,
extraction de règles d'association, analyse de cas extrême) et les
méthodes prédictives (classification, groupement).
Chapitre I : L'extraction de connaissances
à partir de données biologiques -
21 - 2eme approche (symbolique,
numérique)
Une distinction est faite par type de données
traitées en entrée. Nous distinguons alors :
· les méthodes symboliques, notamment
l'extraction de motifs fréquents, l'extraction de règles
d'association, la classification par treillis, et la classification par arbres
de décision ;
· les méthodes numériques, en
particulier, les méthodes statistiques (classification automatique,
ACP), les modèles de Markov cachés d'ordre 1 et 2, les
méthodes neuronales, et les algorithmes
génétiques.
3eme approche (supervisé, non
supervisé, par renforcement)
L'apprentissage supervisé est basé sur
la construction d'un modèle où l'on considère un ensemble
de classes d'exemples de cas déjà traités, et on cherche
l'appartenance d'un objet à une classe en considérant les
similarités entre l'objet et les éléments de la classe.
Ces classes sont nommées préalablement. On essayera d'expliquer
et/ou de prévoir un ou plusieurs phénomènes observables et
effectivement mesurés.
L'apprentissage non supervisé utilise un
ensemble de données dans lequel aucune d'elles n'a d'importance
particulière par rapport aux autres, i.e. aucune n'est
considérée individuellement comme l'objectif de l'analyse. Cette
méthode permet la formation de groupes d'éléments
(clusters) homogènes partageant certaines similarités. Il n'y a
pas de classes à expliquer ou de valeur à prédire, la
méthode doit découvrir par elle-même les groupes
d'éléments. Il appartiendra ensuite à l'expert du domaine
de déterminer l'intérêt et la signification des groupes
constitués.
L'apprentissage par renforcement a pour but
d'apprendre à partir d'expériences acquises en différentes
situations, de façon à optimiser une récompense
numérique au cours du temps. Un exemple est de considérer un
agent autonome qui doit prendre des décisions en fonction de son
état courant. En retour, l'environnement récompense l'agent en
positif ou négatif. L'agent cherche un comportement décisionnel
(stratégie ou politique) optimal pour maximiser la somme des
récompenses au cours du temps.
Pour notre étude, nous avons donc choisi la
catégorisation citée dans l'article de Larose [Larose, 2005] et
nous avons fait une étude comparative sur cette base, car nous pensons
que relativement à celles qui existent dans la littérature c'est
la plus utilisée. Nous avons alors les tâches suivantes
:
Chapitre I : L'extraction de connaissances
à partir de données biologiques -
22 -
(1) La description
La description explore les données sans
forcément chercher à prouver une hypothèse ou
répondre à une question. L'objectif est de décrire les
données ou donner des résumés sur celles-ci. On utilise
pour cela, les outils d'analyse exploratoire de données (EAD) qui sont
interactifs et visuels et s'appuient sur des méthodes graphiques. Viens
ensuite, le Data Miner qui interprétera les modèles
déduits.
(2) L'estimation
Elle consiste à estimer la valeur d'un champ
à partir des caractéristiques d'un objet. Le champ à
estimer est un champ à valeurs continues. Contrairement à la
classification, le résultat d'une estimation permet d'obtenir une valeur
pour une variable continue. Par exemple, on peut estimer le revenu d'un
ménage selon divers critères (type de véhicule,
profession, type d'habitation, etc.), il sera ensuite possible de
définir des tranches de revenus pour classifier les individus. Un
intérêt de l'estimation est de pouvoir ordonner les
résultats pour ne retenir, si on le désire, que les n meilleures
valeurs.
(3) La prédiction
Elle consiste à estimer la valeur future d'un
champ à partir des caractéristiques d'un objet. Cela revient
à prédire la valeur d'une variable à partir d'autres
variables, dont on connaît les valeurs, appelées variables
prédictrices. Dans ce cas, la construction des modèles se fait
grâce à l'apprentissage à partir d'anciens cas
(données dont on connaît les valeurs de la variable à
prédire). Chaque modèle construit est accompagné par une
valeur d'une fonction score indiquant son taux d'erreur (ou son taux
d'exactitude).
(4) La classification
Elle consiste à examiner les
caractéristiques d'un élément qui se présente afin
de l'affecter à une classe prédéfinie ou connue à
l'avance, celle-ci est un champ particulier à valeurs discrètes.
L'utilisation de la classification se fait depuis déjà bien
longtemps pour comprendre notre vision du monde (espèces animales,
minérales ou végétales). Elle permet de repartir en
classes des objets ou individus. Ces classes sont discrètes :
homme/femme/bleu/blanc, etc. Un exemple de classification est l'attribution
d'un sujet principal à un article de presse.
Dans un cadre informatique, les objets ou
éléments sont représentés par un enregistrement et
le résultat de la classification viendra alimenter un champ. Il est
souvent utilisé les méthodes suivantes : la méthode K-ppv
(plus proche voisin), les arbres de décision, et les réseaux de
neurones.
Chapitre I : L'extraction de connaissances
à partir de données biologiques -
23 -
(5) Le groupement
Pour cette tâche, il n'y a pas de classe
à expliquer ou de valeur à prédire définie à
priori, il s'agit de créer des groupes d'objets homogènes dans la
population, ayant les mêmes caractéristiques.
(6) La recherche d'association
Elle consiste à trouver des corrélations
ou relations entre attributs (items). La recherche de liens associatifs est
utilisée intensivement dans les bases transactionnelles. Il s'agit de
découvrir les items les plus fréquemment en relation. Un exemple,
est la détermination des articles (cahier et stylo bleu, riz et oeufs,
...) qui se vendent ensemble dans un supermarché.
Ainsi, pour réaliser l'une ou l'autre des
tâches précitées, on utilise une ou plusieurs
méthodes et elles sont nombreuses. Il est difficile de les
présenter toutes. Ceci dit, celles qui sont présentées
ci-dessous sont tout de même les plus importantes. Il faut noter qu'il
n'y a pas de méthode meilleure, chacune présente des avantages et
des inconvénients.
(1) Les méthodes de
visualisation
Elles permettent la visualisation des données
et donc l'analyse l'exploratoire avec comme objectif le dégagement de
motifs, de structures, de synthèses, etc. Elles sont basées sur
des graphiques qui facilitent l'interprétation des résultats.
Dans le premier type de visualisation, l'utilisateur ne connaît pas
forcément ce qu'il cherche dans les données, il essaye de
chercher des modèles, des motifs, ou plus généralement des
hypothèses qu'il veut démontrer. Au deuxième type de
visualisation, l'utilisateur a une hypothèse qu'il veut tester et
confirmer. Ce type de visualisation est dérivé directement des
statistiques, et ne convient pas vraiment au principe même de la fouille
de données (bien qu'il en fasse partie). Les méthodes les plus
utilisées sont : les graphiques de statistiques
élémentaires (moyenne, écart type, variance), les
histogrammes, les nuages de points, et les courbes.
(2) Les réseaux de neurones
Un réseau neuronal est composé de
groupes de noeuds (neurones) où chaque groupe de noeuds correspond
à une couche. Il est formé par au moins trois couches : input,
intermédiaire et output. Dans la couche input, chaque noeud correspond
à une variable prédictrice. La couche output contient un ou
plusieurs noeuds et les variables à prédire.
Chapitre I : L'extraction de connaissances
à partir de données biologiques -
24 -
Le réseau peut avoir plusieurs couches
intermédiaires (mais un seul input et un seul output), appelées
aussi couches cachées. Chaque noeud de la couche j est relié
à tous les noeuds de la couche j+1. A chaque arc est associé un
poids (une valeur) Wij, c'est le poids de l'arc entre le noeud i et le noeud j.
Les valeurs input des noeuds de la première couche sont les valeurs des
variables prédictrices. Les valeurs internes des autres noeuds (des
couches intermédiaires et de la couche output) sont calculées
à travers une fonction de sommation.
Les réseaux de neurones sont des outils
très utilisés pour la classification, l'estimation, la
prédiction et le groupement. Ils permettent de construire un
modèle qui prédit la valeur d'une variable à partir
d'autres variables connues appelées variables prédictrices. Si la
variable à prédire est discrète (qualitative) alors il
s'agit d'une classification, si elle est continue (quantitative) il s'agit
alors de régression. Les méthodes les plus utilisés sont :
le Perceptron multicouches et les réseaux de Kohonen.
(3) Les arbres de décision
Un arbre de décision est une
représentation graphique d'une procédure de classification. Les
noeuds internes de l'arbre sont des tests sur les champs ou attributs, et les
feuilles sont les classes. Lorsque les tests sont binaires, le fils gauche
correspond à une réponse positive au test et le fils droit
à une réponse négative.
Un arbre de décision cible la classification
i.e. la prédiction de variables discrètes. La méthode
consiste à construire un arbre et pour chaque élément
qu'on veut classifier, il entre par le noeud racine et passe d'un noeud
père à un noeud fils, s'il satisfait une condition posée.
Le noeud feuille auquel il arrivera est sa classe. Un arbre de décision
peut donc être perçu comme étant un ensemble de
règles qui mènent à une classe. La construction de l'arbre
se fait par un algorithme approprié. Les algorithmes les plus
utilisés sont : ID3, CHAID, CART, QUEST, et C5 [Quinlan, 1986],
[Wilkinson, 1992], [Gaussier, 2009], [Quinlan, 1993], [Denison et al., 1998],
[Callas, 2009].
(4) SVM (machines à vecteur de
support)
Les machines à vecteurs de support sont une
classe d'algorithmes d'apprentissage initialement définis pour la
discrimination i.e. la prévision d'une variable qualitative initialement
binaire. Elles ont été ensuite généralisées
à la prévision d'une variable quantitative. Dans le cas de la
discrimination d'une variable dichotomique, ils sont basés sur la
recherche de l'hyperplan de marge optimale qui, lorsque c'est possible, classe
correctement les données tout en étant le plus
éloigné possible de toutes les
Chapitre I : L'extraction de connaissances
à partir de données biologiques -
25 -
observations. Le principe est donc de trouver une
fonction de discrimination, dont la capacité de
généralisation (qualité de prévision) est la plus
grande possible. Donc les SVM peuvent être utilisés pour
résoudre des problèmes de discrimination (i.e. décider
à quelle classe appartient un échantillon), ou de
régression (i.e. prédire la valeur numérique d'une
variable).
(5) K - plus proches voisins
(K-ppv)
La méthode des K plus proches voisins (K-ppv,
nearest neighbor ou K-nn) est une méthode dédiée à
la classification qui peut être étendue à des tâches
d'estimations. La méthode K-ppv est une méthode de raisonnement
à partir de cas. Elle part de l'idée de prendre des
décisions en recherchant un ou des cas similaires déjà
résolus en mémoire. Elle décide de la classe à
laquelle appartient un nouveau cas, en examinant les k cas qui lui sont les
plus similaires ou proches. Il n'y a pas d'étape d'apprentissage
consistant en la construction d'un modèle à partir d'un
échantillon d'apprentissage. C'est l'échantillon d'apprentissage
qui constitue le modèle. On lui associe une fonction de distance et une
fonction de choix de la classe en fonction des classes des voisins les plus
proches.
(6) Les réseaux
bayésiens
Un réseau bayésien ou probabilistique
est un graphe dirigé, acyclique où chaque noeud représente
une variable continue ou discrète, et chaque arc représente une
dépendance probabilistique. Si un arc relie un noeud Y à un noeud
Z, alors Y est le parent de Z et Z est le descendant de Y. Chaque variable est
indépendante des variables auxquelles elle n'est pas reliée. Les
variables peuvent être continues ou discrètes. Chaque lien entre
deux variables est pondéré par la valeur de la dépendance
probabilistique, ainsi la valeur que porte l'arc reliant Y à Z est en
fait P (Z/Y).
(7) Induction de règles
C'est une technique qui permet d'identifier des
profils, associations ou structures entre les items ou objets qui sont
fréquents dans les bases de données. Autrement dit, il s'agit
d'identifier les items qui apparaissent souvent ensemble lors d'un
évènement. Cette règle d'association est une règle
de la forme : « Si X et Y alors Z », règle dont la
sémantique peu être énoncée : « Si X et Y
apparaissent simultanément alors Z apparait ». Pour
considérer et exprimer cette association sous forme d'une règle,
il faut définir des quantités numériques qui vont servir
à valider son intérêt, d'où : le support et la
confiance.
Le support est la fréquence d'apparition
simultanée des éléments qui apparaissent
Chapitre I : L'extraction de connaissances
à partir de données biologiques -
26 -
dans la condition et dans le résultat, soit :
support=fréquence (condition et résultat), et la
confiance=fréquence (condition et résultat) / fréquence
(condition). Ainsi, les règles dont le support et la confiance sont
assez élevés sont alors privilégiées. Les
algorithmes les plus utilisés sont : Apriori, AIS, FP-Growth [Agrawal et
al., 1993],[Agrawal et Srikant., 1994], [Han et al., 2000].
(8) Les techniques de groupement
Ces techniques ou méthodes visent la
description des données. Elles consistent à diviser les
données en groupes de manière à ce que les données
d'un même groupe soient similaires et les données de deux groupes
différents soient différentes. Le degré de ressemblance
entre les données est calculé par une méthode de
similitude. Les méthodes de groupement se divisent en deux types : le
groupement basé sur les partitions et le groupement hiérarchique.
La technique la plus connue du premier type est la méthode des
K-moyenne. Elle consiste à diviser les données en K groupes, K
étant donné par l'utilisateur. Cette méthode commence par
un groupement aléatoire des données (en K groupes), ensuite
chaque enregistrement est affecté au plus proche groupe. Après
l'exécution de la première itération, les moyennes des
groupes sont calculées et le processus est répété
jusqu'à stabilisation des groupes. L'algorithme le plus utilisé
est : K-moyenne.
(9) Les modèles de Markov
cachés
Les modèles de Markov cachés d'ordre 1
ou 2 (HMM1 et HMM2 pour Hidden Markov Models) sont utilisés pour la
classification des différentes données temporelles ou spatiales.
Contrairement aux algorithmes classiques qui fournissent une réponse
exacte, les HMMs permettent un apprentissage automatique, ils interviennent par
exemple dans de nombreux algorithmes d'analyse de séquences biologiques
que ce soit pour, la détection de gènes, l'inférence et la
détection de motifs, ou encore la recherche de mots exceptionnels. En
effet, pour toutes ces opérations sur les séquences biologiques,
il est tenu compte des caractéristiques propres de la séquence,
de la position d'une sous séquence i.e. des caractéristiques de
ses voisins temporels ou spatiaux.
(10) Les treillis
Les treillis de concepts formels (ou treillis de
Galois) sont une structure mathématique permettant de représenter
les classes non disjointes sous-jacentes à un ensemble d'objets
(exemples, instances, t-uples ou observations) décrits à partir
d'un
Chapitre I : L'extraction de connaissances
à partir de données biologiques -
27 -
ensemble d'attributs. Ces classes non disjointes sont
aussi appelées concepts formels. Une classe matérialise un
concept. Ce concept peut être défini formellement par une
extension (exemples du concept) ou par une intension (abstraction du concept).
Les treillis sont utilisés en classification.
(11) Autres méthodes
La régression linéaire
(méthode statistique)
C'est une technique qui vise la prédiction de
la valeur d'une variable continue. Son objectif est de définir le
meilleur modèle qui associe une variable quantitative « output
» à plusieurs variables prédictrices « input ».
Cette opération s'appelle ajustement du modèle aux
données. Les modèles linéaires sont les plus
fréquemment utilisés. C'est ce qu'on appelle la régression
linéaire. La relation qui relie une variable à prédire
Y à p autres variables prédictrices est une
équation de régression souvent sous cette forme : Y = a0 + a1
X1 + a2 X2 + ... + ap Xp
Les méthodes les plus utilisés sont :
régression simple, régression multiple.
Les algorithmes
génétiques
Les algorithmes génétiques ne
constituent pas une méthode de fouille de données à part
entière et ne ciblent directement aucune tâche. Ils viennent aider
le processus de fouille de données. Ce sont des heuristiques qui guident
la recherche de bons modèles dans un espace de recherche très
vaste. Les algorithmes génétiques se basent sur les principes de
sélection, enjambement, et mutation qui sont des notions issues de la
génétique.
| 
