Datenclustering
Ermitteln abweichender Daten mithilfe von k-Means-Clustering
Überlegen Sie, wie Sie abweichende Datenelemente in einem sehr großen Dataset identifizieren könnten, beispielsweise potenziell betrügerische Kreditkartentransaktionen oder riskante Darlehensanträge. Das ist keine leichte Aufgabe. Eine Herangehensweise ist es, die Datenelemente in ähnlichen Clustern zu gruppieren und anschließend innerhalb der Cluster Datenelemente zu suchen, die sich auf eine Art von den anderen Datenelementen im Cluster unterscheiden.
Es gibt viele verschiedene Clusteringalgorithmen. Einer der ältesten und am häufigsten verwendeten ist der k-Means-Algorithmus. In diesem Artikel erkläre ich die Funktionsweise des k-Means-Algorithmus und präsentiere ein vollständiges C#-Demoprogramm. Warum sollten Sie überhaupt einen k-Means-Clusteringcode von Grund auf erstellen, wenn es doch bereits viele eigenständige Datenclusteringtools gibt? Die Integration vorhandener Clusteringtools in ein Softwaresystem kann sich als schwierig oder sogar unmöglich erweisen. Die Tools können zudem nicht unbedingt an ungewöhnliche Szenarien angepasst werden. Darüber hinaus bestehen möglicherweise Probleme im Zusammenhang mit den Urheberrechten oder dem geistigen Eigentum. Nach dem Lesen dieses Artikels werden Sie in der Lage sein, mit k-Means-Clustering zu experimentieren. Außerdem werden Sie über Grundkenntnisse im Hinzufügen von Clusteringfunktionen zu einer .NET-Anwendung verfügen.
Sehen Sie sich Abbildung 1 an, um ein Gefühl dafür zu bekommen, was k-Means-Clustering ist und worauf ich in diesem Artikel hinaus will. Das Demoprogramm beginnt mit dem Erstellen eines Dummysets von 20 Datenelementen. In der Clusteringterminologie werden Datenelemente manchmal als Tupel bezeichnet. Jedes Tupel steht hier für eine Person und besitzt zwei numerische Attributwerte: einen für „heigth“ (Größe) in Zoll und einen für „weight“ (Gewicht) in Pfund. Eine der Einschränkungen des k-Means-Algorithmus besteht darin, dass er nur in Fällen angewendet wird, in denen die Datentupel vollständig numerisch sind.
.png)
Abbildung 1: Clustering mithilfe von k-Means
Die Dummydaten werden in ein Array im Speicher geladen. Als Nächstes wird die Anzahl von Clustern auf drei festgelegt. Auch wenn es erweiterte Clusteringtechniken gibt, die die optimale Anzahl von zu verwendenden Clustern vorschlagen können, ist das Datenclustering insgesamt ein explorativer Prozess. Die beste Anzahl zu verwendender Cluster wird normalerweise durch systematisches Probieren ermittelt. Wie Sie gleich sehen werden, ist das k-Means-Clustering ein iterativer Prozess. Im Demoprogramm gibt es eine maxCount-Variable, mit Sie einschränken können, wie häufig die Hauptclusteringschleife ausgeführt werden soll. Hier wurde der Wert willkürlich auf 30 festgelegt.
Anschließend wird im Hintergrund der k-Means-Algorithmus verwendet, um jedes Datentupel in einem der drei Cluster zu platzieren. Es gibt viele Möglichkeiten, ein Clustering zu codieren. In diesem Fall wird ein Clustering von einem int-Array definiert. Dabei repräsentiert der Arrayindex ein Tupel, und der zugehörige Arraywert repräsentiert die 0-basierte Cluster-ID. In Abbildung 1 wird folglich Tupel 0 (65.0, 220.0) Cluster 0, Tupel 1 (73.0, 160.0) Cluster 1, Tupel 2 (59.0, 110.0) Cluster 2, Tupel 3 (61.0, 120.0) Cluster 3 usw. zugewiesen. Beachten Sie, dass Cluster 0 acht Tupel, Cluster 1 fünf Tupel und Cluster 2 sieben Tupel zugewiesen wurden.
Als Nächstes werden im Demoprogramm die Daten nach Cluster gruppiert angezeigt. Beim Überprüfen der Clusterdaten erkennen Sie, dass Cluster 0 als Cluster für schwere Personen, Cluster 1 als Cluster für große Personen und Cluster 2 als Cluster für kleine Personen bezeichnet werden könnte. Das Demoprogramm wird abgeschlossen, indem die Cluster 0 zugewiesenen Tupel analysiert werden. Es wird zudem anhand bestimmter Kriterien festgelegt, dass Tupel 5 (67.0, 240.0) das am stärksten abweichende Tupel ist.
In den folgenden Abschnitten beschreibe ich schrittweise den Code, mit dem der Screenshot in Abbildung 1 erstellt wurde, sodass Sie den Code für Ihre eigenen Erfordernisse ändern können. Dieser Artikel setzt mittlere Programmierkenntnisse in einer C-Sprache voraus. Es wird nicht davon ausgegangen, dass Sie sich im Datenclustering auskennen. Ich habe das Demoprogramm mithilfe von C# codiert. Dabei habe ich jedoch kein OOP-Format verwendet, damit Sie die Demo bei Bedarf unkompliziert in einer anderen Sprache umgestalten können. Ich zeige in diesem Artikel den gesamten Quellcode für das Demoprogramm.
Der k-Means-Algorithmus
Von seinem Prinzip her ist der k-Means-Algorithmus zumindest ziemlich einfach. Sie werden jedoch sehen, dass einige Implementierungsdetails sich als ein wenig schwierig erweisen können. Das Konzept des k-Means-Algorithmus basiert auf dem Schwerpunkt. Beim Datenclustering ist der Schwerpunkt eines Datentupelsatzes das Tupel, das für die Gruppe am repräsentativsten ist. Dies lässt sich am besten an einem Beispiel erklären. Angenommen, Sie haben drei height-weight-Tupel, die den Tupeln in Abbildung 1 ähneln:
[a] (61.0, 100.0)
[b] (64.0, 150.0)
[c] (70.0, 140.0)
Welches Tupel ist am repräsentativsten? Sie können dies ermitteln, indem Sie ein mathematisches Durchschnittstupel (Mittel) berechnen und dann das Tupel als Schwerpunkt auswählen, das die kürzeste Distanz zum Durchschnittstupel aufweist. In diesem Fall ergibt sich folgendes Durchschnittstupel:
[m] = ((61.0 + 64.0 + 70.0) / 3, (100.0 + 150.0 + 140.0) / 3)
= (195.0 / 3, 390.0 / 3)
= (65.0, 130.0)
Welches der drei Tupel hat nun die kürzeste Distanz zu (65.0, 130.0)? Es gibt verschiedene Möglichkeiten, die „kürzeste Distanz“ zu definieren. Am häufigsten, und auch in diesem Demoprogramm, wird sie mithilfe der euklidischen Distanz bestimmt. Die euklidische Distanz zwischen den beiden Tupeln entspricht der Quadratwurzel der Summe der quadrierten Differenzen zwischen jeder Komponente der Tupel. Dies kann wieder am besten an einem Beispiel erklärt werden. Die euklidische Distanz zwischen Tupel (61.0, 100.0) und dem Durchschnittstupel (65.0, 130.0) ist:
dist(m,a) = sqrt((65.0 - 61.0)^2 + (130.0 - 100.0)^2)
= sqrt(4.0^2 + 30.0^2)
= sqrt(16.0 + 900.0)
= sqrt(916.0)
= 30.27
Vergleichbar:
dist(m,b) = sqrt((65.0 - 64.0)^2 + (130.0 - 150.0)^2)
= 20.02
dist(m,c) = sqrt((65.0 - 70.0)^2 + (130.0 - 140.0)^2)
= 11.18
Da die kleinste der drei Distanzen die Distanz zwischen dem mathematischen Durchschnitt und Tupel [c] ist, ist der Schwerpunkt der drei Tupel Tupel [c]. Wenn Sie herausfinden möchten, wie die Distanzen das abschließende Clusteringergebnis beeinflussen, können Sie mit dem Demoprogramm experimentieren und verschiedene Definitionen für die Distanz zwischen zwei Tupeln verwenden.
Sobald das Konzept eines Clusterschwerpunkts verstanden wurde, ist der k-Means-Algorithmus relativ einfach. In Pseudocode sieht das folgendermaßen aus:
assign each tuple to a randomly selected cluster
compute the centroid for each cluster
loop until no improvement or until maxCount
assign each tuple to best cluster
(the cluster with closest centroid to tuple)
update each cluster centroid
(based on new cluster assignments)
end loop
return clustering
Im Web finden Sie mehrere gute Onlineanimationen des k-Means-Algorithmus. Das Bild in Abbildung 2 zeigt das im Demoprogramm erstellte Clustering. Das eingekreiste Datenelement in jedem Cluster ist der Clusterschwerpunkt.
.png)
Abbildung 2: Clusterdaten und -schwerpunkte
Allgemeine Programmstruktur
Die gesamte Programmstruktur für die in Abbildung 1 gezeigte Demo ist mit ein paar kleinen Änderungen in Abbildung 3 aufgeführt. Ich habe in Visual Studio 2010 eine neue C#-Konsolenanwendung mit dem Namen „ClusteringKMeans“ erstellt. Mit einer neueren Version von Visual Studio sollte dies genauso funktionieren. Im Fenster „Projektmappen-Explorer“ habe ich die Datei „Program.cs“ in „ClusteringKMeansProgram.cs“ umbenannt. Hierdurch wurde automatisch die von der Vorlage generierte Klasse umbenannt. Die nicht benötigten Anweisungen am Anfang der Datei habe ich entfernt.
Abbildung 3: Allgemeine Programmstruktur
using System;
namespace ClusteringKMeans
{
class ClusteringKMeansProgram
{
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin outlier data detection demo\n");
Console.WriteLine("Loading all (height-weight) data into memory");
string[] attributes = new string[] { "Height", "Weight" };
double[][] rawData = new double[20][];
rawData[0] = new double[] { 65.0, 220.0 };
rawData[1] = new double[] { 73.0, 160.0 };
rawData[2] = new double[] { 59.0, 110.0 };
rawData[3] = new double[] { 61.0, 120.0 };
rawData[4] = new double[] { 75.0, 150.0 };
rawData[5] = new double[] { 67.0, 240.0 };
rawData[6] = new double[] { 68.0, 230.0 };
rawData[7] = new double[] { 70.0, 220.0 };
rawData[8] = new double[] { 62.0, 130.0 };
rawData[9] = new double[] { 66.0, 210.0 };
rawData[10] = new double[] { 77.0, 190.0 };
rawData[11] = new double[] { 75.0, 180.0 };
rawData[12] = new double[] { 74.0, 170.0 };
rawData[13] = new double[] { 70.0, 210.0 };
rawData[14] = new double[] { 61.0, 110.0 };
rawData[15] = new double[] { 58.0, 100.0 };
rawData[16] = new double[] { 66.0, 230.0 };
rawData[17] = new double[] { 59.0, 120.0 };
rawData[18] = new double[] { 68.0, 210.0 };
rawData[19] = new double[] { 61.0, 130.0 };
Console.WriteLine("\nRaw data:\n");
ShowMatrix(rawData, rawData.Length, true);
int numAttributes = attributes.Length;
int numClusters = 3;
int maxCount = 30;
Console.WriteLine("\nk = " + numClusters + " and maxCount = " + maxCount);
int[] clustering = Cluster(rawData, numClusters, numAttributes, maxCount);
Console.WriteLine("\nClustering complete");
Console.WriteLine("\nClustering in internal format: \n");
ShowVector(clustering, true);
Console.WriteLine("\nClustered data:");
ShowClustering(rawData, numClusters, clustering, true);
double[] outlier = Outlier(rawData, clustering, numClusters, 0);
Console.WriteLine("Outlier for cluster 0 is:");
ShowVector(outlier, true);
Console.WriteLine("\nEnd demo\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
// 14 short static method definitions here
}
}
Aus Gründen der Einfachheit habe ich einen statischen Methodenansatz verwendet und alle Fehlerüberprüfungen entfernt. Im ersten Teil des Democodes werden zu die gruppierenden Daten für die Größe und das Gewicht festgelegt. Da nur 20 Tupel vorhanden sind, habe ich die Daten hartcodiert und im Speicher in einem Array namens „rawData“ gespeichert. Normalerweise werden die Daten in einer Textdatei oder SQL-Tabelle gespeichert. In diesen Fällen müssen Sie eine Hilfsfunktion schreiben, um die Daten in den Speicher zu laden. Wenn die Datenquelle für den Computerspeicher zu groß ist, müssen Sie den Democode ändern, sodass er eine externe Datenquelle anstelle eines Datenarrays durchläuft.
Nach dem Festlegen der Rohdaten wird vom Programm die Hilfsfunktion „ShowMatrix“ aufgerufen, um die Daten anzuzeigen. Anschließend werden den Variablen „numAttributes“, „numClusters“ und „maxCount“ die Werte „2“ („height“ und „weight“) bzw. „3“ und „30“ zugewiesen. Durch den Aufruf von „maxCount“ wird die Anzahl von Iterationen in der Hauptschleife zum Verarbeiten des Algorithmus eingeschränkt. Der k-Means-Algorithmus tendiert dazu, schnell zu konvergieren. Sie müssen jedoch vielleicht ein wenig mit dem Wert „maxCount“ experimentieren.
Das gesamte Clustering wird von der Cluster-Methode ausgeführt. Die Methode gibt ein int-Array zurück, das definiert, wie jedes Tupel einem Cluster zugewiesen wird. Nach Abschluss zeigt das Demoprogramm das codierte Clustering sowie die nach Cluster gruppierten Rohdaten an.
Das Demoprogramm wird abgeschlossen, indem die gruppierten Daten mithilfe der Outliers-Methode im Hinblick auf Ausreißertupel (möglicherweise abweichende Tupel) analysiert werden. Die Methode akzeptiert eine Cluster-ID und gibt die Werte des Datentupels zurück, das vom Clusterschwerpunkt (dem repräsentativsten Tupel) am weitesten entfernt ist (gemäß euklidischer Distanz). In diesem Fall ist für Cluster 0, dem Cluster für schwere Personen, das Ausreißertupel (67.0, 240.0) die schwerste Person.
Berechnen von Clusterschwerpunkten
Wie bereits beschrieben, ist ein Clusterschwerpunkt ein Tupel, das für die einem Cluster zugewiesenen Tupel am repräsentativsten ist. Eine Methode zum Festlegen eines Clusterschwerpunkts ist die Berechnung eines mathematischen Durchschnittstupels und das anschließende Ermitteln des Tupels, das die geringste Distanz zum Durchschnittstupel aufweist. Die Hilfsmethode „UpdateMeans“ berechnet das mathematische Durchschnittstupel für jeden Cluster und wird in Abbildung 4 aufgeführt.
Abbildung 4: UpdateMeans-Methode
static void UpdateMeans(double[][] rawData, int[] clustering,
double[][] means)
{
int numClusters = means.Length;
for (int k = 0; k < means.Length; ++k)
for (int j = 0; j < means[k].Length; ++j)
means[k][j] = 0.0;
int[] clusterCounts = new int[numClusters];
for (int i = 0; i < rawData.Length; ++i)
{
int cluster = clustering[i];
++clusterCounts[cluster];
for (int j = 0; j < rawData[i].Length; ++j)
means[cluster][j] += rawData[i][j];
}
for (int k = 0; k < means.Length; ++k)
for (int j = 0; j < means[k].Length; ++j)
means[k][j] /= clusterCounts[k]; // danger
return;
}
Die UpdateMeans-Methode setzt voraus, dass ein Array aus Arrays mit dem Namen „means“ bereits vorhanden ist und nicht erst erstellt und zurückgegeben wird. Da davon ausgegangen wird, dass das means-Array vorhanden ist, sollten Sie es in einen ref-Parameter umwandeln. Das means-Array wird mit der Hilfsmethode „Allocate“ erstellt:
static double[][] Allocate(int numClusters, int numAttributes)
{
double[][] result = new double[numClusters][];
for (int k = 0; k < numClusters; ++k)
result[k] = new double[numAttributes];
return result;
}
Der erste Index im means-Array stellt eine Cluster-ID dar, und der zweite Index weist auf das Attribut hin. Wenn beispielsweise „means[0][1] = 150.33“, dann beträgt der Durchschnitt des weight-Werts (1) der Tupel in Cluster 0 „150.33“.
Die UpdateMeans-Methode füllt zuerst die vorhandenen Werte im means-Array mit Nullen auf, durchläuft dann jedes Datentupel und berechnet die Anzahl von Tupeln in jedem Cluster. Die Summen werden für jedes Attribut akkumuliert, und anschließend wird jede akkumulierte Summe durch die entsprechende Clusteranzahl geteilt. Beachten Sie, dass die Methode eine Ausnahme auslöst, wenn die Clusteranzahl 0 ist. Daher sollten Sie eine Fehlerüberprüfung hinzufügen.
Die ComputeCentroid-Methode (siehe Abbildung 5) bestimmt die Schwerpunktwerte, d.h. die Werte des Tupels mit der geringsten Distanz zu den Durchschnittstupelwerten für einen bestimmten Cluster.
Abbildung 5: ComputeCentroid-Methode
static double[] ComputeCentroid(double[][] rawData, int[] clustering,
int cluster, double[][] means)
{
int numAttributes = means[0].Length;
double[] centroid = new double[numAttributes];
double minDist = double.MaxValue;
for (int i = 0; i < rawData.Length; ++i) // walk thru each data tuple
{
int c = clustering[i];
if (c != cluster) continue;
double currDist = Distance(rawData[i], means[cluster]);
if (currDist < minDist)
{
minDist = currDist;
for (int j = 0; j < centroid.Length; ++j)
centroid[j] = rawData[i][j];
}
}
return centroid;
}
Die ComputeCentroid-Methode durchläuft jedes Tupel im Dataset. Tupel, die nicht im angegebenen Cluster sind, werden übersprungen. Für jedes Tupel im angegebenen Cluster wird mit der Hilfsmethode „Distance“ die euklidische Distanz zwischen dem Tupel und dem Clustermittelwert berechnet. Die Tupelwerte, die am nächsten an den Mittelwerten liegen (mit der kleinsten Distanz) werden gespeichert und zurückgegeben.
Die UpdateCentroids-Methode ruft für jeden Cluster „ComputeCentroid“ auf, um die Schwerpunkte für alle Cluster anzugeben:
static void UpdateCentroids(double[][] rawData, int[] clustering,
double[][] means, double[][] centroids)
{
for (int k = 0; k < centroids.Length; ++k)
{
double[] centroid = ComputeCentroid(rawData, clustering, k, means);
centroids[k] = centroid;
}
}
Die UpdateCentroids-Methode setzt voraus, dass ein Array von Arrays namens „centroids“ vorhanden ist. Das centroids-Array ist dem means-Array sehr ähnlich: Der erste Index stellt eine Cluster-ID dar und der zweite Index weist auf das Datenattribut hin.
Zusammengefasst besitzt jeder Cluster einen Schwerpunkt, der das repräsentativste Tupel im Cluster darstellt. Schwerpunktwerte werden durch Ermitteln des einzelnen Tupels in jedem Cluster berechnet, das in jedem Cluster die geringste Distanz zum Durchschnittstupel (Mittel) aufweist. Jedes Datentupel wird dem Cluster zugewiesen, dessen Clusterschwerpunkt dem Tupel am nächsten ist.
Distance-Funktion und Datennormalisierung
Die ComputeCentroid-Methode ruft eine Distance-Methode auf, um zu bestimmen, welches Datentupel am nächsten am Clustermittelwert liegt. Wie oben beschrieben, wird die Distanz von Tupeln zum Mittelwert in der Regel mithilfe der euklidischen Distanz berechnet:
static double Distance(double[] tuple, double[] vector)
{
double sumSquaredDiffs = 0.0;
for (int j = 0; j < tuple.Length; ++j)
sumSquaredDiffs += Math.Pow((tuple[j] - vector[j]), 2);
return Math.Sqrt(sumSquaredDiffs);
}
Sie können auch andere Möglichkeiten zum Definieren der Distanz in Erwägung ziehen. Häufig wird die Summe der absoluten Werte der Differenzen zwischen jeder Komponente verwendet. Da bei der euklidischen Distanz Differenzen quadriert werden, wiegen große Differenzen viel schwerer als kleine Differenzen.
Die Datennormalisierung ist ein weiterer wichtiger Faktor hinsichtlich der Wahl der distance-Funktion im k-Means-Clusteringalgorithmus. Das Demoprogramm verwendet rohe, nicht normalisierte Daten. Da die Tupelgewichte in der Regel Werte wie „160.0“ und Tupelgrößen normalerweise Werte wie „67.0“ sind, haben die Unterschiede bei den Gewichten einen größeren Einfluss als die Unterschiede bei den Größen. In vielen Situationen ist es nützlich, neben der Überprüfung des Clusterings von rohen Daten die rohen Daten vor dem Clustering zu normalisieren. Es gibt verschiedene Methoden, wie Sie Daten normalisieren können. Eine verbreitete Methode ist es, für jedes Attribut den Mittelwert (m) und die Standardabweichung (sd) zu berechnen. Anschließend wird für jeden Attributwert (v) ein normalisierter Wert nv = (v-m)/sd berechnet.
Zuweisen jedes Tupels zu einem Cluster
Wenn Sie eine Methode zur Berechnung des Schwerpunkts für jeden Cluster haben, können Sie eine Methode zum Zuweisen jedes einzelnen Tupels zu einem Cluster schreiben. Die Assign-Methode ist in Abbildung 6 aufgeführt.
Abbildung 6: Assign-Methode
static bool Assign(double[][] rawData,
nt[] clustering, double[][] centroids)
{
int numClusters = centroids.Length;
bool changed = false;
double[] distances = new double[numClusters];
for (int i = 0; i < rawData.Length; ++i)
{
for (int k = 0; k < numClusters; ++k)
distances[k] = Distance(rawData[i], centroids[k]);
int newCluster = MinIndex(distances);
if (newCluster != clustering[i])
{
changed = true;
clustering[i] = newCluster;
}
}
return changed;
}
Die Assign-Methode akzeptiert ein Array von Schwerpunktwerten und durchläuft jedes Datentupel Für jedes Datentupel wird die Distanz zu jedem Clusterschwerpunkt berechnet und in einem lokalen Array mit dem Namen „distances“ gespeichert. Hier stellt der Index des Arrays eine Cluster-ID dar. Mit der Hilfsmethode „MinIndex“ wird der Index in Arraydistanzen mit dem kleinsten Distanzwert festgelegt. Dies entspricht der Cluster-ID des Clusters, in dem der Schwerpunkt am nächsten am Tupel liegt.
Hier sehen Sie die Hilfsmethode „MinIndex“:
static int MinIndex(double[] distances)
{
int indexOfMin = 0;
double smallDist = distances[0];
for (int k = 0; k < distances.Length; ++k)
{
if (distances[k] < smallDist)
{
smallDist = distances[k]; indexOfMin = k;
}
}
return indexOfMin;
}
Wenn sich in „Assign“ die berechnete Cluster-ID von der im Arrayclustering gespeicherten vorhandenen Cluster-ID unterscheidet, wird das Arrayclustering aktualisiert. Zusätzlich wird ein boolesches Flag aktiviert und deaktiviert, um darauf hinzuweisen, dass mindestens eine Änderung im Clustering vorgenommen wurde. Mit diesem Flag wird bestimmt, wann die Hauptalgorithmusschleife angehalten werden soll: wenn die Höchstzahl an Iterationen überschritten wird, oder wenn das Clustering unverändert ist.
Bei der Implementierung des k-Means-Algorithmus wird davon ausgegangen, dass jedem Cluster immer mindestens ein Datentupel zugewiesen ist. Abbildung 6 zeigt, wie mit der Assign-Methode nicht verhindert werden kann, dass einem Cluster keine Tupel zugewiesen werden. In der Praxis ist dies normalerweise kein Problem. Die Verhinderung der Fehlerbedingung ist ein wenig kompliziert. Ich erstelle dafür meistens ein Array mit dem Namen „centroidIndexes“, das in Verbindung mit Arrayschwerpunkten funktioniert. Wie Sie wissen, enthalten Arrayschwerpunkte Schwerpunktwerte. Beispielsweise ist (61.0, 120.0) der Schwerpunkt für Cluster 2 in Abbildung 2. Das centroidIndexes-Array enthält den zugehörigen Tupelindex, beispielsweise [3]. In der Assign-Methode müssen Sie als Erstes jedem Cluster das Datentupel zuweisen, das die Schwerpunktwerte enthält. Nur in diesem Fall durchläuft die Methode jedes verbleibende Tupel und weist jedes Tupel einem Cluster zu. So wird sichergestellt, dass jeder Cluster mindestens ein Tupel besitzt.
Die Cluster-Methode
Die Cluster-Methode (siehe Abbildung 7) ist die Routine auf oberster Ebene, die alle Hilfsmethoden und untergeordneten Hilfsmethoden aufruft, tatsächlich das Datenclustering auszuführen.
Abbildung 7: Die Cluster-Methode
static int[] Cluster(double[][] rawData, int numClusters,
int numAttributes, int maxCount)
{
bool changed = true;
int ct = 0;
int numTuples = rawData.Length;
int[] clustering = InitClustering(numTuples, numClusters, 0);
double[][] means = Allocate(numClusters, numAttributes);
double[][] centroids = Allocate(numClusters, numAttributes);
UpdateMeans(rawData, clustering, means);
UpdateCentroids(rawData, clustering, means, centroids);
while (changed == true && ct < maxCount)
{
++ct;
changed = Assign(rawData, clustering, centroids);
UpdateMeans(rawData, clustering, means);
UpdateCentroids(rawData, clustering, means, centroids);
}
return clustering;
}
Die while-Hauptschleife weist wiederholt jedes Datentupel einem Cluster zu, berechnet für jeden Cluster das neue Tupelmittel und berechnet dann mithilfe der neuen Mittelwerte für jeden Cluster die neuen Schwerpunkte. Die Schleife wird beendet, wenn in der Clusterzuweisung keine Änderungen auftreten oder eine Höchstzahl erreicht wird. Da das means-Array nur für die Berechnung von Schwerpunkten verwendet wird, empfiehlt es sich, Cluster umzugestalten, indem der Aufruf von „UpdateMeans“ in der UpdateCentroids-Methode platziert wird.
Vor dem Start der Verarbeitungsschleife wird das Clusteringarray von der InitClustering-Methode initialisiert:
static int[] InitClustering(int numTuples,
int numClusters, int randomSeed)
{
Random random = new Random(randomSeed);
int[] clustering = new int[numTuples];
for (int i = 0; i < numClusters; ++i)
clustering[i] = i;
for (int i = numClusters; i < clustering.Length; ++i)
clustering[i] = random.Next(0, numClusters);
return clustering;
}
Die InitClustering-Methode weist zuerst jeweils Tupel 0 über numClusters-1 an Cluster 0 über numClusters-1 zu, sodass jeder Cluster mit mindestens einem zugewiesenen Tupel startet. Die verbleibenden Tupel werden einem willkürlich ausgewählten Cluster zugewiesen.
Im Bereich der Initialisierung von k-Means-Clustering wurden überraschend viele Forschungsarbeiten durchgeführt. Vielleicht interessiert es Sie, auch mit anderen als den hier besprochenen Methoden zu experimentieren. In vielen Fällen hängt das endgültige vom k-Means-Algorithmus erzeugte Clustering davon ab, wie das Clustering initialisiert wurde.
Suchen nach abweichenden Daten
Das Datenclustering kann einfach zum Untersuchen unterschiedlicher Clusterings und zum Suchen nach unerwarteten oder überraschenden Ergebnissen verwendet werden. Eine weitere Einsatzmöglichkeit besteht darin, nach ungewöhnlichen Datentupeln innerhalb eines Clusters zu suchen. Das Demoprogramm überprüft Cluster 0, um das Tupel in dem Cluster mit der größten Distanz zum Clusterschwerpunkt zu finden. Zu diesem Zweck wird eine Methode mit dem Namen „Outlier“ verwendet, die in Abbildung 8 aufgeführt ist.
Abbildung 8: Die Outlier-Methode
static double[] Outlier(double[][] rawData, int[] clustering,
int numClusters, int cluster)
{
int numAttributes = rawData[0].Length;
double[] outlier = new double[numAttributes];
double maxDist = 0.0;
double[][] means = Allocate(numClusters, numAttributes);
double[][] centroids = Allocate(numClusters, numAttributes);
UpdateMeans(rawData, clustering, means);
UpdateCentroids(rawData, clustering, means, centroids);
for (int i = 0; i < rawData.Length; ++i)
{
int c = clustering[i];
if (c != cluster) continue;
double dist = Distance(rawData[i], centroids[cluster]);
if (dist > maxDist)
{
maxDist = dist;
Array.Copy(rawData[i], outlier, rawData[i].Length);
}
}
return outlier;
}
Nach der Initialisierung von means- und centroids-Arrays durchläuft die Outlier-Methode jedes Tupel im angegebenen Cluster. Dabei wird die euklidische Distanz zwischen dem Tupel und dem Clusterschwerpunkt berechnet. Anschließend werden die Werte des Tupels mit der größten Distanz zu den Schwerpunktwerten zurückgegeben. Geringfügig abweichend hiervon können Sie erwägen, den Index des am weitesten entfernten Datentupels zurückzugeben.
Es gibt weitere Methoden, mit denen Sie gruppierte Daten auf Abweichungen untersuchen können. Beispielsweise können Sie die Durchschnittsdistanz zwischen jedem Tupel und dem zugewiesenen Clusterschwerpunkt bestimmen. Alternativ können Sie die Distanzen der Clusterschwerpunkte voneinander untersuchen.
Anzeigeroutinen
Aus Gründen der Vollständigkeit sollen an dieser Stelle ein paar vereinfachte Anzeigeroutinen besprochen werden. Im Codedownload befinden sich etwas raffiniertere Versionen. Wenn Sie die vereinfachten Routinen verwenden, müssen Sie ihre Aufrufe in der Main-Methode ändern. Zum Anzeigen von Rohdaten, Mittelwerten und Schwerpunkten können Sie folgenden Code verwenden:
static void ShowMatrix(double[][] matrix)
{
for (int i = 0; i < numRows; ++i)
{
Console.Write("[" + i.ToString().PadLeft(2) + "] ");
for (int j = 0; j < matrix[i].Length; ++j)
Console.Write(matrix[i][j].ToString("F1") + " ");
Console.WriteLine("");
}
}
Zum Anzeigen des Clusteringarrays können Sie folgenden Code verwenden:
static void ShowVector(int[] vector)
{
for (int i = 0; i < vector.Length; ++i)
Console.Write(vector[i] + " ");
Console.WriteLine("");
}
Zum Anzeigen der Werte eines Ausreißers können Sie folgenden Code verwenden:
static void ShowVector(double[] vector)
{
for (int i = 0; i < vector.Length; ++i)
Console.Write(vector[i].ToString("F1") + " ");
Console.WriteLine("");
}
Zum Anzeigen von Rohdaten, die nach Cluster gruppiert sind, können Sie folgenden Code verwenden:
static void ShowClustering(double[][] rawData,
int numClusters, int[] clustering)
{
for (int k = 0; k < numClusters; ++k) // Each cluster
{
for (int i = 0; i < rawData.Length; ++i) // Each tuple
if (clustering[i] == k)
{
for (int j = 0; j < rawData[i].Length; ++j)
Console.Write(rawData[i][j].ToString("F1") + " ");
Console.WriteLine("");
}
Console.WriteLine("");
}
}
Zusammenfassung
Das Datenclustering ist eng verwandt mit der Datenklassifizierung und wird deshalb auch gelegentlich mit ihr verwechselt. Beim Clustering handelt es sich um eine unüberwachte Technik, mit der Datenelemente gruppiert werden, und zwar ohne ein vorheriges Wissen über die Gruppen. In der Regel ist dies ein explorativer Prozess. Die Klassifizierung ist dagegen eine überwachte Technik, die die Angabe bekannter Gruppen in Trainingsdaten erfordert, nach denen jedes Datentupel in einer der Gruppen platziert wird. Die Klassifizierung wird normalerweise zur Vorhersage verwendet.
Der Code und die Erklärung in diesem Artikel sollten Sie in die Lage versetzen, folgende Aktionen auszuführen: das Experimentieren mit dem k-Means-Datenclustering, das Erstellen eines vollständig anpassbaren, eigenständigen Clusteringtools oder das Hinzufügen von Clusteringfeatures zu einer .NET-Anwendung, ohne sich auf externe Abhängigkeiten zu verlassen. Neben dem k-Means-Algorithmus gibt es noch viele andere Clusteringalgorithmen. Einige von ihnen werde ich in zukünftigen MSDN Magazine-Artikeln besprechen, einschließlich Datenentropieminimierung, Category Utility und Naive Bayes-Inferenz.
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" (Rezepte für die .NET-Testautomatisierung, Apress 2006) und kann unter jammc@microsoft.com erreicht werden.
Unser Dank gilt dem folgenden technischen Experten für die Durchsicht dieses Artikels: Darren Gehring