Visualisation et ECD
Notre activité de recherche est concentrée sur la visualisation et l'extraction de connaissances dans les données. L'extraction de connaissances
dans les données peut être définit comme le processus non trivial de découverte de connaissances nouvelles, potentiellement utiles et compréhensibles
dans les données. La fouille de données concerne plus précisément le coeur de ce processus : la découverte de connaissances nouvelles. Ce domaine
relativement récent d'extraction de connaissances dans les données regroupe des travaux de plusieurs domaines de recherche : les bases de données,
l'apprentissage symbolique automatique, les statistiques, l'analyse de données et la visualisation.
Dans les approches usuelles, la visualisation n'intervient en général que lors de deux étapes particulières du processus de fouille de données :
- dans l'une des toutes premières étapes pour "voir" les données ou leur distribution,
- dans l'une des toutes dernières étapes du processus pour prendre connaissance des résultats.
Entre ces deux étapes il y a en général exécution d'un algorithme automatique de fouille de données.
Le but de nos travaux de recherche est d'augmenter le rôle de la visualisation dans ce processus. Ceci peut être mené à bien de plusieurs façons :
- en faisant collaborer des méthodes visuelles avec les méthodes automatiques soit en pré-traitement soit en post-traitement,
- en remplaçant l'algorithme automatique de fouille de données par un algorithme graphique interactif, on parle alors de fouille visuelle de données ou
"Visual Data Mining",
- en augmentant les interactions.
Par ailleurs une limite connue des algorithmes de visualisation est la difficulté à traiter des ensembles de
données de grandes tailles (en nombre d'individus ou lignes de la base de données ou en nombre d'attributs
ou colonnes de la base de données). L'approche coopérative utilisant simultanément des algorithmes automatiques
et graphiques est un excellent moyen de pouvoir dépasser les limites des outils de visualisation, on parle de
"passage à l'échelle".
Nous allons présenter les travaux que nous menons dans ces directions.
Collaboration entre méthodes graphiques interactives et méthodes automatiques
Dans le processus d'extraction de connaissances à partir de données, il y a au moins deux moyens de faire collaborer les méthodes automatiques avec
des méthodes graphiques interactives. Il est possible d'utiliser les méthodes graphiques en pré-traitement de l'algorithme automatique ou en post-traitement
de ce même algorithme.
Pré-traitement graphique
Un exemple de pré-traitement est celui qui consiste à préparer les données avant d'utiliser un algorithme d'induction d'arbre de décision. Le but d'un tel
algorithme est de construire un modèle des données à partir d'un ensemble de données dont la classe est connue a priori, puis à partir de ce modèle, de
retrouver la classe d'un nouvel individu. La plupart des algorithmes d'arbres de décision ne savent faire que des coupes univariées (ne faisant intervenir
qu'un seul attribut (colonne) des données, la coupe est parallèle aux axes). Dans le cas d'une frontière oblique, celle-ci sera approximée par des coupes
successives formant un "escalier". L'arbre obtenu aura alors beaucoup de nœuds et sera difficilement interprétable. Une solution est alors de visualiser
ces données, de tracer interactivement la coupe oblique puis de calculer un nouvel attribut qui sera la distance à la droite tracée.
Prenons un exemple sur un petit set de données : Drug d'un logiciel commercial, il comporte 6 attributs et 200 individus.
Sur les données initiales, l'arbre de décision obtenu avec C4.5 donne 7,5% d'erreur avec un arbre de taille 19 (en nombre de nœuds). Lorsque l'on créé le
nouvel attribut, l'arbre obtenu avec C4.5 donne alors 0% d'erreur avec un arbre de taille 10. Ce simple pré-traitement graphique permet d'une part
d'améliorer la compréhensibilité des résultats (la taille de l'arbre a diminuée) et d'autre part d'améliorer le taux de précision de l'algorithme.
Post-traitement graphique
Dans le cas de post-traitement graphique, l'algorithme de visualisation est utilisé pour aider l'utilisateur à comprendre le résultat obtenu par l'algorithme
automatique. L'idée ici est de trouver une représentation graphique qui permette d'expliquer plus facilement les résultats obtenus par les algorithmes de
classification. Nous allons prendre deux exemples dans le cadre de la classification supervisée : l'un traitant les résultats des algorithmes d'arbre de décision,
l'autre traitant les résultats des SVM (Support Vecteur Machine ou Séparateur à Vaste Marge).
Ces quelques outils illustrent l'intérêt de faire coopérer entre elles des méthodes automatiques et des méthodes graphiques interactives. La compréhensibilité
des résultats est ainsi accrue et la précision des algorithmes automatiques peut être facilement améliorée.
Fouille visuelle de données
La dernière possibilité pour augmenter la part de la visualisation dans les outils de fouilles de données est de remplacer l'algorithme automatique de fouille de
données par un algorithme graphique interactif. On parle alors de fouille visuelle de données. L'utilisateur d'un tel système est le spécialiste des données pas
un expert en fouille ou analyse de données. Ce type d'approche, relativement récent présente aux moins les avantages suivants :
- on peut bénéficier de l'expertise du domaine tout au long du processus de fouille,
- la confiance dans le modèle obtenu et sa compréhension sont accrues puisque l'utilisateur a participé à la création du modèle en question,
- on peut utiliser les capacités humaines en reconnaissance de formes.
Nous avons développé un algorithme de construction interactive d'arbres de décision (CIAD). Celui-ci est basé sur une représentation 2D des données sous
la forme des projections (2D) de l'ensemble des paires possibles d'attributs. Les résultats de l'algorithme ont été comparés avec d'autres algorithmes
d'induction d'arbre de décision tels que CART, C4.5 et OC1. Les résultats obtenus montrent que l'on obtient un taux de précision à peu près équivalent
aux algorithmes automatiques avec une taille d'arbre souvent inférieure.
Traitement de données symboliques
Cet algorithme de construction interactive d'arbre de décision a ensuite été étendu pour pouvoir traiter des données symboliques
de type intervalle ou taxonomique. Lorsque l'on a affaire à des données de types intervalles et continues, dans le cas d'une projection 2D, il y
a 3 cas possibles :
- deux variables continues, on affiche un point
- un varirable continue et une variable intervalle, on affiche un segment,
- deux variables intervalles, on affiche une croix.
Le principe de construction interactive de l'arbre de décision reste inchangé.
Nous n'avons pas encore pu comparer notre algorithme avec des versions automatiques car aucun résultat n'est disponible à l'heure actuelle.
Augmentation des interactions
La dernière manière d'augmenter la part de la visualisation est d'utilisersimultanément plusieurs méthodes de visualisation.
Nous avons développé un environnement 3D de fouille de données. Cet environnement comporte à la fois des outils graphiques et des outils automatiques.
Le développement a été réalisé en C / C++ sur station SGI-O2 et sur Linux. Il permet d'ajouter aisément n'importe quel outil de fouille (graphique ou non)
et n'utilise que des bibliothèques Open-Source (Open-GL, Open-Motif et Open-Inventor) assurant ainsi une bonne indépendance vis-à-vis de la plate-forme
utilisée.
Traitement de grands ensembles de données
La plupart des algorithmes de fouille de données actuels ne sont pas bien adaptés pour pouvoir traiter de grands
ensembles de données. Par grand on entend jusqu'à au moins un milliard d'individus et plusieurs milliers de
dimensions. Plusieurs approches peuvent être suivies pour pouvoir effectuer un tel traitement. Une première
solution est de faire coopérer entre elles des méthodes automatiques et des méthodes visuelles (puisqu'une
méthode visuelle ne peut à l'heure actuelle résoudre à elle seule le problème). Nous avons développés plusieurs
algorithmes permettant de traiter des ensembles de grandes tailles et utilisant à la fois des méthodes
automatiques et graphiques.
Approche coopérative pour la classification supervisée
de grands ensembles de données
Une première solution est d'utiliser des algorithmes de SVM en coopération avec des algorithmes de visualisation.
Dans ce cas précis nous avons utilisé un algorithme de SVM norme 1 pour réduire le nombre de dimensions (colonnes)
de l'ensemble de données. Une fois ce nombre de dimensions ramené à une ou deux dizaine(s), on peut utiliser
l'algorithme de création interactive d'arbre de décision pour effectuer la classification de l'ensemble de
données. Il est intéressant de remarquer que la réduction du nombre de dimensions par exemple sur l'ensemble
de données Breast Cancer du Kent Ridge Bio-medical Data Set Repository, permet de passer de 24481 dimensions
à 10 dimensions sans perte d'information (le taux de précision est même augmenté de plus de 5%), certains parlent
alors de "dimensionality selection" au lieu de "dimensionality reduction". Cette réduction du nombre de dimensions
permet aussi d'interpréter graphiquement les résultats obtenus ce qui est totalement impossible avec l'ensemble de
données initial.
Approche symbolique pour la classification supervisée
de grands ensembles de données
Pour pouvoir traiter des ensembles de données ayant un très nombre d'individus, nous utilisons une représentation
de plus haut niveau des données. La première étape du traitement consiste alors à utiliser un algorithme de
classification non superviséee (clustering) sur les individus de chaque classe. Pour chaque cluster, on utilise
alors les valeurs minimum et maximum sur chaque attribut pour créer des variables de type intervalle. On utilise
ensuite l'algorithme de création interactive d'arbre de décision sur ces données symboliques. On peut ainsi
traiter des ensembles de données de tailles arbitrairement grandes en nombre d'individus.
Approche hybride pour la classification non supervisée
et la détection d'outliers
Dans ce dernier cas nous nous intéressons à la détection d'outliers dans des ensembles de données ayant un
très grands nombre de dimensions (colonnes). Le problème des données en très grandes dimensions est que
les notions de proximité ou de distance perdent de leur signification lorsque le nombre de dimensions
devient très important, en effet plus le nombre de dimensions est important, plus les individus peuvent être
considérés comme éloignés les uns des autres et donc, tout individu devient un outlier potentiel.
Pour pallier ce problème nous utilisons un algorithme génétique pour la sélection d'un sous-ensemble de
dimensions pertinent pour la détection d'outlier.
On arrive ainsi encore à ramener le nombre de dimensions utilisées à environ une dizaine.
Ce type d'approche nous permet de plus, avec l'aide du spécialiste des données, de qualifier l'outlier : est ce
une erreur (valeur impossible) ou un individu ayant un comportement significativement différent des autres
individus ? Ceci est absolument impossible à effectuer si le spécialiste des données doit examiner plusieurs
dizaines de milliers de valeurs (suivant les plusieurs milliers de dimensions de l'ensemble de données).
Une autre solution pour traiter de grands ensembles de données est de paralléliser des algorithmes
existant. Nous avons parallélisé un ensembles d'algorithmes de SVM pour permettre le traitement de très
grands ensembles de données sur des machines standard.
Parallélisation d'algorithmes de SVM
Enfin pour terminer la description des activités de recherche quelques mots sur les travaux menés sur les algorithmes de SVM et leur parallélisation.
Nous nous sommes initialement intéressés aux algorithmes de SVM pour fournir une aide à l'utilisateur lors de la construction interactive de l'arbre
de décision. En étudiant ces algorithmes nous nous sommes rendus compte que certains algorithmes pouvaient être parallélisés sans trop de difficultés.
Nous avons donc approfondit un peu le sujet et développer plusieurs versions d'algorithmes parallèles et distribués de SVM.
Pour tester les performances réelles de notre implémantation, nous avons classifié un milliard de données (lignes de la base de données) en 10
dimensions (colonnes de la base de données) en 7 minutes sur dix pentium-III, 800 MHz, 256 Mo RAM, Linux. Le même fichier en dimension 50
nécessitant quant à lui 2h10 sur les mêmes dix machines.
La complexité de l'algorithme varie linéairement en fonction du nombre d'individus (lignes de la base de données), et du carré de la dimension des données
(colonnes de la base de données).
L'algorithme original était un algorithme incrémental en ligne, nous en avons développé une version incrémentale et parallèle en colonne. Sa complexité est
équivalente à l'algorithme précédent (avec les lignes et les colonnes jouant des rôles inversés).
Ces algorithmes ont ensuite éte appliqués dans plusieurs domaines : la fouille de textes, la bioinformatique, les donnés temporelles, etc.
Toute question ou commentaire est la ou le bienvenu(e) : Francois Poulet
Dernière mise à jour le 21 Juillet 2004