i ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA - PHAN CHÍ THỦY PHAN CHÍ THỦY KHOA HỌC MÁY TÍNH LUẬT KẾT HỢP ĐA CẤP VÀ ỨNG DỤNG CHO BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP ĐA CẤP TẠI SIÊU THỊ ĐIỆN MÁY HUY CƯỜNG – QUẢNG NGÃI LUẬN VĂN THẠC SĨ KỸ THUẬT Chuyên ngành: KHOA HỌC MÁY TÍNH KHÓA 2015-2017 Đà Nẵng – Năm 2018 ii ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA - PHAN CHÍ THỦY LUẬT KẾT HỢP ĐA CẤP VÀ ỨNG DỤNG CHO BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP ĐA CẤP TẠI SIÊU THỊ ĐIỆN MÁY HUY CƯỜNG – QUẢNG NGÃI Chuyên ngành : KHOA HỌC MÁY TÍNH Mã số: 60.48.01.01 LUẬN VĂN THẠC SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN KHOA HỌC: TS TRƯƠNG NGỌC CHÂU Đà Nẵng - Năm 2018 iii LỜI CẢM ƠN Trước hết em xin gửi lời cảm ơn chân thành đến tồn thể thầy giáo Khoa Công nghệ Thông tin – Trường Đại học Bách khoa – Đại học Đà Nẵng tận tình dạy dỗ chúng em suốt trình học tập nghiên cứu trường Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc đến Thầy giáo TS Trương Ngọc Châu – Giảng viên chính, Khoa Cơng nghệ Thơng tin – Trường Đại học Bách khoa – Đại học Đà Nẵng quan tâm hướng dẫn đưa gợi ý, góp ý, chỉnh sửa vơ q báu cho em trình làm luận văn tốt nghiệp Cuối xin chân thành cảm ơn người bạn, đồng nghiệp, gia đình tạo điều kiện giúp đỡ, chia với em suốt trình làm luận văn Đà Nẵng, ngày 09 tháng 11 năm 2017 HỌC VIÊN Phan Chí Thủy iv LỜI CAM ĐOAN Tơi cam đoan cơng trình nghiên cứu riêng hướng dẫn Thầy TS Trương Ngọc Châu Các số liệu, kết nêu luận văn trung thực chưa công bố cơng trình khác Đà Nẵng, ngày 09 tháng 11 năm 2017 Tác giả luận văn Phan Chí Thủy v MỤC LỤC Trang phụ bìa Lời cảm ơn i Lời cam đoan ii Mục lục iii Tóm tắt luận văn v Danh mục ký hiệu, từ viết tắt vi Danh mục bảng vii Danh mục hình vẽ viii MỞ ĐẦU CHƯƠNG TỔNG QUAN KHAI PHÁ DỮ LIỆU 1.1 Các khái niệm 1.1.1 Khai phá liệu 1.1.2 Các kĩ thuật khai phá liệu 1.2 Khai phá luật kết hợp 1.2.1 Các khái niệm 1.2.1.1 Mục (Item) 1.2.1.2 Tập mục (Itemset) 1.2.1.3 Giao dịch (Transaction) 1.2.1.4 Độ hỗ trợ tập mục 1.2.1.5 Tập mục phổ biến 1.2.1.6 Luật kết hợp 1.2.1.7 Độ hỗ trợ độ tin cậy luật kết hợp 1.2.2 Phân loại luật kết hợp 1.2.2.1 Luật kết hợp nhị phân 1.2.2.2 Luật có thuộc tính số thuộc tính hạng mục 10 1.2.2.3 Luật kết hợp đơn mức 11 1.2.2.4 Luật kết hợp đa mức 11 1.2.3 Ứng dụng luật kết hợp 12 1.3 Một số thuật toán khai phá luật kết hợp: 12 1.3.1 Phát biểu toán 12 1.3.2 Thuật toán Apriori 12 1.3.2.1 Thuật toán 13 1.3.2.2 Cách sinh luật từ tập mục phổ biến 16 1.3.3 Thuật toán FP-Growth 17 1.3.3.1 Giới thiệu 17 1.3.3.2 Cấu trúc FP- Tree 17 1.3.3.3 Xây dựng FP-Tree 18 vi 1.3.3.4 Ví dụ minh họa xây dựng FP - Tree 18 1.3.3.5 Khai phá FP-Tree để tìm tập mục phổ biến 22 CHƯƠNG KHAI PHÁ LUẬT KẾT HỢP ĐA CẤP DỰA TRÊN .….25 TẬP MỤC PHỔ BIẾN NGUYÊN THỦY 25 2.1 Luật kết hợp đa cấp 25 2.2 Một số phương pháp khai phá luật kết hợp đa cấp 26 2.2.1 Khai phá luật kết hợp đa cấp dựa ma trận logic 26 2.2.1.1 Giới thiệu: 26 2.2.1.2 Thuật toán: 26 2.2.1.3 Ví dụ minh họa 26 2.2.3 Khai phá luật kết hợp đa cấp dựa tập mục phổ biến nguyên thủy 34 2.2.3.1 Giới thiệu: 34 2.2.3.2 Thuật toán 35 2.2.3.3 Ví dụ minh họa: 35 2.3 Kết luận: 45 CHƯƠNG CÀI ĐẶT THỰC NGHIỆM, ỨNG DỤNG CHO BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP ĐA CẤP TẠI SIÊU THỊ ĐIỆN MÁY HUY CƯỜNG – QUẢNG NGÃI46 3.1 Dữ liệu đầu vào: 46 3.1.1 Bảng giao tác liệu lưu trữ file Context.txt theo quy ước: 46 3.1.2 Giá trị độ hỗ trợ tối thiểu minsup (s) 47 3.1.3 Giá trị độ tin cậy tối thiểu minconf (c) 47 3.2 Dữ liệu đầu ra: 47 3.3 Cài đặt chương trình: 47 3.4 Phân tích, nhận xét kết thực nghiệm: 49 3.5 Kết luận: 49 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 50 DANH MỤC TÀI LIỆU THAM KHẢO 51 PHỤ LỤC 52 QUYẾT ĐỊNH GIAO ĐỀ TÀI BẢN SAO KẾT LUẬN CỦA HỘI ĐỒNG, BẢN SAO NHẬN XÉT CỦA CÁC PHẢN BIỆN vii TÓM TẮT LUẬN VĂN LUẬT KẾT HỢP ĐA CẤP VÀ ỨNG DỤNG CHO BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP ĐA CẤP TẠI SIÊU THỊ ĐIỆN MÁY HUY CƯỜNG – QUẢNG NGÃI Học viên: PHAN CHÍ THỦY Mã số: Chun ngành: KHOA HỌC MÁY TÍNH Khóa: 2016-2018 Trường Đại học Bách khoa - ĐHĐN Tóm tắt - Ngày nay, lĩnh vực kinh doanh nói chung tốn kinh doanh mặt hàng siêu thị nói riêng vấn đề cạnh tranh, đầy biến động Trãi qua thời gian, đơn vị/tổ chức hoạt động lĩnh vực này, lưu trữ khối lượng liệu khổng lồ Khi lưu trữ khối liệu này, họ hy vọng rằng, chúng chứa đựng thơng tin thực có giá trị, để trợ giúp cho việc định đắn kịp thời tại, có chiến lược phát triển kinh doanh hợp lý bền vững tương lai Xuất phát từ nhu cầu thực tế này, Khai phá liệu (KPDL) sở liệu (CSDL) xu hướng quan trọng công nghệ thông tin (CNTT) giới, hướng tiếp cận hiệu sử dụng luật kết hợp (Association rules), nhằm phát mối liên hệ có tính phổ biến thành phần liệu sở liệu, khai phá luật kết hợp đa cấp hướng hứa hẹn đầy triển vọng Từ khóa – Công nghệ thông tin; Khai phá liệu; Luật kết hợp; Luật kết hợp đa cấp; Cơ sở liệu; Thơng tin; Tính phổ biến; Quyết định; Chiến lược; Kinh doanh; Siêu thị THE MULTI-LEVEL ASSOCIATION RULES AND APPLICATION FOR PROBLEM OF MINING MULTI-LEVEL ASSOCIATION RULES AT HUY CUONG – QUANG NGAI MACHINE ELECTRIC SUPERMARKET Abstract – Nowdays, the business areas in general and the business problem of Items in supermarkets in particular, are a matter of competition, full of change Over time, the units/organizations active in this field, has been hosting a huge volume of data When storing this data blocks, they hope that, in them shall contain such information is really valuable, In order to help the decision-making right and timely in the present, as well as strategies developing rational and sustainable business in the future Derived from this fact needs, data mining in the DATABASE has been and is a significant trend of the information technology (IT) world, one of the most efficient approach is to use the association rules, which aims to uncover the popular relationships between the data elements in the DATABASE, in which mining multilevel association rules are directions promises full prospects Key words – Information Technology; Data Mining; Asociation Rules; Multil-level Association Rules; Databases; Information; Prequent; Decision; Strategy; Business; Supermarkets viii DANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT CÁC KÝ HIỆU: c s F-List F-List(l) F-ListP FP(l)-Tree FP-TreeP k-Itemset Lk Ck  Độ tin cậy tối thiểu Độ hỗ trợ tối thiểu Danh sách tập mục phổ biến gồm phần tử FP-Tree Danh sách tập mục phổ biến gồm phần tử mức l Danh sách tập mục phổ biến gồm phần tử FP-TreeP Cây FP-Tree mức khái niệm l Cây FP-Tree dựa mơ hình điều kiện nút P Tập mục gồm có k phần tử Tập mục phổ biến có k phần tử Tập ứng viên có k phần tử Rỗng, khơng có phần tử CÁC TỪ VIẾT TẮT: CFP The algorithm for Constructing FP(l)-Tree CSDL Cơ sở liệu KPDL Khai phá liệu MHĐK Mơ hình điều kiện MLBL Multilevel Association Rule Based on Boolean Matrix TMPB Tập mục phổ biến FP-Tree Frequent Pattern-Tree ix DANH MỤC CÁC BẢNG Số hiệu bảng 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 3.1 3.2 3.3 Tên bảng Trang Bảng liệu giao dịch D Hệ thống liệu bán hàng đơn giản Bảng liệu giao dịch D Bảng liệu giao dịch D, với thuộc tính người Bảng liệu hệ thống bán hàng Hệ thống sở liệu đơn giản Tập mục xếp theo độ hỗ trợ giảm dần Bảng F-List Các giao tác xếp theo bảng F-List Bảng tổng hợp kết xây dựng MHĐK tổng quát FP-Tree tương ứng Hệ thống liệu giao dịch cửa hàng thực phẩm Bảng mã hóa mặt hàng thực phẩm Bảng mã hóa mặt hàng theo mức khái niệm Hệ thống liệu giao dịch cửa hàng điện tử Bảng mã hóa mặt hàng điện tử theo mức khái niệm Bảng mã hóa mặt hàng điện tử Bảng F-List(0) mức nguyên thủy Luật kết hợp mức nguyên thủy Luật kết hợp mức Luật kết hợp mức Tri thức phát từ Luật kết hợp mức (Mức nguyên thủy) Tri thức phát từ Luật kết hợp mức Tri thức phát từ Luật kết hợp mức 10 10 14 19 19 20 20 24 26 28 28 35 36 36 37 42 44 45 52 57 58 x DANH MỤC CÁC HÌNH VẼ Số hiệu hình vẽ 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10 1.11 1.12 1.13 1.14 1.15 1.16 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 2.17 2.18 2.19 2.20 2.21 Tên hình vẽ Quá trình phát tri thức Dữ liệu phân cấp khái niệm Tập mục phổ biến L1 Tập mục ứng cử C2 tập mục phổ biến L2 Tập mục ứng cử C3 tập mục phổ biến L3 Tập mục ứng cử C4 Cây FP-Tree khởi tạo Cây FP-Tree sau thực xong giao dịch thứ Cây FP-Tree sau thực xong giao dịch thứ hai Cây FP-Tree sau thực xong giao dịch thứ ba Cây FP-Tree sau thực xong giao dịch thứ tư Cây FP-Tree toàn cục Cây FP-Tree MHĐK “P” (cây FP-TreeP) Cây FP-TreeM MHĐK “M” Cây FP-TreeAM MHĐK “AM” Cây FP-TreeCM MHĐK “CM” Hệ thống phân cấp khái niệm mặt hàng thực phẩm Ma trận 1-Itemset mức Ma trận 1-Itemset mức Ma trận 2-Itemset phổ biến mức Ma trận 3-Itemset phổ biến mức Ma trận 1-Itemset mức Ma trận 1-Itemset phổ biến mức Ma trận 2-Itemset mức Ma trận 2-Itemset phổ biến mức Ma trận 3-Itemset phổ biến mức Ma trận 1-Itemset phổ biến mức Ma trận 2-Itemset mức Ma trận 3-Itemset mức Hệ thống phân cấp khái niệm mặt hàng điện tử Cây FP(0)-Tree sau đọc xong giao dịch thứ Cây FP(0)-Tree hoàn chỉnh Cây FP(l)-tree bước Cây FP(l)-Tree bước Cây FP(l)-Tree bước Cây FP(1)-Tree hoàn chỉnh Cây FP(2)-Tree hoàn chỉnh Trang 11 15 15 15 16 20 20 21 21 21 22 23 23 23 24 27 29 29 30 30 31 31 31 32 32 33 33 34 35 37 37 38 38 39 39 39 56 #CONF: 0.75 51 112 ==> 111 221 331 #SUP: #CONF: 1.0 52 111 ==> 112 221 331 #SUP: #CONF: 0.75 Mitsumi”, khả khách hàng mua thêm: “Máy tính xách tay IBM”; “Máy tính xách tay VIO” “Máy in b/w Canon” là: 75% Nếu khách hàng mua: “Máy tính xách tay VIO”, khả khách hàng mua thêm: “Máy tính xách tay IBM”; “Phụ kiện máy tính chuột Mitsumi” “Máy in b/w Canon” là: 100% Nếu khách hàng mua: “Máy tính xách tay IBM”, khả khách hàng mua thêm: “Máy tính xách tay VIO”; “Phụ kiện máy tính chuột Mitsumi” “Máy in b/w Canon” là: 75% 57 PHỤ LỤC BẢNG 3.2 – TRI THỨC PHÁT HIỆN ĐƯỢC TỪ LUẬT KẾT HỢP Ở MỨC TT 10 11 12 13 14 Luật kết hợp Tri thức phát từ Luật kết hợp Nếu khách hàng mua: “Phụ kiện máy tính Chuột”, 22 ==> 11 #SUP: #CONF: 0.8 khả khách hàng mua thêm: “Máy tính Xách tay” là: 80% Nếu khách hàng mua: “Máy tính Xách tay”, 11 ==> 22 #SUP: #CONF: 1.0 khả khách hàng mua thêm: “Phụ kiện máy tính Chuột” là: 100% Nếu khách hàng mua: “Máy in B/w”, khả 33 ==> 11 #SUP: #CONF: 1.0 khách hàng mua thêm: “Máy tính Xách tay” là: 100% Nếu khách hàng mua: “Máy tính Xách tay”, 11 ==> 33 #SUP: #CONF: 0.75 khả khách hàng mua thêm: “Máy in B/w” là: 75% Nếu khách hàng mua: “Máy in B/w”, khả 33 ==> 22 #SUP: #CONF: 1.0 khách hàng mua thêm: “Phụ kiện máy tính Chuột” là: 100% Nếu khách hàng mua: “Phụ kiện máy tính Chuột”, 22 ==> 33 #SUP: #CONF: 0.6 khả khách hàng mua thêm: “Máy in B/w” là: 60% Nếu khách hàng mua: “Phần mềm Giáo dục”, 44 ==> 22 #SUP: #CONF: 1.0 khả khách hàng mua thêm: “Phụ kiện máy tính Chuột” là: 100% Nếu khách hàng mua: “Phụ kiện máy tính Chuột”, 22 ==> 44 #SUP: #CONF: 0.6 khả khách hàng mua thêm: “Phần mềm Giáo dục” là: 60% Nếu khách hàng mua: “Phụ kiện máy tính Chuột” 22 33 ==> 11 #SUP: #CONF: 1.0 Máy in B/w”, khả khách hàng mua thêm: “Máy tính Xách tay” là: 100% Nếu khách hàng mua: “Máy tính Xách tay” 11 33 ==> 22 #SUP: #CONF: 1.0 Máy in B/w”, khả khách hàng mua thêm: “Phụ kiện máy tính Chuột” là: 100% Nếu khách hàng mua: “Máy tính Xách tay” 11 22 ==> 33 #SUP: #CONF: 0.75 “Phụ kiện máy tính Chuột”, khả khách hàng mua thêm: “Máy in B/w” là: 75% Nếu khách hàng mua: “Máy in B/w”, khả 33 ==> 11 22 #SUP: #CONF: 1.0 khách hàng mua thêm: “Máy tính Xách tay” “Phụ kiện máy tính Chuột” là: 100% Nếu khách hàng mua: “Phụ kiện máy tính Chuột”, 22 ==> 11 33 #SUP: #CONF: 0.6 khả khách hàng mua thêm: “Máy tính Xách tay” “Máy in B/w” là: 60% Nếu khách hàng mua:“Máy tính Xách tay”, khả 11 ==> 22 33 #SUP: #CONF: 0.75 khách hàng mua thêm:“Phụ kiện máy tính 58 Chuột” “Máy in B/w” là:75% 59 PHỤ LỤC BẢNG 3.3 – TRI THỨC PHÁT HIỆN ĐƯỢC TỪ LUẬT KẾT HỢP Ở MỨC TT 10 11 12 13 14 Luật kết hợp Tri thức phát từ Luật kết hợp Nếu khách hàng mua: “Phụ kiện máy tính”, khả ==> #SUP: #CONF: 0.8 khách hàng mua thêm: “Máy tính” là: 80% Nếu khách hàng mua: “Máy tính”, khả khách ==> #SUP: #CONF: 1.0 hàng mua thêm: “Phụ kiện máy tính” là: 100% Nếu khách hàng mua: “Máy in”, khả khách ==> #SUP: #CONF: 1.0 hàng mua thêm: “Máy tính” là: 100% Nếu khách hàng mua: “Máy tính”, khả khách ==> #SUP: #CONF: 0.75 hàng mua thêm: “Máy in” là: 75% Nếu khách hàng mua: “Máy in”, khả khách ==> #SUP: #CONF: 1.0 hàng mua thêm: “Phụ kiện máy tính” là: 100% Nếu khách hàng mua: “Phụ kiện máy tính”, khả ==> #SUP: #CONF: 0.6 khách hàng mua thêm: “Máy in” là: 60% Nếu khách hàng mua: “Phần mềm”, khả ==> #SUP: #CONF: 1.0 khách hàng mua thêm: “Phụ kiện máy tính” là:100% Nếu khách hàng mua: “Phụ kiện máy tính”, khả ==> #SUP: #CONF: 0.6 khách hàng mua thêm: “Phần mềm” là: 60% Nếu khách hàng mua: “Phụ kiện máy tính” “Máy ==> #SUP: #CONF: 1.0 in”, khả khách hàng mua thêm: “Máy tính” là: 100% Nếu khách hàng mua: “Máy tính” “Máy in”, khả ==> #SUP: #CONF: 1.0 khách hàng mua thêm: “Phụ kiện máy tính” là: 100% Nếu khách hàng mua: “Máy tính” “Phụ kiện máy ==> #SUP: #CONF: 0.75 tính”, khả khách hàng mua thêm: “Máy in” là: 75% Nếu khách hàng mua: “Máy in”, khả khách ==> #SUP: #CONF: 1.0 hàng mua thêm: “Máy tính” “Phụ kiện máy tính” là: 100% Nếu khách hàng mua: “Phụ kiện máy tính”, khả ==> #SUP: #CONF: 0.6 khách hàng mua thêm: “Máy tính” “Máy in” là: 60% Nếu khách hàng mua: “Máy tính”, khả khách ==> #SUP: #CONF: 0.75 hàng mua thêm: “Phụ kiện máy tính” “Máy in” là: 75% 60 61 62 63 64 65 I 66 67 ',d 68 ( ... - PHAN CHÍ THỦY LUẬT KẾT HỢP ĐA CẤP VÀ ỨNG DỤNG CHO BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP ĐA CẤP TẠI SIÊU THỊ ĐIỆN MÁY HUY CƯỜNG – QUẢNG NGÃI Chuyên ngành : KHOA HỌC MÁY TÍNH Mã số: 60.48.01.01... TẮT LUẬN VĂN LUẬT KẾT HỢP ĐA CẤP VÀ ỨNG DỤNG CHO BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP ĐA CẤP TẠI SIÊU THỊ ĐIỆN MÁY HUY CƯỜNG – QUẢNG NGÃI Học viên: PHAN CHÍ THỦY Mã số: Chuyên ngành: KHOA HỌC MÁY TÍNH... mô thử nghiệm thuật toán khai phá luật kết hợp đa cấp dựa tập mục phổ biến nguyên thủy (Thuật toán CFP) ứng dụng cho toán khai phá luật kết hợp đa cấp siêu thị điện máy Huy Cường - Quảng Ngãi Đối