Upload
trancong
View
225
Download
0
Embed Size (px)
Citation preview
Techniques de fouille de données en chimie
>
Philippe JAUFFRETLaboratoire des Systèmes d ’Information ChimiqueUMR 5076 du CNRS - Montpellier<[email protected]>
04/01/2003 2
Sommaire
QUITTER><
• Introduction - définitions
• Fonctions d ’un système de fouille de données
• Fouille de données et OLAP
• Prétraitement des données
• Association
• Classification
04/01/2003 3
Fouille de données1)
De quoi on parle et pourquoi on en parle ?
04/01/2003 4
Explosion du volume des données : CA
QUITTER><
1900 2000
500K
1M35 M substances cataloguées5,6 M de réactions (CASREACT)
Nb documents/an
04/01/2003 5
Pourquoi fouiller les données ?
QUITTER><
Nature, 10 juin 1999
De nouvelles techniques doiventêtre élaborées pour transformerles données en connaissances
04/01/2003 6
Pourquoi fouiller les données ?
QUITTER><
« To understand is to perceive patterns. »(Sir Isaiah Berlin)
04/01/2003 7
Pourquoi fouiller les données ?
« Most researchers are accustomed to studying a relatively small data set for a long time, using statistical models to tease out patterns. At some fundamental level that paradigmhas broken down »
(Kihn)
QUITTER><
04/01/2003 8
Pourquoi fouiller les données ?
La fouille de données apparaîtcomme une évolution naturelle destechnologies de bases de données.
QUITTER><
04/01/2003 9
Une définition…parmi tant d ’autres
« Data mining is the process of discovering meaningfull new correlations, pattern andtrends by sifting through large amounts of data stored in repositories, using pattern recognition technologies as well as statistical and mathematical techniques »
(Gartner Group)
QUITTER><
04/01/2003 10
Fouille de données:interdisciplinarité ?
QUITTER><
La fouille de données fait appel a demultiples compétences :
- bases de données- statistiques- théorie de l ’information- apprentissage automatisé- visualisation- connaissance du domaine
d ’application (chimie)
04/01/2003 11
Extraction de Connaissances à partir de Bases de Données
« Knowledge Discovery in Databases is the process of extracting previously unknown, valid, and actionable information from large databases »
(Cabena 98)
QUITTER><
04/01/2003 12
La fouille de données est une étape de l ’ECBD (I)
QUITTER><
Sélection donnéesciblées
Préparation des données Echantillon
Fouille de données
ModèlesMotifs
Vérification, Evaluation
Bases dedonnées brutes
L ’ECBD est un processus- itératif- interactif
04/01/2003 13
La fouille de données est une étape de l ’ECBD (II)
QUITTER><
• fixer les objectifscomprendre le domaine d ’application, et ce qu ’on veut apprendre
• sélectionner l ’échantillonacquisition et intégration
• nettoyer et transformer les donnéesbruit, champs manquants, données aberrantes,…réduction de la dimension, choix de représentation,...
• fouille des donnéeschoix de la méthode adaptée aux objectifs
• vérification et consolidation• utilisation...
04/01/2003 14
Fouille de données et apprentissage automatisé
QUITTER><
DM ML
domaine
méthodes
Seulement desexemples « positifs »
Exemples positifs:généralisation
Exemples négatifs:spécialisation
Généralisationattribut par attribut
Généralisation globale (par nupletsd ’attributs)
04/01/2003 15
une terminologie souvent confuse...
• Lexique pour le Data Mining :http://www.twocrows.com/glossary.htm
• Lexique pour l ’apprentissage automatisé :
http://robotics.stanford.edu/~ronnyk/glossary.html
QUITTER><
04/01/2003 16
2)Fonctions d ’un système
de Fouille de données
04/01/2003 17
Conceptualisation/Classification
QUITTER><
généraliser des données et les abstraire. Identifier des descripteurs (modèles)permettant de distinguer des classesd ’objets et de décrire des concepts
( Comment établir des classes de solvants utilisables pour la généralisation d ’exemplesde réactions?)
04/01/2003 18
Prédiction
QUITTER><
prévoir ou estimer la valeur d ’un attribut.
(estimer le rendement d ’une réaction ou la faisabilitéd ’un chemin de synthèse non encore expérimentépar l ’analyse d ’expériences préalables analogues)
04/01/2003 19
Association
QUITTER><
Identifier des corrélations ou des liensde causes à effet
( pour procéder à la réduction d ’un ester, on utilise souvent NiAlH4 comme réactif; quels groupements protecteurs utiliser dans uncontexte donné ?; etc.)
04/01/2003 20
Regroupement (cluster)
QUITTER><
regrouper un ensemble d ’objets endifférentes classes, de façon à mettre enévidence une similarité à l ’intérieur desclasses et les différences inter-classes
(Etant donné un ensemble de réactions, est-ilpossible d ’identifier des intervalles de températuresfréquemment utilisées ?)
04/01/2003 21
Détection des points aberrants
QUITTER><
(une donnée dont un attribut aumoins à une valeur très éloignée decelles des autres données)
Une telle donnée peut provenir d ’uneerreur d ’acquisition; elle peut aussirévéler une exception utile...
04/01/2003 22
Fonctions multiples
QUITTER><
Utilisation de plusieurs fonctions de fouille simultanément ou succes-sivement
dans GRAMS, le regroupement (selon le rendement)est utilisé pour définir un « seuil de pertinence »Ce seuil est utilisé à son tour pour optimiser laconstruction des réseaux de schémas réactionnels,par généralisation/classification.
04/01/2003 23
Mesures d ’intérêt
QUITTER><
Un processus de fouille de données est une « boîte noire » qui peut déceler de très nombreux motifs ou« connaissances » dans les données fournies.Il faut filtrer les connaissances apprises.
Une connaissance apprise automatiquement estintéressante si elle est :- facile à comprendre par les utilisateurs- originale ou inattendue- potentiellement utile- fiable sur un échantillon représentatif
04/01/2003 24
Types de méthodes
QUITTER><
Méthodes prédictives :prédire la valeur de certains attributs en fonction d ’autres attributs
Méthodes descriptives :découvrir des « motifs » permettant de comprendre l ’organisation desdonnées
04/01/2003 25
3)Fouille de données
et OLAP
04/01/2003 26
Outils en ligne de traitementanalytique des données
QUITTER><
(un peu hors-sujet ici, mais faut pas mourir idiot…)
OLAP: On-Line Analytical Processing
s ’appliquent plutôt à des « entrepotsde données »
(vs OLTP: On-Line Transaction Processingsur les BD relationelles)
04/01/2003 27
Qu ’est-ce c ’est qu ’un« entrepôt de données » ?
QUITTER><
(ou Data Warehouse )• Une base de données décisionnelle(vs transactionnelle),pouvant intégrerplusieurs bases de données opérationnelles. • Pas d ’accès répétitifs mais desrequêtes souvent très complexes.• Typiquement, les données sont desdonnées historiques ou consolidées(vs données courantes, opérationnelles)
04/01/2003 28
Modélisation desentrepôt de données
QUITTER><
comme pour les BD, modèles relationnelsen forme d ’étoiles, de flocons de neige ou deconstellation :
REACTION
Reaction_idCreateur_id
GCR_idCondition_idSolvant_id
Catalyseur_idrdt_sup, inf
ReacteurCommentaires
Catalyseur
Catalyseur_idMolecule_id
Nb_molecules
Condition
Condition_idAtmosphère
pH_min, maxTemp_min, max
Temp_variaDurée_min, max
DiversReflux Solvant
Solvant_idMolecule_id
Nb_molecules
GCR
GCR_idCreateur_idtopo_GCRform_GCR
04/01/2003 29
Outil typique de visualisation/décision: le cube de données
QUITTER><
Description de systèmes polycycliques
04/01/2003 30
QUITTER><
• projeter en 2 dimensions
• pivoter le cube
• utiliser une hiérarchie conceptuellepour obtenir des informations plusrésumées (« roll up ») ou pour augmenterle niveau de détails(« drill down »)
Principales fonctionssur les cubes OLAP
04/01/2003 31
QUITTER><
• Limitée aux variables de type numériqueou catégoriel (mois de l ’année, pays, etc.)
• Bien adapté au domaine de l ’entreprise(comptabilité, gestion, …)
Limitation destechniques OLAP
04/01/2003 32
4)prétraitement des
données
04/01/2003 33
Architecture d ’un système defouille de données
QUITTER><
Procédures de prétraitement
Moteur de fouille de données
Procédures d’évaluation
Base deconnaissances
Base de données
04/01/2003 34
0
10
20
30
40
50
60
70
80
90
100
Choix desobjectifs
Prétraitement Fouille dedonnées
Analyse desrésultatsEvaluation
D ’après: Bhattacharyya University of Illinois at Chicago
Coût du prétraitement dansle processus d ’EBCD
QUITTER><
04/01/2003 35
Critères de qualité des données
QUITTER><
• consistance• complétude• précision• homogénéïté• accessibilité• interprétabilité, ...
La qualité de l ’apprentissage dépend de la qualité des données
04/01/2003 36
Les étapes du prétraitement
QUITTER><
• le « nettoyage » des donnéescomplètement des données manquantes,élimination des points aberrants, lissage,élimination des doublons,...
• l ’intégrationfusion de diverses sources de données
• les transformationschoix de représentations (interfaces), mises à
l ’échelle, normalisation, etc.
04/01/2003 37
QUITTER><
• Incomplétude des données :données non disponibles lors de l’acquisitiondonnées non pertinentes dans le contexte de la BD.
• bruit ou erreurs :protocole d’acquisition impréciserreurs de saisie
• Inconsistance :hétérogénéïté des sources de donnéeserreurs de saisie
Les causes d ’erreurs ?
04/01/2003 38
QUITTER><
• Elimination des données incomplètes
• Complètement automatique (valeur par défaut, valeur moyenne, procédure ad-hoc)
• Complètement manuel
Traitement des données manquantes
04/01/2003 39
Complètement des données manquantes : valeur par défaut
QUITTER><
dans les BD de réactions, la pression est souvent omise dans la description des conditions réactionnelles :
--> on peut généralement compléter par « pression normale »
04/01/2003 40
Complètement des données manquantes: procédure ad-hoc
QUITTER><
O
P
NO
O
O
+ +
N
O
27%
toluènereflux
PO+
Compléter la relation d’appariement atomique Ajout des réactants et des produits implicites
P
NO
O
O NO
O
+27%
toluènereflux
04/01/2003 41
QUITTER><
• Protocole de saisieDans les bases ISIS (MDL), le champs « rendement » indique parfois les rendements extrêmes de plusieurs exemples.
• Modélisation du domainecatalyseurs/réactifs, réactions mono/multi-étapes
• AlgorithmesDans les bases ISIS (MDL), la procédure d ’appariement des atomes est automatisée. On a relevé de nombreux exemples d ’appariements faux (notamment dans les cas de réarrangement)
Origine des bruits dans les BD
04/01/2003 42
QUITTER><
• détection des données « suspectes »
- tri et partitions- régressions- regroupements (clustering)
• traitement- élimination- lissage- interactif
Traitement des données bruitées
04/01/2003 43
QUITTER><
toutes les données nécessaires à la fouille ne sont pas nécessairement présentes dans un seul lieu.
applications en structure/activitédonnées physico-chimiques Beilstein+ données structurales CSD
Intégration des données : pourquoi ?
04/01/2003 44
QUITTER><
jonction : une même entité peut ne pas avoir le même nom dans deux sources de données
homogénéïté : unités de mesures, échelles,...
Intégration des données : difficultés
04/01/2003 45
QUITTER><
• Pas de fouille sans modèle du domaine (ontologie, schéma conceptuel).
• Une représentation adaptée conditionne l ’efficacité du système
• réduction des attributs : optimisationdu processus de fouille
Transformation des données :modèle et représentation
04/01/2003 46
QUITTER><
normalisation gaussienne :
V - Vσv
V’ =Moyenne =0Ecart-type =1
normalisation min-max, par échelle décimale, etc.
Transformation des données :normalisation
04/01/2003 47
QUITTER><
• méthodes paramétriquesPartant d ’un modèle donné, ne
retenir que les attributs reconnus comme pertinents (PCA, régression, etc.)• méthodes non-paramétriques
Pas d ’hypothèses sur les modèles (histogrammes, regroupements, etc.)
Réduction du nombre d ’attributs
04/01/2003 48
QUITTER><
• Les données étant initialement dans un espace de dimension N, trouver un espace de dimension N’ <N (chaque vecteur directeur est une combinaison linéaire des vecteurs initiaux) tel que la perte d ’information soit minimale
• ne fonctionne qu ’avec des attributs de type numérique• perte potentielle d ’interprétabilité
Analyse par Composantes Principales
04/01/2003 49
QUITTER><
• identifier une droite modélisant le comportement global de données bi-dimensionnelles
y = ax + bles coefficients a et b sont généralement déterminés par la méthode des moindres carrés.
• ne fonctionne qu ’avec des attributs de type numérique
Analyse par régression linéaire (I)
04/01/2003 50
QUITTER><
xx
xx
x
xx
xx
xx
x
xx
xx x
x
Ancien X
Ancien Y Nouvel attribut
Analyse par régression linéaire (II)
04/01/2003 51
QUITTER><
• généralisation de la régression linéaire.Cette fois-ci, y dépend de plusieurs autres variables :
y = a0 + a1x1 + a2x2 + ...
• ne fonctionne qu ’avec des attributs de type numérique
Analyse par régression multi-linéaire
04/01/2003 52
QUITTER><
• partitionner un espace continu en intervalles. La valeur de l ’attribut devient le numéro de l ’intervalle.
Pb potentiel de pertinence aux frontières
discrétisation
04/01/2003 53
QUITTER><
• partitionner un ensemble de valeurs en classes. La valeur de l ’attribut devient le descripteur de la classe.
Ne s ’applique pas aux variables uniformément réparties ou globalement trop proches.
Regroupement (clustering)
04/01/2003 54
QUITTER><
• si une hiérarchie de concepts est disponible pour un attribut, on peut réduire la complexité de la représentation en remplacant une donnée de bas niveau par un concept de plus haut niveau
ex: remplacer la température (numérique) d ’une réaction par l’une des valeurs: {très froid, froid, tempéré, chaud, très chaud}
Hiérarchie de concepts
04/01/2003 55
QUITTER><
Il ne s ’agit plus de réduire le nombre d ’attributs (la description) mais le nombre de données.La difficulté est de sélectionner un sous-ensemble représentatif de l’ensemble des données. Cela ne peut généralement se faire que si l ’on connaît une partition en classes (l’échantillon doit respecter le pourcentage de chaque classe)
Echantillonage
04/01/2003 56
5)association
04/01/2003 57
QUITTER><
• Objectif :établir des associations (corrélations ou relations de causes à effets) entredes données.
• une des fonctions majeures de lafouille de données (très nombreusesapplications…)
ASSOCIATION
04/01/2003 58
QUITTER><
Comment organiser au mieux les rayons d’un grand magasin ? (en fonction des corrélations observéesdans les factures des clients)
Comment composer un catalogue de façon à ce que sa consultation soit « naturelle » ?
Mais aussi : quel est le meilleur solvant (le plus utilisé)pour un type de réactions donné ? Peut-on corréler laprésence d ’un fragment moléculaire et l ’observation depropriétés physico-chimiques ? Etc.
Associations: quelques exemples
04/01/2003 59
QUITTER><
L ’affirmation « A⇒B » est-elle utile et fiable ?(A et B étant des prédicats sur les données)
• support: p(A∧B)• confiance: p(B|A) = p(A ∧ B)/p(A)
Ss-populationVérifiant A
« A⇒B » est une associationpertinente si et seulement sison support et sa confiancesont supérieurs à desseuils donnés (minsup et minconf)
Mesures classiques d ’intérêtdes règles d ’association
Ss-populationVérifiant B
04/01/2003 60
QUITTER><
Idée: un seul indicateur de l’intérêt d’une règle
Conviction(A ⇒ B) = p(A)*p(¬ B)/p(A ∧ ¬B)(« est-ce que A est peu présent sans B » ?)
• Varie entre 1 (si A et B sont indépendants) et +∞ (si A ⇒ B)• Plus la conviction est forte, « meilleure » est la règle
• Moins utilisée que support/confiance, parce que d’interprétation moins intuitive •Repose sur l’équivalence entre :
A⇒B ¬A∨B ¬ (A∧ ¬ B)
Mesure moins utilisée : la conviction
04/01/2003 61
QUITTER><
Mesures subjectives :
• utilité : peut-on exploiter cetteassociation ?
• caractère inattendu ...
Autres mesures d ’intérêtdes règles d ’association
04/01/2003 62
QUITTER><
Règles d ’associationet motifs fréquents
Chaque individu de la population peut contenir des motifs de bases prédéfinis : I1, I2, …, In
On cherche à établir des règles d’association du type
{Ij1, …, Ijk} ⇒ {Il1, …,Ilm }
C’est à dire « si un individu contient les motifs Ij1, …, Ijk , alors il contient aussi Il1, …,Ilm , avec une bonne probabilité »
Exemple : Population = factures d’un hypermarchéRègle: {choucroute} ⇒ {knacks, waedele, riesling}
04/01/2003 63
QUITTER><
Evaluation des règles basées sur les motifs fréquents
Support (A,B ⇒ C,D,E) = % des individus contenant A,B,C,D,E
K-motif fréquent :support (I1, I2, …, Ik ) ≥ minsup
Confiance (A,B ⇒ C,D,E) = p(C,D,E | A,B)
04/01/2003 64
QUITTER><
principe: pour qu ’un motif (A,B)soit un motif fréquent dans les données, il faut que A et B soient eux-mêmesdes motifs fréquents.
pour qu’un motif (A,B,C)soit fréquent, il faut que (A,B), (A,C), et (B,C)soient des motifs fréquents.
Rechercher tous les motifs fréquents ?
04/01/2003 65
QUITTER><
Soit M1 l ’ensemble des motifs fréquents observésdans les données (support > seuil); i ← 1M ← M1tant que Mi ≠ ∅
Ci+1 ← ensemble des motifs de « taille » i+1engendrés à partir de MiMi+1 ← restriction de Ci+1 aux motifs fréquentsM ← M ∪ Mii ← i+1
fin tant queretourner (M)
Algorithme « a priori »
04/01/2003 66
QUITTER><
• La taille des ensembles de candidatscroît exponentiellement avec la tailledes motifs
• Exploration itérative de l ’ensemble des données
Problèmes de l ’algorithme« a priori »
04/01/2003 67
QUITTER><
exploration « en profondeur d ’abord »de l ’arbre des motifs fréquents
→ convergence (beaucoup) plus rapidevers les « grands » motifs fréquents
optimisations de l ’algorithme« a priori » (I)
04/01/2003 68
QUITTER><
Utilisation de contextes pour limiter lagénération des candidats
→ permet l ’élagage de l ’arbre decroissance des motifs.
optimisations de l ’algorithme« a priori » (II)
04/01/2003 69
QUITTER><
R : A ⇒ B,CR’: A,B ⇒ C
Ces 2 règles ont même support.Si conf(R) > minconf, alors R est valide et R’ est redondante
De manière générale, il suffit de considérer les plus grands k-ensembles fréquents, et d’en extraire les règles de condition minimale, si elles existent. Sinon, il faut analyser les sous-ensembles.
Elimination des règles redondantes
04/01/2003 70
QUITTER><
1) discrétiser les valeurs numériquesen ensembles d ’intervalles(techniques de regroupement)
2) considérer les prédicats :« x est dans l ’intervalle numéro i »
Associations de valeurs numériques
04/01/2003 71
6)classification
04/01/2003 72
Classification : objectif
• Établir un modèle ( arbre de décision, jeu de règles, formule, …) permettant de ranger des données dans une des catégories préalablement définies.
QUITTER><
04/01/2003 73Classification etapprentissage supervisé• Lors d ’un processus de classification,
l ’apprentissage est supervisé : les classes sont connues a priori, et chaque donnée de l ’échantillon d ’apprentissage est assortie d ’un label indiquant la classe à laquelle appartient cette donnée.
• S ’oppose au « clustering » qui met en jeu un apprentissage non supervisé où le but du jeu est de découvrir une classification pertinente
QUITTER><
04/01/2003 74
Techniques de classification
• Classification bayesienne
• arbres de décision
• k-plus proches voisins
• autres méthodes
QUITTER><
04/01/2003 75
Classification bayesienne
• Méthode probabiliste fondée sur le théorème de Bayes
• Largement utilisée lorsque les attributs décrivant les données sont indépendants, ou lorsque leur inter-relations sont bien connues
• Coûteuse, car nécessitant le calcul de nombreuses probabilités
QUITTER><
04/01/2003 76
Théorème de Bayes
• On cherche à savoir pour quelle classe Ci la probabilité que X soit classé dans Ci est la meilleure : P(Ci|X) . Pour calculer cette probabilité, on utilise le théorème de Bayes:
P(Ci|X) = P(X|Ci) * P(Ci) / P(X)
• P(Ci|X) : probabilité « a posteriori » de classer X dans Ci (ce que l ’on cherche à maximiser sur l ’ensemble des classes Ci)
• P(X|Ci) : probabilité « a priori » de X sachant Ci (à évaluer d ’après l ’échantillon d ’apprentissage)
• P(Ci) : fréquence de la classe Ci sur l ’échantillon d ’apprentissage
• P(X) : indépendant des classes Ci
QUITTER><
04/01/2003 77
Approche naïve
• Le problème revient donc à évaluer P(X|Ci) sur l ’échantillon d ’apprentissage
• Si l ’on suppose que tous les attributs xj de X sont indépendants, on a :
• P(X|Ci) = P(x1,x2,…xn|Ci) = P(x1|Ci)*P(x2|Ci)*…*P(xn|Ci)
• dans le cas d ’attributs catégoriels, P(xj|Ci) peut être estimée par la fréquence des individus ayant xj comme valeur du jième
attribut.• Dans le cas d ’attributs continus, P(x1|Ci) est estimée par une
Gaussienne.
QUITTER><
04/01/2003 78
Un exemple classique :le match de tennis aura-t-il lieu ?
Données disponibles
P(fort| oui) = 3/5P(fort|non) = 3/9P(faible| oui) = 2/5P(faible|non) = 6/9
P(élevée| oui) = 4/5P(élevée|non) = 3/9P(normale| oui) = 2/5P(normale|non) = 6/9
P(chaud| oui) = 2/5P(chaud|non) = 2/9P(doux| oui) = 2/5P(doux|non) = 4/9P(froid| oui) = 1/5P(froid|non) = 3/9
P(pluvieux| oui) = 2/5P(pluvieux|non) = 3/9P(couvert| oui) = 0P(couvert|non) = 4/9P(soleil|oui) = 3/5P(soleil|non) = 2/9
vent
humidité
température
ciel
D ’après T. Mitchell « Machine Learning » McGraw Hill, 1997.
Probabiblités a priori
P(« oui ») = 5/14 P(« non ») = 9/14
ciel temperature humidité vent matchsoleil chaud élevée faible ouisoleil chaud élevée fort ouicouvert chaud élevée faible nonpluvieux doux élevée faible nonpluvieux froid normale faible nonpluvieux froid normale fort ouicouvert froid normale fort nonsoleil doux élevée faible ouisoleil froid normale faible nonpluvieux doux normale faible nonsoleil doux normale fort noncouvert doux élevée fort noncouvert chaud normale faible nonpluvieux doux élevée fort oui
QUITTER><
04/01/2003 79
Un exemple classique :le match de tennis aura-t-il lieu ?
Probabiblités a priori À partir de ces probabilités,on peut décider enfonction de la météo si un match prévu sejouera ou pas. Exemple :
X= (pluvieux, chaud, élevée, faible)
P(X| « oui ») = P(pluvieux | « oui »)* P(chaud | « oui ») * P(élevée | « oui ») * P(faible | « oui ») * P( « oui »)
= 2/5*2/5*4/5*2/5*5/14= 0,018286
P(X| « non ») = P(pluvieux | « non »)* P(chaud | « non ») * P(élevée | « non ») * P(faible | « non ») * P( « non »)
= 3/9*2/9*3/9*6/9*9/14= 0,010582
Il y a de bonnes chancesque ce match soit joué !
P(fort| oui) = 3/5P(fort|non) = 3/9P(faible| oui) = 2/5P(faible|non) = 6/9
P(élevée| oui) = 4/5P(élevée|non) = 3/9P(normale| oui) = 2/5P(normale|non) = 6/9
P(chaud| oui) = 2/5P(chaud|non) = 2/9P(doux| oui) = 2/5P(doux|non) = 4/9P(froid| oui) = 1/5P(froid|non) = 3/9
P(pluvieux| oui) = 2/5P(pluvieux|non) = 3/9P(couvert| oui) = 0P(couvert|non) = 4/9P(soleil|oui) = 3/5P(soleil|non) = 2/9
vent
humidité
température
ciel
P(« oui ») = 5/14 P(« non ») = 9/14
QUITTER><
04/01/2003 80
Limites de la classification Bayesienne
• L ’approche « naïve » suppose que tous les attributs sont linéairement indépendants
• Si ce n ’est pas le cas, il faut connaître les relations entre les attributs et le modèle (et les calculs) sont plus complexes.
• De toutes manières, le calcul de toutes les probabilités a priori est très coûteux.
• Mais, quand elle est réalisable, la classification Bayesienne est celle qui obtient les meilleurs résultats.
QUITTER><
04/01/2003 81
Classification par construction d ’un arbre de décision
• Un arbre de décision est une structure de type « organigramme » – chaque nœud interne est un test sur un des attributs– chaque feuille est le label d ’une classe
• La construction d ’un arbre de décision se fait par partitions récursives de l ’échantillon de données en considérant à chaque étape l ’attribut qui « partitionne le mieux » les données
QUITTER><
04/01/2003 82
Exemple : profil d ’unacheteur d ’ordinateur
age income student credit_rating buys_computer...30 high no fair no...30 high no excellent no31...40 high no fair yes40... medium no fair yes40... low yes fair yes40... low yes excellent no31…40 low yes excellent yes..30 medium no fair no...30 low yes fair yes40... medium yes fair yes...30 medium yes excellent yes31…40 medium no excellent yes31…40 high yes fair yes40... medium no excellent no
D ’après J. Ross Quinlan. The effect of noise on concept learning . In Ryszard S. Michalski, Jaime G. Carbonell, and Tom M. Mitchell, editors, Machine Learning: An Artificial Intelligence Approach, volume 2, chapter 6. Morgan Kaufmann, 1986.
Échantillon d ’apprentissage
QUITTER><
04/01/2003 83
À quoi veut-on arriver ?
age?
student? credit rating?
excellent fairyesno
…30 31…40 40...
yesno noyes yes
QUITTER><
04/01/2003 84
Algo général de construction de l ’arbre de décision
Partition initiale:ensemble des données
Reste-t-il des partitionsoù plusieurs classes sont
présentes ?
Choisir une partition hétérogène
Reste-t-il des critèresde sélection ?
Sélectionner « le meilleur »critère d ’éclatementpour cette partition
Éclater la partition analysée selonle critère choisi
stop
stop
QUITTER><
04/01/2003 85
Le « meilleur critère » departitionnement ?
• Intuitivement, celui qui sépare le mieux les instances des différentes classes.
• Différentes approches numériques – « gain d ’information » (Quinlan : système ID3)– index GINI (IntelligentMiner IBM)– ...
QUITTER><
04/01/2003 86Arbres de décision etrègles
• Il est facile d ’extraire d ’un arbre de décision des règles du type « si…alors » :
• chaque chemin de la racine à une feuille est représentée par une règle
IF age = “...30” AND student = “no” THEN buys_computer = “no”IF age = “...30” AND student = “yes” THEN buys_computer = “yes”IF age = “31…40” THEN buys_computer = “yes”IF age = “40...” AND credit_rating = “excellent” THEN buys_computer = “yes”IF age = “40...” AND credit_rating = “fair” THEN buys_computer = “no”
QUITTER><
04/01/2003 87
surspécification
• Si l ’on pousse trop loin le processus de classification sur l ’échantillon d ’apprentissage, les définition des classes obtenues seront de peu d ’utilité car elles ne reconnaîtront plus d ’exemples en dehors de ceux de l ’échantillon.
Arrêter la classification assez tôt !
Valider la classification obtenue
QUITTER><
04/01/2003 88
Validation croisée
• plusieurs méthodes de validation
• la plus utilisée : validation croisée
• découper le jeu de données disponible en– échantillon d ’apprentissage 3/5– échantillon de validation 2/5
• recommencer plusieurs fois en modifiant le découpage
QUITTER><
04/01/2003 89
Avantages de la classification par arbres de décision
• relativement rapide
• conversion immédiate vers un jeu de règles faciles à comprendre et à utiliser
QUITTER><
04/01/2003 90
Classification par la méthode des k plus proches voisins
• toutes les données sont représentées dans un espace vectoriel de dimension n (Rn), munie d ’une distance (distance euclidienne)
• soit à déterminer la classe d ’un vecteur X quelconque. Soient y1, y2, …,yk ses k voisins les plus proches de l ’échantillon d ’apprentissage. X sera rangé dans la classe la plus répandue parmi ces k voisins.
QUITTER><
04/01/2003 91
Importance du facteur k
+
+
+
•Pour k=1, est classé -
•Pour k=5, est classé +
Importance dela phase de validation
QUITTER><
04/01/2003 92
diagrammes de Voronoï
Les surfaces de décisionpour les 1-NN sur R2 sont
appelées diagrammes de Voronoï
QUITTER><
04/01/2003 93
Intérêt et limitations de la méthode kNN
• + Très simple à mettre en œuvre• + Complexité linéaire par rapport à la taille de
l ’échantillon d ’apprentissage
• - Peut nécessiter la normalisation et la pondération des attributs.
• - K est un paramètre de la méthode : critères de choix de k ?
QUITTER><
04/01/2003 94Classification par algorithme génétique
• les règles de classification selon la valeur des attributs peuvent être codées sous forme de chromosomes, et leur pertinence évaluée sur l ’échantillon d ’apprentissage. Elles sont optimisées selon les règles évolutionistes
• Cf. cours AG
QUITTER><
04/01/2003 95Classification par réseaux de neurones
• les réseaux de neurones sont par construction dédiés à la classification
• Cf. cours RN
QUITTER><
04/01/2003 96Autres techniques de classification
• logique floue• raisonnement à partir de cas• espace des versions• ………….
• Ne seront pas présentées ici
QUITTER><
04/01/2003 97
Pour les curieux• Une bible du KDD : « Advances in Knowledge Discovery and Data
Mining », U. M. Fayyad , G. Piatetsky-Shapiro , P. Smyth, R. Uthurusamy (Editors), AAAI Press/The MIT Press, 1996.
• Pour la chimie : H.M. Cartwright « Applications of Artificial Intelligence in Chemistry » Oxford University Press, 1993.
• Un site Web incontournable (mais il en a beaucoup d ’autres) : http://www.kdnuggets.com/
QUITTER><