Je suis maître de conférences à l'Université Paris 13 et je suis membre du Laboratoire d'Informatique de l'université de Paris Nord (LIPN) où j'effectue mes recherches au sein de l'équipe Apprentissage Artificiel & Applications (A3). J'effectue mon service d'enseignement au Département Informatique de l'Institut Galilée

J'ai réalisé ma thèse de doctorat sous la direction scientifique du Pr.Younès Bennani dans le cadre d'une convention CIFRE entre la société Numsight et l'Université Paris 13. J'ai défendu ma thèse intitulée "Réduction de Dimension en Apprentissage Numérique Non Supervisé" le 11 décembre 2006 devant le jury composé de

qui m'a décerné le titre de docteur de l'université Paris 13 avec la mention Très Honorable.

Résumé de mes activités de recherche

L'évolution de l'informatique et des technologies de stockage a entraîné une explosion du volume des données disponibles et ce phénomène a été renforcé par la prise de conscience des décideurs de la valeurs des connaissances potentielles que renferment implicitement leurs bases de données. Néanmoins, en l'absence de méthodes d'exploration et d'analyse adaptées, ces grandes masses de données n'apportent aucune plus-value et le développement de ces outils de traitements est un des enjeux fondamentaux de l'extraction de connaissances à partir de données. La réduction de l'espace de description et la réduction du nombre d'individus sont deux approches duales qui apportent des éléments de réponse ce problème; on les regroupe souvent sous l'appellation « réduction de dimensions ». Je me suis intéressé à la pondération et à la sélection de variables dans le contexte de la classification non supervisée. Une première approche limite l'effet de la présence d'attributs redondants en utilisant un mécanisme de pondération à l'algorithme d'apprentissage des cartes auto-organisées. Nous avons ensuite proposé une méthode de classification à deux niveaux qui intègre une procédure de sélection de variables pertinentes par rapport à une partition dont le nombre de groupes est fixé automatiquement. Enfin, nous proposons différentes techniques de sélection de variables basées sur une pondération obtenue à l'aide de notre extension de l'algorithme de l'algorithme W-KMeans proposé par Huang et al. au cas des cartes auto-organisées. Ces différentes contributions nous ont permis d'identifier différents axes de poursuites de nos recherches qui nous semblent pertinents : la recherche de relations causales et le traitement des masses de données multimodales.

Mots-clefs

Contexte et Problématique

L'évolution de l'informatique et des technologies de stockage a entraîné une explosion du volume des données disponibles et ce phénomène a été renforcé par la prise de conscience des décideurs de la valeurs des connaissances potentielles que renferment implicitement leurs bases de données. Ainsi, une société de téléphonie mobile, un groupe bancaire ou une société d'assurance sont généralement tous très intéressés par l'évaluation précise du risque qu'un client client passe à la concurrence. De même, dans le domaine de la santé publique, de nombreuses pathologies nécessitent une détection précoce pour être prises en charge efficacement, il serait donc important de pouvoir identifier précisément les patients à risque. Néanmoins, les grandes masses de données disponibles n'apportent aucune plus-value en absence de méthodes d'exploration et d'analyse adaptées à leur volume. Mettre en place des outils de traitements permettant d'expliciter les connaissances implicites disponibles dans ces données est fondamental et représente un des enjeux majeurs du domaine de l'extraction de connaissances à partir de données. La réduction de l'espace de description et la réduction du nombre d'individus sont deux approches duales qui apportent des éléments de réponse ce problème; on les regroupe souvent sous l'appellation « réduction de dimensions ». Leurs objectifs est de sélectionner ou d'extraire un sous-ensemble optimal de caractéristiques et/ou d'individus pour un critère fixé auparavant. En éliminant les informations non pertinentes ou redondantes selon le critère utilisé, ces approches permettent de réduire la taille de l'ensemble des données selon ses deux dimensions, pour le rendre plus représentatif du problème. En effet, les principaux objectifs de la réduction de la dimension sont :

Les algorithmes d’apprentissage artificiel requièrent typiquement peu de caractéristiques ou de variables très significatives caractérisant le phénomène étudié. Dans le domaine de la reconnaissance de formes ou de la fouille de données, introduire un module de réduction de l'espace de description, pour éliminer toute information inconséquente et redondante, améliore généralement l'erreur finale du système qui est directement liée aux nombre de caractéristiques utilisées. Soulignons que l’importance de chaque caractéristique dépend de la taille de la base d’apprentissage (pour un échantillon de petite taille, l’élimination d’une caractéristique importante peut diminuer l’erreur). Il faut aussi noter que des caractéristiques individuellement peu pertinentes peuvent être très informatives si on les utilise conjointement; l'exemple du XOR illustre parfaitement ce problème.

La classification non supervisée est une des méthodes qui permet de réduire le nombre d'individus soit en remplaçant chaque groupe par un ou plusieurs représentants, soit choisissant un mode de représentation plus adapté. Dans le premier cas, les représentants sont, soit issus de la population initiale (sélection d'instance), soit des individus prototypes ou individus moyens. Un changement de langage de représentation intervient par exemple dans le cas des modèles de mélange où chaque groupe est représenté par sa probabilité à priori et une loi de distribution; une discrétisation de l'espace où un groupe est représenté par son effectif et un produit cartésien d'intervalles peut être vu comme un cas particulier du cas précédent. La classification est souvent utilisée pour faciliter l'apprentissage et diminuer le temps de traitement; c'est notamment le cas lorsqu'on adopte une approche de classification à deux niveaux, ou que l'on sélectionne les instances situées autour de la frontière de décision dans un problème de classement.

Positionnement et Motivations

La réduction de la dimension est un problème complexe qui a été largement étudié dans le cas de l'apprentissage supervisé. Dans le cadre de ma thèse, je me suis intéressé à ce problème dans le cadre de l'apprentissage numérique non supervisé où l'absence d'étiquette rend la difficulté encore plus grande. Mes travaux se positionnent dans le cadre de l'analyse exploratoire de données en grandes dimensions et je me suis focalisé sur la classification automatique à partir de cartes auto-organisées (Kohonen, 2001) qui permettent en outre de réduire le nombre d'individus à étudier et de visualiser les proximités inter-groupes. Ensuite, bien que parfois complémentaires, deux grandes approches de réduction de l'espace de descriptions s'opposent du points de vue de leurs objectifs : l'extraction de caractéristiques et la sélection de variables.

L'extraction de caractéristiques se révèle souvent plus efficace en apprentissage supervisé lorsqu'on cherche à construire un classificateur mais demande à l'utilisateur un effort important d'interprétation pour comprendre la nouvelle représentation de ses données. Ensuite, d'une part, les techniques classiques utilisables en apprentissage non supervisé comme l'analyse factorielle en composantes principales (ACP), ou le positionnement multidimensionnel (MDS) sont limitées par leur caractère linéaire. D'autre part, les méthodes non linéaires comme Isomap ou le plongement localement linéaire (LLE) ont une complexité trop importante pour être utilisées sur de grandes masses de données; ce dernier point est toutefois à nuancer depuis l'apparition récente de méthodes incrémentales de calcul. Ainsi, je me suis orienté vers l'approche par sélection de variable qui permet une compréhension directe des résultats par l'utilisateur sans avoir à fournir d'effort particulier pour interpréter de nouveaux attributs. Par ailleurs, dans certains domaine d'application, le recueil des données peut être coûteux et dans ce cas une approche par sélection de variables permet également de réduire les coûts.

Contributions et Résultats

Traitement la redondance par pondération

Les bases de données réelles contiennent souvent beaucoup de redondance qui est parfois souhaitable mais qui doit être prise compte lors de l'analyse pour ne pas biaiser les conclusions. D'une part, cette redondance permet parfois de détecter les valeurs aberrantes et les individus atypiques. A titre illustratif, lors d'une étude de marché basée sur une enquête auprès de consommateurs, certains peuvent répondre de manière incohérente et il est important de pouvoir le détecter : un moyen simple consiste à introduire de la redondance dans les questionnaires. D'autre part, elle facilite aussi la prise en compte des valeurs manquantes (Cottrell et al., 2003) qui sont fréquentes lorsqu'on travaille sur des données réelles. Nous avons proposé une modification de l'algorithme des cartes auto-organisées qui prennent en compte explicitement la présence de variables redondantes en intégrant un mécanisme de pondération qui en limite l'effet.

Notre approche baptisée « μ-SOM » se base sur une classification croisée des individus et des variables1 (Guérif et al., 2005); ces dernières sont représentées par des vecteurs dont chaque dimension correspond à un individus prototypes ce qui permet d'une part une grande robustesse aux valeurs aberrantes (Vesanto et al., 1999). Un poids potentiel attribué à chaque variable prototype est partagé entre les variables qu'elle représente limitant ainsi l'effet de la redondance. Cette approche permet également de détecter le bruit qui correspond à des variables non structurantes. En effet, ces dernières sont mal quantifiées et leur variance intra-classe est forte ce qui conduit à des valeurs proche de zéro pour l'ensemble des unités; ainsi, l'ensemble de ces variables est représenté par une seule variables prototypes et leur poids est ainsi fortement affaibli. Cette approche a été évaluée avec succès sur de nombreux jeux de données artificielles et sur des données réelles issues du domaine du marketing.

Sélection conjointe de variables et du nombre de groupes

Bien que de nombreuses heuristiques aient été proposées pour la sélection du nombre de groupes en classification automatique, ce point reste un problème ouvert. Les plupart des approches proposées reposent, soit sur des critères de qualité qui font l'hypothèse qu'une bonne classification comporte des groupes compacts et bien séparés, soit sur le principe de la longueur de description minimale (MDL). Nous avons proposé une approche de sélection de variables intégrée au processus à un algorithme classification à deux niveaux2 (Guérif et Bennani, 2006). Le premier niveau utilise l'algorithme d'apprentissage des cartes auto-organisées, et le second niveau correspond à la segmentation de la carte par l'algorithme des kmeans en faisant intervenir l'indice de Davies-Bouldin pour le choix du nombre de groupes (Vesanto et al., 2000).

Nous guidons une procédure de type backward à l'aide d'une première de pertinence individuelle des variables qui correspond au maximum de leurs valeurs test (Morineau, 1984) sur l'ensemble des groupes. Une seconde mesure de pertinence collective est utilisée pour vérifier que la suppression de la variable n'entraîne pas de remise en cause des groupes identifiés : on regarde pour cela la différence des valeurs prise par l'indice de Davies-Bouldin pour un même découpage avec et sans la variable. La statistique lambda de Wilks est utilisée comme critère d'arrêt (Cibas, 1996). Bien que cette approche ait été validée sur des données artificielles, nous n'avons pas poursuivi dans cette voie car d'une part sa complexité est prohibitive lorsqu'on travaille sur plusieurs milliers d'individus et d'autre part, le critère d'arrêt utilisé n'est plus utilisable lorsque la dimension de l'espace de description dépasse le nombre d'individus.

De la pondération à la sélection de variables

L'expérience des deux approches précédentes nous a amené à penser qu'une approche de sélection de variables basées sur une pondération serait à la fois plus souple et plus efficace du poids de vue calculatoire. Nous avons étendu l'algorithme ω-kmeans proposé par (Huang et al., 2005) au cas des cartes auto-organisées et nous avons baptisée notre algorithme « ω-SOM ». La distance euclidienne classique utilisée pour la recherche de l'individu prototype le plus proche de celui présenté à la carte est remplacée par une distance euclidienne pondérée et les poids des différentes dimensions sont optimisées de manière à chaque itération. A la fin de l'apprentissage, la pondération indique la contribution relative des différentes dimensions et peut être utilisée comme mesure de pertinence dans une procédure de sélection de variables.

Nous avons proposé différentes approches de sélection de variables guidée par la pondération. Notre première approche3 (Guérif, 2006) combine une recherche de type backward et un test de Wilcoxon le rang des distances entre les individus et leur représentant; comme toutes les approches de type backward, elle souffre d'un manque d'efficacité du point de vue calculatoire. Les nombreuses expérimentations réalisées ont montré que la procédure de recherche s'arrêtait systématiquement lors d'une « augmentation brutale » du poids candidat à l'élimination; nous avons alors proposé une recherche basée sur un seuil du rapport entre deux poids consécutifs lorsqu'on les considère dans l'ordre décroissant4 (Guérif et Benanni, 2007ab). Ces différentes approches ont été validées sur différents de jeux de données artificiels de dimension et de complexité variables. Les résultats obtenus sont très satisfaisant puisque sans utiliser d'information sur la classe des individus nous obtenons des performances comparables à celles des méthodes supervisées.

Synthèse et Améliorations envisagées

Nous avons proposé différents algorithmes de pondération et de sélection de variables pour l'apprentissage numérique non supervisé; la qualité des solutions obtenues lors de nombreuses expérimentations sont tout à fait satisfaisantes mais nous envisageons malgré tout d'améliorer encore nos approches. Ainsi, nous pensons que les performances de l'algorithme μ-SOM pourrait être améliorées en remplaçant la distance euclidienne utilisée pour comparer les profils de variables par une mesure d'information mutuelle. Ensuite, l'utilisation d'une pondération locale plutôt que globale dans l'algorithme ω-SOM permettrait sans nul doute d'accroître ses performances et une hybridation avec l'algorithme μ-SOM offrirait un gain de performance notable du point de vue calculatoire. Enfin, au delà de ces travaux à court terme, nous avons également identifié différents axes de poursuites de ces recherches à plus long termes qui nous semblent pertinents : la recherche de relations causales et le traitement des masses de données multimodales. Ces deux points seront développés plus loin dans mon projet de recherche.

Références