Оптимизируйте свои подборки Сохраняйте и классифицируйте контент в соответствии со своими настройками.
Наборы данных машинного обучения могут содержать миллионы примеров, но не все алгоритмы кластеризации эффективно масштабируются. Многие алгоритмы кластеризации вычисляют сходство между всеми парами примеров, что означает, что время их выполнения увеличивается пропорционально квадрату количества примеров. \(n\), обозначенный как \(O(n^2)\) в обозначениях сложности. \(O(n^2)\) алгоритмы непрактичны для наборов данных с миллионами примеров.
Алгоритм k-средних имеет сложность \(O(n)\), что означает, что алгоритм масштабируется линейно с \(n\). Этот алгоритм будет в центре внимания данного курса.
Типы кластеризации
Исчерпывающий список различных подходов к кластеризации см. в «Комплексном обзоре алгоритмов кластеризации» Сюй, Д. и Тиан, Ю. Энн. Данные. наук. (2015) 2: 165. Каждый подход лучше всего подходит для конкретного распределения данных. В этом курсе кратко обсуждаются четыре распространенных подхода.
Центроидная кластеризация
Центроид кластера — это среднее арифметическое всех точек кластера. Кластеризация на основе центроидов организует данные в неиерархические кластеры. Алгоритмы кластеризации на основе центроидов эффективны, но чувствительны к начальным условиям и выбросам. Из них наиболее широко используется k-средние. Он требует от пользователей определения количества центроидов k и хорошо работает с кластерами примерно одинакового размера.
Рисунок 1: Пример кластеризации на основе центроидов.
Кластеризация на основе плотности
Кластеризация на основе плотности объединяет смежные области с высокой плотностью примеров в кластеры. Это позволяет обнаружить любое количество кластеров любой формы. Выбросы не назначаются кластерам. Эти алгоритмы испытывают трудности с кластерами различной плотности и данными большой размерности.
Рисунок 2: Пример кластеризации на основе плотности.
Кластеризация на основе распределения
Этот подход к кластеризации предполагает, что данные состоят из вероятностных распределений, таких как распределения Гаусса . На рисунке 3 алгоритм, основанный на распределении, группирует данные в три распределения Гаусса. По мере увеличения расстояния от центра распределения вероятность того, что точка принадлежит распределению, уменьшается. Полосы показывают это уменьшение вероятности. Если вам неудобно предполагать определенное базовое распределение данных, вам следует использовать другой алгоритм.
Рисунок 3: Пример кластеризации на основе распределения.
Иерархическая кластеризация
Иерархическая кластеризация создает дерево кластеров. Неудивительно, что иерархическая кластеризация хорошо подходит для иерархических данных, таких как таксономии. Для примера см. «Сравнение 61 секвенированного генома Escherichia coli» Оксаны Лукьянченко, Труди Вассенаар и Дэйва Ассери. Любое количество кластеров можно выбрать, срезав дерево на нужном уровне.
Рисунок 4: Пример иерархической древовидной кластеризации животных.
[[["Прост для понимания","easyToUnderstand","thumb-up"],["Помог мне решить мою проблему","solvedMyProblem","thumb-up"],["Другое","otherUp","thumb-up"]],[["Отсутствует нужная мне информация","missingTheInformationINeed","thumb-down"],["Слишком сложен/слишком много шагов","tooComplicatedTooManySteps","thumb-down"],["Устарел","outOfDate","thumb-down"],["Проблема с переводом текста","translationIssue","thumb-down"],["Проблемы образцов/кода","samplesCodeIssue","thumb-down"],["Другое","otherDown","thumb-down"]],["Последнее обновление: 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,["# Clustering algorithms\n\nMachine 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-------------------\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\n### Centroid-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\n### Density-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\n### Distribution-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\n### Hierarchical 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)"]]
