L'algorithme des K voisins les plus proches et son implémentation en NodeJs

Un algorithme simple mais gourmand en mémoire

L’algorithme des K voisins les plus proches repose sur la notion de distance entre des éléments classifiés et des nouveaux éléments à classer. La tâche principale de cet algorithme est de pouvoir prévoir une catégorisation d’un objet à partir d’objets dont on connait la déjà la catégorie.

L’idée est de décortiquer nos objets suivants des propriétés nominales ou numériques et pour classer un nouvel objet, il suffit d’identifier les éléments les plus proches, les plus semblables. C’est pourquoi on parle de voisins. La lettre K fait quand à elle référence au nombre de voisins que l’on doit étudier pour déterminer la classe.

Si in prends par exemple la classification de détection de la musique électronique, dont le but serait d’identifier les morceaux de musique électronique et ceux qui ne le sont pas. On pourrait imaginer un algorithme étudiant le tempo et le nombre de mots chantés par l’artiste. On aurait déjà une centaine de morceaux étudiés et classé. Lorsqu’on veut classer un nouveau morceau il suffirait de regarder ces deux indicateurs pour déterminer une ressemblance avec l’ensemble des morceaux déjà catégorisés…

Un exemple !

Pour bien comprendre notre algo nous allons prendre un exemple réel, celui de l’immobilier. Imaginons une agence pourvue d’un jeune stagiaire qui souhaiterait prédire le temps de vente d’un bien.

Toute chose égales par ailleurs il pourrait considérer deux facteurs : le nombre de parcs publics présents à moins de 20 min à pied du logement et le nombre de pièces.

Donnée d’entrainement

Ce dernier va donc constituer un set de données d’entrainement avec l’ensemble des transactions de son agence. Chaque bien est donc classé en deux catégories : ceux qui se sont vendus rapidement et ceux qui ont nécessité un temps plus important pour être cédés.

Bien 1 : Pièces : 1 - Parcs : 2 - Catégorie : vendu rapidement
Bien 2 : Pièces : 2 - Parcs : 3 - Catégorie : vendu rapidement
Bien 3 : Pièces : 1 - Parcs : 1 - Catégorie : vendu rapidement
Bien 4 : Pièces : 3 - Parcs : 0 - Catégorie : vendu rapidement
Bien 5 : Pièces : 1 - Parcs : 1 - Catégorie : vendu rapidement
...

Nouvel exemple à classer

Tout le bureau est excité, on rentre un nouvel appartement (2 pièces, et 2 parcs à proximité) ! Chacun y va de son pronostique, mais notre stagiaire a une méthode secrète :

Il va donc déterminer la distance de ce nouveau bien avec chacun des biens déjà vendus et il va déduire des trois biens les plus proches pour savoir ce qu’il en sera de ce bien.

L’algorithme va donc consister à un calcul de distance puis on va sélectionner la classe dominante parmi les 3 classes des 3 voisins les plus proches.

Mise en pratique avec Nodejs

// nous ferons grand usage du module
// lodash qui est bien pratique lorsqu'on
// travaille sur des tableaux avec nodejs (https://lodash.com/)
var _ = require('lodash')

// On crée une variable data contenant un Array de l'ensemble de nos
// appartements déjas vendus dans le passé (cahcun des apprt est dans un sous tableau,
// le premier chiffre présentant le nombre de pièces, le second le nombre de parcs)
var data_training = [[1,2],[2,3],[1,1],[3,0],[1,1]];
// Pour chaque élément de notre tableau on associe une étiquette
var labels = ["vendu", "non_vendu","non_vendu","vendu","vendu"]

//Partie 2 :  Notre élément à classer
// 2 pièces, 2 parcs à proximité (l'ordre est capital !)
var element_to_class = [2,2]

// on crée un array vide
// pour contenir l'ensemble de nos résultats de cacul de distance
var array_of_results =[]

//Partie 3 :  calcul de la distance
// on itère sur notre set d'entrainement
_.forEach(data_training, function(element_of_array, key) {
 // Pour le premier passage dans la boucle
 // element_of_array= [1,2]
 // calcul ( Xa0 - Xb0 )^2
 var difference_square_first_feature = (element_to_class[0]-element_of_array[0])*(element_to_class[0]-element_of_array[0])
 // calcul ( Xa1 - Xb1 )^2
 var difference_square_second_feature = (element_to_class[1]-element_of_array[1])*(element_to_class[1]-element_of_array[1])
 // Calcul de la différence euclidienne
 var euclidean_distance = Math.sqrt(difference_square_first_feature + difference_square_second_feature)

 // Création d'un objet contenant le résultat du calcul de la distance
 var result = {}
 result.euclidean_distance = euclidean_distance
 result.label = labels[key]

 // on pousse cet objet dans notre tableau
 array_of_results.push(result)
});

// nous devons maintenant trouver les trois classes dont la distance est la plus faible
// pour trouver la classe de notre élément à classe (element_to_class)
// Nous classons donc le tableau array_of_results par la propriété euclidean_distance
// de manières ascendate (asc)
var array_ordened = _.orderBy(array_of_results, ['euclidean_distance'], ['asc']);

// nous prenons les trois premiers voisins
var three_first = _.take(array_ordened, 3);

//three first sera égale à
//[ { euclidean_distance: 33, label: 'non_vendu' },
// { euclidean_distance: 36.013886210738214, label: 'non_vendu' },
// { euclidean_distance: 37, label: 'vendu' } ]

var vote_for_label_vendu = 0;
var vote_for_label_non_vendu = 0;

// pour chcun des trois premiers voisins nous comptons les votes
_.forEach(three_first, function(element,key){
 if(element.label == "vendu"){
    vote_for_label_vendu ++;
 }else {
    vote_for_label_non_vendu ++;
 }
});

if(vote_for_label_vendu>vote_for_label_non_vendu){
 console.log("Ce bien sera vendu rapidement");
} else {
 console.log("Ce bien ne sera pas vendu rapidement");

}

Pour pouvoir exécuter ce code :

1. Créez un dossier sur votre ordinateur (p.ex immobilier)

2. Ouvres un terminal et déplacez vous avec la commande cd (change directory)

   $ cd immobilier

3. Installez lodash (via npm qu’il faut d’abord initialiser)

   $ npm init
   $ npm install lodash --save

4. Créez votre fichier index.js (soit directement via le terminal ou bien avec votre éditeur de code préféré). Ce dernier contiendra le code

   $ touch index.js

5. Copiez le code précédent.

6. Lancez l’algorithme !

   $ node index.js

Pour bien comprendre je vous invite à reprendre ligne par ligne et d’essayer de le réécrire à votre sauce (l’utilisation de lodash (https://lodash.com/) n’est pas obligatoire mais très conseillée)