CEA, LITEN,
Laboratoire des systèmes solaires (L2S).
50 av. du Lac Léman,
73375 LE BOURGET DU LAC - CEDEX

 

Mon travail concerne la fouille de données (data mining) à l’aide de méthodes supervisées et non-supervisées, paramétriques et non-paramétriques. Mon intérêt se focalise en particulier sur les données de grande dimension (décrites par de nombreuses variables).


lien vers la page de DD-HDS               
            lien vers la page de Rankvisu               

Les espaces de grande dimension présentent des propriétés peu intuitives quoique bien connues (habituellement regroupées sous le terme de « fléau de la dimension »). Ces phénomènes peuvent rendre problématique l’utilisation de la majorité de l’arsenal classique des méthodes d’analyse de données lorsque les variables sont trop nombreuses. Le travail présenté ici s’attache à l’extraction d’information à partir de données de grande dimension dont les variables sont liées par des relations non-linéaires complexes. Je m'intéresse en particulier aux techniques dites de "réduction de dimension" (aussi désignées par les termes de "mapping" ou de "multi dimensional scaling") qui permettent de visualisation des données.

Les travaux présentés ici sont le plus souvent des réponses apportées à des problèmes concrets. Ils résultentd'analyses menées sur des données réelles que l'on m'a soumises (données génomiques, protéomiques, sociologique, etc). Aujourd'hui, je travaille dans le domaine de la production et l'utilisation d'éléctricité photovoltaïque à l'Institut National de l'Energie Solaire (INES).



 1.   Le fléau de la dimension

Confrontée à des données de grande dimension, l’intuition est souvent prise en défaut. En effet elle se base sur notre expérience d’un monde tridimensionnel dont les propriétés diffèrent largement des propriétés des espaces de grande dimension (décroissance de l’hypervolume de la boule unité, désertification de l’espace, dépeuplement du centre des hypervolumes, etc). Parmi ces propriétés déconcertantes, le phénomène de concentration de la mesure joue un rôle particulièrement important. La concentration de la mesure est la tendance des distributions de distances euclidiennes à se resserrer autour de la distance moyenne pour tendre vers une loi de Dirac lorsque la dimension tend vers l’infini. De ce fait, il devient de plus en plus difficile de distinguer les « courtes » et les « longues » distances quand la dimension augmente. Généralement, ce phénomène perturbe considérablement l’analyse de données, en particulier les méthodes non-linéaires de réduction de dimension. En effet, celles-ci ont pour point commun de s’appuyer sur les courtes distances.


 2.   Méthodes de réduction de la dimension

   DD-HDS: Méthode basée sur les distances
Le but classique des méthodes non-linéaires de réduction de dimension est d’exprimer l’organisation spatiale des données dans un espace vectoriel euclidien de dimension réduite en conservant les voisinages (un exemple est présenté figure 1). Deux failles ont été identifiées dans les fonctions d’évaluation des réductions de dimension. Nous proposons donc une nouvelle méthode baptisée DD-HDS pour Data-Driven High Dimensional Scaling qui corrige ces défauts [a4, c1, d3, d4, d5].
1) La proposition largement partagée est de chercher à conserver les distances entre données en favorisant la préservation des distances courtes. Pour cela un « stress » évalue les différences entre les distances dans l’espace d’origine et dans la représentation en pondérant cette différence pour favoriser les distances courtes. Deux solutions existent : la pondération selon les distances dans l’espace d’origine, ou selon les distances dans la représentation. Ces deux solutions pénalisent soit les « faux-voisinages » (données éloignées représentées comme proches) soit les « déchirements » (données proches représentées comme éloignées). Dans le cadre de DD-HDS, la pondération s’appuie sur le minimum entre la distance dans l’espace d’origine et dans la représentation de façon à pénaliser simultanément les « faux-voisinages » et les « déchirements ».
2) La pondération est destinée à donner un poids plus important aux distances courtes qu’aux distances longues lors du calcul du stress. Classiquement, cette fonction est l’inverse de la distance (ou l’inverse de la distance au carré). Pourtant, cette fonction est inappropriée lorsque la dimension des données est grande du fait de la concentration de la mesure. Nous proposons une fonction de pondération en cumulative de gaussienne inversée ajustée sur la distribution des distances de façon à ce que les poids donnés aux distances courtes et longues soient effectivement différents.
De plus, l’optimisation des positions des données dans l’espace de représentation est obtenue par « Force-Directed Placement » pour sa capacité à éviter les minima locaux. De fait, DD-HDS se montre très efficace pour la représentation des données quelle que soit leur dimension.

Figure 1 :  
Carte du monde en 2 dimensions obtenue par projection DD-HDS.
A gauche : données en 3 dimensions. A droite la représentation par DD-HDS.
La couleur des points (à droite) exprime la qualité de conservation des distances entre le point et ses voisins (plus le point est clair, mieux les distances sont conservées).


 RankVisu: Méthode basée sur les rangs de voisinage
Dans les cas difficiles, il arrive que la préservation des distances entre les données étudiées ne puisse pas se faire sur un expace de faible dimension quelque soit la méthode utilisée.  Dans ce type de situation, nous proposons d'utiliser une méthode de réduction s'appuyant sur une information plus faible que les distances: les rangs de voisinage. Cette méthode baptisée RankVisu montre une étonnant capacité à mettre en évidence les grappes de données.

 3.   Choix de la métrique pour comparer des données

La plus grande partie des analyses que nous menons s'appuie sur la notion de proximité et est, par conséquent, tributaire d'une métrique. Il convient donc de la choisir avec soin. Nous pouvons nous guider sur la capacité à révéler les connaissances préalables relatives aux données pour faire ce choix [d2, e3]. Notons que ce travail est complémentaire des représentations non-linéaires. En effet, au contraire de la plupart des méthodes linéaires qui font implicitement le choix de la métrique euclidienne, beaucoup de méthodes non-linéaires de réduction de dimension peuvent aisément s'accommoder d'autres métriques.

 4.   Evaluation local des mappings

Il est essentiel de s'intéroger sur ce qu'un utilisateur peut tirer comme information de la présentation d'une carte. Poser cette question revient à se demander quels éléments sont dignes de foi et quels structures observées ne sont que le résultat d'erreur de représentation (artefacts). Il apparait que sans réponse à cette question, les mappings n'ont pas d'interet pratique. Afin de rendre utilisable les représentations issues des méthodes de réduction de dimension, nous proposons un outil d'évaluation local basé sur un code coleur bidimensionnel.