Grupiranje

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

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

Algoritmi u grupiranju podataka mogu biti 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

Uvod

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

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

k-sredine i derivacije

Grupiranje k-sredina

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 = (x₁, x₂, x₃) i Y = (y₁, y₂, y₃). Tada centroid Z postaje Z = (z₁, z₂, z₃), gdje z₁ = (x₁ + y₁)/2 and z₂ = (x₂ + y₂)/2 and z₃ = (x₃ + y₃)/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

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

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.

S 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$ $\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

Biologija

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

U transkriptomici se grupiranje koristi za izgradnju grupe gena sa srodnim izražajnim obrascima. Često takve grupe sadrže funkcionalno srodne proteine poput enzima za određenu stazu ili gena koji su koregulirani. Visoki protočni elementi upotrebom izražajnih sekvencijalnih oznaka (ISO-i) ili DNA mikroredova mogu biti snažni alati za bilježenje genoma odnosno generalnog aspekta genomike.
U sekvencijalnoj analizi se grupiranje koristi za povezivanje homolognih sekvenca u obitelji gena. To je vrlo važan koncept u bioinformatici i općenito u evolucijskoj biologiji. Vidi evolucija genskom duplikacijom.

Tržišno istraživanje

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 razumjeli odnose između različitih grupa potrošača/mogućih potrošača.

Segmentiranje tržišta i određivanje tržišnih ciljeva
Smještanje proizvoda
Razvoj novih proizvoda
Odabiranje ispitnih tržišta (vidi : eksperimentalne tehnike)

Usporedbe među grupiranjima podataka

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 B_k veličine.

Više informacija