Có N phần tử cần chia thành 2 cụm, mỗi cụm có ít nhất 1 phần tử. Công thức nào sau đây cho ta tổng số cách chia cụm: 

Câu hỏi yêu cầu tìm công thức tính số cách chia N phần tử thành 2 cụm, mỗi cụm có ít nhất 1 phần tử.

Phân tích các phương án:

* Phương án a: S(N,2) = 2^N - 1
* Tổng số tập con của một tập N phần tử là 2^N. Tuy nhiên, trong đó bao gồm cả tập rỗng và chính tập N phần tử. Để chia thành 2 cụm, ta cần loại trừ trường hợp tập rỗng. Vì mỗi cách chia như vậy sẽ có một cách chia đối xứng (đảo ngược vai trò 2 cụm), do đó ta cần chia đôi kết quả. Tuy nhiên, công thức này vẫn không chính xác vì nó không loại trừ việc một trong hai cụm rỗng.

* Phương án b: S(N,2) = 2^(N-1)
* Xét một tập hợp N phần tử. Để chia thành hai cụm, ta có thể duyệt qua từng phần tử. Với mỗi phần tử, ta có 2 lựa chọn: hoặc là cho vào cụm thứ nhất, hoặc là cho vào cụm thứ hai. Như vậy, tổng số cách chia là 2^N. Tuy nhiên, cách chia này tính cả trường hợp tất cả các phần tử đều thuộc cụm thứ nhất hoặc tất cả các phần tử đều thuộc cụm thứ hai (tức là một cụm rỗng). Vì mỗi cụm phải có ít nhất 1 phần tử, ta cần trừ đi 2 trường hợp này. Số cách chia sẽ là (2^N - 2) / 2 = 2^(N-1) - 1. Do đó, phương án này chưa chính xác.

* Phương án c: S(N,2) = 2^(N-1) - 1
* Cách giải thích tương tự như phương án b, nhưng đã trừ đi các trường hợp cụm rỗng và chia đôi để tránh trùng lặp. Đây là đáp án chính xác.

* Phương án d: S(N,2) = 2^N
* Phương án này tính tất cả các tập con, bao gồm cả trường hợp tập rỗng và không chia đôi để loại bỏ các cách chia trùng lặp.

Vậy, đáp án đúng là: S(N,2) = 2^(N-1) - 1

Thuật toán liên kết đơn (Single-linkage clustering) là một phương pháp phân cụm phân cấp. Trong thuật toán này, khoảng cách giữa hai cụm được định nghĩa là khoảng cách ngắn nhất giữa hai điểm dữ liệu bất kỳ thuộc hai cụm đó. Do đó, ở mỗi bước, thuật toán sẽ chọn hai cụm gần nhau nhất để hợp nhất. Công thức khoảng cách giữa cụm mới Cp và cụm còn lại Cq sẽ là d(Cp, Cq) = min{d(Ci, Cq), d(Cj, Cq)} trong đó Ci và Cj là hai cụm đã được hợp nhất để tạo thành Cp.

Như vậy, đáp án d là đáp án chính xác.

Trong ma trận không tương tự (dissimilarity matrix), giá trị tại vị trí (i, j) thể hiện khoảng cách giữa phần tử xi và xj. Trong trường hợp này, chúng ta cần tìm khoảng cách giữa x1 và x2. Nhìn vào ma trận, giao điểm của hàng x1 và cột x2 (hoặc ngược lại) cho ta giá trị 1.

Khoảng cách giữa hai phần tử x1 và x5 được cho trực tiếp trong ma trận không tương tự. Dựa vào ma trận, ta thấy giá trị tại vị trí giao giữa hàng x1 và cột x5 (hoặc ngược lại) là 9.