DBSCAN
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].
 Przykład klastrów uzyskanych za pomocą algorytmu DBSCAN | |
| Rodzaj | |
|---|---|
| Złożoność | |
| Czasowa |
(średnia) |
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 [3].
Opis
edytuj
Algorytm przyjmuje dwa parametry wejściowe (należy je dobrać pod kątem konkretnego zagadnienia)[1][5]:
- – maksymalny promień sąsiedztwa,
- – minimalna liczba obiektów wchodzących w skład klastra.
Algorytm dokonuje grupowania zbioru w następujący sposób[1][3][5]:
- 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[2].
Implementacje
edytujImplementacja algorytmu jest dostępna między innymi w bibliotece scikit-learn języka Python[6] oraz w bibliotece fpc w języku R[7].
Przypisy
edytuj- ↑ a b c Artur Starczewski, Piotr Goetzen, Meng Joo Er, A New Method for Automatic Determining of the DBSCAN Parameters, „Journal of Artificial Intelligence and Soft Computing Research”, 10 (3), 2020, s. 209–221, DOI: 10.2478/jaiscr-2020-0014 [dostęp 2024-01-08] (ang.).
- ↑ a b c d Karolina Sala, Przegląd technik grupowania danych i obszary zastosowań, „Społeczeństwo i Edukacja. Międzynarodowe Studia Humanistyczne”, 2 (25), Instytut Studiów Międzynarodowych i Edukacji Humanum, 2017, s. 141–145 [dostęp 2024-01-08].
- ↑ a b c Martin Ester i inni, A density-based algorithm for discovering clusters in large spatial databases with noise, „Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96)”, AAAI Press, 1996, s. 226–231.
- ↑ Saif Ur Rehman i inni, DBSCAN: Past, present and future, IEEE, luty 2014, s. 232–238, DOI: 10.1109/ICADIWT.2014.6814687, ISBN 978-1-4799-2259-8.
- ↑ a b c Agnieszka Nowak-Brzezińska, Tomasz Xięski, Grupowanie danych złożonych, „Studia Informatica”, 32 (2A), Gliwice: Wydawnictwo Politechniki Śląskiej, 2011, s. 391–402 [dostęp 2024-01-08].
- ↑ sklearn.cluster.DBSCAN [online], scikit-learn [dostęp 2024-01-08] (ang.).
- ↑ dbscan function - RDocumentation [online], www.rdocumentation.org [dostęp 2024-08-19].