Độ đo gần gũi gồm có:

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.

Câu hỏi yêu cầu xác định khoảng cách giữa x3 và x4 sau khi thực hiện một bước trong thuật toán liên kết đơn (Single Linkage). Thuật toán liên kết đơn sử dụng khoảng cách nhỏ nhất giữa hai điểm dữ liệu thuộc hai cụm khác nhau để xác định khoảng cách giữa hai cụm đó. Tuy nhiên, ở đây ta mới chỉ gom x1 và x2 thành một cụm, và câu hỏi hỏi khoảng cách giữa x3 và x4. Do đó, việc gom cụm này không ảnh hưởng đến khoảng cách ban đầu giữa x3 và x4. Nhìn vào ma trận không tương tự đã cho, ta thấy khoảng cách giữa x3 và x4 là 0.

Thuật toán Complete Linkage (Liên kết đầy đủ) định nghĩa khoảng cách giữa hai cụm là khoảng cách lớn nhất giữa hai điểm bất kỳ thuộc hai cụm đó.

Như vậy, khoảng cách giữa cụm C = {x1, x2} và x3 sẽ là max(d(x1, x3), d(x2, x3)).

Để trả lời câu hỏi này, ta cần có ma trận không tương tự (dissimilarity matrix) để biết giá trị d(x1, x3) và d(x2, x3). Vì ma trận này không được cung cấp trong đề bài, ta không thể tính toán chính xác khoảng cách giữa cụm C và x3. Do đó, không thể xác định đáp án đúng trong các lựa chọn A, B, C, D chỉ dựa trên thông tin đã cho.

Vì không có ma trận khoảng cách, nên không có đáp án đúng trong các đáp án đã cho.