K means clustering
Het K-Means-algoritme
K-Means is een van de eenvoudigste en meest gebruikte clusteralgoritmen. Het doel is om n datapunten te verdelen in k clusters, waarbij elk datapunt tot het cluster met het dichtstbijzijnde middelpunt (centroïde) behoort. Het algoritme werkt iteratief. Eerst worden k initiële centroïden gekozen, vaak willekeurig of met behulp van k-means++. Daarna worden alle datapunten toegewezen aan het dichtstbijzijnde centroïde. Vervolgens worden de centroïden herberekend als het gemiddelde van de toegewezen punten. Deze stappen worden herhaald tot de centroïden niet meer veranderen of een maximaal aantal iteraties is bereikt. K-Means convergeert altijd, maar naar een lokaal optimum. De uitkomst hangt af van de initiële centroïden; daarom wordt het algoritme vaak meerdere keren uitgevoerd met verschillende initialisaties. Het aantal clusters k moet vooraf worden gekozen. Methoden zoals de elbow-methode of silhouette-analyse helpen bij het bepalen van een geschikte k. K-Means is snel en schaalbaar, maar werkt het beste bij bolvormige, goed gescheiden clusters. Het is gevoelig voor uitbijters en kan alleen numerieke data verwerken. Voor categorische data bestaan varianten zoals K-Modes.
Praktische overwegingen en varianten
Bij het toepassen van K-Means zijn er verschillende praktische overwegingen. Allereerst moeten de features worden geschaald, omdat het algoritme gebaseerd is op afstanden. Zonder normalisatie kunnen features met grote bereiken de clustering domineren. Ten tweede is de keuze van k cruciaal. De elbow-methode plot de within-cluster sum of squares (WCSS) tegen k en zoekt naar een 'elleboog' waar de afname afvlakt. De silhouette-score meet hoe goed elk punt bij zijn cluster past en hoe ver het van andere clusters verwijderd is. Een score dicht bij 1 betekent een goede clustering. K-Means heeft moeite met clusters van verschillende dichtheden en niet-bolvormige clusters. In zulke gevallen zijn DBSCAN of spectral clustering betere keuzes. Er bestaan ook varianten zoals K-Medoids (PAM), waarbij het clustercentrum een daadwerkelijk datapunt is, wat robuuster is tegen uitbijters. Mini-Batch K-Means is een variant die grote datasets efficiënt kan verwerken door mini-batches te gebruiken. K-Means wordt veel toegepast in beeldcompressie, documentclustering, klantsegmentatie en het initiëren van andere algoritmen. Het blijft een werkpaard van unsupervised learning.