CƠ SỞ LÝ THUYẾT
2.2. Các kỹ thuật liên quan
Dù không phủ nhận cách chọn các itemset dựa trên tần suất, cách này xem tất cả các item và các giao dịch trong CSDL giao dịch nhƣ nhau. Trong thực tế, các item hay các giao dịch có thể quan trọng khác nhau đối với người sử dụng. Ví dụ, itemset (Nước hoa, đá quí) đối với trưởng nhóm bán hàng có thể có lợi nhuận tiềm ẩn cao hơn itemset (Nước hoa, son môi). Thật sự có ích nếu có nhiều mô hình nói về tầm quan trọng theo ngữ nghĩa cho các itemset.
Khai thác các itemset dựa trên ràng buộc đã tạo nên qui trình mô tả sự quan tâm của người dùng không khác gì so với các ràng buộc. Bốn khuynh hướng dựa trên ràng buộc là R ng uộc khả chuyển CC , các it m có trọng số WI , hai thác độ có ích cao (HUM), và Chia s các itemset (IS). Khác biệt chính giữa các hướng tiếp cận này là (1) mức độ khác nhau về độ mịn được dùng để xác định tầm quan trọng ngữ nghĩa của các itemset, và (2) chiến lƣợc tỉa cành khác nhau đƣợc phát triển theo các ràng buộc xác định trên các itemset.
R ng uộc khả chuyển CC đƣợc Pei et al [7]. đƣa ra có ƣu điểm đáng kể trong việc nghiên cứu khai thác dựa trên ràng buộc. Trong hướng tiếp cận này, một itemset S1 = i1, ...., im là itemset tiền của itemset S2 = i1, . . ., in nếu các item trong S1 và S2 đƣợc liệt kê theo cùng thứ tự và mn.
Định nghĩa 2.16. Ràng buộc C đƣợc gọi là khả chuyể ô iệu theo thứ tự O trên các item nếu có itemset S thỏa tính chất P, thì bất cứ itemset tiền tố nào của S cũng vậy. Ràng buộc C đƣợc gọi là kh chuy n ơn ệu đối với một thứ tự O trên các item nếu có itemset S vi phạm tính chất P, thì bất cứ itemset tiền tố nào của S cũng vậy. Ràng buộc C đƣợc gọi là kh chuy n đối với một thứ tự O nếu nó khả chuyển không đơn điệu hoặc khả chuyển đơn điệu đối với thứ tự O.
Sau đây là minh họa một ràng buộc khả chuyển.
Ví dụ 2.3. Xét bảng 1.2 là bảng lợi nhuận.
Cho avg(S)30 là ràng buộc lợi nhuận trung bình của itemset S. Ta có avg(ABCD)
= (5+100+38+1)/4 = 36. Nếu các item sắp xếp theo lợi nhuận đơn vị giảm dần, ta đƣợc <B, C, A, D>.
Itemset BCAD có BCA, BC, và B là các itemset tiền tố của nó theo thứ tự <B, C, A, D>.
Thì avg(BCA) = 47.67, avg (BC) = 69, và avg (B) = 100.
Lợi nhuận trung bình của itemset BCAD ít nhất là 30, xem đây là lợi nhuận trung bình cho các itemset tiền tố của nó theo thứ tự <B, C, A, D>.
Theo định nghĩa, ràng buộc avg(ABCD) 30 thì khả chuyển không đơn điệu đối với thứ tự <B, C, A, D>.
Do vậy, nó khả chuyển theo thứ tự <B, C, A, D>.
Hướng tiếp cận item có trọng số (WI) và hướng tiếp cận khai thác có giá trị (VAM) cho thấy tầm quan trọng ngữ nghĩa của các itemset ở mức item. Cả hai hướng tiếp cận giả sử các item trong CSDL giao tác (các cột trong một bảng) có các trọng số khác nhau. Ví dụ, một máy tính (món hàng A) có thể quan trọng hơn điện thoại (món hàng B) về mặt lợi nhuận. Nếu tìm kiếm với khối lƣợng lớn thì dùng hướng tiếp cận khai thác có giá trị. Chiến lược tỉa được phát triển theo hướng WI chẳng qua dùng ràng buộc khả chuyển theo thứ tự sắp xếp các item theo thứ tự giảm dựa trên trọng số.
Theo cách này, hai cách tính đƣợc đƣa ra để thay thế độ hỗ trợ. Cách tính đầu tiên đƣợc gọi là độ hỗ trợ có trọng số, đƣợc định nghĩa nhƣ sau:
) S ( s ) w ( S port sup
S
i p
w
p
(2.1) Với wp biểu thị trọng số của item ip.
Yếu tố đầu tiên của cách tính độ hỗ trợ có trọng số có xu hướng theo các luật có nhiều item. Khi số item lớn, thậm chí nếu tất cả các trọng số nhỏ, thì tổng trọng số có thể lớn. Độ hỗ trợ có trọng số chuẩn được đưa ra để giảm khuynh hướng này và đƣợc định nghĩa nhƣ sau:
) S ( s ) w S (
) 1 S ( port sup
S
i p
nw
p
(2.2) với |S| là số item trong itemset S.
Cách tính độ hỗ trợ truyền thống là một trường hợp đặc biệt của độ hỗ trợ có trọng số chuẩn, do khi tất cả các trọng số dành cho các item bằng 1, thì độ hỗ trợ có trọng số chuẩn giống hệt độ hỗ trợ. Hướng tiếp cận các item có trọng số (WI) và hướng tiếp cận khai thác giá trị thêm vào (VAM) dùng các item có trọng số để xác định tầm quan trọng ngữ nghĩa của các itemset ở mức item. Không giống nhƣ khai thác tập phổ biến, nó xem tất cả các item như nhau, cả hai hướng tiếp cận này giả sử các item trong một tập dữ liệu giao tác (các cột trong bảng) có các trọng số khác nhau để phản ánh tầm quan trọng của chúng đối với người dùng.
Hướng tiếp cận khai thác độ có ích cao (HUM) cho thấy tầm quan trọng ngữ nghĩa của các itemset ở mức giao tác. Hướng tiếp cận này giả sử các giao tác trong CSDL (các hàng trong bảng) có các giá trị có ích khác nhau. Ví dụ, cùng một cách chữa trị cho nhiều bệnh nhân khác nhau (các giao tác khác nhau, cũng một thang thuốc nhƣ vậy) sẽ có nhiều cấp độ hiệu quả khác nhau. Chiến lƣợc tỉa cho hướng này dùng ràng buộc khả chuyển có thứ tự sắp xếp các giao tác giảm dần dựa trên các giá trị có ích của chúng.
Một mô hình dữ liệu khác bằng cách gán một trọng số cho mỗi giao tác.
Trọng số biểu diễn tầm quan trọng của giao tác trong tập dữ liệu. Các trọng số đƣợc gán cho các giao tác cũng đƣợc gọi là các trọng số dọc. Ví dụ, trọng số có thể phản ánh thời gian giao tác, có nghĩa là, các giao tác càng gần càng có trọng số lớn. Dựa trên mô hình này, độ hỗ trợ có gắn trọng số dọc đƣợc định nghĩa nhƣ sau:
T t
T
t q
v w
w )
S ( port
sup q S (2.3) với wq và w biểu thị trọng số dọc đối với các giao tác tq và t, một cách tương ứng.
Mô hình trọng số hổn hợp dùng cả hai trọng số ngang và dọc. Trong mô hình này, mỗi item đƣợc gán một trọng số ngang và mỗi giao tác đƣợc gán với trọng số dọc.
Độ hỗ trợ trọng số hỗn hợp đƣợc định nghĩa nhƣ sau:
) S ( port sup ) S ( port sup ) S ( port
sup m nv v (2.4) Cả supportv và supportm là các mở rộng của phép đo độ hỗ trợ truyền thống. Nếu tất cả các trọng số ngang và dọc đƣợc bật là 1, thì cả supportv và supportm đúng là độ hỗ trợ truyền thống.
Hướng tiếp cận chia s itemset (IS) cho thấy tầm quan trọng ngữ nghĩa của các giá trị số có liên quan tiêu biểu với các item riêng lẻ trong một CSDL giao tác (các ô trong bảng). Ảnh hưởng rõ ràng khi mua tập các món hàng (itemset) được đo bằng việc chia sẻ từng món hàng (item), là phần chia của giá trị số nói chung nào đó, nhƣ là tổng số các item đƣợc bán. Ví dụ 2.1 máy tính đƣợc bán trong giao tác này có thể đƣợc xem là quan trọng hơn hai máy tính đƣợc bán trong giao tác khác.
Vì vậy miền của bảng có thể là các con số rõ ràng, nhƣ là số các item đƣợc bán, chứ
không phải là miền nhị phân {0,1}, 1 là item xuất hiện trong giao tác, 0 có nghĩa là không xuất hiện. Dùng cách tìm kiếm heuristic để tìm các itemset với các giá trị chia sẻ cao hơn ngƣỡng chia sẻ tối thiểu.
Cấu trúc chia sẻ itemset có đề cập đến các trọng số cho cả các thuộc tính và cho các cặp giá trị thuộc tính. Ảnh hưởng rõ ràng nhất của việc mua một itemset có thể đƣợc đo bằng độ chia sẻ itemset, giao tác của giá trị số tổng quan nào đó, nhƣ là tổng giá trị của tất cả các món hàng đƣợc bán. Ví dụ, trong một tập dữ liệu giao tác, trọng số trên một thuộc tính có thể biểu diễn giá của một mặt hàng, và trọng số của một cặp giá trị thuộc tính có thể biểu diễn số lƣợng mặt hàng trong một giao tác.
Dựa trên mô hình này, trong framework chia sẻ itemset, độ hỗ trợ đƣợc tổng quát hóa. Độ hỗ trợ đếm cho itemset S đƣợc định nghĩa nhƣ sau:
T t i I T
t i S p q
) t , i ( w
) t , i ( w )
S sup(
_
count q S p (2.5) Với w(ip,tq)biểu thị trọng số của thuộc tính ip đối với giao tác tq và w(ip,tq )>0.
Tương tự, độ hỗ trợ khối lượng được định nghĩa như sau:
T
t i I
T
t i S p q p
) i ( w ) t , i ( w
) i ( w ) t , i ( w )
S sup(
_
amount q S p (2.6)
Với w(ip) là trọng số của thuộc tính ip và w(ip)>0.
Phép đo độ có ích khác, đƣợc định nghĩa nhƣ sau:
S
q T P
t i Sw ( ip, tq ) w ( ip ) )
S (
u (2.7)
Với w(ip,tq)biểu thị giá trị độ có ích của thuộc tính ip đối với giao tác tq, w(ip) biểu thị giá trị có ích của thuộc tính ip, w(ip,tq )>0 và w(ip)>0.
Hàm tính độ có ích tương tự như độ hỗ trợ số lượng, ngoại trừ nó biểu diễn một giá trị độ có ích, nhƣ là lợi nhuận theo đô la, hơn là tỉ lệ tổng trọng số của tất cả các giao tác trong tập dữ liệu.
Hướng tiếp cận chia sẻ itemset (IS) cho thấy tầm quan trọng ngữ nghĩa của các giá trị số có liên quan tiêu biểu đến các item cá nhân trong một tập dữ liệu giao tác (các ô trong bảng).
Khai thác kết hợp dựa trên độ có ích hướng mục tiêu (OOA) cho phép người dùng thiết lập các mục tiêu cho qui trình khai thác. Trong phương pháp này, các thuộc tính đƣợc phân thành hai nhóm, các thuộc tính mục tiêu và các thuộc tính không mục tiêu. Một thuộc tính không mục tiêu (còn đƣợc gọi là thuộc tính không mục đích) chỉ được cho phép xuất hiện trong các vế trước của luật kết hợp. Một thuộc tính mục tiêu (đƣợc gọi là thuộc tính mục đích trong) chỉ đƣợc phép xuất hiện ở vế sau của luật. Cặp giá trị thuộc tính đích đƣợc gán các giá trị có ích. Vấn đề khai thác là để tìm các tập phổ biến không có thuộc tính đích, sao cho các giá trị có ích của các cặp giá trị thuộc tính đích tương ứng của chúng trên ngưỡng. Ví dụ, trong bảng 2.1, “Cách xử lý” là thuộc tính không mục tiêu, trong khi “Hiệu quả” và
“Hiệu ứng phụ” là hai thuộc tính mục tiêu. Mục đích của vấn đề khai thác là tìm ra các “cách xử lí” có “hiệu quả cao” và ít “hiệu ứng phụ”. Phép đo độ có ích đƣợc định nghĩa nhƣ sau:
S
q T
t u ( tq ) )
S ( s ) 1 S (
u (2.8)
Với S là các itemset không mục tiêu đƣợc khai thác (cặp giá trị thuộc tính “Cách xử lý” trong ví dụ) và u(tq)biểu thị độ có ích của giao tác tq. Hàm u(tq)đƣợc định nghĩa nhƣ sau:
q
p C
i p
q) f ( i )
( t
u (2.9)
Với Cq biểu thị tập các item đích trong giao tác tq và f(ip)là hàm tính độ có ích của item ip, biểu thị độ có ích liên quan đến ip. Nếu chỉ có một thuộc tính đích và trọng số của nó bằng 1, tqTSu(tq)chính là s(S), thì u(S) bằng 1.
Tiếp tục ví dụ, ta gán các giá trị có ích cho các cặp giá trị thuộc tính đích đƣợc minh họa trong bảng 2.2 và nhận các giá trị có ích phù hợp với các xử l í đƣợc
minh họa trong bảng 2.3. Ví dụ, “Cách xử lý” 5 có giá trị có ích lớn nhất 1.2, và vì vậy, nó đạt đến tốt nhất mục tiêu do người dùng xác định.
Bảng 2.1: Tập dữ liệu y khoa
Hướng tiếp cận khai thác OOA đều đạt được tầm quan trọng ngữ nghĩa của các itemset ở mức giao tác. Họ giả sử các giao tác trong một tập dữ liệu (các hàng trong bảng) có liên quan đến các giá trị có ích phản ánh tầm quan trọng của chúng đối với người dùng.
TID Cách xử lý Hiệu quả Hiệu ứng phụ
t1 1 2 4
t2 2 4 2
t3 2 4 2
t4 2 2 3
t5 2 1 3
t6 3 4 2
t7 3 4 2
t8 3 1 4
t9 4 5 2
t10 4 4 2
t11 4 4 2
t12 4 3 1
t13 5 4 1
t14 5 4 1
t15 5 1 1
t16 5 3 1
Bảng 2.2: Các giá trị có ích dành cho thuộc tính “Hiệu quả” và “Hiệu ứng phụ”.
Hiệu quả Hiệu ứng phụ
Giá trị Ngữ nghĩa Độ có ích Giá trị Ngữ nghĩa Độ có ích
5 Tốt hơn nhiều 1 4 Rất nghiêm trọng -0.8
4 Tốt hơn 0.8 3 Nghiêm trọng -0.4
3 Không ảnh hưởng 0 2 Chút ít 0
2 Xấu -0.8 1 Bình thường 0.6
1 Xấu nhiều -1
Bảng 2.3: Độ có ích của các item
Itemset Độ có ích Cách xử lý = 1 -1.6 Cách xử lý = 2 -0.25 Cách xử lý = 3 -0.066 Cách xử lý = 4 0.8 Cách xử lý = 5 1.2
Hai chiến lƣợc tỉa chính dùng trong khai thác các itemset là tính chất Apriori trong khai thác tập phổ biến và tính chất khả chuyển đối với ràng buộc khả chuyển dựa trên việc khai thác các itemset.
Tính chất Apriori (bao đóng giảm) cho biết nếu một itemset là phổ biến theo độ hỗ trợ, thì toàn bộ các tập con khác rỗng của nó cũng phải phổ biến theo độ hỗ trợ. Ví dụ, trong bảng 1.3, nếu itemset AD là một tập phổ biến, các tập con A và D của nó cũng phải là các tập phổ biến. Tất nhiên, ràng buộc độ hỗ trợ của các tập phổ biến thì không đơn điệu.
Định nghĩa 2.17. Một ràng buộc C là ôn ơn ệu nếu khi có một itemset S vi phạm một ràng buộc C, thì các itemset có nhiều item hơn S nhƣng chứa S cũng vi phạm. Ràng buộc C là ơn ệu nếu tất cả itemset S thỏa ràng buộc C, thì các itemset có nhiều item hơn S nhƣng chứa S cũng thỏa.
Xem ví dụ sau cho thấy ràng buộc độ có ích có thể không hẳn là đơn điệu cũng không hẳn là không đơn điệu.
Ví dụ 2.4. Xét các itemset trong bảng 1.3. Gọi u(S) là lợi nhuận của một itemset S.
Ta có u(AD) = 135, u(ABD) = 106, và u(ACD) = 150. Do u(AD)> u(ABD) và u(AD) < u(ACD), lợi nhuận của một superset AD (một tập có nhiều item hơn AD mà có chứa AD) có thể thấp hơn hoặc cao hơn lợi nhuận của AD.
Ràng buộc khả chuyển theo thứ tự đảm bảo tập các itemset đóng giảm theo lưới của tất cả các itemset tiền tố của nó được định nghĩa theo thứ tự đó. Tuy nhiên, ràng buộc độ có ích có thể không nhất thiết phải khả chuyển. Ví dụ sau cho thấy ràng buộc độ có ích không khả chuyển theo thứ tự tăng hay giảm theo lợi nhuận của mỗi thành phần.
Ví dụ 2.5. Xét các itemset trong bảng 1.3. Gọi u(S) là lợi nhuận của một itemset S.
Trong bảng 1.3, u(A) = 110, u(B) = 200, u(C) = 190, và u(D) = 85. Thứ tự giảm của lợi nhuận là <B, C, A, D>. Các itemset B và BC là các itemset tiền tố của BCAD. Do u(B) = 200, u(BC) = 138, và u(BCAD) = 144, thì u(B) > u(BCAD) và u(BC) < u(BCAD), điều đó cho thấy lợi nhuận của các itemset tiền tố của BCAD có thể cao hơn hay thấp hơn lợi nhuận của BCAD. Tương tự như vậy thứ tự tăng của lợi nhuận là <D, A, C, B>. Các itemset DAC và DA là các itemset tiền tố của DACB. Do u(DAC)=150 và u(DA) = 135, thì u(DA) < u(DACB) và u(DAC) >
u(DACB), điều đó cho thấy lợi nhuận của các itemset tiền tố của DACB có thể cao hơn hay thấp hơn lợi nhuận của DACB. Do không phải thứ tự tăng cũng không phải thứ tự giảm có thể đảm bảo rằng lợi nhuận của itemset ABCD thì luôn luôn cao hơn (hay thấp hơn) lợi nhuận của bất kì itemset tiền tố nào. Ta có kết luận u(S) không khả chuyển với một thứ tự tăng hay giảm.
Do ràng buộc độ có ích có thể không khả chuyển, hai chiến lƣợc tỉa trên không thể dùng cho các ràng buộc độ có ích. Có vẻ khó để tìm một chiến lƣợc tỉa hiệu quả cho các ràng buộc độ có ích, chiến lƣợc tỉa mới sẽ đƣợc trình bày trong phần tiếp theo.