L’algorithme knn python d’apprentissage des k plus proches voisins (KNN) est utilisé pour effectuer de la classification de données.
Introduction
Pour prédire la classification d’une nouvelle donnée, l’algorithme se base sur les k enregistrements issus de l’ensemble de données d’apprentissage sont alors localisés les plus similaires à ce nouvel enregistrement.
La similitude entre les enregistrements peut être mesurée de différentes manières. Et généralement un bon point de départ est la distance euclidienne.
L’algorithme knn python :
Pour une entrée x quelle est sa classe y si je me base sur les k voisins les plus proches de x ?
- Trouver les k entrée partie les données d’entrainement qui sont les plus “proches” de mon entrée x (ici on utilisera par exemple la distance euclidienne)
- Faire voter chacune de ces données d’entrainement pour sa classe y.
- Retourner la classe majoritaire
Ainsi, Le succès de l’algorithme va reposer sur la quantité de donnée d’entrainement et sur la qualité de la mesure de la distance entre 2 vecteurs x.
Implémentation python de l’algorithme knn des k plus proches voisins.
Finalement, Voici un exemple d’utilisation et d’implémentation Python sur la base de données qui concerne l’accord d’un crédit en fonction de l’age et du montant demandé. La classe correspond à la réponse OUI ou NON.
from math import sqrt
# Faire une predicition de la classification
def predire_classification(donnee_test, entrainement, nombre_voisins_vote):
voisins = recherche_voisins(entrainement, donnee_test, nombre_voisins_vote)
sortie = [vecteur[-1] for vecteur in voisins]
prediction = max(set(sortie), key=sortie.count)
return prediction
#Distance euclidienne de 2 vecteurs
def distance_euclidienne(vecteur1, vecteur2):
distance = 0.0
for i in range(len(vecteur1)-1):
distance += (vecteur1[i] - vecteur2[i])**2
return sqrt(distance)
# Recherche les voisins
def recherche_voisins(entrainement, donnee_test, nbVoisins):
distances = list()
for ligneEntrainement in entrainement:
dist = distance_euclidienne(donnee_test, ligneEntrainement)
distances.append((ligneEntrainement, dist))
distances.sort(key=lambda tup: tup[1])
kVoisins = list()
for i in range(nbVoisins):
kVoisins.append(distances[i][0])
return kVoisins
# Données d'entrainement
donneesApprentissage = [[25,40000,'NON'],
[30,60000,'OUI'],
[35,80000,'NON'],
[45,50000,'NON'],
[20,60000,'NON'],
[60,15000,'NON'],
[70,5000,'OUI'],
[80,1000,'NON'],
[33,80000,'OUI'],
[32,10000,'NON']]
prediction = predire_classification(donneesApprentissage[1], donneesApprentissage, 3)
print('On devrait trouver %s, la prediction est : %s.' % (donneesApprentissage[1][-1], prediction))
Liens externes :
https://fr.wikipedia.org/wiki/M%C3%A9thode_des_k_plus_proches_voisins
