Approche pragmatique de la classification
· Arbres hiérarchiques
· Partitionnements
Jean-Pierre Nakache
Josiane Confais
TECHNIP
Préface, Gilbert SaportaIII
Avant-proposV
Introduction
1
Généralités
7
1. Distances et indices de similarité7
1.1. Distance d définie sur un ensemble E7
1.2. Similarité définie sur un ensemble E8
1.3. Dissimilarité définie sur un ensemble E8
2. Mesures de ressemblance entre individus8
2.1. Données numériques8
2.2. Données ordinales10
2.3. Données de fréquences10
2.4. Données binaires10
2.5. Données nominales11
2.6. Données mixtes12
3. Mesures de similarité entre variables12
3.1. Données numériques12
3.2. Données ordinales13
3.3. Données de fréquences13
3.4. Données binaires13
3.5. Données nominales14
3.6. Données mixtes15
4. Qualités d'une classification15
5. Préparation des données en vue d'une classification
15
Chapitre 1 Classification ascendante hiérarchique
17
1.1. Hiérarchie totale de parties d'un ensemble E17
1.2. Hiérarchie de parties indicée18
1.3. Arbre hiérarchique indicé18
1.4. Choix du nombre de classes par coupure de l'arbre19
1.5. Distances ultramétriques et arbres hiérarchiques21
1.5.1. Distances ultramétriques21
1.5.2. Boules ultramétriques21
1.5.3. Propriétés21
1.6. Equivalence entre hiérarchie indicée et distance ultramétrique22
1.6.1. Toute hiérarchie totale indicée HE permet de définir sur E une distance ultramétrique
22
1.6.2. A toute distance ultramétrique du définie sur E, on peut faire correspondre une hiérarchie totale indicée22
1.6.3. Conséquence de l'équivalence entre hiérarchie indicée HE et distance ultramétrique du23
1.6.4. Algorithme de Lerman25
1.7. Construction d'un arbre hiérarchique ascendant26
1.7.1. Algorithme de base26
1.7.2. Algorithme de Roux29
1.7.3. Axiome de la médiane34
1.7.4. Algorithme des voisins réciproques35
1.8. Algorithmes d'agrégation fondés sur un lien métrique35
1.8.1. Le critère du saut minimal35
1.8.2. Le critère du diamètre36
1.8.3. Le critère de la moyenne37
1.8.4. Le critère de Ward (perte d'inertie minimale)37
1.8.5. Application38
1.8.6. Mise à jour des distances: utilisation de la formule de Lance et Williams42
1.9. Algorithmes d'agrégation fondés sur la densité43
1.9.1. Méthode des k- plus proches voisins44
1.9.2. Méthode des noyaux uniformes44
1.9.3. Méthode EML44
1.9.4. Avantages et inconvénients des algorithmes hiérarchiques45
1.10. Comparaison de deux arbres hiérarchiques ascendants46
1.10.1. Ordonnance associée à une matrice des distances d entre individus d'un ensemble E: Od46
1.10.2. Définition mathématique d'une pré-ordonnance46
1.10.3. Graphe d'une ordonnance47
1.10.4. Ecart entre deux ordonnances48
1.10.5. Ecart entre deux hiérarchies ascendantes49
1.11. Algorithmes hiérarchiques avec obtention de classes de forme arbitraire49
1.11.1. Cure49
1.11.2. Rock52
1.11.3. Birch53
1.11.4. Chameleon57
1.11.5. Classification spatiale hiérarchique
60
Chapitre 2 Perte d'inertie minimale et saut minimal
65
2.1. Perte d'inertie minimale65
2.1.1. Passage d'une partition à la suivante67
2.1.2. Procédure d'agrégation suivant le critère de Ward67
2.1.3. Exemples illustratifs69
2.1.4. Application du critère de Ward aux données Ester et al73
2.2. Saut minimal77
2.2.1. Ultramétrique sous-dominante delta de la distance d77
2.2.2. Lien avec l'arbre de longueur minimale78
2.2.3. Construction de l'arbre de longueur minimale par l'algorithme de Kruskal78
2.2.4. Application numérique78
2.2.5. Représentation simultanée: arbre de longueur minimale et arbre hiérarchique81
2.2.6. Effet de chaîne81
2.2.7. Application aux données Ester et al
85
Chapitre 3 Classification hiérarchique descendante
89
3.1. Classification non supervisée: classes monothétiques89
3.1.1. Variables quantitatives89
3.1.2. Variables de nature mixte90
3.1.3. Variables binaires: méthode de Williams et Lambert90
3.1.4. Applications91
3.2. Classification non supervisée: approche conceptuelle95
3.2.1. Fonctions PU et CU95
3.2.2. Algorithme COBWEB100
3.2.3. Algorithme CLASSIT100
3.3. Classification de grandes collections de documents: algorithme PDDP100
3.4. Classification supervisée102
3.4.1. Méthode Cart103
3.4.2. Méthode Chaid
106
Chapitre 4 Classification par partition
109
4.1. Méthodes k-means109
4.1.1. Méthode des centres mobiles110
4.1.2. Méthode des nuées dynamiques113
4.2. Extension de la méthode k-means aux variables qualitatives ou mixtes114
4.2.1. Algorithme k-modes114
4.2.2. Algorithme k-prototypes115
4.2.3. Autres méthodes116
4.3. Méthode des k-medoids117
4.3.1. PAM117
4.3.2. Autres méthodes: Clara, Clarans, Findit120
4.4. Mélange de distributions
124
Chapitre 5 Classification conjointe (hiérarchie et partition) appliquée aux grands tableaux de données mixtes
129
5.1. Différentes étapes130
5.1.1. Codage des données sous forme disjonctive complète130
5.1.2. Analyse factorielle du tableau disjonctif complet130
5.1.3. Classification hiérarchique des individus repérés par leurs composantes factorielles131
5.1.4. Partition autour des centres mobiles et détermination des groupements stables132
5.1.5. Classification hiérarchique des groupements stables132
5.1.6. Consolidation de la partition finale132
5.2. Application de la classification conjointe: utilisation du logiciel SPAD133
5.3. Utilisation du logiciel SAS pour effectuer une classification conjointe146
5.3.1. Les outils proposés par SAS/STAT146
5.3.2. Les méthodes d'agrégation de la procédure Cluster146
5.3.3. Classification k-means avec la procédure Fastclus147
5.3.4. Enchaînement Fastclus - Cluster
147
Chapitre 6 Techniques particulières de classification pour le Data Mining
153
6.1. Méthodes de classification fondées sur la densité153
6.1.1. Méthode DBSCAN154
6.1.2. Méthodes dérivées de DBSCAN: GDBSCAN, OPTICS160
6.1.3. BRIDGE: utilisation conjointe de k-means et DBSCAN163
6.1.4. Autres méthodes164
6.2. Méthodes de classification fondées sur un modèle164
6.2.1. Approche neuronale: le modèle de Kohonen165
6.2.2. Autres approches probabilistes174
6.2.3. Approche basée sur la notion de fonction d'influence: DENCLUE
174
6.3. Méthodes fondées sur le quadrillage de l'espace176
6.4. Classification simultanée des individus et des variables179
6.4.1. Ré-ordonnancement du tableau après classification séparée des lignes et des colonnes du tableau179
6.4.2. Ré-ordonnancement des lignes et des colonnes d'un tableau de contingence182
6.5. Méthode d'agrégation de relations binaires
184
Chapitre 7 Nombre de classes à retenir
189
7.1. Utilisation de l'échelle des similarités associée à un arbre hiérarchique189
7.2. Autres indices graphiques190
7.2.1. Indices fondés sur la somme de carrés190
7.2.2. Indices fondés sur des pseudo-statistiques192
7.3. Indice dérivé d'une classification fondée sur la densité: BIC195
7.4. Graphique «silhouette»196
7.5. Autres indices201
7.6. Comparaison de deux partitions
201
Chapitre 8 Caractérisation des classes
207
8.1. Caractérisation unidimensionnelle207
8.1.1. Caractérisation par des variables illustratives207
8.1.2. Extension aux variables actives208
8.2. Application: données Cancer209
8.2.1. Description des classes retenues211
8.2.2. Valeurs-test213
8.3. Autres caractérisations unidimensionnelles213
8.3.1. Graphiques en étoiles214
8.3.2. Graphiques des profils214
8.4. Caractérisation multidimensionnelle214
8.4.1. Représentation graphique des variables et classes sur le meilleur plan factoriel214
8.4.2. Utilisation d'une méthode explicative multidimensionnelle
217
Chapitre 9 Classification d'un ensemble de variables
219
9.1. Procédure Varclus220
9.1.1. Algorithme220
9.1.2. Exemple illustratif221
9.1.3. Cas de variables binaires à classer: application aux données NHP225
9.1.4. Cas de variables mixtes à classer: application aux données Cancer226
9.2. Variante de VARCLUS: méthode de Qannari et Vigneau230
9.3. Méthode de Lerman236
9.4. Méthode de Bertin
236
Logiciels et algorithmes
241
Références bibliographiques247
Index257