Khai thác top-rank-k tập được đánh trọng số

Trong bài báo này, chúng tôi đề xuất giải thuật WIT-TOP-K dựa trên cấu trúc cây WIT-tree để khai thác Top-rank-k của các tập được đánh trọng số dựa trên cơ sở giao dịch có trọng số. Kết quả thực nghiệm cho thấy thuật toán đề xuất thực hiện khá nhanh và chính xác đối với các cơ sở dữ liệu có kích thước vừa phải với mức ngưỡng thích hợp.
Nội dung trích xuất từ tài liệu:
Khai thác top-rank-k tập được đánh trọng sốKHOA HỌC CÔNG NGHỆKHAI THÁC TOP-RANK-K TẬP ĐƯỢC ĐÁNH TRỌNG SỐNguyễn Thành NgôTrường Đại học Công nghiệp Thực phẩm Tp Hồ Chí MinhNgày gửi bài: 08/4/2016Ngày chấp nhận đăng: 06/6/2016TÓM TẮTTrong bài báo này, chúng tôi đề xuất giải thuật WIT-TOP-K dựa trên cấu trúc cây WIT-tree để khai thácTop-rank-k của các tập được đánh trọng số dựa trên cơ sở giao dịch có trọng số. Kết quả thực nghiệm cho thấythuật toán đề xuất thực hiện khá nhanh và chính xác đối với các cơ sở dữ liệu có kích thước vừa phải với mứcngưỡng thích hợp.Từ khóa: Top-rank-k mining, luật kết hợp, tập phổ biến, khai thác tập có trọng sốAN EFFICIENT ALGORITHM FOR MINING WEIGHTED ITEMSET TOP-RANK-KABSTRACTIn this paper, we propose an efficient algorithm, called WIT-TOP-K, based on the WIT-tree datastructure to mine the weighted itemset Top-rank-k in weighted transaction database. The experiment resultsshow that the proposed algorithm performs quickly and accurately with respect to the moderate-sized databaseswith a appropriate thresholds.Key words: Top-rank-k mining, association rules, frequent itemset, frequent patterns, weighted itemsets1. GIỚI THIỆUKhai thác dữ liệu được dùng để mô tả quá trình tìm kiếm, chắc lọc và khai phá tri thứctrong cơ sở dữ liệu. Quá trình này bao gồm tập hợp nhiều kỹ thuật được sử dụng trong tiếntrình phát hiện tri thức và tìm ra được mối quan hệ giữa các mẫu trong cơ sở dữ liệu(transaction database).Khai thác luật kết hợp là một phần quan trọng trong quá trình khám phá tri thức trongdữ liệu (KDD) [2]. Khai thác luật kết hợp được sử dụng để xác định mối quan hệ giữa các sảnphẩm trong cơ sở dữ liệu giao dịch và điều này dẫn đến việc nó chỉ quan tâm đến việc kháchhàng có mua hay không mua sản phẩm nào đó. Thực tế, mỗi một sản phẩm có thể có giá trịkhác nhau. Tương tự mỗi item trong cơ sở dữ liệu giao dịch cũng có trọng số khác nhau tùythuộc từng cơ sở dữ liệu cụ thể. Vì vậy, việc khai thác trên loại dữ liệu này mang tính thựctiễn cao.Năm 1998, Ramkumar, Ranka và Tsur [4] cũng như Cai, Fu, Cheng và Kwong [3] đãđề xuất một mô hình để mô tả các khái niệm về việc khai thác luật kết hợp có trọng số và dựatrên giải thuật Apriori để tìm ra các tập phổ biến được đánh trọng số. Từ đó nhiều kỹ thuậtkhai thác luật kết hợp có trọng số được đề xuất như: Wang, Yang, Yu [6] và Tao, Murtagh,và Farid [5].Giải thuật khai thác Top-rank-k bằng Node-list tiến hành khai thác Top-rank-k của cáctập phổ biến chỉ dựa trên cơ sở dữ liệu nhị phân chưa tiến hành trên cơ sở dữ liệu nhị phân cótrọng số, và với việc dựa trên cấu trúc cây FP cho nên khiến cho việc tìm kiếm các tập phổbiến phải quét cơ sở dữ liệu đến 2 lần.Trong bài báo này chúng tôi trình bày về thuật toán khai thác Top-rank-k dựa trên thuậttoán WIT-FWI. Thuật toán WIT-FWI dựa trên phần giao giữa các Tidset để tính nhanh cáctrọng số hỗ trợ và để sinh ra các ứng viên từ các lớp tương đương cho trước. Các tập phổ biếncó trọng số hỗ trợ thỏa điều kiện trọng số hỗ trợ tối thiểu sẽ được giữ lại, các tập không thỏaTẠP CHÍ KHOA HỌC CÔNG NGHỆ & THỰC PHẨM SỐ 09/201660KHOA HỌC CÔNG NGHỆsẽ bị xóa bỏ khỏi cây. Thuật toán WIT-TOP-K cũng được dựa trên giải thuật WIT-FWI đểtính nhanh các các trọng số hỗ trợ, các tập được đánh trọng số có kích thước là 1 mà trọng sốhỗ trợ của nó thỏa điều kiện ngưỡng Top-rank-k cho trước sẽ được đưa vào bảng gọi là Tabk.Từ các tập được tìm thấy trong bảng Tabk, sẽ phát sinh ra các ứng viên mới dựa theo các lớptương đương, và sử dụng định lý 2.1 để loại bỏ các tập không thỏa điều kiện ngưỡng k.2. MỘT SỐ ĐỊNH NGHĨA VÀ KHÁI NIỆM CƠ BẢNĐịnh nghĩa 2.1. Cơ sở dữ liệu giao dịch của tập được đánh trọng số (D) bao gồm: mộttập hợp các giao dịch T = {t1,t2,….,tm} ; một tập các item I = {i1,i2,…,in} và một tập hợp cáctrọng số W = {w1,w2,…,wn} tương ứng với mỗi một item có trong I.Bảng 2.1: Trọng số của các itemItemABCDEWeight35135Định nghĩa 2.2. Trọng số giao dịch của một giao dịch tk được gọi là tw và được nghĩanhư sau: ...