DBSCAN

DBSCAN

Przykład klastrów uzyskanych za pomocą algorytmu DBSCAN
Rodzaj	klasteryzacja
Złożoność
Czasowa	$O(n\cdot log(n))$ (średnia)

DBSCAN (od ang. Density-Based Spatial Clustering of Applications with Noise) – algorytm grupowania danych (klasteryzacji) oparty na gęstości. Jego pierwsza wersja została opublikowana w 1996 roku przez Martina Estera wraz ze współautorami.

Klastrami utworzonymi za pomocą tego algorytmu są obszary o dużym zagęszczeniu obiektów w porównaniu z otoczeniem, co odpowiada intuicyjnemu rozumieniu grupowania. Algorytm umożliwia znalezienie klastra o dowolnym kształcie, w tym klastra otaczającego inny klaster. W odróżnieniu od algorytmu k-średnich, DBSCAN nie wymaga określenia liczby klastrów. Średnia złożoność czasowa algorytmu wynosi $O(n\cdot log(n))$.

Opis

Ilustracja działania algorytmu dla $MinPts=4.$ Czerwone punkty (w tym punkt A) są punktami centralnymi, żółte (B i C) są punktami granicznymi, niebieski (N) jest szumem

Algorytm przyjmuje dwa parametry wejściowe (należy je dobrać pod kątem konkretnego zagadnienia):

• $eps$ – maksymalny promień sąsiedztwa,
• $MinPts$ – minimalna liczba obiektów wchodzących w skład klastra.

Algorytm dokonuje grupowania zbioru $X$ w następujący sposób:

1. Wylosuj ze zbioru danych punkt $p\in X.$
2. Znajdź wszystkie punkty ze zbioru $X,$ których odległość od punktu $p$ jest mniejsza bądź równa $eps.$
3. Jeśli liczba punktów znalezionych w punkcie 2 jest większa bądź równa $MinPts,$ punkt $p$ jest punktem centralnym i można na jego podstawie zbudować nowy klaster. W takim wypadku:
   1. Utwórz nowy klaster zawierający punkt $p$ i wszystkie punkty znalezione w punkcie 2.
   2. Dołączaj do klastra kolejne punkty, o ile są osiągalne gęstościowo z punktów już znajdujących się w klastrze, to znaczy:
      1. jeśli odległość punktu $q\in X$ od dowolnego punktu centralnego w klastrze jest mniejsza bądź równa $eps,$ a w odległości mniejszej bądź równej $eps$ od punktu $q$ znajduje się co najmniej $MinPts$ punktów, punkt $q$ jest także punktem centralnym – do klastra należy ten punkt oraz wszystkie inne znajdujące się w promieniu $eps,$
      2. jeśli odległość punktu $q\in X$ od dowolnego punktu centralnego w klastrze jest mniejsza bądź równa $eps,$ ale w odległości mniejszej bądź równej $eps$ od punktu $q$ znajduje mniej niż $MinPts$ punktów, punkt $q$ jest punktem granicznym – do klastra należy ten punkt, ale już niekoniecznie inne punkty znajdujące się w promieniu $eps.$
4. Wybierz kolejny punkt $p\in X$ (pomijając punkty znajdujące się już wewnątrz klastrów i punkty sprawdzone w punkcie 3) i wróć do punktu 3. Jeśli nie ma już nieprzejrzanych punktów, zakończ działanie algorytmu. Punkty niezaklasyfikowane do żadnego z klastrów traktowane są jako szum.

W zależności od kolejności przetwarzania punktów, przynależność punktów granicznych do klastrów może się zmienić. Pod tym względem algorytm jest więc niedeterministyczny.

Implementacje

Implementacja algorytmu jest dostępna między innymi w bibliotece scikit-learn języka Python oraz w bibliotece fpc w języku R.