ImageMining:

Classification non-supervisée:
Clustering
My Abdelouahed Sabri
[email protected]
Introduction
• Le clustering consiste en un regroupement (partitionnement) des
objets en des groupes (paquets) homogènes (clusters).
• Un cluster est une collection d’objets (éléments) qui partagent des
caractéristiques communes ou trop proches et qui sont dissimilaires
aux objets des autres clusters.
Applications
• Les applications du clustering sur les bases d’images peuvent être
répertoriées en 3 catégories :
• Segmentation des bases de données (d’images) en des catégories d’images ;
images représentants les forêts, champs, voitures, bâtiments, lacs, …
• Segmentation des images en des régions homogènes
• Extraction de connaissances afin de faire apparaitre des sous-ensembles et
sous-concepts éventuellement impossibles à distinguer naturellement.
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Clustering hiérarchique (Hierarchical Clustering)
• Clustering basé sur la densité (Density-based Clustering)
• Clustering Basé sur les Modèles (Model-Based Clustering)
•…
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Diviser un ensemble de données en un nombre prédéfini de clusters, sans
qu'il y ait de chevauchement entre les clusters:
• Chaque point de données est affecté à un cluster unique
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Diviser un ensemble de données en un nombre prédéfini de clusters, sans
qu'il y ait de chevauchement entre les clusters:
• Chaque point de données est affecté à un cluster unique

2 clusters 3 clusters
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Diviser un ensemble de données en un nombre prédéfini de clusters, sans
qu'il y ait de chevauchement entre les clusters:
• Chaque point de données est affecté à un cluster unique

• Algorithmes
• K-means
• k-Médoïdes
• Fuzzy C-Means (FCM)
• …
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Clustering Hiérarchique (Hierarchical Clustering)
• Les données sont regroupées dans une hiérarchie de clusters imbriqués.
• Le résultat peut être représenté sous forme d’un arbre (dendrogramme).
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Clustering Hiérarchique (Hierarchical Clustering)
• Les données sont regroupées dans une hiérarchie de clusters imbriqués.
• Le résultat peut être représenté sous forme d’un arbre (dendrogramme).
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Clustering Hiérarchique (Hierarchical Clustering)
• Les données sont regroupées dans une hiérarchie de clusters imbriqués
➢ Le résultat peut être représenté sous forme d’un arbre (dendrogramme).
• Deux approches principales :
1. Clustering agglomératif (bottom-up) :
✓ Commence avec chaque point de données dans son propre cluster, et ces clusters sont
ensuite fusionnés par étapes successives en fonction de la similarité.
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Clustering Hiérarchique (Hierarchical Clustering)
• Les données sont regroupées dans une hiérarchie de clusters imbriqués
➢ Le résultat peut être représenté sous forme d’un arbre (dendrogramme).
• Deux approches principales :
1. Clustering agglomératif (bottom-up) :
✓ Commence avec chaque point de données dans son propre cluster, et ces clusters sont
ensuite fusionnés par étapes successives en fonction de la similarité.
2. Clustering divisif (top-down) :
✓ Commence avec tous les points dans un seul cluster, qui est ensuite divisé en sous-clusters de
plus en plus petits.
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Clustering Hiérarchique (Hierarchical Clustering)
• Clustering Basé sur la Densité (Density-Based Clustering)
• Regroupe les points de données en fonction de la densité des régions:
➢ Les régions de forte densité sont considérées comme des clusters,
➢ Les régions de faible densité sont traitées comme du bruit ou des anomalies.
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Clustering Hiérarchique (Hierarchical Clustering)
• Clustering Basé sur la Densité (Density-Based Clustering)
• Regroupe les points de données en fonction de la densité des régions:
➢ Les régions de forte densité sont considérées comme des clusters,
➢ Les régions de faible densité sont traitées comme du bruit ou des anomalies.
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Clustering Hiérarchique (Hierarchical Clustering)
• Clustering Basé sur la Densité (Density-Based Clustering)
• Regroupe les points de données en fonction de la densité des régions:
➢ Les régions de forte densité sont considérées comme des clusters,
➢ Les régions de faible densité sont traitées comme du bruit ou des anomalies.
➢Algorithmes
➢ DBSCAN (Density-Based Spatial Clustering of Applications with Noise)
➢ DENCLUE (DENsity-based CLUstEring)
➢ Mean Shift
➢…
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Clustering Hiérarchique (Hierarchical Clustering)
• Clustering Basé sur la Densité (Density-Based Clustering)
• Clustering Basé sur les Modèles (Model-Based Clustering)
• Suppose que les données sont générées par un ensemble de modèles sous-
jacents (par exemple, des distributions statistiques).
• Trouver les paramètres de ces modèles et assigner les points de données aux modèles
les plus probables.
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Clustering Hiérarchique (Hierarchical Clustering)
• Clustering Basé sur la Densité (Density-Based Clustering)
• Clustering Basé sur les Modèles (Model-Based Clustering)
• Suppose que les données sont générées par un ensemble de modèles sous-
jacents (par exemple, des distributions statistiques).
• Trouver les paramètres de ces modèles et assigner les points de données aux modèles
les plus probables.
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Clustering Hiérarchique (Hierarchical Clustering)
• Clustering Basé sur la Densité (Density-Based Clustering)
• Clustering Basé sur les Modèles (Model-Based Clustering)
• Suppose que les données sont générées par un ensemble de modèles sous-
jacents (par exemple, des distributions statistiques).
• Trouver les paramètres de ces modèles et assigner les points de données aux modèles
les plus probables.
Types de Clustering
• Clustering Partitionnel (Partitioning Clustering)
• Clustering Hiérarchique (Hierarchical Clustering)
• Clustering Basé sur la Densité (Density-Based Clustering)
• Clustering Basé sur les Modèles (Model-Based Clustering)
• Suppose que les données sont générées par un ensemble de modèles sous-
jacents (par exemple, des distributions statistiques).
• Trouver les paramètres de ces modèles et assigner les points de données aux modèles
les plus probables.
• Algorithmes
• GMM (Gaussian Mixture Models)
• EM (Expectation-Maximization)
• SOM (Self-Organizing Maps)
• HMM (Hidden Markov Models)
• …
Algorithmes de clustering
• Il existe une multitude d’algorithmes de clustering qui peuvent être
utilisés dans le cas de l’Image-mining :
• Les méthodes basées centroïdes telles que les algorithmes des k-moyennes
(K-means) ou k-médoïdes ,
• Les méthodes de regroupement hiérarchique ;
• Algorithme de maximisation de l'espérance (Expectation-Maximization; EM),
• Algorithme de C-moyennes floues (Fuzzy C-means clustering; FCM)
•…
K-means
• K-means est l'un des algorithmes les plus connus en classification non
supervisée (clustering)
• Simple, efficace, rapide, …
• Principe
• C’est algorithme itératif qui minimise la somme des distances entre chaque pixel et le
centroïde de son cluster.
• Consiste à regrouper les pixels en un certain nombre de classes représentant les
régions.
• Le nombre de classes (K) est choisi selon une connaissance préalable et suivant
combien de régions souhaitées.
• Le critère d’arrêt de l’algorithme est basé sur la stabilité des moyennes.

20
K-means
• Avantages
• L’algorithme de k-Means est très populaire du fait qu’il est très facile à
comprendre et à mettre en œuvre.
• La méthode résous une tâche non supervisée, donc elle ne nécessite aucune
information sur les données,
• Rapidité et faibles exigences en taille mémoire,
• La méthode est applicable à tout type de données en choisissant une bonne
notion de distance.

21
K-means
• Inconvénients
• Le nombre de classes est un paramètre de l’algorithme.
➔Un bon choix du nombre k est nécessaire,
➔Un mauvais choix de k produit de mauvais résultats: sur- ou sous- clustering
• Les points isolés sont mal gérés (Ils doivent appartenir obligatoirement
à un cluster ?) ➔ très sensible au bruit
• Ne trouve pas nécessairement la configuration la plus optimale
correspondant à la fonction objective minimale.
• Les résultats de l'algorithme du K-Means sont sensibles à l'initialisation
aléatoires des centres.

22
K-means
• Algorithme:
1. Choix aléatoire de la position initiale des K centroïdes de clusters.
2. Affecter les pixels à un cluster suivant un critère de minimisation des
distances (généralement selon une mesure de distance euclidienne).
3. Une fois tous les pixels placés, recalculer les centroïdes de chaque cluster.
4. Réitérer les étapes 2 et 3 jusqu’à ce que plus aucune réaffectation ne soit
faite,

23
FCM (Fuzzy C-Means; C-moyennes floues)
• FCM est un algorithme de classification non-supervisée basé sur la
logique floue.

Principe:
• Un pixel peut appartenir à plusieurs classes mais selon le degré
d’appartenance
• Chaque degré exprime l’appartenance incertaine d’un pixel à une région
donnée.
• Le degré d’appartenance se situe dans l’intervalle [0, 1] et les classes
obtenues ne sont pas forcément disjointes.

24
FCM (Fuzzy C-Means; C-moyennes floues)
• Avantages
• non supervisé
• toujours converge
• Inconvénients
• Le principal inconvénient de ces méthodes réside dans le fait que la classification
ne repose que sur l’intensité des éléments de volume sans prendre en compte
l’information spatiale, ce qui la rend sensible au bruit et a l’hétérogénéité
d’intensité
• Longue durée de calcule
• Sensibilité a la conjecture initiale (vitesse, minimums locaux, bruit)

25
FCM (Fuzzy C-Means; C-moyennes floues)
• Algorithme
1. Fixer les paramètres :
• C : le nombre de classes,
• m: degré de flou,
• ε : critère d’arrêt.
2. Initialiser la matrice de degrés d’appartenance U par des valeurs aléatoires
dans l’intervalle [0,1],
3. Calculer les centroïdes des classes,
4. Mettre à jour la matrice degrés d’appartenance suivant la position des
centroïdes,
5. Répéter les étapes 3 à 4 jusqu’à satisfaction du critère d’arrêt.

26
Expectation Maximisation (EM)
• EM est utilisé pour trouver l’estimation du maximum de
vraisemblance à partir d’un ensemble de données.
• Le choix initial des paramètres affecte le déroulement de la
classification jusqu’à générer des clusters incohérents.

27
Expectation Maximisation (EM)
• Algorithme:
• Initialisation : Choisir des paramètres initiaux :
• μj : la moyenne de chaque cluster,
• σ : la variance ,
• P(Cj) : la proportion de chaque classe.
• Étape E : Estimer la probabilité que le vecteur v des pixels appartient à un
cluster
• Étape M: Mise à jour les paramètres.
• Répéter l'itération de base, jusqu'à stabilisation des paramètres.

28
Mean-Shift
Le Mean-Shift est une méthode de clustering basée sur l’estimation de
densité.
• Principe:
• Chaque pixel est représenté par un point dans l’espace à N dimensions pour
ce faire, on calcule la densité locale en un point et on déplace itérativement la
fenêtre en direction du gradient de densité maximum.

29
Mean-Shift
• Algorithme
1. Choisir une répartition uniforme des fenêtres de recherche initiales,
2. Calculer le centroide des données pour chaque fenêtre,
3. Centrer la fenêtre de recherche sur le centroide de l'étape 2,
4. Répéter les étapes 2 et 3 jusqu'un à convergence,
5. Fusionner les fenêtres se trouvant au même point final,
6. Grouper les données traversées par les fenêtres fusionnées.

30
 Clustering en ImageMning
• Comment on peut utiliser les algorithmes de Clustering sur des bases
d’images?
Segmenter des images Regrouper une base d’images en des sous-ensembles

Dataset
ToDO
• Votre tâche consiste à écrire un code Matlab (ou Python) pour faire le
clustering sur deux bases d’images :
• 2Classes : images à segmenter en deux classes
• 4Classes : images à segmenter en quatre classes
• Le résultat de chaque clustering sera enregistré dans un fichier *.csv
• La forme du fichier *.csv sera sous la forme suivante:
image_name, class

image1.jpg,1

image2.jpg,1

image3.jpg,1
Réflexion
• Comment on peut faire une segmentation d’image (Clustering)
utilisant un algorithme de classification supervisée?

Modèle de classification
supervisée