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

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

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

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

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ự

Clustering on Picture động xác định số cụm trên tập 1 AFC-PFS

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

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

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

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

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

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

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ư:

- 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.

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.

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

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.

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

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.

- 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.

8. Đóng góp chính của luận án

Luận án có bốn đóng góp chính là:

- Đề xuất một thuật toán phân cụm mờ mới trên tập mờ viễn cảnh (FC-PFS)

bằng cách mở rộng hàm mục tiêu của thuật toán phân cụm trên tập mờ trực

cảm. Đồng thời tính chất hội tụ của thuật toán đề xuất cũng được đánh giá về

mặt lý thuyết, sự cần thiết để đảm bảo tính đúng của thuật toán.

- Đưa ra một cải tiến của thuật toán FC-PFS cho việc phân cụm mờ viễn cảnh

tự động xác định số cụm. Phương pháp cải tiến là sự kết hợp của FC-PFS với

thuật toán tối ưu bầy đàn PSO [28] để đưa ra số cụm và kết quả phân cụm tối

ưu cho từng bộ dữ liệu.

- Đưa ra một cải tiến của thuật toán FC-PFS cho việc xử lý với các dữ liệu phức

tạp. Phương pháp này kết hợp FC-PFS với thuật toán tối ưu bầy đàn PSO và

phương pháp phân cụm đa tâm để xử lý hiệu quả với cả dữ liệu số, dữ liệu kiểu

loại và dữ liệu có cấu trúc phức tạp.

- Ứng dụng FC-PFS 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 với hai phương pháp. Phương pháp thứ nhất kết hợp FC-PFS với

phương pháp hồi quy không thời gian. Phương pháp thứ hai đề xuất luật mờ

viễn cảnh mới và phương pháp sinh luật mờ viễn cảnh này từ kết quả của FC-

PFS để dự báo ảnh đầu ra của bài toán.

9. Tính mới của luận án

Trong luận án này, thuật toán phân cụm mờ viễn cảnh (FC-PFS) được đề xuất

để khắc phục các nhược điểm của các thuật toán phân cụm trên tập mờ nâng cao trước

đây. Thuật toán phân cụm trên tập mờ viễn cảnh cung cấp khá đầy đủ thông tin, đặc

biết là sự phù hợp của mô hình với tham số “độ từ chối”. Ngoài ra các kết quả chứng

minh tính chất hội tụ bằng lý thuyết và kiểm chứng chất lượng phân cụm cũng cho thấy

tính hiệu quả của thuật toán phân cụm mờ này. Bên cạnh những ưu điểm của thuật toán

FC-PFS, thuật toán vẫn có một số hạn chế cần khắc phục.

- Thứ nhất là làm thế nào để xác định số lượng cụm phù hợp nhất cho mỗi bộ

dữ liệu. Vì mỗi tập dữ liệu có các tính năng và phân phối mẫu khác nhau nên số lượng

cụm cũng khác nhau. Việc xác định số lượng tối ưu như vậy cho thuật toán phân cụm

sẽ mang lại chất lượng phân cụm tốt nhất. Đồng thời, luận án cũng trình bày một

phương pháp gọi là Phân cụm mờ viễn cảnh tự động xác định số cụm (AFC-PFS) để

xác định số lượng cụm phù hợp nhất cho FC-PFS. Đây là một phương pháp lai giữa

thuật toán tối ưu hóa bầy đàn (PSO) [28] và FC-PFS trong đó các giải pháp kết hợp

bao gồm số cụm, tâm cụm tương đương và ma trận thành viên được đóng gói và tối

ưu hóa trong PSO. Các kết quả thực nghiệm cho thấy AFC-PFS có hiệu suất tốt hơn

các phương pháp liên quan.

- Thứ hai, cũng bởi sự phức tạp và khác nhau về thành phần các trường thuộc

tính cũng như cấu trúc của các bộ dữ liệu mà thuật toán FC-PFS cho kết quả không

đủ tốt như các dữ liệu kiểu kết hợp giữa số và kiểu loại, các dữ liệu có cấu trúc vòng,

hình cầu và một số cấu trúc phức tạp khác. Chính vì vậy luận án cũng đưa ra một

thuật toán cải tiến của FC-PFS được gọi là PFCA-CD có khả năng xử lý dữ liệu kiểu

hỗn hợp (số và kiểu loại) và cấu trúc dữ liệu riêng biệt để xử lý trên các dữ liệu phức

tạp. Ý tưởng của phương pháp này là sửa đổi FC-PFS, sử dụng phép đo mới cho các

thuộc tính phân loại, cho phép một cụm có thể chứa nhiều tâm và một chiến lược tiến

hóa - tối ưu hóa các phương án. Các thí nghiệm chỉ ra rằng thuật toán được đề xuất

dẫn đến chất lượng phân cụm hiệu quả hơn các thuật toán khác thông qua một số chỉ

số đánh giá chất lượng cụm.

- Thứ ba, thuật toán FC-PFS còn được ứng dụng 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 luận án này, hai phương pháp dự báo lai

mới dựa trên phân cụm mờ cho bài toán dự báo thời tiết ngắn hạn được đề xuất.

Phương pháp đầu tiên được đặt tên là PFC-STAR sử dụng kết hợp phân cụm mờ các

hình ảnh vệ tinh và hồi quy không thời gian. Phương pháp thứ hai có tên là PFC-PFR

tích hợp FC-PFS với luật mờ viễn cảnh. Những phương pháp này được trang bị các

quy trình huấn luyện giúp nâng cao độ chính xác của kết quả dự báo. Thực nghiệm

tính toán cho thấy các phương pháp được đề xuất tốt hơn so với các phương pháp liên

quan khác.

10. Bố cục của luận án

- Mở đầu: Trình bày bối cảnh nghiên cứu; tổng quan nhanh và các hạn chế về

bài toán phân cụm mờ; các vấn đề nghiên cứu; mục tiêu nghiên cứu; hướng

tiếp cận và phương pháp nghiên cứu; nội dung nghiên cứu; phạm vi và giới

hạn nghiên cứu; các đóng góp chính và bố cục của luận án.

- Chương 1: Trình bày một số kiến thức cơ sở cho đề tài nghiên cứu, bao gồm:

khái niệm về tập mờ, các thuật toán phân cụm mờ, các thuật toán phân cụm

mờ mở rộng và ứng dụng trong dự báo thời tiết ngắn hạn. Ngoài ra một số độ

đo tiêu chí đánh giá và bộ dữ liệu chuẩn cho thực nghiệm cũng được trình bày

trong chương này.

- Chương 2: Trình bày về thuật toán phân cụm trên tập mờ viễn cảnh, bao gồm:

ý tưởng thuật toán, cách thức triển khai thuật toán, đánh giá sự hội tụ bằng lý

thuyết và thực nghiệm tính toán.

- Chương 3: Trình bày cải tiến của thuật toán phân cụm trên tập mờ viễn cảnh

với việc tự động xác định số cụm và xử lý dữ liệu phức tạp, kèm theo các thực

nghiệm kiểm chứng.

- Chương 4: Áp dụng thuật toán phân cụm mờ viễn cảnh cho bài toán dự báo

thời tiết ngắn hạn từ ảnh mây về tinh.

- Kết luận: Nêu kết quả thu được, hạn chế của đề tài và các hướng nghiên cứu

tương lai.

CHƯƠNG 1. CƠ SỞ LÝ THUYẾT

Trong chương này, các kiến thức cơ sở phục vụ cho luận án được trình bày cụ

thể làm nền tảng phát triển của các thuật toán ở các chương sau.

Tập mờ

Tập mờ (FS) được định nghĩa lần đầu bởi Lotfi Aliasker Zadeh vào năm 1965

[98] như sau:

Định nghĩa 1.1. Một tập mờ (FS) [98] trong một tập nền không rỗng là,

(1.1) ̇ = , ̇ ()|∀ ∈ , ̇ () ∈ [0,1].

trong đó ̇() là độ thuộc của ∈ .

Một mở rộng trực tiếp của tập mờ FS chính là tập mờ loại 2 (T2FS) [60] được

định nghĩa:

Định nghĩa 1.2. Một tập mờ loại 2 (T2FS) [60] trong tập nền không rỗng là,

(1.2) = , , (, )|∀ ∈ , ∀ ∈ ⊆ [0,1].

ở đây là tập con của , (, ) là độ mờ của độ thuộc (), ∀ ∈ . Khi (, ) = 1, được gọi là T2FS khoảng. Tương tự, khi (, ) = 0, trả về tập FS.

Một mở rộng khác của FS chính là tập mờ trực cảm (IFS) [10]. Tập mờ này

được đưa ra bởi Atanassov vào năm 1986 như sau:

Định nghĩa 1.3. Một tập mờ trực cảm (IFS) [10] trong một tập nền không rỗng

là,

(1.3) = {⟨, (), ()⟩| ∈ },

trong đó () là độ thuộc của mỗi phần tử ∈ và () là độ không thuộc thỏa mãn các ràng buộc,

(1.4) (), () ∈ [0,1], ∀ ∈ ,

(1.5) 0 ≤ () + () ≤ 1, ∀ ∈ .

Chỉ số mờ trực cảm là một phần tử (còn được gọi là mức độ do dự) chỉ ra tính

không xác định được ký hiệu là,

(1.6) () = 1 − () − (), ∀ ∈ .

Khi () = 0, IFS trả về tập mờ thường. Độ do dự có thể được tính thông qua

hàm thuộc bởi toán tử Yager [13], đó là,

(1.7) () = 1 − () − (1 − ())/,

Cuối cùng, tập mờ viễn cảnh (PFS) [21] được tác giả Bùi Công Cường đưa ra

lần đầu vào năm 2014, mở rộng trực tiếp từ tập mờ trực cảm.

Định nghĩa 1.4. Tập mờ viễn cảnh (PFS) [21] trong một tập nền không rỗng

là,

(1.8) = {⟨, (), (), ()⟩| ∈ },

trong đó () là độ khẳng định của mỗi phần tử ∈ , () là độ trung lập và () là độ phủ định thỏa mãn các ràng buộc,

(1.9) (), (), () ∈ [0,1], ∀ ∈ ,

(1.10) 0 ≤ () + () + () ≤ 1, ∀ ∈ .

Độ từ chối của một phần tử được tính là () = 1 − () + () +

(), ∀ ∈ . Trong các trường hợp () = 0 PFS trả về tập IFS truyền thống. Rõ ràng, PFS là một sự mở rộng của IFS mà trong đó độ từ chối được thêm vào định

nghĩa. Đó là lý do tại sao nên sử dụng PFS và ý nghĩa quan trọng của tập này trong

các ứng dụng thực tế.

Độ đo tương tự và đánh giá chất lượng cụm

Trong luận án, các độ đo tương tự được sử dụng để đánh giá chất lượng cụm

gồm có độ đo Mean Accuracy (MA) tính giá trị nhỏ nhất các phần tử thuộc về đúng

cụm, chỉ số Davies-Bouldin (DB) [24], chỉ số Rand [89], chỉ số Alternative Silhouette

() [89], chỉ số WGLI [89] và PBM [100]. Trong các chỉ số trên, chỉ số MA và

Rand đánh giá chất lượng cụm thông qua các giá trị cụm có sẵn mà bộ dữ liệu cung

cấp. Chỉ số này nhằm đánh giá xem các phần tử có được phân vào các cụm chính xác

hay không. Các chỉ số còn lại là DB, ASWC, WGLI, PBM là các chỉ số đánh giá nội

tại chất lượng cụm. Tức là các chỉ số này chỉ đánh giá chất lượng cụm thông qua

khoảng cách của các phần tử đối với tâm cụm hay khoảng cách giữa các cụm. Trong

luận án, các chỉ số đánh giá chất lượng cụm nội tại lẫn chỉ số ngoài được sử dụng để

đánh giá chất lượng cụm.

Chỉ số MA được tính như sau:

, (1.11) MA = 100% × min ,…,

với là số phần tử thuộc về cụm sau khi phân cụm, là số phần tử thực tế thuộc

về cụm . Chỉ số MA càng lớn thể hiện chất lượng phân cụm càng tốt.

Chỉ số DB được biểu diễn như sau.

= , (1.12) ∑ :

∑ −

(1.13) , ( = 1, . . . , ), =

(1.14) = − , (, = 1, . . . , , ≠ ),

Trong đó là kích thước của cụm i. là số đo độ phân tán trong cụm, và

là số đo sự khác biệt giữa cụm i và cụm j. Giá trị càng nhỏ cho thấy hiệu suất tốt hơn

cho chỉ số DB. Chỉ số Rand được định nghĩa như sau:

, = (1.15)

trong đó () là số cặp điểm dữ liệu cùng thuộc một lớp trong R và giống (hoặc

khác) cụm trong Q với R và Q là 2 cụm phổ biến. () là số cặp điểm dữ liệu thuộc

về lớp khác trong R và giống (hoặc khác) cụm. Khi đó giá trị chỉ số Rand lớn hơn thì

chất lượng cụm tốt hơn.

Một trong những chỉ số đánh giá ổn định nhất cho việc phân cụm, Alternative

Silhouette () [89], được sử dụng để đo lường chất lượng cụm.

(1.16) ∑ , ASWC =

, ,

(1.17) , ( = 1, . . . , ), =

ở đây , là khoảng cách trung bình của phần tử tới tất cả các phần tử khác trong

cụm , , là khoảng cách ngắn nhất của phần tử tới tất cả các phần tử khác không thuộc cụm . là một hằng số có giá trị nhỏ (ví dụ: 10-6 đối với dữ liệu chuẩn hoá)

được sử dụng để tránh phép chia cho 0 khi , = 0. Giá trị tối đa cho biết hiệu suất

tốt hơn đối với chỉ số ASWC.

Chỉ số PBM được trình bày như sau:

(1.18) , =

trong đó biểu thị tổng khoảng cách giữa các điểm dữ liệu và giá trị trung bình của dữ liệu, là tổng của các khoảng cách trong của các phần tử trong cùng nhóm, là khoảng cách tối đa giữa các tâm cụm. Phân vùng tốt nhất được tìm thấy khi PBM đạt

giá trị lớn nhất.

WGLI là sự kết hợp của mạng lưỡng cực có trọng số () và độ thuộc trung bình

lớn nhất MMD nhằm tránh việc đạt được cực trị địa phương. Giá trị tối đa cho biết

hiệu suất tốt hơn của chỉ số WGLI.

() ,

(1.19) =

, = (1.20) ∑ max

, = = ∑ − (), (1.21)

, (1.22) = ∑

∈

∑ ∑ (, ) , (1.23) =

(1.24) (, ) =

1.0 > , (1 − ) ≤ ≤ , 0.0 < (1 − ), ở đây là giá trị thuộc của phần tử thuộc cụm . Theo Zhang và cộng sự [100] thì

= 0.7. Nói chung, cần lưu ý là giả định > 0.5. Giả sử là một mạng lưỡng cực có trọng số mà tập đỉnh được chia thành hai tập và , tất cả các cạnh trong mạng là một kết nối từ một đỉnh trong và tương ứng. Giả sử và là tập các đỉnh khác nhau thuộc và thì là thương của các cạnh nối các đỉnh trong tới các đỉnh trong và là tổng của các hàng.

Thuật toán phân cụm mờ

Bezdek và các cộng sự [12] giới thiệu bài toán phân cụm mờ bằng việc cực tiểu

hóa hàm mục tiêu (1). Trong đó, độ thuộc của dữ liệu Xk tới cụm thứ j được biểu diễn

bởi được thêm vào hàm mục tiêu trong công thức (1). Sự khác biệt này so với

phân cụm rõ cho thấy một điểm có thể thuộc vào một cụm khác phụ thuộc vào độ

thuộc của nó. Chú ý rằng, trong công thức (1.25) N, C, m và Vj theo thứ tự là số các

điểm dữ liệu, số cụm, bộ mờ hóa (thường được đặt bằng 2) và điểm tâm cụm j ( =

1, . . . , ).

−

(1.25) ∑ = ∑

Các ràng buộc của (1.25) là,

. (1.26) = 1 ∈ [0,1] ∑

Bằng cách sử dụng phương pháp Lagrange, Bezdek và cộng sự [12] sử dụng

∑

lược đồ lặp để tính độ thuộc và các tâm cụm của bài toán (1.25–1.26) như sau:

∑

; = 1, . . . , , (1.27) =

∑

; = 1, . . . , , = 1, . . . , . = (1.28)

FCM đã được chứng minh là hội tụ tới cực tiểu địa phương hoặc điểm yên ngựa

của hàm mục tiêu (1.25) [12], tuy nhiên, mặc dù FCM là một thuật toán phân cụm tốt

nhưng việc chọn số cụm, bộ mờ hóa, độ đo khoảng cách như thế nào lại là vấn đề

đáng để xem xét vì một lựa chọn không tốt có thể không cho kết quả phân cụm tốt

với các mẫu có thành phần gây nhiễu. Ví dụ, trong trường hợp các mẫu chứa các cụm

hoặc khác nhau về số lượng hoặc khác nhau về mật độ, có thể mẫu bên trái của một

cụm có đóng góp nhiều hơn cho các cụm khác. Lựa chọn sai các tham số và độ đo có

thể khiến FCM rơi vào tình trạng tối ưu cục bộ và thuộc về nhiễu cũng như ngoại lệ.

Thuật toán phân cụm FCM được trình bày trong hình 1.1.

Phương pháp phân cụm mờ loại 2 khoảng [38] với mục đích tối ưu hóa các hàm dưới đây với [, ] là bộ mờ khoảng thay vì bộ mờ thô trong các công thức (1.25–1.26).

−

(1.29) ∑ → , = ∑

−

(1.30) ∑ → . = ∑

Begin

Khởi tạo

Cập nhật tâm cụm và độ thuộc

Sai

Điều kiện dừng

Đúng

End

Hình 1.1. Thuật toán phân cụm FCM

Các ràng buộc trong (1.25–1.26) được giữ nguyên. Bằng các kỹ thuật tương tự

để giải quyết bài toán tối ưu mới, khoảng thuộc = , và các tâm ban đầu của

cụm được tính theo công thức (1.31–1.33). Trong các giá trị này, sau các vòng lặp,

hàm mục tiêu và sẽ đạt min.

∑

ế <

∑

⎧ ⎪ (1.31) , = ượ ạ

⎨ ⎪ ⎩

∑

ế ≥

∑

⎧ ⎪ (1.32) , = ượ ạ

∑

⎨ ⎪ ⎩

∑

(1.33) ; = 1, . . . , , =

trong đó là một giá trị bất kỳ trong khoảng và . Tuy nhiên, hạn chế của lớp các thuật toán cài đặt FCM trên T2FS là thiên về tính toán do đó việc triển khai FCM

trên IFS thường được ưu tiên hơn. IFS [10], bao gồm các yếu tố đặc trưng bởi cả các

giá trị thuộc và không thuộc, là phương tiện hữu ích để xử lý dữ liệu mơ hồ và không

chắc chắn.

Thuật toán phân cụm mờ trực cảm trong [15,16] nhằm cực tiểu hóa hàm mục

∗

tiêu (1.34) đã tích hợp entropy với hàm mục tiêu của FCM như sau.

∗

−

(1.34) ∑ = ∑ + ∑

ở đây,

∗ =

(1.35) ∑ .

Chú ý rằng, khi () = 0, hàm (34) trả về giá trị tương ứng của FCM trong (1.15). Các ràng buộc của (1.34–1.35) là tương tự các ràng buộc của FCM, như vậy,

các tác giả đã chia hàm mục tiêu trong (1.34) thành hai thành phần và sử dụng phương

pháp Lagrange để giải quyết bài toán đầu tiên và đạt được nghiệm như trong (1.27–

1.28). Tiếp theo, độ do dự được tính bằng cách sử dụng toán tử Yager [13] bằng công

thức (1.36) và được sử dụng để cập nhật độ thuộc trong công thức (1.37):

(1.36) = 1 − − 1 −

(1.37) = + .

Độ thuộc mới được sử dụng để tính các tâm cụm trong công thức (1.27). Thuật

toán dừng khi sự khác biệt giữa hai độ thuộc liên tiếp không lớn hơn ngưỡng cho trước.

Một số thuật toán khác

1.4.1. Thuật toán tối ưu bầy đàn

Thuật toán tối ưu hóa bầy đàn (PSO) lần đầu tiên được giới thiệu bởi Eberhart

và Kennedy (1995) [28] là một chiến lược tiến hóa nhằm tối ưu hóa một vấn đề bằng

phương pháp lặp cố gắng cải thiện một giải pháp ứng viên tới một chất lượng cho

trước. PSO mô phỏng sự chuyển động của các sinh vật trong một bầy chim hoặc cá

để tìm thức ăn. Giả sử rằng có cá thể trong bầy, mỗi cá thể trong số đó được

trình bày là một giải pháp của bài toán và được mã hóa với vị trí và vận tốc .

Thuật toán PSO gồm các bước sau: khởi tạo bầy, tính toán các giá trị fitness và cập

nhật các phương án.

() ← ; () ← ;

Begin Phương án i Phương án h

ℎ ℎ

Tính giá trị fitness Tính giá trị fitness

Cập nhật Pbest Cập nhật Gbest Cập nhật Pbest

Sai Sai

Cập nhật và Cập nhật và ℎ Điều kiện

dừng

Đúng

End

Hình 1.2. Sơ đồ thuật toán tối ưu PSO

Trước tiên, vị trí và vận tốc của mỗi phương án được khởi tạo ngẫu nhiên. Tiếp

theo, mỗi phương án được đánh giá chất lượng bằng giá trị fitness. Tùy thuộc vào bài

toán cụ thể, giá trị fitness được thiết kế để đánh giá chất lượng của phương án. Cuối

cùng, quá trình cập nhật được mô tả trong phương trình 1.38-1.39.

(1.38) = + − + ( − ),

(1.39) = + , = 1, … ,

trong đó, các tham số , ≥ 0 là các tham số của thuật toán PSO. Thường thì , được thiết lập là giá trị 1. là vị trí mà phương án có giá trị tốt nhất ở hiện tại và là vị trí có giải pháp hiện tại tốt nhất.

Toàn bộ quá trình được lặp lại cho đến khi số lần lặp tối đa đã đạt tới hoặc giải

pháp tốt nhất tại hai bước liên tiếp không đổi. Sơ đồ thuật toán PSO được trình bày

trong hình 1.2.

1.4.2. Thuật toán DifFuzzy

Thuật toán phân cụm DifFuzzy [20] dựa trên FCM và các biểu đồ khuếch tán

để phân dữ liệu vào các cụm có cấu trúc hình học phi tuyến phức tạp. Trước hết, hàm

bổ trợ được định nghĩa như sau:

(1.40) (): (0, ∞) →

trong đó ∈ (0, ∞) là một số nguyên dương. Các node và được kết nối bằng một

cạnh nếu: − < . () bằng với số lượng các thành phần của đồ thị liền kề

sao cho chứa ít nhất M đỉnh, trong đó M là tham số bắt buộc của thuật toán

DifFuzzy. Hàm () ban đầu nhận giá trị không, và sau đó tăng lên đến giá trị tối đa

của nó sau đó quay trở lại giá trị 1.

(1.41) (), = ∈(,∞)

∧

,() =

(1.42) 1 ế à ở ù ộ ụ,

−

− ượ ạ,

trong đó là một số thực dương. Hàm: L(): (0, ∞) → (0, ∞):

∧ () = ∑ ∑

(1.43) ().

Có hai giới hạn được xác định rõ:

() = + ∑ ( − 1)

(1.44) () = , → à →∞

trong đó tương ứng với số lượng các điểm trong cụm thứ . Thuật toán DifFuzzy thực hiện điều này bằng việc tìm kiếm ∗ thỏa mãn các mối quan hệ:

(1.45) (∗) = (1 − )( + ∑ ( − 1) ) + ,

trong đó là ∈ (0,1) là tham số trong của thuật toán với giá trị mặc định là 0.3. Các ma trận phụ được định nghĩa như sau.

∧ =

(1.46) (∗).

Ma trận được định nghĩa là ma trận đường chéo với các phần tử đường chéo:

(1.47) , , = ∑ ,, = 1,2, . . . . . . ,





trong đó , là các mục của ma trận . Cuối cùng, Ma trận được định nghĩa,

  DWIP

 2 max jiD ,  ,...1 i N

, (1.48)

trong đó ∈ × là ma trận xác định và là một tham số trong của DifFuzzy với giá trị mặc định là 0.1. DifFuzzy cũng tính một tham số nguyên phụ α bởi,

, (1.49) =

trong đó tương ứng với giá trị riêng thứ hai (lớn nhất) của và ⌊. ⌋ biểu thị phần nguyên. Để tính khoảng cách khuếch tán giữa điểm mềm và cụm , sử dụng công thức sau.

(1.50) , (, ) = −

trong đó () = 1 nếu = , và () = 0 trong các trường hợp còn lại. Cuối cùng giá

trị thuộc của điểm mềm trong cụm , được xác định là

∑

(,)

(1.51) . () =

Quy trình này được áp dụng cho mọi điểm dữ liệu mềm và cho mỗi cụm thứ ∈ {1,2, . . . , }. Đầu ra của DifFuzzy là số các cụm () và mỗi điểm dữ liệu một tập

hợp các số đại diện cho mức độ thuộc trong mỗi cụm. Giá trị thuộc của , = 1,2, . . . , , trong cụm thứ , = 1, . . . , được biểu thị bằng (). Độ thuộc là một giá trị từ 0 đến 1, trong đó các giá trị gần 1 tương ứng với các điểm có nhiều khả năng

thuộc về cụm đó. Tổng các giá trị thuộc của một điểm dữ liệu trong tất cả các cụm

luôn là 1.

1.4.3. Thuật toán Dissimilarity

Thuật toán Dissimilarity [25] là giải thuật dựa trên thuật toán phân cụm mờ K-

Medoids với trọng số liên quan cho mỗi ma trận không tương tự bao gồm 5 bước

dưới đây:

- Khởi tạo

Cố định (số lượng các cụm) , 2 ≤ << ; Cố định m, 1 < < +∞; Cố định

, 1 ≤ < +∞; Cố định (số lần lặp); Cố định > 0 và << 1. Cố định số yếu tố () = 1 ≤ << của các nguyên mẫu ( = 1, . . . . , ). Thiết lập = 0. Thiết lập

, =

(), . . . . ,

() = (1, . . . ,1) hoặc thiết lập

() =

(), . . . . ,

() =

, . . . . ,

() ∈ ()( = 1, . . . , ). ()( = 1. . . , ) trên

1, . . . , . Chọn ngẫu nhiên các nguyên mẫu khác nhau

Cho mỗi đối tượng ( = 1, . . . , ) tính toán mức độ thuộc của cụm mờ :

()

() =

ℎ

()

ℎ

(1.52) , , ℎ ⎡ ⎢ ⎢ ⎢ ⎣ ⎤ ⎥ ⎥ ⎥ ⎦

()

∑

∈

()

∈ℎ

∑ (, ) = ∑ ∑ (, ) ℎ ⎡ ⎢ ⎢ ⎢ ⎣ ⎤ ⎥ ⎥ ⎥ ⎦

()

(),,

() =

()

(1.53)

∈

= , ()

- Tính toán giá trị tốt nhất

(), . . . . ,

() và phân cụm mờ được đại diện bởi () =

tiêu chí phân cụm thiểu

→ . Thiết lập = + 1. Vector của các trọng số có liên quan () = () () = ∗ ∈ () của cụm mờ ( = 1, . . . . , ) được tính là cố định. Nguyên mẫu theo thủ tục được mô tả trong mệnh đề: nguyên mẫu = ∗ ∈ () của cụm mờ ( = 1, . . . . , ) được chọn để giảm J: ∑ () (, ∗) ∑

() và các phân cụm mờ được

- Tính toán trọng số liên quan tốt nhất

(), . . . ,

()( = 1, . . . , )

(), . . . ,

Khi vector của nguyên mẫu () =

() là cố định, các thành phần ()( = 1, . . . , ) tương ứng được tính như trong phương trình

đại diện bởi () =

của vector trọng số (1.54) hoặc (1.56) nếu hàm matching được đưa ra trong công thức (1.55) hoặc (1.57),

tương ứng.

ℎ

(1.54) ] } = {∏ [∑ ()ℎ(, ) ∑ ()(, )

∈

∏ ∑ () ∑ ℎ ∑ () ∑

∈

= , ℎ(, ) (, )

∈

(1.55) ∑ , (, ) = ∑ (, ) ()(, ) = ∑

(1.56)

∈

= ∑ ()(, ) ∑ ()ℎ(, )

∈

= , ∑ () ∑ ∑ () ∑ (, ) ℎ(, )

(1.57) (, ) (,)(, ) =

∈

, (, )

- Định nghĩa phân hoạch mờ tốt nhất

(), . . . . ,

() và vector của trọng số liên () của ( = 1, . . . , ) trong

(), . . . . ,

() được cố định. Độ thuộc

Các vector của nguyên mẫu () =

quan () = cụm mờ ( = 1, . . . . , ) được tính như trong phương trình (1.58).

()

() =

()

(1.58) ,

()

, ℎ ⎡ ⎢ ⎢ ⎢ ⎣ ⎤ ⎥ ⎥ ⎥ ⎦

()

∑

() ∈

()

∈ℎ

∑ (, ) = ∑ ∑ (, ) ℎ ⎡ ⎢ ⎢ ⎢ ⎣ ⎤ ⎥ ⎥ ⎥ ⎦

- Điều kiện dừng

Tính toán:

()

(),,

() =

()

(1.59)

= (, ) () ∈

Nếu () − () ≤ or < : STOP; ngược lại quay lại bước đầu tiên.

1.4.4. Phương pháp FCM-STAR

Pfeifer và Deutsch [70] đã đề xuất mô hình không - thời gian tuyến tính, là

một phiên bản 3D của mô hình hồi quy thông thường (AR) và nó cho phép người

dùng dự báo một chuỗi không thời gian dựa trên thông tin trong quá khứ của nó theo

không gian và thời gian. Giá trị của mỗi điểm ảnh (, , ) trong một ảnh có thể

được mô phỏng như một hàm "" của các điểm ảnh lân cận theo không gian và thời

gian, với giả định của quan hệ nhân quả.

(1.60) (, , ) = ( + , + , + ),

trong đó (, , ) là vùng bao phủ lân cận theo không gian và thời gian với < 0. Phương trình (1.60) được sửa lại cho việc phân cụm dựa vào thuật toán STAR theo Shukla, Kishtawal và Pal [76] như sau.

(, , ) ,

∑ ∑ (, , ) = ∑ (1.61) ,,

trong đó, 2 + 1, 2 + 1và tương ứng với tổng số hàng, cột và khung theo thứ tự, là trọng số tương ứng biểu thị trọng số cho cụm , = 0, . . . , , = 0, … , .

và ,, Trọng số được tính bằng cách tối thiểu hàm,

(, , )

∑ ∑ (, , ) − ∑ → , (1.62) ,,

trong đó ‖. ‖biểu diễn khoảng cách Euclide. Phương trình (1.61) được giải bằng

phương pháp bình phương tối thiểu sử dụng nhân tố QR [67]. Sau khi tìm ra trọng số,

tất cả các điểm ảnh trong hình dự đoán sẽ được tính bằng phương trình (1.62).

Bộ dữ liệu thực nghiệm

Tập dữ liệu thử nghiệm cho thuật toán phân cụm mờ viễn cảnh và thuật toán mở

rộng được lấy trên kho dữ liệu học máy chuẩn UCI [88] như IRIS, WINE, WDBC,

GLASS, IONOSPHERE, HABERMAN, HEART, CMC, ABALONE, SERVO,

AUTOMOBILE và STATLOG. Đây là các tập dữ liệu chuẩn được sử dụng cho các

bài toán phân cụm, phân lớp. Bảng 1.1 thể hiện mô tả chi tiết về bộ dữ liệu thử nghiệm.

Bảng 1.1. Mô tả tập dữ liệu thử nghiệm

Dữ liệu

Số bản

Số thuộc

Số thuộc tính

Số cụm

Số phần tử ở mỗi lớp

tính số

kiểu loại

ghi

IRIS

150

(50,50,50)

WINE

178

(59,71,48)

WDBC

569

(212,357)

GLASS

214

(70,76,17,13,9,29)

IONOSPHERE

351

(126,225)

HABERMAN

306

(225,81)

HEART

270

(150,120)

CMC

1473

(415,227,831)

ABALONE

4177

(1528,1307,1342)

AUTOMOBILE

205

(3,22,67,53,30,25)

SERVO

167

(33,36,22,40,36)

STATLOG

1000

(700,300)

Các dữ liệu đầu vào cho bài toán dự báo thời tiết ngắn hạn là các ảnh vệ tinh

nhận được từ [63] ở cùng một vị trí và cùng khoảng thời gian. Bộ sưu tập hình ảnh

bao gồm ba bộ hình ảnh: Malaysia (dữ liệu 1, hình 1.3), Luzon – Philippines (dữ liệu

2, hình 1.4) và Jakarta – Indonesia (dữ liệu 3, hình 1.5). Các ảnh vệ tinh thể hiện màu

sắc là các đám mây với màu càng đậm thể hiện mây càng dày. Các ảnh liên tiếp thể

hiện sự chuyển động của mây trong một khu vực. Mỗi tập dữ liệu chứa 7 ảnh liên tiếp

từ 7.30 sáng đến 13.30 chiều từ 28/11/2014. Tất cả các hình ảnh có cùng kích thước

(100x100 pixel). Những hình này được đưa ra trong các hình từ 1.3 – 1.5. Mỗi tập

ảnh được chia thành các tập con là tập huấn luyện và tập kiểm tra mà trong đó, 3 ảnh

cuối là 3 ảnh giả sử đã được dự đoán.

7.30 8.30 9.30 10.30 11.30 12.30 13.30

Hình 1.3. Ảnh mây vệ tinh của bộ dữ liệu 1

7.30 8.30 9.30 10.30 11.30 12.30 13.30

Hình 1.4. Ảnh mây vệ tinh của bộ dữ liệu 2

7.30 8.30 9.30 10.30 11.30 12.30 13.30

Hình 1.5. Ảnh mây vệ tinh của bộ dữ liệu 3

Kết luận chương

Trong chương này, một số kiến thức cơ sở về tập mờ, các độ đo đánh giá chất

lượng cụm, các thuật toán phân cụm và các thuật toán liên quan khác đã được trình

bày. Các kiến thức cơ sở này sẽ là nền tảng cho việc đề xuất và cải tiến thuật toán giải

quyết những bài toán ở các chương sau của luận án.

CHƯƠNG 2. THUẬT TOÁN PHÂN CỤM MỜ VIỄN CẢNH

Chương này trình bày một thuật toán phân cụm mờ viễn cảnh mới, được đề xuất

dựa trên tính chất của tập mờ viễn cảnh. Kết quả này được thể hiện chi tiết trong

[CT1]. Những khảo sát về tính chất hội tụ của thuật toán ở góc độ lý thuyết cũng như

kiểm chứng thuật toán thông qua thực nghiệm số được thực hiện đảm bảo tính đúng

và hiệu quả của thuật toán. Kết quả này được thể hiện trong [CT2].

2.1. Ý tưởng thuật toán

Thuật toán phân cụm mờ viễn cảnh được đưa ra dựa trên ý tưởng của thuật toán

phân cụm mờ mờ trực cảm và áp dụng trên tập mờ viễn cảnh. Ý tưởng của thuật toán

là thiết kế hàm mục tiêu là tổng của hai thành phần là tổng khoảng cách của các điểm

dữ liệu đến các tâm cụm và đại lượng entropy. Thành phần thứ nhất được cải tiến từ

hàm mục tiêu của thuật toán phân cụm mờ thường [12] với mục tiêu cực tiểu hóa đại

lượng (2 − )‖ − ‖. Cũng giống với thuật toán FCM, một điểm dữ liệu nếu

thuộc về một cụm thì khoảng cách từ điểm đó tới tâm cụm phải nhỏ nên do đó độ

thuộc của điểm dữ liệu vào cụm sẽ lớn. Với việc thay thế thành phần độ thuộc trong

FCM bằng đại lượng (2 − ), điều này càng thể hiện rõ hơn khi một điểm dữ liệu

nếu càng gần tâm cụm thì không những giá trị độ khẳng định phải lớn và giá trị độ

từ chối phải nhỏ. Ở đây, tác giả sử dụng giá trị (2 − ) trong mô hình để chắc chắn

với giá trị (2 − ) ≤ 1 thì ≤ 1, thỏa mãn điều kiện của PFS.

Thành phần thứ hai trong hàm mục tiêu chính là đại lượng entropy

( + ). Bằng việc cực tiểu hóa đại lượng này, các điểm dữ liệu sẽ giảm giá trị

và , với mục tiêu cực tiểu nhanh hơn so với . Điều này sẽ giúp cực tiểu độ từ

chối của mô hình, giúp việc phân cụm cụm cải tiến được độ chính xác hơn.

2.2. Thuật toán phân cụm mờ viễn cảnh

2.2.1. Hàm mục tiêu

Trong phần này, một mô hình thuật toán phân cụm mờ viễn cảnh mới dựa trên

lý thuyết của tập mờ viễn cảnh đã được trình bày. Giả sử có một tập X chứa N điểm

dữ liệu trong không gian đa chiều. Bài toán đặt ra là phải chia tập dữ liệu thành C

nhóm bằng việc cực tiểu hóa hàm mục tiêu (2.1).

= ∑

+ ∑

2 −

−

∑

(2.1)

Các ràng buộc được định nghĩa như sau:

(2.2) + + ≤ 1 ; , , ∈ [0,1]

(2.3) ∑ 2 − = 1,

(2.4) ∑ = 1, +

= 1, . . . , ; = 1, . . . ,

Mô hình đề xuất trong công thức (2.1–2.4) dựa trên nguyên lý của tập PFS và

được tóm tắt như sau:

 Ràng buộc trong (2.2) phản ánh định nghĩa của các tập PFS trong (Định nghĩa

4).

 Công thức (2.3) chỉ ra độ thuộc của điểm tới tâm cụm , được biểu diễn

bởi 2 − .

 Công thức (2.4) đảm bảo trên các tập PFS vì ít nhất một trong hai nhân tố không

chắc chắn là độ trung lập và độ từ chối luôn luôn tồn tại trong mô hình.

Tiếp theo, phương pháp Lagrange được sử dụng để xác định các giải pháp tối

ưu của mô hình (2.1–2.4)

Định lý 1. Nghiệm tối ưu của bài toán trong (2.1–2.4) là:

, ( = 1, . . . , , =

= 1 − + − 1 − + (2.5)

1, . . . , ),

∑

()

(2.6) , ( = 1, . . . , ; = 1, . . . , ), =

∑

(2.7) 1 − , ( = 1, . . . , ; = 1, . . . , ), =

∑

, ( = 1, . . . , ). = (2.8)

Chứng minh: Lấy đạo hàm của của theo , ta được:

(2.9) , = ∑ 2 − −2 + 2

( = 1, . . . , ; = 1, . . . , )

Khi = 0, ta được:

2 −

(2.10) = 0, −2 + 2

( = 1, . . . , ; = 1, . . . , )

(2.11) ⇔ 2 − = 2 − ,

∑

( = 1, . . . , ; = 1, . . . , )

∑

(2.12) , ( = 1, . . . , ) ⇔ =

Hàm Lagrange với đối số là,

−

(2.13) () = 2 −

+ + − 2 − − 1

()

Khi = 0, ta được:

2 −

−

(2.14) − 2 − = 0, = ()

( = 1, . . . , ; = 1, . . . , )

(2.15) , ( = 1, . . . , ; = 1, . . . , ) ⇔ =

Từ các công thức (2.3, 2.15), các nghiệm của được thiết lập như sau.

(2.16) ∑ = 1, ( = 1, . . . , ; = 1, . . . , )

∑

(2.17) , ( = 1, . . . , ; = 1, . . . , ) ⇔ =

Kết hợp (2.17) trong (2.15), ta được:

∑

(2.18) , ( = 1, . . . , ; = 1, . . . , ) =

Tương tự, hàm Lagrange với quan hệ là,

−

(2.19) ∑ () = ∑ + 2 −

∑ ∑ − 1. + − ∑ +

()

(2.20) = + 1 − + = 0, ( = 1, . . . , ; = 1, . . . , )

(2.21) ⇔ = − 1 − , ( = 1, . . . , ; = 1, . . . , )

Từ các công thức (2.4, 2.21), ta có:

(2.22) ∑ ∑ + = 1, ( = 1, . . . , ; = 1, . . . , )

∑

(2.23) ∑ ⇔ ∑ = 1 − , ( = 1, . . . , ; = 1, . . . , )

∑

⇔ = . ( = 1, . . . , ; = 1, . . . , ) (2.24)

Kết hợp (2.24) với (2.21), ta được:

∑

(2.25) . ( = 1, . . . , ; = 1, . . . , ) = 1 − ∑

Cuối cùng, bằng cách sử dụng toán tử Yager [13], thay thế () bởi + vào công thức (1.36) để nhận được giá trị độ từ chối của phần tử như

(2.26) = 1 − + − 1 − +

trong đó ∈ (0,1] là một hệ số mũ được sử dụng để điều khiển độ từ chối của các

tập PFS. Như vậy, định lý đã được chứng minh.

2.2.2. Chi tiết thuật toán

Thuật toán FC-PFS được trình bày chi tiết như trong bảng 2.1.

Bảng 2.1. Thuật toán phân cụm mờ viễn cảnh

I:

Dữ liệu với bản ghi với thuộc tính; Số lượng cụm ; ngưỡng ; số mờ

; số mũ và số vòng lặp tối đa > 0

O: Ma trận , , and tâm cụm ;

FC-PFS:

() ← ( = 1, . . , ; =

t = 0

() ← ;

1, … , ) thỏa mãn ràng buộc (64)

Repeat

() ( = 1, . . . , ) bằng công thức (2.8)

t = t + 1

() ( = 1, . . . , ; = 1, . . . , ) bằng công thức (2.6)

Tính toán

() ( = 1, . . . , ; = 1, . . . , ) bằng công thức (2.7)

Tính toán

() ( = 1, . . . , ; = 1, . . . , ) bằng công thức (2.5)

Tính toán

Until () − () + () − () + () − () ≤ or >

Có thể nhận thấy, các công thức tính , có độ phức tạp tính toán là (), và với có độ phức tạp tính toán là (). Như vậy độ phức tạp tính toán của cả thuật toán sẽ là () với là số lần lặp của thuật toán. Thông thường,

trong bài toán phân cụm mờ thì số cụm là nhỏ nên độ phức tạp tính toán của thuật

toán này sẽ là ().

2.3. Khảo sát tính chất hội tụ của thuật toán

Trong phần này, một số mệnh đề dẫn đến sự hội tụ của FC-PFS được trình bày

như sau.

Mệnh đề 2.1: Cho ∶ → R, () ∶= (, , , ), trong đó V, N, Z là các giá trị cố định. Khi đó, U* thuộc là một cực tiểu địa phương chặt của ϕ nếu và chỉ nếu ∗ được tính bằng công thức (2.6).

Chứng minh: Nếu μ thỏa mãn các ràng buộc (2.3), ta xét hàm giảm Lagrange

của (). Xét = (; ; : : : ; ) là bội số và L(U, ) là hàm Lagrange.

−

∑ L(U, ) = ∑ + 2 − (2.27) ∑ ∑ − 1 + − ∑ 2 −

Khi đó,

2 −

−

(,)

(2.28) − 2 − = 0 =

Tại ∗ và tính đạo hàm bậc 2 của L(U, ):

2 −

−

ế ( − 1) = = = (2.29) (, ) 0 ế ượ ạ

Thay thế hàm cập nhật của vào đạo hàm bậc 2 của L(U, ) để tính ma trận

∗

Hessian (∗). Đây là một ma trận không rỗng có các phần tử theo đường chéo:

−

α, = ( − 1) 2 −

> 0

−

∑

(2.30) =( − 1)2 −

và α, = 0 với ≠ , ≠ . Ma trận Hessian của tại U∗ có tất cả các giá trị riêng

> 0 với (1 ≤ ≤ ;1 ≤ ≤ ).

Điều này cho thấy U∗ là một cực tiểu địa phương chặt của .

Tiếp theo, cố định U thuộc M, thuộc N; Z thuộc Z và xét sự tối thiểu của

J theo các biến V = {V}.

Mệnh đề 2.2: Xét ∶ → , () ≜ (; ; ; ), với U; N; Z là các ∗, 1 ≤

giá trị cố định. Khi đó ∗ là một cực tiểu địa phương của nếu và chỉ nếu ≤ được tính toán theo công thức (2.8).

Chứng minh: Khi không có ràng buộc nào của , để tối thiểu qua , cần

tồn tại ∇(∗) thỏa mãn với mọi i,

()

= ∑ = 0 tại ∗ (2.31) 2 − −2 + 2

Tiếp theo, lấy đạo hàm bậc 2 ta được,

−

2 −

> 0 ế = = (2.32) () 0 ế ượ ạ

Ma trận Hessian của () tại ∗ có tất cả các giá trị riêng > 0. Điều này cho

thấy ∗ là một cực tiểu địa phương của ().

Chứng minh tương tự, ta có đạt cực tiểu tại ∗ khi U; V; Z được cố định trong không gian của chúng.

Mệnh đề 2.3: Xét : → ≜ (; ; ; ), với U; N; Z là các giá trị cố định. Khi đó ∗ là một cực tiểu địa phương của nếu và chỉ nếu , 1 ≤ ≤ , 1 ≤ ≤ được tính toán theo công thức (2.7).

Chứng minh: Với mỗi có ràng buộc theo (2.4), xem xét cực tiểu của () với nhân tử Lagrange. Xét = (; ; : : : ; ) là các nhân tử và (, ) là hàm Lagrange, ta có.

−

(2.33) ∑ (, ) = ∑ + 2 −

∑ ∑ − 1. + − ∑ +

Khi N* là bình phương của hệ phương trình:

(2.34) = ln + 1 − + = 0, (, )

> 0 ế = à = = (2.35) 1 (, ) 0 ế ượ ạ.

Ma trận Hessian của (∗, ) tại ∗ có tất cả các giá trị riêng lớn hơn 0 và ∗

cũng là giá trị cực tiểu của ().

Định lý Zangwill [99] được sử dụng để chứng minh hội tụ.

Mệnh đề 2.4: Xét : ∈ → và = ∗ ∈ : (∗) < () ∀ ∈

(∗, ). Xét : → là một thuật toán lặp và = (); = 0,1, …

Nếu E là liên tục trên \, là hàm cơ sở của , và (): =

0,1,2, … ; ∈ ⊂ được chứa trong một tập compact ⊆ với bất kỳ ∈

, khi đó với mỗi một lần lặp được sinh bởi E, ta có sẽ dừng ở một phương án ∗ ∈ hoặc tồn tại một dãy con ⊂ sao cho → ∗ ∈ .

Để áp dụng định lý Zangwill [99], cần chứng minh rằng là hàm giảm và thuật toán liên tục trên đoạn [0,1]\. Sau đó, chỉ cần chứng minh là hàm giảm. Xét là thuật toán cập nhật các tham số trong công thức (2.1–2.4).

Mệnh đề 2.5: = (∗, ∗, ∗, ∗): (∗, ∗, ∗, ∗) < (, , , ),

∀(, , , ) ∈ (∗, ∗, ∗, ∗), . Khi đó làm hàm giảm với , .

Chứng minh: Do hàm Norm và hàm mũ là các hàm liên tục nên tổng của chúng

cũng là liên tục nên liên tục trên × . Giả sử (, , , ) ∉ , khi đó

(, , , ) = °°°(, , , )

= °°, , , ℎ()

(2.36) < °°(, , , ) = °(, , (), )

< °(, , , ) = (, (), , ) < (, , , )

= ((), , , ) < (, , , )

Khi đó, là hàm giảm, điều này khẳng định hội tụ.

2.4. Kết quả thực nghiệm

Môi trường thử nghiệm thuật toán phân cụm mờ viễn cảnh trình bày trong bảng

2.1 được mô tả như sau:

 Công cụ thử nghiệm: thuật toán đề xuất FC-PFS, thuật toán FCM [12], IFCM

[16], KFCM [34] và KIFCM [54] sử dụng ngôn ngữ lập trình C và thực thi trên

Linux Cluster 1350 với 8 node tính toán có tốc độ 51.2 GFlops. Mỗi node là một

máy tính với 4 chíp Intel Xeon dual core 3.2GHz và 2GBRam. Kết quả thử

nghiệm được lấy làm kết quả trung bình sau 50 lần chạy.

 Thiết lập các tham số: Các giá trị của các tham số như bộ mờ hóa = 2, = 10, ∈ (0,1), và = 1000 được thiết lập cho tất cả các thuật

toán trong [12,15,34,54].

 Các mục tiêu:

 Minh họa các hoạt động của thuật toán FC-PFS đề xuất trong tập dữ liệu;

 Đánh giá chất lượng phân cụm của các thuật toán thông qua các chỉ số. Thời

gian tính toán của thuật toán cũng được xem xét trong các thử nghiệm;

 Đánh giá hiệu năng của các thuật toán bằng các giá trị tham số khác nhau.

2.4.1. Ví dụ minh họa cho FC-PFS

Trước tiên, luận án minh họa từng bước của thuật toán FC-PFS để phân lớp tập

dữ liệu IRIS. Trong trường hợp này với = 150, = 4, = 3, các ma trận khởi tạo

thuộc, trung lập và độ từ chối có cùng kích thước 150 x 3 được khởi tạo ngẫu nhiên

thỏa mãn ràng buộc (2.2) như sau,

, () = (2.37)

0.174279 0.164418 0.198673 0.140933 0.169170 0.198045 ....... 0.225422 0.161006 0.125153

, () = (2.38)

0.215510 0.321242 0.320637 0.324118 0.312415 0.330315 …….. 0.306056 0.329532 0.326154

. () = (2.39)

0.469084 0.422466 0.402644 0.433791 0.424756 0.397048 …….. 0.395095 0.419692 0.440974

Phân phối dữ liệu theo giá trị khởi tạo ban đầu được minh họa như hình 2.1. Từ

bước 5 của FC-PFS, tâm cụng được tính bằng công thức (2.8) cho kết quả như sau:

(2.40) . =

5.833701 3.027605 3.845183 1.248464 5.784128 3.041955 3.650875 1.148453 5.677982 3.079381 3.456761 1.073087

Các ma trận độ thuộc, độ trung lập và độ từ chối được tính và cho kết quả:

, () = (2.41)

0.118427 0.169661 0.344978 0.117641 0.171776 0.340098 ……… 0.400281 0.159727 0.067458

, (2.42) () =

0.182454 0.191161 0.194988 0.190864 0.192596 0.198008 ……. 0.198376 0.193556 0.189481

. () = (2.43)

Cluster1

Cluster2

0.495291 0.479725 0.389716 0.493854 0.478521 0.390903 ……. 0.350145 0.482186 0.499905

m c n

i

Cluster3

i

h t d w

l a p e s

sepal length in cm

Hình 2.1. Các cụm tại bước khởi tạo

Từ các ma trận này, giá trị của () − () + () − () +

() − () được tính toán là 0.102. Giá trị này vẫn lớn hơn nên thuật toán tiếp

tục bước lặp.

Hình 2.2. Các cụm sau bước lặp đầu tiên

Hình 2.3. Kết quả phân cụm cuối cùng

Tương tự, các ma trận tâm cụm, độ thuộc, độ trung lập và độ từ chối tiếp tục

được tính toán lại cho đến khi điều kiện dừng thỏa mãn. Các ma trận này được chỉ ra

trong (2.44–2.46) và được minh họa trong hình 2.2.

, ∗= (2.44)

0.000769 0.001656 0.551091 0.004785 0.010665 0.543119 …….. 0.261915 0.350356 0.017994

, ∗= (2.45)

0.182155 0.182103 0.245264 0.181528 0.181223 0.242352 ……. 0.186777 0.195800 0.176763

. ∗= (2.46)

0.489544 0.489825 0.192064 0.490654 0.492324 0.201595 ……. 0.442305 0.385736 0.493112

Các tâm cụm cuối cùng được tính và có kết quả như trong (2.47). Các cụm và

tâm cụm kết quả được minh họa trong hình 2.3. Tổng số bước lặp là 11.

. (2.47) ∗=

6.762615 3.048669 5.631044 2.047229 5.879107 2.757631 4.349495 1.389834 5.003538 3.403553 1.484141 0.251154

2.4.2. So sánh chất lượng phân cụm

Chất lượng phân cụm và thời gian tính toán của thuật toán đề xuất FC-PFS được so

sánh với một số thuật toán liên quan gồm: FCM, IFCM, KFCM, KIFCM. Đây là các thuật

toán điển hình cho bài toán phân cụm mờ, được sử dụng phổ biến hiện nay. Các bộ dữ liệu

được thực hiện bởi các thuật toán trên với kết quả thực nghiệm là giá trị trung bình của 50

lần chạy. Các kết quả thử nghiệm với hệ số mũ = 0.6 được chỉ ra trong bảng 2.2.

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 ( =

. )

Data

Độ đo MA (%)

FC-PFS

FCM

IFCM

KFCM

KIFCM

IRIS

96.1

96.7*

95.3

84.50

73.3

WINE

87.1*

85.9

82.6

86.20

86.6

WDBC

67.2

62.5

56.5

76.20*

70.6

GLASS

74.5*

71.2

73.4

73.50

IONOSPHERE

72.9

71.5

78.6*

60.12

57.6

HABERMAN

76.9

72.2

78.4*

76.70

76.9

87.7

88.10*

74.9

HEART

87

85.9

70.4

61.40

58.7

CMC

77.1*

72.8

Rand Index (%)

Data

FC-PFS

IFCM

KFCM

KIFCM

FCM

IRIS

92.4

95.7*

88.6

84.2

WINE

71.3

72.8

73.4

84.2*

68.4

WDBC

56.9

60.2

62.5*

54.1

51.7

GLASS

71.4

70.5

71.9*

67.9

64.7

IONOSPHERE

49.9

50.1

50.2

52.17*

52.1

HABERMAN

49.84

49.87

49.86

49.9*

49.8

HEART

53.9

60.7*

50.7

50.8

CMC

55.6*

55.4

55.1

50.8

48.3

Data

DB

FC-PFS

IFCM

KFCM

KIFCM

FCM

IRIS

3.05

2.91*

3.15

4.21

4.9

WINE

2.77*

2.93

2.88

3.75

3.76

WDBC

1.76*

1.87

1.97

5.03

10.6

GLASS

8.13

5.13*

9.68

13.94

5.9

IONOSPHERE

2.9

2.53*

4.15

2.68

3.9

HABERMAN

2.28

2.21*

2.58

4.92

4.81

HEART

2.03*

2.05

2.29

4.67

4.82

CMC

2.59*

2.85

4.01

3.81

Data

Thời gian tính toán (sec)

FCM

FC-PFS

IFCM

KFCM

KIFCM

IRIS

0.033

0.011

0.01*

0.282

0.481

WINE

0.112*

0.242

0.15

2.56

1.28

WDBC

0.241*

0.323

0.254

3.54

5.007

GLASS

0.534

0.182*

0.277

3.55

4.7

IONOSPHERE

0.177

0.103*

0.194

4.42

4.84

HABERMAN

0.029

0.02*

0.126

0.381

HEART

0.071

0.048*

0.07

0.905

0.903

CMC

0.534

0.433

0.422*

6.28

8.15

*: Giá trị tốt nhất

Qua kết quả nhận được, rõ ràng FC-PFS cho kết quả phân cụm tốt hơn các thuật

toán phân cụm khác trong nhiều trường hợp. Ví dụ, với tập dữ liệu WINE, giá trị

Mean Accuracy của FC-PFS là 87.1%, tốt hơn của FCM, IFCM, KFCM và KIFCM

lần lượt là 85.9%, 82.6%, 86.2% và 86.6%. Tương tự, với tập dữ liệu GLASS, giá trị

Mean Accuracy của FC-PFS là 74.5%, tốt hơn của FCM, IFCM, KFCM và KIFCM

lần lượt là 71.2%, 73.4%, 73.5% và 64%. Khi xét đến chỉ số Rand của FC-PFS với

tập dữ liệu CMC, kết quả có được là 55.6% trong khi giá trị Rand tương ứng của

FCM, IFCM, KFCM và KIFCM lần lượt là 55.4%, 55.1%, 50.8% và 48.3%. Giá trị

DB của FC-PFS trên tập dữ liệu CMC tương tự giá trị DB trên cùng tập dữ liệu với

FCM và nhỏ hơn giá trị DB của IFCM, KFCM và KIFCM lần lượt là 2.59, 2.59, 2.85,

4.01 và 3.81. Lấy giá trị trung bình MA của FC-PFS, được kết quả là 79.85%, đây là

hiệu năng trung bình của thật toán. Con số này cao hơn của FCM (77.3%), IFCM

(77.9%), KFCM (75.84%) và KIFCM (70.32%). Các kết quả này được mô tả trong

hình 2.4.

Hình 2.4. Độ chính xác trung bình của các thuật toán

Mặc dù, các kết quả thử nghiệm là rất khác nhau, ví dụ, giá trị MA của tất cả

các thuật toán trên tập dữ liệu IRIS khá cao (73.3% - 96.7%). Tuy nhiên, với các tập

dữ liệu có nhiễu, ví dụ, tập WDBC, các giá trị MA của các thuật toán là nhỏ (56.5%

- 76.2%). Tương tự, các giá trị Rand nhận được trên tập dữ liệu chuẩn như IRIS có

chỉ số Rand cao (76% - 95.7%) và không đều, trên tập dữ liệu có nhiễu như WDBC,

IONOSPHERE và HABERMAN, miền giá trị Rand giảm xuống lần lượt là (51.7% -

62.5%), (49.9% - 52.17%) và (49.84% - 49.9%). Với chỉ số DB, dữ liệu phức tạp cho

giá trị DB cao hơn các tập dữ liệu kiểu khác. Mặc dù miền giá trị của các chỉ số đánh

giá của các thuật toán là rất đa dạng, nhìn chung, kết quả phân cụm của thuật toán

FC-PFS trong các miền phân lớp là tốt hơn. Chi tiết trong bảng 2.3.

Bảng 2.3. Các miền phân lớp của thuật toán

Algorithms MA (%) Rand index (%) DB

FC-PFS 67.2 – 96.1 49.84 – 92.4 1.76 – 8.13

FCM 62.5 – 96.7 49.87 – 95.7 1.87 – 5.13

IFCM 56.5 – 95.3 49.86 – 88.6 1.97 – 9.68

KFCM 60.12 – 88.1 49.9 – 84.2 2.68 – 13.94

KIFCM 57.6 – 86.6 48.3 – 76 3.76 – 10.6

Hình 2.5. Thời gian tính toán của các thuật toán

Thời gian tính toán của các thuật toán được thể hiện trong hình 2.5. Dễ dàng

nhận thấy, thuật toán FC-PFS đề xuất có thời gian tính toán một chút chậm hơn FCM

nhưng nhanh hơn KFCM và KIFCM. Ví dụ, thời gian tính toán của FC-PFS trên tập

dữ liệu IRIS là 0.033s trong 11 bước lăp. Thời gian tính toán của FCM, IFCM, KFCM

và KIFCM cũng trên tập dữ liệu này lần lượt là 0.011, 0.01, 0.282 và 0.481s. Sự khác

biệt lớn nhất về thời gian tính toán giữa thuật toán FC-PFS và các thuật toán khác xảy

ra trên tập dữ liệu CMC với độ lệnh chuẩn vào khoảng 7.6s. Trong các tập dữ liệu

khác, FC-PFS có thời gian tính toán tốt hơn các thuật toán khác, ví dụ, trong tập dữ

liệu WINE, thời gian tính toán của of FC-PFS, FCM, IFCM, KFCM và KIFCM lần

lượt là 0.112, 0.242, 0.15, 2.56 và 1.28s.

Với những kết quả đánh giá và thử nghiệm trên, một số nhận xét được rút

ra như sau:

 FC-PFS cho kết quả phân cụm tốt hơn các thuật toán khác trong nhiều trường hợp;

 FC-PFS có thời gian tính toán tốt hơn một số thuật toán khác, đặc biệt là so với

KFCM và KIFCM.

2.4.3. Đánh giá thuật toán qua các tham số

Tiếp theo, để kiểm tra hiệu năng của thuật toán đề xuất, thuật toán được thử

nghiệm với một số giá trị hệ số mũ khác nhau nhằm xác định sự ảnh hưởng của hệ

số này với hiệu năng của hệ thống. Để hiểu sự ảnh hưởng của hệ số, thống kê các lần

mà thuật toán cho kết quả tốt nhất đối với tất cả các bộ dữ liệu được đưa ra trong bảng

2.4.

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.

Algorithms

MA

RI

DB

= 0.2 = 0.4

= 0.6

= 0.8

= 0.2 = 0.4

= 0.6

= 0.8

= 0.2

= 0.4

= 0.6

= 0.8

FC-PFS

FCM

IFCM

KFCM

KIFCM

Bảng 2.4 cho biết khi giá trị hệ số mũ nhỏ, số lần thuật toán FC-PFS đạt giá trị

Mean Accuracy (MA) tốt nhất ít hơn so với một số thuật toán khác, ví dụ, với =

0.2, FC-FCM không hiệu quả bằng KFCM (2 so với 3). Tuy nhiên, khi tăng giá trị ,

FC-PFS cho kết quả MA tốt hơn. Thuật toán FC-PFS cho giá trị MA tốt khi = 0.4,

= 0.6 và = 0.8. Trong bảng này cho thấy giá trị = 0.6 cho chất lượng cụm tốt

nhất ở cả ba chỉ số MA, RI lẫn DB.

Hình 2.6. Giá trị MA của các thuật toán theo hệ số mũ

Hình 2.7. Thời gian tính toán của các thuật toán theo hệ số mũ (s)

Hình 2.6 là biểu đồ thể hiện giá trị MA được tính dựa trên các giá trị hệ hệ số

mũ cho trước. Nó cho thấy, thuật toán FC-PFS khá ổn định với chất lượng phân cụm

thể hiện ở giá trị MA vào khoảng 80.6%, trong khi của các thuật toán FCM, IFCM,

KFCM và KIFCM lần lượt là 77.3%, 72.5%, 75.8% và 67.4%. Chất lượng phân cụm

của FC-PFS được chứng minh là tốt hơn các thuật toán khác qua các trường hợp khác

nhau của hệ số mũ . Hình 2.7, thời gian tính toán trung bình được biểu diễn theo hệ

số mũ. Nó cũng chứng minh rằng, thời gian tính toán trung bình của thuật toán đề

xuất chậm hơn một chút so với FCM nhưng nhanh hơn KFCM và KIFCM. Thời gian

tính toán trung bình của FC-PFS vào khoảng 0.22s.

Một số nhận xét:

 Nên chọn giá trị hệ số mũ lớn để thuật toán FC-PFS có được kết quả phân cụm tốt.

 Chất lượng phân cụm của FC-PFS ổn định hơn trong nhiều trường hợp (xấp xỉ

80.6%), tốt hơn FCM, IFCM, KFCM và KIFCM.

2.5. Kết luận chương

Trong chương này, nhằm cải thiện chất lượng phân cụm của thuật toán FCM,

thuật toán phân cụm mờ viễn cảnh FC-PFS đã được đề xuất, là khái quát hóa của

thuật toán FCM và IFCM. Bằng cách kết hợp các thành phần của tập PFS và mô hình

phân cụm, thuật toán đề xuất cho kết quả phân cụm tốt hơn một số thuật toán phân

cụm khác như FCM, IFCM, KFCM và KIFCM. Kết quả thử nghiệm được tiến hành

trên tập dữ liệu chuẩn UCI đã khẳng định được hiệu quả của thuật toán đề xuất. Kết

quả này là cơ sở để cho các nghiên cứu, cải tiến tiếp theo của thuật toán trên các bài

toán mở rộng như tự động xác định số cụm, xử lý dữ liệu phức tạp và áp dụng cho

một số ứng dụng dự báo trong tương lai.

Các kết quả của Chương này đã được công bố trong công trình CT1 và CT2:

[CT1]. Pham Huy Thong, Le Hoang Son (2016), “Picture fuzzy clustering: a new

computational intelligence method”, Soft Computing 20(9), pp. 3549-3562. (SCIE,

2018, IF= 2.784, Springer).

[CT2]. Pham Thi Minh Phuong, Pham Huy Thong, Le Hoang Son (2018),

“Theoretical analysis of picture fuzzy clustering: Convergence and property”,

Journal of Computer Science and Cybernetics 34(1), pp. 17-32.

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

Trong chương này, hai cải tiến của thuật toán FC-PFS được trình bày nhằm

mục tiêu khắc phục những tồn tại của FC-PFS với việc tự động xác định số cụm và

xử lý với dữ liệu phức tạp.

- Cải tiến thứ nhất là một phương pháp dựa trên cách tiếp cận cắt tỉa được đề

xuất với tên gọi phân cụm mờ viễn cảnh tự động (AFC-PFS) để xác định số cụm phù

hợp nhất cho FC-PFS. AFC-PFS là thuật toán lai giữa phương pháp tối ưu hóa bầy

đàn (PSO) [28] và FC-PFS. Giải pháp kết hợp gồm số lượng các cụm và các tâm cụm

tương ứng và ma trận thành viên được đóng gói trong PSO. Các giải pháp kết hợp

được tối ưu hóa bởi chiến lược PSO và các hoạt động chính của FC-PFS. Để xác định

số lượng các cụm, luận án đề xuất một khái niệm mới là chỉ số viễn cảnh tổng hợp

(PCC). Thuật toán mới được thử nghiệm trên tập dữ liệu chuẩn của UCI [88] bằng

các chỉ số chất lượng phân cụm khác nhau. Các kết quả của phương pháp này được

trình bày trong [CT3].

- Cải tiến thứ hai là phương pháp xử lý dữ liệu phức tạp với tên gọi phân cụm

mờ viễn cảnh xử lý dữ liệu phức tạp (PFCA-CD) được đưa ra với cách tiếp cận phân

cụm đa tâm và lai ghép giữa phương pháp tối ưu hóa bầy đàn (PSO) [28] và FC-PFS.

Thuật toán đưa ra cách lựa chọn các tâm của một cụm sao cho xử lý được hiệu quả

với các dữ liệu phức tạp. Các kết quả của phương pháp này được trình bày trong

[CT4].

3.1. Thuật toán phân cụm mờ tự động xác định số cụm

3.1.1. Ý tưởng thuật toán

Bảng 1.1 mô tả tập dữ liệu thử nghiệm trong đó số cụm () phải được xác định

trước. Do đó, cần phải tự động xác định số cụm này trước khi các giải pháp tối ưu

được xem xét. Trong chương này, ý tưởng chính của thuật toán sẽ được trình bày,

diễn giải chi tiết các công thức, sơ đồ khối, và cuối cùng, luận ám tổng kết ưu và

nhược điểm của thuật toán đề xuất.

Luận án đề xuất thiết kế một phương thức lai giữa thuật toán tối ưu hóa bầy đàn

PSO [28] và FC-PFS, được đặt tên là AFC-PFS, trong đó các giá trị ngưỡng, số cụm,

tâm cụm tương ứng và ma trận độ thuộc được đóng gói và tối ưu bởi chiến lược của

thuật toán PSO. Thuật toán mới AFC-PFS sử dụng lược đồ tối ưu PSO, mỗi cá thể

hay mỗi phương án trong PSO khởi tạo ngẫu nhiên giá trị các tham số và sau đó lặp

giảm số lượng cụm cho đến khi chỉ số chất lượng cụm trong phạm vi chấp nhận

được theo một ngưỡng . Số lượng các cụm đã đạt được được coi là một giá trị tối ưu với các giá trị hiện tại của các tham số của ( (),(),()và ). Sau đó, thuật toán FC-PFS được sử dụng để có được kết quả phân cụm cuối cùng bao gồm độ thuộc, độ trung lập và độ từ chối ( (),(), ()) và các các tâm cụm ().

Tiếp theo, thuật toán kiểm tra lại quá trình cập nhật các giá trị tốt (pbest và

gbest) trong PSO bằng cách so sánh trị của chỉ số đánh giá Alternative Silhouette

() [89] được tính từ kết quả cụm cuối cùng với các giá trị pbest và gbest hiện

tại. Các pbest mới và gbest được sử dụng để định hướng sự thay đổi giá trị ngưỡng

( và ). Cũng cần lưu ý rằng, ngưỡng cập nhật, đặc biệt là sau đó được sử dụng để định hướng các hoạt động trong những bước lặp tiếp theo. Cụ thể, các giá trị mới sau bước đầu tiên là: ( (),(),()) nhận được từ FC-PFS, ngưỡng và , số tối ưu cụm và giá trị . Giá trị được tính từ ( (),(),()) và so sánh với ngưỡng mới để một lần nữa giảm số lượng các cụm . Sau đó, giá trị mới được sử dụng cho FC-PFS để làm kết quả cho cụm khác. Do đó, ngưỡng sẽ ảnh hưởng đến số lượng cụm tối ưu trong thuật toán. Thuật toán được thực hiện lặp lại cho đến

khi kết quả giải pháp không thay đổi thông qua hai bước lặp liên tiếp hoặc số lần lặp

đã đạt tối đa.

3.1.2. Chi tiết thuật toán

Chi tiết thuật toán được mô tả như sau. Khởi tạo ban đầu số lượng phương án của

PSO là = , , . . , , trong đó mỗi phương án gồm các thành phần sau:

 ( (),(),()): là ma trận độ thuộc, độ trung lập và độ từ chối của phương án ,

 (): Các tâm cụm tương ứng với (,,),

 : một ngưỡng để xác định số lượng các cụm của phương án ,

 : vận tốc dịch chuyển ngưỡng của phương án ,

 : số lượng các cụm của phương án .

Một phương án bắt đầu từ một số cụm nhất định được biểu thị bằng , là căn bậc hai của số phần tử trong tập dữ liệu, và cố gắng để thay đổi nó theo các giá trị hiện tại của ( (),(),()) và . Để làm được điều này, chỉ số viễn cảnh tổng hợp () được đề xuất. Giá trị càng lớn thì cụm đó sẽ có xu hướng được giữ lại.

(3.1) , ( = 1, . . . , ), = ∑ 1 − −

trong đó c là số cụm cho trước. Tiêu chí cho việc lựa chọn số lượng cụm phụ thuộc

vào ngưỡng của phương án. Khi tìm thấy số cụm tối ưu cho phương án này, áp dụng FC-PFS để có được các giải pháp mới ( (),(),(),()). Để kiểm chứng kết

quả, thuật toán đề xuất được cài đặt và so sánh với các thuật toán tương tự khác. Phép

đo này đóng vai trò là một giá trị fitness trong PSO. Một trong những chỉ số đánh giá

ổn định nhất cho việc phân cụm Alternative Silhouette () [89], được sử dụng để đo lường chất lượng cụm. Cần lưu ý rằng từ các giải pháp ( (),(),(),()), ta

phải sử dụng một phương pháp giải mờ để xác định cụm mà phần tử thuộc về.

Nếu giải pháp đạt được các kết quả là tốt hơn so với những giải pháp trước đó,

các giải pháp ngày được ghi nhận là giải pháp tối ưu cục bộ địa phương Pbest-

() ,

() () , ( cách thay đổi ngưỡng như sau.

) của phương án. Sau đó, phương án được cập nhật bằng

= + × () × ( − ) + × () × ( − ),

(3.2)

(3.3) = + , ( = 1, . . . , ),

ở đây , là các tham số PSO để cập nhật (một cách tổng quát = = 1). Luận án định nghĩa một giá trị mới, khi đó các giải pháp khác nhau ( (),(),(),) có thể nhận được kết quả tốt hơn so với các giải pháp tối ưu cục bộ địa phương Pbest

() ,

() ( đến khi tất cả các bước lặp được thực hiện. Các giải pháp cuối cùng cho kết quả số

). Cập nhật tất cả các phương án được tiếp tục lặp lại cho

lượng các cụm là phù hợp nhất, các tâm cụm và ma trận thuộc của nó được xác định

từ tất cả các phương án thông qua các giá trị tốt nhất của các giá trị cục bộ từng

phương án () và tổng thể tất cả các phương án ().

Sơ đồ khối của thuật toán được thể hiện ở hình 3.1 và bảng 3.1 dưới đây.

← , ← , = 0, ← , ( = 1, … , ), = 0

Begin

Phương án i Phương án j

+ +; Giảm số cụm ; + +; Giảm số cụm ;

Tính toán (, , , ) bằng FC-PFS với số cụm ; Tính giá trị ASWC; Tính toán (, , , ) bằng FC-PFS với số cụm ; Tính giá trị ASWC;

Cập nhật Pbest; Cập nhật Pbest;

Cập nhật Gbest

Sai Sai

Điều kiện dừng Cập nhật và Cập nhật và

Đúng

Kết thúc

Hình 3.1. Lược đồ của thuật toán AFC-PFS

Một số tham số của thuật toán PSO như sau:

 : ngưỡng có chất lượng cụm tốt nhất của phương án .

 : giá trị chất lượng tốt nhất mà một phương án đạt được.

 : số lượng tốt nhất của các cụm mà một phương án đạt được.

() ,

() ( phương án có chất lượng cụm tốt nhất theo thứ tự.

 ): ma trận độ thuộc, độ trung lập và độ từ chối của

()

() ,

).  : các tâm cụm tương ứng với (



(,,): ma trận độ thuộc, độ trung lập và độ từ chối có chất lượng cụm tốt nhất của bầy theo thứ tự.

 : tâm cụm tương đương (,,).

 : ngưỡng có chất lượng cụm tốt nhất của tất cả các phương án.

 : giá trị chất lượng tốt nhất mà tất cả các phương án đạt được.

 : số lượng tốt nhất của cụm mà tất cả các phương án đạt được.

Bảng 3.1. Mô tả chi tiết thuật toán AFC-PFS

I: Dữ liệu với () bản ghi với thuộc tính; Số lượng cụm lớn nhất (); ngưỡng , số vòng lặp tối đa > 0, số phương án .

O: Ma trận , , và tâm cụm ; số cụm phù hợp nhất ()

1: Khởi tạo một phương án ( = 1, . . . , ):

- Khởi tạo ngẫu nhiên ( (), (), ()) thỏa mãn công thức (2.2)

- Khởi tạo ngẫu nhiên giá trị và

- Gán số cụm của phương án i là =

- Gán giá trị tốt nhất của phương án i là = 0

End

() = 0

2: t = 0

3: Repeat

4: For each phương án

t = t + 1 5:

6: For = 1 to

7: Tính giá trị theo công thức (3.1)

End 8:

9: ∑ =

10: = 0

11:

For = 1 to 12: If < −

13: Loại cụm

14: + +

15: End

16: End

17: = −

18: If < 2 break

19:

Sử dụng FC-PFS với là số cụm và tính toán các ma trận ( (),(),(),()). Các tham số khác của FC-PFS được đặt mặc định.

20: Tính toán giá trị theo công thức (1.16)

21: If = 0 or <

()

22: =

() ,

23: ) = ( (),(),(),()) (

24: =

25:

26:

()

27: = If () = 0 or () < () =

() ,

28: ) (,,,) = (

29: =

30: =

31: Cập nhật bằng công thức (3.2)

32: Cập nhật bằng công thức (3.3)

33: Endforeach

34: Until () − () < or >

35: End

36: Output (, , ,,) = (,,,,)

Thuật toán đề xuất dựa trên PSO thường có các bước chung như sau: khởi tạo

tập các phương án ban đầu, tiến hành lặp trong việc tính toán các giá trị fitness và cập

nhật các phương án.

Trước tiên, tập hợp các phương án được thiết lập với số phương án xác định.

Một ngưỡng và giá trị vận tốc dùng để thay đổi ( và ) của phương án được khởi tạo ngẫu nhiên. Số cụm cho mỗi giải pháp () được thiết lập là . Các độ mờ viễn cảnh của mỗi phương án được thiết lập ngẫu nhiên thỏa mãn điều kiện của tập

mờ viễn cảnh. Việc khởi tạo như trong bước 1.

Tiếp theo, các bước 6-17 thực hiện giảm số cụm của phương án dựa trên các

giá trị ( = 1. . . ) trong phương trình (111). Nếu + nhỏ hơn giá trị

trung bình của ( = 1. . . ), cụm được loại bỏ. Nếu < 2, việc tính toán cho

phương án kết thúc.

Sau đó, mỗi phương án sử dụng FC-PFS để chia dữ liệu thành các cụm theo bước 19. Công việc này được tiến hành với một số ít các bước lặp để tránh hội tụ đến

giá trị tối ưu địa phương với một số lượng các cụm không đúng. Kết quả phân cụm

được sử dụng để tính trong đó nó được xem như hàm fitness của PSO tại bước

20.

Cuối cùng, quá trình cập nhật được thể hiện từ bước 21-32. Nếu giá trị

tốt hơn so với các giải pháp hiện tại tốt nhất của phương án () và giải pháp toàn cục tốt nhất () thì và được cập nhật. Giá trị ngưỡng sau đó được cập nhật trong các bước 27-32. Thuật toán sẽ kết thúc khi giải pháp tốt nhất toàn

cục không thay đổi qua một số hữu hạn lần lặp liên tiếp hoặc số lần lặp vượt

ngưỡng. Thuật toán AFC-PFS sẽ cho kết quả là số lượng các cụm và giải pháp phân

cụm của nó (,,,,) đồng thời.

Theo kết quả của chương 2, độ phức tạp tính toán của FC-PFS là () với là số lần lặp của thuật toán FC-PFS. Thuật toán AFC-PFS còn cần đến số lần lặp của thuật toán PSO sau mỗi quá trình tính toán, khi đó độ phức tạp của thuật toán là () với là số lần lặp của thuật toán PSO. Do trong thuật toán này thường được đặt là một số hữu hạn lần lặp với giá trị không quá lớn nên độ phức tạp của thuật toán là (). Do số lượng cụm trong mỗi quá trình lặp PSO là khác nhau và

giảm dần nên trong trường hợp thuận lợi, thuật toán sẽ cho nhỏ và độ phức tạp cỡ

(). Trong trường hợp xấu nhất, khi không thể giảm được số cụm hoặc số cụm giảm không đáng kể thì độ phức tạp thuật toán sẽ là () do ≈ √.

Sau đây là một ví dụ về loại bỏ một cụm trong bước 13 của AFC-PFS.

Giả sử có bốn phần tử trong dữ liệu (,,,) và số lượng cụm tối đa là 3. Giá trị của ngưỡng = 0.1, các độ thuộc , , của mỗi phần tử được sinh ngẫu

nhiên như trong bảng 3.2.

Bảng 3.2. Giá trị của các phần tử trong ví dụ

Dataset × (2 − )

Cụm 1 0.25 0.1 0.2 0.45

Cụm 2 0.3 0.2 0.4 0.48

Cụm 3 0.04 0.3 0.25 0.07

Cụm 1 0.2 0.1 0.4 0.32

Cụm 2 0.4 0.05 0.35 0.66

Cụm 3 0.015 0.2 0.7 0.02

Cụm 1 0.3 0.2 0.1 0.57

Cụm 2 0.2 0.1 0.4 0.32

Cụm 3 0.061 0.1 0.2 0.101

Cụm 1 0.03 0.05 0.35 0.05

Cụm 2 0.1 0.15 0.5 0.15

Cụm 3 0.5 0.1 0.4 0.8

Dựa vào bảng 3.2, mỗi phần tử có các độ thuộc khác nhau với các cụm khác

nhau và giá trị tối đa × (2 − ) cho biết phần tử thuộc cụm nào. Bảng này cũng cho

thấy rằng và thuộc cụm 1, thuộc cụm 2 và thuộc cụm 3. Theo bước 9, giá trị ( = 1,2,3) được tính như dưới đây.

= 0.503,

= 0.495,

= 0.312.

Sau đó, giá trị trung bình được tính: = 0.436769. So sánh giá trị này với

các giá trị , = 1,2,3.

= 0.503 > 0.436769 – 0.1 = 0.336769 do đó cụm 1 được giữ lại.

= 0.495 > 0.436769 – 0.1 = 0.336769 do đó cụm 2 được giữ lại.

= 0.312 < 0.436769 – 0.1 = 0.336769 do đó cụm 3 bị xóa.

Sau khi loại bỏ cụm 3, các giá trị , , của mỗi phần tử thu được như trong

bảng 3.3.

Bảng 3.3. Giá trị của các phần tử sau khi loại bỏ cụm 3 trong ví dụ

× (2 − ) Dataset

Cụm 1 0.25 0.1 0.2 0.45 Cụm 2 0.3 0.2 0.4 0.48

Cụm 1 0.2 0.1 0.4 0.32 Cụm 2 0.4 0.05 0.35 0.66

Cụm 1 0.3 0.2 0.1 0.57 Cụm 2 0.2 0.1 0.4 0.32

Cụm 1 0.03 0.05 0.35 0.05 Cụm 2 0.1 0.15 0.5 0.15

Dựa trên giá trị tối đa (2 − ) trong bảng 8, các phần tử có thể xác định số

cụm mà chúng thuộc về. Chi tiết, , và thuộc cụm 2 và thuộc cụm 1. Các độ thuộc sau đó được cập nhật bởi thuật toán FC-PFS sau bước 19 trong bảng 8.

Cuối cùng, thuật toán AFC-PFS đề xuất có những ưu điểm sau so với những

thuật toán khác có liên quan:

1) Thuật toán AFC-PFS sử dụng chiến lược tiếp cận của PSO và các giá trị

ngưỡng cho bài toán phân cụm mờ.

2) AFC-PFS linh hoạt hơn trong việc áp dụng cho các phương pháp phân cụm

mờ khác bằng cách thay đổi FC-PFS với các thuật toán phân cụm mờ khác với

những thay đổi tương ứng của hàm thuộc và các giải pháp phân cụm. Tùy

thuộc vào bài toán, người dùng có thể xây dựng một hàm mục tiêu tương ứng

phù hợp để xây dựng một khung lai dựa trên PSO như được trình bày trong

chương này.

Tuy nhiên, mô hình đề xuất vẫn tồn tại một số hạn chế như sau:

1) Thời gian tính toán khá lớn vì mỗi phương án phải áp dụng FC-PFS cho kết

quả phân cụm trong mỗi lần lặp. Mặc dù, số lần lặp được thiết lập cho FC-

PFS là nhỏ (ít hơn 100), thời gian thực hiện của thuật toán vẫn còn lớn.

2) Thuật toán đề xuất tìm ra số cụm dựa trên chiến lược từ trên xuống. Như

vậy, số cụm trong mỗi phương án được giảm từ một số cụm nhất định và

không thể tăng lại được. Do đó có thể bỏ sót nghiệm. Nói cách khác, trường

hợp này hiếm khi xảy ra vì số lượng các cụm thực tế thường nhỏ hơn rất

nhiều số phần tử của tập dữ liệu được sử dụng để thiết lập giá trị của .

3.1.3. Kết quả thực nghiệm

Ở phần này, thuật toán đề xuất AFC-PFS được cài đặt bên cạnh thuật toán GA

[48] của phương pháp cắt tỉa, phương pháp không tham số (NPM) [32] của phương

pháp quét và thuật toán CCE [68] của phương pháp tiền xử lý trong ngôn ngữ lập

trình C và thực thi trên hệ thống IBM 1350 với cấu hình: Intel Xeon Dual Core 3.2

GHz, 2Gb RAM.

Các thông số của phương pháp đề xuất được lựa chọn như sau: hệ số là 0.6;

bộ mờ hóa được thiết lập là 2; Các tham số cho thuật toán PSO: được đặt thành 10; , được đặt thiết lập là 1 [28]. giá trị được thiết lập là 10-5. Kết quả thử nghiệm có được là kết quả trung bình sau 50 bước chạy. Số cụm tối đa được thiết

lập là √ trong đó là số lượng các phần tử trong mỗi tập dữ liệu. Để đánh giá độ

chính xác, các giá trị trung bình và chuẩn được xem xét sử dụng.

Để kiểm tra sự tác động của việc sử dụng ASWC trong việc đo chất lượng phân

cụm, AFC-PFS được cài đặt với hai biến thể sử dụng các chỉ số đánh giá khác nhau

là WGLI [89] và PBM [100].

Bảng 3.4 mô tả số cụm trung bình và giá trị của các thuật toán sau 50 lần thử

nghiệm. AFC-PFS với chỉ số ASWC cho kết quả là bốn giá trị gần với số cụm thực.

Ví dụ: số cụm trung bình của thuật toán AFC-PFS (ASWC) cho tập dữ liệu WINE là

3.38. Con số này có sự khác biệt nhỏ nhất với số cụm thực trên tập dữ liệu này 3 (lỗi:

0.38) so với 3.85 (resp. 0.85) của GA (ASWC), 10 (resp. 7) của CCE, 3.52 (resp.

0.52) của NPM (ASWC), 6.72 (resp. 3.72) của – PFS (PBM) và 2 (resp. 1) của AFC-

PFS (WGLI). Hơn nữa, AFC-PFS (ASWC) cho ta số cụm chính xác cho tập dữ liệu

WDBC và IONOSPHERE.

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

IRIS

WINE

WDBC

GLASS

IONOSPHERE

HABERMAN

HEART

được định sẵn trong cột)

Dataset

(2)

(3)

(2)

(6)

(2)

ASWC WGLI PBM

2.36 2.14 4.26

3.85 3.51 3.4

2.66 2.82 3.55

7.36 2.66 12.51

2.58 3.01 6.13

2.6 2.45 4.7

3.63 2.27 5.28

NPM

ASWC WGLI PBM

3.38 2.34 2.04

3.52 4.22 4.57

2.64 2.12 2.01

6.74 2.535 7.01

2.08 2.28 2.72

2.06 2.04 2.52

2.24 2.03 2.35

CCE

3 AFC- PFS

ASWC WGLI PBM

2 2 5.22

3.38 2 6.72

2 2 4.88

6.64 2 6.72

2 2 3.44

2.04 2.02 4.94

3.76 3.04 6.48

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.

Dataset

IRIS WINE WDBC GLASS

IONOSPHERE HABERMAN HEART

ASWC WGLI PBM

0.84 0.4 0.38

1.4 1.04 1.341

0.66 0.98 1.13

1.36 0.65 1.429

0.47 0.62 0.869

0.51 0.82 2.05

1.62 0.539 2.36

NPM

ASWC WGLI PBM

1.14 0.47 0.44

1.29 2.3 1.45

0.82 0.74 0.16

2.41 0.34 0.36

0.34 0.505 0.04

0.23 0.29 0.44

0.43 0.311 0.39

CCE

AFC- PFS

ASWC WGLI PBM

0.25 0.22 2.78

0.85 0.65 1.44

0.01 0.26 0.78

3.24 1.54 2.22

0.34 0.25 1.56

0.18 0.22 2.46

0.72 0.32 2.68

Hình 3.2. Số cụm trung bình của các thuật toán

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

Tương tự, giá trị ASWC của AFC-PFS (ASWC) cho WINE và GLASS có

chênh lệch ít hơn so với những phương pháp khác. AFC-PFS với chỉ số WGLI đứng

thứ hai với ba giá trị thu được có sự khác biệt nhỏ về số lượng các cụm so với các

phương pháp khác, tương tự với AFC-PFS (ASWC) trên tập dữ liệu WDBC,

IONOSPHERE và HABERMAN. Tuy nhiên, phương pháp này cho kết quả là số

lượng các cụm nhỏ giữa 2 và 3. Phương pháp CCE hoạt động đúng với bộ dữ liệu

IRIS khi cho kết quả ba cụm. Nó tạo ra nhiều hơn hoặc thậm chí nhiều hơn số cụm

thực của các tập dữ liệu khác. Phương pháp NPM (WGLI) cũng là một trường hợp

tốt cho tập dữ liệu HEART.

Bảng 3.5 trình bày sự thay đổi kết quả số cụm của các thuật toán thông qua giá

trị STD. CCE là một phương pháp tiền xử lý, nó không cho phép có bất kỳ thay đổi

giá trị nào thông qua 50 lần chạy (STD = 0). AFC-PFS (WGLI) thường có giá trị STD

nhỏ hơn các giá trị STD. so với các phương pháp khác. Các giá trị của phương pháp

này được trình bày trong bảng 4, thường nhỏ hơn 1 và số cụm của AFC-PFS (WGLI)

nằm giữa 2 và 3. AFC-PFS (aswc) cũng có giá trị nhỏ STD. nhỏ, ngoại trừ với trường

hợp của tập dữ liệu GLASS (3.24). AFC-PFS (PBM) có giá trị STD. lớn nhất trong

tất cả các biến thể của AFC-PFS mà trong đó, hầu hết các giá trị là lớn hơn 1.

Hình 3.2 cho thấy số cụm trung bình của các thuật toán với thanh sai số. Rõ

ràng, biểu đồ số cụm trung bình khá khác biệt trong các thuật toán và trong mỗi tập

dữ liệu. Trong tập dữ liệu IRIS, AFC-PFS (PBM) và GA (PBM) có số cụm trung bình

lớn hơn 4 trong khi số cụm trung bình của các thuật toán khác nằm giữa 2 và 3. Sai

số của các thuật toán khi sử dụng chỉ số PBM như giá trị fitness thường lớn hơn những

chỉ số khác, đặc biệt là trong GA và AFC-PFS. Chỉ có CEE là phương pháp không

có sai số trong biểu đồ này vì nó là phương pháp tiền xử lý và không sử dụng bất kỳ

tiến trình ngẫu nhiên nào. Phương pháp NPM có kết quả ổn định, số lượng cụm thay

đổi không đáng kể. Với tập dữ liệu GLASS, số lượng cụm của các thuật toán biến

động đáng kể, một số trong đó có cố cụm ít hơn 3 (các thuật toán sử dụng WGLI như

giá trị fitness), một số khác cho số cụm nằm giữa 6 và 8 và GA (PBM) là trên 12. Sai

số cho tập dữ liệu GLASS cũng khá cao trong hầu hết các thuật toán; với sáu thuật

toán có sai số trên 1. Để xác định lý do phát sinh sai số, các giá trị STD của AFC-

PFS (ASWC) và các phương pháp khác được tính toán và cho thấy có giá trị khá lớn

trên bộ dữ liệu GLASS. Để làm rõ hơn điều này, một biểu đồ phân tán cho mối tương

quan giữa các thành phần với các cụm thực sự của dữ liệu GLASS được mô tả trong

hình 3.3. Hình này chỉ ra rằng sự phân tán các phần tử trên tập dữ liệu này là không

tốt để có thể xác định chính xác số lượng cụm. Sáu biểu đồ đầu tiên cho thấy sự phân

bố của các phần tử với mật độ cao trong một diện tích nhỏ cho thấy các cụm được

sáp nhập một cách nghiêm ngặt. Có thể thấy rõ hơn điều này trong hình 3.4. Trong

hình này, hệ số tương quan giữa thành phần thứ nhất và thành phần thứ hai trên tập

dữ liệu GLASS. Một số yếu tố xác định vị trí hẹp làm cho một khu vực mật độ cao

và một số phần tử khác xuất hiện xa khu vực này. Đây rõ ràng là nhiễu và các biên.

Trong trường hợp này, thuật toán thậm chí khó tìm được cách phân phần tử vào các

cụm cho trước. Đây chính là lý do tại sao giá trị STD của tất cả các thuật toán thường

khá cao và rất khó để có thể xác định một số lượng phù hợp của các cụm.

Hình 3.4. 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

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

GA

NPM

AFC-PFS

Dataset

ASWC WGLI

PBM

ASWC WGLI

PBM

ASWC WGLI

PBM

IRIS

3.575

0.404

5.281

3.831

0.404

5.319

3.789

0.405

5.347

WINE

3.353

0.401

718.1

3.483

0.399

741.127

3.573

0.4

711.377

WDBC

3.129

0.386

1517.152

4.269

0.404

1570.496

4.495

0.401

1548.157

GLASS

2.03

0.319

3.871

2.928

0.374

3.381

2.621

0.368

3.359

IONOSPHERE

1.393

0.253

2.544

1.522

0.3

2.482

1.556

0.305

2.503

HABERMAN

1.681

0.342

18.037

1.788

0.363

17.356

1.674

0.352

20.5

HEART

1.83

0.36

96.768

1.92

0.379

103.476

1.93

0.381

103.471

(Các giá trị bôi đậm có nghĩa là tốt nhất trong một hàng)

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

GA

NPM

AFC-PFS

Dataset

ASWC

WGLI

PBM

ASWC

WGLI

PBM

ASWC

WGLI

PBM

IRIS

0.588

0.011

0.156

0.179

0.006 0.045

0.358

0.012

0.151

WINE

0.319

0.007

1.337

0.182

0.008 4.426

0.243

0.007795

0.485

WDBC

0.508

0.032

5.677

0.351

0.013 9.462

0.448

0.01

3.598

GLASS

0.725

0.057

0.768

0.216

0.032 0.389

0.58

0.022

0.157

IONOSPHERE

0.221

0.08

0.592

0.288

0.072 0.811

0.093

0.037

0.128

HABERMAN

0.136

0.03

1.793

0.075

0.024

1.82

0.097

0.014

3.059

HEART

0.129

0.026

5.059 0.00049 0.002 0.001 0.00449

2.46E-05

0.001182

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

GA

NPM

AFC-PFS

Dataset

ASWC WGLI

PBM

ASWC WGLI

PBM

ASWC WGLI

PBM

IRIS

3.727 0.411

5.556

3.585 0.406

5.732

3.831

0.414

5.317

WINE

3.191 0.406 721.752

3.013 0.403 737.249

3.483 0.409 740.872

WDBC

3.471 0.407 1829.917 4.134

0.424 1680.676 4.318 0.414 1545.791

GLASS

2.805 0.391

3.221

2.929 0.384

3.514

2.845

0.39

3.231

IONOSPHERE

1.544 0.308

2.185

1.501 0.311

2.475

1.418 0.335

2.422

HABERMAN

1.761 0.361

17.074

1.795 0.366

17.218

1.79

0.364

17.334

HEART

1.891 0.373

98.349

1.924 0.378

105.88

1.919 0.377 104.292

(Các giá trị bôi đậm có nghĩa là tốt nhất trong một hàng)

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

GA

NPM

AFC-PFS

Dataset

ASWC WGLI

PBM ASWC WGLI

PBM

ASWC WGLI

PBM

IRIS

0.278

0.005

0.11

0.362

0.006

0.608

1.8E-4

1.12E-5

1.31E-3

WINE

0.408

0.001

22.072

0.005

39.304

2.24E-3

9.14E-3

29.8

0.39

WDBC

0.902

0.008

3.505

0.01

3.748

2.69E-3

1.04E-4

3.459

0.56

GLASS

0.308

0.015

0.129

0.028

0.011

0.024

4.733E-3

0.1

0.182

IONOSPHERE

0.09

0.036

0.134

0.322

0.034

0.001

1.021E-4

0.004

0.362

HABERMAN

0.076

0.01

0.512

0.029

0.003

0.041

4.189E-3

1.19

0.849

HEART

0.068

0.011

3.989

0.037

0.006

0.053

8.822E-3

4.011

2.851

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

GA

NPM

AFC-PFS

Dataset

ASWC WGLI

PBM

ASWC WGLI

PBM

ASWC WGLI

PBM

IRIS

1.466

0.3

5.635

1.511

0.292

6.992

1.533

0.294

7.077

WINE

3.163

0.388 1292.967

1.619

0.334 1305.432

2.399

0.389

1296.49

WDBC

1.505

0.341 2261.864

1.862

0.344 2220.938

1.875 0.347 2269.417

GLASS

1.261

0.229

5.08

2.012

0.255

3.675

1.334

0.216

3.732

IONOSPHERE

1.05

0.098

3.762

1.066

0.14

3.778

1.078

0.138

3.141

HABERMAN

1.44

0.25

23.811

1.485

0.243

28.647

1.372

0.224

29.457

HEART

1.304

0.225

142.812

1.318

0.221

183.382

1.256

0.21

136.406

(Các giá trị bôi đậm có nghĩa là tốt nhất trong một hàng)

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

GA

NPM

AFC-PFS

Dataset

ASWC WGLI PBM ASWC WGLI

PBM ASWC WGLI

PBM

IRIS

0.099

0.025

0.069

0.289

0.041

0.165

0.337

0.037

0.174

WINE

0.403

0.01

21.848

0.037

0.049

33.767

0.105

7.47E-3

14.35

WDBC

0.191

0.014

30.537

0.208

0.056

68.883

0.10

0.012

72.401

GLASS

0.051

0.018

0.106

0.131

0.08

0.025

0.075

0.016

0.063

IONOSPHERE

0.028

0.007

0.056

0.001

1.33E-3

1.42E-3

0.023

0.016

0.041

HABERMAN

0.053

0.017

2.086

0.01

0.018

0.209

0.038

0.019

0.308

HEART

0.041

0.013

5.83

0.016

0.006

0.914

0.06)

0.035

. 1.952

(Các giá trị bôi đậm có nghĩa là tốt nhất trong một hàng)

Để đánh giá chất lượng của thuật toán đề xuất so với những thuật toán khác, các

giá trị trung bình (STD) của các chỉ số PBM, WGLI và ASWC cho các thuật toán

được tính trong bảng 3.6–3.11. Bảng 3.6 mô tả giá trị chỉ số đánh giá của các thuật

toán sử dụng ASWC như giá trị fitness. Thuật toán đề xuất có giá trị về chỉ số ASWC

cho WINE, WDBC, IONOSPHERE và HEART là lớn nhất. Ví dụ, trong bộ dữ liệu

WINE với giá trị ASWC, thuật toán đề xuất nhận được 3.573 so với 3.483 của NPM

và 3.353 của GA. NPM cũng có ba giá trị lớn nhất cho ASWC trong IRIS, GLASS

và HABERNAMS. Điều này cho thấy AFC-PFS có chất lượng phân cụm tốt hơn so

với MMI và GA dựa trên chỉ số ASWC cho các tập dữ liệu. Tương tự, đối với chỉ số

WGLI, AFC-PFS có ba giá trị lớn nhất cho tập dữ liệu IRIS, IONOSPHERE và

HEART, NPM cũng có ba giá trị lớn nhất với WDBC trên GLASS HABERMAN và

GA. Đối với chỉ số PBM, AFC-PFS có cả hai giá trị lớn nhất (trong IRIS và

HABERMAN) so với ba của (WINE, WDBC và HEART) của NPM và một của GA.

Do đó, đối với tất cả các chỉ số đánh giá, AFC-PFS có chín giá trị tối đa, bằng NPM

và nhiều hơn so với GA. Những kết quả này chỉ ra rằng AFC-PFS có chất lượng phân

cụm tương tự chất lượng phân cụm của NPM và tốt hơn GA trong cả ba chỉ số. Bảng

3.8–3.11 cho biết kết quả phân cụm của ba thuật toán trên các chỉ số.

Hình 3.5. Giá trị ASWC trung bình của các thuật toán với giá trị sai số

Hình 3.6. Giá trị WGLI trung bình của đầu ra các thuật toán với sai số

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.

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

Chi tiết cho các chỉ số đánh giá cho các thuật toán được trình bày trong hình

3.5–3.8. Trong hình 3.5, có thể thấy rằng các giá trị trung bình chỉ số ASWC cho các

thuật toán bằng cách sử dụng PBM thì nhỏ hơn so với những thuật toán khác, mặc dù

sai số của chúng là rất nhỏ. Hình 3.6 hiển thị các kết quả tương tự như hình 3.5. Nó

cũng chỉ ra rằng cài đặt thuật toán với WGLI đóng vai trò giá trị fitness không làm

cho kết quả có chỉ số ASWC và WGLI cao. Khi sử dụng WGLI hoặc ASWC, kết quả

nhận được thường như nhau.

Bảng 3.12. Thời gian tính toán của các thuật toán (giây)

AFC-PFS

Dataset

GA

CCE

NPM

PBM

WGLI

ASWC

IRIS 14.79 311 21.88 13.96 13.89 13.91

WINE 109.46 24203 191.533 101.8 99.94 118.93

WDBC 2425.4 56920 8451.33 2449.2 2343.48 2325.8

GLASS 66.05 1280 118.89 64.7 68.71 68.66

IONOSPHERE 919.51 8738 1883.98 897.16 896.14 912.91

HABERMAN 101.88 20461 179.86 99.71 105.77 101.77

HEART 273.23 2628 385.04 223.69 224.83 224.9

(Các giá trịbôi đậm có nghĩa là tốt nhất trong một hàng)

Hình 3.7–3.8 chỉ ra các giá trị đối ngẫu với các giá trị trong hình 3.5 – 3.6 khi

thuật toán sử dụng PBM để tính toán, chỉ số đầu ra của PBM rõ ràng cao hơn so với

những phương pháp khác, các kết quả của các thuật toán bằng cách sử dụng ASWC

và WGLI đều thấp hơn hoặc bằng. Do đó, chỉ số PBM dường như tương phản với

ASWC và WGLI.

Theo bảng 3.12, rõ ràng là thời gian chạy của AFC-PFS là nhanh hơn so với các

thuật toán khác. Cụ thể, AFC-PFS (trên tập WGLI) cho thời gian chạy tốt hơn trên

các tập dữ liệu IRIS, WINE và IONOSPHERE, và AFC-PFS (trên tập PBM) cũng

cho thời gian chạy tốt hơn trên GLASS, HABERMAN và HEART. Chỉ xét trên tập

dữ liệu WDBC, thời gian chạy của AFC-PFS (ASWC) là nhỏ nhất với 2325,8 giây

so với 2449,2 của AFC-PFS (PBM), 2344,48 của AFC-PFS (WGLI), 2425,4 của GA,

8451,33 của NPM và 56920 của CEE. Do đó, AFC-PFS là thuật toán nhanh nhất so

với GA, NPM và CEE, đặc biệt trên tập dữ liệu có kích thước và quy mô lớn.

3.2. Thuật toán phân cụm mờ với dữ liệu phức tạp

Trong phần này, thuật toán phân cụm mờ viễn cảnh với dữ liệu phức tạp (PFCA-

CD) được trình bày để khắc phục nhược điểm của FC-PFS. Qua tìm hiểu các nghiên

cứu liên quan về dữ liệu phức tạp, tác giả đưa ra định nghĩa về dữ liệu phức tạp như

sau.

Định nghĩa 3.1: Dữ liệu phức tạp là các dữ liệu gồm cả dữ liệu số, dữ liệu kiểu

loại, dữ liệu có các cấu trúc đặc biệt như các điểm dữ liệu trong các cụm xen kẽ lẫn

nhau, các điểm dữ liệu bố trí trên một đường thẳng hay theo các đường cong, ….

3.2.1. Độ đo cho thuộc tính kiểu loại

Giả sử , là khoảng cách của phẩn tử và trên thuộc tính ℎ ( = 1, … , , = 1, … , , ℎ = 1, … , ). Nếu thuộc tính ℎ là dữ liệu số, ℎ, được tính dựa theo công thức tính khoảng cách Euclid. Nếu dữ liệu là kiểu loại thì khoảng

cách được tính bằng phương trình (3.4).

, (3.4) ℎ, ℎ = 0 ế ℎ = ℎ 1 ượ ạ

Dữ liệu đầu vào được chuẩn hoá trên đoạn [0, 1] với 0 là khoảng cách tối thiểu

giữa hai phần tử và 1 là khoảng cách lớn nhất giữa hai phần tử. Theo phương trình

(3.4), nếu hai phần tử kiểu loại là không bằng nhau, khoảng cách giữa chúng là 1.

3.2.2. Thuật toán phân cụm với dữ liệu phức tạp (PFCA-CD)

Để phân vùng dữ liệu với kiểu kết hợp và cấu trúc khác biệt, thuật toán FC-PFS

được kết hợp với thuật toán PSO [28] và được đặt tên là Picture Fuzzy Clustering

Algorithm (PFCA-CD) như sau: Giả sử cho tập dữ liệu chứa dữ liệu kết hợp số và

kiểu loại có cấu trúc phức tạp và số các cụm . Thay vì sử dụng thao tác lặp của FC-

PFS, ta sử dụng bước lặp của PSO. Tập ban đầu của PSO là = , , . . ,

mà trong đó mỗi phương án bao gồm các thành phần sau:

 (, , ): độ thuộc, độ trung lập và từ chối của các phần tử tương ứng

trong .

 (,,): độ thuộc, độ trung lập và từ chối của các phần tử

trong có chất lượng cụm tốt nhất theo thứ tự.

 and : tập các tâm cụm tương ứng với (,,) và

(,,) theo thứ tự.

 : giá trị chất lượng tốt nhất mà một phương án đạt được.

Một phương án bắt đầu từ một giá trị cho trước của (,,) và cố gắng để

thay đổi chúng để sao cho đạt được giá trị tối ưu (fitness). Giá trị tối ưu được chọn

theo cùng một cách để tính hàm tối ưu như trong phương trình (3.5)

−

∑ = ∑ + 2 − (3.5) ∑ ∑ , +

Quá trình này có thể được coi là sự kết hợp tốt nhất giữa giá trị fitness và trạng

thái hiện hành của các phương án. Nếu các thuật toán cho kết quả là tốt hơn so với

thuật toán tối ưu địa phương

những liên quan khác, các giải pháp Pbest-(,,,) của các phương án được ghi lại. Sau đó, sự

tiến hóa của phương án được thực hiện bằng cách thay đổi giá trị của (,,và

). Trong sự tiến hóa, (,) được tính theo phương trình (2.6–2.7) và (3.6–3.7)

như dưới đây.

(3.6) = + − + − ,

( = 1, … , , = 1, … , ),

= + − + − , (3.7) ( = 1, … , , = 1, … , ),

trong đó (,,và ) là những giá trị tốt nhất của tất cả các phương án. Tâm của cụm được chọn bằngvòng lặp trình bày ở bảng 3.13.

Bảng 3.13. Cách chọn tâm cụm

Xác định tâm cụm ()

= ∅

Repeat

Tìm ∉ , ∈ , sao cho

2 −

‖ − ℎ‖ = ℎ,

= ∪

∑ 2 − ‖ − ‖ > và ℎ ∉ Until ,

Begin

() ← ;

() ←

Particle i Particle h

() ← ; () ← ;

; ( = 1, , = ; ( = 1, , =

1, ) thỏa mãn (2.2) 1, ) thỏa mãn (2.2)

Tính toán (, , , ) và giá trị fitness. Tính toán (, , , ) và giá trị fitness.

Cập nhật Pbest. Cập nhật Pbest.

Cập nhật Gbest

Sai Sai

Điều kiện dừng

Đúng

Kết thúc

Hình 3.9. Sơ đồ thuật toán PFCA-CD

Thuật toán sẽ tiếp tục lặp lại việc cập nhất tất cả các phương án cho đến khi giá

trị tối ưu toàn cục không đổi sau một số hữu hạn lần lặp hoặc vượt quá số lần lặp tối

đa cho phép. Các giải pháp cuối cùng bao gồm các giá trị phù hợp nhất của các tâm

cụm và ma trận độ thuộc được xác định với giá trị fitness tối thiểu. Chi tiết của thuật

toán đề xuất được trình bày trong hình 3.9 và bảng 3.14.

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

Thuật toán phân cụm mờ trên tập mờ viễn cảnh cho dữ liệu phức tạp (PFCA-CD)

I:

Tập dữ liệu có số phần tử () trong không gian chiều; Số cụm ();

ngưỡng , số mờ và số bước lặp > 0

O: Ma trận , , và các tâm cụm ;

PFCA-CD

() ← ( = 1, , =

t = 0

() ← ;

1, ) thỏa mãn (2.2)

Repeat

t = t + 1

() ( = 1, ) theo bảng 3.13

For each phương án

() ( = 1, ; = 1, ) bằng công thức (3.6)

Chọn tâm

() ( = 1, ; = 1, ) bằng công thức (3.7)

Tính toán

() ( = 1, ; = 1, ) bằng công thức (2.5)

Tính toán

10:

Tính toán

11:

Tính toán giá trị fitness bằng công thức (3.5)

12:

Cập nhật giá trị Pbesti

13:

Cập nhật giá trị Gbest

14: Until giá trị Gbest không đổi sau một số hữu hạn lần lặp hoặc số lần lặp vượt

End

15: Output (, , ,) = (,,,)

quá maxSteps

Phương pháp PFCA-CD được đề xuất ở trên có một số ưu điểm sau:

- Sử dụng nhiều tâm cụm cho mỗi cụm do đó mỗi cụm với các phần tử dữ liệu

phân tán trong cấu trúc không phải hình cầu và khác biệt có thể sẽ dễ dàng

biểu diễn qua các tâm cụm này.

- Sử dụng thuật toán FC-PFS với chiến lược PSO có thể làm nhanh quá trình

hội tụ.

- Sử dụng một phép đo mới cho các giá trị thuộc tính phân loại phù hợp trong

việc tính toán khoảng cách giữa hai đối tượng.

Tuy nhiên, phương pháp này vẫn có nhược điểm:

- Thuật toán PSO có thể cho kết quả tốt, nhưng không chắc là tốt nhất.

- Thời gian tính toán của PSO là khá cao. Độ phức tạp của thuật toán đề xuất là ( + ) cho mỗi phương án tại mỗi vòng lặp, trong đó là số lượng

các phần tử trong tập dữ liệu và là số cụm. Do đó, độ phức tạp của thuật toán là ( × ( + ) × ) trong đó và

là số bước lặp và số các phương án theo thứ tự. Do và thường bé, độ phức tạp của thuật toán đề xuất là ( × ). Nếu = 1, độ phức tạp của thuật toán chỉ là (). Trong trường hợp

xấu nhất, =maxsteps, thời gian tính toán của thuật toán được đề

xuất có thể cao nhất.

3.2.3. Kết quả thực nghiệm

Thuật toán đề xuát PFCA-CD được so sánh cùng các thuật toán khác gồm

DifFuzzy [20] và Dissimilarity [24]. Trong đó thuật toán DifFuzzy [20] là thuật toán

điển hình cho bài toán phân cụm với dữ liệu có cấu trúc phức tạp và thuật toán

Dissimilarity [24] là thuật toán phổ biến cho bài toán phân cụm với dữ liệu hỗn hợp

gồm dữ liệu kiểu loại và dữ liệu số.

Các thực nghiệm được cài đặt trên ngôn ngữ lập trình C và chạy trên một cụm

máy chủ Linux 1350 với tám nút 51.2GFlops. Mỗi nút có hai CPU Intel Xeon lõi kép

3,2 GHz, 2GB RAM. Kết quả thử nghiệm là giá trị trung bình sau 50 lần chạy.

Đo chất lượng cụm: chỉ số Mean Accuracy (MA), Davies-bouldin (DB) [24],

RAND (RI) [89] và Alternative Silhouette (ASWC) [89] được sử dụng để đánh giá

chất lượng phân cụm của các thuật toán.

Thiết lập tham số: một số giá trị của các tham số như fuzzifier = 2, = 10, = 1000 được thiết lập cho tất cả các thuật toán. Riêng PFCA-CD, các giá trị được thiết lập = = 1, ∈ 0.6 và = 10.

Mục tiêu: nghiên cứu này nhằm đánh giá chất lượng phân cụm của các thuật

toán thông qua các chỉ số đánh giá. Một số thử nghiệm qua các trường hợp khác nhau

20000

18000 16000 14000

Cụm 1

12000 10000 8000

Cụm 2

6000 4000 2000

của các tham số cũng được xét đến.

Hình 3.10. Sự phân bố dữ liệu của bộ dữ liệu STATLOG với hai thuộc

0.7

0.6

)

0.5

m m

( i

0.4

0.3

0.2

à d u ề h C

0.1

0.2

0.4

0.6

0.8

Đường kính (mm)

tính

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

250

200

Cụm 1

150

Cụm 2

) h c n i ( e x i

Cụm 3

100

Cụm 4

à d u ề h C

Cụm 5

Cụm 6

100

120

140

Chiều dài trục cơ sở (inch)

Cụm 1

Cụm 2

Cụm 3

Cụm 4

Cụm 5

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

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

Bộ dữ liệu thử nghiệm cho thuật toán phân cụm mờ viễn cảnh với dữ liệu phức

tạp được thử nghiệm trên các bộ dữ liệu IRIS, GLASS, ABALONE, AUTOMOBILE,

SERVO và STATLOG trong bảng 1.1. Trong đó ABALONE là bộ dữ liệu có số bản

ghi lớn, chỉ có dữ liệu số. Ba bộ dữ liệu còn lại có lẫn dữ liệu số và dữ liệu kiểu loại.

Hình 3.10–3.13 mô tả sự phân bố của dữ liệu STATLOG, ABALONE, SERVO và

AUTOMOBILE với hai thuộc tính. Có thể thấy được tính phức tạp về cấu trúc của

các dữ liệu này khi sự phân bố của các điểm dữ liệu vào các cụm là xen kẽ nhau,

không tập trung theo hình cầu mà có xu hướng kéo dài với các hình dạng phức tạp,

gây ra sự khó khăn trong việc phân cụm dữ liệu.

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á)

IRIS

MA ASWC DB RI

DifFuzzy 66.667 1.569 2.707 81.960

Dissimilarity 92.639 1.946 9.915 79.092

GLASS

PFCA-CD 92.667 11.217 76.599 1.971

DifFuzzy 66.667 0.621 4.654 67.557

Dissimilarity 86.888 1.082 4.239 57.303

AUTOMOBILE DifFuzzy

PFCA-CD 88.785 11.808 66.994 1.142

- - - -

Dissimilarity 96.404 1.715 3.812 62.56

ABALONE

PFCA-CD 96.464 1.147 4.936 61.346

DifFuzzy 33.333 0.745 6.437 63.912

Dissimilarity 82.146 1.411 8.721 64.371

SERVO

PFCA-CD 93.157 0.937 5.319 69.458

DifFuzzy 20 0.699 5.356 65.356

1.21 8.279 63.862 Dissimilarity 77.35

STATLOG

4.667 66.607 PFCA-CD 94.538 1.035

- - - DifFuzzy -

Dissimilarity 1.076 2.868 54.006 100

PFCA-CD 1.02 2.7 50.512 89.3

e g a t n e c r e P

100 90 80 70 60 50 40 30 20 10 0

y t i r a

l i

y z z u F f i

D C - A C F P

i s s i D

IRIS

GLASS

ABALONE AUTOMOBILE

SERVO

STATLOG

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

ASWC

toán với các tập dữ liệu khác nhau

x e d n

i

y t i d

i l

a V

y t i r a

l i

y z z u F f i

D C - A C F P

i s s i D

IRIS

GLASS

ABALONE

AUTOMOBILE

SERVO

STATLOG

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

Bảng 3.15 cho biết giá trị chỉ số đánh giá trung bình của thuật toán. Có thể thấy

rằng thuật toán PFCA-CD có chất lượng phân cụm tốt hơn với trên chỉ số đánh giá

so sánh với những thuật toán khác. Trong hầu hết trường hợp, thuật toán được đề xuất

có ít nhất một chỉ số đánh giá có giá trị tốt nhất. Ví dụ, với tập dữ liệu ABALONE và

SERVO, các giá trị chỉ số đánh giá của PFCA-CD tốt hơn so với MA, DB và RI của

DifFuzzy và Dissimilarity. Cụ thể là 93.157 (MA), 5.319 (DB) và 69.458 (RI) so với

33.333 (MA), 6.437 (DB) và 63.912 (RI) của DifFuzzy và 82.146 (MA), 8.721 (DB)

và 64.371 (RI) của Dissimilarity cho tập dữ liệu ABALONE. Hình 3.14 còn cho biết

thêm về các giá trị MA và RI của các thuật toán trên các tập dữ liệu khác nhau. Trong

hầu hết các trường hợp, thuật toán đề xuất cho giá trị tốt hơn so với DifFuzzy và

Dissimilarity. Tuy nhiên, đối với dữ liệu AUTOMOBILE và STATLOG thì thuật

toán đề xuất lại cho kết quả không tốt so với thuật toán Dissimilarity. Mặc dù vậy các

kết quả thực nghiệm chỉ ra độ sai lệch giữa các chỉ số của hai thuật toán là không lớn.

Điều này cho thấy thuật toán đề xuất hiệu quả hơn trong việc phân cụm các dữ liệu

phức tạp về mặt cấu trúc và là dữ liệu số.

Hình 3.15 cho ta thấy 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. Có thể thấy rằng các kết quả của thuật toán đề xuất nhỏ hơn

của DB với các tập dữ liệu STATLOG, SERVO, AUTOMOBILE. Trong ASWC, thuật

toán đề xuất có tốt hơn với tập dữ liệu IRIS và GLASS là các tập dữ liệu số. Điều này có

nghĩa là ASWC không cho kết quả tốt hơn với tập dữ liệu phức tạp.

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)

Số lần đạt giá trị tốt nhất Thuật toán

DifFuzzy 3

Dissimilarity 9

PFCA-CD 12

Bảng 3.16 hiển thị thời gian mà mỗi thuật toán cần để đạt được giá trị tốt nhất

trong bảng 3.15. PFCA-CD đứng đầu trong 12 giá trị tốt nhất, Dissimilarity đứng thứ

hai với 9 giá trị và thuật toán còn lại có ba lần giá trị tốt nhất. Sự biến động của các

chỉ số đánh giá được đưa ra trong bảng 3.17.

Bảng 3.17. Giá trị STD cho các chỉ số đánh giá của các thuật toán

MA ASWC DB RI

IRIS DifFuzzy 0 0 0 0

Dissimilarity 7.144 0.447 6.512 11.375

PFCA-CD 8.55 0.267 3.663 6.886

GLASS DifFuzzy 0 0 0 0

Dissimilarity 38.586 1.014 5.352 49.76

PFCA-CD 3.184 0.094 3.354 0.936

AUTOMOBILE DifFuzzy - - - -

Dissimilarity 2.63 0.039 4.113 0.247

PFCA-CD 0.7 0.002 0.086 0.072

ABALONE DifFuzzy 0 0 0 0

Dissimilarity 9.694 1.433 12.587 4.23

PFCA-CD 1.938 0.132 5.938 0.806

SERVO DifFuzzy 0 0 0 0

Dissimilarity 5.23 0.088 13.358 1.121

PFCA-CD 3.435 0.053 5.089 0.864

STATLOG DifFuzzy - - - -

Dissimilarity 2.96E-4 0.433 0.075 0

PFCA-CD 4.612 0.011 9.891 0.688

Trong bảng 3.17, giá trị STD cho các chỉ số đánh giá của thuật toán Diffuzzy

không thay đổi theo thời gian vì thuật toán này không sử dụng chiến lược heuristic.

Các giá trị STD của PFCA-CD thay đổi ít hơn so với thuật toán Dissimilarity. Điều

này có nghĩa là thuật toán đề xuất cho kết quả ổn định hơn so với Dissimilarity.

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

DifFuzzy Dissimilarity PFCA-CD

IRIS 31.048 (1.369) 4.165 (3.626) 4.743 (0.919)

GLASS 522.184 (35.528) 122.44 (121.87) 17.577 (1.39)

AUTOMOBILE 5214.669 (4457.619) 7643.86 (844.934) -

ABALONE 149.553 (0.058) 318.622 (71.871) 22.9 (9.017)

SERVO 16.975 (2.9E-3) 19.124 (3.439) 19.064 (6.279)

3082.443 (253.439) 108.688 (5.991) - STATLOG

Bảng 3.18 mô tả thời gian chạy của tất cả các thuật toán với giá trị chuẩn (STD).

Thời gian tính toán của thuật toán đề xuất là ngắn hơn so với những thuật toán khác

với các tập dữ liệu GLASS, AUTOMOBILE, SERVO và STATLOG. Chỉ trong tập

dữ liệu ABALONE và IRIS, thuật toán đề xuất có thời gian nhiều hơn. Trong tập dữ

liệu IRIS, thuật toán đề xuất cần 4.743 giây so với 4.165 giây của Dissimilarity. Sự

chênh lệch là nhỏ hơn một giây và đặc biệt là với thuật toán đề xuất cùng với giá trị

STD là thì thời gian nhỏ hơn nhiều so với những thuật toán khác, điều này có nghĩa

là thuật toán đề xuất cho thời gian chạy tốt như các thuật toán khác với tập dữ liệu

IRIS. Chỉ riêng tập dữ liệu AUTOMOBILE, thuật toán được đề xuất sẽ cần nhiều

thời gian hơn để chạy (7643.86 so với 5214.669 so với Disimilarity). Điều này cho

thấy rằng thuật toán được đề xuất không có hiệu quả trong dữ liệu số lớn và chỉ tốt

trên tập dữ liệu số.

3.3. Kết luận chương

Chương này đã trình bày hai thuật toán cải tiến cho thuật toán FC-PFS là thuật

toán phân cụm mờ viễn cảnh tự động xác định số cụm AFC-PFS và thuật toán phân

cụm mờ viễn cảnh cho dữ liệu phức tạp PFCA-CD.

Thuật toán AFC-PFS là sự kết hợp giữa thuật toán tối ưu hóa bầy đàn (PSO) và

phân cụm mờ viễn cảnh, mà trong đó giải pháp kết hợp này bao gồm số các cụm và

các tâm cụm cũng như ma trận thuộc được đóng gói trong PSO. Trong phần này, một

hàm mới để tìm số lượng cụm phù hợp nhất ở trạng thái hiện hành của các phương

án trong PSO cũng được đề xuất. Phân cụm mờ viễn cảnh và chỉ số ASWC được sử

dụng để đánh giá các kết quả của giải pháp. Do đó, thuật toán đề xuất cho số lượng

cụm phù hợp nhất trên tập dữ liệu. Kết quả thử nghiệm trên các tập dữ liệu chuẩn của

kho dữ liệu học máy UCI đã chỉ ra rằng, trong hầu hết các trường hợp, thuật toán

AFC-PFS, đặc biệt là thuật toán AFC-PFS với chỉ số đánh giá ASWC, không chỉ cho

số lượng trung bình các cụm gần thực tế nhất mà còn có tốc độ nhanh hơn các thuật

toán khác, đặc biệt là với tập dữ liệu có kích thước và quy mô dữ liệu lớn.

Thuật toán phân cụm mờ cho tập dữ liệu phức tạp (PFCA-CD) cho phép thực

hiện phân cụm dữ liệu cả số và kiểu loại với cấu trúc khác nhau. PFCA-CD là sự kết

hợp giữa tối ưu hóa bầy đàn và phân cụm mờ viễn cảnh mà trong đó có sự kết hợp

tương đương các tâm cụm và ma trận độ thuộc được đóng gói trong PSO. Ý tưởng

mới cho phép nhanh chóng tìm ra mỗi cụm khi mỗi tâm cụm có thể xử lý với dữ liệu

có cấu trúc phức tạp và hình dạng của dữ liệu không phải là hình cầu. Như vậy, quá

trình này tạo ra các giải pháp phù hợp nhất cho bài toán đặt ra. Kết quả thử nghiệm

trên các tập dữ liệu chuẩn của kho dữ liệu học máy UCI cho thấy chất lượng cụm

cũng tốt hơn các thuật toán phân cụm khác mà còn cho tốc độ nhanh hơn các thuật

toán khác.

Kết quả của chương này đã được công bố trong công trình CT3 và CT4:

[CT3]. Pham Huy Thong, Le Hoang Son (2016), “A novel automatic picture fuzzy

clustering method based on particle swarm optimization and picture composite

cardinality”, Knowledge-Based Systems 109, pp. 48-60. (SCI, 2018, IF=5.101,

Elservier).

[CT4]. Pham Huy Thong, Le Hoang Son (2016), “Picture fuzzy clustering for

complex data”, Engineering Applications of Artificial Intelligence 56, pp. 121-130.

(SCIE, 2018, IF=3.526, Elservier).

CHƯƠNG 4. ỨNG DỤNG CỦA THUẬT TOÁN

PHÂN CỤM MỜ VIỄN CẢNH

Trong chương này, luận án trình bày ứng dụng của thuật toán FC-PFS vào bài

toán dự báo thời tiết ngắn hạn dựa trên ảnh mây vệ tinh. Đầu vào của bài toán là chuỗi

ảnh mây vệ tinh ở tại cùng một địa điểm với các mốc thời gian liên tiếp nhau. Các

điểm ảnh sử dụng trong thuật toán được lấy trong không gian màu RGB. Đầu ra của

bài toán là ảnh dự báo tiếp theo của chuỗi ảnh đầu vào. Có hai phương pháp dự báo

được trình bày trong chương này như sau:

- Phương pháp PFC-STAR là sự kết hợp của thuật toán phân cụm mờ viễn

cảnh và hồi quy không thời gian. Phương pháp PFC-STAR đề xuất bao gồm

ba bước. Trước tiên, FC-PFS được sử dụng để phân vùng các mẫu thành

các cụm. Tiếp theo, tất cả các phần tử của các cụm này được gắn nhãn và

thực hiện biến đổi rời rạc (DFT) dựa trên bộ lọc được nhúng vào để làm rõ

các thang đo không dự đoán trước để làm tăng thời gian dự đoán. Cuối cùng,

thuật toán STAR được sử dụng để dự đoán hình ảnh đầu ra của bài toán dự

báo thời tiết ngắn hạn với hai bước xác định và trọng số huấn luyện. Quá

trình huấn luyện có thể điều chỉnh trọng số để thích ứng hơn với các kết quả

đầu ra. Kỹ thuật STAR được sử dụng hai lần trong phương pháp này với

mục đích làm tăng độ chính xác của kết quả.

- Phương pháp thứ hai được đặt tên là PFC-PFR tích hợp phân cụm mờ viễn

cảnh với luật mờ viễn cảnh. Đây là một phương pháp cho dự báo ngắn hạn

từ các diễn biến của dữ liệu trước đó. Kết hợp kỹ thuật này với FC-PFS có

thể dẫn đến độ chính xác dự đoán tốt hơn. Trong PFC-PFR, các luật mờ

được sử dụng cho bước dự đoán. Hơn nữa, để dự đoán hình ảnh đầu ra chính

xác hơn, các thông số cho chức năng giải mờ trong phương pháp này được

huấn luyên với thuật toán tối ưu hóa bầy đàn [28]. Các luật mờ viễn cảnh

sau đó được giải mời bởi các tham số thích hợp của hàm giải mờ để có được

kết quả dự đoán hình ảnh tốt hơn. Trong phương pháp này có hai phương

pháp nhỏ được áp dụng đó là một phương pháp sử dụng luật mờ tam giác

và phương pháp sử dụng luật mờ hình thang.

Để đánh giá phương thức đề xuất, chuỗi hình ảnh vệ tinh khu vực Đông Nam Á

[63] được sử dụng để đánh giá tính chính xác của các phương pháp dự báo. Các kết

quả của chương được công bố trong [CT5].

FC-PFS

Cụm các pixels

4.1. Phương pháp PFC-STAR

Ảnh đầu vào

DFT-filter

STAR

FC-PFS

Cụm các pixels

Ảnh đầu vào

DFT-filter

Ảnh trong không gian Fourier Dự đoán ảnh trong không gian Fourier

Ảnh trong không gian Fourier

Chuyển ảnh về không gian thường và loại bỏ nhiễu

FC-PFS

Cụm các pixels

Ảnh đầu vào

DFT-filter

…

Ảnh đầu ra Ảnh trong không gian Fourier

Hình 4.1. Thuật toán PFC-STAR

Hình 4.1 minh họa các bước chính của thuật toán PFC-STAR. Các chuỗi hình

ảnh đầu vào của thuật toán PFC-STAR trước tiên được xử lý bằng thuật toán FC-PFS

và biến đổi rời rạc Fourier (DFT). FC-PFS được sử dụng để chia tất cả các điểm ảnh

trong những hình ảnh này thành các cụm và đánh dấu chúng bằng các màu khác nhau.

DFT-Filter được sử dụng để loại bỏ các vùng không dự đoán được trong các hình ảnh

và thay thế chúng thành miền Fourier. Tiếp theo, sử dụng kỹ thuật STAR để dự đoán

kết quả hình ảnh từ tất cả ảnh trong miền Fourier và trong các cụm điểm ảnh. Điều

này nhằm mục đích tìm ra trọng số cho mỗi cụm điểm ảnh trong mỗi ảnh để xác định

hình ảnh dự đoán. Và cuối cùng, trước khi dẫn đến hình ảnh dự đoán cuối, một số

nhiễu sẽ được loại bỏ bằng phương pháp lọc Adaptive Median Filtering [3].

STAR

Ảnh Ảnh Ảnh Ảnh

STAR

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

Để nâng cao độ chính xác trong hình ảnh dự đoán, kỹ thuật STAR được sử dụng

hai lần để xác định và huấn luyện trọng số. − 2 ảnh đầu tiên được sử dụng như đầu

vào của STAR để tính toán trọng số. Ví dụ trong hình 4.2, giả sử có bốn hình ảnh

theo thứ tự. Hai hình ảnh đầu tiên được sử dụng để tính toán trọng số của các tâm

điểm ảnh của ảnh , và sau đó ảnh và được dùng để huấn luyện trọng số để có được các tâm điểm ảnh của ảnh . Do đó, các trọng số để dự đoán hình ảnh có thể được tính toán theo phương trình (4.1) như sau.

(, , ) ,

∑

∑ (, , − 1) = ∑ (4.1) (, , ) = ∑ ,, (, , ) ,, ∑

trong đó 2 + 1, 2 + 1 và tương ứng với tổng số hàng, cột và khung theo thứ tự, là các trọng số tương ứng và biểu thị trọng số được đặt trong tập dự đoán và ,,

cho cụm , = 0, … , , = 0, … , .

Biến đổi Fourier rời rạc (DFT) là biến đổi Fourier lấy mẫu và do đó nó không

chứa tất cả các tần số tạo thành một hình ảnh, nhưng chỉ có một tập hợp các mẫu đủ

lớn để mô tả đầy đủ miền không gian hình ảnh. Số các tần số tương ứng với số điểm

ảnh trong miền không gian ảnh, tức là các ảnh trong miền không gian và miền Fourier

có cùng kích thước. Đối với hình vuông kích thước × , DFT hai chiều được thể

hiện theo phương trình (4.2).

ℎ

(4.2) ∑ , (, , ) = ∑ (ℎ, , )

trong đó (ℎ, , ) là hình ảnh trong miền không gian vào thời gian và hệ số mũ là hàm

cơ sở tương ứng với mỗi điểm (, , ) trong không gian Fourier. DFT đảo ngược từ

không gian Fourier thành miền không gian được mô tả trong công thức (4.3).

(4.3) ∑ ∑ . (, , ) = (, , )

Hình ảnh dự đoán có thể bao gồm nhiễu và các điểm ảnh ngoài biên. Nhiễu

được loại bỏ bằng cách sử dụng phương pháp [3]. Phương pháp này thực hiện xử lý

không gian để giữ lại các chi tiết của ảnh và làm mịn các nhiễu. Lợi ích chính đối với

phương pháp tiếp cận thích nghi để lọc trung tính là các cửa sổ thích ứng của bộ lọc

không làm thay đổi cạnh hoặc các cấu trúc nhỏ trong ảnh. Thêm vào đó, một số điểm

()

ảnh tại đường biên được chuẩn hoá bằng phương trình (120).

()2 −

()

(4.4) (, , ) =

Các thành phần của phương trình này được tính từ mô hình FC-PFS.

Trước tiên, thuật toán PFC-STAR sử dụng FC-PFS thay vì các phương pháp

phân cụm mờ khác để các pixel được phân thành các cụm có chất lượng cụm cao,

giúp nâng cao kết quả của quá trình dự đoán. Thứ hai, thuật toán đề xuất bao gồm hai

quá trình kết hợp xác định và huấn luyện trọng số cho việc dự đoán hình ảnh, khi đó

thuật toán có thể cho kết quả dự đoán chính xác hơn. Các trọng số có thể được điều

chỉnh với ảnh huấn luyện, làm cho chúng phù hợp hơn với các hình tiếp theo.

Tuy nhiên, PFC-STAR vẫn có một số hạn chế. Đầu tiên, việc sử dụng kỹ thuật

STAR có thể dẫn đến kết quả đầu ra tốt theo kịch bản là thuật toán có thể cho kết quả

tốt với dữ liệu này nhưng không tốt cho tập dữ liệu khác. Thứ hai, PFC-STAR sử

dụng biến đổi DFT cho việc tiền xử lý dữ liệu và biến đổi ngược DFT để tạo đầu ra.

Thời gian thực thi các thủ tục này thường lớn. Cuối cùng, kỹ thuật STAR được sử

dụng hai lần để giải quyết các phương trình xác định và huấn luyện trọng số, và điều

này đặt thuật toán vào tình huống cần nhiều gian để thực thi.

4.2. Phương pháp PFC-PFR

Thuật toán đề xuất được mô tả trong hình 4.3. Các chuỗi hình ảnh đầu vào của

thuật toán PFC-PFR trước tiên được xử lý trước bằng việc tính toán các ma trận sai

khác của các pixel. Các ma trận này sau đó được xử lý bởi thuật toán FC-PFS để phân

vùng một cách phù hợp các cụm để tạo ra các luật mờ viễn cảnh. Các tham số cho

hàm giải mờ trong phương pháp này được huấn luyện bởi thuật toán tối ưu hóa bầy

đàn [28]. Các luật mờ viễn cảnh sau đó được giải mờ bởi các tham số thích hợp của

hàm giải mờ để có được kết quả dự đoán hình ảnh tốt hơn.

Ảnh đầu vào 1

Ảnh đầu vào 3

Ảnh đầu vào N - 2

Ảnh đầu vào 2

Ảnh đầu vào N - 1

Ảnh đầu vào N

…

Ma trận sai khác 1

Ma trận sai khác 2

Ma trận sai khác 3

Ma trận sai khác N -2

Ma trận sai khác N -1

…

Sinh luật mờ viễn cảnh từ các kết quả phân cụm Phân cụm ma trận sai khác sử dụng FC-PFS

Hình ảnh dự báo

Huấn luyện trọng số giải mờ sử dụng PSO để nâng cao độ chính xác kết quả đầu ra

Hình 4.3. Sơ đồ thuật toán PFC-PFR

4.2.1. Số mờ viễn cảnh tam giác

Hình 4.4. Số mờ viễn cảnh tam giác của tập mờ viễn cảnh A

Các luật mờ viễn cảnh được phát triển dựa trên luật mờ IF-THEN được đề xuất

bởi Zadeh [98]. Số mờ hình tam giác (TPFN) cho các luật mờ viễn cảnh được mô tả bởi năm số thực (, , , , ) thỏa mãn (′ ≤ ≤ ≤ ≤ ′) và hai hàm tam giác

như trong phương trình (4.5–4.6) và hình 4.4 như sau.

, ớ ≤ ≤

0, ượ ạ

, = (4.5) , ớ ≤ ≤

′ , ớ ′ ≤ ≤ , ớ ≤ ≤ ′

′ 1, ượ ạ

. (4.6) + =

Tích hợp (4.5–4.6) với (2.5) và biểu thị = + , các giá trị độ trung lập và

độ từ chối được tính trong phương trình (4.7–4.8).

− ,

(4.7) = (1 − (1 − − ))

(4.8) = 1 − ( + ) − (1 − ( + ))

() là giá trị giải mờ của TPFN (hình 4.4) và được tính trong phương trình

(4.9).

ℎ

′′ ∑

, () = (4.9)

trong đó ℎ ≥ 0, = 1, … ,5 là trọng số giải mờ của TPFN.

4.2.2. Số mờ viễn cảnh hình thang

Hình 4.5. Số mờ viễn cảnh hình thang của tập mờ viễn cảnh A

Ngoài số mờ tam viễn cảnh giác được trình bày ở trên, luận án cũng trình bày số

mờ viễn cảnh hình thang (TpPFN) cho luật mờ viễn cảnh. TpPFN được biểu diễn bởi sáu số thực (, , , , , ) với (′ ≤ ≤ ′ ≤ ≤ ≤ ′) và hai hàm hình thang

được thể hiện trong các phương trình (4.10–4.11) và hình 4.5 như sau.

′

, ớ ≤ ≤ ′

1, ớ ′ ≤ ≤ 0, ượ ạ

⎧ ⎪ , ớ ≤ ≤ , = (4.10)

⎨ ⎪ ⎩

′ ′′ , ớ ′ ≤ ≤ ′ , ớ ≤ ≤ ′

′ 0, ớ ′ ≤ ≤ 1, ượ ạ

⎧ ⎪ . + = (4.11)

⎨ ⎪ ⎩

Đặt = + kết hợp với phương trình (2.5), giá trị độ trung lập và độ từ chối

được tính như trong công thức (4.7–4.8).

DEF(A) là giá trị giải mờ của TpPFN A (hình 4.5 và công thức 4.12)

ℎ

ℎ′ℎℎ′ℎℎℎ′ ∑

. () = (4.12)

trong đó ℎ ≥ 0, = 1, … ,6, là trọng số giải mờ của TpPFN.

4.2.3. Chi tiết thuật toán

Sinh luật mờ Bước 3 Phân cụm dữ liệu Bước 2 Tiền xử lý Bước 1

Dự đoán ảnh đầu ra Bước 7 Huấn luyện tham số giải mờ Bước 6 Nội suy đầu ra Bước 4, 5

Hình 4.6. Các bước trong thuật toán PFC-PFR

Các luật mờ gần nhất liên quan đến quan sát đầu vào được sử dụng để đưa ra

kết luận nội suy cho các hệ thống dựa trên luật mờ thưa. Sơ đồ nội suy luật mờ sau

đây minh họa rằng:

Luật 1: nếu = , và = ,, … = , thì =

Luật 2: nếu = , và = ,, … = , thì =

....

Luật q: nếu = , và = ,, …. = , thì =

∗ và =

∗ ∗ , … =

Quan sát: =

Kết luận: y =∗

trong đó luật là luật mờ j trong cơ sở luật mờ, biểu diễn biến tiền đề , là biến kết luận, , biểu diễn tập mờ tiền đề của luật , biểu diễn tập mờ hệ quả của ∗ biểu diễn quan sát thứ cho biến tiền đề , ∗chỉ ra các hệ quả nội suy luật , của tập mờ, là số lượng các biến xuất hiện trong tiền đề luật mờ, là số luật mờ

= 1, . . , và = 1, . . , .

Giả sử ta có một tập dữ liệu với chuỗi thời gian làm đầu vào {(), (), . . . , ()}, và một chuỗi thời gian đầu ra (), = 0, . . , . Phương pháp PFC-PFR đề xuất có thể được mô tả như trong hình 4.6.

Các bước của thuật toán PFC-PFR được mô tả chi tiết dưới đây

Bước 1: mỗi phần tử trong ma trận sai khác được tính theo công thức (4.13) dựa trên tỷ lệ khác nhau (), = 1, . . , của chuỗi thời gian thứ của chuỗi đầu vào () tại thời điểm , trong đó = 1, . . ,

()() ()

× 100%. (4.13) () =

Các tỷ thời gian vào lệ khác {(), (), . . . , ()} của chuỗi

luyện {, , . . . , },

(), . . . ,

(),

{(), (), . . . , ()}, = 0, . . , tại thời điểm được xác định dựa trên (4.13). N trong đó được biểu diễn bởi mẫu huấn {(), (), . . . , (), ()}, = 1, . . , được xây dựng lại. Biểu diễn = () () là đầu vào (), = {(), (), . . . , (), ()}, trong đó

(đầu ra) thứ của , = 1, . . , .

Bước 2: Thuật toán FC-PFS được sử dụng để phân vùng mẫu huấn luyên vào một cụm tương ứng () {, , . . . , }. Tâm của cụm , độ thuộc , độ trung

lập và độ từ chối của , = 1, . . , , = 1, . . , .

Bước 3: Các luật mờ viễn cảnh sử dụng TPFN (TpPFN) được tạo ra dựa trên

các cụm{, , . . . , }, trong đó, luật tương ứng , được trình bày như sau:

Luật j: nếu = , và = , và ... và = , thì =

Trong đó luật là luật mờ tương ứng với cụm , là biến tiền đề thứ , ,

là tập mờ tiền đề thứ của luật , là biến hệ quả, là tập mờ hệ quả thứ của luật , = 1, . . , , = 1, . . , , và một bộ số thực (, , , , ) của TPFN , hay

, bên cạnh độ thuộc, thì độ trung (, , , , , ) của TpPFN , với =

lập và độ từ chối cũng đóng một vai trò quan trọng trong việc xác định các điểm ranh

giới phù hợp đại diện cho các luật. Giá trị tốt nhất cho thấy một miền lớn các khả

năng + và một miền nhỏ độ từ chối 1 + . Điều này có nghĩa là một điểm

“tốt” không chỉ có độ thuộc và độ trung lập cao mà còn không đạt được độ từ chối dù

là nhỏ. Do đó, FC-PFS cho ta thêm thông tin và định hướng PFR để chọn các điểm

thích hợp hơn nhằm tạo ra các luật tốt hơn so với các thuật toán phân cụm khác như

FCM. Ở bước này, có hai tùy chọn với số mờ viễn cảnh tam giác và số mờ viễn cảnh

hình thang như sau:

a. Sử dụng số mờ viễn cảnh tam giác:

Các giá trị (, , , , ) của TPFN , được tính theo công thức (4.14–4.18).

(),

′ = ,,..., ,

(4.14)

(),

′ = ,,..., ,

(4.15)

(), với , =

()

∑

() ,,...,

(4.16) (), , =

∑

() ,,...,

()

∑

() ,,...,

(4.17) , , =

∑

() ,,...,

() là đầu vào thứ của mẫu huấn luyện , = 1, . . , , = 1, . . , . Số

(4.18) . , =

trong đó thực (, , , , ) của TPFN của luật j được mô tả trong (4.19–4.23).

′ = ,,..., ,

(4.19)

′ = ,,..., , ,

(4.20)

∑

() ,,..., à

, (4.21) = , với , =

∑

,,..., à

()

∑

() ,,..., à

, (4.22) =

∑

,,..., à

()

. (4.23) =

trong đó là đầu ra mong muốn của và = 1, . . , . Dựa trên các phương trình (4.14–4.23), TPFN của các luật mờ được xây dựng.

b. Sử dụng số mờ viễn cảnh hình thang:

Các số thực (′, , ′, , , ′) của TpPFN , được tính trong công thức (4.24–

4.29) với =

(),

′ = ,,..., ,

(4.24)

(),

′ = ,,..., ,

()

(4.25)

′ = ,

(),

() là tâm của cụm

(), với =

(4.26)

(),

()

∑

′ ,

() ,,..., à

, = (), (4.27) với thành phần thứ .

∑

′ ,

() ,,..., à

()

∑

() ,,..., à

(4.28) , , =

∑

() ,,..., à

() là đầu vào thứ của mẫu huấn luyện , = 1, … , , = 1, … , . Các trong đó số thực (, , , , , ) của TpPFN của luật j được mô tả trong các công thức (4.30–4.35).

(4.29) . , =

′ = ,,..., ,

(4.30)

′ = ,,..., ,

(),

(4.31)

′ =

(),

() là tâm cụm với

(), với =

(4.32)

(),

∑

′

() ,,..., à

= (), (4.33) thành phần thứ .

∑

,,..., à

′

()

∑

() ,,..., à

, (4.34) =

∑

,,..., à

()

. (4.35) =

trong đó là đầu ra mong muốn của và = 1, … , . Dựa theo các công thức (4.24– 4.35), TpPFN của các luật mờ viễn cảnh được tạo ra.

∗ theo công thức (4.36)

() > 0, thì tính đầu ra

Bước 4: Nếu một số luật mờ viễn cảnh được kích hoạt bởi các đầu vào thứ của

()

∑ ,

× ,

mẫu có nghĩa là , và di chuyển đến bước 6. Nếu không chuyển qua bước 5.

∗ =

()

∑ ,

() thuộc tập mờ tam giác viễn

() biểu thị là giá trị độ thuộc của đầu vào

(4.36)

cảnh ,, = 1, . . , và = 1, . . , . Nó được tính toán dựa trên hàm mờ viễn cảnh

tam giác với biểu diễn số lượng các luật mờ viễn cảnh được kích hoạt và

là giá trị giải mờ của tập mờ viễn cảnh kết quả của luật mờ viễn cảnh , = 1, . . , ,

= 1, . . , .

,..., =

Bước 5: Nếu không tồn tại bất kỳ luật mờ viễn cảnh đang hoạt động nào, tính theo trọng số của của luật với các quan sát đầu vào =

(), . . . ,

(),

, = ∗ theo phương trình (4.38). ∗là vector đầu (), là vector của các giá trị giải mờ của tập luật mờ - vào ,, ,, . . . , ,. ∗ − là khoảng cách Euclide giữa các

phương trình (4.37) và tính toán đầu ra

vectơ ∗ và . Các ràng buộc của các trọng số là: 0 ≤ ≤ 1, = 1, . . , và

∑ = 1 . là giá trị giải mờ của tập mờ viễn cảnh hệ quả .

1 (4.37) =

ℎ

∑ ∗ − ‖∗ − ℎ‖

∗ = ∑ × ,

(4.38)

Bước 6: Để có được dự đoán hình ảnh tốt, thuật toán PSO được sử dụng để xác

định các tham số thích hợp cho hàm giải mờ. Theo công thức (4.9) cho TPFN hoặc

(4.12) cho TpPFN, thuật toán sẽ huấn luyện các tham số trong công thức này. Quá

trình huấn luyện tham số giải mờ sử dụng hai ma trận sai khác ( − 1) và ( − 2)

với vai trò kiểm tra mẫu thử và mẫu đầu vào (). Thuật toán PSO [28] được sử dụng

để tối ưu hóa các tham số này.

Giả sử dữ liệu có phương án, mỗi phương án được mã hóa với các

trọng số tương ứng với trọng số để tính toán giá trị giải mờ cho TPFN hoặc TpPFN.

(), = 1, … ,6). Tham số

Nếu phương án nhận được giải pháp tốt hơn các phương án trước đó, nó sẽ được () là ghi lại thành tối ưu cục bộ địa phương -(

vận tốc thay đổi các tham số của phương án , = 1, … ,6. Tiến trình tối ưu hóa sẽ

tiếp tục với tất cả các phương án cho đến khi hoàn thành tất cả các vòng lặp. Giải

pháp cuối cùng phù hợp nhất của năm tham số nhận được từ tất cả các phương án

thông qua các giá trị tốt nhất của các phương án () và toàn cục (). chứa (tham số cho giá trị giải mờ để các luật có độ chính xác cao nhất) và giá

trị , giá trị chất lượng tốt nhất mà tất cả các phương án đạt được - giá trị fitness.

Hàm fitness được tính bằng công thức (4.39) như là sự khác biệt giữa các ma trận

tương tự từ các tham số và ma trận pixel thứ ( − 1).

() ,

() −

() là giá trị

() là giá trị pixel thứ của ma trận pixel ( − 1); trong đó pixel thứ của ma trận pixel mới được tạo ra từ các tham số . Mỗi phương án

(4.39) = ∑

được cập nhật theo phương trình (4.40–4.41) như dưới đây.

(),

() +

() =

() −

() + −

(),

(4.40)

() =

() +

(4.41)

trong đó , ≥ 0 là các tham số của PSO. Nói chung, các giá , này thường được thiết lập là 1. Chi tiết của phương pháp này được mô tả trong bảng 4.1.

Bảng 4.1. Thuật toán huấn luyện tham số dựa trên PSO

I: Dữ liệu ; ngưỡng , số vòng lặp tối đa maxSteps, số phương án trong PSO-

O: Các tham số tối ưu (, , , , , ) của hàm giải mờ.

Thuật toán

() ← , ℎ

1: = 0 ( = ← , = 0,

1, . . , ), t = 0

Repeat 2:

t = t + 1 3:

4: For each phương án

Tính ma trận sai khác nội suy bằng công thức (4.36) hay (4.38) 5:

6: Tính giá trị cho phương án theo công thức (4.39)

7: If (< or =0)

8: =

9: Lưu phương án tốt nhất là phương án

10: If ( < or =0)

11: =

Lưu phương án tốt nhất toàn cục là phương án i 12:

13: Cập nhật phương án bằng công thức (4.40–4.41)

14: Until ( > or t > maxSteps)

Bước 7: Cuối cùng, giá trị dự báo ()tại thời gian được tính toán ∗, trong đó ( − 1) là giá trị thực tế tại thời điểm − 1

∗).

dựa trên tỷ lệ biến đổi trong phương trình (4.42).

(4.42) () = ( − 1) × (1 +

Phương pháp PFC-PFR có một số lợi thế. Đầu tiên, PFC-PFR sử dụng FC-PFS

để phân vùng các pixel khác nhau trong hình ảnh giúp quy trình làm việc chính xác

hơn. Thứ hai, việc sử dụng các luật mờ viễn cảnh nội suy có thể giúp các thuật toán

tránh được kết quả quá khớp hoặc không chính xác. Cuối cùng, các phương pháp đề

xuất sử dụng huấn luyện tham số giải mờ với thuật toán PSO để cải thiện độ chính

xác dự đoán của các hình ảnh đầu ra. Phương pháp cho kết quả dự đoán hình ảnh

chính xác hơn so STAR. Tuy nhiên, thuật toán đề xuất như PFC-STAR có thời gian

tính toán cao vì tiến trình huấn luyện sử dụng PSO.

4.3. Kết quả thực nghiệm

Các thuật toán đã được cài đặt trong thực nghiệm sau:

 Các phương pháp PFC- STAR, PFC-PFR áp dụng luật mờ viễn cảnh tam giác

và PFC-PFR áp dụng luật mờ viễn cảnh hình thang.

 PFC-STAR* và PFC-PFR*: các phương pháp PFC-STAR và PFC-PFR mà

không cần huấn luyện.

 FCM-STAR là phương pháp Shukla, Kishtawal & Pal (2014).

 FCM-FR: kết hợp fuzzy C-Means (FCM) và luật mờ thường (FR). Ở đây,

FCM được sử dụng kết hợp với luật mờ thường [98] FR thay cho PFR để đánh

giá hiệu suất của thuật toán này so với những thuật toán khác.

 Phương pháp suy diễn mờ (FIR) trong [69].

 ANN trong [45].

Kết quả thử nghiệm được lấy trung bình sau 50 lần chạy. Tính chính xác của dự

đoán được đo bằng chỉ số Root Mean Squared Error (RMSE) như trong công thức

()()

(4.43).

(4.43) , = ∑

trong đó () và () biểu diễn các giá trị pixel ảnh thật và pixel

của ảnh dự đoán tại thời điểm trong tổng số điểm ảnh.

Bảng 4.2. So sánh giá trị RMSE của các thuật toán

Data PFC-PFR* FCM-FR

Ảnh dự Ảnh dự Ảnh dự Ảnh dự Ảnh dự Ảnh dự

báo 1 báo 2 báo 3 báo 1 báo 2 báo 3

Data 1 4.303 7.245 8.198 4.371 7.72 8.879

Data 2 6.225 11.325 14.391 6.497 10.278 11.995

Data 3 6.826 9.854 10.509 7.551 10.985 12.071

PFC-STAR* FCM-STAR

Data 1 6.893 7.738 9.646 8.661 8.865 9.828

Data 2 8.704 10.324 12.422 11.158 11.809 12.546

Data 3 9.549 10.42 11.309 12.955 13.209 13.772

FIR ANN

Data 1 4.789 26.395 19.323 5.001 9.453 11.488

Data 2 4.669 26.335 19.412 7.793 11.309 14.35

Data 3 4.967 26.172 19.426 8.892 10.995 15.469

PFC-PFR PFC-STAR

Data 1 4.13 6.557 7.021 4.428 5.331 5.453

Data 2 5.154 9.521 11.642 5.422 9.883 11.072

Data 3 6.088 8.601 9.193 5.985 10.018 11.274

PFC-PFR+

Data 1 4.141 6.749 9.619

Data 2 6.33 11.418 12.482

Data 3 6.314 9.995 10.468

Giá trị RMSE của các thuật toán mà giá trị in đậm bao hàm các thuật toán tốt

nhất cho một dữ liệu cụ thể và hình ảnh dự đoán được trình bày trong bảng 4.2. Ví

100

dụ, với dữ liệu 1 và hình ảnh dự đoán 1, RMSE giá trị của PFC-PFR*, FCM-FR,

PFC-STAR*,FCM-STAR, FIR, ANN, PFC-PFR và PFC-STAR là 4.303, 4.371,

6.893, 8.661, 4.789, 5.001, 4.13 và 4.428, tương ứng. Rõ ràng là giá trị RMSE của

PFC-PFR là nhỏ nhất trong số tất cả để giá trị được đánh dấu là đậm trong bảng.

Tương tự, thực nghiệm thực hiện kết hợp với các dữ liệu và hình ảnh dự đoán khác

và nhận được kết quả trong bảng 4.2. Có một số nhận xét như sau:

Thứ nhất, theo số lượng các giá trị in đậm trong bảng, có thể được nhận ra rằng

hai phương pháp đề xuất (PFC-PFR và PFC- STAR) có những lợi thế đáng kể so với

những thuật toán khác bao gồm các thuật toán mới mà không sử dụng phương pháp

huấn luyện (PFC-PFR*, PFC- STAR*), một thuật toán lai giữa một thuật toán phân

cụm hiện có và thành phần đề xuất (FCM -FR) cùng với ba thuật toán có tương tự

(FCM-STAR, FIR và ANN). PB-PFR cho kết quả tốt hơn một chút so với PFC-STAR

với số lượng các giá trị đậm là 4 so với 3 của PFC-STAR.

Thứ hai, các phương pháp đề xuất không cho kết quả tốt nhất cho hình ảnh dự

đoán đầu tiên. Các giá trị trung bình của PFC-PFR và PFC-STAR bởi tất cả dữ liệu

cho hình ảnh dự đoán 1 tương ứng là 5.124 và 5.278, trong khi những thuật toán khác

như FC-PFR*, PFC-STAR*, FCM-FR, FCM-STAR, FIR và ANN có giá trị tương

ứng là 5.785, 8.382, 6.139, 10.92, 4.808, 7.228. Giá trị tốt nhất trong trường hợp này

là của FIR. Tuy nhiên, PFC-PFR và PFC-STAR cũng có các giá trị RMSE nhỏ và tốt

hơn các thuật toán còn lại.

Thứ ba, các phương pháp được đề xuất là hiệu quả cho các hình ảnh dự đoán 2

và 3. Trong hình ảnh dự đoán 2, các giá trị trung bình của các thuật toán đề xuất (PFC-

PFR và PFC-STAR), các biến thể mà không cần huấn luyện (PFC-PFR* và PFC-

STAR*), thuật toán lai FCM-FR và ba thuật toán tương tự (FCM-STAR, FIR và

ANN) là (8.226, 8.41), (9.474, 9.494, 9.661), và (11.12 11.03 13.769), theo thứ tự.

PFC-PFR là phương pháp tốt nhất trong trường hợp này. Tương tự, trong hình ảnh

dự đoán 3, các giá trị trung bình của các phương pháp được đề xuất (PFC-PFR và

PFC- STAR), các biến thể mà không cần huấn luyện (PFC-PFR* và PFC-STAR*),

thuật toán lai FCM-FR và ba thuật toán tương tự (FCM-STAR, FIR và ANN) là

(9.285, 9,266, 10.98) và (12.04, 19.38, 13.769). PFC- STAR là phương pháp có kết

quả tốt nhất trong trường hợp này. Nó đã cho thấy rằng các phương pháp đề xuất có

101

khả năng duy trì độ chính xác cao của hình ảnh dự đoán trong khoảng thời gian dự

báo. Điều này là quan trọng bởi vì khoảng thời gian dự báo lớn hơn có thể cho hiệu

suất và độ chính xác không như mong muốn. Những thay đổi của giá trị RMSE giữa

một số hình ảnh dự đoán của các phương pháp được đề xuất là không lớn so với

E S M R

Data 3

Data 2

ị r t á G

Data 1

35 30 25 20 15 10 5 0

những thuật toán khác.

E S M R

Data 3

Data 2

ị r t á G

Data 1

90 80 70 60 50 40 30 20 10 0

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

E S M R

Data 3

Data 2

ị r t á G

Data 1

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

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

Bảng 4.3. So sánh giá trị RMSE của các thuật toán

Data PFC-PFR*

FCM-FR

Ảnh dự

báo 1

báo 2

báo 3

báo 1

báo 2

báo 3

Data 1

1.041

1.359

1.503

1.058

1.448

1.628

Data 2

1.333

1.189

1.300

1.392

1.080

1.083

Data 3

1.374

1.146

1.143

1.520

1.277

1.313

PFC-STAR*

FCM-STAR

Data 1

1.669

1.452

1.769

2.097

1.663

1.802

Data 2

2.390

1.240

1.864

1.084

1.122

1.133

Data 3

2.608

1535.752

1.498

1.922

1.211

1.230

FIR

ANN

Data 1

1.160

4.951

3.544

1.773

1.211

2.107

Data 2

1.000

2.766

1.753

1.188

1.669

1.296

Data 3

1.000

3.043

2.113

1.278

1.790

1.683

PFC-PFR

PFC-STAR

Data 1

1.000

1.230

1.288

1.000

1.072

1.000

Data 2

1.104

1.000

1.051

1.038

1.161

1.000

Data 3

1.226

1.000

1.165

1.205

1.226

PFC-PFR+

Data 1

1.003

1.266

1.764

Data 2

1.355

1.199

1.127

Data 3

1.271

1.162

1.139

Thứ tư, hình 4.7 – 4.9 minh họa tổng giá trị RMSE của các thuật toán bằng tất

cả dữ liệu trong hình ảnh được dự đoán 1, 2 và 3, tương ứng. Tổng giá trị được tính

bằng tổng các giá trị RMSE của tất cả dữ liệu cho một hình ảnh dự đoán. Các con số

cũng khẳng định rằng các phương pháp được đề xuất là tốt hơn so với những phương

pháp khác có liên quan (FCM-STAR, FIR à ANN). Hơn nữa, các phương pháp huấn luyện trong PFC-PFR và PFC-STAR là khá quan trọng vì chúng làm giảm đáng kể

103

các giá trị RMSE khi so sánh giữa các phương pháp được đề xuất (PFC-PFR và PFC-

STAR), các biến thể mà không cần huấn luyên (PFC-PFR* và PFC-STAR*). Sự kết

hợp giữa các phương pháp được đề xuất cũng tốt hơn so với sự kết hợp của một thuật

toán cụm mờ FCM và phương pháp luật mờ (PFR). Điều này cho thấy vai trò của

thuật toán phân cụm mờ viễn cảnh (PFC) nhằm nâng cao tính chính xác của dự báo.

Bảng 4.4. STD của giá trị RMSE của các thuật toán

Data PFC-PFR*

FCM-FR

Ảnh dự

Ảnh dự báo

báo 1

báo 2

báo 3

báo 1

báo 2

0.104

0.627

1.347

Data 1

0.143

0.721

1.471

0.425

0.805

2.441

Data 2

0.479

0.799

2.345

0.413

0.752

2.311

Data 3

0.451

0.785

2.67

PFC-STAR*

FCM-STAR

0.103

0.634

1.241

Data 1

0.11

0.651

1.113

0.612

0.731

2.451

Data 2

0.662

0.701

2.703

0.426

0.702

2.234

Data 3

0.568

0.893

2.523

FIR

ANN

0.000

Data 1

0.036

0.176

0.569

0.000

Data 2

0.167

0.361

0.685

0.000

Data 3

0.017

0.248

0.305

PFC-PFR

PFC-STAR

0.04

0.467

0.716

Data 1

0.101

0.599

1.428

0.083

0.425

0.757

Data 2

0.741

0.831

2.551

0.168

0.699

0.724

Data 3

0.532

0.702

2.234

PFC-PFR+

0.076

0.424

0.479

Data 1

0.505

0.458

0.468

Data 2

1.013

3.463

1.911

Data 3

104

Bảng 4.3 là minh chứng so sánh các giá trị RMSE giữa các thuật toán bằng cách

đánh dấu các giá trị đậm trong bảng 4.2 là 1 và tính toán bao nhiêu lần giá trị khác

trong cùng một dữ liệu và hình ảnh dự đoán lớn hơn các giá trị in đậm này. Các lần

được viết xuống trong bảng 4.3 để hiển thị rõ ràng tỷ lệ giữa các thuật toán. Bảng 4.4

biểu thị giá trị tiêu chuẩn (STD) cho giá trị RMSE của các thuật toán trong bảng 4.2.

l

Predicted Image 1

Predicted Image 2

s e u a v E S M R

Predicted Image 3

9 10 11 12 13 14 15 16

Số cụm

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

l

Predicted Image 1

Predicted Image 2

s e u a v E S M R

Predicted Image 3

9 10 11 12 13 14 15 16

Số cụm

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

l

Predicted Image 1

Predicted Image 2

s e u a v E S M R

Predicted Image 3

9 10 11 12 13 14 15 16

Number of clusters

Hình 4.12. Giá trị RMSE của thuật toán PFC-PFR với các cụm khác nhau

11.30

12.30

13.30

11.30

12.30

13.30

của dữ liệu 3

11.30

12.30

13.30

11.30

12.30

13.30

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)

11.30

12.30

13.30

11.30

12.30

13.30

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)

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

Trong hình 4.10 – 4.12, các giá trị RMSE được minh họa với thanh sai số của

thuật toán PFC-PFR bằng các số khác nhau của cụm dữ liệu 1, 2 và 3, tương ứng.

Điều này cho thấy sự ổn định của thuật toán trong các trường hợp khác nhau của các

tham số. Cuối cùng, hình 4.13 – 4.15 hiển thị các kết quả minh họa của ba hình ảnh

dự báo cuối cùng (11h30, 12h30 và 13h30).

4.4. Kết luận chương

Trong chương này, hai phương pháp dự báo lai mới dựa trên ảnh mây vệ tinh

cho bài toán dự báo thời tiết ngắn hạn được đề xuất. Phương pháp đầu tiên được đặt

tên là PFC-STAR là sự kết hợp của phân cụm mờ viễn cảnh và mô hình hồi quy

không thời gian STAR. Phương pháp thứ hai là PFC-PFR tích hợp phân cụm mờ viễn

cảnh và quy tắc sinh luật mờ với hai biến thể là luật mờ viễn cảnh tam giác và luật

mờ viễn cảnh hình thang. Cả hai thuật toán này đều sử dụng thêm thuật toán huấn

luyện để nâng cao độ chính xác dự báo. Đánh giá thử nghiệm trên các chuỗi hình ảnh

vệ tinh cho thấy các phương pháp đề xuất cho chất lượng tốt hơn so với những người

có liên quan.

Nội dung của chương này đã được công bố trong công trình CT5:

[CT5]. Le Hoang Son, Pham Huy Thong (2017), “Some novel hybrid forecast

methods based on picture fuzzy clustering for weather nowcasting from satellite

image sequences”, Applied Intelligence 46(1), pp. 1-15. (SCIE, 2018, IF= 2.882,

Springer).

107

KẾT LUẬN

Với mục tiêu nghiên cứu một số phương pháp phân cụm mờ mới trên tập mờ

viễn cảnh, luận án đã đạt được một số kết quả như sau:

- Đề xuất thuật toán FC-PFS là một thuật toán phân cụm mờ viễn cảnh mới. Tính chất hội tụ của thuật toán được khảo sát và chứng minh về lý thuyết.

Đồng thời, thực nghiệm kiểm chứng trên bộ dữ liệu chuẩn UCI, thuật toán

cũng đạt hiệu quả hơn so với các thuật toán liên quan. Những nghiên cứu chi tiết về thuật toán mới này đã được công bố trên hai công trình [CT1, CT2].

- Đề xuất thuật toán AFC-PFS, trên cơ sở cải tiến thuật toán phân cụm trên tập mờ viễn cảnh cho bài toán phân cụm mờ tự động xác định số cụm. Đây

là một thuật toán mới lai ghép giữa thuật toán phân cụm mờ viễn cảnh và

thuật toán tối ưu bầy đàn PSO. Thực nghiệm kiểm chứng cho thây thuật toán

cho kết quả tốt hơn các thuật toán khác liên quan. Kết quả nghiên cứu này được công bố trong [CT3].

- Đề xuất thuật toán PFCA-CD, trên cơ sở cải tiến thuật toán phân cụm trên tập mờ viễn cảnh nhằm xử lý các dữ liệu phức tạp. Đây là một thuật toán

mới được đề xuất để phân cụm mờ dữ liệu gồm cả dữ liệu kiểu loại và dữ

liệu số. Đồng thời thuật toán cũng có thể xử lý với các dữ liệu có cấu trúc

phức tạp mà các thuật toán phân cụm mờ thông thường tỏ ra không hiệu quả.

Các kết quả thực nghiệm đã chỉ ra những ưu điểm của thuật toán này so với các thuật toán liên quan. Nghiên cứu này được công bố trong [CT4].

- Ứng dụng thuật toán phân cụm mờ viễn cảnh FC-PFS 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. Ở đây luận án đã đưa ra hai

phương pháp kết hợp thuật toán phân cụm mờ viễn cảnh với thuật toán hồi

quy không thời gian STAR và kết hợp với luật mờ viễn cảnh. Luật mờ viễn

cảnh là một luật mờ mới được trình bày trong luận án được sinh ra bằng các

kết quả của phân cụm mờ viễn cảnh, dựa trên các số mờ tam giác và hình

thang để tính toán suy luận ra kết quả đầu ra dự báo. Các thực nghiệm trên

các ảnh mây vệ tinh cho thấy tính hiệu quả của phương pháp này. Kết quả nghiên cứu được công bố tại [CT5].

108

Bên cạnh các kết quả nghiên cứu đã đạt được, các nghiên cứu trong luận án vẫn

còn tồn tại một số hạn chế như:

- Thuật toán phân cụm mờ viễn cảnh có nhiều tham số trong quá trình tính toán, do đó cần tài nguyên bộ nhớ rất lớn, đặc biệt là khi tính toán với bộ dữ liệu lớn.

- Thuật toán phân cụm mờ viễn cảnh là thuật toán lặp nên cần khá nhiều thời gian để tính toán. Do các giá trị đầu vào ban đầu được khởi tạo bởi các giá

trị ngẫu nhiên nên số vòng lặp của thuật toán sẽ phụ thuộc nhiều vào độ tốt

của dữ liệu ban đầu. Hơn nữa, các cải tiến của thuật toán này đều có sự kết

hợp với thuật toán tối ưu bầy đàn PSO dẫn đến thuật toán sẽ cần rất nhiều tài nguyên tính toán.

- Trong bài toán dự báo thời tiết ngắn hạn, luận án mới chỉ đưa ra cách tiếp cận dựa trên ảnh mây về tinh mà chưa xem xét đến các yếu tố khác của thời

tiết như nhiệt độ, áp suất, tốc độ gió, độ ẩm, v.v. dẫn đến các kết quả dự báo chưa thực sự mang tính thực tiễn.

Hướng phát triển tiếp theo của các nghiên cứu trong luận án này sẽ tập trung

vào một số điểm sau:

- Cải tiến các thuật toán đã có để giảm thiểu tài nguyên bộ nhớ sử dụng, đồng thời tăng tốc độ tính toán như áp dụng tính toán trên các mô hình song song, các mô hình tính toán phân tán để đạt được hiệu quả cao nhất.

- Kết hợp thêm các yếu tố về thời tiết như nhiệt độ, độ ẩm, hướng gió, v.v. cho bài toán dự báo thời tiết ngắn hạn để có được dự báo chính xác, gần với

thực tiễn hơn.

109

DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ

ĐÃ CÔNG BỐ

[CT1]. Pham Huy Thong, Le Hoang Son (2016), “Picture fuzzy clustering: a

new computational intelligence method”, Soft Computing 20(9), pp. 3549-

3562. (SCIE, 2018 IF= 2.784, Springer).

[CT2]. Pham Thi Minh Phuong, Pham Huy Thong, Le Hoang Son (2018),

“Theoretical analysis of picture fuzzy clustering: Convergence and property”,

Journal of Computer Science and Cybernetics 34(1), pp. 17-32.

[CT3]. Pham Huy Thong, Le Hoang Son (2016), “A novel automatic picture

fuzzy clustering method based on particle swarm optimization and picture

composite cardinality”, Knowledge-Based Systems 109, pp. 48-60. (SCI, 2018

IF=5.101, Elsevier).

[CT4]. Pham Huy Thong, Le Hoang Son (2016), “Picture fuzzy clustering for

complex data”, Engineering Applications of Artificial Intelligence 56, pp. 121-

130. (SCIE, 2018 IF=3.526, Elsevier).

[CT5]. Le Hoang Son, Pham Huy Thong (2017), “Some novel hybrid forecast

methods based on picture fuzzy clustering for weather nowcasting from

satellite image sequences”, Applied Intelligence 46(1), pp. 1-15. (SCIE, 2018

IF= 2.882, Springer).

110

TÀI LIỆU THAM KHẢO

[1]. Abdullah, M., Al-Anzi, F., & Al-Sharhan, S. (2018, March), “Hybrid

Multistage Fuzzy Clustering System for Medical Data Classification”, In 2018

International Conference on Computing Sciences and Engineering (ICCSE),

1-6.

[2]. Agrawal, D., & Pandey, S. (2018), “FUCA: Fuzzy‐based unequal clustering

algorithm to prolong the lifetime of wireless sensor networks”, International

Journal of Communication Systems 31(2), e3448.

[3]. Al-amri, S. S., Kalyankar, N. V., & Khamitkar, S. D. (2010), “A comparative

study of removal noise from remote sensing image”, arXiv preprint

arXiv:1002.1148.

[4]. Aliahmadipour, L. T. (2017), “On hesitant fuzzy clustering and clustering of

hesitant fuzzy data”, Fuzzy sets, rough sets, multisets and clustering, 157-168.

[5]. Alp Erilli, N., Yolcu, U., Eğrioğlu, E., Hakan Aladağ, Ç., & Öner, Y. (2011),

“Determining the most proper number of cluster in fuzzy clustering by using

artificial neural networks”, Expert Systems with Applications 38(3), 2248-2252.

[6]. Amiri, E., & Dehkordi, M. N. (2018), “Dynamic data clustering by combining

improved discrete artificial bee colony algorithm with fuzzy logic”,

International Journal of Bio-Inspired Computation 12(3), 164-172.

[7]. Amirkhani, A., Mosavi, M. R., Mohammadi, K., & Papageorgiou, E. I. (2018),

“A novel hybrid method based on fuzzy cognitive maps and fuzzy clustering

algorithms for grading celiac disease”, Neural Computing and Applications

30(5), 1573-1588.

[8]. Arima, C., Hakamada, K., Okamoto, M., & Hanai, T. (2008), “Modified Fuzzy

Gap statistic for estimating preferable number of clusters in Fuzzy k-means

clustering”, Journal of bioscience and bioengineering 105(3), 273-281.

[9]. Arora, J., Khatter, K., & Tushir, M. (2019), “Fuzzy c-means clustering

strategies: A review of distance measures”, In Software Engineering, 153-162.

[10]. Atanassov, K. (1986), “Intuitionistic fuzzy sets”, Fuzzy Sets and Systems 20,

87–96.

111

[11]. Bai, L., Liang, J., & Dang, C. (2011), “An initialization method to

simultaneously find initial cluster centers and the number of clusters for

clustering categorical data”, Knowledge-Based Systems 24(6), 785-795.

[12]. Bezdek, J. E. (1984), “FCM: The fuzzy c-means clustering algorithm”,

Computers & Geosciences 10(2), 191-203.

[13]. Burillo, P., Bustince, H. (1996), “Entropy on intuitionistic fuzzy set and on

interval-valued fuzzy set”, Fuzzy Sets and Systems 78, 305–316.

[14]. Butkiewicz, B.S. (2012), "Fuzzy clustering of intuitionistic fuzzy data", In

International Conference on Artificial Intelligence and Soft Computing, 213-220.

[15]. Chaira, T. (2011), “A novel intuitionistic fuzzy C means clustering algorithm and

its application to medical images”, Applied Soft Computing 11(2), 1711-1717.

[16]. Chaira, T. P. (2013), “An Atanassov's intuitionistic Fuzzy Kernel Clustering

for Medical Image segmentation”, International Journal of Computational

Intelligence Systems, 1-11.

[17]. Chen, L., Wang, S., Wang, K., & Zhu, J. (2016), “Soft subspace clustering of

categorical data with probabilistic distance”, Pattern Recognition 51, 322-332.

[18]. Cheung, Y. M., & Jia, H. (2013), “Categorical-and-numerical-attribute data

clustering based on a unified similarity metric without knowing cluster

number”, Pattern Recognition 46(8), 2228-2238.

[19]. Chowdhary, C. L., & Acharjya, D. P. (2018), “Segmentation of mammograms

using a novel intuitionistic possibilistic fuzzy c-mean clustering algorithm”, In

Nature Inspired Computing, 75-82.

[20]. Cominetti, O., Matzavinos, A., Samarasinghe, S., Kulasiri, D., Liu, S., Maini,

P., & Erban, R. (2010), “DifFUZZY: a fuzzy clustering algorithm for complex

datasets”, International Journal of Computational Intelligence in

Bioinformatics and Systems Biology 1(4), 402-417.

[21]. Cuong, B.C. (2014), “Picture fuzzy sets”, Journal of Computer Science and

Cybernetics 30(4), 409-420.

112

[22]. D’Urso, P., Disegna, M., & Massari, R. (2019), “Fuzzy Clustering in Travel

and Tourism Analytics”, In Business and Consumer Analytics: New Ideas,

839-863.

[23]. D'Urso, P., De Giovanni, L., & Massari, R. (2018), “Robust fuzzy clustering

of multivariate time trajectories”, International Journal of Approximate

Reasoning 99, 12-38.

[24]. Davies, D.L, Bouldin, D.W. (1979), “A cluster separation measure”, IEEE

Transactions on Pattern Analysis and Machine Intelligence 2, 224-227.

[25]. De Carvalho, F. D. A., Lechevallier, Y., & De Melo, F. M. (2013), “Relational

partitioning fuzzy clustering algorithms based on multiple dissimilarity

matrices”, Fuzzy Sets and Systems 215, 1-28.

[26]. De Oliveira, J. P. (2007), “Advances in fuzzy clustering and its applications”,

Chichester, Wiley.

[27]. Du, M., Ding, S., & Xue, Y. (2018), “A robust density peaks clustering

algorithm using fuzzy neighborhood”, International Journal of Machine

Learning and Cybernetics 9(7), 1131-1140.

[28]. Eberhart, R. C., & Kennedy, J. (1995), “A new optimizer using particle swarm

theory”, Proceedings of the sixth international symposium on micro machine

and human science 1, (1995, October) 39-43.

[29]. Evans, A. N. (2006), “Cloud motion analysis using multichannel correlation-

relaxation labeling”, Geoscience and Remote Sensing Letters 3(3), 392-396.

[30]. Fang, Y., & Wang, J. (2012), “Selection of the number of clusters via the bootstrap

method”, Computational Statistics & Data Analysis 56(3), 468-477.

[31]. Ferreira, M. R., & de Carvalho, F. D. (2012), “Kernel fuzzy clustering methods

based on local adaptive distances”, Proceedings of 2012 IEEE International

Conference on In Fuzzy Systems (FUZZ-IEEE), 1-8.

[32]. Fujita, A., Takahashi, D. Y., & Patriota, A. G. (2014), “A non-parametric

method to estimate the number of clusters”, Computational Statistics & Data

Analysis 73, 27-39.

113

[33]. Germann, U., & Zawadzki, I. (2002), “Scale-dependence of the predictability

of precipitation from continental radar images”, Part I: Description of the

methodology. Monthly Weather Review 130(12), 2859-2873.

[34]. Graves, D., Pedrycz, W. (2010), “Kernel-based fuzzy clustering and fuzzy

clustering: A comparative experimental study”, Fuzzy sets and systems 161(4),

522-543.

[35]. He, Z., Cichocki, A., Xie, S., & Choi, K. (2010), “Detecting the number of

clusters in n-way probabilistic clustering”, IEEE Transactions on Pattern

Analysis and Machine Intelligence 32(11), 2006-2021.

[36]. Huang, Z. (1998), “Extensions to the k-means algorithm for clustering large

data sets with categorical values”, Data mining and knowledge discovery 2(3),

283-304.

[37]. Hung, W. L. (2004), “Fuzzy clustering based on intuitionistic fuzzy relations”,

International Journal of Uncertainty, Fuzziness and Knowledge-Based

Systems 12(4), 513-529.

[38]. Hwang, C. R. (2007), “Uncertain fuzzy clustering: interval type-2 fuzzy

approach to c-means”, IEEE Transactions on Fuzzy Systems 15(1), 107-120.

[39]. Iakovidis, D. P. (2008), “Intuitionistic fuzzy clustering with applications in

computer vision”, Lecture Notes in Computer Science 5259, 764–774.

[40]. Ienco, D., & Bordogna, G. (2018), “Fuzzy extensions of the DBScan clustering

algorithm”, Soft Computing 22(5), 1719-1730.

[41]. Ji, J., Bai, T., Zhou, C., Ma, C., & Wang, Z. (2013), “An improved k-

prototypes clustering algorithm for mixed numeric and categorical data”,

Neurocomputing 120, 590-596.

[42]. Ji, J., Pang, W., Zhou, C., Han, X., & Wang, Z. (2012), “A fuzzy k-prototype

clustering algorithm for mixed numeric and categorical data”, Knowledge-

Based Systems 30, 129-135.

[43]. Ji, Z. X. (2013), “Interval-valued possibilistic fuzzy C-means clustering

algorithm”, Fuzzy Sets and Systems 253, 138 – 156.

114

[44]. Jiang, H., Chen, X., He, T., Chen, Z., & Li, X. (2018), “Fuzzy clustering of

crowdsourced test reports for apps”, ACM Transactions on Internet

Technology (TOIT) 18(2), 18.

[45]. Kaur, P., Soni D., Gosain D.A., India I.I. (2012), “Novel Intuitionistic Fuzzy

C-Means Clustering for Linearly and Nonlinearly Separable Data”, WSEAS

Transactions on Computers 11(3), 65-76.

[46]. Khan, M. J., Yousaf, A., Khurshid, K., Abbas, A., & Shafait, F. (2018, April),

“Automated forgery detection in multispectral document images using fuzzy

clustering”, In 2018 13th IAPR International Workshop on Document Analysis

Systems (DAS) 393-398.

[47]. Kumar, D., Verma, H., Mehra, A., & Agrawal, R. K. (2019), “A modified

intuitionistic fuzzy c-means clustering approach to segment human brain MRI

image”, Multimedia Tools and Applications 78(10), 12663-12687.

[48]. Le, T., Altman, T., & Gardiner, K. J. (2012), “A fuzzy clustering method using

Genetic Algorithm and Fuzzy Subtractive Clustering”, In Proceeding Intl'Conf

on Information and Knowledge Engineering (WORLDCOMP-IKE'12), (2012,

July) 426-432.

[49]. Lee, J. S., & Olafsson, S. (2013), “A meta-learning approach for determining

the number of clusters with consideration of nearest neighbors,” Information

Sciences 232, 208-224.

[50]. Lei, T., Liu, P., Jia, X., Zhang, X., Meng, H., & Nandi, A. K. (2019),

“Automatic Fuzzy Clustering Framework for Image Segmentation”, IEEE

Transactions on Fuzzy Systems.

[51]. Li, C., Cerrada, M., Cabrera, D., Sanchez, R. V., Pacheco, F., Ulutagay, G., &

Valente de Oliveira, J. (2018), “A comparison of fuzzy clustering algorithms

for bearing fault diagnosis”, Journal of Intelligent & Fuzzy Systems 34(6),

3565-3580.

[52]. Li, C., Zhao, H., & Xu, Z. (2018), “Kernel c-means clustering algorithms for

hesitant fuzzy information in decision making”, International Journal of Fuzzy

Systems 20(1), 141-154.

115

[53]. Liang, J., Zhao, X., Li, D., Cao, F., & Dang, C. (2012), “Determining the

number of clusters using information entropy for mixed data”, Pattern

Recognition 45(6), 2251-2265.

[54]. Lin, K. (2014), “A Novel Evolutionary Kernel Intuitionistic Fuzzy C-means

Clustering Algorithm”, IEEE Transactions on Fuzzy Systems 22(5), 1074 – 1087.

[55]. Linda, O. Manic, M. (2012), “General type-2 fuzzy c-means algorithm for

uncertain fuzzy clustering”, IEEE Transactions on Fuzzy Systems 20(5), 883 - 897.

[56]. Maraziotis, I. A.(2012), “A semi-supervised fuzzy clustering algorithm

applied to gene expression data”, Pattern Recognition 45(1), 637-648.

[57]. Marzano, F. S., Rivolta, G., Coppola, E., Tomassetti, B., & Verdecchia, M.

(2007), “Rainfall nowcasting from multisatellite passive-sensor images using

a recurrent neural network”, IEEE Transactions on Geoscience and Remote

Sensing 45(11), 3800-3812.

[58]. Mass, C., & Mass, C. F. (2011), “Nowcasting: The Next Revolution in Weather

Prediction”, Bulletin of the American Meteorological Society. Available at:

http://www.atmos.washington.edu/cliff/BAMSNowcast7.11.pdf.

[59]. Melgani, F. (2006), “Contextual reconstruction of cloud-contaminated

multitemporal multispectral images”, IEEE Transactions on Geoscience and

Remote Sensing 44(2), 442-455.

[60]. Mendel, J.M., John, R.B. (2002), “Type-2 fuzzy sets made simple”, IEEE

Transactions on Fuzzy Systems 10(2), 117-127.

[61]. Moh’d Alia, O. (2018), “A dynamic harmony search-based fuzzy clustering

protocol for energy-efficient wireless sensor networks”, Annals of

Telecommunications 73(5-6), 353-365.

[62]. Nadig, K., Potter, W., Hoogenboom, G., & McClendon, R. (2013),

“Comparison of individual and combined ANN models for prediction of air

and dew point temperature”, Applied intelligence 39(2), 354-366.

[63]. National Oceanic and Atmospheric Administration (2015), “MTSAT West

Color Infrared Loop”, Available at:

http://www.goes.noaa.gov/sohemi/sohemiloops/shirgmscolw.html.

116

[64]. Ngo, L. T., Dang, T. H., & Pedrycz, W. (2018), “Towards interval-valued

fuzzy set-based collaborative fuzzy clustering algorithms”, Pattern

Recognition 81, 404-416.

[65]. Nguyen, T. P. Q., & Kuo, R. J. (2019), “Partition-and-merge based fuzzy

genetic clustering algorithm for categorical data”, Applied Soft Computing 75,

254-264.

[66]. Oner, S. C., & Oztaysi, B. (2018), “An interval type 2 hesitant fuzzy MCDM

approach and a fuzzy c means clustering for retailer clustering”, Soft

Computing 22(15), 4971-4987.

[67]. Paige, C. C., Saunders, M. A. (1982), “LSQR: An algorithm for sparse linear

equations and sparse least squares”, ACM Transactions on Mathematical

Software (TOMS) 8(1), 43-71.

[68]. Pakhira, M. K. (2012), “Finding Number of Clusters before Finding Clusters”,

Procedia Technology 4, 27-37.

[69]. Park, S., & Lee, S. R. (2014), “Red tides prediction system using fuzzy

reasoning and the ensemble method”, Applied intelligence 40(2), 244-255.

[70]. Pfeifer, P. E., & Deutrch, S. J. (1980), “A Three-Stage Iterative Procedure for

Space-Time Modeling Phillip”, Technometrics 22(1), 35-47.

[71]. Pham, T. X., Siarry, P., & Oulhadj, H. (2018), “Integrating fuzzy entropy

clustering with an improved PSO for MRI brain image segmentation”, Applied

Soft Computing 65, 230-242.

[72]. Rivolta, G., Marzano, F. S., Coppola, E., & Verdecchia, M. (2006), “Artificial

neural-network technique for precipitation nowcasting from satellite

imagery”, Advances in Geosciences 7(7), 97-103.

[73]. Ruspini, E. H., Bezdek, J. C., & Keller, J. M. (2019), “Fuzzy Clustering: A

Historical Perspective”, IEEE Computational Intelligence Magazine 14(1),

45-55.

[74]. Salgado, C. M., Vieira, S. M., & Sousa, J. M. (2018), “Mixed fuzzy clustering

for deriving predictive models in intensive care units”, In Operations Research

Applications in Health Care Management, 81-99.

117

[75]. Shukla, B. P., & Pal, P. K. (2012), “A source apportionment approach to study

the evolution of convective cells: An application to the nowcasting of

convective weather systems”, IEEE Journal of Selected Topics in Applied

Earth Observations and Remote Sensing 5(1), 242-247.

[76]. Shukla, B. P., Kishtawal, C. M., & Pal, P. K. (2014), “Prediction of Satellite

Image Sequence for Weather Nowcasting Using Cluster-Based

Spatiotemporal Regression”, IEEE Transactions on Geoscience and Remote

Sensing 52(7), 4155 – 4160.

[77]. Son LH, Cuong BC, Long HV (2013), “Spatial Interaction–Modification

Model and Applications to Geo-Demographic Analysis”, Knowledge-Based

Systems 49, 152-170.

[78]. Son, L.H. (2014), “Enhancing Clustering Quality of Geo-Demographic

Analysis Using Context Fuzzy Clustering Type-2 and Particle Swarm

Optimization”, Applied Soft Computing 22, 566 – 584.

[79]. Son, L.H. (2014), “HU-FCF: A Hybrid User-Based Fuzzy Collaborative

Filtering Method in Recommender Systems”, Expert Systems With

Applications 41(15), 6861 – 6870.

[80]. Son, L.H. (2014), “Optimizing Municipal Solid Waste Collection Using

Chaotic Particle Swarm Optimization in GIS Based Environments: A Case

Study at Danang City, Vietnam”, Expert Systems With Applications 41(18),

8062 – 8074.

[81]. Son, L.H. (2015), “DPFCM: A Novel Distributed Picture Fuzzy Clustering Method

on Picture Fuzzy Sets”, Expert Systems With Applications 42(1), 51 - 66.

[82]. Son, L.H., Cuong, B.C., Lanzi, P.L., Thong, N.T. (2012), “A novel

intuitionistic fuzzy clustering method for geo-demographic analysis”, Expert

Systems with Applications 39(10), 9848-9859.

[83]. Son, L.H., Lanzi, P.L., Cuong, B.C., Hung, H.A. (2012), “Data Mining in GIS:

A Novel Context-Based Fuzzy Geographically Weighted Clustering

Algorithm”, International Journal of Machine Learning and Computing 2(3),

235 – 238.

118

[84]. Son, L.H., Linh, N.D., Long, H.V. (2014), “A lossless DEM compression for

fast retrieval method using fuzzy clustering and MANFIS neural network”,

Engineering Applications of Artificial Intelligence 29, 33-42.

[85]. Song, Y., Lu, J., Lu, H., & Zhang, G. (2019), “Fuzzy Clustering-based

Adaptive Regression for Drifting Data Streams”, IEEE Transactions on Fuzzy

Systems.

[86]. Trabelsi, M., & Frigui, H. (2019), “Robust fuzzy clustering for multiple

instance regression”, Pattern Recognition 90, 424-435.

[87]. Turner, B. J., Zawadzki, I., & Germann, U. (2004), “Predictability of

precipitation from continental radar images—Part III: Operational nowcasting

implementation (MAPLE)”, J. Appl. Meteorol 43(2), 231–248.

[88]. UCI Repository of Machine Learning Databases, Irvine, University of

California, 2007. URL: http://archive.ics.uci.edu/ml/

[89]. Vendramin, L., Campello, R.J., Hruschka, E.R. (2010), “Relative clustering

validity criteria: A comparative overview”, Statistical Analysis and Data

Mining 3(4), 209-235.

[90]. Ward System Group (1993), “Manual of NeuroShell 2”, Ward System Group,

Frederick.

[91]. Wang, R., Wang, J., Gao, H., & Wei, G. (2019), “Methods for MADM with

picture fuzzy muirhead mean operators and their application for evaluating the

financial investment risk”, Symmetry 11(1), 6.

[92]. Wang, Y., Zheng, S., Zhang, W., Wang, G., & Wang, J. (2018), “Fuzzy entropy

complexity and multifractal behavior of statistical physics financial dynamics”,

Physica A: Statistical Mechanics and its Applications 506, 486-498.

[93]. Xu, Z. (2012), “Intuitionistic fuzzy aggregation and clustering,” Springer,

Chicago.

[94]. Xu, Z., Wu. J. (2010), “Intuitionistic fuzzy C-means clustering algorithms”,

Journal of Systems Engineering and Electronics 21(4), 580-590.

[95]. Xue, M., Zhou, L., Kojima, N., dos Muchangos, L. S., Machimura, T., &

Tokai, A. (2018), “Application of fuzzy c-means clustering to PRTR

119

chemicals uncovering their release and toxicity characteristics”, Science of the

Total Environment 622, 861-868.

[96]. Yang, M. S., Hwang, P. Y., & Chen, D. H. (2004), “Fuzzy clustering

algorithms for mixed feature variables”, Fuzzy Sets and Systems 141(2), 301-

317.

[97]. Yu, H., Liu, Z., & Wang, G. (2014), “An automatic method to determine the

number of clusters using decision-theoretic rough set”, International Journal

of Approximate Reasoning 55(1), 101-115.

[98]. Zadeh, L. A. (1965), “Fuzzy sets”, Information and control 8(3), 338-353.

[99]. Zangwill, W. I. (1969), “Convergence conditions for nonlinear programming

algorithms”, Management Science 16(1), 1-13.

[100]. Zhang, D., Ji, M., Yang, J., Zhang, Y., & Xie, F. (2014), “A novel cluster

validity index for fuzzy clustering based on bipartite modularity”, Fuzzy Sets

and Systems 253, 122-137.

[101]. Zhang, X. (2018), “Pythagorean fuzzy clustering analysis: a hierarchical

clustering algorithm with the ratio index‐based ranking methods”,

International Journal of Intelligent Systems 33(9), 1798-1822.

[102]. Zhao, F., Liu, H., Fan, J., Chen, C. W., Lan, R., & Li, N. (2018), “Intuitionistic

fuzzy set approach to multi-objective evolutionary clustering with multiple

spatial information for image segmentation”, Neurocomputing 312, 296-309.

[103]. Zhao, H., Xu Z., Wang, Z. (2013), “Intuitionistic Fuzzy Clustering Algorithm

Based On Boole Matrix And Association Measure”, International Journal of

Information Technology & Decision Making 12(1), 95-118.

[104]. Zhao, Q., Shao, S., Lu, L., Liu, X., & Zhu, H. (2018), “A new PV array fault

diagnosis method using fuzzy C-mean clustering and fuzzy membership

algorithm”, Energies 11(1), 238.

[105]. Zhou, J. C. (2016), “Fuzzy clustering with the entropy of attribute weights”,

Neurocomputing 198, 125-134.

[106]. Zimmermann, H. (2001), “Fuzzy set theory-and its applications”, US:

Springer.

120

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

Đề 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.

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊ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

LUẬN ÁN TIẾN SĨ TOÁN HỌC

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊ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

LUẬN ÁN TIẾN SĨ TOÁN HỌC

LỜI CAM ĐOAN

LỜI CẢM ƠN

MỤC LỤC

DANH MỤC THUẬT NGỮ VÀ TỪ VIẾT TẮT

DANH MỤC BẢNG BIỂU

DANH MỤC HÌNH VẼ

MỞ ĐẦU

CHƯƠNG 1. CƠ SỞ LÝ THUYẾT

  DWIP

Dữ liệu

Số bản

Số thuộc

Số thuộc tính

Số cụm

Số phần tử ở mỗi lớp

tính số

kiểu loại

ghi

CHƯƠNG 2. THUẬT TOÁN PHÂN CỤM MỜ VIỄN CẢNH

I:

O: Ma trận , , and tâm cụm ;

2.4.1. Ví dụ minh họa cho FC-PFS

m c n

i

i

h t d w

l a p e s

sepal length in cm

Data

Độ đo MA (%)

FC-PFS

96.1

87.1*

67.2

74.5*

72.9

76.9

87

77.1*

Rand Index (%)

Data

FC-PFS

92.4

71.3

56.9

71.4

49.9

49.84

53.9

55.6*

Data

DB

FC-PFS

3.05

2.77*

1.76*

8.13

2.9

2.28

2.03*

2.59*

Data

Thời gian tính toán (sec)

FC-PFS

0.033

0.112*