Thuật toán hiệu quả khai thác tập tương quan hiếm có trọng số kết hợp độ đo ALL-CONFIDENCE

Bài viết đề xuất một cách tiếp cận khai thác tập tương quan hiếm có trọng số theo hướng tiếp cận không thỏa tính chất bao đóng giảm và đồng thời thỏa ràng buộc phản đơn điệu của độ đo tương quan all-confidence.
Nội dung trích xuất từ tài liệu:
Thuật toán hiệu quả khai thác tập tương quan hiếm có trọng số kết hợp độ đo ALL-CONFIDENCE Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Huế, ngày 07-08/6/2019 DOI: 10.15625/vap.2019.00058 THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP TƯƠNG QUAN HIẾM CÓ TRỌNG SỐ KẾT HỢP ĐỘ ĐO ALL-CONFIDENCE Phan Thành Huấn1,2, Lê Hoài Bắc3 1 Khoa Toán - Tin học, Trƣờng Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh 2 Bộ môn Tin học, Trƣờng Đại học Khoa học Xã hội và Nhân văn, Đại học Quốc gia Tp. Hồ Chí Minh 3 Khoa Công nghệ thông tin, Trƣờng Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh huanphan@hcmussh.edu.vn, lhbac@fithcmus.edu.vn TÓM TẮT: Khai thác tập hiếm là một kỹ thuật khai thác rất quan trọng cùng với các ứng dụng tiềm năng như phát hiện các cuộc tấn công máy tính, giao dịch gian lận trong các tổ chức tài chính, tin sinh học, y tế. Trong khai thác dữ liệu truyền thống trên dữ liệu giao dịch thì các item không có trọng số (như nhau). Tuy nhiên, trong một số ứng dụng thực tế thì mỗi item có trọng số khác nhau (thể hiện mức độ quan trọng hay ý nghĩa của từng item) - cần khai thác các tập phổ biến/ hiếm có trọng số của item. Trong bài viết này, chúng tôi đề xuất một cách tiếp cận khai thác tập tương quan hiếm có trọng số theo hướng tiếp cận không thỏa tính chất bao đóng giảm và đồng thời thỏa ràng buộc phản đơn điệu của độ đo tương quan all-confidence. Thuật toán chúng tôi đề xuất được gọi là ALLCONF-CORSI. Chúng tôi tiến hành thực nghiệm thuật toán trên bộ dữ liệu thực của UCI và bộ dữ liệu giả lập của trung tâm nghiên cứu IBM Almaden, cho thấy thuật toán đề xuất hiệu quả. Từ khóa: độ đo all-confidence, tập tương quan hiếm có trọng số, thuật toán ALLCONF-CORSI. I. GIỚI THIỆU Thuật toán khai thác luật kết hợp truyền thống [1-3] chỉ dùng một giá trị ngƣỡng phổ biến tối thiểu minsup với ngầm định là các mặt hàng có cùng tính chất và tần số trong dữ liệu, điều này không thực tế. Trong kinh doanh bán lẻ, thƣờng các mặt hàng thiết yếu, hàng tiêu dùng và các sản phẩm giá rẻ đƣợc mua nhiều hơn, trong khi các mặt hàng xa xỉ và các sản phẩm giá trị cao lại ít đƣợc mua (tập hiếm). Nếu chọn minsup quá cao thì các mặt hàng đƣợc khai thác thông thƣờng có giá thành thấp và mang lại lợi nhuận không cao cho doanh nghiệp. Ngƣợc lại, nếu chọn minsup quá thấp thì các mặt hàng đƣợc khai thác quá lớn, điều này làm cho doanh nghiệp khó khăn khi ra quyết định kinh doanh. Từ đó, có nhiều thuật toán khai thác tập hiếm đƣợc đề xuất nhƣ Apriori-Inverse, Rarity, Walky-G. Các thuật toán này dựa trên Apriori [8-9], Eclat [10] và có nhiều hạn chế nhƣ quét dữ liệu nhiều lần, sử dụng nhiều bộ nhớ, các chiến lƣợc cắt tỉa (không tái sử dụng cho lần khai thác tiếp theo). Những năm cuối của thế kỷ 20, C.H.Cai và đồng sự [5] đã đề xuất mô hình khai thác tập phổ biến có trọng số của mục hàng (mức độ quan trọng hay mức ý nghĩa của các mục hàng là khác nhau) chứa nhiều tri thức hơn so với khai thác tập phổ biến truyền thống (không trọng số). Sau đó, có nhiều tác giả nghiên cứu và đề xuất thuật toán [5-6] giải quyết vấn đề này. Tuy nhiên, các thuật toán đều tiếp cận và giải quyết theo hƣớng thỏa tính chất bao đóng giảm. Năm 2003, F.Tao có bàn luận đến hƣớng giải quyết bài toán trên theo cách tiếp cận “không thỏa tính chất bao đóng giảm”, điều này làm gia tăng đáng kể không gian tìm kiếm. Nhƣng ở công trình [6] F.Tao và đồng sự vẫn giải quyết bài toán theo hƣớng thỏa tính chất bao đóng giảm và thuật toán tựa Apriori. Trong những năm gần đây, S. Kamepalli cùng đồng sự đề xuất thuật toán IWI [7] sử dụng cấu trúc FP-Tree và khai thác tập hiếm có trọng số theo hƣớng tiếp cận không thỏa tính chất bao đóng giảm. Trong những năm gần đây, để đáp ứng nhu cầu ứng dụng khai thác dữ liệu trong các bài toán tiềm năng nhƣ phát hiện các cuộc tấn công máy tính, giao dịch gian lận trong các tổ chức tài chính, tin sinh học, y tế,… S. Bouasker và đồng sự [10] đã đề xuất thuật toán CORI khai thác tập hiếm không trọng số và kết hợp độ đo tƣơng quan bond [4] (tương quan giữa độ phổ biến và độ phủ của tập mục hàng trong các giao dịch). Thuật toán sử dụng cấu trúc IT-Tree khai thác tập hiếm và từ tập hiếm này xác định tập tƣơng quan hiếm. Tuy nhiên, thuật toán CORI khai thác tập tƣơng quan hiếm trên dữ liệu không có trọng số. Từ những khảo sát trên, chúng tôi đề xuất thuật toán giải quyết bài toán khai thác tập tƣơng quan hiếm có trọng số “không thỏa tính chất bao đóng giảm”, đây là thách thức lớn. Trong bài toán này, chúng tôi giải quyết kết hợp khai thác tập hiếm có trọng số và độ đo tƣơng quan all_confidence [4] (tương quan giữa độ phổ biến tập mục hàng và độ phổ biến tối đại của mục hàng trong tập). Dựa vào tập tương quan hiếm có trọng số đã tìm đƣợc, chúng tôi khai thác luật kết hợp hiếm và tất cả luật kết hợp hiếm đều có độ tin cậy nhỏ hơn ngƣỡng minallconf cho trƣớc. Thuật toán đề xuất bao gồm các thuật toán con nhƣ sau: - Xây dựng mảng Index_COOC chứa các items đồng xuất hiện và các item xuất hiện ít nhất trong một giao dịch của từng item hạt nhân; - Xây dựng cây nLOOC-Tree chứa các mẫu xuất hiện ít nhất trong một giao dịch của item hạt nhân; - Thuật toán ALLCONF-CORSI khai thác hiệu quả tập tƣơng quan hiếm có trọng số kết hợp độ đo tƣơng quan All-Confidence dựa trên mảng Index_LOOC và cây nLOOC-Tree. Phan Thành Huấn, Lê Hoài Bắc 451 Trong phần 2, bài báo trình bày các khái niệm cơ bản về khai thác tập phổ biến, tập hiếm không trọng số và có trọng số. Phần 3, xây dựng thuật toán xác định mảng chứa itemset đồng xuất hiện và itemset xuất hiện ít nhất trong một gia ...