Technische Referenz für den Microsoft Clustering-Algorithmus

Gilt für: SQL Server 2019 und früher Analysis Services Azure Analysis Services Fabric/Power BI Premium

In diesem Abschnitt wird die Implementierung des Microsoft Clustering-Algorithmus erläutert, einschließlich der Parameter, mit denen Sie das Verhalten von Clusteringmodellen steuern können. Außerdem bietet der Abschnitt Anleitungen zur Verbesserung der Leistung beim Erstellen und Verarbeiten von Clustermodellen.

Weitere Informationen zum Verwenden von Clustermodellen finden Sie in folgenden Themen:

• Mingingmodellinhalt von Clustermodellen (Analysis Services - Data Mining)

• Beispiele für Clustermodellabfragen

Implementierung des Microsoft Clustering-Algorithmus

Der Microsoft Clustering-Algorithmus bietet zwei Methoden zum Erstellen von Clustern und zum Zuweisen von Datenpunkten zu den Clustern. Die erste Methode, der K-Means-Algorithmus , ist eine harte Clustermethode. Dies bedeutet, dass ein Datenpunkt nur zu einem Cluster gehören kann und dass für die Mitgliedschaft der einzelnen Datenpunkte in diesem Cluster nur eine einzige Wahrscheinlichkeit berechnet wird. Die zweite Methode, die Expectation Maximization (EM) -Methode, ist eine weiche Clustermethode . Dies bedeutet, dass ein Datenpunkt stets zu mehreren Clustern gehört und dass für jede Kombination aus Datenpunkt und Cluster eine Wahrscheinlichkeit berechnet wird.

Den zu verwendenden Algorithmus können Sie durch Festlegen des CLUSTERING_METHOD -Parameters auswählen. Die Standardmethode für das Clustering ist die skalierbare EM-Methode.

EM-Clustering

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, der die Implementierung von EM im Microsoft Clustering-Algorithmus beschreibt, finden Sie unter Skalieren von EM (Erwartungsmaximierung) von Clustering zu großen Datenbanken.

K-Means Clustering

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 diskrete Clusterattribute an. Für diskrete Attribute wird die Entfernung eines Datenpunkts von einem bestimmten Cluster wie folgt berechnet:

1 - P (Datenpunkt, Cluster)

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.

Updates des Microsoft Clustering-Algorithmus in SQL Server 2008

In SQL Server 2008 wurde die Standardkonfiguration des Microsoft-Clusteringalgorithmus geändert, um den internen Parameter NORMALIZATION = 1 zu verwenden. Normalisierung erfolgt unter Verwendung der Z-Ergebnisstatistiken, und es wird eine Normalverteilung angenommen. Ziel dieses geänderten Standardverhaltens ist, 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. 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.

Anpassen des Microsoft Clustering-Algorithmus

Der Microsoft Clustering-Algorithmus unterstützt mehrere Parameter, die das Verhalten, die Leistung und die Genauigkeit des resultierenden Miningmodells beeinflussen.

Festlegen von Algorithmusparametern

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 vom Algorithmus verwendet wird. Die folgenden Clustermethoden stehen zur Verfügung:

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 in der 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.

Die Standardeinstellung 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.

Der Standardwert ist 1.

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

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 ist 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.

Der Standardwert 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.

Der Standard ist 100.

Modellierungsflags

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.

Anforderungen

Ein Clustermodell muss eine Schlüsselspalte und Eingabespalten enthalten. Sie können Eingabespalten auch als vorhersagbar definieren. Auf Predict Only festgelegte Spalten werden nicht verwendet, um Cluster zu erstellen. Die Verteilung dieser Werte in den Clustern wird berechnet, nachdem die Cluster erstellt sind.

Eingabespalten und vorhersagbare Spalten

Der Microsoft Clustering-Algorithmus unterstützt die spezifischen Eingabespalten und vorhersagbaren Spalten, die in der folgenden Tabelle aufgeführt sind. Weitere Informationen dazu, was die Inhaltstypen bedeuten, wenn sie in einem Miningmodell verwendet werden, finden Sie unter Inhaltstypen (Data Mining).

Weitere Informationen

Microsoft Clustering-Algorithmus
Beispiele für Clustermodellabfragen
Mingingmodellinhalt von Clustermodellen (Analysis Services - Data Mining)