Описание алгоритма кластеризации из книги Advanced Algorithms and Data Structures Final Release 2021 by Marcello La Rocca

Page 418, Section 12.3 DBSCAN

Описание DBSCAN было опубликовано в 1996г представляя новый подход к решению проблемы. Название является аббревиатиурой "Кластеризация на основе плотности расположения объектов". Главное его отличие от K-Means уже заложено в названии. K-means основан на центроидах которые строят кластеры в виде выпуклых множеств вокруг точек выбранных в качестве центроидов. Плотностный алгоритм DBSCAN определяет кластера как множество точек что близко расположеных друг к другу. Достаточно близко что бы плотность точек (количество) в любом кластере была выше определенного порога.

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

Так как и K-Means, DBSCAN - это плоский алгоритм жесткой кластеризации, имеется ввиду что каждая точка принадлежит (в большинстве) одному кластеру (или не принадлежит кластеру для шума). С 100% верятностью все кластеры являются объектами на одном и том же уровне, без иерархии в группах.

В K-Means, центроиды инициализированные случайным образом играют важную роль в алгоритме (с хорошей скоростью сходимости) настолько что случайные перезапуски сравниваются перед выбором наилучшей клакстеризации. Это не относится к алгоритму DBSCAN, где точки прокручиваются циклично в некотором роде случайным образом. Но это действие влияет в меньшей степени на результат. Следовательно этот алгоритм можест считатся детерминированным.

DBSCAN в итоге расширяет концепцию "одноканальной кластеризации" (single-linkage clustering) путем введения минимальной плотности точек, требующих наличия двух точек соединяющих друг друга. Это снижает эффект однозвенной цепи (наихудший побочный эффект этого алгоритма). Вызывая независимые кластеры соединенные тонкой линией (точек шума) ошибочно классифицированные как единый кластер.