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

Chia sẻ: Thi Thi | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

72
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ý hiệu L k là tập tất cả các k-tập mục thường xuyên, nếu card ( L k ) < k + 1 thì TMTX tối đại có kích thước bằng k. Chứng minh. Thật vậy, giả sử tồn tại tập mục thường xuyên X có kích thước lớn hơn k. Khi đó, X sẽ có nhiều hơn k tập mục con kích thước k 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 ) < k + 1 . Từ mệnh đề 3.1.4. suy ra quá trình từng bước phát hiện các TMTX trong T, (theo kích thước từ nhỏ đến lớn), sẽ dừng tại bước k khi card ( L k ) < k + 1 . 3.2. Thuật toán Dựa trên các kết quả trong mục 3.1., chúng tôi đề nghị thuật toán sau đây, gọi là thuật toán BMB, phát hiện TMTX trong CSDL giao tác. Thuật toán BMB bao gồm hai pha: • Xây dựng ma trận nhị phân A tương ứng với cơ sở dữ liệu T. • Dựa trên ma trận A, phát hiện tập các tập mục thường xuyên L. 3.2.1. Xây dựng ma trận nhị phân Giả sử cơ sở dữ liệu giao tác T có m giao tác và n mục: T = { t1 , t2 ,..., tm } , I = { i1 , i2 ,..., in } . Để thu được ma trận nhị phân A, ta quét một lần cơ sở dữ liệu và tính các phần tử a pq của A theo (3.1). 3.2.2. Phát hiện các tập mục thường xuyên Dựa vào ma trận nhị phân A thu được sau pha một, ta tiến hành phát hiện các TMTX theo phương pháp tiếp cận từng bước. Bước k = 1: Tính độ hỗ trợ của từng véc tơ cột của A, tức là tính các tổng sum(Aq), q = 1, 2, ..., n. Nếu sum( Aq ) ≥ minsup thì mục i q tương ứng với Aq là mục thường xuyên. Nạp mục thường xuyên i q này vào tập các 1-tập mục thường xuyên L1 . 17 T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 Bước k = 2: a) Tỉa ma trận A : xóa tất cả các cột của A có độ hỗ trợ nhỏ hơn minsup (căn cứ vào nhận xét sau mệnh đề 3.1.2.); xóa tất cả các dòng của A có tổng các phần tử nhỏ hơn 2 , (căn cứ vào mệnh đề 3.1.1.). Gọi ma trận thu được từ A sau khi xoá các cột và các dòng như trên là A 1 . b) Lập tập C 2 tất cả các tổ hợp chập 2 của các cột của A 1 . Tính độ hỗ trợ của mỗi tổ hợp c ∈ C 2 . Nếu c có độ hỗ trợ không nhỏ hơn minsup thì tập mục tương ứng là 2-tập mục thường xuyên. Nạp TMTX này vào tập các 2-tập mục thường xuyên L 2 . Bước k = 3: a) Tỉa ma trận A 1 như sau: xóa tất cả các cột của A 1 ứng với mục i q có card ( L 2 (i q )) < 3 (theo mệnh đề 3.1.3.); xóa tất cả các dòng của A 1 có tổng các phần tử nhỏ hơn 3. Gọi ma trận thu được từ A 1 sau khi xoá các cột và các dòng như trên là A 2 . b) Lập tập C 3 tất cả các tổ hợp chập 3 của các cột của A 2 . Tính độ hỗ trợ của mỗi tổ hợp c ∈ C 3 . Nếu c có độ hỗ trợ không nhỏ hơn minsup thì tập mục tương ứng là 3-tập mục thường xuyên. Nạp TMTX này vào tập các 3-tập mục thường xuyên L 3 . Các bước tiếp k = 4, 5, ... tiếp theo thực hiện tương tự. Quá trình tìm kiếm TMTX dừng tại bước k khi card ( L k ) < k + 1 hoặc C k = ∅ . Tựa code của thuật toán BMB là như sau. Input: Cơ sở dữ liệu T, độ hỗ trợ minsup Output: Tập các tập mục thường xuyên L. 1. Xây dựng ma trận nhị phân A tương ứng với cơ sở dữ liệu T; 2. for mỗi cột Ai của A if sum(Aq) >= minsup // sum(Aq) là tổng các thành phần của Aq 3. L1 ← iq ; 4. else xoá cột Aq khỏi A. 5. 6. for mỗi hàng Ap của A 7. if sum(Ap) < 2 Xoá hàng Ap khỏi A ; 8. 9. 10. ( k = 2 ; card (L k −1 ) > k − 1 ; k ++ ) { 11. Tìm tất cả tổ hợp châp k của các véc tơ cột của A ; 12. for mỗi tổ hợp chập k các véc tơ cột A q1 , A q 2 ,..., A q k 13. 18 for ( { ) T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 14. B = A q1 ∩ A q 2 ∩ ... ∩ A q k ; 15. if sum(B) >= minsup { L k ← i q1 ,i q 2 ,...,i q k 16. 17. }; } 18. for mỗi mục iq thuộc Lk 19. if card (L k (i q )) < k Xoá cột Aq tương ứng với mục iq khỏi A ; 20. for mỗi hàng Ap của A 21. if sum(Ap) < k+1 22. Xoá dòng Ap khỏi A ; 23. k=k+1 24. 25. } 26. return L = A1 ∪ A 2 ∪ ... ∪ A k ; 3.3. Ví dụ. Xét cơ sở dữ liệu giao tác T (bảng 1) Bảng 1: CSDL T Bảng 2: ma trận nhị phân A Giao tác t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 Mục giao dịch i1, i2, i4, i5 i2 i2, i4, i5, i6 i1, i3 i1, i4, i5 i2, i4, i5 i1 i2, i5 i1, i2, i3, i4, i5 i1, i2 TID t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 i1 1 0 0 1 1 0 1 0 1 1 i2 1 1 1 0 0 1 0 1 1 1 i3 0 0 0 1 0 0 0 0 1 0 i4 1 0 1 0 1 1 0 0 1 0 i5 1 0 1 0 1 1 0 1 1 0 i6 0 0 1 0 0 0 0 0 0 0 Giả sử minsup = 2. Quá trình phát hiện các TMTX trong T theo thuật toán BMB là như sau. Pha 1. Ta có ma trận nhị phân tương ứng với T là ma trận A cho trong bảng 2. Pha 2. Tìm các tập mục thường xuyên. Bước k = 1: Ta có L1 = { i1 , i2 , i3 , i4 , i5 } . Vì card ( L1 ) = 5 > 1 , quá trình tìm ki ếm ti ếp t ụ c. 19