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

T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008

15

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 lượng bộ nhớ.

BMB thích hợp cho việc khai phá các CSDL lớn.

2. Bài toán khai phá tập mục thường xuyên

Cho tập các mục I i i i = { 1 2 , ,..., n } . Mỗi giao tác t là một tập con của I, ( ) t I ⊆ . Tập

T t t t = { 1 2 , ,..., m } của m giao tác được gọi là một cơ sở dữ liệu các giao tác. Mỗi tập con gồm k

mục phân biệt của I được gọi là một k-tập mục.

Định nghĩa 2.1. Cho CSDL T và tập mục X I ⊆ . Ta gọi số các giao tác trong T chứa

X là độ hỗ trợ của X. Ký hiệu độ hỗ trợ của X là sup(X), ta có:

sup( ) card X t T t X = ∈ ⊇ ({ }) .

X được gọi là tập mục thường xuyên (hay phổ biến) nếu sup(X) ≥ minsup, trong đó

minsup là ngưỡng hỗ trợ tối thiểu cho trước bởi người sử dụng.