Testlauf

Winnow-Klassifikation unter Verwendung von C#

James McCaffrey

Laden Sie die Codebeispiele herunter

In der Maschine lernen (ML) ist eine Klassifizierung-Problem in dem Ziel ist es, ein Modell zu erstellen, die ein Ergebnis vorhersagt, das der diskrete, nichtnumerische Werte annimmt. Beispielsweise sollten Sie die politische Partei (Demokraten oder Republikaner) einer Person vorherzusagen. Es gibt viele unterschiedliche Klassifizierung Algorithmen und Techniken, wie z. B., Naive Bayes Klassifikation, logistische Regression Klassifizierung und neuronales Netz-Klassifizierung.

Eine sehr einfache und interessante Klassifizierung-Technik ist den verletzend-Algorithmus verwendet. (Das englische Wort Worfeln Mittel, um unerwünschte Elemente entfernen). Der beste Weg, um ein Gefühl für das, was verletzend-Klassifizierung und zu sehen, wohin dieses Artikels ist es, einen Blick auf das Demoprogramm in Abbildung 1.

Abbildung 1 Worfeln Algorithmus Klassifizierung Demo

Das Ziel das Demoprogramm ist vorherzusagen, die politische Partei Demokraten oder Republikaner, ein Mitglied der Vereinigten Staaten House Of Representatives, basierend auf der Vertreter Stimmen auf 16 Rechnungen. Das Repräsentantenhaus hat 435 Mitglieder. Ein bekannter Benchmark-Datensatz enthält 435 Elemente in eine einfache Textdatei gespeichert. Die ersten drei Datenelemente sind:

republican,n,y,n,y,y,y,n,n,n,y,?,y,y,y,n,y
republican,n,y,n,y,y,y,n,n,n,n,n,y,y,y,n,?
democrat,?,y,y,?,y,y,n,n,n,n,y,n,y,y,n,n

Die erste Spalte in einer Zeile ist entweder Demokraten oder Republikaner. Die nächsten 16 Spalten sind entweder n (keine Stimmen), y (ja), oder? (fehlende, unbekannte oder enthalten). Die erste Spalte stellt das Mitglied Abstimmung über eine Stückliste mit Bezug zu behinderte Kinder. Die zweite ist eine Stückliste mit Bezug zu einem Wasserprojekt. Und so weiter. Sie brauchen nicht zu wissen, was Bill jede Spalte zugeordnet ist, aber wenn Sie interessiert sind finden Sie in diesem Datensatz (mit Beschreibungen) an vielen Stellen im Internet durch eine Suche nach "UCI Abstimmung Daten."

Worfeln Klassifizierung richtet sich an eine ganz bestimmte Art von Klassifikation-Problem: ein Klasse Vorhersagen kann nehmen Sie einen von zwei möglichen Werten (diese werden binäre Klassifikation Probleme genannt) wo die Vorhersagedienst Variablen (häufig genannt "Funktionen" in der ML-Terminologie) können einen von zwei möglichen Werten auch annehmen. Der Rohe Abstimmung Datensatz erfüllt diese Anforderungen, wenn die fehlenden Werte behandelt werden. Der am häufigsten verwendete Ansatz für den Umgang mit fehlenden Werten ist einfach, jedes Datenelement zu löschen, die einen oder mehrere fehlende Werte hat. Allerdings Stimmen bei der Abstimmung von Daten, ein fehlender Wert oft stellt eine stillschweigende "Nein", also das Demoprogramm mit "Nein"-stimmen alle fehlenden Werte ersetzt.

Die Demo-Anwendung verwendet die ersten 100 Datenelemente in der Abstimmung statt alle 435 Artikel festgelegt. Die Demo unabhängige Variable codiert "Nein"-Stimmen als 0 und "Ja" Stimmen als 1 und die abhängige Partei X Variablenwerte "Demokrat" als 0 und "Republikaner" als 1 codiert. Die Demo wird die abhängige Y Variable aus der ersten Spalte auf die letzte Spalte, da mit der letzten Spalte für Y bequemer ist, beim Codieren und häufigere verschoben.

Die Demo teilt nach dem Zufallsprinzip 100-Element codierte DataSet in eine 80-Element Trainingssatz erstellen Sie Modell und ein 20-Punkt-Prüfgerät, die Genauigkeit des Modells zu bewerten. Die Demo verwendet den verletzend-Algorithmus, um 16 Gewichte (eine für jede Eingabe) zu finden: 0.2500, 0.500, . . , 0.0625. Mit diesen Gewichten, prognostiziert das Demo-Modell richtig die politische Partei 97,50 Prozent der der Ausbildung Gegenstände (78 von 80) und 95.00 Prozent der Prüflinge (19 von 20).

Die Demo endet mithilfe des Objektmodells vorherzusagen, die Partei eines hypothetischen Vertreters, die auf alle 16 Rechnungen mit "Ja" gestimmt. Auf der Grundlage des Modells ist die Vorhersage, dass die Person ein Republikaner.

Dieser Artikel setzt voraus, Sie haben zumindest fortgeschrittene Programmierkenntnisse, aber nicht annehmen, dass Sie wissen nichts über den verletzend-Klassifizierung-Algorithmus. Die Demo ist codiert mit c#, aber Sie sollte nicht viel Mühe haben, wenn Sie den Code in eine andere Sprache, z. B. Visual Basic .NET oder JavaScript umgestalten möchten.

Verständnis des verletzend-Algorithmus

Der Einfachheit halber angenommen Sie, die Trainingsdaten auf nur fünf Stimmen anstatt 16 basiert. Zum Beispiel:

1, 0, 1, 1, 0 -> 0
1, 1, 1, 0, 1 -> 1
0, 0, 0, 1, 0 -> 1

Das heißt also, der ersten Zeile "Ja-Stimme," "Nein," "Ja Stimme," "Ja,"-"Nein," "Demokrat." Angenommen Sie, ein Modell trainiert wird und Gewichte {0,75 3,00, 1.00, 0.50, 0.40 liefert}. Um eine vorhergesagte Ausgang zu berechnen, den Algorithmus nur jeder Eingabewert mit dem entsprechenden Gewicht multipliziert, addiert die Begriffe und vergleicht dann die kumulierte Summe gegen einen Schwellenwert. Beispielsweise für das erste Element ist die kumulierte Summe:

(1 * 0.75) + (0 * 3.00) + (1 * 1.00) + (1 * 0.50) + (0 * 0.40) = 2.25

Der Schwellenwert ist 5.0 dann, da die kumulierte Summe (2.25) kleiner als der Schwellenwert ist, die vorhergesagte Y 0, ist in diesem Fall eine korrekte Vorhersage.

Ein Modell der Dressur sollen einen Satz von Gewichten zu finden, so dass bei der Anwendung auf Trainingsdaten mit bekannten Ausgabewerten berechneten Ausgaben eng die bekannten Ausgaben übereinstimmen. In hochrangigen Pseudocode die verletzend ist Algorithmus:

initialize weights
loop until done
  for each training item
    compute Y
    if correct do nothing
    else if incorrect
      if computed Y is too large
        divide all relevant weights by 2.0
      else if computed Y is too small
        multiply all relevant weights by 2.0
  end for
end loop

Angenommen, für die drei Daten Elemente Gewichte erwähnt, werden initialisiert:

{ 2.50, 2.50, 2.50, 2.50, 2.50 }

Der berechnete Y für das erste Training-Element (1, 0, 1, 1, 0 -> 0) ist:

Y = (1 * 2.50) + (0 * 2.50) + (1 * 2.50) + (1 * 2.50) + (0 * 2.50) = 7.50 -> 1

Dies ist eine falsche Vorhersage die berechnete Y 1 zu groß im Vergleich zu der gewünschten Y 0, so die entsprechenden Gewichte mit einem Faktor von 2.0 unterteilt sind. Die entsprechenden Gewichte sind diese Gewichte 1 Eingänge zugeordnet. Die neue Schnitte sind:

{ 2.50 / 2, (no change), 2.50 / 2, 2.50 / 2, (no change) }
= { 1.25, 2.50, 1.25, 1.25, 2.50 }

Nun, das zweite Training-Element (1, 1, 1, 0, 1 -> 1) ist mit der neuen Gewichte verarbeitet:

Y = (1 * 1.25) + (1 * 2.50) + (1 * 1.25) + (0 * 1.25) + (1 * 2.50) = 7.50 -> 1

Dies ist eine korrekte Vorhersage, so dass alle Gewichte bleiben allein. Das dritte Element der Ausbildung (0, 0, 0, 1, 0 -> 1) ist mit den aktuellen Schnitten verarbeitet:

Y = (0 * 1.25) + (0 * 2.50) + (0 * 1.25) + (1 * 1.25) + (0 * 2.50) = 1.25 -> 0

Dies ist eine falsche Vorhersage die berechnete Y 0 zu klein im Vergleich zu der gewünschten Y 1, so relevanten Gewichte mit 2.0 multipliziert werden:

{ (no change), (no change), (no change), 1.25 * 2.0, (no change) }
= { 1.25, 2.50, 1.25, 2.50, 2.50 }

Wenn Sie ein wenig über den Trainingsprozess verletzend denken, werden Sie zwei wichtige Merkmale feststellen. Zunächst verwendet der Algorithmus nur falsche Informationen. Zweitens fährt der Algorithmus im Wesentlichen die Gewichte der irrelevante Prädiktoren 0, worfeln sie raus. Dies macht oft verletzend Klassifizierung äußerst effektiv in Situationen, in denen viele der Vorhersagedienst Variablen irrelevant. Obwohl die grundlegenden Worfeln ist Algorithmus ganz einfach, gibt es einige Implementierungsdetails zu lösen z. B. entscheiden, wie die Gewichte zu initialisieren und bestimmen, wann man aufhören Training.

Allgemeine Programmstruktur

Die allgemeine Struktur des Demo-Programm mit ein paar Anweisungen der WriteLine entfernt und kleinere Änderungen platzsparend, präsentiert sich in Abbildung 2. Um das Demoprogramm zu erstellen, ich Visual Studio gestartet und erstellt eine neue C#-Konsolenanwendung mit dem Namen WinnowPredict. Die Demo hat keine signifikanten .NET Versionsabhängigkeiten, so dass beliebige Version von Visual Studio arbeiten sollte. Nachdem der Template-Code in den Editor geladen, ich löschte alle using-Anweisungen außer den einzigen Hinweis auf die Top-Level-System-Namespace. Im Fenster Projektmappen-Explorer ich benannte Datei Program.cs zu WinnowProgram.cs und Visual Studio automatisch umbenannt Klasse Programm für mich.

Abbildung 2 insgesamt Demo Programmstruktur

using System;
namespace WinnowPredict
{
  class WinnowProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin Winnow algorithm demo");
      int[][] data = new int[100][];
      data[0] = new int[] { 0, 1, 0, 1, 1, 1, 0, 0,
        0, 1, 0, 1, 1, 1, 0, 1, 1 };
      // Etc.
      // Create, train and test matrices from data
      // Instantiate Winnow classifier
      // Train using training data
      // Compute accuracy
      // Predict party of hypothetical person
      Console.WriteLine("End Winnow demo");
      Console.ReadLine();
    } // Main
    static void MakeTrainTest(int[][] data, int seed,
      out int[][] trainData, out int[][] testData) { . . }
    static void ShowVector(double[] vector, int decimals,
      int valsPerRow, bool newLine) { . . }
    static void ShowMatrix(int[][] matrix, int numRows,
      bool indices) { . . }
  }
  public class Winnow
  {
    private int numInput;
    private double[] weights;
    private double threshold;
    private double alpha;
    private static Random rnd;
    public Winnow(int numInput, int rndSeed) { . . }
    public int ComputeOutput(int[] xValues) { . . }
    public double[] Train(int[][] trainData) { . . }
    public double Accuarcy(int[][] trainData) { . . }
    private static void Shuffle(int[][] trainData) { . . }
  }
}

Das Demoprogramm ist ein bisschen zu lang, in seiner Gesamtheit in diesem Artikel zu präsentieren, sondern den kompletten Source-Code (WinnowProgram.cs) finden Sie in der beigefügten Dateidownload. Alle verletzend Klassifizierung Programmlogik enthalten ist im Programm definierten Klasse verletzend.

Die Main-Methode beginnt mit der Einrichtung einer Datengruppe 100-Element wie in gezeigt Abbildung 3.

Abbildung 3 die Main-Methode Einrichten eines 100-Item-Datensatzes

using System;
namespace WinnowPredict
{
  class WinnowProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin Winnow algorithm prediction demo");
      int[][] data = new int[100][];
      data[0] = new int[] { 0, 1, 0, 1, 1, 1, 0, 0,
        0, 1, 0, 1, 1, 1, 0, 1, 1 };
...

Um die Daten zu erstellen, befindet sich das UCI Abstimmung Datensatz im Web I, kopiert und in Notepad eingefügt und verwendet dann bearbeiten-ersetzen, platzieren die Daten direkt in ein Array von Arrays Stil-Matrix. Auch wenn Sie ein erfahrener Programmierer sind, möglicherweise nicht mit C#-Matrix-Syntax vertraut, aber Sie werden wahrscheinlich daran gewöhnen die Codierung Muster schnell. In einem nicht-Demo-Szenario würden Sie irgendeine Methode zum Laden von Daten aus der Textdatei in eine Matrix schreiben.

Als nächstes die ersten vier Linien und die letzte Zeile der gesamten Datenmenge mit einer Hilfsmethode angezeigt werden, und das DataSet gliedert sich in einen Trainingssatz (80 Teile) und Test-Set (20 Stück):

Console.WriteLine("\nFirst few lines of all data are: \n");
ShowMatrix(data, 4, true);
Console.WriteLine("\nSplitting data into 80% train" +
  " and 20% test matrices");
int[][] trainData = null;
int[][] testData = null;
MakeTrainTest(data, 0, out trainData, out testData);

Methode MakeTrainTest hat einen hartcodierten 80 bis 20 Prozent Split (vielleicht möchten die Prozent als Trainingsdaten verwenden parametrisieren). Nach der Anzeige Teil der Trainingsdaten zu vergewissern, dass nichts schief gelaufen, die Demo verletzend Klassifizierung und Objekt verwendet die Zug-Methode zum Erstellen eines Modells, d. h. um eine Reihe von guten Gewichte zu finden:

Console.WriteLine("First few rows of training data are:");
ShowMatrix(trainData, 3, true);
Console.WriteLine("Begin training using Winnow algorithm");
int numInput = 16;
Winnow w = new Winnow(numInput, 0);
weights = w.Train(trainData);
Console.WriteLine("Training complete");

Der verletzend-Konstruktor erfordert die Anzahl der X-Variablen und einen Startwert für die Erzeugung von Zufallszahlen, die zum Verarbeiten von der Ausbildung Gegenstände in zufälliger Reihenfolge. Als nächstes die Demo zeigt die endgültige Gewichte von der Zug-Methode gefunden, und berechnet dann die Genauigkeit des Modells auf die Ausbildung und Test-Sets:

Console.WriteLine("Final model weights are:");
ShowVector(weights, 4, 8, true);
double trainAcc = w.Accuarcy(trainData);
double testAcc = w.Accuarcy(testData);
Console.WriteLine("Prediction accuracy on training data = " +
  trainAcc.ToString("F4"));
Console.WriteLine("Prediction accuracy on test data = " +
  testAcc.ToString("F4"));

Die Demo schließt mit der Vorhersage der politischen Partei eines hypothetischen US Haus-Vertreter, die "Ja" auf alle 16 Rechnungen gestimmt, wie in Abbildung 4.

Abbildung 4 Vorhersage der politischen Partei

...
  Console.WriteLine("Predicting party of Representative" + "
    with all 'yes' votes");
  int[] unknown = new int[] { 1, 1, 1, 1, 1, 1, 1, 1,
  1 , 1, 1, 1, 1, 1, 1, 1 };
  int predicted = w.ComputeOutput(unknown);
  if (predicted == 0)
    Console.WriteLine("Prediction is 'democrat'");
  else
    Console.WriteLine("Prediction is 'republican'");
  Console.WriteLine("End Winnow demo");
  Console.ReadLine();
} // Main

Klasse verletzend

Die verletzend-Klasse verfügt über fünf Datenelemente:

private int numInput;
private double[] weights;
private double threshold;
private double alpha;
private static Random rnd;

Daten Mitglied Schwellenwert enthält den Wert, der bestimmt, ob berechnete Y 0 (unterhalb der Schwelle) oder 1 (Schwelle) ist. Daten Mitglied Alpha ist der Faktor, um Abnahme (genannt Herabstufung in Forschungsliteratur) oder erhöhen (so genannte Förderung) Gewichte, wenn eine falsche Y berechnet wird. Der Standardwert für Alpha ist 2.0, wie zuvor in diesem Artikel gezeigt. Vielleicht möchten experimentieren mit zwei unterschiedliche Werte für Förderung und Rückstufung, anstatt einer einzigen alpha-Wert für beide.

Die verletzend Konstruktor wird definiert wie folgt:

public Winnow(int numInput, int rndSeed)
{
  this.numInput = numInput;
  this.weights = new double[numInput];
  for (int i = 0; i < weights.Length; ++i)
    weights[i] = numInput / 2.0;
  this.threshold = 1.0 * numInput;
  this.alpha = 2.0;
  rnd = new Random(rndSeed);
}

Der Schwellenwert wird auf die Anzahl von input-Variablen, z. B. 16,0 in der Demo initialisiert. Dieser Wert ist standardmäßig für den Algorithmus verletzend, aber vielleicht möchten mit alternativen Werten experimentieren. Die Nein-Effect-Multiplikation mit 1,0 gibt es darauf hin, dass unterschiedliche Werte verwendet werden können, aber sie auf die Anzahl der Eingabevariablen bezogen werden sollte.

Mit der Anzahl von input-Variablen, 16 in der Demo das Gewichte-Array zugeordnet. Jedes der Gewichte ist auf die Anzahl der Eingabevariablen geteilt durch 2 oder 8.0 in der Demo initialisiert. Dieser Wert ist willkürlich, und wieder, Sie möchten z. B. testen. Der Algorithmus verletzend noch nicht durch Forschung sehr viel im Vergleich zu vielen anderen, häufiger verwendet Klassifizierung Algorithmen untersucht worden.

ComputeOutput-Methode ist einfach:

public int ComputeOutput(int[] xValues)
{
  double sum = 0.0;
  for (int i = 0; i < numInput; ++i)
    sum += weights[i] * xValues[i];
  if (sum > this.threshold)
    return 1;
  else
    return 0;
}

Hinweis, der Wert 1 zurückgegeben wird wenn die kumulierte Summe größer als der Schwellenwert, im Gegensatz zu größer oder gleich dem Schwellenwert ist. Dies ist willkürlich und mit "> =" statt ">" keine erheblichen Auswirkungen auf den Algorithmus haben.

Die Trainingsmethode

Verletzend-Algorithmus-Trainingsprogramm ist eines der kürzeste und einfachste aller ML-Klassifizierung-Algorithmen. Die Methodendefinition beginnt:

public double[] Train(int[][] trainData)
{
  int[] xValues = new int[numInput];
  int target;
  int computed;
  Shuffle(trainData);
...

Lokales Array "xValues" hält die Eingabewerte aus dem Training-Element, aber nicht das Ziel Ausgabewert. Lokale Variable "Ziel" hält den gewünschten Y-Wert aus einem Datenelement Training. Lokale Variable "berechnet" speichert den berechneten Y-Wert für einen bestimmten Satz von Eingabewerten X und den aktuellen Satz von Gewichten. Shuffle-Methode ordnet die Reihenfolge der Trainingsdaten mit dem Fisher-Yates-Mini-Algorithmus.

Als nächstes beginnt die wichtigste Trainingsprinzip-Schleife:

for (int i = 0; i < trainData.Length; ++i)
{
  Array.Copy(trainData[i], xValues, numInput); // Inputs
  target = trainData[i][numInput]; // Last value is target
  computed = ComputeOutput(xValues);
  // Update weights here
}

Wie bereits erwähnt, ist es nicht ganz klar wie lange trainieren. Die Demo wird nur einmal durchlaufen die Trainingsdaten. Eine Alternative besteht darin, mehrere Male Trainingsdaten, stoppt nach einer festgelegten Anzahl von Iterationen durchlaufen oder vielleicht wenn ein Teil der gewünschten Genauigkeit erreicht wurde.

Innerhalb der Schleife wichtigste Trainingsprinzip Gewichte aktualisiert werden, verwenden den Code in Abbildung 5.

Abbildung 5 aktualisieren Gewichte

if (computed == 1 && target == 0) // Decrease
{
  for (int j = 0; j < numInput; ++j)
  {
    if (xValues[j] == 0) continue; // Not relevant
    weights[j] = weights[j] / alpha; // Demotion
  }
}
else if (computed == 0 && target == 1) // Increase
{
  for (int j = 0; j < numInput; ++j)
  {
    if (xValues[j] == 0) continue; // Not relevant
    weights[j] = weights[j] * alpha; // Promotion
  }
}

Methode Zug schließt mit dem Kopieren die besten Gewichte fanden in einem lokalen Rückkehr-Array:

...
  } // end for
  double[] result = new double[numInput]; // = number weights
  Array.Copy(this.weights, result, numInput);
  return result;
} // Train

Zusammenfassung

Dieser Artikel basiert auf der Forschungsarbeit, die ursprünglich den Algorithmus verletzend präsentiert "lernen schnell, wenn irrelevante Attribute gibt es zuhauf: Ein neuer Algorithmus Linear-Threshold"(1998), N. Littlestone. Dieses Papier finden Sie im PDF-Format im Web an mehreren Standorten.

Hintergrund-Recherchen für diesen Artikel, stieß ich auf eine interessante Implementierung des verletzend Algorithmus unter Verwendung der Sprache f# geschrieben. Die Implementierung ist in einem persönlichen Blog-Beitrag geschrieben von Mathias Brandewinder (bit.ly/1z8hfj6).

Obwohl verletzend Klassifizierung speziell für binäre Klassifikation Probleme konzipiert ist, wo die unabhängigen X-Variablen alle binären sind, empfiehlt es sich, über Probleme zu experimentieren, wo ein oder mehrere X-Variablen kategorisch sind. Nehmen wir beispielsweise an, eine Prädiktor-Variable ist "Farbe" und kann einen der drei Werte annehmen: "rot", "grün" oder "blau". Wenn Sie 1-des-N Codierung, rot wird (1, 0, 0), grün (0, 1, 0), wird blau wird (0, 0, 1), und verletzend-Algorithmus angewendet werden kann.

Dr. James McCaffrey arbeitet für Microsoft Research in Redmond, Washington  Er arbeitete an verschiedenen Microsoft-Produkten, einschließlich Internet Explorer und Bing. Er kann erreicht werden unter jammc@microsoft.com.

Dank der folgenden technischen Experten bei Microsoft Research für die Überprüfung dieses Artikels: Nathan Brown und Kirk Olynyk