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

Phân cụm K-means

Chia các điểm thành k cụm bằng cách lặp lại việc gán điểm vào tâm cụm gần nhất và dời tâm cụm.

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

  • Gán điểm vào tâm cụm gần nhất
  • Dời tâm cụm về trung bình của cụm
  • Lặp thuật toán đến khi ổn định

Đề bài

Xem bản gốc (English)

K-means tìm các nhóm trong dữ liệu không có nhãn. Bắt đầu từ các tâm cụm đã cho, lặp lại iterations lần:

  1. Gán: đưa mỗi điểm vào cụm có tâm gần nó nhất (khoảng cách Euclid). Nếu hai tâm cụm gần bằng nhau, chọn tâm có chỉ số nhỏ hơn.
  2. Cập nhật: dời mỗi tâm cụm đến trung bình của các điểm thuộc cụm đó. Tâm cụm không có điểm nào thì giữ nguyên.

Hãy cài đặt k_means(points, centroids, iterations).

Đầu vào

points: Các điểm dữ liệu, mỗi điểm là một danh sách tọa độ.

centroids: k tâm cụm ban đầu, có cùng số tọa độ.

iterations: Số vòng gán và cập nhật cần chạy.

Đầu ra

Trả về các tâm cụm cuối cùng theo thứ tự ban đầu.

Ràng buộc

1 ≤ số điểm ≤ 1.000, 1 ≤ k ≤ 20, 1 ≤ số chiều ≤ 10

0 ≤ iterations ≤ 100

-1.000 ≤ mỗi tọa độ ≤ 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

Hai điểm đầu gần (0, 0) hơn và hai điểm cuối gần (10, 10) hơn. Các tâm cụm mới là trung bình: ((1 + 1.5) / 2, (1 + 2) / 2) = (1.25, 1.5) và ((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

Vòng 1: (100) ở xa mọi điểm, nên cả ba điểm vào cụm 1, tâm cụm này dời đến (0 + 1 + 10) / 3 ≈ 3.666667; cụm 2 không có điểm nào nên vẫn ở 100. Vòng 2 gán giống hệt, nên kết quả là [[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

Luân phiên giữa việc gán mọi điểm vào centroid gần nhất và tính lại từng centroid từ các điểm đã gán.

Gợi ý 2

Khi khoảng cách bằng nhau, chọn centroid có chỉ số nhỏ hơn, và giữ nguyên centroid rỗng.

Gợi ý 3

Lấy trung bình từng tọa độ riêng biệt, rồi lặp lại đầy đủ vòng assign-update đúng số lần yêu cầu.

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

thời gian O(iterations × n × k × d), bộ nhớ phụ O(n + k d)

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.