DBSCAN () — алгоритм кластеризації даних, який запропонували Мартін Естер (), , Йорґ Сандер () та Сяовей Су () у 1996 році. Він є алгоритмом кластеризації заснованим на щільності: для заданої множини точок у деякому просторі він відносить в одну групу точки, які розташовані найбільш щільно (точки з багатьма сусідами) та розмічає точки, які лежать в областях з невеликою щільністю (чиї сусіди розташовані занадто далеко) як викиди. DBSCAN є одним з найпоширеніших алгоритмів кластеризації, а також найбільш цитованим у науковій літературі. Найбільш цитовані статті по добуванню даних згідно з сервісом Microsoft академічного пошуку DBSCAN має рейтинг 24.
Більш рання версія
Роберт Ф. Лінг () у 1972 році опублікував статтю «Теорія і побудова k-кластерів» в журналі «» з дуже близькою оцінкою часової складністю виконання O(n³), тоді, як DBSCAN має у найгіршому випадку час виконання O(n²), і DBSCAN, сформульований у вигляді орієнтованому на запити діапазонів у базу даних, дозволяє прискорити індексування. Алгоритми також відрізняються в обробці точок розташованих на межі.
Попередні визначення Розглянемо множину точок в деякому просторі, яку будемо кластеризувати. Метою кластеризації процедурою DBSCAN є поділ точок на ядрові, (щільно-)досяжні та викиди, які визначаються так:
Точка є ядровою, якщо хоча б знаходяться на відстані (відстань є радіусом окола ) від неї, включно з . Кажуть, що ці точки безпосередньо досяжні з . Точка безпосередньо досяжна з , якщо точка знаходиться на відстані не більшій ніж від точки ядрової точки . Точка є досяжною з , якщо існує шлях з точок та , де кожна безпосередньо досяжна з (всі точки шляху повинні бути ядровими, можливо за виключенням ). Всі точки не досяжні з будь-якої іншої точки є викидами.
Отже, ядрова точка утворює «кластер» разом з усіма точками (не важливо ядрові чи ні) досяжними з неї. Кожен кластер містить принаймні одну ядрову точку. Не-ядрові точки можуть бути частиною кластера, тоді вони утворюють «ребро» кластера, оскільни з них не будуть досяжні інші точки.
Досяжність не є симметричним відношенням, бо, за визначенням, немає точок досяжних з не-ядрової точки (не-ядрова точка може бути досяжною, але відносно неї немає досяжних точок). Тому, поняття зв'язності потрібне для формального визначення степені кластеризації в DBSCAN. Дві точки та є щільно-зв'язними, якщо існує точка з якої вони є досяжними. Щільна-зв'язність є симетричною.
Тоді кластер має дві властивості: Всі точки кластера взаємно щільно-зв'язні. Якщо точка є щільно-зв'язно зв'язною з будь-якою точкою кластера, то вона так само належить кластеру.
Алгоритм
Початковий алгоритм на основі запитів до БД Алгоритму DBSCAN потрібні два параметри: ε (eps) і мінімальна кількість точок необхідних для утворення щільної області (minPts). Побудова починається з довільної точки, яка раніше не використовувалась. Виконується запит щодо точок з ε-околу, і, якщо там буде достатньо точок, то утворюється кластер. Інакше, точка маркується як шумова. Зауважимо, що ця точка може бути знайдена пізніше в достатньо великому ε-околі іншої точки і належати кластеру, а не бути шумовою.
Якщо точка знаходиться у щільній частині кластера, то і її ε-окіл також буде частиною цього кластера. Отже, всі точки ε-околу також будуть додані у кластер, так само і ε-околи цих точок, якщо вони також будуть щільними. Цей процес продовжується доти, поки щільно-зв'язний кластер не буде знайдено повністю. Після цього виконується запит на нову необроблену точку, яка опрацьовується і, або знаходиться новий кластер, або вона позначається як шумова.
Алгоритм DBSCAN можна використовувати з будь-якою функцією відстані (так само, як функції подібності або інші предикати). Тому можна розглядати функцію відстані (dist) як додатковий параметр.
Алгоритм записаний на псевдокоді буде виглядати так:
DBSCAN(DB, distFunc, eps, minPts) { C = 0 /* Лічильник міток кластерів */ for each point P in database DB { if label(P) ≠ undefined then continue /* Раніше оброблено у внутрішньому циклі */ Neighbors N = RangeQuery(DB, distFunc, P, eps) /* Пошук сусідів */ if |N| < minPts then { /* Перевірка щільності */ label(P) = Noise /* Позначається як Шум */ continue
C = C + 1 /* Мітка наступного кластера */ label(P) = C /* Помічаємо початкову точку */ Seed set S = N \ {P} /* Множина з сусідів для перевірки */ for each point Q in S { /* Обробляємо кожну точку */ if label(Q) = Noise then label(Q) = C /* Зміна з Шум на граничну точку */ if label(Q) ≠ undefined then continue /* Раніше оброблені */ label(Q) = C /* Помічається сусід */ Neighbors N = RangeQuery(DB, distFunc, Q, eps) /* Пошук сусідів */ if |N| ≥ minPts then { /* Перевірка щільності */ S = S ∪ N /* Додаємо нових сусідів у множину для перевірки */
Тут RangeQuery може бути реалізована за допомогою індексування бази даних для кращої швидкодії або можна використати повільний лінійний пошук:
RangeQuery(DB, distFunc, Q, eps) { Neighbors = empty list for each point P in database DB { /* Перебираємо всі точки в базі */ if distFunc(Q, P) ≤ eps then { /* Обчислюємо відстань і порівнюємо з епсилон */ Neighbors = Neighbors ∪ {P} /* Додаємо до результату */
return Neighbors
Абстрактний алгоритм
Алгоритм DBSCAN можна абстрактно описати наступними кроками:
Знайти точки у кожному ε-околі кожної точки та визначити ядрові точки, у яких більше ніж minPts сусідів. Знайти компоненти зв'язності для ядрових точок на графі сусідів, виключивши з розгляду точки, які не є ядровими. Приєднати кожну не ядрову точку до найближчого кластера, за умови, що кластер знаходиться в ε (eps) околі, інакше помітити її як шумову.
Наївна реалізація потребує зберігання списку сусідів на кроці 1, тому потрібно використовувати суттєвий об'єм пам'яті. Оригінальний алгоритм DBSCAN не потребує цього, бо виконує ці кроки для однієї точки за раз.
Складність DBSCAN сканує кожну точку бази, можливо, навіть декілька разів. Наприклад, коли це кандидати до різних кластерів. Однак, з практичної точки зору, часова складність визначається кількістю запитів regionQuery. DBSCAN робить рівно один запит для кожної точки і, якщо використовувати просторовий індекс при пошуку сусідів, то можна це виконувати за час . Тоді можна досягти середньої часової складності за умови вибору параметру у такий спосіб, щоб запит повертав у середньому точок. Без використання такого прискорення з просторовим індексом або для вироджених даних (коли всі точки на відстані меншій ніж ), у найгіршому випадку часова складність буде . Матриця відстаней розміру можна зберігати у пам'яті розміру , без використання матриці відстаней, реалізація DBSCAN потребує лише пам'яті.
Переваги
Не потрібно вказувати апріорну кількість кластерів, як це потрібно для методу k-середніх. Знаходить кластери довільної форми. Може навіть знаходити кластер повністю оточений (але не лінійно зв'язний) іншим кластером. За допомогою параметру MinPts можна позбутись ефекту одного зв'язку, коли різні кластери зв'язані тонкою лінією. Має поняття шуму, і є надійним для виявлення аномалій. Потребує всього два параметри і здебільшого нечутливий до впорядкування точок. (Однак, точки розташовані на границі двох різних кластерів можуть змінити належність кластерам, якщо поміняти їх порядок у базі.) Призначений для використання з базами даних, які можуть прискорити регіональні запити, наприклад, використовують R*-дерево. Параметри minPts та ε можуть бути визначені , якщо дані зрозумілі.
Недоліки DBSCAN не є детерміністичним: точки на межі, які досяжні з декількох кластерів, можуть належати одному або іншому кластеру в залежності від порядку обробки даних. Для більшості наборів даних та областей, така проблема з'являється рідко і має незначний вплив на результат кластеризації, бо шумові та ядрові точки визначаються однозначно. DBSCAN* класифікує точки на межі як шум, що робить алгоритм детерміністичним і більш статистично узгоджену інтерпретацію компонент. Якість кластеризації залежить від функції відстані, яка використовується у функції regionQuery(P,ε). Зазвичай використовується евклідова відстань. Особливо при кластеризації багатовимірних даних ця метрика може стати негодящою через так зване «прокляття розмірності», що ускладнює пошук придатного значення для ε. Цей ефект, однак, присутній і в будь-якому іншому алгоритмі кластеризації, який використовує евклідову відстань. Не може кластеризувати набори даних з великим перепадом щільностей, оскільки неможливо підібрати поєднання значень minPts-ε, яке б відповідало різним кластерам. Якщо дані та масштаб не дуже зрозумілі, то вибір доречного порогового значення відстані ε може бути складним.
Дивись розділ нижче про модифікації алгоритму, які вирішують ці вади.
Оцінка параметрів Кожна задача добування даних має проблему визначення параметрів. Кожен параметр впливає специфічним чином. Для DBSCAN потрібно визначати параметри ε та minPts. Ці параметри повинні бути визначені користувачем. В ідеальній ситуації значення ε визначається з проблеми, яка розв'язується (наприклад, це може бути фізична відстань), а minPts визначається з бажаного мінімального розміру кластера.
MinPts: Як правило мінімальне значення параметру можна обчислити залежно від кількості вимірів D набору даних. А саме, minPts ≥ D + 1. Найменше значення minPts = 1, очевидно, не має сенсу, бо тоді кожна точка утворить кластер. При minPts ≤ 2, результат буде такий же самий, які і при ієрархічній кластеризації, тільки дерево буде обмежено висотою ε. Тому, щонайменшим значенням minPts буде 3. Однак, краще брати більші значення, як для наборів даних з шумами, так і для побудови більш вагомих кластерів. Як правило вибирають minPts = 2·dim, але можливо слід використовувати і більші значення для дуже великих даних, або для зашумлених даних або даних з великою кількістю дублікатів. ε: Значення для ε можна вибрати за допомогою графу k-відстані виводячи відстань по графіку для k = minPts-1 найближчих сусідів впорядкованих від найбільшого до найменшого значення. Гарним значення ε відповідає точці на графіку, де утворюється «згин»: якщо ε вибрано занадто малим, то велика частина даних не буде кластерізована; якщо ж ε буде занадто великим, то кластери зіллються і різні об'єкти опиняться в одному кластері. Загалом, краще брати невеликі значення ε, бо, як правило, тільки невеликі частини даних повинні бути в межах цієї відстані один від одного. Крім того, можна використати алгоритм OPTICS для вибору ε, але тоді можна його застосувати і для кластеризації даних. Функція відстані: Вибір функції відстані тісно пов'язаний з вибором ε, і має значний вплив на результати. Загалом, перш за все необхідно визначити розумну міру подібності для набору даних, перш ніж вибирати параметр ε. Для цього параметра немає оцінок, але функцію відстані слід обирати відповідно до набору даних. Наприклад, для географічних даних, відстань, яка вимірюється по великому колу, є найбільш прийнятною.
OPTICS можна розглядати як узагальнення DBSCAN, який замінює параметр ε максимальним значенням, що найбільше впливає на швидкодію. MinPts по суті стає мінімальним розміром кластера. Хоча цей алгоритм набагато простіше параметризувати, ніж DBSCAN, його результати трохи важче використати ніж результати DBSCAN, бо він будує ієрархічну кластеризацію замість простого розбиття даних, як це робить DBSCAN.
Нещодавно, один з авторів DBSCAN переглянув роботу DBSCAN та OPTICS, й оприлюднив удосконалену версію ієрархічного алгоритму DBSCAN (HDBSCAN*), яка вже не використовує поняття точок на межі. Натомість, кластер утворюють лише ядрові точки.
Узагальнення
DBSCAN (GDBSCAN) був узагальнений тими ж авторами на довільні предикати «окіл» та «щільність». Параметри ε та minPts були переміщені з алгоритму у ці предикати. Наприклад, для даних на багатокутнику, поняття «сусідні» можна сприймати, як такі, що мають перетин, а поняття щільності використовує площі полігонів замість підрахування кількості об'єктів.