Le laboratoire de science des données
Classification k-NN pondérée à l’aide de C#
Dr. James McCaffrey de Microsoft Research utilise un programme complet et des instructions étape par étape pour expliquer la technique d’apprentissage automatique du bonheur, qui peut être utilisée pour prédire le score d’une personne à partir de son revenu et de son éducation, par exemple.
Le but d’un problème de classification pondéré k-NN (“k-plus proches voisins”) est de prédire une valeur discrète appelée étiquette de classe. L’idée est mieux expliquée par un exemple concret. Supposons que vous ayez un ensemble de 30 éléments de données où chaque élément se compose du revenu annuel d’une personne, de son éducation (années) et de son score de bonheur de la personnalité (0, 1 ou 2). Vous voulez prédire le score de bonheur d’une personne à partir de son revenu et de son éducation. Il s’agit d’un exemple de classification multiclasse car la variable à prédire, le bonheur, a trois valeurs possibles ou plus. Si la variable à prédire n’avait que deux valeurs possibles, le problème serait appelé classification binaire. La technique k-NN peut gérer à la fois les problèmes de classification multi-classes et binaires.
Une bonne façon de voir où va cet article est de jeter un coup d’œil à la capture d’écran d’un programme de démonstration dans Figure 1. La démo configure 30 éléments de données. Chacun a un identifiant de données (de 0 à 29), un revenu annuel (normalisé en divisant par 100 000 $), une éducation (normalisée en divisant par 20) et un score de bonheur (0, 1, 2). Les éléments de données ressemblent à :
ID Income Education Happy -------------------------- 00 0.32 0.43 0 01 0.26 0.54 0 . . . 12 0.39 0.43 1 . . . 29 0.71 0.22 2
Le graphique dans Figure 2 affiche les données. L’objectif est de prédire le score de bonheur d’une personne qui a (revenu, éducation) de (0,62, 0,35). Notez que toutes les valeurs de prédicteur sont numériques. Il s’agit d’une caractéristique clé de la technique de classification k-NN présentée dans cet article. Si vous disposez de données prédictives non numériques, telles que l’âge d’une personne en années, vous devez utiliser une technique de classification différente telle qu’un réseau neuronal ou un arbre de décision.
Le programme de démonstration spécifie k = 6, puis calcule les six points de données les plus proches de l’élément (0,62, 0,35) à classer. Sur les six points les plus proches, trois sont de classe 0, un est de classe 1 et deux sont de classe 2. Un schéma de vote à la règle de la majorité simple conclurait que (0,62, 0,35) est de classe 0. La démo utilise un schéma de vote pondéré où plus proche les points de données reçoivent plus de poids. Les votes pondérés sont (0,5711, 0,1782, 0,2508). La plus grande valeur est à l’index [0] et donc la prédiction est bonheur = 0.
Cet article suppose que vous avez des compétences de programmation intermédiaires ou supérieures avec un langage de la famille C tel que Python ou Java, mais ne suppose pas que vous savez quoi que ce soit sur la classification K-NN pondérée. Le code de démonstration complet et les données associées sont présentés dans cet article. Le code source et les données sont également disponibles dans le téléchargement qui l’accompagne. Toutes les vérifications d’erreur normales ont été supprimées pour garder les idées principales aussi claires que possible.
Comprendre la classification k-NN pondérée
La première étape de la classification k-NN pondérée consiste à calculer les distances entre l’élément de données à prédire et chacun des points de données. Il existe de nombreuses façons de calculer la distance entre deux points, mais la distance euclidienne est simple et efficace dans la plupart des cas.
Par exemple, la distance euclidienne entre l’élément cible (0,62, 0,35) et le point de données [09] à (0.61, 0.42) est :
dist = sqrt( (0.62 - 0.61)^2 + (0.35 - 0.42)^2 )
= sqrt( 0.0001 + 0.0049 )
= sqrt(0.0050)
= 0.0707
Il est important que les valeurs des prédicteurs numériques soient normalisées afin que les variables de grande ampleur, telles que le revenu, ne submergent pas les variables de plus petite ampleur.
L’étape suivante consiste à trouver les k points de données les plus proches de l’élément cible. Cela se fait en triant toutes les distances et en extrayant les k premiers éléments et distances. Pour les données de démonstration, les k = 6 éléments les plus proches de (0,62, 0,35) sont :
ID Data Class Dist Inv Dist ------------------------------------ 09 (0.61 0.42) 0 0.0707 14.1421 07 (0.55 0.32) 0 0.0762 13.1306 18 (0.55 0.41) 1 0.0922 10.8465 28 (0.64 0.24) 2 0.1118 8.9443 05 (0.49 0.32) 0 0.1334 7.4953 29 (0.71 0.22) 2 0.1581 6.3246
Pour pondérer plus lourdement des éléments de données plus proches, l’inverse de la distance est utilisé. À ce stade, vous pouvez simplement additionner les distances inverses pour chaque classe comme suit :
class 0: 14.1421 + 13.1306 + 7.4953 = 34.7680
class 1: 10.8465
class 2: 8.9443 + 6.3246 = 15.2689
-------
60.8834
La prédiction est la classe avec les votes pondérés les plus élevés, la classe 0. Le programme de démonstration normalise les votes pondérés en divisant chacun par leur somme, qui est de 60,8834. Cela rend la somme des votes pondérés à 1,0 et un peu plus facile à interpréter :
class 0: 34.7680 / 60.8834 = 0.5711
class 1: 10.8465 / 60.8834 = 0.1782
class 2: 15.2689 / 60.8834 = 0.2508
------
1.0000
La plus grande faiblesse de la classification k-NN est qu’il n’y a pas de bonne façon de sélectionner la valeur de k. Pour un problème donné, différentes valeurs de k donnent souvent des prédictions différentes. Une technique pour résoudre ce problème consiste à utiliser plusieurs valeurs différentes de k, puis à utiliser la classe prédite la plus courante.
Le programme de démonstration
Le programme de démonstration complet, avec quelques modifications mineures pour gagner de la place, est présenté dans Liste 1. Pour créer le programme, j’ai lancé Visual Studio et créé une nouvelle application console C# .NET Core nommée KNN. J’ai utilisé Visual Studio 2019 (édition communautaire gratuite), mais la démo n’a pas de dépendances importantes, donc n’importe quelle version de Visual Studio fonctionnera correctement. Vous pouvez également utiliser le programme Visual Studio Code.
Une fois le code du modèle chargé, dans la fenêtre de l’éditeur, j’ai supprimé toutes les références d’espace de noms inutiles, ne laissant que la référence à l’espace de noms système de niveau supérieur. Dans la fenêtre de l’Explorateur de solutions, j’ai cliqué avec le bouton droit sur le fichier Program.cs, je l’ai renommé en KNNProgram.cs plus descriptif et j’ai autorisé Visual Studio à renommer automatiquement la classe Program en KNNProgram.
Liste 1 :
Code de démonstration k-NN complet
using System;
namespace KNN
{
class KNNProgram
{
static void Main(string[] args)
{
Console.WriteLine("Begin weighted k-NN classification demo ");
Console.WriteLine("Normalized income, education data: ");
Console.WriteLine("[id = 0, 0.32, 0.43, class = 0]");
Console.WriteLine(" . . . ");
Console.WriteLine("[id = 29, 0.71, 0.22, class = 2]");
double[][] data = GetData();
double[] item = new double[] { 0.62, 0.35 };
Console.WriteLine("nNearest (k=6) to (0.35, 0.38):");
Analyze(item, data, 6, 3); // 3 classes
Console.WriteLine("nEnd weighted k-NN demo ");
Console.ReadLine();
}
static void Analyze(double[] item, double[][] data, int k, int c)
{
// 1. Compute all distances
int N = data.Length;
double[] distances = new double[N];
for (int i = 0; i < N; ++i)
distances[i] = DistFunc(item, data[i]);
// 2. Get ordering
int[] ordering = new int[N];
for (int i = 0; i < N; ++i)
ordering[i] = i;
double[] distancesCopy = new double[N];
Array.Copy(distances, distancesCopy, distances.Length);
Array.Sort(distancesCopy, ordering);
// 3. Show info for k-nearest
double[] kNearestDists = new double[k];
for (int i = 0; i < k; ++i)
{
int idx = ordering[i];
ShowVector(data[idx]);
Console.Write(" dist = " +
distances[idx].ToString("F4"));
Console.WriteLine(" inv dist " +
(1.0 / distances[idx]).ToString("F4"));
kNearestDists[i] = distances[idx];
}
// 4. Vote
double[] votes = new double[c]; // one per class
double[] wts = MakeWeights(k, kNearestDists);
Console.WriteLine("nWeights (inverse technique): ");
for (int i = 0; i < wts.Length; ++i)
Console.Write(wts[i].ToString("F4") + " ");
Console.WriteLine("nnPredicted class: ");
for (int i = 0; i < k; ++i)
{
int idx = ordering[i];
int predClass = (int)data[idx][3];
votes[predClass] += wts[i] * 1.0;
}
for (int i = 0; i < c; ++i)
Console.WriteLine("[" + i + "] " +
votes[i].ToString("F4"));
} // Analyze
static double[] MakeWeights(int k, double[] distances)
{
// Inverse technique
double[] result = new double[k]; // one per neighbor
double sum = 0.0;
for (int i = 0; i < k; ++i) {
result[i] = 1.0 / distances[i];
sum += result[i];
}
for (int i = 0; i < k; ++i)
result[i] /= sum;
return result;
}
static double DistFunc(double[] item, double[] dataPoint)
{
double sum = 0.0;
for (int i = 0; i < 2; ++i) {
double diff = item[i] - dataPoint[i + 1];
sum += diff * diff;
}
return Math.Sqrt(sum);
}
static double[][] GetData()
{
double[][] data = new double[30][];
data[0] = new double[] { 0, 0.32, 0.43, 0 };
data[1] = new double[] { 1, 0.26, 0.54, 0 };
data[2] = new double[] { 2, 0.27, 0.6, 0 };
data[3] = new double[] { 3, 0.37, 0.36, 0 };
data[4] = new double[] { 4, 0.37, 0.68, 0 };
data[5] = new double[] { 5, 0.49, 0.32, 0 };
data[6] = new double[] { 6, 0.46, 0.7, 0 };
data[7] = new double[] { 7, 0.55, 0.32, 0 };
data[8] = new double[] { 8, 0.57, 0.71, 0 };
data[9] = new double[] { 9, 0.61, 0.42, 0 };
data[10] = new double[] { 10, 0.63, 0.51, 0 };
data[11] = new double[] { 11, 0.62, 0.63, 0 };
data[12] = new double[] { 12, 0.39, 0.43, 1 };
data[13] = new double[] { 13, 0.35, 0.51, 1 };
data[14] = new double[] { 14, 0.39, 0.63, 1 };
data[15] = new double[] { 15, 0.47, 0.4, 1 };
data[16] = new double[] { 16, 0.48, 0.5, 1 };
data[17] = new double[] { 17, 0.45, 0.61, 1 };
data[18] = new double[] { 18, 0.55, 0.41, 1 };
data[19] = new double[] { 19, 0.57, 0.53, 1 };
data[20] = new double[] { 20, 0.56, 0.62, 1 };
data[21] = new double[] { 21, 0.28, 0.12, 1 };
data[22] = new double[] { 22, 0.31, 0.24, 1 };
data[23] = new double[] { 23, 0.22, 0.3, 1 };
data[24] = new double[] { 24, 0.38, 0.14, 1 };
data[25] = new double[] { 25, 0.58, 0.13, 2 };
data[26] = new double[] { 26, 0.57, 0.19, 2 };
data[27] = new double[] { 27, 0.66, 0.14, 2 };
data[28] = new double[] { 28, 0.64, 0.24, 2 };
data[29] = new double[] { 29, 0.71, 0.22, 2 };
return data;
}
static void ShowVector(double[] v)
{
Console.Write("idx = " + v[0].ToString().PadLeft(3) +
" (" + v[1].ToString("F2") + " " +
v[2].ToString("F2") + ") class = " + v[3]);
}
} // Program
} // ns
Le programme de démonstration code en dur les données dans une fonction GetData() définie par le programme. Les données sont renvoyées sous la forme d'un double de style tableau de tableaux[ ][ ] matrice. Dans un scénario non démo, vous souhaiterez peut-être stocker des données dans un fichier texte et écrire une fonction d'assistance pour lire les données dans une matrice de tableaux.
La première valeur de chaque élément de données est un ID arbitraire. J'ai utilisé des nombres entiers consécutifs de 0 à 29, mais dans de nombreux cas, vous auriez des identifiants significatifs tels que le numéro d'identification d'employé d'une personne. L'algorithme k-NN n'a pas besoin d'ID de données, la colonne ID aurait donc pu être omise. Les deuxième et troisième valeurs sont les valeurs de prédicteur normalisées. La quatrième valeur est l'ID de classe. Les ID de classe pour k-NN n'ont pas besoin d'être des entiers de base zéro, mais l'utilisation de ce schéma est pratique.
Calcul des distances
La première étape de l'algorithme k-NN consiste à calculer la distance entre chaque élément de données étiqueté et l'élément à classer. D'après mon expérience et quelques résultats de recherche, le choix de la fonction de distance à appliquer n'est pas aussi critique qu'on pourrait s'y attendre, et la simple distance euclidienne fonctionne généralement bien.
L'implémentation de démonstration de la distance euclidienne est :
static double DistFunc(double[] item, double[] dataPoint)
{
double sum = 0.0;
for (int i = 0; i < 2; ++i) {
double diff = item[i] - dataPoint[i+1];
sum += diff * diff;
}
return Math.Sqrt(sum);
}
Notez que l'indexation de la boucle for est codée en dur avec 2 pour le nombre de valeurs de prédicteur et la différence entre l'élément[i] et point de données[i+1] est décalé pour tenir compte de la valeur de l'ID de données à la position [0]. Le point ici est qu'il existe généralement un compromis entre le codage d'un algorithme d'apprentissage automatique pour un problème spécifique et le codage de l'algorithme en vue d'une utilisation à des fins générales. Parce que k-NN est si simple et facile à mettre en œuvre, je préfère généralement l'approche code-pour-problème spécifique.
Trier ou classer les distances
Une fois que toutes les distances ont été calculées, l'algorithme k-NN doit trouver les k distances les plus proches (les plus petites). L'approche utilisée par la démo consiste à utiliser une surcharge soignée de la méthode .NET Array.Sort pour trier uniquement les distances et les index de données associés en parallèle. Le code clé est :
int[] ordering = new int[N]; for (int i = 0; i < N; ++i) ordering[i] = i; double[] distancesCopy = new double[N]; Array.Copy(distances, distancesCopy, distances.Length); Array.Sort(distancesCopy, ordering);
Le tableau nommé tri contient initialement 0, 1, 2 . . 29. Une copie des 29 distances à l'élément à classer est créée car vous ne voulez pas perdre les distances dans leur ordre d'origine. L'instruction Array,Sort(distancesCopy, ordering) trie les valeurs du tableau distancesCopy de la plus petite à la plus grande à l'aide de l'algorithme Quicksort, et réorganise simultanément les valeurs d'index dans le tableau de commande. Le résultat est que la première valeur dans l'ordre des tableaux est l'index dans les données de l'élément avec la plus petite distance, la deuxième valeur dans l'ordre contient l'index de la deuxième distance la plus proche, et ainsi de suite. Une fonctionnalité très intéressante du langage C#.
Emballer
Les deux principaux avantages de la classification k-NN pondérée sont 1.) elle est simple à comprendre et à mettre en œuvre, et 2.) les résultats sont facilement interprétables. Les deux principaux inconvénients de la classification k-NN pondérée sont 1.) il n'existe aucun moyen de choisir la valeur de k, et 2.) la technique ne fonctionne bien qu'avec des valeurs de prédicteur strictement numériques car il n'est généralement pas possible de définir un bonne fonction de distance pour les points de données non numériques.
Pour un exemple utilisant Python, consultez l'article « Classification k-NN pondérée à l'aide de Python ».
A propos de l'auteur
Dr. James McCaffrey travaille pour Microsoft Research à Redmond, Wash. Il a travaillé sur plusieurs produits Microsoft, dont Azure et Bing. Jacques est joignable au [email protected].
.