Aller au contenu

Clustering Techniques

Techniques de clustering Les techniques de clustering sont des méthodes d'analyse multivariée qui permettent de regrouper des individus selon leur similarité en un nombre fini de classes.

D'après le document Clustering Techniques

Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.

Document source

Clustering Techniques

Data Analysis, Clustering · PDF · 21 pages · 2017

Afficher l'aperçu du document

Consulter le document original →

Techniques de clustering

Les techniques de clustering sont des méthodes d'analyse multivariée qui permettent de regrouper des individus selon leur similarité en un nombre fini de classes. Cet article couvre les principales méthodes de clustering, notamment la classification hiérarchique ascendante et le partitionnement, ainsi que les métriques de similarité utilisées pour évaluer la qualité des partitions.

Objectif et méthodes de clustering

L'objectif du clustering est de regrouper des individus selon leur similarité. Pour cela, il est essentiel de définir une métrique de similarité ou de dissemblance. La qualité de la partition dépendra de la capacité à regrouper des individus similaires tout en séparant ceux qui sont différents.

Notion de similarité

La similarité entre individus peut être mesurée par des distances. La distance entre deux individus i et j est donnée par la formule suivante :

d(i, j) = ∑k=1K | xki − xkj |

Cette distance de Minkowski permet de calculer différentes mesures de similarité :

  • λ = 2 : distance Euclidienne
  • λ = 1 : distance de Manhattan

Il est recommandé d'utiliser la distance euclidienne pour combiner le clustering avec les méthodes de composantes principales.

Similarité entre groupes

Pour construire un dendrogramme, il est nécessaire de définir la similarité ou la dissemblance entre les groupes d'individus. Deux approches sont couramment utilisées :

  • Lien simple : distance entre les deux points les plus proches dans les groupes A et B.
  • Lien complet : la plus grande distance entre un élément de A et un élément de B.

Ces définitions peuvent être appliquées à toute mesure de distance.

Classification hiérarchique ascendante

La classification hiérarchique ascendante est une méthode qui construit un arbre hiérarchique (dendrogramme) représentant les liens entre les individus. Chaque branche de l'arbre regroupe les individus d'un groupe polythétique, où chaque élément possède de nombreuses caractéristiques.

Algorithme d'agglomération classique

Le processus de classification hiérarchique se déroule en plusieurs étapes :

  1. Calculer la matrice de distance D.
  2. Regrouper les individus i et j les plus proches pour créer un nouvel élément (i,j).
  3. Mettre à jour D en enlevant les colonnes et les lignes relatives à i et j et en les remplaçant par une ligne et une colonne pour le nouvel élément.
  4. Répéter le processus à partir de l'étape 2 sur la nouvelle matrice.

Chaque arbre hiérarchique peut être considéré comme une séquence de partitions imbriquées, allant du plus précis (chaque individu est une classe) au plus général (une seule classe).

Méthode WARD

La méthode WARD vise à regrouper deux éléments en maximisant la qualité de la partition obtenue, en minimisant l'inertie intra-classe. La qualité d'une partition est jugée bonne si :

  • Les individus dans chaque cluster sont homogènes (faible variabilité intra-cluster).
  • Les individus dans différents clusters sont très différents (forte variabilité entre clusters).

Dans un espace Euclidien, on peut appliquer le théorème de Huygens :

Inertie totale = Inertie entre clusters + Inertie intra-cluster

Partitionnement : méthode K-means

La méthode K-means est une technique de partitionnement qui divise les individus en k groupes. Le processus se déroule en plusieurs étapes :

  1. Choisir au hasard les centres de classes d'une partition.
  2. Affecter chaque individu à la classe dont le centre est le plus proche.
  3. Déplacer l'ancien centre vers le nouveau centre de gravité des nouvelles classes.
  4. Réaffecter les individus aux classes dont le centre est le plus proche.
  5. Rechercher les nouveaux centres de gravité.
  6. Répéter le processus jusqu'à stabilisation des centres de gravité.

Ce processus continue jusqu'à ce que la partition soit optimale, c'est-à-dire que les changements dans l'inertie inter-cluster ne dépassent pas un seuil défini.

Exemple d'une partition en trois classes

Considérons un exemple où nous avons trois classes. Au départ, nous choisissons des centres de classes au hasard. Ensuite, nous affectons chaque individu à la classe dont le centre est le plus proche. Après cela, nous déplaçons les centres vers les nouveaux centres de gravité et réaffectons les individus. Ce processus se répète jusqu'à ce que les centres ne changent plus.

Points clés à retenir

  • Le clustering regroupe des individus selon leur similarité.
  • Les méthodes de clustering incluent la classification hiérarchique et le partitionnement.
  • Les mesures de distance influencent la qualité des partitions.
  • La méthode K-means est efficace pour partitionner les données en groupes.

Glossaire

  • Clustering : Technique de regroupement d'individus selon leur similarité.
  • Dendrogramme : Représentation graphique des liens entre individus dans un arbre hiérarchique.
  • Inertie : Mesure de la variabilité intra-cluster et inter-cluster.
  • Méthode WARD : Technique de classification hiérarchique qui minimise l'inertie intra-cluster.
  • K-means : Méthode de partitionnement qui divise les individus en k groupes.

Questions fréquentes

Qu'est-ce que le clustering ?

Le clustering est une méthode d'analyse qui regroupe des individus selon leur similarité en un nombre fini de classes. Cela permet d'identifier des structures ou des patterns au sein des données.

Comment fonctionne la méthode K-means ?

La méthode K-means fonctionne en choisissant des centres de classes au hasard, puis en affectant chaque individu à la classe dont le centre est le plus proche. Ce processus est répété jusqu'à ce que les centres de gravité se stabilisent.

Quelle est la différence entre la distance Euclidienne et la distance de Manhattan ?

La distance Euclidienne mesure la distance directe entre deux points dans un espace, tandis que la distance de Manhattan mesure la distance en suivant les axes d'un système de coordonnées, ce qui peut donner des résultats différents selon la distribution des données.

Pourquoi utiliser la méthode WARD ?

La méthode WARD est utilisée pour maximiser la qualité de la partition en minimisant l'inertie intra-cluster, ce qui permet d'obtenir des clusters homogènes et bien séparés.

Comment évaluer la qualité d'une partition ?

La qualité d'une partition peut être évaluée en examinant la variabilité intra-cluster et inter-cluster. Une bonne partition aura une faible variabilité intra-cluster et une forte variabilité entre les clusters.

Partager

Commentaires

Aucun commentaire pour le moment. Posez la première question.

Les commentaires sont relus avant publication. Votre e-mail n'est jamais affiché.

← Toutes les révisions