IT-Tree và thuật toán Apriori

IT-TREE VÀ THUẬT TOÁN APRIORI TRẦN ĐÌNH NGHĨA(*), NGUYỄN QUỐC HUY(**) TÓM TẮT Khám phá itemsets là công việc quan trọng trong khai thác dữ liệu. Nhờ đó mà ta có thể khai thác luật kết hợp từ các itemsets đó. Tuy nhiên, không gian tìm kiếm trong giai đoạn tìm các itemsets cần thiết thì rất lớn theo từng bước, độ dài k của các item. Do vậy, chúng ta cần phải quan tâm đến việc rút gọn không gian tìm kiếm. Apriori (2,7) là một tính chất quan trọng, nhờ đó mà ta có thể loại bỏ những itemsets không cần thiết ở các bước sau. Thuật toán Apriori (2,7) là thuật toán kinh điển trong việc khai thác tập phổ biến. IT-Tree (1,3,4,5) (tidset-itemset search tree) là một cấu trúc cây được Zaki và các đồng nghiệp đưa ra, có nhiều điểm giống thuật toán Apriori. ABSTRACT Mining itemsets is significant work in data mining. Therefore, we can mine association rules from these itemsets. However, the search space in mining itemsets phase is very large if the length k of itemsets grows up. Thus, it is necessary to interest in reducing the search space. Apriori [2] is an important property from which we can remove unnecessary itemsets in the next steps. Apriori algorithm [2] is a classic algorithm in mining frequent itemsets. IT-Tree [1,3] (tidset-itemset search tree) is a tree structure proposed by Zaki et al with many factors the same as Apriori algorithm. 1. GIỚI THIỆU Khai thác các itemsets là công việc rất cần thiết trong lĩnh vực khai thác dữ liệu và rất phổ biến trong các ứng dụng phân tích thị trường, thiết kế catalog, và phân khúc khách hàng. Bài toán khai thác itemsets sẽ rất lớn nếu cơ sở dữ liệu lớn, khi đó không gian tìm kiếm sẽ rất lớn và sẽ không thực hiện được trong thực tế. Do vậy, vấn đề giảm không gian tìm kiếm rất cần thiết để hiện thực bài toán này trong thực tế. Hiện nay thuật toán Apriori được xem là mẫu mực để giải quyết bài toán này, gần đây cấu trúc IT-Tree cũng đóng góp không nhỏ vào bài toán khai thác itemsets. Thuật toán Apriori sinh ra các tập ứng viên để tính trong một lần duyệt bằng việc sử dụng chỉ các itemsets đã được thấy là phổ biến trong lần duyệt trước mà không cần quan tâm đến các giao tác trong cơ sở dữ liệu (CSDL). Cơ sở của điều đó là bất kỳ tập con nào của itemsets phổ biến phải là phổ biến, đây là tính chất Apriori. Vì vậy, các tập ứng cử có k-item có thể được sinh ra bằng cách kết nối các tập phổ biến có (k - 1)-item, và xoá các tập ứng viên nếu nó có chứa bất kỳ một tập con nào mà không phải là phổ biến. Thủ tục này nói chung dẫn đến một số nhỏ hơn nhiều các tập ứng cử viên, nói cách khác nó khá hiệu quả trong việc "tỉa gọn" không gian tìm kiếm. IT-Tree có cách tiếp cận đơn giản là dựa trên phần giao nhau của tập các giao tác để tính độ phổ biến và khái niệm mới lớp tương đương nhằm chia không gian xử lý ban đầu thành tập các không gian nhỏ độc lập giúp cho việc tìm kiếm nhanh hơn. Một điểm mới nữa của phương pháp IT-tree là dựa trên phần khác nhau trên Tidset của các tập dữ liệu nhằm làm giảm kích thước bộ nhớ yêu cầu và giúp cho việc tính độ phổ biến nhanh hơn. (*) , ( ** )Th.S, Khoa Công nghệ thông tin, Trường Đại học Sài Gòn Để giảm kích thước bộ nhớ lưu Tidset, tác giả của IT-Tree là Zaki và Gouda đề nghị lưu Diffset (tập khác nhau giữa Tidset(X) so với Tidset(Y)), Diffset có kích thước khá nhỏ so với Tidset nên dung lượng bộ nhớ giảm đáng kể. IT-Tree thỏa tính chất Apriori. Hình 1.1 Thuật toán Apriori Thuật toán Apriori sử dụng độ hỗ trợ tối thiểu (minsup) để loại bỏ các ứng viên không thoả minsup. Giá trị minsup do người dùng đưa ra. Định nghĩa 1. Độ hỗ trợ của itemset: Độ hỗ trợ (Support) của một tập X trong tập các giao tác D, kí kiệu supp(X) xác định như sau:   D XD/TT supp(X)   ; Miền giá trị: 0 Supp(X) 1 với mọi tập X. Định nghĩa 2. Lớp tương đương: Cho I là tập các danh mục và IX  . Gọi hàm p(X, k) = X[1:k] gồm k phần tử đầu của X và một quan hệ tương đương dựa vào tiền tố K trên itemset như sau: ),(),(,, kYpkXpYXIYX k   . Hai itemset có cùng một lớp tương đương khi và chỉ khi chúng chia sẻ k phần tử đầu. Mỗi nút trong IT-Tree đại diện cặp Itemset-Tidset )(XtX  , thực tế là lớp tiền tố. Tất cả các nút con của nút X thuộc về lớp tương đương vì chúng cùng tiền tố X. Bảng 1.1: Cơ sở dữ liệu giao tác Mã giao tác A C D T W t1 1 1 0 1 1 t2 0 1 1 0 1 t3 1 1 0 1 1 t4 1 1 1 0 1 t5 1 1 1 1 1 t6 0 1 1 1 0 Kí hiệu lớp tương đương là    nlllP ,...,, 21 , trong đó P là nút cha và mỗi li là một mục dữ liệu đơn, đại diện cho nút )( ii PltPl  . Chẳng hạn, nút gốc của cây tương ứng với lớp [] = {A,C,D,T,W}, nút trái cùng của gốc là lớp [A] chứa tất cả các itemset có A là tiền tố, nghĩa là tập {C,D,T,W}. Như vậy, mỗi lớp thành viên đại diện cho một con của nút cha. Một lớp đại diện cho các mục dữ liệu mà các mục dữ liệu đó là tiền tố để có thể mở rộng thành các lớp mới. Rõ ràng, không có cây con nào của một tiền tố không tồn tại được xét. Điểm mạnh của phương pháp lớp tương đương là không gian xử lí ban đầu được chia thành các phần nhỏ độc lập. Đối với mỗi nút gốc con của nút X, có thể xem như một vấn đề mới hoàn toàn; mỗi nút có thể sinh ra các itemset bên dưới. Hình 1.2. Cấu trúc IT-Tree của bảng 1.1 2. SO SÁNH Dựa vào tính chất Apriori, cả 2 đều áp dụng để tỉa các itemsets không cần thiết để giảm không gian tìm kiếm. IT-Tree cũng thoả tính Apriori. Như hình vẽ 1.2, ta thấy các nút con xuất hiện trên một tập giao tác nào đó thì các nút cha chắc chắn cũng sẽ xuất hiện trên tập giao tác đó. Ngược lại, nếu nút cha chỉ cần không xuất hiện trên 1 giao tác nào cả thì tập con – là tập cha hợp với 1 item nào đó – cũng sẽ không xuất hiện trên toàn cơ sở dữ liệu. Từ đó ta có thể tiên nghiệm được nhờ vào tính chất này để loại bỏ cả nhánh lớp tương đương có chứa tiền tố mà đã xác định là không xuất hiện trên cơ sở dữ liệu giao tác. 2.1. Ý tưởng tỉa itemsets giữa thuật toán Apriori và IT-Tree Giải thuật phổ biến nhất của loại này là giải thuật Apriori, trong đó có trình bày tính chặn dưới của itemset thỏa minsup. Giải thuật Apriori sử dụng các tính chất này bằng cách tỉa bớt những ứng viên thuộc tập không phổ biến trước khi tính độ phổ biến của chúng. Cách tối ưu có thể thực hiện được vì các giải thuật tìm kiếm ưu tiên theo chiều rộng (BFS) bảo đảm rằng các giá trị hỗ trợ của các tập của một ứng viên đều được biết trước. Giải thuật Apriori đếm tất cả các ứng viên có k phần tử trong một lần đọc CSDL. Phần cốt lõi của bài toán là xác định các ứng viên trong mỗi giao tác. Thuật toán Apriori tỉa các itemsets không phổ biến. IT-Tree áp dụng lí thuyết lớp tương đương, dựa vào hình vẽ 1.2 là minh hoạ của bảng cơ sở dữ liệu giao tác 1.1, ta thấy các lớp con của một lớp nào đó là: một itemsets gồm các item. Mỗi item xuất hiện trên một số giao tác, và tập các giao tác chứa item đó gọi là tập giao tác (tidset). Một itemset gồm nhiều item, nên tidset của itemset đó là phần giao của các tidset con. Do vậy, trên IT-Tree sẽ không xuất hiện những itemset mà có tập tidset rỗng, điều đó tương đương với việc itemset đó không xuất hiện trên CSDL và sẽ vô nghĩa khi xét đến nó. IT-Tree tỉa các itemsets không xuất hiện trên CSDL. 2.2. Điểm yếu của thuật toán Apriori và điểm mạnh của IT-Tree Như thuật toán Apriori trong hình 1.1, dòng 3 là thủ tục apriori_gen dùng để sinh các ứng viên. Thủ tục apriori_gen sinh ra tập ứng viên mới k-itemsets từ (k-1)-itemsets, tham khảo hình 2.1. Trong thủ tục này một (k-1)-itemsets kết nối với các item khác trong Lk-1 và tạo ra 1 ứng viên mới có k items và tính độ hỗ trợ của ứng viên đó. Nếu ứng viên nào thoả độ hỗ trợ thì lưu vào tập Ck. Để thấy rõ điểm yếu của thuật toán Apriori, giả sử thực hiện một bài toán có độ hỗ trợ tối thiểu (minsup) là 0. Lúc đó cơ sở dữ liệu có n item thì sẽ có 2n ứng viên, nếu n lớn thì số ứng viên quá lớn. Lý do là thủ tục apriori_gen luôn luôn phải thực hiện công việc kết nối, đối với các item vô nghĩa kết nối với (k-1)-itemsets cho ra một k-itemsets vô nghĩa. Sau đó còn phải tốn một thao tác để tính độ hỗ trợ cho itemsets vô nghĩa đó mới có thể xác định itemsets đó không thuộc tập Ck. Ngoài ra, nếu độ hỗ trợ tối thiểu minsup bị thay đổi thì thuật toán sẽ phải thực hiện lại từ đầu, điều này sẽ rất mất thời gian. Hình 2.1. Thủ tục apriori_gen Phương pháp IT-tree có một số điểm mạnh như sau: i) Đọc CSDL một lần và lưu vào tập [] = {1 – itemset}, vì khi sinh các tập phổ biến khác ở mức kế, thuật toán chỉ đơn giản hợp hai tập phổ biến ở mức trên lại thành tập mới, Tidset mới được tính bằng cách giao hai Tidset của các tập tạo ra nó. Như vậy, nếu dung lượng bộ nhớ đủ chứa thì phương pháp này chỉ cần đọc CSDL một lần. ii) Không cần phải sinh ứng viên như họ thuật toán Apriori. Điều này kéo theo không cần phải có thao tác tính độ hỗ trợ không cần thiết để xác định ứng viên đó có phổ biến hay không. Giả sử độ hỗ trơ tối thiểu (minsup) là 0 thì cũng không ảnh hưởng gì đến việc sinh ứng viên. iii) Có thể dùng thuật toán song song để khai thác tập phổ biến. 2,3. Ứng dụng trong bài toán tìm luật kết hợp Bài toán tìm luật kết hợp có 2 giai đoạn. Giai đoạn 1 tìm tập phổ biến, giai đoạn 2 tìm luật kết hợp từ các tập phổ biến đó. Trong việc tìm luật tập phổ biến có các thuật toán tiêu biểu sau Apriori, Apriori-Gen, Apriori-Tid, FP-Growth (2,7). Bài toán luật kết hợp [8,9,10,11,12] Cho một tập các giá trị I, một cơ sở dữ liệu giao dịch D, độ hỗ trợ tối thiểu minsup, độ tin cậy mincof, tìm các luật kết hợp dạng X  Y trên D thoả mãn điều kiện Support(X  Y) ≥ minsup và Confidence(X  Y) ≥ mincof.  Xác định các tập phổ biến: Việc xác định các tập phổ biến gồm có hai bước chính sau đây: - Xác định các tập ứng viên (Ck). - Xác định các tập phổ biến (L) dựa vào tập ứng viên Để xác định tập ứng viên, ta thực hiện các bước sau đây: - Tìm các tập ứng viên một itemset. - Quét CSDL D để xác định độ hỗ trợ của các tập ứng cử viên. Trong vòng đầu tiên, các tập ứng cử viên cũng chính là tất cả các mục có trong CSDL. Tại vòng thứ k (k>1), các tập ứng cử viên được xác định dựa vào các tập phổ biến đã xác định tại vòng k – 1, sử dụng hàm Apriori-gen() (2). Sau khi đã xác định được các tập ứng cử viên, thuật toán quét từng giao dịch trong CSDL để tính độ hỗ trợ của các tập ứng cử viên. Quá trình xác định các tập phổ biến sẽ kết thúc khi không xác định được thêm tập phổ biến nào nữa. Nội dung hàm Apriori-gen(). Hàm Apriori-gen() thực hiện hai bước (2,9): - Bước đầu tiên, Lk – 1 được kết nối với chính nó thu được Ck. - Bước thứ hai, Apriori_gen() xoá tất cả các itemsets từ kết quả kết nối mà có một số tập con (k – 1) không có trong Lk – 1. Sau đó nó trả về itemsets phổ biến kích thước k còn lại.  Sinh các luật kết hợp từ tập phổ biến: Việc phát hiện các tập phổ biến rất tốn kém về mặt tính toán. Tuy nhiên, ngay khi tìm được tất cả các tập phổ biến (l  L), ta có thể dễ dàng sinh ra các luật kết hợp có thể có bằng các bước như sau: - Tìm tất cả các tập con không rỗng x, của tập phổ biến l  L. - Với mỗi tập con x tìm được, ta xuất ra luật dạng x  (l - x) nếu tỉ lệ Support(l)/Support(x) ≥ mincof ( %).  Ứng dụng IT-Tree trong giai đoạn xác định tập phổ biến: Nhận xét thấy chỉ có những itemset nào có tập giao tác khác rỗng thì mới có thể xuất hiện trong giao tác, lúc đó mới tính độ hỗ trợ và so sánh với minsup. Còn lại những itemset có tập giao tác bằng rỗng thì không xuất hiện trong cơ sở dữ liệu đó. Ví dụ một tập các món hàng mà không được bán lần nào hết thì tập món hàng đó không xuất hiện trong hoá đơn bán hàng. Do vậy ta có thể tỉa bớt những tập đó trong quá trình sinh tập k-itemsets từ tập (k-1)-itemsets để giảm bớt không gian xử lí. Để ứng dụng IT-Tree ta cần thay thế hàm Apriori_gen trong thuật toán Apriori thành hàm IT_Tree, như trong hình 2.2, để sinh ra một k-itemset từ hai (k-1)-itemsets ta cần phải xét đến hai yếu tố: 1. Hai (k-1)-itemsets phải cùng tiền tố 2. Giao hai tập giao tác của hai (k-1)-itemsets, nếu tập giao khác rỗng thì k-itemset được thêm vào tập Ck. Hình 2.2: Hàm IT_Tree tìm itemsets phổ biến Trong hàm IT_Tree [1,3,4,5,12] gọi    nlllP ,...,, 21 là lớp tương đương, trong đó P là nút cha và mỗi li là một mục dữ liệu đơn, đại diện cho nút )( ii PltPl  . Dòng 9 gọi đệ quy lại hàm IT_Tree để tính tiếp cho lớp tương đương tính từ nút [Pi]. 3. KẾT LUẬN IT-Tree là hình ảnh minh họa trường hợp tổng quát của thuật toán Apriori. Nhưng với tổ chức như IT-Tree, ta có thể đọc CSDL chỉ một lần và sử dụng tập tidset để tính độ hỗ trợ nếu cần. Để giải quyết một thuật toán hiệu quả về khai thác itemsets trên CSDL lớn, ta cần phải quan tâm đến 2 vấn đề: - Rút gọn không gian tìm kiếm - Giảm thiểu việc đọc thông tin từ cơ sở dữ liệu IT-Tree có thể xem là cấu trúc dữ liệu lí tưởng để cải tiến được những thuật toán có liên quan đến khai thác itemsets, nên nó là công cụ hữu ích nếu chúng ta làm việc với các vấn đề khai thác luật kết hợp và khai thác itemsets có ích. Thuật toán IT-Tree có thể thay thế hoàn toàn các thuật toán họ Apriori để thực hiện tối ưu giai đoạn tìm itemsets theo một tiêu chí nào đó, ví dụ như độ hỗ trợ và độ có ích. Chúng tôi đã tiến hành thử nghiệm thuật toán khai thác các itemsets phổ biến trên một số CSDL giao tác tạo được bằng phương pháp tạo ma trận số ngẫu nhiên. Căn cứ vào các kết quả thử nghiệm và việc phân tích cấu trúc thuật toán, chúng tôi nhận thấy thực hiện theo IT-Tree có những ưu điểm vượt trội so với các thuật toán họ Apriori. Ngoài ra, tính chất Apriori kết hợp với ý tưởng IT-Tree còn có thể áp dụng được trong bài toán khai thác đồ thị con phổ biến là bài toán được nhiều người quan tâm và nghiên cứu trong lĩnh vực khai thác dữ liệu. CHÚ THÍCH 1. IT_Tree([P], minsup) 2. for all li  [P] do 3. [Pi] =  4. for all lj  [P], with j > i do 5. I = lj 6. T = t(li)  t(lj) 7. if Pi .Support()  minsup then 8. [Pi] = [Pi]  { TI  } 9. IT_Tree ([Pi], minsup) [1]. Các từ khoá: tập phổ biến, IT-Tree, tập có ích, itemsets TÀI LIỆU THAM KHẢO 1. Nguyễn Quốc Huy (2008) , “Khai thác itemsets có ích từ cơ sở dữ liệu”, Luận văn thạc sĩ Tin học, ĐH KHTN, ĐHQG TP.HCM. 2. Nguyễn Thanh Thuỷ, Khai phá dữ liệu – Kĩ thuật và ứng dụng. Bài giảng trường thu Hệ mờ và ứng dụng, Hà Nội, tháng 8-2001. 3. Le, B., Nguyen, H., Cao, T.A.,Vo, B.: A Novel Algorithm for Mining High Utility Itemsets. In: IEEE 1 st Asian Conference on Intelligent Information and Database Systems, April 1- 3, 2009, Quang Binh, Vietnam, pp. 13 - 17 (2009). 4. Bac Le., Huy Nguyen., Bay Vo.: Mining high Utility Itemsets from Vertical distributed Databases. In: IEEE RIFV’09, July, 2009, Danang, Vietnam. 5. Bac Le., Tu Bao Ho., Huy Nguyen., Bay Vo.: Parallel Method for Mining High Utility Itemsets from Vertically Partitioned Distributed Databases. In: Springer KES’09, Sep, 2009, Santiago, Chile. 6. C. J. Matheus and P. K. Chan and G. Piatetsky-Shapiro, Systems for knowledge discovery in databases, Ieee Trans. On Knowledge And Data Engineering, vol 5, pp 903-913, 1993 url= 7. Christian Borgelt and Rudolf Kruse, Department of Knowledge Processing and Language Engineering School of Computer Science. Induction of Association Rules: AprioriImplementation.Otto-von-Guericke-UniversityofMagdeburg Universităatsplatz 2, D- 39106 Magdeburg, Germany. 8. Jiawei Han and Yongjian Fu, Dynamic Generation and Refinement of Concept Hierarchies for Knowledge Discovery in Databases,KDD Workshop, pp 157-168, 1994, url= 9. Jiawei Han, Jian Pei, Yiwen Yin. Mining Frequent Patterns without Candidate Generation. SIGMOD Conference 2000. 10. Jiawei Han and Micheline Kamber, Data mining: Concepts and Techniques. Academic Press 2001. 11. J. Han, Y. Cai, and N. Cercone. Data-driven Discovery of Quantitative Rules in Relational Databases. IEEE Trans. Knowledge and Data Eng., 5:29--40, 1993. url= 12. R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In Proc. 1994 Int.Conf.VLDB,Santiago,Chile,Sept.1994. rl=citeseer.nj.nec.com/article/agrawal94fast.html