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

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.
Nội dung trích xuất từ tài liệu:
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 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 = { i1 , i2 ,..., in } . Mỗi giao tác t là một tập con của I, ( t ⊆ I ) . Tập T = { t1 , t2 ,..., tm } 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( X ) = card ({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. 15 T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 Bài toán khai phá TMTX được phát biểu như sau: Cho CSDL giao tác T và ngưỡng hỗ trợ tối thiểu minsup. Tìm tất cả các TMTX theo ngưỡng minsup, nghĩa là tìm tập L = { X ⊆ I sup( X ) ≥ minsup} . 3. Thuật toán dựa trên ma trận nhị phân BMB 3.1. Cơ sở lý thuyết Định nghĩa 3.1.1. Ma trận nhị phân là ma trận mà mỗi phần tử của nó chỉ có thể nhận giá trị 0 hoặc 1. Định nghĩa 3.1.2. Cho cơ sở dữ liệu T gồm m giao tác và n mục, T = { t1 , t2 ,..., tm } , I = { i1 , i2 ,..., in } . Ta xây dựng ma trận A = ( a pq ) cỡ m × n như sau:  1 neu giao tac t p chua muc iq , a pq =   0 truong hop nguoc lai. (3.1) Khi đó, A được gọi là ma trận nhị phân tương ứng của T. Véc tơ cột Aq của A được gọi là véc tơ cột tương ứng với mục ip . Định nghĩa 3.1.3. [8]. Cho V1 , V2 ,..., Vk là k véc tơ nhị phân cỡ m. Ta gọi giao của V1 , V2 ,..., Vk ( ký hiệu V1 ∩ V2 ∩ ... ∩ Vk ) là véc tơ nhị phân P = (pi) cỡ m với:  1 khi vi j = 1 ∀ j ∈ {1, 2,..., k } , pi = vi1 ∧ vi 2 ∧ ... ∧ vik =   0 truong hop nguoc lai, i = 1, 2,..., m. Định nghĩa 3.1.4. Xét cơ sở dữ liệu T với ma trận nhị phân tương ứng A; A q1 , A q2 ,..., A qk là k véc tơ cột nào đó của A, ( 1 ≤ k ≤ m ), P là giao của A q1 , A q2 ,..., A qk . Tổng tất cả các phần tử của P được gọi là độ hỗ trợ của A q1 , A q2 ,..., A qk . ( Trường hợp k = 1, độ hỗ trợ của véc tơ cột Aq bằng tổng tất cả các thành phần của nó). Dễ thấy độ hỗ trợ của tổ hợp véc tơ cột A q1 , A q2 ,..., A qk trong A cũng chính là độ hỗ trợ của tập mục tương ứng i q1 , i q2 ,..., i qk trong T. k-tập mục i q1 , i q2 ,..., i qk là thường xuyên khi và chỉ khi k-tổ hợp véc tơ cột A q1 , A q2 ,..., A qk có độ hỗ trợ không nhỏ hơn giá trị minsup. Do đó, bài toán khai phá TMTX trong T tương đương với bài toán tìm tất cả các tổ hợp véc tơ cột của A có độ hỗ trợ không nhỏ hơn giá trị minsup. Từ định nghĩa độ hỗ trợ của một tổ hợp véc tơ cột trong ma trận nhị phân A, dễ dàng suy ra các mệnh đề sau đây. Mệnh đề 3.1.1. Nếu tổng tất cả các phần tử của véc tơ dòng nào đó của A nhỏ hơn k thì có thể bỏ qua véc tơ dòng này khi tính độ hỗ trợ của các k-tổ hợp véc tơ cột trong A. Mệnh đề 3.1.2. (Tính chất anti-monotone). Nếu iq1 , iq2 , ... , iqk là k-tập mục thường xuyên thì mọi tập con của nó cũng là thường xuyên. Từ mệnh đề 3.1.2. suy ra, nếu véc tơ cột nào đó của A có độ hỗ trợ nhỏ hơn minsup thì ta có thể loại bỏ nó khỏi A trong quá trình tìm kiếm các TMTX dựa trên ma trận A. 16 T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 Mệnh đề 3.1.3. Ký hiệu Lk là tập tất cả các k-tập mục thường xuyên, L k (i q ) là tập các k-tập mục thường xuyên chứa i q . Nếu card ( L k (i q )) < k thì mọi (k+1)-tập mục chứa i q không thể là TMTX. Chứng minh. Thật vậy, giả sử X là (k+1)-tập mục thường xuyên, khi đó X sẽ có k tập mục con kích thước k chứa i q và tất cả các tập mục con này đều là thường xuyên (theo mệnh đề 3.1.2.). Điều này mâu thuẫn với giả thiết card ( L k (i q )) < k . Từ mệnh đề 3.1.3. suy ra, nếu card ( L k (i q )) < k thì trong quá trình phát hiện các TMTX có kích thước lớn hơn k ta không cần quan tâm đến mục i q . Véc tơ cột ứng với i q bị loại bỏ khỏi ma trận A . Mệnh đề 3.1.4. Ký h ...