Tan Khai Ngo

Extracting high occupancy itemsets (HOIs) from transaction databases is a significant and emerging area in data mining. This process aims to identify itemsets whose occupancy exceeds a user-defined minimum threshold. Over the years, numerous studies have sought to address this challenge, yet determining an appropriate minimum occupancy threshold remains difficult. Setting the threshold too low can lead to an overwhelming number of HOIs, rendering many mining algorithms inefficient and potentially exhausting memory resources. Conversely, if the threshold is set too high, the mining algorithm may fail to identify any HOIs whatsoever. Establishing an effective minimum threshold frequently entails a time-consuming generate-and-test process. This work introduces a novel method for mining top-k HOIM. The primary innovation of the algorithm lies in its candidate itemset pruning strategy. Specifically, if transactions containing items from the newly expanded itemset have the same length, the algorithm omits the Upper Bound (UBO) calculation, thereby significantly enhancing computational efficiency. In cases where UBO calculation is required, the process concludes as soon as the threshold is reached, without completing the entire loop. Additionally, the method leverages the comparison of UBO values stored in the Estimated Occupancy Co-Occurrence Structure (EOCS) matrix to facilitate early pruning of extended itemsets comprising two items. The proposed algorithm utilizes a depth-first search technique in conjunction with an equivalence class to process potential itemsets. Experiments conducted on both synthetic and real-world datasets show that this innovative approach is 20-25 times faster and requires 2 times less memory than baseline algorithms.

Khai thác tập mục chiếm hữu cao là khai thác các tập mục có độ chiếm hữu lớn hơn một ngưỡng cho trước từ cơ sở dữ liệu giao dịch. Những nghiên cứu gần đây về khai thác tập mục chiếm hữu cao phải đối mặt với hai thách thức lớn, đó là không gian tìm kiếm theo hàm mũ và ngưỡng chiếm hữu tối thiểu lại phụ thuộc vào người sử dụng. Người dùng phải chỉ định các ngưỡng chiếm hữu tối thiểu này để phù hợp với những công việc khai thác của họ, việc lựa chọn ngưỡng này trong thực tế là không đơn giản vì người dùng chưa hoặc không có đủ thông tin về cơ sở dữ liệu (CSDL) cần khai thác. Lựa chọn ngưỡng này quá cao sẽ đưa đến không tìm đủ các mẫu cần thiết. Ngược lại, nếu ngưỡng được chọn quá thấp, số lượng tập mục trả về là rất lớn và cần nhiều thời gian phân tích, do đó trong nghiên cứu này chúng tôi đề xuất một thuật toán khai thác không dựa vào ngưỡng chiếm hữu mà dựa vào 𝑘 tập mục hàng đầu cần khai thác. Theo sự tìm hiểu của chúng tôi, đây là nghiên cứu đầu tiên trong khai thác top-k tập mục chiếm hữu cao. Kết quả thử nghiệm cho thấy phương pháp tiếp cận được mô tả trong bài viết này đạt được hiệu suất tốt hơn về khả năng mở rộng và tính hiệu quả cao.