Następnie uzyskany podział jest poprawiany w ten sposób, że niektóre elementy są przenoszone do innych klas, tak, aby uzyskać minimalną wariancję wewnątrz każdej z nich – dąży się do zapewnienia jak największego podobieństwa elementów w ramach każdego ze skupień, przy jednoczesnej maksymalnej różnicy pomiędzy samymi klasami (skupieniami). Podstawowy algorytm (J. MacQueen, 1967): wybór środków (centroidów) klas (skupień) – poprzedzony ustaleniem liczby klas (skupień) dobór centroidów dokonany jest m.in. poprzez losowy wybór k obserwacji, wybór k pierwszych obserwacji ze zbioru czy dobór pozwalający na maksymalizację odległości skupień, przypisanie punktów do najbliższych centroidów – każdy element przypisujemy do klasy (skupienia), do którego środka ma najbliżej (miarą podobieństwa jest tu odległość między elementem a centroidem – najczęściej wykorzystuje się odległość euklidesową, jej kwadrat lub też tzw.