Atelier Fouille de données
Méthodes de classification non supervisées Les méthodes de classification non supervisées sont essentielles en fouille de données, permettant de regrouper des individus en classes homogènes selon certaines caractéristiques.
D'après le document Atelier Fouille de données
Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.
Document source
Business Analytics, Data Science, Classification · PDF · 33 pages · 2021
Afficher l'aperçu du document
Méthodes de classification non supervisées
Les méthodes de classification non supervisées sont essentielles en fouille de données, permettant de regrouper des individus en classes homogènes selon certaines caractéristiques. Cet article explore la classification automatique, en se concentrant sur les algorithmes de K-means et de classification hiérarchique, tout en fournissant des définitions, des exemples et des explications sur des concepts clés tels que l'inertie et les critères d'agrégation.
Introduction à la classification automatique
La classification automatique vise à regrouper des individus en classes homogènes. On distingue deux approches : la classification automatique, qui repose sur des algorithmes formalisés, et la classification subjective, qui s'appuie sur l'intuition des praticiens. Dans ce cours, nous nous concentrerons sur la classification automatique, qui se divise en deux catégories principales :
- Classification hiérarchique : Cette méthode effectue une partition de classes de plus en plus vaste (classification hiérarchique ascendante) ou de moins en moins vaste (classification hiérarchique descendante).
- Classification non-hiérarchique : Dans ce cas, le nombre de classes est fixé à l'avance, comme dans la méthode des centres mobiles.
Indice de dissimilarité
Soit E l’ensemble des n objets à classer. Une dissimilarité d est une application de E × E dans R+ telle que :
1. d(i, i) = 0 ∀i ∈ E
2. d(i, i’) = d(i’, i) ∀i, i’ ∈ E × E
Une distance qui satisfait ces propriétés est un indice de dissimilarité. Pour un nuage d’individus, on peut résumer les distances entre individus dans une matrice des distances notée D, où chaque coefficient dij représente la distance entre l’individu Mi et l’individu Mj.
Notion d’inertie
Une partition est considérée comme bonne si elle satisfait deux critères :
- Les individus proches doivent être regroupés pour former des classes homogènes.
- Les individus éloignés doivent être séparés, ce qui implique que les classes doivent être distinctes.
L’inertie est une mesure de l’homogénéité d’un ensemble de points. L’inertie intraclasse mesure l’homogénéité des classes, tandis que l’inertie interclasse mesure la séparation entre les classes. Le théorème de Huygens stipule que :
Inertie totale = Inertie inter-classe + Inertie intra-classe
La classification K-means
L’algorithme K-means permet de découvrir des classes dans des données. Il est important de noter que les classes créées n'ont pas de relations hiérarchiques et que le nombre de classes est précisé à l'avance. L'algorithme fonctionne sur des variables continues et calcule les distances intra-classe et inter-classe.
Principe algorithmique
Le processus de l'algorithme K-means se déroule comme suit :
Entrée : k le nombre de groupes cherchés
DEBUT
Choisir aléatoirement les centres des groupes
REPETER
Affecter chaque cas au groupe dont il est le plus proche de son centre
Recalculer le centre de chaque groupe
JUSQU‘A ce que la stabilisation des centres soit atteinte
FIN
L'algorithme s'arrête lorsque deux itérations successives conduisent à la même partition ou qu'un critère de convergence est atteint.
Justification de l'algorithme
La variance intra-classes ne peut que décroître entre les étapes, ce qui garantit la convergence de l'algorithme. La partition finale dépend du choix initial des centres.
La classification hiérarchique
La classification hiérarchique consiste à créer, à chaque étape, une partition en agrégeant les éléments les plus proches. L'algorithme ne fournit pas une partition en q classes, mais une hiérarchie de partitions sous forme d'arbres appelés dendrogrammes.
Distance entre éléments et groupes
Au départ, on construit une matrice de distances entre tous les individus. Pour calculer la distance entre un individu et un groupe, on utilise des critères d’agrégation. Par exemple, pour trois objets x, y, z, la distance entre le groupe h (x et y) et z peut être définie comme :
d(h,z) = Min {d(x,z), d(y,z)} (saut minimal)
On peut également définir la distance du saut maximal ou la distance moyenne.
Principe algorithmique de la classification hiérarchique
L'algorithme de classification ascendante hiérarchique suit les étapes suivantes :
- Construire la matrice de distances entre les n éléments.
- Agrégation des deux éléments les plus proches.
- Construire une nouvelle matrice de distances jusqu’à obtenir un seul élément regroupant tous les objets.
Le dendrogramme
Le dendrogramme indique les objets et classes fusionnés à chaque itération, ainsi que la valeur du critère choisi pour chaque partition. Chaque palier correspond à une fusion de classes, et une coupure horizontale correspond à une partition.
Critère d’agrégation selon la variance
Le principe de l’algorithme d’agrégation selon la variance consiste à rechercher une partition telle que la variance interne de chaque classe soit minimale, ce qui maximise la variance entre les classes.
Exercice d'application
Pour appliquer ces concepts, il est recommandé de travailler sur un jeu de données et de réaliser une classification K-means suivie d'une classification hiérarchique pour observer les différences et les similarités entre les classes obtenues.
Points clés à retenir
- La classification automatique regroupe des individus en classes homogènes.
- K-means et la classification hiérarchique sont deux méthodes principales.
- L'inertie mesure l'homogénéité et la séparation des classes.
- Les dendrogrammes illustrent la hiérarchie des classes.
Glossaire
- Classification automatique : Regroupement d'individus par algorithmes.
- K-means : Algorithme de classification non hiérarchique.
- Dendrogramme : Représentation graphique des classes hiérarchiques.
- Inertie : Mesure de l'homogénéité d'un ensemble de points.
- Critères d’agrégation : Règles pour calculer les distances entre groupes.
Questions fréquentes
Qu'est-ce que la classification automatique ?
La classification automatique est un processus qui regroupe des individus en classes homogènes à l'aide d'algorithmes formalisés, sans intervention humaine directe.
Comment fonctionne l'algorithme K-means ?
L'algorithme K-means fonctionne en choisissant aléatoirement des centres de groupes, puis en affectant chaque individu au groupe le plus proche, et en recalculant les centres jusqu'à stabilisation.
Quelle est la différence entre classification hiérarchique et non hiérarchique ?
La classification hiérarchique crée une hiérarchie de classes, tandis que la classification non hiérarchique, comme K-means, fixe le nombre de classes à l'avance sans relations hiérarchiques.
Qu'est-ce que l'inertie dans la classification ?
L'inertie mesure l'homogénéité d'un ensemble de points. Une faible inertie intraclasse indique des classes homogènes, tandis qu'une forte inertie interclasse indique une bonne séparation entre les classes.
Quels sont les critères d'agrégation en classification ?
Les critères d'agrégation déterminent comment calculer la distance entre groupes, incluant des méthodes comme le saut minimal, le saut maximal et la distance moyenne.
Commentaires
Aucun commentaire pour le moment. Posez la première question.