Alustus

Algoritmi alkaa valitsemalla satunnaisesti K alkuperäistä klusterikeskipistettä, joita kutsutaan myös sentroideiksi. Nämä sentroidit toimivat jokaisen klusterin lähtöpisteinä. Yleinen tapa on valita satunnaisesti K datapistettä aineistosta alkusentroidiksi.

Kohdistusvaihe

Tässä vaiheessa jokainen datapiste liitetään lähimpään sentroidiin. Etäisyys mitataan tyypillisesti euklidisella etäisyydellä, mutta myös muita etäisyysmittoja voidaan käyttää. Jokainen datapiste sijoitetaan siihen klusteriin, jota lähin sentrodi edustaa.

Päivitysvaihe

Kun kaikki datapisteet on liitetty klustereihin, sentroidit lasketaan uudelleen. Jokaiselle klusterille uusi sentrodi lasketaan kaikkien kyseiseen klusteriin kuuluvien datapisteiden keskiarvona. Käytännössä sentrodi siirtyy klusterinsa keskelle.

Iterointi

Vaiheita 2 ja 3 toistetaan iteratiivisesti. Jokaisella iteraatiolla datapisteet kohdistetaan uudelleen klustereihin päivitettyjen sentroidien perusteella, ja sitten sentroidit lasketaan uudelleen uusien klusterijakojen mukaan. Tätä iteratiivista prosessia jatketaan, kunnes pysäytyskriteeri täyttyy.

Konvergenssi

Algoritmi pysähtyy, kun jokin seuraavista ehdoista täyttyy:

• Sentroidit eivät muutu merkittävästi: sentroidien sijainnit vakiintuvat, eli seuraavissa iteraatioissa niiden sijainneissa tapahtuu vain vähäisiä muutoksia;

• Datapisteiden klusterijako ei muutu: datapisteet pysyvät samoissa klustereissa, mikä osoittaa, että klusterirakenne on vakiintunut;

• Maksimi iteraatiomäärä saavutetaan: ennalta määritelty suurin sallittu iteraatiomäärä saavutetaan. Tämä estää algoritmia jatkamasta loputtomasti.

Konvergenssin jälkeen K-means-algoritmi on jakanut datan K klusteriin, joista jokaista edustaa oma sentrodinsa. Tuloksena saadut klusterit pyritään pitämään sisäisesti yhtenäisinä ja ulkoisesti erillisinä valitun etäisyysmitan ja iteratiivisen tarkennuksen perusteella.