Prehľad hierarchickej klastrovej analýzy
Skôr ako sa pustíme do porozumenia hierarchickej klastrovej analýze, najprv sa pokúsime pochopiť, čo je klaster? A čo je klastrová analýza? Klaster je kolekcia dátových objektov; dátové body v klastri sú si navzájom viac podobné a odlišné od dátových bodov v inom klastri. Zhluková analýza je v podstate zoskupením týchto údajových bodov do zoskupenia. Zhlukovanie je typ algoritmu strojového učenia bez dozoru, v ktorom nie sú žiadne školené súbory údajov. Existuje niekoľko typov klastrových analýz, jedným takýmto typom je hierarchické klastrovanie.
Hierarchické zoskupovanie pomôže pri vytváraní zoskupení v správnom poradí / hierarchii. Príklad: Najbežnejším každodenným príkladom je spôsob objednávania súborov a priečinkov v počítači podľa správnej hierarchie.
Druhy hierarchického zoskupovania
Hierarchické zoskupovanie sa ďalej delí na dva typy, tj aglomeračné zoskupovanie a deliace zoskupovanie (DIANA).
Aglomeračné zoskupovanie
V tomto prípade zoskupovania sa hierarchický rozklad uskutočňuje pomocou stratégie zdola nahor, kde sa začína vytváraním atómových (malých) zhlukov pridávaním jedného údajového objektu po druhom a následným zlúčením ich dohromady, aby sa na konci vytvoril veľký zhluk., ak tento klaster spĺňa všetky podmienky ukončenia. Tento postup je opakovaný, kým sa všetky dátové body neprenesú do jedného veľkého klastra.
AGNES (AGglomerative NESting) je typ aglomeračného zoskupovania, ktorý kombinuje dátové objekty do zoskupenia na základe podobnosti. Výsledkom tohto algoritmu je stromová štruktúra nazývaná Dendrogram. Tu používa metriky vzdialenosti na rozhodovanie, ktoré údajové body by sa mali kombinovať s ktorým zoskupením. V zásade zostavuje dištančnú maticu a kontroluje pár klastrov s najmenšou vzdialenosťou a kombinuje ich.
Vyššie uvedený obrázok ukazuje zhlukovanie aglomerácií verzus delenie
Na základe toho, ako sa meria vzdialenosť medzi každým zoskupením, môžeme mať 3 rôzne metódy
- Jednoduché spojenie : Ak je najkratšia vzdialenosť medzi dvoma bodmi v každom zoskupení definovaná ako vzdialenosť medzi zoskupeniami.
- Kompletné spojenie : V tomto prípade budeme považovať najdlhšiu vzdialenosť medzi bodmi v každom zoskupení ako vzdialenosť medzi zoskupeniami.
- Priemerná väzba: Tu vezmeme priemer medzi každým bodom v jednom zoskupení do každého druhého bodu v druhom zoskupení.
Teraz diskutujme o silných a slabých stránkach AGNES; tento algoritmus má časovú zložitosť najmenej O (n 2 ), preto pri škálovaní nefunguje dobre, a ďalšou významnou nevýhodou je to, že čokoľvek, čo sa stalo, sa nedá nikdy vrátiť späť, tj ak nesprávne zoskupíme akýkoľvek klaster v skoršom štádiu algoritmus potom nebudeme môcť zmeniť výsledok / ho zmeniť. Ale tento algoritmus má aj svetlú stránku, pretože existuje veľa menších zhlukov, ktoré môžu byť užitočné v procese objavovania a vytvára usporiadanie objektov, ktoré je veľmi užitočné pri vizualizácii.
Divisive Clustering (DIANA)
Diana v podstate znamená Divisive Analysis; Toto je ďalší typ hierarchického zoskupovania, kde v zásade funguje na princípe prístupu zhora nadol (inverzia AGNES), kde algoritmus začína vytvorením veľkého zoskupenia a rekurzívne rozdeľuje najviac nepodobný klaster na dva a pokračuje, kým ' všetky podobné údajové body patria do príslušných zhlukov. Tieto deliace algoritmy vedú k vysoko presným hierarchiám ako aglomeračný prístup, ale sú výpočtovo drahé.
Vyššie uvedený obrázok ukazuje postupný proces delenia zhlukov
Viacfázové hierarchické zoskupovanie
Aby sme zlepšili kvalitu klastrov generovaných vyššie uvedenými technikami hierarchického klastrovania, integrujeme naše hierarchické klastrovacie techniky s inými technikami klastrovania; nazýva sa to viacfázové zoskupovanie. Rôzne typy viacfázového klastrovania sú nasledujúce:
- BIRCH (Vyvážené opakované zníženie a zhlukovanie pomocou hierarchií)
- ROCK (RObust Clustering pomocou odkazov)
- CHAMELEON
1. Vyvážené opakované zníženie a zhlukovanie pomocou hierarchií
Táto metóda sa používa hlavne na zoskupovanie obrovského množstva číselných údajov integráciou nášho hierarchického / mikro zoskupovania v počiatočnej fáze a do makra zoskupovania / iteračného rozdelenia v neskoršej fáze. Táto metóda pomáha pri prekonávaní problému škálovateľnosti, ktorému čelíme v programe AGNES, a neschopnosti vrátiť späť to, čo sa urobilo pred krokom. BIRCH používa vo svojom algoritme dva dôležité pojmy
a. Funkcia klastrovania (pomáha pri zhrnutí klastra)
CF je definovaná ako (n - počet údajových bodov v zoskupení, lineárny súčet n bodov, druhá mocnina n bodov). Uloženie funkcie klastra týmto spôsobom pomáha zabrániť tomu, aby sa o ňom ukladali podrobné informácie, a CF má v rôznych klastroch povahu aditíva.
CF1 + CF2 =
b. Strom funkcií klastra (pomáha pri reprezentácii klastra ako hierarchie)
Strom CF je vyvážený strom s vetviacim faktorom B (maximálny počet detí) a prahom T (maximálny počet podskupín, ktoré je možné uložiť v uzloch listov).
Algoritmus v zásade funguje v 2 fázach; vo fáze 1 prehľadáva databázu a vytvára strom CF v pamäti a vo fáze 2 používa klastrovací algoritmus, ktorý pomáha pri zoskupovaní listových uzlov odstránením odľahlých hodnôt (riedke zhluky) a zoskupuje klaster s maximálnou hustotou. Jedinou nevýhodou tohto algoritmu je to, že spracúva iba číselný typ údajov.
2. Robustné zoskupovanie pomocou odkazov
Spojenie je definované ako počet bežných susedov medzi dvoma objektmi. Algoritmus ROCK je typ algoritmu zoskupovania, ktorý používa tento koncept prepojenia s kategorickým súborom údajov. Pretože vieme, že algoritmy zoskupovania na meranie vzdialenosti neposkytujú vysokokvalitné klastre pre kategorický súbor údajov, ale v prípade ROCK sa prihliada aj na susedstvá údajových bodov, tj ak dva dátové body majú rovnaké okolie, potom sú s najväčšou pravdepodobnosťou patria do toho istého klastra. Algoritmus v prvom kroku skonštruuje riedky graf s prihliadnutím na maticu podobnosti s konceptom susedstva a prahu podobnosti. V druhom kroku sa na riedkeho grafu používa aglomeračná hierarchická technika zoskupovania.
3. Chameleón
Tento typ hierarchického klastrovacieho algoritmu využíva koncepciu dynamického modelovania. Zaujíma vás, prečo sa to nazýva dynamické? Nazýva sa to dynamická, pretože má schopnosť sa automaticky prispôsobiť charakteristikám vnútorného klastra vyhodnotením podobnosti klastra, tj ako dobre sú prepojené dátové body v rámci klastra a v blízkosti klastrov. Jednou z nevýhod chameleónu je, že náklady na spracovanie sú príliš vysoké (O (n 2 ) pre n objekty je najhoršia časová zložitosť).
Zdroj obrázka - Google
záver
V tomto článku sme sa dozvedeli, čo je klaster a čo je klastrová analýza, rôzne typy hierarchických klastrových techník, ich výhody a nevýhody. Každá z techník, ktoré sme prediskutovali, má svoje plus a mínus, preto predtým, ako začneme s algoritmom, musíme porozumieť našim údajom pomocou správnej prieskumnej analýzy údajov a vybrať algoritmus s opatrnosťou.
Odporúčané články
Toto je sprievodca analýzou hierarchického klastra. Tu diskutujeme prehľad, aglomeračné zhlukovanie, deliace sa zhlukovanie (DIANA) a viacfázové hierarchické zhlukovanie. Viac informácií nájdete aj v nasledujúcich článkoch
- Hierarchické zoskupovanie v R.
- Clustering Algorithm
- klastre
- Metódy zhlukovania
- Klastrovanie v strojovom učení
- Hierarchické zoskupovanie Aglomeračné a deliace sa zoskupovanie