Một cách tiếp cận tìm tập phổ biến dựa trên giàn trong khai phá luật kết hợp

Tóm tắt

Khai phá luật kết hợp trong các cơ sở dữ liệu giao dịch lớn là bài toán đã được nhiều người quan tâm nghiên cứu. Bài toán khai phá luật kết hợp thường được thực hiện qua hai bước. Trong đó, bước đầu tiên là tìm tập phổ biến và bước thứ hai tìm các luật kết hợp dựa trên tập phổ biến tìm được. Hiện đã có rất nhiều thuật toán tìm tập phổ biến và thuật toán đề xuất sinh giàn từ quan hệ nhị phân, tuy nhiên các thuật toán này có độ phức tạp rất lớn. Trong bài báo này chúng tôi giới thiệu một kỹ thuật tìm tập phổ biến dựa trên giàn có độ phức tạp đa thức. Ưu điểm của cách tiếp cận này là bỏ qua giai đọan tìm tập ứng viên như trong thuật toán Apriori mà tìm trực tiếp tập phổ biến.