Freigeben über

Oktober 2015

Band 30, Nummer 10

Dieser Artikel wurde maschinell übersetzt.

Testlauf – Lineare Diskriminanzanalyse mithilfe von C#

Durch James McCaffrey

Das Ziel eines Problems binäre Klassifikation ist auf den Wert einer Variablen vorherzusagen, die einen von zwei möglichen Werten annehmen kann. Beispielsweise empfiehlt es sich, Änderung in der Aktienkurs von einigen Unternehmen (Erhöhung oder Verringerung) auf Grundlage der Vorhersage Variablen wie die durchschnittliche Anzahl von Freigaben verkauft, Anzahl der Transaktionen, Insider, Preis, Gewinn-Verhältnis usw. vorherzusagen. Oder könnte die politische Neigung einer Person (bedienen oder konservative) Alter, Einkommen, Ausbildung und so weiter anhand vorhergesagt werden soll.

Es gibt ungefähr ein Dutzend wichtige Algorithmen, die für binäre Klassifikation verwendet werden können. Lineare discriminate Analyse (LDA) ist eine der ältesten Methoden, die von den 1930er Jahren. Dieser Artikel erläutert, was LDA ist, wird beschrieben, wie es funktioniert und zeigt, wie Sie LDA mit Code implementieren.

Realistisch gesehen ist es unwahrscheinlich, dass Sie jemals LDA Code zu schreiben. Dennoch stehen drei Gründe, die Sie in diesem Artikel hilfreich sein könnte. Erstens gibt Ihnen zu verstehen, wie LDA Programmieren gründliche Funktionsweise der LDA für den Fall, dass Sie stoßen Sie jemals auf ihn kennen. Zweitens können einige Codierungstechniken, die bei der Implementierung von LDA verwendet in anderen, häufiger Programmierung Szenarios nützlich sein. Schließlich die Ideen hinter LDA sind außergewöhnlich raffinierte und Sie fanden LDA interessante erkenntnisreich.

Die beste Methode, um ein Gefühl für welche LDA binäre Klassifikation ist abzurufen und worauf dieser Artikel ist ist auf einen Blick auf das Demoprogramm in Abbildung 1.

Lineare Descriminate Analyse binäre Klassifikation Demo
Abbildung 1 lineare Descriminate Analyse binäre Klassifikation Demo

Das Ziel des Demoprogramms ist die politische Neigung, bedienen oder einer Person, die auf Grundlage der Person Alter und Jahreseinkommen konservative vorherzusagen. Die Demo verwendet ein winziger Trainingsdataset nur acht Elemente, um das Vorhersagemodell LDA zu erstellen. Alter und Einkommen haben wurde in irgendeiner Weise so normalisiert, dass die Werte, die beide ungefähr sind identisch.

Politische Neigung wurde damit, bedienen 0 ist und konservative 1 codiert. Im Gegensatz zu viele binäre klassifikationsalgorithmen können LDA jede Art von Codierung für die Variable Sie vorhersagen. Damit die politischen Neigung konnte als-1 und + 1, oder "A" und "B" codiert wurden.

Grundlegende LDA binäre Klassifikation kann mit einer beliebigen Anzahl von Vorhersage-Variablen. Und es ist möglich, erweitern grundlegende LDA um vorherzusagen, eine Variable, die einen der drei oder mehr Werte annehmen können. Beispielsweise können Sie vorhersagen, politische Neigung, in denen die möglichen Werte bedienen, konservativ und Mittel sind. Dieser Artikel beschreibt nur binäre Klassifikation.

Der Schlüssel zur LDA ist, einen so genannten linearen discriminate, normalerweise dargestellt durch Großbuchstaben "w". Verwenden die acht Datenelemente, berechnet die Demo w = (-0.868,-0.496). W Arrays müssen die gleiche Anzahl von Werten, wie Vorhersage Variablen vorhanden sind. Bei der Berechnung der w hinter den Kulissen die Demo berechnet die Mittel für jede der beiden Klassen, dann die Mittel zum Berechnen von XY-Matrizen für jede Klasse verwendet, und schließlich die XY-Matrizen verwendet, um eine kombinierte in-Klasse XY-Matrix zu berechnen. Die Matrix innerhalb der Klasse wird benötigt, w zu berechnen.

Nach der Berechnung w, Demo wird durch die Klasse für eine neue Person vorhergesagt werden, die ALTER normalisiert hat = 4.0 und normalisiert Income = 5.0. Die Vorhersage LDA ist, dass die Person, die eine bedienen politische Neigung.

Dieser Artikel setzt Sie mindestens fortgeschrittene Programmierkenntnisse verfügen, jedoch nicht vorausgesetzt, dass Sie klassifikationsalgorithmus LDA auskennen. Die Demo mit c# codiert ist sollten, aber Sie Probleme sollten Sie den Code in einer anderen Sprache wie z. B. Visual Basic .NET oder JavaScript umzugestalten.

Grundlegendes zu LDA binäre Klassifikation

Die wichtigsten Konzepte LDA binäre Klassifikation werden in die beiden Diagramme Siehe dargestellt Abbildung 2. Das obere Diagramm zeigt die Daten aus der Demo-Programm. Die drei blaue Punkte dargestellt drei Personen bedienen sind. Die fünf roten Punkte sind die Conservatives. Gelber Punkt in (4.0, 5.0) stellt eine Person mit unbekannten politische Neigung dar. Auch für solche ein einfaches Problem ist es nicht offensichtlich, wenn die unbekannte Person als eine bedienen oder eine vorsichtig klassifiziert werden soll.

LDA Vorhersage mit dem Initialisierungsvektor Discriminate

Abbildung 2 LDA Vorhersage mit dem Initialisierungsvektor Discriminate

Beachten Sie, dass nur die Demo Daten angezeigt werden deshalb, könnte Siehe Abbildung 2 ist, dass es nur zwei Vorhersage-Variablen. Falls mehr als zwei Vorhersage Variablen sind, wäre es nicht möglich, die Daten so gut in 2D Diagramm finden Sie unter, aber gelten dieselben Prinzipien von LDA. Unabhängig davon, wie viele Vorhersage-Variablen in binäre LDA vorhanden sind, werden es nur zwei Klassen. Es ist einfach, die Anzahl der Vorhersage-Variablen (zwei oder mehr) mit der Anzahl der Werte zu verwechseln, die Variable Vorhersagen (immer genau zwei für binäre Klassifikation) nutzen kann.

Die meisten Algorithmen für binäre Klassifikation versuchen Sie, eine Linie (technisch gesehen ein Vektor) zu suchen, die explizit die beiden Klassen getrennt. Beispielsweise im oberen Diagramm in Abbildung 2, Sie können sich vorstellen, einem hypothetischen, trennen die Zeile, die über ausgeführt wird (3, 9) nach unten, um (5, 0). Alle unbekannten Datenpunkt auf der linken Seite der Zeile würde als bedienen klassifiziert werden, und einen beliebigen Punkt auf der rechten Seite wäre eine vorsichtig. LDA funktioniert ganz anders.

Der erste Schritt beim LDA ist eine Linie bezeichnet die discriminate gefunden. In Abbildung 2, die discriminate Zeile ist Grün, und der discriminate als (0.868, 0.496). In LDA, ist die discriminate Zeile immer durch einen einzelnen Endpunkt identifiziert und der Ausgangspunkt ist immer implizit (0, 0,.., 0).

Aber Moment mal. die Ausgabe des Demoprogramms in Abbildung 1 zeigt die discriminate (-0.868,-0.496) statt (+0.868, +0.496). Wie sich herausstellt, eine Konstante die Komponenten der discriminate multipliziert, und es ist keine Auswirkung auf das Ergebnis. Daher soll das Diagramm unten im Abbildung 2 nützlicher suchen und wichtige zur Veranschaulichung, verwendet (+0.868, +0.496) für w, anstatt die tatsächlichen berechnete Werte, die negativ waren. Mit anderen Worten, multipliziert ich beide Komponenten mit-1.

Anders ausgedrückt, die discriminate konnte identifiziert werden durch einen beliebigen Punkt auf die grüne Linie im Abbildung 2, wie z. B.-2 * (-0.868,-0.496) = (1.736, 0.992). Der standard, aber keine universelle Ansatz ist in LDA die discriminate skalieren, sodass es die Länge 1 vom Ursprung hat. Beachten Sie, dass die Länge von (0, 0), (0.868, 0.496) = Sqrt ((0 - 0.868) ^ 2 + (0 - 0.496) ^ 2) = Sqrt (0.754 + 0.246) = sqrt(1.000) = 1.

Aber was ist die Bedeutung des Vektors discriminate? In Abbildung 2, sind Schwarze gestrichelte Linien aus jedem Datenpunkt auf der discriminate Zeile, in dem die gestrichelten Linien senkrecht zu den discriminate sind projiziert. Wie sich herausstellt, die discriminate ist die zeilenweise, beginnend bei (0, 0), die gleichzeitig minimiert die Entfernung der projizierten Punkte für jede Klasse und den Abstand zwischen den beiden Gruppen von projizierten Punkt maximiert. Dieses Konzept ist überhaupt nicht offensichtlich.

OK, aber auch, wenn es möglich ist, den discriminate Vektor für einen Satz von Daten zu berechnen, ist noch nicht klar wie die discriminate verwendet werden kann, eine Vorhersage zu treffen. In Abbildung 2, die Lila Raute mit der Bezeichnung "bedeutet" ist der durchschnittliche Datenpunkt bedeutet, dass die zwei-Klasse. Sie können sehen, dass der Mittelwert in der Mitte zwischen den zwei Gruppen von Datenpunkten ist. Nehmen Sie nun eine senkrechte gestrichelte Linie vom Mittelwert Violett auf die grüne discriminate Linie. Die Projektion Zeile würde am zu drücken (5.2, 3.0).

Und nehmen Sie nun eine senkrechte Zeile aus der gelben, zeigen Sie auf die Zeile, grüne discriminate klassifizieren. Da die Projektion des Punkts zum Klassifizieren von auf der linken Seite der Projektion vom Mittelwert liegt, nähert sich die Projektionen bedienen Datenpunkte und wird daher als bedienen klassifiziert. Wenn Sie die Projektion aus unbekannten Zeitpunkt in die discriminate Zeile auf der anderen Seite der Projektion vom Mittelwert zurückgegangen, würde der Punkt so konservativ klassifiziert wurden. Eine sehr raffinierte Idee.

Implementieren von LDA binäre Klassifikation

Die allgemeine Struktur des Demoprogramms mit ein paar WriteLine-Anweisungen entfernt und kleinere Änderungen um Platz zu sparen werden im Abbildung 3. Um das Demoprogramm zu erstellen, wenn ich Visual Studio gestartet und erstellt eine neue C#-Konsolenanwendung namens LinearDiscriminate. Das Demo umfasst keine wichtigen Abhängigkeiten von .NET Version jeder Version von Visual Studio arbeiten, sollten. Nachdem Sie der Code in den Editor geladen, habe ich gelöscht alle using-Anweisungen, mit Ausnahme der einzelnen Verweis auf den System-Namespace der obersten Ebene. Im Projektmappen-Explorer-Fenster, wenn ich LinearDiscriminateProgram.cs Datei Program.cs umbenannt und Visual Studio automatisch die Klasse Program für mich umbenennen zulässig.

Abbildung 3 allgemeine Struktur eines Demo-Programms

using System;
namespace LinearDiscriminate
{
  class LinearDiscriminateProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin LDA demo");
      // All program control statements here
      Console.WriteLine("End LDA demo");
      Console.ReadLine();
    }
    static int Prediction(double[][] data,
      double[] x, double[][] w) { . . }
    static int Prediction(double[][] data,
      double[][] x, double[][] w) { . . }
    static double[][] Mean(double[][] data,
      int c) { . . }
    static double[][] Discriminate(double[][] data,
      bool unitize) { . . }
    static double[][] ScatterWithin(double[][] data) { . . }
    static double[][] Scatter(double[][] data, int c) { . . }
    static double[][] Unitize(double[][] vector) { . . }
    // Matrix helper methods here
  }
} // ns

Das Demoprogramm ist zu lang und hier in seiner Gesamtheit vorhanden, aber Sie finden den vollständigen Quellcode im Download, der diesen Artikel begleitet. Ich verwendete einen Ansatz für die statische Methode anstelle einer objektorientierten Programmiersprache Ansatz.

Die Main-Methode beginnt mit dem hartcodiert acht Element Trainingsdataset in ein Array von Arrays Style-Matrix einrichten:

double[][] data = new double[8][];
data[0] = new double[] { 1.0, 4.0, 0 };
data[1] = new double[] { 2.0, 2.0, 0 };
// Etc. for [2] through [6]
data[7] = new double[] { 9.0, 8.0, 1 };
ShowMatrix(data, 2, true);

In einem Szenario mit nicht-Demo würden Sie wahrscheinlich, dass Daten aus einer Textdatei in den Arbeitsspeicher, die über eine Methode mit dem Namen etwas LoadData wie lesen. Berechnen der discriminate erfolgt folgendermaßen:

double[][] w = Discriminate(data, true);
Console.WriteLine("Discriminate is: ");
ShowMatrix(w, 6, true);

Beachten Sie, dass der Rückgabewert der Discriminate-Methode ein Array von Arrays Matrix statt ein Array ist. Die meisten Vorgänge, die in LDA verwendet werden Matrix-Vorgänge, z. B. Matrixmultiplikation und die Umkehrung der Matrix. Anstelle eines Arrays mit zwei Zellen ist w hier eine Matrix mit zwei Zeilen und eine Spalte. Eine solche Spalte Matrizen werden als Spaltenvektoren bezeichnet. Wenn Sie häufig mit Matrizen arbeiten, kann es anstelle von Arrays mit Freude daran gewöhnt erhalten eine Weile dauern.

In Abbildung 1, sehen Sie, dass mehrere Objekte berechnet und angezeigt werden. Die anzeigeanweisungen befinden sich in der Discriminate-Methode und die Hilfsmethoden und sollen Ihnen LDA zu erleichtern. Sie würden wahrscheinlich die anzeigeanweisungen im Produktionscode entfernen.

Die Anweisungen, die das Element einrichten, um vorherzusagen sind:

double[] x = new double[] { 4.0, 5.0 };
Console.WriteLine("Predicting class for Age Income =");
ShowVector(x, 1);

Aufrufen der Einfachheit halber hier ist das Element, das vorhergesagt, obwohl es später in einer Matrix eine Spalte konvertiert werden muss in einem normalen numerisches Array untergebracht. Die Vorhersage-Anweisungen sind:

int c = Prediction(data, x, w);
Console.Write("Predicted class: " + c);
if (c == 0)
  Console.WriteLine(" (liberal)");
else
  Console.WriteLine(" (conservative)");

Die Vorhersage-Methode akzeptiert der Datenmatrix um den Mittelwert der Mittel zu berechnen, siehe Abbildung 2. Die Methode erfordert auch das Element, um vorherzusagen, X und der discriminate Vektor, w.

Berechnen der Discriminate

Unterscheidung Methode berechnet LDA discriminate Vektor. Der Code ist mit WriteLine und Anzeige-Anweisungen entfernt, überraschend kurz, da die meiste Arbeit erfolgt durch Hilfsmethoden:

static double[][] Discriminate(double[][] data, bool unitize)
{
  double[][] mean0 = Mean(data, 0);
  double[][] mean1 = Mean(data, 1);
  double[][] Sw = ScatterWithin(data);
  double[][] SwInv = MatrixInverse(Sw);
  double[][] diff = MatrixSubtract(mean0, mean1);
  double[][] w = MatrixProduct(SwInv, diff);
  if (unitize == true) return Unitize(w);
  else return w;
}

Die discriminate LDA, Rangordnungs-ist recht komplex, aber die Ergebnisse sind ziemlich einfach. Hilfsmethode Mittelwert berechnet den Mittelwert einer bestimmten Klasse (0 oder 1). Angenommen, die drei Datenelemente, stellen bedienen (0-Klasse) sind (1, 4), (2, 2) und (3, 3). Wird von ihrem Mittelwert ((1 + 2 + 3) / 3, (4 + 2 + 3) / 3) = (2.0, 3.0).

Punktdiagramm in Matrix ist ein Maß, wie Variable DataSet ist. Mit zwei Klasse Mittel, mean0 mean1 und XY in Matrix Sw verfügen ist die discriminate das Produkt die Umkehrung der Software und die Matrix Differenz zwischen mean0 und mean1.

Finden Sie verschiedene Ressourcen im Internet, in denen das Recht komplexe mathematische erläutert, das die Formel für die discriminate abgeleitet wird. Denken Sie daran, dass viele verschiedene Versionen der Ableitung für w vorhanden sind. Insbesondere werden möglicherweise Verweise auf Kovarianz und XY-(Sb) zwischen angezeigt. Kovarianz ist eine mathematische Entität, die XY innerhalb entspricht. Punktdiagramm zwischen ist Unterscheidung einer mathematischen Entität, die in die Ableitung der Gleichung für den LDA verwendet wird, Punkt-zwischen wird jedoch nicht explizit verwendet die discriminate berechnen oder um eine Vorhersage zu treffen.

Unterscheidung-Methode hat einen booleschen Parameter namens unitize, die angibt, ob die discriminate Einheit Länge ist, d. h. eine Länge von 1.0 skalieren. In den meisten Fällen möchten Sie true als entsprechendes Argument übergeben.

Eine Vorhersage

Das Demoprogramm besitzt zwei überladene Methoden der Vorhersage. Die erste akzeptiert das Element, um vorherzusagen, X, als normale numerisches Array:

static int Prediction(double[][] data, double[] x, double[][] w)
{
  double[][] xm = MatrixFromVector(x);
  return Prediction(data, xm, w);
}

Diese Version der Vorhersage wird zum Aufrufen der Einfachheit halber und ist einfach ein Wrapper um die Version des Vorhersagemodell die Arbeit übernimmt:

static int Prediction(double[][] data, double[][] x, double[][] w)
{
  int dim = data[0].Length - 1; // at least 2
  double[][] wT = MatrixTranspose(w); // 1 x d
  double[][] m0 = Mean(data, 0); // d x 1
  double[][] m1 = Mean(data, 1); // d x 1
  double[][] m = MatrixAdd(m0, m1); // d x 1
  m = MatrixProduct(m, 0.5); // d x 1 
  double[][] tc = MatrixProduct(wT, m); // ((1xd)(dx1) = 1 x 1
  double[][] wTx = MatrixProduct(wT, x); // (1xd)(dx1) = 1 x 1
  if (wTx[0][0] > tc[0][0]) return 0; else return 1;
}

Vorhersage-Methode berechnet das Austauschen von w, damit sie in der Matrixmultiplikation verwendet werden kann. Das bedeutet, dass die beiden Klassen werden berechnet und dann der Mittelwert dieser beiden Techniken berechnet, indem der Wert jeder einzelnen Komponente mit 0,5 multipliziert und anschließend in der Matrix m gespeichert ist.

Matrix-Tc ist die Konstante Schwellenwert und ist das Produkt aus dem Austauschen der discriminate Vektor, wT und den Mittelwert der Klasse wird angegeben, m. Matrix Tc werden immer eine 1 x 1-Matrix mit einem einzelnen Wert. Der Wert in der Matrix Tc die Projektion des Mittelwerts auf discriminate Vektor darstellt.

Die Projektion des Elements um vorherzusagen, ist X, klicken Sie auf der discriminate Vektor als das Produkt das Austauschen der discriminate Vektor und x auf ähnliche Weise berechnet. Leider ist, da die Projektion der discriminate kann positiv oder negativ ist, den booleschen Vergleichsoperator verwenden, die kleiner-als oder größer-als Problem zum Problem variiert. Der einfachste Ansatz besteht darin, größer-als zu sehen, ob es Ergebnisse erhalten, die sinnvoll sind. Welcher Operator verwenden, können Sie programmgesteuert ermitteln, aber dieser Ansatz führt zu viel mehr Code, als Sie erwarten.

Eine Option bei der Vorhersage ist die Projektion des Durchschnitts der Klasse Mittel unter Berücksichtigung der Wahrscheinlichkeit jeder Klasse anpassen. Diese Anpassung ist log(p0 / p1), wobei p0 die Wahrscheinlichkeit der Klasse 0 ist und p1 die Wahrscheinlichkeit der Klasse 1 ist. Für den Demodaten p0 = 3/8 = 0,375 und p1 = 5/8 0.625, =, damit die Stufe der Anpassung ist log(0.375 / 0.625) = log(0.6) =-0.22. Beachten Sie, dass die beiden Wahrscheinlichkeiten davon ausgegangen, dass sind gleich, und klicken Sie dann auf p0 = p1 und die Anpassung Faktor wäre log(1) = 0.

Kommentare und Einschränkungen

Es gibt tatsächlich mehrere unterschiedliche Arten von LDA. Die in diesem Artikel vorgestellte heißt in der Regel Fisher LDA. LDA kann auch verwendet werden für die Funktionsauswahl (identifizieren, welche Variablen Vorhersage besonders hilfreich sind, sodass weniger nützlich vorausgesagt ignoriert werden können), sowie die Klassifizierung. Und es ist eine völlig andere statistische LDA (latenten Dirichlet-Verteilung) in natürlicher sprachverarbeitung verwendet.

Binäre Klassifikation LDA hat mathematisch elegant, aber einige wichtige Einschränkungen. Hinter den Kulissen verschiedene Versionen der LDA verschiedene Annahmen, z. B. die Vorhersage-Variablen werden normalerweise verteilt und ähnliche während Kovarianzen haben. In vielen Fällen sind diese Annahmen nicht true. In jedem Fall funktioniert in der Praxis LDA oft sogar ziemlich gut, wenn die mathematische Annahmen erfüllt sind nicht. Eine weitere Einschränkung der Mathematik ist, dass die Umkehrung der Matrix XY innerhalb von LDA berechnet werden muss. Umkehrung der Matrix ist ein sehr kompliziert Prozess und kann leicht fehlschlagen.

Vielleicht ist die größte Beschränkung LDA binäre Klassifikation, es wird davon ausgegangen, dass die beiden Klassen linear getrennt sind. Vage Dies bedeutet, dass im Diagramm wie in Abbildung 2, es ist möglich, eine gerade Linie zu suchen, die die beiden Klassen getrennt. Die Daten für viele Probleme nicht nur linear getrennt.

Meiner Meinung nach LDA binäre Klassifikation ist schön sind alternative Klassifizierung Algorithmen, insbesondere logistischen Regression-Klassifikation und Klassifizierung durch neuronales Netz, die praktikabler sind. Aber LDA sicher interessant ist.

Dr. James McCaffrey ist in Redmond (Washington) für Microsoft Research tätig. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und Bing. Dr. McCaffrey erreichen Sie unter jammc@microsoft.com.

Unser Dank gilt den folgenden technischen Experten von Microsoft Research für die Durchsicht dieses Artikels: Madison Minsk und Amy Shan