k-means on a line

Run the whole k-means loop on points along a line, from given starting centroids, until it settles.

What to build

A program that runs k-means in one dimension and prints the centroids after each round.

Requirements

  • Each round assigns every point to its nearest centroid (a tie goes to the earlier centroid) and then moves each centroid to the mean of its points; an empty cluster keeps its centroid.
  • After each round print round r: C1 C2 ... with 2 decimal places.
  • Stop after the first round in which the centroids did not change, and print converged in round r.

Input

Line 1: the points. Line 2: the starting centroids.

Output

One line per round, then the last line.

Constraints

1 to 500 points; 1 to 10 centroids; it converges within 100 rounds.

Example

Input:

1 2 3 10 11 12
1 3

Output:

round 1: 1.50 9.00
round 2: 2.00 11.00
round 3: 2.00 11.00
converged in round 3

Why it works

Assigning to the nearest centroid and moving centroids to their clusters' means both lower the inertia, so the centroids stop changing after a finite number of rounds.

Examples

Example 1 · Input
1 2 3 10 11 12
1 3
Expected output
round 1: 1.50 9.00
round 2: 2.00 11.00
round 3: 2.00 11.00
converged in round 3
Example 2 · Input
0 10
0 10
Expected output
round 1: 0.00 10.00
converged in round 1

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

Hints

Hint 1

Each round: assign every point to the nearest centroid (ties to the lower one), then set each centroid to the mean of its points.

Hint 2

A centroid with no points stays where it is.

Hint 3

Stop after the first round in which no centroid changed.

Solution

Show one correct solution (try it yourself first)
points = list(map(float, input().split()))
centroids = list(map(float, input().split()))
for r in range(1, 101):
    labels = [min(range(len(centroids)), key=lambda k: (abs(p - centroids[k]), k)) for p in points]
    new = []
    for k, c in enumerate(centroids):
        mine = [p for p, label in zip(points, labels) if label == k]
        new.append(sum(mine) / len(mine) if mine else c)
    print(f"round {r}:", *[f"{c:.2f}" for c in new])
    if new == centroids:
        print(f"converged in round {r}")
        break
    centroids = new

Lesson: Clustering with k-means →