X-Means: Ein Algorithmus zur Clusterbildung unter selbstständiger Abschätzung der optimalen Clusteranzahl

Inhaltsverzeichnis

1 Clustering Einführung
1.1 Ziel des Clusterings

2 Die Methode k-means
2.1 Einführung
2.2 Vorgehen bei k-means
2.3 Abgrenzung von gutem und schlechtem Clustering
2.4 Nachteile von k-means

3 Die Methode x-means
3.1 Einführung
3.2 Variabelenvereinbarung
3.3 Modellerstellung und -bewertung
3.4 Das BIC-Bewerungskriterium
3.5 Verbesserung der Geschwindigkeit
3.5.1 Beschleunigung des k-means-Algorithmus
3.5.2 Beschleunigung des Improve-Structure Schrittes
3.5.3 Ergänzdende Beschleunigung

4 Experimentelle Ergebnisse

5 Zusammenfassung und Ausblick

Abbildungsverzeichnis

Abbildung 1: In Anlehnung an Pelleg, Moore (2000)

Abbildung 2: In Anlehnung an Pelleg, Moore (2000)

Abbildung 3: In Anlehnung an Pelleg, Moore (2000)

Abbildung 4: In Anlehnung an Pelleg, Moore (2000)

Abbildung 5: k-means für k=3, In Anlehnung an Pelleg, Moore (2000)

Abbildung 6: Split der Väter in zwei Söhne, In Anlehnung an Pelleg, Moore (2000)

Abbildung 7: Erster Schritt von 2-means, In Anlehnung an Pelleg, Moore (2000)

Abbildung 8: Endposition der Centriode, In Anlehnung an Pelleg, Moore (2000)

Abbildung 9: Endszenario, In Anlehnung an Pelleg, Moore (2000)

Abbildung 10: Durchschnittliche Verzerrung pro Punkt von x-means und k-means im Vergleich, In Anlehnung an Pelleg, Moore (2000)

Abbildung 11: Durchschnittliche Run-time von x-means und k-means bei 3 Dimensionen und 250 Klassen an 233-Mhz Pentium 2, In Anlehnung an Pelleg, Moore (2000)

1 Clustering Einführung

1.1 Ziel des Clusterings

Clusteranalysen werden oft als erster Schritt verwendet um große und komplexe Datensätze zu analysieren. Die daraus gewonnen Informationen bilden dann wiederum die Grundlage um bei anderen Data Mining Verfahren bessere Ergebnisse zu erzielen.¹

Eine (semi)automatische Segmentierung der relevanten Daten bzw. Datensätze in Kategorien, Klassen oder Gruppen (Cluster) kann mit Hilfe einer Clusteranalyse erfolgen wobei Objekte gleicher Cluster möglichst ähnlich, Objekte verschiedener Cluster möglichst unähnlich zueinander sein sollten. Diese Ähnlichkeiten werden anhand von Distanzen, welche sich mit unterschiedlichsten Verfahren² berechnen lassen, ermittelt. Dabei lassen sich Ähnlichkeitsmaße sowohl für metrische als auch ordinale und nominale Merkmale unterscheiden. Bei den metrischen Merkmalen werden geometrische Abstandskonstrukte wie die euklidische Distanz³ oder die Blockmetrik⁴ angewendet, während bei nominal skalierten Variablen vorwiegend Übereinstimmungsmaße herangezogen werden.⁵

2 Die Methode k-means

2.1 Einführung

Die k-means Methode gehört zu den partitionierenden Verfahren und ist eine der bekanntesten und am häufigsten angewandten Clusteringmethoden. Partitionierende Clusteringverfahren zeichnen sich dadurch aus, dass sie eine Datenmenge in k Cluster(C) zerlegen, wobei jeder Cluster mindestens ein Objekt (p) enthält und jedes Objekt zu genau einem Cluster gehört. Jede Klasse wird durch einen zentralen Punkt den so genannten Centroiden (µc), der den Mittelwert aller Punkte im Clusters darstellt, gekennzeichnet. Die Kompaktheit so entstandener Cluster wird beispielsweise durch die Summe der quadrierten euklidischen Einzeldistanzen aller Punkte eines Clusters zum jeweiligen Clustercentroiden ermittelt.⁶

2.2 Vorgehen bei k-means

Nach dem Bilden einer zufälligen Ausgangssituation, bei der k Cluster zufällig gewählt werden, wird geprüft ob es Punkte innerhalb der Klassen gibt, die näher am Centroiden einer anderen Klasse als dem Klassenmittelpunkt der eigenen Klasse liegen. Ist dies der Fall, werden diese jeweiligen Punkte in die andere Klasse verschoben und die Centroide neu berechnet. Dieser iterative Prozess findet so lange statt, bis keine Veränderung mehr festgestellt wird.⁷

2.3 Abgrenzung von gutem und schlechtem Clustering

Die nachfolgenden Abbildungen (Abbildung 1-4) zeigen die euklidischen Distanzen der Objekte (Punkte) eines Clusters zu deren Centroiden als Strecken.⁸ Dabei soll für jeweils zwei Cluster ein optimales von einem schlechten Clustering abgegrenzt werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1 Abbildung 2 Abbildung 3 Abbildung 4

Wie in Abbildung 1 und 2 zu sehen ist, kann diese Clusterverteilung keinesfalls als optimal angesehen werden. Vielmehr handelt es sich hierbei um eine schlechte Klassenbildung der vorhandenen Punkte, wie man schon in der Ausgangssituation unschwer erkennen kann. Die Abbildungen 3 und 4 zeigen demgegenüber ein optimales Clustering für die gegebenen Punkte. Hier ist die Summe der Abstände clusterinterner Objekte zu ihren jeweiligen Centroiden minimal.⁹

2.4 Nachteile von k-means

Der k-means Algorithmus galt lange Zeit als Zugpferd für die Cluseranalyse metrischer Daten. Er besitzt jedoch drei grundlegende Nachteile. Erstens ist jede Iteration sehr rechenaufwendig, was den Algorithmus zu langsam macht um große Datenbasen, insbesondere solche wie sie in der realen Umwelt angetroffen werden, echtzeitnah analysieren zu können. Zweitens muss die Anzahl der Klassen vom Benutzer angegeben werden. Drittens werden mit statischer Klassenanzahl schlechtere lokale Optima als mit dynamischer Anzahl der Cluster gefunden. Außerdem hat eine gute bzw. schlechte Wahl der zufällig ausgesuchten Initialcluster einen großen Einfluss sowohl auf Performanz als auch auf Verzerrung der Ergebnisse.¹⁰

Aufgrund dieser Tatsachen entwickelten Dan Pelleg und Andrew Moore auf Basis von k-means einen schnelleren und qualitativ hochwertigeren Algorithmus, welcher zusätzlich in der Lage ist die Anzahl der Cluster selbstständig zu bestimmen.

3 Die Methode x-means

3.1 Einführung

Aufbauend auf k-means greift der x-means Algorithmus die oben genannten Probleme auf und versucht diese zu umgehen bzw. zu beheben. Dabei wird vom Benutzer im Gegensatz zu k-means nicht die Angabe einer Klassenanzahl k gefordert, sondern lediglich ein Bereich in welchem die optimale Klassenanzahl wahrscheinlich liegen wird.¹¹ Nun beginnt der Algorithmus mit dem Wert für k, welcher die untere Grenze des angegebenen Bereichs repräsentiert. Anschließend wird k so lange durch Splits¹² vorhandener Centroide erhöht, bis die obere Grenze des Bereichs erreicht wird. Nach jeder Iteration wird eine Bewertung der vorhandenen Konstellation durch die Bewertungskriterien BIC oder AIC¹³ vorgenommen. Die Entscheidung ob und welche Centroide aufgespaltet werden wird hier auch auf Grundlage des Bewertungskriteriums BIC getroffen. Anschließend wird das Modell mit der Clusteranzahl k, welche den höchsten BIC-Wert erreicht hat, ausgegeben.¹⁴

3.2 Variabelenvereinbarung

Im Folgenden soll µj für die Koordinaten des j-ten Centroiden stehen. Die Variable i soll den Index des Centroiden darstellen, welcher sich am nächsten zum i-ten Datenpunkt befindet. Die Variable D soll die Menge der Eingabedaten darstellen und Di die Anzahl der Daten deren nächster Centroide µi ist. Es gelte R = |D| und Ri = |Di|. Die Anzahl der Dimensionen soll von M repräsentiert werden.¹⁵

3.3 Modellerstellung und -bewertung

Der Algorithmus bedient sich eines iterativen Prozesses folgender Schritte:

1. Improve-Params
2. Improve-Structure

Diese zwei Schritte werden so lange wiederholt bis die Anzahl der Cluster k die obere Grenze erreicht.¹⁶

Die Improve-Params Operation entspricht trivialer Weise der Ausführung eines herkömmlichen k-mean Verfahrens, wie es weiter oben schon beschrieben wurde.

Der zweite Schritt Improve-Structure untersucht ob und wenn ja wo neue Centroiden durch Splitting gebildet werden sollten. Dazu werden einige Clusterzentren derart geteilt, dass es zur Herausbildung zweier neuer Cluster kommt. Das Problem, welche dieser Centroiden geteilt werde sollten, wird zuerst an zwei grundsätzlichen Ideen erläutert und danach an einem Beispiel erklärt.¹⁷

Die erste Idee besteht darin zufällig einen Centroiden auszuwählen und einen neuen in der Nähe des Ausgewählten zu erstellen. Danach wird ein Durchlauf mit k-means gestartet und geprüft, ob das resultierende Modell eine bessere Bewertungspunktzahl erzielen kann. Wenn das so ist wird der neue Centroid angenommen, sonst wird das Ausgangsmodell bevorzugt. Dies wirft jedoch die Frage auf, welcher Klassenmittelpunkt es am ehesten verdient „geboren“ zu werden. Und im Falle keiner Verbesserung der Punktzahl wird das Problem aufgeworfen wie weiter zu verfahren ist. Die Lösung kann auch nicht darin bestehen einfach alle Klassenzentren auf diese Weise zu testen um dann das beste Modell auszuwählen, da dies eine sehr aufwendige und langwierige Prozedur wäre um auch nur einen Cluster hinzuzufügen.¹⁸

Die zweite Überlegung sucht nach heuristischen Verfahren, beispielsweise die Hälfte aller Clusterzentren heraus, je nachdem wie viel versprechend es wäre sie zu splitten. Diese werden dann geteilt und nach einem Durchlauf von k-means wird überprüft, ob das Modell besser punkten kann als die Ausgangssituation. Diese Idee ist im Gegensatz zum ersten Ansatz schneller, wirft aber wiederum die Überlegung auf nach welchem heuristischen Kriterium die Centroide zur Teilung ausgesucht werden sollen. Und was passiert in jenen Fällen, wenn es nur sinnvoll wäre einen oder zwei Centroide zu splitten?¹⁹

Die Lösung, welche der x-means Algorithmus vorschlägt soll nun an einem Beispiel verdeutlicht werden.

In Abbildung 5 ist eine k-means Lösung für drei Cluster dargestellt. Die spezifischen Centroide sind rot eingetragen. Außerdem sind zusätzlich die Grenzen der Klassen abgetragen innerhalb derer die Punkte zum jeweiligen Klassenzentrum gehören.

[...]

¹ Vgl. Martin (1998): Data Warehousing, S. 269

² z.B. Euklidische Distanz, Manhatten Distanz, Maximums-Metrik

³ Was der Luftlinie zwischen den jeweiligen Punkten entspricht.

⁴ Auch als Manhatten Distance bekannt. Dies entspricht der Entfernungsmessung über rechtwinklig verbundene Straßenecken.

⁵ Vgl. Hippner, Küsters, Meyer, Wilde (2001): Handbuch Data Mining im Marketing, S. 112 oder Ester, Sanders (2000): Knowledge Discovery in Databases, S. 45-48

⁶ Vgl. Ester, Sanders (2000): Knowledge Discovery in Databases, S. 51-54

⁷ Vgl. Pelleg, Moore (2000): X-means: Extending K-means with Efficient Estimation of the Number of Clusters

⁸ Die Punkte werden der Übersicht halber im zweidimensionalen Raum dargestellt

⁹ Vgl. Ester, Sanders (2000): Knowledge Discovery in Databases, S. 51-54

¹⁰ Vgl. Pelleg, Moore (2000): X-Means: Extending K-means with Efficient Estimation of the Number of Clusters

¹¹ Dieser könnte jedoch auch als [1...n] angegeben werden

¹² Ein Split stellt die Teilung eines Centroiden in mehrere Kinder dar.

¹³ Bayesian Information Criterion bzw. Akaike Information Criterion, im Folgenden wird BIC verwendet.

¹⁴ Vgl. Stöttinger (2004): Kombiniertes Data Mining. Effiziente Generierung von Hilfsinformationen während des Data Mining, S. 46, 47

¹⁵ Vgl. Pelleg, Moore (2000): X-Means: Extending K-means with Efficient Estimation of the Number of Cluster

¹⁶ Wenn also gilt: k > kmax

¹⁷ Vgl. Pelleg, Moore (2000): X-Means: Extending K-means with Efficient Estimation of the Number of Clusters

¹⁸ Vgl. Pelleg, Moore (2000): X-Means: Extending K-means with Efficient Estimation of the Number of Clusters

¹⁹ Vgl. Pelleg, Moore (2000): X-Means: Extending K-means with Efficient Estimation of the Number of Cluster