Initialisatie

Het algoritme begint met het willekeurig selecteren van K initiële clustercentra, ook wel centroïden genoemd. Deze centroïden dienen als startpunten voor elke cluster. Een gangbare methode is om willekeurig K datapunten uit de dataset te kiezen als de initiële centroïden.

Toewijzingsstap

In deze stap wordt elk datapunt toegewezen aan de dichtstbijzijnde centroïde. De afstand wordt meestal gemeten met behulp van de Euclidische afstand, maar andere afstandsmaatstaven kunnen ook worden gebruikt. Elk datapunt wordt geplaatst in de cluster die wordt vertegenwoordigd door de dichtstbijzijnde centroïde.

Update-stap

Zodra alle datapunten aan clusters zijn toegewezen, worden de centroïden herberekend. Voor elke cluster wordt de nieuwe centroïde berekend als het gemiddelde van alle datapunten die tot die cluster behoren. In wezen wordt de centroïde verplaatst naar het midden van zijn cluster.

Iteratie

Stap 2 en 3 worden iteratief herhaald. In elke iteratie worden datapunten opnieuw toegewezen aan clusters op basis van de bijgewerkte centroïden, en vervolgens worden de centroïden herberekend op basis van de nieuwe clusterindelingen. Dit iteratieve proces gaat door totdat aan een stopcriterium is voldaan.

Convergentie

Het algoritme stopt wanneer aan een van de volgende voorwaarden is voldaan:

• Centroïden veranderen niet significant: de posities van de centroïden stabiliseren, wat betekent dat er in opeenvolgende iteraties minimale verandering is in hun locaties;

• Toewijzingen van datapunten veranderen niet: datapunten blijven in dezelfde clusters, wat aangeeft dat de clusterstructuur stabiel is geworden;

• Maximaal aantal iteraties is bereikt: een vooraf gedefinieerd maximaal aantal iteraties is bereikt. Dit voorkomt dat het algoritme oneindig blijft draaien.

Na convergentie heeft het K-means algoritme de data opgedeeld in K clusters, waarbij elke cluster wordt vertegenwoordigd door zijn centroïde. De resulterende clusters zijn bedoeld om intern samenhangend en extern gescheiden te zijn op basis van de gekozen afstandsmaatstaf en het iteratieve verfijningsproces.