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 »

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) :

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.