Pregled hijerarhijske analize klasteriranja

Prije nego što nastavimo i razumijemo hijerarhijsku analizu klastera, pokušajmo shvatiti što je klaster? A što je analiza klastera? Klaster je zbirka podataka podataka; podatkovne točke unutar klastera slične su jedna drugoj i razlikuju se od podataka u drugom klasteru. Analiza klastera u osnovi je grupiranje ovih podataka u skupinu. Klasteriranje je vrsta algoritma strojnog učenja bez nadzora, gdje ne postoje skupovi podataka s oznakom treninga. Postoje različite vrste analiza klastera, jedna takva vrsta je hijerarhijsko grupiranje.

Hijerarhijsko grupiranje pomoći će u stvaranju klastera pravilnim redoslijedom / hijerarhijom. Primjer: najčešći svakodnevni primjer koji vidimo je kako naručimo datoteke i mape na našem računalu pravilnom hijerarhijom.

Vrste hijerarhijskih klastera

Hijerarhijsko grupiranje dalje je klasificirano u dvije vrste, tj. Aglomeracijsko grupiranje i Divisivno grupiranje (DIANA)

Aglomerativno grupiranje

U ovom slučaju klasteriranja, hijerarhijska dekompozicija vrši se uz pomoć strategije odozdo prema gore, gdje započinje stvaranjem atomskih (malih) klastera dodavanjem jednog podatka objekta, a zatim ih spaja zajedno kako bi stvorio veliki klaster na kraju, gdje ovaj klaster ispunjava sve uvjete zaustavljanja. Ovaj je postupak iterativan sve dok se sve podatkovne točke ne dovedu pod jedan veliki skup.

AGNES (AGglomerative NESting) je vrsta aglomerativnog grupiranja koja kombinira podatkovne objekte u klaster na temelju sličnosti. Rezultat ovog algoritma je stablo temeljeno na strukturi zvanoj Dendrogram. Ovdje koristi metriku udaljenosti da odluči koje podatkovne točke treba kombinirati s kojim klasterom. U osnovi, ona konstruira matricu udaljenosti i provjerava za par klastera s najmanjom udaljenošću i kombinira ih.

Na gornjoj slici prikazano je aglomerativno nasuprot razdjelnom grupiranju

Na osnovu kako se mjeri udaljenost između svih klastera možemo imati 3 različite metode

  • Pojedinačna veza : Gdje je najkraća udaljenost između dviju točaka u svakom klasteru definirana kao udaljenost između klastera.
  • Kompletna povezanost : U ovom ćemo slučaju najdužu udaljenost između točaka u svakom klasteru smatrati udaljenostima između klastera.
  • Prosječno povezivanje: Ovdje ćemo uzeti prosjek između svake točke u jednom klasteru do svake druge točke u drugom klasteru.

Sada razgovarajmo o jakim i slabostima u AGNES-u; ovaj algoritam ima vremensku složenost od najmanje O (n 2 ), stoga ne djeluje dobro u skaliranju, a još jedan veliki nedostatak je da sve što je učinjeno nikada ne možemo poništiti, tj. ako pogrešno grupiramo bilo koji klaster u ranijoj fazi algoritam tada nećemo moći promijeniti rezultat / modificirati ga. No ovaj algoritam ima i svijetlu stranu, jer postoji mnogo manjih klastera koji mogu biti korisni u procesu otkrivanja i stvara redoslijed predmeta koji su vrlo korisni u vizualizaciji.

Podjela klastera (DIANA)

Diana u osnovi stoji za Divisive Analysis; ovo je druga vrsta hijerarhijskog grupiranja gdje u osnovi djeluje na principu pristupa odozgo prema dolje (obrnuto od AGNES-a) gdje algoritam započinje formiranjem velikog klastera i on rekurzivno dijeli najrazličitiji klaster na dva i nastavlja se dok ne ' ponovo sve slične podatkovne točke pripadaju u njihove klastere. Ovi algoritmi za podjelu rezultiraju visoko preciznim hijerarhijama nego aglomerativnim pristupom, ali računski su skupi.

Gornja slika prikazuje podjela po korak po korak

Višefazno hijerarhijsko klasteriranje

Da bismo poboljšali kvalitetu klastera generiranih gore spomenutim hijerarhijskim tehnikama klasteriranja, integriramo naše hijerarhijske tehnike grupiranja s drugim tehnikama klasteriranja; to se naziva višefazno grupiranje. Različite vrste klastera u više faza su sljedeće:

  • BIRCH (uravnoteženo iterativno smanjivanje i klasteriranje pomoću hijerarhije)
  • ROCK (klasteriranje RObust pomoću veza)
  • KAMELEON

1. Uravnoteženo iterativno smanjivanje i klasteriranje pomoću hijerarhije

Ova metoda se uglavnom koristi za grupiranje ogromne količine numeričkih podataka integrirajući naše hijerarhijsko / mikro grupiranje u početnoj fazi i makro grupiranje / iterativno particioniranje u kasnijoj fazi. Ova metoda pomaže u prevladavanju problema s skalabilnošću s kojim smo se suočili u AGNES-u i nemogućnosti poništenja onoga što je učinjeno prije koraka. BIRCH koristi dva važna koncepta u svom algoritmu

a. Karakterizacija klastera (Pomaže pri sažimanju klastera)

CF je definiran kao (n- broj podatkovnih točaka u klasteru, linearni zbroj n točaka, kvadratni zbroj n bodova). Spremanje značajki klastera na ovaj način pomaže u izbjegavanju pohrane detaljnih informacija o njemu, a CF je po svojoj naravi aditivan za različite klastere.

CF1 + CF2 = 1+ n 2, LS 1 + LS 2, SS 1 + SS 2 >

b. Stablo značajki klastera (pomaže u predstavljanju klastera kao hijerarhije)

CF stablo je uravnoteženo stablo s faktorom grananja B (maksimalni broj djece) i pragom T (maks. Broj potklastera koji se mogu pohraniti u listove čvorove).

Algoritam u osnovi djeluje u 2 faze; u fazi 1 skenira bazu podataka i gradi CF stablo memorije, a u fazi 2 koristi algoritam klasteriranja koji pomaže u grupiranju lisnih čvorova uklanjanjem odljevaka (rijetkih klastera) i grupiranje klastera s maksimalnom gustoćom. Jedini nedostatak ovog algoritma je taj što on upravlja samo numeričkim tipom podataka.

2. Čvrsto grupiranje pomoću linkova

Veza se definira kao broj zajedničkih susjeda između dva objekta. ROCK algoritam je vrsta algoritma grupiranja koji koristi ovaj koncept povezivanja s kategorijskim podacima. Kao što znamo da algoritmi klasteriranja izmjerenih na daljinu ne pružaju visokokvalitetne klastere za kategorijski skup podataka, ali u slučaju ROCK uzima u obzir i susjedstvo podatkovnih točaka, tj. Ako dvije podatkovne točke imaju isto susjedstvo, tada su najvjerojatnije pripadaju istom klasteru. Algoritam će u prvom koraku konstruirati rijetki graf uzimajući u obzir matricu sličnosti s konceptom susjedstva i praga sličnosti. U drugom koraku koristi aglomerativnu hijerarhijsku tehniku ​​grupiranja na rijetkom grafu.

3. kameleon

Ova vrsta algoritma hijerarhijskog grupiranja koristi koncept dinamičkog modeliranja. Pitate se zašto se to zove dinamično? Zove se dinamičnim jer ima mogućnost automatske prilagodbe unutarnjim karakteristikama klastera procjenjujući sličnost klastera, tj. Koliko su dobro povezane podatkovne točke unutar klastera i u blizini klastera. Jedan od nedostataka kameleona je taj što je trošak obrade previsok (O (n 2 ) za n objekata je najgora vremenska složenost).

Izvor slike - Google

Zaključak

U ovom smo članku naučili što je klaster, a što analiza klastera, različite vrste hijerarhijskih tehnika grupiranja, njihove prednosti i mane. Svaka od tehnika o kojima smo razgovarali ima svoj plus i minus, stoga prije nego što nastavimo s algoritmom trebamo razumjeti naše podatke pravilnom analizom podataka istraživača i odabrati algoritam s oprezom.

Preporučeni članci

Ovo je vodič za Hijerarhijsku analizu klastera. Ovdje ćemo raspravljati o pregledu, aglomeracijskom grupiranju, podjelama klastera (DIANA) i višefaznim hijerarhijskim grupiranjem. Možete pogledati i sljedeće članke da biste saznali više

  1. Hijerarhijsko klasteriranje u R
  2. Algoritam klastera
  3. klasteri
  4. Metode klasteriranja
  5. Klasteriranje u strojnom učenju
  6. Hijerarhijsko grupiranje | Aglomerativno i podjeljeno grupiranje

Kategorija:

Veliki podaci