K-Means er den mest udbredte clustering-algoritme inden for unsupervised machine learning. Algoritmen opdeler et datasæt i K foruddefinerede klynger (clusters), hvor hvert datapunkt tilhører den klynge hvis centrum (centroid) det er nærmest.
Algoritmen fungerer iterativt i følgende trin: 1) Vælg K tilfældige centroids, 2) Tildel hvert datapunkt til nærmeste centroid, 3) Genberegn centroids som gennemsnittet af alle punkter i klyngen, 4) Gentag trin 2-3 indtil centroids ikke længere flytter sig væsentligt (konvergens).
Valget af K er afgørende for algoritmens resultat. Den populære "Elbow Method" kører K-Means med forskellige K-værdier og plotter den samlede intra-cluster varians (WCSS). Det optimale K ligger typisk ved "albuen" - det punkt hvor yderligere klynger ikke giver væsentlig reduktion i varians. Silhouette-analysen er en anden metode der måler hvor godt hvert datapunkt passer i sin klynge versus nabolynger.
K-Means bruger typisk euklidisk afstand som lighedsmål, hvilket fungerer bedst med sfæriske klynger af nogenlunde ens størrelse. Algoritmen er følsom over for outliers og initialiseringen af centroids. K-Means++ er en forbedret initialiseringsmetode der spreder de initiale centroids mere jævnt, hvilket giver mere konsistente resultater.
Mini-Batch K-Means er en variant der behandler data i små batches i stedet for hele datasættet på én gang, hvilket gør algoritmen skalerbar til meget store datasæt med kun marginalt tab i klyngekvalitet.
I praksis bruges K-Means til kundesegmentering, billedkomprimering (farvereduktion), anomalidetektion, dokumentklyngedannelse og som forbehandlingstrin for andre ML-algoritmer. Algoritmens styrke er dens simplicitet, hastighed og skalerbarhed.