Bài 3 · Danh sách khác biệt

dEclat — mọi tập phổ biến bằng danh sách khác biệt

dEclat chính là Eclat, chỉ khác ở chỗ thay vì lưu trọn danh sách giao dịch, nó lưu danh sách khác biệt cho gọn. Nó vẫn tìm ra toàn bộ tập phổ biến; điểm khác duy nhất là cách tính độ phổ biến: lấy độ phổ biến của phần đầu trừ đi số giao dịch khác biệt.

1. Ý tưởng chung

Danh sách khác biệt lưu phần chênh lệch giữa một tập và phần đầu của nó, nên thường ngắn hơn danh sách giao dịch rất nhiều, nhờ vậy tính toán nhanh và đỡ tốn bộ nhớ.

Khi làm tay, ta theo thói quen thế này: ở mức một, tức từng mặt hàng riêng lẻ, vẫn giữ danh sách giao dịch bình thường; chỉ bắt đầu dùng danh sách khác biệt từ mức hai, khi ghép hai mặt hàng trở đi.

Cần nhớ là kết quả của dEclat giống hệt Eclat: nó cho ra tất cả các tập phổ biến, chứ không phải chỉ tập đóng hay tập tối đại.

2. Hai quy tắc tính

Ở mức hai, khi phần đầu là một mặt hàng

Danh sách khác biệt của tập hai mặt hàng là những giao dịch có mặt hàng đầu nhưng vắng mặt hàng sau. Độ phổ biến của tập bằng độ phổ biến của mặt hàng đầu trừ đi số giao dịch khác biệt vừa đếm.

Từ mức ba trở đi, khi ghép hai thành viên cùng nhóm

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 là danh sách khác biệt của tập mới. Độ phổ biến của tập mới 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. Lưu ý thứ tự: luôn lấy của thành viên sau trừ đi của thành viên trước, và trừ độ phổ biến từ thành viên trước.

3. Giải mẫu từng bước

Vẫn bảng dữ liệu quen thuộc, ngưỡng phổ biến bằng ba, thứ tự xét là A, D, T, W rồi C. Độ phổ biến của từng mặt hàng: A bốn, D bốn, T bốn, W năm, C sáu.

Nhóm phần đầu A — bước sang mức hai

Tính cho cặp AD và cặp AT.

Với AD: A có ở các giao dịch 1, 3, 4, 5; D có ở 2, 4, 5, 6. Những giao dịch có A mà vắng D là 1 và 3, nên danh sách khác biệt gồm hai giao dịch. Độ phổ biến của AD bằng bốn trừ hai, còn hai, nhỏ hơn ngưỡng nên loại. Với AT: những giao dịch có A mà vắng T chỉ là giao dịch 4, nên danh sách khác biệt gồm một giao dịch; độ phổ biến của AT bằng bốn trừ một, còn ba, đạt ngưỡng nên giữ.

Tính cho cặp AW và cặp AC.

Với AW: mọi giao dịch có A thì đều có W, nên không có giao dịch nào khác biệt; danh sách khác biệt rỗng, độ phổ biến của AW bằng bốn trừ không, vẫn là bốn. Với AC: tương tự, mọi giao dịch có A thì đều có C, nên danh sách khác biệt cũng rỗng, độ phổ biến của AC là bốn. Như vậy nhóm con của A gồm ba thành viên: AT có danh sách khác biệt gồm giao dịch 4, còn AW và AC đều có danh sách khác biệt rỗng.

Lên mức ba và mức bốn trong nhóm A.

Ghép AT với AW để được ATW: lấy danh sách khác biệt của AW (đang rỗng) bỏ đi phần của AT, kết quả vẫn rỗng; độ phổ biến của ATW bằng độ phổ biến của AT là ba, trừ không, vẫn là ba. Ghép AT với AC để được ATC: tương tự, danh sách khác biệt rỗng, độ phổ biến ba. Ghép AW với AC để được AWC: danh sách khác biệt rỗng, độ phổ biến bốn. Cuối cùng lên mức bốn, ghép ATW với ATC để được ATWC: danh sách khác biệt vẫn rỗng, độ phổ biến ba.

Các nhóm D, T và W

Nhóm D. Cặp DT có danh sách khác biệt gồm giao dịch 2 và 4, độ phổ biến bốn trừ hai còn hai nên loại. Cặp DW có những giao dịch có D mà vắng W là giao dịch 6, nên danh sách khác biệt gồm một giao dịch, độ phổ biến bốn trừ một còn ba. Cặp DC có danh sách khác biệt rỗng, độ phổ biến bốn. Lên mức ba, ghép DW với DC để được DWC: lấy phần của DC (rỗng) bỏ đi phần của DW, vẫn rỗng, độ phổ biến của DWC bằng ba trừ không, là ba.

Nhóm T. Cặp TW có những giao dịch có T mà vắng W là giao dịch 6, danh sách khác biệt một giao dịch, độ phổ biến bốn trừ một còn ba. Cặp TC có danh sách khác biệt rỗng, độ phổ biến bốn. Lên mức ba, ghép TW với TC để được TWC: danh sách khác biệt rỗng, độ phổ biến ba.

Nhóm W. Cặp WC có danh sách khác biệt rỗng, độ phổ biến năm.
Kết quả: mười chín tập phổ biến

Năm tập một mặt hàng: A độ phổ biến bốn, D bốn, T bốn, W năm, C sáu. Các tập hai mặt hàng: AT độ phổ biến ba, AW bốn, AC bốn, DW ba, DC bốn, TW ba, TC bốn, WC năm. Các tập ba mặt hàng: ATW ba, ATC ba, AWC bốn, DWC ba, TWC ba. Và một tập bốn mặt hàng: ATWC độ phổ biến ba. (Một vài tên viết gọn theo thứ tự chữ cái: AC cũng là AC, TC chính là CT, WC chính là CW, DC chính là CD, còn ATWC chính là ACTW.)

4. Bài tập tự luyện

Dùng bảng P, ngưỡng phổ biến bằng hai. Năm giao dịch: giao dịch một có B, C, M; giao dịch hai có B, E; giao dịch ba có B, C, E, M; giao dịch bốn có C, E, O; giao dịch năm có B, C, E, M. Sau khi loại O, thứ tự xét là M, B, C, E.

Bài một. Tính danh sách khác biệt và độ phổ biến của MB, MC, ME ở mức hai.

M có mặt ở các giao dịch 1, 3, 5, độ phổ biến ba. Với MB: B có ở 1, 2, 3, 5, nên mọi giao dịch có M thì đều có B; danh sách khác biệt rỗng, độ phổ biến ba trừ không là ba. Với MC: C có ở 1, 3, 4, 5, nên mọi giao dịch có M cũng có C; danh sách khác biệt rỗng, độ phổ biến ba. Với ME: E có ở 2, 3, 4, 5, mà M ở 1, 3, 5; giao dịch 1 có M mà vắng E, nên danh sách khác biệt gồm một giao dịch, độ phổ biến ba trừ một là hai.

Bài hai. Lên mức ba: tính danh sách khác biệt và độ phổ biến của MBC, MBE.

Ghép MB với MC để được MBC: lấy danh sách khác biệt của MC (rỗng) bỏ đi phần của MB (cũng rỗng), kết quả rỗng; độ phổ biến của MBC bằng độ phổ biến của MB là ba, trừ không, vẫn là ba. Ghép MB với ME để được MBE: lấy phần của ME (gồm giao dịch 1) bỏ đi phần của MB (rỗng), kết quả vẫn là giao dịch 1; độ phổ biến của MBE bằng ba trừ một, là hai. Đi tiếp lên mức bốn, ghép MBC với MBE để được MBCE: phần khác biệt vẫn là giao dịch 1, độ phổ biến ba trừ một, là hai.