DBSCAN: Clustering oparte na gęstości

Gęstość zamiast odległości do centroidu

DBSCAN – Density-Based Spatial Clustering of Applications with Noise, opublikowany przez Ester, Kriegel, Sander i Xu w 1996 roku – przyjmuje całkowicie inny pogląd na klaster niż k-means. Zamiast mierzyć odległość do centroidu, pyta, czy punkt znajduje się w gęstej okolicy i rośnie poprzez łączenie ze sobą punktów, które są wzajemnie dostępne przez obszary o dużej gęstości. Dwa parametry definiują gęstość: eps, promień, oraz minPts, liczba punktów (w tym sam punkt), która musi znajdować się w promieniu eps, aby dana okolica była uznawana za gęstą.

demo na żywo · powiązana symulacja● LIVE

Rdzeń punktów, punkty graniczne, szum

Każdy punkt przypada do jednej z trzech kategorii. Rdzeń punktu to taki, który posiada co najmniej minPts punktów, w tym samego siebie, w promieniu eps – jest niejednoznacznie wewnątrz gęstej klastra. Punkt graniczny nie jest wystarczająco gęsty sam w sobie, aby być rdzeniem, ale leży w promieniu eps od takiego, który to jest, więc zostaje wciągnięty do tego klastra z jego brzigu. Cokolwiek innego jest szumem i nigdy nie jest zmuszane do bycia częścią klastra – jest po prostu oznaczany jako odstępnik, co stanowi prawdziwy wynik algorytmu, a nie jego błąd.

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
}

Dlaczego skupiny mogą mieć dowolny kształt

Rozszerzenie skumu (expandCluster) działa poprzez dostępność gęstości: jeśli punkt A jest punktem rdzeniowym, a punkt B znajduje się w odległości eps od A, to B dołącza do skupiny A, a jeśli B również jest punktem rdzeniowym, to poszukiwania kontynuowane są na zewnątrz od B. Ponieważ łańcuch podąża za gęstością tam, gdziekolwiek prowadzi, zamiast mierzyć odległość do jednego ustalonego centrum, skupina może śledzić łuk, spiralę lub dwie koncentryczne pierścienie – kształty, które całkowicie zdezorientowałyby metodę opartą na centroidzie. Kosztem jest to, że pojedynczy wąski most gęstych punktów przypadkowo łączy ze sobą dwa skupiny, które człowiek uznałby za oddzielne, dlatego eps musi być dostrojony, a nie zgadywany.

Ustawianie wartości eps i minPts

minPts zazwyczaj ustawia się na wartość zbliżoną do dwóch razy liczby wymiarów, z praktycznym dnem wynoszącym 3 lub 4 w dwóch wymiarach. Dla eps, standardowe podejście oblicza dla każdego punktu odległość do jego współrzędnego punktu o minPts-tym rzędzie, sortuje te odległości i je przedstawia – wykres k-odległości. Gęste obszary generują małe, płaskie odległości; krzywa ostro wygina się w górę, gdy punkty zaczynają się rozrzedzać, a ten łokiet jest rozsądnym eps. Ustaw eps zbyt małą wartość i wszystko staje się szumem; ustaw ją zbyt dużą i cały zbiór danych zapada się w jeden gęstość.

Często zadawane pytania

Jak DBSCAN różni się od k-średnich?

K-średnie wymaga podania liczby skupień k z góry i zakłada, że skupienia są w przybliżeniu kuliste i o podobnej wielkości, ponieważ minimalizują dystans do pojedynczego centroidu. DBSCAN nie potrzebuje podawania liczby skupień, znajduje skupienia o nieregularnych kształtach, śledząc gęstość, a wyraźnie oznaczane są punkty odstające jako szum zamiast wymuszania na każdym punkcie przynależności do skupienia.

Jak wybrać eps i minPts?

Często stosowaną heurystyką jest ustawienie minPts na około podwójną liczbę wymiarów, a następnie narysowanie krzywej odległości każdego punktu od jego minPts-tego najbliższego sąsiada w rosnącym porządku – wykresu k-odległości. W miejscu, gdzie ta krzywa ostro się wygina do góry, łokieć, jest to rozsądne eps: poniżej tego punktów jest gęstość, a powyżej nie.

Dlaczego dwa uruchomienia DBSCAN mogą oznaczyć punkt inaczej?

Punkty centralne i punkty szumu są zawsze oznaczane w ten sam sposób, ale punkt graniczny może znajdować się w odległości eps od punktów centralnych z dwóch różnych skupień. Które skupienie to „wyłania” zależy od kolejności przetwarzania punktów. Ten przypadek brzegowy jest rzadki w praktyce i nie wpływa na punkty centralne, które przenoszą kształt skupień.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz DBSCAN i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację DBSCAN