Unter dem Clusteringproblem versteht man das Zusammenfassen von Objekten oder Daten zu Gruppen, den Clustern. Sie werden im Gegensatz zur Klassifizierung nicht vorgegeben, sondern ergeben sich auf Grund der Ähnlichkeit der verschiedenen, betrachteten Objekte. Mit Ähnlichkeit ist dabei der räumliche Abstand der Objekte, als Vektoren dargestellt, gemeint. Es gibt verschiedene Verfahren diesen Abstand zu bestimmen wie z.B. die Euklidische- oder Minkowski-Metrik. Bereits beim Bestimmen der Ähnlichkeit stellt man fest, dass es keine eindeutige Clusterbestimmung gibt.
Clusteringverfahren
Es gibt verschiedene Verfahren die einzelnen Objekte in Cluster einzuordnen, die jeweils ihre eigenen Vor- und Nachteile haben und andere Ergebnisse erzielen. Meistens muss man, um die besten Ergebnisse für einen Datensatz zu erzielen, verschiedene dieser Verfahren mit unterschiedlichen Parametern ausprobieren und sich danach für eines entscheiden. Es existiert nämlich kein Verfahren, dass allgemein am besten funktioniert. Zu den häufig vorkommenden Unsupervised Learning Verfahren zählen:
Hierarchisches Clustering
Beim hierarchischen Clustering wird zu Beginn entweder die Menge aller Objekte gesamt (top-down) oder die Menge aller einzelnen Objekte (bottom-up) als Cluster angenommen. Beim top-down Verfahren, wird der jeweils größte Cluster aufgeteilt, in dem das am weitesten Entfernte Objekt zum Zentrum des Clusters als ein neues Clusterzentrum ausgewählt wird. Danach ordnet der Algorithmus alle Objekte dem jeweils näheren Clusterzentrum zu. Beim bottom-up Verfahren werden die jeweils kleinsten und nähesten Cluster zu einem neuen Cluster zusammengefasst. Schwierig bei beiden Verfahren ist, einerseits festzulegen auf welche Art man den Abstand der einzelnen Objekte bestimmt, andererseits, wie weit man die Cluster aufteilen, bzw. zusammenfassen will. Schließlich sollte man den Vorgang nicht so lange wiederholen, bis so viele Cluster wie Objekte oder nur noch ein Cluster übrig bleiben.
Partitionierendes Clustering
Beim partitionierenden Clustering wird zunächst eine Zahl k festgelegt, die die Anzahl der Cluster vorgibt. Darauf bestimmt der jeweilige Algorithmus k Clusterzenten. Beispielsweise legt der K-Means-Algorithmus, einer der verbreitetsten partitionierenden Clusteringverfahren, die Clusterzentren zufällig fest. Diese Zentren werden anschließend so verschoben, dass die Summer der quadrierten Abstände der Objekte zu ihrem nächsten Clusterzentrum minimiert wird. Vorteil des partitionierenden Verfahrens ist, dass die Zugehörigkeit der einzelnen Objekte zu einem Cluster während der Clusterfindung veränderbar ist. Andererseits ist die Eigenschaft, dass bereits zu Beginn festgelegt die Anzahl der Clusterzentren festgelegt wird ein großer Nachteil, da man um optimale Ergebnisse zu erzielen, den Algorithmus mit verschiedenen Werten ausführen und anschließend eines auswählen muss.
Dichtenbasiertes Custering
Beim dichtebasierten Clustering werden die verschiedenen Cluster durch die Dichte der einzelnen Objekte im Raum bestimmt. Das populärste dieser Verfarhen ist der DBSCAN Algorithmus. Dabei wird ein Abstand ε zusammen mit einer Zahl k bestimmt. Objekte, die k Nachbarobjekte mit dem Abstand kleiner ε bestizen, stellen zusammen Kernobjekte dar. Wenn zwei Kernobjekte mit Abstand ε zueinander vorliegen, werden sie zu einem Cluster zusammengefasst. Objekte die keine Kernobjekte sind, sich aber in der Nähe eines Clusters befinden, ordnet man dem Cluster hinzu. Die Objekte die keinem Cluster zugehörig sind, gelten als Rauschobjekte.
Anwendungen
Da Clusteringverfahren abstrakte Zusammenhänge in Daten finden, die ein Mensch so womöglich nicht offensichtlich wahrnimmt, finden sie heute in vielen Bereichen wie z.B. in der Marktanalyse Anwendung. In der Marktanalyse wird das Clustering verbreitet eingesetzt um Daten aus z.B. Umfragen auszuwerten. Hierbei werden Kunden in allgemeine Gruppen eingeteilt um beispielsweise bessere Produktplatzierungen zu ermöglichen. Außerdem wird das Clustering im Natural Language Processing (NLP) eingesetzt. Hierbei ermöglichen sie die automatisierte Auswertung von Texten und Sprache. Ein weiteres interessantes Feld, in dem Clustering zum Einsatz kommt, ist die Kriminalitätsanalyse. Hierbei erlaubt das Clustering eine effizienten Einsatz von Polizei- und Sicherheitskräften, da man Kriminalitäts-Hot-Spots besser erkennen kann.
Hürden des Clusterings
Das Clustering ist bei großen Datenmengen sehr zeitaufwendig, besonders wenn der Raum mehrere Dimensionen besitzt. Weiter ist die Effektivität des Clusterings durch das gewählte Verfahren der Abstandmessung bestimmt. In der Regel gibt es kein allgemein richtiges Ergebnis. Das liegt daran, dass dieses in Abhängigkeit der verschiedenen Verfahren mit jeweils verschiedenen Parametern zum Teil drastisch unterschiedlich ausfällt. Dadurch ist es schwer, das Ergebnis zu interpretieren und die Richtigkeit zu überprüfen. Möglichkeiten diese Überprüfung durchzuführen wären, das Resultat des Clusterings mit bekannten Klassifizierungen zu vergleichen oder die Auswertung durch einen menschlichen Experten. Beide Varianten sind aber nur bedingt geeignet, da einerseits das Clustering nicht nötig wäre, wenn es bereits bekannte Klassifizierungen gäbe und andererseits menschliche Beurteilungen stets sehr subjektiv ist.
