DBSCAN - DBSCAN

Gęstość klastry oparte przestrzenna aplikacji z hałasem ( DBSCAN ) jest grupowanie danych algorytm zaproponowany przez Martina Ester , Hans-Peter Kriegel , Jörg Sander i Xiaowei Xu w roku 1996. Jest to grupowanie gęstość oparte algorytm nieparametryczny: podany zestaw punktów w jakiejś przestrzeni, grupuje razem punkty, które są blisko siebie upakowane (punkty z wieloma pobliskimi sąsiadami ), oznaczając jako odstające punkty, które leżą samotnie w regionach o małej gęstości (których najbliżsi sąsiedzi są zbyt daleko). DBSCAN to jeden z najpopularniejszych algorytmów klastrowania, a także najczęściej cytowany w literaturze naukowej.

W 2014 roku algorytm został nagrodzony testem czasu (nagrodą przyznawaną algorytmom, które zyskały dużą uwagę w teorii i praktyce) na wiodącej konferencji data mining ACM SIGKDD . Od lipca 2020 r. artykuł uzupełniający „DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN” pojawia się na liście 8 najczęściej pobieranych artykułów prestiżowego czasopisma ACM Transactions on Database Systems (TODS) .

Historia

W 1972 roku, Robert F. Ling opublikował ściśle związane algorytmu w „Theory and Construction K-Clusters” w komputerze Urzędowym przybliżony złożoności środowiska wykonawczego O (n³). DBSCAN ma najgorszy przypadek O(n²), a zorientowane na bazę danych sformułowanie zapytań zakresowych DBSCAN pozwala na przyspieszenie indeksu. Algorytmy nieco różnią się sposobem obsługi punktów granicznych.

Wstępny

Rozważ zbiór punktów w jakiejś przestrzeni, które mają zostać zgrupowane. Niech $ε$ będzie parametrem określającym promień sąsiedztwa względem pewnego punktu. Na potrzeby klastrowania DBSCAN punkty są klasyfikowane jako punkty podstawowe , punkty osiągalne ( gęstość -) i wartości odstające w następujący sposób:

Punkt $p$ jest punktem centralnym, jeśli co najmniej punkty $minPts$ znajdują się w odległości $ε$ od niego (w tym $p$ ).
Punkt $q$ jest bezpośrednio osiągalny z punktu $p,$ jeśli punkt $q$ znajduje się w odległości $ε$ od punktu $p$ rdzennego . Mówi się, że punkty są bezpośrednio osiągalne z punktów podstawowych.
Punkt $q$ jest osiągalny z $p,$ jeśli istnieje ścieżka $p 1, ..., p n$ z $p 1 = p$ i $p n = q$ , gdzie każde $p i +1$ jest bezpośrednio osiągalne z $p i$ . Zauważ, że oznacza to, że punkt początkowy i wszystkie punkty na ścieżce muszą być punktami podstawowymi, z możliwym wyjątkiem $q$ .
Wszystkie punkty, do których nie można dotrzeć z żadnego innego punktu, są punktami odstającymi lub punktami szumu .

Teraz, jeśli $p$ jest punktem centralnym, to tworzy klaster wraz ze wszystkimi punktami (rdzeniowymi lub nie-rdzeniowymi), które są z niego osiągalne. Każdy klaster zawiera co najmniej jeden punkt centralny; Punkty inne niż podstawowe mogą być częścią klastra, ale tworzą jego „krawędź”, ponieważ nie można ich użyć do osiągnięcia większej liczby punktów.

Na tym diagramie

minPts = 4

. Punkt A i pozostałe czerwone punkty są punktami centralnymi, ponieważ obszar otaczający te punkty w promieniu

ε

zawiera co najmniej 4 punkty (wliczając sam punkt). Ponieważ wszystkie są osiągalne od siebie, tworzą jeden klaster. Punkty B i C nie są punktami centralnymi, ale są osiągalne z punktu A (poprzez inne punkty centralne), a zatem również należą do klastra. Punkt N to punkt szumu, który nie jest ani punktem centralnym, ani bezpośrednio osiągalnym.

Osiągalność nie jest relacją symetryczną: z definicji tylko punkty kluczowe mogą dotrzeć do punktów innych niż kluczowe. Nie jest odwrotnie, więc punkt, który nie jest zasadniczy, może być osiągalny, ale nic nie można z niego osiągnąć. Dlatego potrzebne jest dalsze pojęcie powiązania , aby formalnie zdefiniować zakres klastrów znalezionych przez DBSCAN. Dwa punkty $p$ i $q$ są połączone gęstością, jeśli istnieje punkt $o$ taki, że zarówno $p,$ jak i $q$ są osiągalne z $o$ . Połączenie gęstości jest symetryczne.

Klaster spełnia wtedy dwie właściwości:

Wszystkie punkty w klastrze są wzajemnie powiązane gęstością.
Jeśli punkt jest osiągalny pod względem gęstości z jakiegoś punktu klastra, jest on również częścią klastra.

Algorytm

Oryginalny algorytm oparty na zapytaniach

DBSCAN wymaga dwóch parametrów: ε (eps) i minimalnej liczby punktów wymaganych do utworzenia gęstego obszaru (minPts). Zaczyna się od arbitralnego punktu startowego, który nie został odwiedzony. Pobierane jest ε-sąsiedztwo tego punktu i jeśli zawiera wystarczająco dużo punktów, uruchamiany jest klaster. W przeciwnym razie punkt zostanie oznaczony jako szum. Zauważ, że ten punkt może później zostać znaleziony w wystarczająco dużym środowisku ε innego punktu i dlatego może być częścią klastra.

Jeśli okaże się, że punkt jest gęstą częścią gromady, jego ε-sąsiedztwo jest również częścią tego gromady. Stąd wszystkie punkty znajdujące się w obrębie ε-sąsiedztwa są dodawane, podobnie jak ich własne ε-sąsiedztwo, gdy również są gęste. Ten proces trwa do momentu całkowitego znalezienia klastra połączonego gęstością. Następnie pobierany i przetwarzany jest nowy nieodwiedzony punkt, co prowadzi do odkrycia kolejnego klastra lub szumu.

DBSCAN może być używany z dowolną funkcją odległości (jak również funkcjami podobieństwa lub innymi predykatami). Funkcję odległości (dist) można zatem traktować jako dodatkowy parametr.

Algorytm można wyrazić w pseudokodzie w następujący sposób:

DBSCAN(DB, distFunc, eps, minPts) {
    C := 0                                                  /* Cluster counter */
    for each point P in database DB {
        if label(P) ≠ undefined then continue               /* Previously processed in inner loop */
        Neighbors N := RangeQuery(DB, distFunc, P, eps)     /* Find neighbors */
        if |N| < minPts then {                              /* Density check */
            label(P) := Noise                               /* Label as Noise */
            continue
        }
        C := C + 1                                          /* next cluster label */
        label(P) := C                                       /* Label initial point */
        SeedSet S := N \ {P}                                /* Neighbors to expand */
        for each point Q in S {                             /* Process every seed point Q */
            if label(Q) = Noise then label(Q) := C          /* Change Noise to border point */
            if label(Q) ≠ undefined then continue           /* Previously processed (e.g., border point) */
            label(Q) := C                                   /* Label neighbor */
            Neighbors N := RangeQuery(DB, distFunc, Q, eps) /* Find neighbors */
            if |N| ≥ minPts then {                          /* Density check (if Q is a core point) */
                S := S ∪ N                                  /* Add new neighbors to seed set */
            }
        }
    }
}

gdzie RangeQuery można zaimplementować przy użyciu indeksu bazy danych w celu uzyskania lepszej wydajności lub przy użyciu wolnego skanowania liniowego:

RangeQuery(DB, distFunc, Q, eps) {
    Neighbors N := empty list
    for each point P in database DB {                      /* Scan all points in the database */
        if distFunc(Q, P) ≤ eps then {                     /* Compute distance and check epsilon */
            N := N ∪ {P}                                   /* Add to result */
        }
    }
    return N
}

Algorytm abstrakcyjny

Algorytm DBSCAN można podzielić na następujące kroki:

Znajdź punkty w sąsiedztwie ε (eps) każdego punktu i zidentyfikuj główne punkty z więcej niż sąsiadami minPts.
Znajdź podłączonych komponentów z kluczowych punktów na wykresie sąsiada, ignorując wszystkie pobocznych punktów.
Przypisz każdy punkt niebędący rdzeniem do pobliskiego klastra, jeśli klaster jest sąsiadem ε (eps), w przeciwnym razie przypisz go do szumu.

Naiwna implementacja tego wymaga przechowywania sąsiedztwa w kroku 1, co wymaga znacznej ilości pamięci. Oryginalny algorytm DBSCAN nie wymaga tego, wykonując te kroki w jednym punkcie na raz.

Złożoność

DBSCAN odwiedza każdy punkt bazy danych, prawdopodobnie wielokrotnie (np. jako kandydaci do różnych klastrów). Jednak ze względów praktycznych złożoność czasowa zależy głównie od liczby wywołań regionuQuery. DBSCAN wykonuje dokładnie jedno takie zapytanie dla każdego punktu, a jeśli używana jest struktura indeksująca, która wykonuje zapytanie sąsiedztwa w $O(log n)$ , uzyskuje się ogólną średnią złożoność czasu działania $O(n log n)$ (jeśli parametr $ε$ jest wybrany w znaczący sposób, to znaczy taki, że średnio tylko $o (log n)$ punkty są zwracane). Bez użycia przyspieszającej struktury indeksowej lub na zdegenerowanych danych (np. wszystkie punkty w odległości mniejszej niż $ε$ ), złożoność czasu wykonania najgorszego przypadku pozostaje $O(n ² )$ . Macierz odległości o rozmiarze $(n ²- n)/2$ może zostać zmaterializowana, aby uniknąć ponownego obliczania odległości, ale wymaga to pamięci $O(n ²)$ , podczas gdy implementacja DBSCAN nie oparta na macierzy potrzebuje tylko pamięci $O(n)$ .

DBSCAN może znaleźć nieliniowo separowalne klastry. Ten zestaw danych nie może być odpowiednio pogrupowany za pomocą k-średnich lub grupowania EM mieszaniny Gaussa.

Zalety

DBSCAN nie wymaga a priori określania liczby klastrów w danych, w przeciwieństwie do k-średnich .
DBSCAN potrafi znaleźć klastry o dowolnym kształcie. Może nawet znaleźć klaster całkowicie otoczony (ale nie połączony) z innym klastrem. Dzięki parametrowi MinPts redukowany jest tzw. efekt pojedynczego ogniwa (różne klastry połączone cienką linią punktów).
DBSCAN ma pojęcie o szumie i jest odporny na wartości odstające .
DBSCAN wymaga tylko dwóch parametrów i jest w większości niewrażliwy na kolejność punktów w bazie danych. (Jednak punkty znajdujące się na krawędzi dwóch różnych klastrów mogą zamienić członkostwo w klastrze, jeśli kolejność punktów zostanie zmieniona, a przypisanie do klastra jest unikalne tylko do izomorfizmu).
DBSCAN jest przeznaczony do użytku z bazami danych, które mogą przyspieszać zapytania o regiony, np. przy użyciu drzewa R* .
Parametry minPts i ε mogą być ustawione przez eksperta dziedzinowego, jeśli dane są dobrze zrozumiane.

Niedogodności

DBSCAN nie jest całkowicie deterministyczny: punkty graniczne, które są osiągalne z więcej niż jednego klastra, mogą być częścią każdego klastra, w zależności od kolejności przetwarzania danych. W przypadku większości zbiorów danych i domen sytuacja ta nie pojawia się często i ma niewielki wpływ na wynik grupowania: zarówno w przypadku punktów podstawowych, jak i punktów szumu, DBSCAN jest deterministyczny. DBSCAN* to odmiana, która traktuje punkty graniczne jako szum, dzięki czemu uzyskuje się w pełni deterministyczny wynik, a także bardziej spójną statystyczną interpretację komponentów połączonych gęstością.
Jakość DBSCAN zależy od miary odległości użytej w funkcji regionQuery(P,ε). Najczęściej używaną metryką odległości jest odległość euklidesowa . Zwłaszcza w przypadku danych wysokowymiarowych , metryka ta może być prawie bezużyteczna ze względu na tak zwaną „ Klątwę wymiarowości ”, co utrudnia znalezienie odpowiedniej wartości dla ε. Efekt ten jest jednak również obecny w każdym innym algorytmie opartym na odległości euklidesowej.
DBSCAN nie może dobrze grupować zbiorów danych z dużymi różnicami w gęstościach, ponieważ kombinacja minPts-ε nie może być wtedy wybrana odpowiednio dla wszystkich klastrów.
Jeśli dane i skala nie są dobrze zrozumiane, wybór znaczącego progu odległości ε może być trudny.

Zapoznaj się z sekcją poniżej dotyczącą rozszerzeń dotyczących modyfikacji algorytmicznych w celu rozwiązania tych problemów.

Estymacja parametrów

Każde zadanie eksploracji danych ma problem z parametrami. Każdy parametr wpływa na algorytm w określony sposób. Dla DBSCAN potrzebne są parametry ε i minPts . Parametry muszą być określone przez użytkownika. Idealnie, wartość ε jest podana przez problem do rozwiązania (np. odległość fizyczna), a minPts jest wtedy pożądaną minimalną wielkością klastra.

MinPts : Z reguły minimalny minPts można wyprowadzić z liczby wymiarów D w zbiorze danych, ponieważ minPts ≥ D + 1. Niska wartość minPts = 1 nie ma sensu, ponieważ wtedy każdy punkt jest punkt centralny z definicji. Przy minPts ≤ 2, wynik będzie taki sam jak w przypadku grupowania hierarchicznego z metryką pojedynczego łącza, z dendrogramem przeciętym na wysokości ε. Dlatego minPts muszą być wybrane co najmniej 3. Jednak większe wartości są zwykle lepsze dla zestawów danych z szumem i dadzą bardziej znaczące klastry. Z reguły można zastosować minPts = 2· dim , ale może być konieczne wybranie większych wartości dla bardzo dużych danych, danych zaszumionych lub danych zawierających wiele duplikatów.
ε: Wartość ε można następnie wybrać za pomocą wykresu k-odległości , wykreślając odległość do najbliższego sąsiada k = minPts -1 w kolejności od największej do najmniejszej wartości. Dobre wartości ε są tam, gdzie ten wykres pokazuje „łokieć”: jeśli ε zostanie wybrane o wiele za małe, duża część danych nie zostanie zgrupowana; natomiast dla zbyt dużej wartości ε klastry połączą się i większość obiektów będzie w tym samym klastrze. Ogólnie rzecz biorąc, preferowane są małe wartości ε i z reguły tylko niewielka część punktów powinna znajdować się w tej odległości od siebie. Alternatywnie do wybrania ε można użyć wykresu OPTICS , ale sam algorytm OPTICS może być użyty do klastrowania danych.
Funkcja odległości: wybór funkcji odległości jest ściśle powiązany z wyborem ε i ma duży wpływ na wyniki. Ogólnie rzecz biorąc, przed wybraniem parametru ε konieczne będzie najpierw zidentyfikowanie rozsądnej miary podobieństwa dla zbioru danych. Nie ma oszacowania dla tego parametru, ale funkcje odległości należy dobrać odpowiednio do zbioru danych. Na przykład w przypadku danych geograficznych często dobrym wyborem jest odległość wielkiego okręgu .

OPTICS można postrzegać jako uogólnienie DBSCAN, które zastępuje parametr ε maksymalną wartością, która głównie wpływa na wydajność. MinPts wtedy zasadniczo staje się minimalnym rozmiarem klastra do znalezienia. Chociaż algorytm jest znacznie łatwiejszy do parametryzacji niż DBSCAN, wyniki są nieco trudniejsze w użyciu, ponieważ zwykle generuje hierarchiczne klastrowanie zamiast prostego partycjonowania danych, które tworzy DBSCAN.

Niedawno jeden z pierwotnych autorów DBSCAN ponownie przyjrzał się DBSCAN i OPTICS i opublikował udoskonaloną wersję hierarchicznego DBSCAN (HDBSCAN*), w którym nie ma już pojęcia punktów granicznych. Zamiast tego klaster tworzą tylko główne punkty.

Związek z grupowaniem widmowym

DBSCAN może być postrzegany jako specjalny (efektywny) wariant klastrowania widmowego : połączone komponenty odpowiadają optymalnym klasterom widmowym (bez obcinania krawędzi – klastrowanie widmowe próbuje podzielić dane z minimalnym odcięciem ); DBSCAN znajduje połączone komponenty na (asymetrycznym) wykresie osiągalności. Jednak klastrowanie widmowe może być intensywne obliczeniowo (aż bez aproksymacji i dalszych założeń) i należy wybrać liczbę klastrów zarówno dla liczby wektorów własnych do wyboru, jak i liczby klastrów do wytworzenia z k-średnimi na spektralnym zanurzeniu . Tak więc, ze względu na wydajność, oryginalny algorytm DBSCAN pozostaje lepszy niż implementacja spektralna, a ta zależność jest jak dotąd tylko teoretyczna. ${\ Displaystyle O (n ^ {3})}$ $k$

Rozszerzenia

Generalized DBSCAN (GDBSCAN) to uogólnienie tych samych autorów na dowolne predykaty „sąsiedzkie” i „gęste”. Parametry ε i minPts są usuwane z oryginalnego algorytmu i przenoszone do predykatów. Na przykład w przypadku danych wielokątów „sąsiedztwo” może być dowolnym przecinającym się wielokątem, podczas gdy predykat gęstości wykorzystuje obszary wielokątów, a nie tylko liczbę obiektów.

Zaproponowano różne rozszerzenia algorytmu DBSCAN, w tym metody zrównoleglania, estymacji parametrów i obsługi niepewnych danych. Podstawowa idea została rozszerzona o hierarchiczne grupowanie przez algorytm OPTICS . DBSCAN jest również używany jako część algorytmów klastrowania podprzestrzeni, takich jak PreDeCon i SUBCLU . HDBSCAN to hierarchiczna wersja DBSCAN, która jest również szybsza niż OPTICS, z której można wyodrębnić z hierarchii płaską partycję składającą się z najbardziej znanych klastrów.

Dostępność

Stwierdzono, że różne implementacje tego samego algorytmu wykazują ogromne różnice w wydajności, przy czym najszybszy zestaw danych testowych kończy się w ciągu 1,4 sekundy, a najwolniejszy zajmuje 13803 sekundy. Różnice można przypisać jakości implementacji, różnicom językowym i kompilatorowym oraz wykorzystaniu indeksów do akceleracji.

Apache Commons Math zawiera implementację Java algorytmu działającego w czasie kwadratowym.
ELKI oferuje implementację DBSCAN oraz GDBSCAN i innych wariantów. Ta implementacja może używać różnych struktur indeksowych dla podkwadratowego środowiska wykonawczego i obsługuje dowolne funkcje odległości i dowolne typy danych, ale może być wyższa od zoptymalizowanych (i wyspecjalizowanych) implementacji niskiego poziomu na małych zestawach danych.
mlpack zawiera implementację DBSCAN akcelerowaną technikami wyszukiwania zakresów w dwóch drzewach.
PostGIS zawiera ST_ClusterDBSCAN – dwuwymiarową implementację DBSCAN, która wykorzystuje indeks R-drzewa. Obsługiwany jest dowolny typ geometrii, np. Point, LineString, Polygon itp.
R zawiera implementacje DBSCAN w pakietach dbscan i fpc . Oba pakiety obsługują dowolne funkcje odległości poprzez macierze odległości. Pakiet fpc nie obsługuje indeksów (a zatem ma kwadratową złożoność czasu działania i pamięci) i jest raczej powolny ze względu na interpreter języka R. Pakiet dbscan zapewnia szybką implementację C++ przy użyciu drzew kd (tylko dla odległości euklidesowej), a także zawiera implementacje DBSCAN*, HDBSCAN*, OPTICS, OPTICSXi i innych powiązanych metod.
scikit-learn zawiera implementację DBSCAN w Pythonie dla dowolnych metryk Minkowskiego , którą można przyspieszyć za pomocą drzew kd i balowych, ale która używa pamięci kwadratowej najgorszego przypadku. Wkład scikit-learn zapewnia implementację algorytmu HDBSCAN *.
Biblioteka pyclustering zawiera implementację DBSCAN w Pythonie i C++ tylko dla odległości euklidesowej, a także algorytm OPTICS.
SPMF zawiera implementację algorytmu DBSCAN z obsługą drzewa kd tylko dla odległości euklidesowej.
Weka zawiera (jako pakiet opcjonalny w najnowszych wersjach) podstawową implementację DBSCAN, która działa w czasie kwadratowym i pamięci liniowej.

Languages

In other projects