Clusteranalyse

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Clusterverfahren)
Wechseln zu: Navigation, Suche
QS-Informatik

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)

Unter Clusteranalyse (Clustering-Algorithmus, gelegentlich auch: Ballungsanalyse) versteht man Verfahren zur Entdeckung von Ähnlichkeitsstrukturen in (großen) Datenbeständen. Die so gefundenen Gruppen von „ähnlichen“ Objekten werden als Cluster bezeichnet, die Gruppenzuordnung als Clustering. Die gefundenen Ähnlichkeitsgruppen können graphentheoretisch, hierarchisch, partitionierend oder optimierend sein. Die Clusteranalyse ist eine wichtige Disziplin des Data-Mining, dem Analyseschritt des Knowledge Discovery in Databases Prozesses.

Bei der Clusteranalyse ist das Ziel neue Gruppen in den Daten zu identifizieren (im Gegensatz zur Klassifikation, bei der Daten bestehenden Klassen zugeordnet werden). Man spricht von einem „uninformierten Verfahren“, da es nicht auf Klassen-Vorwissen angewiesen ist. Diese neuen Gruppen können anschließend beispielsweise zur automatisierten Klassifizierung, zur Erkennung von Mustern in der Bildverarbeitung oder zur Marktsegmentierung eingesetzt werden (oder in beliebigen anderen Verfahren, die auf ein derartiges Vorwissen angewiesen sind).

Die zahlreichen Algorithmen unterscheiden sich vor allem in ihrem Ähnlichkeits- und Gruppenbegriff, ihrem Cluster-Modell, ihrem algorithmischen Vorgehen (und damit ihrer Komplexität) und der Toleranz gegenüber Störungen in den Daten. Ob das von einem solchen Algorithmus generierte „Wissen“ nützlich ist, kann jedoch in der Regel nur ein Experte beurteilen. Ein Clusteringalgorithmus kann unter Umständen vorhandenes Wissen reproduzieren (beispielsweise Personendaten in die bekannten Gruppen „männlich“ und „weiblich“ unterteilen), oder auch für den Anwendungszweck nicht hilfreiche Gruppen generieren. Die gefundenen Gruppen lassen sich oft auch nicht verbal beschreiben (z. B. „männliche Personen“), gemeinsame Eigenschaften werden in der Regel erst durch eine nachträgliche Analyse identifiziert. Bei der Anwendung von Clusteranalyse ist es daher oft notwendig, verschiedene Verfahren und verschiedene Parameter zu probieren, die Daten vorzuverarbeiten und beispielsweise Attribute auszuwählen oder wegzulassen.

Beispiel[Bearbeiten]

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Angewendet auf einen Datensatz von Fahrzeugen könnte ein Clustering-Algorithmus (und eine nachträgliche Analyse der gefundenen Gruppen) beispielsweise folgende Struktur liefern:

 
 
 
 
 
 
 
Fahrzeuge
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Fahrräder
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
LKW
 
PKW
 
Rikschas
 
Rollermobile
 

Dabei ist Folgendes zu beachten:

  • Der Algorithmus selbst liefert keine Interpretation („LKW“) der gefundenen Gruppen. Hierzu ist eine separate Analyse der Gruppen notwendig.
  • Ein Mensch würde eine Fahrradrikscha als Untergruppe der Fahrräder ansehen. Für einen Clusteringalgorithmus aber sind 3 Räder oft ein signifikanter Unterschied, den sie mit einem Dreirad-Rollermobil teilen.
  • Die Gruppen sind oftmals nicht „rein“, es können also beispielsweise kleine LKW in der Gruppe der PKW sein.
  • Es treten oft zusätzliche Gruppen auf, die nicht erwartet wurden („Polizeiautos“, „Cabrios“, „rote Autos“, „Autos mit Xenon-Scheinwerfern“).
  • Manche Gruppen werden nicht gefunden, beispielsweise „Motorräder“ oder „Liegeräder“.
  • Welche Gruppen gefunden werden, hängt stark vom verwendeten Algorithmus, Parametern und verwendeten Objekt-Attributen ab.
  • Oft wird auch nichts (sinnvolles) gefunden.
  • In diesem Beispiel wurde nur bekanntes Wissen (wieder-)gefunden – als Verfahren zur „Wissensentdeckung“ ist die Clusteranalyse hier also gescheitert.

Geschichte[Bearbeiten]

Historisch gesehen stammt das Verfahren aus der Taxonomie in der Biologie, wo über eine Clusterung von verwandten Arten eine Ordnung der Lebewesen ermittelt wird. Allerdings wurden dort ursprünglich keine automatischen Berechnungsverfahren eingesetzt. Inzwischen können zur Bestimmung der Verwandtschaft von Organismen unter anderem ihre Gensequenzen verglichen werden. Siehe auch: Kladistik

Prinzip/Funktionsweise[Bearbeiten]

Mathematische Modellierung[Bearbeiten]

Die Eigenschaften der zu untersuchenden Objekte werden mathematisch als Zufallsvariablen aufgefasst. Sie werden in der Regel in Form von Vektoren als Punkte in einem Vektorraum dargestellt, deren Dimensionen die Eigenschaftsausprägungen des Objekts bilden. Bereiche, in denen sich Punkte anhäufen (Punktwolke), werden Cluster genannt. Bei Streudiagrammen dienen die Abstände der Punkte zueinander oder die Varianz innerhalb eines Clusters als sogenannte Proximitätsmaße, welche die Ähnlichkeit bzw. Unterschiedlichkeit zwischen den Objekten zum Ausdruck bringen.

Ein Cluster kann auch als eine Gruppe von Objekten definiert werden, die in Bezug auf einen berechneten Schwerpunkt eine minimale Abstandssumme haben. Dazu ist die Wahl eines Distanzmaßes erforderlich. In bestimmten Fällen sind die Abstände (bzw. umgekehrt die Ähnlichkeiten) der Objekte untereinander direkt bekannt, so dass sie nicht aus der Darstellung im Vektorraum ermittelt werden müssen.

Grundsätzliche Vorgehensweise[Bearbeiten]

In einer Gesamtmenge/gruppe mit unterschiedlichen Objekten, werden die Objekte, die sich ähnlich sind, zu Gruppen (Clustern) zusammengefasst.

Als Beispiel sei folgende Musikanalyse gegeben. Die Werte ergeben sich aus dem Anteil der Musikstücke, die der Nutzer pro Monat online kauft.

Person 1 Person 2 Person 3
Pop 2 1 8
Rock 10 8 1
Jazz 3 3 1

In diesem Beispiel würde man die Personen intuitiv in zwei Gruppen einteilen. Gruppe1 besteht aus Person 1&2 und Gruppe 2 besteht aus Person 3. Das würden auch die meisten Clusteralgorithmen machen. Dieses Beispiel ist lediglich aufgrund der gewählten Werte so eindeutig, spätestens mit näher zusammenliegenden Werten und mehr Variablen (hier Musikrichtungen) und Objekten (hier Personen), ist leicht vorstellbar, dass die Einteilung in Gruppen nicht mehr so trivial ist.

Etwas genauer und abstrakter ausgedrückt: Die Objekte einer heterogenen (beschrieben durch unterschiedliche Werte ihrer Variablen) Gesamtmenge werden mit Hilfe der Clusteranalyse zu Teilgruppen (Cluster/Segmente) zusammengefasst, die in sich möglichst homogen (die Unterschiede der Variablen möglichst gering) sind. In unserem Musikbeispiel kann die Gruppe aller Musikhörer (eine sehr heterogene Gruppe) in die Gruppen der Jazzhörer, Rockhörer, Pophörer, etc. (jeweils relativ homogen) unterteilt werden bzw. werden die Hörer mit ähnlichen Präferenzen zu der entsprechende Gruppe zusammengefasst.

Eine Clusteranalyse (z. B. bei der Marktsegmentierung) erfolgt dabei in folgenden Schritten:

Schritte zur Clusterbildung:

  1. Variablenauswahl: Auswahl (und Erhebung) der für die Untersuchung geeigneten Variablen. Sofern die Variablen der Objekte/Elemente noch nicht bekannt/vorgegeben sind, müssen alle für die Untersuchung wichtigen Variablen bestimmt und anschließend ermittelt werden.
  2. Proximitätsbestimmung: Wahl des Proximitätsmaßes und Bestimmung der Distanz- bzw. Ähnlichkeitswerte (je nach Proximitätsmaß) zwischen den Objekten über ein geeignetes Proximitätsmaß. Abhängig von der Art der Variablen bzw. der Skalenart der Variablen wird eine entsprechende Distanzfunktion zur Bestimmung des Abstandes (Distanz) zweier Elemente oder eine Ähnlichkeitsfunktion zur Bestimmung der Ähnlichkeit verwendet. Die Variablen werden zunächst einzeln verglichen und aus der Distanz der einzelnen Variablen die Gesamtdistanz (oder Ähnlichkeit) berechnet. Die Funktion zur Bestimmung von Distanz oder Ähnlichkeit wird auch Proximitätsmaß genannt. Der durch ein Proximitätsmaß ermittelte Distanz- bzw. Ähnlichkeitwert nennt sich Proximität. Werden alle Objekte miteinander verglichen, ergibt sich eine Proximitätsmatrix, welche jeweils zwei Objekten eine Proximität zuweist.
  3. Clusterbildung: Bestimmung und Durchführung eines/der geeigneten Clusterverfahrens, um anschließend mit Hilfe des/dieser Verfahrens Gruppen/Cluster bilden zu können (die Proximitätsmatrix wird hierdurch reduziert). Im Regelfall werden hierbei mehrere Verfahren kombiniert, z. B.:
  • Finden von Ausreißern durch das Single-Linkage Verfahren (hierarchisches Verfahren)
  • Bestimmung der Clusterzahl durch das Ward-Verfahren (hierarchisches Verfahren)
  • Bestimmung der Clusterzusammensetzung durch das Austauschverfahren (partitionierendes Verfahren)

Weitere Schritte der Clusteranalyse:

  1. Bestimmung der Clusterzahl durch Betrachtung der Varianz innerhalb und zwischen den Gruppen. Hier wird bestimmt, wie viele Gruppen tatsächlich gebildet werden, denn bei der Clusterung selbst ist keine Abbruchbedingung vorgegeben. z. B. wird bei einem agglomerativen Verfahren folglich so lange fusioniert, bis nur noch eine Gesamtgruppe vorhanden ist.
  2. Interpretation der Cluster (abhängig von den inhaltlichen Ergebnissen, z. B. durch t-Wert)
  3. Beurteilung der Güte der Clusterlösung (Bestimmung der Trennschärfe der Variablen, Gruppenstabilität)

Unterschiedliche Proximitätsmaße/Skalen[Bearbeiten]

Die Skalen bezeichnen den Wertebereich, den die betrachtete(n) Variable(n) des Objektes annehmen kann. Je nachdem welche Art von Skala vorliegt, muss man ein passendes Proximitätsmaß verwenden. Es gibt drei Hauptkategorien von Skalen:

  • Binäre Skalen
die Variable kann zwei Werte z. B. 0 oder 1 annehmen z. B. männlich/weiblich.
Verwendete Proximitätsmaße (Beispiele):
  • Nominale Skalen
die Variable kann unterschiedliche Werte annehmen um eine qualitative Unterscheidung zu treffen, z. B. ob Pop, Rock oder Jazz bevorzugt wird.
Verwendete Proximitätsmaße (Beispiele):
  • Metrische Skalen
die Variable nimmt einen Wert auf einer vorher festgelegten Skala eine quantitative Aussage zu treffen z. B. wie gerne eine Person Pop auf einer Skala von 1 bis 10 hört.
Verwendete Proximitätsmaße (Beispiele):

Formen der Gruppenbildung (Gruppenzugehörigkeit)[Bearbeiten]

Hauptartikel: Cluster (Informatik)

Es sind drei unterschiedliche Formen der Gruppenbildung (Gruppenzugehörigkeit) möglich. Bei den nichtüberlappenden Gruppen wird jedes Objekt nur einer Gruppe (Segment, Cluster) zugeordnet, bei den überlappenden Gruppen kann ein Objekt mehreren Gruppen zugeordnet werden, und bei den Fuzzygruppen gehört ein Element jeder Gruppe mit einem bestimmten Grad des Zutreffens an.

 
 
 
 
 
Nichtüberlappend
 
 
 
 
 
 
 
Formen der Gruppenbildung
 
 
Überlappend
 
 
 
 
 
 
 
 
 
 
 
 
Fuzzy
 


Man unterscheidet zwischen „harten“ und „weichen“ Clusteringalgorithmen. Harte Methoden (z. B. k-means, Spectral Clustering, Kernel PCA) ordnen jeden Datenpunkt genau einem Cluster zu, wohingegen bei weichen Methoden (z. B. EM-Algorithmus mit mixture-of-Gaussians model) jedem Datenpunkt für jeden Cluster ein Grad zugeordnet wird, mit der dieser Datenpunkt in diesem Cluster zugeordnet werden kann. Weiche Methoden sind insbesondere dann nützlich, wenn die Datenpunkte relativ homogen im Raum verteilt sind und die Cluster nur als Regionen mit erhöhter Datenpunktdichte in Erscheinung treten, d.h. wenn es z. B. fließende Übergänge zwischen den Clustern oder Hintergrundrauschen gibt (harte Methoden sind in diesem Fall unbrauchbar).

Unterscheidung der Clusterverfahren[Bearbeiten]

Clusterverfahren lassen sich in graphentheoretische, hierarchische, partitionierende, und optimierende Verfahren sowie in weitere Unterverfahren einteilen.

Diese Klassifikation bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.
  • Partitionierende Verfahren
verwenden eine gegebene Partitionierung und ordnen die Elemente durch Austauschfunktionen um, bis die verwendete Zielfunktion ein Optimum erreicht. Zusätzliche Gruppen können jedoch nicht gebildet werden, da die Anzahl der Cluster bereits am Anfang festgelegt wird (vgl. hierarchische Verfahren).
  • Hierarchische Verfahren
gehen von der feinsten (agglomerativ bzw. bottom-up) bzw. gröbsten (divisiv bzw. top-down) Partition aus (vgl. Top-down und Bottom-up). Die gröbste Partition entspricht der Gesamtheit aller Elemente und die feinste Partition enthält lediglich ein Element bzw. jedes Element bildet seine eigene Gruppe/Partition. Durch Aufteilen bzw. Zusammenfassen lassen sich anschließend Cluster bilden. Einmal gebildete Gruppen können nicht mehr aufgelöst oder einzelne Elemente getauscht werden (vgl. partitionierende Verfahren). Agglomerative Verfahren kommen in der Praxis (z. B. bei der Marktsegmentierung im Marketing) sehr viel häufiger vor.
 
 
 
 
 
graphentheoretisch
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
divisiv
 
 
 
 
 
 
 
hierarchisch
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
agglomerativ
 
Clusterverfahren
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Austauschverfahren
 
 
 
 
 
 
 
partitionierend
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
iterierte Minimaldistanzverfahren
 
 
 
 
 
 
optimierend
 
 
 
 
 


Zu beachten ist, dass man noch diverse weitere Verfahren und Algorithmen unterscheiden kann, unter anderem überwachten (supervised) und nicht-überwachten (unsupervised) Algorithmen oder modellbasierte Algorithmen, bei denen eine Annahme über die zugrundeliegende Verteilung der Daten gemacht wird (z. B. mixture-of-Gaussians model).

Verfahren[Bearbeiten]

Es sind eine Vielzahl von Clustering-Verfahren in den unterschiedlichsten Anwendungsgebieten entwickelt worden. Man kann folgende Verfahrenstypen unterscheiden:

  • (Zentrumsbasierte) Partitionierende Verfahren,
  • hierarchische Verfahren,
  • dichte-basierte Verfahren und
  • kombinierte Verfahren.

Die erste beiden Verfahrenstypen sind die klassischen Clusterverfahren während die anderen Verfahren eher neueren Datums sind.

Partitionierende Clusterverfahren[Bearbeiten]

Die Gemeinsamkeit der partitionierenden Verfahren ist, dass zunächst die Zahl der Cluster k festgelegt werden muss (Nachteil). Dann werden 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 quadrierten 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 k multivariate Normalverteilungen modelliert. Mit Hilfe des EM-Algorithmus werden die unbekannten Parameter (\mu_i, \Sigma_i mit 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[Bearbeiten]

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, das 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[Bearbeiten]

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 \epsilon mindestens k weitere Objekte haben, sind Kernobjekte. Zwei Kernobjekte, deren Distanz kleiner als \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 \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[Bearbeiten]

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 Laplace-Matrix, eine spezielle Transformierte der Adjazenzmatrix (Matrix der Ähnlichkeit zwischen allen n Objekten), hat bei k Zusammenhangskomponenten (Clustern) den Eigenwert Null mit der Vielfachheit k. Daher untersucht man die k kleinsten Eigenwerte der Lagrange-Matrix und den zugehörigen k dimensionalen Eigenraum (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.

Literatur[Bearbeiten]

Grundlagen und Verfahren[Bearbeiten]

  •  Martin Ester, Jörg Sander: Knowledge Discovery in Databases. Techniken und Anwendungen. Springer, Berlin 2000, ISBN 3540673288.
  • Backhaus, K., Erichson, B., Plinke, W., Weiber, R. Multivariate Analysemethoden. Eine anwendungsorientierte Einführung. Springer ISBN 3-540-00491-2
  • Bickel, S., Scheffer, T., Multi-View Clustering. Proceedings of the IEEE International Conference on Data Mining, 2004
  • Shi, J., Malik, J. Normalized Cuts and Image Segmentation, in Proc. of IEEE Conf. on Comp. Vision and Pattern Recognition, Puerto Rico 1997

Anwendung[Bearbeiten]

  • Bacher, J., Pöge, A., Wenzig, K., Clusteranalyse – Anwendungsorientierte Einführung in Klassifikationsverfahren, 3. Auflage. München, Oldenbourg 2010, ISBN 978-3-486-58457-8
  • Bortz, J. (1999), Statistik für Sozialwissenschaftler. (Kap. 16, Clusteranalyse). Berlin: Springer
  • Härdle, W.; Simar, L. Applied Multivariate Statistical Analysis, Springer, New York, 2003
  • Homburg, C., Krohmer. H. Marketingmanagement: Strategie – Instrumente – Umsetzung – Unternehmensführung, 3 Edition, Kapitel 8.2.2, Gabler, Wiesbaden, 2009
  • Moosbrugger, H., Frank, D.: Clusteranalytische Methoden in der Persönlichkeitsforschung. Eine anwendungsorientierte Einführung in taxometrische Klassifikationsverfahren. Huber, Bern 1992, ISBN 3-456-82320-7.

Einzelnachweise[Bearbeiten]

  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.  S. Vinod: Integer programming and the theory of grouping. In: Journal of the American Statistical Association. 64, 1969, S. 506--517.
  3.  J.C. Bezdek: Pattern recognition with fuzzy objective function algorithms. Plenum Press, New York 1981.
  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. Kaufman, L., & Roussew, P. J. (1990). Finding Groups in Data - An Introduction to Cluster Analysis. A Wiley-Science Publication John Wiley & Sons.
  6. Florek, K., Łukasiewicz, J., Perkal, J., & Steinhaus, H. i Zubrzycki S.(1951). Taksonomia wrocławska. Przegląd Antropol, 17, 193-211.
  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. McQuitty, L. L. (1957). Elementary linkage analysis for isolating orthogonal and oblique types and typal relevancies. Educational and Psychological Measurement.
  9. Sneath, P. H. (1957). The application of computers to taxonomy. Journal of general microbiology, 17(1), 201-226.
  10. Ward Jr, J. H. (1963). Hierarchical grouping to optimize an objective function. Journal of the American statistical association, 58(301), 236-244.
  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.  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. Xu, L., Neufeld, J., Larson, B., & Schuurmans, D. (2004). Maximum margin clustering. In Advances in neural information processing systems (pp. 1537-1544).
  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. Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), 298-305.
  16. Bickel, S., & Scheffer, T. (2004, November). Multi-View Clustering. In ICDM (Vol. 4, pp. 19-26).