Condividi tramite

Dicembre 2017

Volume 32 Numero 12

Il presente articolo è stato tradotto automaticamente.

Esecuzione dei test - Informazioni sulla classificazione k-NN con C#

Da James McCaffrey

James McCaffreyL'obiettivo di un problema di classificazione è utilizzare i valori di due o più variabili predittive (spesso chiamati funzionalità nella terminologia di machine learning [ML]) per stimare una classe (talvolta definita come un'etichetta). Potrebbe ad esempio, si desidera stimare il rischio di un server non riusciti (basso, medio o alto) in base a numero medio di richieste HTTP gestite e la temperatura fisica del server.

Sono disponibili numerose tecniche di classificazione ML, tra cui naïve Bayes classificazione, la classificazione di rete neurale e classificazione di albero delle decisioni. L'algoritmo k-più vicino adiacenti (k-NN) è un approccio relativamente semplice ed elegante. Rispetto ad altre tecniche, i vantaggi della classificazione k-NN sono semplicità e flessibilità. I due svantaggi principali sono k-NN non funziona bene con i valori non numerici predittive che non supporta la scalabilità per set di dati di grandi dimensioni.

Questo articolo spiega esattamente come classificazione k-NN funziona e presenta un programma demo end-to-end scritto in c#. Il modo migliore per vedere in questo articolo è a due punte è esaminare il programma demo in figura 1. Il problema demo consiste nello stimare la classe ("0", "1", "2") di un elemento che dispone di due variabili predittive con valori (5,25, 1,75). Se k (il numero di valori adiacente per esaminare) è impostato su 1, la classe prevista è "1". Se k è impostato su 4, la classe prevista è "2". Dietro le quinte, il programma demo utilizza un set di training gli elementi di dati per eseguire le stime 33.

Demo di classificazione utilizzando l'algoritmo k-NN
Figura 1 Demo di classificazione utilizzando l'algoritmo k-NN

Molte librerie ML dispongono di funzioni di classificazione di k-NN incorporati, ma le funzioni di libreria possono essere difficile o Impossibile (a causa di problemi legali) per integrare in un sistema di produzione. Informazioni sulle modalità di implementazione di classificazione k-NN da zero offre controllo completo e la possibilità di personalizzare il sistema.

Questo articolo si presuppone è migliore delle competenze di programmazione o intermedia, ma non si supponga che si conosca la classificazione k-NN. Il programma demo è codificato tramite c#, ma si dovrebbe essere troppo difficile refactoring del codice in un altro linguaggio, ad esempio Java o Python. Il programma demo è un po' troppo lungo per presentare nella sua interezza, ma il codice sorgente completo è disponibile nel download del file che accompagna questo articolo.

Comprendere l'algoritmo k-NN

Il grafico in figura 2 rappresenta i dati utilizzati nel programma dimostrativo. Sono disponibili 33 elementi di training. Ogni elemento dispone di due valori predittive x0 e x1. L'algoritmo k-NN può gestire i problemi con un numero qualsiasi di variabili predittive, ma la demo utilizza solo due, in modo che il problema è possibile visualizzare facilmente in un grafico.

Programma demo i dati di Training
Dati di Training programma Demo figura 2

I valori delle variabili predittive sono tutte comprese tra 0 e 9. Quando si esegue la classificazione k-NN, è importante normalizzare i valori predittive in modo che grandezze non sovraccaricare grandezze di piccole dimensioni. Ad esempio, si supponga reddito annuale di variabili predittive (ad esempio $48.000) e la validità (ad esempio, 32). È stato possibile normalizzare dividendo tutti i valori di reddito per 10.000 (che fornisce valori come 4.8) e dividendo tutti i valori di durata per 10 (che forniscono valori come 3.2). Due altre tecniche di normalizzazione comuni sono normalizzazione del punteggio z e normalizzazione min-max.

Molte tecniche di Machine Learning, incluse classificazione k-NN, richiedono i dati che sono noto di training, correggere predittive valori ed etichette di classe. I dati di training demo ha tre classi diverse, indicate da rosso, verde e giallo. Il colore blu del punto dati in (5,25, 1,75) è sconosciuto per la stima. Se k è impostato su 1, k-NN trova l'elemento di dati di training più vicino, singolo e restituisce la classe dell'elemento di dati più vicino come la classe prevista dell'elemento sconosciuto.

In questo esempio, per il (5,25, 1,75) unknown elemento dati di training, il più vicino è verde (classe = "1"): punti alla (6.0, 1.0) in modo la classe prevista è "1". Quando si usa k-NN, è necessario specificare come misurare la distanza tra gli elementi di dati che consente di definire cosa significa "più vicino". Il programma demo Usa la distanza euclidea. La distanza tra (5,25, 1,75) e (6.0, 1.0) è sqrt ((5.25-6.0) ^ 2 + (1,75 1.0) ^ 2) = sqrt (0.5625 + 0.5625) = sqrt(1.1250) = 1.061, come visualizzato figura 1.

Se k è impostato su 4, classe stimate dipende da quattro elementi di dati di training più vicino. Nell'esempio demo, sono i quattro elementi più vicini (6.0, 1.0), (5.0, 3.0), (4.0, 2.0) e (4.0, 1.0). La classe associata etichette per gli elementi sono ("1", "0", "2", "2"). Poiché sono presenti altre etichette "2" a "0" e "1" etichette, la classe prevista è "2".

Quando si utilizza k-NN, è necessario specificare la modalità determinare la classe stimata dal set delle etichette di classe KB più vicine. Il programma demo utilizza un approccio di maggioranza dei voti. Si noti che quando si utilizza un voto di maggioranza semplice, è possibile eseguire in situazioni di parità. In pratica, tuttavia, sono relativamente rari ties maggioranza dei voti k-NN. Il programma demo restituisce l'etichetta di classe più basso nel caso di valori equivalenti. Ad esempio, se le etichette associate sono ("2", "1", "1", "2"), quindi il programma demo voto meccanismo restituisce "1".

Il programma Demo

Per codificare il programma demo, avviato Visual Studio e creato un nuovo programma dell'applicazione di console in c# e denominato KNN. Si usa Visual Studio 2015, ma il programma demo non ha significative dipendenze di .NET Framework in modo da una versione recente di Visual Studio funziona correttamente.

Dopo che il codice del modello caricato nella finestra dell'editor, pulsante destro del mouse sul file Program.cs nella finestra Esplora soluzioni e rinominato il file in KNNProgram.cs, quindi Visual Studio rinominare automaticamente classe Program per me è consentito. Nella parte superiore del codice modello generato, è stato eliminato tutti non necessari tramite istruzioni, lasciando solo quella che fa riferimento il livello superiore dello spazio dei nomi System.

La struttura complessiva di programma, con poche modifiche secondarie per risparmiare spazio, viene visualizzata figura 3. Demo utilizza un approccio semplice metodo statico e tutti i normali errori è stato rimosso per mantenere i concetti principali non crittografato.

Figura 3 struttura generale del programma

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 dimostrazione inizia configurando i dati di training:

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

I dati sono hardcoded e archiviati in una matrice di matrice di matrici di stile. In uno scenario non demo è probabilmente necessario leggere i dati in memoria da un file di testo. Poiché la classificazione k-NN, tutti i dati di training vengono in genere archiviati in memoria, la tecnica non scala facilmente per scenari con grandi set di dati. Metodo LoadData è definita come segue:

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;
}

I primi due valori di ogni elemento sono i valori delle previsioni e l'ultimo valore è l'etichetta di classe. Una struttura alternativa comune consiste nell'archiviare predittive valori in una matrice, ma memorizzare le etichette di classe in una matrice separata. Il codice di esempio si presuppone che le etichette di classe sono di tipo numeriche e consecutivamente numero a partire da 0. Se le etichette di classe sono non numerico, ad esempio "bassa", "supporto" "alto", è necessario codificare i dati, in una fase di pre-elaborazione, o a livello di programmazione durante la lettura dei dati in memoria.

Successivamente, le demo imposta l'elemento sconosciuto per la stima, nel modo seguente:

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

Il programma demo in realtà non utilizza la variabile numFeatures, ma come si vedrà a breve, vi sono molti punti di personalizzazione possibile per la classificazione k-NN e un valore numFeatures può essere utile.

Successivamente, demo rende più semplice stima k-NN possibili:

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

Il metodo di classificazione accetta parametri per l'elemento per la stima, una matrice di dati di training, il numero di classi nei dati di training e il numero di vicini più prossimi da valutare. In generale, è possibile implementare il metodo di classificazione in modo che analizza i dati di training per determinare a livello di codice il numero di classi, ma lo sforzo richiesto supera il vantaggio, ritengo.

Il programma demo termina con:

...
  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();
}

Non vi sono eventuali regole buona per determinare il valore di k quando si utilizza la classificazione k-NN. Il valore di k nella classificazione k-NN è un hyperparameter e deve essere determinato dall'intuizione e sperimentazione.

Implementa l'algoritmo k-NN

In generale pseudo-codice, l'algoritmo di classificazione k-NN usata nella demo è:

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

Inizia la definizione di metodo di classificazione calcolando e l'archiviazione in una matrice le distanze tra l'elemento sconosciuto per classificare e tutti gli elementi di formazione, come illustrato nella figura 4.

Figura 4 definizione di classificare (metodo)

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;
  }
...

Non è sufficiente archiviare e ordinare solo la distanza tra l'elemento sconosciuto a ogni elemento di training, in quanto è necessario conoscere la classe associata a ogni distanza. Il programma demo definisce una classe contenitore semplice, denominata IndexAndDistance, che contiene un indice a un elemento di training e la distanza associata all'elemento sconosciuto:

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'etichetta di classe viene archiviata indirettamente in quanto se si conosce l'indice di un elemento di training, è possibile cercare l'etichetta di classe nella matrice di dati di training come ultima cella nella riga a cui punta dall'indice. Un progetto alternativo consiste nell'archiviare in modo esplicito l'etichetta di classe, ma l'indice dell'elemento di formazione di archiviazione offre una maggiore flessibilità. In alternativa è possibile archiviare in modo esplicito l'indice e l'etichetta di classe.

Perché è necessario ordinare gli elementi della distanza di indice per determinare gli elementi più vicino di k k-NN, la definizione di IndexAndDistance implementa l'interfaccia IComparable definendo un metodo CompareTo. In questo modo è possibile ordinare automaticamente una matrice di oggetti IndexAndDistance. Se il refactoring del codice di demo un linguaggio di programmazione che non supporta l'ordinamento automatico, si deve implementare un metodo di ordinamento personalizzato che opera su una struttura oppure implementare un metodo di ordinamento personalizzato che funziona con matrici parallele.

Sono disponibili alcune alternative per gli elementi della distanza di indice di ordinamento, ad esempio, utilizzando una struttura di dati di heap, ma ritengo la maggiore complessità superiore qualsiasi miglioramento delle prestazioni, si otterrebbe.

Una volta archiviate tutte le voci di indice distanza di training, l'ordinamento in base e vengono visualizzate informazioni per gli elementi di KB più vicino:

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'etichetta di classe c, viene estratto da [2] di cella di una riga di dati di training. Ciò presuppone che esistano due variabili predittive. Un approccio di livello superiore potrebbe essere per passare un argomento numFeatures al metodo di classificazione, quindi accedere cella [numFeatures].

La visualizzazione di informazioni sugli elementi di formazione di KB più vicino è facoltativa, ma illustra un vantaggio della classificazione k-NN rispetto a numerose altre tecniche. L'algoritmo k-NN è piuttosto interpretabile nel senso che è possibile determinare esattamente come sono stato classificato un elemento sconosciuto. Alcune tecniche, una classificazione di rete neurale in particolare, sono difficili o impossibili da interpretare.

Il metodo di classificazione conclude analizzando gli elementi di formazione di KB più vicino per determinare una classe stimata per l'elemento sconosciuto:

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

Il metodo di supporto voto accetta la matrice di tutti gli elementi della distanza di indice. Un approccio alternativo consiste nel passare solo le celle k prima della matrice.

Distanza e voto

Il metodo di classificazione chiama i metodi di supporto, distanza e fornire un voto. Metodo distanza è definita come segue:

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

Si tratta di un'implementazione semplice di distanza euclidea. Alternative comuni, che è possibile includono distanza di Manhattan, Mahalanobis distanza e le misure basate sui somiglianza, ad esempio il kernel funzione radiale di base. Perché k-NN necessita di una nozione di "più vicino" e la maggior parte delle metriche di distanza lavorare con dati numerici rigorosamente o rigorosamente non numerico, non è ideale per i problemi con tipi di dati numerici e per categoria classificazione k-NN.

Metodo helper voto verrà presentato in figura 5. Determinare un'etichetta di classe consenso dagli elementi k è leggermente più complessi rispetto a cui si può immaginare. La dimostrazione utilizza l'approccio più semplice, in cui ciascuno degli elementi più vicino di k training Ottiene un voto per la relativa etichetta di classe. Questo approccio non prende in considerazione la distanza. Un'alternativa comune è voti peso di distanza in modo che gli elementi di training più vicino all'elemento sconosciuto avere maggiore influenza.

Figura 5, il metodo di voto

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'implementazione di demo non riguarda in modo esplicito con gli elementi di dati di training duplicati. Quantità di dati reali non dispone di una quantità eccessiva di dati duplicati, ma se i dati di training includono un numero elevato di duplicati, è consigliabile rimuoverli.

Conclusioni

L'algoritmo di classificazione k-NN è probabilmente una delle più semplici di tutte le tecniche di machine learning. Oltre a motivi di semplicità, classificazione k-NN può facilmente risolvere i problemi di multi-class (a differenza di alcune tecniche che funzionano con facilità solo per la classificazione binaria). Un altro vantaggio è che k-NN è possibile gestire facilmente con i dati con caratteristiche insolite, ad esempio i dati dimostrativo fittizio che ha diversi gruppi di etichette di classe. Alcune tecniche, ad esempio la regressione logistica e non kernel macchine a vettori di supporto consente di gestire solo con dati separabili in modo lineare. Due altri vantaggi offerti dalle classificazione k-NN sono la flessibilità di implementazione e interpretazione dei risultati.

Il lato negativo classificazione k-NN non funziona bene con dati categorici o tipi di dati numerici e per categoria. La tecnica non è facilmente scalabile per set di dati di grandi dimensioni. E classificazione k-NN è altamente sensibile alla geometria locale dei dati di training.

Quando si dispone di un problema di classificazione con valori di predittive esclusivamente numerico e un set non enorme di dati di training (ad esempio, gli elementi meno di un milione), k-NN è spesso utilizzare il primo approccio. Quindi tento tecniche più sofisticate, tra cui in genere di classificazione di rete neurale. In alcuni casi, un approccio di insieme che combina i risultati di classificazione k-NN con la classificazione di rete neurale può provocare un sistema di stima molto accurati.

Ripristino di emergenza. James McCaffreyfunziona per Microsoft Research Redmond, WA Ha lavorato su diversi prodotti Microsoft, tra cui Internet Explorer e Bing. Dr. McCaffrey può essere raggiunto al jamccaff@microsoft.com.

Grazie per i seguenti esperti Microsoft che ha revisionato in questo articolo: Chris Lee, Ricky Loynd, Davide Tran

Viene illustrato in questo articolo nel forum di MSDN Magazine