DBSCAN: кластеризация по плотности

🎯 Зачем это нужно?

Представь ситуации из жизни:

🍕 Доставка еды: Delivery Club группирует заказы по районам - не по расстоянию от центра, а там, где много заказов рядом друг с другом

📱 Обнаружение аномалий: Банки ловят мошенников - нормальные транзакции “кучкуются”, а подозрительные торчат отдельно

🎵 Spotify рекомендации: Алгоритм находит “плотные скопления” похожих треков, игнорируя музыкальные “выбросы”

В отличие от k-means, DBSCAN не требует заранее знать количество кластеров и отлично находит выбросы!

📚 История вопроса

DBSCAN придумали в 1996 году немецкие учёные Мартин Эстер и его команда. Название расшифровывается как “Density-Based Spatial Clustering of Applications with Noise” - звучит страшно, но суть простая: “группируй по плотности и игнорируй шум” 🤓

Интересный факт: алгоритм создавали для географических данных, но теперь он используется везде - от анализа ДТП до поиска сообществ в соцсетях!

💡 Интуиция

Представь вечеринку в большом зале 🎉. Люди естественно собираются в группы:

• Плотные группы = кластеры (компании друзей)
• Одиночки между группами = шум/выбросы
• Люди на краю групп = граничные точки

DBSCAN работает так же: ищет “плотные районы” точек и игнорирует одиночек.

[МЕДИА: image_01] Описание: Визуализация концепции DBSCAN через аналогию с вечеринкой Промпт: “educational illustration showing party scene from above, people clustered in groups, some isolated individuals, colorful visualization representing DBSCAN clustering concept, modern flat design”

Ключевые идеи:

• Если вокруг точки много соседей (≥ minPts) в радиусе ε → это ядро кластера
• Точки рядом с ядром → граничные точки кластера
• Одиночки → шум

📐 Формальное определение

Параметры:

• ε (epsilon) - радиус поиска соседей
• minPts - минимальное количество точек для формирования кластера

Типы точек:

• Core point (ядерная): имеет ≥ minPts соседей в радиусе ε
• Border point (граничная): не ядерная, но находится в ε-окрестности ядерной
• Noise point (шум): не ядерная и не граничная

Алгоритм:

1. Для каждой точки найти ε-соседей
2. Если соседей ≥ minPts → точка ядерная
3. Объединить ядерные точки в кластеры (если они ε-достижимы)
4. Добавить граничные точки к кластерам
5. Оставшиеся точки = шум

[МЕДИА: image_02] Описание: Диаграмма типов точек в DBSCAN с примерами ε-окрестностей Промпт: “technical diagram showing DBSCAN point types, core points with epsilon neighborhoods, border points, noise points, circles showing radius epsilon, mathematical visualization, clean educational style”

🔍 Примеры с разбором

Пример 1: Простой случай

Данные: точки (1,1), (1,2), (2,1), (2,2), (8,8), (8,9), (15,15) Параметры: ε = 2, minPts = 2

Шаг 1: Найдем соседей для каждой точки в радиусе ε = 2

• (1,1): соседи (1,2), (2,1), (2,2) → 3 соседа ≥ 2 → ядерная
• (1,2): соседи (1,1), (2,1), (2,2) → 3 соседа → ядерная
• (2,1): соседи (1,1), (1,2), (2,2) → 3 соседа → ядерная
• (2,2): соседи (1,1), (1,2), (2,1) → 3 соседа → ядерная
• (8,8): сосед только (8,9) → 1 сосед < 2 → проверим дальше
• (8,9): сосед только (8,8) → 1 сосед < 2 → проверим дальше
• (15,15): соседей нет → шум

Шаг 2: (8,8) и (8,9) не ядерные, но они соседи друг друга. Поскольку ни одна не ядерная, обе становятся шумом.

Результат:

• Кластер 1: (1,1), (1,2), (2,1), (2,2)
• Шум: (8,8), (8,9), (15,15)

Пример 2: С кодом

from sklearn.cluster import DBSCAN
import numpy as np

# Данные: координаты кафе в городе
cafes = np.array([
    [1, 1], [1, 2], [2, 1],     # Центр города
    [8, 8], [8, 9], [9, 8],     # Спальный район  
    [15, 15]                     # Окраина
])

# Кластеризация
dbscan = DBSCAN(eps=2, min_samples=2)
clusters = dbscan.fit_predict(cafes)

print(clusters)  # [-1 означает шум]
# Результат: [0, 0, 0, 1, 1, 1, -1]

Кластер 0: центр города, кластер 1: спальный район, -1: одинокое кафе на окраине.

🎮 Практика

Базовый уровень 🟢

Задача 1: Даны точки: (0,0), (1,0), (0,1), (10,10). При ε=2, minPts=2 определи тип каждой точки.

Задача 2: Объясни, почему при ε=1, minPts=3 точка (5,5) с соседями (5,6), (6,5) будет шумом?

Задача 3: В каких ситуациях DBSCAN лучше k-means? Приведи 2 примера.

Продвинутый уровень 🟡

Задача 4: Напиши псевдокод алгоритма поиска ε-соседей для точки.

Задача 5: Данные точки образуют букву “L”. Сколько кластеров найдет DBSCAN при подходящих параметрах? А k-means с k=1?

Задача 6: Реализуй функцию подсчета соседей:

def count_neighbors(point, data, eps):
    # Твой код здесь
    pass

Челлендж 🔴

Задача 7: Как выбрать оптимальные ε и minPts для реального датасета? Предложи метод.

Задача 8: DBSCAN нашел кластеры различной плотности. Как это повлияет на результат? Предложи модификацию алгоритма.

⚠️ Частые ошибки

❌ Ошибка: “DBSCAN всегда лучше k-means” ✅ Правильно: DBSCAN хорош для неравномерной плотности и выбросов, но медленнее на больших данных 💡 Почему: У каждого алгоритма свои сильные стороны

❌ Ошибка: “minPts = 2 всегда достаточно”
✅ Правильно: minPts зависит от размерности данных (рекомендуется minPts ≥ размерность + 1) 💡 Почему: В высоких размерностях нужно больше точек для определения плотности

❌ Ошибка: “ε подбираю случайно” ✅ Правильно: Используй k-distance график или анализ данных 💡 Почему: Неправильный ε может объединить все точки в один кластер или разбить на шум

🎓 Главное запомнить

✅ Суть: DBSCAN группирует точки по плотности, находит выбросы автоматически ✅ Параметры: ε (радиус), minPts (мин. количество соседей)
✅ Применение: Обнаружение аномалий, кластеры произвольной формы, неизвестное количество кластеров

🔗 Связь с другими темами

Откуда пришли: Из урока 321 знаем основы кластеризации и k-means - DBSCAN решает его ограничения

Куда ведет: Дальше изучим иерархическую кластеризацию и методы оценки качества кластеров. DBSCAN также основа для более сложных алгоритмов типа OPTICS