L’algorithme des k plus proches voisins (KNN) en Python en moins de 128 mots.

L’algorithme d’apprentissage des k plus proches voisins (KNN) est utilisé pour effectuer de la classification de données.

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. Généralement un bon point de départ est la distance euclidienne.

L’algorithme est le suivant :

Pour une entrée x quelle est sa classe y si je me base sur les k voisins les plus proches de x ?

1. 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)
2. Faire voter chacune de ces données d’entrainement pour sa classe y.
3. Retourner la classe majoritaire

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.

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))