Bài 1 · Tập đóng

Charm — tìm các tập đóng

Charm đi tìm các tập đóng, tức là những tập phổ biến không bị một tập cha nào cùng độ phổ biến che lấp. Cách làm của nó là lần lượt ghép từng cặp mặt hàng, rồi dựa vào việc so sánh hai danh sách giao dịch để quyết định: lúc thì gộp luôn hai mặt hàng vì chúng đi liền nhau, lúc thì mở thêm một nhánh mới để đào sâu.

1. Ý tưởng chung

Một tập gọi là đóng khi không có tập cha trực tiếp nào của nó có cùng độ phổ biến. Hiểu nôm na, tập đóng là "người đại diện" cho cả một nhóm tập con cùng độ phổ biến, nhờ vậy ta nén dữ liệu lại mà vẫn suy ra được độ phổ biến của mọi tập con.

Để bắt đầu, ta sắp các mặt hàng theo độ phổ biến từ thấp đến cao; nếu bằng nhau thì xếp theo bảng chữ cái. Với bảng dữ liệu của chúng ta, thứ tự đó là A rồi D rồi T (cả ba cùng có độ phổ biến bốn), sau đó tới W (độ phổ biến năm) và cuối cùng là C (độ phổ biến sáu).

Ta xét lần lượt từng mặt hàng. Với mỗi mặt hàng đang xét, ta đem nó ghép với từng mặt hàng đứng sau nó, mỗi lần ghép lại quyết định một trong bốn tình huống dưới đây.

2. Bốn tình huống khi ghép một cặp

Gọi mặt hàng đang xét là mặt hàng trước, mặt hàng đem ghép là mặt hàng sau. Ta nhìn vào phần chung của hai danh sách giao dịch; nếu phần chung còn đạt ngưỡng phổ biến thì xét tiếp một trong bốn tình huống sau, tùy theo quan hệ giữa hai danh sách:

Tình huống một — hai danh sách giống hệt nhau

Hai mặt hàng luôn xuất hiện cùng nhau ở đúng những giao dịch như nhau. Khi đó ta gộp mặt hàng sau vào mặt hàng trước, và bỏ hẳn mặt hàng sau khỏi danh sách vì ở đâu có cái này thì ở đó có cái kia.

Tình huống hai — danh sách của mặt hàng trước nằm gọn trong danh sách của mặt hàng sau

Mọi giao dịch có mặt hàng trước thì cũng có mặt hàng sau, nhưng mặt hàng sau còn xuất hiện thêm ở vài chỗ khác. Ta vẫn gộp mặt hàng sau vào mặt hàng trước, nhưng giữ lại mặt hàng sau, vì nó còn ghép được với những mặt hàng khác.

Tình huống ba — danh sách của mặt hàng sau nằm gọn trong danh sách của mặt hàng trước

Ngược lại với tình huống hai. Ta bỏ mặt hàng sau khỏi danh sách, đồng thời mở một nhánh con mới cho tập ghép để đào sâu sau này.

Tình huống bốn — không bên nào chứa trọn bên nào

Hai danh sách có phần chung nhưng mỗi bên vẫn có giao dịch riêng. Ta giữ cả hai mặt hàng, và mở một nhánh con mới cho tập ghép.

Điểm dễ sai nhất nằm ở đây: mỗi khi tình huống một hoặc hai làm mặt hàng trước "lớn lên" (gộp thêm một mặt hàng mới), thì tất cả những nhánh con đã mở từ trước cũng phải được gộp thêm mặt hàng mới đó, bởi vì chúng dùng chung phần đầu với mặt hàng trước. Chính nhờ quy tắc này mà nhánh AT về sau lớn dần thành ACTW.

Khi xét xong một mặt hàng, ta ghi tập hiện có (đã lớn lên) vào danh sách các tập đóng, với điều kiện nó chưa bị một tập nào tìm được trước đó cùng độ phổ biến bao trùm.

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

Ta dùng 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. Mỗi bước hãy thử tự nghĩ trước, sau đó mở lời giải để đối chiếu.

Nhánh mặt hàng A (A có mặt ở các giao dịch 1, 3, 4, 5)

Ghép A với D.

A có ở các giao dịch 1, 3, 4, 5; D có ở 2, 4, 5, 6. Phần chung chỉ là giao dịch 4 và 5, tức độ phổ biến bằng hai. Vì hai nhỏ hơn ngưỡng ba nên cặp AD không đủ phổ biến, ta bỏ qua, không xét tiếp.

Ghép A với T.

A có ở các giao dịch 1, 3, 4, 5; T có ở 1, 3, 5, 6. Phần chung là 1, 3, 5, độ phổ biến bằng ba, vẫn đạt ngưỡng. Bây giờ so hai danh sách: A có giao dịch 4 mà T không có, ngược lại T có giao dịch 6 mà A không có, nên không bên nào chứa trọn bên kia. Đây là tình huống bốn: ta mở một nhánh con mới cho tập AT, gắn cho nó danh sách giao dịch 1, 3, 5.

Ghép A với W.

A có ở các giao dịch 1, 3, 4, 5; W có ở 1, 2, 3, 4, 5. Mọi giao dịch có A thì đều có W, còn W xuất hiện thêm ở giao dịch 2. Vậy danh sách của A nằm gọn trong danh sách của W, đúng là tình huống hai. Ta gộp W vào A, nên mặt hàng đang xét bây giờ là AW. Đồng thời, vì A vừa lớn lên, nhánh con AT đã mở lúc nãy cũng phải gộp thêm W, trở thành ATW.

Ghép tập đang xét (lúc này là AW) với C.

AW có ở các giao dịch 1, 3, 4, 5; C có ở tất cả sáu giao dịch. Mọi giao dịch có AW đều có C, nên lại là tình huống hai. Ta gộp C vào, tập đang xét trở thành ACW với độ phổ biến bốn. Và một lần nữa, nhánh con đang là ATW cũng gộp thêm C, trở thành ACTW với danh sách giao dịch 1, 3, 5.

Kết thúc nhánh A.

Trước hết ta đào sâu nhánh con. Nhánh con bây giờ chỉ còn một tập là ACTW, không còn gì để ghép thêm, nên ta ghi nhận ACTW là một tập đóng, độ phổ biến ba. Sau đó, quay về tập đang xét, ta ghi nhận tiếp ACW là một tập đóng, độ phổ biến bốn.

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

Nhánh D (D có ở các giao dịch 2, 4, 5, 6). Ghép D với T cho phần chung chỉ gồm giao dịch 5 và 6, độ phổ biến bằng hai, dưới ngưỡng nên bỏ. Ghép D với W cho phần chung là 2, 4, 5; hai danh sách không bên nào chứa trọn bên kia nên là tình huống bốn, ta mở nhánh con DW. Ghép D với C thì mọi giao dịch có D đều có C, là tình huống hai, ta gộp C vào để được CD và đồng thời nhánh con DW lớn lên thành DWC. Cuối nhánh, ta thu được CDW là tập đóng độ phổ biến ba và CD là tập đóng độ phổ biến bốn.

Nhánh T (T có ở các giao dịch 1, 3, 5, 6). Ghép T với W cho phần chung là 1, 3, 5; không bên nào chứa trọn bên kia, là tình huống bốn, ta mở nhánh con TW. Ghép T với C thì mọi giao dịch có T đều có C, là tình huống hai, ta gộp C để được CT và nhánh con TW lớn lên thành TWC. Khi đào sâu, tập TWC có cùng danh sách giao dịch 1, 3, 5 với ACTW đã tìm trước đó, lại là tập con của ACTW, nên nó bị ACTW bao trùm và ta không ghi nó vào nữa. Cuối nhánh, ta chỉ thu được CT là tập đóng độ phổ biến bốn.

Nhánh W (W có ở các giao dịch 1, 2, 3, 4, 5). Ghép W với C thì mọi giao dịch có W đều có C, là tình huống hai, ta gộp C để được CW. Ta thu được CW là tập đóng độ phổ biến năm.

Nhánh C. Không còn mặt hàng nào đứng sau để ghép, nên ta chỉ ghi nhận C là tập đóng độ phổ biến sáu.
Kết quả: bảy tập đóng

C độ phổ biến sáu; CW độ phổ biến năm; ACW độ phổ biến bốn; CD độ phổ biến bốn; CT độ phổ biến bốn; CDW độ phổ biến ba; và ACTW độ phổ biến ba.

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

Hãy dùng một bảng dữ liệu khác để luyện, gọi là bảng P, với ngưỡng phổ biến bằng hai. Bảng gồm 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. Hãy tự chạy Charm bằng tay rồi mở đáp án để so.

Bài một. Hãy lập bảng dạng dọc và loại bỏ mặt hàng không đủ phổ biến.

B có mặt ở các giao dịch 1, 2, 3, 5 nên độ phổ biến bốn. C có mặt ở 1, 3, 4, 5 nên độ phổ biến bốn. E có mặt ở 2, 3, 4, 5 nên độ phổ biến bốn. M có mặt ở 1, 3, 5 nên độ phổ biến ba. O chỉ có mặt ở giao dịch 4, độ phổ biến một, nhỏ hơn ngưỡng hai nên ta loại bỏ O. Sắp theo độ phổ biến từ thấp đến cao, ta xét M trước, rồi tới B, C, E.

Bài hai. Ghép M với B rơi vào tình huống nào, và cho kết quả gì?

M có ở các giao dịch 1, 3, 5; B có ở 1, 2, 3, 5. Phần chung là 1, 3, 5, độ phổ biến ba, đạt ngưỡng. Mọi giao dịch có M thì đều có B, còn B xuất hiện thêm ở giao dịch 2, nên danh sách của M nằm gọn trong danh sách của B. Đây là tình huống hai: ta gộp B vào M, được tập MB với danh sách giao dịch 1, 3, 5.

Bài ba. Hãy liệt kê toàn bộ tập đóng và tập tối đại của bảng P.

Có bảy tập đóng: B độ phổ biến bốn; C độ phổ biến bốn; E độ phổ biến bốn; BE độ phổ biến ba; CE độ phổ biến ba; BCM độ phổ biến ba; và BCEM độ phổ biến hai. Chỉ có một tập tối đại duy nhất là BCEM, độ phổ biến hai. Gợi ý để hiểu: M chỉ xuất hiện cùng với B và C, nên tập đại diện đóng của M là BCM.