Mit Sammlungen den Überblick behalten Sie können Inhalte basierend auf Ihren Einstellungen speichern und kategorisieren.
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.
Abbildung 1: Beispiel für ein centroidbasiertes Clustern.
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.
Abbildung 2: Beispiel für ein dichtebasiertes Clustern.
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.
Abbildung 3: Beispiel für ein distributionsbasiertes Clustern.
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.
Abbildung 4: Beispiel für ein hierarchisches Baumcluster mit Tieren.
[[["Leicht verständlich","easyToUnderstand","thumb-up"],["Mein Problem wurde gelöst","solvedMyProblem","thumb-up"],["Sonstiges","otherUp","thumb-up"]],[["Benötigte Informationen nicht gefunden","missingTheInformationINeed","thumb-down"],["Zu umständlich/zu viele Schritte","tooComplicatedTooManySteps","thumb-down"],["Nicht mehr aktuell","outOfDate","thumb-down"],["Problem mit der Übersetzung","translationIssue","thumb-down"],["Problem mit Beispielen/Code","samplesCodeIssue","thumb-down"],["Sonstiges","otherDown","thumb-down"]],["Zuletzt aktualisiert: 2025-06-09 (UTC)."],[[["\u003cp\u003eMany clustering algorithms have a complexity of O(n^2), making them impractical for large datasets, while the k-means algorithm scales linearly with a complexity of O(n).\u003c/p\u003e\n"],["\u003cp\u003eClustering approaches include centroid-based, density-based, distribution-based, and hierarchical clustering, each suited for different data distributions and structures.\u003c/p\u003e\n"],["\u003cp\u003eCentroid-based clustering, particularly k-means, is efficient for grouping data into non-hierarchical clusters based on the mean of data points, but is sensitive to initial conditions and outliers.\u003c/p\u003e\n"],["\u003cp\u003eDensity-based clustering connects areas of high data density, effectively discovering clusters of varying shapes, but struggles with clusters of differing densities and high-dimensional data.\u003c/p\u003e\n"],["\u003cp\u003eDistribution-based clustering assumes data follows specific distributions (e.g., Gaussian), assigning points based on probability, while hierarchical clustering creates a tree of clusters, suitable for hierarchical data.\u003c/p\u003e\n"]]],[],null,["Machine learning datasets can have millions of\nexamples, but not all clustering algorithms scale efficiently. Many clustering\nalgorithms compute the similarity between all pairs of examples, which\nmeans their runtime increases as the square of the number of examples \\\\(n\\\\),\ndenoted as \\\\(O(n\\^2)\\\\) in complexity notation. \\\\(O(n\\^2)\\\\) algorithms are not\npractical for datasets with millions of examples.\n\nThe [**k-means algorithm**](/machine-learning/glossary#k-means) has a\ncomplexity of \\\\(O(n)\\\\), meaning that the algorithm scales linearly with \\\\(n\\\\).\nThis algorithm will be the focus of this course.\n\nTypes of clustering\n\nFor an exhaustive list of different approaches to clustering, see\n[A Comprehensive Survey of Clustering Algorithms](https://link.springer.com/article/10.1007/s40745-015-0040-1)\nXu, D. \\& Tian, Y. Ann. Data. Sci. (2015) 2: 165. Each approach is best suited to\na particular data distribution. This course briefly discusses four common\napproaches.\n\nCentroid-based clustering\n\nThe [**centroid**](/machine-learning/glossary#centroid) of a cluster is the\narithmetic mean of all the points in the\ncluster. **Centroid-based clustering** organizes the data into non-hierarchical\nclusters. Centroid-based clustering algorithms are efficient but sensitive to\ninitial conditions and outliers. Of these, k-means is the most\nwidely used. It requires users to define the number of centroids, *k*, and\nworks well with clusters of roughly equal size.\n**Figure 1: Example of centroid-based clustering.**\n\nDensity-based clustering\n\nDensity-based clustering connects contiguous areas of high example density into\nclusters. This allows for the discovery of any number of clusters of any shape.\nOutliers are not assigned to clusters. These algorithms have difficulty with\nclusters of different density and data with high dimensions.\n**Figure 2: Example of density-based clustering.**\n\nDistribution-based clustering\n\nThis clustering approach assumes data is composed of probabilistic\ndistributions, such as\n[**Gaussian distributions**](https://wikipedia.org/wiki/Normal_distribution). In\nFigure 3, the distribution-based algorithm clusters data into three Gaussian\ndistributions. As distance from the distribution's center increases, the\nprobability that a point belongs to the distribution decreases. The bands show\nthat decrease in probability. When you're not comfortable assuming a particular\nunderlying distribution of the data, you should use a different algorithm.\n**Figure 3: Example of distribution-based clustering.**\n\nHierarchical clustering\n\n**Hierarchical clustering** creates a tree of clusters. Hierarchical clustering,\nnot surprisingly, is well suited to hierarchical data, such as taxonomies. See\n[*Comparison of 61 Sequenced Escherichia coli Genomes*](https://www.researchgate.net/figure/Pan-genome-clustering-of-E-coli-black-and-related-species-colored-based-on-the_fig1_45152238)\nby Oksana Lukjancenko, Trudy Wassenaar \\& Dave Ussery for an example.\nAny number of clusters can be chosen by cutting the tree at the right level.\n**Figure 4: Example of a hierarchical tree clustering animals.** **Key terms:**\n|\n| - [k-means algorithm](/machine-learning/glossary#k-means)\n| - [centroid](/machine-learning/glossary#centroid)\n| - [Gaussian distributions](/machine-learning/glossary#Normal_distribution)"]]
