Initialisering

Algoritmen starter med at tilfældigvis vælge K indledende klyngecentre, også kaldet centroider. Disse centroider fungerer som udgangspunkter for hver klynge. En almindelig metode er tilfældigt at vælge K datapunkter fra datasættet som de indledende centroider.

Tildelingsfase

I denne fase tildeles hvert datapunkt til den nærmeste centroid. Afstanden måles typisk ved hjælp af Euklidisk afstand, men andre afstandsmål kan også anvendes. Hvert datapunkt placeres i den klynge, der repræsenteres af den nærmeste centroid.

Opdateringsfase

Når alle datapunkter er tildelt klynger, bliver centroiderne beregnet på ny. For hver klynge beregnes den nye centroid som gennemsnittet af alle datapunkter, der tilhører den pågældende klynge. I praksis flyttes centroiden til midten af sin klynge.

Iteration

Trin 2 og 3 gentages iterativt. I hver iteration tildeles datapunkterne på ny til klynger baseret på de opdaterede centroider, og derefter beregnes centroiderne på ny ud fra de nye klyngetildelinger. Denne iterative proces fortsætter, indtil et stopkriterium er opfyldt.

Konvergens

Algoritmen stopper, når en af følgende betingelser er opfyldt:

• Centroider ændrer sig ikke væsentligt: Centroiderne stabiliseres, hvilket betyder, at der i de efterfølgende iterationer kun er minimale ændringer i deres positioner;

• Tildelinger af datapunkter ændrer sig ikke: Datapunkterne forbliver i de samme klynger, hvilket indikerer, at klyngestrukturen er blevet stabil;

• Maksimalt antal iterationer er nået: Et foruddefineret maksimalt antal iterationer er nået. Dette forhindrer algoritmen i at køre uendeligt.

Når algoritmen konvergerer, har K-means opdelt dataene i K klynger, hvor hver klynge er repræsenteret ved sin centroid. De resulterende klynger tilstræber at være internt sammenhængende og eksternt adskilte baseret på den valgte afstandsmetrik og den iterative forfinelsesproces.