Clustering

Clustering ist eine unüberwachte maschinelle Lerntechnik, die ähnliche Datenobjekte basierend auf definierten Ähnlichkeitsmaßen in Cluster gruppiert und in der explorativen Datenanalyse in Bereichen wie Mustererkennung und Bioinformatik eingesetzt wird.

Clustering, auch bekannt als Clusteranalyse, ist eine Datenanalysetechnik, die eine Menge von Objekten in Gruppen, sogenannte Cluster, aufteilt, sodass Objekte innerhalb desselben Clusters einander ähnlicher sind als Objekten in anderen Clustern, gemäß einem spezifischen Ähnlichkeits- oder Distanzmaß, das vom Analysten definiert wird. Es ist eine Hauptaufgabe der explorativen Datenanalyse und eine gängige Technik für die statistische Datenanalyse, die in Bereichen wie Mustererkennung, Bildanalyse, Information Retrieval, Bioinformatik, Datenkompression, Computergrafik und maschinellem Lernen eingesetzt wird. Als unüberwachte Lernmethode verlässt sich das Clustering nicht auf beschriftete Daten; stattdessen entdeckt es inhärente Strukturen und Gruppierungen in den Daten ohne Vorwissen über Klassenlabels.

Der Begriff "Clustering" umfasst eine Familie von Algorithmen und Aufgaben und nicht einen einzelnen spezifischen Algorithmus. Verschiedene Algorithmen unterscheiden sich erheblich in ihrem Verständnis davon, was ein Cluster ausmacht und wie man Cluster effizient identifiziert. Gängige Vorstellungen von Clustern umfassen Gruppen mit kleinen Abständen zwischen den Mitgliedern, dichte Bereiche des Datenraums, Intervalle oder bestimmte statistische Verteilungen. Folglich kann Clustering als ein multi-kriterielles Optimierungsproblem formuliert werden, und der geeignete Algorithmus und die Parametereinstellungen (wie die Distanzfunktion, die Dichteschwelle oder die Anzahl der erwarteten Cluster) hängen vom jeweiligen Datensatz und der beabsichtigten Verwendung der Ergebnisse ab. Die Clusteranalyse ist keine automatische Aufgabe, sondern ein iterativer Prozess der Wissensentdeckung oder der interaktiven multi-kriteriellen Optimierung, der oft Versuch und Irrtum erfordert, um die Datenvorverarbeitung und Modellparameter anzupassen, bis das Ergebnis die gewünschten Eigenschaften erreicht.

Neben dem Begriff Clustering existieren mehrere ähnliche Begriffe, darunter automatische Klassifikation, numerische Taxonomie, Botryologie (von griechisch βότρυς 'Traube'), typologische Analyse und Gemeinschaftserkennung. Die subtilen Unterschiede liegen oft in der Verwendung der Ergebnisse: Beim Data Mining sind die resultierenden Gruppen das Objekt des Interesses, während bei der automatischen Klassifikation die resultierende Unterscheidungskraft von Interesse ist.

Geschichte

Die Clusteranalyse hat ihren Ursprung in der Anthropologie mit der Arbeit von Driver und Kroeber im Jahr 1932. Sie wurde von Joseph Zubin 1938 und Robert Tryon 1939 in die Psychologie eingeführt und von Raymond Cattell ab 1943 berühmt für die Klassifikation von Eigenschaftstheorien in der Persönlichkeitspsychologie verwendet. Seitdem hat sich das Clustering zu einem grundlegenden Werkzeug in zahlreichen wissenschaftlichen Disziplinen entwickelt, mit Hunderten von veröffentlichten Algorithmen, die über die Jahrzehnte entwickelt wurden.

Clustermodelle

Der Begriff "Cluster" kann nicht präzise definiert werden, was ein Hauptgrund für die Vielfalt der Clustering-Algorithmen ist. Es gibt einen gemeinsamen Nenner: eine Gruppe von Datenobjekten. Verschiedene Forscher verwenden jedoch unterschiedliche Clustermodelle, und jedes Modell kann durch verschiedene Algorithmen implementiert werden. Das Verständnis dieser Clustermodelle ist entscheidend für das Verständnis der Unterschiede zwischen den Algorithmen. Typische Clustermodelle umfassen:

Konnektivitätsmodelle: Hierarchisches Clustering baut Modelle auf der Grundlage von Distanzkonnektivität auf, bei denen Cluster durch die Verknüpfung von Objekten basierend auf Nähe gebildet werden.
Zentroidmodelle: Der k-Means-Algorithmus repräsentiert jedes Cluster durch einen einzelnen Mittelwertvektor, oder Zentroid, und weist Objekte dem nächsten Zentroid zu.
Verteilungsmodelle: Cluster werden mithilfe statistischer Verteilungen modelliert, wie multivariate Normalverteilungen, die vom Expectation-Maximization (EM)-Algorithmus verwendet werden.
Dichtemodelle: Algorithmen wie DBSCAN, OPTICS und HDBSCAN definieren Cluster als zusammenhängende dichte Regionen im Datenraum, die durch dünn besiedelte Bereiche getrennt sind.
Subraummodelle: Beim Biclustering (auch bekannt als Co-Clustering oder Zwei-Modus-Clustering) werden Cluster sowohl mit Clustermitgliedern als auch mit relevanten Attributen modelliert, sodass Cluster in verschiedenen Unterräumen der Daten existieren können.
Gruppenmodelle: Einige Algorithmen liefern kein verfeinertes Modell für ihre Ergebnisse und geben lediglich die Gruppierungsinformationen an.
Graphbasierte Modelle: Eine Clique, eine Teilmenge von Knoten in einem Graphen, bei der jedes zwei Knoten durch eine Kante verbunden sind, kann als prototypische Form eines Clusters betrachtet werden. Lockerungen der vollständigen Konnektivitätsanforderung, bekannt als Quasi-Cliquen, werden in Algorithmen wie dem HCS-Clustering-Algorithmus verwendet.
Modelle mit signierten Graphen: In signierten Graphen hat jeder Pfad ein Vorzeichen aus dem Produkt der Vorzeichen auf den Kanten. Unter der Annahme der Balancetheorie können Kanten ihr Vorzeichen ändern, was zu einem gegabelten Graphen führt. Das schwächere "Clusterbarkeitsaxiom" (kein Zyklus hat genau eine negative Kante) führt zu Ergebnissen mit mehr als zwei Clustern oder Teilgraphen mit nur positiven Kanten.
Neuronale Modelle: Das bekannteste unüberwachte neuronale Netzwerk ist die selbstorganisierende Karte, und diese Modelle können in der Regel als ähnlich zu einem oder mehreren der oben genannten Modelle charakterisiert werden, einschließlich Subraummodellen, wenn neuronale Netzwerke Formen der Hauptkomponentenanalyse oder der unabhängigen Komponentenanalyse implementieren.

Arten des Clusterings

Ein "Clustering" ist im Wesentlichen eine Menge von Clustern, die normalerweise alle Objekte im Datensatz enthält. Es kann auch die Beziehung der Cluster zueinander angeben, wie eine Hierarchie von Clustern, die ineinander verschachtelt sind. Clusterings können grob unterschieden werden als:

Hartes Clustering: Jedes Objekt gehört zu einem Cluster oder nicht.
Weiches Clustering (auch Fuzzy-Clustering): Jedes Objekt gehört zu jedem Cluster in einem bestimmten Grad, wie einer Wahrscheinlichkeit der Zugehörigkeit.

Feinere Unterscheidungen umfassen:

Strikt partitionierendes Clustering: Jedes Objekt gehört zu genau einem Cluster.
Strikt partitionierendes Clustering mit Ausreißern: Objekte können auch zu keinem Cluster gehören, in diesem Fall werden sie als Ausreißer betrachtet.
Überlappendes Clustering (auch alternatives Clustering, Multi-View-Clustering): Objekte können zu mehr als einem Cluster gehören, was in der Regel harte Cluster beinhaltet.
Hierarchisches Clustering: Objekte, die zu einem Kind-Cluster gehören, gehören auch zum Eltern-Cluster, was eine baumartige Struktur erzeugt.
Subraum-Clustering: Obwohl ein überlappendes Clustering, innerhalb eines eindeutig definierten Unterraums, wird nicht erwartet, dass sich Cluster überlappen.

Algorithmen

Clustering-Algorithmen können basierend auf ihrem Clustermodell kategorisiert werden. Es gibt möglicherweise über 100 veröffentlichte Clustering-Algorithmen, und nicht alle liefern Modelle für ihre Cluster, was die Kategorisierung erschwert. Es gibt keinen objektiv "korrekten" Clustering-Algorithmus; wie bereits erwähnt, "liegt das Clustering im Auge des Betrachters". Tatsächlich zeigt ein axiomatischer Ansatz, dass es unmöglich ist, dass jede Clustering-Methode drei grundlegende Eigenschaften gleichzeitig erfüllt: Skaleninvarianz (Ergebnisse bleiben unter proportionaler Skalierung der Distanzen unverändert), Reichhaltigkeit (alle möglichen Partitionen der Daten können erreicht werden) und Konsistenz zwischen Distanzen und der Clusterstruktur. Der am besten geeignete Algorithmus für ein bestimmtes Problem muss oft experimentell ausgewählt werden, es sei denn, es gibt einen mathematischen Grund, ein Clustermodell einem anderen vorzuziehen.

Prominente Clustering-Algorithmen umfassen:

K-Means: Ein zentroidbasierter Algorithmus, der Daten in k Cluster partitioniert, indem er die Summe der Quadrate innerhalb des Clusters minimiert. Er ist einfach und effizient, erfordert jedoch die Angabe der Anzahl der Cluster und ist empfindlich gegenüber Ausreißern.
Hierarchisches Clustering: Baut eine Hierarchie von Clustern entweder agglomerativ (bottom-up) oder divisiv (top-down) auf. Es erfordert keine vordefinierte Anzahl von Clustern und erzeugt ein Dendrogramm.
DBSCAN: Ein dichtebasierter Algorithmus, der Cluster als dichte Regionen identifiziert, die durch dünn besiedelte Bereiche getrennt sind. Er kann Cluster beliebiger Form finden und mit Ausreißern umgehen, erfordert jedoch die Abstimmung von Parametern wie Epsilon und Mindestpunktzahl.
Expectation-Maximization (EM): Ein verteilungsbasierter Algorithmus, der Cluster als Gaußsche Verteilungen modelliert und iterativ Parameter schätzt, um die Wahrscheinlichkeit zu maximieren.
OPTICS: Eine Erweiterung von DBSCAN, die eine Cluster-Reihenfolge erzeugt, was sie robuster gegenüber variierenden Dichten macht.
Selbstorganisierende Karten (SOM): Ein neuronales Netzwerkmodell, das hochdimensionale Daten auf ein niedrigdimensionales Gitter abbildet und topologische Beziehungen bewahrt.

Anwendungen

Clustering wird in vielen Bereichen weit verbreitet eingesetzt. In der Mustererkennung hilft es, Gruppen in Daten für Klassifikationsaufgaben zu identifizieren. In der Bildanalyse wird es für die Bildsegmentierung und Objekterkennung verwendet. Im Information Retrieval organisiert Clustering Dokumente nach Thema für Suche und Empfehlungen. In der Bioinformatik gruppiert es Gene oder Proteine mit ähnlichen Expressionsmustern. Bei der Datenkompression reduziert Clustering die Datengröße, indem Gruppen mit Prototypen dargestellt werden. In der Computergrafik unterstützt es die Farbquantisierung und die Vereinfachung von Netzen. In der künstlichen Intelligenz ist Clustering eine Kerntechnik für unüberwachtes Lernen, die es Systemen ermöglicht, Muster ohne beschriftete Beispiele zu entdecken.

Herausforderungen und Überlegungen

Clustering stellt mehrere Herausforderungen dar. Die Bestimmung der optimalen Anzahl von Clustern ist oft schwierig und kann Domänenwissen oder Heuristiken erfordern. Die Wahl der Distanzmetrik beeinflusst die Ergebnisse erheblich; gängige Metriken umfassen die euklidische Distanz, die Manhattan-Distanz und die Kosinus-Ähnlichkeit. Hochdimensionale Daten können unter dem Fluch der Dimensionalität leiden, bei dem Distanzen weniger aussagekräftig werden. Clustering-Ergebnisse sind empfindlich gegenüber Initialisierung und Parametereinstellungen, und es gibt keine universelle Lösung. Darüber hinaus bedeutet der iterative Charakter des Clusterings, dass Ergebnisse mithilfe interner oder externer Bewertungsmetriken wie dem Silhouettenkoeffizienten oder dem Rand-Index validiert werden sollten, um sicherzustellen, dass sie die gewünschten Eigenschaften erfüllen.