Klasteru veidošanas metode ir uzdevums grupēt objektu kopu tā, lai tie vienā grupā būtu vairāk līdzīgi viens otram nekā objektiem citās nozarēs. Tas ir galvenais datu ieguves uzdevums un vispārīga statistiskās analīzes tehnika, ko izmanto daudzās jomās, tostarp mašīnmācībā, modeļu atpazīšanas, attēlu atpazīšanas, informācijas izguves, datu saspiešanas un datorgrafikas jomā.
Optimizācijas problēma
Pati klasterizācijas metode nav viens konkrēts algoritms, bet gan vispārīgs uzdevums, kas jāatrisina. To var panākt ar dažādiem algoritmiem, kas būtiski atšķiras izpratnē, kas veido grupu un kā to efektīvi atrast. Klasterizācijas metodes izmantošana metasubjektu veidošanai ietver grupas izmantošanu arnelieli attālumi starp dalībniekiem, blīvi telpas apgabali, intervāli vai noteikti statistikas sadalījumi. Tāpēc klasterizāciju var formulēt kā vairāku mērķu optimizācijas problēmu.
Atbilstošā metode un parametru iestatījumi (tostarp tādi vienumi kā izmantojamā attāluma funkcija, blīvuma slieksnis vai paredzamo kopu skaits) ir atkarīgi no individuālās datu kopas un paredzētā rezultātu izmantošanas. Analīze kā tāda nav automātisks uzdevums, bet iteratīvs zināšanu atklāšanas vai interaktīvas vairāku mērķu optimizācijas process. Šī klasterizācijas metode ietver izmēģinājumu un kļūdu mēģinājumus. Bieži vien ir nepieciešams modificēt datu pirmapstrādes un modelēšanas parametrus, līdz rezultāts sasniedz vēlamās īpašības.
Papildus terminam "grupēšana" ir vairāki vārdi ar līdzīgu nozīmi, tostarp automātiskā klasifikācija, skaitliskā taksonomija, ganrioloģija un tipoloģiskā analīze. Smalkas atšķirības bieži slēpjas klasterizācijas metodes izmantošanā metasubjektu attiecību veidošanai. Ja datu ieguvē interesē iegūtās grupas, tad automātiskajā klasifikācijā šīs funkcijas jau veic diskriminējošā vara.
Klasteru analīze tika balstīta uz daudziem Krēbera darbiem 1932. gadā. To psiholoģijā ieviesa Zubins 1938. gadā un Roberts Trions 1939. gadā. Un šos darbus Cattell izmantoja kopš 1943. gada, lai norādītu klasterizācijas metožu klasifikāciju teorētiski.
Termiņš
Jēdzienu "kopas" nevar precīzi definēt. Tas ir viens no iemesliem, kāpēc ir tik daudz klasterizācijas metožu. Ir kopsaucējs: datu objektu grupa. Tomēr dažādi pētnieki izmanto dažādus modeļus. Un katrs no šiem klasterizācijas metožu lietojumiem ietver dažādus datus. Dažādu algoritmu atrastais jēdziens ievērojami atšķiras pēc tā īpašībām.
Klasteru veidošanas metodes izmantošana ir galvenais, lai izprastu atšķirības starp instrukcijām. Tipiski kopu modeļi ir šādi:
- Centroid s. Tas ir, piemēram, kad k-means klasterizācija attēlo katru klasteru ar vienu vidējo vektoru.
- Savienojuma modelis s. Tā ir, piemēram, hierarhiska klasterizācija, kas veido modeļus, pamatojoties uz attāluma savienojamību.
- Izplatīšanas modelis s. Šajā gadījumā klasteri tiek modelēti, izmantojot klasterizācijas metodi, lai veidotu metasubjektu statistiskos sadalījumus. Piemēram, daudzfaktoru normālā atdalīšana, kas ir piemērojama gaidu maksimizēšanas algoritmam.
- Blīvuma modelis s. Tie ir, piemēram, DBSCAN (Spatial Clustering Algorithm with Noise) un OPTICS (Order Points for Structure Detection), kas definē kopas kā savienotus blīvus reģionus datu telpā.
- Apakštelpas modelis c. Divu klasteru veidošanā (pazīstama arī kā kopgrupēšana vai divi režīmi) grupas tiek modelētas ar abiem elementiem un atbilstošiem atribūtiem.
- Modeļa s. Daži algoritmi to nedarapilnveidotas attiecības klasterizācijas metodei, lai ģenerētu meta-subjekta rezultātus un vienkārši nodrošinātu informācijas grupēšanu.
- Modelis, kura pamatā ir grafiks s. Kliķe, tas ir, mezglu apakškopa, kurā katrus divus savienojumus malas daļā var uzskatīt par klastera formas prototipu. Kopējā pieprasījuma pavājināšanās ir pazīstama kā kvazikliķes. Tieši tāds pats nosaukums ir parādīts HCS klasterizācijas algoritmā.
- Neironu modeļi s. Vispazīstamākais neuzraudzītais tīkls ir pašorganizējošā karte. Un tieši šos modeļus parasti var raksturot kā līdzīgus vienai vai vairākām iepriekš minētajām klasterizācijas metodēm meta-subjekta rezultātu veidošanai. Tas ietver apakštelpas sistēmas, kad neironu tīkli īsteno nepieciešamo galveno vai neatkarīgo komponentu analīzes formu.
Šis termins faktiski ir šādu grupu kopa, kas parasti satur visus objektus datu klasterizācijas metožu kopā. Turklāt tas var norādīt uz klasteru savstarpējām attiecībām, piemēram, sistēmu hierarhiju, kas iebūvētas viena otrā. Grupēšanu var iedalīt šādos aspektos:
- Cietā centroīdu klasterizācijas metode. Šeit katrs objekts pieder grupai vai atrodas ārpus tās.
- Mīksta vai neskaidra sistēma. Šajā brīdī katrs objekts jau zināmā mērā pieder jebkuram klasterim. To sauc arī par c-means izplūdušo klasterizācijas metodi.
Un iespējamas arī smalkākas atšķirības. Piemēram:
- Stingra sadalīšanas klasterizācija. Šeitkatrs objekts pieder tieši vienai grupai.
- Stingra sadalīšanas klasterizācija ar novirzēm. Šajā gadījumā objekti var arī nepiederēt nevienai klasterim un tikt uzskatīti par nevajadzīgiem.
- Pārklājoša klasterizācija (arī alternatīva, ar vairākiem skatiem). Šeit objekti var piederēt vairāk nekā vienai filiālei. Parasti ietver cietas kopas.
- Hierarhiskās klasterizācijas metodes. Objekti, kas pieder bērngrupai, pieder arī vecāku apakšsistēmai.
- Apakštelpas veidošanās. Lai gan tās ir līdzīgas klasteriem, kas pārklājas, unikāli definētā sistēmā savstarpējām grupām nevajadzētu pārklāties.
Instrukcijas
Kā minēts iepriekš, klasterizācijas algoritmus var klasificēt, pamatojoties uz to klasteru modeli. Nākamajā pārskatā tiks uzskaitīti tikai šo norādījumu redzamākie piemēri. Tā kā var būt vairāk nekā 100 publicētu algoritmu, ne visi nodrošina modeļus savām kopām, tāpēc tos nevar viegli klasificēt.
Nav objektīvi pareiza klasterizācijas algoritma. Bet, kā minēts iepriekš, instrukcija vienmēr atrodas novērotāja redzeslokā. Konkrētai problēmai vispiemērotākais klasterizācijas algoritms bieži ir jāizvēlas eksperimentāli, ja vien nav matemātiska iemesla dot priekšroku vienam modelim, nevis citam. Jāatzīmē, ka algoritms, kas paredzēts vienam tipam, parasti nedarbojasdatu kopa, kas satur radikāli atšķirīgu priekšmetu. Piemēram, k-means nevar atrast neizliektas grupas.
Uz savienojumu balstīta klasterizācija
Šī savienība ir pazīstama arī ar tās nosaukumu, hierarhisko modeli. Tas ir balstīts uz tipisku ideju, ka objekti ir vairāk saistīti ar blakus esošajām daļām, nevis ar tām, kas atrodas daudz tālāk. Šie algoritmi savieno objektus, veidojot dažādas kopas atkarībā no to attāluma. Grupu var raksturot galvenokārt ar maksimālo attālumu, kas nepieciešams, lai savienotu dažādas kopas daļas. Visās iespējamās distancēs veidosies citas grupas, kuras varēs attēlot, izmantojot dendrogrammu. Tas izskaidro, no kurienes nāk vispārpieņemtais nosaukums "hierarhiskā klasterizācija". Tas nozīmē, ka šie algoritmi nenodrošina vienu datu kopas nodalījumu, bet gan nodrošina plašu pilnvaru kārtību. Pateicoties viņam, noteiktos attālumos ir aizplūšana savā starpā. Dendrogrammā y ass apzīmē attālumu, kādā kopas saplūst. Un objekti ir sakārtoti pa X līniju tā, lai grupas nesajauktos.
Uz savienojumu balstīta klasterizācija ir vesela metožu saime, kas atšķiras ar veidu, kā tās aprēķina attālumus. Papildus ierastajai distances funkciju izvēlei lietotājam ir jāizlemj arī par savienojuma kritēriju. Tā kā klasteris sastāv no vairākiem objektiem, tā aprēķināšanai ir daudz iespēju. Populāra izvēle ir pazīstama kā vienas sviras grupēšana, šī ir metodepilna saite, kas satur UPGMA vai WPGMA (nesvērts vai svērts pāru ansamblis ar vidējo aritmētisko, pazīstams arī kā vidējo saišu klasterēšana). Turklāt hierarhiskā sistēma var būt aglomeratīva (sākot ar atsevišķiem elementiem un apvienojot tos grupās) vai daloša (sākot ar pilnīgu datu kopu un sadalot to sadaļās).
Izplatīta klasterizācija
Šie modeļi ir visciešāk saistīti ar statistiku, kuras pamatā ir sadalījumi. Klasterus var viegli definēt kā objektus, kas, visticamāk, pieder vienam un tam pašam sadalījumam. Šīs pieejas ērta iezīme ir tā, ka tā ir ļoti līdzīga mākslīgo datu kopu izveides veidam. Iztverot izlases objektus no sadalījuma.
Lai gan šo metožu teorētiskais pamatojums ir lielisks, tās cieš no vienas galvenās problēmas, kas pazīstama kā pārmērīga pielāgošana, ja vien modeļa sarežģītībai netiek noteikti ierobežojumi. Lielāka asociācija parasti labāk izskaidros datus, tāpēc ir grūti izvēlēties pareizo metodi.
Gausa maisījuma modelis
Šī metode izmanto visu veidu cerību maksimizēšanas algoritmus. Šeit datu kopa parasti tiek modelēta ar fiksētu (lai izvairītos no ignorēšanas) Gausa sadalījumu skaitu, kas tiek inicializēti nejauši un kuru parametri tiek iteratīvi optimizēti, lai labāk atbilstu datu kopai. Šī sistēma konverģēs uz vietējo optimālo. Tāpēc vairāki piegājieni var dotdažādi rezultāti. Lai iegūtu visprecīzāko klasterizāciju, līdzekļi bieži tiek piešķirti Gausa sadalījumam, kuram tie, visticamāk, pieder. Un maigākām grupām tas nav nepieciešams.
Uz izplatīšanu balstīta klasterizācija rada sarežģītus modeļus, kas galu galā var noteikt korelāciju un atkarību starp atribūtiem. Tomēr šie algoritmi lietotājam uzliek papildu slogu. Daudzām reālās pasaules datu kopām var nebūt īsi definēta matemātiskā modeļa (piemēram, pieņemot, ka Gausa sadalījums ir diezgan spēcīgs pieņēmums).
Blīvuma klasterizācija
Šajā piemērā grupas pamatā ir definētas kā apgabali ar lielāku necaurlaidību nekā pārējā datu kopa. Objekti šajās retajās daļās, kas ir nepieciešami visu komponentu atdalīšanai, parasti tiek uzskatīti par trokšņa un malu punktiem.
Populārākā uz blīvumu balstītā klasterizācijas metode ir DBSCAN (telpiskā trokšņa klasterizācijas algoritms). Atšķirībā no daudzām jaunākām metodēm, tai ir labi definēts klastera komponents, ko sauc par "blīvuma sasniedzamību". Līdzīgi kā uz saitēm balstīta klasterizācija, tā ir balstīta uz savienojuma punktiem noteiktos attāluma sliekšņos. Tomēr šī metode apkopo tikai tos vienumus, kas atbilst blīvuma kritērijam. Sākotnējā versijā, kas definēts kā minimālais citu objektu skaits šajā rādiusā, klasteris sastāv no visiemar blīvumu saistīti vienumi (kas var veidot brīvas formas grupu, atšķirībā no daudzām citām metodēm) un visi objekti, kas atrodas atļautajā diapazonā.
Vēl viena interesanta DBSCAN īpašība ir tā, ka tā sarežģītība ir diezgan zema - tam ir nepieciešams lineārs diapazona vaicājumu skaits datu bāzē. Un arī neparasti ir tas, ka tas atradīs būtībā vienādus rezultātus (tas ir deterministiski kodola un trokšņa punktiem, bet ne robeželementiem) katrā darbībā. Tāpēc nav nepieciešams to palaist vairākas reizes.
Galvenais DBSCAN un OPTICS trūkums ir tas, ka tie sagaida zināmu blīvuma samazināšanos, lai noteiktu klasteru robežas. Piemēram, datu kopās ar Gausa sadalījumiem, kas pārklājas (parasti mākslīgiem objektiem), klasteru robežas, ko ģenerē šie algoritmi, bieži šķiet patvaļīgas. Tas notiek tāpēc, ka grupu blīvums nepārtraukti samazinās. Un Gausa maisījumu datu kopā šie algoritmi gandrīz vienmēr pārspēj tādas metodes kā EM klasterēšana, kas spēj precīzi modelēt šāda veida sistēmas.
Vidējā pārvietošanās ir klasterizācijas pieeja, kurā katrs objekts pārvietojas uz apkārtnes blīvāko apgabalu, pamatojoties uz visa kodola aprēķinu. Galu galā objekti saplūst līdz lokālas necaurlaidības maksimumiem. Līdzīgi k-vidējo klasteru veidošanai, šie "blīvuma piesaistītāji" var kalpot kā datu kopas pārstāvji. Bet vidējā maiņavar noteikt patvaļīgas formas kopas, kas līdzīgas DBSCAN. Dārgās iteratīvās procedūras un blīvuma novērtējuma dēļ vidējā nobīde parasti ir lēnāka nekā DBSCAN vai k-Means. Turklāt tipiskā maiņas algoritma pielietojamība augstas dimensijas datiem ir sarežģīta kodola blīvuma novērtējuma nevienmērīgās darbības dēļ, kas izraisa klasteru astes pārmērīgu sadrumstalotību.
Vērtējums
Klasteru veidošanas rezultātu pārbaude ir tikpat sarežģīta kā pati klasterizācija. Populāras pieejas ietver "iekšējo" vērtēšanu (kur sistēma tiek samazināta līdz vienam kvalitātes mēram) un, protams, "ārējo" vērtēšanu (kur klasteru salīdzina ar esošo "pamatpatiesības" klasifikāciju). Cilvēka eksperta manuālais un netiešais rezultāts tiek atrasts, pārbaudot klasterizācijas lietderību paredzētajā lietojumprogrammā.
Iekšējie karoga pasākumi ir saistīti ar problēmu, jo tie atspoguļo līdzekļus, kurus var uzskatīt par klasterizācijas mērķiem. Piemēram, ir iespējams grupēt datus, kas iegūti pēc Silueta koeficienta, izņemot to, ka nav zināms efektīvs algoritms, kā to izdarīt. Izmantojot šādu iekšējo mēru novērtēšanai, labāk ir salīdzināt optimizācijas problēmu līdzību.
Ārējai zīmei ir līdzīgas problēmas. Ja ir tādas "zemes patiesības" birkas, tad nevajag klasterēties. Un praktiskajos lietojumos šādu jēdzienu parasti nav. No otras puses, etiķetes atspoguļo tikai vienu iespējamo datu kopas nodalījumu, kas nenozīmēka nav citas (varbūt pat labākas) klasterizācijas.
Tātad neviena no šīm pieejām nevar noteikt faktisko kvalitāti. Bet tas prasa cilvēka novērtējumu, kas ir ļoti subjektīvs. Tomēr šāda statistika var būt informatīva, lai identificētu sliktās kopas. Taču nevajadzētu atmest subjektīvo cilvēka vērtējumu.
Iekšējā atzīme
Kad klasterizācijas rezultāts tiek novērtēts, pamatojoties uz datiem, kas paši ir grupēti, to dēvē par šo terminu. Šīs metodes parasti piešķir vislabāko rezultātu algoritmam, kas izveido grupas ar augstu līdzību grupās un starp tām zemu. Viens no trūkumiem, kas saistīti ar iekšējo kritēriju izmantošanu klasteru novērtēšanā, ir tas, ka augsti rādītāji ne vienmēr nodrošina efektīvu informācijas izguves lietojumprogrammu. Turklāt šis rādītājs ir novirzīts uz algoritmiem, kas izmanto to pašu modeli. Piemēram, k-vidējā klasterizācija dabiski optimizē objektu attālumus, un uz to balstīts iekšējais kritērijs, iespējams, pārvērtēs iegūto klasterizāciju.
Tāpēc šie novērtēšanas pasākumi ir vispiemērotākie, lai gūtu priekšstatu par situācijām, kad viens algoritms darbojas labāk nekā cits. Bet tas nenozīmē, ka katra informācija sniedz ticamākus rezultātus nekā citi. Derīguma termiņš, ko mēra ar šādu indeksu, ir atkarīgs no apgalvojuma, ka datu kopā pastāv struktūra. Dažiem veidiem izstrādātam algoritmam nav izredžu, ja komplektā ir radikāliatšķirīgu sastāvu vai ja novērtējums mēra dažādus kritērijus. Piemēram, k-mean klasterizācija var atrast tikai izliektas kopas, un daudziem punktu rādītājiem ir tāds pats formāts. Datu kopā ar neizliektiem modeļiem nav pareizi izmantot k-vidējos un tipiskus vērtēšanas kritērijus.
Ārējais novērtējums
Izmantojot šāda veida grupēšanu, klasterizācijas rezultāti tiek novērtēti, pamatojoties uz datiem, kas netika izmantoti grupēšanai. Tas ir, piemēram, zināmās klases etiķetes un ārējie testi. Šādi jautājumi sastāv no iepriekš klasificētu priekšmetu kopas, un tos bieži veido eksperti (cilvēki). Tādējādi atsauces komplektus var uzskatīt par novērtēšanas zelta standartu. Šāda veida vērtēšanas metodes mēra, cik tuvu klasterizācija ir norādītajām atsauces klasēm. Tomēr nesen tika apspriests, vai tas ir piemērots reāliem datiem vai tikai sintētiskām kopām ar faktisku pamata patiesību. Tā kā klasēs var būt iekšēja struktūra, un esošie atribūti var neļaut atdalīt klasterus. Turklāt no zināšanu atklāšanas viedokļa zināmu faktu reproducēšana var ne vienmēr radīt gaidīto rezultātu. Īpašā ierobežotā klasterizācijas scenārijā, kad grupēšanas procesā jau tiek izmantota metainformācija (piemēram, klašu etiķetes), nav triviāli saglabāt visu informāciju novērtēšanas nolūkos.
Tagad ir skaidrs, kas neattiecas uz klasterizācijas metodēm un kādi modeļi tiek izmantoti šiem nolūkiem.
