DBSCAN: Кластеризація на основі щільності

Щоденність замість відстані до центральної точки

DBSCAN – Density-Based Spatial Clustering of Applications with Noise, опублікований Ester, Kriegel, Sander та Xu у 1996 році – використовує абсолютно інший підхід до визначення кластера, ніж k-means. Замість вимірювання відстані до центральної точки, він запитує, чи знаходиться точка в щільному сусідстві, і росте кластери шляхом з’єднання точок, які взаємно досяжні через щільні регіони. Два параметри визначають щільність: eps – радіус, та minPts – кількість точок (включаючи саму точку), яка повинна знаходитися в межах цього радіуса, щоб сусідство вважалося щільним.

Ядерные точки, граничные точки, шум

Кожна точка потрапляє в одну з трьох категорій. Ядерна точка має щонайменше minPts точок, включаючи саму себе, у межах радіуса eps – вона однозначно знаходиться всередині щільної області. Гранична точка недостатньо щільна, щоб бути ядерною, але розташована на відстані eps від такої, тому її притягують до кластера з краю. Все, що не підпадає під ці критерії, вважається шумом і ніколи не включається в кластер – вона просто маркована як викид, який є справжнім результатом роботи алгоритму, а не його неспроможністю.

for (const p of points) {
  if (p.visited) continue;
  p.visited = true;
  const nbrs = regionQuery(p, eps);
  if (nbrs.length < minPts) { p.label = 'noise'; continue; }   // not dense enough
  const cluster = newCluster();
  expandCluster(p, nbrs, cluster, eps, minPts);                 // chain-grow through core points
}

Чому кластери можуть мати будь-яку форму

expandCluster працює на основі досяжності щільності: якщо точка A є центральною точкою, а точка B знаходиться в межах eps від A, B приєднується до кластера A, і якщо B також є центральною точкою, пошук продовжується від А. Оскільки ланцюг слідує за там, де щільність найбільша, а не вимірює відстань до одного фіксованого центру, кластер може простежувати форму півмісяця, спіралі або дві концентричні кільця – форми, які повністю заплутали б метод на основі центроїдів. Компроміс полягає в тому, що вузький місток щільно розташованих точок випадково може з’єднати два кластери, які людина вважала б окремими, що й пояснює необхідність налаштування eps замість того, щоб просто вгадувати.

Встановлення eps та minPts

minPts зазвичай встановлюється приблизно вдвічі більше, ніж кількість вимірів, з практичним мінімальним значенням 3 або 4 у двох вимірах. Для eps стандартна евристика для кожного точкового об’єкта обчислює відстань до його minPts-го найближчого сусіда, сортує ці відстані та будує графік k-відстаней – цей графік показує відстані до k-го найближчого сусіда. У щільних областях відстані мають невеликий нахил; крива різко піднімається там, де точки починають розрізнятися, і ця точка найбільшого нахилу є розумним значенням eps. Якщо eps встановлено занадто мало, все стає шумом; якщо воно встановлено занадто велике, весь набір даних згортається в один кластер.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте DBSCAN і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.