B ộa GIÁO DỤC VÀ ĐÀO TẠO * • TRƯỜNG ĐẠI HỌC s PHẠM HÀ NỘI • • • • ===80 O c&=== NGUYỄN VĂN PHÓNG KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN CÓ TRỌNG SỐ LUẬN VĂN THẠC SĨ MÁY TÍNH HÀ NỘI, 2015 B ộ• GIÁO DỤC VÀ ĐÀO TẠO • • TRƯỜNG ĐẠI HỌC s PHẠM HÀ NỘI ===#0 EO08=== NGUYỄN VĂN PHÓNG KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN CÓ TRỌNG SỐ • Chuyên ngành: K hoa học m áy tính M ã số: 60 48 01 01 LUẬN VĂN THẠC SĨ MÁY TÍNH Người hướng dẫn khoa học: TS NGUYỄN LONG GIANG HÀ NỘI, 2015 LỜI CẢM ƠN Để hoàn thành luận văn nhận giúp đỡ tận tình thày hướng dẫn khoa học, thầy cô trường Đại học Sư phạm Hà Nội Tôi xin chân thành cảm ơn thầy cô trường Đại học Sư phạm Hà Nội tạo điều kiện học tập, nghiên cứu giúp đỡ nhiều trình làm luận văn Đặc biệt xin cảm ơn thầy TS Nguyễn Long Giang Viện Công Nghệ Thông Tin tận tình hướng dẫn, bảo suốt trình học tập, nghiên cứu đề tài giúp đỡ hoàn thành luận văn Vĩnh Phúc, ngày 01 tháng 10 năm 2015 Học viên Nguyễn Văn Phóng LỜI CAM ĐOAN Tôi xin cam đoan kết nghiên cứu hướng dẫn khoa học TS Nguyễn Long Giang Các số liệu, kết nêu ưong luận văn trung thực chưa công bố công trình khác Học viên Nguyễn Văn Phóng MUC LUC • • MỤC LỤC i Danh mục ký hiệu, chữ viết tắt iii Danh mục bảng iv Danh mục hình Y MỞ ĐẦU Chương 1: TỔNG QUAN VỀ KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN 1.1 Các khái niệm 1.1.1 Cơ sở liệu giao tác 1.1.2 Tập mục thường xuyên luật kết hợp 1.1.3 Các tính chất tập mục thường xuyên 1.1.4 Bài toán khai phá luật kết hợp 1.2 Một số thuật toán khai phá tập mục thường xuyên 1.2.1 Thuật toán Apriori 1.2.2 Thuật toán FP-growth 14 1.3 Kết luận 21 ChươngO 2: KHAI MỤC THƯỜNG XUYÊN CÓ TRỌNG SỐ 22 a PHÁ TẬP « • 2.1 Thuật toán MINWAL theo tiếp cận Apriori 22 2.1.1 Các khái niệm 22 2.1.2 Thuật toán MINWAL 25 2.1.3 Ví dụ minh họa 28 2.2 Thuật toán WFIM theo tiếp cận FP-Growth 50 2.2.1 Các khái niệm 51 2.2.2 Thuật toán WFIM 55 2.2.3 Ví dụ minh họa 56 2.3 THUẬT TOÁN FSM 60 ii 2.3.1 Cơ sở lý thuyết thuật toán FSM 60 2.3.2 Thuật toán FSM 61 2.3.3 Nhận xét thuật toán FSM 63 2.4 Kết luận 64 Chương 3: THỬ NGHIỆM VÀ ĐÁNH GIÁ CÁC THUẬT TOÁN .65 3.1 Chuẩn bị số liệu thử nghiệm 66 3.2 Kết thử nghiệm đánh giá thuật toán 66 3.2.1 Đánh giá thuật toán WFIM vói thuật toán FP-Growth 66 3.2.2 Đánh giá thuật toán WFTM, FP-Growth MINWAL 68 KẾT LUẬN .71 ■ TÀI LIỆU THAM KHẢO .72 PHỤ LỤC DANH MUC CÁC KÝ HIÊU, • « CÁC CHỮ VIẾT TẮT l\lA •7• Ký hiệu, chữ viết tắt Diên giải CSDL Cơ sở liệu TID Transction Identifcation w Tập trọng sô mục L Tập tât mục thường xuyên ck Tập k-tập mục ứng viên Lk Tập k-tập mục thường xuyên SCịX) Sô đêm hô trợ tập mục X WFIk Tập k-tập mục thường xuyên có trọng sô WFI Tập tât tập mục thường xuyên có trọng sô MaxW Trọng sô có giá trị lớn nhât CSDL giao tác MinW Trọng sô cổ giá trị nhỏ nhât tập mục điêu kiện min_weight Ngưỡng trọng sô thiêu mỉn_sup Ngưỡng hô trợ thiêu support Độ hô trợ tập mục conf Độ tin cậy minconf Độ tin cậy cực tiêu BFS Breadth First Search DFS Depth First Search WFIM Weighted Frequent Itemset Mining Danh mục bảng Bảng 1.1 Biểu diễn ngang sở liệu giao tác Bảng 1.2 Biểu diễn dọc sở liệu giao tác Bảng 1.3 Ma trận giao tác sở liệu bảng 1 Bảng 1.4 CSDL giao tác minh họa thực thuật toán Aprìorì 12 Bảng 1.5 CSDL giao tác minh họa cho thuật toán FP- growth .15 Bảng 2.1 CSDL giao tác 24 Bảng 2.2 Trọng số mục 24 Bảng 2.3 CSDL giao tác D .28 Bảng 2.4 Trọng số mục 29 Bảng 2.5 CSDL giao tác 51 Bảng 2.6 Ví dụ mục với khoảng trọng sổ khác 52 Bảng 2.7 Tập tập mục thường xuyên với khoảng trọng số khác 54 Bảng 2.8 Mục thường xuyên có trọng sổ (sắp xếp tăng dần theo trọng sổ) 57 Danh muc hình Hình 1.2 Cây FP-tree xây dựng dần thêm giao tác ti, t2, t3 16 Hình 1.3 Cây FP-tree CSDL DB bảng 17 Hình 1.4 FP-tree phụ thuộc m 19 Hình 1.5 Các FP-tree phụ thuộc am, cm cam 20 Hình 2.1 Cây FP-Tree tổng quát thuật toán FP-Tree 57 Hình 2.2 Cây FP-Tree với tiền tổ ịr } 59 Hình 3.1 Số lượng tập mục thường xuyên thuật toán WFIM so với FPGrowth (tập liệu Connect) 67 Hình 3.2 Thời gian thực thuật toán WFIM so với FP-Growth (tập liệu Connect) 67 Hình 3.3 Số lượng tập mục thường xuyên thuật toán FP-Growth, WFIM MINWAL (tập liệu Connect) .69 Hình 3.4 Thời gian thực thuật toán FP-Growth, WFIM MINWAL (tập liệu Connect) 70 MỞ ĐẦU Lý chọn đề tài Khai phá luật kết họp giói thiệu Agrawal [4] vào năm 1994 phân tích sở liệu bán hàng siêu thị, phân tích sở thích mua khách hàng cách tìm mặt hàng khác khách hàng mua lần mua Những thông tin giúp người quản lý kinh doanh tiếp thị chọn lọc thu xếp không gian bày hàng họp lý hơn, giúp cho kinh doanh hiệu Bài toán khai phá luật kết hợp bao gồm hai toán Bài toán thứ tìm tập mục thường xuyên (Frequent itemset) thỏa mãn ngưỡng hỗ trợ tối thiểu cho trước, toán thứ hai sinh luật kết hợp (Association rule) thỏa mãn ngưỡng tin cậy cho trước từ tập mục thường xuyên tìm Mọi khó khăn toán khai phá luật kết hợp tập trung toán thứ nhất, khai phá tất tập mục thường xuyên thỏa mãn ngưỡng độ hỗ trợ cho trước, nghiên cứu khai phá luật kết họp phần lớn tập trung vào toán khai phá tập mục thường xuyên Kể từ Agrawal đề xuất, khai phá tập mục thường xuyên thu hút quan tâm nhiều nhà nghiên cứu, có hàng trăm kết nghiên cứu công bố giói thiệu thuật toán hay đề xuất giải pháp nâng cao hiệu thuật toán có Tập mục thường xuyên có vai trò quan ưọng nhiều ứng dụng thực tế quản lý quan hệ khách hàng, nâng cao hiệu thương mại điện tử, lĩnh vực sinh tin học, phân tích cấu trúc Protein DNA, mở rộng truy vấn, hỗ trợ tư vấn tuyển sinh đào tạo, phát xâm nhập mạng Bài toán khai phá luật kết họp kinh điển Agrawal cộng đề xuất [4] gọi toán khai phá luật kết họp nhị phân giá tri mục liệu ưong giao tác 1, tức quan tâm mục liệu có xuất giao tác hay không Do đó, mang ngữ nghĩa thống kê, 63 for each X£Ck 17 if lmv(X)> lmv 18 19 Fk ^ F k v { X ] 20 else if CF(X)[...]... mục thường xuyên tập trung vào tìm các thuật toán mới hoặc đề xuất giải pháp nâng cao hiệu quả các thuật toán đã có Phần này sẽ trình bày khái quát các kỹ thuật chính để khai phá tập mục thường xuyên Bài toán khai phá tập mục thường xuyên có thể chia thành hai bài toán nhỏ: tìm các tập mục ứng viên và tìm các tập mục thường xuyên Tập mục ứng viên là tập mục mà ta hy vọng nó là tập mục thường xuyên, phải... là tập mục thường xuyên có trọng sổ chuẩn hóa thì bất kỳ một tập con bậc cao nào của X cũng sẽ là tập mục thường xuyên có trọng so chuẩn hóa Mệnh đề 2.3 [5] Neu X là một (k +1) - tập mục thường xuyên có trọng sổ chuẩn hóa thì X phải là tập cha bậc thấp của một к -tập mục thường xuyên có trọng so chuẩn hóa Y Với các kết luận nêu ữong các Mệnh đề 2.1, 2.2 và 2.3, ta có thể xây dựng thuật toán khai phá tập. .. kết nối để tạo ra tập ứng viên ck.Theo mệnh đề 2.3, một k-tâp mục ứng viên chỉ có thể là tập mục thường xuyên có trọng số chuẩn hóa nếu nó là tập cha bậc thấp của một (k-l) -tập mục thường xuyên có trọng số chuẩn hóa Vĩ thế, khi thủ tục con này thực hiện, nó sẽ kết nối các tập mục thường xuyên có trọng số chuẩn hóa ưong Lk_i với một trong số các mục có trọng số nhỏ hơn để lập thành một tập cha bậc thấp... có ừọng số của chúng và nhập các tập mục thường xuyên có trọng số chuẩn hóa tìm được vào tập Lk Tập Lk này cũng sẽ là tập các ứng viên được sử dụng để tạo các tập mục cha có khả năng là tập mục thường xuyên có trọng số chuẩn hóa tại vòng lặp tiếp theo Cấu trúc của thuật toán MINWAL(W) tương tự như thuật toán Apriori, nhưng về chi tiết có một số khác biệt Mặc dù các k -tập mục thường xuyên có trọng số. .. phá dữ liệu và học máy, có ý nghĩa khoa học và thực tiễn cao Do đó, tôi chọn đề tài Khai phá tập mục thường xuyên có ttọng số 2 Mục đích nghiên cứu Nắm bắt được kiến thức tổng quan về các phương pháp khai phá tập mục thường xuyên kinh điển và một số phương pháp khai phá tập mục thường xuyên có trọng số, trên cơ sở đó cài đặt, thử nghiệm và đánh giá các thuật toán trên các bộ số liệu mẫu 3 Nhiệm vụ... 2: KHAI PHÁ TÂP MUC THƯỜNG XUYÊN CÓ TRONG SỐ « I • Chương này trình bày thuật toán khai phá tập mục thường xuyên có trọng số MINWAL [5] dựa trên thuật toán Apriori và thuật toán khai phá tập mục thường xuyên có trọng số WFIM dựa trên thuật toán FP-Growth [10] theo hướng tiếp cận cấu trúc cây (FP-Tree) bằng cách đưa vào ràng buộc trọng số là phân khoảng trọng số và ngưỡng trọng số nhỏ nhất 2.1 Thuật... wminsupp X được gọi là tập mục thường xuyên có trọng số chuẩn hóa nếu: NWsupport (x)>wminsupp (2.3) Trường họp ngược lại, X được gọi là tập mục không thường xuyên có trọng số chuẩn hóa Giả sử Y là một q -tập mục con của I và k là một số nguyên thỏa mãn q