Thuật toán khai phá nhanh tập lợi ích cao với số lượng phần tử tối thiểu

Bài viết trình bày đề xuất một chiến lược mới để tỉa tập ứng viên nhằm giảm không gian tìm kiếm và đề xuất thuật toán ImprovedMinFHM khai phá hiệu quả tập lợi ích cao với số lượng phần tử tối thiểu
Nội dung trích xuất từ tài liệu:
Thuật toán khai phá nhanh tập lợi ích cao với số lượng phần tử tối thiểuKỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018DOI: 10.15625/vap.2018.00066 THUẬT TOÁN KHAI PHÁ NHANH TẬP LỢI ÍCH CAO VỚI SỐ LƯỢNG PHẦN TỬ TỐI THIỂU Nguyễn Mạnh Hùng 1, Đậu Hải Phong2 1 Phòng Sau đại học - Học viện Kỹ thuật Quân sự 2 Khoa Toán và Tin học, Trường Đại học Thăng Long manhhungk12@mta.edu.vn, phong4u@gmail.comTÓM TẮT: Khai phá tập lợi ích cao trong cơ sở dữ liệu giao dịch là một trong nhiệm vụ phổ biến trong khai phá dữ liệu và có ứngdụng rộng rãi trong nhiều lĩnh vực thực tế. Các thuật toán truyền thống thường đưa ra một số lượng lớn tập các phần tử có lợi íchcao gây khó khăn cho phân tích của người dùng. Một khái niệm “tập lợi ích cao với số lượng phần tử tối thiểu” được đề xuất năm2016 của tác giả Philippe Fournier-Viger và các đồng sự. Thuật toán MinFHM khai phá tập lợi ích cao với số lượng phần tử tốithiểu dựa trên cấu trúc EUCS (Estimated Utility Co-Occurrence Structure) để loại bớt tập ứng viên nhằm giảm không gian tìmkiếm. Tuy nhiên, cấu trúc EUCS sử dụng ngưỡng TWU (Transaction Weighted Utility), đây là một ngưỡng cao hơn mức cần thiết.Do đó, số lượng tập ứng viên được sinh ra lớn hơn rất nhiều so với thực tế tập lợi ích cao với số lượng phần tử tối thiểu được sinhra. Trong bài báo này chúng tôi đề xuất một chiến lược mới để tỉa tập ứng viên nhằm giảm không gian tìm kiếm và đề xuất thuậttoán ImprovedMinFHM khai phá hiệu quả tập lợi ích cao với số lượng phần tử tối thiểu. Kết quả thử nghiệm trên các bộ dữ liệu chothấy rằng thuật toán ImprovedMinFHM có tốc độ thực hiện nhanh hơn và sinh ra số lượng ứng viên ít hơn so với thuật toánMinFHM.Từ khóa: High Utility Mining, TWU, EUCS, ImprovedMinFHM. I. GIỚI THIỆU Ngày nay, việc tìm kiếm các tri thức tiềm ẩn trong khối lượng dữ liệu khổng lồ đang gia tăng nhanh chónglà bài toán rất được quan tâm. Khai phá tập lợi ích cao (HUIs) là một dạng bài toán khó để tìm kiếm các tập cógiá trị lợi ích lớn hơn một ngưỡng cho trước. Không giống như tìm tập phổ biến, bài toán tìm tập lợi ích cao chophép đánh giá mức độ quan trọng của từng phần tử trong dữ liệu. Trong các thuật toán khai phá tập lợi ích caotruyền thống [1], [2], [3], [4], [5], [6], [7],… thì chúng sinh ra một số lượng lớn các tập lợi ích cao. Điều này làmtốn dung lượng lưu trữ và thời gian để phân tích một lượng lớn tập lợi ích cao [8], [9]. Để giải quyết vấn đề này,đã có một số nhóm thuật toán khai phá tập lợi ích cao đại diện được đề xuất như: tập lợi ích đóng (Closed HUIs-CHUI)[8], tập lợi ích lớn nhất (Maximal HUIs-MaxHUI) [10], bộ sinh tập lợi ích cao (Generator of HUIs -GHUI) [9]. Năm 2016, nhóm Philippe Fournier Viger [11] và cộng sự đã đề xuất bài toán khai phá tập lợi ích cao vớisố lượng phần tử tối thiểu (MinHUIs) nhằm giải quyết vấn đề thường thấy của các thuật toán khai phá tập lợi íchcao là các tập lợi ích cao được sinh ra gồm nhiều phần tử nhưng lại đại diện cho những trường hợp ít gặp. Ví dụ,có một vài khách hàng mua số lượng lớn các mặt hàng dẫn đến các mặt hàng này có khả năng là tập lợi ích cao.Nhưng với mục đích quảng cáo, tiếp thị thì các nhà bán hàng chỉ quan tâm đến tìm kiếm một số ít các mặt hàngsinh ra lợi nhuận cao. Khi đó, nhà bán hàng có thể tập trung giới thiệu, quảng cáo một số ít mặt hàng cho sốlượng lớn khách hàng hơn là quá nhiều mặt hàng cho số ít khách hàng. Một trong những thách thức trong khai phá tập lợi ích cao là các tập lợi ích không có tính chất đóng(closure properties) [12], điều này sẽ làm bùng nổ số lượng ứng viên và tăng thời gian duyệt dữ liệu để kiểm tracác ứng viên. Để giảm số lượng ứng viên thì đa số các thuật toán đều sử dụng ngưỡng TWU (TransactionsWeighted Utility) do Liu[13] đề xuất. Thuật toán MinFHM [11] là mở rộng của thuật toán FHM [2] sử dụng mộtcấu trúc lượng giá lợi ích đồng xuất hiện của một cặp phần tử (EUCS) làm điều kiện để cắt tỉa tập ứng viên và kếthợp với một vài thuộc tính cho khai phá MinHUIs. Kết quả cho thấy rằng thuật toán MinFHM nhanh hơn rấtnhiều so với các thuật toán FHM [2], CHUD [8], GHUI-Miner [9]. Trong bài báo này, chúng tôi đề xuất một chiến lược cắt tỉa mới và thuật toán ImprovedMinFHM để giảmsố lượng ứng viên và không gian tìm kiếm cho bài toán khai phá tập lợi ích cao với số lượng phần tử tối thiểu.Nội dung tiếp theo của bài báo được tổ chức như sau: Phần II, những vấn đề liên quan đến khai phá tập lợi íchcao với số lượng phần tử tối thiểu; Phần III, đề xuất chiến lược cắt tỉa mới và thuật toán ImprovedMinFHM; PhầnIV, Kết quả đánh g ...