Cho các điểm A(1, 1), B(2, 1), C(4, 3), D(5, 4). Sử dụng thuật toán phân cụm k-mean để chia 4 điểm vào 2 cụm. Kết quả phân cụm là:

Thuật toán k-means là một thuật toán phân cụm nhằm chia dữ liệu thành k cụm khác nhau, trong đó mỗi điểm dữ liệu thuộc về cụm có khoảng cách gần nhất đến trung tâm của cụm đó. Để giải bài toán này, ta cần thực hiện các bước lặp sau: 1. **Khởi tạo:** Chọn ngẫu nhiên 2 điểm làm tâm cụm ban đầu. Ví dụ, chọn A(1,1) và D(5,4) làm tâm cụm C1 và C2. 2. **Gán điểm vào cụm:** Tính khoảng cách Euclidean từ mỗi điểm đến tâm của hai cụm, sau đó gán điểm đó vào cụm có khoảng cách gần nhất. * Khoảng cách từ B(2,1) đến A(1,1) = sqrt((2-1)^2 + (1-1)^2) = 1 * Khoảng cách từ B(2,1) đến D(5,4) = sqrt((2-5)^2 + (1-4)^2) = sqrt(9 + 9) = sqrt(18) ≈ 4.24 => B thuộc C1 * Khoảng cách từ C(4,3) đến A(1,1) = sqrt((4-1)^2 + (3-1)^2) = sqrt(9 + 4) = sqrt(13) ≈ 3.61 * Khoảng cách từ C(4,3) đến D(5,4) = sqrt((4-5)^2 + (3-4)^2) = sqrt(1 + 1) = sqrt(2) ≈ 1.41 => C thuộc C2 Vậy C1 = {A, B}, C2 = {C, D}. 3. **Tính lại tâm cụm:** Tính lại tâm của mỗi cụm bằng cách lấy trung bình cộng tọa độ của các điểm trong cụm. * Tâm C1 = ((1+2)/2, (1+1)/2) = (1.5, 1) * Tâm C2 = ((4+5)/2, (3+4)/2) = (4.5, 3.5) 4. **Lặp lại bước 2 và 3:** Lặp lại quá trình gán điểm và tính lại tâm cụm cho đến khi không có sự thay đổi về thành viên của các cụm hoặc đạt đến số lần lặp tối đa. * Khoảng cách từ A(1,1) đến (1.5, 1) = 0.5 * Khoảng cách từ A(1,1) đến (4.5, 3.5) = sqrt((1-4.5)^2 + (1-3.5)^2) = sqrt(12.25 + 6.25) = sqrt(18.5) ≈ 4.3 => A thuộc C1 * Khoảng cách từ B(2,1) đến (1.5, 1) = 0.5 * Khoảng cách từ B(2,1) đến (4.5, 3.5) = sqrt((2-4.5)^2 + (1-3.5)^2) = sqrt(6.25 + 6.25) = sqrt(12.5) ≈ 3.54 => B thuộc C1 * Khoảng cách từ C(4,3) đến (1.5, 1) = sqrt((4-1.5)^2 + (3-1)^2) = sqrt(6.25 + 4) = sqrt(10.25) ≈ 3.2 * Khoảng cách từ C(4,3) đến (4.5, 3.5) = sqrt((4-4.5)^2 + (3-3.5)^2) = sqrt(0.25 + 0.25) = sqrt(0.5) ≈ 0.71 => C thuộc C2 * Khoảng cách từ D(5,4) đến (1.5, 1) = sqrt((5-1.5)^2 + (4-1)^2) = sqrt(12.25 + 9) = sqrt(21.25) ≈ 4.6 * Khoảng cách từ D(5,4) đến (4.5, 3.5) = sqrt((5-4.5)^2 + (4-3.5)^2) = sqrt(0.25 + 0.25) = sqrt(0.5) ≈ 0.71 => D thuộc C2 Vậy C1 = {A, B}, C2 = {C, D}. Do đó, đáp án đúng là A: C1 = {A, B}; C2 = {C, D}. Lưu ý: Thuật toán k-means có thể cho ra các kết quả khác nhau tùy thuộc vào việc chọn tâm cụm ban đầu. Do đó, cần thực hiện nhiều lần với các tâm cụm ban đầu khác nhau để tìm ra kết quả tốt nhất.