Klasterių analizė

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigacija, paiešką
 Broom icon.svg  Šį puslapį ar jo dalį reikia sutvarkyti pagal Vikipedijos standartus – neišverstos vidinės nuorodos
Jei galite, sutvarkykite.
 Crystal Clear action spellcheck.png  Šį straipsnį ar jo skyrių reikėtų peržiūrėti.
Būtina ištaisyti gramatines klaidas, patikrinti rašybą, skyrybą, stilių ir pan.
Ištaisę pastebėtas klaidas, ištrinkite šį pranešimą ir apie tai, jei norite, praneškite Tvarkos projekte.

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[1][2]. Labiausiai šį metodą išgarsino Cattell 1943 metų pradžioje[3] klasifikuojant bruožus asmenybės psichologijoje.

Apibrėžimas[redaguoti | redaguoti vikitekstą]

Sąvoka – klasteris negali būti tiksliai apibūdinta, būtent todėl yra tiek daug klasterizacijos algoritmų.[4] 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[redaguoti | redaguoti vikitekstą]

Pagrindinis straipsnis – Duomenų klasterizacijos 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.[4] 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.[4] Pavyzdžiui, k-vidurkių klasterizacijos algoritmas negali surasti išgaubtų klasterių.[4]

Jungianti klasterizacija (hierarchinė klasterizacija)[redaguoti | redaguoti vikitekstą]

Pagrindinis straipsnis – 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 sujungiaobjektus į klasterius remiantis atstumu. Klasteris gali būti aprašytas maksimaliu atstumu, kuris reikalingas sujungi 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 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,[5] todėl šie metodai yra per lėti dideliems duomenų rinkiniams. Specialiems atvejams, optimalaus efektyvumo metodai (yra komleksiškumo) žinomi kaip: SLINK[6] vienos-jungties ir CLINK[7] – 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.[reikalingas šaltinis] Iš šių metodų išsivystė kiti metodai, pavyzdžiui tankiu-paremta klasterizacija.

Centroidais paremta klasterizacija[redaguoti | redaguoti vikitekstą]

Pagrindinis straipsnis – k-vidurkių klasterizavimas.

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,[8] 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[redaguoti | redaguoti vikitekstą]

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[redaguoti | redaguoti vikitekstą]

Tankiu paremtoje klasterizacijoje,[9] 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[10] tankiu paremtos klasterizacijos metodas yra DBSCAN.[11] 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[12] yra DBSCAN apibendrinimas ir nereikalauja parametro vertės parinkimo, todėl pateikia hierarchinį rezultatą panašų į tą, kurį pateikia hierarchinė klasterizacija. DeLi-Clu,[13] 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,[14] 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[redaguoti | redaguoti vikitekstą]

Per pastaruosius metus buvo įdėta nemažai pastangų tobulinant esamus algoritmus.[15][16] Iš minimų yra CLARANS (Ng ir Han, 1994),[17] ir BIRCH (Zhang ir kiti, 1996).[18] 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.[19]

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ą.[20] Pavyzdžiai: CLIQUE[21] ir SUBCLU.[22]

Idėjos iš tankiu-paremtų klasterizacijos metodų buvo pritaikytos (ypač iš DBSCAN/OPTICS šeimos algoritmų) poerdvių klasterizacijai (HiSC,[23] hierarchinė poerdvių klasterizacija ir DiSH[24]) ir koreliacijos klasterizacija (HiCO,[25] hierarchinė klasterizacijos klasterizacija, 4C[26] naudojant „koreliacijos jungtis“ ir ERiC[27] tyrinėjant hierarchinius tankiu-paremtus koreliacijos klasterius).

Buvo pasiūlytos kelios klasterizacijos sistemos, kurios remiasi abipuse informacija. Marina Meilă's informacijos variacija;[28], kitas – hierarchinė klasterizacija.[29] Naudojant genetinius algoritmus, daug skirtingų priklausomybės funkcijų gali būti optimizuota, taip pat ir abipusė informacija.[30] Be to, žinios perdavimo algoritmas, naujas Kompiuterių mokslo ir Statistinės fizikos patobulinimas, leido sukurti naujų naujo tipo algoritmų.[31]

Kiti metodai[redaguoti | redaguoti vikitekstą]

Analizė ir įvertinimas[redaguoti | redaguoti vikitekstą]

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[redaguoti | redaguoti vikitekstą]

Daugiau informacijos galite rasti straipsnyje Klasterių skaičiaus nustatymas.

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ą.[32] 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.[4] 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.[4] 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 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 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:[33]
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 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[redaguoti | redaguoti vikitekstą]

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š ansto 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ų.[34] Be to, žvelgiant iš žinių atradimo perspektyvos, esamų žinių atkūrimas ne visada gali parodyti norimą rezultatą.[34] Esant specialiam scenarijui, kai atliekama apribota klasterizacija, kur meta informacija yra naudojama klasterizacijos procese, informacijos „ištiesinimas“ vertinime gali būti sudėtingas.[35]

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 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 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:[32]
Kai , . Išgavos dydis neturi jokio poveikio F-matui, kai . Didinant yra perskirstomas išgavos svoris galutiniam F-matui.
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 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.[38] Be to, glaudumas ir išgava yra vadinami Wallace’s indeksais ir .[39]
Klaidų matrica gali būti panaudota klasterizacijos algoritmo rezultatų vizualizacijai. Ji parodo, kaip stipriai skiriasi klasteris nuo klasterio-standarto.

Pritaikymas[redaguoti | redaguoti vikitekstą]

Šablonas:Refimprove section

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.[40]
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.[41]
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.[42]
Matematinė chemija
Ieškant struktūrinių panašumų. Pavyzdžiui 3000 cheminių junginių buvo suklasifikuoti į klasterių erdvę su 90 topologinių indeksų.[43]
Klimatologija
Naudojama klimato režimų, jūros lygio, atmosferos slėgio tyrimuose.[44]
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[redaguoti | redaguoti vikitekstą]

Šablonas:Commons category

Specialūs klasterių analizės tipai[redaguoti | redaguoti vikitekstą]

Klasterių analizėje naudojamos technikos[redaguoti | redaguoti vikitekstą]

Duomenų projekcijos ir pirminis apdorojimas[redaguoti | redaguoti vikitekstą]

Kitos technikos[redaguoti | redaguoti vikitekstą]

Šaltiniai[redaguoti | redaguoti vikitekstą]

  1. Bailey, Ken (1994). “Numerical Taxonomy and Cluster Analysis”, Typologies and Taxonomies. ISBN 9780803952591.
  2. Tryon, Robert C. (1939). Cluster Analysis: Correlation Profile and Orthometric (factor) Analysis for the Isolation of Unities in Mind and Personality. Edwards Brothers.
  3. Cattell, R. B.. „The description of personality: Basic traits resolved into clusters“. Journal of Abnormal and Social Psychology, 38, 476–506 (1943). DOI:10.1037/h0054116. 
  4. 4,0 4,1 4,2 4,3 4,4 4,5 Estivill-Castro, Vladimir. „Why so many clustering algorithms — A Position Paper“. ACM SIGKDD Explorations Newsletter, 4 (1), 65–75 (20 June 2002). DOI:10.1145/568574.568575. 
  5. Everitt, Brian (2011). Cluster analysis. Chichester, West Sussex, U.K: Wiley. ISBN 9780470749913.
  6. Sibson, R.. „SLINK: an optimally efficient algorithm for the single-link cluster method“. The Computer Journal, 16 (1), 30–34 (1973). DOI:10.1093/comjnl/16.1.30. 
  7. Defays, D.. „An efficient algorithm for a complete link method“. The Computer Journal, 20 (4), 364–366 (1977). DOI:10.1093/comjnl/20.4.364. 
  8. „Least squares quantization in PCM“. IEEE Transactions on Information Theory, 28 (2), 129–137 (1982). DOI:10.1109/TIT.1982.1056489. 
  9. Density-based Clustering“. WIREs Data Mining and Knowledge Discovery, 1 (3), 231–240 (2011). DOI:10.1002/widm.30. 
  10. Microsoft academic search: most cited data mining articles: DBSCAN is on rank 24, when accessed on: 4/18/2010
  11. (1996) "A density-based algorithm for discovering clusters in large spatial databases with noise". Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96): 226–231, AAAI Press. 
  12. (1999) "OPTICS: Ordering Points To Identify the Clustering Structure". ACM SIGMOD international conference on Management of data: 49–60, ACM Press. 
  13. „DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking“. LNCS: Advances in Knowledge Discovery and Data Mining, 3918, 119–128 (2006). DOI:10.1007/11731139_16. 
  14. (2005) "An Approach to find Embedded Clusters Using Density Based Techniques". LNCS Vol.3816: 523–535, Springer Verlag. 
  15. Sculley, D. (2010). "Web-scale k-means clustering" in Proc. 19th WWW. {{{booktitle}}}. 
  16. „Extensions to the k-means algorithm for clustering large data sets with categorical values“. Data Mining and Knowledge Discovery, 2, 283–304 (1998). 
  17. R. Ng and J. Han. „Efficient and effective clustering method for spatial data mining“. In: Proceedings of the 20th VLDB Conference, pages 144–155, Santiago, Chile, 1994.
  18. Tian Zhang, Raghu Ramakrishnan, Miron Livny. "An Efficient Data Clustering Method for Very Large Databases. " In: Proc. Int’l Conf. on Management of Data, ACM SIGMOD, pp. 103–114.
  19. „Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases“. ACM Transactions on Database Systems, 15 (4), 483–517 (1990). DOI:10.1145/99935.99938. 
  20. „Subspace clustering“. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2 (4), 351–364 (July 2012). DOI:10.1002/widm.1057. 
  21. „Automatic Subspace Clustering of High Dimensional Data“. Data Mining and Knowledge Discovery, 11, 5–33 (2005). DOI:10.1007/s10618-005-1396-1. 
  22. Karin Kailing, Hans-Peter Kriegel and Peer Kröger. Density-Connected Subspace Clustering for High-Dimensional Data. In: Proc. SIAM Int. Conf. on Data Mining (SDM’04), pp. 246–257, 2004.
  23. „Finding Hierarchies of Subspace Clusters“. LNCS: Knowledge Discovery in Databases: PKDD 2006, 4213, 446–453 (2006). DOI:10.1007/11871637_42. 
  24. „Detection and Visualization of Subspace Cluster Hierarchies“. LNCS: Advances in Databases: Concepts, Systems and Applications, 4443, 152–163 (2007). DOI:10.1007/978-3-540-71703-4_15. 
  25. „Mining Hierarchies of Correlation Clusters“. Proc. 18th International Conference on Scientific and Statistical Database Management (SSDBM), 119–128 (2006). DOI:10.1109/SSDBM.2006.35. 
  26. (2004) “Computing Clusters of Correlation Connected objects”, Proceedings of the 2004 ACM SIGMOD international conference on Management of data - SIGMOD '04, 455. DOI:10.1145/1007568.1007620. ISBN 1581138598.
  27. (2007) “On Exploring Complex Relationships of Correlation Clusters”, 19th International Conference on Scientific and Statistical Database Management (SSDBM 2007), 7. DOI:10.1109/SSDBM.2007.21. ISBN 0-7695-2868-6.
  28. Meilă, Marina. „Comparing Clusterings by the Variation of Information“. Learning Theory and Kernel Machines, 2777, 173–187 (2003). DOI:10.1007/978-3-540-45167-9_14. 
  29. „Hierarchical Clustering Based on Mutual Information“ (1 December 2003). 
  30. Auffarth, B.. „Clustering by a Genetic Algorithm with Biased Mutation Operator“. WCCI CEC (July 18–23, 2010). 
  31. „Clustering by Passing Messages Between Data Points“. Science, 315 (5814), 972–976 (2007). DOI:10.1126/science.1136800. PMID 17218491. 
  32. 32,0 32,1 Introduction to Information Retrieval. Cambridge University Press. ISBN 978-0-521-86571-5.
  33. Dunn, J.. „Well separated clusters and optimal fuzzy partitions“. Journal of Cybernetics, 4, 95–104 (1974). DOI:10.1080/01969727408546059. 
  34. 34,0 34,1 (2010) "On Using Class-Labels in Evaluation of Clusterings". MultiClust: Discovering, Summarizing, and Using Multiple Clusterings, ACM SIGKDD. 
  35. (2014) "Model Selection for Semi-Supervised Clustering". Proceedings of the 17th International Conference on Extending Database Technology (EDBT),: 331–342. DOI:10.5441/002/edbt.2014.31. 
  36. Rand, W. M.. „Objective criteria for the evaluation of clustering methods“. Journal of the American Statistical Association, 66 (336), 846–850 (1971). DOI:10.2307/2284239. 
  37. E. B. Fowlkes & C. L. Mallows (1983), „A Method for Comparing Two Hierarchical Clusterings“, Journal of the American Statistical Association 78, 553–569.
  38. „Comparing partitions“. J. of Classification, 2 (1). 
  39. „Comment“. Journal of the American Statistical Association, 78, 569–579 (1983). DOI:10.1080/01621459.1983.10478009. 
  40. „Semi-supervised Cluster Analysis of Imaging Data“. NeuroImage, 54 (3), 2185–2197 (2011). DOI:10.1016/j.neuroimage.2010.09.074. PMID 20933091. 
  41. Bewley, A., & Upcroft, B. (2013). Advantages of Exploiting Projection Structure for Segmenting Dense 3D Point Clouds. In Australian Conference on Robotics and Automation [1]
  42. „Real-time volume estimation of a dragline payload“. IEEE International Conference on Robotics and Automation, 2011, 1571–1576. 
  43. „Determining Structural Similarity of Chemicals Using Graph Theoretic Indices“. Discr. Appl. Math., 19, 17–44 (1988). DOI:10.1016/0166-218x(88)90004-2. 
  44. „Classifications of Atmospheric Circulation Patterns: Recent Advances and Applications“. Ann. N.Y. Acad. Sci., 1146, 105–152 (2008). 

Nuorodos[redaguoti | redaguoti vikitekstą]