Apprentissage Supervisé Classification

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Content

1 Introduction

2 Classification
Définition et généralités
Processus de classification

3 Evaluation des méthodes de classification

Généralités
Exemple
Matrice de confusion
Accuracy, Recall, Précision, F1 score

4 k-Nearest Neighbor (k-NN)

Généralités
Principe et algoithme

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Étapes du Machine Learning

Étapes du Machine Learning
1 Définition des Objectifs du Projet : Clarifier les buts et les résultats attendus.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Étapes du Machine Learning

Étapes du Machine Learning
1 Définition des Objectifs du Projet : Clarifier les buts et les résultats attendus.
2 Collecte des Données : Identifier et acquérir les sources de données
pertinentes.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Étapes du Machine Learning

Étapes du Machine Learning
1 Définition des Objectifs du Projet : Clarifier les buts et les résultats attendus.
2 Collecte des Données : Identifier et acquérir les sources de données
pertinentes.
3 Prétraitement des Données
▸ Nettoyage des Données : les valeurs manquantes, les erreurs et les incohérences.
▸ Transformation des Données : Normaliser, standardiser et encoder.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Étapes du Machine Learning

Étapes du Machine Learning
1 Définition des Objectifs du Projet : Clarifier les buts et les résultats attendus.
2 Collecte des Données : Identifier et acquérir les sources de données
pertinentes.
3 Prétraitement des Données
▸ Nettoyage des Données : les valeurs manquantes, les erreurs et les incohérences.
▸ Transformation des Données : Normaliser, standardiser et encoder.
4 Sélection des Algorithmes
▸ Entraînement et Validation du Modèle
▸ Évaluation des Performances : Mesurer la précision, la robustesse.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Étapes du Machine Learning

Étapes du Machine Learning
1 Définition des Objectifs du Projet : Clarifier les buts et les résultats attendus.
2 Collecte des Données : Identifier et acquérir les sources de données
pertinentes.
3 Prétraitement des Données
▸ Nettoyage des Données : les valeurs manquantes, les erreurs et les incohérences.
▸ Transformation des Données : Normaliser, standardiser et encoder.
4 Sélection des Algorithmes
▸ Entraînement et Validation du Modèle
▸ Évaluation des Performances : Mesurer la précision, la robustesse.

Remarque
Sélection des Algorithmes : Identifier et choisir l’algorithme de machine
learning (supervisé, non supervisé, par renforcement) les plus adaptés aux
caractéristiques des données et aux objectifs fixés.
Pertinence du Modèle : Opter pour les modèles les plus pertinents permet
d’assurer des performances optimales tout en garantissant une bonne capacité de
UP-Mathématique 2024-2025 ESPRIT school of engineering
Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Algorithme de machine learning

Dénition
Un algorithme de machine learning est un processus qui permet à une machine
d’apprendre à partir de données, en identifiant des motifs ou en prédisant des
valeurs à partir de variables d’entrée.

UP-Mathématique
Figure: Type d'algorithme
2024-2025 ESPRIT school of engineering
Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Apprentissage Supervisé

L’apprentissage supervisé, aussi appelé Machine Learning supervisé, fait partie

des méthodes d’apprentissage automatique.
Il consiste à entraîner un algorithme à l’aide de données d’entrée et de sortie
connues et étiquetées.
L’objectif est d’utiliser ces données d’entraînement pour construire un modèle
capable de prédire avec précision la sortie pour de nouvelles données non vues.
L’algorithme mesure sa précision par le biais de la fonction de perte, en s’ajustant
jusqu’à ce que l’erreur soit suffisamment réduite.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Catégories d’apprentissage supervisé

L’apprentissage supervisé peut être divisé en deux sous-catégories : la régression et
la classification.
Régression
La régression permet de comprendre la relation entre les variables dépendantes
et indépendantes.
Elle est couramment utilisée pour établir des projections, telles que le chiffre
d’affaires d’une entreprise donnée.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Catégories d’apprentissage supervisé

L’apprentissage supervisé peut être divisé en deux sous-catégories : la régression et
la classification.
Régression
La régression permet de comprendre la relation entre les variables dépendantes
et indépendantes.
Elle est couramment utilisée pour établir des projections, telles que le chiffre
d’affaires d’une entreprise donnée.

Classication
La classification utilise un algorithme pour attribuer avec précision des données
de test à des catégories particulières.
Attribuer une catégorie ou une classe à chaque observation d’un ensemble de
données, en fonction de ses caractéristiques.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Classification

Dénition
La classification permet de prédire si un élément est membre d’un groupe ou d’une
catégorie donnée.

Classes:
Identification de groupes avec des profils particuliers.
Possibilité de décider de l’appartenance d’une entité à une classe.
Caractéristiques de classification:
Apprentissage supervisé: classes connues à l’avance.
Qualité de la classification (taux d’erreur).

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Exemples de problème de classification

La détection de spams:
▸ Après avoir scanné le texte d’un mail,
▸ Tagguer certains mots et phrases.
▸ La signature du message peut être injectée dans un algorithme de classification.
Déterminer si oui ou non il s’agit d’un spam.
L’analyse du risque dans le domaine de la santé:
▸ Les statistiques vitales d’un patient.
▸ L’historique de santé.
▸ Les niveaux d’activités.
▸ Les données démographiques
Ces données peuvent être croisées pour attribuer une note (un niveau de
risque) et évaluer la probabilité d’une maladie.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Processus de classification

Le processus de classification se fait en deux étapes:

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Processus de classification

Le processus de classification se fait en deux étapes:

Etape 1
Construction du modèle à partir de l’ensemble d’apprentissage (training set).

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

Processus de classification

Le processus de classification se fait en deux étapes:

Etape 1
Construction du modèle à partir de l’ensemble d’apprentissage (training set).

Etape 2
Utilisation du modèle: tester la précision du modèle (test set) et l’utiliser dans la
classification de futur donnée( nouvelles données) .

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

10

Etape 1: Construction de modèle

Chaque donnée est affectée à une classe selon ces valeurs.

1 La classe d’une donnée est déterminée par l’attribut classe.
2 L’ensemble des données d’apprentissage (train set) est utilisé dans la construction
du modèle (entrainement).
3 Le modèle est représenté par des règles de classification (Algorithme
d’apprentisage)

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

11

Etape 2: Utilisation du modèle

Classification de nouvelles donnée ou donnée inconnues

Estimer le taux d’erreur du modèle
▸ La classe connue d’une donnée test est comparée avec le résultat du modèle.
▸ Taux d’erreur = pourcentage de tests incorrectement classés par le modèle.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

12

Exemple:Construction de modèle

Figure: Construction de modèle

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

13

Exemple:Validation de modèle

Figure: Construction de modèle

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

14

Exemple:Utilisation de modèle

Figure: Construction de modèle

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

15

Evaluation des méthodes de classification

Évaluer les performances d’un modèle de classification est primordial:

Pour savoir si le modèle est globalement significatif: Mon modèle traduit-il
vraiment une causalité ?
Pour se donner une idée des performances en déploiement : Quelle sera la
fiabilité (les coûts associés) lorsque j’utiliserai mon modèle ?
Pour comparer plusieurs modèles candidats: Lequel parmi plusieurs modèles sera
le plus performant compte tenu de mes objectifs ?

Remarque
La mesure et l’évaluation de la performance d’un modèle de classification se fait
toujours sur l’échantillon de test: Il faut tester la performance de modèle sur des
données qui n’ont pas été utilisées pour construire le modèle de classification.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

16

Evaluation des méthodes de classification

Plusieurs indicateurs permettent de mesurer la performance des modèles de

classification.
Chaque indicateur a ses spécificités.
il faut bien souvent en utiliser plusieurs pour avoir une vision complète de la
performance de votre modèle.
Pour évaluer la performance d’un modèle de classification nous présentons quatre
indicateurs qui sont calculés à partir de la matrice de confusion:
L’accuracy.
Le recall.
La precision.
F1 score.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

17

Exemple de classification
score de churn
Nous avons une base de données client qui ont été abonnés à un service.
Des clients qui sont encore abonnés.
Des clients qui ont résilié le service.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

18

Exemple de classification

Nous construisons un score de churn : pour chaque client, on prédit s’il va résilier ou
conserver son abonnement le mois suivant.

Quelle est la performance de ce score ?

A quel point je peux lui faire confiance pour prédire les résiliations futures?

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

19

Evaluation des méthodes de classification

Matrice de confusion
Une matrice de confusion sert à évaluer la qualité d’une classification. Elle est obtenue en comparant les données classées avec des données de
référence (test set) qui doivent être différentes de celles ayant servi à réaliser la classification (train set).

Classification supervisée binaire, y ∈ {0, 1} , où la modalité de la variable à prédire correpond à la classe postive et l’autre à la classe négative, on
nomme les coefficients de la matrice de confusion:

Figure: Construction de modèle

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

20

Matrice de confusion

Les fausses prédictions:

▸ Nombre de faux négatifs (FN): les clients qui ont résilié mais pour lesquels le score a prédit à
tort qu’ils allaient rester abonnés.
▸ Nombre de faux positifs (FP): les clients qui sont restés abonnés alors que le score a prédit à
tort qu’ils allaient résilier.
Les bonnes prédictions:
▸ Nombre de vrais positifs (VP): les clients qui ont résilié pour lesquels le score a bien prédit
qu’ils allaient résilier.
▸ Nombre de vrais négatifs(VN): les clients qui sont toujours abonnés et pour lesquels
l’algorithme a bien prédit qu’ils resteraient abonnés.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

21

Evaluation des méthodes de classification

Accuracy
Il indique le pourcentage de bonnes prédictions.
vrais positifs + vrais négatifs
Accuracy =
total

Parfois, l’accuracy ne suffit pas:

Considérons un problème de 2-classes:
▸ Nombre de Classes 0 égal à 9990
▸ Numbre de Classes 1 égal à 10.
▸ La base de données n’est pas équilibrée.
Si le modèle prédit que tout est de classe 0, la précision est de
9990/10000 = 99, 9%. La précision est trompeuse car le modèle ne détecte aucun
exemple de classe 1.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

22

Recall

Le recall (rappel) permet de répondre à la question suivante :

Quelle proportion de résultats positifs réels a été identifiée correctement ?

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

22

Recall

Le recall (rappel) permet de répondre à la question suivante :

Quelle proportion de résultats positifs réels a été identifiée correctement ?

Recall
Il donne une indication sur la part de faux négatifs.
vrais positifs
Recall =
Vrais positif + faux négatifs

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

22

Recall

Le recall (rappel) permet de répondre à la question suivante :

Quelle proportion de résultats positifs réels a été identifiée correctement ?

Recall
Il donne une indication sur la part de faux négatifs.
vrais positifs
Recall =
Vrais positif + faux négatifs

Un modèle ne produisant aucun faux négatif a un rappel de 1.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

23

Précision

La précision permet de répondre à la question suivante:

Quelle proportion d’identifications positives était effectivement correcte ?

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

23

Précision

La précision permet de répondre à la question suivante:

Quelle proportion d’identifications positives était effectivement correcte ?

Précision
Il donne une indication sur les faux positifs.
vrais positifs
Precision =
Vrais positifs + faux positifs

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

23

Précision

La précision permet de répondre à la question suivante:

Quelle proportion d’identifications positives était effectivement correcte ?

Précision
Il donne une indication sur les faux positifs.
vrais positifs
Precision =
Vrais positifs + faux positifs

Un modèle de classification ne produisant aucun faux positif a une précision de 1.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

24

Précision et Recall

Pour évaluer les performances d’un modèle de façon complète: Il faut analyser à
la fois la précision et le rappel.
La précision et rappel sont fréquemment en tension: l’amélioration de la précision
se fait généralement au détriment du rappel et réciproquement.
Si on veut comparer les performances de deux classificateurs et on a:
▸ Supposons que le classificateur A a un recall plus élevé et le classificateur B a une précision
plus élevée.
Alors on ne peut pas comparer les classificateurs A et B
Différents outils ont été créés pour évaluer simultanément la précision et le rappel.
La F-score en fait partie.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

25

F1 score

Le F1 score combine la précision et le recall d’un classificateur en une seule

métrique en prenant leur moyenne harmonique.
Le F1 score est utilisé pour comparer les performances de deux classificateurs
dans le cas suivant:
▸ Supposons que le classificateur A a un recall plus élevé et le classificateur B a une précision
plus élevée.
▸ Dans ce cas, les F1 score des deux classificateurs peuvent être utilisés pour déterminer celui qui
produit les meilleurs résultats.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

25

F1 score

Le F1 score combine la précision et le recall d’un classificateur en une seule

métrique en prenant leur moyenne harmonique.
Le F1 score est utilisé pour comparer les performances de deux classificateurs
dans le cas suivant:
▸ Supposons que le classificateur A a un recall plus élevé et le classificateur B a une précision
plus élevée.
▸ Dans ce cas, les F1 score des deux classificateurs peuvent être utilisés pour déterminer celui qui
produit les meilleurs résultats.

F1 score
Il est la moyenne pondérée de la précision et du recall. Par conséquent, ce score prend en compte à la fois les faux positifs et les faux négatifs.

2 ∗ (Recall ∗ Precision)
F1 score =
Recall + Precision

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

26

Généralités

L’algorithme des k plus proches voisins est un algorithme d’apprentissage

supervisé, il est nécessaire d’avoir des données labellisées.
À partir d’un ensemble E de données labellisées, il sera possible de classer
(déterminer le label) une nouvelle donnée (n’appartenant pas à E ).
Il est aussi possible d’utiliser l’algorithme des k plus proches voisins pour la
régression (on cherche à déterminer une valeur à la place d’une classe).

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

27

Généralités

Méthode de raisonnement à partir de cas: prendre des décisions en recherchant

un ou des cas similaires déjà résolus.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

27

Généralités

Méthode de raisonnement à partir de cas: prendre des décisions en recherchant

un ou des cas similaires déjà résolus.
Pas d’étape d’apprentissage: construction d’un modèle à partir d’un échantillon
d’apprentissage.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

27

Généralités

Méthode de raisonnement à partir de cas: prendre des décisions en recherchant

un ou des cas similaires déjà résolus.
Pas d’étape d’apprentissage: construction d’un modèle à partir d’un échantillon
d’apprentissage.
Modèle= échantillon d’apprentissage + fonction de distance + fonction de choix de
la classe en fonction des classes des voisins les plus proches.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

28

Principe
Soit la base de donnée:

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

28

Principe
On veut prédire à quelle classe appartient la nouvelle donnée:

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

28

Principe
Si on prend un seul voisin:

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

29

Principe
Si on considère deux voisins:

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

29

Principe
Si on considère trois voisins:

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

29

Principe
Si on considère quatres voisins:

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

30

Algorithme de KNN

Début Algorithme
Input :
un ensemble de données D .
une fonction de définition distance d.
Un nombre entier k
une nouvelle observation X
Output:
Prédire la variable de sortie y de X :
Faire :
1 Calculer toutes les distances de cette observation X avec les autres observations du jeu de données D.
2 Retenir les k observations du jeu de données D les proches de X en utilisation le fonction de calcul de distance d
3 Prendre les valeurs de y des k observations retenues : et calculer le mode de y retenues.
4 Retourner la valeur calculée dans l’étape 3 comme étant la valeur qui a été prédite par K-NN pour l’observation X .
Fin Algorithme

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

31

Distance

L’algorithme, K-NN a besoin d’une fonction de calcul de distance entre deux

observations.
Dénition distance
on appelle distance sur un ensemble E de Rn , une application définie de E × E à
valeurs dans R+ notée d qui à tout couple (x, y) ∈ E × E fait correspondre un réel
positif ou nul d(x, y) vérifiant:
1 d(x, y) = 0 SSi x = y .
2 d(x, y) = d(y, x), ∀(x, y) ∈ E 2 .
3 d(x, y) ≤ d(x, z) + d(z, y), ∀(x, y, z) ∈ E 3 .

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

32

Type des distance

Il existe plusieurs fonctions de calcul de distance:
La distance euclidienne.
la distance de Manhattan.
la distance de Minkowski
la distance de Jaccard.
la distance de Hamming.
Le choix de la fonction de distance en fonction des types de données qu’on manipule.
Ainsi pour les données quantitatives (exemple : poids, salaires, taille, montant de
panier éléctronique etc...) et du même type: la distance euclidienne est un bon
candidat.
La distance de Manhattan est une bonne mesure à utiliser quand les données
(input variables) ne sont pas du même type (exemple :age, sexe, longueur, poids
etc...).

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

33

Distance euclidienne

Dénition
C’est la distance qui calcule la racine carrée de la somme des différences carrées entre les coordonnées de deux points:
Soient X = (x1 , x2 , ..., xn ) et Y = (y1 , y2 , ..., yn ) la distance euclidienne entre X et Y est:
¿
Án
À ∑ (xi − yi )2 .
d(X, Y ) = Á
i=1

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

33

Distance euclidienne

Dénition
C’est la distance qui calcule la racine carrée de la somme des différences carrées entre les coordonnées de deux points:
Soient X = (x1 , x2 , ..., xn ) et Y = (y1 , y2 , ..., yn ) la distance euclidienne entre X et Y est:
¿
Án
À ∑ (xi − yi )2 .
d(X, Y ) = Á
i=1

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

34

Distance Manhattan

Dénition
C’est la distance qui calcule la somme des valeurs absolues des différences entre les coordonnées de deux points:
Soient X = (x1 , x2 , ..., xn ) et Y = (y1 , y2 , ..., yn ) la distance Manhattan entre X et Y est:
n
dm (X, Y ) = ∑ ∣xi − yi ∣.
i=1

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

34

Distance Manhattan

Dénition
C’est la distance qui calcule la somme des valeurs absolues des différences entre les coordonnées de deux points:
Soient X = (x1 , x2 , ..., xn ) et Y = (y1 , y2 , ..., yn ) la distance Manhattan entre X et Y est:
n
dm (X, Y ) = ∑ ∣xi − yi ∣.
i=1

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

35

Distance de Minkowski

Dénition
La distance de Minkowski ou métrique de Minkowski est une généralisation à la fois de la distance euclidienne et de la distance de Manhattan:
Soient X = (x1 , x2 , ..., xn ) et Y = (y1 , y2 , ..., yn ) la distance Minkowski d’ordre p entre X et Y est:
¿
Á n
p
Á p
dM (X, Y ) = À ∑ (xi − yi ) .
i=1

Remarque
Si p → +∞ alors la distance de Minkowski nous obtenons la distance de Chebyshev:
Soient X = (x1 , x2 , ..., xn ) et Y = (y1 , y2 , ..., yn ) la distance Minkowski d’ordre p entre X et Y est:
¿
Á n
p
Á p
dT (X, Y ) = lim À ∑ (xi − yi ) = max ∣xi − yi ∣.
p→+∞ i
i=1

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

36

Comment choisir la valeur K

Le choix de la valeur K à utiliser pour effectuer une classification avec K-NN,

varie en fonction du jeu de données.
En règle générale, moins on utilisera de voisins (un nombre K petit) plus on sera
sujette au sous apprentissage (underfitting).
Par ailleurs, plus on utilise de voisins (un nombre K grand) plus, sera fiable dans
notre classification.
Toutefois, si on utilise K nombre de voisins avec K = N et N étant le nombre
d’observations, on risque d’avoir du overfitting.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

37

Limitations de K-NN

K-NN est un algorithme assez simple à appréhender.

Principalement, grâce au fait qu’il n’a pas besoin de modèle pour pouvoir
effectuer une prédiction.
Le contre coût est qu’il doit garder en mémoire l’ensemble des observations pour
pouvoir effectuer sa prédiction. Ainsi il faut faire attention à la taille du jeu
d’entrainement.
Le choix de la méthode de calcul de la distance ainsi que le nombre de voisins k
peut ne pas être évident. Il faut essayer plusieurs combinaisons et faire du tuning
de l’algorithme pour avoir un résultat satisfaisant.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

38

Application : Classification à l’aide de l’algorithme KNN

Nous avons un ensemble d’objets avec les caractéristiques suivantes :Poids (en
grammes) et couleurs.
Notre objectif est de classer un nouvel objet en fonction de ses voisins les plus
proches pour déterminer s’il s’agit d’un fruit ou d’un légume.
Le nouvel objet a comme caractéristiques : Poids= 92g et Couleur = 1 (Rouge).

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

39

Application : Classification à l’aide de l’algorithme KNN

Objets Poids Couleurs Classe Distance Ecludienne

Cerise 43 1 (rouge) Fruit .............
Pomme 150 1 (rouge) Fruit .............
Poire 174 2 (jaune) Fruit .............
Brocoli 140 3 (vert) Légume .............
Laitue 92 3 (vert) Légume .............
Carott 165 4 (orangé) Légume .............

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

40

Application : Classification à l’aide de l’algorithme KNN

Pour que les valeurs des données se situent dans une plage similaire, nous allons
tout d’abord transformer les données en standardisant les poids et les couleurs de
notre ensemble d’entrainement avant de calculer les distances euclidiennes.
Moyenne et écart-type des caractéristiques : Moyenne Poids : 127.33 g, Écart-type
Poids : 45.89 g, Moyenne Couleur : 2.33, Écart-type Couleur : 1.11 .

Objets Poids Couleurs Classe Distance Ecludienne

Cerise -1,84 -1,2 Fruit .............
Pomme 0,49 -1,2 Fruit .............
Poire 1,02 -0,3 Fruit .............
Brocoli 0,28 0,6 Légume .............
Laitue -0,77 0,6 Légume .............
Carott 0,82 1,5 Légume .............

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

41

Application : Classification à l’aide de l’algorithme KNN

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

41

Application : Classification à l’aide de l’algorithme KNN

Nous allons calculer les distances euclidiennes entre le nouvel objet et chaque
objet de cet ensemble, puis sélectionner les 3 plus proches voisins.

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

41

Application : Classification à l’aide de l’algorithme KNN

Nous allons calculer les distances euclidiennes entre le nouvel objet et chaque
objet de cet ensemble, puis sélectionner les 3 plus proches voisins.
Le nouvel objet (Poids standardisé = -0.77, Couleur standardisée = -1.2)

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

41

Application : Classification à l’aide de l’algorithme KNN

Nous allons calculer les distances euclidiennes entre le nouvel objet et chaque
objet de cet ensemble, puis sélectionner les 3 plus proches voisins.
Le nouvel objet (Poids standardisé = -0.77, Couleur standardisée = -1.2)
Objets Poids Couleurs Classe Distance Ecludienne
Cerise -1,84 -1,2 Fruit 1,07
Pomme 0,49 -1,2 Fruit 1,26
Poire 1,02 -0,3 Fruit 2
Brocoli 0,28 0,6 Légume 2,08
Laitue -0,77 0,6 Légume 1,8
Carott 0,82 1,5 Légume 3,13

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

41

Application : Classification à l’aide de l’algorithme KNN

Nous allons calculer les distances euclidiennes entre le nouvel objet et chaque
objet de cet ensemble, puis sélectionner les 3 plus proches voisins.
Le nouvel objet (Poids standardisé = -0.77, Couleur standardisée = -1.2)
Objets Poids Couleurs Classe Distance Ecludienne
Cerise -1,84 -1,2 Fruit 1,07
Pomme 0,49 -1,2 Fruit 1,26
Poire 1,02 -0,3 Fruit 2
Brocoli 0,28 0,6 Légume 2,08
Laitue -0,77 0,6 Légume 1,8
Carott 0,82 1,5 Légume 3,13
Les 3 plus proches voisins sont : Cerise (Fruit), Pomme (Fruit) et Laitue
(Légume).

UP-Mathématique 2024-2025 ESPRIT school of engineering

Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

41

Application : Classification à l’aide de l’algorithme KNN

Nous allons calculer les distances euclidiennes entre le nouvel objet et chaque
objet de cet ensemble, puis sélectionner les 3 plus proches voisins.
Le nouvel objet (Poids standardisé = -0.77, Couleur standardisée = -1.2)
Objets Poids Couleurs Classe Distance Ecludienne
Cerise -1,84 -1,2 Fruit 1,07
Pomme 0,49 -1,2 Fruit 1,26
Poire 1,02 -0,3 Fruit 2
Brocoli 0,28 0,6 Légume 2,08
Laitue -0,77 0,6 Légume 1,8
Carott 0,82 1,5 Légume 3,13
Les 3 plus proches voisins sont : Cerise (Fruit), Pomme (Fruit) et Laitue
(Légume).
Conclusion: Selon l’algorithme KNN (K=3), comme la majorité des voisins (2 sur
3) sont des Fruits, le nouvel objet sera classé comme un Fruit.
UP-Mathématique 2024-2025 ESPRIT school of engineering
Introduction Classication Evaluation des méthodes de classication k-Nearest Neighbor (k-NN)

42

Thank you for your attention.

UP-Mathématique 2024-2025 ESPRIT school of engineering