CƠ SỞ LÝ THUYẾT
2.3. Khuôn mẫu chung để khai thác itemset có ích
Suốt quá trình khám phá tri thức, các phép đo dựa trên độ có ích có thể dùng theo 3 cách, còn gọi là các vai trò của các phép đo dựa trên độ có ích. Hình 2.1 cho thấy 3 vai trò này. Đầu tiên, các phép đo đƣợc dùng để tỉa các mẫu không quan tâm trong quá trình khai thác dữ liệu để thu hẹp không gian xử lý nhằm cải tiến hiệu quả khai thác. Ví dụ, ngƣỡng của độ hỗ trợ có thể đƣợc dùng để lọc ra các mẫu có độ hỗ trợ thấp trong quá trình khai thác dữ liệu và cải tiến tính hiệu quả. Tương tự nhƣ vậy, ngƣỡng độ có ích có thể đƣợc định nghĩa và đƣợc dùng để tỉa các mẫu có các giá trị có ích thấp. Thứ hai là, các phép đo đƣợc dùng để xếp hạng các mẫu theo thứ tự mức độ quan tâm của chúng. Thứ 3 là, các phép đo đƣợc dùng trong suốt quá trình hậu xử lí để chọn ra các mẫu đáng quan tâm. Ví dụ, sau khi khai thác dữ liệu, chúng ta có thể dùng phép thử chi-square để chọn ra các luật có các tương quan quan trọng. Cách thứ hai và thứ ba cũng có thể kết hợp bằng cách lọc trước các mẫu và xếp hạng chúng. Đối với cách hai và ba, các phép đo dựa trên độ có ích không cần kết hợp với thuật toán khai thác dữ liệu. Luận văn tập trung vào phương pháp đầu tiên do nó có thể cải tiến hiệu quả khai thác bằng cách giảm chi phí không gian và thời gian của thuật toán khai thác.
Nhƣ đã biết, u(S) đóng vai trò chính trong việc xác định các vấn đề khai thác dữ liệu dựa trên độ có ích. Các phép đo độ có ích khác nhau dùng các công thức khác nhau đối với u(S).
Khảo sát cách định nghĩa u(S) theo hàm tính độ có ích do người dùng định nghĩa f. Trong ví dụ 1.1, lợi ích của một itemset phản ánh mục tiêu nhà quản lí cửa hàng trong việc khám phá các itemset sinh ra lợi nhuận đáng kể (ví dụ, minutil = 150). Người dùng cho rằng BD là hữu dụng, do lợi nhuận của itemset BD lớn hơn minutil. Ta quan sát thấy ngữ nghĩa lợi nhuận đƣợc phản ánh bởi hàm f(x,y), với x là số lƣợng bán của một item và y là lợi nhuận đơn vị của item. Độ có ích của một itemset đƣợc định lƣợng bằng tích của x và y, nghĩa là, f(x,y) x.y. Giá trị của x nhận được từ tập dữ liệu giao tác và chỉ tùy thuộc vào tập dữ liệu ẩn bên dưới.
Ngược lại, giá trị y thường không có sẵn trong tập dữ liệu giao tác mà chỉ tùy thuộc
vào người dùng quan tâm đến mẫu đó. Vì vậy, trong trường hợp này, tầm quan trọng của một item đƣợc đo theo hai phần. Một là tầm quan trọng thống kê của một item đƣợc đo theo tham số x, đây là tham số khách quan độc lập với ứng dụng. Phần còn lại là tầm quan trọng ngữ nghĩa của item đƣợc đo theo tham số y, đây là tham số chủ quan tùy thuộc vào ứng dụng và người dùng. Kết quả là, f(x,y) kết hợp phép đo khách quan và chủ quan của một item với nhau. Sự kết hợp này cho thấy tầm quan trọng của itemset đó đối với ứng dụng, 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 một itemset.
Bảng 2.4: Các phép đo độ quan tâm dựa trên độ có ích
Các phép đo Các mô hình dữ liệu
Độ hỗ trợ có trọng số Trọng số cho item Độ hỗ trợ có trọng số chuẩn Trọng số cho item Độ hỗ trợ có trọng số ngang Trọng số cho giao tác
Độ hỗ trợ có trọng số hỗn hợp Trọng số cho cả item và giao tác Các thuộc tính hướng mục tiêu và
không mục tiêu
Trọng số trên giao tác cho các thuộc tính hướng mục tiêu
Độ hỗ trợ đếm Trọng số cho item và ô trong tập dự liệu Độ hỗ trợ khối lƣợng Trọng số cho item và ô trong tập dự liệu Yao et al Trọng số cho item và ô trong tập dự liệu
Luận văn giới hạn các miền biến thiên giá trị khách quan là các giá trị số, bởi vì, thông tin độ có ích giao tác có thể đƣợc diễn tả theo hình thức này.
Hình 2.1: Vai trò của các phép đo dựa trên độ có ích.
Dữ liệu Khai thác dữ liệu
Các phép đo độ quan tâm
Các mẫu đã khaithác
Xếp hạng
Lọc
Các mẫu cuối cùng
Giá trị chủ quan có liên quan đến một giá trị đặc biệt trong lĩnh vực mô tả sự quan tâm của người dùng. Trong thực tế, giá trị của yp do người dùng gán theo sự diển dịch của anh ta theo tri thức chuyên biệt của lĩnh vực đó đƣợc đo bằng các yếu tố độ có ích nào đó, nhƣ là chi phí, lợi nhuận, hoặc giá trị thẩm mỹ. Ví dụ, cho i1 = A, i2 = B. Sử dụng bảng 1.2 ta có, y1 = 5 và y2 = 100. Bất đẳng thức y2>y1 cho thấy người quản lí cửa hàng thích món hàng B hơn món hàng A, do mỗi món hàng B kiếm nhiều lợi nhuận hơn món hàng A.
Có đƣợc giá trị khách quan xpq từ một tập dữ liệu giao tác và giá trị chủ quan yp từ người dùng, một hàm tính độ có ích diễn tả tầm quan trọng của một itemset có thể đƣợc định nghĩa nhƣ một hàm hai chiều f(x,y).
Hàm tính độ có ích f(x,y) là một hàm tính độ có ích thống nhất. Cho c là hằng số. Bảng 2.4 tóm tắt tầm quan trọng ngữ nghĩa của hàm tính độ có ích thống nhất này ở mức item, mức giao tác, và mức ô. Bảng 3.5 cho thấy làm thế nào sử dụng hàm tính độ có ích thống nhất để diễn tả tất cả các phép đo dựa trên độ có ích đã có.
Với khuôn mẫu chung để định nghĩa f(x,y), ta thu đƣợc nhiều phép đo dựa trên độ có ích đã có.
Bảng 2.5: Tầm quan trọng ngữ nghĩa của hàm tính độ có ích
Ngữ nghĩa Hàm có ích f(xpq,yp) Giá trị có ích u(S) Không có ipS f(xpq,yp )1 u(S)s(S)
Ngữ nghĩa trên item tqTS f(xpq,yp )s(S) u(S)ipS f(ip)s(S) Ngữ nghĩa trên transaction ipS f(xpq,yp)c u(S)ctqTS f(tq )
Ngữ nghĩa trên ô ipStqTS f(xpq,yp )0 u(S)ipStqTS f(xpq,yp )
Bảng 2.6: Các phép đo độ quan tâm dựa trên độ có ích
Các phép đo Hàm có ích thống nhất f(xpq,yp ) Độ hỗ trợ ipS f(xpq,yp )1
Độ hỗ trợ có trọng số ipS f(xpq,yp )wp
Độ hỗ trợ có trọng số chuẩn ipS f(xpq,yp )wp /S Độ hỗ trợ có trọng số ngang tqTS f(xpq,yp )wq /c Độ hỗ trợ có trọng số hổn hợp f(xpq,yp )wp wq /c Các thuộc tính mục tiêu và không mục tiêu ipS f(xpq,yp)uq(S) Độ hỗ trợ đếm f(xpq,yp )w(ip,tq )/c
Độ hỗ trợ khối lƣợng f(xpq,yp ) w(ip,tq )w(ip )/c Yao et al f(xpq,yp )w(ip,tq )w(ip)
Xét đến các tính chất toán học của các phép đo dựa trên độ có ích đã thảo luận ở trên. Hướng tiếp cận item có trọng số (WI) và hướng tiếp cận khai thác có thêm giá trị (VAM) phản ánh tầm quan trọng ngữ nghĩa của các itemset ở mức item bằng cách định nghĩa các trọng số khác nhau trên các item. Do luôn luôn có thứ tự giảm dựa trên trọng số của tất cả các item, một hàm đơn điệu tiền tố có thể đƣợc định nghĩa ipS f(ip )đối với itemset S liên quan đến thứ tự giảm của các trọng số của các item, với f(ip) là trọng số của item ip. Hướng tiếp cận độ hỗ trợ có trọng số dọc và hướng tiếp cận OOA cho thấy tầm quan trọng ngữ nghĩa của các itemset ở mức giao tác. Do luôn luôn có một thứ tự giảm dựa trên các trọng số của tất cả các giao tác, một hàm đơn điệu tiền tố đƣợc định nghĩa tqTS f(tq)đối với itemset S liên quan đến thứ tự giảm trên các trọng số của các giao tác, với f(tq) là trọng số của giao tác tq. Vì vậy, hàm tính độ có ích của phép đo WI, VAM, VWS, và phép đo OOA thỏa tính khả chuyển. Hướng tiếp cận độ hỗ trợ có trọng số hổn hợp, và hướng tiếp cận chia sẻ itemset cho thấy tầm quan trọng ngữ nghĩa của các itemset ở mức ô. Do 3 hướng tiếp cận này dùng hàm tính độ có ích không âm, theo định lý 2.2 tính chất cận trên độ có ích, hàm tính độ có ích của của các phép đo độ hỗ trợ có trọng số hổn hợp, các phép đo chia sẻ itemset thỏa tính chất biên trên. Bảng 2.7 tóm tắt các tính chất toán học của các phép đo dựa trên độ có ích nói trên.
Bảng 2.7: Các tính chất toán học của các phép đo dựa trên độ có ích.
Các phép đo độ có ích Tính chất toán học
Độ hỗ trợ Phản đơn điệu
Độ hỗ trợ có trọng số Khả chuyển
Độ hỗ trợ có trọng số chuẩn Khả chuyển Độ hỗ trợ có trọng số ngang Khả chuyển Độ hỗ trợ có trọng số hổn hợp Chặn trên Các thuộc tính mục tiêu và không mục tiêu Khả chuyển
Độ hỗ trợ đếm Chặn trên
Độ hỗ trợ khối lƣợng Chặn trên
Yao et al Chặn trên
Đối với biểu thức (2.1) và (2.2), một hàm đơn điệu tiền tố có thể đƣợc định nghĩa theo thứ tự giảm dần các trọng số của các item. Theo định lí 2.1, chúng thỏa tính khả chuyển. Tương tự, đối với biểu thức (2.3) và (2.8), một hàm đơn điệu tiền tố có thể đƣợc định nghĩa theo thứ tự giảm dần các trọng số của các giao tác. Theo định lí 2.1, chúng cũng thỏa tính khả chuyển. Bây giờ ta chứng minh biểu thức (2.4), (2.5), (2.6), và (2.7) thỏa tính chất chặn trên. Đối với biểu thức (2.4), wp>0.
Đối với biểu thức (2.5), (2.6), và (2.7), w(ip,tq)>0 và w(ip)>0. Vì vậy, biểu thức (2.4), (2.5), (2.6), và (2.7) là các hàm không âm. Theo định lí 2.2, chúng thỏa tính chất biên trên.
Từ đó cho thấy ta có thể thiết kế một chiến lƣợc tỉa hiệu quả dành cho các phép đo độ có ích này bằng cách dùng các tính chất toán học đƣợc xác định. Ngƣợc lại, có thể kết hợp các tính chất này vào trong các thuật toán đƣợc sử dụng cho các phép đo độ có ích này.
CHƯƠNG 3