Trong khai thác tập phổ biến người dùng chỉ khai thác các itemset có tần suất cao. Tuy nhiên trong thực tế còn một số tập quan trọng chƣa đƣợc khám phá là do hạn chế của tập phổ biến. Tập phổ biến chỉ phản ánh tương quan về mặt thống kê nhƣng không phản ánh đƣợc tầm quan trọng về mặt ngữ nghĩa giữa các item. Luận văn đề cập cách khai thác các itemset dựa trên độ có ích để tránh hạn chế trên. Cách này cho phép người dùng định lượng mức độ quan tâm của mình khi xác định độ có ích của các item. Khi độ có ích của các itemset thỏa ràng buộc độ có ích cho trước nào đó có nghĩa là các itemset đang đƣợc quan tâm. Các chiến lƣợc tỉa dùng trong các hướng khai thác các itemset trước đây không dùng được trong ràng buộc độ có ích. Cần có thuật toán chiến lƣợc tỉa mới để khai thác các itemset dựa trên độ có ích bằng cách kết hợp với các chiến lƣợc tỉa đã có.
Mục đích khai thác tập phổ biến là tìm ra tất cả tập phổ biến, các itemset phải có ít nhất độ hỗ trợ tối thiểu nhất định, đó là phần trăm các giao tác chứa itemset.
Khi sử dụng độ hỗ trợ thì chỉ có những itemset tần suất cao mới hấp dẩn được người dùng.
Tập phổ biến xuất hiện hạn chế khi khai thác đến tầm quan trọng của các itemset. Đó là khi độ hỗ trợ tối thiểu thấp thì rất nhiều tập phổ biến mà người dùng không quan tâm vẩn đƣợc sinh ra. Ví dụ, hàng ngàn sản phẩm kết hợp với nhau chỉ xuất hiện trong 1% giao tác. Nếu quá nhiều tập phổ biến đáng ra không cần quan tâm lại được tìm thấy, người sử dụng buộc phải thực hiện thao tác khác để chọn những itemset thực sự quan tâm. Hạn chế thứ hai là độ hỗ trợ dựa trên tần suất itemset không là độ đo tương xứng cho sự quan tâm của người dùng nào đó. Giả sử mục tiêu của người trưởng nhóm bán hàng là tìm ra các itemset có thể sinh ra lợi nhuận cao hơn ngƣỡng. Ví dụ sau minh họa khai thác các itemset dựa trên độ hỗ trợ có thể dẫn đến một số itemset có khả năng lợi nhuận cao nhất sẽ không đƣợc tìm thấy do có độ hỗ trợ thấp.
Bảng 1.1: Cơ sở dữ liệu giao tác
Mã giao tác Item A Item B Item C Item D
t1 4 0 1 0
t2 2 0 0 6
t3 0 0 1 30
t4 3 0 0 5
t5 1 0 0 6
t6 4 0 2 10
t7 2 0 0 8
t8 1 1 1 1
t9 0 1 0 10
t10 5 0 0 9
Bảng 1.2: Lợi nhuận đơn vị cho các item Tên Item Lợi nhuận
Item A 5
Item B 100
Item C 38
Item D 1
Bảng 1.3: Độ hỗ trợ và lợi nhuận cho các item
Các itemset Độ hỗ trợ Lợi nhuận
A 80 110
B 20 200
C 40 190
D 90 85
AB 10 105
AC 30 197
AD 70 135
BC 10 138
BD 20 211
CD 30 193
ABC 10 143
ABD 10 106
ACD 20 150
BCD 10 139
ABCD 10 144
Ví dụ 1.1: Xét CSDL giao tác minh họa trong bảng 1.1 và lợi nhuận của từng item minh họa trong bảng 1.2. Mỗi giá trị trong CSDL giao tác biểu thị số lƣợng bán của một item. Qua bảng 1.1 và 1.2, độ hỗ trợ và lợi nhuận cho toàn bộ các itemset có thể
đƣợc tính nhƣ trong bảng 1.3. Trong 10 giao dịch ở bảng 1.1 chỉ có hai giao dịch 8 và 9, bao gồm cả thành phần B và D, độ hỗ trợ của itemset BD là 2 10 20%. Do t8
gồm 1B và 1D, t9 gồm 1D và 10D, tổng cộng có 2B và 11D xuất hiện trong các giao dịch có chứa itemset BD. Qua bảng 1.2, lợi nhuận cho mỗi item B là 100 và mỗi item D là 1. Vì vậy lợi nhuận của các itemset BD đƣợc tính là 2 100 + 11 1 211.
Lợi nhuận của các itemset khác trong bảng 1.3 được tính tương tự như vậy. Giả sử độ hỗ trợ tối thiểu là 40%, các tập phổ biến trong bảng 1.3 là D, A, DA và C nhƣng 4 itemset có khả năng lợi nhuận nhất là BD, B, AC và CD, tất cả là các tập không phổ biến.
1.3.2. Vấn đề cần giải quyết
Ở ví dụ 1.1 cho thấy hướng khai thác tập phổ biến này không thoả mục tiêu của người trưởng nhóm bán hàng. Trong trường hợp này độ hỗ trợ chỉ phản ánh sự tương quan về mặt thống kê của các item, chứ không phản ánh được tầm quan trọng ngữ nghĩa của chúng. Mặt khác, tương quan thống kê không thể xác định một itemset có ích như thế nào ứng với sự quan tâm người dùng (lợi nhuận). Trong ví dụ này, lợi nhuận của itemset không chỉ phụ thuộc vào độ hỗ trợ của itemset, mà còn phụ thuộc vào giá của các item trong itemset đó.
Do vậy nên cần phải phát triển hướng khai thác itemset dựa trên độ có ích, hướng này cho phép người dùng diển tả các giá trị có ích và tìm ra các itemset có giá trị có ích cao hơn ngƣỡng. Khi khai thác các itemset dựa trên độ có ích, độ có ích định lượng sự quan tâm người dùng, và tính hữu dụng của các itemset được định lượng dưới dạng giá trị độ có ích của chúng. Đúng ra một itemset S hữu dụng với người dùng nếu thoả có ích, đó là ràng buộc theo hình thức u(S) minutil với u(S) là giá trị độ có ích của itemset S, minutil là ngưỡng do người dùng định nghĩa. Trong thực tế giá trị độ có ích của một itemset có thể tính dưới dạng chi phí, lợi nhuận, và giá trị thẩm mỹ, hay những cách tính khác tùy theo sự quan tâm của người dùng. Đối với ví dụ 1.1 thì các giá trị độ có ích của các itemset có thể đƣợc thể hiện theo lợi nhuận và đƣợc minh họa trong bảng 1.3. Ví dụ giá trị có ích u(ABCD) 144 cho thấy siêu thị lời 144 khi bán các item A, B, C, D với nhau.
Giả sử n có ích là u(S) 140, có nghĩa là chỉ có các itemset lãi ít nhất 140 thì mới có ý nghĩa với người quản lý siêu thị. Itemset ABCD được quan tâm, vì thoả u(ABCD) 140. Ràng buộc độ có ích đo tầm quan trọng itemset theo hai cách.
Một là của một itemset đƣợc tính bằng độ hỗ trợ; cách còn lại là của một itemset được đo bởi người dùng. Sự kết hợp này cho ra tầm quan trọng của một itemset trong ứng dụng định sẵn, và không chỉ phản ánh tầm quan trọng về mặt thống kê mà còn tầm quan trọng về mặt ngữ nghĩa của các itemset.
Khai thác các itemset dựa trên ràng buộc rất quan trọng, ở đó người dùng đƣợc phép xác định mục tiêu theo ý nghĩa của các ràng buộc để cho ra tầm quan trọng ngữ nghĩa của một itemset trong ứng dụng định sẵn. Nhiều ngữ nghĩa khác nhau, ví dụ nhƣ tầm quan trọng của các item, hoặc tầm quan trọng của các giao tác, đƣợc mô tả theo ràng buộc. Tuy nhiên, các ràng buộc dùng trong các kiểu nhƣ vậy gọi là khả chuyển. Một ràng buộc n khi có một itemset vi phạm một thuộc tính, thì các itemset tiền tố theo thứ tự xác định của các item trong itemset đó cũng vậy.
Trong các nghiên cứu trước đó về các ràng buộc khả chuyển cho thấy nhiều khía cạnh hữu dụng về tầm quan trọng ngữ nghĩa của các itemset trong các ứng dụng đã có, các ràng buộc tự nhiên khác có thể không khả chuyển thì cũng hữu dụng cho việc diễn tả khía cạnh phức tạp hơn về tầm quan trọng ngữ nghĩa. Do tính hiệu quả của các phương pháp sẵn có trong việc khai thác tập phổ biến và khai thác các itemset dựa trên ràng buộc khả chuyển, nên cần phải nghiên cứu tỉ mỉ để tìm ra chiến lƣợc tỉa cành nào của chúng vì đa số có thể ứng dụng đƣợc cho ràng buộc độ có ích. Tuy nhiên cũng khó thực hiện, vì một itemset có càng nhiều item, càng ít giao tác liên quan đến đến itemset đó. Do đó các ràng buộc độ có ích không thể khả chuyển. Nên cần phải phát triển các chiến lƣợc tỉa cành hiệu quả cho các ràng buộc độ có ích.
Luận văn đề cập các thuật toán hiệu quả để quản lý các ràng buộc độ có ích, một loại ràng buộc không khả chuyển có thể diển tả các mức độ quan trọng ngữ
nghĩa mà không bị các lý thuyết đã có và các kỹ thuật trong khai thác các itemset ràng buộc. Chính xác là đưa ra một hướng khai thác các itemset dựa trên độ có ích, cho phép người dùng diễn tả sự quan tâm của họ đối với một itemset thông qua í có ích, một hàm liên quan đến các giá trị cụ thể trong một miền mà người dùng quan tâm. Kết hợp hàm tính độ có ích với cơ sở dữ liệu nào đó, các itemset tìm đƣợc chứa 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. Khái niệm m n n là các itemset được tìm thấy có giá trị độ có ích thoả ràng buộc độ có ích. Kết quả là, hướng khai thác các itemset dựa trên độ có ích có thể tìm ra một nhóm các itemset mà không do các kỹ thuật khai thác tập phổ biến cũng không do kỹ thuật khai thác dựa trên ràng buộc khả chuyển đã tồn tại có thể tìm thấy.
Hướng khai thác các itemset dựa trên độ có ích cho việc tìm kiếm các itemset quan trọng trong nhiều ứng dụng, bao gồm khai thác web và tìm kiếm thông tin (IR). Ví dụ bảng 1.1 có thể đƣợc quan tâm khi mô tả tập các trang web để khai thác web, mỗi cột biểu diển một từ khoá, mỗi hàng biểu diển một trang web, và giá trị trên mỗi ô biểu thị số lần xuất hiện từ khoá trên trang đó. Bảng 1.1 đƣợc xem nhƣ tập các tài liệu đã đƣợc sử dụng trong việc tìm kiếm thông tin, mà ở đó mỗi cột biểu diển một từ, mỗi hàng biểu diễn một tài liệu, và giá trị trong mỗi ô biểu thị tần suất một từ xuất hiện trong tài liệu. Bảng 1.2 có thể đƣợc xem nhƣ sự quan tâm của người sử dụng giữa các từ hay các từ khoá. Dùng thuật toán UMining đã được đề nghị, trang web hay tài liệu ứng với sự quan tâm của người sử dụng có thể được tìm ra. Nói chung, khai thác các itemset dựa trên độ có ích cho ta một khuôn mẫu tổng quát để khai thác các itemset có trọng số, mà ở đó giá trị độ có ích của mỗi item trong một itemset biểu thị trọng số.