Juli 2015

Band 30, Nummer 7

Test Run – Lineare Regression mit C#

Von James McCaffrey

Das Ziel eines linearen Regressionsproblems ist es, den Wert einer numerischen Variablen anhand der Werte von einer oder mehreren numerischen Vorhersagevariablen vorherzusagen. Sie möchten z. B. das jährliche Einkommen einer Person vorhersagen, basierend auf deren Bildungsgrad, der Berufserfahrung in Jahren und ihrem Geschlecht (männlich = 0, weiblich = 1).

Die vorherzusagende Variable wird in der Regel als "abhängige Variable" bezeichnet. Die Vorhersagevariablen werden in der Regel als "unabhängige Variablen" bezeichnet. Wenn es nur eine einzelne Vorhersagevariable gibt, wird das Verfahren auch als einfache lineare Regression bezeichnet. Wenn es zwei und mehr Vorhersagevariablen gibt, wird das Verfahren generell als multiple oder multivariate lineare Regression bezeichnet.

Ich empfehle Ihnen, sich das Demoprogramm in Abbildung 1 anzusehen. Dort erfahren Sie, um was es bei diesem Artikel geht. Das C#-Demoprogramm sagt das Jahreseinkommen auf Basis von Bildung, Arbeit und Geschlecht vorher. Das Demoprogramm generiert als Erstes 10 synthetische Datenelemente. Bildungsgrad ist ein Wert zwischen 12 und 16. Berufserfahrung ist ein Wert zwischen 10 und 30. Geschlecht ist eine Indikatorvariable, mit "männlich" als Referenzwert, codiert als 0, und "weiblich" codiert als 1. Das Einkommen, in der Einheit "tausend Dollar", befindet sich in der letzten Spalte. In einem nicht als Demonstration gedachten Szenario würden Sie wahrscheinlich Daten aus einer Textdatei mit einer Methode mit einem Namen wie MatrixLoad einlesen.

Abbildung 1 Lineare Regression mit C#

Nach dem Generieren der synthetischen Daten verwendet das Demoprogramm die Daten zum Erstellen einer sogenannten Designmatrix. Eine Designmatrix ist lediglich die Datenmatrix mit einer zusätzlichen, führenden Spalte, die alle 1.0-Werte enthält. Es gibt zahlreiche verschiedene Algorithmen, die für die lineare Regression verwendet werden können. Einige davon können die Rohdatenmatrix verwenden, während andere eine Designmatrix verwenden. Das Demoprogramm verwendet eine Methode, die eine Designmatrix erfordert.

Nach dem Erstellen der Designmatrix sucht das Demoprogramm die Werte für vier Koeffizienten (12.0157, 1.0180, 0.5489,-2.9566). Die Koeffizienten werden manchmal auch als b- oder Beta-Werte bezeichnet. Der erste Wert, 12.0157, wird normalerweise als "konstantes Glied", auch Regressionskonstante, bezeichnet. Es handelt sich um eine Konstante, die keiner Vorhersagevariablen zugeordnet ist. Der zweite, dritte und vierte Koeffizientenwert (1.0180, 0.5489,-2.9566) sind jeweils dem Bildungsgrad, der Berufserfahrung und dem Geschlecht zugeordnet.

Der letzte Teil der Ausgabe in Abbildung 1 verwendet die Werte der Koeffizienten, um das Einkommen für eine hypothetische Person vorherzusagen, die über einen Bildungsgrad von 14 und 12 Jahre Berufserfahrung verfügt, und deren Geschlecht 0, also männlich, ist. Das vorhergesagte Einkommen beträgt 32.86, was wie folgt berechnet wird:

income = 12.0157 + (1.0180)(14) + (0.5489)(12) + (-2.9566)(0)
                = 12.0157 + 14.2520 + 6.5868 + 0
                = 32.86

Mit anderen Worten, um eine Vorhersage mittels linearer Regression zu treffen, werden die Vorhersagewerte mit ihren entsprechenden Koeffizientenwerten multipliziert und summiert. Das ist ganz einfach. Beachten Sie, dass der führende Regressionskonstantenwert (im Beispiel 12.0157) als ein Koeffizient betrachtet werden kann, der einer Vorhersagevariablen zugeordnet ist, die immer den Wert 1 hat. Diese Tatsache erklärt teilweise die Spalte mit 1.0-Werten in der Designmatrix.

Das Wesentliche eines linearen Regressionsproblems ist die Berechnung der Werte der Koeffizienten mithilfe der Rohdaten bzw. entsprechend mit der Designmatrix. Dies ist nicht ganz einfach. Das Demoprogramm verwendet ein Verfahren, das als geschlossene Form der Matrizeninversion bezeichnet wird, auch bekannt als Methode der (gewöhnlichen) kleinsten Quadrate (OLS, Ordinary Least Squares). Alternative Verfahren zum Bestimmen der Werte der Koeffizienten sind unter anderem iterative gewichtete kleinste Quadrate, Maximum-Likelihood-Schätzung (maximale Wahrscheinlichkeit), Ridge-Regression, Gradientenabstieg und viele andere.

In Abbildung 1, bevor die Vorhersage getroffen wird, berechnet das Demoprogramm eine Metrik namens "Bestimmtheitsmaß" (R-squared), die auch als "Bestimmtheits- oder Determinationskoeffizient" bezeichnet wird. Das Bestimmtheitsmaß ist ein Wert zwischen 0 und 1, der beschreibt, wie gut das Vorhersagemodell den Rohdaten entspricht. Dies wird manchmal in der Form ausgedrückt "der Prozentsatz der Variation, der durch das Modell erklärt wird". Grob interpretiert könnte man sagen, je näher das Bestimmtheitsmaß bei 1 liegt, desto besser ist das Vorhersagemodell. Der Demowert 0.7207 (oder 72 %) würde für reale Daten als relativ hoch (gut) angesehen.

Dieser Artikel geht davon aus, dass Sie über mindestens fortgeschrittene C#-Programmierkenntnisse verfügen, aber er nimmt nicht an, dass Sie irgendetwas über lineare Regression wissen. Das Demoprogramm ist zu lang, um es im Ganzen darzustellen, aber der vollständige Quellcode ist in dem Download enthalten, der zu diesem Artikel gehört.

Grundlegendes zur linearen Regression

Lineare Regression lässt sich in der Regel am besten mit einem Diagramm erläutern. Betrachten Sie den Graph in Abbildung 2. Die Daten in dem Graph stellen Vorhersagen von Jahreseinkommen auf Grundlage einer einzigen Variablen dar, nämlich "Jahre Berufserfahrung". Jeder der roten Punkten entspricht einem Datenpunkt. Für das äußerste linke Datenelement gilt beispielsweise "Arbeit = 10" und "Einkommen = 32.06". Die lineare Regression bestimmt zwei Koeffizienten: eine Regressionskonstante und einen für die Arbeitsvariable. Wie sich herausstellt, sind die Werte der Koeffizienten 27.00 und 0.43.

Abbildung 2 Lineare Regression mit einer unabhängigen Variablen

Die Koeffizientenwerte bestimmen die Gleichung einer Linie, die in Abbildung 2 in Blau dargestellt ist. Die Linie (die Koeffizienten) minimieren die Summe der quadrierten Abweichungen zwischen den tatsächlichen Datenpunkten (yi) und den vorhergesagten Datenpunkte (fi). Zwei der 10 Abweichungen sind mit gestrichelten Linien in Abbildung 2 dargestellt. Die erste angezeigte Abweichung ist yi - fi = 28.6 - 32.6 = -4.0. Beachten Sie, dass Abweichungen positiv oder negativ sein können. Wenn die Abweichungen nicht quadriert würden, könnten sich die negativen und positiven Werte gegenseitig aufheben.

Der Graph in Abbildung 2 zeigt, wie einfach eine lineare Regression mit nur einer unabhängigen Variablen funktioniert. Die multivariate lineare Regression erweitert dieselbe Idee – also das Bestimmen von Koeffizienten, die die Summe der quadrierten Abweichungen minimieren – mithilfe mehrerer unabhängiger Variablen.

Intuitiv ausgedrückt bestimmt die linearer Regression die beste Linie durch einen Satz von Datenpunkten. Diese beste Linie kann für Vorhersagen verwendet werden. Wen beispielsweise in Abbildung 2 eine hypothetische Person 25 Jahren Berufserfahrung hätte, wäre ihr vorhergesagtes Einkommen auf der blauen Linie etwa 38.

Lösen der Gleichung der kleinsten Quadrate

Wenn ein lineares Regressionsproblem n Vorhersagevariablen hat, müssen n+1 Koeffizientenwerte gefunden werden, einer für jeden Vorhersagewert plus den Regressionskonstantenwert. Das Demoprogramm verwendet das einfachste Verfahren, um die Werte der Koeffizienten zu bestimmen. Die Werte der Koeffizienten werden häufig durch die etwas einschüchternde Gleichung in Abbildung 3 angegeben. Die Gleichung ist nicht so kompliziert, wie es zunächst den Anschein hat.

Abbildung 3 Lösung linearer Regressionskoeffizienten mit Matrizen

Der griechische Buchstabe Beta ähnelt einem ß ("sz") und stellt die Werte der Koeffizienten dar. Beachten Sie, dass alle Buchstaben in der Gleichung in Fettdruck sind, was in der Mathematik anzeigt, dass sie mehrwertige Objekte (Matrizen oder Arrays/Vektoren) darstellen statt einfacher skalarer Werte (einfache Zahlen). Der Großbuchstaben X steht für die Designmatrix. Der Großbuchstabe X mit einem T-Exponenten steht für die transponierte Designmatrix. Das *-Symbol bedeutet Matrixmultiplikation. Der Exponent -1 bedeutet Matrixinversion. Der Großbuchstabe Y ist ein Spaltenvektor (eine Matrix mit einer Spalte) der abhängigen Variablenwerte. Daher bedeutet das Auflösen nach Koeffizientenwerten tatsächlich das Verstehen von Matrixoperationen.

Die Diagramme in Abbildung 4 illustrieren die Matrixtransposition, Matrixmultiplikation und Matrixinversion. Beim Transponieren einer Matrix werden lediglich Zeilen und Spalten vertauscht. Angenommen, wir haben beispielsweise eine 2x3-Matrix, d. h. eine mit 2 Zeilen und 3 Spalten. Die transponierte Matrix wäre dann 3x2, wobei die Zeilen der ursprünglichen Matrix zu den Spalten der transponierten Matrix werden.

Abbildung 4 Einsatz von drei Matrixoperationen zum Bestimmen linearer Regressionskoeffizienten

Matrixmultiplikation erscheint vielleicht etwas merkwürdig, wenn Sie vorher noch nichts damit zu tun hatten. Wenn Sie eine Matrix der Dimensionen (n x m) mit einer Matrix der Dimensionen (m x p) multiplizieren, ist das Ergebnis eine Matrix mit den Dimensionen (n x p). Beispielsweise ergibt eine 3x4-Matrix * einer 4x2-Matrix eine 3x2-Matrix. Eine detaillierte Erläuterung der Matrixmultiplikation würde den Rahmen dieses Artikels sprengen, aber sobald Sie einige Beispiele gesehen haben, ist der Prozess leicht verständlich und einfach in Code zu implementieren.

Die dritte Matrixoperation für das Auflösen nach linearen Regressionskoeffizientenwerten ist die Matrixinversion, die leider schwer zu verstehen und schwierig zu implementieren ist. Für die Zwecke dieses Artikels ist es ausreichend zu wissen, dass das Inverse einer Matrix nur definiert ist, wenn die Matrix dieselbe Anzahl von Zeilen und Spalten hat (eine quadratische Matrix ist). Abbildung 4 zeigt eine 3x3-Matrix und ihr Inverses.

Es gibt mehrere Algorithmen, die zum Bestimmen des Inversen einer Matrix verwendet werden können. Das Demoprogramm verwendet ein Verfahren namens "Doolittle-Zerlegung".

Zusammenfassend lässt sich sagen, dass ein lineares Regressionsproblem mit n Vorhersagevariablen das Bestimmen der Werte für n+1 Koeffizienten umfasst. Dies kann mithilfe von Matrizen und Matrixtransposition, Matrixmultiplikation und Matrixinversion ausgeführt werden. Transposition und Multiplikation sind einfach, doch das Bestimmten des Inversen einer Matrix ist schwierig.

Struktur des Demoprogramms

Um das Demoprogramm zu erstellen, habe ich Visual Studio gestartet und die Projektvorlage "Konsolenanwendung" ausgewählt. Das Projekt habe ich "LinearRegression" genannt. Das Programm hat keine nennenswerten .NET Framework-Abhängigkeiten, sodass jede Version von Visual Studio funktionieren sollte.

Nachdem der Vorlagencode in den Editor im Solution Explorer-Fenster geladen wurde, habe ich mit der rechten Maustaste auf die Datei "Program.cs" geklickt und sie in "LinearRegressionProgram.cs" umbenannt. Daraufhin habe ich Visual Studio automatisch die Programmklasse umbenennen lassen. Am oberen Rand des Editorfensters habe alle "using"-Anweisungen gelöscht, mit Ausnahme der einen, die auf den Namespace der obersten Ebene, "System", verweist.

Die Gesamtstruktur des Demoprogramms, mit ein paar kleinen Änderungen, um Platz zu sparen, ist in Abbildung 5 dargestellt. Die gesamte Programmsteuerungslogik ist in der Methode "Main" enthalten. Das Demoprogramm verwendet einen Ansatz mit statischen Methoden anstelle eines OOP-Ansatzes.

Abbildung 5 Struktur des Demoprogramms für lineare Regression

using System;
namespace LinearRegression
{
  class LinearRegressionProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin linear regression demo");
      // Generate synthetic data
      // Create design matrix
      // Solve for LR coefficients
      // Calculate R-squared value
      // Do a prediction
      Console.WriteLine("End linear regression demo");
      Console.ReadLine();
    }
    static double Income(double x1, double x2,
      double x3, double[] coef) { . . }
    static double RSquared(double[][] data,
      double[] coef) { . . }
    static double[][] DummyData(int rows,
      int seed) { . . }
    static double[][] Design(double[][] data) { . . }
    static double[] Solve(double[][] design) { . . }
    static void ShowMatrix(double[][] m, int dec) { . . }
    static void ShowVector(double[] v, int dec) { . . }
    // ----------
    static double[][] MatrixTranspose(double[][] matrix)
      { . . }
    static double[][] MatrixProduct(double[][] matrixA,
      double[][] matrixB) { . . }
    static double[][] MatrixInverse(double[][] matrix)
      { . . }
    // Other matrix routines here
  }
} // ns

Die Methode "Income" gibt ein vorhergesagtes Einkommen aus Eingabeparametern mit Werten für Bildungsgrad, Berufserfahrung und Geschlecht zurück, wobei ein Array aus Koeffizientenwerten verwendet wird. Die Methode "RSquared" gibt den Wert des Bestimmtheitsmaßes des Modells aus den Daten und den Koeffizienten zurück. Die Methode "DummyData" generiert die synthetischen Daten, die für das Demoprogramm verwendet werden.

Die Methode "Design" akzeptiert eine Matrix aus Daten und gibt eine erweiterte Designmatrix mit einer führenden Spalte mit 1.0-Werten zurück. Die Methode "Solve" akzeptiert eine Designmatrix und verwendet Matrixoperationen zum Bestimmen der linearen Regressionskoeffizienten.

Die meiste harte Arbeit wird von einem Satz statischer Methoden erledigt, die Matrixoperationen durchführen. Das Demoprogramm definiert eine Matrix auf die einfachste Weise als Array von Arrays. Eine Alternative besteht darin, eine programmatisch definierte Matrixklasse zu erstellen, aber meiner Meinung nach, ist diese Herangehensweise unnötig kompliziert. Manchmal sind normale Arrays besser als programmatisch definierte Objekte.

Die Methode "MatrixTranspose" gibt die Transposition einer Matrix zurück. Die Methode "MatrixProduct" gibt das Ergebnis der Multiplikation zweier Matrizen zurück. Die Methode "MatrixInverse" gibt das Inverse einer Matrix zurück. Das Demoprogramm beinhaltet viele Hilfsmethoden. Insbesondere die Methode "MatrixInverse" ruft die Hilfsmethoden "MatrixDuplicate", "MatrixDecompose" und "HelperSolve" auf.

Die Methode "Solve"

Das Herzstück des Demoprogramms für lineare Regression ist die Methode "Solve". Die Definition der Methode beginnt folgendermaßen:

static double[] Solve(double[][] design)
{
  int rows = design.Length;
  int cols = data[0].Length;
  double[][] X = MatrixCreate(rows, cols - 1);
  double[][] Y = MatrixCreate(rows, 1);
...

Der einzelne Eingabeparameter ist eine Designmatrix. Ein alternativer Ansatz, den Sie in Erwägung ziehen können, besteht darin, die Quelldatenmatrix zu übergeben und dann "Solve" die Hilfsmethode "Design" aufrufen zu lassen, um die Designmatrix zu erhalten. Die Hilfsmethode "MatrixCreate" reserviert Speicherplatz für eine Matrix mit der angegebenen Anzahl von Zeilen und Spalten und gibt eine solche zurück. Die lokale X-Matrix enthält die Werte der unabhängigen Variablen (mit vorangestelltem 1.0-Wert). Die lokale Y-Matrix hat nur eine Spalte und enthält die Werte der abhängigen Variablen (Jahreseinkommen im Demoprogramm).

Als Nächstes werden die Zellen in den Matrizen X und Y unter Verwendung der Werte in der Designmatrix aufgefüllt:

int j;
for (int i = 0; i < rows; ++i)
{
  for (j = 0; j < cols - 1; ++j)
  {
    X[i][j] = design[i][j];
  }
  Y[i][0] = design[i][j]; // Last column
}

Beachten Sie, dass die Indexvariable "j" außerhalb der geschachtelten for-Schleifen deklariert ist, damit sie zum Auffüllen der Y-Matrix verwendet werden kann. Mit den vorliegenden X- und Y-Matrizen können die linearen Regressionskoeffizienten gemäß der Gleichung in Abbildung 3 bestimmt werden:

...
  double[][] Xt = MatrixTranspose(X);
  double[][] XtX = MatrixProduct(Xt, X);
  double[][] inv = MatrixInverse(XtX);
  double[][] invXt = MatrixProduct(inv, Xt);
  double[][] mResult = MatrixProduct(invXt, Y);
  double[] result = MatrixToVector(mResult);
  return result;
} // Solve

Im Demoprogramm hat Matrix X die Größe 10x4, sodass ihre Transposition Xt die Größe 4x10 hat. Das Produkt aus Xt und X hat die Größe 4x4, und das Inverse hat ebenfalls die Größe 4x4. Im Allgemeinen müssen Sie bei einem linearen Regressionsproblem mit n unabhängigen Vorhersagevariablen, wenn Sie das Matrixinversionsverfahren verwenden, das Inverse einer Matrix mit der Größe (n+1) x (n+1) bestimmen. Dies bedeutet, dass das Inversionsverfahren Technik nicht für lineare Regressionsprobleme geeignet ist, die eine sehr große Zahl von Vorhersagevariablen besitzen.

Das Produkt aus der 4x4-Inversmatrix und der transponierten 4x10-Transpositionsmatrix, im Code "InvXt", hat die Größe 4x10. Das Produkt aus InvXt und der 10x1-Y-Matrix, im Code "mResult" ("Matrixergebnis"), hat die Größe 4x1. Diese Werte sind die Koeffizienten, die Sie benötigen. Der Einfachheit halber werden die Werte in der einspaltigen Y-Matrix mit der Hilfsmethode "MatrixToVector" in ein normales Array übertragen.

Berechnen des Bestimmtheitsmaßes

Wie zuvor erwähnt, ist die Metrik "Bestimmtheitsmaß" ein Maß dafür, wie gut die tatsächlichen Datenpunkte der berechneten Regressionslinie entsprechen. Mathematisch ausgedrückt ist das Bestimmtheitsmaß definiert als R2 = 1 - (SSres/SStot). Der Term "SSres" heißt in der Regel die "Summer der quadrierten Residuen." Es handelt sich dabei um Summe der quadrierten Differenzen zwischen den tatsächlichen Y-Werten und den vorhergesagten Y-Werten, wie im Graph in Abbildung 2 dargestellt. Der Term "SStot" ist "Gesamtsumme der Quadrate". Es handelt sich hierbei um die Summe der quadrierten Differenzen zwischen jedem tatsächlichen Y-Wert und dem Mittelwert (Durchschnitt) aller tatsächlichen Y-Werte.

Die Metrik "Bestimmtheitsmaß" (R-squared) wird bei der linearen Regression auch als "Determinationskoeffizient" bezeichnet und steht im Zusammenhang mit einer anderen statistischen Kennzahl namens "r-squared" ("kleines" r-squared), ist aber nicht identisch damit. Die Interpretation des Bestimmtheitsmaßes ist etwas schwieriger und hängt von der spezifischen Problemdomäne ab, die untersucht wird. In den Natur- und Sozialwissenschaften, in denen Daten in der Regel unstrukturiert und unvollständig sind, wird ein Wert von 0.6 oder größer häufig als ziemlich gut angesehen.

Es gibt ein alternatives Maß der durch das Regressionsmodell erklärten Varianz, das als "angepasstes Bestimmtheitsmaß" bezeichnet wird. Diese Metrik berücksichtigt die Anzahl der Vorhersagevariablen und die Anzahl der Datenelemente. Für die meisten Zwecke ist die Verwendung des einfachen Bestimmtheitsmaßwerts gut genug, um eine Vorstellung von der Vorhersagequalität eines linearen Regressionsmodells zu bekommen.

Zusammenfassung

Wenn Sie im Internet nach Beispielen suchen, wie eine lineare Regression mithilfe einer Programmiersprache ausgeführt wird, werden Sie nicht viele Referenzen finden. Ich glaube, es gibt zwei Hauptgründe für diesen relativen Mangel an Informationen. Erstens ist das Auflösen nach linearen Regressionskoeffizienten mithilfe von Matrixoperationen ziemlich schwierig, größtenteils wegen der Matrixinversionsoperation. In gewisser Hinsicht betrachte ich die Methode "MatrixInverse" des Demoprogramms als eine der kompliziertesten Coderoutinen, die ich je geschrieben habe. Zweitens gibt es jede Menge vorhandene, eigenständige Tools, die eine lineare Regression ausführen können, insbesondere das Tabellenkalkulationsprogramm Excel mit seinem Datenanalyse-Add-In. Es ist relativ selten erforderlich, Projektmappencode für lineare Regression direkt in ein Softwaresystem einzubetten.

Die lineare Regression wird bereits seit Jahrzehnten untersucht, und es gibt viele Möglichkeiten, um das Verfahren zu erweitern. Sie können z. B. sogenannte Interaktionseffekte einführe, die zwei oder mehr Vorhersagevariablen kombinieren. Diese Erweiterungen werden manchmal auch als "allgemeine lineare Modelle" bezeichnet, um sie von der grundlegenden Form der linearen Regression zu unterscheiden.

Meiner Meinung nach ist die linearer Regression das "Hello World"-Verfahren der klassischen Statistik. Es gibt keine klare, allgemein anerkannte Unterscheidung zwischen der klassischen Statistik und dem Machine Learning, aber ich tendiere dazu, die klassischen statistischen Verfahren als solche anzusehen, die zuerst von Mathematikern seit dem frühen Beginn des 20. Jahrhunderts untersucht wurden. Meiner Meinung nach sind Machine Learning-Verfahren wie die Klassifikation mittels neuronaler Netze solche, die jüngeren Ursprungs und erst in den 50er-Jahren aufgetaucht sind. Die lineare Regression der klassischen Statistik ist eng mit einem Machine Learning-Verfahren namens "logistische Regression" verwandt, das bereits Thema mehrerer Test Run-Kolumnen gewesen 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: Charles Parker