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

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 { }1 2, ,..., nI i i i= . Mỗi giao tác t là một tập con của I, ( )t I⊆ . Tập { }1 2, ,..., mT t t t= 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( ) cardX 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. T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 16 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 { }sup( )L X I 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, { }1 2, ,..., mT t t t= , { }1 2, ,..., nI i i i= . Ta xây dựng ma trận ( )pqA a= cỡ m n× như sau: 1 , 0 . p q pq neu giao tac t chua muc i a 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 1 2, ,..., kV V V là k véc tơ nhị phân cỡ m. Ta gọi giao của 1 2, ,..., kV V V ( ký hiệu 1 2 ... kV V V∩ ∩ ∩ ) là véc tơ nhị phân P = (pi) cỡ m với: { } 2 1 1 1, 2,..., , ... 0 , i j i i1 i ik khi v j k p v v v truong hop nguoc lai = ∀ ∈ = ∧ ∧ ∧ =   1,2,..., .i 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; 1 2 , ,..., kq q q A A A là k véc tơ cột nào đó của A, (1 k m≤ ≤ ), P là giao của 1 2 , ,..., kq q q A A A . Tổng tất cả các phần tử của P được gọi là độ hỗ trợ của 1 2 , ,..., kq q q A A A . ( Trường hợp k = 1, độ hỗ trợ của véc tơ cột qA 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 1 2 , ,..., kq q q A A A trong A cũng chính là độ hỗ trợ của tập mục tương ứng 1 2 , ,..., kq q q i i i trong T. k-tập mục 1 2 , ,..., kq q q i i i là thường xuyên khi và chỉ khi k-tổ hợp véc tơ cột 1 2 , ,..., kq q q A A A 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 1 2 , , ... , kq q q i i i 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. T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 17 Mệnh đề 3.1.3. Ký hiệu kL là tập tất cả các k-tập mục thường xuyên, ( )k qL i là tập các k-tập mục thường xuyên chứa qi . Nếu ( ( ))k qcard L i k< thì mọi (k+1)-tập mục chứa qi 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 qi 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 ( ( ))k qcard L i k< . Từ mệnh đề 3.1.3. suy ra, nếu ( ( ))k qcard L i 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 qi . Véc tơ cột ứng với qi bị loại bỏ khỏi ma trận A . Mệnh đề 3.1.4. Ký hiệu kL là tập tất cả các k-tập mục thường xuyên, nếu ( ) 1kcard L k< + 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 ( ) 1kcard L k< + . 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 ( ) 1kcard L k< + . 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: { }1 2, ,..., mT t t t= , { }1 2, ,..., nI i i i= . Để 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ử pqa 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 ( )qsum A minsup≥ thì mục qi tương ứng với qA là mục thường xuyên. Nạp mục thường xuyên qi này vào tập các 1-tập mục thường xuyên 1L . T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 18 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à 1A . b) Lập tập 2C tất cả các tổ hợp chập 2 của các cột của 1A . Tính độ hỗ trợ của mỗi tổ hợp 2c C∈ . 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 2L . Bước k = 3: a) Tỉa ma trận 1A như sau: xóa tất cả các cột của 1A ứng với mục qi có 2( ( )) 3qcard L i < (theo mệnh đề 3.1.3.); xóa tất cả các dòng của 1A có tổng các phần tử nhỏ hơn 3. Gọi ma trận thu được từ 1A sau khi xoá các cột và các dòng như trên là 2A . b) Lập tập 3C tất cả các tổ hợp chập 3 của các cột của 2A . Tính độ hỗ trợ của mỗi tổ hợp 3c C∈ . 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 3L . 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 ( ) 1kcard L k< + hoặc kC = ∅ . 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 3. if sum(Aq) >= minsup // sum(Aq) là tổng các thành phần của Aq 4. L1 ← iq ; 5. else xoá cột Aq khỏi A. 6. for mỗi hàng Ap của A 7. if sum(Ap) < 2 8. Xoá hàng Ap khỏi A ; 9. for ( )k 1k 2 ; (L ) k 1 ; kcard ++−= > − 10. { 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 ( )1 2 kq q qA , A ,...,A 13. { T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 19 14. 1 2 kq q q B A A ... A= ∩ ∩ ∩ ; 15. if (B)sum minsup>= 16. { }1 2 kk q q qL i ,i ,..., i← ; 17. } 18. for mỗi mục iq thuộc Lk 19. if k q(L (i )) kcard < 20. Xoá cột Aq tương ứng với mục iq khỏi A ; 21. for mỗi hàng Ap của A 22. if sum(Ap) < k+1 23. Xoá dòng Ap khỏi A ; 24. k = k + 1 25. } 26. return 1 2 kL A A ... A= ∪ ∪ ∪ ; 3.3. Ví dụ. Xét cơ sở dữ liệu giao tác T (bảng 1) Bảng 1: CSDL T Giao tác Mục giao dịch t1 i1, i2, i4, i5 t2 i2 t3 i2, i4, i5, i6 t4 i1, i3 t5 i1, i4, i5 t6 i2, i4, i5 t7 i1 t8 i2, i5 t9 i1, i2, i3, i4, i5 t10 i1, i2 Bảng 2: ma trận nhị phân A TID i1 i2 i3 i4 i5 i6 t1 1 1 0 1 1 0 t2 0 1 0 0 0 0 t3 0 1 0 1 1 1 t4 1 0 1 0 0 0 t5 1 0 0 1 1 0 t6 0 1 0 1 1 0 t7 1 0 0 0 0 0 t8 0 1 0 0 1 0 t9 1 1 1 1 1 0 t10 1 1 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ó { }1 1 2 3 4 5, , , ,L i i i i i= . Vì 1( ) 5 1card L = > , quá trình tìm kiếm tiếp tục. T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 20 Bảng 3: Ma trận A1 Bảng 4: Ma trận A2 TID i1 i2 i3 i4 i5 t1 1 1 0 1 1 t3 0 1 0 1 1 t4 1 0 1 0 0 t5 1 0 0 1 1 t6 0 1 0 1 1 t8 0 1 0 0 1 t9 1 1 1 1 1 t10 1 1 0 0 0 TID i1 i2 i4 i5 t1 1 1 1 1 t3 0 1 1 1 t5 1 0 1 1 t6 0 1 1 1 t9 1 1 1 1 Bước k = 2: a) Xóa cột i6 (vì có sum(i6) < minsup ) và các dòng t2, t7 (có tổng các phần tử nhỏ hơn 2) của A, ta thu được ma trận rút gọn A1 (bảng 3). b) Tập các tổ hợp chập 2 của 5 cột của A1 là { }2 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5, , , , , , , , ,C i i i i i i i i i i i i i i i i i i i i= . Ta có { }2 1 2 1 3 1 4 1 5 2 4 2 5 4 5, , , , , ,L i i i i i i i i i i i i i i= . Vì 2( ) 7 2card L = > , quá trình tìm kiếm tiếp tục. Bước k = 3: a) Xóa cột i3 ( vì L2(i3) = 1 < 2 ) và các dòng t4, t8, t10 (có tổng các phần tử nhỏ hơn 3) của A1, thu được ma trận A2 (bảng 4) : b) Các tổ hợp chập 3 của các cột của A2 là { }3 1 2 4 1 2 5 1 4 5 2 4 5, , ,C i i i i i i i i i i i i= . Ta có { }3 1 2 4 1 2 5 1 4 5 2 4 5, , ,L i i i i i i i i i i i i= . Vì 3( ) 4 3card L = > , quá trình tìm kiếm tiếp tục. Cuối cùng, thu được tập gồm 17 tập mục thường xuyên: 1 2 3 4L L L L L= ∪ ∪ ∪ . 4. Tính toán thử nghiệm và kết luận Để đánh giá độ hiệu quả của thuật toán BMB, chúng tôi đã tiến hành so sánh nó với thuật toán Apriori. Hai thuật toán này được lập trình và tính toán thử nghiệm trong môi trường Matlab. Cơ sở dữ liệu thử nghiệm là cơ sở dữ liệu nhân tạo thu được bằng cách sử dụng thủ tục tạo dữ liệu nhân tạo thiết kế bởi IBM Quest Project, (R. Agrawal et al. giới thiệu trong [2]). Các tham số gán cho thủ tục tạo dữ liệu này là: • Số các mục trong I • Số các giao tác trong CSDL • Độ dài trung bình của các giao tác • Độ dài trung bình của các tập mục. Kết quả tính toán thử nghiệm cho thấy thuật toán BMB hiệu quả hơn so với Apriori; độ hiệu quả của BMB càng cao khi độ hỗ trợ tối thiểu càng nhỏ. Nguyên nhân là vì để tìm các TID i1 i2 i4 i5 t1 1 1 1 1 t9 1 1 1 1 Bảng 5: Ma trận A3 Bước k = 4: a) Chỉ có các dòng t3, t5, t6 của A2 bị xóa , thu được ma trận A3 (bảng 5): b) Chỉ còn lại một tổ hợp chập 4 của các cột của A3: { }4 1 2 4 5C i i i i= . Ta có { }4 1 2 4 5L i i i i= . Vì 4( ) 1 4card L = < , quá trình kết thúc. T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008 21 TMTX, thuật toán Apriori luôn phải sinh ra các ứng viên tại mỗi bước, mà khi độ hỗ trợ tối thiểu nhỏ thì số các tập mục ứng viên sẽ lớn, dẫn đến quá trình kết nối và tỉa các ứng viên sẽ tiêu tốn rất nhiều thời gian. Trong khi đó, BMB không cần tạo các ứng viên; thời gian mà nó dành cho việc tính các k-độ hỗ trợ cũng giảm dần khi cỡ ma trận nhị phân bị thu nhỏ dần sau mỗi bước tỉa. Hơn nữa, để lưu trữ ma trận nhị phân chỉ cần một dãy bit, do đó giảm được rất nhiều dung lượng bộ nhớ cần thiết. BMB thích hợp cho việc khai phá các CSDL lớn
Tóm tắt Bài báo này trình bày một thuật toán mới khai phá tập mục thường xuyên dựa trên ma trận nhị phân: thuật toán BMB. Đặc điểm của thuật toán này 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 nhanh, đơ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, do đó giảm được rất nhiều dung lượng bộ nhớ cần thiết. BMB có thể ứng dụng cho việc khai phá các CSDL lớn. Summary In this paper, a new frequent itemset mining algorithm based on the Binary matrix is proposed. The main features of this algorithm are that it only scans the transaction database once, it does not produce candidate itemsets and it uses only the fast and simple operations on binary vectores. In addition, it stores all transaction data in bits, so it needs less memory space. BMB can be applied to mining large databases. Tài liệu tham khảo [1] R. Agrawal, T. Imielinski, and A. N. Swami, Mining association rules between sets of items in large databases. In International Conference on 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., 1993. [2] R. Agrawal, and R. Srikant, Fast algorithms for mining association rules. In pro-ceedings of 20th International Conference on Very Large Databases, Santiago, Chile, 1994. [3] B. Goethals, Survey on Frequent Parttern Mining. Technical Report, Helsinki, Institute for Information Technology, 2003. [4] IBM Synthetic data. 2004. [5] Sotiris Kotsiantis, Dimitris Kanellopoulos, Association rules Mining: A recent Overview. GESTS International Transactions on Computer Science and Engineering, vol. 32(1), 2006. [6] D. Liu, Z. Kedem, An efficient Algorithm for Discovering The Maximal Frequent Itemset. IEEE Transaction on Knowledge and Data Engineering 14(3), 2002. [7] J. Park, M. Chen, and P. Yu, An effective hash-based algorithm for mining association rules. Proc. 1995 ACM-SIGMOD Int. Conf. Management of Data, San Jose: ACM Press, 1995. [8] Kenneth H. Rosen, Discrete Mathematics and Its Applications. MacGraw-Hill, 1994. [9] Z. Xu, and S. Zhang, An Optimization Algorithm Based on Apriori for Association Rules. Computer Engineering 29(19), 2003. [10] Q. L. Zhao, and S. S. Bhowmik, Association rules Mining: A Survey. Technical Report, CAIS, Nanyang Technological University, Singapore, No. 2003116, 2003.