← 返回 microsoft 的题目列表Implement K-Means Clustering From Scratch
类型：online_judge
Problem: Implement K-Means Clustering From Scratch
Given a 2D dataset, implement the K-Means clustering algorithm from scratch (do not call existing clustering implementations such as sklearn.cluster.KMeans). You may use Python / NumPy / PyTorch (any one or a combination).
Requirements
Input:
Integer k: number of clusters
Integer max_iters: maximum number of iterations
Float tol: convergence threshold (stop when centroid movement is below this value)
n 2D points [(x1,y1), (x2,y2), ...]
Output:
k centroids (sort centroids lexicographically before printing, keep 4 decimals)
A label for each point (0 ~ k-1, corresponding to the sorted centroid index)
Initialization:
Random init: randomly pick k data points as initial centroids (use the given seed for reproducibility).
Iteration:
Assignment step: assign each point to the nearest centroid (Euclidean distance)
Update step: recompute each centroid as the mean of points assigned to it
If an empty cluster occurs: reinitialize its centroid to the data point that is farthest from its nearest existing centroid (deterministic).
Input Format (stdin)
Line 1: n k max_iters tol seed
Next n lines: two floats x y per line
Output Format (stdout)
First k lines: cx cy for each centroid (4 decimals)
Last line: n integer labels separated by spaces
Constraints
1 <= n <= 2e5
1 <= k <= 100
1 <= max_iters <= 300
Coordinate range: [-1e4, 1e4]
Expected per-iteration time: O(nk) (vectorization allowed but not required)
Example
Input
6 2 100 1e-6 0
0 0
0 1
1 0
10 10
10 11
11 10
Output
0.3333 0.3333
10.3333 10.3333
0 0 0 1 1 1