DBSCAN

DBSCAN — алгоритм кластеризации, основанный на плотности точек.

Что делает алгоритм

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

Когда использовать

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

Например, его удобно использовать, если:

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

Основная идея

Кластер в DBSCAN — это не область вокруг центра, а группа точек, связанных через близких соседей.

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

Так кластер постепенно растёт, пока рядом остаются достаточно плотные участки данных.

Алгоритм DBSCAN по шагам

DBSCAN последовательно просматривает точки и строит кластеры из плотных областей.

1. Выбрать необработанную точку

Алгоритм берёт точку, которая ещё не была обработана.

2. Найти соседей

Для выбранной точки находятся все точки, расположенные на расстоянии не больше eps.

3. Проверить число соседей

Если соседей меньше, чем minSamples, точка не начинает новый кластер. Она временно считается шумовой.

Если соседей достаточно, начинается новый кластер.

4. Добавить соседей в кластер

Все найденные соседи добавляются в текущий кластер.

5. Расширять кластер

Для каждой добавленной точки снова проверяется её окрестность.

Если у этой точки тоже достаточно соседей, эти соседи добавляются в тот же кластер.

Если соседей мало, точка остаётся в кластере, но от неё кластер дальше не расширяется.

6. Перейти к следующей точке

Когда кластер больше не растёт, алгоритм выбирает следующую необработанную точку и повторяет процесс.

Результат. Плотные связанные области становятся кластерами, а точки, которые не удалось присоединить ни к одной такой области, остаются шумом.

Пример кластеризации

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

uses MLABC, PlotML;

begin
  var (X, trueLabels) := Datasets.MakeMoons(
    n := 400,
    noise := 0.08,
    seed := 42);

  var scaler := new StandardScaler;
  var Xscaled := scaler.FitTransform(X);

  var model := new DBSCAN(
    0.25,
    minSamples := 5);

  var labels := model.FitPredict(Xscaled);

  var (xs, ys) := Xscaled.Cols(0, 1);
  Plot.Points(xs, ys, labels, size := 6);
  Plot.Title := 'DBSCAN: кластеры сложной формы';
end.

Вывод и смысл результата

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

Чёрные точки — шумовые объекты. В этом примере их две: они не принадлежат ни к одному кластеру.

Важно: DBSCAN очень чувствителен к масштабу признаков. Вот та же модель без StandardScaler:

uses MLABC, PlotML;

begin
  var (X, trueLabels) := Datasets.MakeMoons(
    n := 400,
    noise := 0.08,
    seed := 42);

  var model := new DBSCAN(
    0.25,
    minSamples := 5);

  var labels := model.FitPredict(X);

  var (xs, ys) := X.Cols(0, 1);
  Plot.Points(xs, ys, labels, size := 6);
  Plot.Title := 'DBSCAN: кластеры сложной формы';
end.

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

Основные параметры

eps — радиус окрестности точки.

Если eps слишком маленький, многие точки могут стать шумовыми. Если слишком большой, разные кластеры могут слиться в один.

minSamples — минимальное число точек в окрестности радиуса eps, при котором точка может начать расширение кластера.

Чем больше minSamples, тем плотнее должна быть область, чтобы алгоритм счёл её частью кластера.

Чем отличается от KMeans

Алгоритм	Что нужно задать	Что хорошо находит
KMeans	число кластеров k	компактные группы вокруг центров
DBSCAN	eps и minSamples	плотные области сложной формы

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

Ограничения DBSCAN

• чувствителен к выбору eps;
• плохо работает, если кластеры имеют сильно разную плотность;
• зависит от масштаба признаков;
• на больших данных может работать дольше простых методов.

Что дальше

Для DBSCAN почти всегда стоит проверить масштабирование признаков.

Качество кластеризации можно оценивать с помощью Silhouette Score или, если известны правильные метки, через Adjusted Rand Index.