Luận án tiến sĩ: Nghiên cứu luật kết hợp hiếm - Ứng dụng hệ thống thông tin tại ĐHQG Hà Nội

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ -------œ¯•------- CÙ THU THỦY NGHIÊN CỨU PHÁT HIỆN LUẬT KẾT HỢP HIẾM VÀ ỨNG DỤNG LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2013 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ -------œ¯•------- CÙ THU THỦY NGHIÊN CỨU PHÁT HIỆN LUẬT KẾT HỢP HIẾM VÀ ỨNG DỤNG Chuyên ngành: Hệ thống thông tin Mã số: 62 48 05 01 LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. Hà Quang Thụy HÀ NỘI - 2013 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của các đồng tác giả trước khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được công bố trong các công trình nào khác.

Tác giả Cù Thu Thủy 1 LỜI CẢM ƠN Luận án được thực hiện tại Bộ môn Hệ thống thông tin - Khoa Công nghệ thông tin - Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội, dưới sự hướng dẫn khoa học của PGS. Đỗ Văn Thành và PGS. Hà Quang Thụy. Trước tiên tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy Đỗ Văn Thành và thầy Hà Quang Thụy, những người đã đưa tôi đến với lĩnh vực nghiên cứu này.

Các thầy đã tận tình giảng dạy, hướng dẫn giúp tôi tiếp cận và đạt được thành công trong công việc nghiên cứu của mình. Các thầy đã luôn tận tâm động viên, khuyến khích và chỉ dẫn giúp tôi hoàn thành được bản luận án này. Tôi xin bày tỏ lòng biết ơn tới các Thầy Cô thuộc Khoa Công nghệ thông tin và cán bộ Phòng Đào tạo - Trường Đại học Công nghệ, đã tạo mọi điều kiện thuận lợi giúp đỡ tôi trong quá trình học tập và nghiên cứu tại trường. Tôi xin cảm ơn TS.

Yun Sing Koh và GS. Marzena Kryszkiewicz đã chia sẻ những tài liệu và kinh nghiệm nghiên cứu. Tôi xin chân thành cảm ơn PGS. Hồ Thuần, PGS.

Nguyễn Xuân Huy, PGS.TS Đoàn Văn Ban, GS.TS Vũ Đức Thi, PGS.TS Lương Chi Mai, PGS.TS Đỗ Trung Tuấn, PGS. Nguyễn Hà Nam đã đóng góp ý kiến quý báu giúp tôi hoàn thiện bản luận án. Tôi xin cảm ơn tập thể cán bộ, giảng viên Khoa Hệ thống thông tin kinh tế, Ban Giám đốc Học viện Tài chính đã nhiệt tình ủng hộ, hết lòng tạo điều kiện giúp đỡ tôi trong suốt thời gian học tập và nghiên cứu. Sự động viên, cổ vũ của bạn bè là nguồn động lực quan trọng để tôi hoàn thành luận án.

Tôi xin bày tỏ lòng biết ơn sâu sắc tới gia đình, chồng và các con tôi đã tạo điểm tựa vững chắc cho tôi có được thành công như ngày hôm nay. Tác giả Cù Thu Thủy 2 MỤC LỤC LỜI CAM ĐOAN 1 LỜI CẢM ƠN 2 MỤC LỤC 3 DANH MỤC CÁC KÍ HIỆU VÀ CHỮ VIẾT TẮT 6 DANH MỤC CÁC BẢNG 7 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ 8 MỞ ĐẦU 10 Lý do chọn đề tài 10 Mục tiêu cụ thể và phạm vi nghiên cứu của luận án 12 Ý nghĩa khoa học và thực tiễn của luận án 12 Đóng góp của luận án 13 Cấu trúc của luận án 14 Chương 1 – PHÁT HIỆN LUẬT KẾT HỢP VÀ LUẬT KẾT HỢP HIẾM 18 1. Luật kết hợp và phương pháp chung phát hiện luật kết hợp 18 1. Bài toán phát hiện luật kết hợp 18 1.

Quy trình hai bước phát hiện luật kết hợp 19 1. Phát hiện luật kết hợp từ CSDL tác vụ 20 1. Phát hiện luật kết hợp với một ngưỡng độ hỗ trợ 20 1. Phát hiện luật kết hợp với độ hỗ trợ khác nhau 26 1.

Phát hiện luật kết hợp từ CSDL định lượng 33 1. Phát hiện luật kết hợp định lượng 33 1. Phát hiện luật kết hợp mờ 34 1. Phân hoạch mờ 36 1.

Phát hiện luật kết hợp hiếm 38 1. Giới thiệu chung về luật kết hợp hiếm 38 1. Một số hướng nghiên cứu chính phát hiện luật kết hợp hiếm 39 1. Luật hiếm Sporadic 44 3 1.

Khuynh hướng nghiên cứu về luật hiếm 47 Chương 2 - PHÁT HIỆN LUẬT KẾT HỢP HIẾM TRÊN CƠ SỞ DỮ LIỆU TÁC VỤ 49 2. Luật kết hợp Sporadic tuyệt đối hai ngưỡng 49 2. Giới thiệu về luật Sporadic tuyệt đối hai ngưỡng 49 2. Tập Sporadic tuyệt đối hai ngưỡng 50 2.

Thuật toán tìm tập Sporadic tuyệt đối hai ngưỡng đóng 53 2. Luật kết hợp Sporadic không tuyệt đối hai ngưỡng 61 2. Giới thiệu về luật kết hợp Sporadic không tuyệt đối hai ngưỡng 61 2. Tập Sporadic không tuyệt đối hai ngưỡng 62 2.

Thuật toán tìm tập Sporadic không tuyệt đối hai ngưỡng đóng 64 2. Luật kết hợp với ràng buộc mục dữ liệu âm 72 2. Giới thiệu về luật kết hợp với ràng buộc mục dữ liệu âm 72 2. Tập phổ biến có ràng buộc mục dữ liệu âm 74 2.

Thuật toán tìm tập phổ biến với ràng buộc mục dữ liệu âm 77 Chương 3 - PHÁT HIỆN LUẬT KẾT HỢP HIẾM TRÊN CƠ SỞ DỮ LIỆU ĐỊNH LƯỢNG 82 3. Giới thiệu về phát hiện luật kết hợp hiếm trên CSDL định lượng 82 3. Luật kết hợp Sporadic tuyệt đối hai ngưỡng mờ 82 3. Giới thiệu về luật Sporadic tuyệt đối hai ngưỡng mờ 82 3.

Tập Sporadic tuyệt đối hai ngưỡng mờ 83 3. Thuật toán tìm tập Sporadic tuyệt đối hai ngưỡng mờ 84 3. Luật kết hợp Sporadic không tuyệt đối hai ngưỡng mờ 89 3. Giới thiệu về luật Sporadic không tuyệt đối hai ngưỡng mờ 89 3.

Tập Sporadic không tuyệt đối hai ngưỡng mờ 90 3. Thuật toán tìm tập Sporadic không tuyệt đối hai ngưỡng mờ 90 Chương 4 - ỨNG DỤNG LUẬT KẾT HỢP MẪU ÂM VÀ MÔ HÌNH HỒI QUY CHUYỂN TIẾP TRƠN TRONG PHÂN TÍCH VÀ DỰ BÁO KINH TẾ 96 4. Mô hình hồi quy chuyển tiếp trơn 96 4 4. Phân tích hồi quy 96 4.

Mô hình hồi quy chuyển tiếp trơn logistic 97 4. Xây dựng mô hình hồi quy chuyển tiếp trơn logistic 98 4. Ứng dụng luật kết hợp mẫu âm và mô hình hồi quy chuyển tiếp trơn trong xây dựng mô hình phân tích và dự báo chỉ số chứng khoán 100 4. Dữ liệu phục vụ xây dựng mô hình 103 4.

Phát hiện mối quan hệ giữa chỉ số chứng khoán và các cổ phiếu 104 4. Xây dựng mô hình dự báo chỉ số chứng khoán 106 4. Ứng dụng luật kết hợp mẫu âm và mô hình hồi quy chuyển tiếp trơn trong xây dựng mô hình dự báo chỉ số giá tiêu dùng (CPI) 112 4. Dữ liệu phục vụ xây dựng mô hình dự báo chỉ số CPI 113 4.

Phát hiện mối quan hệ giữa giá hàng hóa và chỉ số CPI 114 4. Xây dựng mô hình dự báo chỉ số CPI 115 KẾT LUẬN 121 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ CÓ LIÊN QUAN ĐẾN LUẬN ÁN 123 TÀI LIỆU THAM KHẢO 124 5 DANH MỤC CÁC KÍ HIỆU VÀ CHỮ VIẾT TẮT Kí hiệu Tiếng Anh Tiếng Việt CSDL Database Cơ sở dữ liệu CPI Consumer Price Index Chỉ số giá tiêu dùng GDP Gross Domestic Product Tổng sản phẩm quốc nội CHARM Closed Association Rules Phát hiện luật kết hợp đóng Mining conf Confidence Độ tin cậy NC-CHARM Negative Constrains - Closed Phát hiện luật kết hợp đóng Association Rules Mining với ràng buộc mục dữ liệu âm. minAS Minimum absolute support Độ hỗ trợ cận dưới minConf Minimum confidence Độ tin cậy cực tiểu minSup Minimum support Độ hỗ trợ cực tiểu. Trong luật kết hợp Sporadic hai ngưỡng sẽ được coi là độ hỗ trợ cận dưới.

maxSup Maximum support Độ hỗ trợ cận trên MCISI Mining Closed Imperfectly Phát hiện tập mục Sporadic Sporadic Itemsets tuyệt đối đóng MCPSI Mining Closed Perfectly Phát hiện tập mục Sporadic Sporadic Itemsets không tuyệt đối đóng MFISI Mining Fuzzy Imperfectly Phát hiện tập mục Sporadic Sporadic Itemsets tuyệt đối mờ MFPSI Mining Fuzzy Perfectly Phát hiện tập mục Sporadic Sporadic Itemsets không tuyệt đối mờ. PPI Producer Price Index Chỉ số giá của người sản xuất STR Smooth Transition Regression Hồi quy chuyển tiếp trơn sup Support Độ hỗ trợ WPI Wholesale Price Index Chỉ số giá bán buôn 6 DANH MỤC CÁC BẢNG Bảng 0.1: CSDL tác vụ 16 Bảng 0.2: CSDL định lượng 17 Bảng 1.1: Bảng diễn giải các kí hiệu sử dụng trong thuật toán Apriori 21 Bảng 1.2: Rời rạc hoá thuộc tính định lượng có số giá trị nhỏ 33 Bảng 1.3: Rời rạc hoá thuộc tính định lượng có giá trị số 34 Bảng 2.1: Thông tin về các CSDL giả định 57 Bảng 2.2: Kết quả thực hiện MCPSI và Apriori-Inverse trên CSDL giả định 58 Bảng 2.3: Kết quả thực hiện MCPSI và Apriori-Inverse trên T5I1000D10K 59 Bảng 2.4: Kết quả thực hiện MCPSI và Apriori-Inverse trên CSDL thực 60 Bảng 2.5: Bảng kết quả thử nghiệm trên CSDL T5I1000D10K 69 Bảng 2.6: Bảng kết quả thử nghiệm trên CSDL giả định 70 Bảng 2.7: Thông tin về CSDL thực và kết quả thử nghiệm 70 Bảng 2.8: Kết quả tìm các tập Sporadic không tuyệt đối trên CSDL thực 71 Bảng 2.9: Kết quả thử nghiệm trên tệp dữ liệu Mushroom với minSup = 0,1 71 Bảng 2.10: Kết quả thử nghiệm trên tệp dữ liệu Mushroom với maxSup = 0,5 71 Bảng 2.11: Bảng dữ liệu với các mục dữ liệu âm của ví dụ 2.12: Bảng dữ liệu minh họa cho ví dụ 2.13: Bảng kết quả thử nghiệm thuật toán NC-CHARM 80 Bảng 3.1: CSDL mờ 87 Bảng 3.2: Các thuộc tính và độ hỗ trợ của các thuộc tính 87 Bảng 3.3: Các tập 2-thuộc tính và độ hỗ trợ của các tập dữ liệu 88 Bảng 3.4: Kết quả thực hiện thử nghiệm thuật toán MFPSI 89 Bảng 3.5: Các thuộc tính và độ hỗ trợ của các thuộc tính 92 Bảng 3.6: Các tập 2-thuộc tính và độ hỗ trợ của các tập dữ liệu 92 Bảng 3.7: Tập Sporadic không tuyệt đối mờ tìm được ở Nodes thứ nhất 93 Bảng 3.8: Kết quả thử nghiệm ở trường hợp 5 95 Bảng 4.1: Chỉ số HNX được tính theo mô hình xây dựng và thực tế 109 Bảng 4.2: Chỉ số CPI được tính theo mô hình xây dựng và thống kê 119 7 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 0.1: Phân bố các chủ đề phát hiện luật kết hợp trong nội dung của luận án 15 Hình 1.1: Thuật toán Apriori 22 Hình 1.2: Kết nối Galois và toán tử đóng Galois 24 Hình 1.3: Tính chất của các cặp Tập mục dữ liệu ´ Tập định danh 25 Hình 1.4: Thuật toán CHARM 27 Hình 1.5: Minh họa về các phân hoạch mờ 36 Hình 1.6: Thuật toán Apriori-Inverse 45 Hình 1.7: Thuật toán MIISR 46 Hình 2.1: Thuật toán MCPSI 54 Hình 2.2: Không gian tìm kiếm tập Sporadic tuyệt đối hai ngưỡng 56 Hình 2.3: Biểu đồ so sánh kết quả thực hiện MCPSI và Apriori-Inverse trên các CSDL giả định 59 Hình 2.