Mikä on K-Means-klusterointi?

K-Means-klusterointi on valvomaton oppiminen -algoritmi, ja kaikista valvomattomista oppimisalgoritmeista K-Means-klusterointi on ehkä laajimmin käytetty, sen voiman ja yksinkertaisuuden ansiosta. Miten K-Means-klusterointi toimii tarkalleen?

Lyhyt vastaus on, että K-Means-klusterointi toimii luomalla viitepisteen (sentroidin) halutun määrän luokkia varten, ja sitten määrittämällä data-pisteet luokkaan klustereiden perusteella, joka on lähimpänä viitepistettä. Vaikka tämä on nopea määritelmä K-Means-klusteroinnille, otetaan hieman aikaa perehtyäkseen K-Means-klusterointiin ja saadaan parempi intuitio siitä, miten se toimii.

Klusteroinnin määrittely

Ennen kuin tarkastellaan tarkalleen algoritmeja, joita käytetään K-Means-klusteroinnin suorittamiseen, otetaan hetki aikaa määritellä klusterointia yleisesti.

Klusterit ovat vain ryhmiä, ja klusterointi on vain asettaminen ryhmiin. Data-tieteellisessä mielessä klusterointialgoritmit pyrkivät tekemään kaksi asiaa:

• Takaavat, että kaikki data-pisteet klusterissa ovat mahdollisimman samanlaisia toisiinsa nähden.
• Takaavat, että kaikki data-pisteet eri klustereissa ovat mahdollisimman erilaisia toisiinsa nähden.

Klusterointialgoritmit ryhmittelevät kohteita jonkin samankaltaisuuden mittarin perusteella. Tämä tehdään usein etsimällä “sentroidi” eri mahdollisista ryhmistä tietojoukossa, vaikka ei yksinomaan. On olemassa erilaisia klusterointialgoritmeja, mutta kaikkien klusterointialgoritmien tavoitteena on sama, määrätä joukon sisäiset ryhmät.

K-Means-klusterointi

K-Means-klusterointi on yksi vanhimmista ja yleisimmin käytetyistä klusterointialgoritmeista, ja se toimii vektori-kvantalisoinnin perusteella. On piste avaruudessa, josta valitaan alkuperä, ja sitten piirretään vektoreita alkuperästä tietojoukon kaikkiin data-pisteisiin.

Yleensä K-Means-klusterointi voidaan jakaa viiteen eri vaiheeseen:

• Aseta kaikki instanssit alijoukkoihin, joissa alijoukkojen määrä on yhtä suuri kuin K.
• Etsi uuden klusterijakojen keskipiste/keskiarvo.
• Pohjautuen näihin sentroideihin, määritä kunkin pisteen tiettyyn klusteriin.
• Lasketaan etäisyydet jokaisesta pisteestä sentroideihin ja määritä pisteet klustereihin, joissa etäisyys sentroidista on vähin.
• Kun pisteet on määritetty klustereihin, etsi uudet klusterien sentroidit.

Yllä mainitut vaiheet toistetaan, kunnes koulutusprosessi on valmis.

Alkuvaiheessa sentroidit asetetaan jonnekin data-pisteiden sekaan.
Kuva: Weston.pace via wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternatiivisesti, kun sentroidit on asetettu, voidaan K-Means-klusterointia ajatella vaihtelevan kahden eri vaiheen välillä: data-pisteiden merkintä ja sentroidien päivittäminen.

Toisessa vaiheessa etäisyysmittari, kuten euklidinen etäisyys, käytetään laskemaan, mihin sentroidiin tietty piste on lähimpänä, ja sitten pisteet määritetään kyseisen sentroidin luokkaan. Kuva: Weston.pace via Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

Data-pisteiden merkintävaiheessa jokainen data-piste määritetään merkinnällä, joka asettaa sen lähimpään sentroidin klusteriin. Lähin sentroidi määritetään yleensä käyttämällä neliöitä euklidista etäisyyttä, vaikka muita etäisyysmittareita, kuten Manhattanin etäisyyttä, kosini- ja Jaccard- etäisyyttä, voidaan käyttää riippuen siitä, minkälaista dataa syötetään klusterointialgoritmiin.

Kolmannessa vaiheessa sentroidit siirretään kaikkien data-pisteiden keskiarvoon. Luokat määritetään uudelleen. Kuva: Weston.pace via Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

Sentroidien päivittämisvaiheessa sentroidit lasketaan etsimällä keskietäisyys kaikkien data-pisteiden välillä, jotka ovat tällä hetkellä klusterissa.

Miten valita oikea arvo “K”:lle

Koska K-Means-klusterointi on valvomaton algoritmi ja luokkien määrä ei ole tiedossa etukäteen, miten päättää oikean luokkien määrästä / oikeasta arvosta “K”:sta?

Yksi tekniikka oikean K-arvon valitsemiseen on kutsuttu “kyynärmenetelmäksi“. Kyynärmenetelmä koostuu K-Means-klusterointialgoritmin suorittamisesta eri K-arvojen joukossa ja tarkkuusmittarin, yleensä Sum of Squared Error, käyttämisestä määrittämiseen, mitkä K-arvot antavat parhaat tulokset. Sum of Squared Error määritetään laskemalla keskietäisyys klusterin sentroidin ja klusterin data-pisteiden välillä.

Kyynärmenetelmän termi tulee siitä, että kun piirrät SSE:n eri K-arvojen suhteen, tuloksena oleva linjakaavio on usein “kyynär”-muotoinen, jossa SSE vähenee nopeasti ensimmäisten K-arvojen osalla, mutta sitten tasoittuu. Tällaisissa olosuhteissa K-arvo, joka sijaitsee kyynärvaiheessa, on paras arvo K:lle, koska siitä eteenpäin on nopeasti vähenevät palautusarvot.

Mini-Batch K-Means-klusterointi

Kun tietojoukot kasvavat suuremmaksi, laskenta-aika kasvaa myös. Perus-K-Means-klusterointi voi kestää pitkään, kun se suoritetaan massiivisilla tietojoukoilla, ja tästä syystä K-Means-klusterointiin on tehty muutoksia, jotta algoritmin tila- ja aikakustannukset voidaan vähentää.

Mini-Batch K-Means-klusterointi on K-Means-klusteroinnin variantti, jossa tietojoukon koko, jota tarkkaillaan, on rajoitettu. Normaali K-Means-klusterointi toimii koko tietojoukon kanssa kerran, kun taas Mini-Batch K-Means-klusterointi jaa tietojoukon osiin. Mini-erät otetaan satunnaisesti koko tietojoukosta, ja kunkin uuden iteraation kohdalla valitaan uusi satunnainen otos ja käytetään päivittämään sentroidien sijaintia.

Mini-Batch K-Means-klusteroinnissa klusterit päivitetään yhdistämällä mini-erän arvot ja oppimissuhde. Oppimissuhde vähenee iteraatioiden aikana, ja se on käänteisesti suhteessa data-pisteiden määrään, jotka on asetettu tiettyyn klusteriin. Oppimissuhteen vähentämisen vaikutus on, että uuden datan vaikutus vähenee, ja konvergenssi saavutetaan, kun useiden iteraatioiden jälkeen klustereissa ei ole muutoksia.

Tutkimusten tulokset Mini-Batch K-Means-klusteroinnin tehokkuudesta osoittavat, että se voi vähentää laskenta-aikaa pienellä kompromissilla klusterin laadun suhteen.

K-Means-klusteroinnin sovellukset

K-Means-klusterointia voidaan käyttää turvallisesti mihin tahansa tilanteeseen, jossa data-pisteet voidaan jakaa eri ryhmiin / luokkiin. Tässä on joitain yleisiä K-Means-klusteroinnin käyttötapauksia.

K-Means-klusterointia voidaan soveltaa asiakirjojen luokitteluun, jossa asiakirjat ryhmitellään ominaisuuksien, kuten aiheiden, tagien, sanan käytön, metatiedon ja muiden asiakirjojen ominaisuuksien perusteella. Sitä voidaan myös käyttää luokittamaan käyttäjiä boteiksi tai ei-boteiksi toimintamallien perusteella, kuten viestien ja kommenttien perusteella. K-Means-klusterointia voidaan käyttää myös ryhmittelemään ihmisiä ryhmiin terveydenhuollon seuraamisen perusteella, kuten sairauksien, iän, potilashistorian jne. perusteella.

K-Means-klusterointia voidaan myös käyttää avoimempiin tehtäviin, kuten suosittelujärjestelmien luomiseen. Käyttäjät, kuten Netflixin käyttäjät, voidaan ryhmitellä yhteen katselumallien perusteella ja suositella samanlaista sisältöä. K-Means-klusterointia voidaan käyttää myös poikkeamien havaitsemistehtäviin, jossa korostetaan mahdollisia petos- tai viallisia kohteita.