Luận án Tiến sĩ Toán học: 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:124

Thêm vào BST

Báo xấu

32
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài nghiên cứu, tổng hợp, phân tích và đề xuất thuật toán phân cụm mờ viễn cảnh, kiểm chứng bằng lý thuyết về sự hội tụ của thuật toán và thực nghiệm, so sách hiệu quả so với một số thuật toán phân cụm mờ khác.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Toán học: 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

ĐẠ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
ĐẠ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
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
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
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
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
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
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
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
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
DANH MỤC HÌNH VẼ Hình 1.1. Thuật toán phân cụm FCM .......................................................................25 Hình 1.2. Sơ đồ thuật toán tối ưu PSO ......................................................................27 Hình 1.3. Ảnh mây vệ tinh của bộ dữ liệu 1 .............................................................34 Hình 1.4. Ảnh mây vệ tinh của bộ dữ liệu 2 .............................................................34 Hình 1.5. Ảnh mây vệ tinh của bộ dữ liệu 3 .............................................................34 Hình 2.1. Các cụm tại bước khởi tạo ........................................................................44 Hình 2.2. Các cụm sau bước lặp đầu tiên..................................................................45 Hình 2.3. Kết quả phân cụm cuối cùng .....................................................................45 Hình 2.4. Độ chính xác trung bình của các thuật toán ..............................................48 Hình 2.5. Thời gian tính toán của các thuật toán ......................................................49 Hình 2.6. Giá trị MA của các thuật toán theo hệ số mũ ............................................51 Hình 2.7. Thời gian tính toán của các thuật toán theo hệ số mũ (s)..........................51 Hình 3.1. Lược đồ của thuật toán AFC-PFS .............................................................56 Hình 3.2. Số cụm trung bình của các thuật toán .......................................................64 Hình 3.3. Sự tương quan giữa các thành phần với các cụm của dữ liệu GLASS .....64 Hình 3.4. Sự tương quan giữa các thành phần đầu tiên và thứ hai với các cụm thực trên tập dữ liệu GLASS .............................................................................................66 Hình 3.5. Giá trị ASWC trung bình của các thuật toán với giá trị sai số ..................70 Hình 3.6. Giá trị WGLI trung bình của đầu ra các thuật toán với sai số ..................70 Hình 3.7. Các giá trị trung bình PBM của đầu ra các thuật toán với sai số của tập dữ liệu IRIS, GLASS, IONOSPHERE, HABERMAN và HEART. .............................71 Hình 3.8. Giá trị PBM trung bình của các đầu ra của các thuật toán với sai số của các tập dữ liệu WINE và WDBC ....................................................................................71 Hình 3.9. Sơ đồ thuật toán PFCA-CD.......................................................................75 Hình 3.10. Sự phân bố dữ liệu của bộ dữ liệu STATLOG với hai thuộc tính ..........78 Hình 3.11. Sự phân bố dữ liệu của bộ dữ liệu ABALONE với hai thuộc tính .........78 7
Hình 3.12. Sự phân bố dữ liệu của bộ dữ liệu AUTOMOBILE với hai thuộc tính ..79 Hình 3.13. Sự phân bố dữ liệu của bộ dữ liệu SERVO với hai thuộc tính ...............79 Hình 3.14. Biểu đồ biểu diễn các giá trị MA và RI của tất cả các thuật toán với các tập dữ liệu khác nhau ................................................................................................81 Hình 3.15. Biểu đồ biểu diễn các giá trị của ASWC và DB của tất cả các thuật toán với các tập dữ liệu khác nhau ....................................................................................81 Hình 4.1. Thuật toán PFC-STAR ..............................................................................87 Hình 4.2. Ví dụ về tính toán và huấn luyện trọng số của thuật toán STAR..............88 Hình 4.3. Sơ đồ PFC-PFR .........................................................................................90 Hình 4.4. Số mờ viễn cảnh tam giác của tập mờ viễn cảnh A ..................................90 Hình 4.5. Số mờ viễn cảnh hình thang của tập mờ viễn cảnh A ...............................91 Hình 4.6. Các bước trong thuật toán PFC-PFR ........................................................92 Hình 4.7. RMSE của các thuật toán với dữ liệu trong hình ảnh dự đoán 1 ............102 Hình 4.8. RMSE của các thuật toán với dữ liệu trong hình ảnh dự đoán 2 ............102 Hình 4.9. RMSE của các thuật toán với dữ liệu trong hình ảnh dự đoán 3 ............102 Hình 4.10. Giá trị RMSE của thuật toán PFC-PFR với các cụm khác nhau của dữ liệu 1 ....105 Hình 4.11. Giá trị RMSE của thuật toán PFC-PFR với các cụm khác nhau của dữ liệu 2 ....105 Hình 4.12. Giá trị RMSE của thuật toán PFC-PFR với các cụm khác nhau của dữ liệu 3 ....106 Hình 4.13. Kết quả dự báo của dữ liệu 1 bởi PFC-PFR (A) và PFC-STAR(B) .....106 Hình 4.14. Kết quả dự báo của dữ liệu 2 bởi PFC-PFR (A) và PFC-STAR(B) .....106 Hình 4.15. Kết quả dự báo của dữ liệu 3 bởi PFC-PFR (A) và PFC-STAR(B) .....106 8
MỞ ĐẦU 1. Nhu cầu và ý nghĩa của phân cụm và phân cụm mờ Ngày nay, với sự phát triển về mọi mặt của đời sống từ kinh tế, văn hóa, giáo dục cho đến công nghệ và đặc biệt, lĩnh vực công nghệ thông tin đã có những bước phát triển chóng mặt. Công nghệ thông tin ngày càng khẳng định vai trò quan trọng, làm trung tâm chi phối mọi hoạt động, là cầu nối trao đổi thông tin giữa các thành phần của xã hội toàn cầu, của mọi vấn đề. Như một hệ quả tất nhiên, lượng thông tin, dữ liệu được được thu thập, lưu trữ cũng ngày một lớn hơn và đang phát triển một cách bùng nổ trong những năm gần đây. Chính vì vậy, câu hỏi làm thế nào để trích xuất ra các thông tin, các tri thức từ lượng dữ liệu khổng lồ đó đang là thách thức cũng như mang lại cơ hội nghiên cứu, khám phá cho các nhà khoa học. Khai phá dữ liệu là quá trình xử lý dữ liệu và nhận biết các mẫu và các xu hướng trong thông tin để có thể giúp người dùng đưa ra quyết định hoặc đánh giá. Có nhiều bài toán khai phá dữ liệu như phân lớp, phân cụm, hồi quy, v.v., trong đó bài toán phân cụm dữ liệu là bài toán tương đối phổ biến và có nhiều ứng dụng. Phân cụm dữ liệu là việc sắp xếp các đối tượng dữ liệu vào từng cụm sao cho các phần tử trong cùng một cụm có mức độ tương tự là cao nhất và hai phần tử bất kỳ ở hai cụm khác nhau có mức độ tương tự là thấp nhất. Việc phân cụm như vậy giúp cho việc khai phá dữ liệu, đặc biệt là các bài toán dữ liệu lớn trở nên hiệu quả khi các dữ liệu được phân thành các nhóm với các tính chất đặc trưng. Việc phân cụm này đặc biệt hiệu quả khi dữ liệu có phân bố các cụm tách rời nhau và không chứa nhiễu. Tuy nhiên, với các bộ dữ liệu có sự phân bố các cụm xen kẽ, dữ liệu không chắc chắn, dữ liệu chứa nhiễu hoặc thiếu một số thuộc tính thì cách phân cụm như vậy không hiệu quả. Trên thực tế, mỗi một phần tử trong bộ dữ liệu có thể thuộc về nhiều cụm dữ liệu với các mức độ khác nhau. Để giải quyết vấn đề này, dựa trên lý thuyết về tập mờ của Zadeh [98], Bezdek [12] đã đưa ra thuật toán phân cụm mờ - Fuzzy C-means (FCM) nhằm giải quyết các nhược điểm trên. Thuật toán này được xem như một trong những phương pháp trích rút các quy tắc và luật mờ trong khai phá dữ liệu, trong đó các yếu tố mờ thực sự phổ biến [26, 73, 106]. Phân cụm mờ có nhiều ứng dụng trong thực tế cuộc sống ở nhiều lĩnh vực khác nhau như: 9
- Trong kinh tế: dự báo tỉ giá, dự báo chứng khoán, dự báo tài chính [91-92] - Trong y khoa: Hỗ trợ chuẩn đoán hình ảnh, hỗ trợ tư vấn khám bệnh [1,7,15,16,19,47,51,71,74,95] - Trong thủy văn: dự báo thời tiết ngắn hạn [76] - Trong xử lý ảnh: Phân đoạn ảnh [50,102] - Trong hệ tư vấn: hỗ trợ ra quyết định [44,52] - Trong an ninh: phát hiện lỗi, xâm nhập [46,104] - Trong mạng không dây: đặt các cảm biến, phương pháp truyền tin [2,61] Trong các ứng dụng của phân cụm mờ, bài toán dự báo thời tiết ngắn hạn nổi bật bởi việc kết hợp các kết quả của phân cụm với xử lý ảnh để đưa ra ảnh dự báo đầu ra. Dự báo thời tiết là một ứng dụng khoa học và công nghệ để dự đoán trạng thái của bầu khí quyển tại một vị trí nhất định và nó đóng một vai trò quan trọng trong cuộc sống hàng ngày của con người. Các dự báo thời tiết có độ chính xác cao sẽ làm giảm những rủi ro mà con người có thể phải đối mặt. Một trong những phần quan trọng nhất của dự báo thời tiết là dự báo thời tiết ngắn hạn [87]. Dự báo thời tiết ngắn hạn kết hợp mô tả về trạng thái hiện tại của khí quyển và dự báo ngắn hạn về khí quyển sẽ xẩy ra trong vài giờ tiếp theo [33]. Điều này cho phép nó có thể dự báo các tính chất thời tiết trong ngắn hạn như mưa, mây và các cơn bão với các nguyên nhân rõ ràng trong khoảng thời gian này, theo [58]. Các dữ liệu rada mới nhất, dữ liệu vệ tinh và dữ liệu dựa trên quan sát được sử dụng để phân tích các biến đổi trong phạm vi hẹp như một thành phố và thực hiện một dự báo chính xác cho khoảng thời gian vài giờ sau. Tuy nhiên, quan sát vệ tinh là sự lựa chọn thích hợp cho tất cả các khu vực trong vùng phủ sóng của nó [57,72]. Một vài phương pháp điển hình được sử dụng rộng rãi trong dự báo thời tiết dựa theo các quan sát của hình ảnh vệ tinh cụ thể như [29,59,75-76]. Đặc biệt, Evans [29] sử dụng mô hình tương quan đa kênh cho việc gán nhãn để phân tích chuyển động đám mây. Melgani [59] xây dựng lại bối cảnh hình ảnh đa thời gian và đa quang phổ bị nhiễu đám mây. Shukla và Pal [75] đề xuất một cách tiếp cận để nghiên cứu sự tiến hóa của các tế bào đối lưu. 10
Shukla, Kishtawal và Pal [76] đề xuất một phương pháp để dự đoán các chuỗi hình ảnh vệ tinh kết hợp mô hình hồi quy không thời gian (STAR) với phân cụm mờ (Fuzzy C-Means - FCM) để tăng độ chính xác dự báo. Mặc dù kỹ thuật này đã cho kết quả dự báo tốt hơn so với các phương pháp trong [29,59,75], tuy nhiên nó vẫn không đủ tốt vì những hạn chế của các tập mờ như độ do dự và mơ hồ. Park và Lee [69] trình bày một cách tiếp cận bằng suy diễn mờ và phương pháp tập hợp để dự báo thủy triều đỏ. Theo cách tiếp cận này, suy diễn mờ là một phương pháp dự đoán xuất phát từ một đề xuất gần đúng từ thông tin mơ hồ và kiến thức dựa trên một mô hình mờ. Phương pháp tập hợp sau đó đã được sử dụng để giúp cải thiện độ chính xác của kết quả phân loại và dự đoán. Các tác giả trong [62] đã so sánh các mô hình mạng neuron nhân tạo riêng lẻ và kết hợp (ANN) cho bài toán dự đoán nhiệt độ không khí và điểm sương. Mô hình này được phát triển theo kiến trúc mạng Ward [90] bao gồm một mạng nơ ron ba lớp với các lớp đầu vào, ẩn và đầu ra. Mặc dù dự đoán dựa trên ANN có thể cho độ chính xác cao hơn, nó vẫn có trở ngại bởi một số tham số như hàm khởi động, số lượng các nút trong lớp ẩn, phân phối các nút giữa các lớp của mô hình theo kiểu Ward phải xác định. 2. Các tiếp cận chính đối với phân cụm mờ Các yêu cầu về hệ thống thông minh và tự động đặt FCM vào thách thức lớn trong các ứng dụng như phân tích dữ liệu, nhận dạng mẫu, phân đoạn ảnh, phân tích nhóm vị trí, ảnh vệ tinh và phân tích tài chính. Một số phương pháp cải tiến hoặc lai ghép kết hợp FCM với một số thuật toán tối ưu khác được trình bày trong [6, 7, 23, 40, 65, 85, 86, 101] nhằm nâng cao chất lượng phân cụm. Tuy nhiên, chất lượng phân cụm của FCM thường không đủ tốt do thuật toán này được cài đặt trên cơ cở của các tập mờ truyền thống, trong đó vẫn có những giới hạn về độ thuộc, sự do dự và mơ hồ của các tham số mẫu. Chính vì vậy việc nghiên cứu các thuật toán phân cụm trên các tập mờ nâng cao nhằm mục tiêu giải quyết các nhược điểm này. Đến nay đã có rất nhiều thuật toán phân cụm trên các tập mờ nâng cao như thuật toán phân cụm trên tập mờ loại 2 (T2FS) [57], tập mờ trực cảm, v.v. mang lại chất lượng phân cụm tốt hơn. Nhiều thuật toán phân cụm dựa trên tập mờ loại 2 (T2FS) [57] được đề xuất như trong [38, 41, 55, 64, 66, 88]. Những thuật toán này tập trung vào sự không chắc chắn với bộ mờ hóa mở rộng nhằm điều khiển độ mờ trong FCM. 11
Mặc dù chất lượng phân cụm tốt hơn FCM, nhưng thời gian tính toán khá lớn nên các nghiên cứu thường mở rộng FCM trên tập mờ trực cảm (IFS) [10]. Một số nghiên cứu phát triển FCM trên IFS được đề xuất bởi các tác giả trong [4, 36, 39, 93, 105]. Chaira [15] và Chaira & Panwar [16] giới thiệu thuật toán phân cụm mờ trực cảm dựa trên hàm mục tiêu mới để phân cụm các ảnh chụp CT não nhằm phát hiện các vấn đề bất thường trong não. Một số nghiên cứu khác được đề xuất phát triển trên tập thuộc tính mờ và độ đo mờ để đánh giá chất lượng phân cụm [9,14,27,103]. Lê Hoàng Sơn và cộng sự [77-84] đã đề xuất thuật toán phân cụm mờ trực cảm để phân tích nhân khẩu học dựa vào các kết quả nghiên cứu gần đây liên quan đến IFS và thuật toán phân cụm mờ xác suất. Phân cụm mờ với hàm nhân (KFCM) được áp dụng để nâng cao chất lượng phân cụm của FCM như trong các nghiên cứu [34, 45, 54]. Tổng quan về các thuật toán phân cụm mờ trực cảm được tổng hợp trong [94]. Tuy nhiên, các thuật toán này vẫn cho kết quả vẫn chưa tốt và không phản ánh được nhiều yếu tố như độ “do dự” tồn tại trong nhiều ứng dụng. Vào năm 2014, Bùi Công Cường và cộng sự đã giới thiệu tập mờ viễn cảnh (PFS) [21], là một sự khái quát hóa của tập mờ truyền thống và tập mờ trực cảm. Các mô hình dựa trên PFS có thể được áp dụng cho nhiều tình huống cần ý kiến của con người liên quan nhiều đến các câu trả lời kiểu: đồng ý, do dự, không đồng ý và từ chối trả lời. Các tình huống này có thể cho kết quả rõ ràng hơn trên các thuật toán phân cụm dựa trên IFS. Chính vì vậy việc phát triển thuật toán phân cụm mờ trên PFS sẽ nâng cao độ chính xác phân cụm. Hiện nay các thuật toán phân cụm mờ viễn cảnh mới chỉ dừng lại ở việc đưa ra một số độ đo kết hợp sử dụng phân cụm phân cấp để thực hiện như trong [57] mà chưa xem xét đến việc phân cụm theo cách tiếp cận phân hoạch. 3. Các vấn đề tồn tại của phân cụm mờ Ngoài các nhược điểm về chất lượng cụm, thuật toán FCM và các thuật toán phân cụm trên các tập mờ nâng cao còn có một số nhược điểm khác như xác định số cụm hay xử lý với dữ liệu phức tạp. Thứ nhất, thuật toán FCM và các thuật toán phân cụm trên các tập mờ nâng cao phải xác định trước số cụm trước khi thực hiện phân cụm [32]. Điều này là khá quan trọng vì hiệu suất của một thuật toán phân cụm phụ thuộc rất nhiều vào số lượng các 12
cụm ban đầu [49, 53]. Việc xác định số cụm ban đầu không tốt dẫn đến chất lượng cụm không tốt, chứa nhiễu hoặc các điểm ngoại biên [97]. Qua nghiên cứu, có ba cách tiếp cận cụ thể là quét, tiền xử lý và cắt tỉa đang được sử dụng nhiều nhất. - Quét: Là cách đơn giản nhất mà trong đó số cụm trong miền cho trước và chọn một cụm có chất lượng cụm tốt nhất trong các chỉ số có giá trị như số cụm cuối cùng. Cách tiếp cận này được sử dụng trong các nghiên cứu của Alp Erilli và cộng sự [5], Arima và cộng sự [8], Fang và Wang [30], Fujita và cộng sự [32], Lee và Olafsson [49], Liang và cộng sự [53]. Tuy nhiên, độ phức tạp tính toán là nhược điểm chính của cách tiếp cận này vì nó phải quét tất cả các ứng viên để tìm ứng viên tốt nhất. Do đó, theo phương pháp này thì thời gian tính toán tỷ lệ thuận với độ lớn của tập dữ liệu và miền ứng viên. - Tiền xử lý: Phương pháp này sử dụng phân tích thống kê để ước tính số lượng cụm phù hợp nhất theo phân phối dữ liệu. Các phương pháp thống kê có thể là lý thuyết đại số [35] hay đánh giá trực quan của xu hướng cho các cụm dựa trên thuật toán của Pakhira [68]. Tuy nhiên, một số nhược điểm của cách tiếp cận này vẫn còn tồn tại chính là việc xử lý độc lập với các hoạt động phân cụm, khả năng xử lý dữ liệu bị chồng chéo và độ phức tạp tính toán cao. - Cắt tỉa: cách tiếp cận này ước tính cả số cụm phù hợp nhất và xác định kết quả đầu ra cụm. Bắt đầu với một số cố định các cụm, trong mỗi quá trình lặp, chúng sử dụng các chỉ số có giá trị để kiểm tra chất lượng phân cụm của phân hoạch hiện tại và cố gắng để tăng cường chất lượng đó bằng cách thay đổi số cụm theo một chiến lược nhất định. Bằng tiếp cận đó, cả chất lượng cụm và thời gian tính toán của thuật toán đều được cải thiện. Cách tiếp cận này được mô tả trong công trình của Bai và cộng sự [11], Cheung và Jia [18], Le và cộng sự [48], Maraziotis [56], và Yu và cộng sự [97]. Các chiến lược có thể là một phương pháp lai giữa thuật toán di truyền và cụm mờ trừ [48] và hàm đánh giá chất lượng cụm mới [56, 97]. Tuy nhiên, đôi khi chúng tạo ra số lượng cụm ít hơn mong đợi. Các nghiên cứu đều đã chứng minh được phương pháp cắt tỉa là cách tiếp cận hiệu quả nhất khi thực hiện phân cụm cả về khía cạnh chất lượng các cụm cũng như độ phức tạp tính toán. 13
Thứ hai, xử lý với dữ liệu phức tạp là vấn đề còn tại đối với FCM và các thuật toán phân cụm trên tập mờ nâng cao. Các phương pháp phân cụm trên tập dữ liệu phức tạp được chia thành hai nhóm: loại dữ liệu hỗn hợp bao gồm dữ liệu kiểu loại, dữ liệu số và cấu trúc đặc biệt của dữ liệu. - Trong nhóm thứ nhất, đã có nhiều nghiên cứu về phân cụm cho cả hai loại dữ liệu kiểu loại và số. Hwang [37] mở rộng thuật toán K-means để thực hiện phân cụm cho tập dữ liệu lớn bao gồm các giá trị phân loại. Yang, Hwang và Chen [96] sử dụng thuật toán phân cụm mờ để phân vùng các biến chức năng hỗn hợp bằng cách đưa ra một độ đo không tương tự cho dữ liệu mang tính biểu tượng và dữ liệu mờ. Ji và cộng sự [42-43] đề xuất các thuật toán phân cụm k-prototype là kết hợp giữa giá trị trung bình và tâm cụm mờ để làm mẫu của một cụm và sử dụng một độ đo mới dựa trên sự đồng xuất hiện của các giá trị để đánh giá sự không tương tự giữa các đối tượng dữ liệu và mẫu của cụm. Chen, Wang, Wang và Zhu [17] giới thiệu phương pháp phân cụm mềm cho dữ liệu kiểu loại bằng cách sử dụng lược đồ lựa chọn thuộc tính mềm để mỗi thuộc tính phân loại được gán tự động một trọng số tương quan với sự phân tán được làm mịn trong cụm. Nhiều phương thức dựa trên các ma trận không tương tự để xử lý cho dữ liệu kết hợp được giới thiệu bởi De Carvalho, Lechevallier và De Melo [25]. Ý tưởng chính của các phương pháp này là kết hợp các ma trận khác nhau để có được một phân vùng đồng thuận cuối cùng. Mặc dù các phương pháp này có thể phân vùng dữ liệu hỗn hợp một cách hiệu quả, nhưng chúng lại gặp khó khăn trong việc giải quyết với cấu trúc dữ liệu riêng biệt phức tạp. - Trong nhóm thứ hai, nhiều nhà nghiên cứu đã cố gắng phân vùng cấu trúc phức tạp của dữ liệu có hình học nội tại của các cụm phi cầu và không lồi. Các tác giả trong [20] đề xuất một phương pháp gọi là DifFuzzy kết hợp các ý tưởng từ FCM và khuếch tán trên đồ thị để giải quyết vấn đề của các cụm có cấu trúc hình học phi tuyến phức tạp. Phương pháp này được áp dụng cho một lượng lớn các lớp bài toán phân cụm do không yêu cầu bất kỳ thông tin trước về số các cụm. Ferreira và de Carvalho [31] giới thiệu phương thức phân cụm mờ với hàm nhân dựa trên khoảng cách thích ứng địa phương để phân vùng dữ liệu phức tạp. Ý tưởng chính của các phương pháp này được dựa trên một khoảng cách thích ứng địa phương, trong đó các độ đo tương tự được tính là tổng của các khoảng cách Euclidean giữa các mẫu và tâm cụm được tính riêng lẻ cho mỗi biến bởi giá trị trung bình và hàm hạt nhân. Độ đo 14
tương tự được tối ưu để học các trọng số của các biến trong quá trình phân cụm và để làm tăng hiệu suất của các thuật toán. Tuy nhiên, phương pháp này chỉ có thể xử lý dữ liệu số. Như vậy, thuật toán DifFuzzy [20] và thuật toán phân cụm mờ dựa trên ma trận không tương tự Dissimilarity [25] là hai phương pháp phân cụm điển hình trong mỗi nhóm. 4. Mục tiêu và nội dung nghiên cứu Với kết quả tổng quan những nghiên cứu liên quan, các mục tiêu của luận án được đề xuất như sau: - Mục tiêu 1: Nghiên cứu, tổng hợp, phân tích và đề xuất thuật toán phân cụm mờ viễn cảnh. Kiểm chứng bằng lý thuyết về sự hội tụ của thuật toán và thực nghiệm, so sách hiệu quả so với một số thuật toán phân cụm mờ khác. - Mục tiêu 2: Nghiên cứu, phát triển các thuật toán phân cụm mở rộng trên tập mờ viễn cảnh như: phân cụm với việc xác định số cụm tự động, phân cụm với dữ liệu phức tạp. Kiểm chứng, so sánh hiệu quả so với một số thuật toán liên quan khác. - Mục tiêu 3: Nghiên cứu và phát triển các ứng dụng của thuật toán phân cụm trên tập mờ viễn cảnh vào các bài toán dự báo thời tiết dựa trên ảnh mây vệ tinh. Nội dung nghiên cứu Dựa vào mục tiêu nghiên cứu của luận án, các nội dung nghiên cứu của đề tài được trình bày như sau: - Nội dung 1: Nghiên cứu phát triển thuật toán phân cụm mờ mới trên tập mờ viễn cảnh (FC-PFS). - Nội dung 2: Khảo sát tính chất hội tụ của thuật toán FC-PFS về mặt lý thuyết và kiểm chứng về mặt thực nghiệm trên bộ dữ liệu chuẩn UCI. - Nội dung 3: Đề xuất mở rộng của FC-PFS cho việc phân cụm mờ tự động xác định số cụm. - Nội dung 4: Đề xuất mở rộng của FC-PFS trong xử lý các dữ liệu phức tạp. - Nội dung 5: Xây dựng luật mờ viễn cảnh từ FC-PFS. 15
- Nội dung 6: Ứng dụng luật mờ viễn cảnh trong bài toán dự báo thời tiết ngắn hạn dựa trên ảnh mây vệ tinh. Trong hai nội dung nghiên cứu trên, nội dung 1 và nội dung 2 được trình bày cụ thể trong chương 2, nội dung 3 và nội dung 4 được trình bày chi tiết trong chương 3, nội dung 5 và nội dung 6 được trình bày trong chương 4. 5. Dữ liệu nghiên cứu Tập dữ liệu thực nghiệm trong luận án được lấy từ bộ dữ liệu chuẩn UCI Machine Learning Respository [88] cho các thuật toán phân cụm và bộ dữ liệu ảnh mây vệ tinh được lấy từ [63] với khu vực Đông Nam Á. 6. Phương pháp nghiên cứu Từ sáu nội dung nghiên cứu ở trên, các phương pháp nghiên cứu được đề xuất và thực hiện để hoàn thiện đề tài nghiên cứu, cụ thể như sau: - Khảo cứu: Khảo sát các phương pháp liên quan về phân cụm mờ, xử lý dữ liệu không chắc chắn. - Nghiên cứu gia tăng: Cải tiến, mở rộng thuật toán phân cụm mờ (FCM) trên tập mờ viễn cảnh. - Nghiên cứu lý thuyết: Phân tích và chứng minh một số tính chất về sự hội tụ của mô hình đề xuất. - Nghiên cứu mở rộng: Mở rộng thuật toán FC-PFS trong một số trường hợp đặc biệt. - Nghiên cứu ứng dụng: Ứng dụng mô hình đề xuất cho bài toán dự báo thời tiết ngắn hạn dựa trên ảnh mây vệ tinh. 7. Phạm vi và giới hạn của đề tài nghiên cứu Từ các mục tiêu, nội dung và phương pháp nghiên cứu, phạm vi và giới hạn của đề tài nghiên cứu được đề xuất như sau: - Lý thuyết: Phát triển phân cụm mờ viễn cảnh theo tiếp cận phân hoạch. - Ứng dụng: Áp dụng cho bài toán dự báo thời tiết ngắn hạn dựa trên ảnh mây vệ tinh với việc sử dụng phương pháp hồi quy không thời gian, suy luận mờ và sử dụng luật mờ viễn cảnh. 16