Алгоритмы и структуры данных

DBSCAN — Кластеризация на основе плотности

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

Как работает DBSCAN
DBSCAN не опирается на сложные математические формулы — он использует два основных параметра:
Эпсилон (ε) — это радиус вокруг точки, в пределах которого алгоритм ищет ближайших соседей. Этот радиус называют "окрестностью".
Минимум точек (minPts) — минимальное количество точек в пределах радиуса ε, чтобы считать точку "основной".

Алгоритм выделяет три типа точек:
1) Основные точки — точки, вокруг которых находится не меньше minPts соседей в пределах радиуса ε. Они формируют "ядро" кластера.
2) Пограничные точки — точки, которые сами по себе не образуют кластер (меньше minPts соседей), но лежат в окрестности основной точки. Они как бы "пристегнуты" к кластеру.
3) Точки шума — точки, которые не принадлежат ни к одному кластеру и не попадают в окрестность основных точек. Это выбросы, которые игнорируются при построении кластеров.

www.tgoop.com/the_algorithms/4936

4.2K viewsApr 18 at 11:59

DBSCAN — Кластеризация на основе плотности

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

Как работает DBSCAN
DBSCAN не опирается на сложные математические формулы — он использует два основных параметра:
Эпсилон (ε) — это радиус вокруг точки, в пределах которого алгоритм ищет ближайших соседей. Этот радиус называют "окрестностью".
Минимум точек (minPts) — минимальное количество точек в пределах радиуса ε, чтобы считать точку "основной".

Алгоритм выделяет три типа точек:
1) Основные точки — точки, вокруг которых находится не меньше minPts соседей в пределах радиуса ε. Они формируют "ядро" кластера.
2) Пограничные точки — точки, которые сами по себе не образуют кластер (меньше minPts соседей), но лежат в окрестности основной точки. Они как бы "пристегнуты" к кластеру.
3) Точки шума — точки, которые не принадлежат ни к одному кластеру и не попадают в окрестность основных точек. Это выбросы, которые игнорируются при построении кластеров.

BY Алгоритмы и структуры данных