Алгоритм DBSCAN

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Статья написана с использованием LLM GPT-5.5 Thinking и проверена участником Eva Vallistu 14:11, 27 июня 2026 (MSD) Промпт приводится полностью в Обсуждение:Алгоритм кластеризации DBSCAN

Содержание

1 Основные понятия и определения
2 Алгоритм
3 Выбор параметров
4 Свойства
5 Реализация
6 См. также
7 Литература

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) — плотностный алгоритм кластеризации, предназначенный для выделения областей высокой плотности в метрическом пространстве и обнаружения объектов, не принадлежащих ни одному кластеру. Алгоритм относится к методам обучения без учителя и особенно полезен в задачах, где кластеры имеют произвольную форму, а число кластеров заранее неизвестно.

В отличие от K-means, DBSCAN не требует предварительно задавать число кластеров и не предполагает, что кластеры имеют выпуклую или сферическую форму. В отличие от многих вариантов иерархической кластеризации, алгоритм строит разбиение напрямую, используя локальную плотность точек. Существенной частью результата является явное выделение шума, то есть объектов, интерпретируемых как выбросы.

Основные понятия и определения

Пусть задано конечное множество объектов $X={x_1,\ldots,x_n}$ и метрика $\rho:X\times X\to \mathbb{R}_{\geq 0}$ . Алгоритм DBSCAN использует два параметра:

$\varepsilon>0$ — радиус окрестности;
$\operatorname{MinPts}\in\mathbb{N}$ — минимальное число точек в окрестности, необходимое для признания точки плотностной.

$\varepsilon$ -окрестностью точки $p\in X$ называется множество

$N_{\varepsilon}(p)={q\in X:\rho(p,q)\leq \varepsilon}.$

Точка $p$ называется ядровой точкой (core point), если

$|N_{\varepsilon}(p)|\geq \operatorname{MinPts}.$

Точка $q$ называется непосредственно плотностно достижимой из точки $p$ , если $p$ является ядровой точкой и

$q\in N_{\varepsilon}(p).$

Точка $q$ называется плотностно достижимой из точки $p$ , если существует последовательность точек

$p=p_0,p_1,\ldots,p_k=q,$

такая что каждая точка $p_{i+1}$ непосредственно плотностно достижима из $p_i$ .

Две точки $p$ и $q$ называются плотностно связными, если существует точка $o\in X$ , из которой обе точки $p$ и $q$ плотностно достижимы.

Кластером в DBSCAN называется максимальное непустое множество точек, плотностно связных между собой. Точки, не входящие ни в один кластер, считаются шумом.

В результате каждая точка множества $X$ получает один из трёх типов:

ядровая точка;
граничная точка, попадающая в окрестность некоторой ядровой точки, но сама не являющаяся ядровой;
шумовая точка.

Алгоритм

DBSCAN последовательно просматривает точки выборки. Если точка ещё не была посещена, строится её $\varepsilon$ -окрестность. Если в этой окрестности меньше чем $\operatorname{MinPts}$ точек, точка временно помечается как шум. Если условие плотности выполнено, из неё начинается расширение нового кластера.

Расширение кластера происходит за счёт итеративного добавления точек, непосредственно плотностно достижимых из уже найденных ядровых точек. Если среди соседей встречается ранее помеченная шумовая точка, она может быть переопределена как граничная точка текущего кластера.

Типичная схема алгоритма:

все точки помечаются как непосещённые;

выбирается непосещённая точка $p$ ;

вычисляется $N_{\varepsilon}(p)$ ;

если $|N_{\varepsilon}(p)|<\operatorname{MinPts}$ , точка помечается как шумовая;

иначе создаётся новый кластер, в который помещается $p$ ;

кластер расширяется всеми точками, плотностно достижимыми из $p$ ;

процесс повторяется, пока не будут посещены все точки.

В псевдокоде процедура расширения кластера может быть записана следующим образом:

$\operatorname{DBSCAN}(X,\varepsilon,\operatorname{MinPts})$

$C\leftarrow 0$
для каждой непосещённой точки :
- пометить $p$ как посещённую;
- найти $N_{\varepsilon}(p)$ ;
- если $|N_{\varepsilon}(p)|<\operatorname{MinPts}$ , пометить $p$ как шум;
- иначе $C\leftarrow C+1$ и расширить кластер $C$ из точки $p$ .

Корректность построения основана на том, что для фиксированных $\varepsilon$ и $\operatorname{MinPts}$ каждый кластер является максимальной компонентой плотностной связности.

Выбор параметров

Качество DBSCAN существенно зависит от выбора параметров $\varepsilon$ и $\operatorname{MinPts}$ .

Параметр $\operatorname{MinPts}$ задаёт минимальную локальную плотность. На практике его часто выбирают не меньше размерности пространства плюс единица:

$\operatorname{MinPts}\geq d+1,$

где $d$ — число признаков. Более крупные значения делают алгоритм устойчивее к шуму, но могут приводить к разбиению разреженных кластеров или их полному исчезновению.

Параметр $\varepsilon$ определяет пространственный масштаб кластеризации. Если $\varepsilon$ слишком мал, большинство точек будет помечено как шум. Если $\varepsilon$ слишком велик, несколько различных областей плотности могут слиться в один кластер.

Один из распространённых эвристических способов выбора $\varepsilon$ основан на графике расстояний до $k$ -го ближайшего соседа, где обычно

$k=\operatorname{MinPts}-1$

или $k=\operatorname{MinPts}$ , в зависимости от принятого соглашения о включении самой точки в окрестность. Для каждой точки вычисляется расстояние до $k$ -го ближайшего соседа, затем эти расстояния сортируются по возрастанию. Значение $\varepsilon$ выбирают в области излома графика.

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

$x'*{ij}=\frac{x*{ij}-\mu_j}{\sigma_j},$

где $\mu_j$ и $\sigma_j$ — среднее и стандартное отклонение $j$ -го признака.

Для данных с высокой размерностью выбор $\varepsilon$ становится менее устойчивым из-за концентрации расстояний. В таких случаях DBSCAN часто применяют после понижения размерности или используют альтернативные плотностные методы.

Свойства

DBSCAN обладает следующими преимуществами:

не требует заранее задавать число кластеров;
способен находить кластеры произвольной формы;
явно выделяет шумовые объекты;
использует только понятие расстояния и может применяться с различными метриками;
хорошо работает для пространственных данных и задач, где кластеры соответствуют областям высокой плотности.

Основные ограничения алгоритма:

чувствительность к выбору $\varepsilon$ и $\operatorname{MinPts}$ ;
трудности при наличии кластеров существенно различной плотности;
ухудшение качества в пространствах высокой размерности;
зависимость результата от выбранной метрики и масштабирования признаков;
возможная неоднозначность назначения граничных точек, достижимых из нескольких кластеров.

Временная сложность DBSCAN зависит от способа поиска соседей. При наивной реализации, когда для каждой точки расстояние вычисляется до всех остальных точек, сложность составляет

$O(n^2).$

При использовании пространственных индексов, таких как kd-деревья или R-деревья, для низкоразмерных данных средняя сложность может быть близка к

$O(n\log n).$

Однако в высокой размерности эффективность таких индексов снижается, и поведение алгоритма приближается к квадратичному.

Память в базовой реализации требуется для хранения данных, меток кластеров и служебных отметок посещения. Если заранее вычисляется полная матрица расстояний, объём памяти возрастает до

$O(n^2).$

Реализация

Ниже приведён пример применения DBSCAN на языке Python с использованием библиотеки scikit-learn.

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
 
X = np.array([
[0.0, 0.1],
[0.1, 0.0],
[0.2, 0.1],
[5.0, 5.1],
[5.1, 5.0],
[5.2, 5.1],
[10.0, 10.0]
])
 
X_scaled = StandardScaler().fit_transform(X)
 
model = DBSCAN(eps=0.5, min_samples=2, metric="euclidean")
labels = model.fit_predict(X_scaled)
 
print(labels)

В scikit-learn параметр eps соответствует $\varepsilon$ , а параметр min_samples соответствует $\operatorname{MinPts}$ . Метка -1 используется для шумовых точек.

Пример простой учебной реализации, не использующей пространственные индексы:

import numpy as np
 
def region_query(X, point_id, eps):
distances = np.linalg.norm(X - X[point_id], axis=1)
return np.where(distances <= eps)[0].tolist()
 
def expand_cluster(X, labels, visited, point_id, neighbors, cluster_id, eps, min_pts):
labels[point_id] = cluster_id
i = 0
 
```
while i < len(neighbors):
    q = neighbors[i]
 
    if not visited[q]:
        visited[q] = True
        q_neighbors = region_query(X, q, eps)
 
        if len(q_neighbors) >= min_pts:
            for r in q_neighbors:
                if r not in neighbors:
                    neighbors.append(r)
 
    if labels[q] == -1:
        labels[q] = cluster_id
 
    i += 1
```
 
def dbscan(X, eps, min_pts):
n = len(X)
labels = np.full(n, -1)
visited = np.zeros(n, dtype=bool)
cluster_id = 0
 
```
for point_id in range(n):
    if visited[point_id]:
        continue
 
    visited[point_id] = True
    neighbors = region_query(X, point_id, eps)
 
    if len(neighbors) < min_pts:
        labels[point_id] = -1
    else:
        expand_cluster(
            X, labels, visited, point_id,
            neighbors, cluster_id, eps, min_pts
        )
        cluster_id += 1
 
return labels
```

Данная реализация предназначена только для иллюстрации. В практических задачах для больших выборок используют реализации с оптимизированным поиском соседей, например на основе структур данных для метода ближайших соседей.

См. также

Литература

Ester M.; Kriegel H.-P.; Sander J.; Xu X. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise // Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. — 1996. — С. 226—231.

Schubert E.; Sander J.; Ester M.; Kriegel H.-P.; Xu X. DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN // ACM Transactions on Database Systems. — 2017. — Т. 42. — № 3. — С. 1—21.

Han J.; Kamber M.; Pei J. Data Mining: Concepts and Techniques. — 3. — Morgan Kaufmann, 2011.

Aggarwal C. C.; Reddy C. K. Data Clustering: Algorithms and Applications. — CRC Press, 2014.

Hastie T.; Tibshirani R.; Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2. — Springer, 2009.

Источник — «http://www.recognition.su/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_DBSCAN»

Категории: Кластеризация | Обучение без учителя | Алгоритмы машинного обучения

@@ Строка 213: / Строка 213: @@
 * [[Обучение без учителя]]
 * [[K-means]]
-* [[Иерархическая кластеризация]]
-* [[Метод ближайших соседей]]
-* [[Выброс]]
 * [[Метрика]]
-* [[Понижение размерности]]
 == Литература ==

Алгоритм DBSCAN

Материал из MachineLearning.

Текущая версия

Содержание

Основные понятия и определения

Алгоритм

Выбор параметров

Свойства

Реализация

См. также

Литература

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты