k-means-klyngeanalyse

k-means minimerer summen af kvadrerede afstande inden for klyngerne (inerti), dvs. summen over alle punkter af den kvadrerede euklidiske afstand til deres tildelte centroide. Standardproceduren, Lloyds algoritme, skifter mellem et tildelingstrin (hvert punkt til den nærmeste centroide) og et opdateringstrin (hver centroide til gennemsnittet af sine punkter). Intet trin kan øge inertien, så algoritmen konvergerer, men kun til et lokalt minimum; at finde det globale optimum er NP-hårdt. Stuart Lloyd beskrev metoden i en rapport fra Bell Labs i 1957, som blev publiceret i 1982 (IEEE Transactions on Information Theory); navnet k-means stammer fra MacQueen (1967).

Resultatet afhænger meget af startpunkterne. k-means++ (Arthur og Vassilvitskii, 2007) vælger hvert nyt startmidtpunkt med en sandsynlighed proportional med den kvadrerede afstand til de allerede valgte, hvilket spreder dem og giver en forventet O(log k)-approksimationsgaranti; det er standard i scikit-learn, og algoritmen køres som regel flere gange, hvor kørslen med lavest inerti beholdes. Mini-batch k-means opdaterer centroiderne ud fra små tilfældige batches for at kunne håndtere meget store datasæt.

Antallet af klynger k skal vælges på forhånd, typisk med albuemetoden på inertikurven, silhouetscoren eller gap-statistikken, og helst tjekkes mod den faglige betydning. Fordi metoden bruger kvadreret euklidisk afstand, antager k-means underforstået konvekse, nogenlunde kugleformede klynger af samme størrelse og er følsom over for skalaen af features og over for outliers, så features standardiseres normalt først. I mange dimensioner bliver afstande mindre informative, og det hjælper ofte først at reducere antallet af dimensioner, fx med PCA.

Til klynger med vilkårlig form egner tæthedsbaserede metoder som DBSCAN eller HDBSCAN sig bedre; gaussiske blandingsmodeller er en blød, probabilistisk generalisering af k-means; og k-medoids begrænser midtpunkterne til faktiske datapunkter for at være mere robust. k-means bruges også til vektorkvantisering, fx til at bygge kodebøgerne i product quantization til nærmeste-nabo-søgning.