Nội dung

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM ĐÌNH PHONG PHÁT TRIỂN MỘT SỐ PHƯƠNG PHÁP THIẾT KẾ HỆ PHÂN LỚP TRÊN CƠ SỞ LÝ THUYẾT TẬP MỜ VÀ ĐẠI SỐ GIA TỬ LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Hà Nội - 2017 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Đình Phong PHÁT TRIỂN MỘT SỐ PHƯƠNG PHÁP THIẾT KẾ HỆ PHÂN LỚP TRÊN CƠ SỞ LÝ THUYẾT TẬP MỜ VÀ ĐẠI SỐ GIA TỬ Chuyên ngành: Khoa học máy tính Mã số: 62 48 01 01 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. GS. TS. Nguyễn Thanh Thủy 2. PGS. TSKH. Nguyễn Cát Hồ Hà Nội – 2017 LỜI CAM ĐOAN Tôi xin cam đoan rằng, ngoại trừ các nội dung được trích từ tài liệu tham khảo hoặc các công trình khác như đã được ghi rõ trong luận án, các kết quả được trình bày trong luận án này là công trình nghiên cứu của tôi và được hoàn thành dưới sự hướng dẫn của GS. TS. Nguyễn Thanh Thủy và PGS. TSKH. Nguyễn Cát Hồ. Các kết quả nghiên cứu là trung thực, chưa từng được công bố trước đó. Các kết quả được viết chung với các tác giả khác đã được sự đồng ý của các đồng tác giả trước khi đưa vào luận án. Tác giả luận án Phạm Đình Phong ii LỜI CẢM ƠN Với lòng biết ơn sâu sắc, tôi xin chân thành cảm ơn các thầy GS. TS. Nguyễn Thanh Thủy và PGS. TSKH. Nguyễn Cát Hồ đã trực tiếp chỉ bảo và tận tình hướng dẫn tôi hoàn thành luận án này. Tôi chân thành cảm ơn thầy TS. Trần Thái Sơn đã có nhiều hỗ trợ trong quá trình nghiên cứu và có những nhận xét, đánh giá trong quá trình hoàn thiện luận án. Tôi xin được bày tỏ lòng biết ơn đối với các thầy giáo, cô giáo Bộ môn Khoa học máy tính, Khoa Công nghệ thông tin, Phòng đào tạo, Ban giám hiệu Trường Đại học Công nghệ đã tận tình chỉ bảo, giảng dạy và tạo điều kiện thuận lợi trong suốt thời gian học tập, nghiên cứu và hoàn thành luận án. Tôi xin được cảm ơn tất cả những người thân, bạn bè và các đồng nghiệp đã tạo điều kiện, động viên và hỗ trợ tôi về mọi mặt. Cuối cùng, tôi xin được được bày tỏ tình cảm và lòng biết ơn vô hạn tới bố mẹ và những người thân trong gia đình, đặc biệt là vợ tôi – Phan Thị Quế Anh, người đã luôn động viên, khích lệ, chia sẻ và gánh vác công việc để tôi có thời gian học tập, nghiên cứu và hoàn thành luận án. iii MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i LỜI CẢM ƠN ........................................................................................................... iii MỤC LỤC ................................................................................................................. iv DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT .............................................. vii DANH MỤC CÁC BẢNG........................................................................................ ix DANH MỤC CÁC HÌNH VẼ, BIỂU ĐỒ .............................................................. xiii MỞ ĐẦU .....................................................................................................................1 CHƯƠNG 1 TỔNG QUAN VỀ HỆ DỰA TRÊN LUẬT NGÔN NGỮ MỜ ............9 1.1. MỘT SỐ KHÁI NIỆM CƠ BẢN .................................................................. 9 1.1.1. Tập mờ...................................................................................................9 1.1.2. Biến ngôn ngữ .......................................................................................9 1.1.3. Phân hoạch mờ ....................................................................................10 1.1.4. Luật ngôn ngữ mờ và hệ luật ngôn ngữ mờ ........................................11 1.1.5. Bài toán phân lớp dữ liệu ....................................................................12 1.2. HỆ DỰA TRÊN LUẬT NGÔN NGỮ MỜ ................................................. 12 1.2.1. Cấu trúc của hệ dựa trên luật ngôn ngữ mờ ........................................13 1.2.2. Bài toán thiết kế hệ phân lớp dựa trên luật ngôn ngữ mờ ...................14 1.2.3. Những vấn đề tồn tại ...........................................................................19 1.3. ĐẠI SỐ GIA TỬ .......................................................................................... 19 1.3.1. Đại số gia tử của biến ngôn ngữ ..........................................................20 1.3.2. Lượng hóa đại số gia tử .......................................................................22 1.3.3. Ý nghĩa ứng dụng của đại số gia tử .....................................................25 1.3.4. Những vấn đề còn tồn tại ....................................................................28 1.4. KẾT LUẬN CHƯƠNG 1 ............................................................................ 29 CHƯƠNG 2 LÕI NGỮ NGHĨA VÀ NGỮ NGHĨA HÌNH THANG CỦA KHUNG NHẬN THỨC NGÔN NGỮ VÀ ỨNG DỤNG GIẢI BÀI TOÁN PHÂN LỚP .....30 2.1. MỞ RỘNG ĐẠI SỐ GIA TỬ CHO VIỆC MÔ HÌNH HÓA LÕI NGỮ NGHĨA CỦA CÁC TỪ NGÔN NGỮ................................................................ 30 iv 2.2. MỞ RỘNG KHÁI NIỆM ĐỘ ĐO TÍNH MỜ ............................................. 37 2.3. HỆ KHOẢNG TÍNH MỜ LIÊN KẾT VỚI ĐỘ ĐO TÍNH MỜ CỦA CÁC TỪ NGÔN NGỮ ................................................................................................ 40 2.4. ÁNH XẠ ĐỊNH LƯỢNG NGỮ NGHĨA KHOẢNG .................................. 44 2.5. MỞ RỘNG ĐỘ ĐO TÍNH MỜ CỦA CÁC PHẦN TỬ 0 VÀ 1 ................. 46 2.6. ỨNG DỤNG LÕI NGỮ NGHĨA VÀ NGỮ NGHĨA HÌNH THANG TRONG THIẾT KẾ HỆ PHÂN LỚP DỰA TRÊN LUẬT NGÔN NGỮ MỜ.. 49 2.6.1. Thiết kế ngữ nghĩa tính toán dựa trên tập mờ của các từ ngôn ngữ ....50 2.6.2. Sinh tập luật khởi đầu từ dữ liệu dựa trên ngữ nghĩa ĐSGT mở rộng 56 2.6.3. Tối ưu các tham số ngữ nghĩa và tìm kiếm hệ luật tối ưu ...................59 2.6.4. Đánh giá kết quả ứng dụng lõi ngữ nghĩa và ngữ nghĩa hình thang trong thiết kế hệ phân lớp dựa trên luật ngôn ngữ mờ ...................................61 2.6.4.1. Dữ liệu và phương pháp thực nghiệm ......................................61 2.6.4.2. So sánh đánh giá hai cấu trúc phân hoạch mờ đơn và đa thể hạt . ..................................................................................................63 2.6.4.3. So sánh đánh giá hai phương pháp lập luận single winner rule và weigted vote ........................................................................................69 2.6.4.4. So sánh đánh giá các phương pháp thiết kế hệ phân lớp theo tiếp cận đại số gia tử ................................................................................71 2.6.4.5. So sánh đánh giá với một số phương pháp theo tiếp cận lý thuyết tập mờ ...........................................................................................73 2.6.4.6. So sánh đánh giá với một số tiếp cận khác...............................77 2.6.5. Biểu diễn ngữ nghĩa tính toán dựa trên tập mờ hình thang đảm bảo tính giải nghĩa được của khung nhận thức ngôn ngữ .....................................79 2.7. KẾT LUẬN CHƯƠNG 2 ............................................................................ 84 CHƯƠNG 3 THIẾT KẾ HIỆU QUẢ HỆ PHÂN LỚP DỰA TRÊN LUẬT NGÔN NGỮ MỜ SỬ DỤNG KỸ THUẬT TÍNH TOÁN MỀM .........................................85 3.1. THIẾT KẾ HIỆU QUẢ HỆ PHÂN LỚP DỰA TRÊN LUẬT NGÔN NGỮ MỜ SỬ DỤNG CÁC THUẬT TOÁN TỐI ƯU ................................................ 85 3.1.1. Đánh giá tính hiệu quả của thuật toán MOPSO so với thuật toán GSA . .............................................................................................................88 v 3.1.1.1. Thuật toán tối ưu bầy đàn đa mục tiêu .....................................88 3.1.1.2. Ứng dụng thuật toán MOPSO tối ưu các tham số ngữ nghĩa và tìm kiếm hệ luật tối ưu .............................................................................92 3.1.1.3. Thực nghiệm so sánh thuật toán MOPSO so với thuật toán GSA ..................................................................................................94 3.1.2. Đánh giá tính hiệu quả của thuật toán MOPSO-SA so với thuật toán MOPSO ..........................................................................................................96 3.1.2.1. Thuật toán tối ưu đa mục tiêu lai MOPSO-SA ........................96 3.1.2.2. Ứng dụng thuật toán MOPSO-SA tối ưu các tham số ngữ nghĩa và tìm kiếm hệ luật tối ưu ........................................................................99 3.1.2.3. Thực nghiệm so sánh thuật toán MOPSO-SA so với thuật toán MOPSO ................................................................................................101 3.2. NÂNG CAO HIỆU QUẢ SINH LUẬT MỜ VỚI NGỮ NGHĨA DỰA TRÊN ĐẠI SỐ GIA TỬ SỬ DỤNG KỸ THUẬT LỰA CHỌN ĐẶC TRƯNG103 3.2.1. Một số khái niệm cơ bản về lý thuyết thông tin ................................104 3.2.2. Kỹ thuật lựa chọn đặc trưng sử dụng trọng số động .........................105 3.2.3. Ứng dụng thuật DWFS trong thiết kế FLRBC trên cơ sở ĐSGT .....107 3.2.4. Kết quả thực nghiệm và thảo luận .....................................................109 3.3. KẾT LUẬN CHƯƠNG 3 .......................................................................... 113 KẾT LUẬN CỦA LUẬN ÁN.................................................................................115 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN ...............................................................................................................117 TÀI LIỆU THAM KHẢO .......................................................................................119 PHỤ LỤC ................................................................................................................... A vi DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Các ký hiệu AX Đại số gia tử tuyến tính AXmp Đại số gia tử mở rộng AXmrtp Đại số gia tử mở rộng toàn phần μ(h) Độ đo tính mờ của gia tử h fm(x) Độ đo tính mờ của từ ngôn ngữ x f(x) Hàm định lượng khoảng của từ ngôn ngữ x μA(x) Hàm xác định độ thuộc của giá trị x vào tập mờ A |x| Độ dài của từ ngôn ngữ x Xk Tập các các từ có độ dài đúng bằng k X(k) Tập các các từ có độ dài nhỏ hơn hoặc bằng k X Biến ngôn ngữ H Tập các gia tử |H| Số lượng gia tử trong H. Hmr Tập các gia tử mở rộng (bổ sung thêm gia tử h0) H+ Tập các gia tử dương H- Tập các gia tử âm H(x) Tập các từ được cảm sinh từ x bởi tác động của các gia tử k(x) Khoảng tính mờ mức k của x RMSR Root mean squared residual Các từ viết tắt ĐSGT Đại số gia tử DB Database (Cơ sở dữ liệu) FLRBC Fuzzy linguistic rule-based classifier (Hệ phân lớp dựa trên luật ngôn ngữ mờ) vii FLRBS fuzzy linguistic rule-based system (Hệ dựa trên luật ngôn ngữ mờ) FURIA Fuzzy unordered rules induction algorithm (Giải thuật cảm sinh các luật mờ không có thứ tự) GSA Genetic simulated annealing (Tôi luyện mô phỏng di truyền) KB Knowledge base (Cơ sở tri thức) LFoC Linguistic frames of cognition (Khung nhận thức ngôn ngữ) MOO Multi-objective optimization (Tối ưu đa mục tiêu) MOPSO Multi-objective particle swarm optimization (Giải thuật tối ưu bầy đàn đa mục tiêu) PAES Pareto archived evolution strategy (Chiến lược tiến hóa lưu trữ Pareto) PI Power set of intervals (Tập các khoảng con có thể) PSO Particle swarm optimization (Tối ưu bầy đàn) RCS Rule and condition selection (Lựa chọn luật và điều kiện luật) RIPPER Repeated incremental pruning to produce error reduction (Giảm lỗi bằng lặp lại cắt tỉa gia tăng) SVM Support vector machine (Máy véc-tơ hỗ trợ) SWR Single winner rule (Luật thắng đơn) WV Weighted vote (Bầu cử có trọng số) viii DANH MỤC CÁC BẢNG TRONG NỘI DUNG CHÍNH Bảng 2.3. So sánh độ chính xác giữa các hệ phân lớp sử dụng cấu trúc đa thể hạt và đơn thể hạt sử dụng kiểm định Wilcoxon Signed Rank với α = 0,05 …………... 68 Bảng 2.4. So sánh độ phức tạp của các hệ phân lớp sử dụng cấu trúc đa thể hạt và đơn thể hạt sử dụng kiểm định Wilcoxon Signed Rank với α = 0,05 …………... 68 Bảng 2.6. So sánh độ chính xác của các hệ phân lớp được thiết kế trên cơ sở ĐSGT AXmr và AXmrtp giữa sử dụng phương pháp lập luận SWR và WV bằng phương pháp kiểm định Wilcoxon Signed Rank với α = 0,05 …………………………...…….. 70 Bảng 2.7. So sánh độ phức tạp của các hệ phân lớp được thiết kế trên cơ sở ĐSGT AXmr và AXmrtp giữa sử dụng phương pháp lập luận SWR và WV bằng phương pháp kiểm định Wilcoxon Signed Rank với α = 0,05 …………………………………. 70 Bảng 2.9. So sánh độ chính xác của FRBC_AXmrtp, FRBC_AXmr và FRBC_AX sử dụng phương pháp kiểm định Wilcoxon Signed Rank với α = 0,05 ……………... 72 Bảng 2.10. So sánh độ phức tạp của FRBC_AXmrtp, FRBC_AXmr và FRBC_AX sử dụng phương pháp kiểm định Wilcoxon Signed Rank với α = 0,05 ……………... 72 Bảng 2.11. So sánh độ chính xác của FRBC_AXmrtp và FRBC_AXmr so với All Granularities và Product-1-ALL TUN sử dụng kiểm định Wilcoxon Signed Rank với α = 0,05 ……...………………………………………………………………. 74 Bảng 2.12. So sánh độ phức tạp của FRBC_AXmrtp và FRBC_AXmr so với All Granularities và Product-1-ALL TUN sử dụng kiểm định Wilcoxon Signed Rank với α = 0,05 ………………………………………………………………………. 75 Bảng 2.14. So sánh độ chính xác của FRBC_AXmrtp và FRBC_AXmr so với hệ phân lớp PAES-RCS sử dụng kiểm định Wilcoxon Signed Rank với α = 0,05 ……..... 77 Bảng 2.15. So sánh độ phức tạp của FRBC_AXmrtp và FRBC_AXmr so với hệ phân lớp PAES-RCS sử dụng kiểm định Wilcoxon Signed Rank với α = 0,05 .……… 77 Bảng 2.16. So sánh độ chính xác của FRBC_AXmrtp và FRBC_AXmr so với FURIA và C4.5 sử dụng kiểm tra Wilcoxon Signed Rank với α = 0,05 …………………. 79 Bảng 2.17. So sánh độ phức tạp của FRBC_AXmrtp và FRBC_AXmr so với FURIA và C4.5 sử dụng kiểm tra Wilcoxon Signed Rank với α = 0,05 ………………..... 79 Bảng 2.18. So sánh các kết quả thực nghiệm giữa hai hệ phân lớp FRBC_AXmrtp_k0 và FRBC_AXmrtp…………………………………………………………………... 82 ix