Tài liệu Thuật toán khai phá tập mục thường xuyên dựa trên ma trận nhị phân

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 rất nhiều dung