Technische Referenz für den Microsoft Clustering-Algorithmus

Beim EM-Clustering optimiert der Algorithmus iterativ ein Clusteranfangsmodell, um die Daten anzupassen, und bestimmt die Wahrscheinlichkeit, mit der ein Datenpunkt in einem Cluster vorhanden ist. Der Algorithmus beendet den Prozess, wenn das probabilistische Modell den Daten entspricht. Die Funktion, mit der bestimmt wird, ob die Daten übereinstimmen, ist der Log-Likelihood für die Daten unter Vorgabe des Modells.

Wenn während des Prozesses leere Cluster generiert werden oder die Mitgliedschaft eines oder mehrerer Cluster unter einen vorgegebenen Schwellenwert fällt, werden den Clustern mit niedrigen Auffüllungen bei neuen Punkten neue Ausgangswerte zugewiesen und der EM-Algorithmus wird erneut ausgeführt.

Die Ergebnisse der EM-Clustermethode sind probabilistisch. Dies bedeutet, dass jeder Datenpunkt zu allen Clustern gehört, jede Zuweisung eines Datenpunkts zu einem Cluster jedoch eine andere Wahrscheinlichkeit hat. Da die Methode ein Überlappen der Cluster zulässt, überschreitet die Summe der Elemente aller Cluster möglicherweise die Gesamtelemente im Trainingssatz. In den Miningmodellergebnissen werden Ergebnisse, die Unterstützung angeben, angepasst, um dies zu berücksichtigen.

Der EM-Algorithmus ist der in Microsoft Clustering-Modellen verwendete Standardalgorithmus. Dieser Algorithmus wird als Standard verwendet, da er mehrere Vorteile gegenüber dem K-Means-Clustering bietet:

• Erfordert höchstens einen Datenbankscan.

• Funktioniert trotz des beschränkten Arbeitsspeichers (RAM).

• Verfügt über die Fähigkeit, einen Vorwärtscursor zu verwenden.

• Übertrifft Samplingansätze.

Die Microsoft-Implementierung stellt zwei Optionen bereit: skalierbares und nicht skalierbares EM. Standardmäßig werden beim skalierbaren EM die ersten 50.000 Datensätze verwendet, um dem Anfangsscan Werte zuzuweisen. Ist dieser Vorgang erfolgreich, verwendet das Modell nur diese Daten. Wenn das Modell mit 50.000 Datensätzen nicht geeignet ist, werden weitere 50.000 Datensätze gelesen. In nicht skalierbarem EM wird das ganze Dataset unabhängig von seiner Größe gelesen. Mit dieser Methode werden unter Umständen zwar genauere Cluster erstellt, die Arbeitsspeicheranforderungen können jedoch erheblich sein. Da skalierbares EM-Clustering mit einem lokalen Puffer arbeitet, erfolgt die Iteration durch die Daten deutlich schneller und der Algorithmus nutzt den CPU-Arbeitsspeichercache besser aus als das nicht skalierbare EM-Clustering. Darüber hinaus ist das skalierbare EM dreimal so schnell wie das nicht skalierbare EM, auch wenn alle Daten in den Hauptspeicher passen. In den meisten Fällen führt die Verbesserung der Leistung nicht zu einer geringeren Qualität des Gesamtmodells.

Einen technischen Bericht mit einer Beschreibung der EM-Implementierung im Microsoft Clustering-Algorithmus finden Sie unter Scaling EM (Expectation Maximization) Clustering to Large Databases (möglicherweise nur in englischer Sprache).

K-Means-Clustering ist eine gängige Methode zum Zuweisen der Clustermitgliedschaft, indem Unterschiede zwischen Elementen eines Clusters minimiert und die Entfernung zwischen den Clustern gleichzeitig maximiert werden. Das Wort "Means" im Begriff K-Means bezieht sich auf den Schwerpunkt des Clusters. Hierbei handelt es sich um einen willkürlich ausgewählten Datenpunkt, der so lange iterativ optimiert wird, bis er das genaue arithmetische Mittel aller Datenpunkte des Clusters repräsentiert. Das "K" verweist auf eine beliebige Anzahl von Punkten, mit denen dem Clusterprozess Anfangswerte zugewiesen werden. Der K-Means-Algorithmus berechnet das Quadrat der euklidischen Entfernungen zwischen Datensätzen in einem Cluster und dem Vektor, der das arithmetische Clustermittel darstellt, und konvergiert zu einer endgültigen Menge von K-Clustern, wenn diese Summe den Mindestwert erreicht.

Der K-Means-Algorithmus weist jeden Datenpunkt genau einem Cluster zu und lässt keine Unsicherheit in Bezug auf die Mitgliedschaft zu. Die Mitgliedschaft in einem Cluster wird als Entfernung vom Schwerpunkt ausgedrückt.

In der Regel wird der K-Means-Algorithmus zum Erstellen von Clustern kontinuierlicher Attribute verwendet, wobei die Berechnung der Entfernung zu einem arithmetischen Mittel unkompliziert ist. Die Microsoft-Implementierung passt die K-Means-Methode jedoch mithilfe von Wahrscheinlichkeiten an, um diskrete Attribute zu gruppieren.  Für diskrete Attribute wird die Entfernung eines Datenpunkts von einem bestimmten Cluster wie folgt berechnet:

1 - P (Datenpunkt, Cluster)

Hinweis

Der Microsoft Clustering-Algorithmus macht die zur Berechnung von K-Means verwendete Abstandsfunktion nicht verfügbar. Abstandsmaße stehen im abgeschlossenen Modell nicht zur Verfügung. Sie können jedoch mithilfe einer Vorhersagefunktion einen Wert zurückgeben, der dem Abstand entspricht, wobei der Abstand als Wahrscheinlichkeit eines Datenpunkts, der zum Cluster gehört, berechnet wird. Weitere Informationen finden Sie unter ClusterProbability (DMX).

Der K-Means-Algorithmus bietet zwei Methoden zum Abfragen des Datasets: die nicht skalierbare K-Means-Methode oder die skalierbare K-Means-Methode. Bei der nicht skalierbaren K-Means-Methode wird das gesamte Dataset geladen und ein Clustering durchlaufen. Dahingegen verwendet der Algorithmus bei der skalierbaren K-Means-Methode die ersten 50.000 Fälle und liest zusätzliche Fälle nur dann, wenn weitere Daten erforderlich sind, um eine passende Übereinstimmung zwischen Modell und Daten zu erzielen.

In SQL Server 2008 wurde die Standardkonfiguration des Microsoft Clustering-Algorithmus geändert, so dass dieser den internen Parameter NORMALIZATION = 1 verwendet. Die Normalisierung erfolgt unter Verwendung von z-Ergebnis-Statistiken und geht von einer Normalverteilung aus. Das Ziel dieses geänderten Standardverhaltens bestand darin, die Auswirkung von Attributen mit großen Magnituden und vielen Ausreißern zu minimieren. Die z-Ergebnis-Normalisierung kann jedoch zu einer Änderung der Clusteringergebnisse in anormalen (z. B. gleichmäßigen) Verteilungen führen. Durch diese Implementierung stellen Kunden, die Lösungen von SQL Server 2005 Analysis Services zu 2008 migrieren, möglicherweise fest, dass Clustermodelle jetzt unterschiedliche Ergebnisse erzeugen. Um eine Normalisierung zu vermeiden, jedoch das gleiche Verhalten wie mit dem K-Means-Clustering-Algorithmus in SQL Server 2005 zu erzielen, können Sie im Dialogfeld Parametereinstellungen den benutzerdefinierten Parameter NORMALIZATION hinzuzufügen und dessen Wert auf 0 festlegen.

Hinweis
Der NORMALIZATION-Parameter ist eine interne Eigenschaft des Microsoft Clustering-Algorithmus und wird nicht unterstützt. Im Allgemeinen wird die Verwendung von Normalisierung in Clusteringmodellen empfohlen, da sie die Modellergebnisse verbessert.

In der folgenden Tabelle werden die Parameter beschrieben, die mit dem Microsoft Clustering-Algorithmus verwendet werden können. Diese Parameter wirken sich sowohl auf die Leistung als auch auf die Genauigkeit des resultierenden Miningmodells aus.

• CLUSTERING_METHOD
  Gibt an, welche Clustermethode der Algorithmus verwendet. Die folgenden Clustermethoden stehen zur Verfügung:

  ID	Methode
  1	EM skalierbar
  2	EM nicht skalierbar
  3	K-Means skalierbar
  4	K-Means nicht skalierbar

  Die Standardeinstellung ist 1 (EM skalierbar).

• CLUSTER_COUNT
  Gibt die ungefähre Anzahl der vom Algorithmus zu erstellenden Cluster an. Falls die ungefähre Anzahl von Clustern nicht aus den Daten erstellt werden kann, erstellt der Algorithmus so viele Cluster wie möglich. Durch Festlegen des CLUSTER_COUNT-Parameters auf 0 wird der Algorithmus zur Verwendung heuristischer Methoden veranlasst, um die Anzahl von zu erstellenden Clustern so gut wie möglich zu bestimmen.

  Der Standardwert ist 10.

• CLUSTER_SEED
  Gibt den numerischen Ausgangswert für die zufällige Clustergenerierung für die Anfangsphase der Modellerstellung an.

  Durch Ändern dieses Werts können Sie die Art und Weise ändern, wie Anfangscluster erstellt werden, und anschließend Modelle vergleichen, die mit unterschiedlichen Anfangswerten erstellt wurden. Wenn der Anfangswert geändert wird, die gefundenen Cluster sich jedoch nicht erheblich ändern, kann das Modell als relativ stabil betrachtet werden.

  Der Standardwert ist 0.

• MINIMUM_SUPPORT
  Gibt die Mindestanzahl von Fällen an, die erforderlich sind, um einen Cluster zu erstellen. Wenn die Zahl der Fälle im Cluster kleiner als dieser Wert ist, gilt der Cluster als leer und wird verworfen.

  Wenn Sie diese Zahl zu hoch festgelegt haben, entgehen Ihnen möglicherweise gültige Cluster.

  Hinweis
  Wenn Sie die Standardclustermethode EM verwenden, haben einige Cluster möglicherweise einen niedrigeren Unterstützungswert als der angegebene Wert. Dies liegt daran, dass jeder Fall im Hinblick auf seine Mitgliedschaft in allen möglichen Clustern ausgewertet wird und für einige Cluster möglicherweise nur minimale Unterstützung besteht.

  Die Standardeinstellung ist 1.

• MODELLING_CARDINALITY
  Gibt die Anzahl von Stichprobenmodellen an, die während des Clusterprozesses erstellt wurden.

  Eine Reduzierung der Anzahl von Kandidatenmodellen kann zwar zur Verbesserung der Leistung führen, beinhaltet jedoch das Risiko, einige gute Kandidatenmodelle zu verpassen.

  Der Standardwert ist 10.

• STOPPING_TOLERANCE
  Gibt den Wert an, mit dem bestimmt wird, wann Konvergenz erreicht ist und die Modellerstellung mit dem Algorithmus abgeschlossen ist. Konvergenz ist erreicht, wenn die Gesamtänderung der Clusterwahrscheinlichkeiten kleiner als das Verhältnis des STOPPING_TOLERANCE-Parameters geteilt durch die Modellgröße ist.

  Der Standardwert ist 10.

• SAMPLE_SIZE
  Gibt die Anzahl von Fällen an, die bei jedem Durchlauf des Algorithmus verwendet werden, wenn der CLUSTERING_METHOD-Parameter auf eine der skalierbaren Clustermethoden festgelegt ist. Das Festlegen des SAMPLE_SIZE-Parameters auf 0 bewirkt eine Clustererstellung für das gesamte Dataset in einem einzelnen Durchlauf. Das gesamte Dataset in einem einzelnen Durchlauf zu laden, kann zu Problemen mit dem Arbeitsspeicher und der Leistung führen.

  Der Standardwert lautet 50.000.

• MAXIMUM_INPUT_ATTRIBUTES
  Gibt die maximale Anzahl von Eingabeattributen an, die der Algorithmus verarbeiten kann, bevor die Funktionsauswahl aufgerufen wird. Wenn dieser Wert auf 0 festgelegt wird, ist keine maximale Anzahl von Attributen angegeben.

  Durch Erhöhen der Attributanzahl kann die Leistung erheblich beeinträchtigt werden.

  Die Standardeinstellung ist 255.

• MAXIMUM_STATES
  Gibt die maximale Anzahl der vom Algorithmus unterstützten Attributstatus an. Wenn ein Attribut mehr Status als die maximale Anzahl hat, verwendet der Algorithmus die gebräuchlichsten Status und ignoriert die restlichen Status.

  Durch Erhöhen der Statusanzahl kann die Leistung erheblich beeinträchtigt werden.

  Die Standardeinstellung ist 100.

Der Algorithmus unterstützt die folgenden Modellierungsflags. Modellierungsflags werden beim Erstellen der Miningstruktur oder des Miningmodells definiert. Die Modellierungsflags geben an, wie die Werte in den einzelnen Spalten während der Analyse behandelt werden.

Der Microsoft Clustering-Algorithmus unterstützt bestimmte Eingabespalten und vorhersagbare Spalten. Diese sind in der nachstehenden Tabelle aufgelistet. Weitere Informationen zur Bedeutung der Inhaltstypen in einem Miningmodell finden Sie unter Inhaltstypen (Data Mining).

Hinweis
Zyklische und sortierte Inhaltstypen werden unterstützt, der Algorithmus behandelt sie jedoch als diskrete Werte und führt keine spezielle Verarbeitung durch.