Machine Learning : l’algorithme des k plus proches voisins

L’algorithme des k plus proches voisins ou k-nearest neighbors (kNN) est un algorithme d’apprentissage automatique (Machine Learning) supervisé simple et facile à mettre en œuvre qui peut être utilisé pour résoudre les problèmes de classification et de régression.

Euh…wait a minute ?!? ***Pause***

Décomposons tous ces termes un par un

Machine Learning supervisé

Un algorithme de Machine Learning supervisé (par opposition à un algorithme de Machine Learning non supervisé) est un algorithme qui repose sur des données d’entrée étiquetées . Celui-ci va apprendre à partir de ces données et va produire une sortie appropriée lorsque de nouvelles données non étiquetées sont fournies.

Imaginez qu’un ordinateur soit un enfant, nous en sommes le superviseur (un parent, un tuteur ou un enseignant, par exemple) et nous souhaitons que l’enfant (l’ordinateur) apprenne à quoi ressemble un cochon. Nous montrerons à l’enfant plusieurs images différentes, dont certaines sont des cochons et le reste pourrait être des images de n’importe quel autre animal (chats, chiens, etc.).
Quand on voit un cochon, on crie «cochon!». Quand ce n’est pas un cochon, on crie «non, pas cochon!». Après avoir répété cela plusieurs fois avec l’enfant, on leur montre une photo et on leur demande: «cochon ou pas?». La plupart du temps, ils vont correctement identifier la présence ou non d’un cochon sur l’image.
Et bien de façon un peu imagé, c’est ça le Machine Learning supervisé.

Des algorithmes de Machine Learning supervisés sont utilisés pour résoudre des problèmes de classification ou de régression.

Problème de classification

Un problème de classification a une valeur discrète en sortie. Par exemple, les 2 intitulés “aime l’ananas sur la pizza” et “n’aime pas l’ananas sur la pizza” sont des données discrètes. Il n’y a pas de juste milieu. L’analogie ci-dessus consistant à apprendre à un enfant à identifier un cochon est un autre exemple de problème de classification.

Cette image montre à quoi des données de classification peuvent ressembler. Nous avons un prédicteur (ou un ensemble de prédicteurs) et une étiquette. Dans l’image, nous essayons de prédire si quelqu’un aime l’ananas (1) sur sa pizza ou non (0) en fonction de son âge (le prédicteur).
Il est courant de représenter la sortie (étiquette) d’un algorithme de classification sous la forme d’un nombre entier tel que 1, -1 ou 0. Dans ce cas, ces nombres sont purement représentatifs. Les opérations mathématiques ne doivent pas être effectuées sur eux, car cela n’aurait aucun sens. Si on essaye, quelle est la valeur de “aime l’ananas” + “n’aime pas l’ananas”? Effectivement, nous ne pouvons pas les ajouter, donc nous ne devrions pas non plus ajouter ou soustraire leurs représentations numériques {1, -1 ou 0}.

Problème de régression

Un problème de régression a pour sortie un nombre réel (un nombre décimale avec une virgule). Par exemple, nous pourrions utiliser les données du tableau ci-dessous pour estimer le poids d’une personne en fonction de sa taille.

Les données utilisées dans une analyse de régression seront similaires aux données présentées dans l’image ci-dessus. Nous avons une variable indépendante (ou un ensemble de variables indépendantes) et une variable dépendante (ce que nous essayons de deviner compte tenu de nos variables indépendantes). Par exemple, nous pourrions dire que la hauteur est la variable indépendante et le poids, la variable dépendante.

En outre, chaque ligne est généralement appelée un exemple, une observation ou un point de données, tandis que chaque colonne (n’incluant pas l’étiquette / la variable dépendante) est souvent appelée un prédicteur, une dimension, une variable indépendante ou une entité.

Machine Learning non supervisé

Un algorithme de Machine learning non supervisé utilise des données d’entrée sans étiquette – en d’autres termes, aucun enseignant (étiquette) ne dit à l’enfant (ordinateur) quand il a raison ou quand il a commis une erreur afin de pouvoir s’auto-corriger.

Contrairement à l’apprentissage supervisé qui essaie d’apprendre une fonction qui nous permettra de faire des prédictions à l’aide de nouvelles données non étiquetées, l’apprentissage non supervisé essaie d’apprendre la structure de base des données pour nous donner plus d’informations.

Le Machine Learning supervisé et non supervisé ont 2 objectifs bien différents.

Si vous voulez maîtriser tous ces concepts de classification / régression, supervisé / non supervisé à travers un cours théorique et des exemples concrets, vous pouvez suivre ma formation complète de Machine Learning.

Les k plus proches voisins (k Nearest Neighbors – kNN)

L’algorithme kNN suppose que des objets similaires existent à proximité. En d’autres termes, des éléments similaires sont proches les uns des autres.

Remarquez dans l’image ci-dessus que la plupart du temps, des points de données similaires sont proches les uns des autres. L’algorithme KNN repose sur le fait que cette hypothèse est suffisamment vraie pour que l’algorithme soit utile. L’algorithme kNN utilise l’idée de similitude (parfois appelée distance ou proximité) avec certaines notions de mathématique que nous aurions pu apprendre dans notre enfance, à savoir le calcul de la distance entre des points sur un graphique.

Remarque: il est nécessaire de comprendre comment nous calculons la distance entre les points d’un graphique avant de poursuivre. Si vous ne connaissez pas ou avez besoin d’un rappel sur la façon dont on calcule la distance entre 2 points, cliquez ici puis revenez pour la suite 🙂

Il existe d’autres méthodes de calcul de la distance. Sachez que l’utilisation d’une méthode plutôt qu’une autre dépend du problème à résoudre. Cependant, la distance en ligne droite (également appelée distance euclidienne) est un choix sûr!

L’algorithme kNN

1. Charger les données
2. Initialiser k au nombre de plus proches voisins choisi
   3. Pour chaque exemple dans les données:
   3.1 Calculer la distance entre notre requête et l’observation itérative actuelle de la boucle depuis les données.
   3.2 Ajouter la distance et l’indice de l’observation concernée à une collection ordonnée de données
   4. Trier cette collection ordonnée contenant distances et indices de la plus petite distance à la plus grande (dans ordre croissant).
   5. Sélectionner les k premières entrées de la collection de données triées (équivalent aux k plus proches voisins)
   6. Obtenir les étiquettes des k entrées sélectionnées
   7. Si régression, retourner la moyenne des k étiquettes
   8. Si classification, retourner le mode (valeur la plus fréquente/commune) des k étiquettes

Implémentation de l’algorithme kNN (from scratch)

from collections import Counter
import math

def knn(data, query, k, distance_fn, choice_fn):
    """Algorithme des k plus proches voisins kNN"""
    
    neighbor_distances_and_indices = []
    
    # 3. Pour chaque observation des données
    for index, example in enumerate(data):
        # 3.1 Calculer la distance entre notre requête et l'observation itérative actuelle
        # de la boucle depuis les données.
        distance = distance_fn(example[:-1], query)
        
        # 3.2 Ajouter la distance et l'indice de l'observation concernée 
        # à une collection ordonnée de données
        neighbor_distances_and_indices.append((distance, index))
    
    # 4. Trier cette collection ordonnée contenant distances et indices de
    # la plus petite distance à la plus grande (dans l'ordre croissant)
    sorted_neighbor_distances_and_indices = sorted(neighbor_distances_and_indices)
    
    # 5. Sélectionner les k premières entrées de la précédente collection de données
    k_nearest_distances_and_indices = sorted_neighbor_distances_and_indices[:k]
    
    # 6. Obtenir les étiquettes des k entrées sélectionnées
    k_nearest_labels = [data[i][1] for distance, i in k_nearest_distances_and_indices]

    # 7. Si régression (choice_fn = mean), retourner la moyenne des k étiquettes
    # 8. Si classification (choice_fn = mode), retourner le mode des k étiquettes
    return k_nearest_distances_and_indices , choice_fn(k_nearest_labels)

def mean(labels):
    """Calcul de la moyenne des k étiquettes"""
    return sum(labels) / len(labels)

def mode(labels):
    """Calcul du mode des k étiquettes"""
    return Counter(labels).most_common(1)[0][0]

def euclidean_distance(point1, point2):
    """Calcul de la distance euclidienne"""
    sum_squared_distance = 0
    for i in range(len(point1)):
        sum_squared_distance += math.pow(point1[i] - point2[i], 2)
    return math.sqrt(sum_squared_distance)

def main():
    '''
    # Données de régression
    # 
    # Colonne 0: taille (en pouces)
    # Colonne 1: poids (en livres)
    '''
    reg_data = [
       [65.75, 112.99],
       [71.52, 136.49],
       [69.40, 153.03],
       [68.22, 142.34],
       [67.79, 144.30],
       [68.70, 123.30],
       [69.80, 141.49],
       [70.01, 136.46],
       [67.90, 112.37],
       [66.49, 127.45],
    ]
    
    # Question:
    # Compte tenu des données dont nous disposons, quelle est la meilleure 
    # estimation du poids d'une personne mesurant 60 pouces?
    reg_query = [60]
    reg_k_nearest_neighbors, reg_prediction = knn(
        reg_data, reg_query, k=3, distance_fn=euclidean_distance, choice_fn=mean
    )
    
    '''
    # Données de Classification
    # 
    # Colonne 0: age
    # Colonne 1: aime l'ananas
    '''
    clf_data = [
       [22, 1],
       [23, 1],
       [21, 1],
       [18, 1],
       [19, 1],
       [25, 0],
       [27, 0],
       [29, 0],
       [31, 0],
       [45, 0],
    ]
    # Question:
    # À la lumière des données dont nous disposons, une personne de 33 ans aime-t-elle
    # l'ananas sur sa pizza?
    clf_query = [33]
    clf_k_nearest_neighbors, clf_prediction = knn(
        clf_data, clf_query, k=3, distance_fn=euclidean_distance, choice_fn=mode
    )

if __name__ == '__main__':
    main()

Choisir la bonne valeur pour k

Pour sélectionner la valeur de k qui convient à vos données, nous exécutons plusieurs fois l’algorithme KNN avec différentes valeurs de k. Puis nous choisissons le k qui réduit le nombre d’erreurs rencontrées tout en maintenant la capacité de l’algorithme à effectuer des prédictions avec précision lorsqu’il reçoit des données nouvelles (non vues auparavant).

Voici quelques points à garder en tête:

1. Lorsque nous diminuons la valeur de k à 1, nos prédictions deviennent moins stables. Imaginons un instant que nous ayons k = 1 et que nous ayons un point de requête entouré de plusieurs points rouges et d’un vert (je pense au coin en haut à gauche du graphique coloré plus haut dans l’article), mais le point vert est le voisin le plus proche. Logiquement, nous penserions que le point de requête est probablement rouge, mais parce que k = 1, l’algorithme kNN prédit de manière incorrecte que le point de requête est vert.
2. Inversement, à mesure que nous augmentons la valeur de k, nos prédictions deviennent de plus en plus stables en raison du vote à la majorité ou de la moyenne. On est donc plus susceptible de faire des prédictions plus précises (jusqu’à un certain point). En contre partie, nous commençons à être sujet à nombre croissant d’erreurs. C’est à ce stade que nous savons que nous avons poussé le bouchon trop loin la valeur de k trop loin.
3. Dans les cas où nous votons à la majorité (par exemple, en choisissant le mode dans un problème de classification) parmi les étiquettes, nous choisissons généralement un nombre impair pour k (pour avoir un départage en cas d’égalité).

Avantages

1. L’algorithme est super simple et facile à mettre en œuvre.
2. Il n’est pas nécessaire de construire un modèle, d’ajuster plusieurs paramètres ou de faire des hypothèses supplémentaires.
3. L’algorithme est polyvalent. Il peut être utilisé pour la classification, la régression et la recherche d’informations (comme nous le verrons dans la section suivante).

Inconvénients

• L’algorithme ralentit considérablement à mesure que le nombre d’observations et/ou de variables dépendantes/indépendantes augmente. En effet, l’algorithme parcourt l’ensemble des observations pour calculer chaque distance.

kNN en pratique

Le principal inconvénient de KNN, qui est le ralentissement considérable à mesure que le volume de données augmente, en fait un choix peu pratique dans un contexte où les prédictions doivent être faites rapidement. De plus, certains algorithmes plus rapides peuvent produire des résultats de classification et de régression plus précis.

Cependant, à condition que vous disposiez de ressources informatiques suffisantes pour traiter rapidement les données que vous utilisez pour effectuer des prédictions, kNN peut toujours être utile pour résoudre des problèmes dont les solutions dépendent de l’identification d’objets similaires. Un exemple est l’utilisation de l’algorithme kNN dans les systèmes de recommandation, une application de la kNN-search.

Systèmes de recommandation

À l’échelle, cela ressemblerait à recommander des produits sur Amazon, des articles sur Medium, des films ou séries sur Netflix ou des vidéos sur YouTube. Nous pouvons être certains qu’ils utilisent tous des moyens plus efficaces de proposer des recommandations en raison du volume énorme de données qu’ils traitent.

Cependant, nous pourrions reproduire un de ces systèmes de recommandation à une plus petite échelle en utilisant ce que nous avons appris ici dans cet article. Tentons de construire l’embryon d’un système de recommandation de films.

À quelle question essayons-nous de répondre?

Compte tenu de notre ensemble de données de films, quels sont les 5 films les plus similaires à une requête de film?

Recueillir des données de films

Si nous travaillions chez Netflix, Hulu ou IMDb, nous pourrions récupérer les données de leur entrepôt de données. Puisque nous ne travaillons dans aucune de ces entreprises, nous devons obtenir nos données par un autre moyen. Nous pourrions utiliser certaines données de films provenant du repository UCI Machine Learning, du dataset d’IMDb ou encore créer minutieusement les nôtres.

Exploration, nettoyage et préparation des données

Partout où nous avons obtenu nos données, il peut y avoir des problèmes que nous devons corriger pour les préparer à l’algorithme kNN. Par exemple, les données peuvent ne pas être au format attendu par l’algorithme ou il peut y avoir des valeurs manquantes que nous devrions renseigner ou encore supprimer des données avant de les transférer dans l’algorithme.

Notre implémentation kNN ci-dessus repose sur des données structurées. Il doit être sous forme de tableau. En outre, l’implémentation suppose que toutes les colonnes contiennent des données numériques et que la dernière colonne de nos données comporte des étiquettes sur lesquelles nous pouvons effectuer certaines fonctions. Ainsi, quelle que soit l’origine des données, nous devons les rendre conformes à ces contraintes.

Les données ci-dessous sont un exemple de ce à quoi nos données nettoyées pourraient ressembler. Les données contiennent trente films, y compris des données pour chaque film sur sept genres et leur classement IMDB. La colonne ‘Label’ des étiquettes comporte que des zéros parce que nous n’utilisons pas cet ensemble de données pour la classification ou la régression.

En outre, certaines relations entre les films ne seront pas prises en compte (acteurs, réalisateurs et thèmes, par exemple) lors de l’utilisation de l’algorithme kNN simplement parce que les données qui capturent ces relations sont absentes de l’ensemble de données. Par conséquent, lorsque nous exécutons l’algorithme kNN sur nos données, la similarité sera basée uniquement sur les genres de film présents ainsi que les évaluations IMDB des films.

Utilisation de l’algorithme

Imaginez un instant que nous naviguons sur le site « Recommande Moi un Film », un spin-off fictif d’IMDB, et nous tombons sur le film Pentagon Papers. Nous ne sommes pas sûr de vouloir le regarder, mais ce type de film nous intrigue. Nous sommes curieux de connaître d’autres films similaires. On fait défiler la section « More like this » pour voir les recommandations qui seront faites par « Recommande Moi un Film ». l’algorithme de recommandations commence à tourner.

Le site Web « Recommande Moi un Film » envoie une demande à son back-end pour les 5 films les plus similaires à Pentagon Papers. Le back-end dispose d’un ensemble de données de recommandation exactement comme le tableau ci-dessus. Il commence par créer la représentation des lignes (mieux connu sous le nom de feature vector) pour Pentagon Papers, puis exécute un programme similaire à celui ci-dessous pour rechercher les 5 films les plus similaires à Pentagon Papers, puis renvoie les résultats à l’écran.

Voici un exemple de système de recommandations (from scratch) à partir du fichier movies_recommendation_data.csv sur le film Pentagon Papers.

# En utilisant les fonctions knn et euclidean_distance 
# de notre algorithme kNN ci-dessus

def recommend_movies(movie_query, k_recommendations):
    raw_movies_data = []
    with open('movies_recommendation_data.csv', 'r') as md:
        # Eliminer la première ligne (header)
        next(md)

        # Lire les données
        for line in md.readlines():
            data_row = line.strip().split(',')
            raw_movies_data.append(data_row)

    # Préparer les données à être utiliser dans l'algorithme kNN en
    # choissant les colonnes appropriées et en convertissant les colonnes 
    # numériques en nombres car elles ont été lues sous forme de string
    movies_recommendation_data = []
    for row in raw_movies_data:
        data_row = list(map(float, row[2:]))
        movies_recommendation_data.append(data_row)

    # Utiliser l'algorithme kNN pour obtenir les 5 films les plus similaires
    # à Pentagon Papers.
    recommendation_indices, _ = knn(
        movies_recommendation_data, movie_query, k=k_recommendations,
        distance_fn=euclidean_distance, choice_fn=lambda x: None
    )

    movie_recommendations = []
    for _, index in recommendation_indices:
        movie_recommendations.append(raw_movies_data[index])

    return movie_recommendations

if __name__ == '__main__':
    the_post = [7.2, 1, 1, 0, 0, 0, 0, 1, 0] # feature vector pour Pentagon Papers
    recommended_movies = recommend_movies(movie_query=the_post, k_recommendations=5)

    # Afficher les titres des films recommandés
    for recommendation in recommended_movies:
        print(recommendation[1])

Lorsque nous exécutons ce programme, nous voyons que « Recommande Moi un Film » recommande 12 Years A Slave, Hacksaw Ridge, Queen of Katwe, The Wind Rises et A Beautiful Mind. Maintenant que nous comprenons parfaitement le fonctionnement de l’algorithme kNN, nous sommes en mesure d’expliquer exactement comment l’algorithme kNN en est venu à formuler ces recommandations.
Félicitations d’être arrivé jusqu’au bout !

Pour aller encore plus loin dans la compréhension de tous ces algorithmes, je vous recommande de jeter un œil à cette formation complète de Machine Learning.

Conclusion

L’algorithme des k plus proches voisins (kNN) est un algorithme de Machine Learning supervisé simple qui peut être utilisé pour résoudre des problèmes de classification et de régression. Il est facile à mettre en œuvre et à comprendre, mais présente un inconvénient majeur: son ralentissement est important à mesure que la taille des données utilisées augmente.

kNN recherche les distances entre une requête cible et toutes les observations des données. Ensuite il sélectionne les k observations les plus proches de la requête. Enfin il vote pour le libellé le plus fréquent (dans le cas de la classification) ou la moyenne des libellés (en le cas de la régression).

Dans le cas de la classification et de la régression, nous avons vu que choisir la bonne valeur de k pour nos données se faisait en essayant plusieurs k et en choisissant celui qui fonctionnait le mieux.

Pour finir l’article, nous avons examiné un exemple d’utilisation de l’algorithme kNN dans les systèmes de recommandation, une application de kNN-search.

Précision

[1] Le système de recommandation de films kNN implémenté dans cet article ne traite pas le cas où la requête de film pourrait faire partie du dataset de recommandation par souci de simplicité. Cela pourrait être absurde dans un système réel en production et devrait être traité de manière appropriée.

J’espère que l’article vous a plu, n’hésitez pas à partager et/ou commenter si c’est le cas, merci 🙂