L'algorithme du plus proche voisin en MATLAB : Guide complet d'implémentation

Une approche pratique pour construire des systèmes de classification et de recherche efficaces

Points essentiels à retenir

L'algorithme k-NN peut être implémenté directement avec les fonctions natives de MATLAB comme fitcknn ou knnsearch, offrant une solution rapide et optimisée
Pour une compréhension approfondie, vous pouvez implémenter votre propre version en calculant les distances entre points et en sélectionnant les k voisins les plus proches
Le choix de la métrique de distance est crucial pour l'efficacité de l'algorithme (euclidienne, Manhattan, Minkowski, etc.)

Comprendre l'algorithme du plus proche voisin

L'algorithme du plus proche voisin (Nearest Neighbor ou NN) est une méthode simple mais puissante en apprentissage automatique. Son extension, l'algorithme des k plus proches voisins (k-NN), est utilisée pour la classification et la régression. Le principe est simple : un nouvel élément est classé selon la majorité des classes de ses k voisins les plus proches.

mindmap root["Algorithme du plus proche voisin"] Principes ["Recherche de similarité"] ["Classification par proximité"] ["Non-paramétrique"] Métriques["Métriques de distance"] ["Euclidienne (la plus courante)"] ["Manhattan"] ["Minkowski"] ["Mahalanobis"] Applications ["Classification"] ["Régression"] ["Recherche d'images similaires"] ["Systèmes de recommandation"] Variantes ["k-NN (k plus proches voisins)"] ["Weighted k-NN"] ["Condensed NN"] ["Méthodes d'accélération (KD-Tree, Ball-Tree)"]

En MATLAB, vous disposez de plusieurs approches pour implémenter cet algorithme, allant des fonctions intégrées à une implémentation personnalisée. Nous allons explorer ces différentes méthodes.

Utilisation des fonctions natives de MATLAB

MATLAB offre des fonctions intégrées qui simplifient considérablement l'implémentation de l'algorithme du plus proche voisin.

Principales fonctions pour k-NN dans MATLAB

Fonction	Description	Syntaxe de base
fitcknn	Crée un modèle de classification k-NN	mdl = fitcknn(X, Y, 'NumNeighbors', k)
knnsearch	Recherche les k voisins les plus proches	[idx, dist] = knnsearch(X, Y, 'K', k)
ClassificationKNN	Classe représentant un classifieur k-NN	Générée par fitcknn
predict	Prédit les classes à l'aide d'un modèle k-NN	labels = predict(mdl, Xnew)

Exemple d'utilisation de fitcknn

% Charger les données (exemple avec fisheriris)
load fisheriris
X = meas;      % Caractéristiques
Y = species;   % Étiquettes

% Créer un modèle KNN avec k=5
knnModel = fitcknn(X, Y, 'NumNeighbors', 5);

% Effectuer une validation croisée
cvModel = crossval(knnModel);
loss = kfoldLoss(cvModel);
fprintf('Erreur de validation croisée: %f\n', loss);

% Prédire la classe d'un nouveau point
nouveauPoint = [5 1.45 3.2 0.8];
classePredit = predict(knnModel, nouveauPoint);
disp(['Classe prédite: ', char(classePredit)]);

Exemple d'utilisation de knnsearch

% Définir un ensemble de points
points = [1 2; 3 4; 5 6; 7 8; 9 10];
point_cible = [4 5];

% Trouver les 3 plus proches voisins
[indices, distances] = knnsearch(points, point_cible, 'K', 3);

% Afficher les résultats
fprintf('Indices des 3 plus proches voisins: %s\n', mat2str(indices));
fprintf('Distances aux 3 plus proches voisins: %s\n', mat2str(distances));

Implémentation personnalisée de l'algorithme

Pour mieux comprendre le fonctionnement de l'algorithme ou pour des besoins spécifiques, vous pouvez implémenter votre propre version de l'algorithme du plus proche voisin.

Fonction pour trouver le plus proche voisin

function [pointPlusProche, distance] = trouverVoisinPlusProche(points, cible)
    % Récupère le nombre de points
    nPoints = size(points, 1);
    
    % Initialisation
    distanceMin = Inf;
    pointPlusProche = [];
    
    % Boucle à travers tous les points
    for i = 1:nPoints
        % Calcul de la distance euclidienne
        distanceCourante = norm(points(i,:) - cible);
        
        % Mise à jour si nécessaire
        if distanceCourante < distanceMin
            distanceMin = distanceCourante;
            pointPlusProche = points(i,:);
        end
    end
    
    % Renvoi des résultats
    distance = distanceMin;
end

Implémentation de l'algorithme k-NN

function classe = knn(donnees_entrainement, classes_entrainement, nouveau_point, k)
    % Calcul des distances entre le nouveau point et tous les points d'entrainement
    num_points = size(donnees_entrainement, 1);
    distances = zeros(num_points, 1);
    
    for i = 1:num_points
        distances(i) = norm(donnees_entrainement(i,:) - nouveau_point);
    end
    
    % Tri des distances
    [distances_triees, indices] = sort(distances);
    
    % Sélection des k plus proches voisins
    voisins_indices = indices(1:k);
    classes_voisins = classes_entrainement(voisins_indices);
    
    % Détermination de la classe majoritaire
    classe = mode(classes_voisins);
end

Fonction pour l'interpolation du plus proche voisin (images)

function output = nearest_neighbor_interpolation(input, facteur_echelle)
    [hauteur, largeur] = size(input);
    nouvelle_hauteur = round(hauteur * facteur_echelle);
    nouvelle_largeur = round(largeur * facteur_echelle);
    
    output = zeros(nouvelle_hauteur, nouvelle_largeur);
    
    for i = 1:nouvelle_hauteur
        for j = 1:nouvelle_largeur
            % Calcul des coordonnées correspondantes dans l'image originale
            x = max(1, round(j / facteur_echelle));
            y = max(1, round(i / facteur_echelle));
            
            % Attribution de la valeur du pixel le plus proche
            output(i, j) = input(y, x);
        end
    end
    
    % Conversion au même type que l'entrée
    output = cast(output, class(input));
end

Performance et optimisation

La performance de l'algorithme k-NN dépend de plusieurs facteurs, notamment le choix de k, la métrique de distance, et la méthode d'optimisation utilisée. Voici une analyse comparative des performances selon différentes configurations :

Cette visualisation nous montre clairement que le choix de la méthode d'implémentation a un impact significatif sur les performances. L'utilisation de structures de données optimisées comme les KD-Trees améliore considérablement la vitesse d'exécution pour les grands ensembles de données.

Optimisations avancées en MATLAB

Utilisation du calcul parallèle

Pour les grands ensembles de données, vous pouvez améliorer les performances en utilisant le calcul parallèle :

% Activer le pool parallèle
parpool('local');

% Optimisation des hyperparamètres en parallèle
opts = struct('UseParallel', true);
knnModel = fitcknn(X, Y, 'OptimizeHyperparameters', 'auto', 'HyperparameterOptimizationOptions', opts);

Structures de données accélérées

MATLAB implémente automatiquement des structures de données optimisées comme les KD-Trees pour accélérer la recherche du plus proche voisin. Vous pouvez spécifier la méthode à utiliser :

% Utiliser un KD-Tree pour la recherche
[indices, distances] = knnsearch(points, point_cible, 'K', 3, 'NSMethod', 'kdtree');

Démonstration vidéo

Cette vidéo explique comment implémenter efficacement l'algorithme k-NN en MATLAB en moins de 2 minutes :

Cette démonstration montre les étapes essentielles pour implémenter et utiliser l'algorithme k-NN en MATLAB, en utilisant la fonction intégrée fitcknn. Elle présente également comment charger les données, créer un modèle, et effectuer des prédictions.

Exemples visuels de l'application k-NN

Visualisation des surfaces de décision avec k-NN

Cette image illustre la visualisation des surfaces de décision créées par un classifieur k-NN en MATLAB. Les différentes couleurs représentent les régions de l'espace attribuées à chaque classe. Cette visualisation est particulièrement utile pour comprendre comment le classificateur partage l'espace des caractéristiques et prend ses décisions.

Cette seconde image explique le principe fondamental de l'algorithme k-NN : la classification d'un nouvel élément (point d'interrogation) en fonction de la majorité des classes parmi ses k voisins les plus proches. Dans cet exemple, avec k=3, le nouvel élément serait classé comme un triangle, car deux des trois plus proches voisins sont des triangles.

Questions fréquemment posées

Comment choisir la valeur optimale de k ?

La valeur optimale de k dépend de vos données. Un k trop petit peut rendre l'algorithme sensible au bruit, tandis qu'un k trop grand peut masquer les détails locaux. Une approche courante consiste à utiliser la validation croisée pour tester différentes valeurs de k et choisir celle qui donne la meilleure performance. En général, utilisez des valeurs impaires pour éviter les égalités dans les votes. En MATLAB, vous pouvez automatiser ce processus avec :


  % Recherche du k optimal par validation croisée
  kValues = 1:2:15;
  errors = zeros(length(kValues), 1);
  
  for i = 1:length(kValues)
      knnModel = fitcknn(X, Y, 'NumNeighbors', kValues(i));
      cvModel = crossval(knnModel);
      errors(i) = kfoldLoss(cvModel);
  end
  
  [~, idx] = min(errors);
  kOptimal = kValues(idx);
  fprintf('Valeur optimale de k: %d\n', kOptimal);

Quelles sont les différentes métriques de distance utilisables ?

MATLAB permet d'utiliser plusieurs métriques de distance dans l'algorithme k-NN :

Euclidienne (par défaut) : distance en ligne droite entre deux points
Manhattan : somme des différences absolues des coordonnées
Minkowski : généralisation des distances euclidienne et Manhattan
Mahalanobis : prend en compte la covariance des variables
Cosinus : mesure la similarité d'orientation plutôt que la magnitude

Vous pouvez spécifier la métrique lors de l'appel des fonctions :


  % Utiliser la distance de Manhattan
  knnModel = fitcknn(X, Y, 'NumNeighbors', 5, 'Distance', 'cityblock');
  
  % Ou avec knnsearch
  [indices, distances] = knnsearch(points, point_cible, 'K', 3, 'Distance', 'cityblock');

Comment gérer les grands ensembles de données avec k-NN ?

L'algorithme k-NN peut devenir lent avec de grands ensembles de données. Voici quelques stratégies pour améliorer les performances :

Structures de données accélérées : utilisez des KD-Trees ou des Ball-Trees
Calcul parallèle : activez le traitement parallèle en MATLAB
Réduction de dimensionnalité : appliquez PCA ou d'autres techniques pour réduire le nombre de dimensions
Sous-échantillonnage : réduisez la taille du jeu de données d'entraînement
Approximation : utilisez des algorithmes comme Approximate Nearest Neighbors

Exemple de réduction de dimensionnalité avec PCA :


  % Appliquer PCA avant k-NN
  [coeff, score] = pca(X);
  X_reduced = score(:, 1:5);  % Garder les 5 premières composantes principales
  
  % Utiliser les données réduites pour k-NN
  knnModel = fitcknn(X_reduced, Y, 'NumNeighbors', 5);

Comment utiliser le k-NN pondéré en MATLAB ?

Le k-NN pondéré attribue des poids différents aux voisins en fonction de leur distance. Les voisins plus proches ont une influence plus grande sur la classification. En MATLAB, vous pouvez implémenter le k-NN pondéré en utilisant le paramètre 'Distance' avec des poids :


  % k-NN pondéré avec poids inversement proportionnels à la distance
  knnModel = fitcknn(X, Y, 'NumNeighbors', 5, 'Distance', 'euclidean', 'DistanceWeight', 'inverse');
  
  % Autres options pour DistanceWeight :
  % - 'equal' : tous les voisins ont le même poids (par défaut)
  % - 'inverse' : poids proportionnel à 1/distance
  % - 'squaredinverse' : poids proportionnel à 1/distance²
  % - @custom_function : fonction personnalisée qui définit les poids