Luận án Phát triển một số thuật toán phân cụm mờ viễn cảnh và ứng dụng trong dự báo

Nội dung tài liệu: Luận án Phát triển một số thuật toán phân cụm mờ viễn cảnh và ứng dụng trong dự báo

1. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN PHẠM HUY THÔNG PHÁT TRIỂN MỘT SỐ THUẬT TOÁN PHÂN CỤM MỜ VIỄN CẢNH VÀ ỨNG DỤNG TRONG DỰ BÁO LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội, 2020
2. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN PHẠM HUY THÔNG PHÁT TRIỂN MỘT SỐ THUẬT TOÁN PHÂN CỤM MỜ VIỄN CẢNH VÀ ỨNG DỤNG TRONG DỰ BÁO Chuyên ngành: Cơ sở toán học cho tin học Mã số: 9460117.02 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS. TS. Lê Hoàng Sơn 2. PGS. TS. Nguyễn Thị Hồng Minh Hà Nội, 2020
3. 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 hoàn thành dưới sự hướng dẫn khoa học của PGS. TS. Lê Hoàng Sơn và PGS. TS. Nguyễn Thị Hồng Minh. Các kết quả nghiên cứu của tôi được viết chung với các tác giả khác đã được sự nhất trí của đồng tác giả khi đưa vào luận án. Tôi xin cam đoan các kết quả nêu trong luận án là trung thực và chưa được công bố trong bất cứ công trình nào trước thời gian công bố. Tác giả luận án Phạm Huy Thông i
4. LỜI CẢM ƠN Trước hết, tác giả xin được gửi lời cảm ơn chân thành và sâu sắc nhất tới tập thể giáo viên hướng dẫn, PGS. TS. Lê Hoàng Sơn và PGS. TS. Nguyễn Thị Hồng Minh. Thầy, Cô đã trực tiếp hướng dẫn, định hướng chuyên môn, giúp đỡ tận tình, ân cần chỉ dạy giúp cho tác giả có thể hoàn thành luận án này. Tôi xin chân thành gửi lời cảm ơn đến quý thầy cô, các anh chị em đồng nghiệp của Trung tâm Tính toán Hiệu Năng Cao và khoa Toán – Cơ – Tin học, Trường Ðại học Khoa học Tự nhiên đã quan tâm giúp đỡ, tạo điều kiện về nhiều mặt, chỉ bảo tận tình trong quá trình tác giả thực hiện luận án này. Nhờ đó tác giả đã tiếp thu được nhiều ý kiến đóng góp và nhận xét quí báu thông qua các buổi thảo luận seminar để hoàn chỉnh luận án. Xin chân thành cảm ơn Viện Công nghệ Thông tin, Đại học Quốc gia Hà Nội đã hết sức tạo điều kiện về thời gian và công việc để tác giả có thể tập trung hoàn thành quá trình học tập, nghiên cứu và hoàn thiện luận án. Cuối cùng xin cảm ơn gia đình, bạn bè đã cổ vũ và động viên tác giả trong công việc và học tập cũng như trong quá trình thực hiện luận án này. Xin chúc mọi người luôn mạnh khoẻ, đạt được nhiều thành tích cao trong công tác, học tập và nghiên cứu khoa học! Hà Nội, ngày tháng năm 2020 Tác giả luận án Phạm Huy Thông ii
5. MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i LỜI CẢM ƠN ............................................................................................................ ii DANH MỤC THUẬT NGỮ VÀ TỪ VIẾT TẮT ...................................................... 3 DANH MỤC BẢNG BIỂU ........................................................................................ 5 DANH MỤC HÌNH VẼ .............................................................................................. 7 MỞ ĐẦU ..................................................................................................................... 9 CHƯƠNG 1. CƠ SỞ LÝ THUYẾT ........................................................................ 20 Tập mờ .............................................................................................................. 20 Độ đo tương tự và đánh giá chất lượng cụm .................................................... 21 Thuật toán phân cụm mờ .................................................................................. 24 Một số thuật toán khác ..................................................................................... 27 1.4.1. Thuật toán tối ưu bầy đàn ........................................................................ 27 1.4.2. Thuật toán DifFuzzy ................................................................................ 28 1.4.3. Thuật toán Dissimilarity .......................................................................... 30 1.4.4. Phương pháp FCM-STAR ....................................................................... 32 Bộ dữ liệu thực nghiệm .................................................................................... 33 Kết luận chương ............................................................................................... 34 CHƯƠNG 2. THUẬT TOÁN PHÂN CỤM MỜ VIỄN CẢNH ............................. 35 2.1. Ý tưởng thuật toán ............................................................................................ 35 2.2. Thuật toán phân cụm mờ viễn cảnh ................................................................. 35 2.2.1. Hàm mục tiêu ........................................................................................... 35 2.2.2. Chi tiết thuật toán ..................................................................................... 39 2.3. Khảo sát tính chất hội tụ của thuật toán ........................................................... 39 2.4. Kết quả thực nghiệm ........................................................................................ 42 2.4.1. Ví dụ minh họa cho FC-PFS .................................................................... 43 1
6. 2.4.2. So sánh chất lượng phân cụm .................................................................. 46 2.4.3. Đánh giá thuật toán qua các tham số ....................................................... 50 2.5. Kết luận chương ............................................................................................... 52 CHƯƠNG 3. MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN PHÂN CỤM MỜ VIỄN CẢNH .. ........................................................................................................ 53 3.1. Thuật toán phân cụm mờ tự động xác định số cụm ......................................... 53 3.1.1. Ý tưởng thuật toán ................................................................................... 53 3.1.2. Chi tiết thuật toán ..................................................................................... 54 3.1.3. Kết quả thực nghiệm ................................................................................ 62 3.2. Thuật toán phân cụm mờ với dữ liệu phức tạp ................................................. 72 3.2.1. Độ đo cho thuộc tính kiểu loại ................................................................. 73 3.2.2. Thuật toán phân cụm với dữ liệu phức tạp (PFCA-CD) ......................... 73 3.2.3. Kết quả thực nghiệm ................................................................................ 77 3.3. Kết luận chương ............................................................................................... 84 CHƯƠNG 4. ỨNG DỤNG CỦA THUẬT TOÁN PHÂN CỤM MỜ VIỄN CẢNH .... 86 4.1. Phương pháp PFC-STAR ................................................................................. 87 4.2. Phương pháp PFC-PFR .................................................................................... 89 4.2.1. Số mờ viễn cảnh tam giác ........................................................................ 90 4.2.2. Số mờ viễn cảnh hình thang .................................................................... 91 4.2.3. Chi tiết thuật toán ..................................................................................... 92 4.3. Kết quả thực nghiệm ........................................................................................ 99 4.4. Kết luận chương ............................................................................................. 107 KẾT LUẬN ............................................................................................................. 108 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ ĐÃ CÔNG BỐ ...... 110 TÀI LIỆU THAM KHẢO ....................................................................................... 111 2
7. DANH MỤC THUẬT NGỮ VÀ TỪ VIẾT TẮT STT Từ viết tắt Từ tiếng anh Ý nghĩa Automatic Fuzzy Thuật toán phân cụm mờ tự 1 AFC-PFS Clustering on Picture động xác định số cụm trên tập Fuzzy Set mờ viễn cảnh 2 ASWC Alternative Silhouette Chỉ số Silhouette thay thế Phương pháp ước lượng số 3 CCE Cluster Count Extraction cụm bằng tiền xử lý dữ liệu Chỉ số chất lượng cụm Davies– 4 DB Davies–Bouldin index Bouldin 5 FCM Fuzzy C-means Thuật toán phân cụm mờ Fuzzy Clustering on Thuật toán phân cụm mờ viễn 6 FC-PFS Picture Fuzzy Set cảnh 7 GA Genetic algorithm Thuật toán di truyền 8 IFS Intuitionistics Fuzzy Set Tập mờ trực cảm 9 KFCM Kernel Fuzzy C-means Phân cụm mờ với hàm nhân Kernel Intuitionistic Phân cụm mờ trực cảm với 10 KIFCM Fuzzy C-means hàm nhân 11 MA Mean Accuracy Độ chính xác trung bình 12 NPM Non-Parametric Method Phương pháp phi tham số Picture Composite 13 PCC Chỉ số viễn cảnh tổng hợp Cardinality Picture Fuzzy Clustering Thuật toán phân cụm mờ viễn 14 PFCA-CD Algorithm for Complex cảnh cho dữ liệu phức tạp Data Picture Fuzzy Clustering Phân cụm mờ viễn cảnh kết 15 PFC-PFR with Picture Fuzzy Rule hợp luật mờ viễn cảnh 3
8. Picture Fuzzy Clustering Phân cụm mờ viễn cảnh kết 16 PFC-STAR with Spatio-temporal hợp hồi quy không-thời gian Autoregressive 17 PFS Picture Fuzzy Set Tập mờ viễn cảnh Particle Swarm 18 PSO Thuật toán tối ưu bầy đàn Optimization 19 T2FS Type 2 Fuzzy Set Tập mờ loại 2 Triangular Picture Fuzzy 20 TPFN Số mờ viễn cảnh tam giác Number Trapezoidal Picture Fuzzy 21 TpPFN Số mờ viễn cảnh hình thang Number Weighted Global – Local Chỉ số dựa trên giá trị trọng số 22 WGLI validity-based index toàn cục – địa phương 4
9. DANH MỤC BẢNG BIỂU Bảng 1.1. Mô tả tập dữ liệu thử nghiệm ................................................................... 33 Bảng 2.1. Thuật toán phân cụm mờ viễn cảnh .......................................................... 39 Bảng 2.2. So sánh chất lượng cụm và thời gian chạy của các thuật toán ( = 0.6) . 46 Bảng 2.3. Các miền phân lớp của thuật toán ............................................................. 49 Bảng 2.4. Thống kê các kết quả tốt nhất của các thuật toán với hệ số khác nhau. 50 Bảng 3.1. Mô tả chi tiết thuật toán AFC-PFS ........................................................... 57 Bảng 3.2. Giá trị của các phần tử trong ví dụ ........................................................... 60 Bảng 3.3. Giá trị của các phần tử sau khi loại bỏ cụm 3 trong ví dụ ........................ 61 Bảng 3.4. Số cụm trung bình của thuật toán với các chỉ số đánh giá khác nhau (giá trị in đậm có nghĩa là một trong những giá trị gần nhất với số các lớp được định sẵn trong cột) ................................................................................................................... 63 Bảng 3.5. Giá trị STD của thuật toán nhận được bằng cách sử dụng chỉ số đánh giá khác nhau như giá trị fitness. .................................................................................... 63 Bảng 3.6. Các giá trị đầu ra trung bình PBM, WGLI và ASWC của các thuật toán bằng cách sử dụng ASWC như giá trị fitness (các giá trị bôi đậm có nghĩa là tốt nhất trong một hàng) ......................................................................................................... 67 Bảng 3.7. Các giá trị đầu ra độ lệch chuẩn (STD) của PBM, WGLI và ASWC của các thuật toán sử dụng ASWC như giá trị fitness ........................................................... 67 Bảng 3.8. Các giá trị trung bình PBM, WGLI và ASWC của các thuật toán sử dụng WGLI như các giá trị fitness (các giá trị bôi đậm có nghĩa là tốt nhất trong một hàng) ............. 67 Bảng 3.9. Các giá trị đầu ra độ lệch chuẩn PBM, WGLI và ASWC của các thuật toán sử dụng WGLI như các giá trị fitness ....................................................................... 68 Bảng 3.10. Các giá trị đầu ra trung bình PBM, WGLI và ASWC của của các thuật toán bằng cách sử dụng PBM như giá trị fitness (các giá trị bôi đậm có nghĩa là tốt nhất trong một hàng) ................................................................................................. 68 Bảng 3.11. Các giá trị đầu ra chuẩn PBM, WGLI và ASWC của của các thuật toán sử dụng PBM như giá trị fitness các giá trị bôi đậm có nghĩa là tốt nhất trong một hàng) ... 69 Bảng 3.12. Thời gian tính toán của các thuật toán (giây) ......................................... 72 5
10. Bảng 3.13. Cách chọn tâm cụm ................................................................................ 74 Bảng 3.14. Thuật toán phân cụm mờ viễn cảnh cho dữ liệu phức tạp ...................... 76 Bảng 3.15. Các giá trị chỉ số đánh giá trung bình của các thuật toán (Giá trị đậm có nghĩa là tốt nhất trong mỗi tập dữ liệu và chỉ số đánh giá) ....................................... 80 Bảng 3.16. Thời gian để đạt được giá trị tốt nhất của các thuật toán (Giá trị đậm có nghĩa là tốt nhất) ........................................................................................................ 82 Bảng 3.17. Giá trị STD cho các chỉ số đánh giá của các thuật toán ......................... 83 Bảng 3.18. Thời gian tính toán (với giá trị STD) của các thuật toán theo giây ........ 84 Bảng 4.1. Thuật toán huấn luyện tham số dựa trên PSO .......................................... 98 Bảng 4.2. So sánh giá trị RMSE của các thuật toán................................................ 100 Bảng 4.3. So sánh giá trị RMSE của các thuật toán................................................ 103 Bảng 4.4. STD của giá trị RMSE của các thuật toán .............................................. 104 6