Přehled analýzy hierarchického klastru

Než se pustíme do porozumění hierarchické klastrové analýze, nejprve se pokusme pochopit, co je klastr? A co je klastrová analýza? Klastr je kolekce datových objektů; datové body v klastru jsou si navzájem podobné a odlišné od datových bodů v klastru. Clusterová analýza je v podstatě seskupením těchto datových bodů do klastru. Clustering je typ algoritmu strojového učení bez dozoru, kde neexistují žádné trénované datové sady. Existuje několik typů klastrových analýz, jedním typem je hierarchické klastrování.

Hierarchické seskupování pomůže při vytváření klastrů ve správném pořadí / hierarchii. Příklad: Nejobvyklejším každodenním příkladem je způsob uspořádání souborů a složek v počítači podle správné hierarchie.

Druhy hierarchického klastru

Hierarchické klastrování je dále rozděleno do dvou typů, tj. Aglomerativní klastrování a dělící klastrování (DIANA)

Aglomerační klastrování

V tomto případě shlukování se hierarchický rozklad provádí pomocí strategie zdola nahoru, kde začíná vytvořením atomových (malých) klastrů přidáním jednoho datového objektu najednou a poté jejich sloučením dohromady, aby se na konci vytvořil velký klastr., kde tento cluster splňuje všechny podmínky ukončení. Tento postup je iterativní, dokud nejsou všechny datové body přeneseny do jednoho velkého klastru.

AGNES (AGglomerative NESting) je typ aglomeračního klastru, který kombinuje datové objekty do klastru na základě podobnosti. Výsledkem tohoto algoritmu je stromová struktura nazvaná Dendrogram. Zde používá metriky vzdálenosti k rozhodnutí, které datové body by měly být kombinovány s kterým klastrem. Sestavuje v zásadě distanční matici a kontroluje pár shluků s nejmenší vzdáleností a kombinuje je.

Výše uvedený obrázek ukazuje shlukování aglomerací vs. dělení

Na základě toho, jak se měří vzdálenost mezi jednotlivými klastry, můžeme mít 3 různé metody

  • Jednoduchá vazba : Kde je nejkratší vzdálenost mezi dvěma body v každém seskupení definována jako vzdálenost mezi shluky.
  • Kompletní propojení : V tomto případě budeme považovat nejdelší vzdálenost mezi body v každém klastru jako vzdálenost mezi klastry.
  • Průměrné propojení: Zde vezmeme průměr mezi každým bodem v jednom klastru na každý druhý bod v jiném klastru.

Nyní pojďme diskutovat o silných a slabých stránkách AGNES; tento algoritmus má časovou složitost alespoň O (n 2 ), proto se mu při škálování nedaří dobře, a další hlavní nevýhodou je, že cokoli, co bylo provedeno, nemůže být nikdy vráceno, tj. pokud nesprávně seskupíme jakýkoli klastr v dřívější fázi algoritmus pak nebudeme moci změnit výsledek / upravit jej. Ale tento algoritmus má také jasnou stránku, protože existuje mnoho menších shluků, které mohou být užitečné v procesu objevování a vytváří uspořádání objektů, které je velmi užitečné při vizualizaci.

Divisive Clustering (DIANA)

Diana v podstatě znamená Divisive Analysis; Toto je další typ hierarchického shlukování, kde v zásadě funguje na principu přístupu shora dolů (inverzní AGNES), kde algoritmus začíná vytvořením velkého shluku a rekurzivně rozdělí nejneobvyklejší shluk na dva a pokračuje, dokud všechny podobné datové body patří do příslušných skupin. Tyto dělicí algoritmy mají za následek vysoce přesné hierarchie než aglomerativní přístup, ale jsou výpočetně nákladné.

Výše uvedený obrázek ukazuje postupný proces dělení klastrů

Vícefázové hierarchické klastry

Abychom zlepšili kvalitu klastrů generovaných výše uvedenými technikami hierarchického klastrování, integrujeme naše hierarchické klastrovací techniky s jinými klastrovacími technikami; to se nazývá vícefázové klastrování. Různé typy vícefázového klastru jsou následující:

  • BIRCH (Vyvážené opakující se redukce a shlukování pomocí hierarchií)
  • ROCK (RObust Clustering pomocí odkazů)
  • CHAMELEÓN

1. Vyvážené opakující se redukce a shlukování pomocí hierarchií

Tato metoda se používá hlavně pro klastrování obrovského množství číselných dat integrací našeho hierarchického / mikro klastrování v počáteční fázi a makro klastrování / iterativní rozdělení v pozdější fázi. Tato metoda pomáhá překonat problém škálovatelnosti, kterému jsme čelili v programu AGNES, a neschopnost vrátit zpět to, co bylo provedeno před krokem. BIRCH používá ve svém algoritmu dva důležité pojmy

A. Clustering feature (Pomáhá při sumarizaci clusteru)

CF je definován jako (n - počet datových bodů v klastru, lineární součet n bodů, druhá mocnina n bodů). Uložení funkce klastru tímto způsobem pomáhá zabránit tomu, aby se o něm ukládaly podrobné informace, a CF je pro různé klastry v podstatě aditivní.

CF 1 + CF 2 = 1+ n 2, LS 1 + LS 2, SS1 + SS2>

b. Strom funkcí clusteru (pomáhá při reprezentaci klastru jako hierarchie)

Strom CF je vyrovnaný strom s větvícím faktorem B (maximální počet dětí) a prahem T (maximální počet podskupin, které lze uložit v uzlech listů).

Algoritmus v zásadě funguje ve 2 fázích; ve fázi 1 prohledává databázi a vytváří strom CF v paměti a ve fázi 2 používá klastrovací algoritmus, který pomáhá při seskupování listových uzlů odstraněním odlehlých hodnot (řídké klastry) a seskupuje klastr s maximální hustotou. Jedinou nevýhodou tohoto algoritmu je to, že zpracovává pouze číselný typ dat.

2. Robustní klastrování pomocí odkazů

Propojení je definováno jako počet společných sousedů mezi dvěma objekty. Algoritmus ROCK je typ shlukového algoritmu, který používá tento koncept spojení s kategorickým datovým souborem. Protože víme, že algoritmy shlukování měřené podle vzdálenosti neposkytují vysoce kvalitní klastry pro kategorický datový soubor, ale v případě ROCK bere v úvahu také sousedství datových bodů, tj. Pokud dva datové body mají stejné sousedství, pak jsou s největší pravděpodobností patří do stejného klastru. Algoritmus vytvoří v prvním kroku řídký graf s přihlédnutím k matici podobnosti s konceptem sousedství a prahem podobnosti. Ve druhém kroku používá aglomerační hierarchickou shlukovou techniku ​​na řídkém grafu.

3. Chameleon

Tento typ hierarchického klastrovacího algoritmu používá koncept dynamického modelování. Zajímá vás, proč se tomu říká dynamický? Říká se tomu dynamika, protože má schopnost se automaticky přizpůsobit charakteristikám interního klastru tím, že vyhodnotí podobnost klastru, tj. Jak dobře jsou propojeny datové body v klastru a v blízkosti klastrů. Jednou z nevýhod chameleonu je, že náklady na zpracování jsou příliš vysoké (O (n 2 ) pro n objekty je nejhorší složitost času).

Zdroj obrázku - Google

Závěr

V tomto článku jsme se dozvěděli, co je klastr a co je klastrová analýza, různé typy hierarchických klastrových technik, jejich výhody a nevýhody. Každá z technik, o nichž jsme hovořili, má své vlastní plus a mínus, proto než budeme pokračovat s algoritmem, musíme porozumět našim datům pomocí správné průzkumné analýzy dat a vybrat algoritmus s opatrností.

Doporučené články

Toto je průvodce hierarchickou klastrovou analýzou. Zde diskutujeme přehled, aglomerační klastrování, dělící klastrování (DIANA) a vícefázové hierarchické klastrování. Další informace naleznete také v následujících článcích

  1. Hierarchické shlukování v R
  2. Clustering Algorithm
  3. shluky
  4. Metody shlukování
  5. Shlukování ve strojovém učení
  6. Hierarchické klastry Aglomerativní a dělící se shlukování

Kategorie:

Velká data