Technische Referenz zum Microsoft Clustering-Algorithmus

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 enthält sie Anleitungen zur Verbesserung der Leistung beim Erstellen und Verarbeiten von Clusteringmodellen.

Weitere Informationen zur Verwendung von Clusteringmodellen finden Sie in den folgenden Themen:

• Miningmodell-Inhalt für Clustering-Modelle (Analysis Services - Data Mining)

• Beispiele für Clusteringmodellabfragen

Implementierung des Microsoft Clustering-Algorithmus

Der Microsoft Clustering-Algorithmus bietet zwei Methoden zum Erstellen von Clustern und das Zuweisen von Datenpunkten zu den Clustern. Der erste, der K-Mittel-Algorithmus , ist eine harte Clustering-Methode. Dies bedeutet, dass ein Datenpunkt nur zu einem Cluster gehören kann und dass eine einzelne Wahrscheinlichkeit für die Mitgliedschaft der einzelnen Datenpunkte in diesem Cluster berechnet wird. Die zweite Methode, die Em-Methode (Erwartungsmaximierung ), ist eine weiche Clusteringmethode . Dies bedeutet, dass ein Datenpunkt immer zu mehreren Clustern gehört und dass eine Wahrscheinlichkeit für jede Kombination von Datenpunkt und Cluster berechnet wird.

Sie können den zu verwendenden Algorithmus auswählen, indem Sie den CLUSTERING_METHOD-Parameter festlegen. Die Standardmethode für clustering ist skalierbare EM.

EM-Clustering

Im EM-Clustering verfeinert der Algorithmus iterativ ein anfängliches Clustermodell, um die Daten anzupassen, und bestimmt die Wahrscheinlichkeit, dass ein Datenpunkt in einem Cluster vorhanden ist. Der Algorithmus beendet den Prozess, wenn das probabilistische Modell zu den Daten passt. Die Funktion, die verwendet wird, um die Anpassung zu bestimmen, ist die Protokollwahrscheinlichkeit der Daten, die das Modell gegeben hat.

Wenn leere Cluster während des Prozesses generiert werden oder die Mitgliedschaft eines oder mehrerer Cluster unter einen bestimmten Schwellenwert fällt, werden die Cluster mit niedrigen Populationen an neuen Punkten erneut eingeteilt, und der EM-Algorithmus wird erneut ausgeführt.

Die Ergebnisse der EM-Clusteringmethode sind probabilistisch. Dies bedeutet, dass jeder Datenpunkt zu allen Clustern gehört, aber jede Zuordnung eines Datenpunkts zu einem Cluster hat eine andere Wahrscheinlichkeit. Da die Methode die Überlappung von Clustern ermöglicht, kann die Summe der Elemente in allen Clustern die Gesamtzahl der Elemente im Schulungssatz überschreiten. In den Ergebnissen des Miningmodells werden Punktewertungen, die die Unterstützung angeben, angepasst, um dieses zu berücksichtigen.

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

• Erfordert höchstens einen Datenbankscan.

• Funktioniert trotz eingeschränktem Arbeitsspeicher (RAM).

• Verfügt über die Möglichkeit, einen Vorwärtscursor zu verwenden.

• Übertrifft Stichprobenverfahren.

Die Microsoft-Implementierung bietet zwei Optionen: skalierbare und nicht skalierbare EM. Standardmäßig werden in skalierbarem EM die ersten 50.000 Datensätze verwendet, um den anfänglichen Scan zu initialisieren. Wenn dies erfolgreich ist, verwendet das Modell diese Daten nur. Wenn das Modell nicht mit 50.000 Datensätzen passen kann, werden weitere 50.000 Datensätze gelesen. In nicht skalierbarem EM wird das gesamte Dataset unabhängig von seiner Größe gelesen. Diese Methode kann genauere Cluster erstellen, die Speicheranforderungen können jedoch erheblich sein. Da skalierbare EM auf einem lokalen Puffer ausgeführt wird, ist das Durchlaufen der Daten viel schneller, und der Algorithmus nutzt den CPU-Speichercache wesentlich besser als nicht skalierbare EM. Darüber hinaus ist skalierbare EM dreimal schneller als nicht skalierbare EM, auch wenn alle Daten in den Hauptspeicher passen können. In den meisten Fällen führt die Leistungsverbesserung nicht zu einer geringeren Qualität des vollständigen Modells.

Einen technischen Bericht, der die Implementierung von EM im Microsoft Clustering-Algorithmus beschreibt, finden Sie unter Scaling EM (Erwartungsmaximierung) Clustering in große Datenbanken.

K-Means Clustering

K-means Clustering ist eine bekannte Methode zum Zuweisen der Clustermitgliedschaft, indem die Unterschiede zwischen Elementen in einem Cluster minimiert werden, während der Abstand zwischen Clustern maximiert wird. Das "Mittel" in k-Mittel bezieht sich auf das Zentrum des Clusters, bei dem es sich um einen datenpunkt handelt, der willkürlich ausgewählt und dann iterativ verfeinert wird, bis es den tatsächlichen Mittelwert aller Datenpunkte im Cluster darstellt. Das "k" bezieht sich auf eine beliebige Anzahl von Punkten, die zum Seeden des Clusteringprozesses verwendet werden. Der K-Mittelalgorithmus berechnet die quadratischen Euklidischen Entfernungen zwischen Datensätzen in einem Cluster und dem Vektor, der den Clustermittelwert darstellt, und konvergiert in einem endgültigen Satz von K-Clustern, wenn diese Summe seinen Minimalwert erreicht.

Der K-Mittelalgorithmus weist jedem Datenpunkt genau einen Cluster zu und lässt keine Unsicherheit in der Mitgliedschaft zu. Die Mitgliedschaft in einem Cluster wird als Abstand vom Zentrum ausgedrückt.

In der Regel wird der K-Mittel-Algorithmus zum Erstellen von Clustern fortlaufender Attribute verwendet, wobei die Berechnung des Abstands zu einem Mittel einfach ist. Die Microsoft-Implementierung passt die Methode "k-means" jedoch mithilfe von Wahrscheinlichkeiten an diskrete Clusterattribute an. Bei diskreten Attributen wird der Abstand eines Datenpunkts von einem bestimmten Cluster wie folgt berechnet:

1 – P(Datenpunkt, Cluster)

Hinweis

Der Microsoft Clustering-Algorithmus gibt die Entfernungsfunktion, die bei der Berechnung von K-Mitteln verwendet wird, nicht bekannt, und die Entfernungsmaße stehen im fertigen Modell nicht zur Verfügung. Sie können jedoch eine Vorhersagefunktion verwenden, um einen Wert zurückzugeben, der dem Abstand entspricht, wobei der Abstand als Wahrscheinlichkeit eines Datenpunkts berechnet wird, der zum Cluster gehört. Weitere Informationen finden Sie unter ClusterProbability (DMX).

Der K-Means-Algorithmus stellt zwei Methoden zum Sampling des Datasets bereit: nicht skalierbare K-Means, bei denen das gesamte Dataset geladen und ein Clusterdurchlauf durchgeführt wird, oder skalierbare K-Means, bei denen der Algorithmus die ersten 50.000 Fälle verwendet und nur dann weitere Fälle einliest, wenn mehr Daten benötigt werden, um eine gute Modellanpassung zu erzielen.

Updates für den 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. Die Normalisierung wird mithilfe von Z-Score-Statistiken durchgeführt und nimmt eine normale Verteilung an. Die Absicht dieser Änderung im Standardverhalten besteht darin, die Auswirkung von Attributen zu minimieren, die möglicherweise große Ausmaße und viele Ausreißer aufweisen. Die Normalisierung der Z-Bewertung kann jedoch die Clusteringergebnisse für nicht normale Verteilungen (z. B. einheitliche Verteilungen) ändern. Um die Normalisierung zu verhindern und dasselbe Verhalten wie der K-mittel-Clusteringalgorithmus in SQL Server 2005 zu erhalten, können Sie das Dialogfeld "Parametereinstellungen " verwenden, um den benutzerdefinierten Parameter, NORMALIZATION, hinzuzufügen und den Wert auf 0 festzulegen.

Hinweis

Der NORMALIZATION-Parameter ist eine interne Eigenschaft des Microsoft Clustering-Algorithmus und wird nicht unterstützt. Im Allgemeinen wird die Verwendung der Normalisierung in Clustermodellen empfohlen, um die Modellergebnisse zu verbessern.

Anpassen des Microsoft Clustering-Algorithmus

Der Microsoft Clustering-Algorithmus unterstützt mehrere Parameter, die sich auf das Verhalten, die Leistung und genauigkeit des resultierenden Miningmodells auswirken.

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 die Genauigkeit des resultierenden Miningmodells aus.

KLUSTERIERUNGSMETHODE
Gibt die Clusteringmethode für den zu verwendenden Algorithmus an. Die folgenden Clusteringmethoden sind verfügbar:

Identifikationsnummer	Methode
1	Skalierbare EM
2	Nicht skalierbare EM
3	Skalierbares K-Means
4	Nicht skalierbares K-Means.

Der Standardwert ist 1 (skalierbare EM).

Clusteranzahl
Gibt die ungefähre Anzahl von Clustern an, die vom Algorithmus erstellt werden sollen. Wenn die ungefähre Anzahl von Clustern nicht aus den Daten erstellt werden kann, erstellt der Algorithmus so viele Cluster wie möglich. Das Festlegen der CLUSTER_COUNT auf 0 bewirkt, dass der Algorithmus Heuristiken verwendet, um die Anzahl der zu erstellenden Cluster am besten zu bestimmen.

Der Standardwert ist 10.

Cluster-Saatgut
Gibt die Startnummer an, die zum zufälligen Generieren von Clustern für die erste Phase des Modellaufbaus verwendet wird.

Durch Ändern dieser Zahl können Sie die Art und Weise ändern, wie die anfänglichen Cluster erstellt werden, und dann Modelle vergleichen, die mit unterschiedlichen Samen erstellt wurden. Wenn der Seed geändert wird, die gefundenen Cluster sich jedoch nicht erheblich verändern, kann das Modell als relativ stabil betrachtet werden.

Der Standardwert ist 0.

MINDESTUNTERSTÜTZUNG
Gibt die Mindestanzahl der Fälle an, die zum Erstellen eines Clusters erforderlich sind. Wenn die Anzahl der Fälle im Cluster niedriger als diese Zahl ist, wird der Cluster als leer behandelt und verworfen.

Wenn Sie diese Zahl zu hoch festlegen, verpassen Sie möglicherweise gültige Cluster.

Hinweis

Wenn Sie EM verwenden, bei der es sich um die Standardmäßige Clusteringmethode handelt, weisen einige Cluster möglicherweise einen Unterstützungswert auf, der niedriger als der angegebene Wert ist. Dies liegt daran, dass jeder Fall für seine Mitgliedschaft in allen möglichen Clustern ausgewertet wird, und für einige Cluster gibt es möglicherweise nur minimale Unterstützung.

Der Standardwert ist 1.

Modellierung_Kardinalität
Gibt die Anzahl der Beispielmodelle an, die während des Clusteringprozesses erstellt werden.

Durch die Reduzierung der Anzahl von Kandidatenmodellen kann die Leistung beim Fehlen einiger guter Kandidatenmodelle verbessert werden.

Der Standardwert ist 10.

STOPPING_TOLERANCE
Gibt den Wert an, der verwendet wird, um zu bestimmen, wann die Konvergenz erreicht wird, und der Algorithmus wird mit dem Erstellen des Modells fertig gestellt. Die Konvergenz wird erreicht, wenn die Gesamtänderung der Clusterwahrscheinlichkeiten kleiner als das Verhältnis des STOPPING_TOLERANCE Parameters ist, dividiert durch die Größe des Modells.

Der Standardwert ist 10.

Stichprobengröße
Gibt die Anzahl der Fälle an, die der Algorithmus für jeden Durchlauf verwendet, wenn der parameter CLUSTERING_METHOD auf eine der skalierbaren Clusteringmethoden festgelegt ist. Wenn Sie den parameter SAMPLE_SIZE auf 0 festlegen, wird das gesamte Dataset in einem einzigen Durchlauf gruppiert. Das Laden des gesamten Datasets in einem einzigen Durchlauf kann zu Speicher- und Leistungsproblemen führen.

Der Standardwert ist 50000.

MAXIMALE_EINGABEEIGENSCHAFTEN
Gibt die maximale Anzahl von Eingabeattributen an, die der Algorithmus verarbeiten kann, bevor die Featureauswahl aufgerufen wird. Durch Festlegen dieses Werts auf 0 wird angegeben, dass keine maximale Anzahl von Attributen vorhanden ist.

Das Erhöhen der Anzahl von Attributen kann die Leistung erheblich beeinträchtigen.

Der Standardwert ist 255.

MAXIMUM_STATES
Gibt die maximale Anzahl von Attributzuständen an, die der Algorithmus unterstützt. Wenn ein Attribut mehr Zustände als das Maximum aufweist, verwendet der Algorithmus die am häufigsten verwendeten Zustände und ignoriert die verbleibenden Zustände.

Das Erhöhen der Anzahl von Zuständen kann die Leistung erheblich beeinträchtigen.

Der Standardwert ist 100.

Modellierung von Flaggen

Der Algorithmus unterstützt die folgenden Modellierungskennzeichnungen. Sie definieren Modellierungskennzeichnungen, wenn Sie die Miningstruktur oder das Miningmodell erstellen. Die Modellierungskennzeichnungen geben an, wie Werte in jeder Spalte während der Analyse behandelt werden.

Modellierungsflagge	BESCHREIBUNG
N/A (No improvements necessary unless context provides a translatable equivalent requiring alteration).	Die Spalte wird mit zwei möglichen Zuständen behandelt: Fehlend und Vorhanden. Ein Nullwert ist ein fehlender Wert. Gilt für die Miningmodell-Spalte.
NICHT NULL	Die Spalte darf keine NULL enthalten. Ein Fehler führt dazu, dass Analysis Services während der Modellschulung auf einen Nullwert stößt. Gilt für Miningstrukturspalte.

Anforderungen

Ein Clusteringmodell muss eine Schlüsselspalte und Eingabespalten enthalten. Sie können eingabespalten auch als vorhersagbar definieren. Spalten, die auf Predict Only festgelegt sind, werden nicht zur Bildung von Clustern verwendet. Die Verteilung dieser Werte in den Clustern wird berechnet, nachdem die Cluster erstellt wurden.

Eingabe- und vorhersagbare Spalten

Der Microsoft Clustering-Algorithmus unterstützt die spezifischen Eingabespalten und vorhersehbaren 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 Content Types (Data Mining).

Kolumne	Inhaltstypen
Eingabeattribute	Fortlaufend, zyklisch, diskret, diskretisiert, Schlüssel, Tabelle, geordnet
Vorhersehbares Attribut	Fortlaufend, zyklisch, diskret, diskretisiert, Tabelle, geordnet

Hinweis

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

Siehe auch

Microsoft Clustering-Algorithmus
Beispiele für Clusteringmodellabfragen
Miningmodellinhalt für Clusteringmodelle (Analysis Services - Data Mining)