Grupiranje

Izvor: Wikipedija
Skoči na: orijentacija, traži

Grupiranje podataka je uobičajena tehnika za analizu statističkih podataka, koja se koristi u mnogim područjima, uključujući strojno učenje, podatkovno rudarstvo, prepoznavanje obrazaca, slikovnu analizu i bioinformatiku. Grupiranje je klasifikacija sličnih predmeta u različite grupe, ili preciznije, dijeljenje skupa podataka u podskupove (grupe) tako da podaci u svakom podskupu (idealno) dijele neko zajedničko obilježje - često približnost prema nekoj definiranoj veličini udaljenosti.

Strojno učenje se tipično odnosi prema grupiranju podataka kao obliku nenadziranog učenja.

Ostali nazivi[uredi VE | uredi]

Osim naziva grupiranje podataka (ili samo grupiranje), postoje brojni nazivi sa sličnim značenjem kao što su grupna analiza, automatska klasifikacija, numerička taksonomija, botriologija i tipološka analiza.

Vrste grupiranja[uredi VE | uredi]

Algoritmi u grupiranju podataka mogu biti [[hijerarhija|hijerarhijski ili particionalni. S hijerarhijskim algoritmima neprekinute grupe se pronalaze upotrebom prijašnjih uspostavljenih grupa, tj. ondje gdje particionalni algoritmi određuju sve grupe u jednom hodu. Hijerarhijski algoritmi mogu biti aglomerativni (dnom prema gore) ili divizivni (vrhom prema dolje). Aglomerativni algoritmi počinju sa svakim elementom kao odvojenom grupom te ih spajaju u neprekinuto velike grupe. Divizivni algoritmi počinju s čitavim skupom i nastavljaju ga dijeliti u neprekinuto malene grupe.

Hijerarhijsko grupiranje[uredi VE | uredi]

Uvod[uredi VE | uredi]

Hijerarhijsko grupiranje gradi (aglomeracijske) ili prekida (divizivne) hijerarhiju grupa. Tradicionalni prikaz ove hijerarhije je stablo s individualnim elementima na jednom te pojedinačnom grupom sa svim elementima na drugom kraju. Aglomeracijski algoritmi počinju na vrhu stabla, dok divizivni algoritmi počinju na njegovom dnu. (U figuri strelice označavaju aglomeracijsko grupiranje.)

Sječenjem stabla na danoj visini daje grupiranje u odabranoj preciznosti. U gornjem primjeru sječenje daje nakon drugog reda grupe {a} {b c} {d e} {f}. Sječenje nakon trećeg reda daje grupe {a} {b c} {d e f}, što je zapravo grubo grupiranje s manjim brojem većih grupa.

Aglomerativno hijerarhijsko grupiranje[uredi VE | uredi]

Tradicionalni prikaz

Ova metoda gradi hijerarhiju iz individualnih elemenata naprednim spajanjem grupa. Opet je prisutno šest elemenata {a} {b} {c} {d} {e} i {f}. Prvi korak je određivanje elemenata koji se trebaju spojiti u grupu. Obično se žele uzeti dva najbliža elementa, pa stoga treba definirati udaljenost d(\mathrm{element}_1,\mathrm{element}_2) između elemenata.

Pretpostavimo da su se spojili dva najbliža elementa b i c, te su ostale sljedeće grupe {a}, {b, c}, {d}, {e} i {f} koje se žele spajati dalje. Da se to napravi, treba uzeti udaljenost između {a} i {b c}, te stoga definirati udaljenost između dvije grupe. Obično udaljenost između dvije grupe \mathcal{A} i \mathcal{B} je jedna od sljedećih:

  • najveća udaljenost između elemenata svake grupe (također nazvana potpuno vezno grupiranje)  \max_{x \in \mathcal{A},\, y \in \mathcal{B}} d(x,y)
  • najmanja udaljenost između elemenata svake grupe (također nazvana pojedinačno vezno grupiranje)  \min_{x \in \mathcal{A},\, y \in \mathcal{B}} d(x,y)
  • srednja udaljenost između elemenata svake grupe (također nazvana prosječno vezno grupiranje)  {1 \over {\mathrm{card}(\mathcal{A})\mathrm{card}(\mathcal{B})}}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y)
  • zbroj različitosti svih međugrupa

povećanje u različitosti za grupu koja se spaja (Wardov kriterij)

Svaka aglomeracija se pojavljuje na većoj udaljenosti između grupa od prethodne aglomeracije i jedna može odlučiti zaustaviti grupiranje ili ako su grupe predaleko odvojene da se spoje (kriterij udaljenosti) ili ako postoji dovoljno mali broj grupa (kriterij brojčanosti).

Dijelno grupiranje[uredi VE | uredi]

k-sredine i derivacije[uredi VE | uredi]

Grupiranje k-sredina[uredi VE | uredi]

Algoritam k-sredine dodjeljuje svaku točku grupi čiji je centar (ili centroid) najbliži. Centroid je točka stvorena računanjem aritmetičke sredine za svaku dimenziju odvojeno za sve točke u grupi.

Primjer: Skup podataka ima tri dimenzije, a grupa ima dvije točke: X = (x1, x2, x3) i Y = (y1, y2, y3). Tada centroid Z postaje Z = (z1, z2, z3), gdje z1 = (x1 + y1)/2 and z2 = (x2 + y2)/2 and z3 = (x3 + y3)/2

Ovo je osnovna struktura algoritma (J. MacQueen, 1967.):

  • Nasumično stvaranje k grupa i određivanje središta grupa ili izravno stvaranje k početnih točaka kao središtâ grupe.
  • Dodijeljivanje svake točke središtu najbliže grupe.
  • Ponovno izračunavanje središta novih grupa.
  • Ponavljanje svega dok se neki kriterij konvergencije ne sretne (obično da se dodjeljivanje nije promijenilo.)

Glavne prednosti ovog algoritma su njegova jednostavnost i brzina koja mu dopušta izvođenje na velikim skupovima podataka. Već sustavno ne daje isti rezultat sa savakim novim radom algoritma. Rezultirajuće grupe radije ovise o početnim dodijeljivanjima. Algoritam k-sredina pojačava (ili smanjuje) različitost međugrupa, ali ne osigurava da dano rješenje nije lokalni minimum različitosti.

QT Clust algoritam[uredi VE | uredi]

QT Clust (Heyer et al, 1999.) je alternativna metoda razdiobe podataka koja ne zahtijeva a priori imenovanje broja grupa. Prvo se gradi kandidatna grupa za svaku kao i za pojedinu točku uključivanjem najbliže točke, sljedeće najbliže, i tako dalje, sve dok se ne dosegne prag udaljenosti. Udaljenost između točke i grupe točaka se izračunava upotrebom potpune povezanosti, tj. kao najveća udaljenost od točke do svih članova grupe. Kandidatna grupa s najviše točaka se sprema kao prva prava grupa, a sve se točke u grupi uklanjaju iz daljnjeg razmatranja. Algoritam ponovo susreće, ponavljajući proces s reduciranim skupom točaka podataka.

Raspršeno grupiranje c-sredina[uredi VE | uredi]

Jedan od problema algoritma k-sredina je da daje grubo razdijeljivanje podataka, tj. svaka je točka pridodana jednoj i samo jednoj grupi. Ali točaka na rubu grupe ili blizu druge grupe ne mora biti jednako mnogo u grupi kao točaka u središtu grupe.

Stoga u raspršenom grupiranju svaka se točka ne zadržava u danoj grupi, ali ima stupanj pripadnosti određenoj grupi kao i u difuzivnoj logici. Za svaku točku x postoji koeficijent koji daje stupanj pripadnosti k-toj grupi u_k(x). Obično zbroj tih koeficijenata mora biti jedan tako da u_k(x) označuje vjerojatnost pripadanja određenoj grupi:

 \forall x \sum_{k=1}^{\mathrm{num.}\ \mathrm{clusters}} u_k(x) \ =1.

Sa raspršenim c-sredinama centroid grupe se izračunava kao sredina svih točaka s težinom na njihovom stupnju pripadnosti grupi, to jest

\mathrm{center}_k = {{\sum_x u_k(x) x} \over {\sum_x u_k(x)}}.

Stupanj pripadnosti određenoj grupi je obrnut udaljenosti od grupe

u_k(x) = {1 \over d(\mathrm{center}_k,x)},

Onda se koeficijenti normaliziraju i zapliću s realnim parametrom m>1 tako da je njihov zbroj 1. Dakle u_k(x) = \frac{1}{\sum_j \left(\frac{d(\mathrm{center}_k,x)}{d(\mathrm{center}_j,x)}\right)^{\frac{1}{m-1}}}

Algoritam raspršenih c-sredine je uvelike sličan algoritmu k-sredina; kada je m\leftarrow 1, algoritmi su jednaki:

  • Odabere se broj grupa
  • Dodijeli se nasumice svakoj točki koeficijente za pripadnost grupama
  • Ponavlja se sve dok algoritam nije konvergirao (to jest, koeficijentska promjena između dva ponavljanja nije veća od \epsilon, dani prag osjetljivosti):
    • Izračuna se centroid za svaku grupu upotrebom gornje formule
    • Za svaku se točku izračunaju njeni koeficijenti pripadnosti grupama upotrebom gornje formule

Algoritam raspršenih c-sredina jednako smanjuje međugrupnu različitost, ali ima iste probleme kao k-sredine, minimum je lokalni minimum, a rezultati ovise o početnom odabiru težina.

Primjene[uredi VE | uredi]

Biologija[uredi VE | uredi]

U biologiji ima dvije glavne primjene u poljima računalne biologije i bioinformatike.

Tržišno istraživanje[uredi VE | uredi]

Grupna analiza se široko koristi u tržišnom istraživanju kada se radi s mnogostruko promjenjivim podacima iz anketa i upitnika. Tržišni istraživači koriste metode grupne analize kako bi razdijelili opću populaciju potrošača u tržišne segmente i kako bi bolje razumijeli odnose između različitih grupa potrošača/mogućih potrošača.

Usporedbe među grupiranjima podataka[uredi VE | uredi]

Do sada je predloženo nekoliko načina za veličinu sličnosti među dvama grupiranjima. Takva veličina se može koristiti za uspoređivanje kako se algoritmi grupiranja dosta različitih podaka izvode na skupu podataka. Mnoga od tih veličina se izvode iz združene matrice (alias zbrkovita matrica), npr. Randova veličina i Fowlkes-Mallowsove Bk veličine.

Više informacija[uredi VE | uredi]