Testlauf

Konvertieren von numerischen Daten in kategorische Daten

James McCaffrey

James McCaffreyAuf dem Gebiet des maschinellen Lernens besteht eine wichtige Aufgabe darin, numerische Daten in kategorische Daten zu konvertieren. Liegen Ihnen beispielsweise Daten zur Größe von Menschen in Zoll vor, wie 59,5, 64,0 und 75,5, so können Sie diese numerischen Daten in folgende kategorische Daten konvertieren: 0, 1 und 2. Sie stehen für klein, mittelgroß und groß. Informell wird dieser Prozess gelegentlich auch „Klassieren von Daten“ genannt. In der Fachliteratur über maschinelles Lernen wird bei diesem Prozess gewöhnlich von „Diskretisierung kontinuierlicher Daten“ gesprochen.

Es gibt unterschiedliche Szenarios, in denen Sie Daten möglicherweise diskretisieren möchten. Viele maschinelle Lernalgorithmen, wie die naive Bayes-Klassifikation und -Vorhersage, funktionieren nur mit kategorischen Daten. Sind die Rohdaten numerisch, obwohl Sie naives Bayes anwenden möchten, müssen diese Daten diskretisiert werden. Vielleicht haben Sie auch eine Mischung aus numerischen und kategorischen Daten. Dies kommt oft bei Excel-Tabellen vor. Nur sehr wenige maschinelle Lernalgorithmen können mit Mischdaten eingesetzt werden. Sie können die numerischen Daten aber in kategorische Daten konvertieren und dann einen maschinellen Lernalgorithmus verwenden, der für kategorische Daten funktioniert. Datenclustering mithilfe von Category Utility ist ein Beispiel dafür.

Vielleicht liegt es daran, dass dieses Thema nicht sehr berauschend ist, aber es gibt wenige Ressourcen, die genau beschreiben, wie Diskretisierungsalgorithmen implementiert werden. In diesem Artikel stelle ich einen leistungsstarken Diskretisierungsalgorithmus vor. Obwohl es sich nicht um neue Ideen handelt, wurden die in diesem Artikel vorgestellte Implementierung meines Wissens bisher noch nicht veröffentlicht.

Ich empfehle Ihnen, sich das Demoprogramm in Abbildung 1 anzusehen. Dort erfahren Sie, um was es bei diesem Artikel geht. Bei diesem Demo werden 20 Datenpunkte eingerichtet, die für die Größe von Menschen in Zoll stehen. Die Rohdaten finden Sie im Histogramm von Abbildung 2. Im Demo werden Daten analysiert, ein Discretizer-Objekt erstellt und dann eine interne Darstellung des Discretizer angezeigt. Der Discretizer bewahrt eine Kopie der verschiedenen Werte aus den Rohdaten in einem sortieren Array (niedrige Werte bis hohe Werte) auf, das die Bezeichnung „data“ trägt. Die Anzahl an Kategorien wurde mit drei berechnet und wird in der Membervariable k gespeichert.

Converting Numeric Data to Categorical DataAbbildung 1: Konvertieren von numerischen Daten in kategorische Daten

The Raw Data to CategorizeAbbildung 2: Zu kategorisierende Rohdaten

Jeder Datenpunkt wurde einer der drei Kategorien zugewiesen. Die Kategorien werden jeweils als nullbasierte Ganzzahl (0 bis 2) codiert, und die Zuweisungsinformationen werden in einem Array gespeichert, der die Bezeichnung „clustering“ trägt. Die ersten drei Datenpunkte (60,0, 61,0 und 62,0) wurden Kategorie 0 zugewiesen, die nächsten vier Datenpunkte (66,0, 67,0, 68,0 und 69,0) Kategorie 1 und die letzten vier Datenpunkte (73,0, 74,0, 76,0 und 78,0) Kategorie 2. Das arithmetische Mittel der ersten drei Datenpunkte in Kategorie 0 ist 61,00, und für die Kategorien 1 und 2 liegt es jeweils bei 67,50 und 75,25.

Nach Erstellung des Discretizer-Objekts richtet das Demoprogramm drei bereits vorhandene Datenwerte ein (62,0, 66,0 und 73,0) sowie drei neue Datenwerte (59,5, 75,5 und 80,5). Hier geht es darum, dass manchmal ein fester Datensatz vorhanden ist, in anderen Situationen jedoch nicht. Neue Daten werden dynamisch generiert und müssen konvertiert werden. Der Discretizer konvertiert die sechs numerischen Datenpunkte in kategorische Daten, also in „0, 1, 2“ und „0, 2, 2“.

Dieser Artikel setzt mindestens mittlere Programmierkenntnisse voraus. Ich habe den Diskretisierungsalgorithmus mit C# codiert, Sie sollten den Code jedoch relativ leicht in eine andere Sprache, zum Beispiel Python oder Visual Basic, umgestalten können. Ich habe auf einen Großteil der normalen Fehlerprüfung verzichtet, um den Code kurz zu halten und die wichtigsten Ideen übersichtlich zu gestalten. Der Demoquellcode ist zu lang, um in diesem Artikel vollständig aufgeführt zu werden. Sie finden ihn jedoch unter archive.msdn.microsoft.com/mag201308TestRun.

Leichter als erwartet

Zunächst wird der Eindruck vermittelt, dass sich numerische leicht in kategorische Daten konvertieren lassen. Sie könnten zum Beispiel einfach die Rohdatenquelle in gleiche Intervalle einteilen. Für die Daten im Demo und in Abbildung 2 gilt beispielsweise folgender Bereich: 78,0 - 60,0 = 18,0. Wird dieser Wert durch „k = 3 Intervalle“ geteilt, so entsteht eine Intervallbreite von 6,0 Zoll. Alle Daten zwischen 60,0 und 66,0 würden daher Kategorie 0 zugewiesen, Daten zwischen 66,0 und 72,0 Kategorie 1 und Daten zwischen 72,0 und 78,0 Kategorie 2. Bei der Verwendung von einheitlichen Intervallen tritt jedoch das Problem auf, dass natürliche Datenbrüche ignoriert werden. In Abbildung 2 erkennen Sie, dass ein guter Diskretisierungsalgorithmus Daten grob zwischen 63,0 und 65,0 und nicht bei 66,0 teilen sollte.

Ein zweiter naiver Diskretisierungsansatz wäre, gleiche Häufigkeit zu verwenden. Für die Beispielsdaten sollten Sie die ersten drei Datenpunkte Kategorie 0 zuweisen, die zweiten drei Datenpunkte Kategorie 1 und die letzten fünf Datenpunkte Kategorie 2. Dies ist dadurch zu begründen, dass 11 verschiedene Datenpunkte vorhanden sind, für die „k = 3 Kategorien“ und „11 : 3 = 3“ gelten (mit Abschneiden bei der Ganzzahldivision). Beim Verfahren der gleichen Häufigkeit werden ebenfalls natürliche Datenbrüche ignoriert.

Bei dem in diesem Artikel vorgestellten Diskretisierungsalgorithmus wird ein Datenclusteringansatz verfolgt. Die Rohdaten werden mit einem k-Means-Algorithmus geclustert, bei dem natürliche Datenbrüche berücksichtigt werden. Die vom Clusteringalgorithmus generierten Mittel werden dann zum Kategorisieren neuer Daten verwendet. In Abbildung 1 sehen Sie beispielsweise drei Mittel: 61,00, 67,50 und 75,25. Zum Zuordnen des numerischen Werts 62,5 zu einem kategorischen Wert bestimmt der Discretizer, welcher der drei Mittelwerte am nähesten an 62,5 liegt (in diesem Fall 61,0), und weist dann den Clusterwert, der 61,0 zugewiesen ist (hier 0), als Kategoriewert für 62,5 zu.

K-Means-Clustering

Der k-Means-Clusteringalgorithmus ist recht einfach. Es gibt viele Varianten dieses Algorithmus. In seiner einfachsten Form werden beim Initialisierungsprozess für einen bestimmten Satz an Datenpunkten und eine bestimmte Anzahl an Clustern k die einzelnen Datenpunkte einem willkürlich ausgewählten Cluster zugewiesen. Dann werden die Mittel der Datenpunkte im jeweiligen Cluster berechnet. Danach werden die einzelnen Datenpunkte geprüft und erneut dem Cluster zugewiesen, dessen Mittel dem des Datenpunkts am nächsten kommt. Mittelberechnung und erneute Clusterzuweisung werden so lange wiederholt, bis kein Datenpunkt einem neuen Cluster zugewiesen wird.

Allgemeine Programmstruktur

Das in Abbildung 1 dargestellte Demoprogramm ist eine einzelne Konsolenanwendung. Ich habe Visual Studio 2012 verwendet. Das Demo umfasst aber keine wichtigen Abhängigkeiten, und jede Version von Visual Studio mit Microsoft .NET Framework 2.0 oder höher sollte funktionieren. Ich habe eine neue C#-Konsolenanwendung erstellt und ihr den Namen „BinningData“ gegeben. Nachdem der Vorlagencode im Solution Explorer-Fenster geladen wurde, habe ich die Datei Program.cs umbenannt und ihr den anschaulicheren Namen BinningProgram.cs gegeben. Visual Studio hat daraufhin automatisch die Programmklasse umbenannt. Oben im Quellcode habe ich alle Namespace-Referenzen mit Ausnahme von „System“ und „Collections.Generic“ gelöscht.

Die gesamte Programmstruktur ist mit ein paar kleinen Änderungen in Abbildung 3 dargestellt. Die wichtigsten ausführenden Anweisungen können folgendermaßen zusammengefasst werden:

double[] rawData = new int[] { 66.0, 66.0, ... };
Discretizer d = new Discretizer(rawData);
double numericVal = 75.5;
int catVal = d.Discretize(numericVal);

Abbildung 3: Struktur des Demoprogramms

using System;
using System.Collections.Generic;
namespace BinningData
{
  class BinningProgram
  {
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin discretization of continuous data demo\n");
        double[] rawData = new double[20] {
          66, 66, 66, 67, 67, 67, 67, 68, 68, 69,
          73, 73, 73, 74, 76, 78,
          60, 61, 62, 62 };
        Console.WriteLine("Raw data:");
        ShowVector(rawData, 2, 10);
        Console.WriteLine("\nCreating a discretizer on the raw data");
        Discretizer d = new Discretizer(rawData);
        Console.WriteLine("\nDiscretizer creation complete");
        Console.WriteLine("\nDisplaying internal structure of the discretizer:\n");
        Console.WriteLine(d.ToString());
        Console.WriteLine("\nGenerating three existing and three new data values");
        double[] newData = new double[6] { 62.0, 66.0, 73.0, 59.5, 75.5, 80.5 };
        Console.WriteLine("\nData values:");
        ShowVector(newData, 2, 10);
        Console.WriteLine("\nDiscretizing the data:\n");
        for (int i = 0; i < newData.Length; ++i)
        {
          int cat = d.Discretize(newData[i]);
          Console.WriteLine(newData[i].ToString("F2") + " -> " + cat);
        }
        Console.WriteLine("\n\nEnd discretization demo");
        Console.ReadLine();
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
        Console.ReadLine();
      }
    } // Main
    public static void ShowVector(double[] vector, int decimals,
      int itemsPerRow) { . . }
  } // Program
  public class Discretizer
  {
    public Discretizer(double[] rawData) { . . }
    private static double[] GetDistinctValues(double[] array) { . . }
    private static bool AreEqual(double x1, double x2) { . . }
    public int Discretize(double x) { . . }
    public override string ToString() { . . }
    private void InitializeClustering() { . . }
    private int[] GetInitialIndexes() { . . }
    private int InitialCluster(int di, int[] initialIndexes) { . . }
    private void Cluster() { . . }
    private bool ComputeMeans() { . . }
    private bool AssignAll() { . . }
    private int MinIndex(double[] distances) { . . }
    private static double Distance(double x1, double x2) { . . }
  }
} // ns

Discretizer-Klasse

Die Discretizer-Klasse hat vier Datenmember:

private double[] data;
private int k;
private double[] means;
private int[] clustering;

Der Discretizer-Konstruktor verwendet numerische Daten, um eine Discretize-Methode zu ermöglichen, die einen numerischen Wert akzeptiert und einen kategorischen Wert in Form einer nullbasierten Ganzzahl zurückgibt. Der Discretizer bestimmt die Anzahl der Kategorien automatisch.

Array-Daten enthalten die verschiedenen Werte aus den Rohdaten und werden zum Erstellen von Clustering verwendet. Die Ganzzahl k ist die Anzahl der Cluster, denen die Daten zugewiesen werden, und entspricht somit der Anzahl an Datenkategorien. Das Array mit der Bezeichnung „means“ hat die Größe k und enthält die arithmetischen Mittel der Datenpunkte, die den einzelnen Clustern während des Ausführens des Clustering-Algorithmus zu einem beliebigen Zeitpunkt zugewiesen werden.

Das Array mit der Bezeichnung „Clustering“ codiert, wie die Daten zu einem beliebigen Zeitpunkt geclustert werden. Der Index des Array-Clustering weist auf den Index eines Datenpunkts hin, der in Array-Daten gespeichert ist, und der Wert des Array-Clustering auf die aktuelle Clusterzuweisung. Wenn zum Beispiel „clustering[9] = 2“ ist, dann ist der Datenpunkt bei „data[9]“ dem Cluster 2 zugeordnet.

Discretizer-Konstruktor

Der Discretizer-Konstruktor wird folgendermaßen festgelegt:

public Discretizer(double[] rawData)
{
  double[] sortedRawData = new double[rawData.Length];
  Array.Copy(rawData, sortedRawData, rawData.Length);
  Array.Sort(sortedRawData);
  this.data = GetDistinctValues(sortedRawData);
  this.clustering = new int[data.Length];
  this.k = (int)Math.Sqrt(data.Length); // heuristic
  this.means = new double[k];
  this.Cluster();
}

Zuerst müssen die verschiedenen Werte aus den Rohdaten extrahiert werden. Hierzu gibt es verschiedene Möglichkeiten. Hier sortiert der Code eine Kopie der Rohdaten und ruft dann eine Hilfsmethode auf, nämlich „GetDistinctValues“. Sobald die verschiedenen Werte bestimmt worden sind, kann das Clustering-Array zugewiesen werden.

Und dies ist die Methode „GetDistinctValues“:

private static double[] GetDistinctValues(double[] array)
{
  List<double> distinctList = new List<double>();
  distinctList.Add(array[0]);
  for (int i = 0; i < array.Length - 1; ++i)
    if (AreEqual(array[i], array[i + 1]) == false)
      distinctList.Add(array[i+1]);
  double[] result = new double[distinctList.Count];
  distinctList.CopyTo(result);
  return result;
}

Weil die Quelldaten sortiert wurden, kann die Methode eine Einzelprüfung durchführen und nach Instanzen suchen, bei denen zwei aufeinanderfolgende Werte nicht gleich sind. Die Rohdaten sind vom Typ „double“, weshalb es riskant sein kann, zwei Werte auf genaue Gleichheit zu prüfen. Aus diesem Grund wird die Hilfsmethode „AreEqual“ verwendet.

private static bool AreEqual(double x1, double x2)
{
  if (Math.Abs(x1 - x2) < 0.000001) return true;
  else return false;
}

Bei der Methode „AreEqual“ wird ein willkürlicher Genauigkeitsgrenzwert von 0,000001 verwendet. Sie können diesen Wert als Eingabeparameter in das Discretizer-Objekt aufnehmen. In solch einer Situation wird häufig eine Variable verwendet, die als „epsilon“ bezeichnet wird.

Nachdem die verschiedenen Werte aus den Rohdaten extrahiert wurden, ist k zu bestimmen. Dies ist die Anzahl an Clustern und entspricht gleichzeitig der Anzahl an Kategorien. Hier wird eine Faustregel angewendet, und k wird die Quadratwurzel der Anzahl an Datenelementen. Sie könnten den Konstruktor aber auch so schreiben, dass der Wert von k als Parameter eingereicht wird. Welcher Wert für k optimal ist, ist praktisch ein Problem, das auf dem Gebiet des maschinellen Lernens noch gelöstest werden muss.

Nachdem der Wert von k berechnet wurde, weist der Konstruktor Platz für Array-Mittel zu und ruft dann die Cluster-Methode auf. Diese Methode führt k-Means-Clustering für die Daten durch, und die Werte im endgültigen Means-Array können verwendet werden, um einem beliebigen numerischen Wert einen Kategoriewert zuzuweisen.

Clusteringalgorithmus

Im Zentrum der Discretizer-Klasse steht der Code, der das k-Means-Clustering durchführt. Die Cluster-Methode ist in Abbildung 4 aufgeführt.

Abbildung 4: Cluster-Methode

private void Cluster()
{
  InitializeClustering();
  ComputeMeans();
  bool changed = true; bool success = true;
  int ct = 0;
  int maxCt = data.Length * 10; // Heuristic
  while (changed == true && success == true && ct < maxCt) {
    ++ct;
    changed = AssignAll();
    success = ComputeMeans();
  }
}

Die Cluster-Methode ist recht kurz, weil alle aufwändigen Arbeiten an Hilfsmethoden ausgelagert werden. Bei der Methode „InitializeClustering“ werden alle Datenpunkte einem ersten Cluster zugewiesen. Die Mittel der Datenpunkte, die den einzelnen Clustern zugewiesen sind, werden bei der Clusteringzuweisungen berechnet.

In der Hauptschleife des Clusteringalgorithmus werden alle Datenpunkte über die Methode „AssignAll“ einem Cluster zugewiesen. Die Methode „AssignAll“ ruft die Hilfsmethoden „Distance“ und „MinIndex“ auf. Die Methode „Distance“ definiert den Abstand zwischen zwei Datenpunkten.

private static double Distance(double x1, double x2)
{
  return Math.Sqrt((x1 - x2) * (x1 - x2));
}

Hier wird euklidischer Abstand verwendet, der als Quadratwurzel des Abstands im Quadrat definiert wird. Da es sich bei den Datenpunkten um einzelne Werte und nicht um Vektoren handelt, entspricht der euklidische Abstand „Math.Abs(x1 - x2)“. Vielleicht möchten Sie ja diese einfachere Berechnung verwenden.

Die Schleife ist vorhanden, wenn sich das Clustering-Array nicht ändert (Rückgabewert „AssignAll“), wenn das Means-Array nicht berechnet werden kann, weil die Anzahl der Werte, die einem Cluster zugewiesen sind, null ist, oder wenn für die Schleifenanzahl ein Höchstwert erreicht wurde. Hier wurde maxCt willkürlich die 10-fache Anzahl der Datenpunkte als Wert zugewiesen. Im Allgemeinen konvergiert der Clusteringalgorithmus hier extrem schnell, und eine Bedingung zum Beenden der Schleife bei Erreichen von maxCt ist wahrscheinlich auf einen Logikfehler zurückzuführen. Ergreifen Sie diesbezüglich entsprechende Maßnahmen.

Da vom Clusteringprozess Clustern wiederholt Werte zugewiesen werden, kann die Anzahl der Werte, die einem Cluster zugewiesen sind, auf null fallen, was dazu führt, dass kein Mittel berechnet werden kann. Die Hilfsmethode „ComputeMeans“ versucht, alle k-Means zu berechnen, gibt aber „false“ zurück, wenn die Anzahl null entspricht. Die Methode ist in Abbildung 5 dargestellt.

Abbildung 5: ComputeMeans-Methode

private bool ComputeMeans()
{
  double[] sums = new double[k];
  int[] counts = new int[k];
  for (int i = 0; i < data.Length; ++i)
  {
    int c = clustering[i]; // Cluster ID
    sums[c] += data[i];
    counts[c]++;
  }
  for (int c = 0; c < sums.Length; ++c)
  {
    if (counts[c] == 0)
      return false; // fail
    else
      sums[c] = sums[c] / counts[c];
  }
  sums.CopyTo(this.means, 0);
  return true; // Success
}

Initialisieren von Clustering

Es ist nicht ganz leicht, das Clustering zu initiieren. Nehmen wir an, die Daten bestehen aus 11 sortierten Werten (siehe Abbildung 1) und k, die Anzahl an Clustern, wurde auf drei gesetzt. Nach der Initialisierung besteht das Ziel beim Arraymitglied-Clustering darin, drei 0-Werte in den Zellen 0 bis 2, drei 1-Werte in den Zellen 3 bis 5 und die verbleibenden fünf 2-Werte in den Zellen 6 bis 10 zu haben. Anders ausgedrückt: Das Clustering sollte gleichmäßig nach Häufigkeit verteilt sein.

Der erste Schritt besteht darin, Grenzwerte von {3, 6, 9} zu generieren, die stillschweigend Intervalle von 0-2, 3-5 und ab 6 definieren. Hierzu wird die Hilfsmethode „GetInitialIndexes“ verwendet, von der einfach die Anzahl der Datenpunkte durch die Anzahl der Cluster geteilt wird.

private int[] GetInitialIndexes()
{
  int interval = data.Length / k;
  int[] result = new int[k];
  for (int i = 0; i < k; ++i)
    result[i] = interval * (i + 1);
  return result;
}

Als zweiter Schritt wird eine Hilfsmethode definiert, mit der unter Verwendung von Grenzwerten der Clusterwert für einen bestimmten Datenindexwert berechnet wird.

private int InitialCluster(int di, int[] initialIndexes)
{
  for (int i = 0; i < initialIndexes.Length; ++i)
    if (di < initialIndexes[i])
      return i;
  return initialIndexes.Length - 1; // Last cluster
}

Im Rahmen eines dritten Schritts werden alle Datenindizes einem Cluster zugewiesen.

private void InitializeClustering()
{
  int[] initialIndexes = GetInitialIndexes();
  for (int di = 0; di < data.Length; ++di)
  {
    int c = InitialCluster(di, initialIndexes);
    clustering[di] = c;
  }
}

Im Wesentlichen entspricht der Initialisierungsprozess dem Ansatz der gleichen Häufigkeit, der in diesem Artikel bereits beschrieben wurde.

Discretize-Methode

Nachdem die Daten geclustert wurden, können die endgültigen Werte im Means-Array verwendet werden, um einem numerischen Wert einen nullbasierten kategorischen Wert zuzuweisen. Methode „Discretize“:

public int Discretize(double x)
{
  double[] distances = new double[k];
  for (int c = 0; c < k; ++c)
    distances[c] = Distance(x, data[means[c]]);
  return MinIndex(distances);
}

Von der Methode wird der Abstand zwischen dem Eingabewert x und den einzelnen k-Means berechnet und dann der Index des nächstgelegenen Mittels zurückgegeben. Hierbei handelt es sich um eine Cluster-ID und gleichzeitig um einen kategorischen Wert. Sind die endgültigen Mittel zum Beispiel 61,00, 67,50 und 75,25 und entspricht x 70,00, gilt für den Abstand zwischen x und mean[0] Folgendes: sqrt((70,00 - 61,00)^2) = sqrt(81,00) = 9,00. Zugleich gelten mean[1] = sqrt((70,00 - 67,50)^2) = 2,50 und mean[2] = sqrt((70,00 - 75,25)^2) = 5,25. Der geringste Abstand beträgt 2,50, und zwar bei Index [1]. 70,00 wird daher dem kategorischen Wert 1 zugewiesen.

Zusammenfassung

Sie können den in diesem Artikel verwendeten Code genau so nutzen, um numerische Daten zuverlässig für maschinelles Lernen in kategorische Daten zu konvertieren. Vielleicht möchten Sie die Discretizer-Klasse in einer Klassenbibliothek einkapseln, anstatt den Code direkt in eine Anwendung einzubetten.

Das Hauptfeature, das Sie möglicherweise anpassen möchten, ist die Bestimmung der Kategorienanzahl k. Unter anderem ist dies durch Festlegen eines Schwellenwertes möglich. Unterhalb des Schwellenwertes wird von jedem Datenpunkt ein Kategoriewert generiert. Angenommen, es geht um das Alter von Menschen, und zwar zwischen 1 und 120. Kann nur aus 120 verschiedenen Werten eine Auswahl getroffen werden, könnten Sie k einfach auf 120 setzen, anstatt k als Quadratwurzel von 120 zu berechnen (10 Kategorien).

Dr. James McCaffrey arbeitet im amerikanischen Redmond (Washington) für Microsoft. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und MSN Search. Dr. McCaffrey ist der Autor von „.NET Test Automation Recipes“, Apress 2006, und kann unter jammc@microsoft.com erreicht werden.

Unser Dank gilt dem folgenden technischen Experten für die Durchsicht dieses Artikels: Richard Hughes (Microsoft Research)