Algoritmus shlukování OPTIKA

Uspořádání bodů k identifikaci shlukovací struktury ( OPTICS ) je algoritmus pro hledání [1] shluků v prostorových datech na základě hustoty .  Algoritmus představili Michael Ankerst, Markus M. Breunig, Hans-Peter Kriegel a Jörg Sander [2] . Základní myšlenka algoritmu je podobná DBSCAN [3] , ale algoritmus je navržen tak, aby se zbavil jedné z hlavních slabin algoritmu DBSCAN – problému detekce smysluplných shluků v datech s různou hustotou. K tomu jsou databázové body (lineárně) uspořádány tak, že se prostorově blízké body stanou sousedy v řazení. Kromě toho je pro každý bod uložena speciální vzdálenost, která představuje hustotu, kterou je třeba u shluku předpokládat, aby body patřily do stejného shluku. Toto je reprezentováno jako dendrogram .

Hlavní myšlenka

Podobně jako DBSCAN vyžaduje algoritmus OPTICS dva parametry – parametr ε popisuje maximální zohledněnou vzdálenost (poloměr) a parametr MinPts popisuje počet bodů potřebných k vytvoření shluku. Bod p je bod jádra, pokud alespoň MinPts bodů jsou v jeho ε -sousedství . Na rozdíl od DBSCAN algoritmus OPTICS bere v úvahu také body, které jsou součástí hustšího shluku, takže každému bodu je přiřazena základní vzdálenost , která popisuje vzdálenost k MinPts -tému nejbližšímu bodu:

Zde core-dist = vzdálenost jádra, = -th ve vzestupném pořadí vzdálenosti k .

Dosažitelná vzdálenost bodu o od bodu p je buď vzdálenost mezi o a p , nebo základní vzdálenost bodu p , podle toho, která je větší:

Zde reachability-dist = dosažitelná vzdálenost.

Jestliže p a o jsou nejbližší sousedé a , můžeme předpokládat, že p a o patří do stejného shluku.

Jak základní, tak dosažitelné vzdálenosti nejsou definovány, pokud neexistuje dostatečně hustý shluk (jak je aplikován na ε ). Při dostatečně velkém ε se to nikdy nestane, ale pak jakýkoli dotaz ε -neighborhood vrátí celou databázi, což má za následek běh času . Parametr ε je vyžadován k odříznutí volných shluků, které již nejsou zajímavé, a tím k urychlení algoritmu.

Parametr ε je přísně vzato nepovinný. Dá se jednoduše nastavit na maximální možnou hodnotu. Pokud je však k dispozici prostorový index, ovlivní to výpočetní složitost. OPTICS se od DBSCAN liší tím, že tento parametr není zohledněn, pokud lze ε ovlivnit, tak pouze nastavením maximální hodnoty.

Pseudokód

Základní přístup algoritmu OPTICS je stejný jako DBSCAN , ale namísto podpory mnoha známých, ale dosud nezpracovaných členů klastru, je použita prioritní fronta (tj. indexovaná halda ).

OPTIKA (DB, eps, MinPts) pro každý bod p z DB p.reachable_distance=undefined pro každý hrubý bod p z DB N=getNeighbors (p, eps) označit p jako zpracované vložte p do seřazeného seznamu if (základní_vzdálenost(p, eps, Minpts) != nedefinováno) Semena=prázdná prioritní fronta obnovit (N, p, semena, eps, minpts) za každý další q ze semen N'=getNeighbors(q, eps) označit q jako zpracované vložte q do seřazeného seznamu if (basic_distance(q, eps, Minpts) != undefined) aktualizace (N', q, Seeds, eps, Minpts)

V proceduře update() je prioritní fronta Seeds aktualizována pomocí -neighbors bodů a podle toho:

aktualizace (N, p, Seeds, eps, Minpts) coredist=base_distance(p, eps, MinPts) pro každé o v N pokud (nezpracováno) new_dist_dist=max(coredist, dist(p,o)) if (o.reachable_distance == undefined) // bod o není v Seeds o.reach_distance=new_reach_distance Seeds.insert(o, new_delivery_dist) jinak // tečka o v Seeds, zkontrolujte zlepšení if (new_reach_distance < o.reach_distance) o.reach_distance=new_reach_distance Seeds.move_up(o, new_advance_growth)

OPTIKA umisťuje body v určitém pořadí a označí je nejmenší dosažitelnou vzdáleností (v původním algoritmu se pamatuje i hlavní vzdálenost, ta však není nutná pro další zpracování).

Extrakce shluků

Pomocí grafu dosažitelnosti (speciální druh stromového diagramu ) je snadné získat hierarchickou strukturu shluků. Jedná se o 2D graf, kde jsou body vyneseny na ose x v pořadí, v jakém jsou zpracovány algoritmem OPTIKA, a na ose y je vynesena dosažitelná vzdálenost. Protože body patřící do shluku mají malou dosažitelnou vzdálenost od svého nejbližšího souseda, vypadají shluky na grafu dosažitelnosti jako údolí. Čím je údolí hlubší, tím je shluk hustší.

Výše uvedený obrázek ilustruje tento koncept. V levé horní části obrázku je zobrazena simulovaná datová sada. Pravá horní oblast obrázku zobrazuje kostru získanou algoritmem OPTICS a spodní část obrázku ukazuje graf dosažitelnosti získaný pomocí OPTICS. Barvy v tomto grafu jsou popisky a algoritmus je nevypočítává. Je však jasně vidět, jak údolí na grafu odpovídají shlukům daného souboru dat. Žluté tečky na tomto obrázku jsou považovány za šum a neodpovídají žádným údolím. Obvykle nejsou přiřazeny k žádným shlukům, kromě zastřešujícího shluku „všechna data“ v hierarchickém výsledku.

Extrahování shluků z takového grafu lze provést ručně výběrem intervalů na ose x po zobrazení grafu, výběrem prahové hodnoty na ose y (pak je výsledek podobný shlukování DBSCAN se stejnými hodnotami a minPts, v našem případě může dát dobré výsledky hodnota 0,1), nebo pomocí různých algoritmů, které se snaží určit údolí podle strmosti grafu, podle ohybu nebo podle lokálních maxim. Takto získané shluky jsou obvykle hierarchické a nelze je získat v jediném běhu algoritmu DBSCAN.

Obtížnost

Podobně jako DBSCAN algoritmus zpracuje každý bod pouze jednou a během tohoto zpracování provede jeden -neighbor dotaz . Vzhledem k prostorovému indexu , který zajišťuje, že dotaz sousedství běží včas , dostaneme celkovou dobu běhu . Autoři původního článku o OPTICS uvádějí konstantní zpomalení 1,6x oproti DBSCAN. Všimněte si, že hodnota může výrazně ovlivnit cenu algoritmu, protože příliš velká hodnota může zvýšit složitost dotazu na sousedství na lineární.

Zejména je možný výběr (větší než maximální vzdálenost v datové sadě), ale zjevně vede ke kvadratické složitosti, protože dotaz na seznam sousedů vrací celou datovou sadu. I když není k dispozici žádný prostorový index, vede to k další režii při údržbě haldy. Proto je třeba správně vybrat soubor dat.

Rozšíření

OPTICS-OF [4] je algoritmus detekce anomálií založený na OPTICS. Používá se hlavně k extrakci odlehlých hodnot ze stávajícího běhu algoritmu OPTICS za nízkou cenu ve srovnání s jinými metodami extrakce odlehlých hodnot. Nejznámější verze algoritmu detekce lokálních odlehlých hodnot je založena na stejných konceptech.

DeLi-Clu [5] ,  ( Density-Link-Clustering ) kombinuje myšlenky z metody jediného shlukování a algoritmu OPTICS, eliminuje parametr a přidává zlepšení efektivity oproti OPTICS.

HiSC [6] je hierarchická metoda shlukování podprostoru (paralelně k osám) založená na OPTICS.

HiCO [7] je hierarchický korelační shlukovací algoritmus založený na OPTICS.

DiSH [8] je vylepšením algoritmu HiSC, který dokáže najít složitější hierarchie.

FOPTICS [9] je rychlá implementace využívající náhodné projekce.

HDBSCAN* [10] je založen na vylepšení algoritmu DBSCAN vyloučením hraničních bodů ze shluků, a tedy přesnější definici úrovní hustoty (podle Hartigana) [11] .

Dostupnost

Java implementace OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO a DiSH jsou dostupné v systému dolování dat ELKI (s akcelerovaným indexem pro některé distanční funkce as automatickým shlukováním pomocí metody ξ). Další implementace Java zahrnuje rozšíření sady nástrojů Weka (žádná podpora pro shlukování s ξ). Balíček jazyka R "dbscan" obsahuje implementaci algoritmu OPTICS v C++ (s tradičním shlukováním jako dbscan a ξ) pomocí K-rozměrného stromu pro urychlení indexu pro euklidovskou vzdálenost.

Jazyk Python má následující implementace. OPTICS je k dispozici v knihovně PyClustering . HDBSCAN je k dispozici v knihovně hdbscan , která je postavena na scikit learn .

Poznámky

  1. ↑ Kriegel, Kröger, Sander, Zimek, 2011 , str. 231–240.
  2. ↑ Ankerst, Breunig, Kriegel, Sander, 1999 , str. 49–60.
  3. ↑ Ester, Kriegel, Sander, Xu, 1996 , str. 226–231.
  4. ↑ Breunig, Kriegel, Ng, Sander, 1999 , str. 262–270.
  5. ↑ Achtert, Böhm, Kröger, 2006 , str. 119–128.
  6. ↑ Achtert, Böhm, Kriegel, Kröger, Müller-Gorman, Zimek, 2006 , str. 446–453.
  7. ↑ Achtert, Böhm, Kröger, Zimek, 2006 , str. 119–128.
  8. ↑ Achtert, Böhm, Kriegel, Kröger, Müller-Gorman, Zimek, 2007 , str. 152–163.
  9. ↑ Schneider, Vlachos, 2013 .
  10. ↑ Campello, Moulavi, Zimek, Sander, 2015 , str. 1–51.
  11. ↑ Hartigan, 1975 .

Literatura