Année Universitaire 2021-2022
Mastère
"Business Analytics & Data Science" (BADS)
Atelier Fouille de données
Les méthodes de classification non
supervisées
ZOUAOUI Slim
Introduction
La classification a pour but de regrouper des individus en classes homogènes en fonction de
l’étude de certaines caractéristiques des individus. Par classes homogènes, on entend regrouper
les individus qui se ressemblent et séparer ceux qui sont éloignés.
Il y a alors deux approches distinctes :
– La classification automatique, qui fonctionne selon des algorithmes formalisés ;
– La classification subjective. Celle-ci est effectuée par les praticiens, en fonction de leurs
études qualitatives et de leurs intuitions.
Comme souvent dans l’analyse de données, les meilleures solutions se trouveront dans une
combinaison des deux approches. Dans ce cours, nous aborderons uniquement la classification
automatique.
Introduction
La classification automatique se divise en deux catégories :
La classification automatique hiérarchique : il s’agit d’effectuer une partition de classes de
plus en plus vaste (classification hiérarchique ascendante) ou de moins en moins vaste
(classification automatique descendante). Nous développerons l’algorithme de la classification
hiérarchique ascendante.
La classification automatique non-hiérarchique. Dans ce cas, le nombre de classes de la
partition est fixé en avance. La méthode des centres mobiles illustrera cette approche. La
généralisation de cette méthode, que nous n’introduirons pas ici, conduit à la méthode des
nuées dynamiques.
I- Les Notions
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 satisfait les propriétés d’un indice de dissimilarité.
Matrice des distances
Pour un nuage d’individus, on peut résumer l’ensemble des distances entre individus au sein
d’une matrice des distances que l’on note D. Chaque coefficient dij représente la distance
entre l’individu Mi et l’individu Mj . Par exemple, si l’on choisit comme critère de
ressemblance la distance euclidienne, on a dij = d(Mi,Mj) = .
Avec deux points (M1,M2) qui ont 2 variables uniquement : (x1, y1) et (x2, y2).
Une matrice de distances est une matrice carré, symétrique (dij = dji), de coefficients
positifs (dij ≥ 0) et de coefficients nuls sur la diagonale (dii = d(Mi,Mi) = 0).
I- Les Notions
La notion d’Inertie
Soit une classification en k groupes d'effectifs n1, ... ,nk, les individus étant des points d'un
espace euclidien. Notons les groupes G1, ... ,Gk, et g1, ... ,gk leurs centres de gravité (gest le
centre de gravité du nuage).
I- Les Notions
Une partition pour être bonne doit satisfaire les deux critères suivants :
– Les individus proches doivent être regroupés : chaque classe doit être le plus homogène
possible.
– Les individus éloignés doivent être séparé : les classes de la partition doivent être éloignées
les unes des autres.
Publicité
L’inertie est une mesure de l’homogénéité d’un ensemble de points (nuage ou classe). Une
classe (ou un nuage) sera d’autant plus homogène que son inertie totale sera faible.
L’inertie intraclasse mesure l’homogénéité de l’ensemble des classes. Plus l’inertie
intraclasse est faible, plus la partition est composée de classes homogènes.
L’inertie interclasse mesure la séparation entre les classes d’une partition. Plus l’inertie
interclasse est grande plus les classes sont distinctement séparées.
Théorème de Huygens :
Inertie totale = Inertie inter-classe + Inertie intra-classe
Itot = Iinter + Iintra
Choix de la méthode de classification
II- La classification K-means
(Agrégation autour des centres mobiles)
L’algorithme des K-moyennes permet de trouver des classes dans des données.
les classes qu’il construit n’entretiennent jamais de relations hiérarchiques: une classe
n’est jamais incluse dans une autre classe
L’algorithme fonctionne en précisant le nombre de classes attendues.
L’algorithme calcule les distances Intra-Classe et Inter-Classe.
Il travaille sur des variables continues.
Principe Algorithmique
Entrée :
k le nombre de groupes cherchés
DEBUT
Choisir aléatoirement les centres des groupes
REPETER
i.
ii.
Affecter chaque cas au groupe dont il est le plus proche au son centre
Recalculer le centre de chaque groupe
(stabilisation des centres)
(nombre d'itérations =t)
JUSQU‘A
OU
FIN
II- La classification K-means
(Agrégation autour des centres mobiles)
II- La classification K-means
(Agrégation autour des centres mobiles)
II- La classification K-means
(Agrégation autour des centres mobiles)
II- La classification K-means
(Agrégation autour des centres mobiles)
II- La classification K-means
(Agrégation autour des centres mobiles)
Le processus se stabilise nécessairement et l’algorithme s’arrête soit lorsque deux itérations
successives conduisent à la même partition, soit lorsqu’un critère convenablement choisi (par
exemple, la mesure de la variance intra-classes) cesse de décroître de façon sensible, soit
encore parce qu’un nombre maximal d’itérations a été fixé à priori.
Généralement, la partition obtenue finalement dépend du choix initial des centres.
Justification élémentaire de l’algorithme
La variance intra-classes ne peut que décroître (Ou rester stationnaire) entre l’étape m et
l’étape m+1. Des règles d’affectation permettent de faire en sorte que cette décroissance soit
stricte et donc de conclure à la convergence de l’algorithme puisque l’ensemble de départ I est
fini.
II- La classification K-means
Publicité
(Agrégation autour des centres mobiles)
II- La classification K-means
(Agrégation autour des centres mobiles)
III- La classification hiérarchique
(classification hiérarchique ascendante)
Le principe de l’algorithme consiste à créer, à chaque étape, une partition obtenue en agrégeant
deux a deux les éléments les plus proches. On désignera alors par éléments à la fois les
individus et les regroupements d’individus générés par l’algorithme. Il y a différentes manières
de considérer le nouveau couple d’éléments agrégés, d’ou un nombre important de variante de
cette technique.
L’algorithme ne fournit pas une partition en q classes
d’un ensemble de n objets mais une hiérarchie
de partition, se présentant sous la forme d’arbres
appelés également dendrogrammes
et contenant n-1 partitions.
L’intérêt de ces arbres est qu’ils peuvent donner
une idée du nombre de classes existant
effectivement dans la population.
III- La classification hiérarchique
(classification hiérarchique ascendante)
Distance entre éléments et entre groupes
On suppose au départ que l’ensemble des individus à classer est muni d’une distance. On
construit alors une première matrice de distances entre tous les individus.
Une fois constitué un groupe d’individus, il convient de se demander ensuite sur quelle base on
peut calculer une distance entre un individu et un groupe et par la suite une distance entre deux
groupes. Ceci revient à définir une stratégie de regroupements des éléments, c’est-à-dire se
fixer des règles de calcul des distances entre groupements disjoints d’individus, appelées
critères d’agrégation. Cette distance entre groupements pourra en général se calculer
directement à partir des distances des différents éléments impliqués dans le regroupement.
III- La classification hiérarchique
(classification hiérarchique ascendante)
Par exemple si x, y, z sont trois objets, et si les objets x et y sont regroupés en un seul élément
noté h, on peut définir la distance de ce groupement à z par la plus petite distance des divers
éléments de h à z :
d(h,z) = Min {d(x,z), d(y,z) }
Cette distance s’appelle le saut minimal (single linkage) (Sneath,1957 Johnson,1967) et
constitue un critère d’agrégation.
On peut également définir la distance du saut maximal (ou : Diamètre) en prenant la plus
grande distance des divers éléments de h à z :
d(h,z) = Max {d(x,z), d(y,z)}
Une autre règle simple et fréquemment employée est celle de la distance moyenne; pour deux
objets x et y regroupés en h :
d(h, z) = {d(x, z) + d(y, z)} / 2
III- La classification hiérarchique
(classification hiérarchique ascendante)
Par exemple si x, y, z sont trois objets, et si les objets x et y sont regroupés en un seul élément
noté h, on peut définir la distance de ce groupement à z par la plus petite distance des divers
éléments de h à z :
d(h,z) = Min {d(x,z), d(y,z) }
Cette distance s’appelle le saut minimal (single linkage) (Sneath,1957 Johnson,1967) et
constitue un critère d’agrégation.
On peut également définir la distance du saut maximal (ou : Diamètre) en prenant la plus
grande distance des divers éléments de h à z :
d(h,z) = Max {d(x,z), d(y,z)}
Publicité
Une autre règle simple et fréquemment employée est celle de la distance moyenne; pour deux
objets x et y regroupés en h :
d(h, z) = {d(x, z) + d(y, z)} / 2
III- La classification hiérarchique
(classification hiérarchique ascendante)
Principe Algorithmique
III- La classification hiérarchique
(classification hiérarchique ascendante)
Algorithme de classification
L’algorithme fondamental de classification ascendante hiérarchique se déroule de la façon
suivante :
Étape 1 : il y a n éléments à classer (qui sont les n individus);
Étape 2 : on construit la matrice de distances entre les n éléments et l’on cherche les deux
plus proches, que l’on agrège en un nouvel élément. On obtient une première partition à n-1
classes;
Étape 3 : on construit une nouvelle matrice des distances qui résultent de l’agrégation, en
calculant les distances entre le nouvel élément et les éléments restants (les autres distances
sont inchangées). On se trouve dans les mêmes conditions qu’à l’étape 1, mais avec
seulement n-1 éléments à classer et en ayant choisi un critère d’agrégation. On cherche de
nouveau les deux éléments les plus proches, que l’on agrège. On obtient une deuxième
partition avec n-2 classes et qui englobe la première.
Étape m : on calcule les nouvelles distances jusqu’à n’avoir plus qu’un seul élément
regroupant tous les objets et qui constitue la dernière partition.
III- La classification hiérarchique
(classification hiérarchique ascendante)
Le Dendogramme
Durant les étapes d’un algorithme de classification hiérarchique, on est en train de
construire un dendrogramme.
Le dendrogramme indique les objets et classes qui ont été fusionnées à chaque itération.
Le dendrogramme indique aussi la valeur du critère choisi pour chaque partition rencontrée
Il donne un résumé de la classification hiérarchique
Chaque palier correspond à une fusion de classes
Le niveau d’un palier donne une indication sur la qualité de la fusion correspondante
Toute coupure horizontale correspond à une partition
III- La classification hiérarchique
(classification hiérarchique ascendante)
Simulation du CAH
III- La classification hiérarchique
(classification hiérarchique ascendante)
Simulation du CAH
III- La classification hiérarchique
(classification hiérarchique ascendante)
Simulation du CAH
III- La classification hiérarchique
(classification hiérarchique ascendante)
Coupure du Dendrogramme
III- La classification hiérarchique
(classification hiérarchique ascendante)
Critère d’agrégation selon la variance
A l’étape initiale, l’inertie Intra-classes est nulle et l’inertie inter-classes est égale à l’inertie
totale du nuage puisque chaque élément terminal constitue à ce niveau une classe. A l’étape
finale, c’est l’inertie inter-classes qui est nulle et l’inertie intra-classes est équivalente à
l’inertie totale puisque l’on dispose à ce niveau d’une partition en une seule classe. Par
conséquent, au fur et à mesure que l’on effectue des regroupements, l’inertie intra-classes
Publicité
augmente et l’inertie inter-classes diminue.
Le principe de l’algorithme d’agrégation selon la variance consiste à rechercher à chaque
étape une partition telle que la variance interne de chaque classe soit minimale et par
conséquent la variance entre les classes soit maximale.
III- La classification hiérarchique
(classification hiérarchique ascendante)
Exercice Application
III- La classification hiérarchique
(classification hiérarchique ascendante)
Exercice Application
IV- La classification Mixte
Principe de la classification mixte
L’algorithme de classification mixte procède en
trois phases: l’ensemble des éléments à classer
subit un partitionnement initial (centres mobiles)
de façon à obtenir quelques dizaines, voire
quelques centaines de groupes homogènes; on
procède ensuite à une agrégation hiérarchique de
ces groupes, dont le dendrogramme suggérera
éventuellement le nombre de classes finales à
retenir; et enfin, on optimise (encore par la
technique des centres mobiles) la ou les partitions
correspondant aux coupures choisies de l’arbre.
IV- La classification Mixte
Principe de la classification mixte
L’algorithme de classification mixte procède en
trois phases: l’ensemble des éléments à classer
subit un partitionnement initial (centres mobiles)
de façon à obtenir quelques dizaines, voire
quelques centaines de groupes homogènes; on
procède ensuite à une agrégation hiérarchique de
ces groupes, dont le dendrogramme suggérera
éventuellement le nombre de classes finales à
retenir; et enfin, on optimise (encore par la
technique des centres mobiles) la ou les partitions
correspondant aux coupures choisies de l’arbre.
IV- La classification Mixte
Les étapes de la classification mixte
Cette première étape vise à obtenir, rapidement et à un faible coût, une partition des n objets en k
classes homogènes, où k est largement plus élevé que le nombre de classes désiré dans la population, et
largement plus petit que n. Nous utilisons, pour ce partitionnement initial en quelques dizaines de
classes, l’algorithme d’agrégation autour de centres mobiles. Cette procédure augmente l’inertie entre
les classes à chaque itération et produit une partition en un nombré fixé au préalable de classes mais qui
dépend du choix initial des centres. Ces groupes d’individus ou d’éléments qui apparaissent toujours
dans les mêmes classes seront les éléments de base de l’étape suivante.
La seconde étape consiste à effectuer une classification ascendante hiérarchique où les éléments
terminaux de l’arbre sont les k classes de la partition initiale. Le but de l’étape d’agrégation
hiérarchique est de reconstituer les classes qui ont été fragmentées et d’agréger des éléments
apparemment dispersés autour de leurs centres d’origine.
La partition finale de la population est définie par coupure de l’arbre de la classification ascendante
hiérarchique. L’homogénéité des classes obtenues peut être optimisée par réaffectations.