Initialisering

Algoritmen starter med å tilfeldig velge K innledende klyngesentre, også kjent som sentroider. Disse sentroidene fungerer som utgangspunkt for hver klynge. En vanlig tilnærming er å tilfeldig velge K datapunkter fra datasettet som de innledende sentroidene.

Tildelingssteg

I dette steget blir hvert datapunkt tildelt den nærmeste sentroiden. Avstanden måles vanligvis med Euklidsk avstand, men andre avstandsmål kan også benyttes. Hvert datapunkt plasseres i klyngen som representeres av den nærmeste sentroiden.

Oppdateringssteg

Når alle datapunkter er tildelt klynger, blir sentroidene rekalkulert. For hver klynge beregnes den nye sentroiden som gjennomsnittet av alle datapunktene som tilhører den klyngen. I hovedsak flyttes sentroiden til midten av sin klynge.

Iterasjon

Steg 2 og 3 gjentas iterativt. I hver iterasjon blir datapunktene tildelt klynger på nytt basert på de oppdaterte sentroidene, og deretter rekalkuleres sentroidene basert på de nye klyngetildelingene. Denne iterative prosessen fortsetter til et stoppkriterium er oppfylt.

Konvergens

Algoritmen stopper når ett av følgende kriterier er oppfylt:

• Sentroidene endrer seg ikke vesentlig: posisjonene til sentroidene stabiliseres, noe som betyr at det i påfølgende iterasjoner er minimal endring i deres plassering;

• Tildelingene av datapunkter endres ikke: datapunktene forblir i de samme klyngene, noe som indikerer at klyngestrukturen har blitt stabil;

• Maksimalt antall iterasjoner er nådd: et forhåndsdefinert maksimalt antall iterasjoner er nådd. Dette forhindrer at algoritmen kjører uendelig lenge.

Når algoritmen har konvergert, har K-means delt dataene inn i K klynger, hvor hver klynge er representert av sin sentroid. De resulterende klyngene skal være internt sammenhengende og eksternt adskilte basert på valgt avstandsmål og den iterative forbedringsprosessen.