K-means clustering is an unsupervised learning method that sorts data points into groups based on similarity. It is useful when you have data but no labels, such as customer behavior, image colors, or sensor readings. The goal is to find k clusters so that points inside each cluster are close to one another.
A scatterplot with colored groups and marked centroids gives a clear picture of how the algorithm organizes data.
Key Facts
- K-means partitions n data points into k clusters, where k is chosen before the algorithm starts.
- Assignment step: assign each point to the nearest centroid, usually using Euclidean distance.
- Euclidean distance in 2D: d = sqrt((x2 - x1)^2 + (y2 - y1)^2).
- Update step: move each centroid to the mean of the points assigned to its cluster.
- Objective function: minimize WCSS = sum over clusters sum over points ||x - centroid||^2.
- Elbow method: plot WCSS versus k and choose a k where adding more clusters gives much smaller improvement.
Vocabulary
- Cluster
- A cluster is a group of data points that are more similar to each other than to points in other groups.
- Centroid
- A centroid is the average position of all points currently assigned to a cluster.
- Unsupervised learning
- Unsupervised learning finds patterns in data without using known category labels.
- WCSS
- WCSS, or within-cluster sum of squares, measures the total squared distance from points to their assigned centroids.
- Elbow method
- The elbow method is a graphical way to choose k by looking for the bend in a plot of WCSS against the number of clusters.
Common Mistakes to Avoid
- Choosing k without checking the data, which can force clusters that do not represent real structure. Use an elbow plot, domain knowledge, or validation measures to support the choice.
- Forgetting to scale features, which makes variables with large units dominate the distance calculation. Standardize features when variables are measured on different scales.
- Assuming k-means finds the true global best solution every time, which is wrong because different starting centroids can give different results. Run the algorithm multiple times with different initializations.
- Using k-means on clusters with curved shapes or very different densities, which can produce misleading groups. K-means works best for compact, roughly round clusters of similar size.
Practice Questions
- 1 A point P = (4, 5) is compared with centroids A = (1, 1) and B = (6, 5). Using Euclidean distance, which centroid is closer to P?
- 2 A cluster contains the points (2, 4), (4, 6), and (8, 2). Find the updated centroid after the k-means update step.
- 3 A data set has two long crescent-shaped groups that wrap around each other. Explain why k-means may perform poorly on this data, even if k is chosen correctly.