Tekst źródłowy strony DBSCAN

{{Algorytm infobox
 |nazwa            = DBSCAN
 |grafika          = DBSCAN-density-data.svg
 |wielkość grafiki = 
 |opis grafiki     = Przykład klastrów uzyskanych za pomocą algorytmu DBSCAN
 |rodzaj           = [[analiza skupień|klasteryzacja]]
 |struktura        = 
 |czas             = <math>O(n \cdot log(n))</math> (średnia)
 |pamięć           = 
}}
'''DBSCAN''' (od {{w języku|en|Density-Based Spatial Clustering of Applications with Noise}}) – algorytm [[analiza skupień|grupowania danych]] (klasteryzacji) oparty na gęstości<ref name="starczewski">{{cytuj |autor = Artur Starczewski, Piotr Goetzen, Meng Joo Er |tytuł = A New Method for Automatic Determining of the DBSCAN Parameters |czasopismo = Journal of Artificial Intelligence and Soft Computing Research |data = 2020-07-01 |data dostępu = 2024-01-08 |wolumin = 10 |numer = 3 |s = 209–221 |doi = 10.2478/jaiscr-2020-0014 |język = en}}</ref><ref name="sala">{{Cytuj |autor = Karolina Sala |tytuł = Przegląd technik grupowania danych i obszary zastosowań |url = https://bibliotekanauki.pl/articles/2157869.pdf |czasopismo = Społeczeństwo i Edukacja. Międzynarodowe Studia Humanistyczne |wolumin = 2 |numer = 25 |wydawca = Instytut Studiów Międzynarodowych i Edukacji Humanum |data = 2017 |s = 141–145 |data dostępu = 2024-01-08}}</ref>. Jego pierwsza wersja została opublikowana w 1996 roku przez [[Martin Ester|Martina Estera]] wraz ze współautorami<ref name="ester">{{Cytuj |autor = Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu |tytuł = A density-based algorithm for discovering clusters in large spatial databases with noise |url = https://cdn.aaai.org/KDD/1996/KDD96-037.pdf |s = 226–231 |czasopismo = Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96) |wydawca = AAAI Press |data = 1996}}</ref><ref name="rehman">{{cytuj |autor = Saif Ur Rehman, Sohail Asghar, Simon Fong, S. Sarasvady |tytuł = DBSCAN: Past, present and future |data = 2014-02 |isbn = 978-1-4799-2259-8 |wydawca = IEEE |s = 232–238 |doi = 10.1109/ICADIWT.2014.6814687}}</ref>.

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<ref name="brzezinska">{{Cytuj |autor = Agnieszka Nowak-Brzezińska, Tomasz Xięski |tytuł = Grupowanie danych złożonych |url = http://delibra.bg.polsl.pl/Content/76298/BCPS-85705_2011_Grupowanie-danych-zl_0000.pdf |czasopismo = Studia Informatica |wolumin = 32 |numer = 2A |miejsce = Gliwice |wydawca = Wydawnictwo Politechniki Śląskiej |data = 2011 |data dostępu = 2024-01-08 |s = 391–402}}</ref>. Algorytm umożliwia znalezienie klastra o dowolnym kształcie, w tym klastra otaczającego inny klaster<ref name="sala" />. W odróżnieniu od [[algorytm centroidów|algorytmu k-średnich]], DBSCAN nie wymaga określenia liczby klastrów<ref name="sala" />. Średnia [[złożoność obliczeniowa|złożoność czasowa]] algorytmu wynosi <math>O(n \cdot log(n))</math><ref name="ester" />.

== Opis ==
[[Plik:DBSCAN-Illustration.svg|thumb|Ilustracja działania algorytmu dla <math>MinPts = 4.</math> 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)<ref name="starczewski" /><ref name="brzezinska" />:
* <math>eps</math> – maksymalny promień sąsiedztwa,
* <math>MinPts</math> – minimalna liczba obiektów wchodzących w skład klastra.

Algorytm dokonuje grupowania zbioru <math>X</math> w następujący sposób<ref name="starczewski" /><ref name="ester" /><ref name="brzezinska" />:
# Wylosuj ze zbioru danych punkt <math>p \in X.</math>
# Znajdź wszystkie punkty ze zbioru <math>X,</math> których odległość od punktu <math>p</math> jest mniejsza bądź równa <math>eps.</math>
# Jeśli liczba punktów znalezionych w punkcie 2 jest większa bądź równa <math>MinPts,</math> punkt <math>p</math> jest ''punktem centralnym'' i można na jego podstawie zbudować nowy klaster. W takim wypadku:
## Utwórz nowy klaster zawierający punkt <math>p</math> 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 <math>q \in X</math> od dowolnego punktu centralnego w klastrze jest mniejsza bądź równa <math>eps,</math> a w odległości mniejszej bądź równej <math>eps</math> od punktu <math>q</math> znajduje się co najmniej <math>MinPts</math> punktów, punkt <math>q</math> jest także punktem centralnym – do klastra należy ten punkt oraz wszystkie inne znajdujące się w promieniu <math>eps,</math>
### jeśli odległość punktu <math>q \in X</math> od dowolnego punktu centralnego w klastrze jest mniejsza bądź równa <math>eps,</math> ale w odległości mniejszej bądź równej <math>eps</math> od punktu <math>q</math> znajduje mniej niż <math>MinPts</math> punktów, punkt <math>q</math> jest ''punktem granicznym'' – do klastra należy ten punkt, ale już niekoniecznie inne punkty znajdujące się w promieniu <math>eps.</math>
# Wybierz kolejny punkt <math>p \in X</math> (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<ref name="sala" />.

== Implementacje ==
Implementacja algorytmu jest dostępna między innymi w bibliotece ''scikit-learn'' języka [[Python]]<ref>{{cytuj |tytuł = sklearn.cluster.DBSCAN |data dostępu = 2024-01-08 |opublikowany = scikit-learn |url = https://scikit-learn.org/stable/modules/generated/dbscan-function.html |język = en}}</ref> oraz w bibliotece ''fpc'' w języku [[R (język programowania)|R]]<ref>{{cytuj | tytuł = dbscan function - RDocumentation | data dostępu = 2024-08-19 | opublikowany = www.rdocumentation.org | url = https://www.rdocumentation.org/packages/fpc/versions/2.2-11/topics/dbscan}}</ref>.

== Przypisy ==
{{Przypisy}}

[[Kategoria:Algorytmy grupowania danych]]