Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

K-Means Clustering

Group points into k clusters by repeatedly assigning them to the nearest centroid and moving the centroids.

Bạn sẽ học được gì

  • Assign points to the nearest centroid
  • Move centroids to the cluster mean
  • Iterate an algorithm until it settles

Đề bài

Xem bản dịch

K-means finds groups in unlabeled data. Starting from the given centroids, repeat iterations times:

  1. Assign: put each point in the cluster of its nearest centroid (Euclidean distance). If two centroids are equally close, choose the one with the smaller index.
  2. Update: move each centroid to the average of the points assigned to it. A centroid with no points stays where it is.

Implement k_means(points, centroids, iterations).

Input

points: The data points, each a list of coordinates.

centroids: The k starting centroids, with the same number of coordinates.

iterations: How many assign-and-update rounds to run.

Output

Return the final centroids in their original order.

Ràng buộc

1 ≤ number of points ≤ 1,000, 1 ≤ k ≤ 20, 1 ≤ dimensions ≤ 10

0 ≤ iterations ≤ 100

-1,000 ≤ each coordinate ≤ 1,000

Ví dụ

Ví dụ 1
Đầu vào:
points = [
    [1.0, 1.0],
    [1.5, 2.0],
    [8.0, 8.0],
    [9.0, 8.5]
]
centroids = [
    [0.0, 0.0],
    [10.0, 10.0]
]
iterations = 1

Kết quả mong đợi:
expected = [
    [1.25, 1.5],
    [8.5, 8.25]
]
Đầu vào:
std::vector<std::vector<double>> points = {
    {1.0, 1.0},
    {1.5, 2.0},
    {8.0, 8.0},
    {9.0, 8.5}
};
std::vector<std::vector<double>> centroids = {
    {0.0, 0.0},
    {10.0, 10.0}
};
long long iterations = 1;

Kết quả mong đợi:
std::vector<std::vector<double>> expected = {
    {1.25, 1.5},
    {8.5, 8.25}
};
Đầu vào:
double[][] points = new double[][] {
    new double[] {1.0, 1.0},
    new double[] {1.5, 2.0},
    new double[] {8.0, 8.0},
    new double[] {9.0, 8.5}
};
double[][] centroids = new double[][] {
    new double[] {0.0, 0.0},
    new double[] {10.0, 10.0}
};
long iterations = 1;

Kết quả mong đợi:
double[][] expected = new double[][] {
    new double[] {1.25, 1.5},
    new double[] {8.5, 8.25}
};

Giải thích

The first two points are nearer to (0, 0) and the last two nearer to (10, 10). The new centroids are the averages: ((1 + 1.5) / 2, (1 + 2) / 2) = (1.25, 1.5) and ((8 + 9) / 2, (8 + 8.5) / 2) = (8.5, 8.25).

Ví dụ 2
Đầu vào:
points = [
    [0.0],
    [1.0],
    [10.0]
]
centroids = [
    [0.0],
    [100.0]
]
iterations = 2

Kết quả mong đợi:
expected = [
    [3.666667],
    [100.0]
]
Đầu vào:
std::vector<std::vector<double>> points = {
    {0.0},
    {1.0},
    {10.0}
};
std::vector<std::vector<double>> centroids = {
    {0.0},
    {100.0}
};
long long iterations = 2;

Kết quả mong đợi:
std::vector<std::vector<double>> expected = {
    {3.666667},
    {100.0}
};
Đầu vào:
double[][] points = new double[][] {
    new double[] {0.0},
    new double[] {1.0},
    new double[] {10.0}
};
double[][] centroids = new double[][] {
    new double[] {0.0},
    new double[] {100.0}
};
long iterations = 2;

Kết quả mong đợi:
double[][] expected = new double[][] {
    new double[] {3.666667},
    new double[] {100.0}
};

Giải thích

Round 1: (100) is far from every point, so all three points join centroid 1, which moves to (0 + 1 + 10) / 3 ≈ 3.666667; centroid 2 gets no points and stays at 100. Round 2 assigns the same way, so the result is [[3.666667], [100]].

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Alternate between assigning every point to its nearest centroid and recomputing each centroid from its assigned points.

Gợi ý 2

When distances tie, choose the centroid with the smaller index, and keep an empty centroid unchanged.

Gợi ý 3

Average each coordinate independently, and repeat the full assign-update cycle exactly the requested number of times.

Độ phức tạp mong đợi

O(iterations × n × k × d) time, O(n + k d) extra space

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.