Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

UNIVERSITÉ PARIS 13 THÈSE Présentée par Sébastien GUÉRIF pour obtenir le titre

UNIVERSITÉ PARIS 13 THÈSE Présentée par Sébastien GUÉRIF pour obtenir le titre de Docteur de l’Université Paris 13 Spécialité : Informatique Réduction de dimension en Apprentissage Numérique Non Supervisé Soutenue publiquement le 11 décembre 2006 devant le jury composé de Directeur : Pr. Younès BENNANI, LIPN, Université Paris 13 Rapporteurs : Pr. Cyrille BERTELLE LITIS, Université du Havre Pr. Gilles VENTURINI LIUT, Ecole Polytechnique de l’Université de Tours Examinateurs : Pr. Pascale KUNTZ LINA, Ecole Polytechnique de Nantes Pr. Magnus S. MAGNUSSON HBL, University of Iceland Pr. Jean-Daniel ZUCKER LIM&Bio, Université Paris 13 Invité : M. Emmanuel ECOSSE INSERM, Paris M. Eric JANVIER Numsight, Boulogne Billancourt favet neptunus eunti RÉDUCTION DE DIMENSION EN APPRENTISSAGE NUMÉRIQUE NON SUPERVISÉ Dimension Reduction for Unsupervised Numerical Learning Sébastien GUÉRIF ⊲ ⊳ Université de Paris Nord Sébastien GUÉRIF Réduction de dimension en Apprentissage Numérique Non Supervisé xii+116 p. Remerciements J’adresse toute ma reconnaissance à Younès Bennani qui m’a permis de réaliser cette thèse pour sa disponibilité, ses encouragements, ses conseils et sa conﬁance. Je remercie Claude Baudoin, professeur à l’Université Paris 13, pour sa disponibilité, ses encourage- ments et nos échanges toujours très enrichissants. J’adresse mes sincères remerciements à Monsieur Cyrille Bertelle, professeur à l’Université du Havre, et Monsieur Gilles Venturini, professeur à l’Université de Tours, qui ont accepté d’évaluer ce travail. Je remercie également Pascale Kuntz, professeur à l’Université de Nantes, Magnus Magnusson, pro- fesseur à l’Université d’Islande, et Jean-Daniel Zucker, professeur à l’Université Paris 13, d’avoir accepté de participer à mon jury de thèse. Je tiens à consacrer quelques lignes aux personnes sans qui cette aventure n’aurait vraisemblement jamais commencé : Mohamed Quafafou, qui avait accepté d’encadrer mon mémoire de maîtrise et qui m’a fait connaître l’Université Paris 13, Daniel Kayser et Henry Soldano pour leur soutien lorsque cette thèse n’était encore qu’un projet lointain. J’adresse ma gratitude à la société Numsight qui a ﬁnancé la deuxième moitié de ce travail, et mes remerciements à mes anciens collègues : Eric Janvier, Marc Kerslake, Thierry Couronne, Emmanuel Ecosse et tous les autres qui sont trop nombreux pour être tous cités. La réalisation d’une thèse s’appuie aussi sur un environnement qui est essentiel et qui va au-delà des murs de notre laboratoire ; je tiens à remercier tous les membres de notre laboratoire, mais également Colette et Daniel du service de reprographie, Faiza pour ces encourageants quotidiens. Je consacre une mention particulière à Hakima et Anass pour leur soutien à un moment où j’en avais grand besoin, à Sophie pour sa compagnie nocturne et dominicale, à Céline et Dominique pour ces nombreuses pauses café qui sont toujours l’occasion d’échanges tant personnels que scientiﬁques et à Françoise, Touria et Antoine pour avoir accepté de partager leur bureau avec l’horrible bavard que je suis. “Last but not least”, je remercie ma famille et mes amis pour leur soutien et leurs encourageants. Trop nombreux sont ceux que je n’ai pu nommés, qu’ils trouvent ici l’expression de ma gratitude. Résumé La classiﬁcation automatique - clustering - est une étape importante du processus d’extraction de connaissances à partir de données (ECD). Elle vise à découvrir la structure intrinsèque d’un ensemble d’objets en formant des regroupements - clusters - qui partagent des caractéristiques similaires. La complexité de cette tâche s’est fortement accrue ces deux dernières décennies lorsque les masses de données disponibles ont vu leur volume exploser. En effet, le nombre d’objets présents dans les bases de données a fortement augmenté mais également la taille de leur description. L’augmentation de la dimension des données a des conséquences non négligeables sur les traitements classiquement mis en oeuvre : outre l’augmentation naturelle des temps de traitements, les approches classiques s’avèrent parfois inadaptées en présence de bruit ou de redondance. Dans cette thèse, nous nous intéressons à la réduction de dimension dans le cadre de la classiﬁcation non supervisée. Différentes approches de sélection ou de pondération de variables sont proposées pour traiter les problèmes liés à la présence d’attributs redondants ou d’attributs fortement bruités : • Nous proposons d’abord l’algorithme µ-SOM qui limite l’effet de la présence d’attributs redon- dants en calculant une pondération des attributs à partir d’une classiﬁcation simultanée des objets et des attributs. • Nous présentons ensuite une approche intégrée – embedded – de sélection de variables pour la classiﬁcation automatique qui permet de découvrir à la fois le nombre de groupes d’objets présents dans les données mais aussi un sous-ensemble d’attributs pertinents. • Nous terminons en présentant l’algorithme ωβ-SOM qui introduit une pondération des attributs dans la fonction de coût des cartes auto-organisatrices - Self Organizing Maps - qui est ensuite optimisée itérativement en alternant trois étapes : optimisation des affectations, optimisation des prototypes et optimisation des poids. La pondération obtenue après convergence est ensuite utilisée pour proposer une approche ﬁltre - Filter - de sélection de variables. Nous concluons cette thèse en indiquant les limites des approches proposées et envisageant quelques axes à développer lors de la poursuite ces recherches. Sommaire 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 I Etat de l’art 2 Classiﬁcation non-supervisée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Concepts et déﬁnitions utiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Qu’est-ce qu’une classiﬁcation ? . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.2 Qu’est-ce qu’un groupe d’objets similaires ? . . . . . . . . . . . . . . . . . . . . 6 2.1.3 Comment représenter un objet ? . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Quelques approches classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 Méthodes hiérarchiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2 Nuées dynamiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.3 Modèles de mélange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Approche neuromimétique : les cartes auto-organisées de Kohonen . . . . . . . . . . . . 12 2.3.1 Sources historiques et principes . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.2 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.3 Algorithme d’apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4 Connaissances du domaine et contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4.1 Contraintes sur les groupes : forme et taille . . . . . . . . . . . . . . . . . . . . 15 2.4.2 Contraintes sur les objets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4.3 Contraintes sur les attributs . . . . . . . . . . . . . . . . . . . . . . . . uploads/Litterature/ guerif2006these-pdf.pdf