image menu
Experts Informatique FR
icon loupe
icon croix
All post Connexion

il y a 17 heures

Implémentation avancée de l’algorithme KNN dans différents langages : guide complet et optimisé

Dernière mise à jour : il y a 17 heures

Implémentation avancée de l’algorithme KNN dans différents langages : guide complet et optimisé

Implémentation avancée de l’algorithme KNN dans différents langages : guide complet et optimisé



Contenu de l'article


    
    
  1. Introduction et principes clés
    2. 
    
  2. Implémentation avancée en Python
    3. 
    
  3. Implémentation en R avec packages spécialisés
    4. 
    
  4. Implémentation en Java avec optimisation
    5. 
    
  5. Implémentation en C++ avec bibliothèques performantes
    6. 
    
  6. Implémentation en JavaScript/TypeScript
    7. 
    
  7. Bonnes pratiques et optimisations transverses
    8. 
    
  8. Conclusion et choix du langage selon le contexte
    9. 
    
  9. Articles complémentaires
    10. 
    
  10. Références
    11. 




Introduction et principes clés


L’algorithme des k plus proches voisins (K-Nearest Neighbors, KNN) est une méthode d’apprentissage supervisé non paramétrique, utilisée pour la classification et la régression. Son principe repose sur la recherche des k points les plus proches dans l’espace des caractéristiques pour prédire la classe ou la valeur d’un nouveau point. KNN est apprécié pour sa simplicité, son interprétabilité et son absence de phase d’apprentissage explicite.



Dans cet article, nous explorons des implémentations avancées et optimisées de KNN dans plusieurs langages (Python, R, Java, C++, JavaScript/TypeScript), en mettant l’accent sur les bonnes pratiques, les optimisations possibles et les bibliothèques spécialisées pour chaque langage.



Implémentation avancée en Python



1. Implémentation de base avec scikit-learn


Scikit-learn est la bibliothèque de référence pour le machine learning en Python. Voici un exemple complet, incluant la normalisation, la recherche du meilleur k par validation croisée, et l’utilisation de pipelines pour optimiser le workflow :


from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

# Chargement des données
data = load_iris()
X_train, X_test, y_train, y_test = train_test_split(data.data, data.target, test_size=0.3, random_state=42)

# Pipeline avec normalisation et KNN
pipeline = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier())
])

# Recherche du meilleur k
param_grid = {'knn__n_neighbors': range(1, 20)}
grid_search = GridSearchCV(pipeline, param_grid, cv=5)
grid_search.fit(X_train, y_train)

# Meilleure valeur de k et précision
print(f"Meilleur k : {grid_search.best_params_['knn__n_neighbors']}")
print(f"Précision : {grid_search.best_score_:.2f}")




2. Implémentation from scratch avec optimisation


Pour une compréhension approfondie, voici une implémentation manuelle de KNN en Python, optimisée avec NumPy pour le calcul des distances et la recherche des voisins :


import numpy as np
from collections import Counter

class KNN:
    def __init__(self, k=3):
        self.k = k

    def fit(self, X, y):
        self.X_train = X
        self.y_train = y

    def predict(self, X):
        predictions = [self._predict(x) for x in X]
        return np.array(predictions)

    def _predict(self, x):
        # Calcul des distances
        distances = [np.linalg.norm(x - x_train) for x_train in self.X_train]
        # Sélection des k plus proches voisins
        k_indices = np.argsort(distances)[:self.k]
        k_nearest_labels = [self.y_train[i] for i in k_indices]
        # Vote majoritaire
        most_common = Counter(k_nearest_labels).most_common(1)
        return most_common[0][0]

# Exemple d'utilisation
X_train = np.array([[1, 2], [1, 4], [1, 0], [4, 2], [4, 4], [4, 0]])
y_train = np.array([0, 0, 0, 1, 1, 1])
knn = KNN(k=3)
knn.fit(X_train, y_train)
print(knn.predict(np.array([[0, 0], [3, 3]])))




3. Optimisation avec parallélisation et ANN


Pour les grands jeux de données, l’utilisation de bibliothèques comme faiss (Facebook AI Similarity Search) ou annoy (Approximate Nearest Neighbors Oh Yeah) permet d’accélérer la recherche des voisins :


import faiss

# Indexation des données
index = faiss.IndexFlatL2(2)
index.add(X_train.astype('float32'))

# Recherche des k plus proches voisins
k = 3
distances, indices = index.search(X_test.astype('float32'), k)




Implémentation en R avec packages spécialisés



1. Utilisation du package class


Le package class est la référence pour KNN en R. Voici un exemple complet avec normalisation et validation croisée :


# Chargement des données
data(iris)
train <- iris[1:100, ]
test <- iris[101:150, ]

# Normalisation
train_scaled <- scale(train[, 1:4])
test_scaled <- scale(test[, 1:4])

# Entraînement et prédiction
library(class)
pred <- knn(train_scaled, test_scaled, train$Species, k = 3)

# Évaluation
table(pred, test$Species)




2. Optimisation avec caret et FNN


Le package caret permet d’optimiser le choix de k et de normaliser automatiquement les données. Le package FNN (Fast Nearest Neighbors) est optimisé pour les grands jeux de données :


library(caret)
library(FNN)

# Prétraitement et entraînement
ctrl <- trainControl(method = "cv", number = 5)
model <- train(Species ~ ., data = iris, method = "knn", trControl = ctrl, preProcess = c("center", "scale"), tuneLength = 10)

# Prédiction
predict(model, newdata = test)




Implémentation en Java avec optimisation



1. Implémentation de base


Voici une implémentation simple de KNN en Java, avec calcul de distance euclidienne et vote majoritaire :


import java.util.*;

class Point {
    double[] features;
    int label;

    public Point(double[] features, int label) {
        this.features = features;
        this.label = label;
    }
}

public class KNN {
    private List points;
    private int k;

    public KNN(List points, int k) {
        this.points = points;
        this.k = k;
    }

    public int predict(double[] newPoint) {
        PriorityQueue> queue = new PriorityQueue<>((a, b) -> Double.compare(a.getKey(), b.getKey()));

        for (int i = 0; i < points.size(); i++) {
            double dist = distance(newPoint, points.get(i).features);
            queue.add(new AbstractMap.SimpleEntry<>(dist, points.get(i).label));
        }

        Map labelCounts = new HashMap<>();
        for (int i = 0; i < k; i++) {
            int label = queue.poll().getValue();
            labelCounts.put(label, labelCounts.getOrDefault(label, 0) + 1);
        }

        return Collections.max(labelCounts.entrySet(), Map.Entry.comparingByValue()).getKey();
    }

    private double distance(double[] a, double[] b) {
        double sum = 0;
        for (int i = 0; i < a.length; i++) {
            sum += Math.pow(a[i] - b[i], 2);
        }
        return Math.sqrt(sum);
    }

    public static void main(String[] args) {
        List points = Arrays.asList(
            new Point(new double[]{1, 2}, 0),
            new Point(new double[]{1, 4}, 0),
            new Point(new double[]{4, 2}, 1),
            new Point(new double[]{4, 4}, 1)
        );
        KNN knn = new KNN(points, 3);
        System.out.println(knn.predict(new double[]{2, 3}));
    }
}




2. Optimisation avec Weka


La bibliothèque Weka offre une implémentation optimisée de KNN, avec des options de normalisation et de sélection de k :


import weka.classifiers.lazy.IBk;
import weka.core.Instances;
import weka.core.converters.ConverterUtils.DataSource;

public class KNNWeka {
    public static void main(String[] args) throws Exception {
        DataSource source = new DataSource("iris.arff");
        Instances data = source.getDataSet();
        if (data.classIndex() == -1) {
            data.setClassIndex(data.numAttributes() - 1);
        }

        IBk knn = new IBk(3);
        knn.buildClassifier(data);

        // Prédiction sur un nouvel exemple
        double[] newInstance = {5.1, 3.5, 1.4, 0.2};
        double pred = knn.classifyInstance(new weka.core.DenseInstance(1.0, newInstance));
        System.out.println("Prédiction : " + data.classAttribute().value((int) pred));
    }
}




Implémentation en C++ avec bibliothèques performantes



1. Implémentation de base avec STL


Voici une implémentation efficace de KNN en C++ utilisant la STL pour le calcul des distances et la recherche des voisins :


#include 
#include 
#include 
#include 
#include 

struct Point {
    std::vector features;
    int label;
};

class KNN {
private:
    std::vector points;
    int k;

public:
    KNN(const std::vector& points, int k) : points(points), k(k) {}

    int predict(const std::vector& newPoint) {
        std::vector> distances;
        for (const auto& point : points) {
            double dist = 0;
            for (size_t i = 0; i < point.features.size(); ++i) {
                dist += std::pow(point.features[i] - newPoint[i], 2);
            }
            distances.emplace_back(std::sqrt(dist), point.label);
        }

        std::sort(distances.begin(), distances.end());

        std::map labelCounts;
        for (int i = 0; i < k; ++i) {
            labelCounts[distances[i].second]++;
        }

        return std::max_element(
            labelCounts.begin(),
            labelCounts.end(),
            [](const auto& a, const auto& b) { return a.second < b.second; }
        )->first;
    }
};

int main() {
    std::vector points = {
        {{1, 2}, 0},
        {{1, 4}, 0},
        {{4, 2}, 1},
        {{4, 4}, 1}
    };
    KNN knn(points, 3);
    std::cout << knn.predict({2, 3}) << std::endl;
    return 0;
}




2. Optimisation avec MLpack


MLpack est une bibliothèque C++ optimisée pour le machine learning, offrant une implémentation rapide et scalable de KNN :


#include 

using namespace mlpack;

int main() {
    arma::mat data;
    data::Load("iris.csv", data, true);

    arma::mat trainData = data.rows(0, 100);
    arma::Row trainLabels = data.row(data.n_rows - 1).subrow(0, 100);

    arma::mat testData = data.rows(101, 149);
    arma::Row testLabels = data.row(data.n_rows - 1).subrow(101, 149);

    KNN<> knn(trainData, trainLabels, 3);

    arma::Row predictions;
    knn.Classify(testData, predictions);

    std::cout << "Précision : " << arma::accu(predictions == testLabels) / testLabels.n_elem << std::endl;

    return 0;
}




Implémentation en JavaScript/TypeScript



1. Implémentation de base avec ml.js


La bibliothèque ml-knn (partie de ml.js) permet une implémentation simple et efficace de KNN en JavaScript/TypeScript :


import { KNN } from 'ml-knn';

const X = [[1, 2], [1, 4], [4, 2], [4, 4]];
const y = [0, 0, 1, 1];

const knn = new KNN(X, y, { k: 3 });
const predictions = knn.predict([[2, 3]]);

console.log(predictions); // [0]




2. Implémentation from scratch


Pour une compréhension approfondie, voici une implémentation manuelle en TypeScript :


type Point = { features: number[]; label: number };

class KNN {
    private points: Point[];
    private k: number;

    constructor(points: Point[], k: number) {
        this.points = points;
        this.k = k;
    }

    predict(newPoint: number[]): number {
        const distances = this.points.map(point => ({
            distance: this.euclideanDistance(point.features, newPoint),
            label: point.label
        }));

        distances.sort((a, b) => a.distance - b.distance);

        const kNearest = distances.slice(0, this.k);
        const labelCounts = new Map();

        for (const neighbor of kNearest) {
            labelCounts.set(neighbor.label, (labelCounts.get(neighbor.label) || 0) + 1);
        }

        return Array.from(labelCounts.entries()).reduce((a, b) => b[1] > a[1] ? b : a)[0];
    }

    private euclideanDistance(a: number[], b: number[]): number {
        return Math.sqrt(a.reduce((sum, _, i) => sum + Math.pow(a[i] - b[i], 2), 0));
    }
}

// Exemple d'utilisation
const points: Point[] = [
    { features: [1, 2], label: 0 },
    { features: [1, 4], label: 0 },
    { features: [4, 2], label: 1 },
    { features: [4, 4], label: 1 }
];
const knn = new KNN(points, 3);
console.log(knn.predict([2, 3])); // 0




Bonnes pratiques et optimisations transverses



1. Normalisation des données


La normalisation est cruciale pour KNN, car l’algorithme est sensible à l’échelle des caractéristiques. Utilisez toujours une normalisation (standardisation ou mise à l’échelle min-max) avant d’appliquer KNN.



2. Choix de k


Le choix de k est un compromis entre biais et variance. Utilisez la validation croisée pour trouver la valeur optimale de k. En pratique, k est souvent choisi entre 3 et 10, mais cela dépend des données.



3. Optimisation pour les grands jeux de données


Pour les grands jeux de données, utilisez des structures de données optimisées (k-d trees, ball trees, HNSW) ou des bibliothèques spécialisées (FAISS, Annoy, MLpack) pour accélérer la recherche des voisins.



4. Gestion de la malédiction de la dimensionnalité


En haute dimension, la performance de KNN peut se dégrader. Utilisez des techniques de réduction de dimension (PCA, t-SNE, autoencodeurs) ou de sélection de caractéristiques pour atténuer ce phénomène.



Conclusion et choix du langage selon le contexte


Le choix du langage pour implémenter KNN dépend du contexte et des contraintes du projet :


    
    
  • Python : Idéal pour le prototypage rapide, grâce à scikit-learn et aux nombreuses bibliothèques d’optimisation (FAISS, Annoy).
    • 
    
  • R : Très adapté pour les analyses statistiques et la visualisation, avec des packages comme class et caret.
    • 
    
  • Java : Recommandé pour les applications d’entreprise ou les systèmes nécessitant une intégration avec des frameworks comme Weka.
    • 
    
  • C++ : À privilégier pour les applications nécessitant des performances maximales, notamment avec MLpack.
    • 
    
  • JavaScript/TypeScript : Utile pour les applications web ou les projets full-stack, avec des bibliothèques comme ml-knn.
    • 





Articles complémentaires





Références



            

        

    

    
    
    

        
Commentaires

            

            

                
                


                    
Aucun commentaire n'a été publié.