Mai 2019
Band 34, Nummer 5
[Test Run]
Test Run: Gewichtete k-NN-Klassifizierung mit C#
Durch James McCaffrey
.jpg "James McCaffrey")
Das Ziel eines Machine learning (ML) für ein klassifizierungsproblem ist um einen diskreten Wert vorherzusagen. Beispielsweise empfiehlt es sich um die politischen Ansichten einer Person basierend auf ihren Alter Ausgaben des Gesundheitswesens, Geschlecht, Bildungsgrad und so weiter (konservativ, gemäßigt, liberal) vorherzusagen. Es gibt viele verschiedene klassifikationstechniken, einschließlich neuronale Netzwerke, Entscheidungsstrukturen und logistische Regression. In diesem Artikel zeigen ich zum Implementieren des gewichteten k nächsten Nachbarn-Algorithmus, mit der C# Sprache.
Die beste Möglichkeit, zu verstehen, in diesem Artikel geht auf einen Blick auf die Demo in auszuführen ist Abbildung1 sowie die zugehörigen Daten in ein Diagramm abbildung2. Das Demoprogramm richtet 33 dummydatenelementen ab. Jedes Element steht Alter einer Person, jährliche Gesundheitswesen Ausgaben und einer beliebigen Klasse, um vorherzusagen, (0, 1, 2), die Sie als politische Haltung, für die Concreteness vorstellen können. Die Daten haben nur zwei prädiktorvariablen, daher in einem Diagramm angezeigt werden kann, aber die k-NN mit einer beliebigen Anzahl von prädiktoren funktioniert.
.png "Gewichtete k-NN-Klassifizierung: Demoausführung")
Abbildung 1 gewichtet k-NN-Klassifizierung: Demoausführung
.png "Gewichtete k-NN-Daten")
Abbildung 2 gewichtet k-NN-Daten
Die Daten hat normalisiert wurden. Verwendung von k-NN ist es wichtig, die Daten zu normalisieren, sodass Sie große Werte, z. B. einer jährlichen Kosten der 30.000 Dollar beträgt, nicht die kleinen Werten, z. B. Alter 25 überschwemmen. Das Ziel der Demo ist zum Vorhersagen von der Klasse eine neue Person, die ALTER normalisiert hat und Betriebsausgaben für den (0,35, 0,38). Die Demo legt fest, k = 6 und sucht nach den sechs Daten mit Label-Elemente, die die Element-zu-klassifizieren am nächsten sind.
Nach dem Ermitteln der sechs am nächsten liegende Daten mit Label-Elemente, verwendet das Demoprogramm eine gewichtete abstimmungs-Technik, um eine Entscheidung zu erreichen. Die Abstimmung gewichteten Werte für Klassen (0, 1, 2) sind (0.3879, 0.4911 0.1209), also das Element am (0,35, 0,38) als Klasse 1 klassifiziert werden sollen.
In diesem Artikel wird vorausgesetzt, dass Zwischenzertifikat oder besser Programmierkenntnisse mit C# oder einer C-Sprache wie Python oder Java, jedoch nicht vorausgesetzt, Sie wissen jedoch nichts den gewichteten k-NN-Algorithmus. Der gesamte Democode und die zugehörigen Daten werden in diesem Artikel vorgestellt. Den Quellcode und die Daten sind auch im begleitenden Download verfügbar. Die gesamte normale Fehlerprüfung wurde entfernt, um die Hauptideen so klar wie möglich darzustellen.
Grundlegendes zu den gewichteten k-NN-Algorithmus
Der gewichteten k-NN-Algorithmus ist eine der einfachsten alle ML-Techniken, aber es einige komplizierte Implementierungsdetails gibt. Die erste Frage, die meisten Entwickler haben wird "Wie Sie den Wert von k bestimmt?" Die Antwort etwas geholfen ist, dass der Wert von k durch Versuch und Irrtum ermittelt werden muss.
Wenn k-NN verwenden zu können, müssen Sie die Entfernung aus der Element-zu-klassifizieren, die alle gekennzeichneten Daten berechnen. Es gibt viele Funktionen der Entfernung, aber mithilfe der euklidischen Distanz ist einfach und effektiv. Die Euklidische Distanz zwischen den beiden Elementen wird die Quadratwurzel der Summe der quadrierten Differenzen von Koordinaten. Wenn ein Element für die Daten mit Label ist z. B. (0,20, 0,60) und das Element zum Klassifizieren (0,35, 0,38) klicken Sie dann:
dist = sqrt( (0.20 - 0.35)^2 + (0.60 - 0.38)^2 )
= sqrt(0.0225 + 0.0484)
= 0.2663
Nach dem Berechnen aller entfernungen, und suchen die Abstände k-am nächsten liegt, müssen Sie einen Abstimmung Algorithmus verwenden, um zu bestimmen, die vorhergesagte Klasse. Es gibt viele Möglichkeiten, eine Vorhersage von entfernungen zu berechnen. Das Demoprogramm verwendet die inversen Gewichtungen, die Verfahren, also am besten anhand eines Beispiels erklären. Nehmen wir an, (wie in der Demo, die sechs nächstgelegenen Abstände 0.0728, 0.0781, 0.1118, 0.1217, 0.1300 und 0.1414) und die zugeordnete Bezeichnung sind Klassen, (0, 1, 0, 1, 1, 2). Sie berechnen die Umkehrung der einzelnen Entfernung, ermittelt die Summe der Ihrer inversen, und jede Inverse durch die Summe dividiert. Sind für die Demo die Gegenstücke (13.7363, 12.8041, 8.9445, 8.2169, 7.6923, 7.0721). Die Summe Ihrer inversen ist 58.4663. Jeder umgekehrte Abstand durch die Summe dividiert bietet die Gewichtungen: (0.2349, 0.2190, 0.1530, 0.1405, 0.1316, 0.1210).
Jedes Gewicht wird keine Stimme für die zugeordnete Klasse. Im Demoprogramm haben das erste und dritte nächstgelegene Element Klasse 0 (null), die Stimme für Klasse 0 ist die Summe der Gewichtungen ersten und dritten: 0.2349 + 0.1530 = 0.3879. Ebenso ist die Stimme für Klasse 1 0.2190 + 0.1405 + 0.1316 = 0.4911. Und die Stimme für Klasse 2 ist gerade die sechste Gewichtung 0.1210. Die endgültige Vorhersage ist die Klasse, die die größte Stimme an.
Das Demoprogramm
Das vollständige Demoprogramm (mit einigen kleinen Bearbeitungen, um Platz zu sparen) wird in Abbildung 3 gezeigt. Um die Anwendung zu erstellen, ich Visual Studio gestartet und erstellt eine neue Konsolenanwendung, die mit dem Namen WeightedKNN. Ich habe Visual Studio 2017 verwendet, aber die Demo hat keine nennenswerten .NET Framework-Abhängigkeiten.
Abbildung 3: das gewichtete k-NN-Demoprogramm
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
Nachdem der Vorlagencode geladen, im Editor-Fenster habe ich entfernt alle überflüssige Namespaceverweise, lassen nur den Verweis auf den obersten System-Namespace. Im Fenster Projektmappen-Explorer mit der rechten Maustaste auf die Datei "Program.cs" ich, den aussagekräftigeren WeightedKNNProgram.cs umbenannt und Visual Studio automatisch die Program-Klasse umbenennen zulässig.
Aus Gründen der Einfachheit verwendet das Demoprogramm, einen Ansatz für statischen Code anstelle einer objektorientierten Programmieransatz. Die meiste Arbeit erfolgt in der Methode analysieren.
Laden der Daten in den Arbeitsspeicher
Im Demoprogramm sind die unechten Daten und die Element-zu-klassifizieren:
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 einem echten Szenario würden Sie wahrscheinlich Ihre Daten in einer Textdatei oder SQL-Tabelle speichern und schreiben eine Hilfsmethode zum Laden der Daten in ein Array-von-Arrays-Style-Matrix. Ich bezeichnet die Daten als nur "Daten", etwa TrainData ab, da von k-NN verwendete Daten tatsächlich verwendet werden, um ein allgemeines Modell zu trainieren.
Der erste Wert in jedem Datenelement ist ein beliebiger-ID. Aufeinander folgende ganze Zahlen von 0 bis 32 verwendet, aber in vielen Fällen müssten Sie aussagekräftige-IDs, z. B. Mitarbeiter-ID von einer Person. Der k-NN-Algorithmus benötigen nicht Daten-IDs, sodass die ID-Spalte kann ausgelassen haben. Die zweite und dritte Werte sind die normalisierten prädiktorwerte. Der vierte Wert stellt die Klassen-ID. Klassen-IDs für k-NN müssen keine nullbasierte ganze Zahlen sein, aber mit diesem Schema programmgesteuert eignet.
Entfernungen Computing
Der erste Schritt bei der k-NN-Algorithmus ist zum Berechnen des Abstand zwischen jeder Daten mit Label-Element und die Element-zu-be klassifiziert. Basierend auf meiner Erfahrung und einige Forschungsergebnisse, nicht die Wahl der Distance-Funktion angewendet genauso wichtig, Sie könnten einwenden, und einfache Euklidischer Abstand in der Regel funktioniert gut.
Die demoimplementierung von Euklidische Distanz wird:
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);
}
Beachten Sie, dass die for-Schleife Indizierung hartcodiert mit 2 für die Anzahl der prädiktorwerte, und der Unterschied zwischen Element [i] und ' DataPoint ' [i + 1]-Konto für den Daten-ID-Wert an Position [0] versetzt wird. Der Punkt hierbei ist, dass es in der Regel ein Kompromiss zwischen Codierung einen ML-Algorithmus für ein bestimmtes Problem, und Programmieren den Algorithmus mit einer Ansicht für allgemeine Zwecke verwenden. Da k-NN so einfach und leicht zu implementieren ist, ziehe ich in der Regel den Code für spezifische Problem Ansatz vor.
Auf erster Gedanke scheint die Anforderung der computing einer Distance-Funktion die wesentliche Einschränkung für k-NN zu erzwingen, dass alle prädiktorvariablen ausschließlich numerisch sein müssen. Und bis vor kurzem diese Idee wurde "true", in den meisten Fällen. Einer der Gründe für die erhöhte Interesse an der k-NN ist jedoch, dass es möglich, dass k-NN gemischten numerische und nicht-numerische Daten mit neuronalen Codierung, der die vorhersagevariablen verarbeiten ist.
Kurz gesagt, ist die prädiktorvariablen, die mit einem neuronalen Autoencoder zu codieren. Ein Autoencoder kann nicht-numerische Daten mit One-hot oder 1-von-(n-1)-Codierung zu verarbeiten. Ein Autoencoder prognostiziert die Ausgabewerte der Eingabewerten entsprechend an. Die zentralen verborgene Ebene von einem Autoencoder ist eine vollständig numerische Darstellung für die numerische und nicht-numerische Daten.
Anordnung oder Sortierung die Abstände
Nachdem alle Distanzen berechnet worden sind, muss der k-NN-Algorithmus die nächste k (kleinste) Abstände finden. Ein Ansatz besteht darin, das gesamte Dataset mit jeder Distance-Wert mit der Bezeichnung zu erweitern und dann explizit die ergänzten Daten sortieren. Ein alternativer Ansatz, der Demo, ist eine praktische Überladung von der .NET Array.Sort-Methode verwenden, um nur die Abstände und die zugeordneten Indizes parallel zu sortieren. Der Schlüssel Code ist:
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);
Das Array namens anfänglich Sortierung enthält 0, 1, 2. . 32. Eine Kopie der 33 Entfernung, die die Element-zu-Klassifizierung wird erstellt, da Sie nicht die Abstände in der ursprünglichen Reihenfolge verlieren möchten. Die Anweisung Array.Sort(distancesCopy, ordering) sortiert die Werte im Array DistancesCopy vom kleinsten zum größten Element mit dem Quicksort-Algorithmus und gleichzeitig ordnet die Werte des Indexes im Array sortieren. Das Ergebnis ist, dass der erste Wert in die arraysortierung ist der Index auf die Daten des Elements mit der geringste Abstand, der zweite Wert in der Reihenfolge enthält des Indexes der nächsten Sekunde Entfernung und so weiter. Nett!
Festlegen von k-NN-Gewichtungen und Abstimmen
Die meisten primitiven Form mit, dass die Abstände k nächste vorherzusagen, eine Klasse ist für eine einfache Mehrheit Regel Ansatz. Z. B. wenn k = 4 "und" c = 3, zwei die nächstgelegenen Abstände Klasse 2 zugeordnet sind und eine geringsten Abstand Klasse 0 (null) zugeordnet ist und eine geringsten Abstand Klasse 1 zugeordnet ist, und ein Großteil Regel Ansatz vorhersagt, Klasse 2. Beachten Sie, dass diese gewichtete k-NN mithilfe von uniform Gewichtungen, jeweils mit dem Wert 1/k, mit dem Ansatz der meisten Regel entspricht.
Die meisten Regel Ansatz hat zwei wichtige Probleme: Erstens sind die Verbindungen möglich. Zweitens wird alle entfernungen sind gleichmäßig gewichtet. Das am häufigsten verwendete Gewichtung-Schema für gewichtete k-NN wird umgekehrte Gewichtungen Ansatz verwendet das Demoprogramm angewendet. Aber es gibt viele Techniken. Z. B. die umgekehrte entfernungen Technik alle entfernungen addiert, alle entfernungen wird durch die Summe dividiert, und dann kehrt die Reihenfolge.
Ein anderer Ansatz ist die Verwendung von den Rang der k-nächste entfernungen (1, 2... (6) anstelle von die Abstände selbst. Für k = 6, die Gewichtungen werden berechnet als (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 und So weiter.
Sind für das Demoprogramm, die Inverse, einheitliche Umkehrung und Schwerpunkte (Centroid) Gewichtungen aus:
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
Zusammenfassung
Die gewichtete k-NN-klassifizierungsalgorithmus hat vor kurzem erhöhte Aufmerksamkeit aus zwei Gründen erhalten. Zunächst kann mithilfe von neuronalen Autoencoding k-NN gemischten numerische und nicht-numerische prädiktorwerte behandeln. Zweitens sind bei im Vergleich zu vielen anderen klassifikationsalgorithmen, die die Ergebnisse der gewichteten k-NN relativ leicht zu interpretieren. Interpretierbarkeit finden geworden zunehmend wichtiger aufgrund von gesetzlichen Vorschriften der ML-Techniken von Vorschriften wie der Europäischen Union der DSGVO.
Dr. James McCaffreyist in Redmond (Washington, USA) für Microsoft Research tätig. Er arbeitet in mehreren wichtigen Microsoft-Produkten wie Azure und Bing. Dr. McCaffrey erreichen Sie unter jamccaff@microsoft.com.
Unser Dank gilt den folgenden technischen Experten von Microsoft für die Durchsicht dieses Artikels: Chris Lee, Ricky Loynd