Explication des algorithmes KNN et Kmeans pour l'IA

By Paul Claret

10 minutes read - 06/12/24

Oui oui on va couvrir tout ça dans un seul article.

Prérequis

Donc du coup, je vais vous demander d’être à jour avant de commencer. Veillez à bien comprendre les sujets suivants:
- Supervised, Unsupervised, Semi-Supervised, Reinforcement Learning
- Mon article sur les introduction aux algorithmes de bases
- Facultatif mais bien: Regression Linéaire et logistique

KNN (K-Nearest Neighbors): Classification et régession

Introduction

L’algorithme des K-Nearest Neighbors (KNN) est l’un des algorithmes les plus simples et intuitifs en machine learning. Malgré sa simplicité, il reste souvent très efficace pour des tâches classiques de classification et de régression.

KNN, ou K-Nearest Neighbors, est un algorithme de classification et de régression qui est basé sur l’idée simple que des points similaires sont souvent proches les uns des autres. En d’autres termes, KNN suppose que des exemples appartenant à une même catégorie ou ayant des valeurs similaires sont souvent situés géographiquement proches dans l’espace des caractéristiques.

Par exemple, si vous cherchez à classifier des fruits en fonction de leurs caractéristiques (taille, poids, couleur), KNN examinera les fruits voisins et déduira la catégorie (par exemple, orange ou pomme) selon la majorité des voisins.

Sur l’image ci dessus, si l’on prend on citron vert, que l’on calcule sa “rondeur” et “taille” et la place sur le graphique, on va regarder où il se place et quels sont ses voisons les plus proches. S’il est proche des autres agrumes, c’es surement qu’il fait parti de la famille des agrumes et surement pas des bananes ou fraises.

Pourquoi utiliser KNN ?

KNN est souvent utilisé pour des tâches de machine learning simples où :

• Les relations entre les données ne sont pas trop complexes.
• Une bonne précision est nécessaire sans nécessiter une grande complexité de calcul.
• La compréhension des relations locales est cruciale.

Il est également utilisé comme référence pour comparer d’autres algorithmes plus complexes.

Fonctionnement de KNN

Concept des voisins les plus proches (Nearest Neighbors)

L’algorithme KNN fonctionne en suivant ces étapes essentielles :

1. Choix de la distance : KNN mesure la distance entre le point cible (l’entrée pour laquelle on souhaite prédire une valeur ou une classe) et les points existants dans l’ensemble des données. Les distances les plus couramment utilisées sont :

• Euclidienne : Utilisée pour mesurer la distance la plus directe entre deux points dans un espace multidimensionnel.
• Manhattan : Une autre métrique qui mesure la distance en suivant les axes de l’espace.
• Minkowski : Une généralisation des deux métriques ci-dessus. (peu utilisé) Pour une représentation visuelle des métriques, voici une image:

3. Sélection des K voisins les plus proches : Une fois que la distance est calculée, KNN sélectionne les K voisins les plus proches du point cible. La valeur de K est un hyperparamètre crucial et doit être choisi avec soin.

4. Classification / Régression :

• Pour la Classification : On utilise un vote majoritaire des classes des K voisins. Par exemple, si la majorité des K voisins appartient à la catégorie “chat”, alors le point cible sera également classé comme “chat”.
• Pour la Régression : On prend la moyenne des valeurs des K voisins pour prédire la sortie.

Exemple classification

Dans notre image agrumes plus haut, on va essayer le classer un citron vert. Plaçons le sur notre graphe et regardons qui sont ses voisons les plus proches. Prennons la distance euclidienne et K=3.

On remarque que le citron vert est proche du kiwi, citron jaune et clémentine. On regarde quel est la classe des éléments les plus proches. On trouve 2 agrumes et 1 autre (kiwi). On peut donc en déduire que le citron vert est un agrume.

Les étapes de l’implémentation de KNN

Préparation des Données

Avant de passer à l’implémentation, il est nécessaire de préparer vos données. Cela inclut :

1. Nettoyage des Données : Assurez-vous qu’il n’y a pas de valeurs manquantes ou de bruit dans vos données.
2. Normalisation / Standardisation : Les algorithmes de distance comme KNN sont sensibles aux échelles des variables. C’est pourquoi, il est souvent nécessaire de normaliser les valeurs (par exemple, en utilisant MinMaxScaler).

Normalisation MinMax :

\[ X_{norm}= \frac{X - X_{min}}{X_{max} - X_{min}} \]

Cela permet de garder toutes les valeurs sur la même échelle.

Sélection des Paramètres K

Le choix de la valeur de K est crucial. Trop petit, K peut rendre l’algorithme sensible au bruit, tandis que trop grand, K risque de lisser excessivement les décisions.

• En général, on teste plusieurs valeurs de K (par exemple, 3, 5, 7…) et on utilise des techniques comme cross-validation pour déterminer la meilleure valeur.
• La valeur idéale dépend des propriétés des données et du problème spécifique.

Implémentation simple en Python

Voici un exemple basique pour implémenter KNN avec la bibliothèque scikit-learn en Python :

                
from sklearn.neighbors import KNeighborsClassifier
import numpy as np
                    
# Exemple de données
X = np.array([[1, 2], [2, 3], [3, 4], [6, 7]])
y = np.array(['chat', 'chien', 'oiseau', 'poisson'])
                    
# Création du modèle KNN
knn = KNeighborsClassifier(n_neighbors=3)
                    
# Entraînement du modèle
knn.fit(X, y)
                    
# Prédiction sur un nouvel exemple
nouvelle_donnée = np.array([[2, 2]])
prediction = knn.predict(nouvelle_donnée)
print("Classe prédite :", prediction)
                
            

Avantages et limites de l’algorithme KNN

Avantages

• Simplicité : Facile à comprendre et à mettre en œuvre.
• Efficace pour des petits ensembles de données : Pas besoin d’une grande puissance de calcul.
• Flexible : Peut être utilisé pour la classification comme pour la régression.

Inconvénients

• Coût computationnel élevé sur de grands ensembles de données : Calcul des distances entre chaque point demande beaucoup de temps.
• Sensibilité au choix de K : Une mauvaise valeur de K peut dégrader les performances.
• Influence des variables non pertinentes : Nécessite une bonne prétraitement des données (normalisation, réduction de dimensionnalité).

K-Means: clustering

Introduction

L’algorithme K-Means est l’un des algorithmes de clustering les plus utilisés en machine learning. Contrairement à KNN qui est une méthode supervisée (classification/régression), K-Means appartient aux algorithmes non supervisés. Il est principalement utilisé pour segmentation des données, classification implicite, et analyse exploratoire des données.

K-Means est basé sur l’idée simple de partitionner les données en plusieurs groupes (ou clusters) afin de regrouper des points similaires ensemble tout en maintenant une certaine distance entre les groupes. Chaque cluster est défini par son centre, appelé centroid, qui représente la moyenne des points dans ce groupe.

Par exemple, imaginez un ensemble de clients pour une entreprise. En utilisant K-Means, vous pouvez segmenter ces clients en groupes homogènes en fonction de leurs comportements d’achat, facilitant ainsi une meilleure personnalisation des services.

Pourquoi utiliser K-Means ?

K-Means est souvent utilisé dans les tâches suivantes :

• Segmentation des clients : Comprendre les comportements d’achat des consommateurs.
• Analyse d’images : Regrouper des pixels similaires pour la segmentation d’images.
• Réduction de dimensionnalité : Découper des données complexes en groupes plus simples à comprendre.
• Recherche de modèles : Identification de tendances dans les grandes quantités de données non structurées.

Fonctionnement de l’algorithme K-Means

L’algorithme K-Means fonctionne en suivant une série d’étapes itératives simples.

1. Initialisation des Centroids

La première étape consiste à choisir un nombre K, qui représente le nombre de groupes (clusters) que l’on souhaite créer. Une fois que K est défini :

• L’algorithme sélectionne aléatoirement K points dans l’ensemble des données comme les centroids initiaux.
• Ces centroids servent de référence pour la partition des points dans l’espace des caractéristiques.

2. Attribution des points aux Centroids

Une fois les centroids initialisés :

• Pour chaque point de votre ensemble de données, calculez sa distance au centroid le plus proche (utilisez la distance Euclidienne par défaut).
• Associez ce point au centroid le plus proche en fonction de la distance minimale.

Chaque point est donc assigné au cluster où il se trouve le plus proche du centroid.

3. Mise à jour des Centroids

Après avoir attribué tous les points :

• Pour chaque cluster, calculez la moyenne des coordonnées des points qui y sont assignés.
• Déplacez alors chaque centroid à cette moyenne.

Cela permet de raffiner la position des centroids afin qu’ils représentent au mieux les points regroupés dans leurs clusters respectifs.

4. Répétition jusqu’à convergence

Les étapes 2 et 3 sont répétées jusqu’à ce que l’algorithme atteigne un critère d’arrêt, comme :

• Aucune mise à jour des centroids (les centroids ne changent plus).
• Une certaine tolérance de distance minimale entre les centroids.
• Un nombre fixe d’itérations.

Résumé en un GIF:

Ici on voit les centroids (petites étoiles noires), placé aléatoirement à la première itération (on voit surtout le vert en bas à droite qui est mal placé). Puis au fur et à mesure que l’on itère, on les voit se rapprocher de clusters différents (rouge, bleu, vert). Une fois que les centroids ne bougent plus, il n’y a plus d’interêt à continuer, le programme ne fait plus aucun changement.

Formules clés dans K-Means

La mise à jour des centroids repose sur la formule suivante pour calculer la position moyenne des points dans chaque cluster :

Calcul du centroid \(C_{k}\) pour un cluster \(k\) :

Pour un ensemble de points \(X1,X2,...,XnX_1, X_2, ..., X_n\) appartenant à un même cluster, le centroid \(C_{k}\) est :

\[ C_{k}= \frac{\sum_{i=1}^n X_i}{n} \]

où \(n\) est le nombre de points dans ce cluster.

Les étapes de l’implémentation de K-Means

1. Préparation des Données

Avant d’appliquer l’algorithme K-Means, il est nécessaire de préparer correctement vos données :

1. Nettoyage des Données :

   • Vérifiez et traitez les valeurs manquantes.
   • Éliminez les anomalies et les valeurs aberrantes qui peuvent fausser le clustering.

2. Normalisation des Données :

   • K-Means est sensible à l’échelle des variables.
   • Par conséquent, il est recommandé de normaliser vos caractéristiques (utilisez des méthodes comme StandardScaler ou MinMaxScaler).

Normalisation MinMax :

\[ X_{norm}= \frac{X - X_{min}}{X_{max} - X_{min}} \]

2. Choix du nombre de clusters KK

La valeur de KK doit être sélectionnée avec soin.

Il existe plusieurs méthodes pour choisir un bon KK :

1. La Méthode du Coude (Elbow Method) :

   • Tracez une courbe de l’erreur intra-cluster (sum of squared errors) en fonction de différents KK.
   • Identifiez le point où l’augmentation des clusters ne diminue plus significativement l’erreur.

2. Silhouette Score :

   • Cette métrique analyse la cohérence des clusters en comparant la distance intra-cluster et la distance inter-cluster.

3. Implémentation simple en Python

Vous pouvez facilement implémenter K-Means en utilisant la bibliothèque scikit-learn.

Exemple basique de K-Means :

                
from sklearn.cluster import KMeans
import numpy as np
import matplotlib.pyplot as plt
                    
# Exemple de données
X = np.array([[1, 2], [2, 2], [4, 5], [8, 8], [5, 6]])
                    
# Application de l'algorithme K-Means pour K=2 clusters
kmeans = KMeans(n_clusters=2, random_state=42)
kmeans.fit(X)
                    
# Centroids
centroids = kmeans.cluster_centers_
labels = kmeans.labels_
                    
# Visualisation des clusters
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap=plt.cm.Spectral)
plt.scatter(centroids[:, 0], centroids[:, 1], c='black', marker='X', s=200)
plt.title('K-Means Clusters')
plt.show()
                
            

Avantages et limites de l’algorithme K-Means

Avantages

• Efficacité : K-Means est rapide pour des ensembles de données de taille moyenne.

• Simplicité : Facile à comprendre et à implémenter.

• Flexibilité : Utile pour la segmentation des images, la personnalisation des clients, l’analyse exploratoire des données, etc.

Inconvénients

• Choix du nombre de clusters KK : Il peut être difficile de déterminer le meilleur KK.

• Sensibilité aux valeurs aberrantes : Les anomalies influencent fortement les centroids.

• Assomption de forme circulaire des clusters : K-Means suppose des clusters de forme relativement uniforme.

Conclusion

En résumé, les algorithmes K-Nearest Neighbors (KNN) et K-Means sont des outils essentiels en machine learning, chacun avec ses objectifs et son domaine d’application. Bien que KNN soit principalement utilisé pour des tâches de classification et de régression, tandis que K-Means est une méthode de clustering non supervisé, ils partagent des concepts fondamentaux basés sur les relations entre les points dans l’espace des caractéristiques.

KNN est une méthode intuitive et simple qui détermine la classe ou la valeur d’un point en se basant sur la proximité des voisins. Il offre des résultats souvent précis sans nécessiter beaucoup de prétraitement des données. Cependant, sa complexité computationnelle peut devenir un problème pour de grands ensembles de données, et le choix du paramètre K joue un rôle crucial dans ses performances.

De l’autre côté, K-Means, en tant qu’algorithme de clustering, vise à partitionner un ensemble de données en groupes homogènes. C’est une méthode puissante pour détecter des structures internes, explorer des motifs et comprendre les relations entre les caractéristiques sans avoir besoin d’étiquettes prédéfinies. Toutefois, il nécessite une bonne sélection du nombre de clusters (K) et peut être sensible aux valeurs aberrantes et à l’initialisation des centres de clusters.

Les deux algorithmes nécessitent souvent des étapes cruciales de préparation des données, comme la normalisation ou le nettoyage, afin d’obtenir des résultats optimaux. KNN et K-Means peuvent également être combinés à d’autres méthodes plus avancées (par exemple, K-Means++ pour le clustering ou des optimisations de KNN) pour améliorer leurs performances.

En fin de compte, KNN et K-Means sont des piliers en machine learning qui offrent des solutions efficaces, simples à comprendre, et souvent de bonnes performances, tout en servant de référence solide pour tester et comparer d’autres algorithmes plus sophistiqués.

Vous voulez apprendre l'IA en autonomie ?

Si vous êtes nouveau sur mon site, je vous invite à aller voir ma page sur Roadmap IA qui regroupe tous mes articles dans l'ordre pour vous facilitez l'apprentissage.