Grupowanie gęstościowe. Algorytm DBSCAN – teoria

Dziś rozpoczynam omawianie algorytmów grupowania gęstościowego. Jako przykładem posłużę się DBSCAN-em – ich podaj najpopularniejszym reprezentantem.

Z tego artykułu dowiesz się:
1. Czym jest grupowanie gęstościowe?
2. Jak działa algorytm DBSCAN?
3. O czym należy pamiętać, wykonując grupowanie z użyciem tego algorytmu?

Zakładam, że słyszałeś o DBSCAN-ie. Wybrałem go jako przedstawiciela algorytmów gęstościowych z kilku powodów:

• Jest dosyć popularny – we wstępie nazwałem go najpopularniejszym „gęstościowcem”, choć przyznam, że nie widziałem na ten temat żadnych statystyk. Bazuję na doświadczeniu i intuicji. Wielokrotnie pojawiał się przy okazji różnych konferencji i projektów, w których brałem udział (ciekawostka: jeszcze nigdy nie widziałem, by podczas projektu lub meetup-u ktoś proponował użycie np. OPTICS-a).
• Jego działanie jest intuicyjne – pozwala zrozumieć ideę grupowania gęstościwego i jego zalety w porównaniu z pozostałymi algorytmami grupującymi.

Artykuł ze względu na objętość postanowiłem podzielić na dwie części. W tym wpisie przedstawiam podstawy teoretyczne i schemat działania, tak byś mógł zbudować w sobie pewną intuicję na temat działania tego algorytmu. Druga część, która pojawi się w kolejnym, to przykład praktycznego użycia algorytmu z zastosowaniem kilku popularnych bibliotek oraz porównanie ich działania na różnych zbiorach.

Grupowanie gęstościowe – najważniejsze informacje

Grupowanie gęstościowe polega na budowaniu segmentów na podstawie informacji o zagęszczeniu obserwacji w przestrzeni. Poprzez zagęszczenie należy rozumieć odległości dzielące poszczególne obserwacje w danym obszarze. W mojej ocenie jest ono najbardziej intuicyjną metodą grupowania. Poniżej kilka istotnych informacji na jego temat:

• Najlepiej sprawdza się przy identyfikacji segmentów o nieregularnych (niewypukłych) kształtach.
• Nie umożliwia definiowania liczby powstałych grup (liczbę grup można częściowo zmieniać poprzez zmianę parametrów modelu).
• Wymaga zdefiniowania minimalnej liczby obserwacji potrzebnych do zbudowania grupy.
• Wymaga zdefiniowania minimalnej odległości epsilon, która definiuje sąsiada.
• Daje możliwość budowania grup o różnych (nieregularnych) kształtach (brak założenia o sferyczności grup, tak, jak w przypadku algorytmu k-średnich).
• Nie wszystkie obserwacje muszą zostać przypisane do grup. Obserwacje niespełniające zakładanych kryteriów są uznawane za obserwacje odstające.
• W przypadku przedstawicieli tej grupy algorytmów kluczowy jest dobór odpowiednich parametrów modelu. Choć parametrów nie ma wiele, to dobranie ich w taki sposób, by powstała „odpowiednia” liczba grup i obserwacje nietypowe nie stanowiły znaczącej części zbioru jest w mojej ocenie wielką sztuką (powstanie na ten temat wpis).

Wprowadzenie teoretyczne do algorytmów iteracyjno-optymalizacyjnych.

DBSCAN – najważniejsze informacje

DBSCAN posiada dwa główne parametry wejściowe, od których ustawienia zależy powodzenie procesu grupowania:

• epsilon (w środowisku R-owym oznaczany jako Eps) – promień sąsiedztwa, czyli minimalna odległość dzieląca dwie obserwacje konieczna, by zostały one uznane za sąsiadów.
• min_samples (nazywany również MinPts) – minimalna liczba obserwacji potrzebna by wybrana obserwacja została uznana za punkt centralny danej grupy (punkt centralny również jest liczony).

Schemat działania algorytmu DBSCAN:

1. Dla każdej obserwacji znajdujemy jego sąsiadów, bliższych niż założona wartość epsilon.
2. Każda obserwacja, która ma co najmniej min_samples sąsiadów w odległości mniejszej niż epsilon, nazywana jest punktem centralnym.
3. Wszystkie obserwacje spełniające kryteria opisane w punkcie 2 są ze sobą łączone w jedną grupę.
4. Obserwacje, które nie są punktami centralnymi, a znajdują się w odległości epsilon, zostają przyłączone do istniejących grup.
5. Algorytm kończy działanie:
   1. Obserwacje, które należą do grup, lecz w ich zasięgu epsilon nie znajduje się żadna nowa obserwacja, nazywane są obserwacjami granicznymi danej grupy.
   2. Wszystkie obserwacje, które nie zostały przyłączone do żadnej z grup, stają się obserwacjami odstającymi.

Grupowanie zmiennych ciągłych – k-średnich vs k-modes.

Wady i zalety

Stosując algorytm DBSCAN warto mieć również na uwadze zarówno wszystkie jego ograniczenia, jak i mocne strony.

Zalety:

• Odporny na wpływ obserwacji odstających.
• Znakomicie radzi sobie z grupami o niewypukłym kształcie.
• Daje dobre rezultaty – zachowując przy tym relatywnie szybkie działanie.
• Daje możliwość definiowania wielu miar odległości – jest to problemem w przypadku np. k-średnich.

Wady:

• Nie daje możliwości definiowania a priori liczby segmentów – liczba segmentów zależy od liczby obserwacji i dobranych parametrów.
• Dobór odpowiednich parametrów bywa dosyć problematyczny – ich optymalizacja bywa długa i uciążliwa, gdyż nie ma jednej sprawdzonej metody (istnieje kilka podejść, które przedstawię w przyszłości).

Pozostałe algorytmy gęstościowe

Algorytm DBSCAN to najpopularniejszy reprezentant algorytmów gęstościowych. Warto pamiętać, że do tej samej grupy należą inne algorytmy, które są nieco bardziej wysublimowane. Potrafią również dawać lepsze rezultaty niż DBSCAN. Poniżej najpopularniejsze z nich.

• DBSCAN.
• HDBSCAN.
• OPTICS.

Podsumowanie

W następnym wpisie przedstawię część praktyczną. Skupię się na pokazaniu zastosowania algorytmu DBSCAN na kilku różnych zbiorach oraz porównam wyniki jego grupowania z algorytmem k-średnich.

Jeśli masz jakieś pytania, to proszę podziel się nimi w komentarzu pod wpisem – zapraszam do dyskusji. Jeśli artykuł przypadł Ci do gustu, to proszę, podziel się nim w mediach społecznościowych ze swoimi znajomymi. Będę bardzo wdzięczny. 🙂

photo: pixabay.com (EdiNugraha)