Cho L là tập mục thường xuyên, S là tập con của L thì với mọi tập con S’ của S ta có: 

Thuật toán Apriori là một thuật toán kinh điển trong khai phá luật kết hợp. Ý tưởng chính của thuật toán này là: Bắt đầu bằng cách tạo ra các tập phổ biến (frequent itemsets) có 1 item, sau đó mở rộng lên 2 items, 3 items,... cho đến khi không còn tập phổ biến nào có thể tạo ra nữa. Điểm mấu chốt là tập k item chỉ được tạo ra từ tập k-1 items. Để làm điều này, thuật toán tạo ra danh sách các item dự kiến của tập k-items bằng cách hợp từng đôi một tập k-1 items có trong danh sách, sau đó loại bỏ các tập item không thỏa mãn độ hỗ trợ (support) tối thiểu. Độ tin cậy (confidence) thường được sử dụng sau bước này để đánh giá độ mạnh của luật kết hợp, nhưng không phải là yếu tố để tạo ra các tập phổ biến.

Câu hỏi này kiểm tra kiến thức về số các phân hoạch tập hợp (Stirling number of the second kind). Trong trường hợp này, ta cần chia N phần tử thành 2 cụm, mỗi cụm có ít nhất 1 phần tử.

Để giải bài toán này, ta có thể nghĩ đến việc mỗi phần tử có 2 lựa chọn: thuộc cụm 1 hoặc cụm 2. Như vậy, sẽ có 2^N cách gán. Tuy nhiên, ta cần loại bỏ 2 trường hợp: tất cả các phần tử đều thuộc cụm 1 (cụm 2 rỗng) và tất cả các phần tử đều thuộc cụm 2 (cụm 1 rỗng).

Vậy, số cách chia thành 2 cụm là 2^N - 2. Tuy nhiên, vì thứ tự của 2 cụm không quan trọng (chia {A, B} và {C, D} cũng giống như chia {C, D} và {A, B}), ta phải chia kết quả cho 2. Do đó, ta có (2^N - 2) / 2 = 2^(N-1) - 1.

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

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.