Klasterių analizė

Klasterių analizė, arba klasterizacija yra viena iš tam tikrų objektų rinkinių grupavimo užduočių. Objektai toje pačioje grupėje (dar kitaip vadinama – klasteriu) yra panašesni vienas į kitą negu objektai tarp skirtingų grupių (klasterių). Tai yra pagrindinė duomenų išgavimo, užduotis ir pagrindinė technika atliekant statistinę duomenų analizę, taip pat yra vartojama daugybėje kitų sričių: mašininiame mokyme, atpažinimo teorijoje, vaizdų analizėje, informacijos paieškoje, bioinformatikoje, duomenų suspaudime, ir kompiuterinėje grafikoje.

Pati klasterių analizė nėra specifinis algoritmas, bet gali būti vadinama paprasta užduotimi, kurią reikia išspręsti. Konkrečią užduotį galima išspręsti į pagalbą pasitelkiant skirtingus algoritmus, kurie iš esmės skiriasi supratimu, kas sudaro klasterį ir kaip efektyviai juos surasti. Įprastu supratimu, klasterius sudaro grupės, tarp kurios narių yra nedideli atstumai tankūs duomenų erdvės plotai, intervalai, ar tam tikri statistiniai pasiskirstymai. Klasterių skirstymas gali būti suformuluotas kaip skirtingų užduočių optimizavimo problema. Tam tikras klasterių skirstymo algoritmas ir parametrų nustatymai (įskaitant tokias reikšmės kaip atstumo funkcija  tankio riba, ar numatomų klasterių skaičius) priklauso nuo individualių duomenų rinkinio ir numatomo rezultatų panaudojimo. Klasterių analizė nėra automatinė užduotis, bet pasikartojantis žinių atradimo procesas, ar pasikartojantis skirtingų užduočių optimizavimas, kuriam priklauso bandymai ir nesėkmės. Dažnai tenka koreguoti pirminį duomenų apdorojimą, ar modelio parametrus tam, kad būtų gautas reikalavimus tenkinantis rezultatas.

Be termino klasterizacija, dar yra ir kitų terminų, kurie reiškia tą patį: automatinė clasifikacija, skaitinė taksonomija, botriologija (iš graikų βότρυς „vynuogė“) ir tipologinė analizė. Dažniausiai svarbūs yra subtilūs skirtumai tarp rezultatų: duomenų išgavime svarbiausios yra atskirtos grupės, o automatinėje klasifikacijoje svarbiausia yra skiriamoji galia.

Terminas – klasterių analizė pirmą kartą buvo pavartotas antropologijoje (Driver ir Kroeber 1932 m.), o psichologijoje pritaikė Zubin 1938 metais ir Robert Tryon 1939 metais. Labiausiai šį metodą išgarsino Cattell 1943 metų pradžioje klasifikuojant bruožus asmenybės psichologijoje.

Apibrėžimas 

Sąvoka – klasteris negali būti tiksliai apibūdinta, būtent todėl yra tiek daug klasterizacijos algoritmų. Bendras vardiklis šiai savokai būtų – tam tikra grupė objektų aprašytų tam tikrais duomenimis. Tačiau skirtingi tyrėjai pritaiko skirtingus klasterių modelius ir kiekvienam klasterių modeliui gali būti pritaikyti skirtingi algoritmai. Klasterių sąvokos, kurios yra apibrėžtos skirtingų algoritmų gali savo savybėmis ypatingai skirtis. Suprantant skirtingus klasterių modelius galima suprasti ir skirtumus tarp įvairių klasterizacijos algoritmų. Tipiniai klasterių modeliai:
 Jungiantys modeliai: pavyzdžiui, hierarchinė klasterizacija nubraižo modelį remiantis jungčių atstumais.
 Centroidiniai modeliai: pavyzdžiui, k-vidurkių algoritmai aprašo kiekvieną klasterį vienu vektorių vidurkiu.
 Pasiskirstymo modeliai: klasteriai modeliuojami remiantis statistiniais pasiskirstymais, pavyzdžiui kelių kintamųjų normalinis pasiskirstymas naudojamas lūkesčių-maksimizavimo algoritmo.
 Tankio modeliai: pavyzdžiui, DBSCAN ir OPTICS aprašo klasterius kaip tankius regionus duomenų erdvėje.
 Poerdvių modeliai: Biklasterizacija (taip žinoma kaip Ko-klasterizacija, ar dviejų-tipų-klasterizacija), klasteriai yra modeliuojami naudojant klasterių narius ir reikšmingas savybes.
 Grupiniai modeliai: kai kurie algoritmai nesuteikia išdirbto modelio gautiems rezultatams ir pateikia tik tam tikrą grupinę informaciją.
 Grafais-paremti modeliai: klika (tam tikra grupė su panašiais parametrais), kuri yra dalinis mazgų rinkinys grafe taip sujungtų, kad du mazgai tarpusavyje yra sujungti paviršiumi, kuris laikomas prototipine klasterio forma. Tam tikrų jungčių atpalaidavimas yra vadinamas kvazi-klikomis HCS klasterizacijos algoritmas.

Klasterizacija iš esmės yra klasterių rinkinys, kurį aprašo visi objektai esantys duomenų rinkinyje. Taip pat gali būti pateikiamas ryšys tarp skirtingų klasterių, pazydžiui, hierarchiniame klasteryje įkomponuotos kitų klasterių grupės sudarančios didesnį klasterį. Klasterizacija gali būti apibrėžta kaip:
 griežta klasterizacija: objektas priklauso klasteriui, arba ne
 negriežta klasterizacija (arba: neraiški klasterizacija): kiekvienas objektas priklauso kiekvienam klasteriui su tam tikru laipsniu (pavyzdžiui, tikimybė priklausyti klasteriui)
Yra ir tikslesnių atskyrimų:
 griežto atskyrimo klasterizacija: čia kiekvienas objektas priklauso tiktais vienam klasteriui
 griežto atskyrimo klasterizacija su išskirtimis: objektai, kurie nepriklauso klasteriams yra vadinami išskirtimis.
 persidengianti klasterizacija (taip pat: alternatyvi klasterizacija, skirtingų požiūrių klasterizacija): objektai gali priklausyti keliems klasteriams.
 hierarchinė klasterizacija: objektai priklausantys vaikui-klasteriui taip pat priklauso ir tėvui-klasteriui
 poerdvių klasterizacija: jeigu unikaliai apibrėžiamas poerdvis, persidengiantys klasteriai nebepersidengia ir tampa atskirti.

Algoritmai 

Klasterizacijos algoritmai gali būti suklasifikuoti pagal klasterio modelį, kuris aprašytas aukščiau. Paminėti pavyzdžiai apibrėžia tik pačiųs svarbiausius pavyzdžius. Literatūroje yra virš 100 publikuotų klasterizacijos algoritmų. Ne visi iš jų pateikia modelius savo klasteriams, todėl juos sunku suklasifikuoti. Algoritmų apžvalgą galima rasti statistinių algoritmų sąrašas.

Objektyviu požiūriu, nėra „teisingo“ algoritmo, tačiau yra teigiama, kad klasterizacijos algoritmo teisingumas priklauso nuo stebėtojo. Dažniausiai norint pasirinkti labiausiai tinkamą algoritmą, reikia tą atlikti eksperimentiškai, nebet yra matematinė priežastis, kodėl renkamas vienas, o ne kitas klasterio modelis. Taip pat yra svarbu tai, kad, jeigu algoritmas yra pritaikytas vienam duomenų rinkiniui, yra didelė tikimybė, kad su kitu duomenų rinkiniu algoritmas darbą atliks netinkamai. Pavyzdžiui, k-vidurkių klasterizacijos algoritmas negali surasti išgaubtų klasterių.

Jungianti klasterizacija (hierarchinė klasterizacija) 

Jungianti klasterizacija, dar kitaip vadinama hierarchine klasterizacija, yra paremta ta idėja, kad artimi objektai yra panašesni tarpusavyje, negu tolimesni. Šie algoritmai sujungia objektus į klasterius remiantis atstumu. Klasteris gali būti aprašytas maksimaliu atstumu, kuris reikalingas sujungti klasterio dalis. Skirtinguose atstumuose, skirtingi klasteriai yra suformuojami ir gali būti atvaizduoti dendrograma, kuri paaiškina hierarchinės klasterizacijos sąvoką: šie algoritmai pateikia ne vieną duomenų rinkinio atskyrimą, o pateikia klasterių hierarchiją, kurie yra sujungti vieni su kitais remiantis tam tikrais atstumais. Dendrogramoje, y-ašis žymi atstumą, prie kurio klasteriai susijungia, o x-ašyje sudedami objektai, kurie nesimaišo.

Jungianti klasterizacija yra visa šeima metodų, kurie skiriasi tik tuo, kaip yra skaičiuojamas atstumas. Be atstumo funkcijų pasirinkimo, vartotojas taip pat privalo apsispręsti dėl jungiančiojo kriterijaus (klasteriai susideda iš skirtingų objektų, todėl yra daug kandidatų, tarp kūrių galima skaičiuoti atstumus). Dažniausiai renkamasi vienos-jungties klasterizacija (minimalus objektų atstumas), visiška jungčių klasterizacija (maksimalūs objektų atstumai), ar UPGMA („Nepasvertas grupių porų metodas su aritmetiniu vidurkiu“, taip pat žinomas, kaip vidurkinė jungčių klasterizacija). Taip pat hierarchinė klasterizacija gali būti aglomeracinė, (pradeda nuo vieno elemento ir agreguoja juos į klasterius), arba dalinanti (pradeda nuo pilno duomenų rinkinio ir skaido į smulkesnes dalis).

Šie metodai neatskiria duomenų rinkinyje esančių objektų, bet sukuria hierarchiją, kurioje stebėtojas pats išrenka tinkamus klasterius. Jie yra neatsparūs išskirtims ir tokių atveju yra suformuojamas papildomas klasteris, ar netgi skirtingi klasteriai susijungia („grandinė fenomenas“, pasitaiko vienos-jungties klasterizacija). Kompleksiškuas yra  aglomeracinei klasterizacijai ir  dalinančiai klasterizacijai, todėl šie metodai yra per lėti dideliems duomenų rinkiniams. Specialiems atvejams, optimalaus efektyvumo metodai (yra  komleksiškumo) žinomi kaip: SLINK vienos-jungties ir CLINK – visiška jungčių klasterizacija. Duomenų išgavimo specialistai pripažista šiuos metodus kaip teorinius bazinius klasterių analizės metodus, bet kartais jie yra vadinami pasenusiais. Iš šių metodų išsivystė kiti metodai, pavyzdžiui tankiu-paremta klasterizacija.

Centroidais paremta klasterizacija 

Centroidais paremtoje klasterizacijoje, klasteriai yra apibūdinami centriniu vektoriumi, kuris ne būtinai yra duomenų rinkinio narys. Kai klasterių skaičius yra k, k-vidurkių klasterizacija duoda formalią optimizacijos problemą: surasti  klasterių centrus ir priskirti objektus, kurie yra arčiausiai prie klasterio centro, o kvadratu pakeltas atstumas būtų minimizuojamas.

Pati optimizacijos problema yra NP-sunkumo, o įprastas požiūris – siekti apytikslio sprendimo. Gerai žinomas aproksimuojantis metodas yra Lloyd’s algoritmas, dažniausiai aprašomas kaip „k-vidurkių algoritmas“. Tačiau dažniausiai jis suranda tik vietinį optimumą, todėl reikia algoritmą kartoti keletą kartų su skirtingomis inicializacijomis. Skirtumai tarp k-vidurkių gali būti tokie, kai pasirenkamas geriausias iš skirtingų algoritmo pakartojimų, bet taip pat galima apriboti metodą, kad centroidai būtų duomenų rinkinio nariai (k-viduroidai), pasirinkus medianas (k-medianų klasterizacija), pasirinkus pradinius centrus mažiau atsitiktinai (K-vidurkiai++), arba leidžiant neraiškų klasterių priskyrimą (Fuzzy c-vidurkiai).

Daugiausiai k-vidurkių-tipo algoritmai reikalauja, kad klasterių skaičius –  – būtų iš anksto nurodytas, o tai yra vienas iš didžiausių šių algoritmų trūkumų. Be to algoritmai pirmumo teisę suteikia klasteriams, kurie yra vienodo dydžio, todėl jie visada priskiria objektą artimiausiam centroidui. Tai dažniausiai pasireiškia neteisingai nukirptais klasterių pakraščiais, nes algoritmas optimizuoja klasterių centrus.

K-vidurkiai turi įdomių teorinių savybių. Pirmiausia, algoritmas padalina duomenų erdvę į struktūrą, kuri vadinasi Voronoi diagrama. Antra, tai konceptualiai yra artima artimiausių kaimynų klasifikacijos metodui, kuris yra dažnai naudojamas mašininiame mokyme. Trečia, šis algoritmas gali būti interpretuojamas kaip modeliu paremtos klasifikacijos variacija, o Lloyd’s algoritmas – kaip lūkesčių-maksimizavimo algoritmo variacija.

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ų.

Kiti metodai 
 Pagrindinė sekos algoritmų schema (BSAS)

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ę.

Vidinis įvertinimas 

Kai klasterizacijos rezultatas yra vertinamas ir duomenų, kurie buvo suklasterizuoti, toks vertinimas vadinamas vidiniu. Tokie metodai dažniausiai parodo geriausią rezultatą tada, kai objektai klasterio viduje yra panašiausi, o objektai tarp skirtingų klasterių skiriasi labiausiai. Vienas iš trūkumų, kai naudojamas vidinis įvertinimas yra tas, kad geri rezultatai ne visada reiškia efektyviausią informacijos išgavimą. Taip pat šio tipo įvertinimas yra šališkas panašiems algoritmams, kurie naudoja vienodus klasterių modelius. Pavyzdžiui, k-Vidurkių klasterizacija natūraliai optimizuoja atstumus tarp objektų, o atstumu-paremtas vidinis kriterijus yra linkęs pervertinti klasterio rezultatą.

Tokiu atveju, vidinio įvertinimo priemonės geriausiai tinka suprasti sutuacijas, kur vienas algoritmas pateikia rezultatą su geresniu skaitiniu įverčiu, bet nebūtinai tas algoritmas geriau atspindi tikruosius rezultatus. Validumas įvertinamas priemone, kuri atspindi tam tikros, identifikuotos struktūros buvimą duomenų rinkinyje. Algoritmai, kurie yra sukurti būtent tam tikriems duomenų rinkiniams yra visiškai nepritaikomi kitokio tipo duomenų rinkiniams, arba jeigu įvertinimui matuojamas radikaliai skirtingas kriterijus. Pavyzdžiui, k-vidurkių klasterizacija gali surasti tik ne išgaubtus klasterius, o dauguma vertinimo kriterijų priima išgaubtus klasterius. Duomenų rinkiniams, kur yra išgaubtų klasterių, netinka nei k-Vidurkių metodai nei vertinimo kriterijai, kurie pariima išgaubtumą.

Žemiau pateikti metodai gali būti naudojami klasterizacijos algoritmų kokybės įvertinimui remiantis vidiniu kriterijumi:
 Davies–Bouldin indeksas
 Davies–Bouldin indeksas gali būti suskaičiuotas remiantis formule:
 
 kur n yra klasterių skaičius,  yra klasterio  centroidas,  yra vidutinis atstumas klasteryje  nuo objektų iki centroido , ir  yra atstumas tarp centroidų  ir . Tie algoritmai, sukuriantys klasterius, kurių intra-klasteriniai atstumai yra maži (aukštas intra-klasterinis panašumas) ir dideli inter-klasteriniai atstumai (mažas inter-klasterinis panašumas) turi žemą Davies–Bouldin indeksą, klasterizacijos algoritmas su mažiausiu Davies–Bouldin indeksu yra laikomas geriausiu algoritmu (remiantis šiuo kriterijumi).

 Dunn indeksas
 Dunn indekso tikslas identifikuoti tankį gerai atsiskyrusiuose klasteriuose. Šis indeksas aprašomas nuo minimalaus inter-klasterinio atstumo iki maksimalaus intra-clasterinio atstumo. Kiekvienam klasterio padalinimui, Dunn indeksas gali būti suskaičiuotas:
 
 kur d(i,j) yra atstumas tarp klasterių i ir j, ir d '(k) matuoja intra-klasterinį klasterio k atstumą. Inter-klasterinis atstumas d(i,j) gali būti bet kuris skaičius iš įvertintų atstumų, pavyzdžiui, atstumas tarp klasterių centroidų. Taip pat ir intra-klasterinis atstumas d '(k) gali būti pamatuotas naudojantis daugybe būdų, pavyzdžiui, didžiausias atstumas tarp bet kurios poros elementų klasteryje k. Šiuo atveju geriausi klasteriai pagal Dunn indeksą yra tie, kurie turi didžiausią intra-klasterinį panašumą ir mažiausią inter-klasterinį panašumą.
 Silhouette coeficientas
 Silhouette coeficientas palygina vidutinius atstumus tarp elementų klasteryje su vidutiniais atstumais tarp kitų klasterių. Objektai su didele silhouette reikšme yra laikomi klasterio nariais, o objektai su mažomis vertėmis yra laikomi išskirtimis. Šis indeksas veikia puikiai su k-vidurkių klasterizacija ir yra naudojamas optimalaus klasterių skaičiaus radimui.

Išorinis įvertinimas 
Kai atliekamas išorinis vertinimas, klasterizacijos rezultatai yra vertinami su duomenimis, kurie nebuvo naudojami klasterizacijai, pavyzdžiui iš anksto suklasifikuotas tam tikras duomenų rinkinys pagal atitinkamus kriterijus. Šiuos duomenų rinkinius sudaro eksperto iš anksto suklasifikuoti objektai, todėl jie gali būti panaudoti, kaip standartai, ar etalonai atliekant vertinimą. Šie vertinimo metodai nustato kaip arti klasterizacijos nustatyti klasteriai yra pateiktam etalonui. Tačiau pastaruoju metu vyksta diskusija, ar toks būdas yra adekvatus realiems duomenims, ar tik sukurtiems duomenų rinkiniams, pagal parinktus parametrus, nes klasteriai gali turėti tam tikrą vidinę struktūrą, o parinkti parametrai gali neleisti atskirti klasterių, todėl jie turės anomaljų. Be to, žvelgiant iš žinių atradimo perspektyvos, esamų žinių atkūrimas ne visada gali parodyti norimą rezultatą. Esant specialiam scenarijui, kai atliekama apribota klasterizacija, kur meta informacija yra naudojama klasterizacijos procese, informacijos „ištiesinimas“ vertinime gali būti sudėtingas.

Keletą skirtingų adaptuotų priemonių, galima naudoti vertinimo uždaviniuose. Kai klasteris teisingai priskiriamas, tai yra vadinama teisingu teigiamu (true positive), ir yra įvertinama, ar tikrai klasterizacijos algoritmas priskyrė būtent tam klasteriui.

Išorinės klasterizacijos algoritmų įvertinimo priemonės:
 Rand įvertis (William M. Rand 1971)
 Rand įvertis suskaičiuoja, kiek klasteriai, kuriuos nustato klasterizacijos algoritmas yra panašūs į etalonines klasifikacijas. Taip pat Rand įvertis gali būti panaudotas kaip matas vertinant procentinę algoritmo teisingų sprendimų dalį. Rand įvertis skaičuiojamas:
 
 kur  teisingų teigiamųs skaičius,  teisingų neigiamų skaičius ,  klaidingų teigiamų skaičius, ir  klaidingų neigiamų skaičius. Viena bėda su Rand įverčiu ta, kad klaidingu teigiami ir klaidingi neigiami turi vienodą svorį. Tai yra nepageidaujama su kai kuriais klasterizacijos pritaikymais. F-matas atsižvelgia į minėtą problemą ir atlieka tikimybinę-korekciją, kur gaunamas pakoreguotas Rand įvertis.
 F-matas
 F-matas gali būti panaudotas klaidingų neigiamų įverčių subalansavimui, nes yra pamatuojama išgava per parametrą . Glaudumas ir išgava gali būti suskaičiuoti:
 
 
 kur  glaudumas ir  išgava. F-matą galima suskaičiuoti:
 
 Kai , . Išgavos dydis neturi jokio poveikio F-matui, kai . Didinant  yra perskirstomas išgavos svoris galutiniam F-matui.
 Jaccard įvertis
 Jaccard įvertis tinka panašumui tarp dviejų duomenų rinkinių nustatyti. Jaccard įvertis yra tarp 0 ir 1. 1 reiškia, kad du duomenų rinkiniai yra identiški, o, kai įvertis lygus 0, reiškia, kad duomenų rinkiniai neturi bendrų elementų. Jaccard įvertis apskaičuiojamas pagal formulę:
 
 Ši formulė atitinka elementų skaičių, kuris yra bendras abiem rinkiniams padalintą ir bendro elementų skaičiaus abiejuose duomenų rinkiniuose.

 Fowlkes–Mallows įvertis (E. B. Fowlkes ir C. L. Mallows 1983)
 Fowlkes-Mallows įvertis suskaičiuoja panašumus tarp klasterių, kuriuos suklasterizuoja algoritmas ir etaloninių klasifikacijų. Kuo didesnis Fowlkes-Mallows įvertis, tuo panašesnis klasteris į etaloninę klasifikaciją. Šį įvertį galima suskaičiuoti:
 
 kur  teisingų teigiamų skaičius,  klaidingų teigiamų, ir  klaidingų neigiamų skaičius.  įvertis yra geometrinis glaudumo ir išgavos  ir  vidurkis, o F-matas yra jų harmoninis vidurkis. Be to, glaudumas ir išgava yra vadinami Wallace’s indeksais  ir .

 Mutuali Informacija yra teorinis informacijos matas, kuris parodo, kiek informacijos dalijasi klasterizacija ir tikroji klasifikacija aptikdama netiesiškus dviejų klasterių panašumus. Pakoreguota mutuali informacija, yra pakoreguotas tikimybinis variantas, kur yra sumažinamas šališkumas dėl skirtingo klasterių skaičiaus.
 Confusion matrix
 Klaidų matrica gali būti panaudota klasterizacijos algoritmo rezultatų vizualizacijai. Ji parodo, kaip stipriai skiriasi klasteris nuo klasterio-standarto.

Pritaikymas 

 Biologija, skičiuojamoji biologija ir bioinformatika
Augalų ir gyvūnų ekologija
 klasterių analizė yra naudojama erdvinių ir laiko įtakotų organizmų aibių (grupių) aprašymui heterogenininėje aplinkoje; tai taip pat naudojama augalų sistematikoje tam, kad būtų sugeneruotos dirbtinės filogenezės, ar organizmų (individų) klasteriai, ar rūšys, gentys ir aukštesnio lygio klasės su tomis pačiomis charakteristikomis
Transkriptomika
 klasterizacija yra naudojama genų su panašiomis sekomis grupėms kurti (HCS clusterizacijos algoritmas). Dažnai tokios grupės turi funkciškai susijusius baltymus, pavyzdžiuienzimus skirtus specifiniam metabiliniam keliui, arba gerai, kurie yra ko-reguliuojami. Aukšto našumo eksperimentams atlikti naudojami sekų žymenys, ar DNR mikro-lustinės technologijos, kurios padeda pasiekti aukštos kokybės rezultatų genomo analizėje, ir kitose genomikos rušyse.
Sekų analizė
 klasterizacija yra naudojama homologinių sekų sugrupavimui į genų šeimas. Šie metodai taikomi bioinformatikoje ir evolucinėje biologijoje. Genų duplikacijos paskatintos evoliucijos tyrimuose.
Aukšto-našumo genotipų nustatymo platformose
 klasterizacija automatiškai priskiria atitinkamus genotipus.
Žmogaus genetinė klasterizacija
Genetiniai panašumai naudojami žmonių populiacijos klasterizacijoje.
 Medicina
Medicininis vaizdinimas
 Pozitronų emisijos tomografijoje (PET), naudojama skirtingiems audiniams nustatyti 3 dimensijų formate.
 Verslas ir marketingas
Rinkų tyrimai
 Klasterių analizė naudojama rinkos tyrimuose, kai dirbama su daugybe kintamųjų pateikiančiomis apklausomis ir testais. Rinkos tyrėjai pasitelkę klasterių analizę gali suskirstyti vartotojų populiaciją į atskirtus rinkos segmentus, todėl geriau suprantami įpročiai ir ryšiai tarp skirtingų grupių. Pritaikoma rinkos segmentacijoje, produktų paskirstyme, naujų produktų vystyme ir atrenkant naujas rinkas.
Prekių grupavimas
 Pritaikoma skirstant į unikalių prekių klasterius. Pavyzdžiui eBay produktų grupės.
 World wide web
Socialinių tinklų analizė
 socialiniuose tinkluose klasterizacija padeda atskirti ir atpažinti žmonių grupes.
Paieškos duomenų grupavimas
 Grupuojant bylas ir tinklapius, analizuojant duomenis, galima sukurti naujo tipo paieškos priemones panašias į Google. Yra keletas tinklapių, kurie suteikia klasterizacijos priemonių, pavyzdžiui Clusty.
Žemėlapių optimizacija
 Flickr žemėlapio nuotraukos yra suklasterizuotos tam, kad būtų sumažintas žemėlapio žymų skaičius, todėl pagreitėja žemėlapio valdymas ir sumažėja vizualios netvarkos.
 Kompiuterių mokslas
Programinės įrangos evoliucija
 Klasterizacija naudojama programinės įrangos evoliucijos nustatyme, padeda aptikti, kas yra likę iš senų funkcijų, o kurios funkcijos sunykusios, todėl tai galima laikyti kaip tam tikra restruktūrizacijos forma, ar prevencine priežiūros priemone.
Vaizdų segmentacija
 Naudojama skaitmeninių vaizdų kraštų aptikime, ar objektų atpažinime.
Evoliuciniai algoritmai
 Naudojama skirtingų nišų evoliucinių algoritmų nustatymui ir paskirstymui.
Rekomendacinės sistemos
 Rekomendacinės sistemos skirtos rekomenduoti tam tikrus produktus remiantis vartotojo įpročiais. Šios sistemos naudoja klasterizacijos algoritmus tam, kad nuspėtų vartotojo prioritetus.
Markovo grandinių Monte Carlo metodai
 Klasterizacija padeda aptikti ir nustatyti ir charakterizuoti ekstremumus.
Anomalijų detekcija
 Anomalijos/ išskirtys yra tiesiogiai, arba netiesiogiai nustatomos pasitelkiant klasterizacijos algoritmus.
 Socialiniai mokslai
Nusikaltimų analizė
 Klasterių analizę galima pritaikyti tam tikrų vietų su tam tiro tipo nusikaltimų tikimybe radimui. Galima efektyviai paskirstyti žmogiškuosius išteklius atliekant teisėsaugos operacijas, jeigu yra nustatyto nusikaltimų vietos.
Mokomasis duomenų išgavimas
klasterių analizė pritaikoma mokinių grupių su panašiomis savybėmis nustatymui.
 Tipologijos
 Apklausų duomenys gali būti pritaikyti įpročių analizėje, tipologijos nuomonių išskyrimui, politikoje ir demografijoje.
 Kiti pritaikymai
Robotika veiklos vietoje
 Klasterizacijos algoritmai naudojami su robotinėmis sistemomis nustatant situaciją, sekant objektus, nustatant išskirtis.
Matematinė chemija
 Ieškant struktūrinių panašumų. Pavyzdžiui 3000 cheminių junginių buvo suklasifikuoti į klasterių erdvę su 90 topologinių indeksų.
Klimatologija
 Naudojama klimato režimų, jūros lygio, atmosferos slėgio tyrimuose.
Kuro geologijoje
 Klasterių analizė yra naudojama rekonstruojant trukstamus duomenis, ar logaritmines kreives, visa tai padeda įvertinti rezervuarų savybes.
Fizinė geografija
 Skirtingų vietų cheminių savybių klasterizacija.

Taip pat žiūrėkite

Specialūs klasterių analizės tipai 
 Subalansuota klasterizacija
 Daugiamačių duomenų klasterizacija
 Konceptuali klasterizacija
 Sutarianti klasterizacija
 Apribota klasterizacija
 Duomenų sekų klasterizacija
 HCS klasterizacija
 Sekų klasterizacija
 Spektrinė klasterizacija

Klasterių analizėje naudojamos technikos 
 Dirbtiniai neuronų tinklai (DNT)
 Artimiausių kaimynų paieška
 Kaimyninių komponentų analizė
 Paslėptų klasių analizė
 Giminingumo sklaida

Duomenų projekcijos ir pirminis apdorojimas 
 Dimensijų sumažinimas
 Pagrindinių komponentų analizė
 Multi-dimensinis skalės keitimas

Kitos technikos 
 Svorinių-klasterių modeliavimas
 Daugiadimensiškumas
 Klasterių skaičiaus nustatymas duomenų rinkinyje
 Lygiagrečios koordinatės
 Struktūrizuota duomenų analizė

Šaltiniai

Nuorodos