Benutzer:Sigbert/Sandbox

Partitionierende Clusterverfahren

Die Gemeinsamkeit der partitionierenden Verfahren ist, dass zunächst die Zahl der Cluster ${\displaystyle k}$ festgelegt werden muss (Nachteil). Dann werden ${\displaystyle k}$ Clusterzentren bestimmt und diese iterativ solange verschoben wobei eine vorgegebene Fehlerfunktion minimiert wird. Ein Vorteil ist, dass Objekte während der Verschiebung der Clusterzentren ihre Clusterzugehörigkeit wechseln können.

K-Means-Algorithmus

Die Clusterzentren werden zufällig festgelegt und die Summe der euklidischen Abstände der Objekte zu ihrem nächsten Clusterzentrum wird minimiert. Das Update der Clusterzentren geschieht durch Mittelwertbildung aller Objekte in einem Cluster.

k-Means++^[1]

Als Clusterzentren werden auch zufällig Objekte so ausgewählt, so dass sie etwa uniform im Raum der Objekte verteilt sind. Dies führt zu einem schnelleren Algorithmus.

k-Median-Algorithmus

Hier wird die Summe der Manhattan-Distanzen der Objekte zu ihrem nächsten Clusterzentrum minimiert. Das Update der Clusterzentren geschieht durch die Berechnung des Medians aller Objekte in einem Cluster. Ausreißer in den Daten haben dadurch weniger Einfluss.

k-Medoids oder Partitioning Around Medoids (PAM)^[2]

Die Clusterzentren sind hier immer Objekte. Durch Verschiebung von Clusterzentren auf ein benachbartes Objekt wird die Summe der Distanzen zum nächstgelegenen Clusterzentrum minimiert. Im Gegensatz zum k-Means Verfahren werden nur die Distanzen zwischen den Objekten benötigt und nicht die Koordinaten der Objekte.

Fuzzy C-Means^[3]

Für jedes Objekt wird ein Zugehörigkeitsgrad zu einem Cluster berechnet, oft aus dem reellwertigen Intervall [0,1] (Zugehörigkeitsgrad=1: Objekt gehört vollständig zu einem Cluster, Zugehörigkeitsgrad=0: Objekt gehört nicht zu dem Cluster). Dabei gilt: je weiter ein Objekt vom Clusterzentrum entfernt ist, desto kleiner ist auch sein Zugehörigkeitsgrad zu diesem Cluster. Wie im k-Median-Verfahren werden die Clusterzentren dann verschoben, jedoch haben weit entfernte Objekte (kleiner Zugehörigkeitsgrad) einen geringen Einfluss auf die Verschiebung als nahe Objekte. Damit wird auch eine weiche Clusterzuordnung erreicht: Jedes Objekt gehört zu jedem Cluster mit einem entsprechenden Zugehörigkeitsgrad.

EM-Clustering^[4]

Die Cluster werden als ${\displaystyle k}$ multivariate Normalverteilungen modelliert. Mit Hilfe des EM-Algorithmus werden die unbekannten Parameter (${\displaystyle \mu _{i},\Sigma _{i}}$ mit ${\displaystyle i=1,\ldots ,k}$) der Normalverteilungen iterativ geschätzt. Im Gegensatz zu k-means wird damit eine weiche Clusterzuordnung erreicht: Mit einer gewissen Wahrscheinlichkeit gehört jedes Objekt zu jedem Cluster und jedes Objekt beeinflusst so die Parameter jeden Clusters.

Hierarchische Clusterverfahren

Als hierarchische Clusteranalyse bezeichnet man eine bestimmte Familie von distanzbasierten Verfahren zur Clusteranalyse. Cluster bestehen hierbei aus Objekten, die zueinander eine geringere Distanz (oder umgekehrt: höhere Ähnlichkeit) aufweisen als zu den Objekten anderer Cluster. Dabei wird eine Hierarchie von Clustern aufgebaut: auf der einen Seite ein Cluster der alle Objekte enthält und auf der anderen Seite so viele Cluster wie man Objekte hat, d.h. jedes Cluster enthält genau ein Objekt. Man unterscheidet zwei wichtige Typen von Verfahren:

• die divisiven Clusterverfahren, in dem zunächst alle Objekte als zu einem Cluster gehörig betrachtet werden und dann schrittweise die Cluster in immer kleinere Cluster aufgeteilt werden bis jeder Cluster nur noch aus einem Objekt besteht (auch: „Top-down-Verfahren“)

Divisive Analysis Clustering (DIANA)^[5]

Man beginnt mit einem Cluster, dass alle Objekte enthält. Im Cluster mit dem größten Durchmesser wird das Objekt gesucht, dass die größte mittlere Distanz oder Unähnlichkeit zu den anderen Objekten des Clusters aufweist. Dies ist der Kern des Splittercluster. Iterativ wird jedes Objekt, dass nahe genug am Splittercluster ist diesem hinzugefügt. Der gesamte Prozess wird wiederholt bis jeder Cluster nur noch aus einem Objekt besteht.

• die agglomerativen Clusterverfahren, in dem zunächst jedes Objekt einen Cluster bildet und dann schrittweisen die Cluster in immer größere Cluster zusammengefasst werden bis alle Objekte zu einem Cluster gehören (auch: „Bottom-up-Verfahren“). Die Verfahren in dieser Familie unterscheiden zu einem nach den verwendeten Distanz- bzw. Ähnlichkeitsmaßen (zwischen Objekten, aber auch zwischen ganzen Clustern) und, meist wichtiger, nach ihrer Fusionsvorschrift, welche Cluster in einem Schritt zusammengefasst werden. Die Fusionierungsmethoden unterscheiden sich in der Art und Weise, wie die Distanz des fusionierten Clusters zu allen anderen Clustern berechnet wird. Wichtige Fusionierungsmethoden sind:

Single Linkage^[6][7][8][9]

Die Cluster, deren nächste Objekte die kleinste Distanz oder Unähnlichkeit haben, werden fusioniert.

Ward Methode^[10]

Die Cluster, die den kleinsten Zuwachs der totalen Varianz haben, werden fusioniert.

Für beide Verfahren gilt: einmal gebildete Cluster können nicht mehr verändert oder einzelne Objekte getauscht werden. Es wird die Struktur entweder stets nur verfeinert („divisiv“) oder nur verallgemeinert („agglomerativ“), so dass eine strikte Cluster-Hierarchie entsteht. An der entstandenen Hierarchie kann man nicht mehr erkennen, wie sie berechnet wurde.

Dichtebasierte Verfahren

Bei dichtebasiertem Clustering werden Cluster als Objekte in einem d-dimensionalen Raum betrachtet, welche dicht beieinander liegen, getrennt durch Gebiete mit geringerer Dichte.

DBSCAN^[11] (Density-Based Spatial Clustering of Applications with Noise)

Objekte, die in einem vorgegeben Abstand ${\displaystyle \epsilon }$ mindestens ${\displaystyle k}$ weitere Objekte haben, sind Kernobjekte. Zwei Kernobjekte, deren Distanz kleiner als ${\displaystyle \epsilon }$ ist, gehören dabei zum gleichen Cluster. Nicht-Kern-Objekte, die nahe einem Cluster liegen, werden diesem als Randobjekte hinzugefügt. Objekte, die weder Kernobjekte noch Randobjekte sind, sind Rauschobjekte.

OPTICS^[12] (Ordering Points To Identify the Clustering Structure)

Der Algorithmus erweitert DBSCAN, so dass auch verschieden dichte Cluster erkannt werden. Die Wahl des Parameters ${\displaystyle \epsilon }$ ist nicht mehr so ausschlaggebend um die Clusterstruktur der Objekte zu finden.

Maximum-Margin Clustering^[13]

Es werden (leere) Bereiche in Raum der Objekte gesucht, die zwischen zwei Clustern liegen. Daraus werden Clustergrenzen bestimmt und damit auch die Cluster. Die Technik ist eng angebunden an Support-Vektor-Maschinen.

Kombinierte Verfahren

In der Praxis werden oft auch Kombinationen von Verfahren benutzt. Ein Beispiel ist es erst eine hierarchische Clusteranalyse durchzuführen um eine geeignete Clusterzahl zu bestimmen und danach noch ein k-Means Clustering um das Clustering Resultat zu verbessern. Oft lässt sich in speziellen Situation zusätzliche Information ausnutzen, so dass z.B. die Dimension oder die Anzahl der zu clusternden Objekte reduziert wird.

Spectral clustering^[14][15]

Die zu clusterenden Objekte können auch als Knoten eines Graphs aufgefasst werden und die gewichteten Kanten geben Distanz- oder Unähnlichkeit wieder. Die Lagrange-Matrix, eine spezielle Transformierte der Adjazenzmatrix (Matrix der Ähnlichkeit zwischen allen ${\displaystyle n}$ Objekten), hat bei ${\displaystyle k}$ Zusammenhangskomponenten (Clustern) den Eigenwert Null mit der Vielfachheit ${\displaystyle k}$. Daher untersucht man die ${\displaystyle k}$ kleinsten Eigenwerte der Lagrange-Matrix und den zugehörigen ${\displaystyle k}$ dimensionalen Eigenraum (${\displaystyle k\ll n}$). Statt in einem hochdimensionalen Raum wird nun in dem niedrigdimensionalen Eigenraum, z.B. mit dem k-Means Verfahren, geclustert.

Multiview clustering^[16]

Hierbei wird davon ausgegangen, dass man mehrere Distanz- oder Ähnlichkeitsmatrizen (sog. views) der Objekte generieren kann. Ein Beispiel sind Webseiten als zu clusternde Objekte: eine Distanzmatrix kann auf Basis der gemeinsam verwendeten Worte berechnet werden, eine zweite Distanzmatrix auf Basis der Verlinkung. Dann wird ein Clustering (oder ein Clustering-Schritt) mit der einen Distanzmatrix durchgeführt und das Ergebnis als Input für ein Clustering (oder ein Clustering-Schritt) mit der anderen Distanzmatrix benutzt. Dies wird wiederholt bis sich die Clusterzugehörigkeit der Objekte stabilisiert.

Balanced iterative reducing and clustering using hierarchies (BIRCH)

Für (sehr) große Datensätze wird zunächst ein Preclustering durchgeführt. Die so gewonnenen Cluster (nicht mehr die Objekte) werden dann z.B. mit einer hierarchischen Clusteranalyse weitergeclustert. Dies ist die Basis des eigens für SPSS entwickelten und dort eingesetzten Two-Step clusterings.

1. [1]

   Arthur, D., & Vassilvitskii, S. (2007). k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (pp. 1027-1035). Society for Industrial and Applied Mathematics.
2. [2]

   S. Vinod: Integer programming and the theory of grouping. In: Journal of the American Statistical Association. Band 64, 1969, S. 506--517.
3. [3]

   J.C. Bezdek: Pattern recognition with fuzzy objective function algorithms. Plenum Press, New York 1981.
4. [4]

   A.P. Dempster, N.M. Laird, and D.B. Rubin (1977) Maximum Likelihood from Incomplete Data via the EM algorithm. In: Journal of the Royal statistical Society, Series B, 39(1): 1-38
5. [5]

   Kaufman, L., & Roussew, P. J. (1990). Finding Groups in Data - An Introduction to Cluster Analysis. A Wiley-Science Publication John Wiley & Sons.
6. [6]

   Florek, K., Łukasiewicz, J., Perkal, J., & Steinhaus, H. i Zubrzycki S.(1951). Taksonomia wrocławska. Przegląd Antropol, 17, 193-211.
7. [7]

   Florek, K., Łukaszewicz, J., Perkal, J., Steinhaus, H., & Zubrzycki, S. (1951). Sur la liaison et la division des points d'un ensemble fini. In Colloquium Mathematicae (Vol. 2, No. 3-4, pp. 282-285). Institute of Mathematics Polish Academy of Sciences.
8. [8]

   McQuitty, L. L. (1957). Elementary linkage analysis for isolating orthogonal and oblique types and typal relevancies. Educational and Psychological Measurement.
9. [9]

   Sneath, P. H. (1957). The application of computers to taxonomy. Journal of general microbiology, 17(1), 201-226.
10. [10]

    Ward Jr, J. H. (1963). Hierarchical grouping to optimize an objective function. Journal of the American statistical association, 58(301), 236-244.
11. [11]

    Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Kdd (Vol. 96, pp. 226-231).
12. [12]

    Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander: OPTICS: Ordering Points To Identify the Clustering Structure. In: ACM SIGMOD international conference on Management of data. ACM Press, 1999, S. 49–60 (CiteSeerX).
13. [13]

    Xu, L., Neufeld, J., Larson, B., & Schuurmans, D. (2004). Maximum margin clustering. In Advances in neural information processing systems (pp. 1537-1544).
14. [14]

    Donath, W. E., & Hoffman, A. J. (1973). Lower bounds for the partitioning of graphs. IBM Journal of Research and Development, 17(5), 420-425.
15. [15]

    Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), 298-305.
16. [16]

    Bickel, S., & Scheffer, T. (2004, November). Multi-View Clustering. In ICDM (Vol. 4, pp. 19-26).