Klasteriavimo metodas – tai užduotis sugrupuoti objektų rinkinį taip, kad jie toje pačioje grupėje būtų panašesni vienas į kitą nei į kitų pramonės šakų objektus. Tai pagrindinė duomenų gavybos užduotis ir bendroji statistinės analizės technika, naudojama daugelyje sričių, įskaitant mašininį mokymąsi, modelių atpažinimą, vaizdų atpažinimą, informacijos gavimą, duomenų glaudinimą ir kompiuterinę grafiką.
Optimizavimo problema
Pats klasterizacijos metodas yra ne vienas konkretus algoritmas, o bendra užduotis, kurią reikia išspręsti. Tai galima pasiekti naudojant įvairius algoritmus, kurie labai skiriasi supratimu, kas sudaro grupę ir kaip ją efektyviai rasti. Klasterizacijos metodo naudojimas metasubjektams formuoti apima grupės su naudojimąnedideli atstumai tarp narių, tankūs erdvės regionai, intervalai arba tam tikri statistiniai skirstiniai. Todėl grupavimas gali būti suformuluotas kaip kelių tikslų optimizavimo problema.
Atitinkamas metodas ir parametrų nustatymai (įskaitant tokius elementus kaip naudotina atstumo funkcija, tankio slenkstis arba numatomų grupių skaičius) priklauso nuo individualaus duomenų rinkinio ir numatomo rezultatų panaudojimo. Analizė pati savaime nėra automatinė užduotis, o pasikartojantis žinių atradimo arba interaktyvaus kelių tikslų optimizavimo procesas. Šis grupavimo metodas apima bandymų ir klaidų bandymus. Dažnai reikia keisti išankstinį duomenų apdorojimą ir modeliuoti parametrus, kol rezultatas pasieks norimas savybes.
Be termino „grupavimas“, yra daug žodžių, turinčių panašias reikšmes, įskaitant automatinį klasifikavimą, skaitmeninę taksonomiją, tiek riologiją, tiek tipologinę analizę. Subtilių skirtumų dažnai slypi klasterizacijos metodo naudojimas metasubjektų ryšiams formuoti. Nors išgaujant duomenis domina gautos grupės, automatiniame klasifikavime šias funkcijas jau atlieka diskriminacinė galia.
Klasterių analizė buvo pagrįsta daugeliu 1932 m. Kroeberio darbų. Ją į psichologiją įvedė Zubinas 1938 m., o Robertas Tryonas 1939 m. Šiuos darbus Cattell naudojo nuo 1943 m. teorinei klasterizacijos metodų klasifikacijai nurodyti.
Terminas
Neįmanoma tiksliai apibrėžti „grupės“sąvokos. Tai viena iš priežasčių, kodėl yra tiek daug klasterizacijos metodų. Yra bendras vardiklis: duomenų objektų grupė. Tačiau skirtingi tyrinėtojai naudoja skirtingus modelius. Ir kiekvienas iš šių grupavimo metodų panaudojimo apima skirtingus duomenis. Įvairių algoritmų nustatyta koncepcija labai skiriasi savo savybėmis.
Naudojant grupavimo metodą labai svarbu suprasti instrukcijų skirtumus. Tipiški klasterių modeliai:
- Centroid s. Tai, pavyzdžiui, kai k-means klasterizavimas reiškia kiekvieną klasterį su vienu vidutiniu vektoriumi.
- Ryšio modelis s. Tai, pavyzdžiui, hierarchinis grupavimas, kuris sukuria modelius, pagrįstus nuotoliniu ryšiu.
- Paskirstymo modelis s. Šiuo atveju klasteriai modeliuojami naudojant klasterizacijos metodą, kad susidarytų metasubjektų statistiniai skirstiniai. Pavyzdžiui, daugiamatis normalus atskyrimas, kuris taikomas lūkesčių maksimizavimo algoritmui.
- Tankio modelio s. Tai, pavyzdžiui, DBSCAN (erdvinio grupavimo algoritmas su triukšmu) ir OPTICS (struktūrų aptikimo eilės taškai), kurie apibrėžia grupes kaip sujungtas tankias sritis duomenų erdvėje.
- Suberdvės modelis c. Naudojant grupes (taip pat žinomas kaip bendras klasterizavimas arba du režimai), grupės modeliuojamos naudojant abu elementus ir atitinkamus atributus.
- Modelis s. Kai kurie algoritmai to nedaropatobulintas jų grupavimo metodo ryšys, siekiant generuoti meta-subjekto rezultatus ir tiesiog pateikti informacijos grupavimą.
- Modelis, pagrįstas grafiku s. Klika, tai yra mazgų poaibis, todėl kas dvi kraštinės dalies jungtys gali būti laikomos klasterio formos prototipu. Bendros paklausos susilpnėjimas vadinamas kvaziklikomis. Lygiai toks pat pavadinimas pateikiamas HCS klasterizacijos algoritme.
- Neuroniniai modeliai s. Žinomiausias neprižiūrimas tinklas yra savaime besitvarkantis žemėlapis. Ir būtent šiuos modelius paprastai galima apibūdinti kaip panašius į vieną ar kelis aukščiau išvardintus klasterizacijos metodus, skirtus formuoti meta-subjekto rezultatus. Tai apima poerdvės sistemas, kai neuroniniai tinklai įgyvendina būtiną pagrindinių arba nepriklausomų komponentų analizės formą.
Šis terminas iš tikrųjų yra tokių grupių rinkinys, kuriame paprastai yra visi objektai duomenų grupavimo metodų rinkinyje. Be to, jis gali nurodyti grupių santykį tarpusavyje, pavyzdžiui, sistemų hierarchiją, integruotą viena į kitą. Grupavimą galima suskirstyti į šiuos aspektus:
- Kietas centroidų klasterizacijos metodas. Čia kiekvienas objektas priklauso grupei arba yra už jos ribų.
- Minkšta arba neryški sistema. Šiuo metu kiekvienas objektas tam tikru mastu jau priklauso bet kokiai klasteriui. Jis taip pat vadinamas c-means fuzzy klasterizacijos metodu.
Ir galimi ir subtilesni skirtumai. Pavyzdžiui:
- Griežtas skaidymo grupavimas. čiakiekvienas objektas priklauso tiksliai vienai grupei.
- Griežtas skaidymo grupavimas su nuokrypiais. Tokiu atveju objektai taip pat gali nepriklausyti jokiai klasteriui ir būti laikomi nereikalingais.
- Perdengiantis grupavimas (taip pat alternatyvus, su keliais rodiniais). Čia objektai gali priklausyti daugiau nei vienai šakai. Paprastai tai apima vientisas grupes.
- Hierarchiniai klasterizacijos metodai. Antrinei grupei priklausantys objektai taip pat priklauso pirminiam posistemiui.
- Poerdvės formavimas. Nors ir panašios į persidengiančias grupes, vienareikšmiškai apibrėžtoje sistemoje tarpusavio grupės neturėtų persidengti.
Instrukcijos
Kaip minėta, grupavimo algoritmus galima klasifikuoti pagal jų klasterio modelį. Šioje apžvalgoje bus pateikti tik ryškiausi šių instrukcijų pavyzdžiai. Kadangi gali būti daugiau nei 100 paskelbtų algoritmų, ne visi pateikia savo grupių modelius, todėl jų negalima lengvai klasifikuoti.
Nėra objektyviai teisingo grupavimo algoritmo. Tačiau, kaip minėta aukščiau, instrukcija visada yra stebėtojo matymo lauke. Konkrečiai problemai tinkamiausią klasterizacijos algoritmą dažnai reikia pasirinkti eksperimentiškai, nebent yra matematinė priežastis, kodėl pirmenybė teikiama vienam modeliui, o ne kitam. Reikėtų pažymėti, kad vienam tipui sukurtas algoritmas dažniausiai neveikiaduomenų rinkinys, kuriame yra visiškai kitoks subjektas. Pavyzdžiui, k-means negali rasti neišgaubtų grupių.
Ryšiu pagrįstas klasterizavimas
Ši sąjunga taip pat žinoma savo pavadinimu, hierarchiniu modeliu. Jis pagrįstas tipine idėja, kad objektai yra labiau susiję su kaimyninėmis dalimis, nei su tomis, kurios yra daug toliau. Šie algoritmai sujungia objektus, sudarydami skirtingus grupes, priklausomai nuo jų atstumo. Grupę daugiausia galima apibūdinti didžiausiu atstumu, kurio reikia skirtingoms klasterio dalims sujungti. Visais įmanomais atstumais susiformuos kitos grupės, kurias galima pavaizduoti naudojant dendrogramą. Tai paaiškina, iš kur kilęs bendras pavadinimas „hierarchinė grupuotė“. Tai reiškia, kad šie algoritmai nepateikia vieno duomenų rinkinio skaidinio, o suteikia platų įgaliojimų tvarką. Būtent jo dėka tam tikrais atstumais yra vienas su kitu nutekėjimas. Dendrogramoje y ašis žymi atstumą, kuriuo klasteriai susijungia. Ir objektai yra išdėstyti pagal X liniją, kad grupės nesimaišytų.
Ryšiu pagrįstas grupavimas yra visa metodų, kurie skiriasi atstumų skaičiavimo būdu, šeima. Be įprasto atstumo funkcijų pasirinkimo, vartotojas turi apsispręsti ir dėl ryšio kriterijaus. Kadangi klasterį sudaro keli objektai, yra daug galimybių jį apskaičiuoti. Populiarus pasirinkimas yra žinomas kaip vienos svirties grupavimas, tai yra metodasvisa nuoroda, kurioje yra UPGMA arba WPGMA (nesvertinis arba svertinis porų ansamblis su aritmetiniu vidurkiu, dar žinomas kaip vidutinių nuorodų grupavimas). Be to, hierarchinė sistema gali būti aglomeracinė (pradedant atskirais elementais ir jungiant juos į grupes) arba dalijanti (pradedant nuo pilno duomenų rinkinio ir suskaidant jį į skyrius).
Paskirstytas grupavimas
Šie modeliai yra glaudžiausiai susiję su statistika, pagrįsta padalijimu. Klasteriai gali būti lengvai apibrėžti kaip objektai, kurie greičiausiai priklauso tam pačiam skirstymui. Patogi šio metodo ypatybė yra ta, kad jis labai panašus į dirbtinių duomenų rinkinių kūrimo būdą. Atrinkdami atsitiktinius objektus iš paskirstymo.
Nors šių metodų teorinis pagrindas yra puikus, jie kenčia nuo vienos pagrindinės problemos, vadinamos permontavimu, nebent modelio sudėtingumas būtų ribojamas. Didesnė asociacija paprastai geriau paaiškins duomenis, todėl bus sunku pasirinkti tinkamą metodą.
Gauso mišinio modelis
Šis metodas naudoja įvairius lūkesčių padidinimo algoritmus. Čia duomenų rinkinys paprastai modeliuojamas naudojant fiksuotą (kad būtų išvengta nepaisymo) Gauso skirstinių, kurie inicijuojami atsitiktinai ir kurių parametrai iteratyviai optimizuojami, kad geriau atitiktų duomenų rinkinį, skaičių. Ši sistema susiartins su vietiniu optimalumu. Štai kodėl gali duoti keli bėgimaiskirtingus rezultatus. Norint gauti griežčiausią grupavimą, funkcijos dažnai priskiriamos Gauso skirstiniui, kuriam jie greičiausiai priklauso. O švelnesnėms grupėms tai nėra būtina.
Paskirstymu pagrįstas grupavimas sukuria sudėtingus modelius, kurie galiausiai gali užfiksuoti atributų koreliaciją ir priklausomybę. Tačiau šie algoritmai vartotojui užkrauna papildomą naštą. Daugeliui realaus pasaulio duomenų rinkinių gali nebūti glaustai apibrėžto matematinio modelio (pvz., Gauso skirstinio prielaida yra gana tvirta prielaida).
Tankiu pagrįstas grupavimas
Šiame pavyzdyje grupės iš esmės apibrėžiamos kaip sritys, kurių nepralaidumas didesnis nei likusi duomenų rinkinio dalis. Šiose retose dalyse esantys objektai, kurie būtini norint atskirti visus komponentus, paprastai laikomi triukšmo ir krašto taškais.
Populiariausias tankiu pagrįstas grupavimo metodas yra DBSCAN (Spatial Noise Clustering Algorithm). Skirtingai nuo daugelio naujesnių metodų, jis turi gerai apibrėžtą klasterio komponentą, vadinamą „tankio pasiekiamumu“. Panašiai kaip saitais pagrįstas klasterizavimas, jis pagrįstas prisijungimo taškais tam tikrose atstumo ribose. Tačiau šiuo metodu renkami tik tie elementai, kurie atitinka tankio kriterijų. Pradinėje versijoje, apibrėžtoje kaip minimalus kitų objektų skaičius šiame spindulyje, klasterį sudaro visisu tankiu susiję elementai (kurie gali sudaryti laisvos formos grupę, skirtingai nuo daugelio kitų metodų) ir visi objektai, esantys leistinajame diapazone.
Kita įdomi DBSCAN savybė yra ta, kad jos sudėtingumas yra gana mažas – tam reikia linijinio diapazono užklausų skaičiaus duomenų bazėje. Taip pat neįprasta, kad jis ras iš esmės tuos pačius rezultatus (tai deterministiška šerdies ir triukšmo taškams, bet ne ribiniams elementams) kiekviename paleidime. Todėl nereikia jo paleisti kelis kartus.
Pagrindinis DBSCAN ir OPTICS trūkumas yra tas, kad norint aptikti klasterių ribas, jie tikisi, kad tankis sumažės. Pavyzdžiui, duomenų rinkiniuose su persidengiančiais Gauso skirstiniais – įprastas dirbtinių objektų naudojimo atvejis – šių algoritmų sugeneruotos klasterių ribos dažnai atrodo savavališkos. Taip atsitinka todėl, kad grupių tankis nuolat mažėja. Gauso mišinio duomenų rinkinyje šie algoritmai beveik visada pranoksta tokius metodus kaip EM klasterizavimas, kurie gali tiksliai modeliuoti tokio tipo sistemas.
Vidutinis poslinkis yra grupavimo metodas, kai kiekvienas objektas perkeliamas į tankiausią kaimynystėje esančią sritį, remiantis viso branduolio įvertinimu. Galų gale objektai susilieja į vietines nepralaidumo maksimumus. Panašiai kaip k-means klasterizavimas, šie „tankio pritraukėjai“gali būti duomenų rinkinio atstovai. Tačiau vidutinis poslinkisgali aptikti savavališkos formos grupes, panašias į DBSCAN. Dėl brangios kartotinės procedūros ir tankio įvertinimo vidutinis poslinkis paprastai yra lėtesnis nei DBSCAN arba k-Means. Be to, įprastą poslinkio algoritmą sunku pritaikyti didelės apimties duomenims dėl nevienodo branduolio tankio įvertinimo elgesio, dėl kurio per daug susiskaido klasterio uodegos.
Įvertinimas
Patikrinti grupavimo rezultatus taip pat sunku, kaip ir patį grupavimą. Populiariausi metodai apima „vidinį“įvertinimą (kai sistema sumažinama iki vieno kokybės mato) ir, žinoma, „išorinį“įvertinimą (kai klasterizavimas lyginamas su esama „pagrindinės tiesos“klasifikacija). O žmogaus eksperto rankinis balas ir netiesioginis balas nustatomi išnagrinėjus klasterizacijos naudingumą numatytoje programoje.
Vidinės žymėjimo priemonės turi problemų, nes jos atspindi ypatybes, kurios pačios gali būti laikomos grupavimo tikslais. Pavyzdžiui, galima grupuoti duomenis, pateiktus pagal silueto koeficientą, išskyrus tai, kad nėra žinomo efektyvaus algoritmo, kaip tai padaryti. Naudojant tokią vidinę vertinimo priemonę, geriau palyginti optimizavimo uždavinių panašumą.
Išorinis ženklas turi panašių problemų. Jei yra tokios „pagrindinės tiesos“etiketės, tada nereikia klasterizuotis. O praktikoje tokių sąvokų paprastai nėra. Kita vertus, etiketės atspindi tik vieną galimą duomenų rinkinio skaidinį, o tai nereiškiakad nėra kitos (gal net geresnės) klasterizacijos.
Taigi, nė vienas iš šių metodų negali galutinai įvertinti tikrosios kokybės. Tačiau tam reikia žmogaus vertinimo, kuris yra labai subjektyvus. Nepaisant to, tokia statistika gali būti naudinga nustatant blogas grupes. Tačiau nereikėtų nuvertinti subjektyvaus žmogaus vertinimo.
Vidinis ženklas
Kai klasterizacijos rezultatas vertinamas remiantis duomenimis, kurie patys buvo sugrupuoti, tai vadinama šiuo terminu. Šie metodai paprastai priskiria geriausią rezultatą algoritmui, kuris sukuria grupes su dideliu panašumu ir mažu tarp grupių. Vienas iš vidinių kriterijų naudojimo klasterio vertinime trūkumų yra tas, kad aukšti balai nebūtinai lemia efektyvias informacijos paieškos programas. Be to, šis rezultatas yra nukreiptas į algoritmus, kurie naudoja tą patį modelį. Pavyzdžiui, k-means klasterizavimas natūraliai optimizuoja objektų atstumus, o juo pagrįstas vidinis kriterijus greičiausiai pervertins gautą grupavimą.
Todėl šios vertinimo priemonės geriausiai tinka norint susidaryti vaizdą apie situacijas, kai vienas algoritmas veikia geriau nei kitas. Tačiau tai nereiškia, kad kiekviena informacija suteikia patikimesnių rezultatų nei kita. Galiojimo laikotarpis, išmatuotas tokiu indeksu, priklauso nuo tvirtinimo, kad struktūra egzistuoja duomenų rinkinyje. Kai kuriems tipams sukurtas algoritmas neturi šansų, jei rinkinyje yra radikaliaiskirtinga sudėtis arba jei vertinami skirtingi kriterijai. Pavyzdžiui, k-mean klasterizavimas gali rasti tik išgaubtas grupes, o daugelis balų indeksų turi tą patį formatą. Duomenų rinkinyje su neišgaubtais modeliais netinkama naudoti k vidurkius ir tipinius vertinimo kriterijus.
Išorinis įvertinimas
Šio tipo balų sudarymo metu grupavimo rezultatai vertinami remiantis duomenimis, kurie nebuvo naudojami grupuojant. Tai yra, pavyzdžiui, žinomos klasės etiketės ir išoriniai testai. Tokie klausimai susideda iš iš anksto įslaptintų elementų rinkinio ir dažnai juos sukuria ekspertai (žmonės). Taigi informaciniai rinkiniai gali būti laikomi auksiniu vertinimo standartu. Šio tipo balų skaičiavimo metodai matuoja, kaip klasteris yra arti nurodytų atskaitos klasių. Tačiau neseniai buvo diskutuojama, ar tai tinka tikriems duomenims, ar tik sintetiniams rinkiniams, turintiems tikrąją pagrindinę tiesą. Kadangi klasėse gali būti vidinė struktūra, o esami atributai gali neleisti atskirti grupių. Be to, žinių atradimo požiūriu žinomų faktų atkūrimas nebūtinai gali duoti laukiamo rezultato. Pagal specialų apribotą grupavimo scenarijų, kai metainformacija (pvz., klasių etiketės) jau naudojama grupavimo procese, nėra trivialu saugoti visą informaciją vertinimo tikslais.
Dabar aišku, kas netaikoma klasterizacijos metodams ir kokie modeliai naudojami šiems tikslams.
