KNN from scratch !
Table des matièresClose
(d'après Machine Learning Basics with the K-Nearest Neighbors Algorithm)
1 Quelques définitions
L'algorithme KNN (k-nearest neighbors) est un algorithme d'apprentissage automatique supervisé simple et facile à mettre en œuvre, qui peut être utilisé pour résoudre les problèmes de classification et de régression.
Un algorithme d'apprentissage automatique supervisé (par opposition à un algorithme d'apprentissage automatique non supervisé) est un algorithme qui s'appuie sur des données d'entrée étiquetées pour apprendre une fonction qui produit une sortie appropriée lorsqu'il reçoit de nouvelles données non étiquetées.
Un problème de classification a pour résultat une valeur discrète. Par exemple, "aime l'ananas" et "n'aime pas l'ananas" sont des valeurs discrètes. Il n'y a pas de juste milieu. L'analogie consistant à apprendre à un enfant à identifier un chat ou un chien est un autre exemple de problème de classification.
Un problème de régression a pour résultat un nombre réel. Par exemple, nous pouvons utiliser les données du tableau ci-dessous pour estimer le poids d'une personne en fonction de sa taille.
Taille | Poids |
---|---|
65.78331 | 112.9925 |
71.51521 | 136.4873 |
69.39874 | 153.0269 |
68.21660 | 142.3354 |
67.78781 | 144.2971 |
68.69784 | 123.3024 |
69.80204 | 141.4947 |
70.01472 | 136.4623 |
67.90265 | 112.3723 |
66.78236 | 120.6672 |
66.48769 | 127.4516 |
67.62333 | 114.1430 |
68.30248 | 125.6107 |
67.11656 | 122.4618 |
68.27967 | 116.0866 |
71.09160 | 139.9975 |
66.46100 | 129.5023 |
68.64927 | 142.9733 |
Un algorithme d'apprentissage automatique non supervisé utilise des données d'entrée sans aucune étiquette - en d'autres termes, aucun enseignant (étiquette) ne dit à l'enfant (ordinateur) quand il a raison ou quand il a fait une erreur afin qu'il puisse s'auto-corriger. Contrairement à l'apprentissage supervisé qui tente d'apprendre une fonction qui nous permettra de faire des prédictions à partir de nouvelles données non étiquetées, l'apprentissage non supervisé tente d'apprendre la structure de base des données afin de nous donner un meilleur aperçu des données.
2 L'algorithme
L'algorithme KNN fonctionne de la manière suivante :
- Charger les données
- Initialiser 'K' pour choisir le nombre de voisins à considérer
- Pour chaque enregistrement du jeu de données
- Calculer la distance entre la donnée en question et l'enregistrement courant
- Ajouter la distance et l'indice de l'enregistrement dans une collection ordonnée
- Trier la collection par distances croissantes
- Choisir les 'K' premières entrées de la collection
- Obtenir les étiquettes de ces entrées
- S'il s'agit d'une régression, retourner la valeur moyenne des étiquettes
- S'il s'agit d'un classification, retourner la valeur prépondérante des étiquettes
from collections import Counter import math def knn(data, query, k, distance_fn, choice_fn): neighbor_distances_and_indices = [] # 3. For each example in the data for index, example in enumerate(data): # 3.1 Calculate the distance between the query example and the current # example from the data. distance = distance_fn(example[:-1], query) # 3.2 Add the distance and the index of the example to an ordered collection neighbor_distances_and_indices.append((distance, index)) # 4. Sort the ordered collection of distances and indices from # smallest to largest (in ascending order) by the distances sorted_neighbor_distances_and_indices = sorted(neighbor_distances_and_indices) # 5. Pick the first K entries from the sorted collection k_nearest_distances_and_indices = sorted_neighbor_distances_and_indices[:k] # 6. Get the labels of the selected K entries k_nearest_labels = [data[i][-1] for distance, i in k_nearest_distances_and_indices] # 7. If regression (choice_fn = mean), return the average of the K labels # 8. If classification (choice_fn = mode), return the mode of the K labels return k_nearest_distances_and_indices , choice_fn(k_nearest_labels) def mean(labels): return sum(labels) / len(labels) def mode(labels): return Counter(labels).most_common(1)[0][0] def euclidean_distance(point1, point2): 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)
Exemple de régression :
''' # Regression Data # # Column 0: height (inches) # Column 1: weight (pounds) ''' 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: # Given the data we have, what's the best-guess at someone's weight if they are 60 inches tall? reg_query = [60] reg_k_nearest_neighbors, reg_prediction = knn(reg_data, reg_query, k=3, distance_fn=euclidean_distance, choice_fn=mean) print(reg_prediction)
## 128.24666666666667
Exemple de classification :
''' # Classification Data # # Column 0: age # Column 1: likes pineapple ''' clf_data = [ [22, 1], [23, 1], [21, 1], [18, 1], [19, 1], [25, 0], [27, 0], [29, 0], [31, 0], [45, 0], ] # Question: # Given the data we have, does a 33 year old like pineapples? clf_query = [33] clf_k_nearest_neighbors, clf_prediction = knn(clf_data, clf_query, k=3, distance_fn=euclidean_distance, choice_fn=mode) print(clf_prediction)
## 0
3 Comment choisir une bonne valeur de 'K' :
- Lorsque nous réduisons la valeur de 'K' à 1, nos prédictions deviennent moins stables.
- Inversement, à mesure que nous augmentons la valeur de 'K', nos prédictions deviennent plus stables en raison du vote majoritaire / du calcul de la moyenne, et donc, plus susceptibles de faire des prédictions plus précises (jusqu'à un certain point). Finalement, nous commençons à constater un nombre croissant d'erreurs. C'est à ce moment-là que nous savons que nous avons poussé la valeur de 'K' trop loin.
- Dans le cas d'un vote à la majorité (par exemple dans un problème de classification) parmi les étiquettes, nous choisissons généralement un nombre impair pour K afin de pouvoir trancher.
Le principal inconvénient de l'algorithme KNN est qu'il devient nettement plus lent à mesure que le volume de données augmente, ce qui en fait un choix peu efficace dans les environnements où les prédictions doivent être faites rapidement. De plus, il existe des algorithmes plus rapides qui peuvent produire des résultats de classification et de régression plus précis.
4 Systèmes de recommandations
Comment recommander des produits sur Amazon, des films sur Netflix ou des vidéos sur YouTube ? Bien que nous puissions être certains qu'ils utilisent des moyens plus efficaces pour faire des recommandations en raison de l'énorme volume de données qu'ils traitent, nous pouvons reproduire l'un de ces systèmes de recommandation à plus petite échelle.
Construisons le noyau d'un système de recommandation de films.
Les données dans le fichier moviesrecommendationdata.csv sont un exemple de ce à quoi pourraient ressembler la base de notre système de recommandation. Les données contiennent trente films, y compris des données pour chaque film à travers sept genres et leurs évaluations IMDB. La colonne des étiquettes contient tous les zéros car nous n'utilisons pas cet ensemble de données pour la classification ou la régression.
Imaginez un instant. Nous naviguons sur le site MoviesXb, un spin-off IMDb fictif, et nous rencontrons "The Post". Nous ne sommes pas sûrs de vouloir le regarder, mais son genre nous intrigue ; nous sommes curieux de voir d'autres films similaires. Nous descendons jusqu'à la section "More Like This" pour voir quelles recommandations MoviesXb fera, et l'engrenage algorithmique commence à tourner. Le site Web de MoviesXb envoie une requête à son back-end pour obtenir les 5 films les plus similaires à The Post. Le back-end dispose d'un ensemble de données de recommandation exactement comme le nôtre. Il commence par créer la représentation en ligne (mieux connue sous le nom de vecteur de caractéristiques) pour "The Post", puis il exécute un programme similaire à celui présenté ci-dessous pour rechercher les 5 films les plus similaires à "The Post", et renvoie enfin les résultats au site Web MoviesXb.
def recommend_movies(movie_query, k_recommendations): raw_movies_data = [] with open('movies_recommendation_data.csv', 'r') as md: # Discard the first line (headings) next(md) # Read the data into memory for line in md.readlines(): data_row = line.strip().split(',') raw_movies_data.append(data_row) # Prepare the data for use in the knn algorithm by picking # the relevant columns and converting the numeric columns # to numbers since they were read in as strings movies_recommendation_data = [] for row in raw_movies_data: data_row = list(map(float, row[2:])) movies_recommendation_data.append(data_row) # Use the KNN algorithm to get the 5 movies that are most # similar to The Post. 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 for The Post recommended_movies = recommend_movies(movie_query=the_post, k_recommendations=5) # Print recommended movie titles for recommendation in recommended_movies: print(recommendation[1])
## 12 Years a Slave ## Hacksaw Ridge ## Queen of Katwe ## The Wind Rises ## A Beautiful Mind
Voici comment l'algorithme KNN en est arrivé à faire des recommandations.
Félicitations !