Clusteranalyse

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. Anders ausgedrückt handelt es sich bei Clustering um die Gruppierung von Objekten, so dass die Mitglieder jeder Gruppe ähnlich zueinander sind und unähnlich von anderen Gruppen. 

Grundlagen

Ausgangslage:

Ausgangspunkt ist somit eine Menge O von Objekten, die einheitlich repräsentiert werden. zB als Punkte im Rn Raum (feature vectors). 

Wie bestimmt man die Ähnlichkeit von Objekten?

Üblicherweise werden Ähnlichkeiten zwischen Objekten über ihre Distanz zueinander approximiert. Je größer die Distanz, desto unähnlicher sind die Objekte. 

Ziel:

Ziel ist es bestimmte Gruppen (Klassen, Kluster), die Bestandteil der Ausgangemenge O sind, zu finden, sodass 

• • zwischen Objekten innerhalb eines Clusters große Ähnlichkeit besteht (große intra-cluster Ähnlichkeit)

  • die Ähnlichkeit zu Objekten außerhalb des Clusters möglichst gering ist (geringe inter-cluster Ähnlichkeit)

Unterschied zur Klassifikation

graphentheoretische Clusterverfahren

DBSCAN - dirchteverbundene Cluster

DBSCAN (Density-Based Spatial Clustering of Applications with Noise, etwa: Dichtebasierte räumliche Clusteranalyse mit Rauschen)  arbeitet dichtebasiert und ist in der Lage, mehrere Cluster zu erkennen. Rauschpunkte werden dabei ignoriert und separat zurückgeliefert. 

• • Allgemeines

    • Wikipedia: deutsch | englisch

  • Primärliteratur:

    • Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu (1996-). "A density-based algorithm for discovering clusters in large spatial databases with noise". In Evangelos Simoudis, Jiawei Han, Usama M. Fayyad. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. pp. 226–231. ISBN 1-57735-004-9.

hierarchische Clusterverfahren

• • Allgemeines

    • Wikipedia: deutsch | 

partitionierende Clusterverfahren

dd

k-means-Algorithmus

• • Allgemeines

    • Wikipedia: deutsch 

  • Umsetzung

    • Umsetzung in Excel:

    • k-Means Cluster Analysis in Microsoft Excel

EM-Algorithmus

• • EM-Algorithmus [Wikipedia]

Spektral Clustering

ddd

Maximum Margin Clustering

ddd

Multiview Clustering

...

Self-Organizing Maps (SOMs)

ddd

Fuzzy Clustering

ddd

Literatur

• • Backhaus, Klaus - Multivariante Analysemethoden (Eine anwendungsorientierte Einführung) [Amazon | GoogleBooks | Springer]

  • Backhaus, klaus - Fortgeschrittene Multivariante Analysemethoden (Eine anwendungsorientierte Einführung) [Amazon | GoogleBooks | Springer]

  • Tan, Pan-Ning - Introduction to Data Mining (2004)