Apprentissage non supervisée
Clustering
Mme Hamdad
ESI LCSI.
Plan du cours
• Introduction
• Kmeans (Rappel)
• K-médoides.
• Classification basée sur la densité: DBSCAN
– Principe de fonctionnement
– Caractéristiques
• Classification auto-organisée: SOM
– Principe de fonctionnement
– Caractéristiques
• Conclusion
2
Introduction
• But :Regrouper un ensemble de données en
différents groupes homogènes.
• Les objets d’un même groupe: les plus
similaires possibles
• Les objets de groupes différents: les plus
dissimilaires possibles.
Classification Non Supervisée
1. Les données du même groupe doivent être les plus semblables possible.
2. Les données de groupes différents doivent être les plus différentes
possible.
3. Le nombre de groupes et leur signification ne sont pas connus à
l’avance.
5
Domaines d’application
• Marketing :
- Partitionner une clientèle en segments dotés chacun d’une offre et d’une
communication spécifique.
- Répartir l’ensemble des magasins d’une enseigne selon le type de clientèle, rayon
(selon type d’article) ou selon la taille du magasin.
• Médicale :
- Groupes de patients susceptibles d’être soumis à des protocoles thérapeutiques
déterminés: Un groupe contient tous les patients réagissant identiquement.
• Sociologie : Découper la population en groupes homogènes du point de vue socio-
démographique, style de vie, opinions ou attentes.
• Aménagement de la ville : identifier des groupes de maisons selon leurs types et
emplacements.
• Tremblement de terre ( Earthquake studies): regrouper les épicentres observés
pour identifier des zones dangereuses.
• Classification de documents: clustering des données blogs pour découvrir des
comportements similaires des utilisateurs……..
etc
Taxonomie de la Classification Non
Supervisée
Méthodes
Hiérarchique
Méthodes par
partitionnement
méthodes basées
Clustering densité
Méthodes basées
grille
Méthodes
biomémitique
7
K-means
• Soit E l’ensemble à partitionner.
• Début, on choisit k points de E aléatoirement appelés
centroides.
Entrée : un ensemble d’objets E, nombre de classes K.
• 1. Choisir K individus au hasard dans E(comme centres
des classe initiaux).
• 2. Affecter chaque individu au centre le plus proche.
• 3. Recalculer le centre de chacune de ces classes.
• 4. Répéter l’étape (2) et (3) jusqu’à stabilité des centres.
• 5. Editer la partition obtenue.
• Sortie : Partition de E en K classes.
• Cette méthode est facile à mettre en œuvre.
• Elle converge très vite.
• Elle est sensible aux données aberrantes.
• Elle a tendance à donner des classes de formes
sphériques.
• L’inconvénient majeur de la méthode:
- Le choix aléatoire des noyaux à l’initialisation de
l’algorithme. Car deux choix différents des
représentants initiaux, mènent à des partitions
différentes.
K-medoids
• Trouver k objets représentatives, appelés k-medoids
– PAM (Partitioning Around Medoids: Kaufmann & Rousseeuw
1987)
Début: ensemble initial de médoides et itérativement remplacer
un médoide par un non médoide si ce dernier améliore la
fonction objective.
– PAM est efficace pour des petits datasets
– CLARA (Clustering Large Applications) (Kaufmann & Rousseeuw,
1990): Environ 5 échantillons à 40+2K objets chacun.
– CLARANS (Randomized sampling + spatial data structure (Ester
et al., 1995))
10
10
10
9
9
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
0
0
0 1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9 10
K-means K-medoids
Métriques pour déterminer le
nombre de classes
Méthode Elbow
Méthode du coude.
- Exécuter un clustering k-means sur l'ensemble de
données pour des valeurs de k variant par
exemple de 1 à 10
- Pour chaque valeur de k, calculer la somme des
erreurs au carré ( SSE) ou l’inertie intra classes
- Tracer la courbe des SSE en fonction de K
- Si le graphe ressemble à un bras, alors le «coude»
est la meilleure valeur de k.
Méthode Silhouette
• On dit que c’est la meilleure mesure pour décider
du nombre de classes à définir à partir des
données.
• Pour chaque objet i appartenant au cluster Ck,
calculer a(i):
• la distance moyenne entre i et tous les autres
points de données du même cluster.
• b(i) est la plus petite distance moyenne de i à
tous les points de tout autre cluster auquel il
n'appartient pas. Le cluster avec la plus petite
dissimilarité moyenne est dit "cluster voisin" de i.
• Le coefficient varie entre -1 et 1.
• Une valeur proche de 1 implique que l‘objet est bien
classifié,
• Si s(i) est plutôt négative, ceci indique que l’objet n’est pas
dans le bon cluster.
• Un s (i) proche de zéro signifie que la donnée est à la
frontière de deux clusters naturels.
Avantages et inconvénients
• Cette méthode est meilleure car elle donne le
nombre optimal de clusters.
• Mais cette métrique est coûteuse en calcul
car le coefficient est calculé pour chaque
instance.
• Le choix de la métrique optimale pour le
nombre de clusters doit être pris en fonction
des besoins.
DBSCAN – Density-Based
Spatial Clustering of
Applications with Noise
Composantes de DBSCAN
• Trois types de points:
- Points denses
- Points frontières
- Points aberrants
• Deux paramètres principaux:
- Epsilon: Rayon du voisinage
- Minpoints: Nombre minimal de points dans
ce voisinage.
Un point est dense s’il a un nombre de points
supérieur à Minpoints dans son voisinage
Eléments de DBSCAN
DBSCAN: algorithme basé sur la densité
Densité = Nombre de points à l’intérieur d’un rayon donné
(Eps)
Un point est un noyau s’il a plus qu’un nombre donné de
points (MinPts) à l’intérieur d’un rayon donné (Eps)
Ces points sont à l’intérieur d’un même segment
Un point frontière est un point non noyau qui a un nombre
de points inférieur à MinPts à l’intérieur de son Eps, mais
qui se trouve à moins d’un Eps d’au moins un noyau
Un point bruité est un point qui n’est ni un noyau, ni un
point frontière
DBSCAN : Principe de fonctionnement
• Regroupe les objets dans le même cluster, s’ils sont
connectés l’un à l’autre par une population de point
dense.
• Si A est un point dense alors ses voisins sont dans le
même cluster.
• Idée de base:
– Démarrer d’un point dense A.
– Tout les points joignable par A ou d’autres points
dense connectés à A font partie du même cluster.
– Tout les points non joignable par des points denses
sont des bruits.
– On répète l’opération jusqu’à ce que tout les points soit explorés
24
Source: [6]
DBSCAN : Principe de fonctionnement
𝜀=1
𝑀𝑖𝑛𝑃𝑡
* Pts aberrants
Pts frontière
𝜀
* * Point dense
* * *
A
* *
25
Comment déterminer eps
• Calculer les k distances les plus proches dans une
matrice de points.
• Calculer la moyenne des distances de chaque point par
rapport à ses k voisins les plus proches.
• La valeur de k est donnée par l'utilisateur
• Ensuite, ces k-distances sont tracées dans un ordre
croissant. L’objectif est de déterminer le « coude », qui
correspond au paramètre optimal d’epsilon.
• Le coude va correspondre à un seuil où un changement
brusque se produit.
Dataset multishapes
données météorologiques(USA2015)
DBSCAN : Caractéristiques
Avantages Inconvénients
• Détecte les points aberrants • N’est pas adapté au datasets avec
• Le nombre de classes n’est pas de hautes densités
spécifié • N’est pas adapté au datasets avec
• Peut découvrir des cluster de des points déconnectés
formes arbitraires.
• Si le domaine n’est pas bien
• Les deux paramètres peuvent être étudié, il est difficile de choisir
spécifiés par un expert du
domaine. une mesure de distance
• Peut trouver des clusters non
linéairement séparables
• Est déterministe
29
• Soit le tableau de distance définit sur
I={a,b,c,d,e,f,g} suivant, tel que chaque point
est dans R² :
A B c D e F g
a 0
b 1 0
c 3 2 0
d 6 5 3 0
e 7 6 4 1 0
f 11 10 8 5 4 0
g 16 15 13 10 9 5 0
Questions Réponses
1- Dans DBSCAN, à quoi est minpoints=p+1=2+1=3
Epsilon: On calcul la moyenne des 3 plus
égal minpoints? Calculer proches voisins de tout les points:
epsilon. • a: b,c,d: 1+3+6/3=10/3
2- On donne minpoints=3, • b: a,c,d: 8/3,.......
On trace la courbe de ces moyennes et on
epsilon=4, donnez un point détecte le coude de la courbe croissante:
dense, un point frontière, un eps=4.
point aberrant, et un cluster, 2- c est e sont des points denses car ils
ont 4 points (>minpts) dans leurs
s'ils existent. voisinages.
- f est un point frontière
- g est un point aberrant
- {a,b,c,d,e,f} est un cluster
Self Organizing Map
(SOM)
SOM
• SOM est une classe de réseaux de neurones pour
l’apprentissage non supervisé.
• En pratique: Visualisation, discrétisation, clustering.
• Elle permet de représenter graphiquement des
données de grandes dimension.
• Introduits pour la première fois par Teuvo Kohonen
en 1982
Nuage de Réduire la dimension
données à n
dimensions Montrer les similarités
33
Mapper les données
◎Faire correspondre
chaque donnée à une
position dans l'espace
2D discret
◎Les données les
plus similaires sont
mappés dans la
même position
34
Source image: [3]
• L’objectif de SOM est de trouver un ensemble
de nœuds (codebook en terminologie SOM) et
affecter chaque donnée au nœud qui fournit
sa meilleure approximation.
• Dans la terminologie des réseaux neuronaux,
il existe un neurone associé à chaque
noeud[2].
• les données similaires sont placées à
proximité les uns des autres sur la grille SOM.
Principe de SOM
• Une grille SOM est composée de plusieurs nœuds de
forme circulaire, rectangulaire ou plus généralement
hexagonale,
• Chaque nœud possède :
- Une position fixe sur la grille SOM.
- Un vecteur de poids de la même dimension que
l’espace d’entrée.
- Chaque élément de donnée en entrée est
"mappé" ou "lié" à un nœud sur la grille de la carte.
- Un nœud peut représenter plusieurs
échantillons d’entrées.
La grille SOM
Couche de calcul
Vecteur de
donnée
37
Algorithme SOM
1: Initialiser les nœuds aléatoirement.
• 2: répéter
- Sélectionner un élément
- Déterminer le noeud le plus proche de l’objet
- Mettre à jour ce noeud et les noeuds dans un voisinage
spécifié.
wi(t+1) = wi(t) + h(i,t)(xi – wi(t)) si i voisinage
wi(t+1) = wi(t) si i voisinage
• avec h(i,t) = (t).v(t)
((t) : Le taux d’apprentissage. v(t) :la fonction de voisinage):
v(t)= σ0exp(-S²/σ²(t)
• Tel que: S²=d²(i,i*) et σ²(t)=σ0exp(t/tMax),α(t)=α0exp(t/tMax). σ0,, tMax , et α0
sont les paramètres du modèle.
3- Faire décroître la taille de la zone de voisinage des nœuds gagnants (la
zone qui contient les neurones subissant la transformation).
4- Faire décroître le coéfficient d’apprentissage, (t),
5- Arrêt: Les nœuds ne changent pas beaucoup ou nombre d’itérations
dépassé
6- Affecter chaque élément à son nœud le plus proche et retourner le
résultat.
Algorithme détaillé
Initialisation
Choix du vecteur donnée
Trouver le BMU
Déterminer le voisinage
Ajuster les poids
Répéter jusqu’à convergence
40
Source image: [4]
Algorithme détaillé
Initialisation
Choix du vecteur donnée
Trouver le BMU
Déterminer le voisinage
Ajuster les poids
Répéter jusqu’à convergence
41
Source image: [4]
Algorithme détaillé
Initialisation
Choix du vecteur donnée
◎Aléatoirement
Trouver le BMU ◎Par balayage
Déterminer le voisinage séquentiel de
l’espace de
Ajuster les poids
données
Répéter jusqu’à convergence
42
Source image: [4]
Algorithme détaillé
Initialisation
Choix du vecteur donnée
Trouver le BMU
Déterminer le voisinage
Ajuster les poids
Répéter jusqu’à convergence
43
Source image: [4]
Algorithme détaillé
Initialisation
Choix du vecteur donnée
Trouver le BMU
Déterminer le voisinage
Ajuster les poids
Répéter jusqu’à convergence ◎Taille du
voisinage décroit à
Source image: [4] chaque itération 44
Algorithme détaillé
Initialisation
Choix du vecteur donnée
Trouver le BMU
Déterminer le voisinage
Ajuster les poids % d’apprentissage: décroit
par itération
Répéter jusqu’à convergence ◎ Magnitude de l’ajustement
proportionnelle à la distance
45
Source image: [4]
Algorithme détaillé
Initialisation
Choix du vecteur donnée
Trouver le BMU
Déterminer le voisinage
Ajuster les poids
Répéter jusqu’à convergence
46
Source image: [4]
Clustering
• Appliquer le clustering hiérarchique sur la
carte SOM:
• les nœuds adjacents de la carte topologique
appartiendront à la même classe.
• Pouvoir traiter des très grandes bases, tout en
bénéficiant des avantages de la CAH.
Exemple de clustering
SOM : Caractéristiques
Avantages Inconvénients
• Préserve la topologie dans les • Voisinage fixe: on ne peut casser
deux sens les liaisons entre neurones même
• Processus d’apprentissage pour mieux représenter les
rapide données discontinues.
% K -means
◎Choix du nombre de classes K vs nombre de neurones
◎Les deux sont moins efficaces que DBSCAN quand les données ne
sont pas linéairement séparés
◎
49
Conclusion
Source image: [8]
