Dự thảo tóm tắt 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ờ trên tập mờ viễn cảnh và ứng dụng trong dự báo

Chia sẻ: Acacia2510 _Acacia2510 | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

25
lượt xem 2
download

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

Mục tiêu nghiên cứu của luận án là 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 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ách với các thuật toán liên quan khác. Nghiên cứu, phát triển ứng dụng của thuật toán phân cụm trên tập mờ viễn cảnh vào bài toán dự báo thời tiết dựa trên ảnh mây vệ tinh.

Chủ đề:

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

Lưu

Nội dung Text: Dự thảo tóm tắt 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ờ trên tập 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Ờ TRÊN TẬP 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 DỰ THẢO TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội, 2019
Công trình đƣợc hoàn thành tại: Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội. 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 Phản biện 1: ............................................. Phản biện 2: ............................................. Phản biện 3: ............................................. Luận án sẽ được bảo vệ tại Hội đồng chấm luận án cấp Đại học Quốc gia họp tại: Trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội vào hồi......giờ......., ngày.......tháng.......năm 20... Có thể tìm hiểu luận án tại: - Thư viện Quốc gia Việt Nam, - Trung tâm thông tin - Thư viện, Đại học Quốc gia Hà Nội.
MỞ ĐẦU 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. Tuy nhiên, việc các phân cụm này cũng có một số nhược điểm là mỗi một phần tử chỉ thuộc về một cụm dữ liệu hay một số dữ liệu có thể bị thiếu thông tin hoặc thông tin không chắc chắn. Để giải quyết vấn đề này, dựa trên lý thuyết về tập mờ của Zadeh, Bezdek đã đưa ra thuật toán phân cụm mờ Fuzzy C-mean (FCM) nhằm giải quyết các nhược điểm trên. Thuật toán này được biết đến như một phương thức chính trong phân cụm mờ. Tuy nhiên, chất lượng phân cụm của FCM thường không cao 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, ở đó 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 các 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), tập mờ trực cảm, … mang lại chất lượng phân cụm tốt hơn. Tuy nhiên các thuật toán này khi phân cụm cho kết quả vẫn chưa đưa ra được các thông tin đầy đủ, đặc biệt là sự phù hợp của mô hình. Vào năm 2014, tác giả Bùi Công Cường giới thiệu tập mờ viễn cảnh (PFS), 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 PFS. Chính vì vậy việc phát triển thuật toán phân 1
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ờ trên tập 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 mà chưa xem xét đến việc phân cụm theo cách tiếp cận phân hoạch. 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. 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. 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. Các nghiên cứ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. Thứ hai, xử lý với dữ liệu phức tạp là không dễ 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. Phân cụm mờ có rất nhiều ứng dụng trong thực tế cuộc sống ở rất nhiều lĩnh vực khác nhau như: trong kinh tế với dự báo tỉ giá, dự báo chứng khoán, dự báo tài chính, …; trong y khoa: Hỗ trợ chuẩn đoán hình ảnh, hỗ trợ tư vấn khám bệnh, …; trong thủy văn: dự báo thời tiết ngắn hạn, …; trong xử lý ảnh: Phân đoạn ảnh, …; trong hệ tư vấn: hỗ trợ ra quyết định, … Đề tài nghiên cứu tập trung vào ứng dụng của phân cụm mờ trong bài toán dự báo thời tiết ngắn hạn. 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. Đ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 khoảng thời gian này. Các 2
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 các khu vực trong vùng phủ sóng của nó. Mục tiêu nghiên cứu - 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ờ trên tập mờ viễn cảnh. Kiểm chứng bằng lý thuyết sự hội tụ của thuật toán và thực nghiệm, so sách với các 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 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ách với các thuật toán liên quan khác. - Mục tiêu 3: Nghiên cứu, phát triển ứng dụng của thuật toán phân cụm trên tập mờ viễn cảnh vào 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 - 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. 3
Phƣơng pháp nghiên cứu - 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ề hội tụ của mô hình đề xuất. - Nghiên cứu mở rộng: Mở rộng 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. Phạm vi và giới hạn của đề tài nghiên cứu - Phát triển thuật toán phân cụm mờ trên tập mờ viễn cảnh với phân cụm 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. Bố cục của luận án - Chương 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: Giới thiệu một số kiến thức cơ sở chuẩn bị về đề tài nghiên cứu. Chương này trình bày giới thiệu sơ lược 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 cho việc tự động xác định số cụm, xử lý với dữ liệu phức tạp và ứng dụng trong dự báo thời tiết ngắn hạn. Một số độ đo tiêu chí đánh giá và bộ dữ liệu cũng được trình bày. 4
- Chương 2: Giới thiệu về thuật toán phân cụm trên tập mờ viễn cảnh từ ý tưởng thuật toán, cách thức triển khai thuật toán, đánh giá lý thuyết về sự hội tụ và thực nghiệm tính toán. - Chương 3: Đề xuất 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, có các thực nghiệm kiểm chứng kèm theo. - Chương 4: Áp dụng thuật toán phân cụm mờ trên tập mờ viễn cảnh cho bài toán dự báo ảnh mây về tinh. CHƢƠNG 1. CƠ SỞ LÝ THUYẾT 1.1. Tập mờ Trong phần này tác giả trình bày các khái niệm về tập mờ các các tập mờ nâng cao, đặc biệt là tập mờ viễn cảnh. Tập mờ viễn cảnh là tập mờ tổng quát của tập mờ trực cảm và tập mờ thường với thể hiện được các hành vi ra quyết định giống con người như khẳng đinh, phủ định, trung lập và từ chối 1.2. Độ đo tƣơng tự và đánh giá chất lƣợng cụm Các độ đo tương tự đánh giá chất lượng cụm gồm có chỉ số Mean Accuracy (MA), chỉ số Davies-Bouldin (DB), chỉ số Rand, chỉ số Alternative Silhouette ( ), chỉ số WGLI [64] và PBM [72]. 1.3. Thuật toán phân cụm mờ Trong phần này, các thuật toán phấn cụm mờ trên tập mờ thường, tập mờ loại 2 và tập mờ trực cảm được trình bày. 1.4. Một số thuật toán khác 1.4.1. Thuật toán tối ưu bầy đàn (PSO) Thuật toán tối ưu hóa bầy đàn (PSO) 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. 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. 5
1.4.2. Thuật toán DifFuzzy Thuật toán phân cụm DifFuzzy 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. 1.4.3. Thuật toán Dissimilarity Thuật toán Dissimilarity là 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: khởi tạo, tính toán giá trị tốt nhất, tính toán trọng số liên quan tốt nhất, định nghĩa phân hoạch mờ tốt nhất, và điều kiện dừng. 1.4.4. Phương pháp FCM-STAR Pfeifer và Deutsch đã đề 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. Mật độ của mỗi điểm ảnh ( ) trong một miền hình ảnh có thể được mô phỏng như một hàm " " của mật độ các pixel lân cận theo không gian và thời gian, với giả định của quan hệ nhân quả. 1.5. Bộ dữ liệu thực nghiệm Tập dữ liệu thử nghiệm cho FC-PFS và các thuật toán cải tiến được lấy trên kho dữ liệu học máy chuẩn UCI với những bộ dữ liệu hoàn toàn là số như IRIS, WINE, WDBC, GLASS, IONOSPHERE, HABERMAN, HEART and CMC. 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 được lấy ở 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), Luzon – Philippines (dữ liệu 2) và Jakarta – Indonesia (Dữ liệu 3). 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 ngày 28/11/2014. Các hình ảnh có cùng kích thước (100x100 pixel). 1.6. Kết luận chƣơng Trong chương này, các 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 giải quyết các bài toán ở các chương sau. 6
CHƢƠNG 2. THUẬT TOÁN PHÂN CỤM TRÊN TẬP MỜ VIỄN CẢNH 2.1. Ý tƣởng thuật toán Ý tưởng của thuật toán là thiết kế hàm mục tiêu gồm hai thành phần như của thuật toán phân cụm trên tập mờ trực cảm. Với 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 nhưng thành phần độ thuộc được thay thế bằng đại lượng ( ( )). Đại lượng này thể hiện cho việc một điểm dữ liệu nếu thuộc về một cụm thì giá trị phải lớn và phải càng nhỏ. 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ẽ có giá trị và nhỏ, giúp giảm đi các giá trị trung lập và từ chối của mô hình, giúp mô hình phân cụm cải tiến được độ chính xác hơn. 2.2. Thuật toán phân cụm trên tập mờ viễn cảnh 2.2.1. Hàm mục tiêu Giả sử có một tập X chứa N điểm trong không gian đa chiều. Hãy chia tập dữ liệu thành C nhóm thỏa mãn hàm mục tiêu sau. ∑ ∑ . ( )/ ‖ ‖ ∑ ∑ ( ) , (1) Các ràng buộc được định nghĩa như sau: ; , - (2) ∑ . ( )/ , (3) ∑ . / , (4) Mô hình đề xuất trong công thức (1-4) dựa trên nguyên lý của tập PFS và được tóm tắt như sau:  Mô hình đề xuất là khái quát hóa của mô hình phân cụm mờ trên tập mờ viễn cảnh trong công thức (1-4) khi và điều kiện (4) không tồn tại, mô hình đề xuất là mô hình phân cụm mờ trực cảm. 7
 Khi và , điều kiện (4) không tồn tại, các điều kiện khác thỏa mãn, mô hình đề xuất là mô hình phân cụm mờ.  Công thức (3) chỉ ra độ thuộc của điểm tới tâm cụm là ( ) thỏa mãn các ràng buộc trong mô hình phân cụm mờ truyền thống.  Công thức (4) đảm bảo trên 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 tồn tại trong mô hình.  Một ràng buộc khác trong (2) phản ảnh định nghĩa của các tập PFS. Định lý 1. Các giải pháp tối ưu của hàm mục tiêu trong (1-4) là: ( ) . ( ) / , (5) ( , ), , (6) ‖ ‖ ∑ ( )( ) ‖ ‖ ( ; ), (7) . ∑ /, ∑ ( ; ), ∑ . ( )/ , (8) ∑ . ( )/ ( ). 2.2.2. Chi tiết thuật toán Thuật toán FC-PFS có cấu trúc lắp giống với thuật toán FCM với việc khởi tạo ngẫu nhiên tham số , . Quá trình lặp bắt đầu bằng việc tính , sau đó tính lại các giá trị mới của , và dừng khi các giá trị , gần như không đổi. 8
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 với ý tưởng sử dụng định lý Zangwill để chứng minh hàm mục tiêu của thuật toán sẽ hội tụ với các nghiệm là các giá trị được tính theo công thức (1-4). 2.4. Thực nghiệm số Môi trường thử nghiệm thuật toán được mô tả như sau: thuật toán đề xuất FC-PFS, thuật toán FCM [7], IFCM [10], KFCM [25] và KIFCM [38] sử dụng ngôn ngữ lập trình. Kết quả thử nghiệm là kết quả trung bình sau 50 lần chạy. 2.4.1. Ví dụ minh họa cho FC-PFS Phần này sẽ minh họa chi tiết các bước thực hiện với ví dụ số của thuật toán FC-PFS với tập dữ liệu IRIS. 2.4.2. So sánh chất lượng phân cụm Qua kết quả nhận được, rõ ràng nhận thấy 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. 2.4.3. Đánh giá thuật toán qua các tham số FC-PFS được thử nghiệm với hệ số mũ 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. Kết quả cho thấy 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. Tuy nhiên, khi tăng giá trị , FC-PFS cho kết quả phân cụm tốt hơn. Giá trị cho chất lượng cụm tốt nhất ở chỉ số MA, RI và DB. 2.5. Kết luận chƣơng Trong chương này, thuật toán phân cụm mờ trên tập mờ viễn cảnh được đề xuất. Bằng cách kết hợp các thành phần của PFS và mô hình phân cụm, FC-PFS 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ả 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. 9
CHƢƠNG 3. MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN PHÂN CỤM MỜ TRÊN TẬP MỜ VIỄN CẢNH 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 Trong phần này, 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 và FC-PFS, được đặt tên là AFC-PFS. Ở đó 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 Picture Composite Cardinality ( ) liên quan đến số lượng các 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 bây giờ được coi là một giá trị tối ưu trong sự kết hợp với các giá trị hiện tại của các tham số của ( ( ) , ( ) , ( ) và ). Để đánh giá độ tốt của mỗi phương án, giá trị fitness của PSO được tính bằng giá trị Alternative Silhouette ( ). 3.1.2. Chi tiết thuật toán Khởi tạo ban đầu số lượng phương án của PSO là { }, ở đó 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 dich 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à . 10
Để làm được điều này, giá trị được đề xuất và giá trị này càng nhỏ thì chất lượng cụm càng tốt. ∑ ( ), ( ), (13) ở đó 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 ( ( ) , ( ) , ( ) , ( ) ). Một trong những chỉ số đánh giá ổn định nhất cho việc phân cụm, được sử dụng để đo chất lượng cụm. 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ủa phương án. Sau đó, phương án được cập nhật bằng cách thay đổi ngưỡng như sau. () ( ) () (14) ( ), , ( ), (15) ở đây , là các tham số PSO để cập nhật (một cách tổng quát ). Đị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 () () () () ( , , , ). Sự cập nhật của tất cả các phương án được tiếp tục lặp lại cho đế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ố 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 ( ). Thuật toán AFC-PFS có những lợi thế như sau: - Tổng kết hợp chiến lược PSO và các hoạt động chính của FC-PFS nâng cao hiệu năng của thuật toán.. 11
- 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 FC-PFS bằng các thuật toán phân cụm mờ khác. Tuy nhiên, mô hình đề xuất vẫn tồn tại một số hạn chế là thời gian tính toán là khá lớn. Ngoài ra, 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. 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. 3.1.3. Thực nghiệm số Ở 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 của phương pháp cắt tỉa, phương pháp không tham số (NPM) của phương pháp quét và thuật toán CCE của phương pháp tiền xử lý. Để 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 và PBM. Các kết quả thực nghiệm cho thấy thuật toán đề xuất cho số lượng cụm gần với số lượng cụm mặc định của bộ dữ liệu. Đồng thời, thời gian chạy của AFC-PFS thậm chí còn nhanh hơn một số thuật toán khác. 3.2. Thuật toán phân cụm mờ với dữ liệu phức tạp 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 ( , , ). 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 (16). ( ) { (16) Dữ liệu đầu vào phải đượ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 2 phần tử. 12
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 và được đặt tên là 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à ở đó 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ử.  ( , , ): độ 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. Giá trị tối ưu được tính như sau: ∑ ∑ . ( )/ ‖ ‖ (17) ∑ ∑ ( ), 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 những thuật toán liên quan khác, các giải pháp tối ưu địa phương Pbest- ( , , , ) của các phương án được ghi lại. Sau đó, các phương án được cập nhật giá trị. Trong việc cập nhật, ( , ) được tính theo phương trình (6-7) và (18-19) như dưới đây. ( ) ( ), (18) ( , ), 13
( ) ( ), (19) ( , ), ở đó ( , , và ) là những giá trị tốt nhất toàn cục. Tâm của cụm được chọn là những phần tử có độ thuộc tốt nhất vào cụm j. Việc cập nhật tất cả các phương án được tiếp tục đến khi đạt được một số lần lặp nhất định hay giá trị tối ưu toàn cục không đổi. Chi tiết thuật toán như sau: 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 O: Ma trận , , và các tâm cụm ; 1: t=0 2: ( ) ( ) ( ) ; ; ( , ) thỏa mãn (2) 3: Repeat 4: t=t+1 5: For each phương án ( ) 6: Chọn tâm ( ) ( ) 7: Tính toán ( ; ) bằng công thức (18) ( ) 8: Tính toán ( ; ) bằng công thức (19) 9: ( ) Tính toán ( ; ) bằng công thức (5) 10: Tính toán giá trị fitness bằng công thức (17) 11: Cập nhật giá trị Pbest 12: Cập nhật giá trị Gbest 13: End 14: Until giá trị Gbest không đổi hoặc số lần lặp vượt quá maxSteps 15: Output ( , , , ) = ( , , , ) Phương pháp đề xuất có một số ưu điểm là 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 14
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. Hơn nữa, PFCA-CD với chiến lược PSO có thể làm nhanh quá trình hội tụ, đồng thời 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 là PFCA-CD có thể cho kết quả tốt, nhưng không chắc là tốt nhất và thời gian tính toán vẫn khá cao. 3.2.3. Thực nghiệm số Thuật toán đề xuất PFCA-CD được cài đặt cùng các thuật toán khác như DifFuzzy [13] và Dissimilarity [16]. Thực nghiệm cho thấy 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. 3.3. Kết luận chƣơng Chương này trình bày hai cải tiến của FC-PFS là thuật toán tự động xác định số cụm AFC-PFS và phân cụm mờ cho dữ liệu phức tạp PFCA-CD. Các cải tiến này góp phần giải quyết các hạn chế của FC-PFS và các thuật toán phân cụm mờ khác trong việc tự động xác định số cụm và xử lý với dữ liệu phức tạp cả về kiểu loại lẫn cấu trúc. 15
CHƢƠNG 4. ỨNG DỤNG CỦA THUẬT TOÁN PHÂN CỤM TRÊN TẬP MỜ VIỄN CẢNH 4.1. Phƣơng pháp 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 PFC 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, kỹ thuật STAR được sử dụng để 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. Cuối cùng, phương pháp lọc Adaptive Median Filtering sử dụng để lọc nhiễu ảnh đầu ra. Để 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ố. ảnh đầu tiên được sử dụng như đầu vào của STAR để tính toán trọng số. 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 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. 4.2. Phƣơng pháp PFC-PFR 4.2.1. Số mờ viễn cảnh tam giác 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 [70]. 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 (20-21) và hình 4 như sau. 16
{ , (20) . (21) { Tích hợp (20-21) với (5) và biểu thị , các giá trị độ trung lập và độ từ chối được tính trong phương trình (22-23). ( ( ) ) , (22) ( ) ( ( ) ) . (23) ( ) là giá trị giải mờ của TPFN và được tính trong phương trình (24). ( ) , (24) ∑ ở đó , , là trọng số giải mờ của TPFN. 4.2.2. Số mờ viễn cảnh hình thang 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 (25-26) như sau: , (25) { 17
. (26) { Đặt kết hợp với phương trình (5), giá trị độ trung lập và độ từ chối được tính như trong công thức (23-24). DEF(A) là giá trị giải mờ của TpPFN A được tính như công thức 27 ( ) . (27) ∑ ở đó , , là trọng số giải mờ của TpPFN. 4.2.3. Chi ti t thuật toán Thuật toán PFC-PFR gồm có bảy bước là: tiền xử lý, phân cụm dữ liệu, sinh luật mờ, nội suy đầu ra, huấn luyện tham số giải mờ và dự đoán ảnh đầu ra. Chi tiết các bước được mô tả như sau: Bƣớc 1: mỗi phần tử trong ma trận sai khác được tính theo công thức (28) dựa trên tỷ lệ khác nhau ( ), của chuỗi thời gian thứ của chuỗi đầu vào ( ) tại thời điểm , ở đó () ( ) () . (28) ( ) Các tỷ lệ khác * ( ) ( ) ( )+ của chuỗi thời gian vào * ( ) ( ) ( )+, tại thời điểm được xác định dựa trên (130). N mẫu huấn luyện * +, ở đó được biểu diễn bởi * ( ) ( ) ( ) ( )+, được xây dựng lại. Biểu diễn ( ) ( ) ( ) { } * () () () ( )+, ở đó ( ) ( ) là đầu vào (đầu ra) thứ của , . 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 18