Trong báo cáo này chúng tôi đưa ra một thuật toán mới, gọi là thuật toán BMB, khai phá tập mục thường xuyên. Thuật toán gồm hai pha: * Chuyển đổi cơ sở dữ liệu giao tác ban đầu thành một ma trận nhị phân * Sử dụng các phép toán quan hệ trên các véc tơ của ma trận nhị phân phát hiện TMTX. | T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 Thuật toán khai phá tập mục thường xuyên dựa trên ma trận nhị phân Nguyễn Thanh Tùng (Viện Công nghệ Thông tin - Viện KH&CN Việt Nam) Phạm Quang Trung ( Khoa Công nghệ thông tin – ĐH Thái Nguyên) 1. Mở đầu Phát hiện tập mục thường xuyên (TMTX) trong cơ sở dữ liệu (CSDL) lớn là một kỹ thuật quan trọng của khai phá dữ liệu (KPDL). Ra đời vào năm 1993, xuất phát từ nhu cầu khai phá luật kết hợp trong các cơ sở dữ liệu giao tác của các siêu thị, ngày nay khai phá TMTX còn được sử dụng như là một công cụ hiệu quả để phát hiện các phụ thuộc hàm, các luật kết hợp đa mức (multi-level associa-tion rules), các mẫu hình liên tiếp (sequential patterns). Nhiều thuật toán nhanh khai phá TMTX đã được đề xuất, nhưng cho đến nay thuật toán Apriori do R. Agrawal và R. Srikant [2] đưa ra vẫn là thuật toán cơ bản nhất, có sức thuyết phục và ảnh hưởng lớn đối với cộng đồng KPDL. Nhiều thuật toán sau này được xây dựng dựa trên lược đồ của thuật toán Apriori và được gọi là các thuật toán kiểu Apriori (Apriori-like) [3,5,9,10]. Sử dụng tính chất anti-monotone của TMTX, thuật toán kiểu Apriori thực hiện việc phát hiện các TMTX theo từng bước. Tại mỗi bước phải thực hiện hai thủ tục: kết nối các tập mục và tỉa các ứng viên. Hai thủ tục này đòi hỏi một khối lượng tính toán rất lớn và quá trình xử lý các giao tác rất phức tạp. Do đó, khi CSDL có kích thước rất lớn, các thuật toán kiểu Apriori thường không hiệu quả. Trong báo cáo này chúng tôi đưa ra một thuật toán mới, gọi là thuật toán BMB, khai phá tập mục thường xuyên. Thuật toán gồm hai pha: * Chuyển đổi cơ sở dữ liệu giao tác ban đầu thành một ma trận nhị phân * Sử dụng các phép toán quan hệ trên các véc tơ của ma trận nhị phân phát hiện TMTX. Đặc điểm của BMB là chỉ cần quét CSDL một lần, không sinh các ứng viên và chỉ sử dụng các phép toán đơn giản trên các véc tơ nhị phân. Hơn nữa, để lưu trữ ma trận nhị phân chỉ cần một dãy bit (mỗi bit cho một phần tử), do đó tiết kiệm được
