Nền tảng: đọc dữ liệu theo chiều dọc

1. Bảng dạng ngang và bảng dạng dọc

Bảng dạng ngang là cách ta quen nhìn: mỗi dòng là một giao dịch, liệt kê những mặt hàng được mua trong giao dịch đó. Bảng dạng dọc thì nhìn ngược lại: với mỗi mặt hàng, ta ghi ra nó xuất hiện trong những giao dịch nào. Cái danh sách giao dịch đó gọi là danh sách giao dịch của mặt hàng (tài liệu tiếng Anh gọi là tidset).

Năm thuật toán chúng ta học đều làm việc trên bảng dạng dọc, vì khi đó việc tính độ phổ biến chỉ là đếm xem một danh sách có bao nhiêu giao dịch, còn việc mở rộng một tập chỉ là tìm phần chung của hai danh sách.

2. Độ phổ biến và phần chung của hai danh sách

Độ phổ biến của một tập mặt hàng là số giao dịch có chứa đủ tất cả các mặt hàng trong tập đó. Để tìm danh sách giao dịch của một tập gồm hai mặt hàng, ta lấy phần chung của hai danh sách thành phần, tức là những giao dịch xuất hiện ở cả hai. Đếm phần chung đó được bao nhiêu thì đó chính là độ phổ biến.

3. Eclat — gom nhóm theo phần đầu chung

Eclat là thuật toán gốc mà mọi thuật toán còn lại dựa vào. Ý tưởng của nó là: những tập có chung phần đầu (vài mặt hàng đứng trước giống nhau) được gom vào cùng một nhóm. Trong mỗi nhóm, ta lần lượt ghép từng cặp thành viên với nhau để tạo ra tập dài hơn, rồi lấy phần chung của hai danh sách giao dịch để biết độ phổ biến. Tập nào còn đủ phổ biến thì giữ lại và đào sâu tiếp; tập nào không đủ thì bỏ.

Nói cách khác, Eclat đi theo chiều sâu: cứ mở rộng dần một nhánh cho tới khi không còn mở rộng được nữa, rồi mới quay lại nhánh khác.

4. Danh sách khác biệt — ý tưởng của các bản "d"

Khi danh sách giao dịch dài, lưu trọn cả danh sách rất tốn công. Người ta nghĩ ra cách lưu gọn hơn, gọi là danh sách khác biệt (tiếng Anh là diffset). Thay vì ghi lại toàn bộ giao dịch của một tập, ta chỉ ghi phần chênh lệch giữa tập đó và phần đầu của nó.

Cụ thể, danh sách khác biệt của một tập là những giao dịch có trong phần đầu nhưng lại vắng mặt trong tập. Và có một điều rất tiện: độ phổ biến của tập bằng độ phổ biến của phần đầu trừ đi số giao dịch trong danh sách khác biệt đó. Nghĩa là khi danh sách khác biệt càng ngắn thì tập càng phổ biến.

Khi ghép hai thành viên cùng nhóm để tạo tập dài hơn, ta cũng không cần dò lại danh sách giao dịch. Quy tắc là: lấy danh sách khác biệt của thành viên đứng sau, bỏ đi những giao dịch đã có trong danh sách khác biệt của thành viên đứng trước; phần còn lại chính là danh sách khác biệt của tập mới. Độ phổ biến của tập mới thì bằng độ phổ biến của thành viên đứng trước trừ đi số giao dịch vừa tìm được.

Một mẹo thực hành: khi làm tay, ở mức một (từng mặt hàng riêng lẻ) ta vẫn giữ danh sách giao dịch bình thường; chỉ bắt đầu chuyển sang danh sách khác biệt từ mức hai (khi ghép hai mặt hàng) trở đi. Lúc đó phần đầu là một mặt hàng, nên danh sách khác biệt chính là những giao dịch có ở mặt hàng đầu mà không có ở mặt hàng sau.

Nhận xét đáng nhớ: khi danh sách khác biệt rỗng, tập con và tập ghép có cùng độ phổ biến, nghĩa là chúng luôn xuất hiện cùng nhau. Đây chính là dấu hiệu cho biết tập con chưa phải là tập "đóng".

5. Ba loại tập phổ biến: tất cả, đóng, tối đại

Cùng một bảng dữ liệu, ta có thể quan tâm tới ba mức độ khác nhau.

Quan hệ giữa ba loại: mọi tập tối đại đều là tập đóng, và mọi tập đóng đều là tập phổ biến. Càng đi về phía tối đại thì danh sách càng ngắn nhưng càng ít thông tin. Với bảng dữ liệu của chúng ta, ngưỡng bằng ba, kết quả ba loại như sau: