Regroupement Flashcards
Introduction au regroupement
Regroupement
- Cluster analysis
- Formation de groupes (clusters) ou grappes
- Possibilité de déceler des valeurs aberrantes
Principe
- Cohésion : maximiser la similarité intra-groupe
- Distinction : minimiser la similarité entre les groupes
Qualité
- Dépend de la mesure de similarité utilisée
Approche classique et ancienne
- Classification ascendante ou descendante hiérarchique
Classification versus regroupement
- La classification est une technique d’apprentissage supervisé à l’opposé du regroupement qui est non supervisé
- C’est un moyen d’affecter une nouvelle instance à une classe prédéfinie
- Elle nécessite la collecte et l’étiquetage d’un ensemble de tuples et l’utilisation de modèles d’apprentissage
- On peut utiliser le regroupement sur des données pour former un ensemble de groupes qui deviennent des classes avec une étiquette (ex. étudiants excellents,
bons et moyens)
Groupes
- Disjoints : un objet appartient à un seul groupe
- Chevauchants : un objet peut appartenir à plusieurs groupes
Mesure de similarité
- Basée sur la distance (ex. euclidienne), la densité, etc
Diverses catégories
- Partitionnement, approche hiérarchique, approche fondée sur la densité, regroupement conceptual, etc.
Quelles sont les principales approches du regroupement?
Partitionnement
- Construire des partitions en minimisant par exemple la somme des carrés des écarts. Ex. K-means, CLARANS
Approche hiérarchique
- Décomposition hiérarchique d’objets. Ex. Classification ascendante hiérarchique, Diana, BIRCH
Approche basée sur la densité
- Fonctions de densité et connectivité. Ex. DBSCAN, OPTICS
Regroupement conceptuel
- Chaque groupe d’objets possède une description. Ex. analyse formelle de concepts
Quelles sont les exigences du regroupement?
Performance
Capacité d’expansion (scalability)
- Gestion de données volumineuses
Capacité à analyser différents types d’attributs
- Données numériques continues ou discrètes, binaires, nominales, ordinales, etc
Capacité à traiter des données bruitées
Algorithmes incrémentaux
- Possibilité de mettre à jour les groupes suite à l’ajout de nouvelles instances
Traitement de la haute dimensionnalité
Qu’est-ce que la classification ascendante hiérarchique?
Entrée
- Un ensemble d’observations décrites par des attributs
- Ex. Employés et leurs caractéristiques
Sortie
- Un dendrogramme représentant des groupes imbriqués à divers niveaux de granularité
- La délimitation des groupes se fait par une coupure du dendrogramme
Principe
- La similarité intra-groupe est forte mais est faible entre les groupes
Dendrogramme :
- Au départ, chaque observation constitue un groupe
- On regroupe d’abord deux observations ayant la plus petite distance entre elles
- Deux autres observations avec une distance faible sont ensuite regroupés
- On regroupe l’observation 3 avec le groupe 1
- Les groupes 1 et 2 sont fusionnés
- L’observation 6 ne fait partie d’aucun groupe. C’est un cas aberrant.
Qu’est-ce que la méthode des k-moyennes?
k-moyennes (k-means)
Étapes en partant d’un k donné
- Partitionner les objets en k sous-ensembles
- Identifier les points graines (seeds) comme les centroïdes des groupes
- Affecter chaque objet au groupe ayant le plus proche point de graine
- Retourner à l’étape 2. Arrêter quand aucun changement ne se produit au niveau de l’affectation des objets
Un exemple de k-means:
1. Ensemble initial
2. Partitionner au hasard les objets en k groupes
3. Calculer le centroïde des groupes
4. Réaffecter les objets
5. Mettre à jour les centroïdes
6. Répéter si nécessaire
Répéter
- Calculer le centroïde de chaque partition
- Affecter chaque objet au groupe ayant le centroïde le plus proche
- Arrêt si aucun nouveau changement
Force
- Efficace car complexité O(tkn), avec n objets, k groupes (clusters), et t itérations. Généralement, k et t < < n.
Faiblesses
- Applicable à des données continues
- Nécessité de fournir une valeur pour k. Toutefois, possibilité de calculer automatiquement cette valeur
- Méthode sensible aux données bruitées et aux exceptions
Quelles sont les applications du regroupement?
Biologie
- Taxonomie d’espèces
Recherche d’information
- Regroupement de documents selon leurs thèmes
Marketing
- Découverte de profils de clients
Immobilier
- Identification de propriétés selon leurs caractéristiques
Web
- Groupes d’utilisateurs, communautés dans les réseaux sociaux
Conclusion du regroupement
Le regroupement
- assemble des objets selon leur similarité
Plusieurs catégories d’algorithmes
Diverses mesures de similarité
- Cela dépend du type de données
Nombreuses applications
