DBSCAN - DBSCAN

Prostorové shlukování aplikací s hlukem na bázi hustoty ( DBSCAN ) je algoritmus shlukování dat navržený Martinem Esterem , Hansem-Peterem Kriegelem , Jörgem Sanderem a Xiaowei Xu v roce 1996. Jedná se o neparametrický algoritmus klastrování založený na hustotě : daný soubor bodů v určitém prostoru, seskupuje body, které jsou těsně u sebe (body s mnoha blízkými sousedy ), a označuje jako odlehlé body body, které leží samy v oblastech s nízkou hustotou (jejichž nejbližší sousedé jsou příliš daleko). DBSCAN je jedním z nejběžnějších klastrových algoritmů a je také nejcitovanější ve vědecké literatuře.

V roce 2014 byl algoritmus oceněn testem času (ocenění udělené algoritmům, kterým byla věnována značná pozornost v teorii a praxi) na přední konferenci o těžbě dat ACM SIGKDD . V červenci 2020 se v seznamu 8 nejstahovanějších článků prestižního časopisu ACM Transactions on Database Systems (TODS) objevuje navazující dokument „DBSCAN Revisited, Revisited: Why and How You ((Still) Use DBSCAN“) .

Dějiny

V roce 1972 Robert F. Ling publikoval úzce související algoritmus v „Theory and Construction of k-Clusters“ v The Computer Journal s odhadovanou běhovou složitostí O (n³). DBSCAN má nejhorší případ O (n²) a databázově orientovaná formulace dotazu na rozsah DBSCAN umožňuje zrychlení indexu. Algoritmy se mírně liší ve zpracování hraničních bodů.

Předběžný

Zvažte sadu bodů v určitém prostoru, které chcete seskupit. Nechť $ε$ je parametr určující poloměr sousedství vzhledem k určitému bodu. Pro účely seskupování DBSCAN jsou body klasifikovány jako základní body , ( hustota -) dosažitelné body a extrémní hodnoty , a to následovně:

Bod $p$ je základní bod, pokud jsou ve vzdálenosti $ε$ od něj (včetně $p$ ) alespoň $minPts$ body .
Bod $q$ je přímo dosažitelný z bodu $p,$ pokud je bod $q$ ve vzdálenosti $ε$ od hlavního bodu $p$ . Body jsou prý pouze přímo dosažitelné ze základních bodů.
Bod $q$ je dosažitelný z $p,$ pokud existuje cesta $p 1, ..., p n$ s $p 1 = p$ a $p n = q$ , kde každé $p i +1$ je přímo dosažitelné z $p i$ . Všimněte si toho, že to znamená, že počáteční bod a všechny body na cestě musí být základní body, s možnou výjimkou $q$ .
Všechny body nedosažitelné z jiného bodu jsou odlehlé hodnoty nebo hlukové body .

Nyní, když $p$ je základní bod, pak tvoří klastr společně se všemi body (jádrovými nebo ne-jádrovými), které jsou z něj dosažitelné. Každý klastr obsahuje alespoň jeden základní bod; body, které nejsou jádrem, mohou být součástí klastru, ale tvoří jeho „hranu“, protože je nelze použít k dosažení více bodů.

V tomto diagramu

minPts = 4

. Bod A a ostatní červené body jsou základními body, protože oblast obklopující tyto body v poloměru

ε

obsahuje alespoň 4 body (včetně samotného bodu). Protože jsou všichni navzájem dosažitelní, tvoří jeden klastr. Body B a C nejsou základními body, ale jsou dosažitelné z bodu A (prostřednictvím jiných hlavních bodů), a proto také patří do klastru. Bod N je hlukový bod, který není ani hlavním bodem, ani přímo dosažitelným.

Dosažitelnost není symetrický vztah: podle definice mohou pouze základní body dosáhnout vedlejších bodů. Opak není pravdou, takže bod, který není jádrem, může být dosažitelný, ale nelze z něj dosáhnout ničeho. Proto je k formální definici rozsahu klastrů nalezených DBSCAN zapotřebí další pojem propojenosti . Dva body $p$ a $q$ jsou spojeny hustotou, pokud existuje bod $o$ takový, že $p$ i $q$ jsou dosažitelné z $o$ . Propojení hustoty je symetrické.

Klastr pak splňuje dvě vlastnosti:

Všechny body v klastru jsou vzájemně propojeny hustotou.
Pokud je bod hustoty dosažitelný z některého bodu klastru, je také součástí klastru.

Algoritmus

Původní dotazovací algoritmus

DBSCAN vyžaduje dva parametry: ε (eps) a minimální počet bodů potřebných k vytvoření husté oblasti (minPts). Začíná libovolným výchozím bodem, který nebyl navštíven. Načte se e-okolí tohoto bodu a pokud obsahuje dostatečně mnoho bodů, spustí se klastr. Jinak je bod označen jako šum. Všimněte si, že tento bod může být později nalezen v dostatečně velkém prostředí e jiného bodu, a proto může být součástí klastru.

Pokud je bod shledán jako hustá část klastru, je jeho e-sousedství také součástí klastru. Sečtou se tedy všechny body, které se nacházejí v sousedství e, stejně jako jejich vlastní okolí e, když jsou také husté. Tento proces pokračuje, dokud není klastr připojený k hustotě zcela nalezen. Poté je načten a zpracován nový nenavštívený bod, což vede k objevení dalšího klastru nebo šumu.

DBSCAN lze použít s jakoukoli funkcí vzdálenosti (stejně jako funkce podobnosti nebo jiné predikáty). Funkci vzdálenosti (dist) lze tedy považovat za další parametr.

Algoritmus může být vyjádřen v pseudokódu následujícím způsobem:

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 */
            }
        }
    }
}

kde RangeQuery lze implementovat pomocí databázového indexu pro lepší výkon nebo pomocí pomalého lineárního skenování:

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
}

Abstraktní algoritmus

Algoritmus DBSCAN lze abstrahovat do následujících kroků:

Najděte body v sousedství ε (eps) každého bodu a identifikujte hlavní body s více než minPts sousedy.
Najděte připojená zařízení z klíčových bodů na sousední grafu ignorovat všechny non-core bodů.
Pokud je klastr sousedem ε (eps), přiřaďte každý bod, který není jádrem, poblíž, jinak jej přiřaďte šumu.

Naivní implementace toho vyžaduje uložení čtvrtí v kroku 1, což vyžaduje značnou paměť. Původní algoritmus DBSCAN to nevyžaduje provedením těchto kroků pro jeden bod najednou.

Složitost

DBSCAN navštíví každý bod databáze, možná vícekrát (např. Jako kandidáti různých klastrů). Z praktických důvodů se však časová složitost většinou řídí počtem vyvolání regionQuery. DBSCAN provede přesně jeden takový dotaz pro každý bod a pokud je použita indexovací struktura, která provádí sousední dotaz v $O (log n)$ , získá se celková průměrná složitost běhu $O (n log n)$ (pokud je parametr $ε$ zvolen v smysluplný způsob, tj. takový, že se v průměru vrátí pouze $O (log n)$ bodů). Bez použití zrychlující indexové struktury nebo na degenerovaných datech (např. Všechny body ve vzdálenosti menší než $ε$ ) zůstává složitost doby běhu nejhorší $O (n ²)$ . Matici vzdáleností o velikosti $(n ²- n)/2$ lze materializovat, aby se zabránilo $přepočtu$ vzdáleností, ale to vyžaduje paměť $O (n ²)$ , zatímco implementace DBSCAN bez matice vyžaduje pouze paměť $O (n)$ .

DBSCAN může najít nelineárně oddělitelné klastry. Tento soubor dat nelze adekvátně seskupit pomocí k-means nebo klastrování Gaussian Mixture EM.

Výhody

DBSCAN nevyžaduje, aby jeden určoval počet klastrů v datech a priori, na rozdíl od k-means .
DBSCAN může najít klastry libovolného tvaru. Může dokonce najít klastr zcela obklopený (ale nepřipojený) jiným klastrem. Díky parametru MinPts je takzvaný jednolinkový efekt (různé klastry propojené tenkou čarou bodů) omezen.
DBSCAN má pojem hluk a je robustní vůči odlehlým hodnotám .
DBSCAN vyžaduje pouze dva parametry a je většinou necitlivý na uspořádání bodů v databázi. (Body umístěné na okraji dvou různých klastrů však mohou vyměnit členství v klastru, pokud se změní pořadí bodů a přiřazení klastru je jedinečné pouze do izomorfismu.)
DBSCAN je navržen pro použití s databázemi, které mohou urychlovat dotazy na oblasti, např. Pomocí stromu R* .
Parametry minPts a ε může nastavit odborník na doménu, jsou -li data dobře srozumitelná.

Nevýhody

DBSCAN není zcela deterministický: hraniční body, které jsou dosažitelné z více než jednoho klastru, mohou být součástí kteréhokoli klastru, v závislosti na pořadí zpracování dat. U většiny datových sad a domén tato situace nenastává často a má malý dopad na výsledek shlukování: jak v základních bodech, tak v hlukových bodech je DBSCAN deterministický. DBSCAN* je variací, která považuje hraniční body za šum, a tímto způsobem dosahuje plně deterministického výsledku a také konzistentnější statistické interpretace komponent spojených s hustotou.
Kvalita DBSCAN závisí na míře vzdálenosti použité ve funkci regionQuery (P, ε). Nejběžnější používanou metrikou vzdálenosti je euklidovská vzdálenost . Zejména u vysokodimenzionálních dat může být tato metrika téměř nepoužitelná díky takzvané „ kletbě dimenzionality “, což ztěžuje nalezení vhodné hodnoty pro ε. Tento efekt je však také přítomen v jakémkoli jiném algoritmu založeném na euklidovské vzdálenosti.
DBSCAN nemůže dobře seskupovat datové sady s velkými rozdíly v hustotách, protože kombinaci minPts-ε pak nelze vhodně zvolit pro všechny klastry.
Pokud data a měřítko nejsou dobře srozumitelné, může být výběr smysluplného prahu vzdálenosti ε obtížný.

Algoritmické úpravy k řešení těchto problémů naleznete v níže uvedené části o rozšířeních.

Odhad parametrů

Každý úkol dolování dat má problém s parametry. Každý parametr ovlivňuje algoritmus specifickými způsoby. Pro DBSCAN jsou potřebné parametry ε a minPts . Parametry musí zadat uživatel. V ideálním případě je hodnota ε dána řešením problému (např. Fyzická vzdálenost) a minPts je pak požadovaná minimální velikost klastru.

MinPts : Minimální minPts lze zpravidla odvodit z počtu dimenzí D v datové sadě jako minPts ≥ D + 1. Nízká hodnota minPts = 1 nedává smysl, protože pak každý bod je základní bod podle definice. Při minPts ≤ 2 bude výsledek stejný jako při hierarchickém shlukování s metrikou jednoho odkazu, s dendrogramem vyříznutým ve výšce ε. Proto musí být vybrány minPts alespoň 3. Větší hodnoty jsou však obvykle lepší pro datové sady s šumem a poskytnou významnější klastry. Zpravidla lze použít minPts = 2 · dim , ale může být nutné zvolit větší hodnoty pro velmi velká data, pro hlučná data nebo pro data, která obsahují mnoho duplikátů.
ε: Hodnotu pro ε lze pak vybrat pomocí grafu vzdálenosti k, vynesením vzdálenosti k k = minPts -1 nejbližší soused seřazený od největší po nejmenší hodnotu. Dobré hodnoty ε jsou tam, kde tento graf ukazuje „koleno“: pokud je ε zvoleno příliš malé, velká část dat nebude seskupena; zatímco pro příliš vysokou hodnotu ε se shluky spojí a většina objektů bude ve stejném klastru. Obecně jsou upřednostňovány malé hodnoty ε a obecně by měl být v této vzájemné vzdálenosti pouze malý zlomek bodů. Alternativně lze k výběru ε použít graf OPTICS , ale pak lze k seskupení dat použít samotný algoritmus OPTICS.
Funkce vzdálenosti: Volba funkce vzdálenosti je úzce spjata s volbou ε a má zásadní vliv na výsledky. Obecně bude nutné nejprve určit rozumnou míru podobnosti pro soubor dat, než bude možné zvolit parametr ε. Pro tento parametr neexistuje žádný odhad, ale funkce vzdálenosti je třeba zvolit vhodně pro sadu dat. Například u geografických dat je často vhodnou volbou vzdálenost velkého kruhu .

OPTICS lze chápat jako zobecnění DBSCAN, které nahrazuje parametr ε maximální hodnotou, která většinou ovlivňuje výkon. MinPts se pak v podstatě stává minimální velikostí klastru, kterou lze najít. Přestože je algoritmus parametrizovatelný mnohem snadněji než DBSCAN, výsledky jsou o něco obtížnější na použití, protože obvykle vytvoří hierarchické seskupování namísto jednoduchého dělení dat, které vytváří DBSCAN.

Nedávno jeden z původních autorů DBSCAN přehodnotil DBSCAN a OPTICS a vydal vylepšenou verzi hierarchického DBSCAN (HDBSCAN*), který již nemá pojem hraniční body. Místo toho tvoří klastr pouze základní body.

Vztah ke spektrálnímu shlukování

DBSCAN lze považovat za speciální (efektivní) variantu spektrálního shlukování : Připojené komponenty odpovídají optimálním spektrálním klastrům (žádné hrany - spektrální shlukování se pokouší rozdělit data s minimálním řezem ); DBSCAN najde připojené komponenty na (asymetrickém) grafu dosažitelnosti. Spektrální shlukování však může být výpočetně náročné (až bez aproximace a dalších předpokladů) a je třeba zvolit počet klastrů jak pro počet vlastních vektorů, které je třeba zvolit, tak pro počet klastrů, které se mají vyrobit, s k-prostředky na spektrálním vkládání . Z výkonnostních důvodů tedy zůstává původní algoritmus DBSCAN výhodnější než spektrální implementace a tento vztah je zatím pouze teoreticky zajímavý. ${\ displaystyle O (n^{3})}$ ${\ displaystyle k}$

Rozšíření

Generalized DBSCAN (GDBSCAN) je generalizace stejných autorů na libovolné predikáty „sousedství“ a „hustoty“. Parametry ε a minPts jsou odstraněny z původního algoritmu a přesunuty do predikátů. Například na polygonových datech může být „sousedstvím“ jakýkoli protínající se mnohoúhelník, zatímco predikát hustoty používá polygonové oblasti místo pouze počtu objektů.

Byla navržena různá rozšíření algoritmu DBSCAN, včetně metod pro paralelizaci, odhad parametrů a podporu pro nejistá data. Základní myšlenka byla rozšířena na hierarchické shlukování pomocí algoritmu OPTICS . DBSCAN se také používá jako součást klastrových algoritmů subprostoru, jako jsou PreDeCon a SUBCLU . HDBSCAN je hierarchická verze DBSCAN, která je také rychlejší než OPTICS, z níž lze z hierarchie extrahovat plochý oddíl sestávající z nejvýznamnějších klastrů.

Dostupnost

Bylo zjištěno, že různé implementace stejného algoritmu vykazují obrovské rozdíly ve výkonu, přičemž nejrychlejší ze sady testovacích dat skončila za 1,4 sekundy, nejpomalejší trvala 13803 sekund. Rozdíly lze přičíst kvalitě implementace, rozdílům v jazyce a kompilátoru a použití indexů pro akceleraci.

Apache Commons Math obsahuje implementaci algoritmu Java spuštěného v kvadratickém čase.
Společnost ELKI nabízí implementaci DBSCAN i GDBSCAN a dalších variant. Tato implementace může využívat různé indexové struktury pro subkvadratický běh a podporuje funkce libovolné vzdálenosti a libovolné datové typy, ale může být překonána nízkoúrovňovými optimalizovanými (a specializovanými) implementacemi na malých datových sadách.
mlpack obsahuje implementaci DBSCAN akcelerovanou technikami vyhledávání ve dvou stromových řadách .
PostGIS obsahuje ST_ClusterDBSCAN-2D implementaci DBSCAN, která využívá index R-stromu. Je podporován jakýkoli typ geometrie, např. Point, LineString, Polygon atd.
R obsahuje implementace DBSCAN v balících dbscan a fpc . Oba balíčky podporují funkce libovolné vzdálenosti pomocí distančních matic. Balíček fpc nemá podporu indexu (a má tedy kvadratickou dobu běhu a složitost paměti) a je poměrně pomalý kvůli překladači R. Balíček dbscan poskytuje rychlou implementaci C ++ pomocí stromů kd (pouze pro euklidovskou vzdálenost) a také zahrnuje implementace DBSCAN*, HDBSCAN*, OPTICS, OPTICSXi a dalších souvisejících metod.
scikit-learn obsahuje implementaci DBSCAN v Pythonu pro libovolné metriky Minkowski , kterou lze urychlit pomocí stromů kd a kuličkových stromů, ale která využívá nejhorší kvadratickou paměť. Příspěvek k scikit naučit poskytuje implementaci HDBSCAN * algoritmu.
knihovna pyclustering obsahuje implementaci DBSCAN pro Python a C ++ pouze pro euklidovskou vzdálenost a také algoritmus OPTICS.
SPMF obsahuje implementaci algoritmu DBSCAN s podporou stromu kd pouze pro euklidovskou vzdálenost.
Weka obsahuje (jako volitelný balíček v nejnovějších verzích) základní implementaci DBSCAN, která běží v kvadratickém čase a lineární paměti.

Languages

In other projects