Độ đo ‘gần gũi’ là gì ? 

Để giải bài toán này bằng thuật toán k-means, chúng ta cần thực hiện các bước lặp: khởi tạo các tâm cụm ban đầu, gán các điểm vào cụm gần nhất, và cập nhật tâm cụm. Tuy nhiên, vì đây là một bài trắc nghiệm, chúng ta có thể đánh giá nhanh các phương án dựa trên trực giác về khoảng cách giữa các điểm.

Phương án a: C1={A, B}; C2={C, D}
- A(1, 1), B(2, 1): Hai điểm này khá gần nhau.
- C(4, 3), D(5, 4): Hai điểm này cũng khá gần nhau.
Phương án này có vẻ hợp lý.

Phương án b: C1={A, C}; C2={B, D}
- A(1, 1), C(4, 3): Hai điểm này có vẻ xa nhau hơn.
- B(2, 1), D(5, 4): Hai điểm này cũng có vẻ xa nhau hơn.
Phương án này ít hợp lý hơn.

Phương án c: C1={A, B, C}; C2={D}
- A(1, 1), B(2, 1), C(4, 3): Ba điểm này có độ phân tán lớn hơn so với cụm {A, B}.
- D(5, 4): Một cụm chỉ có một điểm, có thể không phải là kết quả tốt nhất của k-means.
Phương án này ít hợp lý.

Phương án d: C1={A, B, D}; C2={C}
- A(1, 1), B(2, 1), D(5, 4): Ba điểm này có độ phân tán lớn.
- C(4, 3): Một cụm chỉ có một điểm, tương tự như phương án c.
Phương án này ít hợp lý.

Do đó, phương án a có vẻ là phương án hợp lý nhất, vì nó nhóm các điểm gần nhau vào cùng một cụm. Thuật toán k-means sẽ cố gắng giảm thiểu tổng khoảng cách từ mỗi điểm đến tâm cụm của nó, và phương án a dường như đạt được điều này tốt hơn các phương án khác.

Vậy đáp án đúng là a.

Để tìm tâm của cụm C, ta cần tính vector trung bình của các điểm A(1, 1), B(2, 4), C(6, 1).

Tâm của cụm mC được tính như sau:

mC = ((xA + xB + xC) / 3 ; (yA + yB + yC) / 3)

mC = ((1 + 2 + 6) / 3 ; (1 + 4 + 1) / 3)

mC = (9/3 ; 6/3)

mC = (3 ; 2)

Vậy, tâm của cụm là (3 ; 2).

Thuật toán K-means là một thuật toán clustering (phân cụm) phổ biến. Các nhược điểm thường gặp của thuật toán này bao gồm:

- Khó đảm bảo đạt được tối ưu toàn cục: Thuật toán có thể bị mắc kẹt ở các cực tiểu cục bộ.
- Khó phát hiện các cụm có hình dạng phức tạp (không lồi): K-means hoạt động tốt nhất với các cụm có hình dạng tròn hoặc gần tròn.
- Cần xác định trước số cụm k: Việc lựa chọn số lượng cụm phù hợp có thể là một thách thức.

Tuy nhiên, K-means lại là một thuật toán tương đối đơn giản để cài đặt và sử dụng. Do đó, phương án a (Thuật toán khó cài đặt) không phải là nhược điểm của thuật toán K-means.

Thuật toán k-means là một thuật toán phân cụm lặp đi lặp lại nhằm chia dữ liệu thành k cụm, trong đó mỗi điểm dữ liệu thuộc về cụm có khoảng cách gần nhất đến tâm của cụm đó. Quá trình lặp này bao gồm hai bước chính: gán các điểm dữ liệu vào cụm gần nhất và cập nhật tâm cụm. Thuật toán dừng lại khi việc gán các điểm dữ liệu vào các cụm không còn thay đổi nữa, tức là không thể gán (hoặc gán lại) một điểm nào vào một cụm khác mà làm giảm tổng khoảng cách từ các điểm đến tâm cụm tương ứng của chúng. Các đáp án còn lại không phải là điều kiện dừng của thuật toán k-means:
- Số cụm sinh ra là k: Đây là một tham số đầu vào của thuật toán, không phải điều kiện dừng.
- Tùy theo yêu cầu của người dùng: Mặc dù người dùng có thể đặt số lần lặp tối đa, nhưng điều kiện dừng chính vẫn là sự hội tụ của các cụm.
- Khi tất cả các phần tử đã được gán vào k cụm: Điều này luôn đúng trong quá trình thuật toán chạy, không phải là điều kiện để thuật toán dừng lại.

Quá trình phân cụm phân cấp (hierarchical clustering) tạo ra một cấu trúc cây phân cấp, trong đó mỗi nút lá đại diện cho một điểm dữ liệu và các nút cha đại diện cho các cụm được hình thành bằng cách hợp nhất các cụm con. Cây này biểu diễn quá trình gom cụm theo từng bước, từ các điểm dữ liệu riêng lẻ đến một cụm duy nhất chứa tất cả các điểm. Do đó, kết quả của quá trình phân cụm phân cấp là một cây nhị phân (hoặc cây phân cấp) biểu diễn quá trình gom cụm. Các lựa chọn khác không mô tả đầy đủ hoặc chính xác kết quả của thuật toán phân cụm phân cấp:

- a. Một sơ đồ ngưỡng tương tự (hoặc không tương tự): Sơ đồ này có thể được sử dụng để xác định khi nào nên dừng quá trình gom cụm, nhưng nó không phải là kết quả chính của thuật toán.
- b. Một danh sách các cụm: Quá trình phân cụm phân cấp có thể tạo ra một danh sách các cụm tại một ngưỡng cụ thể, nhưng kết quả cốt lõi là cây phân cấp.
- d. k cụm được sinh ra, với k cho trước: Đây là kết quả của các thuật toán phân cụm khác, chẳng hạn như k-means, chứ không phải phân cụm phân cấp.