Một mô hình hiệu quả khai phá tập mục lợi ích cao

Khai phá tập phổ biến từ cơ sở dữ liệu giao dịch là một trong các kỹ thuật khai phá dữ liệu và có rất nhiều ứng dụng trong kinh doanh, y tế, giáo dục,... Bài viết trình bày vấn đề liên quan đến khai phá tập lợi ích cao; Mô hình CWU; Đề xuất thuật toán khai phá tập lợi ích cao sử dụng mô hình CWU; Kết quả đạt được và so sánh với các thuật toán khác.
Nội dung trích xuất từ tài liệu:
Một mô hình hiệu quả khai phá tập mục lợi ích cao Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 13 (33), tháng 6/2015 Một mô hình hiệu quả khai phá tập mục lợi ích cao An Efficient Model for Mining High Utility Itemsets Đậu Hải Phong, Nguyễn Mạnh Hùng Abstract: Today, high utility itemsets mining is an lợi ích trong giao dịch và lợi ích ngoài của phần tử important research issue in data mining because it đó. Ví dụ, lợi ích trong từng giao dịch như số lượng considers the profit and quantity of items in each của mặt hàng trong mỗi lần mua hàng; lợi ích ngoài transaction. Most high utility itemsets algorithms such như giá trị lợi nhuận của từng mặt hàng đó đem lại. as UP-Growth [9], Udepth [5], Two-Phase [3], PB Một tập có lợi ích cao khi giá trị lợi ích của nó không (Projection-Based) [8], ect. use TWU model nhỏ hơn một ngưỡng lợi ích tối thiểu cho trước. (Transaction Weight Utility) for pruning candidates. Một vấn đề khó khăn trong khai phá tập lợi ích cao However, the number of candidate itemsets generated là các tập lợi ích không có tính chất đóng [2]. Tính in these algorithms is enormous. In this paper, we chất này đảm bảo một tập là tập lợi ích cao thì các tập propose a new candidate weight utility model (CWU) con của nó cũng là tập lợi ích cao. Do vậy, số lượng and HP (High Projection) algorithm base on CWU to các ứng cử viên được sinh ra rất lớn và chi phí lớn về reduce the number of candidate itemsets. The thời gian duyệt dữ liệu nhiều lần để kiểm tra các ứng experimental results show that the performance and viên như trong một số thuật toán [3-5]. Để tránh duyệt number candidate of our algorithm is better than Two- dữ liệu nhiều lần thì một số thuật toán dùng cấu trúc Phase [3], PB [8]. cây để tìm tập lợi ích cao như [6,9,10]. Nhưng các Keywords: Data Mining, Frequent Itemsets, High thuật toán này tiêu tốn nhiều thời gian và không gian Utility, Candidate Weight Utility, HP algorithm. bộ nhớ để sinh ra các cây điều kiện của từng tiền tố. Trong [7] Liu đã trình bày mô hình TWU khai phá I. GIỚI THIỆU tập lợi ích cao để loại bớt tập ứng viên. Giá trị lợi ích Khai phá tập phổ biến từ cơ sở dữ liệu giao dịch là của tất cả các phần tử trong giao dịch được tổng hợp một trong các kỹ thuật khai phá dữ liệu và có rất như là lợi ích của giao dịch và lấy nó làm cận trên lợi nhiều ứng dụng trong kinh doanh, y tế, giáo dục,... ích của các tập phần tử trong giao dịch đó. Khi đó, lợi Mục tiêu của khai phá tập phổ biến là tìm ra các tập ích giao dịch có trọng số (viết tắt: TWU – phần tử có tần suất xuất hiện lớn hơn một ngưỡng hỗ Transactions Weight Utility) của một tập phần tử được trợ tối thiểu cho trước. Từ tập phổ biến sinh ra các định nghĩa là tổng các lợi ích của giao dịch có chứa luật dựa trên độ tin cậy tối thiểu. Trong bài toán khai tập đó. Trong thuật toán [7], Liu đã sử dụng mô hình phá tập phổ biến cơ bản thì mọi phần tử là tương TWU để loại đi các tập có TWU nhỏ hơn ngưỡng lợi đương nhau và chỉ quan tâm đến tần suất xuất hiện ích tối thiểu cho trước để giảm số lượng tập ứng cử của phần tử trong các giao dịch. Tuy nhiên, trong viên, sau đó duyệt lại cơ sở dữ liệu để xác định lợi ích thực tế, các phần tử trong cơ sở dữ liệu giao dịch thực tế của các tập và tiếp tục xác định khả năng các thường có các thuộc tính định lượng như: số lượng, tập lớn hơn của nó có là tập lợi ích cao hay không để lợi ích... Năm 2003, Chan [1] đã đưa ra khái niệm lợi sinh tiếp các ứng cử viên. ích của tập phần tử để khắc phục những nhược điểm Trong các thuật toán sử dụng mô hình TWU, thuật của tập phần tử phổ biến cơ bản. Lợi ích của một toán [5,8] thực hiện tìm kiếm tập ứng viên theo chiều phần tử trong một giao dịch được tính toán dựa trên sâu. Ví dụ, xét tập phần tử I={A, B, C, D, E}, từ phần - 26 - Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 13 (33), tháng 6/2015 tử A có thể sinh ra các tập ứng viên {AB}, {ABC}, {ABCD}, {ABCDE},...; từ phần tử B sinh ra các tập Bảng 2. Bảng lợi ích của các phần tử ứng viên {BC}, {BCD}, {BCDE},... Ta thấy, các tập Item A B C D E F ứng viên sinh ra từ phần tử B không còn xuất hiện Lợi ích 3 10 1 6 5 2 phần tử A, nhưng khi lấy TWU làm cận trên thì vẫn có giá trị lợi ích của phần tử A. Điều này làm tăng số Định nghĩa 1 [8] - Lợi ích trong (internal utility) lượng tập ứng viên và chi phí kiểm tra các tập ứng của mỗi phần tử là giá trị của mỗi phần tử trong từng viên. giao dịch. Ký hiệu: O(ik,Tj) – là lợi ích trong của phần tử ik trong giao dịch Tj. Trong bài báo này, chúng tôi đề xuất mô hình CWU (Candidate Weight Utility) và thuật toán khai Ví dụ, O(A,T1) = 1; O(C,T1) = 2 trong Bảng 1. phá tập lợi ích cao dựa trên mô ...