Kas yra K-Means klasterizavimas?

K-means klasterizavimas yra an neprižiūrimas mokymasis algoritmas, o iš visų neprižiūrimų mokymosi algoritmų K-means klasterizavimas gali būti plačiausiai naudojamas dėl savo galios ir paprastumo. Kaip tiksliai veikia K-means klasterizavimas?

Trumpas atsakymas yra tas, kad K reiškia grupavimas veikia pagal atskaitos taško (centroido) kūrimas norimam užsiėmimų skaičiui ir tada duomenų taškų priskyrimas klasių klasteriams pagal tai, kuris atskaitos taškas yra arčiausiai. Nors tai yra greitas K-means klasterizacijos apibrėžimas, šiek tiek pasinerkime į K-means klasterizavimą ir gaukime geresnę intuiciją, kaip ji veikia.

Klasterizacijos apibrėžimas

Prieš nagrinėdami tikslius algoritmus, naudojamus K-means klasterizavimui, užtrukkime šiek tiek laiko, kad apibrėžtume grupavimą apskritai.

Klasteriai yra tik elementų grupės, o grupavimas yra tik elementų įtraukimas į tas grupes. Duomenų mokslo prasme, klasterizacijos algoritmai siekiama padaryti du dalykus:

• Įsitikinkite, kad visi duomenų taškai klasteryje yra kuo panašesni vienas į kitą.
• Įsitikinkite, kad visi duomenų taškai skirtinguose klasteriuose yra kuo nepanašesni vienas į kitą.

Klasterizacijos algoritmai sugrupuoja elementus pagal tam tikrą panašumo metriką. Tai dažnai daroma surandant skirtingų galimų duomenų rinkinio grupių „centroidą“, nors ir ne tik. Yra daugybė skirtingų grupavimo algoritmų, tačiau visų grupavimo algoritmų tikslas yra tas pats – nustatyti duomenų rinkiniui būdingas grupes.

„K“ reiškia grupavimą

„K-Means Clustering“ yra vienas iš seniausių ir dažniausiai naudojamų klasterizacijos algoritmų tipų ir veikia remiantis vektoriaus kvantavimas. Erdvės taškas yra pasirinktas kaip pradžios taškas, o tada vektoriai nubrėžiami nuo pradžios iki visų duomenų rinkinio duomenų taškų.

Apskritai K-means klasterizavimą galima suskirstyti į penkis skirtingus etapus:

• Visus atvejus sudėkite į poaibius, kur poaibių skaičius lygus K.
• Raskite naujai sukurtų klasterio skaidinių vidurinį tašką/centroidą.
• Remdamiesi šiais centroidais, priskirkite kiekvieną tašką konkrečiam klasteriui.
• Apskaičiuokite atstumus nuo kiekvieno taško iki centroidų ir priskirkite taškus klasteriams, kuriuose atstumas nuo centroido yra mažiausias.
• Priskyrę taškus klasteriams, raskite naują klasterių centroidą.

Pirmiau minėti veiksmai kartojami tol, kol baigsis treniruočių procesas.

Pradiniame etape centroidai dedami kažkur tarp duomenų taškų.
Nuotrauka: Weston.pace per wikimedia commons, GNU nemokama dokumentacijos licencija (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Arba po to, kai centroidai yra išdėstyti, galime įsivaizduoti, kad K-means klasterizuojasi kaip keitimasis pirmyn ir atgal tarp dviejų skirtingų fazių: duomenų taškų žymėjimo ir centroidų atnaujinimo.

Antrame žingsnyje atstumo metrika, pvz., Euklido atstumas, naudojama norint apskaičiuoti, kuriam centroidui tam tikras taškas yra arčiausiai, o tada taškai priskiriami to centroido klasei. Nuotrauka: Weston.pace per Wikimedia Commons, GNU nemokama dokumento licencija (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

Duomenų taško žymėjimo fazėje kiekvienam duomenų taškui priskiriama etiketė, kuri įdeda jį į klasterį, priklausantį artimiausiam centroidui. Artimiausias centroidas paprastai nustatomas naudojant kvadratinį Euklido atstumą, nors gali būti naudojamos kitos atstumo metrikos, tokios kaip Manheteno atstumas, kosinusas ir Žakaro atstumas, atsižvelgiant į duomenų tipą, įvedamą į klasterizacijos algoritmą.

Trečiajame etape centroidas perkeliamas į visų duomenų taškų vidurkį. Tada klasės perskirstomos. Nuotrauka: Weston.pace per Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

Atnaujinant centroidą, centroidas apskaičiuojamas nustatant vidutinį atstumą tarp visų šiuo metu klasteryje esančių duomenų taškų.

Kaip pasirinkti tinkamą „K“ reikšmę

Atsižvelgiant į tai, kad K-means klasterizavimas yra neprižiūrimas algoritmas ir klasių skaičius nėra žinomas iš anksto, kaip nuspręsti dėl tinkamo klasių skaičiaus / tinkamos K reikšmės?

Vienas iš būdų, kaip pasirinkti tinkamą K reikšmę, vadinamas „alkūnės technika“. Alkūnės techniką sudaro K vidurkių klasterizacijos algoritmo paleidimas įvairioms K vertėms ir tikslumo metrikos, paprastai kvadratinės klaidos suma, naudojimas, siekiant nustatyti, kurios K reikšmės duoda geriausius rezultatus. Klaidos kvadrato suma nustatoma apskaičiuojant vidutinį atstumą tarp klasterio centroido ir tos klasterio duomenų taškų.

Sąvoka „alkūnės technika“ kilusi iš to, kad kai braižote SSE, atsižvelgdami į skirtingas K reikšmes, gautas linijos grafikas dažnai turi „alkūnės“ formą, kur SSE greitai mažėja per kelias pirmąsias K reikšmes, bet paskui išsilygina. Tokiomis sąlygomis K vertė, esanti ties alkūne, yra geriausia K reikšmė, nes po šios reikšmės grąža greitai mažėja.

Mini-Batch K-Means klasterizavimas

Didėjant duomenų rinkiniams, didėja ir skaičiavimo laikas. Pagrindinis K-means klasterizavimas gali užtrukti ilgai, kai jis vykdomas naudojant didžiulius duomenų rinkinius, todėl buvo atlikti K-means klasterizacijos patobulinimai, leidžiantys sumažinti algoritmo erdvines ir laiko sąnaudas.

Mini-Batch K reiškia grupavimą yra K-means klasterizacijos variantas kur ribojamas svarstomo duomenų rinkinio dydis. Įprastas „K-means“ grupavimas vienu metu veikia visame duomenų rinkinyje / pakete, o „Mini-Batch K-means“ grupavimas suskirsto duomenų rinkinį į poaibius. Mini partijos atsitiktinai atrenkamos iš viso duomenų rinkinio ir kiekvienai naujai iteracijai parenkama nauja atsitiktinė imtis ir naudojama centroidų padėčiai atnaujinti.

Klasterizuojant „Mini-Batch K-Means“, klasteriai atnaujinami derinant mini paketo reikšmes ir mokymosi greitį. Mokymosi greitis mažėja per iteracijas ir yra atvirkštinis duomenų taškų, esančių konkrečioje klasteryje, skaičiui. Mokymosi greičio mažinimo efektas yra tas, kad sumažėja naujų duomenų įtaka ir pasiekiama konvergencija, kai po kelių iteracijų klasteriuose nėra pokyčių.

Mini-partijos K-means klasterizacijos veiksmingumo tyrimų rezultatai rodo, kad jis gali sėkmingai sumažinti skaičiavimo laiką, šiek tiek pakeitus klasterio kokybę.

K-Means klasterizacijos taikymai

K-means klasterizavimą galima saugiai naudoti bet kurioje situacijoje, kai duomenų taškai gali būti suskirstyti į atskiras grupes/klases. Štai keletas įprastų K vidurkio klasterių naudojimo atvejų pavyzdžių.

K-means klasterizavimas gali būti taikomas dokumentų klasifikavimui, grupuojant dokumentus pagal tokias funkcijas kaip temos, žymos, žodžių vartojimas, metaduomenys ir kitos dokumento funkcijos. Jis taip pat gali būti naudojamas klasifikuojant vartotojus kaip robotus ar ne robotus pagal veiklos modelius, pvz., įrašus ir komentarus. K-means klasterizavimas taip pat gali būti naudojamas suskirstyti žmones į grupes pagal susirūpinimą keliantį lygį stebint jų sveikatą, remiantis tokiais požymiais kaip gretutinės ligos, amžius, paciento istorija ir kt.

K-means klasterizavimas taip pat gali būti naudojamas atliekant atviresnes užduotis, pvz., kuriant rekomendacijų sistemas. Tokios sistemos kaip „Netflix“ naudotojai gali būti sugrupuoti pagal žiūrėjimo būdus ir rekomenduojamą panašų turinį. K-means klasterizavimas gali būti naudojamas anomalijų aptikimo užduotims, išryškinant galimus sukčiavimo ar sugedusių elementų atvejus.