Bài giảng Xây dựng hệ khai mỏ dữ liệu: Mẫu thường xuyên, luật kết hợp - Phan Hiền

Mẫu thường xuyên, luật kết hợp là phương pháp khai mỏ dựa trên độ lặp lại thường xuyên của mẫu tin nào đó, xác định quy luật quan hệ giữa các thuộc tính (phần tử) trong mẫu tin đó. Và để hiểu rõ hơn về điều này mời các bạn tham khảo bài giảng Xây dựng hệ khai mỏ dữ liệu: Mẫu thường xuyên, luật kết hợp sau đây.
Nội dung trích xuất từ tài liệu:
Bài giảng Xây dựng hệ khai mỏ dữ liệu: Mẫu thường xuyên, luật kết hợp - Phan Hiền XÂY DỰNG HỆ KHAI MỎ DỮ LIỆU MẪU THƯỜNG XUYÊN, LUẬT KẾT HỢP Phan Hiền KHÁI QUÁT Đây là phương pháp khai mỏ dựa trên độ lặp lại thường xuyên của mẫu tin nào đó.  Xác định quy luật quan hệ giữa các thuộc tính (phần tử) trong mẫu tin đó. Lấy ví dụ: Trong vô số khách hàng mua hàng của siêu thị, nhà quản lý đặt ra vấn đề là các giỏ hàng thường xuyên có các món hàng gì. KHÁI QUÁT Ta nhận thấy thường người dùng mua áo đầm là mua nón kiểu. mua áo đầm  mua nón kiểu (Hỗ trợ là 0.2 và độ tin là 0.8) Ta có thể nói như sau: Chỉ có 20% số người mua áo đầm và nón kiểu trên toàn bộ người mua. Nhưng trong số tất cả người mua áo đầm, có 80% người mua kèm nón kiểu.  Quan tâm đến 2 khái niệm độ tin & hỗ trợ KHÁI NIỆM  Tập giá trị (ItemSet) I = {I1,I2,…,In}  Giao tác (Transaction) T = {Ik,..,Ih} con của I.  Luật kết hợp A và B ◦ A con I, B con I, và A,B cùng thuộc vào T ◦ Suy ra A  B hay B  A Cho tập các sản phẩm I = {G,D,M} T1 = {G,D} T4 = {M,D} Kết hợp G  D có T2 = {G,M,D} T5 = {M} Hỗ trợ : 2/5 T3 = {G} Độ tin : 2/3  Các giá trị trong ItemSet là cùng thuộc tính. KHÁI NIỆM  Các giá trị trong ItemSet là nhiều thuộc tính. I = {X,.,W,.,Y,.} = {X1,…,Xn,… Wk,…, Y1,…, Ym}  Giao tác T là con của I  Luật Xk  Yh có nghĩa ◦ Xk là con của X, Yh là con của Y, và cùng T. Ví dụ: I = {Tuổi, màu} Màu = {xanh, vàng, đỏ} Tuổi = {20,21,22} Giao tác T là ý nghĩa độ tuổi thích màu T1={20,vàng} T2={21,vàng} T3={22,đỏ} T4={20,xanh} ,.. KHÁI NIỆM  Độ hỗ trợ (support) T S ( A)  P( A) AT T T A, BT S ( A, B)  P( A  B)  T  Độ tin (confident) P( A  B) T A, BT C ( A  B)  P( B | A)   P( A) T AT Trong đó A  B   VẤN ĐỀ  Sự lựa chọn các thuộc tính  Độ hỗ trợ, độ tin như thế nào là phù hợp THUẬT TOÁN  Thuật toán Apriori  Thuật toán FP-Tree (Frequent Pattern Tree) Hai thuật toán này mục đích để khai thác các giao tác ít lại mà vẫn có thể xác định được độ hỗ trợ của các kết hợp giá trị. Các thuật toán đều có dùng hệ số tối thiểu của độ hỗ trợ và độ tin để xác định luật. THUẬT TOÁN APRIORI Phát biểu: - Cho độ hỗ trợ, tin tối thiểu là Smin , Cmin - Thuật toán tận dụng yếu tố Giả sử ta có S(A) = x và S(B) = y, trong đó x >= Smin và y < Smin  S(AB) < Smin Thuật toán chủ yếu tập trung vào điều đó để giảm bớt sự duyệt các giao tác khi chuyển từ bộ ứng viên k phần tử sang k+1 phần tử. THUẬT TOÁN APRIORI Thuật toán: 01: Chuẩn bị các ứng viên – độ rộng k (tổ hợp các giá trị cần xét độ hỗ trợ) 02: Chọn ra các ứng viên thỏa độ hỗ trợ 03: Chuẩn bị các ứng viên có độ rộng k+1 Đó là sự kết hợp các phần tử trong luachon mà có khả năng là thỏa độ hỗ trợ. Trở về bước 01. THUẬT TOÁN APRIORI I = {Ii} / i thuộc [1,n] Cho k = 1, ungvienk = I, luachonk = {} Khi [(k Smin thì luachonk += U[i] // tao ungvien(k+1) Với mọi X,Y thuộc luachonk { ta có W = X hợp Y và |W| = k + 1 Nếu mọi Z con W và |Z| = k và mọi Z cũng là con luachonk thì ungvien(k+1) += W } k++ } VÍ DỤ APRIORI Cho tập I = {A,B,C,D,E} Cho tập các giao tác như sau T1 = {A,B,C,D,E} T2 = {A,B,C} T3 = {D,C,B} T4 = {A,B,D} T5 = {D,C} T6 = {D,C,A,B} T7 = {A,B,E,D} Xét với độ hỗ trợ tối thiểu là 0.5 ~ >= 4 lần VÍ DỤ APRIORI B1: ungvien1={A,B,C,D,E}, S(ungvien) = {5,6,5,6,2} luachon1={A:5,B:6,C:5,D:6} Xét AB đều có A,B thuộc luachon1  ungvien2 += AB Xét AC đều có A,C thuộc luachon1  ungvien2 += AC ……… Xét CD đều có C,D thuộc luachon1  ungvien2 += CD  ungvien2 = {AB,AC,AD,BC,BD,CD} VÍ DỤ APRIORI B2: ungvien2 = {AB,AC,AD,BC,BD,CD} tính S(ungvien2) = {5,3,4,4,5,4} luachon2= {AB:5,AD:4,BC:4,BD:5,CD:4} Xét ABD có AB,AD,BD đều thuộc luachon2 => ungvien3 += ABD Xét ABC có AB,AC,BC có AC không thuộc luachon2 Xét BCD có BC,CD,BD đều thuộc luachon2 => ungvien3 += BCD Xét ACD có AC,AD,CD có AC không thuộc luachon2 ungvien3 = {ABD,BCD} VÍ DỤ APRIORI B3: ungvien3 = {ABD,BCD} tính S(ungvien3) = {4,3} luachon3 = {ABD:4} Chấm dứt thuật toán vì ứng viên không còn Lựa chọn = {AB:5,AD:4,BC:4,BD:5,CD:4,ABD:4} Với {A:5,B:6,C:5,D:6} B4: Xác định các luật và độ tin của luật Với ABD ta có AB -> D; AD -> B; BD -> A; A -> BD; B -> AD; D -> AB; Xét luật AB -> D có C(AB->D) = 4/5 …… Bài tập APRIORI Cho tập { gioitinh, tuoi, xe } T1 = {Nam, 20, Dream} T2 = {Nam, 21, Dream} T8 = {Nu, 21, Click} T3 = {Nam, 15, Dream} T9 = {Nu, 17, Dream} T4 = {Nam, 17, Click} T10 = {Nu, 16, Click} T5 = {Nam, 22, Click} T11 = {Nu, 16, Click} T6 = {Nam, 21, Dream} T12 = {Nu, 28, Click} T7 = {Nam, 22, Dream} Trong đó [10,20] : Thanh niên (TN) [21,26] : Trẻ (T) [27,35] : Trung niên (TR) [36,40] : Già (G) Dùng Apriori để xác định các luật có thể với Độ hỗ trợ >= 0.2 và độ tin >= 0.7 THUẬT TOÁN FP - TREE  Thuật toán này tận dụng yếu tố sự kết hợp sau là sự mở rộng của tổ hợp trước đó.  Không cần phải chuẩn bị các ứng viên như Apriori Lấy ví dụ: Ta có AB S(AB) = 3 Khi đó nếu ta tìm thấy được một và chỉ một giao tác có A, B, C khi đó ta có ABC S(ABC) = 1 Mô tả: A:3 B:3 C:1 THUẬT TOÁN FP - TREE Thuật toán: 01: Tạo tập các giá trị với độ hỗ trợ giảm dần và thỏa mãn độ hỗ trợ tối thiểu.  Q 02: Ứn ...