Partitionnement de données

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Exemple de clustering hiérarchique.

Le partitionnement de données (ou data clustering en anglais) est une des méthodes d'analyse des données. Elle vise à diviser un ensemble de données en différents « paquets » homogènes, en ce sens que les données de chaque sous-ensemble partagent des caractéristiques communes, qui correspondent le plus souvent à des critères de proximité (similarité informatique) que l'on définit en introduisant des mesures et classes de distance entre objets.

Pour obtenir un bon partitionnement, il convient d'à la fois :

  • minimiser l'inertie intra-classe pour obtenir des grappes (cluster en anglais) les plus homogènes possibles ;
  • maximiser l'inertie inter-classe afin d'obtenir des sous-ensembles bien différenciés.

Vocabulaire[modifier | modifier le code]

La communauté scientifique francophone utilise différents termes pour désigner cette technique.
Le mot anglais clustering est communément employé. On parle également souvent de méthodes de regroupement. On distingue souvent les méthodes « hiérarchiques » et « de partition »

Clustering non supervisé[modifier | modifier le code]

Le "clustering non supervisé" aussi appelé classification non supervisée, est un processus qui permet de rassembler des données similaires. Le fait qu’il ne soit pas supervisé signifie que des techniques de "machine learning" vont permettre de trouver certaines similarités pour pouvoir classer les données et ce de manière plus ou moins autonome.

Ce type d’analyse permet d’avoir un profil des différents groupes. Cela permet donc de simplifier l’analyse des données en faisant ressortir les points commun et les différences et en réduisant ainsi le nombre de variable des données. Cette technique n’est pas seulement utilisée dans le domaine génétique, mais permet aussi par exemple de lister de potentiels clients lors d’une action publicitaire.

Clustering hiérarchique ou dendrogramme[modifier | modifier le code]

Le "clustering hiérarchique" est une autre technique de classification. Cette fois-ci, le paramètre comparé est décidé à l’avance. Ensuite une fois le paramètre de comparaison choisi, la distance euclidienne, qui permet de connaître la similarité entre l’ensemble des données, est calculée [9]. Pour ce faire, il faut utiliser l’équation 1.

Il suffit alors de lier les individus les plus similaires entre eux, deux par deux, et ce jusqu’à former un diagramme appelé dendrogramme.

Ces diagrammes se lisent de la façon suivante : pour connaître le niveau de similarité entre 2 individus, il faut regarder l’axe des ordonnés et plus la liaison entre deux individus se fait à une ordonnée élevée, moins ceux-ci seront similaires du point de vue du paramètre observé. Si par ailleurs, nous voulons connaître les individus observés, il faut regarder l’axe des abscisses.

Selon le taux de similarité que nous souhaitons, il est alors possible de former un certain nombre de groupe.

Heatmap[modifier | modifier le code]

Un heatmap est une représentation graphique de données statistiques dans une à matrice deux dimensions, qui utilise la technique de "clustering hiérarchique" dans le cas utilisé en cours. Les données y sont représentées par différentes couleurs.

La couleur de la grille représente la valeur du paramètre utilisé pour relier les échantillons, dans le cas de ce qui a été fait en cours il s’agit d’une mesure sur chaque gène, différente pour chaque patient. Plus la couleur est chaude (rouge), plus il y a une similarité.

Différentes méthodes de tri peuvent être utilisées, par exemple un regroupement selon des caractéristiques connues ou un tri selon un paramètres externe.

Comment construit-on un heatmap, quelles sont les grandes étapes ?[modifier | modifier le code]

Il existe différentes façons de construire un heatmap, car plusieurs sites proposent cette fonctionnalité. Nous, nous allons utiliser le site GenePattern https://cloud.genepattern. org/gp/pages/login.jsf.

Avant de faire les différentes manipulations, nous devons préparer deux fichiers (".gct" et ".cls"). Commençons par d’écrire le fichier ".gct". Ce type de fichier est représenté sous forme de tabulation. Les lignes et les colonnes ont un rôle spécifique. La première ligne sera toujours la même, c’est-à-dire : #1.2.

La deuxième ligne comprendra d’abord le nombre de ligne de données et ensuite le nombre de colonne de données.

La troisième contient une liste d’identifiant pour les échantillons associés à chacune des colonnes.

Le reste du fichier contient des données pour chacun des différents gènes. On peut aussi observer qu’il y a une ligne pour chaque gène et une colonne pour chacun des échantillons.

Parlons maintenant du fichier ".cls". Celui-ci est moins complexe que le précédent. Ce type de fichier défini les étiquettes de phénotype et permet d’associer chaque échantillon à une étiquette. La première ligne contient le nombre d’échantillons ainsi que le nombre de classes et cela est toujours suivit du chiffre "1". La deuxième ligne quant à elle contient les noms des numéros de classe.

Enfin la troisième ligne contient une étiquette de classe pour chaque échantillon.

Maintenant que nous avons nos deux fichiers, il faut les charger sur le site indiqué ci-dessus. Cette étape est illustrée à la FIGURE 6

Il faut ensuite se rendre dans la section Modules et taper dans la barre de recherche HierarchicalClustering et cliquer sur celui-ci.

Il faut ensuite changer certains paramètres comme suit :

- Column Distance measure =⇒ Euclidean,

- Row Distance measure =⇒ Euclidean,

- Clustering Method =⇒ Pairwise complete-linkage.

Une fois ces paramètres modifiés, il faut cliquer sur Run.

Une fois cette étape réalisée, il faut retourner dans la section module et cette fois taper HierarchicalClusteringImage dans la barre de recherche et cliquer comme précédemment.

En nous rendant dans la section Jobs, nous remarquons que trois type de fichiers sont apparus (".atr", ".cdt" et ".gtr"). Il peuvent alors être glissé dans leur emplacement respectif. On peut ensuite cliquer sur Run. Cela va nous donner un fichier ".jpeg" dans la section Jobs, qui, une fois ouvert, affiche un heatmap.

Dans quel contexte peut-il être utile de réaliser un heatmap ?[modifier | modifier le code]

Cette technique de mise en relation de deux sets de données triés ayant une mesure en com- mun peut être utilisée dans beaucoup de domaines. Par exemple, durant le laboratoire, les données sont des mesures sur des gènes, les deux sets sont les patients et les gènes, le tri vient des dendogrammes, et cela permet de localiser facilement, graphiquement, des catégo- ries de patients liées à des catégories de gènes à risque. On peut aussi utiliser le même concept sur des cartes thermiques, dont le contexte est à l’origine du nom "heatmap". De manière gé- nérale, on peut l’utiliser pour toute analyse descriptive, à partir du moment où il faut analyser un set de données trop grand pour être analysé manuellement et qui correspond au type de données attendu par un heatmap. Par exemple, la technique pourrait être utilisée pour trier des ponts, comme cela a été suggéré en cours, ou bien pour déterminer quelles caractéristiques macroscopique (mm-μm), associée à des compositions de matériaux (nm, molécules), ont les propriétés les plus intéressantes ; et ce ne sont que des exemples.

Quels fichiers sont produits à l’issue de ces manipulation ?[modifier | modifier le code]

Trois fichiers sont produits suite à un "clustering hiérarchique" :

— Un fichier ".gtr" (gene tree)

— Un fichier ".cdt" (clustered data table)

— Un fichier ".atr" (array tree)

Les fichiers ".gtr" et ".atr" enregistre l’historique de la jonction des nœuds en fonction des gênes ou des tableaux ainsi qu’un score de similariré qui illustre la similarité des deux élé- ments joint. Les fichiers ".gtr" et ".art" sont directement lus lorsqu’on ouvre le fichier ".cdt" correspondant, c’est-à-dire le fichier ".cdt" du même nom. Le fichier ".cdt" contient quant à lui les données d’origines.

Le fichier ".atr" montrent l’historique de la jointure des nœuds représentés selon un "array tree". La première colonne contient les identifiants uniques de chaque nœud. A côté de chacun de ces identifiants se trouve les deux identifiants des éléments joints. La dernière information de chaque ligne est le score de similarité entre les deux éléments joints. Ces éléments peuvent être des nœuds ou des tableaux. Les nœuds sont représentés sous le format "NODE*X" et les tableaux sous le format "ARRY*X", où "*" correspond à un nombre.

Intérêt et applications[modifier | modifier le code]

Le partitionnement de données est une méthode de classification non supervisée (différente de la classification supervisée où les données d'apprentissage sont déjà étiquetées), et donc parfois dénommée comme telle.

Applications : on en distingue généralement trois sortes[1] :

  • la segmentation d'une base de données ; elle peut servir à discrétiser une base de données.
    La segmentation peut aussi permettre de condenser ou compresser les données d'une base de données spatiales (c'est-à-dire réduire la taille des paquets de données à traiter, dans l'ensemble de données considéré) ; par exemple, dans une image aérienne ou satellitaire un SIG peut traiter différemment les forêts, champs, prairies, routes, zones humides, etc. ici considérés comme des sous-espaces homogènes. Un traitement plus fin pouvant ensuite être appliqué à des sous-ensemble de ces classes (ex. : forêt de feuillus, de résineux, artificielles, naturelles, etc.).
    OLAP est une méthode qui facilite l'indexation de telles bases ;
  • la classification (en sous-groupes, sous-populations au sein de la base de données), par exemple d'une base de données clients, pour la gestion de la relation client ;
  • l'extraction de connaissances, qui se fait généralement sans objectif a priori (facteur de sérendipité, utile pour la génération d'hypothèse ou modélisation prédictive), pour faire émerger des sous-ensembles et sous-concepts éventuellement impossibles à distinguer naturellement.

Formalisation[modifier | modifier le code]

Pour faire du partitionnement de données, lesdites données sont supposées être organisées dans une matrice dont chaque ligne correspond à un individu (ou observation) et chaque colonne correspond à un prédicteur (ou variable). On note le nombre d'individus et le nombre de prédicteurs : de telle façon, la matrice est de taille

L'objectif d'un algorithme de partitionnement sera de trouver les "meilleurs" groupes d'individus. Pour cela on se donne une dissimilarité entre les individus et (respectivement, ligne et de ).

Notons le nombre de groupes que l'on souhaite former. Cela revient à trouver une fonction d'attribution qui minimise une fonction coût.

Une fonction coût classique est la variabilité intra-classe (within-cluster variance en anglais) :

D'autres fonctions coûts existent (par exemple l'indice de Dunn, l'indice de Davies-Bouldin ou l'indice de Calinski-Harabasz). Elles peuvent être utilisées pour évaluer la qualité de classification[2].

Algorithmes[modifier | modifier le code]

Il existe de multiples méthodes de partitionnement des données, parmi lesquelles :

Ces méthodes sont implémentées au sein de nombreux logiciels de fouille de données.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Anil K. Jain, M. N. Murty, P. J. Flynn, « Data Clustering: a Review », ACM Computing Surveys, vol. 31, no 3, septembre 1999. DOI:10.1145/331499.331504
  • M.-S. Chen, J. Han, and P. S. Yu, « Data mining: an overview from a database perspective », IEEE Transactions on Knowledge and Data Engineering, vol. 8, no 6, p. 866–883, 1996.
  • A. K. Jain, « Data clustering: 50 years beyond K-means », Pattern Recognition Letters, vol. 31, no 8, p. 651–666, juin 2010.

Notes et références[modifier | modifier le code]

  1. Berkhin, 2002.
  2. (en) « Clustering Indices », sur cran.r-project.org, (consulté le 8 juin 2019)