Bài giảng Khai phá dữ liệu - Chương 3: Khai phá luật kết hợp

Chia sẻ: Nguyễn Thị Hiền Phúc | Ngày: | Loại File: PPTX | Số trang:70

Thêm vào BST

Báo xấu

55
lượt xem 5
download

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

Bài giảng cung cấp cho người học các kiến thức: Khai phá luật kết hợp. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu.

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 Khai phá dữ liệu - Chương 3: Khai phá luật kết hợp

TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM KHOA CÔNG NGHỆ THÔNG TIN BÀI GIẢNG MÔN HỌC KHAI PHÁ DỮ LIỆU CHƯƠNG 3: KHAI PHÁ LUẬT KẾT HỢP Giảng viên: ThS. Nguyễn Vương Thịnh B ộ m ô n : H ệ t h ốn g t h ô n g t in Hải Phòng, 2013
Th ô n g t in v ề g i ản g v iê n Họ và tên Nguyễn Vương Thịnh Đơn vị công tác Bộ môn Hệ thống thông tin – Khoa Công nghệ thông tin Học vị Thạc sỹ Chuyên ngành Hệ thống thông tin Cơ sở đào tạo Trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội Năm tốt nghiệp 2012 Điện thoại 0983283791 Email thinhnv@vimaru.edu.vn Website cá nhân http://scholar.vimaru.edu.vn/thinhnv 2
Th ô n g t in v ề h ọc p h ần Tên học phần Khai phá dữ liệu Tên tiếng Anh Data Mining Mã học phần 17409 Số tín chỉ 03 tín chỉ Số tiết lý thuyết 39 tiết (13 tuần x 03 tiết/tuần) Số tiết thực hành 10 tiết (05 tuần x 02 tiết/tuần) Bộ môn phụ trách Hệ thống thông tin P H ƯƠN G P HÁP H ỌC TẬP, N GHIÊN CỨU v N g h e g i ản g , t h ảo lu ận , t ra o đ ổi v ới g i ản g v iê n t rê n l ớp . P H ƯƠTNựG P n g HÁP h iê n Đ c ứ ÁNu tH GIÁ à i li ệu v à là m b à i t ập ở n h à . v v S V p h ải t h a m d ự ít n h ất 7 5 % t h ời g ia n . v Có 0 2 b à i k i ểm t ra v i ết g i ữa h ọc p h ần ( X = X2 = ( L1 + L2 ) /2 ) . 3 v Th i k ết t h ú c h ọc p h ần b ằn g h ìn h t h ức t r ắc n g h i ệm k h á c h q u a n t rê n m á y t ín h ( Z = 0 . 5 X + 0 . 5 Y) .
Tài liệu tham khảo 1. Jiawei Han and Micheline Kamber, Data Mining Concepts and Techniques, Elsevier Inc, 2006. 2. Ian H. Witten, Eibe Frank, Data Mining – Practical Machine Learning Tools and Techniques (the second edition), Elsevier Inc, 2005 (sử dụng kèm với công cụ W e k a ). 3. Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4th Edition), Pearson Education Inc, 2004. 4. Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú, Giáo trình Khai phá dữ liệu Web, NXB Giáo dục, 2009 4
5
Cô n g c ụ p h ần m ềm h ỗ t rợ Phần mềm Weka được phát triển bởi nhóm nghiên cứu của trường Đại h ọc Wa ik a t o ( N e w Ze a la n d ) t ừ n ă m 1 9 9 9 . Có t h ể d o w n lo a d v ề t ại đ ịa c h ỉ: h t t p ://w w w . c s . w a ik a t o . a c . n z /m l/w e k a /d o w n lo a d in g . h t m l 6
CHƯƠNG 3: KHAI PHÁ LUẬT KẾT HỢP 3.1. MỘT SỐ KHÁI NIỆM CƠ BẢN 3.2. TÌM TẬP PHỔ BIẾN VỚI GIẢI THUẬT APRIORI 3.3. SINH LUẬT KẾT HỢP TỪ CÁC TẬP PHỔ BIẾN 3.4. TÌM TẬP PHỔ BIẾN VỚI GIẢI THUẬT FP - GROWTH 3.5. MỘT SỐ DẠNG THỨC CỦA CSDL GIAO DỊCH 3.6. KHAI PHÁ LUẬT KẾT HỢP VỚI PHẦN MỀM WEKA 7
3.1. MỘT SỐ KHÁI NIỆM CƠ BẢN 3.1.1. Khái niệm mục (item) và tập mục (item set)  Cho một tập gồm n đối tượng I = {I1, I2, I3,…, In}, mỗi phần tử Ii ∈ I được gọi là một mục (item). Một tập con bất kỳ X ⊆ I được gọi là một tập mục (item set).  Cho một tập D = {T1, T2,…, Tm}, mỗi phần tử Tj ∈ D được gọi là một giao dịch (transaction) và là một tập con nào đó của I (Tj ⊆ I). Ví d ụ: I = { A, B, C, D , E, F} , X = Người ta, gọi { A, D E} D làlà m cơộsở dữ t tập liệu m ụgiao c . Mdịch ột c(transaction ơ s ở d ữ lidatabase). ệu g ia o d ịc hSố D giao g ồmdịch c ácó c ttrong ập c Do nký Tj k hiệuh là á c|D|. n h a u c ủa I: T1 {A, B, C, D} T2 {A, C, E} T3 {A, E} T4 {A, E, F} T5 {A, B, C, E, F} 8
Milk, Bread, Coke Beer, Bread Beer, Milk, Diaper, Coke 10:05 10:12 10:15 Beer, Milk, Diaper, Bread Milk, Diaper, Coke 10:23 10:30 9
3.1.2. Độ hỗ trợ (support) ứng với một tập mục “Độ hỗ trợ ứng với tập mục X là xác suất xuất hiện của X trong cơ sở dữ liệu giao dịch D” Hoặc “Đỗ hỗ trợ ứng với tập mục X là C tỷ( X lệ )các giao dịch có chứa X sup( X ) = trên tổng số các giao dịch có trong| cơ D |sở dữ liệu giao dịch D” Trong đó: C(X) là số lần xuất hiện của X hay số giao dịch có chứa X T1 {A, B, C, D} Ví dụ: X = {A, E} thì C(X) = 4 và sup(X) = 4/5 = 80% T2 {A, C, E} T3 {A, E} T4 {A, E, F} T5 {A, B, C, E, F} Các tập mục có độ hỗ trợ lớn hơn một giá trị ngưỡng minsup nào đó c h o t r ước đ ược g ọi là c á c t ập p h ổ b i ến ( f re q u e n t it e m 10 s e t ) .
3.1.3. Luật kết hợp (Association Rule)  Cho hai tập mục X, Y ⊆ I, X ∩ Y = ϕ. Luật kết hợp ký hiệu là X → Y chỉ ra mối ràng buộc của tập mục Y theo tập mục X, nghĩa là khi X xuất hiện trong cơ sở dữ liệu giao dịch thì sẽ kéo theo sự xuất hiện của Độ Y hỗvới trợmột của một luật:tỷ là lệ nào tỷ lệđấy. (hay xác suất) xuất hiện cả X và Y trong  Luật kếtcùng hợpmột được giao đặcdịch. trưng bởi: C( X Y ) sup( X � Y ) = sup( X �Y ) = |D| Đ ộ t in c ậy c ủa lu ật : là tỷ lệ các giao dịch có chứa cả X và Y so với các giao dịch có chứa X. C ( X Ȯ Y ) sup( X Y) conf ( X Y) = = C( X ) sup( X ) Trong đó: C(X ∪ Y): Số giao dịch có chứa cả X và Y. C(X): Số giao dịch có chứa X. 11
 Luật mạnh: Các luật có độ hỗ trợ lớn hơn một giá trị ngưỡng minsup và độ tin cậy lớn hơn một giá trị ngưỡng minconf cho trước được gọi là các luật “mạnh” hay “luật có giá trị” (strong association rules). Cụ thể: N ếu đ ồn g t h ời s u p ( X →Y ) ≥ m in s u p v à c o n f ( X →Y ) ≥ m in c o n f t h ì X →Y đ ược g ọi là lu ật m ạn h ( s t ro n g a s s o c ia t io n ru le ) . 12
3.1.4. Bài toán khai phá luật kết hợp Input: Cơ sở dữ liệu giao dịch D. Các giá trị ngưỡng minsup, minconf. Output: Tất cả các luật mạnh. Để giải quyết bài toán khai phá luật kết hợp bao giờ cũng thường trải qua hai pha: Pha 1: Sinh tất cả các tập phổ biến có thể có. Ở pha này ta sử dụng các giải thuật tìm tập phổ biến như: Apriori, FP-Growth,... Pha 2: Ứng với mỗi tập phổ biến K tìm được ở pha 1, tách K thành hai tập X, Y không giao nhau (K = X ∪ Y và X ∩ Y = ϕ). Tính độ tin cậy của luật kết hợp X → Y, nếu độ tin cậy trên ngưỡng minconf thì nó là luật mạnh. Chú ý là nếu tập K có k phần tử thì số tập con thực sự của K sẽ là 2k – 2, tức là từ K ta sẽ sinh được tối đa là 2k - 2 luật. Lưu ý: Trong một số giải thuật, để xác định một tập là phổ biến người ta không sử dụng khái niệm độ hỗ trợ mà sử dụng khái niệm số lần xuất hiện (support count). Nếu số lần xuất hiện của tập mục trong cơ sở dữ liệu giao dịch lớn hơn một giá trị ngưỡng nào đấy thì nó là tập phổ biến. Giá trị ngưỡng này được xác định là: mincount = � minsup * | D |� 13
3.2. TÌM TẬP PHỔ BIẾN VỚI GIẢI THUẬT AP RIORI 3.2.1. Nguyên lý Apriori “Nếu một tập mục là tập phổ biến thì mọi tập con khác rỗng bất kỳ của nó cũng là tập phổ biến” Ch ứn g m in h : Xét X’ ⊆ X. Ký hiệu p là ngưỡng độ hỗ trợ minsup. Một t ập m ục x u ất h iện b a o n h iê u lần t h ì c á c t ập co n ch ứa t ro n g n ó c ũ n g x u ất h iện ít n h ất b ấy n h iê u lần , nên ta có: C(X’) ≥ C(X) (1). X là tập phổ biến nên: C( X ) sup( X ) � = p C( X ) p | D | (2) |D| C ( X ') Từ (1) và (2) suy C ( X ') > p | D |� sup( X ') = �p ra: |D| Tức là X’ cũng là tập phổ biến (đpcm). 14
3.2.2. Giải thuật Apriori Mục đích: Tìm ra tất cả các tập phổ biến có thể có. Dựa trên nguyên lý Apriori. Hoạt động dựa trên Quy hoạch động: Từ các tập Fi = { ci | ci là tập phổ biến, |ci| = i} gồm mọi tập mục phổ biến có độ dài i (1 ≤ i ≤ k), đi tìm tập Fk+1 gồm mọi tập mục phổ biến có độ dài k+1. Các mục I1, I2,…, In trong tập I được coi là sắp xếp theo một thứ tự cố định. 15
Input: Cơ sở dữ liệu giao dịch D = {t1, t2,…, tm}. Ngưỡng độ hỗ trợ tối thiểu minsup. Output: Tập hợp tất cả các tập phổ biến. mincount = � minsup * | D |� ; F1 = { các tập phổ biến có độ dài 1}; for(k=1; Fk != ?; k++) { Ck+1 = Apriori_gen(Fk); for each t ∈ D { Ct = { c | c ∈ Ck+1 và c ⊆ t}; for each c ∈ Ct c.count++; } Fk+1 = {c ∈ Ck+1 | c.count ≥ mincount}; } 16 return F = U Fk k
Thủ tục con Apriori_gen • Thủ tục con Apriori_gen có nhiệm vụ sinh ra (generation) các tập mục có độ dài k+1 từ các tập mục có độ dài k trong tập Fk. • Được thi hành qua hai bước: nối (join) các tập mục có chung các tiền tố (prefix) và sau đó áp dụng nguyên lý Apriori để loại bỏ bớt những tập không thỏa mãn. Cụ thể: v Bước nối: Sinh các tập mục c là ứng viên của tập phổ biến có độ dài k+1 bằng cách kết hợp hai tập phổ biến li và lj ∈ Fk có độ dài k và trùng nhau ở k-1 mục đầu tiên: c = li + lj = {i1, i2, …, ik-1, ik, ik’}. Với li = {i1, i2,…, ik-1, ik}, lj = {i1, i2,…, ik-1, ik’}, và i1 ≤ i2 ≤…≤ ik-1 ≤ ik ≤ ik’. v Bước tỉa: Giữ lại tất cả các ứng viên c thỏa thỏa mãn nguyên lý Apriori tức là mọi tập con có độ dài k của nó đều là tập phổ biến (∀sk ⊆ c và |sk| = k thì sk ∈ Fk). 17
function Apriori_gen(Fk: tập các tập phổ biến độ dài k): Tập ứng viên có độ dài k+1 { Ck+1 = ?; for each li ∈ Fk for each lj ∈ Fk if (li[1]=lj[1]) and (li[2]=lj[2]) … and (li[k1]=lj[k1]) and (li[k]
Hàm has_infrequent_subset làm nhiệm vụ kiểm tra xem một ứng viên có độ dài k+1 có chứa tập không phổ biến hay không, nếu có thì ứng viên lập tức bị loại. Đây là bước tỉa dựa trên nguyên lý Apriori nhằm loại bỏ nhanh các ứng viên không thỏa mãn. function has_infrequent_subset(c: Ứng viên có độ dài k+1, Fk: Tập các tập phổ biến độ dài k): Boolean { for each sk ⊂ c if sk ∉ Fk then return True; return False; } 19
3.3. SINH LUẬT KẾT HỢP TỪ CÁC TẬP PHỔ BIẾN Để sinh các luật kết hợp: v Với mỗi tập phổ biến X ∈ F, ta xác định các tập mục không rỗng là con của X. v Với mỗi tập mục con S không rỗng của X ta sẽ thu được một luật kết hợp là S→(X\S). Nếu độ tin cậy của luật thỏa mãn ngưỡng minconf thì luật đó là luật mạnh. C( X ) conf ( S ( X \ S )) = minconf C (S ) function Rules_Generation(F: Tập các tập phổ biến): Tập các luật kết hợp mạnh { R = ?; F=F \ F1; //Các tập phổ biến độ dài 1 không dùng để sinh luật for each X ∈ F for each S ⊂ X if conf(S→(X\S)) ≥ minconf then R = R ∪ { S→(X\S)}; return R; 20 }