Initialisering

Algoritmen börjar med att slumpmässigt välja K initiala klustercentra, även kallade centroider. Dessa centroider fungerar som startpunkter för varje kluster. En vanlig metod är att slumpmässigt välja K datapunkter från datamängden som de initiala centroiderna.

Tilldelningssteg

I detta steg tilldelas varje datapunkt till den närmsta centroiden. Avståndet mäts vanligtvis med euklidiskt avstånd, men andra avståndsmått kan också användas. Varje datapunkt placeras i det kluster som representeras av den närmaste centroiden.

Uppdateringssteg

När alla datapunkter har tilldelats kluster beräknas centroiderna om. För varje kluster beräknas den nya centroiden som medelvärdet av alla datapunkter som tillhör det klustret. I princip flyttas centroiden till mitten av sitt kluster.

Iteration

Steg 2 och 3 upprepas iterativt. Vid varje iteration tilldelas datapunkterna om till kluster baserat på de uppdaterade centroiderna, och därefter beräknas centroiderna om utifrån de nya klustertilldelningarna. Denna iterativa process fortsätter tills ett stoppkriterium uppfylls.

Konvergens

Algoritmen avslutas när ett av följande villkor är uppfyllt:

• Centroiderna förändras inte nämnvärt: centroidernas positioner stabiliseras, vilket innebär att det sker minimal förändring i deras lägen mellan iterationerna;

• Datapunkternas tilldelning förändras inte: datapunkterna stannar kvar i samma kluster, vilket indikerar att klusterstrukturen har blivit stabil;

• Maximalt antal iterationer har uppnåtts: ett fördefinierat maximalt antal iterationer har nåtts. Detta förhindrar att algoritmen körs på obestämd tid.

Vid konvergens har K-means-algoritmen delat upp datan i K kluster, där varje kluster representeras av sin centroid. De resulterande klustren syftar till att vara internt sammanhållna och externt separerade baserat på det valda avståndsmåttet och den iterativa förfiningsprocessen.