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
1 2 3 10 11 12 1 3
round 1: 1.50 9.00 round 2: 2.00 11.00 round 3: 2.00 11.00 converged in round 3
0 10 0 10
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