k-means in two dimensions with inertia

Run k-means on points in the plane and measure how tight the clusters it finds are.

What to build

A program that runs two-dimensional k-means from given starting centroids and reports the result.

Requirements

  • Each round: assign every point to its nearest centroid (squared Euclidean distance; ties to the earlier centroid), then move each centroid to the mean of its points; an empty cluster keeps its centroid.
  • Stop after the first round that leaves every centroid unchanged (at most 100 rounds).
  • Print centroid i: (X, Y) for each centroid, inertia I and rounds R, with X, Y and I to 2 decimal places.

Input

Line 1: n and k. Then n lines x y. Then k lines with the starting centroids.

Output

k + 2 lines.

Constraints

1 ≤ n ≤ 500, 1 ≤ k ≤ 10.

Example

Input:

6 2
1 1
1 2
2 1
8 8
8 9
9 8
1 1
2 1

Output:

centroid 1: (1.33, 1.33)
centroid 2: (8.33, 8.33)
inertia 2.67
rounds 3

Why it works

The final assignment and the final centroids agree with each other, so no single step can lower the inertia further: that is where k-means stops.

Examples

Example 1 · Input
6 2
1 1
1 2
2 1
8 8
8 9
9 8
1 1
2 1
Expected output
centroid 1: (1.33, 1.33)
centroid 2: (8.33, 8.33)
inertia 2.67
rounds 3
Example 2 · Input
2 1
0 0
2 2
5 5
Expected output
centroid 1: (1.00, 1.00)
inertia 4.00
rounds 2

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Use squared Euclidean distances; on a tie, the earlier centroid wins.

Hint 2

A round is one assignment and one update; stop after the first round in which no centroid changed.

Hint 3

The inertia is the sum, over points, of the squared distance to the centroid of their final cluster.

Solution

Show one correct solution (try it yourself first)
n, k = map(int, input().split())
points = [tuple(map(float, input().split())) for _ in range(n)]
centroids = [tuple(map(float, input().split())) for _ in range(k)]


def d2(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2


rounds = 0
for rounds in range(1, 101):
    labels = [min(range(k), key=lambda j: (d2(p, centroids[j]), j)) for p in points]
    new = []
    for j in range(k):
        mine = [p for p, label in zip(points, labels) if label == j]
        new.append((sum(p[0] for p in mine) / len(mine), sum(p[1] for p in mine) / len(mine)) if mine else centroids[j])
    changed = new != centroids
    centroids = new
    if not changed:
        break
labels = [min(range(k), key=lambda j: (d2(p, centroids[j]), j)) for p in points]
for i, (x, y) in enumerate(centroids):
    print(f"centroid {i + 1}: ({x:.2f}, {y:.2f})")
print(f"inertia {sum(d2(p, centroids[label]) for p, label in zip(points, labels)):.2f}")
print(f"rounds {rounds}")

Lesson: Clustering with k-means →