Thuật toán tìm nhanh Minimal Generator của tập phổ biến đóng

Tóm tắt

Số lượng tập phổ biến đóng (FCI) thường nhỏ hơn so với tập phổ biến. Tuy nhiên, để khai thác luật kết hợp từ chúng cần phải tìm Minimal Generator (mG) [3],[5]. Việc tiếp cận tìm mG dựa vào phương pháp sinh ứng viên như trong [3],[5] mất nhiều thời gian khi số lượng tập phổ biến lớn. Trong bài báo này chúng tôi đề xuất thuật toán MG-CHARM, một thuật toán hiệu quả để tìm tất cả các mG của các tập phổ biến đóng. Dựa vào nhận xét về các tính chất của mG ở phần 2.4, chúng tôi phát triển một thuật toán không sinh ứng viên bằng cách trực tiếp khai thác mG của một tập đóng cùng lúc với việc tạo ra nó. Vì vậy, thời gian để tìm mG của một tập đóng là không đáng kể. Thực nghiệm chứng tỏ thời gian khai thác theo MG-CHARM nhỏ hơn nhiều so với tìm mG sau khi tìm tất cả các tập đóng (CHARM) , nhất là khi số lượng tập phổ biến lớn.