DBSCAN (od ) – 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 .
Opis thumb|Ilustracja działania algorytmu dla 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): – maksymalny promień sąsiedztwa, – minimalna liczba obiektów wchodzących w skład klastra.
Algorytm dokonuje grupowania zbioru w następujący sposób: Wylosuj ze zbioru danych punkt Znajdź wszystkie punkty ze zbioru których odległość od punktu jest mniejsza bądź równa Jeśli liczba punktów znalezionych w punkcie 2 jest większa bądź równa punkt jest punktem centralnym i można na jego podstawie zbudować nowy klaster. W takim wypadku: Utwórz nowy klaster zawierający punkt i wszystkie punkty znalezione w punkcie 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: jeśli odległość punktu od dowolnego punktu centralnego w klastrze jest mniejsza bądź równa a w odległości mniejszej bądź równej od punktu znajduje się co najmniej punktów, punkt jest także punktem centralnym – do klastra należy ten punkt oraz wszystkie inne znajdujące się w promieniu jeśli odległość punktu od dowolnego punktu centralnego w klastrze jest mniejsza bądź równa ale w odległości mniejszej bądź równej od punktu znajduje mniej niż punktów, punkt jest punktem granicznym – do klastra należy ten punkt, ale już niekoniecznie inne punkty znajdujące się w promieniu Wybierz kolejny punkt (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.
Przypisy
Kategoria:Algorytmy grupowania danych