Clustering vs. Klassifizierung – Mit Beispielen

Holen wir ein wenig aus – nicht umsonst wird unser Zeitalter mitunter das „Daten-Zeitalter“ genannt. Daten sind essenziell, allgegenwärtig und teils in unglaublicher Masse vorhanden. Im Automotive-Bereich ist das Sammeln von Daten unerlässlich, um sichere, funktionale und fortschrittliche Produkte zu schaffen, und das beginnt schon lange vor den Fabrikhallen der Autohersteller, häufig „OEM“ genannt („Original Equipment Manufacturer“). Die Zulieferbranche liefert Hardware und Software, entwickelt, forscht – und sammelt Daten, verwertet diese und bereitet sie so auf, wie der OEM es sich wünscht.

Da die Datenmengen dank Big Data (siehe auch unser Artikel zu den „Big Data Pipelines“) gewaltige Dimensionen aufweisen, ist es eine Aufgabe der Data Science, diese zu segmentieren und zu verwerten. Doch wo anfangen? Und mit welcher Methode? Das klassische Machine Learning kennt hierfür grundsätzlich zwei Methoden: Das Clustering, und die Klassifizierung. Die Klassifizierung zählt zu den „überwachten“ Lernverfahren, was bedeutet, dass die verwendeten Daten bereits mit Labels versehen sein müssen (also jeweils bereits eindeutigen Kategorien angehören). Grob lässt sich sagen, ohne Anspruch auf eine exakte Prozentzahl, dass rund siebzig bis achtzig Prozent der im industriellen Machine Learning eingesetzten Verfahren überwachte Lernverfahren sind. Clustering kommt demnach im Vergleich seltener zum Einsatz, bringt jedoch den großen Vorteil mit sich, dass es als „unüberwachtes“ Verfahren nicht auf vorab existierende Labels angewiesen ist. Dies kann zum Beispiel bei der Analyse von Fehlern in Fehlerlogs hilfreich sein, wenn Art und Ursache der Fehler noch weitestgehend unbekannt sind (dies wären die Labels im überwachten Lernen), sich jedoch bereits Zusammenhänge in verschiedenen Fehlerbildern finden lassen.

Beim Clustering geht es darum, Strukturen und Muster in ungelabelten Daten zu finden. Da es im Vergleich zur Klassifizierung aufgrund der fehlenden Labels jedoch kein wirkliches „richtig oder falsch“ gibt, ist hier Domänenwissen und kritisches Hinterfragen der Ergebnisse der Algorithmen von besonderer Bedeutung. Mit diesem Wissen im Hinterkopf wollen wir im folgenden Abschnitt drei der bekanntesten Clustering-Verfahren etwas genauer erläutern.

Was ist Clustering, und wann setze ich es ein?

Bei der Frage, ob für ein Problem Klassifizierung oder Clustering der richtige Ansatz ist, steht in erster Linie die konkrete Problemstellung im Vordergrund. „Früher hat man überwachtes Lernen praktiziert, dafür benötigte man Trainingsdaten. Heute macht man einfach unüberwachtes Lernen, dann braucht man die Trainingsdaten nicht.“ So oder so ähnlich hat man das sicher schon einmal gehört, wenn es um Clustering im Vergleich zur Klassifizierung geht. Während hier sicherlich ein Funken Wahrheit enthalten sein mag, sind beide Methoden schlicht für unterschiedliche Problemstellungen gemacht.

Stellen wir uns vor, wir seien ein Unternehmen, das versucht, seine Kunden in unterschiedliche Zielgruppen zu segmentieren. Die Daten liegen in Form von Besuchsprotokollen auf unserer Website vor. Nun haben wir zwei Möglichkeiten: Zum einen könnten wir in herkömmlichen Kategorien denken und unsere Besucher nach Alter, Geschlecht etc. sortieren. In diesem Fall wäre Klassifizierung vermutlich die geeignete Wahl. Was aber, wenn unsere Besucher verschiedene Verhaltensmuster aufweisen, die nicht durch diese vorgegebenen Kategorien zu erklären sind? Genau hier kommt Clustering ins Spiel, denn es erlaubt uns, genau diese unbekannten Zusammenhänge aufzudecken. Somit eignet sich Clustering auch als Vorstufe für überwachte Verfahren, denn basierend auf diesen neuen Erkenntnissen lassen sich diese oftmals sehr gut aufsetzen.

Wie aber kann nun ein derartiges Clustering aussehen? Versuchen wir einmal, uns das Ganze etwas bildlicher vorzustellen, indem wir Beispiele verwenden: Egal, in welcher Form die Daten vorliegen, ob als Text, Fehlerlog oder in Form vieler, vieler Zahlen: Wir stellen uns diese Daten als umherschwirrende Teile im Universum vor. Im Machine Learning fragen wir uns: Wo sind meine Punkte? Wo sind meine Sonnen, meine Planeten, und wo „klumpen“, also „clustern“ diese zu „Galaxien“ oder „Kugelsternhaufen“ zusammen. In einem herkömmlichen zweidimensionalen Raum, wie einer Zeichnung, können wir dies sofort sehen. Im dreidimensionalen Raum, wie bei einem Computerspiel, könnten wir den Raum und die Daten rotieren lassen und sehen ebenfalls den Status Quo. In einem multidimensionalen Raum mit 64 Dimensionen gibt es indes keinen Einblick mehr. Am praktischen Beispiel eines Fehlerspeichers wären solche Dimensionen die Frage, wie oft der Fehler aufgetreten ist. Wann genau? Welche Begleitdaten kommen dazu, wie lautet der Kilometerstand, die Fahrzeugdaten und vieles mehr? So erhalten wir zahlreiche Dimensionen – natürlich ohne eine echte räumliche Dimension -, insgesamt also multidimensionalen Raum, in dem wir nun beginnen, die Daten zu clustern.

Dafür gibt es verschiedene Methoden, wir wollen im Folgenden aber auf drei der bekanntesten Verfahren eingehen.

Hierarchisches Clustering – Cluster auf mehreren Ebenen

Eine der bekanntesten und häufig genutzten Clustering Methoden ist das sogenannte Hierarchische Clustering: Eines der einfachsten Verfahren, um Daten zu clustern. Für einen bildlichen Vergleich können wir uns vorstellen, dass die Daten die grobe Struktur eines Baums haben, dessen Blätter die jeweiligen Datenpunkte sind und welche über Zweige und Äste bis hin zum Stamm auf mehreren Ebenen miteinander verknüpft sind. Die Frage ist nun: Welche Blätter gehören zu welchem Zweig, welche Zweige zu welchem Ast, und wo docken die Äste an den Stamm an? Zur Beantwortung dieser Frage werden zunächst alle Blätter als eigener, kleiner Cluster betrachtet. Die beiden ähnlichsten Blätter werden daraufhin demselben Zweig zugeordnet und bilden einen neuen Cluster, der die beiden Blätter enthält. Auf diese Weise wachsen die Cluster in jedem Schritt an, bis am Ende beim Stamm alle Blätter miteinander verknüpft sind. Das Schöne an diesem Ansatz ist, dass sich jede Ebene einzeln betrachten lässt und dadurch verschachtelte Zusammenhänge erkannt werden.

Wie aber weiß der Algorithmus, wann zwei Blätter einen neuen Cluster bilden, oder jeweils ein Blatt einem bestehenden Cluster zugeordnet wird? Dafür gibt es verschiedene „Linkage“-Ansätze, etwa die „Average Linkage“ bei dem die Ähnlichkeit zwischen dem neuen Blatt und dem „durchschnittlichen“ Blatt des bisherigen Zweigs betrachtet wird. Alternative Ansätze zielen dagegen auf das ähnlichste, am Zweig befindliche Blatt („Single Linkage“) oder aber das unähnlichste („Complete Linkage“).

Um noch ein Beispiel zu zitieren, ließe sich das Bild einer DNA-Helix visualisieren. Aus geometrischer Hinsicht handelt es sich vornehmlich um zwei Bänder, die sich umeinanderschlingen. Andere Methoden wie etwa das nachfolgend behandelte k-Means wären hier ungeeignet, da dieses praktisch „mittendurch schneiden“ würde. Mit Single Linkage Hierarchical Clustering ließe sich diese Datenstruktur indes gut erkennen, da dieses – vereinfacht dargestellt – besagt: „Wenn A ein bestehender Cluster ist, und Punkt X ist sehr nah an diesem Cluster befindlich, wird dieser Punkt dazugehören.“ So kann sich das Clustering nach und nach vorarbeiten und auch komplexe Strukturen identifizieren, bis alle ähnlichen Punkte zusammengefasst wurden und einen Schnitt machen kann, um zu sehen, an welchem Punkt das Clustering beendet ist.

k-Means – The Godfather of Clustering für große Datenmengen

Die Überschrift nimmt es vorweg: Das Clustering via k-Means gilt als berühmteste Methode im Clustering, da es einfach skalierbar und parallelisierbar ist, also vor allem zum Clustering riesiger Datenmengen geeignet ist. Vor allem die Möglichkeiten, Clustering per k-Means parallel – teils auf hunderten hochleistungsfähigen Rechnern – zu betreiben und das Ergebnis am Ende zusammenzusetzen, ist für große Datenmengen ein nicht von der Hand zu weisender Vorteil.

Anders als beim schrittweisen Aufbau verschachtelter Cluster beim Hierarchischen Clustering suchen wir bei k-Means nach sogenannten „Zentroiden“, so benannten Prototypen für die jeweiligen Cluster. Klingt ein bisschen nach Machine Learning Star Trek („Die Zentroiden assimilieren, statt zu labeln, Captain k-Means!“), ist aber praktisch eine „Vorstellung“, die repräsentativ für eine bestimmte Art Daten steht und nachfolgend nach dem nächsten Prototyp sucht, der immer wieder auf Basis der realen Datenpunkte neu berechnet und iteriert wird. Für die Philosophen unter den Lesern sei Platons Höhengleichnis und die „Idee“ von Dingen zitiert, wenngleich die wissenschaftliche Realität freilich komplexer ist als unser populärwissenschaftlicher Ansatz.

Der Ablauf von k-Means ist dabei ebenso simpel wie intelligent: Ausgehend von zufällig gewählten „Start-Zentroiden“ werden alle Punkte ihrem nächstgelegenen Zentroiden (und damit einem Cluster) zugeordnet. Auf Basis dieser Zuordnung werden dann neue Zentroiden berechnet als Durchschnitt des aktuellen Clusters. Dieses Vorgehen wird so lange wiederholt, bis sich die Zuordnung von Punkten zu Zentroiden nicht länger ändert.

Das Clustering via k-Means funktioniert immer dann gut, wenn die Datenstruktur in einer Art „Kugelsternhaufen“ angeordnet ist, von annähernd gleichem Durchmesser und ähnlicher Dichte, die sich optimalerweise auch nicht groß überschneiden.

Nicht gut geeignet ist k-Means, wenn die Cluster unterschiedlich groß sind. Wo das bloße Auge Größenunterschiede problemlos wahrnimmt, kann k-Means hier nicht sauber separieren, einfach, weil der zugrunde liegende Algorithmus das so nicht leisten kann. Ein im Bereich Data Science bzw. Machine Learning oft bemühtes Beispiel ist das eines Micky Maus Kopfes, also drei kreisförmige Cluster, ein großer für den „Kopf“, sowie zwei kleinere für die „Ohren“. Selbst bei einer optimalen Wahl der zufälligen „Start-Zentroiden“ kann es passieren, dass die finalen Cluster nicht diesen drei „offensichtlich“ erkennbaren entsprechen. Stattdessen werden gegebenenfalls einige zum „Kopf“ gehörige Punkte den „Ohren“ zugeordnet, da sie aufgrund des Größenunterschieds der jeweiligen Cluster näher am jeweils anderen Zentroiden liegen. Ein weiteres Beispiel wäre der Planet Saturn, mit einem dicken Cluster in der Mitte und einem ringförmigen Cluster darum. k-Means könnte dies nicht interpretieren und würde den Datencluster womöglich fälschlicherweise in der Mitte des Planeten schneiden – für derartige Strukturen, ihr ahnt es schon, wäre das Hierarchische Clustering mit Single Linkage weit besser geeignet.

Auch wichtig beim Einsatz von k-Means ist, auf die Interpretierbarkeit der Cluster zu achten und diese zu prüfen. Oft wird k-Means als vermeintlich kaum fehlbares Magic Tool betrachtet, aber gerade bei großen Projekten ist es unerlässlich, immer wieder auf die Cluster zu schauen, ob diese logisch betrachtet wirklich so ausfallen können, oder ob k-Means Interpretationsschwierigkeiten bekommt. Hierfür sind Visualisierung und Dimensionsreduktionsverfahren ebenfalls essenziell. Einer der absoluten Vorteile, neben der Skalierbarkeit, Parallelisierung und Bewältigung riesiger Datenmengen ist, dass nach „k“ verschiedenen Clustern (daher der Name) gesucht werden kann. Da vorher nicht unbedingt bekannt ist, wie groß dieses „k“ sein muss, können verschiedenste Clusteranordnungen gesucht und am Ende zusammengefasst werden, bzw. lässt sich prüfen, welches „k“ die Daten am besten erklären kann (wir erklären nicht, werfen aber in den Raum, dass die „Ellbogen-Methode“ hier eine Rolle spielt).

Clustering mit DBSCAN – Wenn Mitte und Dichte gesucht werden

Last, but not least, selbstredend, werfen wir unseren Blick auf DBSCAN als dritte Clustering Methode. DBSCAN steht dabei mitnichten für einen häufig zu spät kommenden ÖPNV Scan, sondern für ein dichtebasiertes Clusteringverfahren (hier ersparen wir euch jetzt zahlreiche alberne Wortwitze, aber mit diesem Impuls regen wir eure Fantasie sicherlich bereits an!).

Dieses Verfahren setzt einen Mittelpunkt im hochdimensionalen Raum und sucht von hier aus die Punkte in unmittelbarer Umgebung ab, in der sich bestimmte Strukturen finden lassen. Die Besonderheit, die DBSCAN mitbringt, ist das grobe Funktionsprinzip, mittels dessen sich eine Mitte mit Radius und Dichtestrukturen identifizieren lassen. Cluster sind dabei Mengen von Punkten, die „dichte-verbunden“ sind. Das bedeutet, dass ein Punkt entweder selbst „dicht“ ist, sich also in einem bestimmten Radius entsprechend viele andere Punkte finden lassen, oder sich ein Punkt in der näheren Umgebung eines solchen dichten Punkts befindet.

Der vorigen Beschreibung kann man entnehmen, dass DBSCAN explizit auch „Noise“ erkennen kann, nämlich Punkte, die nicht „dichte-verbunden“ sind. Wo hierarchisches Clustering und k-Means zwangsläufig jeden Datenpunkt einem Cluster zuweisen, kann DBSCAN Datenpunkte identifizieren, die zu keinem Cluster gehören und gewissermaßen lediglich „mitrauschen“. Dies kann daher ein exzellentes Verfahren sein, um die Daten zu finden, die am Ende wirklich von Bedeutung sind, statt nur Daten bestehenden Clustern zuzuordnen und somit Datenpunkte zu übersehen, die in keines der gefundenen Raster passen. DBSCAN kann also Datenpunkte ohne Cluster und ohne viele nahe Partner isolieren und finden, was in anderen Clustering Verfahren nicht möglich ist, da es in deren Modellen schlicht nicht vorgesehen ist. Den vorhin bereits erwähnten Micky Maus Kopf könnte DBSCAN also deutlich besser erkennen und bestimmen, welche Datenpunkte in die Struktur gehören, und welche nicht (die aber dennoch von Bedeutung sein können).

Clustering Methoden in der Data Science – Das Fazit

Mit diesem Artikel habt ihr einen ersten Überblick gewonnen, welche Clustering Methoden gängig sind, wie sie – vereinfacht übermittelt – funktionieren und wann sie sich idealerweise einsetzen lassen. Diese Insights in das komplexe Feld industriellen Machine Learnings verdanken wir der Expertise unseres Data Science Teams mit Ansprechpartner Dr. Daniel Isemann, den wir für diesen Beitrag gründlich ausgehorcht haben – ein Termin, nachdem wir uns gleichzeitig klüger und etwas dümmer fühlten, da wir viel gelernt haben, aber auch klar wurde, welche gewaltige Dimensionen Daten und deren Verarbeitung heutzutage angenommen haben.

Umso wichtiger daher, dass sich OEMs zuverlässige Partner suchen, die eine hohe Expertise und Projekterfahrung aufweisen, um große Projekte effektiv abzuwickeln. Allzu hoch ist andernfalls die Gefahr, im Rahmen der Datensegmentierung nach der sprichwörtlichen Nadel im Heuhaufen zu suchen, mit der zusätzlichen Herausforderung, dass die Nadel die Größe eines Staubkorns hat, der Heuhaufen aber Planetengröße aufweist. Um hier keine Kosten und unnötig lange Entwicklungszeiten in Kauf zu nehmen, können OEMs sowohl aus dem Automotivebereich auf uns zukommen und unkompliziert Kontakt für den Austausch von Expertise oder einer ersten Beratung mit uns aufnehmen, als auch aus anderen Branchen. Schließlich arbeitet die Cognizant Mobility, die Mutterfirma der Mobility Rockstars, auch über den Tellerrand hinaus und hat beispielsweise in der Medizintechnik bereits visionäre Projekte abgeschlossen.

Folgt uns am besten auch auf LinkedIn und/oder abonniert unseren Newsletter, um weitere, spannende Artikel nicht zu verpassen, wie beispielsweise den Partnerartikel zur Klassifizierung.