TỔNG QUAN
Ngày nay, với sự phát triển mạnh mẽ của Internet, ngành công nghệ thông tin đã trở thành một lĩnh vực tiên tiến cả trên thế giới và trong nước Lĩnh vực khai thác dữ liệu đang được chú trọng phát triển, trong đó khai thác luật kết hợp trở nên phổ biến với nhiều ứng dụng thực tiễn Một trong những biến thể mới của khai thác luật kết hợp là mô hình khai thác tập phổ biến có thể xoá đóng, dựa trên các phương pháp khai thác đã được nghiên cứu trước đó.
Các thuật toán như Close, Pascal, Closet, VME, MERIT, MERIT+, và META thường gặp vấn đề về tốn bộ nhớ và thời gian xử lý chậm Tuy nhiên, các thuật toán CHARM và MEI đã được cải tiến để tăng tốc độ khai thác dữ liệu, đồng thời tối ưu hóa không gian lưu trữ và mở rộng khả năng xử lý với quy mô và chiều dài dữ liệu lớn hơn.
Thuật toán META, dựa trên Apriori, được thiết kế để khai thác các mô hình có thể xóa Tuy nhiên, thời gian thực hiện của nó chậm do sử dụng phương pháp tạo ra ứng viên, một chiến lược được coi là ngây thơ trong khai thác dữ liệu.
META đã thực hiện việc quét cơ sở dữ liệu lần đầu tiên để xác định tổng lợi nhuận của các nhà máy và thu thập thông tin liên quan đến từng EI tại các mức k, với k là mức tối đa của các kết quả EIS Chẳng hạn, META phát hiện ra một hoặc nhiều hơn 5 tập phổ biến có thể xóa, xác định mức tối đa của EIS Do đó, META cần thực hiện 6 lần quét cơ sở dữ liệu.
Chiến lược META trong việc tạo ra tập ứng viên là một phương pháp đơn giản, sử dụng (k-1)-itemset X có thể xóa để kết hợp với các (k-1)-itemset có thể xóa khác nhằm tạo ra k-itemset có thể xóa Trong số tất cả các (k-1)-itemset, chỉ một lượng nhỏ có tiền tố giống với item X mới được kết hợp Ví dụ, trong tập 2-itemset có thể xóa {ab, ac, ad, bc, bd, cd}, META sẽ xem xét item đầu tiên {ab} và kết hợp với các itemset còn lại {ac, ad, bc, bd, cd} Chỉ có {ac, ad} mới được kết hợp với {ab}, trong khi {bc, bd, cd} không có liên quan.
Thuật toán VME được đề xuất nhằm khai thác EIS, sử dụng cấu trúc PID_List để tổ chức dữ liệu PID_List bao gồm các cặp , trong đó PID là mã nhận diện sản phẩm và Val là lợi nhuận từ việc bán sản phẩm đó So với META, VME có ưu điểm là tốc độ thực thi nhanh hơn do chỉ quét cơ sở dữ liệu hai lần, dẫn đến thời gian thực thi ngắn hơn Tuy nhiên, thuật toán này cũng tồn tại một số khuyết điểm cần được xem xét.
VME quét các cơ sở dữ liệu để xác định tổng lợi nhuận của các nhà máy, sau đó tiếp tục quét để tìm các tập phổ biến 1-erasable và PID_List của chúng Quá trình quét này tiêu tốn nhiều thời gian và bộ nhớ, nhưng nếu được xem xét kỹ lưỡng, có thể thực hiện một lần duy nhất VME áp dụng chiến lược tìm kiếm theo chiều rộng (breadth-first-search), trong đó các (k-1)-itemset có thể xóa được sử dụng để tạo ra k-itemset có thể xóa Tuy nhiên, việc phân loại các (k-1)-itemsets có tiền tố giống như của (k-2)-itemset có thể xóa sẽ đòi hỏi nhiều thời gian và công sức.
Trong quá trình xử lý tập 2-itemset có thể xóa như {ab, ac, ad, bc, bd, cd}, thuật toán phân chia các phần tử thành các nhóm 2-itemset với các tiền tố giống như tập 1-itemset {a}, {b}, {c} Tập 2-itemset này được phân loại thành ba nhóm: {ab, ac, ad}, {bc, bd}, và {cd} Sau đó, thuật toán kết hợp các phần tử trong từng nhóm để tạo ra các ứng cử viên cho tập 3-itemset có thể xóa, bao gồm {abc}, {abd}, {acd}, và {bcd} Tuy nhiên, quá trình phân chia và kết hợp này tiêu tốn nhiều thời gian.
VME áp dụng các chiến lược liên minh với PID_List của X là tập con của PID_List của Y khi X là con của Y Chiến lược này yêu cầu sử dụng nhiều bộ nhớ và thực hiện các thao tác phức tạp cho một số lượng lớn EIS.
VME lưu trữ giá trị lợi nhuận (Val) cho mỗi sản phẩm trong cặp thuộc PID_List, gây ra tình trạng trùng lặp dữ liệu khi một cặp có thể xuất hiện trong nhiều PID_List khác nhau Hệ quả là thuật toán này tiêu tốn nhiều bộ nhớ.
Việc giảm thiểu sử dụng bộ nhớ có thể đạt được thông qua chỉ số lợi nhuận Thuật toán MERIT khai thác tập có thể xóa nhanh và áp dụng khái niệm NC_Set để tối ưu hóa bộ nhớ Đầu tiên, MERIT tạo ra một cây WPPC, tương tự như cấu trúc FP-tree, trong đó mỗi nút bao gồm một bộ thông tin dạng .
- Ni.item-name là định danh của item
- Ni.weight là giá trị thu được kết hợp với các item
- Ni.childnodes là một tập hợp các nút con kết hợp với các item
- Ni.pre-order là số thứ tự của các nút khi cây được duyệt qua từ trên xuống và từ trái sang phải
- Ni.post-order là số thứ tự của các nút khi cây duyệt qua từ dưới lên và từ trái sang phải
Mã (NC) của mỗi nút Ni trong cây WPPC bao gồm bộ Tập hợp mã số nút (NC_Set) kết hợp với EIS giúp giảm thiểu việc sử dụng bộ nhớ và thời gian khai thác Mặc dù NC_Set mang lại lợi thế cho thuật toán MERIT so với META, nhưng vẫn tồn tại một số nhược điểm cần lưu ý.
MERIT áp dụng các chiến lược liên minh, trong đó NC_Set của mẫu được giả định là một tập con của NC_Set của mẫu, với ⊂ Điều này dẫn đến việc tiêu tốn một lượng bộ nhớ lớn khi xử lý một số lượng lớn các EIS.
Để xây dựng cây WPPC, MERIT cần thực hiện ba lần quét cơ sở dữ liệu Sau đó, hệ thống sẽ quét cây WPPC hai lần để tạo ra tập mã nút NC_Set từ tập phổ biến có thể xóa Các bước này yêu cầu thời gian thực thi và thao tác đáng kể.
MERIT lưu trữ giá trị lợi nhuận của sản phẩm cho từng mã nút NC trong tập mã nút NC_Set, gây ra tình trạng trùng lặp dữ liệu.
MERIT gây ra sự mất mát một số lượng lớn các EIS là do hai nguyên nhân chính sau:
CƠ SỞ LÝ THUYẾT
T ập phổ biến
2.1.1 Định nghĩa Đặt I= {i 1 , i 2 , , i m } là tập hợp tất cả các item, là các thể hiện trừu tượng các thành phần của sản phẩm Một cơ sở dữ liệu sản phẩm được ký hiệu là DB= {P 1 , P 2 , , P n }, trong đó Pi (1≤ i≤n) là một sản phẩm được trình bày dưới dạng , trong đó Items là các mặt hàng (các thành phần) cấu thành Pi và Val là lợi nhuận mà các nhà máy có được bằng cách bán các sản phẩm Pi Một tập
X ⊆ I thì được gọi là một tập phổ biến (itemset), và một tập phổ biến (itemset) với k item được gọi là k-itemset
Trong cơ sở dữ liệu, tập hợp các item {a, b, c, d, e, f, g, h} được sử dụng để tạo ra các sản phẩm từ P1 đến P11 Sản phẩm P1 được cấu thành từ hai thành phần {abc} và nhà máy đã thu được 2.100 ngàn USD từ việc bán sản phẩm này.
Khai thác t ập có thể xóa
2.2.1 Định nghĩa Định nghĩa 2.1 Đặt X (⊆I) là một tập phổ biến, lợi nhuận của X được định nghĩa như sau:
Lợi nhuận của itemset X là tổng lợi nhuận của các sản phẩm chứa ít nhất một item trong tập phổ biến X
Trong ví dụ này, tập X = {ac} được coi là một tập phổ biến Dựa trên cơ sở dữ liệu trong bảng 2.1, các sản phẩm {P1, P2, P3, P4, P6, P7, P11} chứa các thành phần {a}, {c} hoặc {ac} Do đó, giá trị g(X) được tính bằng tổng các giá trị của các sản phẩm: g(X) = P1.Val + P2.Val + P3.Val + P4.Val + P6.Val + P7.Val + P11.Val.
Cho một ngưỡng ξ và một cơ sở dữ liệu sản phẩm DB, đặt T là tổng lợi nhuận của nhà máy Một tập itemset X có thể xóa được nếu: × ξ
Trong đó T được tính như sau:
Tổng lợi nhuận (T) của các nhà máy được tính bằng tổng lợi nhuận của tất cả các sản phẩm Dựa vào dữ liệu trong bảng 2.1, tổng lợi nhuận của nhà máy T được xác định rõ ràng.
5000 ngàn USD Và một itemset X được gọi là có thể xóa (EI) nếu thỏa điều kiện: × ξ
Khi đặt ngưỡng là 16% (ξ = 16%), theo định nghĩa 2.1, giá trị g ({e}) đạt 600 ngàn USD Item e được phân loại là một EI với ξ = 16% vì g ({e}) = 600 5000* 16% 800 Điều này cho thấy rằng các nhà máy không cần thiết phải mua và lưu trữ item e.
Trong trường hợp không sản xuất các sản phẩm P4, P5, P6, P7 và P8, các nhà máy vẫn có khả năng sinh lời lớn hơn hoặc bằng 800 ngàn USD Định nghĩa cơ sở dữ liệu sản phẩm (DB) bao gồm một mảng các chỉ số về lợi nhuận, được biểu diễn qua công thức G[i] = Pi.Val.
Theo Định nghĩa 2.3, lợi nhuận của sản phẩm Pi được xác định là giá trị của phần tử tại vị trí i trong chỉ số lợi nhuận G Đối với dữ liệu trong bảng 2.1, chỉ số lợi nhuận G sẽ được trình bày trong bảng 2.2.
Bảng 2.2 Chỉ số lợi nhuận G
Lợi nhuận của sản phẩm P4 là giá trị của phần tử ở vị trí thứ 4 trong G, ký hiệu là G[4] = 150 ngàn USD
2.2.2 Cấu trúc dPidset Định nghĩa 2.4(Pidset) Đối với một itemset X, p(X), ta đặt bộ định danh sản phẩm, được ký hiệu như sau:
Trong đó, A là một mục trong tập hợp X và p(A) là pidset của mục A, tức là các bộ định danh sản phẩm bao gồm A Định nghĩa 2.5 đề cập đến lợi nhuận của một tập phổ biến dựa trên pidset.
Cho X là một tập phổ biến Lợi nhuận của X ký hiệu là g (X) được tính như sau:
Trong đó G [k] là phần tử ở vị trí k của G
Pidset của tập hợp {a} trong bảng 2.1 là {1,2,3}, vì P1, P2 và P3 đều chứa thành phần {a} Tương tự, pidset của {b} là {1,2,4,5,10} Theo định nghĩa 2.4, piset của itemset X = {ab} được tính là p(X) = p({a}) p({b}) = {1,2,3} ∪ {1,2,4,5,10} = {1,2,3,4,5,10} Lợi nhuận của X được xác định là g(X) = G[1] + G[2] + G[3] + G[4] + G[5].
G[10] có giá trị 4450 ngàn USD Theo định nghĩa 2.2, tập X không thể xóa được với ngưỡng ξ % vì g(X) lớn hơn T ξ, tức là 5000 nhân với 16% bằng 800 ngàn USD Theo định lý 2.1, nếu X là tập k-itemset và B là tập 1-itemset, thì pidset của X được ký hiệu là p(X) và pidset của B là p(B).
Định lý 2.2 đã được chứng minh trong tài liệu [3] Cho hai tập phổ biến XA và XB có cùng tiền tố X, với p(XA) và p(XB) là pidset tương ứng của chúng Pidset của tập hợp XAB được tính dựa trên các pidset của XA và XB.
Chứng minh: Định lý đã được chứng minh trong [3]
Cho ví dụ về CSDL trong bảng 2.1, XA= {ab},với p(XA) = {1,2,3,4,5,10} và
XB ={ac}, với p(XB)= {1,2,3,4,6,7,11} Theo định lý 2.2 thì pidset của item XAB là p(XAB)=p(XBA) = p(XA) p(XB) = {1,2,3,4,5,10} {1,2,3,4,6,7,11} =
Trong định nghĩa 2.6, dPidset được sử dụng để mô tả mối quan hệ giữa hai tập phổ biến XA và XB có cùng tiền tố X pidset của XA được ký hiệu là p(XA) và pidset của XB được ký hiệu là p(XB) dPidset của các pidset này, ký hiệu là dP(XAB), được xác định dựa trên các pidset p(XA) và p(XB).
Theo định nghĩa 2.6, dPidset của pidsetp(XA) và p(XB) là bộ định danh sản phẩm chỉ tồn tại trên p(XB)
XA ={ab} với p(XA) ={ 1,2,3,4,5,10} và XB = {ac} với p(XB)
Dựa trên định nghĩa 2.6, dPidset của XAB được xác định là dP(XAB) = p(XB) \ p(XA) = {1,2,3,4,6,7,11} \ {1,2,3,4,5,10} = {6,7,11} Lưu ý rằng việc đảo ngược thứ tự của XA và XB sẽ dẫn đến kết quả khác, cụ thể là dP(XBA) = p(XA) \ p(XB) = {5,10} Theo định lý 2.3, với một itemset XY có dPidset dP(XY) và pidset p(XY), ta có dP(XY) ⊂ p(XY).
Chứng minh: Định lý đã được chứng minh trong [3]
Theo ví dụ 2.2, p(XAB) = p({abc}) = {1,2,3,4,5,6,7,10,11) Theo ví dụ 2.3, dP(XAB) = dP({abc}) = {6,7,11} Từ kết quả này, dP(XAB) ={6,7,11} ⊂ p(XAB)
Theo định lý 2.3, với tập itemset XY, số lượng phần tử trong dPidset của XY luôn ít hơn so với số phần tử trong pidset của XY Do đó, việc sử dụng dPidset là lựa chọn tối ưu hơn so với pidset, vì thuật toán dPidset mang lại hiệu quả cao hơn.
(1) sử dụng ít bộ nhớ
Định lý 2.4 cho thấy rằng khi có hai tập phổ biến XA và XB cùng tiền tố X, thì việc khai thác dPidset cho tập hợp XAB sẽ yêu cầu ít thời gian hơn do số phần tử ít hơn trong các tập này Cụ thể, dP(XA) và dP(XB) là dPidset tương ứng, giúp tính toán dPidset cho XAB một cách hiệu quả.
( XAB dP XB dP XA dP =
Chứng minh: Định lý đã được chứng minh trong [3]
Ví d ụ 2.5: Đặt X={a}, A={b} và B = {c} là 3 itemset Dựa trên ví dụ CSDL ở bảng 2.1, p(X) ={1,2,3}, p(A) ={1,2,4,5,10} và p(B) ={1,3,4,6,7,11}
(1) Theo định lý 2.1, p(XA) = p(X) p(A) = {1,2,3,4,5,10} và p(XB) = p(X) p(B)
={1,2,3,4,6,7,11} Dựa vào định lý 2.6, dPidset của XAB là dP(XAB) = p(XB)\p(XA) = {1,2,3,4,6,7,11}\{1,2,3,4,5,10} = {6,7,11}
(2) Theo định nghĩa 2.6, dP(XA) = p(A)\p(X) = {4,5,10} và dP(XB) = p(B)\p(X)
={4,6,7,11} Dựa theo định lý 2.4, dPidset của XAB là dP(XAB) = dP(XB)\dP(XA) = {4,6,7,11}\{4,5,10} = {6,7,11}
Từ (1) và (2), dPidset của XAB là dP(XAB) = {6,7,11} Định lý 2.5 Cho XAB là một tập phổ biến Lợi nhuận của XAB được xác định dựa vào XA như sau:
Trong đó g(XA) là lợi nhuận của X và G[k] là phần tử tại vị trí k của G
Chứng minh: Định lý đã được chứng minh trong [3]
Theo ví dụ 2.1, XA ={ab} với p(XA)= {ab} = {1,2,3,4,5,10} và XB ={ac} với p(XB) ={1,2,3,4,6,7,11} Áp dụng định nghĩa 2.5 thì lợi nhuận g(XA) = 4450 và g(XB) F50
(1) Dựa vào định lý 2.2, p(XAB) = {1,2,3,4,5,6,7,10,11} Ví thế lợi nhuận của XAB là g(XAB) = 4850 ngàn USD
(2) Theo định nghĩa 2.6, dP(XAB) = p(XB) \ p(XA) = {1,2,3,4,6,7,11} \ {1,2,3,4,5,10} ={6,7,11} Vì vậy lợi nhuận của XAB dựa trên định lý 2.5 như sau:
Theo nghiên cứu, lợi nhuận của XAB đạt 4850 ngàn USD Định lý 2.6 chỉ ra rằng, với hai tập 1-itemset A và B có thể xóa, nếu kích thước pidset của A lớn hơn kích thước pidset của B, tức là |p(A)| > |p(B)|, thì sẽ có những hệ quả nhất định.
Chứng minh: Định lý đã được chứng minh trong [3]
Ví d ụ 2.7: Đặt A ={a}, B ={b} là hai itemset Theo ví dụ CSDL ở bảng 2.1, p(A)= {1,2,3} và p(B) = {1,2,4,5,10} Khi đó:
Theo định lý 2.7, nếu kích thước của tập k-itemset XA lớn hơn tập k-itemset XB, tức là |dP(XA)| > |dP(XB)|, thì dP(AB) sẽ lớn hơn dP(BA).
Chứng minh: Định lý đã được chứng minh trong [3]
Ví d ụ 2.8: Đặt XA ={ab} với dP(XA) = {4,5,10} và XB = {ac} với dP(XB) = {4,6,7,11}
(1) dP(XAB) = dP(XB)\dP(XA) = {4,6,7,11}\{4,5,10} = {6,7,11}
(2) dP(XBA) = dP(XA)\dP(XB) = {4,5,10}\{4,6,7,11} = {5,10}
Từ (1) và (2) cho thấy kích thước của dP(XBA) nhỏ hơn so với kích thước của dP(XAB)
Khai thác t ập phổ biến đóng
2.3.1 Định nghĩa toán tử đóng [2]
Cho X ⊆I và ánh xạ c : P(I )→ P(I ) với c(X ) = i(t(X )) Ánh xạ c định nghĩa như trên được gọi là toán tử đóng (Closure Operator)
2.3.2 Định nghĩa tập phổ biến đóng [6]
Một tập phổ biến X được gọi là tập phổ biến đóng nếu và chỉ nếu c(X) =X
Hay nói theo cách khác một tập phổ biến X được gọi là đóng nếu không tồn tại superset Y ⊃ X, với
Xét CSDL được cho trong cây EIs trong hình 2.7 ta có:
{e} có độ hỗ trợ là 5 và {eg} là một superset của {e} cũng có độ hỗ trợ là 5 Do đó
{e} không phải là một tập đóng
{eg} là một tập đóng
2.3.3 Cây tìm kiếm IT (Itemset Tidset) và các lớp tương đương [1][6]
Cho I là tập các item và X ⊆ I , ta định nghĩa một hàm p(X,k) chứa k phần tử đầu của X và một quan hệ tương đương dựa vào tiền tố θ K trên itemset như sau:
Nghĩa là, hai itemset thuộc cùng một lớp tương đương khi và chỉ khi chúng chia sẻ chung k phần tử đầu phổ biến
Trong hình 2.8, mỗi nút trong cây IT biểu thị một cặp Itemset-Tidset X ×t(X), thực chất là một lớp tiền tố Tất cả các nút con của nút X đều thuộc về lớp tương đương của nó do chúng cùng chia sẻ tiền tố X.
Hình 2.8 Cây IT: cây tìm kiếm itemset-tidset
Lớp tương đương P được ký hiệu là [P] ={l 1 , l 2,…, l n } Trong đó, P là nút cha và mỗi l i là một item, đại diện cho nút Pl i x t(Pl i )
Dựa vào hình 2.8, nút gốc của các cây tương ứng với lớp [] = {d, e, f, g, h}
Con trái nhất của nút gốc bao gồm lớp [d] trên tất cả các itemset chứa d là tiền tố, tức là {e, f, g, h} Mỗi lớp thành viên đại diện cho một con của nút cha, cho phép mở rộng các items có tiền tố để tạo ra nút phổ biến mới Một tiền tố không phổ biến sẽ không có cây con được kiểm tra, cho thấy sức mạnh của phương pháp tiếp cận lớp tương đương, khi nó phân chia không gian tìm kiếm ban đầu thành các bài toán độc lập.
{ef}x78 {eg}x7 {eh}x8 {fg}x7 {fh}x810 {gh}xφ
{def}x78 {deh}x8 {dfg}x7 {dfh}x8 {dgh}xφ {efh}x8 {egh}x {fgh}x φ
Bắt đầu từ nút X, chúng ta có thể coi nó như một nút hoàn toàn mới và dễ dàng liệt kê các nút khác bằng cách kết hợp tiền tố của chúng với item X trên cùng một lớp tương đương Quá trình này sẽ tiếp tục thực hiện đệ quy đối với các lớp tương đương mới cho đến khi không còn lớp tương đương nào được tạo ra.
Trong khuôn khổ IT-tree, việc liệt kê các mẫu phổ biến là điều hiển nhiên Khi có một nút hoặc lớp tiền tố xác định, chúng ta có thể thực hiện giao tác trên tidset của tất cả các cặp phần tử trong lớp và kiểm tra min_sup, đồng thời đếm hỗ trợ tương ứng Mỗi lớp itemset với tiền tố P, [P] = {l1, l2,…, ln}, cho phép thực hiện các giao tác của t(li) với tất cả t(lj) (j > i) để tạo ra một lớp phổ biến mới, [Pli] = {lj | j > i và σ(Pli lj) ≥ min_sup}.
Với tập hợp []={d, e, f, g, h} và ngưỡng tối thiểu min_sup = 20%, ta xác định các lớp như sau: lớp [d] = {e, f}, lớp [e] = {f}, lớp [f] = {h}, lớp [g] = φ, và lớp [h] = φ Lớp [d] không bao gồm {g} và {h} vì {dg} và {dh} không phải là tập phổ biến Tương tự, lớp [e] cũng không chứa {g} và {h} do {eg} và {eh} không đáp ứng min_sup Cuối cùng, lớp [g] có tập {gh} nhưng không thỏa mãn min_sup, vì vậy nó cũng không được coi là phổ biến.
Hình 2.9 mô tả quá trình khám phá theo chiều sâu (DFS) của IT-tree cho tất cả các mẫu phổ biến
Hình 2.9 Tìm các mẫu phổ biến theo chiều sâu [6]
ENUMERATE-FREQUENT([p]); for all l I ∈[P] do
Tính chất cơ bản của cặp IT
Với bất kỳ hai nút trong cây IT, X i ×t ( X i )vàX j ×t(X j ), nếu X i ⊆ X j thì )
Hàm f được định nghĩa để xác định tổng số thứ tự trên tập hợp tất cả các itemset, với bốn tính chất cơ bản của cặp IT được mô tả trong hình 2.10 Khi xử lý nút P × t (P) với [P] = {l1, l2, …, ln} là lớp tiền tố, ký hiệu itemset Pli được đặt là Xi Mỗi thành viên của [P] tương ứng với một cặp IT Xi × t(Xi) Hai thành phần bất kỳ của lớp [P] được ký hiệu là Xi × t() và Xj × t().
(4) Nếu t(X i )⊆t(X j ) và t(X i )⊇t(X j ) thì c(X i )≠c(X j )≠c(X i ∪ X j ) Theo tính chất 1, nếu phần giao của hai tidset là bằng nhau thì |t(X i )| = |t(X j )|
=|t(X i ∪X j )| mà X i ⊂ X i ∪X j và X j ⊂ X i ∪X j nên X i ,X j không phải là tập đóng
Vì vậy, Xi ,X j thuộc về cùng một tập đóng chứa X i ∪X j
Theo tính chất 2, ta có c(X i ) =c(X i ∪X j )⇒X i không là tập đóng và X i , j i X
X ∪ thuộc về cùng một tập đóng Bên cạnh đó, do t(X j )≠t(X i ) nên X i và X j thuộc về hai tập đóng khác nhau
Tính chất 3 tương tư tính chất 2
Theo tính chất 4, X i , X j , và X i ∪X j sẽ thuộc về ba tập đóng khác nhau
Hình 2.10 trình bày tính chất cơ bản của itemset và tidset Định nghĩa thứ tự tổng thể f là một ánh xạ đơn từ tập các itemset sang tập số nguyên, ký hiệu là P(I) α N Đối với bất kỳ hai itemset X i và X j, chúng ta có thể nói rằng X i ≤ f X j nếu và chỉ nếu f(X i) ≤ f(X j) Hàm f này thiết lập một thứ tự tổng thể trên tất cả các itemset.
Nếu f chỉ thứ tự từ điển, thì ac ≤ ad; tuy nhiên, khi f được sắp xếp theo thứ tự tăng dần của độ phổ biến các itemset, thì ad ≤ ac do σ(ac) ≤ σ(ad).
Trong thế giới thực, nhiều vấn đề vẫn chưa được giải quyết triệt để bởi các phương pháp hiện có Chẳng hạn, các mô hình dữ liệu như điều tra dân số và viễn thông cần tìm các tập phổ biến dài khoảng 30 hoặc 40 Hiện có hai giải pháp cho vấn đề khai thác mô hình dữ liệu dài: thứ nhất là khai thác tập phổ biến tối đại, giúp hiểu các mô hình dài trong lĩnh vực dày đặc nhưng có thể dẫn đến mất mát thông tin nếu tần số của subset không có sẵn, khiến các tập tối đại không thể tạo ra luật Thứ hai là khai thác tập phổ biến đóng, cung cấp một phương pháp khác để giải quyết vấn đề này.
Thuật toán CHARM là một phương pháp hiệu quả để khai thác tất cả các tập phổ biến đóng, khám phá cả không gian tập phổ biến và không gian các giao tác thông qua cây IT-tree Khác với các phương pháp trước đây chỉ tập trung vào không gian tập phổ biến, CHARM áp dụng một phương pháp tìm kiếm mới với cây tìm kiếm kép itemset-tidset Bằng cách sử dụng phương pháp tìm kiếm lai, CHARM nhanh chóng hội tụ tính đóng và xác định các tập phổ biến đóng mà không cần liệt kê nhiều tập con Kỹ thuật diffset được áp dụng để tính toán nhanh tần số, giúp giảm bộ nhớ cho các tính toán trung gian Đồng thời, phương pháp băm nhanh hashbased được sử dụng để loại bỏ các tập "không đóng" trong quá trình tính toán CHARM có ưu điểm là không sinh ứng viên và áp dụng phương pháp chia để trị, cho phép tìm kiếm các tập phổ biến đóng chỉ với một lần đọc cơ sở dữ liệu Các thử nghiệm trên nhiều cơ sở dữ liệu thực tế và tổng hợp cho thấy CHARM vượt trội hơn so với các phương pháp trước đó.
Cho 2 tập phổ biến X, Y ⊆ I, n ếu (X) = (Y), thì X và Y sẽ thuộc về cùng tập phổ biến đóng có tiền tố là X ∪ Y Như vậy ta không cần xét bất cứ tập cha nào của cả X lẫn Y ngoài X ∪ Y Quá trình tiếp tục khám phá đệ qui bằng cách tiếp tục xét các tập cha của X ∪ Y
1 [ỉ] = {li ì t(li) : li ∈ I ∧ (li) ≥ minSup}
4 for each li × t(li) in P do
6 for each lj × t(lj) in P with j>i do
7 X = li ⋃ lj and Y = t(li) ⋂ t(lj)
8 CHARM-PROPERTY(X × Y, li, lj, Pi, [Pi], [P])
CHARM-PROPERTY(X × Y, li, lj, Pi, [Pi], [P])
- Đầu vào: Cơ sở dữ liệu, min-sup
- Đầu ra: Các tập phổ biến đóng
- Đầu tiên thuật toán khởi tạo lớp tiền tố [P] của các nút để kiểm tra các nút 1- itemset và tidset của chúng (l i × t(l i ),l i ∈ Ι) (dòng 1)
- Giả sử các phần tử trong [P] được sắp xếp theo thứ tự tổng thể f
- Gọi thủ tục CHARM-EXTEND để tính toán và tìm ra các phổ biến tập đóng
- Trả về tập phổ biến đóng C
CHARM-EXTEND thực hiện việc xem xét từng cặp IT trong lớp tiền tố [P] Đối với mỗi cặp IT l i × t (l i) (dòng 4), nó kết hợp với các cặp IT khác l j × t (l j) theo tổng thứ tự f (dòng 6) Mỗi li tạo ra một tiền tố mới P i = P∪l i, với lớp [Pi] ban đầu được khởi tạo rỗng (dòng 5) Tại dòng 7, hai cặp IT được kết hợp để tạo ra một cặp mới X Y, trong đó X = l j.
Y = ∩ Dòng 8 kiểm nghiệm bốn tính chất cơ bản của cặp IT có thể áp dụng qua CHARMPROPERTY, giúp CHARM khám phá nhanh các tập phổ biến đóng Đoạn chương trình này có khả năng sửa đổi lớp [P] hiện tại bằng cách loại bỏ cặp IT đã được gộp vào các cặp khác và chèn các cặp IT mới vào lớp mới [Pi] Nó cũng có thể điều chỉnh các tiền tố Pitrong trường hợp hai tính chất đầu tiên được giữ Sau đó, itemset Pi sẽ được thêm vào tập hợp itemset đóng C (dòng 9), với điều kiện là Pi không được gộp vào tập đóng đã tìm thấy trước đó Khi tất cả l j đã được xử lý, chương trình sẽ đệ quy với lớp mới [Pi] theo chiều sâu (dòng 10) Cuối cùng, sau khi trả về kết quả, tập itemset đóng chứa Pi sẽ được tạo ra và chương trình sẽ quay về dòng 4 để xử lý cặp IT tiếp theo trong [P].
Sắp xếp lại các phần tử tự động
Thông thường, việc truy xuất dữ liệu được thực hiện theo thứ tự từ điển, nhưng chúng ta có thể chỉ định thứ tự khác theo ý muốn Một trong những cách tiếp cận hứa hẹn nhất là sắp xếp các tập phổ biến dựa trên độ hỗ trợ của chúng, nhằm tăng cơ hội cắt tỉa các phần tử từ lớp [P] Tính chất 1 và 2 cho thấy rằng hai trường hợp này thuận lợi hơn so với hai trường hợp còn lại.
Khai thác t ập có thể xóa đóng
Một tập có thể xóa được gọi là tập xóa đóng nếu không tồn tại tập cha của nó có cùng lợi nhuận với nó
Xét CSDL được cho trong cây EIS hình 2.6 ta có:
Tập {e} và tập {eg} đều là các tập có thể xóa, tuy nhiên {eg} là superset của {e} với lợi nhuận đạt 600 Điều này cho thấy {e} không phải là tập xóa đóng, trong khi {eg} lại là một tập xóa đóng.
2.4.2 Thuật toán MECI Ý tưởng thuật toán:
- Trước tiên thuật toán sẽ quét CSDL và tính tổng lợi nhuận (T), gain và xác định tập 1-itemset
- Sắp xếp tập 1-itemset theo thứ tự
- Gọi thủ tục expand_E để tìm tập (k-1)itemset
Tìm kiếm các item có thể xóa và xác định xem chúng có phải là item đóng hay không Nếu item đó là đóng, hãy lưu trữ nó; nếu không, hãy bỏ qua và tiếp tục tìm kiếm item tiếp theo.
- Sau đó thực hiện đệ qui lại
Mô tả thuật toán Đầu vào: CSDL DB và ngưỡng ξ ả: Tập các ECIS
Output: , the set of all ECPs
1 Scan to determine the total profit of ( ), the index of gain ( ), and erasable 1-patterns with their pidsets ( 1)
2 Sort 1 by the length of their pidsets in ascending order
3 If 1 has more than one element, the algorithm will call
12 Else if dP( [i]) ⊂ dP( [j])then
15 Else if dP( [i]) ⊃ dP( [j])then
22 If Check_Closed_Property( [i]) == true then
24 Add [i] to Hashtable with [i].val as a key
Function Check_Closed_Property(EI)
1 Let ECPs ← Hashtable[EI.val]
2 If ECPs is not null then
3 For each ECP in ECPs do
Hình 2.16 mô tả quá trình tìm kiếm tập ECIS với gain đạt ngưỡng T×ξ (16% x 50000) trên cây IT Đầu tiên, tập I = {d,e,f,g,h} được sắp xếp giảm dần theo pidset thành t={e,f,d,h,g} Khi t i ={e}, nó kết hợp với các t j ={f,d,h,g} có gain đạt ngưỡng T×ξ để tạo thành các nút con {ed,eh,eg} Nút con {ef} với gain 0 không đạt ngưỡng T×ξ nên bị loại bỏ và không được sinh ra ở mức tiếp theo trên cây IT Ngoài ra, do gain của {e} = 600 và bằng với superset của nó là {eg}`0, {e} không thể là tập xóa đóng nên được thay thế bằng tập {eg}.
Hình2.16 cây IT-tree tìm ECI s thỏa ngưỡng T ×ξ