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 muitakin etäisyysmittoja voidaan käyttää. Jokainen datapiste sijoitetaan siihen klusteriin, jota lähin sentroidi edustaa.

Päivitysvaihe

Kun kaikki datapisteet on liitetty klustereihin, sentroidit lasketaan uudelleen. Jokaiselle klusterille uusi sentroidi lasketaan kaikkien kyseiseen klusteriin kuuluvien datapisteiden keskiarvona. Käytännössä sentroidi 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äytysehto 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ä saavutettu: ennalta määritelty iteraatioiden enimmäismäärä saavutetaan. Tämä estää algoritmia jatkamasta loputtomiin.

Kun konvergenssi saavutetaan, K-means-algoritmi on jakanut datan K klusteriin, joista jokaista edustaa oma sentroidinsa. Tuloksena olevat klusterit pyritään pitämään sisäisesti yhtenäisinä ja ulkoisesti erillisinä valitun etäisyysmitan ja iteratiivisen tarkennuksen perusteella.