Fouille de donn ees
Notes de cours
Ph. PREUX
Universit e de Lille 3
26 mai 2011
http://www.grappa.univ-lille3.fr/~ppreux/fouille
ii
Table des mati`eres
1 Introduction
1.1 Quest ce que la fouille de donn ees ? . . . . . . . . . . . . . . . .
1.2 Quest ce quune donn ee ? . . . . . . . . . . . . . . . . . . . . . .
1.2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .
1.2.2 Les di erentes natures dattributs
1.2.3 Les di erentes natures de valeur dattribut
. . . . . . . .
1.2.4 Le bruit . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.5 Di erentes t aches dextraction dinformation . . . . . . .
1.3 R ef erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 La classication supervis ee
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1
2.2 Une approche na 1ve . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Classication par arbres de d ecision
3.1 Construction dun arbre de d ecision . . . . . . . . . . . . . . . .
3.2 Exemple de construction dun arbre de d ecision par ID3 . . . . .
3.2.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . .
Interpr etation de larbre . . . . . . . . . . . . . . . . . . .
3.2.2
3.3 Utilisation de larbre de d ecision pour classer une donn ee
. . . .
3.4 Les attributs num eriques . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 Test dun attribut num erique . . . . . . . . . . . . . . . .
3.4.2 Rapport de gain . . . . . . . . . . . . . . . . . . . . . . .
3.4.3 Application : construction dun arbre de d ecision en
pr esence dattributs num eriques . . . . . . . . . . . . . . .
3.5 Valeurs dattributs manquantes . . . . . . . . . . . . . . . . . . .
3.5.1 Attributs non valu es dans lensemble dapprentissage . . .
3.5.2 Classication dune donn ee ayant des attributs non valu es
ID3 vs. C4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6
3.7 Validation dun arbre de d ecision . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
3.7.1 Mesures de qualit e dun classeur
3
3
5
5
5
6
7
7
9
11
11
13
14
15
17
21
21
23
24
25
25
27
27
28
28
29
30
31
32
iii
iv
TABLE DES MATI `ERES
3.7.2 Validation crois ee . . . . . . . . . . . . . . . . . . . . . . .
3.7.3 Technique du leave-one-out
. . . . . . . . . . . . . . . . .
3.7.4 Technique de bootstrap (= bagging) . . . . . . . . . . . . .
3.7.5 Conance dans lestimation de lerreur . . . . . . . . . . .
3.8 Sur-apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . .
Elagage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9
3.10 Illustration sur les iris . . . . . . . . . . . . . . . . . . . . . . . .
3.11 Critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.12 Logiciels libres
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.13 Exercices
4 Classeur bay esien
4.1 La r`egle de Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Le th eor`eme de Bayes . . . . . . . . . . . . . . . . . . . .
4.1.2 Application `a la classication . . . . . . . . . . . . . . . .
4.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Attributs num eriques . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
4.4 Valeur dattribut manquante
4.4.1 Absence de la valeur dun attribut dans une donn ee dont
on veut pr edire la classe . . . . . . . . . . . . . . . . . . .
4.4.2 Absence de la valeur dun attribut dans le jeu dappren-
tissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.3 Application au jeu de donn ees (cid:28) iris (cid:29) . . . . . . . . . . .
4.5 Exemple : classication de textes . . . . . . . . . . . . . . . . . .
4.5.1 Repr esentation dun texte . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
4.5.2 Application de la r`egle de Bayes
4.6 Critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7 Logiciels libres
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.8 Exercices
5 Classication `a base dexemples repr esentatifs
5.1 Mesure de la dissimilarit e entre deux donn ees . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
5.1.1 Attribut num erique
5.1.2 Attribut nominal et attribut ordinal
. . . . . . . . . . . .
5.1.3 Valeur dattribut manquante . . . . . . . . . . . . . . . .
5.2 Lalgorithme des plus proches voisins . . . . . . . . . . . . . . . .
5.2.1 Les k plus proches voisins . . . . . . . . . . . . . . . . . .
5.2.2 Application `a (cid:28) jouer au tennis ? (cid:29) . . . . . . . . . . . . .
5.2.3 Critique . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Plus proches voisins sur le jeu de donn ees (cid:28) iris (cid:29) . . . . . . . .
5.4 Plus proches voisins et classication de textes . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Logiciel libre
33
33
33
34
37
39
39
40
41
41
47
48
48
48
50
52
54
54
54
55
57
Advertisement
58
58
60
60
60
65
66
67
67
67
67
68
69
70
71
71
77
TABLE DES MATI `ERES
v
5.6 Exercices
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
6 Classeur a base de regles
6.1 M ethode (cid:28) c4.5rules (cid:29) . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Approche par couverture : lalgorithme Prism . . . . . . . . . . .
6.3 Approche par r`egles dassociation . . . . . . . . . . . . . . . . . .
6.4 Synth`ese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.5 Logiciels libres
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 Classication par r eseaux de neurones
7.1 Le neurone formel
. . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1 Description dun neurone formel
. . . . . . . . . . . . . .
7.1.2 Apprentissage des poids dun perceptron . . . . . . . . . .
7.1.3
Illustration sur les iris . . . . . . . . . . . . . . . . . . . .
7.2 Perceptron multi-couches
. . . . . . . . . . . . . . . . . . . . . .
79
80
82
84
85
85
87
88
88
90
95
98
7.2.1 Topologie dun perceptron multi-couches . . . . . . . . . . 100
7.2.2 Apprentissage des poids dun PMC . . . . . . . . . . . . . 102
7.2.3 Quelques compl ements sur lalgorithme dapprentissage
des poids
. . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.2.4 Dautres r esultats rassurants
. . . . . . . . . . . . . . . . 108
7.3 Application `a (cid:28) jouer au tennis ? (cid:29) . . . . . . . . . . . . . . . . . 109
7.3.1 Num erisation des attributs et de la classe . . . . . . . . . 109
7.4 Critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.5 Les logiciels libres
. . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.6 Exercices
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
8 Classication par MVS
111
8.1 Machine `a vecteurs supports lin eaire . . . . . . . . . . . . . . . . 112
8.1.1 Cas s eparable . . . . . . . . . . . . . . . . . . . . . . . . . 112
8.1.2 Cas non s eparable . . . . . . . . . . . . . . . . . . . . . . 115
8.2 Machine `a vecteurs supports non lin eaire . . . . . . . . . . . . . . 117
8.2.1 Construction dune MVS non lin eaire
. . . . . . . . . . . 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 Classication par s election dattributs
121
vi
TABLE DES MATI `ERES
10 Pour en nir avec la classication
123
10.1 Combinaison de classeurs
. . . . . . . . . . . . . . . . . . . . . . 123
10.1.1 Bagging . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
10.1.2 Boosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
10.2 Apprendre avec des donn ees non etiquet ees
. . . . . . . . . . . . 126
10.3 Synth`ese des m ethodes de classication . . . . . . . . . . . . . . 126
10.4 Logiciels libres
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
10.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
10.6 Exercices
11 Segmentation
131
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
11.2 Segmentation non hi erarchique . . . . . . . . . . . . . . . . . . . 133
11.2.1 Lalgorithme 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 Lalgorithme EM . . . . . . . . . . . . . . . . . . . . . . . 138
. . 143
11.2.5 Autres algorithmes de segmentation non hi erarchique
11.3 Segmentation hi erarchique . . . . . . . . . . . . . . . . . . . . . . 148
11.3.1 M ethode ascendante . . . . . . . . . . . . . . . . . . . . . 148
11.4 Application au jeu de donn ees (cid:28) iris (cid:29) . . . . . . . . . . . . . . . 151
11.4.1 Les centres mobiles sur les (cid:28) iris (cid:29) . . . . . . . . . . . . . 151
11.4.2 EM sur les (cid:28) iris (cid:29) . . . . . . . . . . . . . . . . . . . . . . 153
11.4.3 Segmentation hi erarchique des (cid:28) iris (cid:29) . . . . . . . . . . . 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
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
11.7 Logiciels libres
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
11.8 Exercices
12 M ethodes de projection
157
12.1 Analyse en composantes principales . . . . . . . . . . . . . . . . . 159
12.1.1 LAnalyse 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 : lindexation par la s emantique latente . . 176
12.1.5 Critique de lACP . . . . . . . . . . . . . . . . . . . . . . 179
12.2 La mise `a l echelle multi-dimensionnelle . . . . . . . . . . . . . . 179
12.2.1 Mise `a l echelle m etrique . . . . . . . . . . . . . . . . . . . 182
12.2.2 Mise `a l echelle non m etrique . . . . . . . . . . . . . . . . 183
12.2.3 Diagnostic du r esultat dune MDS . . . . . . . . . . . . . 183
TABLE DES MATI `ERES
vii
12.2.4 Applications
. . . . . . . . . . . . . . . . . . . . . . . . . 184
12.3 R eseaux de Kohonen . . . . . . . . . . . . . . . . . . . . . . . . . 185
12.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 185
12.3.2 Algorithme dapprentissage . . . . . . . . . . . . . . . . . 186
12.3.3 D eroulement de lapprentissage . . . . . . . . . . . . . . . 187
12.3.4 Exploitation dun apprentissage . . . . . . . . . . . . . . . 188
12.3.5 Application des r eseaux de Kohonen `a des textes . . . . . 188
12.3.6 Autres applications des r eseaux de Kohonen . . . . . . . . 193
12.3.7 Critique des cartes de Kohonen . . . . . . . . . . . . . . . 193
12.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
. . . . . . . . . . . . . . . . . . . . . . . . . . 195
12.5 Les logiciels libres
12.6 R ef erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Advertisement
12.7 Exercices
13 Les r`egles dassociation
197
13.1 D enitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
. . . . . . . . . . . . . . . . . . . . . . . . . 199
13.2 Algorithme A-Priori
13.2.1 Construction des ensembles ditems fr equents . . . . . . . 199
13.2.2 G en eration des regles dassociation a partir des EIF . . . 201
13.2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
13.2.4 Application sur lexemple . . . . . . . . . . . . . . . . . . 202
13.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
13.4 Les paires rares mais importantes . . . . . . . . . . . . . . . . . . 203
13.4.1 Similarit e . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
13.4.2 Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
13.4.3 Signature par hashage min . . . . . . . . . . . . . . . . . 205
13.4.4 Hashage localement sensible (LSH) . . . . . . . . . . . . . 206
13.4.5 Hashage k-min . . . . . . . . . . . . . . . . . . . . . . . . 206
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
13.5 Logiciels libres
14 Pr ediction num erique
207
14.1 R egression lin eaire simple et multiple . . . . . . . . . . . . . . . . 207
14.2 Arbres de r egression . . . . . . . . . . . . . . . . . . . . . . . . . 207
14.3 R eseau de neurones . . . . . . . . . . . . . . . . . . . . . . . . . . 208
14.4 R egression `a vecteur support : RVS . . . . . . . . . . . . . . . . . 208
14.5 R egression locale pond er ee . . . . . . . . . . . . . . . . . . . . . . 208
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
14.6 Logiciels libres
15 Pr e- et post-traitement
209
16 Applications de la fouille de donn ees
211
16.1 Fouille de textes
. . . . . . . . . . . . . . . . . . . . . . . . . . . 211
16.2 Fouille du web . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
viii
TABLE DES MATI `ERES
A Rappels de statistiques et plus
213
A.1 Statistiques descriptives dune s erie de mesures . . . . . . . . . . 213
A.2 Corr elation lin eaire . . . . . . . . . . . . . . . . . . . . . . . . . . 221
B Th eor`eme de Bayes
C Complexit e algorithmique
225
227
D Programmation math ematique
231
D.1 Programme lin eaire . . . . . . . . . . . . . . . . . . . . . . . . . . 231
D.2 Programme quadratique ou convexe
. . . . . . . . . . . . . . . . 232
D.3 Programme semi-d enie . . . . . . . . . . . . . . . . . . . . . . . 232
D.4 Programme non lin eaire . . . . . . . . . . . . . . . . . . . . . . . 232
Index
R ef erences bibliographiques
235
241
Notations
On r esume ici les notations utilis ees dans lensemble de ce document :
: ensemble de donn ees ou dexemples (cf. chap. 1, sec. 1.2.1) ;
X
x
, i.e., une donn ee ;
X
: ensemble des attributs d ecrivant chacune des donn ees (cf. chap. 1, sec.
: un el ement de
X
A
1.2.1) ;
a
: un el ement de
, i.e., un attribut ;
A
a : ensemble des valeurs possibles pour lattribut a
A
V
1.2.1) ;
(cf. chap. 1, sec.
A
: espace des donn ees : espace contenant toutes les donn ees possibles pour
D
le probl`eme consid er e ; on a la relation
: nombre de donn ees disponibles (cf. chap. 1, sec. 1.2.1) ;
: nombre dattributs d ecrivant chaque donn ee (cf. chap. 1, sec.
(cf. chap. 1, sec. 1.2.1) ;
X D
N =
P =
|X |
|A|
1.2.1) ;
K : nombre de segments (en segmentation) ;
k : fonction noyau
E : erreur (cf. chap. 3, sec. 3.7) ;
: ensemble des etiquettes possibles dans un probl`eme de classication
Y
donn e, ou un probl`eme de r egression (cf. chap. 2 et chap. 14) ;
y
: un el ement de
, i.e., une classe dans un probl`eme de classication
Y
Y
ou une valeur associ ee a une donn ee dans un probleme de r egression ;
: taux dapprentissage ;
a
par la valeur de b ;
b signie que la valeur de a (typiquement, une probabilit e) est estim ee
a
H
b signie que la valeur num erique de a est a peu pres celle du nombre
d ecimal b (a la pr ecision donn ee pour b, g en eralement le centieme ou le
milli`eme) ;
v est la moyenne des el ements du vecteur v ;
v est la moyenne de la variable al eatoire v ;
var(v) est la variance des el ements du vecteur v ;
var(v) est la variance de la variable al eatoire v ;
d enote l ecart-type.
dissimilarit e : au chap. 5, D au chap. 12.
Exceptionnellement, K et peuvent signier autre chose : K dans les chap.
5 et 9 , dans le chap. 8.
Indi cages :
A etant une matrice, Ai,j d enote l element de la matrice A situ e sur la
ligne i, colonne j.
R esum e
Jai rassembl e ici mes notes de cours et un certain nombre dinformations con-
cernant la fouille de donn ees.
On adopte une approche pragmatique et pratique, tout en essayant de donner
le mat eriel n ecessaire pour comprendre ce que lon fait : le but nest pas dap-
pliquer aveugl ement des algorithmes, mais de conna 1tre des algorithmes et de
savoir quand et comment les appliquer, d etre capable de les utiliser et de juger
les r esultats quils fournissent. En fouille de donn ees, on ne peut pas se contenter
dappliquer aveugl ement une m ethode et de se contenter tout aussi aveugl ement
du r esultat obtenu, comme sil sagissait de LA r eponse au probl`eme. Les algo-
rithmes dextraction dinformation constituent une bo 1te `a outils ; ayant cette
bo 1te a disposition, il nous faut apprendre a les utiliser, comme lartisan ap-
prend `a manier ces outils. Dit autrement, la fouille de donn ees est un art : outre
les connaissances plus ou moins techniques `a acqu erir, il faut ensuite accumuler
beaucoup de pratique.
Au niveau pratique, on sappuie exclusivement sur des logiciels libres : ils sont
ais ement accessibles sur la Toile. Certains sont remarquables. Malheureusement,
il ny a pas `a lheure actuelle de v eritable atelier de fouille de donn ees qui
soit libre. Ceux-ci integrent de tres nombreux outils danalyse et de fouille de
donn ees, de visualisation de donn ees et des r esultats de fouille, de pr esentation
des r esultats (cr eation de tableaux de bord) et de liaison avec des bases et
entrep ots de donn ees : ces logiciels sont assez on ereux.
Advertisement
On ne sattaque pas au probl`eme de la gestion de gros volumes de donn ees ;
ce que lon raconte ici sapplique `a des volumes de donn ees raisonnables (ordre de
grandeur : m ega-octets stock es dans de simples chiers chiers Unix : suite de
caract`eres non structur ee ou des bases de donn ees traditionnelles type sql).
Au-del`a, des architectures sp ecialis ees (entrep ots de donn ees) sont n ecessaires
pour cette gestion. Ici et la, on indique comment passer a l echelle en ce qui
concerne les algorithmes de fouille.
Ces notes ne sont pas particuli`erement destin ees aux etudiants en informa-
tique, au contraire. Il est certain quun etudiant en informatique peut les lire ; il
est tout aussi certain que la r edaction se veut dune accessibilit e beaucoup plus
g en erale. Les notions dinformatique pure qui sont n ecessaires pour une bonne
compr ehension sont introduites dans le texte ou en annexe.
Pr e-requis : une connaissance minimale en math ematiques (alg ebre, analyse,
probabilit es, statistiques) est n ecessaire ainsi quune connaissance minimale en
algorithmique. Ensuite, jessaie dintroduire les notions n ecessaires. En fait, le
plus important est : avoir envie de comprendre, se poser des questions, essayer de
comprendre et exp erimenter sur ordinateur. Ce dernier point est essentiel : pour
fouiller les donn ees, lordinateur est un outil indispensable. En parall`ele, pour
comprendre les m ethodes, les math ematiques constituent loutil indispensable.
Remarque
Des remarques ponctuent le texte ; elles sont ecrites dans des caract`eres plus petits que le
texte normal. Leur lecture nest pas indispensable lors dun premier contact. Elles ont pour
but de donner des d etails qui permettent de mieux comprendre le texte en justiant certains
points ou en soulevant des questions pour aiguiser le regard du lecteur. Il est clair que pour
vraiment comprendre les choses, la lecture de ces remarques est n ecessaire.
Chapitre 1
Introduction
Contenu
1.1 Quest ce que la fouille de donn ees ? . . . . . . . .
1.2 Quest ce quune donn ee ? . . . . . . . . . . . . . .
1.2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . .
1.2.2 Les di erentes natures dattributs
. . . . . . . . . .
1.2.3 Les di erentes natures de valeur dattribut
. . . . .
1.2.4 Le bruit . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.5 Di erentes t aches dextraction dinformation . . . .
1.3 R ef erences . . . . . . . . . . . . . . . . . . . . . . . .
3
5
5
5
6
7
7
9
1.1 Quest ce que la fouille de donn ees ?
La fouille de donn ees consiste `a rechercher et extraire de linformation (utile
et inconnue) de gros volumes de donn ees stock ees dans des bases ou des en-
trep ots de donn ees. Le d eveloppement r ecent de la fouille de donn ees (depuis
le d ebut des ann ees 1990) est li e `a plusieurs facteurs : une puissance de calcul
importante est disponible sur les ordinateurs de bureau ou m eme `a domicile ;
le volume des bases de donn ees augmente enorm ement ; lacc`es aux r eseaux de
taille mondiale, ces r eseaux ayant un d ebit sans cesse croissant, qui rendent le
calcul distribu e et la distribution dinformation sur un r eseau d echelle mondi-
ale viable ; la prise de conscience de lint er et commercial pour loptimisation des
processus de fabrication, vente, gestion, logistique, ...
La fouille de donn ees a aujourdhui une grande importance economique
du fait quelle permet doptimiser la gestion des ressources (humaines et
mat erielles). Elle est utilis ee par exemple :
organisme de cr edit : pour d ecider daccorder ou non un cr edit en fonc-
tion du prol du demandeur de cr edit, de sa demande, et des exp eriences
3
4
CHAPITRE 1. INTRODUCTION
pass ees de pr ets ;
optimisation du nombre de places dans les avions, h otels, ...
r eservation
sur-
organisation des rayonnages dans les supermarch es en regroupant les pro-
duits qui sont g en eralement achet es ensemble (pour que les clients nou-
blient pas b etement dacheter un produit parce quil est situ e `a lautre
bout du magasin). Par exemple, on extraira une r`egle du genre : (cid:28) les
clients qui achetent le produit X en n de semaine, pendant l et e, achetenet
g en eralement egalement le produit Y (cid:29) ;
organisation de campagne de publicit e, promotions, ... (ciblage des ores)
diagnostic m edical : (cid:28) les patients ayant tels et tels symptomes et de-
meurant dans des agglom erations de plus de 104 habitants d eveloppent
couramment telle pathologie (cid:29) ;
analyse du g enome et bio-informatique plus g en eralement
classication dobjets (astronomie, ...)
commerce electronique, recommendation de produits
analyser les pratiques et strat egies commerciales et leurs impacts sur les
ventes
moteur de recherche sur internet : fouille du web
extraction dinformation depuis des textes : fouille de textes
evolution dans le temps de donn es : fouille de s equences.
Le processus complet de fouille de donn ees comprend plusieurs etapes :
1. collecte des informations et organisation de ces infos dans une base de
donn ees ;
2. nettoyage de la base de donn ees : attributs sans valeur, ayant une valeur
invalide (bruit), ... ; normalisation ;
3. s election des attributs utiles ;
4. extraction dinformation dune base de donn ees (Knowledge Discovery in
Databases, ou KDD) ;
5. visualisation des donn ees : histogramme, camembert, arbre, visualisation
3D et plus g en eralement, exploration interactive de donn ees ;
6. evaluation des r esultats de lextraction de connaissance.
Dans ce cours, on sint eressera essentiellement `a la phase 4 et un peu aux
phases 2, 3 et 5. Les aspects concernant les bases de donn ees seront vues dans le
cours du m eme nom. La phase 4 fait appel `a des statistiques et des algorithmes
dintelligence articielle (apprentissage automatique). L etude de quelques ex-
emples typiques de ces algorithmes constitue le corps de ce cours, suivie de
l etude de quelques applications r eelles. Avant tout, nous discutons de la notion
de donn ees.
1.2. QUEST CE QUUNE DONN EE ?
5
1.2 Quest ce quune donn ee ?
Cette section a pour objet de xer un vocabulaire et de rappeler quelques
faits importants concernant les attributs des donn ees et ce que repr esente la
valeur dun attribut. Mais tout dabord quelques notations que nous retrou-
verons dans lensemble du cours, notations r esum ees page ix.
1.2.1 Notations
X
On notera
dattributs. Chaque attribut a
un ensemble de donn ees. Chaque donn ee est d ecrite par un
prend sa valeur dans un certain
ensemble
A
a. Ainsi, on peut consid erer lensemble des donn ees x
ensemble de valeurs
dont les coordonn ees balayent toutes les valeurs possibles des attributs : cest
. Si lon note a1, ... aP les P attributs,
lespace des donn ees que nous noterons
...
aP . Toute donn ee appartient `a cet ensemble et on a
A
=
D
V
a1 V
V
D
.
X D
a2
V
Il est souvent utile davoir une repr esentation g eom etrique de lespace des
donn ees ; chaque attribut correspondant `a un axe de coordonn ees. Sil y a P
attributs, lespace des donn ees est un espace euclidien `a P dimensions.
1.2.2 Les di erentes natures dattributs
Une donn ee est un enregistrement au sens des bases de donn ees, que
lon nomme aussi (cid:28) individu (cid:29) (terminologie issue des statistiques) ou (cid:28) in-
stance (cid:29) (terminologie orient ee objet en informatique) ou m eme (cid:28) tuple (cid:29) (ter-
minologie base de donn ees) et (cid:28) point (cid:29) ou (cid:28) vecteur (cid:29) parce que nalement,
dun point de vue abstrait, une donn ee est un point dans un espace euclidien
ou un vecteur dans un espace vectoriel. Une donn ees est caract eris ee par un en-
semble de (cid:28) champs (cid:29), de (cid:28) caract`eres (cid:29), ou encore d(cid:28) attributs (cid:29) (en suivant
Advertisement
les 3 terminologies pr ec edemment evoqu ees : bases de donn ees, statistiques et
conception orient ee objet).
Un attribut peut etre de nature qualitative ou quantitative en fonction de
lensemble des valeurs quil peut prendre. Un attribut est qualitatif si on ne
peut pas en faire une moyenne ; sa valeur est dun type d eni en extension (une
couleur, une marque de voiture, ...).
Sinon, lattribut est de nature quantitative : un entier, un r eel, ... ; il peut
repr esenter un salaire, une surface, un nombre dhabitants, ... On peut donc
appliquer les op erateurs arithm etiques habituels sur les attributs quantitatifs,
ce qui nest pas le cas des attributs qualitatifs.
Un attribut peut egalement etre un enregistrement (une date par exem-
ple), donc compos e lui-m eme de sous-attributs (jour, mois, ann ee dans le cas
dune date), sur lequel on peut d enir les op erateurs arithm etiques habituels :
donc quantitatif ne signie pas forc ement (cid:28) num erique (cid:29) et, r eciproquement,
attribut qualitatif
attribut quantitatif
attribut nominal : valeurs
non ordonn ees
attribut ordinal : valeurs
ordonn ees
attribut `a valeur absolue
op erations
sur des at-
tributs de di erentes na-
tures
6
CHAPITRE 1. INTRODUCTION
num erique ne signie pas forc ement quantitatif : un code postal est num erique,
mais pas quantitatif.
1.2.3 Les di erentes natures de valeur dattribut
Il nest pas inutile ici de consacrer quelques lignes `a ce quest la valeur dun
attribut. Naturellement, cette valeur est cens ee repr esenter une certaine mesure
dune quantit e dans le monde. Ainsi, quand on dit quune couleur est (cid:28) bleue (cid:29),
cela signie que nous en avons une certaine perception visuelle qui est associ ee
`a ce que, en fran cais, on d esigne par le mot (cid:28) bleu (cid:29) ; elle aurait pu etre verte et
on laurait appel ee verte. Il est a priori impossible de comparer bleu et vert ; ce
sont deux couleurs, un point cest tout : la couleur est un attribut nominal. Si
on dit quaujourdhui, la temp erature est de 20
C, on
peut dire que la temp erature est plus elev ee aujourdhui quhier : cette fois-ci, on
peut comparer les deux valeurs dattributs, cela a un sens. Mais, si on se rappelle
ses cours de physique, on sait bien que ce 20 et ce 18 sont aussi arbitraires que
les mots (cid:28) bleu (cid:29) et (cid:28) vert (cid:29) : ces valeurs d ependent, notamment, des unit es
de mesure : la temp erature est un attribut ordinal. Maintenant, si on dit que
le nombre denfants de Paul est 2 et que Jacques a 3 enfants, dune part on
peut bien armer que Jacques a plus denfants que Paul et, de plus, ces deux
nombres 2 et 3 ne sont pas arbitraires : le nombre denfants est un attribut
absolu.
C et quhier, il faisait 18
(cid:176)
(cid:176)
Au-del`a de la distinction qualitatif/quantitatif, on voit donc appara 1tre des
distinctions plus subtiles entre des attributs dont les valeurs sont arbitraires
et incomparables (attribut nominal), des attributs dont la valeur est arbitraire
mais que lon peut comparer (attribut ordinal) et des attributs dont la valeur
nest pas arbitraire (attribut absolu).
Ces di erentes natures entra 1nent le fait que les op erations que lon peut
faire sur ces attributs ne sont pas les m emes : on ne peut pas soustraire deux
couleurs, on peut soustraire deux temp eratures mais on ne peut pas en faire le
rapport 1, alors que lon peut soustraire et faire le rapport du nombre denfants
de deux personnes.
Quand on fait des statistiques ou de la fouille de donn ees, on eectue de
nombreuses op erations arithm etiques ; hors, selon la nature de lattribut, ces
op erations sont licites ou non... Il importe donc de ne pas faire nimporte quel
calcul, dappliquer nimporte quel algorithme sans prendre garde aux attributs
sur lesquels on les eectue.
Par ailleurs, il faut observer un principe dind ependance du r esultat des
calculs par rapport aux unit es de mesure dans lesquelles sont exprim ees les
1. r e echissez-y par exemple sur cet exemple : si hier il faisait 20
C et quaujourdhui il
en fait 10, fait-il deux fois plus froid aujourdhui quhier ? et si aujourdhui il fait 0, il fait
combien de fois plus froid quhier ? et sil fait -5 ?
(cid:176)
1.2. QUEST CE QUUNE DONN EE ?
7
valeurs des attributs : il ny a aucune raison que linformation extraite dune base
de donn ees change selon quune longueur est exprim ee en millimetres, metres
ou ann ees-lumieres... De cette observation, on pose la regle suivante : on doit principe dind ependance
toujours sarranger pour que le r esultat dune analyse ne d epende pas de lunit e
par rapport aux unit es de
de mesure. (On verra une petite illustration de ce principe au chapitre 12.1,
mesure
section 12.1.1.)
En attendant, si ces quelques lignes vous ont mis en app etit, lisez .
1.2.4 Le bruit
Il importe de ne pas faire comme si toutes les donn ees ont une valeur con-
nue, et encore moins une valeur valide ; il faut donc g erer des donn ees dont
certains attributs ont une valeur inconnue ou invalide ; on dit que les donn ees
sont (cid:28) bruit ees (cid:29). La simple elimination des donn ees ayant un attribut dont la
valeur est inconnue ou invalide pourrait vider compl etement la base de donn ees !
On touche le probleme de la collecte de donn ees ables qui est un probleme pra-
tique tres dicile a r esoudre. En fouille de donn ees, il faut faire avec les donn ees
dont on dispose sans faire comme si on disposait des valeurs de tous les attributs
de tous les individus.
1.2.5 Di erentes t aches dextraction dinformation
Dans certains problemes (probleme de classication supervis ee), chaque
donn ee est aect ee dune caract eristique, par exemple une couleur. Supposons
que lensemble des couleurs possibles soit ni et de faible cardinalit e. Le
probleme de classication supervis ee consiste alors a pr edire la couleur dun
point quelconque etant donn e un ensemble de points color es. G eom etriquement,
cela revient `a trouver un moyen de s eparer les points les uns des autres, en
fonction de leur couleur. Sil ny a que deux couleurs, un simple (hyper)plan 2
peut sure `a les s eparer ; ceux dune certaine couleur sont dun c ot e de lhyper-
plan, les autres etant de lautre c ot e. Dans ce cas, les points sont lin eairement
s eparables (s eparables par un objet g eom etrique qui ressemble `a une droite,
un hyperplan pour etre plus pr ecis au niveau du vocabulaire). G en eralement,
des points dune couleur donn ee se trouvent du mauvais c ot e de lhyperplan.
Cela peut r esulter derreurs dans la valuation des attributs (on sest tromp e en
mesurant certains attributs, ou en attribuant sa couleur `a la donn ee) ; dans ce
2. Un hyper-espace est un espace ayant plus de 3 dimensions ; dans notre cadre, lespace
des donn ees est un hyper-espace `a P dimensions : chaque axe de coordonn ees est associ e
a un attribut. Un hyper-plan est un objet g eom etrique a P 1 dimensions. Dans le cas
particulier o`u P = 3, un hyper-plan est donc un objet en 2 dimensions, soit ce que lon
d enomme habituellement un plan. La notion dhyper-plan g en eralise celle de plan `a un espace
de dimension quelconque.
probl`eme de classication
supervis ee
8
CHAPITRE 1. INTRODUCTION
cas, les donn ees sont bruit ees. Cela peut aussi etre intrins`eque aux donn ees qui
ne peuvent pas etre s epar ees lin eairement. Il faut alors chercher `a les s eparer avec
un objet non hyperplanaire. Le probl`eme de classication sera d eni pr ecis ement
au chap. 2. On verra ensuite diverses approches a ce probleme :
construction dun mod`ele arborescent permettant de pr edire la classe
dune donn ee (cf. chap. 3) ou dun modele exprim e sous forme de regles
(cf. chap. 6). Dans ces deux cas, le mod`ele obtenu est interpr etable par
un humain ;
estimation directe de la classe dune donn ee en fonction des exemples :
une approche probabiliste au chap. 4 et une approche par cas au chap.
5. Dans ces deux cas, il ny a pas dapprentissage, pas de construction de
mod`ele ;
construction dun mod`ele non interpr etable par un humain : les r eseaux
de neurones au chap. 7 qui permettent de sattaquer a des problemes
dans lesquels les donn ees sont d ecrites par de tr`es nombreux attributs
(des images par exemple), ou les machines `a vecteurs supports au chap.
8. Dans ces deux cas, le mod`ele construit nest pas interpr etable par un
humain ; il est utilis e par lalgorithme pour estimer la classe de nouvelles
donn ees ;
construction dun mod`ele par s election de variables au chap. 9.
Enn, le chap. 10 terminera ce survol des m ethodes de r esolution du probl`eme
probl`eme de r egression
de classication en ouvrant quelques pistes.
probl`eme de segmenta-
tion
probl`eme de recherche de
r`egles dassociation
probl`eme destimation
Pour revenir `a notre exemple des points color es, dans dautres cas, lensemble
des couleurs possibles est inni non d enombrables (une valeur r eelle). On est
alors dans un probleme de r egression. On en parlera brievement au chap. 14.
Advertisement
Dans dautres problemes (probleme de segment...