Mai 2019
Volume 34, numéro 5
[Série de tests]
Classification k-NN pondérée à l’aide de C#
Par James McCaffrey
.jpg "James McCaffrey")
L’objectif d’un problème de classification (ML) d’apprentissage consiste à prédire une valeur discrète. Par exemple, vous souhaiterez peut-être prédire la politique Learning (conservateur, modéré, libéral) d’une personne en fonction de leur âge, dépenses de soins de santé, sexe, années de formation et ainsi de suite. Il existe plusieurs techniques de classification différents, y compris les réseaux neuronaux, les arbres de décision et la régression logistique. Dans cet article, je montrerai comment implémenter l’algorithme pondérée voisins de k-le plus proche, à l’aide de la C# langage.
La meilleure façon de comprendre où cet article est menée consiste à examiner la démonstration s’exécutent dans les Figure 1 et un graphique des données associées dans Figure 2. Le programme de démonstration définit des éléments de données factices 33. Chaque élément représente l’âge d’une personne, les dépenses de soins de santé et une classe arbitraire à prédire (0, 1, 2), que vous pouvez considérer comme Learning politique, pour concreteness. Les données ont uniquement deux variables de prédiction, par conséquent, il peut être affiché dans un graphique, mais k-NN fonctionne avec un nombre quelconque de PRÉDICTEURS.
.png "Exécution de démonstration de Classification k-NN pondérée")
Figure 1 pondérée d’exécution de démonstration de Classification k-NN
.png "Données de k-NN pondérée")
Figure 2 pondérée des données de k-NN
Les données a été normalisées. Lorsque vous utilisez k-NN, il est important de normaliser les données afin que les grandes valeurs, telles que des charges annuel de 30 000 $, ne soit inondée de petites valeurs, telles que l’ancienneté de 25. L’objectif de la démonstration est de prédire la classe d’une nouvelle personne a normalisé l’âge et les frais de (0,35, 0.38). La démonstration définit k = 6 et trouve les six éléments de données étiquetées sont le plus proche de l’élément à classer.
Après avoir identifié les six éléments le plus proche de données étiquetées, la démonstration utilise une technique de vote pondérée pour prendre une décision. Les valeurs pondérées votants pour les classes (0, 1, 2) sont (0.3879, 0.4911, 0.1209), par conséquent, l’élément au niveau (0,35, 0.38) est considéré comme la classe 1.
Cet article suppose que vous avez ou intermédiaire en programmation mieux les compétences avec C# ou un langage de famille C comme Python ou Java, mais ne suppose pas que vous connaissez un peu l’algorithme k-NN pondérée. Le code complet de démonstration et les données associées sont présentées dans cet article. Le code source et les données sont également disponibles dans le téléchargement qui accompagne cet article. Vérification d’erreur normale tous les a été supprimée pour garder les idées principales plus clair possible.
Présentation de l’algorithme k-NN pondérée
L’algorithme k-NN pondérée est la plus simple de toutes les techniques de ML, mais il existe quelques détails d’implémentation difficile. La première question que la plupart des développeurs ont est, « Comment déterminez-vous la valeur de k ? » La réponse quelque peu satisfaisante est que la valeur de k doit être déterminée par essais et erreurs.
Lorsque vous utilisez k-NN, vous devez calculer les distances à partir de l’élément à classer à toutes les données étiquetées. Il existe de nombreuses fonctions de distance, mais à l’aide de la distance EUCLIDIENNE est simple et efficace. La distance EUCLIDIENNE entre les deux éléments est la racine carrée de la somme des différences au carré de coordonnées. Par exemple, si un élément de données étiquetées est (0,20, 0,60) et est l’élément à classer (0,35, 0.38) puis :
dist = sqrt( (0.20 - 0.35)^2 + (0.60 - 0.38)^2 )
= sqrt(0.0225 + 0.0484)
= 0.2663
Après avoir computing tous les distances et recherche les distances k-le plus proche, vous devez utiliser un algorithme de vote pour déterminer la classe prévue. Il existe de nombreuses façons pour calculer une prédiction à partir des distances. Le programme de démonstration utilise les pondérations inverses technique, qu’il faut expliquée par exemple. Supposons que, comme dans la démonstration, les distances plus proche six existe (0.0728, 0.0781, 0.1118, 0.1217, 0.1300, 0.1414) et la mention associé classes sont (0, 1, 0, 1, 1, 2). Vous l’inverse de chaque distance de calcul, recherchez la somme des inverses, puis divisez chaque inverse par la somme. Pour la démonstration, inverses sont (13.7363, 12.8041, 8.9445, 8.2169, 7.6923, 7.0721). La somme des inverses est 58.4663. Diviser chaque distance inverse par la somme donne les poids : (0.2349, 0.2190, 0.1530, 0.1405, 0.1316, 0.1210).
Chaque poids est un vote pour sa classe associée. Dans la démonstration, le premier et troisième le plus proche éléments ont classe 0, par conséquent, le vote pour la classe 0 est la somme des poids des première et troisième : 0.2349 + 0.1530 = 0.3879. De même, le vote pour la classe 1 est 0.2190 + 0.1405 + 0.1316 = 0.4911. Et le vote pour la classe 2 est simplement le sixième poids 0.1210. La prédiction finale est la classe qui a le plus grand vote.
Le programme de démonstration
Le programme de démonstration complète, avec quelques modifications mineures à économiser de l’espace, est présenté dans Figure 3. Pour créer le programme, j’ai lancé Visual Studio et créé une nouvelle application console nommée WeightedKNN. J’ai utilisé Visual Studio 2017, mais la démonstration n’a aucune dépendance significative de .NET Framework.
Figure 3 le programme de démonstration de k-NN pondérée
using System;
namespace WeightedKNN
{
class WeightedKNNProgram
{
static void Main(string[] args)
{
Console.WriteLine("Begin weighted k-NN demo ");
Console.WriteLine("Normalized age-expenses data: ");
Console.WriteLine("[id = 0, 0.25, 0.43, class = 0]");
Console.WriteLine(" . . . ");
Console.WriteLine("[id = 32, 0.46, 0.22, class = 2]");
double[][] data = new double[33][];
data[0] = new double[] { 0, 0.25, 0.43, 0 };
data[1] = new double[] { 1, 0.26, 0.54, 0 };
data[2] = new double[] { 2, 0.27, 0.60, 0 };
data[3] = new double[] { 3, 0.37, 0.31, 0 };
data[4] = new double[] { 4, 0.38, 0.70, 0 };
data[5] = new double[] { 5, 0.49, 0.32, 0 };
data[6] = new double[] { 6, 0.46, 0.70, 0 };
data[7] = new double[] { 7, 0.55, 0.32, 0 };
data[8] = new double[] { 8, 0.58, 0.74, 0 };
data[9] = new double[] { 9, 0.67, 0.42, 0 };
data[10] = new double[] { 10, 0.69, 0.51, 0 };
data[11] = new double[] { 11, 0.66, 0.63, 0 };
data[12] = new double[] { 12, 0.29, 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.40, 1 };
data[16] = new double[] { 16, 0.48, 0.50, 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.68, 0.12, 1 };
data[22] = new double[] { 22, 0.78, 0.24, 1 };
data[23] = new double[] { 23, 0.86, 0.30, 1 };
data[24] = new double[] { 24, 0.86, 0.22, 1 };
data[25] = new double[] { 25, 0.86, 0.12, 1 };
data[26] = new double[] { 26, 0.78, 0.14, 1 };
data[27] = new double[] { 27, 0.28, 0.13, 2 };
data[28] = new double[] { 28, 0.25, 0.21, 2 };
data[29] = new double[] { 29, 0.39, 0.14, 2 };
data[30] = new double[] { 30, 0.37, 0.24, 2 };
data[31] = new double[] { 31, 0.45, 0.13, 2 };
data[32] = new double[] { 32, 0.46, 0.22, 2 };
double[] item = new double[] { 0.35, 0.38 };
Console.WriteLine("Nearest (k=6) to (0.35, 0.38):");
Analyze(item, data, 6, 3); // 3 classes
Console.WriteLine("End weighted k-NN demo ");
Console.ReadLine();
} // Main
// ------------------------------------------------------
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];
Show(data[idx]);
Console.WriteLine(" distance = " +
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("Weights (inverse technique): ");
for (int i = 0; i < wts.Length; ++i)
Console.Write(wts[i].ToString("F4") + " ");
Console.WriteLine("\n\nPredicted 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 perneighbor
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 void Show(double[] v)
{
Console.Write("idx = " + v[0].ToString().PadLeft(3) +
" (" + v[1].ToString("F2") + " " +
v[2].ToString("F2") + ") class = " + v[3]);
}
} // Program
} // ns
Une fois le code du modèle chargé, dans la fenêtre Éditeur j’ai supprimé toutes les références d’espace de noms inutiles, en laissant uniquement la référence à l’espace de noms système niveau supérieur. Dans la fenêtre Explorateur de solutions, j’ai cliqué sur le fichier Program.cs renommé ensuite le WeightedKNNProgram.cs plus descriptif et autorisé Visual Studio afin de renommer automatiquement la classe Program.
Par souci de simplicité, le programme de démonstration utilise une approche statique du code plutôt que d’une approche de programmation orientée objet. L’essentiel du travail est effectué dans la méthode d’analyse.
Le chargement de données en mémoire
La démonstration du programme code en dur les données factices et l’élément à classer :
double[][] data = new double[33][];
data[0] = new double[] { 0, 0.25, 0.43, 0 };
// Etc.
data[32] = new double[] { 32, 0.46, 0.22, 2 };
double[] item = new double[] { 0.35, 0.38 };
Dans un scénario non-demo, vous serez probablement stocker vos données dans un fichier texte ou d’une table SQL et écrire une méthode d’assistance pour charger les données dans une tableau de tableaux de style matrice. J’ai nommé les données en tant que simples « données », au lieu de quelque chose comme trainData, car les données utilisées par k-NN n’est pas vraiment utilisées pour former un modèle général.
La première valeur dans chaque élément de données est un code arbitraire. J’ai utilisé des entiers consécutifs à partir de zéro à 32 mais, dans de nombreux cas, vous devriez ID significatives, telles que les ID d’employé d’une personne. L’algorithme k-NN n’a pas besoin de données ID, donc la colonne ID aurait pu être omise. Les deuxième et troisième valeurs sont les valeurs predictor normalisée. La quatrième valeur est l’ID de classe. ID de classe pour k-NN ne doivent être des entiers de base zéro, mais à l’aide de ce schéma est pratique par programmation.
Calcul des Distances
La première étape de l’algorithme k-NN consiste à calculer la distance à partir de chaque élément de données étiquetées à l’élément d’être classé. Selon mon expérience et quelques résultats de recherche, le choix de la fonction de distance pour appliquer n’est pas aussi critique que vous pourriez penser, et la distance EUCLIDIENNE simple 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 est codé en dur avec 2 pour que le nombre de valeurs de prédiction et la différence entre l’élément [i] et le point de données [i + 1] est décalé vers le compte pour la valeur d’ID de données à la position [0]. L’idée ici est qu’il existe généralement un compromis entre un algorithme ML pour un problème spécifique de codage et de codage de l’algorithme avec une vue à l’utilisation à usage général. Étant donné que k-NN est donc simple et facile à implémenter, je préfère généralement l’approche de code pour les problème spécifique.
Au premier abord, l’exigence de l’informatique d’une fonction de distance semble imposer la restriction principale sur k-NN que toutes les variables de prédiction doivent être strictement numériques. Et, jusqu'à récemment cette idée est true, la plupart du temps. Toutefois, une des raisons de l’intérêt accru k-NN est qu’il est possible de k-NN à gérer les données non numériques et mixtes en utilisant l’encodage neuronaux des variables de prédiction.
En bref, l’idée est d’encoder des variables de prédiction à l’aide d’un autoencoder neuronal. Un autoencoder peut traiter des données non numériques à l’aide à chaud ou 1-of-(N-1) encodage. Un autoencoder prédit ses valeurs de sortie en fonction de ses valeurs d’entrée. La couche masquée centrale d’un autoencoder est une représentation complètement numérique des données non numériques et source.
Tri et classement les Distances
Une fois que tous les distances ont été calculés, l’algorithme k-NN doit rechercher les distances k-le plus proche (du plus petit). Une approche consiste à compléter l’ensemble étiqueté de jeu de données avec chaque valeur de distance, puis explicitement trier les données augmentées. Une autre approche, utilisée par la démonstration, consiste à utiliser une surcharge intéressante de la méthode .NET Array.Sort pour trier uniquement les distances et les index de données associées en parallèle. Le code de touche 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é classement initialement conserve 0, 1, 2. . 32. Une copie des 33 distances pour 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 dans le tableau distancesCopy du plus petit au plus grand à l’aide de l’algorithme de tri rapide et réorganise simultanément les valeurs d’index dans le tableau de classement. Le résultat est que la première valeur dans le classement du tableau est l’index pour les données de l’élément avec la plus petite distance, la deuxième valeur de classement conserve l’index de la distance le plus proche de seconde et ainsi de suite. Intéressant !
Détermination des pondérations de k-NN et vote
La forme plus primitif d’utilisation les distances k-le plus proche pour prédire une classe consiste à utiliser une approche de la règle majorité simple. Par exemple, si k = 4 et c = 3, deux des distances plus proche sont associés à la classe 2 et une distance le plus proche est associé à la classe 0 et une distance le plus proche est associé à la classe 1, puis une approche des règles de majorité prédit classe 2. Notez que pondérée k-NN à l’aide de pondérations uniformes, chacun avec la valeur 1/k, est équivalente à l’approche des règles majorité.
L’approche de règle de majorité présente deux problèmes importants : Tout d’abord, les liens sont possibles. Ensuite, tous les distances pondération égale. Le schéma de pondération courant pour k-NN pondérée doit s’appliquer l’approche de poids inverse utilisé par le programme de démonstration. Mais il existe plusieurs autres techniques. Par exemple, la technique de distances inverse additionne tous les distances, divise les distances par la somme, puis inverse l’ordre.
Une autre approche consiste à utiliser le rang des k-le plus proche de distances (1, 2... (6) au lieu des distances eux-mêmes. Pour k = 6, les pondérations des centroïdes de classement est calculées en tant que (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6) / 6 = 0.4083, (1/2 + 1/3 + 1/4 + 1/5 + 1/6) / 6 = 0.2417 et ainsi de suite.
Pour le programme de démonstration, l’inverse, uniforme, poids inverse et les centroïdes sont :
Inverse Uniform Reverse Centroids
---------------------------------------
0.2349 0.1667 0.2156 0.4083
0.2190 0.1667 0.1982 0.2417
0.1530 0.1667 0.1856 0.1583
0.1405 0.1667 0.1705 0.1028
0.1316 0.1667 0.1191 0.0611
0.1210 0.1667 0.1110 0.0278
Pour résumer
L’algorithme de classification k-NN pondérée a reçu récemment une attention accrue pour deux raisons. Tout d’abord, à l’aide d’autoencoding neuronal, k-NN peut gérer les mixte predictor non numériques et valeurs. En second lieu, les résultats de k-NN pondéré par rapport à d’autres algorithmes de classification, sont relativement faciles à interpréter. Ce problème est devenu plus en plus important en raison d’obligations légales de techniques machine Learning à partir de réglementations telles que l’Union européenne du RGPD.
Récupération d’urgence. James McCaffreytravaille pour Microsoft Research à Redmond, Wash. Il a travaillé sur plusieurs produits Microsoft clés dont Azure et Bing. Dr. James McCaffrey peut être contacté à jamccaff@microsoft.com.
Je remercie les experts techniques Microsoft suivants qui a examiné de cet article : Chris Lee, Ricky Loynd