DBSCAN працює на основі ідеї щільнісної досяжності. Кластери визначаються як щільні області точок даних, розділені зонами з меншою щільністю. Його роботу регулюють два основні параметри:

• Епсилон (ε): радіус, у межах якого здійснюється пошук сусідніх точок;

• Мінімальна кількість точок (MinPts): мінімальна кількість точок, необхідна в межах ε-радіусу для формування щільної області (включаючи саму точку).

DBSCAN класифікує точки на три категорії:

• Ядрові точки: точка є ядровою, якщо в її ε-радіусі знаходиться не менше MinPts;

• Прикордонні точки: точка є прикордонною, якщо в її ε-радіусі менше MinPts, але вона досяжна з ядрової точки (тобто знаходиться в ε-радіусі ядрової точки);

• Шумові точки: точка, яка не є ні ядровою, ні прикордонною, вважається шумовою.

Алгоритм

1. Почати з довільної неперевіреної точки;

2. Знайти всі точки в її ε-радіусі;

3. Якщо точка має не менше MinPts сусідів у ε-радіусі, вона позначається як ядрова точка і ініціює новий кластер, який рекурсивно розширюється шляхом додавання всіх безпосередньо щільнісно досяжних точок;

4. Якщо кількість точок у ε-радіусі менша за MinPts, точка позначається як прикордонна точка (якщо вона знаходиться в ε-радіусі ядрової точки) або як шумова точка (якщо ні);

5. Повторювати кроки 1-4, доки всі точки не будуть перевірені.

Уявіть собі точкову діаграму даних. DBSCAN починає з вибору точки. Якщо знаходить достатньо сусідів у її ε-радіусі, позначає її як ядрову точку і починає формувати кластер. Далі цей кластер розширюється шляхом перевірки сусідів ядрової точки та їхніх сусідів і так далі. Точки, які знаходяться поруч із ядровою, але самі не мають достатньої кількості сусідів, позначаються як прикордонні точки. Ізольовані точки визначаються як шум.