Đặt vấn đề Cho J = {i}, i2,., im} là một tập hợp toàn bộ các danh mục đại diện cho các thành phần của sản phẩm. Một cơ sở dữ liệu sản phẩm ký hiệu bằng DB = {P\, P;., Pn}, trong đó mỗi P; (1< i <n) là một sản phẩm. Mỗi sản phẩm được biểu diễn bằng (Items, Val), trong đó Items là toàn bộ danh mục tạo nên san phẩm P; và Val là lợi nhuận thu được khi kinh doanh sản phẩm P;. Một tập X CJ được gọi là một tập danh mục, và một tập danh mục với k danh mục thì được gọi là một k-danh-mục.
Dữ liệu ở Bảng 2.1 (DB,) được sử dụng làm vi dụ trong suốt luận văn trong đó {a, b, c, d, e, ƒ g, h} là tập hợp các danh mục tạo ra các sản phẩm {P, Pạ,. Di liệu ví dụ (DB,) Sản phẩm | Danh mục Lợi nhuận (Đô-la) Pị a,b,c 2,100 P, a,b 1,000 P3 ac 1,000 Py b,c,e 150 Ps bye 50 Po Ge 100 Pị defy 200 Ps d.e,£ h 100 Poy df 50 Pio b, fh 150 Py G 100 Dé hiểu rõ bài toán khai thác EI, hai định nghĩa cơ bản trong [B9] được trình bày lại như sau: Định nghĩa 2. Gọi X (C J) là một tập danh mục. Lợi nhuận của X được tính bằng công thức sau: g(X) = » P,.Val @) { Pil X PịItems # Ø} Lợi nhuận của tập danh mục X là tổng lợi nhuận của những sản phâm chứa ít nhất một danh mục trong X.
Vi dụ gọi X = {ac} là một tập danh mục. Ta có {P\, Pạ, Pa, Pạ, Pạ, P2, P11} là các sản phẩm chứa {a}, {c}, hoặc {ac}. Cho trước ngưỡng ¿ va cơ sở dữ liệu DB, gọi 7 là tổng lợi nhuận của nhà máy. Một tập danh mục X là EI nếu: øŒ)<Tx£ Q) trong đó 7 được tính bằng công thức sau: T= » Pị.Val @) Tổng lợi nhuận của nhà máy là tổng lợi nhuận của toàn bộ sản phẩm.
Xét DB,, ta có T= 5. Một tập danh mục X được gọi là EI nếu ø(X) < 7 x & Vi dụ, cho ế= 16%, theo Định nghĩa 2. Điều này có nghĩa là nhà máy không cần mua và lưu giữ e. Trong tình huống này, nhà máy không sản xuất các sản phẩm P,, Ps, Po, P;, và Ps, nhưng vẫn duy trì được lợi nhuận (lớn hơn hoặc bằng 5.
Từ Định nghĩa 2.2, bài toán khai thác EI là tìm toàn bộ tập danh mục có g(X) nhỏ hơn hoặc bằng 7 x &. Các thuật toán hiện có để khai thác EI Hiện tại có ba thuật toán khai thác EI là: (i) META [B9], (ii) VME [B10], và (iii) MERIT [B8]. Thuật toán Năm 2009, Deng cùng đồng sự [B9] đưa ra định nghĩa EI, bài toán khai thác EI, và thuật toán META để khai thác EI. Thuật toán này lấy ý tưởng từ thuật toán Apriori [B4].
Theo đó, thuật toán sẽ tim EI, từ những ứng viên được sinh từ việc kết hợp các phan tử trong El,¡. Ý tưởng chỉ tiết của thuật toán được mô tả như sau: dau tiên, thuật toán tìm El), sau đó, EI, được sử dụng để tìm EL, El, được sử dụng để tìm Elạ, và cứ như thé cho đến khi không một tập El, nào được tạo ra. Chỉ tiết của META được trình bay trong Hình 2. Input: DB and & Output: EIs, all erasable itemsets in DB 1.scan DB to determine T 2.EI, © {erasable l-itemsets in DB} 3.
GC, = Gen_Candidate (EI,-1) 3) for each product P € DB 6. for each candidate itemset C €GCx 7 if CO P # Ø then 8 C.return EIs = U,EIx function Gen_Candidate (EI,-1) l.for each EI, Ai={Xi, X¿ „ «Xx-2, Xk-1}€ ETk-i 3. for each remaining EI, Az={Vyi, Yor -Vk-zz Vk-iÌ€ETk-t 4. X = [Xi Xã , Xk-27 Xe Yeu} 6.
if No Inerasable Subset (X, EI,;) then 1, add X to Candidates 8.return Candidates function No_Inerasable_Subset(X, EI,-;) 1.for each (k-1)-subset X; of X 2. if X;@ EI,, then 3.return true Hình 2. Thuat toán META 2. Ví dụ Xem xét DB, với € = 16%, đầu tiên, META xác định 7 = 5.000 đô-la va El, = {e, ƒ, d, h, g} kèm với nhuận cua chúng (Bang 2.
El, và lợi nhuận của chúng trên DB, El, Lợi nhuận (Đô-la) e 600 f 600 d 350 h 250 g 200 Sau đó META gọi ham Gen_Candidate với El, là tham số để tạo ra Ely, lặp lại việc gọi hàm Gen_Candidate với El, là tham số dé tạo ra El, va tiếp tục với El; là tham số dé tạo ra Ely. Lúc này El, không thé tạo ra bat kỳ 5-EI nào; do đó, META dừng tại đây. El, El; và El, được hiển thị lần lượt trong Bảng 2. El; và lợi nhuận của chúng trên DB, EI, Lợi nhuận (Đô-la) ed 650 eh 750 eg 600 fd 600 fh 600 Sg 600 dh 500 dg 350 hg 450 Bang 2.
El; và loi nhuận của chúng trên DB, Ek Lợi nhuận (Đô-la) edh 800 edg 650 hs 750 fdh 600 fdg 600 thg 600 dhg 500 Bang 2. EI; và lợi nhuận của chúng trên DB, El, Loi nhuận (Đô-la) edhg 800 fdhg 600 2. Thao luận Thời gian khai thác của META là rất lớn vì những lý do sau: 1. META duyệt dữ liệu lần đầu tiên để xác định tổng lợi nhuận của nhà máy và k lần tiếp theo để xác định thông tin liên quan đến các EI, trong đó k là mức cao nhất của các EI kết quả.
Chiến thuật mà META sử dụng dé tao các ứng viên là không tốt. Trong chiến thuật ấy, một k-EI, X được xem xét với tất cả các k-EI còn lại để tạo El¿,;. Tuy nhiên chỉ một số ít trong số các k-EI còn lại có cùng tiền tố với X thì mới kết hợp được. Ví dụ, xét El; = {edh, edg, fhg, fah, fdg, fhg, dhg}, META dùng phan tử đầu tiên {edh} để kết hợp với tat cả các 3-EI còn lại, {edg, fhg, fah, fdg, fhg, dhg}.
Tuy nhiên {edh} chỉ có thể kết hợp với {edg}, còn {fhg, fah, fdg, fhe, dhg} thì không cần kết hợp. Cấu trúc PID_List Deng cùng đồng sự [B10] đề xuất VME sử dung cấu trúc PID_List đề khai thác EI. PID_List của danh mục A e ï là: PIDs(A) = U (P,.Val) (4) (Pị| AO PiItems # Ø} Ví dụ 2. Xét DB,, ta có PIDs(d) = {Œ1, 200), (8, 100), (9, 50)} và PIDs(h) = {(8, 100), (10, 150)}.
Gọi XA và XB là hai tập k-danh-mục với các PID_List lần lượt là PIDs(XA) và PIDs(XB). PID_List của XAB được xác định như sau: PIDs(XAB) = PIDs(XA) U PIDs(XB) 6) Ví du 2. Lợi nhuận của một tap danh mục, X, được xác định dựa vào PID_List của nó như sau: gŒX) = À Pips, vai (6) Í=1 Vi du 2.2, ta có PIDs(dh) = {(7, 200), (8, 100), (9, 50), (10, 150)}; do đó g(dh) = 200 + 100 + 50 + 150 = 500 đô-la. Thuật toán Dựa vào Định nghĩa 2.2, Deng cùng đồng sự [B10] đề xuất VME để khai thác EI.
Thuật toán này được trình bày trong Hình 2. Input: DB, and £ Output: EIs, all erasable itemsets in DB 1.scan DB to determine T 2.scan DB again to find EI¡, and their PID_lists 3. for each k-itemset P € GC, 7.return EIs = UEIx function Gen_Candidate (E1,.for each EI, Ai={Xi, X2 7 .Xk-2, Xk-1}€ Elw-| 3. for each remaining EI, Ag={yi, Yo, Yx-2, Vk-i}€EIk-i 4.
add X to Candidates 9.return Candidates function No_Inerasable Subset (X, EI,-;¡) 1.for each (k-1)-subset Xs; of X 2. if X;@ EI,, then 3.return true Hình 2. Thuật toán VME 2. Ví dụ Xét DB, với š = 16%, đầu tiên, VME xác định 7 = 5.000 đô-la và El, = {e, ƒ, d, h, g} với các PID_List của chúng (Bảng 2.
El, và các PID_List của chúng trên DB, El, PID_List (4, 150), (5, 50), (6, 100), (7, 200), (8, 100) la%so (7, 200), (8, 100), (9, 50), (10, 150), (11, 100) (7, 200), (8, 100), (9, 50) (8, 100), (10, 150) (7, 200) Tiếp đó VME sẽ sử dung El, dé tao El, sử dung El, dé tao Ely, va sử dung El; để tao Ely. Tuy nhiên El, không tạo ra được bat kỳ 5-EI nào; do đó, VME dừng tại đây. Ely, El; và El, kèm các PID_List của chúng lần lượt được trình bày trong Bảng 2. El; và các PID_List của chúng trên DB, EL PID_List ed (4, 150), (5, 50), (6, 100), (7, 200), (8, 100), (9, 50) ch (4, 150), (5, 50), (6, 100), (7, 200), (8, 100), (10, 150) eg (4, 150), (5, 50), (6, 100), (7, 200), (8, 100), fa (7, 200), (8, 100), (9, 50), (10, 150), (11, 100) ⁄h (7, 200), (8, 100), (9, 50), (10, 150), (11, 100) fg (7, 200), (8, 100), (9, 50), (10, 150), (11, 100) dh (7, 200), (8, 100), (9, 50), (10, 150) dg (7, 200), (8, 100), (9, 50) hg (7, 200), (8, 100), (10, 150) 12 Bảng 2.
El; và các PID_List của chúng trên DB, El PID_List edh (4, 150), (5, 50), (6, 100), (7, 200), (8, 100), (9, 50), (10, 150) edg (4, 150), (5, 50), (6, 100), (7, 200), (8, 100), (9, 50) thg (7, 200), (8, 100), (9, 50), (10, 150), (11, 100) jJdh (7, 200), (8, 100), (9, 50), (10, 150), (11, 100) Sdg (7, 200), (8, 100), (9, 50), (10, 150), (11, 100) Shg (7, 200), (8, 100), (9, 50), (10, 150), (11, 100) dhg (7, 200), (8, 100), (9, 50), (10, 150) Bảng 2. EI/ và các PID_List của chúng trên DB, El, PID_List edhg (4, 150), (5, 50), (6, 100), (7, 200), (8, 100), (9, 50), (10, 150) fdhg (7, 200), (8, 100), (9, 50), (10, 150), (11, 100) 2. Thảo luận Theo [B10], VME thường nhanh hơn META. Tuy nhiên, VME ton tại một vài hạn chế như sau: 1.
VME duyệt dữ liệu để xác định 7 và duyệt lại dữ liệu một lần nữa dé tìm El, với các PID_List của chúng. Duyệt dữ liệu tốn rất nhiều thời gian và bộ nhớ, do đó cần hạn chế. Trong tình huống này, nếu xem xét kỹ, thuật toán chỉ cần duyệt dữ liệu một lần duy nhất. VME sử dụng chiến thuật duyệt theo chiều sâu để khai thác EL.
Trong đó, toàn bộ EI trong El,¡ được sử dụng để tạo ra El,. Tuy nhiên, phân lớp các k-EI có cùng tiền tố là tốn rất nhiều thời gian và thao tác tính toán. Ví dụ, Ely = {ed, eh, eg, fd, fh, fg, dh, dg, hg}. Trong đó có bốn tiền tố 1-EI là {e}, {(/}, {4} và {h).
Các tập 2-EI được phân làm bón nhóm sau: {ed, eh, eg}, {/4, fh, fg}, {dh, dg} và {hg}. Sau đó, thuật toán lần lượt kết hợp các 2-EI trong cùng một nhóm với nhau dé tạo ra El; = {edh, edg, fhg, fah, fdg, fhg, dhg}. VME sử dụng chiến thuật hợp các PID_List nên tốn rất nhiều bộ nhớ sử dụng và thời gian khai thác. VME lưu trữ thông tin lợi nhuận của sản phẩm (Val) trong cặp (PID, Val) của PID_List.