Kiedy DBSCAN jest lepszy od k-średnich?

Gdy skupiska mają nieregularne kształty, gdy w danych jest szum i wartości odstające albo gdy nie znasz liczby grup. K-średnich wygrywa przy kulistych grupach podobnej wielkości i przy bardzo dużych zbiorach w wysokim wymiarze.

Jak dobrać eps w DBSCAN?

Policz dla każdego punktu odległość do k-tego najbliższego sąsiada, posortuj i narysuj. Miejsce, gdzie krzywa gwałtownie rośnie, to rozsądne ε. Potem sprawdź kilka wartości wokół i oceń, czy liczba grup i odsetek szumu są stabilne.

Czy DBSCAN jest deterministyczny?

Prawie. Punkty rdzeniowe i szum są wyznaczone jednoznacznie. Jedyna niejednoznaczność dotyczy punktów brzegowych w zasięgu dwóch klastrów — trafiają do tego, który zostanie przetworzony pierwszy, więc zależą od kolejności danych.

05 · Bez nadzoru · 4 min czytania · aktualizacja 8 października 2026

Jak działa DBSCAN i kiedy jest lepszy od k-średnich?

W skrócie

DBSCAN łączy w grupy obszary gęsto upakowanych punktów, a rzadkie punkty oznacza jako szum. Znajduje skupiska dowolnego kształtu bez podawania ich liczby.

Co to jest

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) to algorytm klasteryzacji, który definiuje skupisko jako obszar, gdzie punkty leżą gęsto, oddzielony od innych obszarów rejonem rzadkim. Nie wymaga podania liczby grup, znajduje skupiska dowolnego kształtu i — co wyjątkowe — potrafi powiedzieć „ten punkt nie należy do żadnej grupy”.

Intuicja: patrzysz z samolotu nocą na mapę świateł. Miasta to gęste plamy, czasem o dziwnych kształtach, połączone tu i ówdzie rzadszymi łańcuchami. Pojedyncze światła na pustkowiu to nie „najmniejsze miasto”, tylko szum. DBSCAN formalizuje dokładnie tę intuicję.

Mechanizm — dlaczego tak działa

Algorytm ma dwa parametry: promień ε (eps) i minimalną liczbę punktów min_samples. Dla każdego punktu liczy, ilu sąsiadów ma w odległości ε (licząc siebie).

Punkt rdzeniowy ma co najmniej min_samples sąsiadów — leży w gęstym miejscu. Punkt brzegowy ma ich mniej, ale leży w zasięgu jakiegoś punktu rdzeniowego. Szum to wszystko inne. Klaster powstaje przez łańcuchowe łączenie punktów rdzeniowych, które są w swoim zasięgu, razem z ich punktami brzegowymi.

Dlaczego to łapie dowolne kształty? Bo klaster rośnie lokalnie, krok po kroku, od sąsiada do sąsiada. Półksiężyc czy pierścień to po prostu ciągła ścieżka gęstych punktów — nikt nie wymaga, by grupa była kulista wokół środka, jak w k-średnich.

Ceną jest wrażliwość na ε. Zbyt małe — większość punktów staje się szumem, a gęste obszary rozpadają się na drobne kawałki. Zbyt duże — mosty między skupiskami przekraczają próg i wszystko zlewa się w jedną grupę. Co gorsza, jedno ε obowiązuje w całej przestrzeni, więc DBSCAN nie radzi sobie, gdy skupiska mają bardzo różną gęstość: rzadsze uzna za szum albo gęstsze połączy. To motywacja dla HDBSCAN, który bada wszystkie gęstości naraz.

Druga słabość to wysoki wymiar. Gdy cech jest dużo, odległości między punktami stają się do siebie podobne (przekleństwo wymiarowości), a pojęcie „gęstego sąsiedztwa” traci ostrość. Dlatego DBSCAN najlepiej działa w kilku–kilkunastu wymiarach, często po wcześniejszej redukcji wymiaru.

Na przykładzie

Najpierw dwa sztuczne półksiężyce (400 punktów, lekki szum). K-średnich z k = 2 tnie je prostą linią: zgodność z prawdziwym podziałem ARI = 0,27. DBSCAN z min_samples=5 i ε między 0,15 a 0,2 odtwarza oba półksiężyce bezbłędnie (ARI 1,00, zero szumu). Przy ε = 0,1 rozpada je na 4 kawałki i 10 punktów szumu, przy ε = 0,3 łączy w jedną grupę.

Teraz prawdziwe dane: 342 pingwiny z Palmer Archipelago, cztery standaryzowane pomiary, min_samples=5. Mediana odległości do 5. sąsiada wynosi 0,47, a 90. percentyl 0,72. Przy ε = 0,3 aż 317 pingwinów (93%) trafia do szumu. Przy ε = 0,5 powstają 4 grupy i 69 punktów szumu. Przy ε od 0,7 do 0,8 DBSCAN stabilnie znajduje 2 grupy (207–216 i 119–121 osobników) i tylko 5–16 punktów szumu: pingwiny białobrewe (Gentoo) osobno, a pingwiny Adeli i maskowe razem. To uczciwy wynik — te dwa gatunki tworzą jeden ciągły obszar gęstości, bez rzadkiej przerwy między nimi.

Dane: Palmer Penguins (pingwiny z Antarktydy)

W praktyce

W scikit-learn: DBSCAN(eps=0.5, min_samples=5); etykieta -1 oznacza szum. Zawsze najpierw StandardScaler.
ε dobieraj z wykresu odległości do k-tego sąsiada (NearestNeighbors, k = min_samples), posortowanych rosnąco: szukaj „kolana”.
min_samples ok. 2 × liczba wymiarów to popularny punkt startu; większe wartości dają gładsze, odporniejsze grupy.
Przy skupiskach różnej gęstości użyj HDBSCAN (w scikit-learn od wersji 1.3) albo OPTICS.
Punkty z etykietą -1 to tani detektor anomalii — ale sprawdź, czy to naprawdę anomalie, a nie po prostu rzadszy klaster.
Typowy błąd: DBSCAN na 50+ surowych cechach bez redukcji wymiaru — wszystko staje się szumem albo jedną grupą.

Najczęstsze pytania

Kiedy DBSCAN jest lepszy od k-średnich?: Gdy skupiska mają nieregularne kształty, gdy w danych jest szum i wartości odstające albo gdy nie znasz liczby grup. K-średnich wygrywa przy kulistych grupach podobnej wielkości i przy bardzo dużych zbiorach w wysokim wymiarze.
Jak dobrać eps w DBSCAN?: Policz dla każdego punktu odległość do k-tego najbliższego sąsiada, posortuj i narysuj. Miejsce, gdzie krzywa gwałtownie rośnie, to rozsądne ε. Potem sprawdź kilka wartości wokół i oceń, czy liczba grup i odsetek szumu są stabilne.
Czy DBSCAN jest deterministyczny?: Prawie. Punkty rdzeniowe i szum są wyznaczone jednoznacznie. Jedyna niejednoznaczność dotyczy punktów brzegowych w zasięgu dwóch klastrów — trafiają do tego, który zostanie przetworzony pierwszy, więc zależą od kolejności danych.

Źródła

Ester M., Kriegel H.-P., Sander J., Xu X., „A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise”, Proceedings of KDD-96, 1996.
Schubert E., Sander J., Ester M., Kriegel H.-P., Xu X., „DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN”, ACM Transactions on Database Systems 42(3), 2017.
Campello R. J. G. B., Moulavi D., Sander J., „Density-Based Clustering Based on Hierarchical Density Estimates”, PAKDD 2013.
Dokumentacja scikit-learn, „DBSCAN”: https://scikit-learn.org/stable/modules/clustering.html#dbscan

Zobacz też

K-means InteraktywneK-means dzieli punkty na k grup: każdy punkt trafia do najbliższego środka, a środki przesuwają się do średniej swojej grupy. Zwraca k grup, nawet gdy ich brak.Pułapki metody k-średnich InteraktywneK-średnich zawsze zwróci k grup, nawet bez sensu. Psują go skale cech, złe ziarno startowe, wydłużone i nierówne skupiska oraz źle dobrane k.Klasteryzacja hierarchicznaKlasteryzacja hierarchiczna łączy punkty krok po kroku w coraz większe grupy i rysuje z tego drzewo – dendrogram. Liczbę grup wybierasz dopiero na końcu.Wykrywanie anomaliiWykrywanie anomalii szuka obserwacji, które nie pasują do reszty danych, zwykle bez etykiet. Działa tylko wtedy, gdy anomalie są rzadkie i naprawdę odmienne.K-średnich czy DBSCANK-średnich dzieli dane na k zwartych, kulistych grup i przypisuje każdy punkt. DBSCAN szuka gęstych obszarów dowolnego kształtu i odrzuca punkty-szum.Przekleństwo wymiarowości InteraktywneWraz z liczbą wymiarów przestrzeń pustoszeje wykładniczo, a odległości między punktami stają się prawie równe. Metody oparte na sąsiedztwie tracą sens.