• Artikel

August 2015

Band 30, Nummer 8

Testlauf - K-Mittel ++ Daten Clusterbildung

Von James McCaffrey

James McCaffreyDaten-Cluster ist der Prozess der Datenelemente gruppieren, damit ähnliche Elemente zusammen platziert werden. Sobald gruppiert, können die Cluster Daten untersucht werden, um festzustellen, ob es gibt Beziehungen, die nützlich sein könnten. Beispielsweise könnte eine große Reihe von Verkaufsdaten Cluster verwendet wurde, Auskunft über die Daten in jedem Cluster Muster offenbaren, die für gezieltes Marketing verwendet werden konnte.

Es gibt mehrere Clusteringalgorithmen. Eine der häufigsten heißt den k-Means-Algorithmus. Es gibt mehrere Varianten dieses Algorithmus. Dieser Artikel beschreibt eine relativ neue Variante namens die k-Mittel ++ Algorithmus.

Schauen Sie sich das Demoprogramm in Abbildung 1. Das Programm beginnt mit 20 Datenelemente, jeweils bestehend aus einer Person Größe in Zoll und Gewicht in Pfund. Als Nächstes wird die Anzahl der Cluster auf 3 festgelegt. In den meisten Szenarien mit Clusterunterstützung Daten muss die Anzahl der Cluster vom Benutzer angegeben werden.

K-Mittel ++ Clusterbildung in Aktion
Abbildung 1 K-Mittel ++ Clusterbildung in Aktion

Das Demoprogramm Cluster dann die Daten mit der k-Mittel ++ Algorithmus. Jede von 20 Datenelementen wird zu einem Cluster mit der ID 0, 1 oder 2 zugewiesen. Die Cluster-Zuweisungen werden in einem Array gespeichert, wobei Index des Arrays entspricht einem Datenindex und der Array-Wert der verbundenen Cluster-ID. Beispielsweise ist das endgültige clustering der Demodaten:

0 2 1 1 2 . . . 1

Dies zeigt Datenelement 0 (Höhe = 65.0, Gewicht = 220,0) ist 0 cluster zugewiesen, Datenelement 1 Cluster 2 zugeordnet ist, Datenelement 2 zugewiesen cluster 1, und so weiter. Die Demo schließt mit der Anzeige der Daten, gruppiert nach Cluster. Hier ist ein sehr klares Muster offenbart. Es gibt acht Menschen geprägt von mittlerer Höhe und schweres Gewicht sieben Menschen bei geringem Gewicht und kurzen Höhe und fünf Personen mit hohen Höhe und mittlerem Gewicht.

Dieser Artikel setzt voraus, Sie haben zumindest fortgeschrittene Programmierkenntnisse, aber nicht davon ausgehen, Sie wissen nichts über die k-Mittel ++ Algorithmus. Das Demoprogramm ist codiert mit c#, aber Sie sollten nicht viel Schwierigkeiten bei der Umgestaltung des Codes in eine andere Sprache, wie Python oder JavaScript. Der Demo-Code ist zu lang, in seiner Gesamtheit zu präsentieren, aber der vollständige Quellcode ist verfügbar in den Codedownload zu diesem Artikel.

Verständnis der K-Mittel ++ Algorithmus

Die k-Mittel ++ Algorithmus ist eine Variation des standard-k-Means-Algorithmus, also um zu verstehen, k-Mittel ++ Sie müssen zuerst die normale k-Means-verstehen. Der k-Means-Algorithmus hat eine interessante Geschichte, und wird manchmal von Lloyds Algorithmus bezeichnet. Das 'k' in k-Means bezieht sich auf die Anzahl der Cluster. In sehr hochrangigen Pseudocode ist die häufigste Form der k-Means-Norm trügerisch einfach:

pick k initial means
loop until no change
  assign each data item to closest mean
  compute new means based on new clusters
end loop

Trotz ihrer einfachen Erscheinung der Norm k-Means-Algorithmus ist in der Tat, sehr subtil und Umsetzung ist überraschend schwierig. Angenommen, die Daten werden von 20 Datenelementen Siehe besteht aus Abbildung 1, mit k auf 3 festgelegt. Der erste Schritt besteht darin drei der Datenelemente fungieren als Mittel zum anfänglichen auszuwählen. Ein gängiger Ansatz ist Datenelemente nach dem Zufallsprinzip ausgewählt. Angenommen, die drei zufällig ausgewählte sind Datenelemente Punkt 2 (59,0, 110,0) als Mittel der Cluster 0, Punkt 4 (75.0, 150.0) als Mittel der Cluster 1 und Punkt 6 (68,0, 230,0) als Mittel der Cluster 2.

Innerhalb der Hauptverarbeitungsschleife wird jedes Datenelement geprüft und Cluster mit engsten Mittelwert zugewiesen. Datenelement 0 (65,0, 220,0) würde also zu Cluster 2 zugeordnet werden, weil Element 0 annähert (68,0, 230.0) als zu den beiden anderen bedeutet. Jedes der restlichen 19 Datenelemente würde zu einem Cluster zugewiesen werden. Beachten Sie, dass die Datenelemente, die zunächst als Mittel ausgewählt wurden zum richtigen Cluster zugewiesen werden würde, weil der Abstand 0 wäre.

Nachdem jedes Datenelement eines der Cluster zugewiesen ist, wird ein neues Mittel für jeden Cluster berechnet. Angenommen Sie, dieses Clusters 0 derzeit nur drei Datenelemente enthält: (59.0, 110.0), (70.0, 210.0), (61.0, 130.0). Das neue Mittel für diesen Cluster wäre:

( (59 + 70 + 61)/3, (110 + 210 + 130)/3 ) =
(190/3, 450/3) =
(63.3, 150.0)

Neue Mittel für Cluster 1 und 2 würde ebenso berechnet werden. Bekanntmachung der neuen Mittel sind nicht unbedingt zu den eigentlichen Daten-Elementen mehr. Technisch, jede neue Mittel ist ein "Schwerpunkt", aber der Begriff "Mittelwert" wird häufig verwendet.

Nach dem Berechnen der neuen Mittel, ist jedes Datenelement erneut geprüft und den Cluster mit dem engsten neue Mittel zugewiesen. Die iterative Update-Cluster, Update-Mittel wird fortgesetzt, solange es keine Änderung in der Cluster-Zuordnungen.

Das alle klingt relativ einfach, aber eine Menge kann durch eine naive Implementierung der Norm k-Means-Algorithmus schief gehen. Insbesondere kann eine schlechte Auswahl für die erste Mittel zu Stabilisierung oder beides zu einer sehr schlechten clustering von Daten oder eine sehr lange Laufzeit führen. Wie sich herausstellt, sind gutes erste Mittel diejenigen, die nicht in unmittelbarer Nähe zueinander. Die k-Mittel ++ Algorithmus wählt ersten Mittel, die nahe beieinander sind, dann verwendet den Norm k-Means-Algorithmus für das clustering.

Die K-Initialisierung Mechanismus bedeutet ++

In hochrangigen Pseudocode die k-Mittel ++ Initialisierung Mechanismus wählen heißt:

select one data item at random as first mean
loop k-1 times
  compute distance from each item to closest mean
  select an item that has large distance-squared
    as next initial mean
end loop

Der Pseudocode ist trügerisch einfach. Die k-Mittel ++ Initialisierung Mechanismus wird illustriert, Abbildung 2. Es gibt neun Punkte, von die jede zwei Komponenten besteht. Die Anzahl der Cluster ist auf 3 festgelegt, so dass 3 Datenelemente als erste Mittel ausgewählt werden müssen.

K-Initialisierung Mechanismus bedeutet ++
Abbildung 2 K-Initialisierung Mechanismus bedeutet ++

Das Diagramm in Abbildung 2 zeigt die k-Mittel ++ Initialisierungsprozess nach zwei der drei ursprünglichen Mittel ausgewählt wurden. Die erste Initiale bedeuten bei (3, 6) wurde nach dem Zufallsprinzip ausgewählt. Dann die Distanz-kariert aus jeder der anderen 8 Datenelemente zum ersten Mittelwert berechnet wurde, und anhand dieser Informationen, bedeuten der zweite Vorlauf an (4, 3) (in einer Weise, die ich kurz erläutern werde) ausgewählt wurde.

Um ein Datenelement als dritte erste Mittel auszuwählen, wird der quadrierte Abstand zwischen jeder Datenpunkt und seinen engsten Mittelwert berechnet. Die Abstände werden als gestrichelte Linien dargestellt. Mithilfe dieser quadrierten Distanz-Werte das dritte Mittel ausgewählt werden, damit die Datenelemente mit kleinen quadratischen Abstand Werte eine geringe Wahrscheinlichkeit weisen, ausgewählt und Datenelemente mit großen quadratischen Abstand Werte haben eine hohe Wahrscheinlichkeit, ausgewählt. Diese Technik wird manchmal proportional Eignung Auswahl genannt.

Proportional-Eignung-Auswahl ist das Herz des k-Mittel ++ Initialisierung Mechanismus. Es gibt mehrere Möglichkeiten, proportional Eignung Auswahl zu implementieren. Das Demoprogramm verwendet eine Technik namens Roulette-Rad-Auswahl. In hochrangigen Pseudocode ist eine Form der Roulette-Rad-Auswahl:

p = random value between 0.0 and 1.0
create an array of cumulative probabilities
loop each cell of cum prob array
  if cum[i] >= p
    return i
  end if
end loop

Ein konkretes Beispiel wird zur Klärung Roulette-Rad-Auswahl. Angenommen Sie, es gibt vier Kandidaten-Elemente (0, 1, 2, 3) mit den zugehörigen Werten (20,0, 10.0, 40,0 30,0). Die Summe der Werte ist 20,0 + 40,0 + 10.0 + 30,0 = 100,0. Proportional-Eignung-Auswahl holt Element 0 mit Wahrscheinlichkeit 20.0/100.0 = 0,20; Wählen Sie Punkt 1 mit Wahrscheinlichkeit 10.0/100.0 = 0,10; Wählen Sie Punkt 2 mit Wahrscheinlichkeit 40.0/100.0 = 0,40; und wählen Sie Punkt 3 mit Wahrscheinlichkeit 30.0/100.0 = 0,30.

Wenn die Wahrscheinlichkeiten der Auswahl als (0.20, 0.10, 0,40 0,30) in einem Array gespeichert sind, können die kumulierten Wahrscheinlichkeiten in ein Array mit Werten (0.20, 0.30, 0,70 1,00) gespeichert werden. Nun, angenommen Sie, eine zufällige p mit Wert 0,83 generiert wird. Wenn i einen Arrayindex in das Array kumulierte Wahrscheinlichkeit ist wenn ich = 0, i [i] = 0.20, die nicht größer als p 0,83, =, sodass i um 1 erhöht. Jetzt = i [i] 0,30, die noch kleiner oder gleich p, daher i um 2 erhöht. Jetzt i [i] = 0,70, die noch kleiner oder gleich p, daher i auf 3 erhöht. Jetzt i [i] = 1,00, die größer als p ist, damit ich = 3 als das ausgewählte Element zurückgegeben.

Beachten Sie, dass die Abstände zwischen den kumulierten Wahrscheinlichkeiten unterscheiden, mit größeren Unterschieden, diese Elemente mit höheren Wahrscheinlichkeiten der Auswahl entsprechen.

Um zusammenzufassen, die k-Mittel ++ Algorithmus wählt erste Mittel, damit die Mittel unähnlich sind, dann verwendet den Norm k-Means-Algorithmus auf Clusterdaten. Der Initialisierungsprozess verwendet proportional Eignung-Auswahl, die auf verschiedene Weise umgesetzt werden kann. Die Demo-Programm verwendet Roulette Rad Auswahl.

Allgemeine Programmstruktur

Die allgemeine Struktur des Demo-Programm, mit einigen geringfügigen Änderungen, platzsparende präsentiert sich in Abbildung 3. Um das Demoprogramm zu erstellen, ich Visual Studio gestartet und erstellt ein neues C#-Konsolenanwendungsprojekt mit dem Namen KMeansPlus. Das Demoprogramm hat keine signifikante Microsoft .NET Framework Abhängigkeiten, also eine relativ neue Version von Visual Studio arbeiten.

Abbildung 3 Allgemeine Programmstruktur

using System;
using System.Collections.Generic;
namespace KMeansPlus
{
  class KMeansPlusProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin k-means++ demo");
      // All program code here
      Console.WriteLine("End k-means++ demo");
      Console.ReadLine();
    }
    public static int[] Cluster(double[][] rawData,
      int numClusters, int seed) { . . }
    public static double[][] InitMeans(int numClusters,
      double[][] data, int seed) { . . }
    private static double[][] Normalized(double[][] rawData) { . . }
    private static double[][] MakeMatrix(int rows, int cols) { . . }
    private static bool UpdateMeans(double[][] data,
      int[] clustering, double[][] means) { . . }
    private static bool UpdateClustering(double[][] data,
      int[] clustering, double[][] means) { . . }
    private static double Distance(double[] tuple,
      double[] mean) { . . }
    private static int MinIndex(double[] distances) { . . }
    static void ShowData(double[][] data, int decimals,
      bool indices, bool newLine) { . . }
    static void ShowVector(int[] vector, bool newLine) { . . }
    static void ShowClustered(double[][] data, int[] clustering,
      int numClusters, int decimals)
  }
} // ns

Nach der Vorlagencode in Laden der Editor im Fenster Projektmappen-Explorer, den, das ich auf Datei Program.cs klickte, benannte sie in aussagekräftigeren KMeansPlusProgram.cs und erlaubt Visual Studio Klasse Program automatisch umbenennen. Im Editor-Fenster am oberen Rand der Vorlage erzeugte Code habe ich gelöscht, alle Verweise auf Namespaces mit Ausnahme der auf der obersten Ebene System-Namespace und den Collections.Generic-Namespace.

Die Main-Methode beginnt mit dem Einrichten von 20 Rohdaten-Elemente:

double[][] rawData = new double[20][];
rawData[0] = new double[] { 65.0, 220.0 };
...
rawData[19] = new double[] { 61.0, 130.0 };

In einem nicht-Demo-Szenario würde Sie wahrscheinlich Daten aus einer Textdatei oder SQL-Datenbank lesen. Nach der Anzeige der Rohdaten, die mithilfe einer Programm definierte Hilfsmethode ShowData benannt, ist die Daten gruppiert:

int numClusters = 3;
int[] clustering = Cluster(rawData,   numClusters, 0);

Zwar gibt es einige Techniken, mit denen Sie die optimale Anzahl von Clustern zu erraten, verwenden in der Regel Sie Versuch und Irrtum. Die Cluster-Methode akzeptiert numerische Rohdaten zu Cluster in einer Matrix von Matrix-Stil-Matrix; die Anzahl der Cluster verwenden (ich hätte "k" verwendet, aber "NumClusters" ist besser lesbar); und einen Startwert für Zufallsgenerator verwendet.

Die Main-Methode schließt mit der Darstellung des Cluster Arrays und zeigt die Rohdaten von Cluster gruppiert:

ShowVector(clustering, true);
ShowClustered(rawData, clustering, numClusters, 1);

Ich habe eine statische Methode vorgehen, anstatt eine OOP-Ansatz. Cluster-Methode ruft vier Hilfsmethoden. Hilfsmethode Normalized akzeptiert eine Matrix der Rohdaten und gibt eine Matrix, wo die Daten normalisiert wurde, so dass alle Werte ungefähr die gleiche Größenordnung (in der Regel zwischen-6.0 und + 6.0 sind). Methode InitMeans implementiert die k-Mittel ++ Initialisierung Mechanismus. Methoden UpdateClustering und "updatemeans" Implementieren der zentrale Teile des standard-k-Means-Algorithmus.

Methoden InitMeans und UpdateClustering rufen beide Hilfsmethode, die Distanz, die die euklidische Distanz zwischen zwei Elementen zurückgibt. Beispielsweise wenn ein Daten-Tupel (3.0, 9.0, 5.0) und eine zweite Tupel ist (6.0, 2.0, 1.0), ist die euklidische Distanz zwischen den zwei Elementen:

Sqrt( (3-2)^2 + (9-6)^2 + (5-1)^2) ) =
Sqrt( 1 + 9 + 16 ) =
Sqrt(26) = 5.1

Andere Definitionen Distanz einsetzbar. Im allgemeinen k-Means- und k-Mittel ++ werden verwendet, um strikt numerische Daten als kategoriale Daten cluster.

Implementieren von K-Mittel ++

Der Code für Methode Cluster präsentiert sich in Abbildung 4. Cluster-Methode beginnt die Rohdaten zu normalisieren, so dass große Bauteile in Datenelementen (z. B. Gewicht Werte in der Demo) kleinere Komponenten (Höhenwerte) dominieren nicht. Die Demo benutzt Gaußschen Normalisierung. Zwei gemeinsame Alternativen sind die min-Max-Normalisierung und Größenordnung Normalisierung. Eine Design-Alternative ist zu normalisieren Ihre Rohdaten in eine Vorverarbeitungsschritt übergeben die normalisierten Daten direkt an die Methode Cluster.

Abbildung 4-Methode Cluster

public static int[] Cluster(double[][] rawData,
 int numClusters, int seed)
{
  double[][] data = Normalized(rawData);
  bool changed = true;
  bool success = true;
  double[][] means = InitMeans(numClusters, data, seed);
  int[] clustering = new int[data.Length];
  int maxCount = data.Length * 10;
  int ct = 0;
  while (changed == true && success == true &&
    ct < maxCount)
  {
    changed = UpdateClustering(data, clustering, means);
    success = UpdateMeans(data, clustering, means);
    ++ct;
  }
  return clustering;
}

Methode InitMeans implementiert die k-Mittel ++ Initialisierung Mechanismus und gibt eine Reihe von heißt sind weit voneinander in Bezug auf die euklidische Distanz. Innerhalb der Cluster Hauptschleife Methode UpdateClustering durchläuft jedes Datenelement und weist jedes Element des Clusters, der nächste aktuelle Mittel/Zentroide zugeordnet. Die Methode gibt false zurück, wenn es keine Änderung an Cluster-Zuordnungen (angibt, dass clustering abgeschlossen ist) oder wenn der neue Cluster in einem Cluster, die hat keine Datenelemente führen würde (Hinweis auf, dass etwas nicht stimmt). Eine Alternative ist, eine Ausnahme auf eine NULL-Count Cluster-Situation zu werfen.

Methode UpdateMeans durchläuft die Daten jeder Cluster zugewiesen und einen neuen Mittelwert/Achsenschwerpunkt für jeden Cluster berechnet. Die Methode gibt false zurück, wenn eine oder mehrere nicht berechnet werden kann, weil ein Cluster verfügt über keine Datenelemente.

Die Hauptschleife Cluster verwendet eine Funktionsüberprüfung der Graf um eine Endlosschleife zu verhindern. Der k-Means-Algorithmus in der Regel sehr schnell stabilisiert, aber es gibt keine Garantie dafür, dass der Algorithmus überhaupt zu stabilisieren wird. Der Wert der MaxCount ist 10 mal der Anzahl der Datenelemente, festgelegt, die willkürlich ist, sondern ist gut für mich in der Praxis gearbeitet.

Die Definition der Methode InitMeans beginnt mit:

public static double[][] InitMeans(int numClusters,
  double[][] data, int seed)
{
  double[][] means = MakeMatrix(numClusters, data[0].Length);
  List<int> used = new List<int>();
...

Array von Arrays landestypischer Matrix namens Mittel hält die Methode zurück, wo der Zeilenindex ist eine Cluster-ID und jede Zeile ist ein Array, das die Komponenten des zugehörigen mittleren hält. Die Liste < Int > Namens verwendet enthält Indizes von Datenelementen, die zugewiesen wurden als anfängliche Mittel, sodass doppelte anfängliche bedeutet, dass verhindert werden können. Diese Vorgehensweise wird vorausgesetzt, dass keine Datenelemente mit identischen Werten vorhanden sind. Beim clustering hängt Umgang mit doppelten Datenelementen Ihr spezielles Problem-Szenario. Eine Alternative zum Entfernen von doppelten Elementen aus den Quelldaten ist doppelte Elemente nach ihrer Frequenz Gewicht.

Als nächstes ist das erste ursprüngliche Mittel ausgewählt und gespeichert:

Random rnd = new Random(seed);
int idx = rnd.Next(0, data.Length);
Array.Copy(data[idx], means[0], data[idx].Length);
used.Add(idx);

Das erste ursprüngliche Mittel wird nach dem Zufallsprinzip aus alle Datenelemente ausgewählt. Die ersten Mittel sind vorhandene Datenelemente und sie werden auch als Medoids bezeichnet.

Nächsten, eine Schleife erstellt wird, wählen Sie die verbleibenden k-1 bedeutet:

for (int k = 1; k < numClusters; ++k)
{
  double[] dSquared = new double[data.Length];
  int newMean = -1;
...

Array-dSquared hält die quadrierten Abstände zwischen jedes Datenelement und die nächste vorhandene anfängliche bedeuten. Variable NewMean enthält das Inhaltsverzeichnis ein Datenelement, das die nächsten ersten bedeuten wird. Als nächstes jedes Datenelement (normalisierte) wird untersucht und dessen dSquared-Wert berechnet und gespeichert:

for (int i = 0; i < data.Length; ++i)
{
  if (used.Contains(i) == true) continue;
  double[] distances = new double[k];
  for (int j = 0; j < k; ++j)
    distances[j] = Distance(data[i], means[k]);
  int m = MinIndex(distances);
  dSquared[i] = distances[m] * distances[m];
}

Die Überprüfung, um festzustellen, ob ein Datenelement wurde bereits eine anfängliche Mittel verwendet nicht wirklich erforderlich, da, wenn das Element verwendet wurde, die Entfernung der Mittelwert des Zertifikatantragstellers im Quadrat die Entfernung auf sich selbst werden, also 0. Das Array mit dem Namen Distanzen enthält euklidischen Abstände aus dem aktuellen Datenelement zu jedem vorhandenen k-Initial Mittel, die bisher ausgewählt wurden.

Erinnern Sie, dass die euklidische Distanz in der Distanz-Methode die Quadratwurzel aus der Summe der quadrierten Differenzen zwischen Datenkomponenten Element nimmt. Da k-Mittel ++ quadrierte Entfernungen verwendet, die Quadrierung Operation in InitMeans macht die Quadratwurzel-Operation in Distanz. Daher könnten Sie den Code vereinfachen, durch die Definition einer Methode, die quadratischen Abstand direkt zurückgibt.

Als nächstes ist die Schleife abgetastet kumulierten Wahrscheinlichkeiten für Roulette-Rad-Auswahl bereit:

double p = rnd.NextDouble();
double sum = 0.0;
for (int i = 0; i < dSquared.Length; ++i)
  sum += dSquared[i];
double cumulative = 0.0;
int ii = 0;
int sanity = 0;

Ein zufälliger Wert zwischen 0.0 und 1.0 generiert und die Summe der quadrierten Abstände wird berechnet, wie im Abschnitt beschreiben proportional Eignung Auswahl erklärt. Statt explizit erstellen ein Array von kumulierten Wahrscheinlichkeiten, ist es effizienter, die aktuelle kumulative Wahrscheinlichkeit dynamisch zu generieren.

Jeder kumulative Wahrscheinlichkeit ist berechnet und geprüft in einer While Schleife, dass implementiert-Rad-Auswahl Roulette:

while (sanity < data.Length * 2)
{
  cumulative += dSquared[ii] / sum;
  if (cumulative >= p && used.Contains(ii) == false)
  {
    newMean = ii; // the chosen index
    used.Add(newMean); // don't pick again
    break;
  }
  ++ii; // next candidate
  if (ii >= dSquared.Length) ii = 0; // past the end
  ++sanity;
}

Die While-Schleife Fortschritte bis der kumulative Wahrscheinlichkeitswert größer oder gleich dem zufälligen p-Wert ist. Doppelte anfängliche bedeutet kann nicht jedoch zugelassen werden, so ist der ausgewählte Mittelwert in der Liste "verwendet" < Int >, das nächste verfügbare Datenelement ausgewählt ist. Wenn der Index Ii nach dem Ende der Daten ausgeführt wird, wird es auf 0 zurückgesetzt. Beachten Sie, dass, wenn ein Datenelement als ein Mittel der ersten bereits ausgewählt wurde, das nächste Element der verfügbaren Daten wahrscheinlich wird nicht sehr wahrscheinlich nächsten Element.

Methode InitMeans schließt mit dem Speichern des ausgewählten anfänglichen Mittelwert und ausgewählte Mittel vom Array zurückgegeben:

...
    Array.Copy(data[newMean], means[k], data[newMean].Length);
  } // k, each remaining mean
  return means;
} // InitMean

Die InitMeans-Methode soll finden k unähnlich Datenelemente als erste Mittel verwendet werden. Roulette-Rad-Auswahl garantiert nicht, dass die gewählten Mittel maximal voneinander unterscheiden sind, und es gibt eine sehr kleine Chance, dass das ausgewählte Mittel ganz nahe beieinander könnte. Daher sollten Sie die Methode InitMeans umgestalten, damit Roulette Rad Auswahl mehrfach verwendet wird, um Kandidaten Mengen der Mittel zu generieren, und dann wieder das Set mit Mitteln, die am meisten von einander abweichen.

Nachbereitung

Dieser Artikel basiert auf dem Forschungspapier 2007-"K-Mittel ++: Die Vorteile der sorgfältigen Seeding"D. Arthur und S. Vassilvitskii. Wie in der Regel bei Forschungsarbeiten der Fall ist, werden praktisch keine Implementierungsdetails zugewiesen. Jedoch das Papier sorgfältig erklärt wie k-Mittel ++ Initialisierung funktioniert und stellt theoretische Grenzen für ihr Verhalten.

Dr. James McCaffrey arbeitet für Microsoft Research in Redmond, Washington, USA. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und Bing. Dr. McCaffrey erreichen Sie unter jammc@microsoft.com.

Dank der folgenden Microsoft Research technischen Experten für die Überprüfung dieses Artikels: Kirk Olynyk