DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

Czym jest DBSCAN?

DBSCAN to algorytm grupowania oparty na gęstości, który identyfikuje klastry jako obszary o wysokiej gęstości punktów, oddzielone regionami o niskiej gęstości. Jest szczególnie skuteczny w przypadku danych z nieregularnymi kształtami klastrów oraz w obecności szumu (punktów odstających).

Kluczowe pojęcia w DBSCAN:

1. Punkt rdzeniowy (core point):

   • Punkt, który ma co najmniej \(MinPts\) sąsiadów w promieniu \(\epsilon\).

2. Punkt brzegowy (border point):

   • Punkt, który znajduje się w otoczeniu \(\epsilon\) punktu rdzeniowego, ale sam nie spełnia warunku minimalnej liczby sąsiadów (\(MinPts\)).

3. Punkt szumu (noise point):

   • Punkt, który nie należy ani do klastra, ani do otoczenia \(\epsilon\) żadnego punktu rdzeniowego.

4. Epsilon (\(\epsilon\)):

   • Maksymalna odległość, w jakiej punkty są uznawane za sąsiadów.

5. Minimalna liczba punktów (\(MinPts\)):

   • Minimalna liczba sąsiadów wymagana, aby punkt był uznany za rdzeniowy.

Jak działa DBSCAN?

1. Wybór punktu początkowego:

   • Algorytm rozpoczyna od dowolnego, nieodwiedzonego punktu.

2. Analiza otoczenia:

   • Sprawdzane są wszystkie punkty znajdujące się w promieniu \(\epsilon\) od wybranego punktu.
   • Jeśli liczba sąsiadów jest większa lub równa \(MinPts\), punkt staje się rdzeniowy i inicjuje nowy klaster.

3. Rozszerzanie klastra:

   • Do klastra dodawane są wszystkie sąsiadujące punkty rdzeniowe oraz brzegowe.
   • Proces rozszerzania trwa, aż wszystkie punkty w klastrze zostaną przetworzone.

4. Przechodzenie do kolejnego punktu:

   • Algorytm przechodzi do następnego nieodwiedzonego punktu i powtarza proces, aż wszystkie punkty zostaną przetworzone.

5. Oznaczanie szumu:

   • Punkty, które nie zostały przypisane do żadnego klastra, są oznaczane jako szum.

Zalety DBSCAN:

• Elastyczność kształtów klastrów:
  • DBSCAN potrafi wykrywać klastry o nieregularnych kształtach.
• Odporność na szum:
  • Punkty odstające są skutecznie oznaczane jako szum.
• Brak potrzeby określania liczby klastrów:
  • Algorytm sam identyfikuje liczbę klastrów na podstawie parametrów \(\epsilon\) i \(MinPts\).

Wady DBSCAN:

• Wybór parametrów:
  • Dobór odpowiednich wartości \(\epsilon\) i \(MinPts\) może być trudny i wymaga eksperymentów.
• Problemy z różną gęstością:
  • Algorytm ma trudności z danymi o klastrach o znacznie różniącej się gęstości.
• Wydajność na dużych zbiorach danych:
  • Przy bardzo dużych zbiorach danych czas działania algorytmu może być długi, szczególnie bez odpowiednich struktur danych (np. KD-tree).

Zastosowania:

1. Wykrywanie anomalii:
   • Identyfikacja punktów odstających w finansach, bezpieczeństwie IT czy medycynie.
2. Przetwarzanie obrazu:
   • Grupowanie pikseli w celu wykrycia obiektów na obrazach.
3. Analiza przestrzenna:
   • Grupowanie obiektów w przestrzeni geograficznej, np. analiza gęstości zaludnienia.
4. Bioinformatyka:
   • Klasyfikacja danych genetycznych na podstawie ich gęstości.

Przykład działania:

Załóżmy zbiór danych w 2D:

• Parametry: \(\epsilon = 2\), \(MinPts = 3\).

1. Punkt \(A\) ma 4 sąsiadów w promieniu \(\epsilon = 2\) -> Punkt rdzeniowy.
2. Punkt \(B\) ma 2 sąsiadów w promieniu \(\epsilon = 2\) -> Punkt brzegowy.
3. Punkt \(C\) nie ma żadnych sąsiadów w promieniu \(\epsilon = 2\) -> Punkt szumu.

Na tej podstawie DBSCAN grupuje punkty \(A\) i \(B\) w jeden klaster, a punkt \(C\) zostaje oznaczony jako szum.

DBSCAN to potężne narzędzie, szczególnie w przypadkach, gdy dane mają nieregularne kształty lub zawierają szum, oferując dużą elastyczność i możliwość analizy gęstości punktów.