Mô hình mới trên cây nén cho khai phá tập mục lợi ích cao

Bài viết Mô hình mới trên cây nén cho khai phá tập mục lợi ích cao đề xuất mô hình CWU (Candidate Weight Utility) trên cây tiền tố nén mẫu lợi ích. Xây dựng thuật toán CTU-PRO+ dựa trên thuật toán CTU-PRO và sử dụng mô hình bài viết đề xuất CWU.
Nội dung trích xuất từ tài liệu:
Mô hình mới trên cây nén cho khai phá tập mục lợi ích cao Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 DOI: 10.15625/vap.2015.000170 MÔ HÌNH MỚI TRÊN CÂY NÉN CHO KHAI PHÁ TẬP MỤC LỢI ÍCH CAO Đậu Hải Phong1, Đoàn Văn Ban2, Đỗ Thị Mai Hường3 1 2 Khoa Toán và Tin học, Trường Đại học Thăng Long Phòng các hệ thống phần mềm tích hợp, Viện Công nghệ thông tin 3 Khoa Công nghệ thông tin, Học viện Kỹ thuật Quân sự phong4u@gmail.com, dvban@ioit.ac.vn, dohuong@gmail.com TÓM TẮT: Hiện nay, một trong những vấn đề được quan tâm trong khai phá dữ liệu là tìm kiếm tập lợi ích cao từ cơ sở dữ liệu lớn. Trong kỹ thuật tìm kiếm tập lợi ích cao thì cả giá trị lợi ích và số lượng khác nhau của từng phần tử trong giao dịch đều được xem xét. Một vấn đề khó khăn trong kỹ thuật này là số lượng các tập các ứng viên được sinh ra là rất lớn vì tập lợi ích cao không có tính chất đóng. Hầu hết các thuật toán khai phá tập lợi ích cao như: UP-Growth, Udepth, Two-Phase, PB, CTU-PRO,… đều sử dụng mô hình TWU (Transactions Weight Utility) để tỉa tập ứng viên. Trong bài báo này chúng tôi đề xuất mô hình CWU (Candidate Weight Utility) trên cây tiền tố nén mẫu lợi ích. Xây dựng thuật toán CTU-PRO+ dựa trên thuật toán CTU-PRO và sử dụng mô hình chúng tôi đề xuất CWU. Kết quả thử nghiệm thuật toán CTU-PRO+ cho thấy thời gian thực hiện với các thuật toán Two-Phase, CTU-PRO cho kết quả tốt hơn.. Từ khóa: Khai phá dữ liệu, tập lợi ích, tập phổ biến, CWU, TWU I. GIỚI THIỆU Khai phá tập phổ biến là nhiệm vụ quan trọng trong khai phá tri thức và có ứng dụng rộng rãi trong kinh doanh, khoa học và các lĩnh vực khác. Mục tiêu của khai phá tập phổ biến là tìm ra các phần tử cùng xuất hiện với một tần suất lớn hơn một ngưỡng tối thiểu cho trước trong cơ sở dữ liệu giao dịch. Tuy nhiên, khai phá tập phổ biến vẫn tồn tại một số hạn chế như: các phần tử trong giao dịch có sự quan trọng ngang nhau và không xem xét số lượng của nó hay trọng lượng liên quan như giá hoặc lợi nhuận. Vì vậy, mô hình khai phá tập phổ biến chỉ phản ánh mối tương quan giữa các phần tử, và nó không phản ánh ý nghĩa của các mặt hàng. Nhưng trong thực tế số lượng và trọng lượng của các phần tử là rất quan trọng như trong bài toán tối đa hóa lợi ích. Để khắc phục những hạn chế trong khai phá tập phổ biến thì một số mô hình khai thác tập lợi ích cao [1][2][3][4][5],… Trong mô hình này cho phép người sử dụng đánh giá được tầm quan trọng của một tập phổ biến bằng giá trị lợi ích. Một tập phần tử được gọi là tập lợi ích cao khi giá trị lợi ích của nó lớn hơn một ngưỡng do người dùng định nghĩa trước. Trong khai phá tập lợi ích cao thì các tập lợi ích không có tính chất đóng [6]. Tính chất này đảm bảo một tập là tập lợi ích thấp thì các tập chứa nó cũng là tập lợi ích thấp. Ví dụ, tập {AB} là tập lợi ích thấp thì tập {ABC} vẫn có thể là tập lợi ích cao. Điều này sẽ làm số lượng ứng cử viên được sinh ra rất lớn và tốn nhiều thời gian để kiểm tra các ứng viên. Trong một số thuật toán [1][3][4],... đều dựa trên hai bước là sinh ứng viên và kiểm tra ứng viên đó có khả năng sinh ra các tập lợi ích cao không với một số lần duyệt dữ liệu nhất định. Để tránh duyệt dữ liệu nhiều lần thì một số thuật toán dùng cấu trúc cây để tìm tập lợi ích cao như [9][10],... nhưng các thuật toán này tiêu tốn nhiều thời gian và không gian bộ nhớ để sinh ra các cây điều kiện của từng tiền tố. Năm 2005, Liu cùng nhóm tác giả đã đưa ra mô hình TWU[12] trong khai phá tập lợi ích cao để loại bớt tập ứng viên. Giá trị lợi ích của tất cả các phần tử trong giao dịch được tổng hợp như là lợi ích của giao dịch và lấy nó làm cận trên lợi ích của các tập phần tử trong giao dịch đó. Khi đó, lợi ích giao dịch có trọng số (viết tắt: TWU – Transactions Weight Utility) của một tập phần tử được định nghĩa là tổng các lợi ích của giao dịch có chứa tập đó. Trong thuật toán [12], Liu đã sử dụng mô hình TWU để loại đi các tập có TWU nhỏ hơn ngưỡng lợi ích tối thiểu cho trước để giảm số lượng tập ứng cử viên, sau đó duyệt lại cơ sở dữ liệu để xác định lợi ích thực tế của các tập và tiếp tục xác định khả năng các tập lớn hơn của nó có là tập lợi ích cao hay không để sinh tiếp các ứng cử viên. Trong các thuật toán sử dụng mô hình TWU, thuật toán [4][5][13],... thực hiện tìm kiếm tập ứng viên theo chiều sâu. Ví dụ, xét tập phần tử I={A, B, C, D, E}, từ phần 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 ứng viên {BC}, {BCD}, {BCDE},... Ta thấy, các tập ứng viên sinh ra từ phần tử B không còn xuất hiện phần tử A, nhưng khi lấy TWU làm cận trên thì vẫn còn giá trị lợi ích của phần tử A. Điều này làm tăng số lượng tập ứng viên và chi phí kiểm tra các tập ứng viên. 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 CTU-PRO+ khai phá tập lợi ích cao dựa trên mô hình CWU để giảm số lượng tập ứng viên và thời gian thực hiện. Nội dung tiếp theo của bài báo được tổ chức như sau. Phần II vấn đề liên quan đến khai phá tập lợi ích cao. Phần III đề xuất mô hình CWU. Phần IV thuật toán CTU-PRO+. Phần V, trình bày kết quả đạt được và so sánh với các thuật toán khác. Phần VI kết luận. 360 MÔ HÌNH MỚI TRÊN CÂY NÉN CHO KHAI PHÁ TẬP MỤC LỢI ÍCH CAO II. CÁC VẤN ĐỀ LIÊN QUAN Cho một cơ sở dữ liệu gồm các giao dịch Ti là D = {T1,T2,T3,…Tn}, các giao dịch được xác định duy nhất bởi Tid, I={i1,i2,i3,…in} là các phần tử (item) xuất hiện trong các giao dịch, X ⊆ I là tập các phần tử (itemsets). Một tập X được gọi là tập k-phần tử khi số lượng phần tử của X là k. Để thuận lợi trong giải thích các khái niệm, chúng tôi đưa ra một cơ sở dữ liệu giao dịch được biểu diễn dưới dạng bảng như Bảng 1. Bảng lợi ích ngoài của các phần tử được cho trong Bảng 2. Tid 1 2 3 4 5 6 7 8 9 10 Tổng Item Lợi ích Bảng 1. Cơ sở dữ liệu giao dịch minh họa Giao dịch TU A B C D E F 2 0 1 1 0 0 80 2 1 1 0 0 0 195 0 0 1 1 10 0 110 0 1 0 0 15 0 225 1 0 1 0 0 1 37 ...