Maggio 2019
Volume 34 Numero 5
[Test Run]
Classificazione k-NN ponderata con C#
Dal James McCaffrey
.jpg "James McCaffrey")
L'obiettivo di un problema di classificazione (ML) di apprendimento è stimare un valore discreto. Potrebbe, ad esempio, si desidera stimare il Learning politico (conservativo, moderato, libero) di una persona in base al loro age, annuale spese sanitarie, sesso, anni della formazione e così via. Sono disponibili molte tecniche di classificazione diversi, tra cui reti neurali e alberi delle decisioni la regressione logistica. In questo articolo illustrato come implementare l'algoritmo ponderato più vicino di k gruppi adiacenti, usando il C# linguaggio.
Il modo migliore per comprendere futuro in questo articolo è Esaminiamo la demo eseguite nelle figura 1 e un grafico dei dati associati nella Figura2. Il programma demo imposta 33 elementi di dati fittizio. Ogni elemento rappresenta età della persona, annuale spese sanitarie e una classe arbitraria da stimare (0, 1, 2), che è possibile considerare come Learning politici, per concreteness. I dati hanno solo due variabili di predittore quindi può essere visualizzato in un grafico, ma funziona k-NN con un numero qualsiasi di predittori.
.png "Esecuzione di Demo classificazione k-NN ponderato")
Figura 1 ponderati esecuzione Demo di classificazione k-NN
.png "Dati k-NN ponderato")
Figura 2 ponderati dati k-NN
I dati normalizzati. Quando si usa k-NN, è importante normalizzare i dati in modo che i valori di grandi dimensioni, ad esempio un costo annua di 30.000 euro, non sovraccaricare i valori di piccole dimensioni, ad esempio un'età di 25 caratteri. L'obiettivo della demo consiste nello stimare la classe di una nuova persona che ha normalizzato l'età e le spese legate (0.35, 0.38). La demo imposta k = 6 e rileva le sei elementi dati con etichetta vicini per l'elemento-a-classificare.
Dopo aver individuato i sei elementi dati con etichetta più vicino, la demo Usa una tecnica di voto ponderata per prendere una decisione. I valori di voti ponderati per le classi (0, 1, 2) sono (0.3879, 0.4911, 0.1209), pertanto l'elemento in corrispondenza (0.35, 0.38) è classificato come classe 1.
Questo articolo si presuppone intermedio o programmazione meglio le competenze con C# o un linguaggio C-famiglia, ad esempio Python o Java, ma non si conosce l'algoritmo k-NN ponderato. Il codice completo demo e i dati associati vengono presentati in questo articolo. Il codice sorgente e i dati sono disponibili anche nel download associato. Controllo degli errori è stata rimossa per mantenere le idee principali più chiare possibili.
Comprendere l'algoritmo k-NN ponderato
L'algoritmo k-NN pesata è una delle più semplici di tutte le tecniche di Machine Learning, ma esistono alcuni dettagli di implementazione complessa. La prima domanda hanno maggior parte degli sviluppatori è: "Come si determina il valore di k?" La risposta in qualche modo soddisfacente è che il valore di k deve essere determinato dalla versione di valutazione ed errori.
Quando si usa k-NN, è necessario calcolare la distanza tra l'elemento-a-classificare a tutti i dati con etichette. Sono disponibili molte funzioni di distanza, ma con la distanza euclidea è semplice ed efficace. La distanza euclidea tra i due elementi è la radice quadrata della somma dei quadrati delle differenze di coordinate. Ad esempio, se è un elemento di dati con etichetta (0,20, 0,60) ed è l'elemento da classificare (0.35, 0.38) quindi:
dist = sqrt( (0.20 - 0.35)^2 + (0.60 - 0.38)^2 )
= sqrt(0.0225 + 0.0484)
= 0.2663
Dopo aver computing tutte le distanze e trovare le distanze più vicino di k, è necessario utilizzare un algoritmo di voto per determinare la classe stimata. Esistono diversi modi per calcolare una stima da distanze. Il programma demo utilizza i pesi inversi tecnica, che può essere spiegato dall'esempio. Si supponga che, come la demo, le distanze più vicine sei sono (0.0728, 0.0781, 0.1118, 0.1217, 0.1300, 0.1414) e associato con l'etichetta classi sono (0, 1, 0, 1, 1, 2). L'inverso di ogni distanza di calcolo, trovare la somma dell'inverte, quindi dividere la somma di ogni operazione inversa. Per la demo, l'inverte sono (13.7363, 12.8041, 8.9445, 8.2169, 7.6923, 7.0721). La somma dell'inverte è 58.4663. Dividendo la somma di ogni distanza inverso consente i pesi: (0.2349, 0.2190, 0.1530, 0.1405, 0.1316, 0.1210).
Ogni peso è un voto per la classe associata. Nella demo, il primo e più vicino terzo elemento hanno classe 0, in modo che il voto per la classe 0 è la somma dei pesi primi e la terzi: 0.2349 + 0.1530 = 0.3879. Analogamente, il voto per la classe 1 è 0.2190 + 0.1405 + 0.1316 = 0.4911. E il voto per la classe 2 è semplicemente il sesto peso, 0.1210. La stima finale è la classe che ha il voto di più grande.
Il programma Demo
Il programma di dimostrazione completo, con alcune modifiche di lieve entità per risparmiare spazio, viene presentato nel figura 3. Per creare il programma, avviato Visual Studio e creato una nuova applicazione console denominata WeightedKNN. Ho utilizzato Visual Studio 2017, ma la demo non ha alcuna dipendenza di .NET Framework significativo.
Figura 3, il programma Demo ponderata k-NN
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
Dopo aver caricato il codice del modello, nella finestra dell'editor rimosso tutti i riferimenti di spazio dei nomi non necessari, lasciando solo il riferimento allo spazio dei nomi di sistema principale. Nella finestra Esplora soluzioni, pulsante destro del mouse sul file Program.cs, rinominato il WeightedKNNProgram.cs più descrittivo e Visual Studio di ridenominazione automatica della classe Program è consentito.
Per semplicità, il programma demo utilizza un approccio statica del codice anziché un approccio di programmazione orientata agli oggetti. La maggior parte delle operazioni viene eseguita nel metodo di analisi.
Il caricamento dei dati in memoria
La demo programma imposta i dati fittizi e l'elemento-a-classificare:
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 };
In uno scenario non-demo, si sarebbe probabilmente archiviano i dati in un file di testo o una tabella SQL e scrivere un metodo helper per caricare i dati in una matrice di matrice di matrici di stile. Denominato i dati come semplicemente "data", invece di un elemento, ad esempio trainData perché i dati utilizzati dalle k-NN davvero non viene usati per eseguire il training di un modello generale.
Il primo valore in ogni elemento di dati è un ID arbitrario. Ho utilizzato valori interi consecutivi compreso tra zero e 32, ma in molti casi, si avranno un ID significativo, ad esempio il numero di ID dipendente di una persona. L'algoritmo k-NN non richiede dati gli ID, in modo che la colonna ID è stato omesso. I valori secondo e terzi sono i valori normalizzati predittore. Il quarto valore è l'ID di classe. ID di classe per k-NN non devono essere numeri interi in base zero, ma con questo schema è pratico a livello di codice.
Computing distanze
Il primo passaggio per l'algoritmo k-NN è per calcolare la distanza tra ogni elemento di dati con etichetta e l'elemento-a-essere classificati. La scelta della funzione di distanza per applicare base alcuni risultati di ricerca e la mia esperienza, non è importante quanto si possa pensare, e la distanza euclidea semplice in genere funziona bene.
L'implementazione di demo di distanza euclidea è:
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);
}
Si noti che l'indicizzazione del ciclo for è hardcoded con 2 per il numero di valori di predittore e la differenza tra l'elemento [i] e dataPoint [i+1] offset all'account per il valore di ID dei dati nella posizione [0]. Il concetto è che si verifica generalmente un compromesso tra la codifica di un algoritmo di Machine Learning per un problema specifico e l'algoritmo con una visualizzazione per utilizzo generico di codifica. Poiché k-NN è molto semplice e facile da implementare, è preferibile in genere l'approccio di codice per specifiche del problema.
Al primo acchito, sembra che il requisito di elaborazione di una funzione di distanza per imporre le principali restrizioni in k-NN che tutte le variabili di predittore devono essere rigorosamente numeriche. E fino a poco questo concetto è stato impostato su true, per la maggior parte. Tuttavia, uno dei motivi per l'interesse dimostrato un aumento in k-NN è che è possibile per k-NN gestire tipi di dati numerici e non numerici usando la codifica neurale delle variabili di predittore.
In breve, l'idea consiste nel codificare variabili predittive tramite un autoencoder neurale. Può gestire un autoencoder 1-of-(N-1) codifica o dati non numerici con quello-hot. Un autoencoder consente di stimare i valori di output in modo da corrispondere i valori di input. Il livello nascosto centrale di un autoencoder è una rappresentazione numerica completamente dei dati numerici e non numerici di origine.
L'ordinamento o le distanze di ordinamento
Dopo che sono state calcolate tutti distanze, l'algoritmo k-NN deve trovare le distanze più vicino di k (dal più piccolo). Un approccio consiste nel migliorare l'intero set di dati con ogni valore distance con l'etichetta, quindi in modo esplicito l'ordinamento dei dati ottimizzati. Un approccio alternativo, usato nella demo è usare un overload del metodo Array. Sort .NET brillante per ordinare solo le distanze e gli indici associati i dati in parallelo. Il codice è:
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);
La matrice denominata ordinamento inizialmente contiene 0, 1, 2. . 32. Viene creata una copia delle 33 distanze per l'elemento-a-classificare perché non si vuole perdere le distanze in base all'ordine originale. L'istruzione Array.Sort(distancesCopy, ordering) Ordina i valori nella matrice distancesCopy dal più piccolo al più grande utilizzando l'algoritmo Quicksort e contemporaneamente Riorganizza i valori di indice nella matrice di ordinamento. Il risultato è che il primo valore nell'ordine della matrice è l'indice per i dati dell'elemento con la distanza minima, il secondo valore nell'ordinamento mantiene l'indice indica la distanza più vicino secondo e così via. Interessante!
Determinare i pesi k-NN e voto
La forma più primitiva di usando le distanze più vicino di k per prevedere una classe consiste nell'usare un approccio delle regole di maggioranza dei nodi semplice. Ad esempio, se k = 4 and c = 3 e due le distanze più vicine sono associati alla classe 2 e una distanza minima è associata alla classe 0 e una distanza minima è associata alla classe 1, quindi un approccio delle regole di maggioranza dei nodi consente di stimare classi 2. Notare che ponderata k-NN con pesi uniformi, ciascuna con valore 1/k, è equivalente dell'approccio della regola maggioranza dei nodi.
L'approccio delle regole di maggioranza ha due problemi significativi: In primo luogo, i valori equivalenti sono possibili. Secondo, tutte le distanze vengono ponderate in modo uniforme. Lo schema di ponderazione più comune per ponderata k-NN consiste nell'applicare l'approccio di pesi inversa usata dal programma demo. Ma esistono diverse altre tecniche. Ad esempio, la tecnica distanze inverso vengono sommati tutti distanze, divide le distanze tutti per la somma, quindi inverte l'ordine.
Un altro approccio consiste nell'usare il rango delle distanze più vicino di k (1, 2,.. 6) invece delle distanze autonomamente. Per k = 6, i pesi di centro di ordine di rango viene calcolati come (1 + 1/2 + 1 o 3 + 1 e 4 + 1, 5 + 1/6) / 6 = 0.4083, (1/2 + 1 o 3 + 1/4 + 1 o 5 + 1/6) / 6 = 0.2417 e così via.
Per il programma demo, l'operazione inversa, uniforme, inverso e i centroidi pesi sono:
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
Conclusioni
L'algoritmo di classificazione k-NN ponderata ha ricevuto recentemente maggiore attenzione per due motivi. In primo luogo, usando autoencoding neurale, k-NN può gestire valori misti predittore numerico e non numerici. In secondo luogo, rispetto a molti altri algoritmi di classificazione, sono relativamente facili da interpretare i risultati della media ponderata k-NN. Interpretazione è diventata sempre più importante a causa dei requisiti legali di tecniche di Machine Learning da normative quali paesi dell'Unione europea del regolamento GDPR.
Dr. James McCaffreylavora per Microsoft Research Redmond, WA Ha lavorato su diversi prodotti Microsoft fondamentali, tra cui Azure e Bing. Dr. È possibile contattarlo McCaffrey jamccaff@microsoft.com.
Grazie per i seguenti esperti tecnici Microsoft che ha esaminato in questo articolo: Chris Lee, Ricky Loynd