Fouille de données Notes de cours

Description

• cours - matière potentielle : ph

Fouille de donnees Notes de cours Ph. PREUX Universite de Lille 3 26 mai 2011

• application au jeu de donnees iris
• programme lineaire
• arbre de decision
• probleme de classification
• synthese des methodes de classification
• illustration sur les iris
• attributs
• attribut
• classification
• classifications
• methodes de projection

Sujets

• cours

Informations

• Publié par: figas
• Nombre de lectures: 95
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

Fouille de donnees
Notes de cours
Ph. PREUX
Universite de Lille 3
[e-mail]
26 mai 2011
http://www.grappa.univ-lille3.fr/ ppreux/fouille~iiTable des matieres
1 Introduction 3
1.1 Qu’est ce que la fouille de donnees ? . . . . . . . . . . . . . . . . 3
1.2 Qu’est ce qu’une donnee ? . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Les di erentes natures d’attributs . . . . . . . . . . . . . 5
1.2.3 Les di erentes natures de valeur d’attribut . . . . . . . . 6
1.2.4 Le bruit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.5 Di erentes t^aches d’extraction d’information . . . . . . . 7
1.3 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 La classi cation supervisee 11
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Une approche na ve . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Classi cation par arbres de decision 15
3.1 Construction d’un arbre de decision . . . . . . . . . . . . . . . . 17
3.2 Exemple de construction d’un arbre de decision par ID3 . . . . . 21
3.2.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.2 Interpretation de l’arbre . . . . . . . . . . . . . . . . . . . 23
3.3 Utilisation de l’arbre de decision pour classer une donnee . . . . 24
3.4 Les attributs numeriques . . . . . . . . . . . . . . . . . . . . . . . 25
3.4.1 Test d’un attribut numerique . . . . . . . . . . . . . . . . 25
3.4.2 Rapport de gain . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.3 Application : construction d’un arbre de decision en
presence d’attributs numeriques . . . . . . . . . . . . . . . 27
3.5 Valeurs d’attributs manquantes . . . . . . . . . . . . . . . . . . . 28
3.5.1 Attributs non values dans l’ensemble d’apprentissage . . . 28
3.5.2 Classi cation d’une donnee ayant des attributs non values 29
3.6 ID3 vs. C4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.7 Validation d’un arbre de decision . . . . . . . . . . . . . . . . . . 31
3.7.1 Mesures de qualite d’un classeur . . . . . . . . . . . . . . 32
iiiiv TABLE DES MATIERES
3.7.2 Validation croisee . . . . . . . . . . . . . . . . . . . . . . . 33
3.7.3 Technique du leave-one-out . . . . . . . . . . . . . . . . . 33
3.7.4 Technique de bootstrap (= bagging) . . . . . . . . . . . . . 33
3.7.5 Con ance dans l’estimation de l’erreur . . . . . . . . . . . 34
3.8 Sur-apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.9 Elagage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.10 Illustration sur les iris . . . . . . . . . . . . . . . . . . . . . . . . 39
3.11 Critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.12 Logiciels libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.13 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4 Classeur bayesien 47
4.1 La regle de Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.1.1 Le theoreme de Bayes . . . . . . . . . . . . . . . . . . . . 48
4.1.2 Application a la classi cation . . . . . . . . . . . . . . . . 48
4.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3 Attributs numeriques . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4 Valeur d’attribut manquante . . . . . . . . . . . . . . . . . . . . 54
4.4.1 Absence de la valeur d’un attribut dans une donnee dont
on veut predire la classe . . . . . . . . . . . . . . . . . . . 54
4.4.2 Absence de la valeur d’un attribut dans le jeu d’appren-
tissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4.3 Application au jeu de donnees iris . . . . . . . . . . . 55
4.5 Exemple : classi cation de textes . . . . . . . . . . . . . . . . . . 57
4.5.1 Representation d’un texte . . . . . . . . . . . . . . . . . . 58
4.5.2 Application de la regle de Bayes . . . . . . . . . . . . . . 58
4.6 Critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.7 Logiciels libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5 Classi cation a base d’exemples representatifs 65
5.1 Mesure de la dissimilarite entre deux donnees . . . . . . . . . . . 66
5.1.1 Attribut numerique . . . . . . . . . . . . . . . . . . . . . 67
5.1.2 Attribut nominal et attribut ordinal . . . . . . . . . . . . 67
5.1.3 Valeur d’attribut manquante . . . . . . . . . . . . . . . . 67
5.2 L’algorithme des plus proches voisins . . . . . . . . . . . . . . . . 67
5.2.1 Les k plus proches voisins . . . . . . . . . . . . . . . . . . 68
5.2.2 Application a jouer au tennis ? . . . . . . . . . . . . . 69
5.2.3 Critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3 Plus proches voisins sur le jeu de donnees iris . . . . . . . . 71
5.4 Plus proches voisins et classi cation de textes . . . . . . . . . . . 71
5.5 Logiciel libre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77TABLE DES MATIERES v
5.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6 Classeur a base de regles 79
6.1 Methode c4.5rules . . . . . . . . . . . . . . . . . . . . . . . . 80
6.2 Approche par couverture : l’algorithme Prism . . . . . . . . . . . 82
6.3 Approche par regles d’association . . . . . . . . . . . . . . . . . . 84
6.4 Synthese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.5 Logiciels libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7 Classi cation par reseaux de neurones 87
7.1 Le neurone formel . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.1.1 Description d’un neurone formel . . . . . . . . . . . . . . 88
7.1.2 Apprentissage des poids d’un perceptron . . . . . . . . . . 90
7.1.3 Illustration sur les iris . . . . . . . . . . . . . . . . . . . . 95
7.2 Perceptron multi-couches . . . . . . . . . . . . . . . . . . . . . . 98
7.2.1 Topologie d’un perceptron multi-couches . . . . . . . . . . 100
7.2.2 Apprentissage des poids d’un PMC . . . . . . . . . . . . . 102
7.2.3 Quelques complements sur l’algorithme d’apprentissage
des poids . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.2.4 D’autres resultats rassurants . . . . . . . . . . . . . . . . 108
7.3 Application a jouer au tennis ? . . . . . . . . . . . . . . . . . 109
7.3.1 Numerisation des attributs et de la classe . . . . . . . . . 109
7.4 Critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.5 Les logiciels libres . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
8 Classi cation par MVS 111
8.1 Machine a vecteurs supports lineaire . . . . . . . . . . . . . . . . 112
8.1.1 Cas separable . . . . . . . . . . . . . . . . . . . . . . . . . 112
8.1.2 Cas non separable . . . . . . . . . . . . . . . . . . . . . . 115
8.2 Machine a vecteurs supports non lineaire . . . . . . . . . . . . . . 117
8.2.1 Construction d’une MVS non lineaire . . . . . . . . . . . 117
8.2.2 Fonctions noyaux . . . . . . . . . . . . . . . . . . . . . . . 118
8.3 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
8.4 Les logiciels libres pour MVS . . . . . . . . . . . . . . . . . . . . 119
8.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
9 Classi cation par selection d’attributs 121vi TABLE DES MATIERES
10 Pour en nir avec la classi cation 123
10.1 Combinaison de classeurs . . . . . . . . . . . . . . . . . . . . . . 123
10.1.1 Bagging . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
10.1.2 Boosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
10.2 Apprendre avec des donnees non etiquetees . . . . . . . . . . . . 126
10.3 Synthese des methodes de classi cation . . . . . . . . . . . . . . 126
10.4 Logiciels libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
10.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
10.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
11 Segmentation 131
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
11.2 Segmentation non hierarchique . . . . . . . . . . . . . . . . . . . 133
11.2.1 L’algorithme des centres mobiles . . . . . . . . . . . . . . 134
11.2.2 Quelques remarques sur les centres mobiles . . . . . . . . 135
11.2.3 Illustration des centres mobiles . . . . . . . . . . . . . . . 136
11.2.4 L’algorithme EM . . . . . . . . . . . . . . . . . . . . . . . 138
11.2.5 Autres algorithmes de segmentation non hierarchique . . 143
11.3 Segmentation hierarchique . . . . . . . . . . . . . . . . . . . . . . 148
11.3.1 Methode ascendante . . . . . . . . . . . . . . . . . . . . . 148
11.4 Application au jeu de donnees iris . . . . . . . . . . . . . . . 151
11.4.1 Les centres mobiles sur les iris . . . . . . . . . . . . . 151
11.4.2 EM sur les iris . . . . . . . . . . . . . . . . . . . . . . 153
11.4.3 Segmentation hierarchique des iris . . . . . . . . . . . 154
11.5 Comparaison de deux segmenta