Навигация по странице
Алгоритм k-средних
В прошлой статье мы уже разобрались с тем, что такое кластеризация, для чего она применяется, и сравнили два самых популярных алгоритма. Сейчас нам предстоит познакомиться поближе с алгоритмом k-средних, понять принцип его работы и рассмотреть реализацию на языке Python.
Давайте вспомним, что из себя представляет алгоритм k-средних. Он прост по своей сути: вы заранее определяете, сколько групп (кластеров) хотите получить, а алгоритм сам находит центры этих групп и относит каждый объект к ближайшему из них.
Представьте, что у вас есть множество точек на плоскости — например, координаты клиентов службы доставки или магазинов на карте. Вы говорите: «хочу разбить их на две группы». Алгоритм начинает с того, что случайно выбирает два центра.
Дальше он смотрит, какие точки ближе к какому центру, и делит их на группы (кластеры). Затем он пересчитывает центры, исходя из новых групп, и снова распределяет точки. Этот процесс повторяется, пока всё не стабилизируется — то есть группы и их центры не перестанут меняться.
Теперь разберём эту логику на простом и понятном примере.
Предположим, что у нас есть некоторые точки (см. рисунок ниже) на плоскости. Мы хотим разделить эти точки на два кластера с помощью алгоритма k-средних. Для этого в абсолютно случайных позициях определим два центроида (точки, представляющие центр кластера) (Шаг 1).
Каждой точке назначается ближайший центроид. В нашем случае точкам A и B назначен оранжевый центроид, а точкам C, D и E – зелёный (Шаг 2).
Теперь центроиды смещаются: каждый перемещается в точку, рассчитываемую как среднее по всем приписанным к нему элементам. То есть расстояния от каждой точки к центроиду своего кластера должны быть одинаковыми и минимальными. Таким образом, оранжевый центроид сдвинется ближе к точкам A и B, а зелёный встанет между точками C, D и E (Шаг 3).
Далее идёт повторение предыдущих двух шагов: точки снова распределяются по новым центроидам, затем смещаются центроиды и так далее. Например, в нашем случае оказывается, что точка C теперь ближе к оранжевому центроиду, нежели к зелёному (Шаг 4).
Этот процесс продолжается до тех пор, пока группы и центры не перестанут изменяться (Шаг 5). Как правило, это происходит за 5–10 итераций, а иногда и быстрее. Вы можете ознакомиться с визуализацией алгоритма k-средних на этом сайте.
В данном примере наши случайные центроиды оказались в удачном положении. Но бывают и такие случаи, когда неудачный выбор начальных центроидов может привести к плохому результату кластеризации. Об этом и поговорим далее.
Представим, что у нас есть девять объектов, которые как-то распределены по плоскости. Для удобства будем считать, что здесь у нас только одно измерение и все наши девять объектов распределены вдоль одной прямой.
Здесь, очевидно, можно выделить три кластера, в каждом из которых по три объекта. Выделим эти кластеры цветом на изображении ниже.
Теперь давайте запустим кластеризацию по алгоритму k-средних. Для начала выберем количество кластеров. Как мы уже убедились ранее, оптимальным количеством кластеров будет три.
Для определения оптимального количества кластеров есть и более надёжный метод, но мы о нём поговорим немного позже.
Переходим ко второму шагу алгоритма k-средних: случайным образом определить 3 центроида. Пусть первый центроид (зелёный) будет между 1 и 2 объектом, второй (оранжевый) – между 3 и 4, а третий (синий) – между 5 и 6.
Уже можно заметить проблему: первые два центроида попали в зону первого кластера, а в зоне третьего кластера не оказалось ни одного центроида. Но мы продолжаем работать по алгоритму.
На третьем шаге мы подсчитываем расстояние от точки 1 до каждого центроида.
На следующем шаге нам необходимо определить точку 1 к ближайшему кластеру. Ближайшим к ней будет зелёный кластер. Далее проделываем аналогичные операции с каждой точкой: вычисляем расстояние до каждого центроида и определяем её к ближайшему.
В итоге получаем такую картину.
То есть к первому кластеру будут отнесены точки 1 и 2, ко второму – только точка 3, а все остальные точки будут отнесены к третьему кластеру.
С точки зрения алгоритма – он отработал правильно, все точки отнесены к ближайшему центроиду. Вот только такой результат не отражает реальной структуры данных. Одна группа разделена надвое, другая объединена с лишними точками. Визуально видно: границы кластеров неестественные, и распределение не имеет смысла.
Как быть в такой ситуации? Здесь на помощь приходит математика. Чтобы формально оценить качество кластеризации, используется метрика под названием «сумма квадратов внутрикластерных расстояний» — по-английски SSE (Sum of Squared Errors).
Принцип работы этой метрики простой:
- Для каждой точки считаем, насколько далеко она находится от центра своего кластера
- Возводим это расстояние в квадрат (чтобы усилить вклад дальних точек)
- Складываем все эти значения по всем точкам
Чем меньше SSE, тем компактнее и логичнее кластеры.
В нашем примере из-за неудачного выбора центров SSE будет больше, чем если бы центры были выбраны правильно. Это сигнал, что алгоритм дал неоптимальный результат.
Визуально представить сколько вариации вносит каждая точка в кластере можно с помощью такой цветной полосы под нашими точками с данными.
Чем длиннее полоска одного цвета — тем больше вклад точек этого цвета в SSE. Используя такую визуализацию, мы можем оценить, какие точки находятся далеко от центра и портят качество кластеризации (здесь такими являются синие точки).
Давайте теперь сравним полученную кластеризацию с «идеальной». Допустим, в этот раз центроиды расположились более удачным образом: первый находится между точками 1 и 2, второй – рядом с точкой 4, а третий – между 8 и 9 точками.
Снова визуализируем вариации каждой точки в кластерах.
Теперь распределение вариаций более равномерное, следовательно, качество кластеризации стало куда лучше по сравнению с прошлым вариантом.
Но качество кластеризации выражается не только в распределении этих цветных полос, но и в их длине. То есть задача алгоритма — минимизировать длину всех этих полос, т.е. «стянуть» все точки ближе к своим центрам.
Ниже представлено сравнение нескольких запусков алгоритма k-средних с одинаковыми данными, но разными начальными положениями центроидов (третья попытка у нас осталась «за кадром»).
Как видно на этом изображении минимальная длина полосы, следовательно, и сумма квадратов внутрикластерных расстояний, получилась именно во второй попытке.
Выбор количества кластеров
После того как мы разобрались, как работает алгоритм k-средних, и увидели, что результат может зависеть от стартовых условий, возникает ещё один важный вопрос: «сколько кластеров выбрать?».
Алгоритм k-средних требует, чтобы мы заранее указали число кластеров k. Но в реальной жизни мы редко знаем точное количество групп заранее. И если выбрать его неправильно, результат может быть либо слишком грубым (слияние разных групп в одну), либо слишком раздробленным (деление одной группы на части).
Мы уже ранее ввели метрику суммы квадратов внутрикластерных расстояний (SSE). Она же и будет ключом к решению проблемы с выбором количества кластеров.
Начнём с простого вопроса: «что будет с метрикой SSE при увеличении числа кластеров?».
Логично предположить, что она будет уменьшаться. Это происходит потому, что чем больше кластеров — тем меньше точек в каждом кластере, и тем ближе каждая точка к своему центру.
В пределе, если сделать количество кластеров равным числу точек, то SSE станет нулевой: каждая точка будет своим собственным кластером. Но это, очевидно, бессмысленно — цель же не в том, чтобы делить до абсурда, а чтобы найти оптимальное число групп.
Давайте визуализируем разделение наших данных на разное количество кластеров – от 1 до 4.
Очевидно, что при количестве кластеров, равном единице, мы получим худший вариант с самой большой метрикой SSE. С увеличением количества кластеров уменьшается и сумма квадратов внутрикластерных расстояний.
Но это происходит не линейно. Давайте сравним между собой эти суммы для разного количества кластеров.
Для большей наглядности перевернём эти линии и построим из них график, соединив вершины каждой линии.
В итоге получаем падающую кривую. В начале SSE убывает резко — добавление кластеров существенно улучшает качество.
Но в какой-то момент кривая «замедляется» — добавление новых кластеров даёт всё меньше и меньше пользы. Этот момент, где кривая резко меняет угол — называют «локтем».
Именно значение количества кластеров, на котором находится «локоть», и будет считаться оптимальным.
А такой визуальный способ определить оптимальное количество кластеров при использовании алгоритма k-средних называется «метод локтя».
Данный метод опирается на простую идею: вначале, когда кластеры только начинают формироваться, каждый новый кластер значительно снижает ошибку, потому что разносит разные группы.
Но после определённого момента (локтя), добавление новых кластеров только слегка «шлифует» уже и так хорошие группы.
Таким образом, метод локтя помогает найти баланс между качеством разбиения и сложностью модели. Мы не просто уменьшаем ошибку, а делаем это оптимально, избегая переобучения и лишней детализации.
Метод локтя хорошо работает, если:
- Кластеры в данных реально существуют
- Они разделены и имеют похожую плотность
- Вы можете построить график и увидеть характерный «излом»
Он не сработает, если:
- Структура данных размыта
- Кластеры неустойчивы или сильно перекрываются
- SSE убывает плавно и без чёткой точки перегиба
В таких случаях лучше использовать дополнительные методы оценки, например, коэффициент силуэта или аналитику по смыслам кластеров.
Реализация k-средних на Python
Итак, мы познакомились с работой алгоритма k-средних, теперь пришло время реализовать его на Python. Начнём мы с простого: воспользуемся уже готовыми функциями из библиотеки scikit-learn.
Быстрая реализация через scikit-learn
Представим, что у нас есть 300 точек. Каждая точка — это, например, человек, описанный двумя характеристиками: допустим, «доход» и «возраст». Мы создаём их случайно так, чтобы они изначально образовали 4 логичные группы, но алгоритм этого не знает.
Для этого в Python можно использовать функцию make_blobs() из библиотеки scikit-learn. Подробно останавливаться на каждой используемой функции и её параметрах мы не будем. Цель этой статьи – показать работу самого алгоритма k-means, а не сторонних функций.
from sklearn.datasets import make_blobs
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.66, random_state=16)
Давайте сразу визуализируем эти точки с помощью библиотеки matplotlib.
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.66, random_state=16)
plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1], s=40)
plt.show()
Получаем такой график (он называется точечной диаграммой или диаграммой рассеяния).
Хоть мы и понимаем, что здесь именно 4 кластера, давайте все же применим метод локтя и убедимся в наших суждениях.
Для этого надо запустить алгоритм k-средних с разным количеством кластеров от 1 до 9 и для каждого случая подсчитать сумму квадратов расстояний до центров кластеров (сумму квадратов внутрикластерных расстояний / SSE).
В коде это будет выглядеть так (код мы полностью переписываем, заменяя предыдущий):
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.66, random_state=16)
sse = []
for k in range(1, 10):
kmeans = KMeans(n_clusters=k, random_state=42)
kmeans.fit(X)
sse.append(kmeans.inertia_)
plt.figure(figsize=(10, 6))
plt.plot(k_range, sse, marker='o')
plt.title("Метод локтя")
plt.xlabel("Количество кластеров (k)")
plt.ylabel("Сумма квадратов внутрикластерных расстояний")
plt.grid(True)
plt.show()
В библиотеке scikit-learn алгоритм k-средних реализован в классе KMeans (в качестве модели машинного обучения). Для того чтобы запустить его, нужно «обучить» модель. Для этого у объекта kmeans класса KMeans необходимо вызвать метод fit(). Это стандартная практика работы с моделями scikit-learn.
Сумму квадратов внутрикластерных расстояний получаем, вызвав метод inertia_() у объекта kmeans.
После того как алгоритм k-средних отработает с количеством кластеров от 1 до 10 и нужные нам метрики окажутся в списке sse, мы строим график зависимости SSE от количества кластеров.
График получается следующим:
На этом графике мы видим ломаную линию, которая резко убывает в начале, а потом «выравнивается». В точке, где это выравнивание происходит, и находится тот самый «локоть» — в нашем случае это k = 4. То есть оптимальное количество кластеров здесь – 4, как мы и хотели.
Теперь запускаем алгоритм k-средних с параметром k (количество кластеров) равным четырём.
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.66, random_state=16)
kmeans = KMeans(n_clusters=4, random_state=42)
clusters = kmeans.fit_predict(X)
centers = kmeans.cluster_centers_
# Визуализируем результат
plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis', s=30)
plt.scatter(centers[:, 0], centers[:, 1], c='red', s=200, alpha=0.75, marker='X', label='Центроиды')
plt.title("Результат кластеризации")
plt.xlabel("Признак 1")
plt.ylabel("Признак 2")
plt.legend()
plt.grid(True)
plt.show()
Здесь метод fit_predict() обучает модель и сразу возвращает список меток: к какому кластеру относится каждая точка. А с помощью метода cluster_centers_() мы получаем координаты центроида каждого кластера.
Далее просто строим точечную диаграмму (диаграмму рассеяния) аналогичную той, что мы построили в начале, только теперь точки раскрашены в цвет своего кластера, а также отмечены центроиды каждого кластера.
В конце оценим проделанную работу: выведем коэффициент силуэта для этой кластеризации.
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.66, random_state=16)
kmeans = KMeans(n_clusters=4, random_state=42)
clusters = kmeans.fit_predict(X)
centers = kmeans.cluster_centers_
# Коэффициент силуэта
sil_score = silhouette_score(X, clusters)
print(sil_score)
В нашем случае коэффициент силуэта равен 0,75, что является отличным показателем.
Ручная реализация
Мы довольно быстро и сумбурно прошлись по уже готовой реализации алгоритма k-средних из библиотеки scikit-learn. Разобраться в её работе совсем не сложно, но наша цель более глобальная – научиться самостоятельно составлять программу на Python для кластеризации данных алгоритмом k-средних.
Да, в реальных задачах лучше пользоваться готовыми и проверенными решениями. Но для понимания основ работы любого алгоритма не обойтись без написания его «с нуля».
Далее мы будем писать код в уже привычном формате, описывая каждый блок отдельно.
Сначала импортируем все нужные модули и библиотеки:
import random
import matplotlib.pyplot as plt
import numpy as np
from sklearn.datasets import make_blobs
На практике вам понадобится лишь один модуль из всех этих – random. Остальные нужны будут лишь для генерации данных и визуализации итогов нашей кластеризации.
Для чистоты эксперимента работать будем все с теми же данными, полученными после работы функции make_blobs(). Только теперь их нужно привести к стандартному типу данных – списку. Для этого воспользуемся методом tolist() из модуля numpy.
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.66, random_state=16)
data = X.tolist()
В переменной data теперь у нас будет храниться список списков, в каждом из которых находятся два элемента – координаты точки на плоскости.
Теперь перейдём к самому алгоритму. Нам необходимо измерять расстояния между точкой и центроидом. Иными словами, с точки зрения геометрии, мы измеряем расстояние между двумя точками – называется оно евклидовым расстоянием. Вычисляется евклидово расстояние по знакомой всем теореме Пифагора.
То есть расстояние между точкой А(x1, y1) и B(x2, y2) будет вычисляться по формуле:
В Python это можно реализовать с помощью такой функции:
def euclidean_distance(a, b):
return ((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2) ** 0.5
Аналогичного результата можно добиться, используя функцию dist() из встроенного модуля math.
Следующим шагом будет создание функции для назначения точек ближайшему кластеру. Назовем эту функцию assign_clusters(), принимать она будет два аргумента: список с координатами всех точек (список data) и список с координатами центроидов (centres).
Суть этой функции простая: мы перебираем в цикле каждую точку из data, считаем для неё расстояния до каждого центроида и выбираем минимальное. В отдельном списке labels храним метки кластера для каждой точки.
В коде это выглядит следующим образом:
def assign_clusters(data, centers):
labels = []
for point in data:
distances = [euclidean_distance(point, center) for center in centers]
min_index = distances.index(min(distances))
labels.append(min_index)
return labels
Дальнейший шаг будет немного сложнее. Когда мы только начинаем кластеризацию, центроиды кластеров выбираются случайно.
Но после того, как точки уже распределились по своим кластерам, надо передвинуть центроиды туда, где действительно «середина» группы.
Напишем функцию update_centers(), которая принимает следующие аргументы:
- data — список всех точек
- labels — список меток кластеров для каждой точки
- k — сколько всего у нас кластеров
Задача этой функции в том, чтобы посмотреть на все точки, которые попали в каждый кластер, и вычислить их среднее положение — новое место для центроида. Для начала мы создаём пустой список new_centres, в котором будут храниться новые координаты для каждого центроида.
def update_centers(data, labels, k):
new_centers = []
Далее проходимся в цикле for по всем кластерам от 0 до k-1 и находим все точки, которые попали в этот кластер.
for cluster_label in range(k):
cluster_points = [point for point, label in zip(data, labels) if label == cluster_label]
Иногда случается, что в какой-то кластер не попала ни одна точка (например, потому, что начальный центр был в пустом месте, слишком далеко от точек кластера). Поэтому проверяем, что список cluster_point не пустой и находим среднее значение координат:
if cluster_points:
x_coords = [p[0] for p in cluster_points]
y_coords = [p[1] for p in cluster_points]
new_center = [sum(x_coords) / len(x_coords), sum(y_coords) / len(y_coords)]
Здесь мы берём отдельно все координаты по каждой оси, считаем их сумму и делим на количество точек. Таким образом, получаем среднюю координату по X и по Y. Это и есть новое место для центра кластера — там, где середина всех его точек.
Если все же текущий кластер пустой, то выбираем новую точку из списка data случайным образом:
else:
new_center = random.choice(data)
В конце добавляем в список new_centres координаты новых центров и возвращаем его из функции. Вся функция выглядит так:
def update_centers(data, labels, k):
new_centers = []
for cluster_label in range(k):
cluster_points = [point for point, label in zip(data, labels) if label == cluster_label]
if cluster_points:
x_coords = [p[0] for p in cluster_points]
y_coords = [p[1] for p in cluster_points]
new_center = [sum(x_coords) / len(x_coords), sum(y_coords) / len(y_coords)]
else:
new_center = random.choice(data)
new_centers.append(new_center)
return new_centers
Мы на финишной прямой – осталось лишь написать функцию с основным циклом k-средних, в которой будет:
- Случайным образом определяться центроиды для каждого кластера
- Каждой точке назначаться метка её кластера (вызов функции assign_clusters())
- Пересчитываться координаты центроидов (вызов функции update_centers())
- Определяться, на сколько сдвинулись координаты центроидов
- Если координаты центроидов смещаются больше какой-то заданной величины, то пункты 2-4 будут повторяться снова
Если величина смещения меньше заданной, то работа функции завершается, возвращаются метки точек и координаты центроидов
Здесь важно определить минимальную величину смещения центроидов, после достижения которой работа алгоритма будет останавливаться. Для этого введём переменную tol (от английского tolerance — «допуск», «терпимость»), которая задаёт насколько маленьким должно быть смещение центроидов.
Для нашей задачи можно присвоить ей значение 0,0001 (1e-4). То есть если суммарные смещения всех центроидов меньше 0,0001, мы решаем, что алгоритм закончил работу.
На практике же часто используют значения 1e-3, 1e-4 или 1e-5 в зависимости от задач. Все зависит от требуемой точности вашего алгоритма. Чем значение больше, тем быстрее, но менее точно, работает программа.
Код последней функции будет несложным – вызываем все описанные ранее функции и измеряем суммарное смещение центроидов. Выглядит эта функция так:
def k_means(data, k, max_iters=100, tol=1e-4):
centers = random.sample(data, k)
for _ in range(max_iters):
labels = assign_clusters(data, centers)
new_centers = update_centers(data, labels, k)
shift = sum(euclidean_distance(c1, c2) for c1, c2 in zip(centers, new_centers))
if shift < tol:
break
centers = new_centers
return labels, centers
Осталось запустить нашу функцию, передав в неё список data и количество кластеров (в нашем случае – 4)
labels, centers = k_means(data, 4)
Для визуализации результатов кластеризации построим точечную диаграмму, на которой каждая точка будет окрашена в цвет своего кластера и отмечены центроиды.
colors = ['blue', 'green', 'orange', 'purple']
plt.figure(figsize=(10, 6))
for idx, point in enumerate(data):
plt.scatter(point[0], point[1], c=colors[labels[idx]], s=30)
for center in centers:
plt.scatter(center[0], center[1], color='red', s=200, alpha=0.75, marker='X')
plt.title("Результат кластеризации")
plt.xlabel("Признак 1")
plt.ylabel("Признак 2")
plt.grid(True)
plt.show()
В результате получаем такое изображение, практически идентичное тому, что было получено с использованием готового алгоритма k-средних из библиотеки scikit-learn:
Давайте вычислим коэффициент силуэта для нашего самописного алгоритма k-средних. Для этого воспользуемся все той же функцией silhouette_score из scikit-learn.
X_float = [tuple(p) for p in data]
sil_score = silhouette_score(data, labels)
print(sil_score)
В результате получаем все то же значение 0,75. Это значит, что мы успешно справились с задачей и самостоятельно реализовали кластеризацию алгоритмом k-средних!
Итак, полный код самого алгоритма k-средних без визуализации и генерации данных будет таким:
import random
# Функция вычисления евклидова расстояния
def euclidean_distance(a, b):
return ((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2) ** 0.5
# Шаг 2. Распределение точек по кластерам
def assign_clusters(data, centers):
labels = []
for point in data:
distances = [euclidean_distance(point, center) for center in centers]
min_index = distances.index(min(distances))
labels.append(min_index)
return labels
# Шаг 3. Пересчёт центров кластеров
def update_centers(data, labels, k):
new_centers = []
for cluster_label in range(k):
cluster_points = [point for point, label in zip(data, labels) if label == cluster_label]
if cluster_points:
x_coords = [p[0] for p in cluster_points]
y_coords = [p[1] for p in cluster_points]
new_center = [sum(x_coords) / len(x_coords), sum(y_coords) / len(y_coords)]
else:
new_center = random.choice(data)
new_centers.append(new_center)
return new_centers
# Шаг 4. Основной цикл k-средних (Проверка на сходимость)
def k_means(data, k, max_iters=100, tol=1e-4):
# Шаг 1. Инициализация центроидов
centers = random.sample(data, k)
for _ in range(max_iters):
labels = assign_clusters(data, centers)
new_centers = update_centers(data, labels, k)
shift = sum(euclidean_distance(c1, c2) for c1, c2 in zip(centers, new_centers))
if shift < tol:
break
centers = new_centers
return labels, centers
# Запуск
labels, centers = k_means(data, 4)
В таблице ниже представлено соответствие каждого шага алгоритма k-средних и наших функций.
Итоги
В этой статье мы подробно разобрали один из самых популярных алгоритмов кластеризации — k-средних. Мы узнали, как он шаг за шагом разбивает данные на кластеры, как выбираются и пересчитываются центроиды кластеров, как выбор числа кластеров влияет на результат и как оценивать качество кластеризации с помощью метрик.
Также мы реализовали алгоритм двумя способами — через готовую библиотеку scikit-learn и вручную, на чистом Python, чтобы лучше понять, как он работает внутри.
Тем не менее важно помнить, что:
- k-средних чувствителен к начальному положению центров. Если они выбраны неудачно, результат может быть далёк от оптимального.
- Поэтому в реальной практике принято запускать алгоритм несколько раз с разными начальными условиями и выбирать лучшее разбиение.
- Также стоит обратить внимание, что k-средних не справляется с выбросами и предполагает, что кластеры имеют примерно одинаковую форму и плотность.
В следующей статье мы как раз и рассмотрим такой случай: познакомимся с алгоритмом кластеризации DBSCAN, который не требует заранее указывать количество кластеров, умеет находить кластеры любой формы и автоматически распознаёт выбросы.
Он работает совсем иначе — на основе плотности точек, и это делает его мощным инструментом в задачах, где алгоритм k-средних не справляется.