Testlauf

Datenclustering mithilfe von Category Utility

James McCaffrey

Datenclustering ist das Platzieren von Datenelementen in verschiedene Gruppen – Cluster. Dieser Prozess erfolgt so, dass sich die Elemente in einer bestimmten Gruppe ähnlich sind und von denen in anderen Gruppen unterscheiden. Clustering ist eine Technik für maschinelles Lernen, die sich in vielen wichtigen Bereichen praktisch nutzen lässt. Mit der Clusteranalyse können Sie zum Beispiel bestimmen, welche Artikeltypen häufig zusammen gekauft werden, um gezielte Werbung für Konsumenten bereitzustellen. Ein weiteres Beispiel ist die Bestimmung von ähnlichen Unternehmen, um Aktienkurse vorauszusagen.

Bei der grundlegendsten Form von Clustering wird der sogenannte k-Means-Algorithmus verwendet. (Lesen Sie dazu meinen Artikel „Ermitteln abweichender Daten mithilfe von k-Means-Clustering“ unter msdn.microsoft.com/magazine/jj891054.) Leider kann das k-Means-Clustering nur in Fällen verwendet werden, in denen die Datenelemente vollständig numerisch sind. Das Clustern von kategorischen Daten (beispielsweise von Farbe, die Werte wie „rot“ und „blau“ aufweisen kann) ist eine schwierige Aufgabe. In diesem Artikel stelle ich einen (so weit ich dies feststellen kann) bisher unveröffentlichten Clusteringalgorithmus vor, der darauf ausgelegt ist, entweder numerische oder kategorische Datenelemente oder eine Kombination von beiden zu verarbeiten. Zur Unterscheidung von den vielen anderen Clusteringalgorithmen nenne ich diesen Algorithmus GACUC (Greedy Agglomerate Category Utility Clustering). In diesem Artikel erhalten Sie alle nötigen Informationen, um mit Datenclustering zu experimentieren, einer .NET-Anwendung oder einem .NET-System Clusteringfeatures hinzuzufügen oder ein leistungsfähiges, eigenständiges Datenclusteringtool zu erstellen.

Sehen Sie sich Abbildung 1 an, um zu verstehen, was Clustering ist und worauf ich in diesem Artikel hinaus will. In der Abbildung wird ein Demoprogramm gezeigt, das Cluster aus einem kleinen Satz von fünf Dummydatenelementen erstellt. Datenelemente werden in der Clusteringterminologie manchmal als Tupel bezeichnet. Jedes Tupel hat drei kategorische Attribute: Farbe, Länge und Starrheit. Die Farbe kann einen von vier möglichen Werten aufweisen: „Red“, „Blue“, „Green“ oder „Yellow“. Die Länge kann „Short“, „Medium“ oder „Long“ sein. Der Wert für die Starrheit kann „False“ oder „True“ sein.

Abbildung 1: Clustering von kategorischen Daten

Das Demoprogramm konvertiert die Zeichenfolgen-Rohdaten zur effizienteren Verarbeitung ins Integer-Format. Die Farbwerte „Red“, „Blue“, „Green“ und „Yellow“ werden als 0, 1, 2 und 3 codiert. Die Längenangaben „Short“, „Medium“ und „Long“ werden als 0, 1 und 2 codiert. Für die Starrheit wird „False“ als 0 und „True“ als 1 codiert. Das erste Rohdatenelement, „Red Short True“ wird somit als „0 0 1“ codiert.

Wie viele Clusteringalgorithmen erfordert auch der GACUC die Anzahl der Cluster, die zu bestimmen sind. In diesem Fall wird als Anzahl von Clustern 2 festgelegt. Das Demoprogramm ermittelt dann mithilfe des GACUCs das beste Clustering der Daten. Im Hintergrund startet der Algorithmus mit der Platzierung der Startwerttupel 0 und 4 in die Cluster 0 bzw. 1. Der Clusteringalgorithmus durchläuft dann die Tupel und ordnet diese jeweils dem Cluster zu, welches das beste Gesamtergebnis generiert. Clustering wird als unbeaufsichtigtes Lernen bezeichnet, da keine Übungsdaten zum Einsatz kommen. Nach einem vorläufigen Clusteringdurchgang führt der GACUC-Algorithmus einen Verfeinerungsdurchgang aus, um das Clustering nach Möglichkeit zu verbessern. In diesem Beispiel wird keine Verbesserung ermittelt.

Das Demoprogramm definiert ein Clustering intern als ein int-Array. Der Index des Arrays gibt einen Tupelindex an, und der Zellwert im Array gibt ein Cluster an. In Abbildung 1 ist das beste Clustering, dass der Algorithmus erreicht, [0,0,1,1,1]. Das bedeutet Tupel 0 („Red Short True“) ist in Cluster 0; Tupel 1 („Red Long False“) ist in Cluster 0; Tupel 2 („Blue Medium True“) ist in Cluster 1 usw. Das Demoprogramm zeigt das abschließende, beste Clustering zur besseren Lesbarkeit im Zeichenfolgenformat. Es wird auch eine wichtige Metrik namens Category Utility (CU) für das beste Clustering angezeigt, in diesem Beispiel „0.3733“. Wie Sie noch sehen werden, ist Category Utility der Schlüssel für den GACUC-Clusteringalgorithmus.

In diesem Artikel werden fortgeschrittene Programmierkenntnisse in einer C-Sprache vorausgesetzt; es wird jedoch nicht davon ausgegangen, dass Sie sich mit Datenclustering auskennen. Ich habe das Demoprogramm in C# mit einem nicht objektorientierten Programmierungsansatz codiert, aber Sie sollten den Democode relativ unkompliziert in OOP oder einer anderen Sprache umgestalten können. Der Übersichtlichkeit halber habe ich alle normalen Fehlerprüfungen entfernt. Der Code für das Demoprogramm ist zu lang, um ihn vollständig im Artikel zu zeigen. Der Schwerpunkt liegt daher auf dem GACUC-Algorithmus, damit Sie den Democode an Ihre eigenen Anforderungen anpassen können. Den vollständigen Quellcode für das Demoprogramm finden Sie unter archive.msdn.microsoft.com/mag201305TestRun.

Category Utility

Zum Datenclustering gehört die Lösung von zwei Hauptproblemen. Das erste Problem besteht darin, genau zu definieren, was ein gutes Datenclustering ausmacht. Das zweite Problem ist, eine effektive Technik zum Durchsuchen aller möglichen Clusteringkombinationen zu bestimmen, um die beste zu ermitteln. Category Utility löst das erste Problem. CU ist eine raffinierte Metrik, die die Qualität von einem Clustering definiert. Niedrige CU-Werte geben ein schlechtes Clustering an, höhere Werte hingegen ein besseres. Soweit ich es herausfinden konnte, wurde CU zuerst 1985 von M. Gluck und J. Corter in einem Forschungsartikel mit dem Titel „Information, Uncertainty, and the Utility of Categories“ definiert.

Die mathematische Gleichung für CU ist auf den ersten Blick etwas einschüchternd:

Aber die Gleichung ist tatsächlich einfacher, als sie aussieht. Das groß geschriebene C in der Gleichung ist ein gesamtes Clustering, das klein geschriebene m ist die Anzahl der Cluster, das groß geschriebene P bedeutet die „Wahrscheinlichkeit von“, das groß geschriebene A bedeutet ein Attribut (beispielsweise die Farbe) und das groß geschriebene V bedeutet einen Attributwert (beispielsweise „Red“). Sofern Sie kein Mathematiker sind, können Sie die CU-Berechnung am besten anhand eines Beispiels nachvollziehen. Nehmen Sie an, der Datensatz aus Abbildung 1 soll geclustert werden, und Sie möchten den CU-Wert für das Clustering berechnen:

k = 0
Red      Short    True
Red      Long     False
k = 1
Blue     Medium   True
Green    Medium   True
Green    Medium   False

Der erste Schritt ist die Berechnung von P(Ck), also den Wahrscheinlichkeiten von den jeweiligen Clustern. Für k = 0, da es fünf Tupel im Datensatz gibt und zwei davon in Cluster 0 sind, gilt P(C0) = 2/5 = 0.40. Vergleichbar: P(C1) = 3/5 = 0.60.

Der zweite Schritt ist die Berechnung der letzten Doppelsumme in der Gleichung, bezeichnet als bedingungsloser Wahrscheinlichkeitsterm. Die Berechnung ist die Summe von N Termen, wobei N die Gesamtanzahl von verschiedenen Attributwerten im Datensatz ist. Dies sieht folgendermaßen aus:

Red: (2/5)^2 = 0.1600
Blue: (1/5)^2 = 0.0400
Green: (2/5)^2 = 0.1600
Yellow: (0/5)^2 = 0.0000
Short: (1/5)^2 = 0.0400
Medium: (3/5)^2 = 0.3600
Long: (1/5)^2 = 0.0400
False: (2/5)^2 = 0.1600
True: (3/5)^2 = 0.3600
Unconditional sum = 1.3200

Der dritte Schritt ist die Berechnung der Doppelsumme des Mittelterms, bedingter Wahrscheinlichkeitsterm genannt. Es gibt m Summen (wobei m die Anzahl der Cluster ist), von denen jede N Terme hat.

Die Berechnung für k = 0 lautet:

Red: (2/2)^2 = 1.0000
Blue: (0/2)^2 = 0.0000
Green: (0/2)^2 = 0.0000
Yellow: (0/2)^2 = 0.0000
Short: (1/2)^2 = 0.2500
Medium: (0/2)^2 = 0.0000
Long: (1/2)^2 = 0.2500
False: (1/2)^2 = 0.2500
True: (1/2)^2 = 0.2500
Conditional k = 0 sum = 2.0000

Die Berechnung für k = 1 lautet:

Red: (0/3)^2 = 0.0000
Blue: (1/3)^2 = 0.1111
Green: (2/3)^2 = 0.4444
Yellow: (0/3)^2 = 0.0000
Short: (0/3)^2 = 0.0000
Medium: (3/3)^2 = 1.0000
Long: (0/3)^2 = 0.0000
False: (1/3)^2 = 0.1111
True: (2/3)^2 = 0.4444
Conditional k = 1 sum = 2.1111

Der letzte Schritt ist die Kombination der berechneten Summen gemäß der CU-Gleichung:

CU = 1/2 * [ 0.40 * (2.0000 - 1.3200) + 0.60 * (2.1111 - 1.3200) ]
   = 0.3733

Eine detaillierte Erklärung dazu, warum genau CU die Qualität eines Clusterings misst, ist faszinierend, würde aber leider den Rahmen dieses Artikels sprengen. Wichtig ist, dass Sie für jedes Clustering eines Datensatzes, der kategorische Daten enthält, einen Wert berechnen können, der beschreibt, wie gut das Clustering ist.

Die Suche nach dem besten Clustering

Nach dem Definieren einer Methode zum Messen der Qualität eines Clusterings besteht das zweite in allen Clusteringalgorithmen zu lösende Problem darin, eine effektive Technik zum Durchsuchen aller möglichen Clusteringkombinationen zu bestimmen, um die beste zu ermitteln. Im Allgemeinen ist es nicht machbar, jedes mögliche Clustering eines Datensatzes zu untersuchen. Zum Beispiel gibt es für einen Datensatz mit nur 100 Tupeln und m = 2 Clustern 2^100/2! = 2^99 mögliche Clusterings. Selbst wenn Sie irgendwie eine Billion Clusterings pro Sekunde untersuchen können, würde es ungefähr 19 Milliarden Jahre dauern, jedes mögliche Clustering zu prüfen. (Zum Vergleich, das geschätzte Alter des Universums beträgt ungefähr 14 Milliarden Jahre.)

Verschiedene Clusteringalgorithmen verwenden unterschiedliche Techniken, um alle möglichen Clusterings zu durchsuchen. Der GACUC-Algorithmus verwendet einen agglomerierenden Greedy-Ansatz. Zu Beginn wird für jeden Cluster ein einzelnes Tupel festgelegt. Für jedes verbleibende Tupel wird dann bestimmt, welcher Cluster k’ das beste Gesamtclustering ergäbe, wenn ihm das aktuelle Tupel hinzugefügt werden würde. Dann wird das aktuelle Tupel tatsächlich zu Cluster k’ zugeordnet. Diese Technik garantiert nicht, dass das optimale Clustering gefunden wird, aber Experimente haben gezeigt, dass hiermit im Allgemeinen ein recht gutes Clustering erstellt wird. Das endgültige vom GACUC-Algorithmus erstellte Clustering hängt davon ab, welche m Tupel als Startwerttupel ausgewählt werden, und von der Reihenfolge, in der die verbleibenden Tupel zu Clustern zugeordnet werden.

Wie sich zeigt, ist die Auswahl eines Startwerttupels keine triviale Angelegenheit ist. Ein naiver Ansatz wäre, einfach beliebige Tupel als Startwerte auszuwählen. Wenn die Startwerttupel sich ähneln, führt dies aber zu einem schlechten Clusteringergebnis. Die Auswahl der Startwerttupel funktioniert besser, wenn m Tupel ausgewählt werden, die so unterschiedlich wie möglich sind. An dieser Stelle ist Category Utility wieder sehr nützlich. Der CU-Wert von jedem beliebigen Satz Startwerttupel, die infrage kommen, kann berechnet werden, und der Satz Tupel mit dem besten CU-Wert (größter Wert, d. h. so unterschiedlich wie möglich) kann für die Startwerttupel verwendet werden. Wie zuvor ist es normalerweise nicht möglich, jeden infrage kommenden Satz von Startwerttupeln zu untersuchen. Die Vorgehensweise besteht daher darin, wiederholt m beliebige Tupel auszuwählen, den CU-Wert dieser beliebigen Tupel zu berechnen und den Satz mit den besten CU-Werten für die Startwerte zu verwenden.

Allgemeine Programmstruktur

In Abbildung 2 wird die Main-Methode des Demoprogramms gezeigt, das in Abbildung 1 ausgeführt wird, wobei einige WriteLine-Anweisungen und Kommentare entfernt wurden. Ich habe Visual Studio 2010 mit Microsoft .NET Framework 4 verwendet. Der Democode umfasst aber keine wichtigen Abhängigkeiten, und jede Version von Visual Studio, die .NET Framework 2.0 oder höher unterstützt, sollte gut funktionieren. Ich habe der Einfachheit halber eine einzelne C#-Konsolenanwendung namens ClusteringCategorical erstellt; ziehen Sie in Betracht, Clustering als eine Klassenbibliothek zu implementieren.

Abbildung 2: Allgemeine Programmstruktur

using System;
using System.Collections.Generic;
namespace ClusteringCategorical
{
  class ClusteringCategoricalProgram
  {
    static Random random = null;
    static void Main(string[] args)
    {
      try
      {
        random = new Random(2);
        Console.WriteLine("\nBegin category utility demo\n");
        string[] attNames = new string[] { "Color", "Length", "Rigid" };
        string[][] attValues = new string[attNames.Length][];
        attValues[0] = new string[] { "Red", "Blue", "Green", "Yellow" };
        attValues[1] = new string[] { "Short", "Medium", "Long" };
        attValues[2] = new string[] { "False", "True" };
        string[][] tuples = new string[5][];
        tuples[0] = new string[] { "Red", "Short", "True" };
        tuples[1] = new string[] { "Red", "Long", "False" };
        tuples[2] = new string[] { "Blue", "Medium", "True" };
        tuples[3] = new string[] { "Green", "Medium", "True" };
        tuples[4] = new string[] { "Green", "Medium", "False" };
        Console.WriteLine("Tuples in raw (string) form:\n");
        DisplayMatrix(tuples);
        int[][] tuplesAsInt = TuplesToInts(tuples, attValues);
        Console.WriteLine("\nTuples in integer form:\n");
        DisplayMatrix(tuplesAsInt);
        int numClusters = 2;
        int numSeedTrials = 10;
        Console.WriteLine("Initializing clustering result array");
        int[] clustering = InitClustering(tuplesAsInt);
        int[][][] valueCounts = InitValueCounts(tuplesAsInt, attValues,
          numClusters);
        int[][] valueSums = InitValueSums(tuplesAsInt, attValues);
        int[] clusterCounts = new int[numClusters];
        Console.WriteLine("\nBeginning clustering routine");
        Cluster(tuplesAsInt, attValues, clustering, valueCounts,
          valueSums, clusterCounts, numSeedTrials);
        double cu = CategoryUtility(valueCounts, valueSums,
          clusterCounts);
        Console.WriteLine("\nCategory Utility of clustering = " +
          cu.ToString("F4"));
        DisplayVector(clustering);
        Refine(20, tuplesAsInt, clustering, valueCounts, valueSums,
          clusterCounts);
        Console.WriteLine("Refining complete");
        DisplayVector(clustering);
        Console.WriteLine("\nFinal clustering in string form:\n");
        DisplayClustering(numClusters, clustering, tuples);
        cu = CategoryUtility(valueCounts, valueSums, clusterCounts);
        Console.WriteLine("\nFinal clustering CU = " + cu.ToString("F4"));
        Console.WriteLine("\nEnd demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
      }
    } // Main
    // All other methods here
  } // class Program
} // ns

In Abbildung 2 führt die Cluster-Methode eine Iteration des grundlegenden GACUC-Clusteringalgorithmus aus. Die numSeedTrials-Variable wird auf 10 festgelegt und der Routine übergeben, die die anfänglichen Startwerttupel bestimmt, die jedem Cluster zugeordnet werden. Die Refine-Methode durchläuft die Daten nach dem Clustering, und versucht, ein Clustering zu finden, dass einen besseren CU-Wert erzielt.

Die wichtigsten Datenstrukturen

Es ist zwar möglich, den CU-Wert eines Datensatzes sofort zu berechnen, indem jeder Tupel im Datensatz durchlaufen wird. Da die Clusteringmethode den CU-Wert viele Male berechnen muss, ist es jedoch viel besser, die Anzahl der Attributwerte von Tupeln, die den Clustern zu beliebigen Zeitpunkten zugeordnet werden, zu speichern. In Abbildung 3 werden die meisten wichtigen Datenstrukturen gezeigt, die der GACUC-Algorithmus verwendet.

Abbildung 3: Wichtige Datenstrukturen

Das valueCounts-Array enthält die Anzahl der Attributwerte nach Cluster. Zum Beispiel enthält „valueCounts[0][2][1]“ die Anzahl von Tupeln mit dem Attribut 0 (Farbe) und dem Wert 2 (grün), die derzeit Cluster 1 zugeordnet sind. Das valueSums-Array enthält die summierte Anzahl aller Cluster für jeden Attributwert. „valueSums[0][2]“ beispielsweise enthält die Gesamtanzahl von Tupeln mit dem Attribut 0 (Farbe) und dem Wert 2 (grün), die zu allen Clustern zugeordnet sind. Das clusterCounts-Array enthält die Anzahl von Tupeln, die derzeit zu jedem Cluster zugeordnet sind. Wenn zum Beispiel „numClusters = 2“ und „clusterCounts = [2,2]“ ist, dann sind zwei Tupel zu Cluster 0 und zwei Tupel zu Cluster 1 zugeordnet. Das clustering-Array codiert die Zuordnung von Tupeln zu Clustern. Der Index von „clustering“ stellt ein Tupel dar, ein Zellenwert stellt einen Cluster dar, und ein Wert von -1 gibt an, dass das zugeordnete Tupel noch nicht zu einem Cluster zugeordnet wurde. Wenn zum Beispiel „clustering[2] = 1“ ist, dann ist Tupel 2 dem Cluster 1 zugeordnet.

Codieren der CategoryUtility-Methode

Der Code für die Methode, die Category Utility berechnet, ist von der Idee her nicht schwierig, aber er ist etwas knifflig. Die Definition der Methode beginnt folgendermaßen:

static double CategoryUtility(int[][][] valueCounts, 
  int[][] valueSums,
  int[] clusterCounts)
{
  int numTuplesAssigned = 0;
  for (int k = 0; k < clusterCounts.Length; ++k)
    numTuplesAssigned += clusterCounts[k];
  int numClusters = clusterCounts.Length;
  double[] clusterProbs = new double[numClusters];   // P(Ck)
  for (int k = 0; k < numClusters; ++k)
    clusterProbs[k] = (clusterCounts[k] * 1.0) / numTuplesAssigned;

Es wird vorausgesetzt, dass die drei Eingabearrays „valueCounts“, „valueSums“ und „clusterCounts“ gültige Werte enthalten, die das derzeitige Clustering wiederspiegeln, wie im vorherigen Abschnitt und in Abbildung 3 beschrieben. Die Methode beginnt damit, das clusterCounts-Array zu durchsuchen, um die Gesamtanzahl von Tupeln zu berechnen, die derzeit Clustern zugeordnet sind. Die Anzahl der Cluster wird von der Length-Eigenschaft des clusterCounts-Arrays abgeleitet, und die Wahrscheinlichkeiten für die Cluster werden dann berechnet und im lokalen clusterProbs-Array gespeichert.

Der nächste Schritt ist, die einzelne bedingungslose Wahrscheinlichkeit für das aktuelle Clustering zu berechnen:

double unconditional = 0.0;
for (int i = 0; i < valueSums.Length; ++i)
{
  for (int j = 0; j < valueSums[i].Length; ++j)
  {
    double p = (valueSums[i][j] * 1.0) / numTuplesAssigned;
    unconditional += (p * p);
  }
}

Nach der Berechnung der bedingungslosen Wahrscheinlichkeit folgt die Berechnung einer bedingten Wahrscheinlichkeit für jeden Cluster:

double[] conditionals = new double[numClusters];
for (int k = 0; k < numClusters; ++k)
{
  for (int i = 0; i < valueCounts.Length; ++i)
  {
    for (int j = 0; j < valueCounts[i].Length; ++j)
    {
      double p = (valueCounts[i][j][k] * 1.0) / clusterCounts[k];
      conditionals[k] += (p * p);
    }
  }
}

Mit den Wahrscheinlichkeiten von jedem Cluster im clusterProbs-Array, dem bedingungslosen Wahrscheinlichkeitsterm in der unconditional-Variable und den bedingten Wahrscheinlichkeitstermen im conditionals-Array kann jetzt der CU-Wert für das Clustering bestimmt werden:

double summation = 0.0;
for (int k = 0; k < numClusters; ++k)
  summation += clusterProbs[k] * 
    (conditionals[k] - unconditional);
return summation / numClusters;
}

Eine gute Methode, um das Verhalten der CU-Funktion zu ergründen, ist das Experimentieren mit dem Democode, indem Sie hartcodierte Clusterings bereitstellen. Beispielsweise können Sie den Code in Abbildung 2 ungefähr folgendermaßen ändern:

string[] attNames = new string[] { "Color", "Length", "Rigid" };
// And so on, as in Figure 1
int[][] tuplesAsInt = TuplesToInts(tuples, attValues);
int[] clustering[] = new int[] { 0, 1, 0, 1, 0 };
// Hardcoded clustering
double cu = CategoryUtility(valueCounts, valueSums, clusterCounts);
Console.WriteLine("CU of clustering = " + cu.ToString("F4"));

Implementieren der Cluster-Methode

Wenn Sie über eine Category Utility-Methode verfügen, ist es relativ einfach, eine Methode zum Clustern von Daten zu implementieren. In Pseudocode sieht die Cluster-Methode in der Übersicht wie folgt aus:

define an empty clustering with all tuples unassigned
determine m good (dissimilar) seed tuples
assign one good seed tuple to each cluster
loop each unassigned tuple t
  compute the CU for each cluster if t were actually assigned
  determine the cluster that gives the best CU
  assign tuple t to best cluster
end loop (each tuple)
return clustering

Zur Vereinfachung durchläuft die Cluster-Methode jedes nicht zugeordnete Tupel der Reihe nach, beginnend bei Tupel „[0]“. Tupel mit niedrigeren Indexzahlen erhalten dadurch effektiv mehr Einfluss. Ich verwende häufig einen anderen Ansatz, nämlich das Durchlaufen von nicht zugeordneten Tupeln in zufälliger oder vermischter Reihenfolge mithilfe eines linearen, kongruenten Vollzyklus-Generators.

Ein überraschend diffiziler Teil des Algorithmus ist, m gute Startwerttupel zu finden. In Pseudocode sieht die GetGoodIndexes-Methode in der Übersicht wie folgt aus:

loop numSeedTrials times
  create a mini-tuples array with length numClusters
  pick numClusters random tuple indexes
  populate the mini-tuples with values from data set
  compute CU of mini data set
  if CU > bestCU
    bestCU = CU
    indexes of best mini data set = indexes of data set
  end if
end loop
return indexes of best mini data set

Hier werden zufällige Tupelindizes durch einen brachialen Ansatz erstellt, der ungefähr „Generieren-Überprüfen-wenn-nicht-verwendet“ lautet. Dieser Ansatz funktioniert bei mir in der Praxis gut.

Da die Cluster-Methode im Allgemeinen ein gutes, aber nicht optimales Clustering zurückgibt, ruft der GACUC-Algorithmus optional eine refine-Methode auf, die versucht, durch Neuanordnen der Zuordnungen von Tupeln und Clustern ein Clustering mit einem besseren CU-Wert zu ermitteln. In Pseudocode sieht die Refine-Methode folgendermaßen aus:

loop numRefineTrials times
  select a random tuple that is in a cluster with at least two tuples
  determine the random tuple's cluster
  select a second cluster that is different from curr cluster
  unassign tuple from curr cluster
  assign tuple to different cluster
  compute new CU
  if new CU > old CU
    leave the cluster switch alone
  else
    unassign tuple from different cluster
    assign tuple back to original cluster
  end if
end loop

Sie können mit vielen anderen Verfeinerungen nach der Verarbeitung experimentieren. Die vorstehende Verfeinerung verwaltet eine feste Anzahl von Clustern. Eine Möglichkeit besteht darin, eine Verfeinerungsmethode zu definieren, die zulässt, dass die Clusteranzahl erhöht oder gesenkt wird.

Eine wichtige Hilfsmethode im GACUC-Clusteringalgorithmus ist eine, die ein Tupel zu einem Cluster zuordnet:

static void Assign(int tupleIndex, int[][] tuplesAsInt, 
  int cluster,  int[] clustering, 
  int[][][] valueCounts, int[][] valueSums,
  int[] clusterCounts)
{
  clustering[tupleIndex] = cluster;  // Assign
  for (int i = 0; i < valueCounts.Length; ++i)  // Update
  {
    int v = tuplesAsInt[tupleIndex][i];
    ++valueCounts[i][v][cluster];
    ++valueSums[i][v];
  }
  ++clusterCounts[cluster];  // Update
}

Die Assign-Methode akzeptiert viele Parameter. Dies ist eine allgemeine Schwäche bei der Verwendung statischer Methoden anstelle eines OOP-Ansatzes. Die Assign-Methode ändert das clustering-Array und aktualisiert anschließend die Arrays, die die Anzahl für jeden Attributwert nach Cluster („valueCounts“), die Anzahl für jeden Attributwert für alle Cluster („valueSums“) und die Anzahl der Tupel, die zu jedem Cluster zugeordnet sind („clusterCounts“), enthalten. Die Unassign-Methode ist im Grunde das Gegenteil von „Assign“. Die drei wichtigen Anweisungen in der Unassign-Methode lauten wie folgt:

clustering[tupleIndex] = -1;  // Unassign
--valueCounts[i][v][cluster]; // Update
--valueSums[i][v];            // Update
--clusterCounts[cluster];     // Update

Zusammenfassung

Mit dem Codedownload zu diesem Artikel und den hier vorgestellten Erklärungen zum GACUC-Clusteringalgorithmus haben Sie alles, was Sie benötigen, um mit Datenclustering zu experimentieren, einer Anwendung Clusteringfeatures hinzuzufügen oder ein Clustering-Hilfsprogramm zu erstellen. Im Unterschied zu vielen Clusteringalgorithmen (einschließlich k-Means) kann der GACUC-Algorithmus einfach geändert werden, um numerische Daten oder kombinierte numerische und kategorische Daten zu verarbeiten. Das Konzept dabei ist die Vorverarbeitung von numerischen Daten durch deren Klassierung in Kategorien. Wenn die Rohdaten zum Beispiel die Größen von Personen in Zentimetern enthalten, könnten Sie die Größe so klassieren, dass Werte unter 152 „kurz“, Werte zwischen 152 und 187 „mittel“ und Werte über 187 „groß“ sind.

Zum Clustern von kategorischen Daten sind viele Algorithmen verfügbar, darunter Algorithmen, die die Clusteringgüte anhand des Category Utility definieren. Der hier vorgestellte Algorithmus ist allerdings relativ einfach, hat sich in der Praxis bewährt, lässt sich auf numerische und kategorische Daten anwenden und kann auch an große Datenmengen angepasst werden. GACUC-Datenclustering kann eine wertvolle Ergänzung für Ihre Entwicklertools sein.

Dr. James McCaffrey ist für Volt Information Sciences Inc. tätig. Er leitet technische Schulungen für Softwareentwickler, die auf dem Campus von Microsoft in Redmond, USA arbeiten. 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: Dan Liebling (Microsoft Research)