Juni 2019

Band 34, Nummer 6

Dieser Artikel wurde maschinell übersetzt.

[Test Run]

Vereinfachte naive Bayes-Klassifikation mit C#

Durch James McCaffrey | Juni 2019 | Code abrufen

James McCaffreyDas Ziel ein Naive Bayes-klassifizierungsproblem ist um einen diskreten Wert vorherzusagen. Beispielsweise möchten Sie die Echtheit des eine Gemstone basierend auf der Farbe, Größe und Form Vorhersagen (0 = Fake, 1 = authentisch). In diesem Artikel ich zeigen, wie Sie implementiert eine vereinfachte Naive Bayes-Klassifizierung 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. Das Demoprogramm richtet 40 dummydatenelementen ab. Jedes Element verfügt über drei prädiktorwerte: Farbe ("Aqua", "Blau", "Cyan", "Düne"), Größe (klein, groß) und Form (Pointed, gerundet, Twisted), gefolgt von einem binären vorherzusagenden Klasse zu (0 oder 1).

Vereinfachte Naive Bayes-Klassifizierung: Demoausführung
Abbildung 1 vereinfacht Naive Bayes-Klassifizierung: Demoausführung

Die Demo richtet ein Element, um vorherzusagen: (Zyan, Small, Verdrehte). Naive Bayes-Klassifikation basiert auf Wahrscheinlichkeiten, die wiederum auf die Zahlen in den Daten basieren. Das Demoprogramm überprüft die 40-Item-Dataset berechnet und zeigt sechs joint Counts: Elemente, die sowohl Cyan und 0 (3 Elemente), Cyan und 1 (5), klein und 0 (18), klein und 1 (15), Twisted und 0 (5), Twisted und 1 (3). Die Demo zählt auch die Anzahl der Elemente der Klasse 0 (24) und Klasse 1-Elemente (16).

Verwenden die Informationen, die Demo berechnet intermediate Werte, die Beweise Begriffe (0.0082, 0.0131) wird aufgerufen, und klicken Sie dann die Beweise Begriffe verwendet, um Pseudo-Wahrscheinlichkeiten ("0.3855", "0.6145") zu berechnen, die Vorhersagen der Klasse 0 und Klasse 1 entsprechen. Da die zweite Pseudo-Wahrscheinlichkeit größer, die Lösung besteht darin, die (Zyan, kleine, Twisted) ist 1-Klasse.

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 Naive Bayes-Klassifikation. 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 Naive Bayes-Klassifikation

Naive Bayes-Klassifikation wird sowohl einfache als auch kompliziert. Implementierung ist relativ einfach, aber die zugrunde liegende Mathematik Ideen sind sehr komplex. Es gibt viele verschiedene mathematische Gleichungen für die, die Naive Bayes-Klassifikation definieren. Drei Beispiele im abbildung2. Buchstaben P ist die Wahrscheinlichkeit; CK ist eine der k-Klassen (0, 1, 2,...); Das Pipe-Symbol wird "deshalb"; gelesen. und X ist ein Vektor der Eingabewerten vornimmt, z. B. (Zyan, kleine, Twisted). Diese Gleichungen leider bereit nicht viel Hilfe, bei der Naive Bayes-Klassifikation erst nach dem implementieren die Technik verstehen.

Drei Formen von Naive Bayes-Klassifizierung Math
Abbildung 2 drei Formen von Naive Bayes-Klassifizierung Math

Meiner Meinung nach ist Naive Bayes-Klassifikation am besten anhand eines konkreten Beispiels erläutert. Der erste Schritt ist, suchen Sie in den Quelldaten und Berechnen der joint Counts. Wenn es Nx prädiktorvariablen (drei in der Demo) und nc-Klassen (zwei in der Demo), stehen Nx * nc Joint zählt, um zu berechnen. Beachten Sie, dass es sich bei der Zählung Prozess bedeutet, dass prädiktor Daten anstatt numerische diskrete müssen.

Nach dem Berechnen der joint Counts, wird jede Anzahl 1 hinzugefügt. Dies heißt Laplace-Glättung und erfolgt, um zu verhindern, dass jedem joint Count 0 (null) und die Ergebnisse des letzten NULL würde. Für die Demodaten sind der geglätteten joint Counts:

cyan and 0:     2 + 1 = 3
cyan and 1:     4 + 1 = 5
small and 0:   17 + 1 = 18
small and 1:   14 + 1 = 15
twisted and 0:  4 + 1 = 5
twisted and 1:  2 + 1 = 3

Als Nächstes werden die unformatierten Anzahl der Elemente der Klasse 0 und Klasse 1 Elemente berechnet. Faktor ist erforderlich, da diese Werte immer größer als 0 (null), ohne Glättung werden. Für die Demodaten sind die Anzahl der Klasse:

0:  24
1:  16

Als Nächstes wird ein Evidence-Term für jede Klasse berechnet. Für Klasse 0 (null) den Evidence-Term ist:

Z(0) = (3 / 24+3) * (18 / 24+3) * (5 / 24+3) * (24 / 40)
        = 3/27 * 18/27 * 5/27 * 24/40
        = 0.1111 * 0.6667 * 0.1852 * 0.6
        = 0.0082

Verwenden Sie die ersten drei Bedingungen, der Berechnung für Z(0) der geglätteten joint Counts für Klasse 0 (null), der geteilt durch die Anzahl von Klassen für 0 (24) zuzüglich der Anzahl der vorhersagevariablen (Nx = 3), für die drei Ergänzungen 1 aufgrund der Laplace-Glättung zu kompensieren. Der vierte Ausdruck ist P (Klasse 0). Die Berechnung von der Klasse 1 Evidence-Term folgt demselben Muster:

Z(1) = (5 / 16+3) * (15 / 16+3) * (3 / 16+3) * (16 / 40)
        = 5/19 * 15/19 * 3/19 * 16/40
        = 0.2632 * 0.7895 * 0.1579 * 0.4
        = 0.0131

Der letzte Schritt ist Pseudo-Wahrscheinlichkeiten zu berechnen:

P(class 0) = Z(0) / (Z(0) + Z(1))
                 = 0.0082 / (0.0082 + 0.0131)
                 = 0.3855
P(class 1) = Z(1) / (Z(0) + Z(1))
                 = 0.0131 / (0.0082 + 0.0131)
                 = 0.6145

Die Summe der Nenner ist den Beweis bezeichnet und wird verwendet, um den Beweis Bedingungen normalisieren, damit sie die Summe 1,0 und lose als Wahrscheinlichkeiten interpretiert werden können. Beachten Sie, dass wenn Sie nur Vorhersage interessiert sind, können Sie einfach den größten Evidence-Term verwenden und überspringen normalisierungsschritt der Beweise.

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 NaiveBayes. Ich habe Visual Studio 2017 verwendet, aber die Demo hat keine nennenswerten .NET Framework-Abhängigkeiten, sodass jede Version von Visual Studio funktionieren sollte.

Abbildung 3: das Demoprogramm für Naive Bayes-Klassifizierung

using System;
using System.IO;
namespace CSharp
{
  class Program
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin simple naive Bayes demo\n");
      string fn = "C:\\NaiveBayes\\data.txt";
      int nx = 3;  // Number predictor variables
      int nc = 2;  // Number classes
      int N = 40;  // Number data items
      string[][] data = LoadData(fn, N, nx+1, ',');
      Console.WriteLine("Training data:");
      for (int i = 0; i < 5; ++i) {
        Console.Write("[" + i + "] ");
        for (int j = 0; j < nx+1; ++j) {
          Console.Write(data[i][j] + " ");
        }
        Console.WriteLine("");
      }
      Console.WriteLine(". . . \n");
      int[][] jointCts = MatrixInt(nx, nc);
      int[] yCts = new int[nc];
      string[] X = new string[] { "Cyan", "Small", "Twisted" };
      Console.WriteLine("Item to classify: ");
      for (int i = 0; i < nx; ++i)
        Console.Write(X[i] + " ");
      Console.WriteLine("\n");
      // Compute joint counts and y counts
      for (int i = 0; i < N; ++i) {
        int y = int.Parse(data[i][nx]);
        ++yCts[y];
        for (int j = 0; j < nx; ++j) {
          if (data[i][j] == X[j])
            ++jointCts[j][y];
        }
      }
      // Laplacian smoothing
      for (int i = 0; i < nx; ++i)
        for (int j = 0; j < nc; ++j)
          ++jointCts[i][j];
      Console.WriteLine("Joint counts: ");
      for (int i = 0; i < nx; ++i) {
        for (int j = 0; j < nc; ++j) {
          Console.Write(jointCts[i][j] + " ");
        }
        Console.WriteLine("");
      }
      Console.WriteLine("\nClass counts: ");
      for (int k = 0; k < nc; ++k)
        Console.Write(yCts[k] + " ");
      Console.WriteLine("\n");
      // Compute evidence terms
      double[] eTerms = new double[nc];
      for (int k = 0; k < nc; ++k) {
        double v = 1.0;
        for (int j = 0; j < nx; ++j) {
          v *= (double)(jointCts[j][k]) / (yCts[k] + nx);
        }
        v *= (double)(yCts[k]) / N;
        eTerms[k] = v;
      }
      Console.WriteLine("Evidence terms:");
      for (int k = 0; k < nc; ++k)
        Console.Write(eTerms[k].ToString("F4") + " ");
      Console.WriteLine("\n");
      double evidence = 0.0;
      for (int k = 0; k < nc; ++k)
        evidence += eTerms[k];
      double[] probs = new double[nc];
      for (int k = 0; k < nc; ++k)
         probs[k] = eTerms[k] / evidence;
      Console.WriteLine("Probabilities: ");
      for (int k = 0; k < nc; ++k)
        Console.Write(probs[k].ToString("F4") + " ");
      Console.WriteLine("\n");
      int pc = ArgMax(probs);
      Console.WriteLine("Predicted class: ");
      Console.WriteLine(pc);
      Console.WriteLine("\nEnd naive Bayes ");
      Console.ReadLine();
    } // Main
    static string[][] MatrixString(int rows, int cols)
    {
      string[][] result = new string[rows][];
      for (int i = 0; i < rows; ++i)
        result[i] = new string[cols];
      return result;
    }
    static int[][] MatrixInt(int rows, int cols)
    {
      int[][] result = new int[rows][];
      for (int i = 0; i < rows; ++i)
        result[i] = new int[cols];
      return result;
    }
    static string[][] LoadData(string fn, int rows,
      int cols, char delimit)
    {
      string[][] result = MatrixString(rows, cols);
      FileStream ifs = new FileStream(fn, FileMode.Open);
      StreamReader sr = new StreamReader(ifs);
      string[] tokens = null;
      string line = null;
      int i = 0;
      while ((line = sr.ReadLine()) != null)  {
        tokens = line.Split(delimit);
        for (int j = 0; j < cols; ++j)
          result[i][j] = tokens[j];
        ++i;
      }
      sr.Close(); ifs.Close();
      return result;
    }
    static int ArgMax(double[] vector)
    {
      int result = 0;
      double maxV = vector[0];
      for (int i = 0; i < vector.Length; ++i) {
        if (vector[i] > maxV) {
          maxV = vector[i];
          result = i;
        }
      }
      return result;
    }
  } // Program
} // ns

Nachdem der Vorlagencode geladen, im Editor-Fenster ich alle nicht benötigten Namespaceverweise entfernt und einen Verweis auf die System.IO-Namespace hinzugefügt. Im Fenster Projektmappen-Explorer mit der rechten Maustaste auf die Datei "Program.cs" ich, den aussagekräftigeren NaiveBayesProgram.cs umbenannt und Visual Studio automatisch die Program-Klasse umbenennen zulässig.

Nach dem Erstellen des Projekts ich mit der Editor die 40-Item dummy-Datendatei mit dem Inhalt, dargestellt erstellt Abbildung 4, und klicken Sie im Stammverzeichnis Projekts als BayesData.txt gespeichert.

Abbildung 4 BayesData.txt Dateiinhalt

Aqua,Small,Twisted,1
Blue,Small,Pointed,0
Dune,Large,Rounded,0
Dune,Small,Rounded,1
Cyan,Large,Rounded,0
Aqua,Small,Rounded,1
Aqua,Small,Rounded,0
Cyan,Small,Pointed,1
Cyan,Small,Pointed,1
Dune,Small,Rounded,1
Dune,Small,Rounded,0
Dune,Small,Rounded,1
Dune,Small,Rounded,1
Cyan,Small,Pointed,1
Dune,Small,Rounded,1
Dune,Large,Rounded,0
Cyan,Small,Twisted,1
Blue,Small,Rounded,0
Aqua,Small,Pointed,1
Aqua,Small,Pointed,1
Dune,Small,Twisted,0
Blue,Small,Rounded,0
Dune,Small,Rounded,0
Blue,Small,Twisted,0
Dune,Small,Rounded,0
Aqua,Large,Pointed,1
Dune,Large,Rounded,0
Dune,Small,Rounded,0
Dune,Small,Rounded,0
Cyan,Large,Rounded,0
Dune,Small,Twisted,0
Dune,Large,Twisted,0
Dune,Small,Rounded,0
Dune,Small,Rounded,0
Dune,Large,Rounded,0
Aqua,Large,Rounded,1
Aqua,Small,Rounded,0
Aqua,Small,Rounded,1
Dune,Small,Rounded,0
Blue,Small,Rounded,0

Laden der Daten in den Arbeitsspeicher

Die Demo verwendet eine im Programm definierte Methode mit dem Namen LoadData, um die Datei als ein Array aus Arrays Stil Matrix der Typzeichenfolge in den Arbeitsspeicher gelesen. LoadData der Methode wird davon ausgegangen, dass die Klassenwerte den letzten Wert in jeder Zeile der Daten sind. Ein alternativer Entwurf besteht die prädiktorwerte in einer zeichenfolgenmatrix gelesen, und lesen die 0-1-Klassenwerte in ein Array vom typinteger.

LoadData mit-Methode ruft eine Hilfsmethode, die mit dem Namen MatrixString, die ein Array aus Arrays zeichenfolgenmatrix mit der angegebenen Anzahl von Zeilen (40) und Spalten (4) erstellt. Ein alternativer Entwurf besteht, um die Anzahl der Zeilen und Spalten programmgesteuert zu berechnen, aber meiner Meinung nach die hartcodierte Ansatz ist einfacher und besser.

Programmlogik

Alle programmsteuerungslogik ist in der Main-Methode enthalten. Der joint Counts werden gespeichert, in ein Array aus Arrays Integer-Matrix, die mit dem Namen JointCts, die mit einer Hilfsmethode namens MatrixInt erstellt wird. Die auf Zeilenindizes von JointCts, zeigen Sie auf die prädiktorwerte (Zyan, kleine, Twisted) und Spaltenindizes verweisen auf den Wert der Objektklasse. JointCts [2] [1] enthält z. B. die Anzahl von Datenelementen, die beide Verdrehte haben und Klasse 1. Ein ganzzahliges Array mit der Länge 2 mit dem Namen yCts enthält die Anzahl der Datenelemente mit Klasse 0 und Klasse 1.

Der Code, der die joint und Anzahl der Klasse verwendet, um die beiden Begriffe der Beweise zu berechnen ist:

double[] eTerms = new double[nc];
for (int k = 0; k < nc; ++k) {
  double v = 1.0;
  for (int j = 0; j < nx; ++j) {
    v *= (double)(jointCts[j][k]) / (yCts[k] + nx);
  }
  v *= (double)(yCts[k]) / N;
  eTerms[k] = v;
}

Beachten Sie, dass diese v ist das Produkt von Nx + 1 Brüche, die alle kleiner als 1,0. Dies ist ein Problem für das Demoprogramm nicht, da es nur Nx gibt = 3 prädiktorwerte und keiner der Bruchteil Begriffe können je kleiner als 1/27 sein 0.0370 =. Aber in einigen Fällen können Sie arithmetische schwierigkeiten ausführen, indem viele sehr kleine Werte multiplizieren.

Eine Technik, arithmetische Fehler zu vermeiden, bei der Berechnung der Beweis Bedingungen ist die Verwendung den Protokoll-Trick, der die Fakten, die nutzt Log(A * B) = log(A) + log(B) und Log(A / B) = log(A) - log(B). Durch das Protokoll der einzelnen Evidence-Term computing und die exp-Funktion von diesem Ergebnis erstellen können Sie Addition und Subtraktion von vielen kleinen Werten anstatt Multiplikation und Division. Eine mögliche refactoring mit der Log-Trick ist:

double[] eTerms = new double[nc];
for (int k = 0; k < nc; ++k) {
  double v = 0.0;
  for (int j = 0; j < nx; ++j) {
    v += Math.Log(jointCts[j][k]) - Math.Log(yCts[k] + nx);
  }
  v += Math.Log(yCts[k]) - Math.Log(N);
  eTerms[k] = Math.Exp(v);
}

Die vorhergesagte Klasse generieren

Nach die Bedingungen der Beweise berechnet worden sind, wird das Demoprogramm addiert werden, und verwendet sie zum Berechnen von Pseudo-Wahrscheinlichkeiten. Ich nenne diese Werte Pseudo-Wahrscheinlichkeiten, daran, auch wenn sie auf 1,0 summieren möchten, nicht sie die Wahrscheinlichkeit eines Ergebnisses über viele wiederholte Stichprobenentnahme Experimente wirklich darstellen. Allerdings können Sie mit Vorsicht Pseudo-Wahrscheinlichkeiten als Milde Formulare zuverlässig interpretieren. Z. B. Pseudo Wahrscheinlichkeiten (0.97, 0,03) Klasse 0 mit ein wenig mehr Sicherheit als vorschlagen (0.56, 0,44).

Durch Aufrufen der programmdefinierten ArgMax Funktion, die den Index des größten Werts in ein numerisches Array zurückgibt, ist die vorhergesagte Klasse generiert. Beispielsweise, wenn ein Array mit Werten (0,20, 0,50, 0,90, 0,10) enthält dann ArgMax gibt 2 zurück.

Zusammenfassung

Das Demoprogramm in diesem Artikel vorgestellten führt binären Klassifizierung, da es nur zwei Klassenwerte. Die Logik des Programm kann auch ohne Änderung für eine Klassifikation verwendet werden. Die prädiktorwerte im Demoprogramm sind alle kategorisch. Wenn Ihre Daten numerische Daten, z. B. eine Gewichtung-Variable mit Werten wie macht 3,78 und 9.21, können Sie das Verfahren in diesem Artikel präsentierte, klassieren von numerischen Daten in Kategorien wie Licht, Medium und Heavy anwenden.

Es gibt mehrere andere Arten von Naive Bayes-Klassifikation zusätzlich zu der in diesem Artikel vorgestellten. Ein Formular verwendet die gleichen zugrunde liegenden mathematischen-Prinzipien an, wie diejenigen im Demoprogramm verwendet, aber Sie Daten verarbeiten können, in dem alle prädiktorwerte numerisch sind. Allerdings müssen Sie Annahmen über die Math-Eigenschaften der Daten, z. B.,, dass die Daten eine (Gaußsche) normalverteilung mit einem bestimmten Mittelwert und Standardabweichung.


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, Kirk Olynyk


Diesen Artikel im MSDN Magazine-Forum diskutieren