Université de Tunis-Elmanar
Institut Supérieur d’Informatique
Cours : Machine Learning
Semestre I : L3CS
Chapitre 4: Classification Ascendante
Hiérarchique
présenté par:
Mohamed Sahbi Bahroun
Année Universitaire 2021/2022 1
Deux familles de méthodes
Méthodes Méthodes
Descriptives Prédictives
Arbres de Décisions
Analyse en
Composantes
Principales ACP
Analyse Discriminante
Méthodes des Centres
Mobiles Régression Linéaire
K-means
Régression Logistique
Classification
Ascendante
Hiérarchique
Réseaux de Neurones
2
Objectif des techniques
descriptives
visent à mettre en évidence des informations présentes mais cachées
par le grand volume des données
il n’y a pas de variable « cible » à prédire
projection du nuage de points sur un espace de dimension inférieure
pour obtenir une visualisation de l’ensemble des liaisons entre variables
et individus tout en minimisant la perte d’information (ACP)
trouver dans l’espace de travail des groupes homogènes d’individus
ou de variables
détection d’associations entre des invidus
3
Objectif des techniques de
classification
Distinguer des sous-ensembles (ou classes) distincts dans la population de départ.
Regrouper les objets en groupes, classes, familles, segments, clusters, de sorte que :
Tous deux objets d’un même groupe se ressemblent le plus.
Tous deux objets de groupes différents se distinguent le plus.
Le nombre de groupes est parfois fixé.
la classification se distingue du classement par le fait que les critères de classification ne sont pas connus a
priori (avant étude de la population). C’est la population qui détermine les critères.
La classification est le plus souvent un préalable à d’autres opérations de data mining.
La classification permet de limiter le nombre de variables par sous-ensemble.
La classification permet de rechercher des corrélations propres à chaque classe et donc plus précises.
il n’existe pas une solution unique au problème de la classification. Autrement dit, il n’y a pas « LA » bonne
classification, mais plusieurs classifications possibles.
visent à synthétiser des informations présentes complexes mais cachées par le volume des données
il n’y a pas de variable « cible » à prédire
4
Techniques de Classification
Par partitionnement : Deux classes sont toujours disjointes.
Principe : partitionnement des objets et évaluation des partitions.
Hiérarchiques : Deux classes sont disjointes ou l’une contient
l’autre.
Principe : décomposition hiérarchique d’ensembles d’objets.
Par Densité :
Principe : se base sur une fonction de densité ou de connectivité
5
Classification par
partitionnenement
6
Classification Hiérarchique
7
Classification hiérarchique :
deux approches
Clustering hiérarchique ascendant : CHA (Agglomératif)
Commencer avec les points en tant que clusters individuels.
A chaque étape, grouper les clusters les plus proches
jusqu’à obtenir 1 seul ou k clusters.
Clustering hiérarchique descendant (Divisif) : Commencer
avec 1 seul cluster comprenant tous les points. A chaque
étape, diviser un cluster jusqu’à obtenir des clusters ne
contenant qu’un point ou jusqu’à obtenir k clusters
8
Types de Classification
Par partitionnement : Deux classes sont toujours disjointes.
• Principe : partitionnement des objets et évaluation des partitions.
Hiérarchiques : Deux classes sont disjointes ou l’une contient l’autre.
• Principe : décomposition hiérarchique d’ensembles d’objets.
Par Densité :
• Principe : se base sur une fonction de densité ou de connectivité
9
Classification Ascendante
Hiérarchique
Principe : Chaque point ou cluster est progressivement absorbé par le
cluster le plus proche.
Algorithme
• Initialisation :
– Chaque individu est placé dans son propre cluster.
– Calcul de la matrice de ressemblance M entre chaque couple de clusters (ici les points)
• Répéter
– Sélection dans M des deux clusters les plus proches Ci et Cj .
– Fusion de Ci et Cj pour former un cluster Cg.
– Mise à jour de M en calculant la ressemblance entre Cg et les clusters existants.
• Jusqu’à fusion des 2 derniers clusters.
10
Structure des données à classer
Soit une matrice rectangulaire dont :
– lignes = individus
– colonnes = variables
Cette structure permet de classer individus ou variables
Soit une matrice carrée de similarités, distances entre :
– Individus
– variables (par exemple : la matrice des corrélations)
Cette structure permet aussi de classer individus ou
variables
11
Algorithme
Entrée : tableau de données (X)
Sortie : Indicateur de partition des individus
Calcul du tableau des distances entre individus
Chaque individu constitue un groupe (classe)
REPETER
Détecter les 2 groupes les plus proches
Les agréger pour n’en former qu’un seul
JUSQU’À tous les individus forment un seul groupe
Identifier le nombre adéquat de groupes
Procéder au partitionnement
Datamining : 2éme IDL 12
Dendrogramme
Durant les étapes d’un algorithmes 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
Datamining : 2éme IDL 13
Exemple de dendrogramme
On « coupe » l'arbre là où les branches sont longues
6
À un niveau de 5, il ne reste que 2 classes
5
3
Si on fixe un niveau de 3 (si on exige une distance
2 d’au moins 3 entre objets de classes différentes),
il y a 4 classes
1
Datamining : 2éme IDL 14
Exemple de dendrogramme
la hauteur d’une branche est proportionnelle à la perte d’inertie interclasse
6
À un niveau de 5, il ne reste que 2 classes
5
3
Si on fixe un niveau de 3 (si on exige une distance
2 d’au moins 3 entre objets de classes différentes),
il y a 4 classes
1
Datamining : 2éme IDL 15
Théoréme de Huyghens
Inertie Totale Inertie inter-classes Inertie intra-classes
La coupure au niveau du dendrogramme se fait lorsque les branches sont les plus
longues. Donc, lorsque l’inertie inter-classes est maximale.
Datamining : 2éme IDL 16
Simulation CAH
n individus / n classes
3
2
4
5
1 2 3 4 5
On construit la matrice de distance entre les n éléments
et on regroupe les 2 éléments les plus proches
Datamining : 2éme IDL 17
Simulation CAH
n -1 classes
3
2
4
5
1 2 3 4 5
Datamining : 2éme IDL 18
Simulation CAH
n -2 classes
1
3
2
4
5
1 2 3 4 5
Datamining : 2éme IDL 19
Simulation CAH
3
2
4
5
n -3 classes
1 2 3 4 5
Datamining : 2éme IDL 20
Simulation CAH
3
2
4
n -4 classes
5
1 2 3 4 5
Datamining : 2éme IDL 21
Simulation CAH
1 2 classes
3
2
4
5
1 2 3 4 5
classes1 classes2
Datamining : 2éme IDL 22
Simulation CAH
1 3 classes
3
2
4
5
1 2 3 4 5
classes1 classes2 classes3
Datamining : 2éme IDL 23
Avantages CAH
Permet de classer : des individus, des variables, des moyennes de
classes obtenues en sortie d’un algorithme des centres mobiles
si on classe des moyennes, on améliore les résultats si on connaît non
seulement les moyennes des classes, mais aussi les inerties intraclasse
et les effectifs des classes
S’adapte aux diverses formes de classes, par le choix de la distance
Permet de choisir le nombre de classes de façon optimale, grâce à des
indicateurs de qualité de la classification en fonction du nombre de
classes
Datamining : 2éme IDL 24
Exemple CAH
Datamining : 2éme IDL 25
Exemple CAH
Datamining : 2éme IDL 26
Exemple CAH
Coupure du dendrogramme au plus
grand écart entre deux centres de
classes
Datamining : 2éme IDL 27
