Fouille de données Notes de cours

Fouille de données Notes de cours

Documents
256 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

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

Informations

Publié par
Nombre de visites sur la page 95
Langue Français
Signaler un problème

Fouille de donnees
Notes de cours
Ph. PREUX
Universite de Lille 3
philippe.preux@univ-lille3.fr
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 segmentations . . . . . . . . . . . . . . . . 154
11.5.1 Analyse de tableau de contingence . . . . . . . . . . . . . 154
11.5.2 Autre approche . . . . . . . . . . . . . . . . . . . . . . . . 155
11.6 Critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
11.7 Logiciels libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
11.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
12 Methodes de projection 157
12.1 Analyse en composantes principales . . . . . . . . . . . . . . . . . 159
12.1.1 L’Analyse en Composantes Principales . . . . . . . . . . . 159
12.1.2 Aspects pratiques . . . . . . . . . . . . . . . . . . . . . . . 173
12.1.3 La (grande) famille des ACP . . . . . . . . . . . . . . . . 175
12.1.4 ACP et textes : l’indexation par la semantique latente . . 176
12.1.5 Critique de l’ACP . . . . . . . . . . . . . . . . . . . . . . 179
12.2 La mise a l’echelle multi-dimensionnelle . . . . . . . . . . . . . . 179
12.2.1 Mise a l’echelle metrique . . . . . . . . . . . . . . . . . . . 182
12.2.2 Mise a l’echelle non metrique . . . . . . . . . . . . . . . . 183
12.2.3 Diagnostic du resultat d’une MDS . . . . . . . . . . . . . 183TABLE DES MATIERES vii
12.2.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . 184
12.3 Reseaux de Kohonen . . . . . . . . . . . . . . . . . . . . . . . . . 185
12.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 185
12.3.2 Algorithme d’apprentissage . . . . . . . . . . . . . . . . . 186
12.3.3 Deroulement de l’apprentissage . . . . . . . . . . . . . . . 187
12.3.4 Exploitation d’un apprentissage . . . . . . . . . . . . . . . 188
12.3.5 Application des reseaux de Kohonen a des textes . . . . . 188
12.3.6 Autres applications des reseaux de Kohonen . . . . . . . . 193
12.3.7 Critique des cartes de Kohonen . . . . . . . . . . . . . . . 193
12.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
12.5 Les logiciels libres . . . . . . . . . . . . . . . . . . . . . . . . . . 195
12.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
12.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
13 Les regles d’association 197
13.1 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
13.2 Algorithme A-Priori . . . . . . . . . . . . . . . . . . . . . . . . . 199
13.2.1 Construction des ensembles d’items frequents . . . . . . . 199
13.2.2 Generation des regles d’association a partir des EIF . . . 201
13.2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
13.2.4 Application sur l’exemple . . . . . . . . . . . . . . . . . . 202
13.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
13.4 Les paires rares mais importantes . . . . . . . . . . . . . . . . . . 203
13.4.1 Similarite . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
13.4.2 Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
13.4.3 par hashage min . . . . . . . . . . . . . . . . . 205
13.4.4 Hashage localement sensible (LSH) . . . . . . . . . . . . . 206
13.4.5 Hashage k-min . . . . . . . . . . . . . . . . . . . . . . . . 206
13.5 Logiciels libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
14 Prediction numerique 207
14.1 Regression lineaire simple et multiple . . . . . . . . . . . . . . . . 207
14.2 Arbres de regression . . . . . . . . . . . . . . . . . . . . . . . . . 207
14.3 Reseau de neurones . . . . . . . . . . . . . . . . . . . . . . . . . . 208
14.4 Regression a vecteur support : RVS . . . . . . . . . . . . . . . . . 208
14.5 R locale ponderee . . . . . . . . . . . . . . . . . . . . . . 208
14.6 Logiciels libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
15 Pre- et post-traitement 209
16 Applications de la fouille de donnees 211
16.1 Fouille de textes . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
16.2 Fouille du web . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211viii TABLE DES MATIERES
A Rappels de statistiques et plus 213
A.1 Statistiques descriptives d’une serie de mesures . . . . . . . . . . 213
A.2 Correlation lineaire . . . . . . . . . . . . . . . . . . . . . . . . . . 221
B Theoreme de Bayes 225
C Complexite algorithmique 227
D Programmation mathematique 231
D.1 Programme lineaire . . . . . . . . . . . . . . . . . . . . . . . . . . 231
D.2 quadratique ou convexe . . . . . . . . . . . . . . . . 232
D.3 Programme semi-de nie . . . . . . . . . . . . . . . . . . . . . . . 232
D.4 non lineaire . . . . . . . . . . . . . . . . . . . . . . . 232
Index 235
References bibliographiques 241Notations
On resume ici les notations utilisees dans l’ensemble de ce document :
{ X : ensemble de donnees ou d’exemples (cf. chap. 1, sec. 1.2.1) ;
{ x2X : un element deX , i.e., une donnee ;
{ A : ensemble des attributs decrivant chacune des donnees (cf. chap. 1, sec.
1.2.1) ;
{ a2A : un element deA, i.e., un attribut ;
{ V : ensemble des valeurs possibles pour l’attribut a2A (cf. chap. 1, sec.a
1.2.1) ;
{ D : espace des donnees : espace contenant toutes les donnees possibles pour
le probleme considere ; on a la relationXD (cf. chap. 1, sec. 1.2.1) ;
{ N =jXj : nombre de donnees disponibles (cf. chap. 1, sec. 1.2.1) ;
{ P =jAj : nombre d’attributs decrivant chaque donnee (cf. chap. 1, sec.
1.2.1) ;
{ K : nombre de segments (en segmentation) ;
{ k : fonction noyau
{ E : erreur (cf. chap. 3, sec. 3.7) ;
{ Y : ensemble des etiquettes possibles dans un probleme de classi cation
donne, ou un probleme de regression (cf. chap. 2 et chap. 14) ;
{ y2Y : un element deY, i.e., une classe dans un probleme de classi cation
ou une valeur associee a une donnee dans un probleme de regression ;
{ : taux d’apprentissage ;
{ a/b signi e que la valeur de a (typiquement, une probabilite) est estimee
par la valeur de b ;
{ ab signi e que la valeur numerique de a est a peu pres celle du nombre
decimal b a( la precision donnee pour b, generalement le centieme ou le
millieme) ;
{ v est la moyenne des elements du vecteur v ;
{ est la moyenne de la variable aleatoire v ;v
{ var(v) est la variance des elements du vecteur v ;
{ var(v) est la v de la variable aleatoire v ;
{ denote l’ecart-type.
{ dissimilarite : au chap. 5, D au chap. 12.
Exceptionnellement,K et peuvent signi er autre chose : K dans les chap.
5 et 9 , dans le chap. 8.
Indi cages :
{ A etant une matrice, A denote l’element de la matrice A situe sur lai;j
ligne i, colonne j.