Partager via

Décembre 2017

Volume 32, numéro 12

Cet article a fait l'objet d'une traduction automatique.

Série de tests - Présentation de la classification k-NN à l’aide de C#

Par James McCaffrey

James McCaffreyL’objectif d’un problème de classification est d’utiliser les valeurs de deux ou plusieurs variables de prédiction (souvent appelés de fonctionnalités dans la terminologie de machine learning (ML)) pour prédire une classe (parfois appelée une étiquette). Par exemple, vous pouvez souhaiter prédire le risque d’un serveur de basculement (faible, moyenne ou élevée) basé sur le nombre moyen de demandes HTTP traitées et la température physique du serveur.

Il existe de nombreuses techniques de classification ML, y compris la classification de naïve Bayes, la classification de réseau neuronal et classification d’arbre de décision. L’algorithme k-le plus proche voisin (k-NN) est une approche relativement simple et élégante. Par rapport à d’autres techniques, les avantages de la classification de k-NN sont plus de simplicité et souplesse. Les deux inconvénients principaux sont que k-NN ne fonctionne pas correctement avec les valeurs non numériques PRÉDICTEUR, et il n’évolue pas bien à des jeux de données volumineux.

Cet article explique exactement comment classification de k-NN fonctionne et présente un programme de démonstration de bout en bout écrit en c#. La meilleure façon de voir où cet article est menée consiste à examiner le programme de démonstration dans Figure 1. Le problème de démonstration est de prédire la classe (« 0 », « 1 », « 2 ») d’un élément qui a deux variables de prédiction avec des valeurs (5,25, 1,75). Si k (le nombre de valeurs de voisin pour examiner) est définie sur 1, la classe prédite est « 1 ». Si k est défini à 4, la classe prédite est « 2 ». En arrière-plan, le programme de démonstration utilise un ensemble de 33 formation des éléments de données pour rendre les prédictions.

Démonstration de classification à l’aide de l’algorithme k-NN
Démonstration de Classification de la figure 1 à l’aide de l’algorithme k-NN

De nombreuses bibliothèques ML ont des fonctions de classification de k-NN intégrées, mais les fonctions de bibliothèque peuvent être difficile, voire impossible (en raison de problèmes juridiques) pour intégrer un système de production. Comprendre comment implémenter la classification de k-NN à partir de zéro vous donne un contrôle total et la possibilité de personnaliser votre système.

Cet article suppose que vous avez intermédiaires ou meilleures compétences de programmation, mais ne suppose pas que vous savez rien à la classification de k-NN. Le programme de démonstration est codé à l’aide de c#, mais vous ne rencontrez trop de refactorisation du code à un autre langage, comme Java ou Python. Le programme de démonstration est un peu trop long pour être affichée dans son intégralité, mais le code source complet est disponible dans le téléchargement du fichier qui accompagne cet article.

Présentation de l’algorithme k-NN

Graphique de Figure 2 représente les données utilisées dans le programme de démonstration. Il existe des éléments de formation 33. Chaque élément a deux valeurs PRÉDICTEUR, x0 et x1. L’algorithme k-NN peut gérer des problèmes avec un nombre quelconque de PRÉDICTEURS, mais la démonstration utilise deux afin que le problème peut être visualisé facilement dans un graphique.

Données d’apprentissage de programme de démonstration
Données de formation du programme de démonstration figure 2

Les valeurs des variables PRÉDICTEUR sont toutes comprises entre 0 et 9. Lorsque vous effectuez la classification de k-NN, il est important de normaliser les valeurs PRÉDICTEUR afin que des grandeurs importantes ne pas surcharger petites amplitudes. Par exemple, supposons que vous avez PRÉDICTEUR variables annuel (par exemple, $48,000) et l’âge (par exemple, 32). Possible de normaliser en divisant toutes les valeurs de revenu par 10 000 (valeurs donnant comme 4.8) et en divisant toutes les valeurs de durée de vie par 10 (donnant une valeur comme 3.2). Deux autres techniques de normalisation courantes sont la normalisation z-score et normalisation min-max.

Nombreuses techniques ML, y compris la classification de k-NN, nécessitent des données a connu d’apprentissage, corriger les valeurs de prévision et les étiquettes de classe. Les données d’apprentissage démonstration ont trois classes différentes, indiqués en rouge, vert et jaune. Au niveau du point de données bleues (5,25, 1,75) est l’inconnu à prédire. Lorsque k est définie sur 1, k-NN recherche l’élément de données unique, le plus proche de formation et retourne la classe de cet élément de données le plus proche en tant que la classe prévue de l’élément inconnu.

Dans cet exemple, pour le (5,25, 1,75) inconnu à un élément de données d’apprentissage, le plus proche est le vert (classe = « 1 ») à un point (6.0, 1.0) afin de la classe prédite est « 1 ». Lorsque vous utilisez k-NN, vous devez spécifier comment mesurer la distance entre des éléments de données permettant de définir ce que signifie « le plus proche ». Le programme de démonstration utilise la distance EUCLIDIENNE. La distance entre (5,25, 1,75) et (6.0, 1.0) est sqrt ((5.25-6.0) ^ 2 + (1,75 1.0) ^ 2) = sqrt (0.5625 + 0.5625) = sqrt(1.1250) = 1.061, tel qu’affiché dans Figure 1.

Lorsque k est défini à 4, la classe prédite varie selon les quatre éléments de données de formation le plus proche. Dans l’exemple de démonstration, les quatre éléments les plus proches sont à (6.0, 1.0), (5.0, 3.0), (4.0, version 2.0) et (4.0, 1.0). Pour les éléments sont des étiquettes de la classe associée (« 1 », « 0 », « 2 », « 2 »). Étant donné que plusieurs libellés « 2 » à « 0 » et « 1 », la classe prédite est « 2 ».

Lors de l’utilisation vous devez spécifier la façon de déterminer la classe prévue de l’ensemble des étiquettes de classe Ko le plus proche de k-NN. Le programme de démonstration utilise une approche de la majorité des voix. Notez que lors de l’utilisation d’une majorité simple, vous pouvez exécuter en cas d’égalité. Toutefois, dans la pratique, ties de majorité k-NN sont relativement rares. Le programme de démonstration retourne l’étiquette la plus basse de la classe en cas de liens. Par exemple, si les étiquettes associées sont (« 2 », « 1 », « 1 », « 2 »), puis le programme de démonstration vote mécanisme retourne « 1 ».

Le programme de démonstration

Pour coder le programme de démonstration, je lancé Visual Studio a créé un programme d’application de console c# et nommé KNN. J’ai utilisé Visual Studio 2015, mais le programme de démonstration n’a aucune dépendance de .NET Framework significatif pour n’importe quelle version récente de Visual Studio fonctionne correctement.

Une fois le code du modèle chargé dans la fenêtre d’éditeur, je cliqué sur le fichier Program.cs dans la fenêtre de l’Explorateur de solutions et renommé le fichier KNNProgram.cs, puis autorisé Visual Studio afin de renommer automatiquement la classe Program pour moi. En haut du code de modèle généré, j’ai supprimé tout inutiles à l’aide d’instructions, en laissant le seul qui fait référence à l’espace de noms système niveau supérieur.

La structure générale du programme, avec quelques modifications mineures pour économiser l’espace, est présentée dans Figure 3. La démonstration utilise une approche simple de méthode statique, et vérification de toutes les erreurs normalement a été supprimé pour garder les idées principales clair.

Figure 3 Structure générale du programme

using System;
namespace KNN
{
  class KNNProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin k-NN classification demo ");
      double[][] trainData = LoadData();
      int numFeatures = 2;
      int numClasses = 3;
      double[] unknown = new double[] { 5.25, 1.75 };
      Console.WriteLine("Predictor values: 5.25 1.75 ");
      int k = 1;
      Console.WriteLine("With k = 1");
      int predicted = Classify(unknown, trainData,
        numClasses, k);
      Console.WriteLine("Predicted class = " + predicted);
      k = 4;
      Console.WriteLine("With k = 4");
      predicted = Classify(unknown, trainData,
        numClasses, k);
      Console.WriteLine("Predicted class = " + predicted);
      Console.WriteLine("End k-NN demo ");
      Console.ReadLine();
    }
    static int Classify(double[] unknown,
      double[][] trainData, int numClasses, int k) { . . }
    static int Vote(IndexAndDistance[] info,
      double[][] trainData, int numClasses, int k) { . . }
    static double Distance(double[] unknown,
      double[] data) { . . }
    static double[][] LoadData() { . . }
  } // Program class
  public class IndexAndDistance : IComparable<IndexAndDistance>
  {
    public int idx;  // Index of a training item
    public double dist;  // To unknown
    // Need to sort these to find k closest
    public int CompareTo(IndexAndDistance other)
    {
      if (this.dist < other.dist) return -1;
      else if (this.dist > other.dist) return +1;
      else return 0;
    }
  }
} // ns

La démonstration commence en définissant les données d’apprentissage :

static void Main(string[] args)
{
  Console.WriteLine(“Begin k-NN classification demo “);
  double[][] trainData = LoadData();
...

Les données sont codé en dur et stockée dans une matrice de style tableau de tableaux. Dans un scénario non-demo vous serez probablement lire les données en mémoire à partir d’un fichier texte. Étant donné que la classification de k-NN stocke habituellement toutes les données d’apprentissage en mémoire, la technique n’évolue pas facilement à des scénarios avec des jeux de données très volumineux. Méthode LoadData est défini comme :

static double[][] LoadData()
{
  double[][] data = new double[33][];
  data[0] = new double[] { 2.0, 4.0, 0 };
    ...
  data[12] = new double[] { 3.0, 4.0, 1 };
    ...
  data[32] = new double[] { 4.0, 2.0, 2 };
  return data;
}

Les deux premières valeurs de chaque élément sont les valeurs de prévision et la dernière valeur est l’étiquette de classe. Une autre conception commune consiste à stocke des valeurs de prédiction dans une matrice, mais les étiquettes de classe dans un tableau distinct. Le code de démonstration suppose que les étiquettes de classe sont numériques et numérotées à partir de 0. Si vos étiquettes de classe sont non numériques, telles que « bas », « moyenne, » « high », vous devez encoder les données, dans une étape de prétraitement, ou par programme lors de la lecture des données en mémoire.

Ensuite, les jeux de démonstration, l’élément inconnu à prédire, comme suit :

int numFeatures = 2;
int numClasses = 3;
double[] unknown = new double[] { 5.25, 1.75 };
Console.WriteLine("Predictor values: 5.25 1.75 ");

La variable numFeatures réellement n’utilise pas le programme de démonstration, mais comme vous le verrez, il existe de nombreux points de personnalisation possibles pour la classification de k-NN, et une valeur numFeatures peut être utile.

Ensuite, la démonstration rend la prédiction la plus simple de k-NN possibles :

int k = 1;
Console.WriteLine("With k = 1");
int predicted = Classify(unknown, trainData,
  numClasses, k);
Console.WriteLine("Predicted class = " + predicted);

La méthode de classification accepte des paramètres pour l’élément à prédire, une matrice de données d’apprentissage, le nombre de classes dans les données d’apprentissage et le nombre de voisins les plus proches à évaluer. En principe, vous pouvez implémenter la méthode classifier afin qu’il analyse les données d’apprentissage pour déterminer par programme le nombre de classes, mais l’effort compense l’avantage, à mon avis.

Le programme de démonstration se termine par :

...
  k = 4;
  Console.WriteLine(“With k = 4”);
  predicted = Classify(unknown, trainData,
    numClasses, k);
  Console.WriteLine(“Predicted class = “ + predicted);
  Console.WriteLine(“End k-NN demo “);
  Console.ReadLine();
}

Il n’existe pas de toutes les règles empirique pour déterminer la valeur de k lors de l’utilisation de classification de k-NN. La valeur de k de classification de k-NN est un hyperparameter et doit être déterminée par intuition et d’expérimentation.

L’algorithme k-NN

Dans le pseudo-code niveau très élevé, l’algorithme de classification de k-NN utilisé par la démonstration est :

Compute distances from unknown to all training items
Sort the distances from nearest to farthest
Scan the k-nearest items; use a vote to determine the result

La définition de méthode classifier commence par le calcul et le stockage dans un tableau les distances entre l’élément inconnu pour classer et tous les éléments de formation, comme indiqué dans Figure 4.

Figure 4 définition de la méthode de classification

static int Classify(double[] unknown,
  double[][] trainData, int numClasses, int k)
{
  int n = trainData.Length;
  IndexAndDistance[] info = new IndexAndDistance[n];
  for (int i = 0; i < n; ++i) {
    IndexAndDistance curr = new IndexAndDistance();
    double dist = Distance(unknown, trainData[i]);
    curr.idx = i;
    curr.dist = dist;
    info[i] = curr;
  }
...

Il n’est pas suffisant pour stocker et trier seulement les distances à partir de l’élément inconnu à chaque élément de la formation, car vous devez connaître la classe associée à chaque distance. Le programme de démonstration définit une classe de conteneur simple nommée IndexAndDistance, qui contient un index à un élément de formation et de la distance associée à l’élément inconnu :

public class IndexAndDistance : IComparable<IndexAndDistance>
{
  public int idx;  // index of a training item
  public double dist;  // distance to unknown
  public int CompareTo(IndexAndDistance other) {
    if (this.dist < other.dist) return -1;
    else if (this.dist > other.dist) return +1;
    else return 0;
  }
}

L’étiquette de classe est stockée indirectement, car si vous connaissez l’index d’un élément de formation, vous pouvez rechercher l’étiquette de classe dans la matrice de données d’apprentissage comme la dernière cellule de la ligne désignée par l’index. Une autre conception consiste à stocker l’étiquette de classe explicitement, mais le stockage de l’index de l’élément d’apprentissage offre plus de souplesse. Une autre solution consiste à stocker explicitement l’index et l’étiquette de classe.

Étant donné que k-NN doit trier les éléments de la distance de l’index pour déterminer les éléments k-le plus proche, la définition de IndexAndDistance implémente l’interface IComparable en définissant une méthode CompareTo. Cela permet de trier automatiquement un tableau d’objets de IndexAndDistance. Si vous refactorisez le code de démonstration pour un langage de programmation qui ne prennent en charge le tri automatique, vous devez posséder pour implémenter une méthode de tri personnalisé qui opère sur une structure ou implémentez une méthode de tri personnalisé qui fonctionne avec des tableaux parallèles.

Il existe quelques solutions à des éléments de la distance de l’index de tri, par exemple, à l’aide d’une structure de données du segment de mémoire, mais dans mon avis sur la complexité accrue compense toute amélioration des performances que vous pourriez obtenir.

Une fois que tous les éléments de distance de l’index d’apprentissage sont stockées, elles sont triées, et informations pour les éléments de k-le plus proche s’affiche :

Array.Sort(info);  // sort by distance
Console.WriteLine("Nearest / Distance / Class");
Console.WriteLine("==========================");
for (int i = 0; i < k; ++i) {
  int c = (int)trainData[info[i].idx][2];
  string dist = info[i].dist.ToString("F3");
  Console.WriteLine("( " + trainData[info[i].idx][0] +
    "," + trainData[info[i].idx][1] + " )  :  " +
    dist + "        " + c);
}

L’étiquette de classe c, est extraites de la cellule d’une ligne de données d’apprentissage de [2]. Cela suppose il existe deux variables de prédiction. Une meilleure approche serait pour passer un argument de numFeatures à la méthode de classification, puis accéder à la cellule [numFeatures].

Affichage d’informations sur les éléments de la formation de k-le plus proche est facultative, mais il illustre le des avantages de la classification de k-NN par rapport à nombreuses autres techniques. L’algorithme k-NN est quelque peu interprétable en ce sens que vous pouvez déterminer exactement comment un élément inconnu a été classé. Certaines techniques, la classification de réseau neuronal notamment, sont difficiles ou impossibles à interpréter.

La méthode de classification conclut en analysant les éléments de formation k-le plus proche pour déterminer une classe prévue pour l’élément inconnu :

...
  int result = Vote(info, trainData, numClasses, k);
  return result;
} // Classify

Méthode d’assistance Vote accepte le tableau de tous les éléments de la distance de l’index. Une autre approche consiste à passer uniquement les cellules k première du tableau.

Distance et vote

La méthode de classification appelle les méthodes d’assistance Distance et votez. Distance de la méthode est définie comme :

static double Distance(double[] unknown, double[] data)
{
  double sum = 0.0;
  for (int i = 0; i < unknown.Length; ++i)
    sum += (unknown[i] - data[i]) * (unknown[i] - data[i]);
  return Math.Sqrt(sum);
}

Il s’agit d’une implémentation simple de distance EUCLIDIENNE. Alternatives courantes que vous pouvez envisager d’incluent distance de Manhattan, Mahalanobis distance et les mesures en fonction de similarité, tels que le noyau de la fonction base radial. K-NN nécessite une notion de « le plus proche » et la plupart des mesures de distance utiliser strictement strictement non numériques ou des données, classification de k-NN n’est pas adaptée pour les problèmes avec les données numériques et par catégorie mixtes.

Méthode d’assistance Vote est présenté dans Figure 5. Détermination d’une étiquette de classe consensus à partir d’éléments de k est un peu plus complexe que vous pouvez deviner. La démonstration utilise l’approche la plus simple, où chacun des éléments de formation plus proche de k Obtient un vote pour son étiquette de classe. Cette approche ne prend pas en compte la distance. Une alternative courante consiste aux votes de poids à distance afin que les éléments de formation qui sont plus proches de l’élément inconnu ont plus d’influence.

La figure 5, la méthode de Vote

static int Vote(IndexAndDistance[] info, double[][] trainData,
  int numClasses, int k)
{
  int[] votes = new int[numClasses];  // One cell per class
  for (int i = 0; i < k; ++i) {       // Just first k
    int idx = info[i].idx;            // Which train item
    int c = (int)trainData[idx][2];   // Class in last cell
    ++votes[c];
  }
  int mostVotes = 0;
  int classWithMostVotes = 0;
  for (int j = 0; j < numClasses; ++j) {
    if (votes[j] > mostVotes) {
      mostVotes = votes[j];
      classWithMostVotes = j;
    }
  }
  return classWithMostVotes;
}

L’implémentation de démonstration ne traite explicitement les éléments de données d’apprentissage en double. Quantité de données réelles n’a pas une quantité excessive de données en double, mais si vos données d’apprentissage incluent un grand nombre de doublons, vous souhaiterez peut-être envisager de les supprimer.

Pour résumer

L’algorithme de classification k-NN est sans doute un des plus simples de toutes les techniques d’apprentissage automatique. En plus de simplicité, la classification de k-NN peut facilement résoudre les problèmes de multi-class (par opposition à certaines techniques de travailler facilement uniquement pour la classification binaire). Un autre avantage est que k-NN peut facilement traiter les données présentant des caractéristiques inhabituelles, telles que les données de démonstration fictif qui a plusieurs poches d’étiquettes de classe. Certaines techniques, telles que la régression logistique et non le noyau prend en charge les machines à vecteurs, peuvent traiter uniquement avec les données qui sont séparables de façon linéaire. Deux autres avantages de la classification de k-NN sont souplesse d’implémentation et l’interopérabilité des résultats.

Dans la partie négative, classification de k-NN ne fonctionne pas correctement avec les données catégoriques ou mixte numérique et par catégorie. La technique n’évolue pas bien à des jeux de données volumineux. Et la classification de k-NN est très sensible à la géométrie locale des données d’apprentissage.

Lorsque j’ai un problème de classification avec des valeurs numériques strictement PRÉDICTEUR et un ensemble non considérable de données d’apprentissage (par exemple, les éléments d’un million), à l’aide de k-NN est souvent ma première approche. Ensuite, je vais essayer des techniques plus sophistiquées, en général, y compris la classification de réseau neuronal. Dans certaines situations, une approche d’ensemble qui combine les résultats de la classification de k-NN avec la classification de réseau neuronal peut conduire à un système de prédiction très robuste et plus précis.

Récupération d’urgence. James McCaffreyfonctionne pour Microsoft Research à Redmond, Washington Il a travaillé sur plusieurs produits Microsoft, y compris Internet Explorer et Bing. Dr. McCaffrey peut être atteint à jamccaff@microsoft.com.

Grâce aux experts techniques Microsoft suivants ayant révisé cet article : Chris Lee, Ricky Loynd, Ken Tran

Discussion sur cet article sur le forum MSDN Magazine