Universit´e de Nantes Laboratoire d’Informatique de Nantes Atlantique ClassAdd, une proc´edure de s´election de k variables bas´ee sur une troncature -additive de l’information mutuelle et sur une Classification Ascendante Hi´erarchique en pr´e-traitement. ` THESE pr´esent´ee et soutenue publiquement le 11 mars 2009 pour l’obtention du grade de Docteur de l’Universit´e de Nantes Sp´ecialit´e Informatique par H´el`ene Daviet Composition du jury Rapporteurs : Youn`es Bennani, Professeur, LIPN-CNRS, Paris XIII Andr´e Hardy, Professeur, FUNDP, Namur Examinateurs : Yves Lechevallier, Directeur de recherche, INRIA Rocquencourt Isra¨el-C´esar Lerman, Professeur ´em´erite, IRISA, Rennes Directeur : Pascale Kuntz, Professeur, LINA, ´equipe COD, Nantes Co-encadrant : Ivan Kojadinovic, Maˆıtre de conf´erences (HDR), Universit´e d’Auckland N˚ED 503-040 E´cole Doctorale Sciences et Technologies de l’Information et des Mat´eriaux Mis en page avec la classe thloria. Remerciements Je remercie Pascale Kuntz et Ivan Kojadinovic de m’avoir encadrée pendant ces années de thèse. Merci Pascale de m’avoir toujours transmis ta confiance en la réussite de ces travaux même pendant cette longue dernière année « loin » de Nantes. Je remercie Younès Bennani et André Hardy d’avoir accepté d’être les rapporteurs de ce travail et Yves Lechevallier et Israël-César Lerman de faire partie du jury. Je remercie l’entreprise PerformanSe de m’avoir accueillie sous contrat CIFRE pen- dant trois ans et particulièrement, Jacques et Vincent Philippé et Serge Baquedano à l’origine de ce partenariat. Je remercie lescollègues dePerformanSe dont labonnehumeur m’apermis depasser trois années très agréables là-bas avec une pensée spéciale pour le compagnon de galère thésard, Philippe. Je remercie aussi les membres de l’équipe COD et ses thésards qui m’ont ouvert la voie : Julien, Jérôme, Manu, Nicolas et Bruno. Enfin,jeremercieStéphanesansquicettethèsen’auraitsûrementjamaisététerminée et aussi mon petit Pierre qui a été bien mignon pour laisser sa maman travailler. i ii À Stéphane et Pierre. iii iv Table des matières Table des figures xi Liste des tableaux xv Introduction 1 Chapitre 1 La sélection de variables 7 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1 Notations et prérequis . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Procédures de génération des sous-ensembles de variables candidats 10 1.2.1 Recherche complète . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Recherche avec une heuristique . . . . . . . . . . . . . . . . . 12 1.2.3 Génération aléatoire . . . . . . . . . . . . . . . . . . . . . . . 14 1.3 Fonctions d’évaluation des sous-ensembles . . . . . . . . . . . . . . . 14 1.3.1 Les méthodes filtres et les méthodes dépendantes du modèle 15 1.3.2 Les mesures de consistance . . . . . . . . . . . . . . . . . . . 18 1.3.3 Les mesures de précision . . . . . . . . . . . . . . . . . . . . 18 1.3.4 L’information mutuelle . . . . . . . . . . . . . . . . . . . . . 19 1.4 Un critère d’arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5 Algorithmes existants . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5.1 Les algorithmes d’ordonnancement de variables . . . . . . . . 20 1.5.2 Les algorithmes de construction du plus petit sous-ensemble de variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.5.3 L’utilisation de l’information mutuelle pour l’évaluation des sous-ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 v Table des matières Chapitre 2 L’information mutuelle en tant que mesure de dépen- dance 27 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.1 Notations et prérequis . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Les bases de la théorie de l’information . . . . . . . . . . . . . . . . 29 2.2.1 La notion d’incertitude . . . . . . . . . . . . . . . . . . . . . 29 2.2.2 L’entropie de Shannon . . . . . . . . . . . . . . . . . . . . . . 30 2.2.3 L’entropie relative . . . . . . . . . . . . . . . . . . . . . . . . 33 2.2.4 L’information mutuelle . . . . . . . . . . . . . . . . . . . . . 34 2.2.5 Généralisation de l’information mutuelle . . . . . . . . . . . . 36 2.3 Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3.1 Estimation classique . . . . . . . . . . . . . . . . . . . . . . . 37 2.3.2 Estimation bayésienne . . . . . . . . . . . . . . . . . . . . . . 37 2.4 D’autres mesures de liaison entre variables . . . . . . . . . . . . . . 38 2.4.1 Généralités sur les corrélations . . . . . . . . . . . . . . . . . 38 2.4.2 Les mesures de divergence . . . . . . . . . . . . . . . . . . . 39 2.4.3 Les mesures de dépendance . . . . . . . . . . . . . . . . . . . 40 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Chapitre 3 La classification de variables 45 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.1 Prérequis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2 La Classification Ascendante Hiérarchique . . . . . . . . . . . . . . . 48 3.2.1 Principe général . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.2 Complexité de l’algorithme . . . . . . . . . . . . . . . . . . . 52 3.2.3 Qualité d’une partition . . . . . . . . . . . . . . . . . . . . . 54 3.3 Application à la classification de variables . . . . . . . . . . . . . . . 57 3.3.1 LaméthodeAVL(AnalysedelaVraisemblancedesLiens)(Ler- man, 1981) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Chapitre 4 ClassAdd : un algorithme de sélection de variables 61 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.1 Pré-requis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 vi 4.1.1 Fonctions de Möbius, formule de Rota (1964) . . . . . . . . . 62 4.1.2 Les modèles log-linéaires . . . . . . . . . . . . . . . . . . . . 65 4.2 L’information mutuelle comme mesure de pertinence . . . . . . . . . 66 4.2.1 La k-additivité . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.3 Une classification hiérarchique des variables comme heuristique de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.3.1 Les critères de qualité d’une partition . . . . . . . . . . . . . 70 4.3.2 Algorithme général . . . . . . . . . . . . . . . . . . . . . . . 71 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Chapitre 5 Les données de l’étude 75 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.1 Les données de PerformanSe . . . . . . . . . . . . . . . . . . . . . . 77 5.1.1 Le contexte applicatif . . . . . . . . . . . . . . . . . . . . . . 77 5.1.2 L’outil PerformanSe Echo . . . . . . . . . . . . . . . . . . . . 78 5.1.3 Les activités Oriente . . . . . . . . . . . . . . . . . . . . . . . 81 5.1.4 Les données de l’APEC . . . . . . . . . . . . . . . . . . . . . 82 5.2 Des jeux de données classiques . . . . . . . . . . . . . . . . . . . . . 82 5.2.1 Données Soybean . . . . . . . . . . . . . . . . . . . . . . . . 82 5.2.2 Données Connect . . . . . . . . . . . . . . . . . . . . . . . . 83 5.2.3 Données Optdigits . . . . . . . . . . . . . . . . . . . . . . . . 83 5.2.4 Données Splice . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.2.5 Données Lung Cancer . . . . . . . . . . . . . . . . . . . . . . 83 5.2.6 Audiology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.3 Des données artificielles . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.3.1 Jeu à 15 variables . . . . . . . . . . . . . . . . . . . . . . . . 83 5.3.2 Jeu à 15 variables avec des relations entre trois variables . . 84 5.3.3 Jeu à 22 variables . . . . . . . . . . . . . . . . . . . . . . . . 84 5.3.4 Jeu à 35 variables . . . . . . . . . . . . . . . . . . . . . . . . 85 5.3.5 Bruitage des données . . . . . . . . . . . . . . . . . . . . . . 85 5.3.6 Taille des données . . . . . . . . . . . . . . . . . . . . . . . . 85 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 vii Table des matières Chapitre 6 Analyse de la robustesse 87 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.1 Qualité de l’approximation 2-additive . . . . . . . . . . . . . . . . . 89 6.1.1 Données non bruitées . . . . . . . . . . . . . . . . . . . . . . 90 6.1.2 Données légèrement bruitées . . . . . . . . . . . . . . . . . . 91 6.1.3 Données très bruitées . . . . . . . . . . . . . . . . . . . . . . 91 6.2 Résistance au bruit et à la taille de l’information mutuelle en tant que mesure de pertinence . . . . . . . . . . . . . . . . . . . . . . . . 93 6.2.1 Résistance au bruit . . . . . . . . . . . . . . . . . . . . . . . 94 6.2.2 Résistance à la taille . . . . . . . . . . . . . . . . . . . . . . . 94 6.3 Comparaison des indices de qualité d’une partition . . . . . . . . . . 95 6.4 Résistance au bruit et à la taille des données de l’indice de qualité . 97 6.4.1 Indice de la hauteur . . . . . . . . . . . . . . . . . . . . . . . 97 6.4.2 Indice du diamètre moyen . . . . . . . . . . . . . . . . . . . . 97 6.4.3 Indice de la distance au centre de la classe . . . . . . . . . . 98 6.4.4 Indice de Hubert . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.4.5 Indice de Calinski . . . . . . . . . . . . . . . . . . . . . . . . 99 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 Chapitre 7 Expérimentations numériques 103 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 7.1 Comparaison des trois algorithmes de génération de sous-ensembles 105 7.1.1 Les données à 22 variables . . . . . . . . . . . . . . . . . . . 105 7.1.2 Les données à 35 variables . . . . . . . . . . . . . . . . . . . 106 7.1.3 Lesdonnées réelles avecuneestimationclassiquedel’informa- tion mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 7.1.4 Les données PerformanSe . . . . . . . . . . . . . . . . . . . . 111 7.2 Validation des résultats obtenus . . . . . . . . . . . . . . . . . . . . 117 7.2.1 Protocole expérimental . . . . . . . . . . . . . . . . . . . . . 117 7.2.2 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . 118 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Conclusion et perspectives 121 viii