Datasets für maschinelles Lernen können Millionen von Beispielen enthalten, aber nicht alle Clustering-Algorithmen sind effizient skalierbar. Viele Clustering-Algorithmen berechnen die Ähnlichkeit zwischen allen Beispielpaaren. Das bedeutet, dass ihre Laufzeit quadratisch mit der Anzahl der Beispiele ansteigt \(n\), was in der Komplexitätsnotation als \(O(n^2)\) angegeben wird. \(O(n^2)\) -Algorithmen sind für Datensätze mit Millionen von Beispielen nicht praktikabel.
Der K-Means-Algorithmus hat eine Komplexität von \(O(n)\), was bedeutet, dass er linear mit \(n\)skaliert. Dieser Algorithmus steht im Mittelpunkt dieses Kurses.
Arten von Clustering
Eine umfassende Liste verschiedener Ansätze zum Clustering finden Sie unter A Comprehensive Survey of Clustering Algorithms (Eine umfassende Übersicht über Clustering-Algorithmen) von Xu, D. und Tian, Y. Ann. Daten. Sci. (2015) 2: 165. Jeder Ansatz eignet sich am besten für eine bestimmte Datenverteilung. In diesem Kurs werden vier gängige Ansätze kurz erläutert.
Centroidbasiertes Clustering
Der Schwerpunkt eines Clusters ist der arithmetische Mittelwert aller Punkte im Cluster. Beim centroidbasierten Clustering werden die Daten in nicht hierarchische Cluster organisiert. Centroidbasierte Clustering-Algorithmen sind effizient, aber empfindlich gegenüber Anfangsbedingungen und Ausreißern. Von diesen wird K-Means am häufigsten verwendet. Die Anzahl der Centroide, k, muss vom Nutzer festgelegt werden. Die Methode eignet sich gut für Cluster mit ungefähr gleicher Größe.
Dichtebasiertes Clustering
Beim dichtebasierten Clustering werden zusammenhängende Gebiete mit hoher Beispieldichte zu Clustern zusammengefasst. So können beliebig viele Cluster beliebiger Form gefunden werden. Ausreißer werden keinen Clustern zugewiesen. Diese Algorithmen haben Probleme mit Clustern unterschiedlicher Dichte und Daten mit vielen Dimensionen.
Verteilungsbasiertes Clustering
Bei diesem Clustering-Ansatz wird davon ausgegangen, dass die Daten aus probabilistischen Verteilungen bestehen, z. B. aus Gaußschen Verteilungen. In Abbildung 3 clustert der distributionsbasierte Algorithmus Daten in drei Gaußverteilungen. Je größer die Entfernung vom Zentrum der Verteilung ist, desto geringer ist die Wahrscheinlichkeit, dass ein Punkt zur Verteilung gehört. Die Balken zeigen diese Abnahme der Wahrscheinlichkeit. Wenn Sie sich nicht sicher sind, ob Sie eine bestimmte zugrunde liegende Verteilung der Daten annehmen können, sollten Sie einen anderen Algorithmus verwenden.
Hierarchisches Clustering
Bei der hierarchischen Clusteranalyse wird ein Clusterbaum erstellt. Hierarchisches Clustering eignet sich nicht überraschend gut für hierarchische Daten wie Taxonomien. Ein Beispiel hierfür ist der Artikel Comparison of 61 Sequenced Escherichia coli Genomes von Oksana Lukjancenko, Trudy Wassenaar und Dave Ussery. Sie können eine beliebige Anzahl von Clustern auswählen, indem Sie den Baum auf der richtigen Ebene abschneiden.
