DBSCAN

Przykład klastrów uzyskanych za pomocą algorytmu DBSCAN
Rodzaj	klasteryzacja
Złożoność
Czasowa	${\displaystyle 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^[1][2]. Jego pierwsza wersja została opublikowana w 1996 roku przez Martina Estera wraz ze współautorami^[3][4].

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^[5]. Algorytm umożliwia znalezienie klastra o dowolnym kształcie, w tym klastra otaczającego inny klaster^[2]. W odróżnieniu od algorytmu k-średnich, DBSCAN nie wymaga określenia liczby klastrów^[2]. Średnia złożoność czasowa algorytmu wynosi ${\displaystyle O(n\cdot log(n))}$^[3].

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

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

Algorytm dokonuje grupowania zbioru ${\displaystyle X}$ w następujący sposób^[1][3][5]:

1. Wylosuj ze zbioru danych punkt ${\displaystyle p\in X.}$
2. Znajdź wszystkie punkty ze zbioru ${\displaystyle X,}$ których odległość od punktu ${\displaystyle p}$ jest mniejsza bądź równa ${\displaystyle eps.}$
3. Jeśli liczba punktów znalezionych w punkcie 2 jest większa bądź równa ${\displaystyle MinPts,}$ punkt ${\displaystyle p}$ jest punktem centralnym i można na jego podstawie zbudować nowy klaster. W takim wypadku:
   1. Utwórz nowy klaster zawierający punkt ${\displaystyle 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 ${\displaystyle q\in X}$ od dowolnego punktu centralnego w klastrze jest mniejsza bądź równa ${\displaystyle eps,}$ a w odległości mniejszej bądź równej ${\displaystyle eps}$ od punktu ${\displaystyle q}$ znajduje się co najmniej ${\displaystyle MinPts}$ punktów, punkt ${\displaystyle q}$ jest także punktem centralnym – do klastra należy ten punkt oraz wszystkie inne znajdujące się w promieniu ${\displaystyle eps,}$
      2. jeśli odległość punktu ${\displaystyle q\in X}$ od dowolnego punktu centralnego w klastrze jest mniejsza bądź równa ${\displaystyle eps,}$ ale w odległości mniejszej bądź równej ${\displaystyle eps}$ od punktu ${\displaystyle q}$ znajduje mniej niż ${\displaystyle MinPts}$ punktów, punkt ${\displaystyle q}$ jest punktem granicznym – do klastra należy ten punkt, ale już niekoniecznie inne punkty znajdujące się w promieniu ${\displaystyle eps.}$
4. Wybierz kolejny punkt ${\displaystyle 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^[2].

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