Tiểu luận Tìm hiểu luật kết hợp trong khai phá dữ liệu

iao dịch hỗ trợ X trên tổng các giao dịch trong D, nghĩa là: (2.1) Độ hỗ trợ tối thiểu minsup là một giá trị cho trước bởi người sử dụng. Nếu tập mục X có sup(X) ³ minsup thì ta nói X là một tập các mục phổ biến. Một tập phổ biến được sử dụng như một tập đáng quan tâm trong các thuật toán, ngược lại, những tập không phải tập phổ biến là những tập không đáng quan tâm. Các phần sau sẽ sử dụng những cụm từ khác như “X có độ hỗ trợ tối thiểu”, hay “X không có độ hỗ trợ tối thiểu” cũng để nói lên rằng X thỏa mãn hay không thỏa mãn support(X) ³ minsup. ®Một khoản mục X được gọi là k-itemset nếu lực lượng của X bằng k, tức là |X|=k. Một luật kết hợp có dạng R: X => Y, trong đó X, Y là tập các mục, X, Y Í I và X ÇY = Æ. X được gọi là tiên đề và Y được gọi là hệ quả của luật. Luật X => Y tồn tại một độ tin cậy c . Độ tin cậy c được định nghĩa là khả năng giao dịch T hỗ trợ X thì cũng hỗ trợ Y. Ta có công thức tính độ tin cậy c như sau: (2.2) Tuy nhiên, không phải bất cứ luật kết hợp nào có mặt trong tập các luật có thể được sinh ra cũng đều có ý nghĩa trên thực tế. Mà các luật đều phải thoả mãn một ngưỡng hỗ trợ và tin cậy cụ thể. Thực vậy, cho một tập các giao dịch D, bài toán phát hiện luật kết hợp là sinh ra tất cả các luật kết hợp mà có độ tin cậy conf lớn hơn độ tin cậy tối thiểu minconf và độ hỗ trợ sup lớn hơn độ hỗ trợ tối thiểu minsup tương ứng do người dùng xác định. Khai phá luật kết hợp được phân thành hai bài toán con: Bài toán 1: Tìm tất cả các tập mục mà có độ hỗ trợ lớn hơn độ hỗ trợ tối thiểu do người dùng xác định. Các tập mục thoả mãn độ hỗ trợ tối thiểu được gọi là các tập mục phổ biến. Bài toán 2: Dùng các tập mục phổ biến để sinh ra các luật mong muốn. Ý tưởng chung là nếu gọi ABCD và AB là các tập mục phổ biến, thì chúng ta có thể xác định luật nếu AB => CD giữ lại với tỷ lệ độ tin cậy: (2.3) Nếu conf ≥ minconf thì luật được giữ lại (luật này sẽ thoả mãn độ hỗ trợ tối thiểu vì ABCD là phổ biến). 2.2. Một số tính chất liên quan đến các hạng mục phổ biến: 2.2.1. Tập mục phổ biến: Tính chất 1 (Độ hỗ trợ của tập con): Với A và B là tập các mục, nếu A Í B thì sup(A) ³ sup(B) Điều này là rõ ràng vì tất cả các giao tác của D hỗ trợ B thì cũng hỗ trợ A. Tính chất 2: Một tập chứa một tập không phổ biến thì cũng là tập không phổ biến. Nếu một mục trong B không có độ hỗ trợ tối thiểu trên D nghĩa là sup(B)< minsup thì một tập con A của B sẽ không phải là một tập phổ biến vì support(B) £ support(A) < minsup (theo tính chất 1) Tính chất 3: Các tập con của tập phổ biến cũng là tập phổ biến Nếu mục B là mục phổ biến trên D, nghĩa là support(B) ³ minsup thì mọi tập con A của B là tập phổ biến trên D vì support(A) ³ support(B) > minsup. 2.2.2. Luật kết hợp: Tính chất 1:( Không hợp các luật kết hợp) Nếu có X®Z và Y®Z trong D thì không nhất thiết XÈY®Z là đúng Xét trường hợp X ÇZ =Æ và các tác vụ trong D hỗ trợ Z nếu và chỉ nếu chúng hỗ trợ mỗi X hoặc Y, khi đó luật XÈY®Z có độ hỗ trợ 0%. Tương tự : X®Y Ù X®Z Þ X®YÈZ Tính chất 2:(Không tách luật) Nếu XÈY®Z thì X®Z và Y®Z chưa chắc xảy ra Ví dụ trường hợp Z có mặt trong một giao tác chỉ khi cả hai X và Y cũng có mặt, tức là sup(XÈY)= sup(Z), nếu độ hỗ trợ của X và Y đủ lớn hơn sup(XÈY), tức là sup(X) > sup(XÈY) và sup(Y) > sup(XÈY) thì hai luật riêng biệt sẽ không đủ độ tin cậy Tuy nhiên đảo lại: X®YÈZ Þ X®Y Ù X®Z Tính chất 3: (Các luật kết hợp không có tính bắc cầu) Nếu X®Y và Y®Z, chúng ta không thể suy ra X®Z. Ví dụ: giả sử T(X) Ì T(Y) Ì T(Z), ở đó T(X), T(Y), T(Z) tương ứng là các giao dịch chứa X,Y,Z, và độ tin cậy cực tiểu minconf conf(X®Y) =conf(Y®Z)=minconf thế thì: conf(X®Y) =minconf2 < minconf vì minconf < 1, do đó luật X®Z không đủ độ tin cậy Tính chất 4: Nếu A®(L - A) không thoả mãn độ tin cậy cực tiểu thì luật B ®(L -B) cũng không thoả mãn, với các tập mục L,A,B và B Í A Ì L Vì supp(B) ³ sup(A) (theo tính chất 1) và định nghĩa độ tin cậy, chúng ta nhận được: (2.4) Cũng như vậy: Nếu có (L-C)® C thì ta cũng có luật (L – D)®D, với DÍC và D¹Æ. Bởi vì DÍC nên (L - D) Ê (L - C), do đó sup(L - D) £ sup(L-C) Þ³ minconf (2.5) Các tính chất này sẽ được sử dụng trong thuật toán mô tả trong các chương sau. 2.3. Một số hướng tiếp cận trong khai phá luật kết hợp Lĩnh vực khai thác luật kết hợp cho đến nay đã được nghiên cứu và phát triển theo nhiều hướng khác nhau. Có những đề xuất nhằm cải tiến tốc độ thuật toán, có những đề xuất nhằm tìm kiếm luật có ý nghĩa hơn… và có một số hướng chính như sau: Luật kết hợp nhị phân là hướng nghiên cứu đầu tiên của luật kết hợp. Hầu hết các nghiên cứu ở thời kỳ đầu về luật kết hợp đều liên quan đến luật kết hợp nhị phân. Trong dạng luật kết hợp này, các mục, thuộc tính, chỉ được quan tâm là có hay không xuất hiện trong giao tác của CSDL chứ không quan tâm về “mức độ” xuất hiện. Ví dụ: Trong hệ thống tính cước điện thoại thì việc gọi 10 cuộc điện thoại và một cuộc được xem là giống nhau. Thuật toán tiêu biểu nhất khai phá dạng luật này là thuật toán Apriori và các biến thể của nó. Đây là dạng luật đơn giản và các luật khác cũng có thể chuyển về dạng luật này nhờ một số phương pháp như rời rạc hoá, mờ hoá, … Một ví dụ về dạng luật này: “gọi liên tỉnh= ‘yes’ AND gọi di động= ‘yes’ => gọi quốc tế= ‘yes’ AND gọi dịch vụ 108 = ‘yes’, với độ hỗ trợ 20% và độ tin cậy 80%” Luật kết hợp có thuộc tính số và thuộc tính hạng mục: Các thuộc tính của các CSDL thực tế có kiểu rất đa dạng, như số nhị phân, giá trị định tính, định lượng... Để phát hiện luật kết hợp với các thuộc tính này, các nhà nghiên cứu đã đề xuất một số phương pháp rời rạc hoá nhằm chuyển dạng luật này về dạng nhị phân để có thể áp dụng các thuật toán đã có. Một ví dụ về dạng luật này “phương thức gọi = ‘Tự động’ AND giờ gọi IN [‘23:00:39.. 23:00:59’] AND Thời gian đàm thoại IN [‘200.. 300’] => gọi liên tỉnh = ‘có’ , với độ hỗ trợ là 23. 53% , và độ tin cậy là 80%”. Luật kết hợp tiếp cận theo hướng tập thô: Tìm kiếm luật kết hợp dựa trên lý thuyết tập thô. Luật kết hợp nhiều mức: Cách tiếp cận theo luật này sẽ tìm kiếm thêm những luật có dạng “mua máy tính PC => mua hệ điều hành AND mua phần mềm tiện ích văn phòng, …” thay vì chỉ những luật quá cụ thể như “mua máy tính IBM PC => mua hệ điều hành Microsoft Windows AND mua phần mềm tiện ích văn phòng Microsoft Office, …”. Như vậy dạng luật đầu là dạng luật tổng quát hoá của dạng luật sau và tổng quát theo nhiều mức khác nhau. Luật kết hợp mờ: Với những hạn chế còn gặp phải trong quá trình rời rạc hoá các thuộc tính số (quantitave attributes), các nhà nghiên cứu đã đề xuất luật kết hợp mờ nhằm khắc phục các hạn chế trên và chuyển luật kết hợp về một dạng tự nhiên hơn, gần gũi hơn với người sử dụng một ví dụ của dạng này là: “thuê bao tư nhân = ‘yes’ AND thời gian đàm thoại lớn AND cước nội tỉnh = ‘yes’ => cước không hợp lệ = ‘yes’, với độ hỗ trợ 4% và độ tin cậy 85%”. Trong luật trên, điều kiện thời gian đàm thoại lớn ở vế trái của luật là một thuộc tính đã được mờ hoá. Luật kết hợp với thuộc tính được đánh trọng số: Trong thực tế, các thuộc tính trong CSDL không phải lúc nào cũng có vai trò như nhau. Có một số thuộc tính được chú trọng hơn và có mức độ quan trọng cao hơn các thuộc tính khác. Ví dụ khi khảo sát về doanh thu hàng tháng, thông tin về thời gian đàm thoại, vùng cước là quan trọng hơn nhiều so với thông tin về phương thức gọi... Trong quá trình tìm kiếm luật, chúng ta sẽ gán thời gian gọi, vùng cước các trọng số lớn hơn thuộc tính phương thức gọi. Đây là hướng nghiên cứu rất thú vị và đã được một số nhà nghiên cứu đề xuất cách giải quyết bài toán này. Với luật kết hợp có thuộc tính được đánh trọng số, chúng ta sẽ khai thác được những luật “hiếm” (tức là có độ hỗ trợ thấp, nhưng có ý nghĩa đặc biệt hoặc mang rất nhiều ý nghĩa). Luật kết hợp song song: Bên cạnh khai thác luật kết hợp tuần tự, các nhà làm tin học cũng tập trung vào nghiên cứu các thuật giải song song cho quá trình phát hiện luật kết hợp. Nhu cầu song song hoá và xử lý phân tán là cần thiết bởi kích thước dữ liệu ngày càng lớn hơn nên đòi hỏi tốc độ xử lý cũng như dung lượng bộ nhớ của hệ thống phải được đảm bảo. Có rất nhiều thuật toán song song khác nhau đã đề xuất để có thể không phụ thuộc vào phần cứng. Bên cạnh những nghiên cứu về các biến thể của luật kết hợp, các nhà nghiên cứu còn chú trọng đề xuất những thuật toán nhằm tăng tốc quá trình tìm kiếm tập phổ biến từ CSDL. Ngoài ra, còn có một số hướng nghiên cứu khác về khai thác luật kết hợp như: khai thác luật kết hợp trực tuyến, khai thác luật kết hợp được kết nối trực tuyến đến các kho dữ liệu đa chiều thông qua công nghệ OLAP, MOLAP, ROLAP, ADO. 2.4. Phát hiện luật kết hợp trên hệ thông tin nhị phân 2.4.1. Các định nghĩa về hệ thông tin nhị phân Hệ thông tin nhị phân Cho các tập O ={o1, o2, …, on} là một tập hữu hạn gồm n đối tượng, D = {d1, d2, …, dm} là một tập hữu hạn gồm m chỉ báo, B = {0, 1} Hệ thông tin nhị phân được định nghĩa là SB = (O, D, B, c) trong đó c là ánh xạ c:O x D → B, c(o,d) = 1 nếu đối tượng o có chỉ báo d và c(o,d) = 0 nếu ngược lại. Các ánh xạ thông tin nhị phân Cho hệ thông tin nhị phân SB = (O, D, B, c). Cho P(O) là các tập con của O, P(D) là các tập con của D. Các ánh xạ thông tin nhị phân rB và lB được định nghĩa như sau: rB: P(D) ® P(O) với ý nghĩa: cho S Ì D, rB(S) = {o Î O| " d Î S, c(o, d) = 1} lB: P(O) ® P(D) với ý nhĩa: cho X Ì O, lB(X) = {d Î D| " o Î X, c(o, d) = 1} Tập chỉ báo phổ biến nhị phân Cho hệ thông tin nhị phân SB = (O, D, B, c) và một ngưỡng q Î (0, 1). Cho S Í D, S là tập chỉ báo phổ biến nhị phân với ngưỡng q nếu card(rB(S)) ≥ q*card(O) Cho LB là một tập gồm tất cả các tập chỉ báo phổ biến nhị phân đã phát hiện từ SB, chúng có thuộc tính như sau: "S Î LB, T Ì S thì T Î LB. Trong đó LB,h là tập con của LB nếu XÎLB,h thì card(X)=h (với h là số nguyên dương). Các luật kết hợp phổ biến nhị phân và hệ số tin cậy Cho hệ thông tin nhị phân SB = (O, D, B, c) và một ngưỡng q Î (0, 1). Cho L là một phần tử của LB, X và Y là hai tập con của L, trong đó: L = X È Y, X ≠ {}, Y ≠ {} và X Ç Y = {} Chúng ta xác định các luật kết hợp nhị phân giữa tập chỉ số X và tập chỉ số Y là một ánh xạ thông tin: X ® Y. Hệ số tin cậy của luật này được biểu diễn là: (2.6) Gọi RB,b là tập tất cả các luật kết hợp phổ biến nhị phân được phát hiện từ SB. Trong đó CFB(r) ≥ b, " r Î RB,b[11,15] Các vectơ chỉ báo nhị phân và các phép toán Cho hệ thông tin nhị phân SB = (O, D, B, c) trong đó O ={o1, o2, …, on} là một tập hữu hạn gồm n đối tượng, D = {d1, d2, …, dm} là một tập hữu hạn gồm m chỉ báo. Vectơ chỉ báo nhị phân: vB(X) = {X1, X2, … , Xn} trong đó: X Ì D là một vectơ với n thành phần, mỗi thành phần Xj chiếm một giá trị trong B. Cho VSB là tập tất cả các vectơ chỉ báo nhị phân của SB, nếu card(X) = 1 thì X là bộ chỉ báo của SB và Xj = c(o, X) Tích vectơ chỉ báo nhị phân: Cho X1, X2 Ì D, vB(X1) = (X11, X12, … , X1n), vB(X2) = (X21, X22, … , X2n) là các phần tử của VSB. Tích vectơ chỉ báo nhị phân vB(X1) và vB(X2) được biểu hiện là vB(X3) = vB(X1) QB vB(X2). Trong đó: vB(X3) = (X31, X32, … , X3n) với X3j = min(X1j, X2j), j = 1¸n X3 = X1 È X2 Î D Từ vectơ vB(X3), biết tất cả các đối tượng hiện có trong tập chỉ báo X1 và X2. Chúng ta dùng vB(X1) để trình diễn rB(X1), vB(X2) để trình diễn rB(X2) và vB(X3) để trình diễn rB(X3). Độ hỗ trợ các vectơ chỉ báo nhị phân Cho X1 Ì D, độ hỗ trợ của vB(X1) biểu diễn supB(vB(X1)) được định nghĩa là: supB(vB(X1)) = {o Ì O| "d Î X1, c(o, d) = 1} (2.7) Dễ thấy rằng: card(supB(vB(X1))) = card(rB(X1)) Tính card(rB(S)) (lực lượng của tập hợp): Cho S = {s1, s2, … , sk} là tập con của D. Trong đó sj là bộ chỉ báo của SB, j = 1 ¸ k. Mỗi sj tương ứng với vectơ chỉ báo nhị phân vB({sj}). Các yếu tố của rB(S) được tính bằng card(rB(S)) = card(supB(vB{s1}) QB supB(vB{s2}) QB … supB(vB{sk})) (2.8) Kí hiệu VSB, h là tập con của VSB chứa chỉ vectơ vB(X) trong đó X Ì D và card(X) = h (h là số nguyên dương cho trước). 2.4.2. Thuật toán phát hiện tập chỉ mục và luật kết hợp nhị phân Thuật toán phát triển từ thuật toán Apriori-Tid. Để phát hiện các tập chỉ báo nhị phân phổ biến từ các luật kết hợp nhị phân từ hệ thông tin nhị phân. Thuật toán này làm việc với các bit trong bộ nhớ và không làm việc với CSDL trên đĩa, vì thế có thể cải tiến tốc độ quá trình phát hiện luật. Cho một CSDL và hai ngưỡng độ hỗ trợ tối thiểu minsup và độ tin cậy tối thiểu minconf của luật kết hợp. Thuật toán Apriori-Tid có hai pha: Pha 1: Phát hiện các tập chỉ báo phổ biến dựa trên ngưỡng minsup cho trước. Pha 2: Xây dựng các luật kết hợp dựa trên một ngưỡng minconf cho trước. Cho ma trận thông tin nhị phân SB = (O, D, B, c) và một ngưỡng q, b Î(0, 1). Trong đó q là minsup và b là minconf. Chi tiết thuật toán Apriori-Tid như sau: Pha 1: Phát hiện tập chỉ mục phổ biến nhị phân 1. TraLoi = Æ ; 2. Sinh LB,1 từ SB theo thủ tục 1.a. dưới đây ; 3. for (k = 2; LB,k {}; k++) 4.{ Sinh LB,k từ LB,k-1 theo thủ tục 2.a. dưới đây ; 5. TraLoi = Èk LB,k-1 ; 6. } 7. Return TraLoi ; 1.a. Sinh LB,1 1. LB,1 = Æ ; 2. for (i = 1; i <= m; i++) 3. if(card(supB(vB({di}))) > q * card(O)) 4. {SaveLargeSet({di}, VSB,1) ; 5. SaveDescriptorVector(vB({di}, VSB,1)) ; 6. } 7. TraLoi = LB,1 ; 8. Return TraLoi ; // Trong đó m = card(D) là lực lượng của lập D. 2.a. Sinh LB,k Dựa trên thuộc tính "S Î LB, T Ì S thì T Î LB, chúng sinh ra LB,k từ LB,k-1. Kết quả như sau: Tạo một ma trận có các dòng và cột là các thành phần của LB, k-1 1. LB,k = Æ ; 2. for (Mỗi X Î LB,k-1 && XY) 3. {T = X È Y ; 4. if(card(supB(vB(T)) > q*card(O)) && card(T) ==k) 5. {SaveLargeSet(T, LB,k) ; 6. SaveDescriptorVector(vB(T), VSB,k)) ; 7. }} 9. TraLoi = LB,k ; 10. Return TraLoi ; Trong đó: SaveLargeSet(T, LB,k) là một hàm để ghi một tập chỉ báo phổ biến nhị phân T vào LB,k. SaveDescriptorVector(vB(T), VSB,k)) là một hàm để lưu một vectơ chỉ báo phổ biến nhị phân vB(T) vào VSB,k. Dựa vào (1) và (2), ta có thể tính rất nhanh supB(vB(T)) tại bước thứ k của vòng lặp ở trên, từ các phần tử của VSB,k-1. Pha 2: Phát hiện các luật phổ biến nhị phân 1. RB,b = Æ ; // Khởi tạo tập luật ban đầu là rỗng 2. for (Mỗi L Î LB) 3. { for(Mỗi X, Y Î L và XÇY ={}) 4. { if(CFB(X=>Y) ³ b) 5. SaveRule(X=>Y, RB,b); // ghi luật X=>Y vào RB,b 6. if(CFB(Y=>X) ³ b) 7. SaveRule(Y=>X, RB,b); // ghi luật Y=>X vào RB,b 8. } 9. } 10. TraLoi = RB,b ; 11. Return RB,b ; // Kết thúc III. MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP 1. Thuật toán Apriori 1.1. Ý tưởng thuật toán Apriori Apriori là một thuật giải được do Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất lần đầu vào năm 1993. Thuật toán tìm giao dịch t có độ hỗ trợ và độ tin cậy thoả mãn lớn hơn một giá trị ngưỡng nào đó. Thuật toán được tỉa bớt những tập ứng cử viên có tập con không phổ biến trước khi tính độ hỗ trợ. Thuật toán Apriori tính tất cả các tập ứng cử của tập k trong một lần duyệt CSDL. Apriori dựa vào cấu trúc cây băm. Tìm kiếm đi xuống trên cấu trúc cây mỗi khi ta chạm lá, ta tìm được một tập ứng cử viên có tiền tố chung được bao gồm trong giao dịch. Sau đó các tập ứng cử này được tìm trong giao dịch đã được ánh xạ trước đó. Trong trường hợp tìm thấy biến đếm được tăng lên 1. Ký hiệu: Giả sử các mục trong mỗi giao dịch được lưu giữ theo trật tự từ điển. Gọi số các mục trong một tập mục là kích thước của nó và gọi tập mục có kích thước k là tập k-mục (tập k mục). Các mục trong mỗi tập mục cũng được giữ ở trật tự từ điển. Ta sử dụng các ký hiệu sau: Lk: Tập các tập k-mục phổ biến (với độ hỗ trợ cực tiểu minsup nào đó) Ck : Tập các tập k-mục ứng cử (các tập mục phổ biến tiềm năng) 1.2. Thuật toán Apriori Input: CSDL D, minsup. Output: Tập các tập mục phổ biến. 1. L1 = {Các 1 - itemset phổ biến}; 2. k=2; 3. While( Lk-1! =Æ ) 4. { Ck = apriori_gen(Lk-1, minsup);// các ứng cử mới theo chương trình con ở dưới đây. 5. for( " giao dịch tÎ D) 6. { Ct=Subset (Ck,t);// ứng cử viên được chứa trong t 7. for (" ứng cử c Î Ct) 8. c.count ++; 10. } 11. Lk={ c Î Ck÷ c.count ³ minsup} 12. k++; 13. } 14. Return L= ÈkLk' ; // sinh ứng cử viên mới (**) Void apriori_gen(Lk-1, minsup ) 1. { for (" itemset l1Î Lk-1) 2. for (" itemset l2Î Lk-1) 3. if((L1(1)== L2(1)&&L1(2) == L2(2)&&...&& L1(k-2) == L2(k-2)) &&L1(k-1) == L2(k-1)) 4. { c= L1 kết nối L2; 5. if( has_inrequent_subset(c, Lk-1)) delete c; 6. else add c to Ck; 7. } 8. return Ck 9.} Boolean has_infrequent_subset(c,Lk-1) 1.{ for (" (k-1)-subset sÎ c) 2. if(s Ï Lk-1) return TRUE; 3. else return FALSE ; 4.} Giải thích: Lần duyệt đầu tiên, sẽ tính số lần xuất hiện của mỗi mục để xác định các 1- itemset phổ biến. Lần duyệt thứ k (k ³ 2) sẽ bao gồm 2 giai đoạn: Tập phổ biến Lk-1 đã tìm thấy ở lần duyệt thứ k-1 được sử dụng để sinh ra các tập ứng cử viên Ck bằng việc sử dụng hàm Apriori_gen. Dựa vào CSDL, tính độ hỗ trợ của các ứng của viên trong Ck. Các ứng cử viên trong Ck mà được chứa trong giao dịch t có thể được xác định một cách hiệu quả bằng việc sử dụng cây băm được mô tả như sau: Trong giai đoạn 2 (giai đoạn sửa, tỉa): xoá bỏ các tập c Î Ck sao cho một vài (k-1) – tập con của c không nằm trong Lk-1. Thủ tục này là đầy đủ bởi đối với bất kì tập nào Lk với độ hỗ trợ tối thiểu thì các tập con kích cỡ (k-1) cũng có độ hỗ trợ tối thiểu, do đó nếu ta mở rộng mỗi tập trong Lk-1 với tất cả các tập mục có thể và sau đó xoá tất cả các tập mà (k-1) – tập con của nó không nằm trong Lk-1, ta sẽ nhận được tập các tập trong Lk. Việc kết nối là tương đương với việc mở rộng Lk-1 với mỗi mục nằm trong CSDL và sau đó xoá bỏ các tập này mà đối với nó (k-1) –itemset nhận được bằng việc xoá đi mục thứ (k-1) không nằm trong Lk-1. Ở giai đoạn này Ck Ê Lk . Với lập luận như vậy, giai đoạn tỉa là giai đoạn người ta xoá khỏi Ck tất cả các tập mà các (k-1) tập con của nó không nằm trong Lk-1 , cũng không xoá bất kỳ một tập nào có thể nằm trong Lk. Hàm Subset: Các tập ứng cử viên Ck được lưu trữ trong một cây băm. Một nút của cây này hoặc là chứa một danh sách của các tập (nút lá) hoặc bảng băm ( một nút trong). Trong mỗi một nút trong, mỗi cụm (bucket) của bảng băm chỉ đến một nút khác. Gốc của cây băm được xem ở độ sâu là 1. Một nút trong ở độ sâu d sẽ dẫn đến nút ở độ sâu d+1. Các tập được lưu trữ trong các lá. Khi ta bổ sung thêm một tập c, ta bắt từ nút gốc và đi xuống cây cho đến khi ta chạm vào một lá. Tại một nút ở độ sâu d, ta quyết định sẽ đi theo cành nào bằng việc áp dụng hàm băm đối với mục thứ d của tập đó và theo con trỏ trong Bucket tương ứng. Tất cả các nút ban đầu được tạo ra như là nút lá. Khi số các tập trong một nút lá vượt quá ngưỡng được chọn, nút lá này được chuyển thành một nút trong. Bắt đầu từ nút gốc, hàm Subset tìm tất cả các ứng cử viên được chứa trong giao dịch t như sau: Nếu ta bắt đầu tại một lá, ta tìm những tập trong nút lá này được chứa trong giao dịch t và bổ sung các mối quan hệ với chúng đối với tập kết quả mong muốn. Nếu ta đang ở một nút trong và ta đến được nó bằng việc băm mục i, ta băm trên mỗi mục đi sau i trong t và áp dụng một cách đệ quy thủ tục đó đối với nút này trong Bucket tương ứng. Đối với nút gốc, ta băm theo mỗi mục trong t. Để thấy được tại sao hàm Subset trả lại tập các tham khảo mong muốn hãy để ý đến những gì sẽ xảy ra tại nút gốc. Đối với bất kỳ tập c nào được chứa trong giao dịch t, mục đầu tiên cần phải có trong t. Tại nút gốc, việc băm mọi mục trong t đảm bảo được rằng ta chỉ không biết các tập mà nó bắt đầu với một mục không nằm trong t. Những lí luận tương tự áp dụng cho các mức sâu hơn. Vì các mục trong bất kì tập nào cũng được sắp thứ tự, nếu ta đến được một nút hiện tại bằng việc băm mục i, ta chỉ cần quan tâm đến những mục trong t nó xuất hiện sau i. // Bước tỉa: Xoá bớt tất cả các tập mục c Î Ck mà (k-1) tập con của c không phụ thuộc Lk-1. 1. for (" tập mục c Î Ck) 2. for (" (k-1) – tập con s của c) 3. if(s Ï Lk-1) 4. delete c khỏi Ck; Nhận xét: Thuật toán Apriori với n là độ dài lớn nhất của tập được sinh ra. Vậy thì thuật toán sẽ thực hiện duyệt toàn bộ các giao tác n+1 lần. Như vậy, nếu bỏ qua thời gian so sánh tìm sự xuất hiện của một mẫu trong một giao tác thì độ phức tạp của thuật toán Apriori là O(A) > O(n*L) trong đó L là kích thước CSDL còn n là độ dài cần đạt được của các mẫu. 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. Thuật toán Apriori được xây dựng nhằm phát hiện các luật kết hợp giữa các đối tượng với độ hỗ trợ và độ tin cậy tối thiểu. 1.3. Sinh các luật kết hợp từ tập mục phổ biến: Sau khi các tập mục phổ biến từ các tác vụ trong CSDL đã được tìm thấy, nó có thể sinh ra các luật kết hợp mạnh, ở đó luật kết hợp mạnh (strong association rule) là luật thoả mãn cả hai độ hỗ trợ cực tiểu và độ tin cậy cực tiểu. Điều đó có thể thực hiện bằng việc sử dụng tính độ tin cậy của luật, ta nhắc lại: độ tin cậy của luật X ® Y là: conf (X ® Y) = P(Y/X) = sup(XÈY)/sup(X) ở đó sup(XÈY) là độ hỗ trợ của XÈY và sup(X) là độ hỗ trợ của X. Có thể coi tỷ số trên là tỷ số giữa: số các tác vụ chứa XÈY và số các tác vụ chứa X. Dựa trên biểu thức tính toán đó, các luật kết hợp có thể được sinh như sau: Với mỗi tập mục phổ biến l, sinh ra tất cả các tập con không rỗng của l Với mỗi tập con không rỗng a của l, ta có luật a ® (l-a) nếu ³ minconf ở đó minconf là ngưỡng độ tin cậy cực tiểu Vì các luật được sinh ra từ các tập mục phổ biến nên độ hỗ trợ của luật đã được thoả mãn, tức là độ hỗ trợ của luật chính là sup(l). Thuật toán đơn giản. Chúng ta cải tiến thủ tục xử lý bằng cách sinh ra các tập con của mục lớn theo kiểu đệ qui ưu tiên độ sâu. Ví dụ: với tập mục ABCD, đầu tiên chúng ta xét tập con ABC, sau đó đến AB,... Tiếp đến, nếu tập con a của tập mục lớn l không sinh ra được luật thì không cần xét đến các tập con của nó nữa. Chẳng hạn: nếu luật ABC® D không đủ độ tin cậy thì ta không cần xét đến luật AB® CD. Điều này có thể chứng minh đơn giản như sau: Nếu luật a ®(l-a) không thoả mãn độ tin cậy, tức là: conf(a®l-a)) nhỏ hơn minconf, thế thì với bất kỳ tập con b nào của a ta có: Vì bÌ a nên supp(b)³supp(a), do vậy: Conf(b®(l-b)) = =conf((a®(l-a))<minconf Tức là độ tin cậy của luật b®(l-b) cũng nhỏ hơn minconf Thuật toán đơn giản này có thể mô tả như sau: Thuật toán 1. For all large itemsets lk , k³2 do call genrules(lk ,lk) Procedure genrules(lk:large k-itemsets, am: large m-itemsets) A={(m-1)-itemsets am-1|am-1Ì am}; for all am-1Î A do again conf=support(lk)/support(am-1); if (conf ³ minconf) then begin output the rule am-1®(lk-am-1), with confidence=conf and support=support(lk) if (m-l > l) then call genrules(lk,am-1); //để sinh ra các luật với tập con của am-1 là phần tiền đề end end Thuật toán nhanh hơn. Ở trên ta đã chỉ ra rằng nếu một luật không thoả mãn với tập cha a thì cũng không thoả mãn với tập con của nó. Ví dụ như trên đã xét: nếu ABC®D không đủ độ tin cậy thì luật AB®CD cũng không đủ độ tin cậy. Điều đó cũng có thể áp dụng theo hướng ngược lại như sau: nếu xảy ra luật với tập con thì cũng xảy ra luật với tập cha. Ví dụ: nếu luật AB®CD có đủ độ tin cậy thì luật ABC®D cũng đủ độ tin cậy. Thuật toán 2. For all larger itemsets lk, k³ 2 do Begin Hl={các phần kết luận của các luật nhận được từ lk với l-mục ở kết luận}; Call ap_genrules(lk,Hl) End Procedure ap_genrules(lk:large k-itemsets, Hm:set of m-item consequents) If (k>m+1) then begin Hm+1=apriori_gen(Hm); For all hm+1ÎHm-1 do Begin Conf = support(lk)/support(lk-hm+1); If (conf ³minconf) then Output the rule(lk-hm+1)®hm+1 //với độ tin cậy là conf và độ hỗ trợ là support (lk) Else Delete hm+1 from Hm+1 End Call ap_genrules(lk, Hm+1) End Thuật toán nhanh hơn này sử dụng thủ tục apriori_gen mô tả ở phần thuật toán Apriori ở trên. Ta xem tại sao thuật toán 2 này nhanh hơn thuật toán 1 trên: Ví dụ, ta xét tập mục ABCDE: Giả sử rằng ACDE®B, ADE®CB là các luật có l-mục ở phần kết luận thoả mãn độ hỗ trợ cực tiểu minconf. Trong thuật toán đơn giản trên, gọi đệ quy genrules(ABCDE, ACD) sẽ kiểm tra các luật với 2-mục ở phần kết luận là: ACD®BE, ADE®BC, CDE®AB và ACE®BD Luật thứ nhất không xảy ra vì E Ì BE và ABCD ®E không thoả mãn độ tin cậy. Các luật thứ hai và thứ ba cũng không thoả mãn độ tin cậy với lý do tương tự. Chỉ có một luật với 2 - mục ở phần kết luận nhận được là ACE®BD, ở đó B và D là các kết luận của các luật kết hợp có 1- mục ở phần kết luận. Thuật toán nhanh hơn mô tả ở trên chỉ kiểm tra một luật này. 2. Thuật toán FP-growth 2.1. Ý tưởng thuật toán Thuật toán kinh điển Apriori tìm tập mục phổ biến thực hiện tốt bởi rút gọn kích thước các tập ứng cử nhờ kỹ thuật tỉa. Tuy nhiên, trong tình huống mà số các mẫu nhiều, mẫu dài hoặc độ hỗ trợ cực tiểu thấp, các thuật toán Apriori gặp phải 2 chi phí lớn: Chi phí cho số lượng khổng lồ các tập ứng cử. Ví dụ: nếu có 104 tập 1-mục phổ biến thì thuật toán Apriori sẽ cần sinh ra hơn 107 các ứng cử 2-mục và thực hiện kiểm tra sư xuất hiệ