Qu'est-ce que l'algorithme des k-plus proches voisins…

kNN (k plus proches voisins) est une méthode non paramétrique utilisée pour la classification et la régression. L'idée est simple : un objet est classé par la majorité des votes de ses voisins, où l'objet est attribué à la classe la plus courante parmi ses k voisins les plus proches. Pour la régression, la valeur moyenne des étiquettes des k voisins proches est prédite.

Aspects clés :

Paramètre k : Nombre de voisins pris en compte lors de la décision. Le choix de k influence fortement le résultat. Un k petit peut être sensible au bruit, un k grand peut ignorer les structures locales.
Métrique de distance : Utilisée pour déterminer la "proximité" entre les points de données. Les plus courantes : distance euclidienne, distance de Manhattan.
Caractéristiques :
- Algorithme "paresseux" : aucune ou très peu d'apprentissage (simplement stockage des données d'entraînement). La prédiction se fait uniquement lors de la requête.
- Facile à implémenter et à comprendre.
- La performance lors de la prédiction peut diminuer avec de grands ensembles de données, car il faut calculer les distances à tous les exemples d'entraînement.
- Sensible à l'échelle des caractéristiques.
- Peut mal fonctionner avec des données bruyantes.

Étapes du processus (pour la classification) :

Choisir la valeur de k.
Choisir la métrique de distance.
Pour un nouvel objet, pour lequel une prédiction doit être faite : a. Calculer la distance entre cet objet et tous les objets de l'ensemble d'entraînement. b. Sélectionner les k objets les plus proches de l'ensemble d'entraînement. c. Déterminer la classe la plus fréquente parmi ces k objets. d. Attribuer cette classe au nouvel objet.

Exemple (pseudo-code) :

# Fonction pour calculer la distance euclidienne
def euclidean_distance(p1, p2):
    # ... calcul de la distance ...

# Fonction pour rechercher les k plus proches voisins et prédire la classe
def predict(training_data, new_data_point, k, distance_metric):
    distances = []
    for data_point in training_data:
        dist = distance_metric(new_data_point, data_point['features'])
        distances.append((dist, data_point['label']))

    # Tri par distance et sélection des k plus proches
    distances.sort(key=lambda x: x[0])
    k_nearest = distances[:k]

    # Comptage des votes de classes
    class_votes = {}
    for dist, label in k_nearest:
        class_votes[label] = class_votes.get(label, 0) + 1

    # Définir la classe avec le plus de votes
    predicted_class = max(class_votes, key=class_votes.get)
    return predicted_class

Qu'est-ce que l'algorithme des k-plus proches voisins (kNN) ?