Klasterių analizė

Pasiskirstymu paremta klasterizacija

Labiausiai su statistika susijęs klasterizacijos modelis yra pasiskirstymo modelis. Klasteriai gali būti apibūdinti kaip objektai, kurie priklauso su didžiausia tikimybe tam tikram pasiskirstymui. Patodu yra tai, kad šis metodas labai primena, kaip yra generuojami dirbtiniai duomenų rinkiniai renkant skirtingus bandinius iš to paties pasiskirstymo.
Šių metodų teorinis pagrindimas yra puikus, tačiau jų trūkumas yra tas, kad šie metodai gali būti perdėtai-pritaikyti, nebent pritaikomi sudėtingi ribojimai. Sudėtingesnis modelis dažniausiai geriau paaiškina duomenis, bet pasirinkti tinkamesnį metodą remiantis modelio kompleksiškumu gali būti sudėtinga.
Vienas iš garsiausių metodų yra Gauso maišytumo modelis (naudoja lūkesčių-maksimizavimo algoritmą). Šiuo atveju duomenų rinkinys yra modeliuojamas su nustatytu Gauso pasiskirstymų skaičiumi, kuris yra atsitiktinai inicializuotas, o jo parametrai yra iteraciškai optimizuoti, kad geriau atitiktų duomenų rinkinį. Šie duomenys bus sulietį į lokalų optimumą, todėl skirtingi pakartojmai parodys skirtingus rezultatus. Norint gauti griežtą klasterizaciją, objektai dažniausiai yra priskiriami Gauso skirstiniui, kuriam objektai priklauso su didžiausia tikimybe, o atliekant negriežtą pasiskirstymą, priskyrimas klasteriui nėra būtinas.
Pasiskirstymu paremta klasterizacija paruošia sudėtingus modelius, kur klasteriai gali turėti koreliaciją ir priklausomybes tarp skirtingų narių. Tačiau, šie algoritmai apsunkina vartotojus: realiems duomenų rinkiniams dažniausiai nėra tvirto matematinio modelio (pavyzdžiui, Gauso pasiskirstymas gali būti traktuojamas kaip tvirta duomenų prielaida).

Tankiu-paremta klasterizacija

Tankiu paremtoje klasterizacijoje, klasteriais yra laikomos sritys, kuriose yra tankiau išsidėstę duomenų rinkinio objektai. Objektai, kurie išsidėstę erdvėje tarp klasterių yra laikomi triukšmu.
Žinomiausias tankiu paremtos klasterizacijos metodas yra DBSCAN. Lyginant su naujesniais metodais, pastarasis turi gerai apibrėžtą klasterių modelį, kuris vadinamas „tankio-pasiekiamumu“. Taip pat kaip ir jungtimis paremta klasterizacija, ji yra paremta atstumo slenksčiu tarp dviejų taškų. Tačiau, šis metodas sujungia tik taškus, kurie tenkina tankio kriterijų, kuris originialiame variante apibrėžiamas kaip objektų skaičius tam tikro spindulio plote. Klasteris susideda iš visų sujungtų tankių sričių su objektais objektų (kurie gali suformuoti atitinkamos formos klasterį lyginant su kitais metodais). Kita įdomi DBSCAN savybė yra ta, kad šios klasterizacijos sudėtingumas yra pakankamai žemas skirtingiems pakartojimams, todėl nereikia klasterizacijų atlikti keletą kartų. OPTICS yra DBSCAN apibendrinimas ir nereikalauja parametro vertės  parinkimo, todėl pateikia hierarchinį rezultatą panašų į tą, kurį pateikia hierarchinė klasterizacija. DeLi-Clu, tankio-jungčių-klasterizacija sujungia idėjas iš vienos-jungties klasterizacijs ir OPTICS, todėl pašalinamas  parametras visiškai ir gaunami aukštesnės kokybės rezultatai lyginant su OPTICS ir naudojant R-tree indeksą.
Pagrindiniai DBSCAN ir OPTICS yra tie, kad jie tikisi „rasti“ tam tikrą tankio sumažėjimą ties klasterio riba. Taip pat jie negali aptikti vidinių klasterių struktūrų, kurios dažniausiai yra stebimos realiuose duomenyse. DBSCAN variantas yra EnDBSCAN, kuris efektyviai aptinka tokio tipo struktūras. Duomenų rinkiniams, kurie yra persidengiantys Gauso pasiskirstymai – dažniausiai naudojamas dirbtiniams duomenims, todėl klasterio ribos atrodo dirbtinai, nes klasterio tankis mažesnis pakraščiuose. Duomenims, kurie sudaryti iš Gauso mišinių ir apdoroti minėtais algoritmais, praktiškai visada yra prastesnės kokybės, nei duomenis apdorojus EM klasterizacijos metodais, kurie yra sukurti modeliuoti būtent tokiems duomenims.
Vidurkių-poslinkis klasterizacijos traktavimas, kur objektai yra pastumiami link tankesnių plotų ir paremti branduolių tankio paskaičiavimu. Objektai yra suliejami į lokalinius tankio maksimumus. Taip pat kaip ir k-vidurkių klasterizacija, šie „tankio pritraukikliai“ gali pateikti duomenų rinkinius, bet vidurkių-poslinkis gali aptikti tam tikrų formų k; lasterius, panašiai kaip ir DBSCAN. Dėl daug resursų reikalaujančių iteracinių procedūrų, vidurkių-poslinkis yra lėtesnis nei DBSCAN, ar k-Vidurkių metodai.

Pastarųjų metų tobulinimas

Per pastaruosius metus buvo įdėta nemažai pastangų tobulinant esamus algoritmus. Iš minimų yra CLARANS (Ng ir Han, 1994), ir BIRCH (Zhang ir kiti, 1996). Esant poreikiui apdoroti vis didesnius duomenų kiekius(dideli duomenys), vis labiau yra vystomi būdai, kaip apdorojant duomenis gauti geresnes charakteristikas, o ne semantinę reikšmę. Visa tai privedė prie pre-klasterizacijos (paviršutinė klasterizacija, kuri gali apdoroti didžiulius duomenų kiekius efektyviai, bet gauti duomenys yra dalinai padalinti duomenų rinkiniai iš kurių atliekama tolimesnė analizė naudojant lėtesnius metodus, tokius kaip k-vidurkių klasterizacija. Skirtingos klasterizacijos buvo pritaikytos, pavyzdžiui pradžia-paremta klasterizacija.
Daugiamačiams duomenims, dauguma metodų yra neįgalūs dėl daugiadimensiškumo, kuris sukelia problemų skaičiuojant atstumus tarp skirtingų dimensijų erdvių. Buvo sukurti nauji algoritmai Daugiamačių duomenų klasterizacijos algoritmai, kurie sutelkia dėmesį į poerdvių klasterizaciją (kur tik kai kurie parametrai yra panaudojami, o klasterių modeliai turi tik svarbius požymius) ir koreliacijos klasterizaciją, kuri atrodo atitinkamai pasuktas („koreliuotas“) poerdvio klasteris, kurį galima sumodeliuoti naudojant požymių koreliaciją. Pavyzdžiai: CLIQUE ir SUBCLU.
Idėjos iš tankiu-paremtų klasterizacijos metodų buvo pritaikytos (ypač iš DBSCAN/OPTICS šeimos algoritmų) poerdvių klasterizacijai (HiSC, hierarchinė poerdvių klasterizacija ir DiSH) ir koreliacijos klasterizacija (HiCO, hierarchinė klasterizacijos klasterizacija, 4C naudojant „koreliacijos jungtis“ ir ERiC tyrinėjant hierarchinius tankiu-paremtus koreliacijos klasterius).
Buvo pasiūlytos kelios klasterizacijos sistemos, kurios remiasi abipuse informacija. Marina Meilă's informacijos variacija;, kitas – hierarchinė klasterizacija. Naudojant genetinius algoritmus, daug skirtingų priklausomybės funkcijų gali būti optimizuota, taip pat ir abipusė informacija. Be to, žinios perdavimo algoritmas, naujas Kompiuterių mokslo ir Statistinės fizikos patobulinimas, leido sukurti naujų naujo tipo algoritmų.

Analizė ir įvertinimas

Klasterizacijos įvertinimas yra dar kitaip vadinama klasterių validacija.
Yra keletas patarimų, kaip pamatuoti panašumus tarp dviejų klasterių. Toks įvertis gali būti pritaikytas pamatavimui, kaip gerai skirtingi algoritmai klasterizuoja duomenų rinkinius. Šie matavimai dažniausiai yra pririšti prie tam tikro kriterijaus tipo, kuris apsprendžia klasterizacijos metodo kokybę.