zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ 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

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

Báo xấu

73
lượt xem 3
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: 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: Ứng với từng giao tác  Tạo cây T Ta tạo nhánh cây chỉ với các giá trị đã có ở Q. Đánh dấu tăng 1 nếu một node trên cây được đi qua lại  số lần lặp lại trong nhánh. 03: Duyệt lại từ node trong Q, theo thứ tự thấp đến cao trên cây T. Để xác định các tổ hợp với các số trên node, xác định độ hỗ trợ.
TẠO FP - TREE Tạo cây với gốc là null ~ TR // Kết quả là cây đủ Q = {Ii} / S(Ii) >= Smin Xếp Q giảm dần theo S Với từng giao tác Tj trong T { Cho (TMP) = (TR.gốc) Cho i = 1 đến Q.kíchthước Nếu Ii thuộc về Tj { Nếu (TMP) có chứa con là (node Ii) (node Ii).solan++ ngược lại Tạo mới (node Ii) là con (TMP) (TMP) = (node Ii) } } // Mỗi lần tạo mới một node thì node.solan = 1
DUYỆT FP - TREE Tạo Pre = {} // chứa các tổ hợp For i = Q.kíchthước đến 1 { Tạo Prefix(Ii) = {} Với từng nhánh có (node Ii) là lá { //là nhánh qua (node Ii) và chỉ xét đến (node Ii) Với từng tổ hợp X có chứa Ii và |X| > |Ii|{ Nếu Prefix(Ii) chứa X Tăng độ hỗ trợ của X Ngược lại Prefix(Ii) += X } // độ hỗ trợ của X là số lần của (node Ii) } Lưu lại vào tập Pre += Prefix(Ii) với điều kiện S(Prefix(Ii)) >= Smin } // Có thể bỏ tất cả (node Ii) sau từng lần duyệt

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.