Variations of k-means often include such optimizations as choosing the best of multiple runs, but also restricting the centroids to members of the data set (k-medoids), choosing medians (k-medians clustering), choosing the initial centers less randomly (k-means++) or allowing a fuzzy cluster assignment (fuzzy c-means).
Variácie k-means často zahŕňajú tak optimalizáciu ako aj výber najlepšej možnosti viacnásobného spustenia, ale tiež obmedzuje ťažiská členom súboru dát (k-medoids), výber mediánov (k-medians), výber počiatočných ťažísk menej náhodne (k-means ++) alebo umožňujú fuzzy priradenie zhlukov (Fuzzy k-means).