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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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