So sánh hiệu suất các thuật toán HAUIM

Trong bài báo "So sánh hiệu suất các thuật toán HAUIM", nhóm tác giả khảo sát toàn diện tình trạng nghiên cứu hiện tại về các thuật toán HAUIM. Chúng tôi so sánh về những cải tiến trong các thuật toán mới, cung cấp những hiểu biết sâu sắc có giá trị về khai thác tập hữu ích trung bình cao. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
So sánh hiệu suất các thuật toán HAUIMKỷ yếu Hội thảo khoa học Khoa Công nghệ thông tin, năm 2024 SO SÁNH HIỆU SUẤT CÁC THUẬT TOÁN HAUIM Phạm Tuấn Khiêm1, *, Trần Đắc Tốt1 Trường Đại học Công Thương Thành phố Hồ Chí Minh 1 * Email: khiempt@huit.edu.vn Ngày nhận bài: 01/04/2024; Ngày chấp nhận đăng: 20/05/2024 TÓM TẮT Một cải tiến trong khai thác tập hữu ích cao (HUI) được sử dụng rộng rãi trong nhiều ứngdụng khai thác tập mẫu, là khai thác tập hữu ích trung bình cao (HAUIM). Một vấn đề lớn vớikhai thác HUI là thước đo độ hữu ích tỷ lệ thuận với độ dài của tập mục, đây là một lỗ hổngchính trong khai thác HUI. Sử dụng thước đo khách quan được gọi là độ hữu ích trung bình,HAUIM xác định các tập mục bằng cách so sánh mức độ hữu ích của các tập mục với độ dàicủa chúng. Trong bài báo này, chúng tôi khảo sát toàn diện tình trạng nghiên cứu hiện tại vềcác thuật toán HAUIM. Chúng tôi so sánh về những cải tiến trong các thuật toán mới, cungcấp những hiểu biết sâu sắc có giá trị về khai thác tập hữu ích trung bình cao.Từ khóa: Khai thác tập hữu ích cao, khai thác tập hữu ích trung bình cao, khai thác dữ liệu,chặn trên độ hữu ích trung bình, chiến lược tỉa. 1. GIỚI THIỆU Khai thác tập phổ biến (FI) là một trong những lĩnh vực chính của khai thác dữ liệu [1].Tìm kiếm các tập mục phổ biến, có tần suất xuất hiện cao trong cơ sở dữ liệu giao dịch là mụctiêu của việc khai thác FI. Tuy nhiên, khai thác tập phổ biến truyền thống chỉ xem xét tần suấtxuất hiện của các tập mặt hàng trong cơ sở dữ liệu giao dịch nhưng lại bỏ qua các yếu tố quantrọng khác như số lượng, lợi nhuận và trọng lượng của các mặt hàng. Khai thác tập hữu íchcao (HUI) [2],[3] là một phần mở rộng của FI, khai thác các tập hữu ích cao bằng cách tínhđến cả số lượng và lợi nhuận của một mục. Vấn đề khai thác HUI gần đây đã thu hút rất nhiềusự quan tâm và nhiều thuật toán khác nhau đã được đề xuất [4]. Trong khai thác HUI, số lượng và đơn vị lợi nhuận của các tập mục được hợp nhất [5] đểtăng ý nghĩa và tính thực tế của các mẫu. Một tập mục được gọi là HUI nếu độ hữu ích của nólớn hơn ngưỡng hữu ích tối thiểu do người dùng chỉ định. Tuy nhiên, cơ sở dữ liệu càng lớnthì số lượng tập tiềm năng trong không gian tìm kiếm càng khổng lồ và việc xử lý lưu trữ trongbộ nhớ là một thách thức. Do đó, việc tỉa các tập mục ứng viên không có triển vọng là điềucần thiết để khai thác HUI hiệu quả. Nhiều thuật toán một pha [6] và hai pha [7], [8] sử dụngđại lượng TWU để loại bỏ các tập mục ứng cử viên không tiềm năng. Trong kỹ thuật hai pha,kỹ thuật apriori không hiệu quả quét cơ sở dữ liệu nhiều lần để tính độ hữu ích của các ứngviên. Các phương pháp một pha hoàn thành cả việc tạo ứng viên và kiểm tra HUI trong mộtgiai đoạn duy nhất, giúp giảm việc quét cơ sở dữ liệu nhiều lần. Một hạn chế lớn trong các phương pháp khai thác HUI là độ đo độ hữu ích tỷ lệ thuậnvới độ dài của tập mục. Ảnh hưởng của độ dài của các tập trong khai thác HUI được loại bỏbằng cách đưa vào một đại lượng hợp lý được gọi là độ hữu ích trung bình. Độ hữu ích củamột tập mục được xác định bằng cách chia độ dài của nó cho độ hữu ích trung bình của nó. 41Phạm Tuấn Khiêm, Trần Đắc TốtTrong bài báo này, chúng tôi trình bày một số thuật toán mới trong khai thác các tập hữu íchtrung bình cao từ một cơ sở dữ liệu giao dịch. Bài báo này có những nội dung nghiên cứu sauđây: Chúng tôi thảo luận về các khía cạnh khác nhau của các thuật toán “Khai thác tập hợp hữu ích trung bình cao” như: công việc liên quan, cách tiếp cận, số pha, các chiến lược tỉa, các hạn chế. Chúng tôi giải thích chi tiết về các thuật toán: HAUI-Miner [9], MHAI [11], HAUIM- GMU [12]. 2. PHƯƠNG PHÁP NGHIÊN CỨU2.1 Khái niệm cơ sở trong khai thác tập hữu ích trung bình cao Cho cơ sở dữ liệu giao dịch ? = {?1 , ?2 , … , ? ? }, với n là số lượng giao dịch trong ?, tập ? = {?1 , ?2 , … , ? ? } gồm m mục phân biệt trong D. ∀ ?? ∈ ?, ?? = {? ? |? = 1, 2, … , ?? , ? ? ∈ ?},với ?? là số các mục trong giao dịch ?? . Bảng 1 biểu diễn ví dụ về cơ sở dữ liệu giao dịch ?dùng để khai thác tập hữu ích trung bình cao, mỗi mục (cột 2 của Bảng 1) trong giao dịch (cột1 của Bảng 1) có một số lượng (mỗi số sau dấu : cột 2 của Bảng 1). Bảng 2 biểu diễn giá trịlợi nhuận của các mục. Bảng 1. Cơ sở dữ liệu giao dịch Mã giao dịch (TID) Giao dịch ?1 A: ...