Đề bài
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:
- 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.
- 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ụ
Đầ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).
Đầ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]].
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.