DBSCAN: Co to jest? Kiedy go używać? Jak tego użyć.

DBSCAN (ang. Density-Spatial Clustering of Applications with Noise) to popularna metoda uczenia bez nadzoru stosowana w budowaniu modeli i algorytmach uczenia maszynowego. Zanim przejdziemy dalej, musimy zdefiniować, czym jest „bez nadzoru” metoda uczenia się. Metody nauki bez nadzoru mają miejsce, gdy nie ma jasnego celu lub rezultatu, który staramy się znaleźć. Zamiast tego gromadzimy dane w klastrze w oparciu o podobieństwo obserwacji. Aby to wyjaśnić, weźmy na przykład Netflix. Na podstawie poprzednich programów, które oglądałeś w przeszłości, Netflix poleci Ci programy do obejrzenia w następnej kolejności. Każdy, kto kiedykolwiek oglądał lub korzystał z Netflix, widział poniższy ekran z zaleceniami (Tak, to zdjęcie jest pobierane bezpośrednio z mojego konta Netflix i jeśli nigdy nie oglądałeś Shameless przed, sugeruję, abyś jak najszybciej).

Ponieważ oglądałem „Bezwstydne”, Netflix zaleca kilka innych podobnych programów do obejrzenia. Ale skąd Netflix zbiera te rekomendacje? Biorąc pod uwagę, że próbuje przewidzieć przyszłość za pomocą tego, co zamierzam obejrzeć w następnej kolejności, Netflix nie ma nic, na czym mógłby opierać się przewidywania lub rekomendacje (brak jasnego ostatecznego celu). Zamiast tego Netflix patrzy na innych użytkowników, którzy również oglądali „Bezwstydne” w przeszłości, i na to, co oglądali ci użytkownicy oprócz „Bezwstydnego”. W ten sposób Netflix grupuje użytkowników w oparciu o podobieństwo zainteresowań. Dokładnie tak działa nauka bez nadzoru. Po prostu grupuj obserwacje razem w oparciu o podobieństwo, mając nadzieję na wyciągnięcie dokładnych wniosków na podstawie klastrów.

Powrót do DBSCAN. DBSCAN to metoda klastrowania używana w uczeniu maszynowym do oddzielania klastrów o wysokiej gęstości od klastrów o niskiej gęstości. Biorąc pod uwagę, że DBSCAN jest algorytmem grupowania opartym na gęstości, świetnie sprawdza się w wyszukiwaniu obszarów danych o dużej gęstości obserwacji w porównaniu z obszarami danych, które nie są zbyt gęste z obserwacjami. DBSCAN może również sortować dane w klastry o różnych kształtach, co stanowi kolejną silną zaletę. DBSCAN działa tak:

  • Dzieli zestaw danych na n wymiarów
  • Dla każdego punktu w zestawie danych DBSCAN tworzy n wymiarowy kształt wokół tego punktu danych, a następnie liczy, ile punktów danych mieści się w tym kształcie.
  • DBSCAN liczy ten kształt jako klaster. DBSCAN iteracyjnie rozwija klaster, przechodząc przez każdy pojedynczy punkt w klastrze i licząc liczbę innych punktów danych w pobliżu. Weź przykład poniżej:

Przechodząc wyżej wspomniany proces krok po kroku, DBSCAN rozpocznie od podzielenia danych na n wymiarów. Po wykonaniu tego DBSCAN rozpocznie się w losowym punkcie (w tym przypadku załóżmy, że był to jeden z czerwonych punktów) i policzy, ile innych punktów znajduje się w pobliżu. DBSCAN będzie kontynuował ten proces, dopóki żadne inne punkty danych nie będą w pobliżu, a następnie będzie wyglądał, tworząc drugi klaster.

Jak można zauważyć na podstawie grafiki, istnieje kilka parametrów i specyfikacji, które musimy podać DBSCAN, zanim zadziała. Dwa parametry, które musimy określić, to:

Jaka jest minimalna liczba punktów danych potrzebna do ustalenia pojedynczego klastra?
Jak daleko może być jeden punkt od następnego punktu w tym samym klastrze?

Wracając do grafiki, epsilon jest promieniem podanym w celu przetestowania odległości między punktami danych. Jeśli punkt mieści się w odległości epsilon od innego punktu, te dwa punkty będą w tej samej grupie.

Ponadto w tym scenariuszu minimalna liczba potrzebnych punktów wynosi 4. Przechodząc przez każdy punkt danych, o ile DBSCAN znajdzie 4 punkty w odległości epsilon od siebie, powstaje klaster.

WAŻNE: Aby punkt został uznany za „rdzeń”, musi zawierać minimalną liczbę punktów w odległości epsilon. Ergo, wizualizacja faktycznie ma tylko DWIE podstawowe punkty. Przejrzyj dokumentację tutaj i spójrz w szczególności na parametr min_samples.

Zauważysz również, że niebieski punkt na grafice nie jest zawarty w żadnym klastrze. DBSCAN niekoniecznie kategoryzuje każdy punkt danych, dlatego jest świetny w obsłudze wartości odstających w zbiorze danych. Przyjrzyjmy się poniższej grafice:

Lewy obraz przedstawia bardziej tradycyjną metodę grupowania, która nie uwzględnia wielowymiarowości. Natomiast prawy obraz pokazuje, jak DBSCAN może przekształtować dane do różnych kształtów i wymiarów, aby znaleźć podobne klastry.

Lewy obraz przedstawia bardziej tradycyjną metodę grupowania, taką jak K-Means, która nie uwzględnia wielowymiarowości. Natomiast prawy obraz pokazuje, jak DBSCAN może przekształtować dane do różnych kształtów i wymiarów, aby znaleźć podobne klastry. Zauważamy również na prawym obrazie, że punkty wzdłuż zewnętrznej krawędzi zestawu danych nie są klasyfikowane, co sugeruje, że są odstające między danymi.

Zalety DBSCAN:

  • Świetnie sprawdza się w rozdzielaniu klastrów o dużej gęstości od klastrów o niskiej gęstości w ramach danego zestawu danych.
  • Doskonale radzi sobie z obsługą wartości odstających w zbiorze danych.

Wady DBSCAN:

  • Nie działa dobrze w przypadku klastrów o różnej gęstości. Podczas gdy DBSCAN doskonale oddziela klastry o wysokiej gęstości od klastrów o niskiej gęstości, DBSCAN walczy z klastrami o podobnej gęstości.
  • Zmaga się z danymi o wysokiej wymiarowości. Wiem, cały ten artykuł opisałem, jak DBSCAN świetnie nadaje się do przekształcania danych w różne wymiary i kształty. Jednak DBSCAN może posunąć się tylko do tej pory, jeśli dane o zbyt wielu wymiarach cierpią, DBSCAN cierpi

Poniżej zamieściłem sposób implementacji DBSCAN w Pythonie, w którym następnie wyjaśniam miary i oceniam model DBSCAN

Implementacja DBSCAN w Pythonie

1. Przypisywanie danych jako naszych wartości X.
Pamiętaj, ponieważ ponieważ jest to nauka bez nadzoru, nie mamy żadnych jasnych wartości y do ustawienia.
2. Utworzenie wystąpienia naszego modelu DBSCAN. W poniższym kodzie epsilon = 3 i min_samples to minimalna liczba punktów potrzebna do utworzenia klastra.
3. Przechowywanie etykiet utworzonych przez DBSCAN
4. Określenie, które punkty składają się na nasze „podstawowe punkty”
5. Obliczanie liczby klastrów
6. Obliczanie wyniku sylwetki

Metryki do pomiaru wydajności DBSCAN:

Wynik sylwetki: wynik sylwetki oblicza się na podstawie średniej odległości między gromadami między punktami ORAZ średniej odległości najbliższej gromady. Na przykład klaster z dużą ilością punktów danych bardzo blisko siebie (wysoka gęstość) ORAZ jest daleko od następnego najbliższego klastra (co sugeruje, że klaster jest bardzo unikalny w porównaniu do następnego najbliższego), będzie miał silną ocenę sylwetki . Punktacja sylwetki wynosi od -1 do 1, gdzie -1 oznacza najgorszy możliwy wynik, a 1 oznacza najlepszy wynik. Wyniki 0 sylwetki sugerują nakładające się klastry.

Bezwładność: bezwładność mierzy sumę kwadratów wewnętrznego skupienia (suma kwadratów jest sumą wszystkich reszt). Bezwładność jest wykorzystywana do pomiaru pokrewieństwa między sobą, im niższy wynik bezwładności, tym lepiej. JEDNAK ważne jest, aby zauważyć, że bezwładność w dużej mierze opiera się na założeniu, że klastry są wypukłe (o kształcie kulistym). DBSCAN niekoniecznie dzieli dane na sferyczne klastry, dlatego bezwładność nie jest dobrym miernikiem do oceny modeli DBSCAN (dlatego nie uwzględniłem bezwładności w powyższym kodzie). Bezwładność jest częściej stosowana w innych metodach grupowania, takich jak grupowanie metodą K.

Inne zasoby:

Blog Naftali Harris jest ogromnym dodatkowym źródłem informacji