- 2065 Baisakh
K-means on six 2-D instances (B65)
Short answer
Using Euclidean distance and initial centroids (1,2.5) and (1,4.5), K-means converges in two iterations. Clusters: {1,3,4,5} centroid (2.5,2.125); {2,6} centroid (2.5,4.75).
Cluster the following instances of given data (2-Dimensional form) with the help of K-means algorithm (Take K = 2).
| Instances | X | Y |
|---|---|---|
| 1 | 1.0 | 2.5 |
| 2 | 1.0 | 4.5 |
| 3 | 2.5 | 3.0 |
| 4 | 2.0 | 1.5 |
| 5 | 4.5 | 1.5 |
| 6 | 4.0 | 5.0 |
Assumption: K = 2 and the initial centroids are instances 1 and 2: C1 = (1.0, 2.5), C2 = (1.0, 4.5). Distance d = √[(x − cx)² + (y − cy)²].
1. Choose k and select k initial centroids (random objects).
2. Repeat
a. Assign each object to the nearest centroid
(Euclidean distance) -> k clusters.
b. Recompute each centroid as the mean of its cluster.
3. Until no object changes cluster (centroids stable).
Iteration 1
| Instance | (X, Y) | d to C1 (1.0, 2.5) | d to C2 (1.0, 4.5) | Cluster |
|---|---|---|---|---|
| 1 | (1.0, 2.5) | 0.00 | 2.00 | C1 |
| 2 | (1.0, 4.5) | 2.00 | 0.00 | C2 |
| 3 | (2.5, 3.0) | 1.58 | 2.12 | C1 |
| 4 | (2.0, 1.5) | 1.41 | 3.16 | C1 |
| 5 | (4.5, 1.5) | 3.64 | 4.61 | C1 |
| 6 | (4.0, 5.0) | 3.91 | 3.04 | C2 |
Clusters: C1 = {1, 3, 4, 5}, C2 = {2, 6}. New centroids:
- C1 = ((1.0 + 2.5 + 2.0 + 4.5)/4, (2.5 + 3.0 + 1.5 + 1.5)/4) = (2.5, 2.125)
- C2 = ((1.0 + 4.0)/2, (4.5 + 5.0)/2) = (2.5, 4.75)
Iteration 2
| Instance | d to C1 (2.5, 2.125) | d to C2 (2.5, 4.75) | Cluster |
|---|---|---|---|
| 1 | 1.55 | 2.70 | C1 |
| 2 | 2.81 | 1.52 | C2 |
| 3 | 0.88 | 1.75 | C1 |
| 4 | 0.80 | 3.29 | C1 |
| 5 | 2.10 | 3.82 | C1 |
| 6 | 3.24 | 1.52 | C2 |
No instance changes its cluster, so the algorithm stops.
Answer: Cluster 1 = {instances 1, 3, 4, 5}, centroid (2.5, 2.125); Cluster 2 = {instances 2, 6}, centroid (2.5, 4.75).
Note: K-means depends on the initial centroids. With instances 1 and 6 as the starting centroids the result is C1 = {1, 2, 3, 4} (centroid (1.63, 2.88)) and C2 = {5, 6} (centroid (4.25, 3.25)).
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- K-means on six 2-D instances (K=2) · Data Mining, chapter 5
- Cluster analysis; K-means on height/width · Data Mining, chapter 5
- Cluster analysis applications; K-means · Data Mining, chapter 5
- K-means on 1-D data, K=2 and K=3 · Data Mining, chapter 5
- Need of clustering; hierarchical vs partitioning; K-means · Data Mining, chapter 5
- K-means on eight points into 3 clusters · Data Mining, chapter 5
- Algorithm and flowchart help; Armstrong flowchart · Computer Programming, chapter 2