29 MARS 2025

INTELLIGENCE ARTIFICIELLE
APPRENTISSAGE SUPERVISE ET NON SUPERVISE

Dr Josky AIZAN
Table des matières
Chapitre 1 : Introduction Générale ......................................................................................................... 3
1.1. Aperçu sur l’Etat Actuel................................................................................................................. 3
1.2. Le Nouveau Paradigme ................................................................................................................... 3
1.3. Origines de l’Apprentissage Automatique ................................................................................ 4
1.4. Domaines de l’Apprentissage Automatique ............................................................................. 5
1.5. Définitions et Particularités .......................................................................................................... 6
1.6. Exemples d’Apprentissage Artificiel ........................................................................................... 8
Chapitre 2 : Apprentissage et Classification ...................................................................................... 10
2.1. Introduction ..................................................................................................................................... 10
2.2. Contexte Général............................................................................................................................ 10
2.3. Présentation de la Problématique ............................................................................................. 11
2.4. Données d’Apprentissage ............................................................................................................ 12
2.5. Types d’Apprentissage .................................................................................................................. 12
2.6. Notions Elémentaires .................................................................................................................... 14
Chapitre 3 : Apprentissage et Classification Supervisés ............................................................... 17
3.1. Introduction ..................................................................................................................................... 17
3.2. Formulation ..................................................................................................................................... 17
3.3. Problème Linéaire et Non-Linéaire ........................................................................................... 18
3.4. Classifieurs à mémoire ................................................................................................................. 20
Chapitre 4 : Apprentissage et Classification Non-Supervisés ...................................................... 35
4.1. Introduction ..................................................................................................................................... 35
4.2. Algorithme des Centres Mobiles ................................................................................................ 36
4.3. Classification Hiérarchique Ascendante ................................................................................. 43
Chapitre 1 : Introduction Générale

1.1. Aperçu sur l’Etat Actuel

Un bref historique dans le domaine de l’apprentissage artificiel, aussi communément

appelé apprentissage automatique -AA (ou Machine Learning, en anglais), nous
amènent à parler des trois grandes époques de l’ordinateur, plus précisément, au
tout début de l’informatique, de son évolution au fil du temps et enfin au monde
d’aujourd’hui et de demain.

De nos jours, nous pouvons constater, que l’évolution de l’informatique s’est faite
principalement sur deux axes :

• Gain en capacité à cumuler de l’information et à sa diffusion dans des domaines

tels que les fouilles de données (Data Mining), les entrepôts de données, les réseaux
et services web, sans oublié leurs applications sous-jacentes sous Smartphones,
d’une part, et

• Gain en intelligence des systèmes informatique, en particuliers, les domaines liés

à l’intelligence artificielle lesquels sont les plus touchés par cette avancée
technologique et comprennent particulièrement, les jeux, la parole, la vision par
ordinateur, etc.

1.2. Le Nouveau Paradigme

Dans cette matière, nous nous intéressons aux théories, algorithmes et applications
liés à un aspect particulier de l’intelligence artificielle (IA) : la faculté d’apprentissage.

De cette notion d’apprentissage, il devient facile de constater que le paradigme de

programmation classique a évolué, ainsi,

• Avant, programmer consiste à prescrire une logique pour faire exécuter (une
tâche).
 • Maintenant, on programme pour rendre intelligent, autrement dit, programmer
pour faire exécuter de manière intelligente des tâches nouvelles réputées
nécessitant du raisonnement et un jugement.

Par un tel mécanisme de programmation, nous serons en mesure de faire doter un

programme d’une aptitude d’apprentissage.

1.3. Origines de l’Apprentissage Automatique

Le Machine Learning est un domaine d'étude de l'IA qui vise à donner aux machines
la capacité d'apprendre.

La discipline de l’apprentissage automatique (AA) possède de riches fondements

théoriques. On sait, désormais, répondre à des questions comme :

- Quelles méthodes d’apprentissage sont les plus efficaces pour tel ou tel type de
problème ?

- Combien d’exemples d’entrainement faut-il fournir à un programme

d’apprentissage pour être certain qu’il apprenne avec une efficacité donnée ?
Etant donnée la variété d’apprentissages qu’on peut rencontrer, il est aisé de deviner
que les fondements de cette discipline, en occurrence l’apprentissage automatique,
proviennent de diverses sciences :

- Des mathématiques pour l’informatique : algèbre linéaire, la probabilité, la logique,

l’analyse élémentaire, …
- La théorie statistique de l’estimation,
 - L’apprentissage Bayésien,

- L’inférence grammaticale ou l’apprentissage par renforcement, et tant d’autres.

1.4. Domaines de l’Apprentissage Automatique

Les principaux domaines d’applications de l’apprentissage automatique (AA) sont les

fouilles de données et l’intelligence artificielle.

 La fouille de données (Data Mining, en anglais) est le processus d’extraction

de la connaissance : il consiste à sélectionner les données à étudier à partir
de bases de données (BDs) (hétérogènes ou homogènes), à épurer ces données
et enfin à les utiliser en apprentissage pour construire un modèle.

Exemples,

- Trouver une prescription pour un malade (patient) à travers des fichiers médicaux
antérieurs.

- Apprentissage de la reconnaissance de transactions frauduleuses par carte de

crédit, par examen des transactions passées avérées frauduleuses.

 L’intelligence artificielle, la vision par ordinateur, la robotique, l’analyse et la

compréhension des images, la reconnaissance de formes, reconnaître des
objets dans les vidéo et extraire des contenus sémantiques des images sont
autant d’applications qui requièrent la construction de modèles par
apprentissage automatique.

Exemples,

- Systèmes de vidéo surveillance pour la détection des intrus.

- Logiciel biométrique de reconnaissance de visages et d’empreintes digitales.

1.5. Définitions et Particularités

Parmi les principales caractéristiques et facultés adoptées par les modèles

d’apprentissage, nous citons : l’entrainement, la généralisation, l’adaptation,
l’amélioration, l’intelligibilité et la prédiction.

1.5.1. Apprentissage

L’apprentissage, ou Learning en anglais, c’est le processus de construire un modèle

général à partir de données (observations) particulières du monde réel.

Ainsi, le but est double :

- Prédire un comportement face à une nouvelle donnée.

- Approximer une fonction ou une densité de probabilité.

Deux (02) branches d’apprentissage existent :

- Apprentissage symbolique, issue de l’IA.

- Apprentissage numérique, issue des statistiques.

Dans la pratique, le mot entraînement (Training, en anglais) est souvent synonyme

de : apprentissage. Ainsi, en science cognitive, l’apprentissage est défini comme étant
la capacité à améliorer les performances au fur et à mesure de l’exercice d’une
activité.
Exemple, un joueur de jeu d’échec : assimile (par expérience, s’entraîne) et raisonne
(ceci lui procure une certaine intelligence ou puissance de raisonnement pour qu’il
puisse progresser) –c’est le cas pour un algorithme intelligent.

1.5.2. Adaptation

Elle peut être vue comme étant la disposition du modèle (algorithme ou système) à
corriger son comportement ou à remanier sa réponse (ex., prédiction) par rapport à
de nouvelles situations.
 Pour
les tâches de perception, en vision artificielle, on accumule les bonnes et mauvaises
expériences, et à partir d’elles, on peut faire évoluer les règles pour mieux effectuer
la tâche, c’est le phénomène d’adaptation ou d’amélioration.

1.5.3. Dilemme de l’Apprentissage : Précision Vs Généralisation

- Précision : c’est l’écart entre une valeur mesurée ou prédite par le modèle et une
valeur réelle.

- Généralisation : c’est la capacité de reconnaître de nouveaux exemples jamais

vus auparavant.

NB : Souvent, un seuil de généralisation est utilisé et est propre à chaque modèle

pendant l’apprentissage.

1.5.4. Intelligibilité

C’est amélioré la compréhension des résultats d’apprentissage, afin que le modèle

puisse fournir une connaissance claire et compréhensible, au sens interprétable
(en anglais, on parle de comprehensibility ou understandability).

Exemple, quand un expert extrait de la connaissance des bases de données (BDs), il

apprend une manière de les résumer ou de les formuler (expliquer, expliciter de
manière simple et précise).

D’un point de vue fouille de données, ça revient purement et simplement à contrôler

l’intelligibilité (clarté) d’un modèle obtenu.

Actuellement, la mesure d’intelligibilité se réduit à vérifier que la connaissance

produite est intelligible et que les résultats sont exprimés dans le langage de
l’utilisateur et la taille des modèles n’est pas excessive.
1.5.5. Classification

En analyse de données, la classification consiste à regrouper des ensembles

d’exemples (souvent, de manière non-supervisée) en classes. Ces classes sont
généralement organisées en une structure : clusters (groupes ou grappes).

1.5.5.1. Classification

C’est le processus de reconnaissance en intention (par leurs propriétés) des classes

décrites en extension (par les valeurs de leurs descripteurs).

Si les valeurs à prédire sont des classes en petit nombre, on parle alors de
classification.

1.5.5.2. Régression

Elle traite des exemples où les valeurs à prédire sont numériques.

Exemple, le nombre d’exemplaires d’un ouvrage qui seront vendus = 4.000. Cette
valeur peut être approchée au jour le jour, pendant que la vente continue sur une
période.

1.6. Exemples d’Apprentissage Artificiel

Soit une distribution (dispersion) de deux types d’étudiants en IA, par rapport aux
autres étudiants (étudiants IA et étudiants non-IA), mesurée sur deux
caractéristiques majeures : la note en Algorithmique (Algo.) et la note en base de
données (BD), et représentée par le graphe de la Fig. 1.1.

Problème : comment faire l’apprentissage ? Ça consiste en quoi ?

D’abord, c’est dire que la représentation visuelle (géométrique) est correcte par
rapport au réel.
 BD Espace de représentation

x x o xx x

o o x x o o

oo x x x

x o o x o xx

0 5 10 15 20 Algo.

Figure 1.1. Répartition des étudiants dans l’espace visuel géométrique des notes.

Enoncé de l’apprentissage :

- Trouver une règle qui décide, dans l’espace de représentation choisi, avec le
moins d’erreurs possibles, quel étudiant est de l’IA et quel étudiant ne l’est pas.
- Quelle sera cette règle ?

Règle : peut être une ligne (droite ou courbe) qui sépare les étudiants IA et non-IA.

- Si la règle de décision est une droite : le problème est linéaire (ex., équation de la
forme y=a.x+b).

L’apprentissage sera de trouver la meilleure droite, en optimisant un critère étudié.

- Si la règle de décision est une courbe : le problème est alors non-linéaire (ex.,
polynôme, log, tangente,…).

Une règle de décision comme courbe sera plus complexe, elle sera avec plus de
restriction (sur les notes des étudiants) pour l’apprentissage.

NB :

- La droite (linaire) choisie mène a une erreur mesurée par le nombre d’exemples
mal classés par rapport au nombre d’exemples bien classés (ex., environ 4/20).
- La droite est souvent moins précise que la courbe mais plus simple.
Chapitre 2 : Apprentissage et
Classification

2.1. Introduction

Le but de cet enseignement est de s’initier à l’apprentissage automatique et à la

modélisation de systèmes de classification ; mais, également, d’étudier et de pouvoir,
au final, concevoir des algorithmes de prédiction. De tels modèles seront capables
de prédire la nature (forme, apparence, texture, couleur, …) et/ou le comportement
(fonction, fonctionnement, variable, variations, …) de nouveaux exemples.

Cependant, la quantité de données récupérées par la technologie imagerie ou dans

des fichiers BD dans divers domaines est très conséquente. L’analyse directe de ces
données pourra donc s’avérer très lente ou trop complexe, voire impossible par des
méthodes traditionnelles. Le but principal des techniques d’optimisation (méthode
statistique, ACP, …) est de filtrer et réduire l’ensemble des données extraites ou
acquises du monde réel afin de sélectionner et ne porter intérêt qu’à un sous-
ensemble des variables les plus pertinentes pour le problème à traiter.

Exemple, soit un vecteur caractéristique , , représentant les

caractéristiques d’une classe objets de la nature (voitures, plantes, …), ainsi cet
espace de dimension est réduit en un espace de dimension , avec , qui est
aussi représentatif et discriminant que celui de dimension , mais plus facile à
traiter.

2.2. Contexte Général

Une fois les données acquises du terrain ou du réel (images, vidéos, fichiers BD) sous
forme de données brutes, il faut les analyser et en extraire de l’information sous
forme de nouvelles connaissances, de descripteurs ou de vecteur de caractéristiques.
Lorsque les données sont conséquentes leur traitement peut se faire par différentes
méthodes en particulier le traitement statistique (dénombrement) lequel est un
privilégié des disciplines de l’IA.
Les deux disciplines (intelligence artificielle –IA et fouille de données –FD) regroupent
en commun différentes techniques de construction de modèles, elles sont
récapitulées sur le schéma de la Figure 2.1.

Construction de Modèles
(en IA et FD)

AA Méthodes Statistiques

 Analyse en composante principale (ACP)

Appr. Par Appr. Non-
Appr. Semi -
Appr.  Analyse Factorielle (AF)
supervisé/a
renforcement supervisé Supervisé
utomatique

Clustering ou Règles Classification Régression

regroupement d‟association (sortie discrète) (sortie continue)

Figure 2.1. Schéma des différentes techniques issues de l’IA et

FD pour la construction de modèles de données.

Les deux principales composantes de la construction de modèles d’apprentissage et

de classification sont des techniques issues de la statistique multivariée ou bien
des techniques d’apprentissage automatique (AA).

Nous nous intéressons plus spécialement aux techniques de l’apprentissage

automatique.

2.3. Présentation de la Problématique

Les méthodes dédiées à l’AA visent à construire des modèles génériques à partir de
données fournies (observées). Ainsi, ces observations ou échantillons sont vues
comme des exemples illustrant les relations entre des variables observées.

Le but : est alors d’utiliser ces exemples pour en déduire des caractéristiques ou
propriétés liant ces données entre elles.
Problème : la difficulté repose sur le fait que les données de l’ensemble
d’apprentissage ne contiennent souvent qu’un nombre fini d’exemples (cas, des
méthodes statistiques).

Ainsi, on ne dispose donc pas de l’ensemble de tous les comportements ou états

possibles, en fonction de toutes les entrées possibles (cas, des modèles non-
déterministes ou probabilistes).

2.4. Données d’Apprentissage

Les données d’apprentissage sont, souvent, réparties en 3 catégories :

- L’ensemble d’apprentissage ou population d’entrainement : constitue

l’ensemble des candidats ou exemples (images, attributs, DB, …) utilisés pour
générer le modèle d’apprentissage. Alors que,

- l’ensemble de Test est constitué des candidats sur lesquels sera appliqué le
modèle d’apprentissage (pour tester et corriger l’algorithme).

- L’ensemble de validation peut être utilisé lors de l’apprentissage (comme sous

population de l’ensemble d’apprentissage) afin de valider (intégrer) le modèle et
d’éviter le surapprentissage.

NB : Selon les domaines, les connaissances ou données d’apprentissage (tel en IA)

peuvent être de diverses formes : mots, phrases, variables ou attributs, des vecteurs
de valeurs : définissant un ensemble de propriétés d’un objet, …

2.5. Types d’Apprentissage

En fonction du type de problème que l’on se pose, voir Fig. 2.1, on peut avoir à mettre
en place différents types d’apprentissage :

- Apprentissage Supervisé : Cette approche a pour objectif la conception d’un

modèle reliant des données d’apprentissage à un ensemble de valeurs de sortie
(un comportement).
 e1 Modèle ou s1
…
… Algorithme …
en d’apprentissage sn

Figure 2.3. Schéma d’un modèle supervisé.

- Apprentissage par Renforcement : Les données en entrée sont les mêmes que
pour l’apprentissage supervisé, cependant l’apprentissage est guidé par
l’environnement sous la forme de récompenses ou de pénalités données en
fonction de l’erreur commise lors de l’apprentissage.

- Apprentissage Non-Supervisé : Il vise à concevoir un modèle structurant

l’information. La différence ici est que les comportements (ou catégories ou encore
les classes) des données d’apprentissage ne sont pas connus, c’est ce que l’on
cherche à trouver.

C1 : classe 1
e1 Modèle ou
… Algorithme
en d’apprentissage C3
C2

Figure 2.4. Schéma d’un modèle non supervisé.

- Apprentissage Semi-Supervisé : Les données d’entrée sont constituées d’exemples

étiquetés et non étiquetés. Ce qui peut être très utile quand on a deux types de
données, car cela permet de ne pas en laisser de côté et d’utiliser toute l’information.

e1 s1
e2 Modèle ou ?
… …
ek Algorithme ?
en-1 … d’apprentissage
… sn-1
en ?
 Figure 2.5. Schéma d’un modèle semi-supervisé ou incrémental.

- NB : Dans notre cas, nous nous concentrerons sur les types d’apprentissage à
savoir supervisé et non-supervisé.

2.6. Notions Elémentaires

2.6.1. Données
Elles représentent l’ensemble des informations relatives à un sujet ou objet d’étude.
Aussi, une donnée constitue un attribut parmi d’autres si un objet d’une classe ou
catégorie (ex., voiture) devrait être représenté par un ensemble de valeurs.

Une donnée devrait être spécifique et caractéristique d’une valeur ou propriété de

l’objet que le système est censé discriminer ou destiné à discerner parmi les objets
de l’environnement auquel il est dédié.

Exemples, la couleur RGB d’une orange, la forme ovale de la poire, le motif de la

texture d’un tissu, …

2.6.2. Vecteur de Caractéristiques

Un vecteur caractéristique ou descripteur, ou encore vecteur de descripteurs, est une
entité cohérente d’une ou plusieurs données caractéristiques ou propriétés
regroupées, structurées et codées.

Exemple, vecteur caractéristique relatif aux avions = (prix, masse, type fuselage,
motorisation, nombre réacteurs, nombre de places, type de trainée, …).

2.6.3. Classe
Une classe, une catégorie ou un groupe, d’objets sont des termes analogues. Une
classe enseigne sur un ensemble d’objets ou échantillons de même nature et ayant
le même vecteur descripteur comme modèle de description.
2.6.4. Notion de Distance
2.6.4.1. Distance d’un objet à une classe

La distance d’un point (donnée ou objet) à une partie (partition ou classe)

, partie de l’espace métrique , est donnée par : .

2.6.4.2. Distance entre deux classes

La distance entre deux ensembles (classes) d’objets et , avec et deux

parties non vides d’un espace métrique muni d’une distance , est donnée par :

2.6.5. Distances Usuelles

2.6.5.1. Distance de Manhattan

2.6.5.2. Distance Euclidienne

Dans le plan 2D :

De manière générale, pour des descripteurs de dimension :

2.6.5.3. Distance de Tchebychev

2.6.5.4. Distance de Mahalanobis

Elle se base sur la corrélation entre les variables (pour mesurer la ressemblance entre
les descripteurs des échantillons) par lesquelles différents modèles peuvent être
identifiés et analysés. C'est, aussi, une manière utile pour déterminer la similarité
entre une série de données (où chaque donnée est un vecteur de valeurs) inconnue
et d’autres connues.

La distance de Mahalanobis tient compte de la variation (variance) et de la covariation

entre les données ; son calcul se fait à travers la matrice de covariance qui permet
de quantifier les écarts conjoints des donnés ou variables par rapport à leurs
espérances respectives.
Chapitre 3: Apprentissage et
Classification Supervisés

3.1. Introduction

Les techniques d’apprentissage supervisé permettent de construire des modèles à

partir d’exemples d’apprentissage ou d’entrainement dont on connait le
comportement ou la réponse. Ces modèles peuvent, ensuite, être utilisés dans
différentes applications, telles que la prédiction ou la classification.

Toutefois, selon la complexité du problème, nous pouvons aussi distinguer deux

catégories de solutions : il serait mieux d’approcher les données traitées par une
fonction exacte, si la complexité est faible ; cependant, en cas de complexité élevée,
nous aurons plus de chance d’approcher toutes les données que si nous optons pour
une solution qui représente le modèle de données par une heuristique.

Les techniques dites de modélisation prédictive (predictive modelling ou predictive

data mining) analysent un ensemble de données et en extraient un ensemble de
règles, formant un modèle prédictif, afin d’essayer de prédire, avec la plus grande
précision, le comportement de nouvelles données. Les techniques dans le domaine
de la prédiction sont les plus classiques, car on peut directement les utiliser dans
des applications concrètes.

3.2. Formulation

Supposons qu’un jeu de données d’apprentissage est formulé par variables

(descripteur de données à valeurs) le décrivant (par exemple, le cas des images en
forme de matrices d’entiers).

Nous disposons alors, pour un ensemble donné, de deux types d’informations : un

vecteur de valeurs prises par chaque variable, et une valeur de sortie
appelée valeur supervisée ou réponse supervisée (qui peut être une classe si l’on
prend un problème de classification).
Si nous formalisons le problème d’apprentissage décrit précédemment, nous
pouvons le représenter comme un ensemble de couples entrée-sortie , avec
∈ , étant le nombre d’exemples ou d’échantillons disponibles.

On appelle alors fonction d’apprentissage la fonction notée : → qui associe un

résultat (valeur) supervisé à chaque vecteur d’entrée.

Le but d’un algorithme d’apprentissage supervisé sera donc d’approcher cette fonction
, uniquement à partir des exemples d’apprentissage.
En fonction du résultat (comportement) supervisé que l’on veut obtenir, on peut
distinguer deux types problèmes :
- Régression : lorsque le résultat supervisé que l’on cherche à estimer est une
valeur dans un ensemble continu de réels.
- Classification : lorsque l’ensemble des valeurs de sortie est discret. Ceci revient
à attribuer une classe (aussi appelée étiquette ou label) pour chaque vecteur
d’entrée.

Nous nous plaçons souvent dans le cas de problème classification à deux classes (2-
classe) qui peut être facilement étendu à N-classe.

3.3. Problème Linéaire et Non-Linéaire

Les méthodes de classification supervisée peuvent être basées sur

- des hypothèses probabilistes (cas du classifieur naïf bayésien),

- des notions de proximité (exemple, k plus proches voisins) ou
- des recherches dans des espaces d'hypothèses (exemple, arbres de décisions).

En fonction du problème, il faut pouvoir choisir le classifieur approprié, c'est-à-dire

celui qui sera à même de séparer au mieux les données d'apprentissage.

On dit qu'un problème est linéairement séparable si les exemples de classes

différentes sont complètement séparables par un hyperplan (appelé hyperplan
séparateur, ou séparatrice). Ce genre de problème se résout par des classifieurs assez
simples, qui ont pour but de trouver l'équation de l'hyperplan séparateur.
Mais, le problème peut également être non séparable de manière linéaire comme
illustré dans la figure 3.1. Dans ce cas, il faut utiliser d'autres types de classifieurs,
souvent plus longs à paramétrer, mais qui obtiennent des résultats plus précis.

Figure 3.1. A Gauche : Problème linéairement séparable (Frontière

linéaire). A Droite : Problème non linéairement séparable.

Remarque,

Un problème, initialement, non linéairement séparable peut s'avérer séparable

avec l'ajout d'un nouvel attribut (cf. figure 3.2). D'où l'intérêt d'un choix judicieux de
ces attributs. C'est ce principe qui est utilisé par le classifieur Support Vector Machine
(SVM) que nous verrons dans la suite (cf. section 3.6.3).

Figure 3.2. Même problème considéré avec 2 ou 3 attributs.

3.4. Classifieurs à mémoire

L'intérêt de ces classifieurs est qu'ils ne nécessitent aucune phase d'apprentissage

ou d’entrainement. Ainsi, ils permettent de déduire directement la classe d'un nouvel
exemple à partir de l'ensemble d'apprentissage.

3.4.1. K-plus proches Voisins

Le classifieur des k plus proches voisins ou k-ppv (k-Nearest Neighbor ou k-NN, en

anglais) est l'un des algorithmes de classification les plus simples.

Principe : Un exemple est classifié par vote majoritaire de ses k "voisins" (par mesure
de distance), c'est-à-dire qu'il est prédit de classe C si la classe la plus représentée
parmi ses k voisins est la classe C.

Un cas particulier est le cas où k = 1, l'exemple est alors affecté à la classe de son
plus proche voisin.

L'opérateur de distance le plus souvent utilisé est la distance Euclidienne,

cependant, en fonction du problème, on peut encore utiliser les distances de
Hamming, de Mahalanobis, etc.

Remarques,

- Le choix du k est très important pour la classification.

- On s’abstient de choisir des valeurs paires de k, pour éviter les cas d'égalité.

Exemple, sur la figure 3.3, on peut voir l’effet du choix de k sur le résultat de la
classification. En effet, si k=1; 3 l'exemple à prédire (noté "?") serait classifié comme
étant de la classe "X", mais si k=5, il serait classifié comme étant de la classe "O".
Figure 3.3 Schéma d'une classification par la méthode k-NN
 Un
pseudo-algorithme des K plus proches voisins est donné par :

Pseudo-Algorithme ;

Déclarations

- M : nombre de classes d’apprentissage ;

- N : nombre d’exemples d’entrainement ;
- : ensemble d’apprentissage formé par les couples ; /* est
l’exemple d’apprentissage et sa classe d’appartenance */
- : exemple test /*dont on cherche la classe d’appartenance*/

Début

< On cherche à classer ?>;

Pour Chaque exemple ∈ Faire
< Calculer la distance entre et >;

FPour

< Trier les échantillons par ordre croissant des distances > ;
Pour les plus proches de (les premières – ayant les plus petites- ) Faire

< Compter le nombre d’occurrences de chaque classe > ;

FPour

< Attribuer à la classe la plus fréquente > ; /*Celle qui apparait le plus souvent*/

Fin.

3.4.2. Classifieur Naïf Bayésien

La classification naïve bayésienne repose sur l'hypothèse que les attributs sont
fortement (ou naïvement) indépendants. Elle est basée sur le théorème de Bayes
qui ne s'applique que sous cette hypothèse.

Théorème de Bayes est donné par : , avec est la probabilité

conditionnelle d'un événement sachant qu'un autre événement de probabilité non
nulle s'est réalisé.

Dans le cas d'une classification, on pose l'hypothèse selon laquelle un "vecteur

d'attributs (représentant un objet) appartient à une classe ", et l'on suppose que
 l'on
cherche à estimer la probabilité , c'est-à-dire la probabilité que l'hypothèse
soit vraie, considérant .

Ainsi, si l'on a un nouvel exemple dont on veut trouver la classe, on

va chercher la probabilité maximale d'appartenance à cette classe :

(3.1)

Cette équation est directement déduite du théorème de Bayes. En effet, comme

l'objectif est de faire une maximisation et que le dénominateur ne dépend pas de
, on peut le supprimer.

Cependant, cette probabilité pourrait être beaucoup trop compliquée à estimer, si

l'on considère le nombre de descriptions possibles. C'est alors que l'on utilise
l'hypothèse d'indépendance, qui nous permet de décomposer la probabilité
conditionnelle en un produit de probabilités conditionnelles. Le classifieur devient
alors :

(3.2)

Remarque,

- Avantage, ce classifieur est souvent utilisé, car très simple d'emploi.

- Inconvénient, cependant, il est très sensible à leur corrélation.

3.5. Classifieurs basés sur des Modèles : Arbres de Décision

3.5.1. Contexte Général

Les arbres de décision sont un outil très populaire de classification. Leur principe
repose sur la construction d'un arbre de taille limitée. La racine constitue le point de
départ de l'arbre et représente l'ensemble des données d'apprentissage. Puis ces
données sont segmentées en plusieurs sous-groupes, en fonction d'une variable
discriminante (un des attributs).

Exemple, sur la Figure 3.5, la première variable discriminante est la température

corporelle. Elle divise la population en deux sous-groupes : les personnes dont la
température est supérieure à 37°C et les autres. Le processus est ensuite réitéré au
deuxième niveau de l'arbre, ou les sous-populations sont segmentées à leur tour en
fonction d'une autre valeur discriminante (dans l'exemple, c'est la toux.
 Figure 3.5 Schéma d'un arbre de décision.

Une fois l'arbre construit à partir des données d'apprentissage, on peut prédire un
nouveau cas en le faisant descendre le long de l'arbre, jusqu'à une feuille. Comme
la feuille correspond à une classe, l'exemple sera prédit comme faisant partie de
cette classe.

Dans l'exemple, on peut en déduire qu'une personne qui a une température < 37°C
et qui a de la toux est prédite comme malade, tandis qu'une personne qui a une
température < 37°C mais pas de toux est considérée comme saine.

Lors de la création de l'arbre, la première question qui vient à l'esprit est le choix de
la variable de segmentation sur un sommet. Pourquoi par exemple avons-nous choisi
la variable "température" à la racine de l'arbre ? Il nous faut donc une mesure afin
d'évaluer la qualité d'une segmentation et sélectionner la meilleure variable sur
chaque sommet. Ces algorithmes s'appuient notamment sur les techniques issues
de la théorie de l'information, et notamment la théorie de Shannon.

L'intérêt des arbres de décision est en premier lieu leur lisibilité. En effet, il est très
simple de comprendre les décisions de l'arbre une fois celui-ci créé, ce qui n'est pas
toujours le cas pour les autres classifieurs que nous verrons. D'autre part,
l'algorithme de création des arbres de décision fait automatiquement la sélection
d'attributs jugés pertinents, et ce, même sur des volumes de données importants.

3.5.2. Idée et Propriétés Générales

Diviser récursivement et le plus efficacement possible les individus de l’ensemble

d’apprentissage par des tests définis à l’aide des variables jusqu’à ce que l’on obtienne
des sous-ensembles d’individus ne contenant (presque) que des exemples
appartenant à une même classe ! A la base, trois opérations seront nécessaires :

1. Décider si un nœud est terminal (tous les individus sont dans la même classe).
 2. Sélectionner un test à associer à un nœud (utiliser critères statistiques).

3. Affecter une classe à une feuille (nœud terminal)- la classe majoritaire !

3.5.3. Exemple Introductif

Décider si un patient est malade ou bien-portant (sain) selon sa température et s’il

a la gorge irritée. A partir des exemples (des patients), des attributs ou variables
(Température et Gorge-irritée), des classes (malade ou sain), construire l’arbre de
décision qui aura :

- 2 classes (malade et bien-portant). Température < 37.5°C ?

Oui Non
- 2 variables (température et gorge-
Gorge-Irritée ? Malade
irritée).
Oui Non
Malade Non-Malade

3.5.4. Classification et Règles

L’arbre de Décision (AD) permet de classer un nouvel exemple : (37.2, oui), c’est-à-
dire, Température=37.2 et Gorge-Irritée=oui, comme appartenant à la classe malade.

L’AD peut être traduit en un système de règles ; lesquelles pouvant être considérées
comme le pseudo-code ou l’algorithme de l’AD :

- Si (Temp. < 37.5) et (Gorge-irritée) Alors malade.

- Si (Temp. < 37.5) et Non (Gorge-irritée) Alors Sain.

- Si (Temp. ≥ 37.5) Alors malade.

3.5.5. Définition du Formalisme : Arbres de Décision

3.5.5.1. Vocabulaire
 Température < 37°C ?
Oui Non

Gorge-Irritée ? Malade
Oui Non
Nœud terminal
Malade Bien-portant ou feuille

Nœud intermédiaire ou test (chaque

nœud inter. est définit par un test
construit à partir d’une variable)

3.5.5.2. Inférence d’Arbres de Décision

Objectif : Inférer (déduire et aussi au sens de construire) un arbre de décision à

partir d’exemples.

Pour ce faire, on a besoin :

a. de comprendre la répartition de la population (ex., de patients) dans l’arbre.

Ainsi, il est intéressant de savoir mesurer le degré de mélange d’une
population.
b. de la définition d’une méthode d’inférence, en saisissant :
• Comment sélectionner le test à effectuer à un nœud ?
• Comment décider si un nœud est terminal ?  Quelle classe
associée à une feuille ?
c. Enfin, de comment tout écrire mathématiquement ?

3.5.6. Mélange et Degré de Mélange

Le calcul du degré de mélange des classes dans la population vient du besoin de

comparer les différents choix possibles.
Ainsi, de ce besoin, on introduit des fonctions qui permettent de mesurer le degré
de mélange d’une population dans les différentes classes.

Les propriétés de ces fonctions devraient être de la sorte :

- Le minimum est atteint lorsque tous les nœuds sont „„purs‟‟ („„purs‟‟ : si tous
les individus associés au nœud appartiennent à la même classe). Ainsi, le
mélange sera minimal (sinon nul).

- Le maximum est atteint lorsque les individus sont équirépartis entre les classes
(mélange maximal).

3.5.6.1. Exemples de Fonctions Mélanges

• Fonction d’Entropie

Avec, classe k et nœud p.

• Fonction de Gini

3.5.7. Notion de Gain

3.5.7.1. Représentation et Fonction Gain

- t : le test (la variable). p

- n : le nombre de modalités de t. Test t à n modalités

- i : la fonction pour mesurer le degré de

mélange. p1 p2 … pn

On introduit la fonction de gain :

Avec,

- : la proportion des individus de la position (nœud) p qui vont en position .

 - La position p est fixée !
- Le but est de chercher le test qui maximise le gain !

3.5.8. Algorithme de Construction d’un Arbre de Décision

Nous présentons le fonctionnement de l‟algorithme à travers un exemple.

3.5.8.1. Données et Notations

Cet algorithme d’apprentissage et de classification correspond au classifieur CART

(Classification And Regression Tree).

• Entrée
- n individus,
- variables continues ou discrètes,
- Une variable supplémentaire contenant la classe de chaque individu (c
classes).
• Sortie
- L’arbre de décision T construit.

Soient,

- : le nombre d’individus associés à la position (nœud) .

- : le nombre d’individus appartenant à la classe k en sachant qu’ils sont
associés à la position .

- : proportion des individus appartenant à la classe k parmi ceux de la

position .

3.5.8.2. Jeu de Données

Soit le tableau suivant récapitulant l’ensemble des clients d’une compagnie

d’assurance.

Id Montant Age (A) Résidence Etudes Internet

Client (M) (R) (E) (I)

1 Moyen moyen Village Oui Oui

2 élevé moyen Bourg Non Non
 3 Faible âgé Bourg Non Non
4 Faible moyen Bourg Oui Oui
5 Moyen jeune Ville Oui Oui
6 élevé âgé Ville Oui Non
7 Moyen âgé Ville Oui Non
8 Faible moyen village non non
• Variables

- M : salaire ou moyenne des montants sur le compte.

- A : âge du client.
- R : lieu de résidence du client.
- E : le client a fait des études supérieures ou non ?
- I : le client consulte ses comptes sur internet ou non ? (classe)

• Mélange Initial

Ainsi, avec 8 clients dont : 3 (oui) ont Internet (classe 1 : oui) et 5 non (classe 2 :
non), le mélange initial (selon Gini) :

3.5.8.3. Procédé

La construction est descendante : on commence par tester les candidats à la racine.

Au début, tous les individus sont regroupés (au niveau 0, la racine de l’arbre).

Ainsi, quatre (04) constructions sont possibles, suivant les variables : Montant
(M), âge (A), résidence (R) et études (E).

3.5.8.4. Tester les Candidats à la Racine

a. Construction selon la variable M (Montant)

 (3 , 5)
Montant (M) ?

Faible Moyen Élevé

Mélange(Faible) =
Gini (1 , 2) (2 , 1) (0 , 2)
Mélange(élevé) = 2 oui, 1 non 0 oui, 2 non Gini

On calcule le Gain selon la variable M

Mélange(Moyen)

b. Construction selon la variable A (âge)

Après avoir calculé les mélanges selon Gini, on calcule le Gain selon la variable A :

c. Construction selon la variable R (Résidence)

On calcule le Gain selon la variable R :

d. Construction selon la variable E (étude)

Après avoir calculé les mélanges selon Gini, on calcule le Gain par rapport la variable
E:
3.5.8.5. Quel Test Choisir ?
Variable Composition Gain
Test nœuds
Montant (M) (1, 2) ; (2, 1) ; (0, 2) 0,135
Age (A) (1, 0) ; (2, 2) ; (0, 3) 0,219
Résidence (1, 2) ; (1, 2) ; (1, 1) 0,010
(R)
Etudes (E) (3, 2) ; (0, 3) 0,169
Remarque,

- Sur la variable R, aucune discrimination sur aucune branche, ainsi on ne gagne

rien avec ce test !
- Sur la variable A, deux nœuds sur trois sont „„purs‟‟, ce qui semble intéressant
!

3.5.8.6. Le Premier Niveau de l’Arbre Appris

Age (A ) ?

Moyen âgé Jeune

Oui 2 oui, 2 non Non

Clients : 1, 2, 4, 8
L’étape suivante consiste à ignorer les valeurs (les supprimer du tableau de valeurs)
pour laquelle „„Age = jeune‟‟ et „„Age = âgé‟‟ (pour les lignes : 3, 5, 6, 7) et ne pas
prendre en considération la variable Age A (retirer la colonne Age).

Puis, continuer la construction des autres niveaux selon les variables restantes, à
savoir : M, R et E.

3.5.8.7. Tester les Candidats Suivants (Construction du 2ème Niveau)

a. Construction selon la variable M (Montant)

On calcule le Gain selon la variable M :

b. Construction selon la variable R (Résidence)

On calcule le Gain selon la variable R :

c. Construction selon la variable E (étude)

Après avoir calculé les mélanges selon Gini, on calcule le Gain par rapport la variable
E:

Remarque,

- Sur E, les deux (02) nœuds sont purs, et le gain est le plus élevé. Ainsi, le niveau
2 de l’arbre de décision est construit sur E.

- Cette construction est la dernière et termine l‟arbre puisque tous les nœuds ainsi
formés sont des feuilles (oui ou non).

3.5.8.8. Arbre Finalement Appris

 Age (A ) ? Jeune

Moyen âgé

Oui Etude (E) ? Non

Oui Non

Oui Non
NB : La structure de l’arbre de décision
construit dépend de l’ensemble d’apprentissage.

3.5.9. Faiblesses

- C’est un algorithme Glouton, sans backtrack (sans retracer ou trace arrière).

- Transposables en règles avec des règles ayant des attributs communs, en
particulier l’attribut utilisé à la racine.
- Présentent des difficultés avec les concepts disjonctifs (cf. agaricus-lepiota).
- Faiblesse du codage attributs-valeurs (ex., classification de molécules !).

3.5.10. Eviter le Sur-apprentissage

On pourrait calculer un arbre „„parfait‟‟ ou presque. Mai, en pratique, un tel arbre

n’existe pas toujours !

Ainsi, l’objectif est de construire un arbre avec la plus petite erreur de

classification possible.

En général,

- L’erreur d’apprentissage diminue à chaque étape.

- L’erreur réelle (de validation) diminue, se stabilise et puis augmente ! c’est le

phénomène de sur-apprentissage.

Ainsi, pour éviter le sur-apprentissage :

- On devrait pouvoir arrêter la croissance de l’arbre à tout moment, mais, à nos

jours, pas de critères théoriques à définir !

- D’où, le dilemme du risque : risque d’arrêter trop tôt contre (vs) le risque
d’arrêter trop tard !

Il existe des méthodes en deux phases :

1. construction de l’arbre.

2. élagage pour essayer de diminuer l’erreur réelle (de validation).

Chapitre 4 : Apprentissage et
Classification Non-Supervisés

4.1. Introduction

Il s’agit d’une tâche principale en intelligence artificielle et dans la fouille exploratoire

de données. C’est une technique d’analyse statistique des données très utilisée dans
de nombreux domaines y compris l’apprentissage automatique, la reconnaissance de
formes, le traitement d’images, la recherche d’information, etc.

L’idée est donc de découvrir des groupes au sein des données, de façon
automatique.

4.1.1. Types de Données

Les données traitées en classification automatique peuvent être de différents formats

et peuvent provenir de différentes sources : images, signaux, textes (caractères,
fichiers, attributs, …), sons, symboles ; ou encore toutes autres valeurs de
paramètres obtenues par d’autres types de mesures.

Par exemple, en reconnaissance des objets dans les images, les informations
collectées sur les objets à traiter seront des données multidimensionnelles, telles les
couleurs d’une zone de l’image ou les variations d’intensité lumineuse pour les
images infrarouges.

Exemple. Une image couleur contenant 𝒏𝒏 lignes et 𝒎𝒎 colonnes et donc 𝒏𝒏 𝐱𝐱 𝒎𝒎 pixels

couleurs. Chaque pixel, composé de trois composantes couleur : R (rouge), V (verte)
et B (bleue), peut être modélisé par une structure "pixel" composée au moins des
champs :
"couleur (R, V, B)" et "label" ; l’image quant à elle sera un tableau de 𝒏𝒏 𝐱𝐱 𝒎𝒎 structures
pixel.
4.1.2. Qu’est-ce qu’une Classe ?

Une classe (ou groupe) est un ensemble formé par des données homogènes : qui “se
ressemblent” au sens d’un critère de similarité (distance, densité de probabilité, etc.).

4.2. Algorithme des Centres Mobiles

Proposé par Lloyd, l’algorithme s’avère très utile pour la classification de données
uni- ou multidimensionnelles.

𝑲𝑲−𝒎𝒎𝒎𝒎𝒎𝒎𝒎𝒎𝒎𝒎 est un algorithme de minimisation alternée qui, étant donné un entier 𝑲𝑲,
va chercher à séparer un ensemble de points en 𝑲𝑲 clusters ou groupes (voir Figure
4.1).

Figure 4.1 Clustering sur un Ensemble de Points (Objets) 2D, en 3 Clusters.

4.2.1. Combien de Classes ?

Le nombre 𝑲𝑲 représente le nombre de classes que l’algorithme doit former à partir

des propriétés des échantillons ou exemples.

Le nombre de groupes 𝐾𝐾 peut être supposé fixe (donné par l’utilisateur) ou fixé par la
nature du problème à traiter. C’est le cas, par exemple, si l’on s’intéresse à classer
des images de chiffres manuscrits (nombre de classes = 10 : 0, …, 9) ou de lettres
manuscrites (nombre de classes = nombres de caractères de l’alphabet), etc.
4.2.2. Données, Classes et Métrique

Exemple. Considérons une image couleur. Une image contient 𝑛𝑛 pixels (𝑥𝑥1,…,𝑥𝑥𝑛𝑛),
chaque pixel 𝑥𝑥𝑖𝑖 contient 3 valeurs (R : rouge, G : vert, B : bleu). On peut donc
représenter le ième pixel (i = 1, …, n) par un vecteur 𝑥𝑥𝑖𝑖 de dimension 𝑑𝑑 =3 : 𝑥𝑥𝑖𝑖 =(𝑥𝑥𝑖𝑖1,𝑥𝑥𝑖𝑖2,𝑥𝑥𝑖𝑖3)𝑇𝑇
∈ {0,1,…,255}3.

Ainsi, si le problème de classification consiste à répartir les données pixel en 3 classes

: rouge, verte, bleue. L’idée revient à mesurer la proportion (métrique en taux) de
chaque composante de couleur (R%, V% et B%) contenue dans chaque pixel afin de
pouvoir l’affecter à la classe d’appartenance.

Mais, on peut aussi procéder de la manière suivante : Si l’on connaît les classes de
certains pixels, on pourra prédire les classes des autres pixels en choisissant une
mesure de (dis)similarité ou de (dis)ressemblance, par exemple une simple distance,
ou encore une mesure de probabilité, etc. Chaque pixel à classer aura donc la classe
de celui qui lui est le plus proche au sens de la mesure de (dis)similarité choisie.

Remarque. Ceci est très utilisé dans des domaines telle la segmentation d’image.

De manière générale, on peut représenter les données comme un ensemble de

vecteurs
(𝑥𝑥1,…,𝑥𝑥𝑛𝑛), chaque 𝑥𝑥𝑖𝑖 est composée de d composantes réelles : 𝑥𝑥𝑖𝑖 = (𝑥𝑥𝑖𝑖1,…,𝑥𝑥𝑖𝑖𝑖𝑖 ,…,𝑥𝑥𝑖𝑖𝑖𝑖 )𝑇𝑇 ∈
ℝ𝑑𝑑.
 Initiation à l’Apprentissage Automatique

4.2.3. Exemple Introductif

Afin d’illustrer le fonctionnement de l’algorithme , considérant

l’ensemble des données suivant, consistant en 7 objets représentés chacun par
un descripteur à 2 paramètres :
Sujets X Y

1 2,0 2,0
2 3,0 4,0
3 6,0 8,0

4 10,0 14,0
5 7,0 10,0

6 9,0 10,0
7 7,0 9,0
On veut grouper ces données (selon leurs similarités) en deux (k=2) groupes :
et .

On procèdera de la manière suivante :

1. A partir des données , choisir (au hasard) les centres

des groupes initiaux à générer.

2. A partir de l’itération , et pour chaque objet (i = 1 .. n) :

a. Calculer sa distance de à chaque centre (j = 1 ... k),

b. Affecter ou réaffecter au groupe de centre (qu’est le plus proche à

), si
.

3. Recalculer le centre (la moyenne) de chaque groupe (j = 1 … k),

1ère étape : Initialisation (itération 0) : Recherche d’une partition initiale.

 Initiation à l’Apprentissage Automatique

Ça consiste à choisir les centres initiaux des 2 groupes. Prenant, par exemple,
les objets 1 et 4 (les plus éloignés –min et max, selon une distance ; optant pour
la distance Euclidienne) comme centres de et .

Itération 1ère :

2ème étape : Les objets restants sont examinés un par un et localisés par rapport
au plus proche cluster.

Ceci nous mènent à calculer d’abord les distances de chaque objet aux 2 groupes
et , représentés respectivement par leurs centres ou centroîdes et ; ces
distances sont données par le tableau suivant (les valeurs des distances sont
arrondîtes, et on ne retient qu’un seul chiffre après la virgule) :

3ème étape : Une fois que les distances sont connues, on réaffecte chaque objet
au cluster , si sa distance au centre est minimale.

Puisque, on n’est pas sûr que chaque objet soit assigné au bon cluster, ceci
nous oblige à réitérer une fois de plus sur l’étape 2 : ce qui revient à recalculer
les distances de chaque objet aux 2 nouveaux centres et . Puis, réaffecter
chaque objet au groupe dont la distance à son centre est minimale.

Itération 2ème :

Recalculons les distances de chaque objet aux 2 groupes et .

Une fois les distances recalculées, on réaffecte chaque objet au cluster qui lui
est le plus proche. Ici, seul l’objet 3 est reclassé dans . Puis, on recalcule les
barycentres des nouveaux groupes.

Itération 3ème :

Recalculons les distances de chaque objet aux 2 groupes et ; on obtient :

On recalcule les barycentres des nouveaux groupes, mais ce n’est pas nécessaire
puisque les groupes n’ont pas changé, ainsi, il y a convergence.
 Initiation à l’Apprentissage Automatique

Condition de Convergence :

L’itération s’arrête lorsque chaque objet est plus proche de son propre moyen
cluster que celui des autres groupes, et la solution finale des clusters sera ce
dernier partitionnement.

4.2.4. Approche de Classification

4.2.4.1. Notations

On utilise les notations suivantes :

- Les , i {1, .., n} sont les points (objets) à séparer.

- Les sont des variables indicatrices associées aux telles que

appartient au cluster , sinon.

- est la matrice des .

- μ est le vecteur des , où est le centre du cluster .

4.2.4.2. Mesure de Distorsion

L’objectif de l’algorithme des centres mobiles ou K-means pour la classification

automatique d’un ensemble de données (exemples) , ∈ , est de
minimiser le critère d’erreur (dite aussi erreur de distorsion ) suivant,
par rapport aux centres des classes et les classes (partitions)
:

(4.1)

avec, est une variable binaire qui vaut 1 si la classe du ième exemple est k
et 0 sinon. est une matrice binaire.

La distorsion ou le critère correspond à la distance euclidienne totale

entre chaque donnée et le centre dont elle est la plus proche (qui doit être
minimale) au sens de la distance Euclidienne :
 Initiation à l’Apprentissage Automatique

(4.2)

4.2.5. Etapes de l’Algorithme K-means

Le but de l’algorithme est de minimiser , il se présente sous la forme d’un
algorithme de minimisation alternée. L’algorithme K-means est composé des
trois étapes suivantes :

1. Etape Initialisation : choisir le vecteur . On initialise les K centres des

classes

(au choix, plusieurs options d’initialisation) pour donner le pas de

départ
de l’algorithme (par exemple, choisir aléatoirement les K centres ou données
parmi les données à traiter comme centres des clusters). Il s’agit donc de

démarrer à l’itération t = 0 avec des valeurs initiales pour les

paramètres du modèle.

2. Etape d’affectation (classification) : Chaque donnée (exemple) est

assignée à la classe du centre dont elle est la plus proche : ∀ i = 1, …, n :

(4.3)

Ainsi, la classe : est l’ensemble des exemples

les plus proches de .

Ceci revient à minimiser par rapport à : pour ,

c’est-à-dire, on associe à le centre le plus proche.

3. Etape de recalage des centres : le centre de chaque classe k est recalculé

comme étant la moyenne arithmétique de toutes les données appartenant à
cette classe (suite à l’étape d’affectation précédente) : ∀ k = 1, …, K :
 Initiation à l’Apprentissage Automatique

(4.4)

t étant l’itération courante.

Ce qui revient à minimiser par rapport à

Les nouveaux centres recalculés des clusters sont la moyenne de

l’ensemble :

(4.5)
Réitérer les étapes (2) et (3) jusqu’à convergence ou équilibre.

Remarques

- L’étape de minimisation par rapport à 𝑧𝑧 revient à répartir les 𝑥𝑥𝑖𝑖 selon les
cellules de Voronoï dont les centres sont les 𝜇𝜇𝑘𝑘.

- Dans l’étape de minimisation selon 𝜇𝜇, 𝜇𝜇𝑘𝑘 est obtenu en annulant la k-ième
coordonnée du gradient de 𝒥𝒥 selon 𝜇𝜇.

4.2.6. Propriétés du K-means

- C’est un algorithme de regroupement simple et rapide, mais aussi très utilisé.

- La méthode k-means minimise une mesure de dissemblance intra-classe pour

les kgroupes.

- Chaque objet est affecté au cluster dont le centre (centroîde/barycentre) est

le plus proche.

- Le centre d’un groupe est la moyenne de tous les points (éléments) de ce

groupe.

- Son inconvénient est qu’il produit un résultat différent à chaque exécution

(initialisation).
 Initiation à l’Apprentissage Automatique

4.2.6.1. Choix de 𝑲𝑲

Le choix de 𝐾𝐾 n’est pas universel, on remarque que si on augmente 𝐾𝐾, la

distorsion diminue, et s’annule lorsque chaque point est centre de son cluster.

Pour pallier à ce phénomène il possible de rajouter un terme en fonction de 𝐾𝐾

dans l’expression de 𝒥𝒥, mais là encore son choix est arbitraire.

4.3. Classification Hiérarchique Ascendante

La classification hiérarchique ou (re)groupement hiérarchique (ou clustering) est

une méthode de classification automatique qui consiste à effectuer une suite de
regroupements en agrégeant à chaque étape les objets (données ou
descripteurs d’objets) ou les groupes d’objets les plus proches.

On trouve des applications dans des domaines très divers tels que la biologie
(classements par espèce, genre), l’archéologie, le traitement d’images, le
traitement de requêtes, etc.

4.3.1. Exemple introductif

Soit un ensemble d’objets représentés par des points numérotés de 1 à 5, dans
un repère euclidien.

Notons 𝒅𝒅 la distance euclidienne mesurée entre les objets.

2
1

3 4

5
 Initiation à l’Apprentissage Automatique

1 2 3 4 5
1 0
2 0 2
3 0 1
4 0
5 0

1ère étape : Cette première étape de la méthode nous conduit à regrouper les
objets 3 et 5, qui sont les points les plus proches (distance minimale), , et
à former un groupe .
A ce groupe est associé son niveau, ou indice d’agrégation , qui est la
distance entre ses deux sous-groupes et , .
2
1

3 4
𝒉𝒉𝟔𝟔
5

Plusieurs solutions sont possibles. Nous en proposons deux à titre d’exemples :

1. Le saut minimal : qui consiste à affecter à la distance entre deux groupes

la distance entre leurs objets les plus proches, et

2. Le diamètre maximal : qui consiste à retenir la distance entre leurs objets

les plus éloignés.

2ème étape : A l’étape suivante, on a la même agrégation pour les deux distances

(même distance minimale), , :

 Initiation à l’Apprentissage Automatique

Saut
minimal
1
1 0

2
1 𝒉𝒉𝟕𝟕

3 4
𝒉𝒉𝟔𝟔

3ème étape : A la troisième étape, les deux hiérarchies deviennent différentes :

• Saut minimal : ,
2
1
𝒉𝒉𝟕𝟕

3 𝒉𝒉𝟖𝟖 4
𝒉𝒉𝟔𝟔
5

S aut minimal

Si on continue à la dernière étape (4ème itération de regroupement), tous les objets

sont regroupés :
 Initiation à l’Apprentissage Automatique

• Saut minimal : ,

Remarque important : Le choix de la distance entre deux groupes influe sur

les regroupements.

4.3.2. Dendrogramme

Cette hiérarchie de regroupement (ou de clustering, en anglais) des objets peut

être représentée par un diagramme dit : dendrogramme. C’est une
représentation arborescente d’une hiérarchie.

La hiérarchie que nous avons obtenue par le critère de saut minimal dans
l’exemple introductif, est représentée par l’arbre ou le dendrogramme de la figure
4.2 :

𝒉𝒉𝟗𝟗
10
𝒉𝒉𝟖𝟖
𝒉𝒉𝟕𝟕
2

𝒉𝒉𝟔𝟔
1

𝒙𝒙𝟑𝟑 𝒙𝒙𝟓𝟓 𝒙𝒙𝟏𝟏 𝒙𝒙𝟐𝟐 𝒙𝒙𝟒𝟒 𝑬𝑬 8

Figure 4.2. Dendrogramme : Hiérarchie obtenue par le saut minimal.

Par définition, une hiérarchie indicée est isomorphe à un arbre dont les nœuds
sont associés aux éléments de et la relation “fils de” , à la relation de borne
supérieure pour l’inclusion.

Les feuilles représentent les objets et la racine l’ensemble . Deux nœuds et

sont ou bien sur deux branches différentes , ou bien sur une même
branche, l’un étant alors inclut dans l’autre ⊂ ⊂ .
 Initiation à l’Apprentissage Automatique

De plus l’ordonnée d’un nœud correspond à son indice . Elle est croissante des
feuilles vers la racine et les feuilles sont d’ordonnée nulle.

4.3.3. Etapes du Regroupement Hiérarchique

D’une manière générale, l’algorithme de clustering ou (re)groupement

hiérarchique ascendant peut comprendre plusieurs itérations, dont le nombre
maximal d’itérations est donné par le nombre et/ou la nature des objets à
regrouper.

Cependant, on peut décider de l’arrêt du regroupement (convergence) par un

seuil de regroupement selon le niveau d’agrégation désiré.

Chaque itération de l’algorithme de classification par clustering hiérarchique

comprend :

1. Calcul de la matrice des distances entre objets, pour la 1ère étape (ou mise
à jour de la matrice des distances entre objets, pour les étapes suivantes).

2. Déterminer la distance minimale (niveau d’agrégation) et repérer les

groupes ou objets concernés.

3. Tester si le niveau d’agrégation n’a pas dépassé le seuil ou le nombre

d’itérations est suffisant, sinon arrêt.

4. Regrouper les objets ou groupes concernés. Réitérer sur 1.