Навигация по странице
Алгоритм DBSCAN
В прошлой статье мы познакомились с алгоритмом кластеризации k-средних. Мы узнали, как алгоритм шаг за шагом разбивает данные на группы, как важен правильный выбор количества кластеров и начальных центроидов, и с какими ограничениями приходится сталкиваться при его использовании.
Однако на практике встречаются задачи, в которых k-средних работает не так хорошо. Например:
- Когда кластеры имеют сложную форму – не круглую и не симметричную
- Когда в данных много выбросов – точек, которые не принадлежат никакому кластеру
- Когда заранее неизвестно, сколько групп должно получиться
В таких случаях требуется более гибкий и устойчивый метод. Сегодня мы познакомимся с алгоритмом DBSCAN (Density-Based Spatial Clustering of Applications with Noise)— одним из самых популярных алгоритмов кластеризации, который справляется с задачами, где k-средних начинает ошибаться.
Мы разберём, как работает DBSCAN, на каких идеях он основан, как правильно подобрать его параметры, и в чём его сильные стороны по сравнению с другими методами. В конце статьи мы также попробуем применить алгоритм к реальным данным и оценим его работу на практике.
Работа алгоритма DBSCAN
Давайте разберём работу алгоритма DBSCAN на простом и понятном примере. Вспомните фитнес-клуб, о котором мы говорили ранее, в самой первой статье. Пусть у нас теперь есть не количество посещений и возраст каждого клиента, а его вес и рост.
Давайте нанесём все данные на график, где по одной оси будет рост, а по другой вес клиента.
Здесь уже распределение данных о клиенте не такое очевидное, как было раньше. Но нам все еще хочется выделить клиентов в группы, объединённые какими-то общими характеристиками.
На графике четко видны две группы людей: люди с весом около 85 килограмм и ростом около 175 в первой, и абсолютно разношёрстный набор людей во второй группе. Кроме этих групп на графике будет видно несколько единичных точек в стороне — это выбросы: люди с необычным соотношением роста и веса, которых не так просто отнести ни к одной из групп.
Давайте выделим каждую группу и выбросы своим цветом.
Примерно такую картину мы хотим получить при кластеризации. Что же, давайте попробуем применить к таким данным уже изученный алгоритм k-средних.
Если применить на этих данных алгоритм k-средних, он начнёт искать центроиды, равномерно делящие пространство.
Проблема в том, что:
- k-средних будет игнорировать плотность распределения точек
- Он всё равно заставит выбросы войти в какой-то кластер, даже если они расположены на большом удалении от кластера
- Он будет ориентироваться только на геометрию расстояний, а не на естественную плотность данных
В результате могут получиться странные границы: например, одна из плотных групп окажется разрезанной пополам только потому, что выбросы «перетянут» центр тяжести кластеров. Это можно увидеть на изображении ниже.
Нас такое не устраивает, значит, пришло время научиться применять алгоритм DBSCAN, который запросто справится с этой задачей. Он смотрит на данные по-другому, анализируя их плотность, то есть сколько точек находится рядом в пределах заданного радиуса.
Там, где точек много — возникает кластер. Там, где точек мало — остаётся пустота или шум.
Алгоритм не пытается подогнать данные под красивую геометрическую фигуру. Он идёт за реальным распределением клиентов в нашем фитнес-клубе.
Теперь давайте разберём, как именно DBSCAN будет действовать на этих данных.
Изначально все наши данные помечены как шум – то есть не относятся ни к какому кластеру, алгоритм их еще не рассматривал. Среди них выбирается случайная точка. Выделим её зелёным на изображении.
Теперь необходимо ввести первый из двух параметров, задаваемых алгоритму DBSCAN – минимальный радиус окружности, в которой будет идти поиск соседей (eps – «эпсилон»).
Собственно, про суть этого параметра мы уже сказали: вокруг выбранной точки строится окружность с радиусом eps (на изображении уже построена).
Далее алгоритм находит все точки, которые попадают внутрь этой окружности, включая саму точку.
И вводим второй параметр – минимальное количество соседей (minPts). Если в построенной окружности вокруг нашей точки соседних точек меньше, чем minPts, то эта точка помечается как шум (пока условно — возможно позже она станет граничной точкой, если будет рядом с кластером).
Если в окружности количество точек больше или равно minPts, то исходная точка отмечается как ядро кластера и вокруг неё будет создаваться первый кластер. На изображении ниже мы отметили ядро кластера и соседние точки (выделены фиолетовым).
Аналогично можно рассмотреть любую другую точку. Также определяется количество её соседей в окружности, если это количество больше заданного, то точка становится ядром.
Но вот если количество точек будет меньше заданного, то эта точка ядром не станет. Пока не будем спешить с новыми терминами и обзовём их «не ядро».
Далее давайте отметим все точки-ядра кластера (тёмно-серые). Среди них выберем одну и будем строить первый, зелёный, кластер.
Теперь все ядра объединяются в один кластер: от выбранной точки строится окружность, все ядра, входящие в эту окружность «расширяют» зелёный кластер.
Если в окружности крайних точек больше нет ядер, то выбирается любое другое ядро и от него строится второй кластер (оранжевый).
Что же теперь делать с серыми точками?
Все просто, те точки, которые не являются ядрами кластеров, но находятся в пределах окрестности ядер, также включаются в этот кластер. Такие точки называются граничными.
Добавляем все точки, граничащие с зелёными ядрами в первый кластер, а граничащие с оранжевыми – во второй.
Оставшиеся точки, которые не попадают ни в один кластер, так и остаются шумом. Также они могут называться «выбросами».
Готово, кластеризация наших данных алгоритмом DBSCAN завершена. Посмотреть анимированную визуализацию работы этого алгоритма вы можете по этой ссылке.
Отметим два основных момента, на основе которых алгоритм принимает решения:
- Много соседей в окрестности → точка – ядро нового или существующего кластера.
- Мало соседей → точка либо шум, либо граничная точка, если окажется рядом с кластером.
Для работы этого нужно задать два параметра:
- eps – минимальный радиус «соседства» точек
- minPts – минимальное количество точек (включая саму точку), которое должно находиться в eps-окрестности, чтобы точку можно было считать ядром кластера.
Далее мы поговорим о том, как же правильно определять эти параметры для корректной работы алгоритма DBSCAN.
Определение параметров eps и minPts
Одно из самых важных умений при работе с алгоритмом DBSCAN – это правильный подбор параметров eps и minPts. От них напрямую зависит, насколько хорошо алгоритм найдет кластеры в ваших данных.
Начнём с параметра minPts. Здесь всё достаточно просто. Есть общее правило: «значение minPts должно быть не меньше размерности пространства плюс один». То есть, если ваши данные двухмерные, как в нашем случае, minPts должно быть как минимум 3. Для трёхмерных данных — не меньше 4 и так далее.
Однако на практике обычно выбирают minPts немного больше – в пределах 5–10. Это позволяет алгоритму более надёжно определять плотные области.
Если поставить слишком маленькое значение, например, minPts = 2, алгоритм начнёт образовывать слишком много маленьких кластеров – фактически каждая пара близких точек будет считаться кластером. Если же значение будет слишком большим, есть риск потерять небольшие, но важные кластеры.
Выбор eps – более тонкая задача. Для этого есть понятный практический метод – построение графика k-ближайших расстояний.
Суть его в следующем: для каждой точки мы находим расстояние до её minPts-го ближайшего соседа (четвёртого, пятого и т.д. в зависимости от значения minPts), затем упорядочиваем все точки по этим расстояниям и строим график. По оси X идут номера точек, по оси Y – расстояния.
На таком графике обычно видно резкий перегиб: сначала расстояния между точками растут медленно, а затем резко увеличиваются. Этот момент перегиба и показывает, где заканчиваются плотные группы точек и начинаются выбросы.
Это аналогично использованию метода локтя для алгоритма k-средних, который мы разбирали в прошлой статье.
График этот мы построим немного позже, когда разберём реализацию алгоритма DBSCAN на Python.
Реализация DBSCAN на Python
Теперь, когда мы разобрались с теорией, давайте перейдём к практике и посмотрим, как можно применить алгоритм DBSCAN на реальных данных. Сначала будем использовать уже готовую реализацию этого алгоритма из библиотеки scikit-learn. А затем уже самостоятельно напишем алгоритм кластеризации на «чистом» Python без сторонних библиотек.
Быстрая реализация через scikit-learn
Для начала нам нужно импортировать все необходимые модули и библиотеки. Здесь нам понадобится сама scikit-learn, из которой импортируем класс DBSCAN, для визуализации будем пользоваться библиотекой matplotlib, а для генерации данных нам подойдёт встроенный модуль random.
import random
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
Для примера сгенерируем набор точек, сгруппированных в несколько плотных областей:
random.seed(42)
data = []
# Первая группа
for _ in range(50):
x = random.gauss(2, 0.4)
y = random.gauss(2, 0.4)
data.append([x, y])
# Вторая группа
for _ in range(50):
x = random.gauss(7, 0.5)
y = random.gauss(7, 0.5)
data.append([x, y])
# Третья группа
for _ in range(50):
x = random.gauss(2, 0.4)
y = random.gauss(7, 0.4)
data.append([x, y])
Напомним, что в этом цикле статей мы не рассматриваем подробно генерацию данных и использование сторонних библиотек. Основной фокус здесь на самих алгоритмах кластеризации!
Визуализируем наши данные до кластеризации:
plt.figure(figsize=(10, 6))
for point in data:
plt.scatter(point[0], point[1], color='gray', s=30)
plt.title("Исходные данные")
plt.xlabel("X")
plt.ylabel("Y")
plt.grid(True)
plt.show()
Получаем такую точечную диаграмму:
Для определения значения параметра eps давайте построим график k-ближайших расстояний. Воспользуемся классом NearestNeighbors из библиотеки scikit-learn.
from sklearn.neighbors import NearestNeighbors
# Строим модель ближайших соседей
neighbors = NearestNeighbors(n_neighbors=5) # 5 = minPts
neighbors_fit = neighbors.fit(data)
distances, indices = neighbors_fit.kneighbors(data)
# Берём расстояния до 5-го соседа (индекс 4, так как индексация с нуля)
k_distances = sorted(distances[:, 4])
# Строим график
plt.figure(figsize=(10, 6))
plt.plot(k_distances)
plt.title("График k-ближайших расстояний (k-distance plot)")
plt.xlabel("Индекс точки (отсортированный)")
plt.ylabel("Расстояние до 5-го соседа")
plt.grid(True)
plt.show()
Получаем такой график.
До примерно индекса 120 значения расстояний растут очень плавно – это плотные области (кластеры). Начиная примерно с индекса 130–135 – кривая резко идёт вверх. После этого расстояния до ближайших соседей начинают быстро увеличиваться – это выбросы и разреженные зоны.
Перелом явно виден в районе расстояния примерно 0,4–0,5. Следовательно, это значение лучше взять в качестве параметра eps.
Но в таком случае у нас будут выбросы. Мы же хотим для этого примера избежать наличия выбросов при кластеризации, поэтому возьмем eps немного больше – 0,65 (красная линия на графике).
Теперь применим DBSCAN к этим данным:
# Создаём объект DBSCAN
db = DBSCAN(eps=0.65, min_samples=5)
# Обучаем модель
labels = db.fit_predict(data)
Здесь мы передаём в конструктор класса DBSCAN следующие аргументы:
- eps=0.65 — радиус поиска соседей для каждой точки
- min_samples=5 — минимальное количество точек в окружности для создания кластера (ранее мы этот параметр называли minPts)
Метод fit_predict() строит кластеры и возвращает список меток (labels), в котором каждой точке присвоен номер её кластера. Если точка не попала ни в один кластер (шум), она получает метку -1.
Построим график, чтобы наглядно увидеть, как алгоритм разделил наши данные:
colors = ['blue', 'green', 'orange', 'purple', 'brown', 'red']
plt.figure(figsize=(10, 6))
for idx, point in enumerate(data):
if labels[idx] == -1:
plt.scatter(point[0], point[1], color='black', s=30) # выбросы черным
else:
plt.scatter(point[0], point[1], color=colors[labels[idx] % len(colors)], s=30)
plt.title("Результат кластеризации DBSCAN")
plt.xlabel("X")
plt.ylabel("Y")
plt.grid(True)
plt.show()
В результате получаем такую точечную диаграмму, на которой каждому кластеру присвоен свой цвет.
После того как мы применили алгоритм DBSCAN к данным, важно не просто посмотреть на результат глазами, но и формально оценить, насколько хорошо сработала кластеризация.
Для этого мы используем несколько метрик:
- Коэффициент силуэта
- Внутрикластерное расстояние
- Межкластерное расстояние
Коэффициент силуэта показывает, насколько хорошо каждая точка:
- Принадлежит своему кластеру
- И насколько далеко находится от других кластеров
Коэффициент принимает значения от -1 до 1:
- Ближе к 1 — кластеры хорошо разделены и компактны.
- Около 0 — кластеры перекрываются.
- Ниже 0 — точки ошибочно попали в чужой кластер.
Внутрикластерное расстояние – это среднее расстояние между точкой и центроидом её кластера.
Чем меньше это значение:
- Тем плотнее точки собраны вокруг центра кластера.
- Тем компактнее сами кластеры.
Межкластерное расстояние – это среднее расстояние между центроидами разных кластеров.
Чем больше это значение:
- Тем лучше кластеры отделены друг от друга.
- Тем проще алгоритму различать группы.
Теперь давайте вычислим эти метрики. Начнём с простого: коэффициент силуэта мы можем взять из той же библиотеки scikit-learn.
from sklearn.metrics import silhouette_score
sil_score = silhouette_score(data, labels)
print("Коэффициент силуэта:", round(sil_score, 2))
У нас получился коэффициент силуэта, примерно равный 0,84. Это очень хороший результат: кластеры чёткие, а точки внутри кластеров хорошо сгруппированы.
Для вычисления двух других метрик нам необходимо определить центры кластеров. Код для определения центра кластера мы уже писали ранее, в прошлой статье. Сейчас просто повторим его:
clusters = {}
for point, label in zip(data, labels):
if label not in clusters:
clusters[label] = []
clusters[label].append(point)
centroids = []
for points in clusters.values():
x_avg = sum(p[0] for p in points) / len(points)
y_avg = sum(p[1] for p in points) / len(points)
centroids.append((x_avg, y_avg))
Теперь нужно вычислить расстояния от каждой точки до центра. Писать собственную функцию для вычисления расстояния уже не будем – воспользуемся готовой euclidian() из библиотеки scipy. Код будет такой:
from scipy.spatial.distance import euclidean
# Внутрикластерное расстояние
intra_distances = []
for label, points in clusters.items():
center = centroids[label]
for point in points:
intra_distances.append(euclidean(point, center))
avg_intra_distance = sum(intra_distances) / len(intra_distances)
print("Внутрикластерное расстояние:", round(avg_intra_distance, 3))
В нашем случае среднее внутрикластерное расстояние равно 0,54. Это говорит о том, что точки внутри каждого кластера расположены очень близко друг к другу.
И последняя метрика – межкластерное расстояние. Здесь мы просто вычислим среднее расстояние между центроидами кластеров. В коде это выглядит так:
# Межкластерное расстояние
inter_distances = []
for i in range(len(centroids)):
for j in range(i + 1, len(centroids)):
inter_distances.append(euclidean(centroids[i], centroids[j]))
avg_inter_distance = sum(inter_distances) / len(inter_distances)
print("Межкластерное расстояние:", round(avg_inter_distance, 2))
На наших данных среднее межкластерное расстояние составило 5,76. Это свидетельствует о том, что кластеры сильно разделены в пространстве.
Анализ показал:
- Кластеры получились плотными и хорошо разделёнными.
- Алгоритм DBSCAN корректно выделил группы без предварительного указания их количества.
- Выбросы были правильно определены и оставлены без присвоения кластера.
Таким образом, можно сделать вывод, что качество кластеризации высокое, а выбранные параметры алгоритма eps=0.65 и min_samples=5 подошли для наших данных.
Ручная реализация
Теперь давайте попробуем написать алгоритм DBSCAN с нуля, на чистом Python.
Никаких готовых функций из библиотек мы использовать не будем – только базовый язык и простую логику.
Код с генерацией данных оставим прежним:
import random
random.seed(42)
data = []
# Первая группа
for _ in range(50):
x = random.gauss(2, 0.4)
y = random.gauss(2, 0.4)
data.append([x, y])
# Вторая группа
for _ in range(50):
x = random.gauss(7, 0.5)
y = random.gauss(7, 0.5)
data.append([x, y])
# Третья группа
for _ in range(50):
x = random.gauss(2, 0.4)
y = random.gauss(7, 0.4)
data.append([x, y])
Теперь переходим к реализации алгоритма DBSCAN. В этот раз мы напишем весь код в одной функции dbscan – это будет логичней и проще.
В прошлой статье мы высчитывали расстояния между точками с помощью самописной функции. Теперь же будем использовать готовую функцию dist() из модуля math.
Чтобы полностью реализовать DBSCAN, нам нужно пройти несколько шагов:
- Создать список меток (для каждой точки будем записывать, к какому кластеру она относится)
- Пройтись по каждой точке данных и определить её окружение (найти всех её соседей)
- Определить, является ли точка ядром кластера (если соседей достаточно) или шумом
- Если это ядро, то нужно создать новый кластер и расширять его через соседние точки, которые тоже могут быть ядрами
- Если точка является шумом, то пометить её как шум (-1)
Теперь рассмотрим все эти этапы в коде.
Сначала определим функцию:
from math import dist
def dbscan(data, eps, minPts):
n = len(data) # число точек
labels = [None] * n # создаём список меток для точек (None — не посещены)
cluster_id = 0 # текущий номер кластера
Здесь мы создали список меток labels, длина которого равна количеству точек. А поскольку изначально все точки не размечены, то заполняем его значениями None.
В переменной cluster_id будем хранить номер текущего кластера. Изначально у нас нет никаких кластеров, следовательно, присвоим этой переменной значение 0.
Теперь проходим по всем индексам наших точек. Обратите внимание, что мы работаем не с самими координатами точек, а только с их индексами!
В цикле for будем перебирать все индексы точек, если точка уже была размечена, то будем просто пропускать её.
for id in range(n):
if labels[id] is not None:
continue
Если точка еще не размечена (имеет метку None), то для неё будем искать всех соседей – точки, находящиеся на расстоянии не более eps. Выглядит это так:
neighbors = [j for j in range(n) if dist(data[id], data[j]) <= eps]
Здесь мы используем функцию dist из модуля math, которая вычисляет расстояние между двумя точками. В результате получаем список neighbors – всех соседей текущей точки.
Теперь решаем, является ли точка ядром кластера. Для этого количество её соседей должно быть больше или равно minPts. Если это не так, то сразу помечаем её как шум – присваиваем метку «-1» и переходим к следующей.
if len(neighbors) < minPts:
labels[id] = -1
continue
Если соседей достаточно, то это значит, что точка – ядро нового кластера:
cluster_id += 1 # создаём новый кластер
labels[id] = cluster_id # помечаем точку как ядро нового кластера
queue = neighbors # создаём очередь для расширения кластера
То есть мы увеличиваем номер кластера и записываем его в качестве метки текущей точки. Список соседей сохраняем в queue (от англ. «очередь»).
Теперь мы будем постепенно расширять наш новый кластер, перебирая всех соседей этой точки. Для этого воспользуемся циклом while:
while queue:
j = queue.pop()
Мы берём по одной точке из очереди соседей (queue.pop()) и проверяем её:
- если точка ещё не посещалась, помечаем её текущим кластером и снова ищем её соседей
- если у точки достаточно соседей, добавляем этих соседей в очередь для дальнейшего расширения кластера
В коде это можно записать так:
if labels[j] is None:
labels[j] = cluster_id
new_neighbors = [k for k in range(n) if dist(data[j], data[k]) <= eps]
if len(new_neighbors) >= minPts:
queue.extend(new_neighbors)
Если эта точка ранее была помечена как шум, но теперь оказалась соседней точкой ядра, мы также переводим её в текущий кластер (она становится граничной точкой):
elif labels[j] == -1:
labels[j] = cluster_id
На этом создание функции завершено, осталось лишь вернуть список labels. Итоговый код для кластеризации данных алгоритмом DBSCAN выглядит так:
from math import dist
def dbscan(data, eps, minPts):
n = len(data)
labels = [None] * n
cluster_id = 0
for id in range(n):
if labels[id] is not None:
continue
neighbors = [j for j in range(n) if dist(data[id], data[j]) <= eps]
if len(neighbors) < minPts:
labels[id] = -1
continue
cluster_id += 1
labels[id] = cluster_id
queue = neighbors
while queue:
j = queue.pop()
if labels[j] is None:
labels[j] = cluster_id
new_neighbors = [k for k in range(n) if dist(data[j], data[k]) <= eps]
if len(new_neighbors) >= minPts:
queue.extend(new_neighbors)
elif labels[j] == -1:
labels[j] = cluster_id
return labels
Теперь осталось лишь запустить нашу функцию с уже известными нам аргументами:
labels = dbscan(data, 0.65, 5)
Используем все тот же код для визуализации работы нашего алгоритма (только уберём строку про выбросы):
import matplotlib.pyplot as plt
colors = ['blue', 'green', 'orange']
plt.figure(figsize=(10, 6))
for idx, point in enumerate(data):
plt.scatter(point[0], point[1], c=colors[labels[idx] % len(colors)], s=30)
plt.title("Ручная реализация DBSCAN")
plt.xlabel("X")
plt.ylabel("Y")
plt.grid(True)
plt.show()
Получаем абсолютно такие же результаты кластеризации.
Итоги
В этой статье мы подробно разобрали алгоритм DBSCAN — один из самых эффективных и популярных алгоритмов кластеризации наравне с k-средних. Мы рассмотрели, как пошагово он объединяет данные в кластеры, опираясь на плотность распределения данных (точек).
Благодаря этому DBSCAN способен находить кластеры произвольной формы и уверенно определять выбросы.
Мы также реализовали алгоритм двумя способами: используя готовую библиотеку scikit-learn и вручную на чистом Python, чтобы лучше понять механизм его работы изнутри. Мы увидели, как ключевые параметры алгоритма — eps и minPts — влияют на итоговый результат, и научились грамотно их подбирать.
Важно помнить, что DBSCAN не требует заранее задавать количество кластеров и отлично справляется с выбросами, в отличие от k-средних. Однако он чувствителен к выбору параметров: неправильный подбор eps или minPts может привести к нежелательным результатам, например, к дроблению одного кластера на несколько мелких или, наоборот, к слиянию разных кластеров в один большой.
Поэтому в реальных задачах принято использовать вспомогательные методы, такие как построение графика k-ближайших расстояний, чтобы правильно определить значение eps. Также стоит учитывать, что хотя DBSCAN хорошо подходит для данных с произвольной формой и переменной плотностью, он плохо справляется с задачами, где плотности кластеров сильно различаются.
Теперь, вооружившись глубоким пониманием работы DBSCAN и навыками его реализации, вы сможете уверенно применять его для решения множества практических задач, где требуется надежная и понятная кластеризация данных.