DBSCAN

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 11. prosince 2021; ověření vyžaduje 1 úpravu .

Prostorové shlukování aplikací se šumem založené na hustotě ( DBSCAN  ) je datový shlukovací algoritmus navržený Maritin Ester, Hans-Peter Kriegel, Jörg Sander a Xiaowei Su v roce 1996 [1] . Toto je shlukovací algoritmus založený na hustotě – daný soubor bodů v nějakém prostoru, algoritmus shlukuje dohromady body, které jsou blízko sebe (body s mnoha blízkými sousedy ), označující jako odlehlé body, které jsou osamělé v oblastech s nízkou hustotou. (nejbližší, jehož sousedé jsou daleko). DBSCAN je jedním z nejčastěji používaných shlukovacích algoritmů a je nejčastěji zmiňován ve vědecké literatuře [2] .

V roce 2014 získal algoritmus ocenění „time-tested“ (cena udělovaná algoritmům, které získaly významnou pozornost v teorii i praxi) na přední konferenci o data miningu KDD [3] .

Rané verze

V roce 1972 již Robert F. Ling publikoval článek s názvem The  Theory and Construction of k-Clusters [4] v The Computer Journal s podobným algoritmem s odhadem výpočetní složitosti [4] . DBSCAN má nejhorší případ složitosti a formulace DBSCAN v databázově orientovaných termínech dotazů na rozsah[ clear ] umožňuje zrychlení pomocí indexu. Algoritmy se liší v zacházení s okrajovými body.

Příprava

Zvažte množinu bodů v nějakém prostoru vyžadující shlukování. Aby bylo možné provést shlukování DBSCAN, jsou body rozděleny na základní body dosažitelné podle hustoty bodů a odlehlé hodnoty následovně:

Nyní, pokud p je jádrový bod, pak tvoří shluk spolu se všemi body (jádrovými nebo nejádrovými) dosažitelnými z tohoto bodu. Každý shluk obsahuje alespoň jeden hlavní bod. Nepodstatné body mohou být součástí shluku, ale tvoří jeho „okraj“, protože se pomocí nich nelze dostat k jiným bodům.

Dosažitelnost není symetrický vztah, protože podle definice nelze dosáhnout žádného bodu z vedlejšího bodu, bez ohledu na vzdálenost (takže vedlejší bod může být dosažitelný, ale nelze z něj dosáhnout ničeho). Proto je další koncept konektivity nezbytný pro formální definici oblasti shluků nalezených algoritmem DBSCAN. Dva body p a q souvisí s hustotou, pokud existuje bod o takový, že oba body p a q jsou dosažitelné z bodu o . Hustota konektivity je symetrická.

Pak cluster splňuje dvě vlastnosti:

  1. Všechny body ve shluku jsou po párech spojeny v hustotě.
  2. Pokud je bod hustoty dosažitelný z nějakého bodu ve shluku, také do shluku patří.

Algoritmus

Původní algoritmus založený na dotazech

DBSCAN vyžaduje zadání dvou parametrů: a minimální počet bodů, které musí tvořit hustou oblast [5] (minPts). Algoritmus začíná z libovolného bodu, který ještě nebyl viděn. Vybere se -okolí bodu a pokud obsahuje dostatek bodů, vytvoří se shluk, jinak je bod označen jako šum. Všimněte si, že tento bod lze později nalézt v sousedství jiného bodu a zahrnout jej do nějakého shluku.

Pokud je bod nalezen jako hustý bod shluku, jeho sousedství je také součástí tohoto shluku. Proto jsou všechny body nalezené v -neighborhood tohoto bodu přidány do shluku. Tento proces pokračuje, dokud není nalezen shluk spojený s hustotou. Poté je vybrán a zpracován nový nenavštívený bod, což vede k objevení dalšího shluku nebo šumu.

DBSCAN lze použít s libovolnou funkcí vzdálenosti [1] [6] (stejně jako s funkcí podobnosti nebo booleovskou podmínkou) [7] . Funkci vzdálenosti (vzdálenost) lze tedy považovat za doplňkový parametr.

Algoritmus lze zapsat v pseudokódu následovně [6] :

DBSCAN(DB; distFunc; eps; minPts) { C=0 /* Počet shluků */ pro každý bod P v databázi DB { if label(P) ≠ undefined then continue /* Bod byl vyhledán ve vnitřní smyčce */ Neighbors N=RangeQuery(DB, distFunc, P, eps) / * Najít sousedy */ if |N|< minPts then { /* Kontrola hustoty */ label(P)=Noise /* Označit jako šum */ pokračovat } C=C + 1 /* další štítek shluku */ štítek(P)=C /* Počáteční bod štítku */ Seed sada S=N \ {P} /* Sousedé pro rozšíření */ pro každý bod Q v S { /* Ošetřete každý počáteční bod */ pokud štítek(Q)=Šum , pak štítek(Q)=C /* Změňte štítek Šum na okraj */ pokud štítek(Q) ≠ nedefinováno , pokračujte /* Prohlédnuto */ štítek(Q)= C /* Označ souseda */ Neighbors N=RangeQuery(DB, distFunc, Q, eps) /* Najít sousedy */ if |N|≥ minPts then { /* Kontrola hustoty */ S=S ∪ N /* Přidat sousedy do nastavit základní body */ } } } }

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

RangeQuery(DB, distFunc, Q, ) { Sousedé=prázdný seznam pro každý bod P v databázi DB { /* Prohledejte všechny body v databázi */ if then { /* Vypočítejte vzdálenost a zkontrolujte epsilon */ Sousedi=Sousedé ∪ {P} /* Přidat k výsledku */ } } vrátit sousedé }

Abstraktní algoritmus

Algoritmus DBSCAN lze rozložit do následujících kroků [6] :

  1. Najdeme body v blízkosti každého bodu a vybereme hlavní body s více než minPts sousedy.
  2. Na grafu sousedů najdeme spojené složky hlavních bodů, ignorujeme všechny nezákladní body.
  3. Přiřaďte každému neprimárnímu nejbližšímu shluku, pokud je shluk -neighbor, jinak bod považujte za šum.

Naivní implementace algoritmu vyžaduje zapamatování sousedů v kroku 1, takže vyžaduje značnou paměť. Původní algoritmus DBSCAN to nevyžaduje provedením těchto kroků jeden bod po druhém.

Obtížnost

DBSCAN navštíví každý bod databáze, možná několikrát (například jako kandidáti pro jiné clustery). Z provozních zkušeností se ale časová náročnost řídí především počtem regionQuery dotazů. DBSCAN provede přesně jeden takový dotaz pro každý bod, a pokud je použita struktura indexu , která dokončí dotaz sousedství v čase O(log n ) , celková průměrná časová složitost je O( n log n ) (pokud je parametr vybrán rozumně, pak je takový, že se v průměru vrátí pouze O(log n ) bodů). Bez použití zrychlující indexové struktury nebo na zdegenerovaných datech (například když jsou všechny body menší než ), zůstává doba běhu v nejhorším případě . Vzdálenost matice velikosti lze vypočítat, aby se zabránilo přepočítávání vzdáleností, ale to vyžaduje paměť , zatímco implementace DBSCAN bez matice vzdálenosti vyžaduje pouze O( n ) paměť.

Výhody

  1. DBSCAN nevyžaduje specifikaci počtu clusterů v datech a priori , na rozdíl od metody k-means .
  2. DBSCAN dokáže najít shluky libovolného tvaru. Dokáže dokonce najít shluky zcela obklopené jinými shluky (ale nejsou s nimi spojené). Díky parametru MinPts je snížen tzv. efekt jednoho spojení (spojení různých shluků tenkou čarou teček).
  3. DBSCAN má pojem šumu a je tolerantní k odlehlým hodnotám .
  4. DBSCAN vyžaduje pouze dva parametry a většinou není citlivý na pořadí bodů v databázi . (Body, které jsou na hranici dvou různých shluků, však mohou skončit v jiném shluku, pokud se změní pořadí bodů a přiřazení shluků je jedinečné až do izomorfismu.)
  5. DBSCAN je navržen pro použití s ​​databázemi, které mohou urychlit dotazy v rozsahu hodnot, jako je například strom R* .
  6. MinPts a parametry mohou být nastaveny odborníky v dané oblasti, pokud jsou data dobře srozumitelná.

Nevýhody

  1. DBSCAN není zcela jednoznačný – okrajové body, které jsou dosažitelné z více než jednoho shluku, mohou patřit do kteréhokoli z těchto shluků v závislosti na pořadí, ve kterém jsou body prohlíženy. U většiny datových sad k těmto situacím dochází jen zřídka a mají malý vliv na výsledek shlukování [6]  – hlavní body a šum jsou jednoznačně zpracovány DBSCAN. DBSCAN* [8] je varianta, která zachází s okrajovými body jako s šumem a dosahuje tak zcela jednoznačného výsledku a také konzistentnější statistické interpretace komponent s hustotou propojenou.
  2. Kvalita DBSCAN závisí na měření vzdálenosti použité ve funkci regionQuery(P,ε). Nejčastěji používanou metrikou vzdálenosti je euklidovská metrika . Zejména pro shlukování vysokorozměrných dat může být tato metrika téměř nepoužitelná kvůli takzvanému „prokletí dimenzionality“ , což ztěžuje nalezení vhodné hodnoty . Tento efekt je však přítomen v jakémkoli jiném algoritmu založeném na euklidovské vzdálenosti.
  3. DBSCAN neumí dobře shlukovat datové sady s velkými rozdíly v hustotě, protože nedokáže vybrat kombinaci, která je přijatelná pro všechny clustery [9] .
  4. Pokud nejsou údaje a měřítko dobře pochopeny, může být obtížné zvolit smysluplný práh vzdálenosti.

Viz část o rozšířeních níže, kde jsou uvedeny algoritmické úpravy zabývající se těmito problémy.

Odhad parametru

Jakákoli úloha dolování dat má problém s parametry. Jakýkoli parametr má specifický vliv na algoritmus. Algoritmus DBSCAN potřebuje parametry a minPts . Parametry musí definovat uživatel. V ideálním případě je hodnota určena řešeným problémem (např. fyzické vzdálenosti) a minPts pak určuje minimální požadovanou velikost shluku [5] .

OPTICS si lze představit jako zobecnění DBSCAN, ve kterém je parametr nahrazen maximální hodnotou, která má největší dopad na výkon. MinPts se pak stane minimální velikostí clusteru. Přestože je algoritmus v doméně výběru parametrů podstatně jednodušší než DBSCAN, jeho výsledky se obtížněji používají, protože obvykle vytváří hierarchické shlukování namísto jednoduchého dělení, které vytváří DBSCAN.

Nedávno jeden z autorů DBSCAN revidoval DBSCAN a OPTICS a publikoval revidovanou verzi hierarchického DBSCAN (HDBSCAN*) [8] , která již nemá koncept okrajových bodů. Pouze hlavní body tvoří shluk.

Rozšíření

Generalized DBSCAN (GDBSCAN) [7] [10] je zobecněním stejných autorů pro libovolné booleovské výrazy „neighborhood“ a „density“. Parametry a minPts jsou odstraněny z algoritmu a přeneseny do booleovských podmínek. Například na polygonálních datech může být „sousedstvím“ jakýkoli průsečík polygonů, zatímco podmínka hustoty používá místo počtu prvků plochu.

Byla navržena různá rozšíření algoritmu DBSCAN, včetně metod pro paralelizaci, odhad parametrů a podporu pro sporná data. Základní myšlenka byla rozšířena na hierarchické shlukování pomocí algoritmu OPTICS . Algoritmus DBSCAN byl také použit jako součást algoritmů shlukování podprostoru jako PreDeCon a SUBCLU . HDBSCAN [8] je hierarchická verze DBSCAN, která je také rychlejší než OPTICS a ve které lze z hierarchie extrahovat plochý oddíl sestávající z nejviditelnějších shluků [11] .

Dostupnost

Byly nalezeny různé implementace algoritmu s obrovským rozdílem ve výkonu, nejrychlejší dokončila práci na testovacích datech za 1,4 sekundy a nejpomalejší strávila 13 803 sekund [12] . Rozdíl lze přičíst kvalitě implementace, rozdílu v jazycích a kompilátorech a použití indexů pro urychlení.

Poznámky

  1. ↑ 1 2 3 Ester, Kriegel, Sander, Xu, 1996 , str. 226–231.
  2. ↑ Microsoft Academic Search, 2010 .
  3. ↑ Cena Test času, 2014 .
  4. ↑ 12 Ling , 1972 , s. 326–332.
  5. ↑ 1 2 Zatímco minPts je intuitivně minimální velikost clusteru, v některých případech může DBSCAN produkovat menší clustery ( Schubert, Sander, Ester, Kriegel, Xu 2017 ). Cluster DBSCAN se skládá alespoň z jednoho základního bodu . Protože jiné body mohou být okrajovými body více než jednoho shluku, není zaručeno, že v každém shluku bude zahrnuto alespoň minPts bodů.
  6. ↑ 1 2 3 4 5 6 7 8 9 Schubert, Sander, Ester, Kriegel, Xu, 2017 , str. 19:1–19:21.
  7. ↑ 1 2 3 4 Sander, Ester, Kriegel, Xu, 1998 , str. 169–194.
  8. ↑ 1 2 3 Campello, Moulavi, Zimek, Sander, 2015 , str. 1–51.
  9. ↑ Kriegel, Kröger, Sander, Zimek, 2011 , str. 231–240.
  10. ↑ Sander, 1998 .
  11. ↑ Campello, Moulavi, Zimek, Sander, 2013 , str. 344.
  12. ↑ Kriegel, Schubert, Zimek, 2016 , str. 341.

Literatura