Tóm tắt Luận án tiến sĩ Toán học: Nghiên cứu một số thuật toán đồng phân cụm mờ cải tiến trong xử lý dữ liệu ảnh

Chia sẻ: Phong Tỉ | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST

Báo xấu

22
lượt xem 2
download

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

Mục đích nghiên cứu của đề tài là nghiên cứu để nâng cao chất lượng phân cụm dữ liệu bằng cách áp dụng Tập mờ giá trị khoảng (IVFs) với FCoC. Nghiên cứu để nâng cao độ ổn định và chất lượng phân cụm dữ liệu bằng cách sử dụng kỹ thuật xác định tâm cụm khởi tạo thay thế phương pháp khởi tạo tâm cụm truyền thống.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Toán học: Nghiên cứu một số thuật toán đồng phân cụm mờ cải tiến trong xử lý dữ liệu ảnh

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ PHẠM VĂN NHÃ NGHIÊN CỨU MỘT SỐ THUẬT TOÁN ĐỒNG PHÂN CỤM MỜ CẢI TIẾN TRONG XỬ LÝ DỮ LIỆU ẢNH Chuyên ngành: Cơ sở toán học cho tin học Mã số : 9460110 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2018
Công trình được hoàn thành tại: VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ BỘ QUỐC PHÒNG Người hướng dẫn khoa học: 1. PGS. TS Ngô Thành Long 2. TS Nguyễn Đức Thảo Phản biện 1: PGS. TS Nguyễn Đức Dũng Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam Phản biện 2: PGS. TS Phạm Văn Hải Đại học Bách khoa Hà Nội Phản biện 3: TS Nguyễn Chí Thành Viện Khoa học và Công nghệ quân sự Luận án được bảo vệ trước Hội đồng chấm luận án cấp Viện, họp tại Viện Khoa học và Công nghệ quân sự vào hồi ……h……, ngày …… tháng …… năm 2018. Có thể tìm hiểu luận án tại thư viện: - Thư viện Viện Khoa học và Công nghệ quân sự. - Thư viện Quốc gia Việt Nam.
1 MỞ ĐẦU 1. Tính cấp thiết của đề tài luận án Đồng phân cụm là một kỹ thuật học không giám sát trong lĩnh vực khai phá dữ liệu. Đồng phân cụm nhằm giải quyết các bài toán phân cụm và phát hiện cấu trúc tiềm ẩn trong dữ liệu phức tạp như đa chiều, nhiều đặc trưng và kích thước lớn. Đồng phân cụm có thể được áp dụng trong một số lĩnh vực nghiên cứu như học máy, khai phá dữ liệu, nhận dạng mẫu, xử lý ảnh, … và ứng dụng trong quốc phòng và an ninh, y tế sinh học, khai thác khoáng sản, quản lý môi trường, … Gần đây, đồng phân cụm mờ (FCoC) đã được phát triển để giải quyết các bài toán phân cụm dữ liệu văn bản, website, ảnh mầu, v.v. Về cơ bản, FCoC đã chứng tỏ được hiệu quả nhất định so với các kỹ thuật phân cụm truyền thống. Tuy nhiên, FCoC còn hạn chế về thu nhận các vấn đề không rõ ràng; nhạy cảm với khởi tạo tâm cụm nên dễ rơi vào tối ưu cục bộ; độ phức tạp tính toán cao; khó tổ chức và cài đặt thuật toán khi dữ liệu có số chiều và kích thước lớn. Hơn nữa, việc xác định số cụm dữ liệu tối ưu vẫn còn là một vấn đề thách thức trong các thuật toán phân cụm. Xuất phát từ những lý do trên, nghiên cứu sinh đã chọn đề tài nghiên cứu cho luận án tiến sĩ “Nghiên cứu một số thuật toán đồng phân cụm mờ cải tiến trong xử lý dữ liệu ảnh” để khắc phục một vài hạn chế của đồng phân cụm mờ. 2. Mục tiêu nghiên cứu của luận án - Nghiên cứu để nâng cao chất lượng phân cụm dữ liệu bằng cách áp dụng Tập mờ giá trị khoảng (IVFs) với FCoC. - Nghiên cứu để nâng cao độ ổn định và chất lượng phân cụm dữ liệu bằng cách sử dụng kỹ thuật xác định tâm cụm khởi tạo thay thế phương pháp khởi tạo tâm cụm truyền thống. - Nghiên cứu nâng cao chất lượng phân cụm dữ liệu nhiều đặc trưng bằng kỹ thuật giảm chiều, giảm đặc trưng. - Nghiên cứu phương pháp xác định số cụm phù hợp của dữ liệu.
2 - Tăng tốc FCoC bằng các kỹ thuật lập trình song song. 3. Đối tượng, phạm vi nghiên cứu của luận án Bao gồm: Thuật toán FCoC và các vấn đề liên quan như phương pháp khởi tạo tâm cụm, kỹ thuật giảm đặc trưng, phương pháp đánh giá xu hướng cụm, tăng tốc đồng phân cụm mờ và dữ liệu phục vụ thử nghiệm phân cụm. 4. Phương pháp nghiên cứu của luận án Phương pháp nghiên cứu của luận án là nghiên cứu để đề xuất cải tiến về mặt lý thuyết thuật toán. Sau đó triển khai thực nghiệm và đánh giá kết quả để chứng tỏ cơ sở lý thuyết đã đề xuất đạt được hiệu suất tốt so với các thuật toán đã được đề xuất trước đó. 5. Ý nghĩa khoa học và thực tiễn của luận án Ý nghĩa khoa học: Nghiên cứu chuyên sâu để cải tiến thuật toán đồng phân cụm mờ. Đưa ra một số kết quả lý thuyết mới cho việc đánh giá chất lượng phân cụm và lập trình thực nghiệm để thu nhận kết quả. Nghiên cứu phân tích chi tiết các thuật toán đồng phân cụm mờ cải tiến. Ý nghĩa thực tiễn: Kết quả nghiên cứu là cơ sở để xây dựng các mô hình phân lớp, phân loại và nhận dạng dữ liệu; ứng dụng nhận dạng mục tiêu trong QP&AN, công nghiệp khai thác khoảng sản, y tế và sinh học v.v. 6. Nội dung nghiên cứu và bố cục của luận án Luận án được tổ chức thành 3 chương cùng với mở đầu, kết luận, danh mục các công trình, bài báo khoa học đã được công bố để diễn đạt các nội dung sau: - Nghiên cứu nâng cao chất lượng đồng phân cụm mờ và khắc phục một số hạn chế về khởi tạo tâm cụm, tốc độ xử lý đồng phân cụm. - Nghiên cứu kỹ thuật giảm chiều dữ liệu và nâng cao hiệu quả đồng phân cụm mờ trong xử lý ảnh siêu phổ. - Nghiên cứu phương pháp xác định số cụm phù hợp. - Nghiên cứu phương pháp đánh giá chất lượng cụm.
3 Chương 1 TỔNG QUAN VỀ ĐỒNG PHÂN CỤM MỜ 1.1. Tổng quan về phân cụm dữ liệu Ngày càng nhiều dữ liệu tổ hợp số, văn bản, website, ảnh số, ... lưu trữ dưới dạng ma trận đa chiều. Nhu cầu tìm hiểu cấu trúc tiềm ẩn trong dữ liệu này đã hình thành các bài toán phức tạp cần được giải quyết. Phân cụm là một kỹ thuật học không giám sát đã được áp dụng nhiều trong phân tích mẫu, học máy, hỗ trợ ra quyết định, … Các kỹ thuật phân cụm được chia thành hai nhóm chính là nhóm phân cụm truyền thống và nhóm phân cụm hiện đại như được chỉ ra trong hình 1.1 và 1.2. Các thuật toán phân cụm truyền thống Phân cụm dựa trên Phân cụm dựa Phân cụm dựa Phân cụm dựa trên lý lý thuyết đồ thị thứ bậc trên lưới thuyết hình học Phân cụm dựa Phân cụm dựa Phân cụm dựa Phân cụm dựa Phân cụm dựa trên mật độ trên phân vùng trên phân bố trên lý thuyết mờ trên mô hình Hình 1.1: Sơ đồ phân nhóm các thuật toán phân cụm truyền thống Các thuật toán phân cụm hiện đại Phân cụm dữ liệu Phân cụm dựa lan Phân cụm dựa lý Phân cụm dựa lý không gian truyền ngược thuyết lượng tử thuyết đồ thị phổ Phân cụm dựa Phân cụm dựa Phân cụm dựa lan Phân cụm Phân cụm trí tuệ bầy đàn trên nhân truyền nhân tạo luồng dữ liệu dữ liệu lớn Hình 1.2: Sơ đồ phân nhóm các thuật toán phân cụm hiện đại
4 Mỗi thuật toán phân cụm có những ưu điểm và hạn chế nhất định, chủ yếu được sử dụng để giải quyết một vài vấn đề cụ thể. Nhu cầu phát triển và mở rộng các thuật toán để nâng cao hiệu quả phân cụm là một nhu cầu hết sức tự nhiên, luôn được các nhà nghiên cứu quan tâm. Ngoài ra, yêu cầu đặt ra đối với các kỹ thuật phân cụm về thông tin đầu vào và đầu ra ngày càng cao hơn, phức tạp hơn. 1.2. Thuật toán phân cụm mờ Kết hợp giữa Tập mờ với các kỹ thuật phân cụm đã hình thành các kỹ thuật phân cụm mờ để nâng cao khả năng nhận biết các vấn đề không rõ ràng. Các kỹ thuật phân cụm mờ được phân loại như chỉ ra trong hình 1.3. Các kỹ thuật phân cụm mờ Thuật toán Thuật toán Đồng Phân cụm mờ phân cụm mờ Phân cụm Phân cụm Phân cụm Đồng Đồng Đồng phân Phân cụm Phân Đồng mờ trọng mờ bán mờ dựa mờ trực phân cụm phân cụm cụm mờ cụm mờ phân cụm số giám sát trên nhân cảm mờ trọng mờ giảm bán giám loại 2 mờ loại 2 số chiều sát Hình 1.3: Sơ đồ phân loại các thuật toán phân cụm mờ Nói chung, việc kết hợp Tập mờ, các thuật toán Phân cụm mờ đã đạt được chất lượng cụm tốt hơn so với một số thuật toán phân cụm rõ. Tuy nhiên, thuật toán phân cụm mờ còn tồn tại một số hạn chế khi tiến hành phân cụm trên các loại dữ liệu đa chiều, nhiều đặc trưng. Để khắc phục hạn chế này, gần đây thuật toán đồng phân cụm mờ đã được phát triển. 1.3. Những vấn đề nghiên cứu của luận án 1.3.1. Mô hình phân cụm dữ liệu Để xác định các vấn đề nghiên cứu cụ thể, luận án biểu diễn quy trình phân cụm dưới dạng mô hình phân cụm chi tiết, như chỉ ra trong hình 1.6.
5 Dữ liệu Tiền xử lý dữ liệu Pha 1 Xác định tâm cụm khởi tạo Xác định số cụm Phân cụm dữ liệu Pha 2 Cụm 1 Cụm 2 Cụm C Đánh giá chất lượng phân cụm và hợp nhất các cụm Pha 3 Kết quả đánh giá cụm Kết quả hợp nhất các cụm Hiển thị kết quả Hình 1.6: Mô hình phân cụm dữ liệu sử dụng thuật toán phân cụm mờ 1.3.2. Nghiên cứu nâng cao chất lượng đồng phân cụm mờ 1.3.3. Nghiên cứu xác định tâm cụm khởi tạo cho đồng phân cụm mờ 1.3.4. Nghiên cứu xác định số cụm tối ưu 1.3.5. Nghiên cứu các kỹ thuật giảm đặc trưng dữ liệu 1.3.6. Nghiên cứu để tăng tốc đồng phân cụm mờ 1.3.7. Nghiên cứu các phương pháp đánh giá trong phân cụm 1.4. Cơ sở toán học của luận án 1.4.1. Thuật toán Phân cụm mờ FCM là thuật toán phân cụm mờ phổ biến nhất đã được cải tiến và áp dụng trong nhiều ứng dụng khác nhau. Hàm mục tiêu của FCM được cho bởi công thức (1.4). C N J FCM (U ; P; X )   ucim dci2 (1.14) c 1 i 1
6 1.4.2. Thuật toán đồng phân cụm mờ FCoC Thuật toán FCoC là một kỹ thuật mở rộng của FCM, được sử dụng để phân cụm dữ liệu đa chiều, nhiều đặc trưng. Hàm mục tiêu của thuật toán đồng phân cụm mờ JFCoC được biểu diễn bởi công thức sau: C N D C N C D J FCoC (U ,V , P)   uci vcj dcij  TU  uci log uci  TV  vcj log vcj (1.16) c 1 i 1 j 1 c 1 i 1 c 1 j 1 Các nghiên cứu FCoC gần đây mới chỉ nghiên cứu và ứng dụng trong phân loại dữ liệu văn bản và phân đoạn ảnh mầu. FCoC còn hạn chế như nhạy cảm với khởi tạo tâm cụm; độ phức tạp tính toán cao. 1.4.3. Thuật toán tối ưu bầy đàn trong mô hình đồng phân cụm mờ Thuật toán tối ưu bầy đàn PSO là một thuật toán sử dụng trí tuệ bầy đàn [49] để mô phỏng theo ý tưởng hành vi bầy đàn của các loài chim. Thuật toán này được coi là một thuật toán đa năng vì nó có thể được áp dụng trong nhiều mô hình ứng dụng khác nhau. Trong luận án này, thuật toán PSO được cải tiến và ứng dụng để khởi tạo tâm cụm thay thế phương pháp khởi tạo tâm cụm ngẫu nhiên. 1.5. Kết luận chương 1 Từ tổng quan về đồng phân cụm mờ cho thấy phân cụm nói chung và đồng phân cụm mờ nói riêng là một kỹ thuật quan trọng trong khai phá dữ liệu. Những nghiên cứu gần đây đã chứng tỏ tính hiệu quả của FCoC trong việc giải quyết các bài toán phân cụm dữ liệu đa chiều, nhiều đặc trưng và được ứng dụng trong QP&AN, y tế và sinh học, khai thác khoáng sản, … Tuy nhiên, FCoC gần đây mới chỉ được ứng dụng để phân loại dữ liệu website, văn bản và ảnh mầu. FCoC chưa đề cập đến dữ liệu có số đặc trưng lớn hơn và phức tạp hơn như ảnh đa phổ và ảnh siêu phổ. Ngoài ra, FCoC còn nhạy cảm với khởi tạo tâm cụm, số cụm tối ưu và giảm đặc trưng dữ liệu. Nội dung tiếp theo của luận án sẽ tập trung xây dựng các thuật toán đồng phân cụm mờ cải tiến để nâng cao chất lượng và ổn định đồng phân cụm mờ. Đề xuất phương pháp đánh giá xu hướng cụm và kỹ thuật giảm đặc trưng mới để xác định số cụm tối ưu và phân tích dữ liệu ảnh siêu phổ.
7 Chương 2 MỘT SỐ TIẾP CẬN CẢI TIẾN NÂNG CAO CHẤT LƯỢNG VÀ TĂNG TỐC ĐỒNG PHÂN CỤM MỜ 2.1. Thuật toán đồng phân cụm mờ giá trị khoảng Trong khai phá dữ liệu, không phải lúc nào chúng ta cũng có thể trích xuất được tri thức thực sự trong một bộ dữ liệu. Do vậy, đã hình thành nên các bài toán nhận dạng mờ bằng cách mô hình hóa dữ liệu bởi các kỹ thuật mờ. IVFs [75] là một trường hợp đặc biệt của Tập mờ loại 2 khoảng. IVFs được xem như dễ cài đặt và có độ phức tạp tính toán thấp hơn Tập mờ loại 2 khoảng. Trong mục này, luận án đề xuất thuật toán đồng phân cụm mờ giá trị khoảng, ký hiệu là IVFCoC. Bằng cách tích hợp các kỹ thuật của IVFs để xây dựng hàm mục tiêu mới cho đồng phân cụm. 2.1.1. Cơ sở thuật toán IVFCoC Thuật toán IVFCoC được xây dựng bằng cách mở rộng hàm mục tiêu đồng phân cụm mờ tổng quát GFCoC: C N D C N C D J GFCoC (U ,V , P)   u v d  TU  u log u  TV  vcjm log vcjm m m ci cj cij m ci m ci (2.2) c 1 i 1 j 1 c 1 i 1 c 1 j 1 Sử dụng hai tham số mờ m1, m2 để tạo thành vùng không rõ ràng (FOU), tương ứng với các giá trị cận trên và cận dưới của đồng phân cụm mờ giá trị khoảng để đưa ra các hàm mục tiêu khác nhau cần được tối thiểu như sau: C N D C N C D J m1 (U ,V , P   ucim1 vcjm1 dcij  Tu  ucim1 log ucim1  Tv  vcjm1 log vcjm1 (2.4) c 1 i 1 j 1 c 1 i 1 c 1 j 1 C N D C N C D J m2 (U ,V , P)   ucim2 vcjm2 dcij  Tu  ucim2 log ucim2  Tv  vcjm2 log vcjm2 (2.5) c 1 i 1 j 1 c 1 i 1 c 1 j 1 Định lý và bổ đề sau được sử dụng để xác định các thành phần của (2.4) và (2.5). Định lý 2.1. J m1 công thức (2.4) và J m2 trong công thức (2.5) đạt được cực tiểu cục bộ khi U ( m1 )  uci( m1 )  , U ( m2 )  uci( m2 )  , V ( m1 )  vcj( m1 )  , CxN CxN CxD V ( m2 )  vcj( m2 )  , P( m1 )   pcj( m1 )  và P( m2 )   pcj( m2 )  thỏa mãn các công thức (2.6)- CxD CxD CxD
8 (2.11). Trong đó c = 1, 2, …, C, i=1, 2, …, N, j = 1, 2, …, D, C tương ứng là số cụm, N là số mẫu và D là số đặc trưng. Bổ đề 2.1. Cho (U ( m1) ) J m1 (U ( m1) ,V ( m1) ) , (U ( m2 ) ) J m2 (U ( m2 ) ,V ( m2 ) ) trong đó C (m ) U ( m1)  uci 1   (m ) CxN và U ( m2 )  uci 2   (m ) CxN thỏa mãn các điều kiện ràng buộc  uci 1 1 và c 1 C (m )  uci 2 1 (với i=1, 2,..., N), chúng ta có dcij>0, m2>m1>1 thì U ( m1) là tối ưu c 1 cục bộ của (U ( m1) ) và U ( m2 ) là tối ưu của (U ( m2 ) ) , nếu và chỉ nếu (m ) uci 1 và (m ) uci 2 (với c=1, 2,..., C và i=1, 2,..., N) tương ứng được tính toán bởi (2.6) và (2.7). Thuật toán IVFCoC bao gồm các bước lặp để cập nhật các thành phần của hàm mục tiêu, như sau: Thuật toán 2.1: Thuật toán đồng phân cụm mờ giá trị khoảng IVFCoC Đầu vào: Dữ liệu X  xi , xi  R D  , i =1..N , số cụm C, các tham số mờ Tu , Tv , m1 , m2 (1  m1  m2  ), ε, số vòng lặp tối đa τmax. Đầu ra: C cụm kết quả. 1. Khởi tạo: Ma trận hàm thuộc U=[uci] thỏa mãn ràng buộc (2.3), u ci  u ci  uci , τ=1. 2. DO 3. Cập nhật pcjL , pcjR và pcj sử dụng (2.36), (2.37) và (2.38); 4. Tính toán dcij sử dụng (2.1); 5. Cập nhật vcj , vcj và vcj sử dụng (2.33), (2.34) và (2.35); 6. Cập nhật u ci , u ci và uci sử dụng (2.30), (2.31) và (2.32); 7. τ=τ+1; 8. UNTILL ((Max( uci [ ]  uci [ 1])   )|| (= Max )) . Độ phức tạp tính toán của IVFCoC là O(CD2Nτ). 2.1.2. Kết quả thực nghiệm Trong mục này, luận án tiến hành một số thực nghiệm trên ảnh mầu, dữ liệu nhiều đặc trưng và ảnh đa phổ để chứng tỏ hiệu quả của IVFCoC. Kết quả thực nghiệm có trong các hình 2.2-2.3 và các bảng 2.1-2.3.
9 Bảng 2.1: Kết quả phân cụm trên các ảnh mầu theo các chỉ số đánh giá Thuật toán PC PE MS IQI DB-I XB-I  E 19021 FCM 0,56 0,371 25,3 0,9 0,78 0,47 18 FCoC 0,96 0,014 26,7 0,79 0,77 0,42 15 IVFCoC 0,98 0,013 22,3 0,96 0,76 0,40 8 FCM 0,62 0,307 24,6 0,91 0,74 0,40 20 210088 FCoC 0,97 0,012 25,3 0,93 0,73 0,46 17 IVFCoC 0,98 0,012 23,2 0,95 0,73 0,44 9 FCM 0,52 0,387 45,6 0,86 0,67 0,44 18 216081 FCoC 0,86 0,003 42,6 0,8 0,56 0,32 14 IVFCoC 0,99 0,002 34,3 0,95 0,67 0,39 7 FCM 0,58 0,337 34,5 0,88 0,77 0,48 19 220075 FCoC 0,94 0,010 35,9 0,81 0,78 0,49 14 IVFCoC 0,98 0,007 30,8 0,95 0,77 0,47 8 FCM 0,78 0,196 20,9 0,98 0,48 0,27 17 241004 FCoC 0,83 0,003 36,3 0,92 0,49 0,25 12 IVFCoC 0,99 0,002 18,5 0,99 0,49 0,25 6 Hình 2.2: Kết quả phân cụm trên các ảnh mầu
10 Bảng 2.2: Kết quả phân cụm sử dụng sau bộ dữ liệu đa chiều Thuật toán PC PE MSE IQI DB-I XB-I Prec. Rec.  FCM 0,80 0,095 19,1 0,75 0,97 0,62 0.79 0.82 27 Dim256 FCoC 0,90 0,046 8,2 0,97 0,91 0,49 0.97 0.96 18 IVFCoC 0,98 0,008 0,7 0,99 0,88 0,44 0.98 0.99 15 FCM 0,78 0,151 11,2 0,86 1,20 0,47 0.91 0.93 17 Dim512 FCoC 0,93 0,037 6,4 0,98 0,93 0,43 0.93 0.95 13 IVFCoC 0,92 0,048 0,8 0,99 0,83 0,35 0.99 0.98 10 FCM 0,75 0,169 21,1 0,72 0,95 0,59 0.85 0.82 19 Dim1024 FCoC 0,95 0,023 7,0 0,98 0,84 0,59 0.96 0.93 15 IVFCoC 0,95 0,022 3,9 0,99 0,78 0,52 0.98 0.99 12 Hình 2.3. Kết quả phân lớp ảnh về tinh đa phổ: a) NDVI; b) Thuật toán FCM; c) Thuật toán FCoC; d) Thuật toán IVFCoC.
11 Bảng 2.3: Kết quả phân lớp ảnh vệ tinh đa phổ sử dụng các thuật toán phân cụm FCM, FCoC và IVFCoC theo các chỉ số đánh giá Thuật toán PC PE MSE IQI DB-I XB-I  FCM 0,21 0,583 5,7 0,83 0,93 0,82 25 FCoC 0,97 0,014 5,6 0,85 0,89 0,80 17 IVFCoC 0,98 0,008 4,7 0,91 0,75 0,68 11 2.1.3. Phân tích và đánh giá thuật toán IVFCoC Theo kết quả thực nghiệm cho thấy, bằng sự kết hợp giữa IVFs với FCoC, thuật toán IVFCoC đã nâng cao khả năng nhận biết các vấn đề không rõ ràng trong dữ liệu nhiều đặc trưng để đạt được hiệu suất tốt hơn so với các thuật toán phân cụm mờ FCM và FCoC. 2.2. Thuật toán đồng phân cụm mờ lai ghép Để khắc phục hạn chế về nhạy cảm với khởi tạo tâm cụm. Trong mục này, thuật toán đồng phân cụm mờ lai ghép (MHFCoC) đã được đề xuất bằng cách lai ghép thuật toán PSO với thuật toán FCoC. Đồng thời, để tăng tốc phân cụm, thuật toán MHFCoC được cài đặt song song trên bộ xử lý đồ hoạ GPU. 2.2.1. Thuật toán tối ưu bầy đàn Trong mục này, thuật toán PSO được sử dụng để tìm tâm cụm khởi tạo cho thuật toán FCoC. Để nâng cao hiệu suất của thuật toán PSO, luận án đã đề xuất thay thế điều kiện dừng mới có độ phức tạp tính toán thấp hơn. Bằng cách sử dụng chỉ số đánh giá chất lượng cụm PC thay thế hàm mục tiêu JFCoC trong công thức hàm thích nghi như sau: 1 N f (X )   C N (2.39)  u PC 2 ci c 1 i 1 2.2.2. Thuật toán đồng phân cụm mờ Nhằm nâng cao chất lượng và độ ổn định đồng phân cụm, mục này đề xuất sử dụng điều kiện dừng mới cho thuật toán FCoC. 2.2.3. Sơ đồ thuật toán MHFCoC Các bước của thuật toán MHFCoC được chỉ ra trong thuật toán 2.2.
12 Thuật toán 2.2. Thuật toánMHFCoC Đầu vào: Bộ dữ liệu X  xi , xi  R D  , i=1, N , Phân bố PSO P  Pi  , Pi (t )  ( pi ,1 , pi ,2 , ..., pi ,K )T ; i =1, N p , Các tham số bầy đàn: c1= c2=2, =1, PSO, max-PSO; Các tham số đồng phân cụm mờ C, Tu, Tv, FCCI, max-FCCI. Đầu ra: Kết quả phân cụm. Thuật toán PSO: 1. Khởi tạo bầy đàn Np phần tử (P, Pbest và A), fGbest (0) .  ( ) 1  2. While (  fGbest  ) do   PSO  3. For k=1 to Np do 4. Tính toán uci; và fi; 5. If ( fi  f Pbest i ) then Pbest-i=Xi; fPbest-i=fi; ( ) ( ) 8. If ( fi  fGbest ) then fGbest  fi ; PGbest= Pbest-i; 9. Tính vận tốc a={ a 1, a 2 , …, a C}, vị trí p={p1, p2, …, pC}. 10. End For 11. End While FCCI Algorithm: 11. Khởi tạo C cụm từ C vị trí của PGbest và tính U={uci}. τ=1; 12. Do 13. Cập nhật pcj; 14. Cập nhật vcj; 15. Cập nhật uci; 16. Tính f()(P); 17. τ=τ+1; 18. While( ( f ( )  P   1 or    FCCI ) )  FCCI 2.2.4. Tăng tốc thuật toán MHFCoC Để tăng tốc mô hình đồng phân cụm mờ lai ghép khắc phục hạn chế về tốc độ tính toán do độ phức tạp của các thuật toán PSO và FCoC. Luận án đã áp dụng kỹ thuật cài đặt thuật toán PSO song song trên GPU. 2.2.5. Kết quả thực nghiệm Thực nghiệm được tiến hành trên một số bộ dữ liệu khác nhau. Kết quả thực nghiệm có trong các bảng 2.7-2.10 và các hình 2.8 và 2.9.
13 Bảng 2.7: Kết quả phân cụm trên các bộ dữ liệu đa chiều sử dụng các mô hình thuật toán FCM, FCoC, IVFCoC, HFCoC và MHFCoC Dữ Thuật toán PC PE MSE IQI DB-I XB-I Prec. Rec.  liệu FCM 0,61 0,271 12,02 0,73 1,59 1,11 0.95 0.93 19 FCoC 0,91 0,047 8,50 0,92 1,17 0,93 0.95 0.96 15 Spambase IVFCoC 0,93 0,014 5,12 0,94 0,84 0,83 0.98 0.97 13 HFCoC 0,92 0,016 7,48 0,91 0,92 0,96 0,98 0,97 10 MHFCoC 0,94 0,011 5,18 0,95 0,67 0,69 0.98 0.98 8 FCM 0,93 0,013 9,63 0,94 1,96 0,63 0.87 0.89 13 FCoC 0,93 0,014 9,63 0,94 1,55 0,63 0.95 0.94 12 Ecoli IVFCoC 0,98 0,002 9,60 0,98 1,83 0,57 0.97 0.97 10 HFCoC 0,96 0,005 9,60 0,97 1,54 0,93 0,98 0,97 9 MHFCoC 0,98 0,001 9,61 0,99 1,36 0,86 0.98 0.98 5 FCM 0,55 0,312 6,36 0,96 1,55 0,38 0.93 0.94 18 FCoC 0,88 0,069 7,47 0,89 1,79 0,54 0.95 0.96 15 Landsat IVFCoC 0,98 0,002 6,25 0,94 1,35 0,39 0.98 0.98 13 HFCoC 0,97 0,009 7,67 0,94 1,52 0,58 0,96 0,97 10 MHFCoC 0,99 0,001 6,18 0,96 1,21 0,68 0.98 0.98 8 Bảng 2.8: Kết quả sử dụng FCM, FCoC, IVFCoC, HFCoC và MHFCoC Thuật toán PC PE MSE IQI DB-I XB-I Prec. Rec.  FCM 0,80 0,095 19,1 0,75 0,97 0,62 0.79 0.82 27 FCoC 0,90 0,046 8,2 0,97 0,91 0,49 0.97 0.96 18 Dim256 IVFCoC 0,98 0,008 0,7 0,99 0,88 0,44 0.98 0.99 15 HFCoC 0,95 0,023 7,5 0,98 0,93 0,42 0,98 0,97 13 MHFCoC 0,98 0,008 5,3 0,99 0,52 0,47 0.99 0.99 12 FCM 0,78 0,151 11,2 0,86 1,20 0,47 0.91 0.93 17 FCoC 0,93 0,037 6,4 0,98 0,93 0,43 0.93 0.95 13 Dim512 IVFCoC 0,92 0,048 0,8 0,99 0,83 0,35 0.99 0.98 10 HFCoC 0,95 0,023 2,9 0,96 0,88 0,39 0,96 0,95 9 MHFCoC 0,95 0,023 1,0 0,99 0,78 0,40 0.99 0.99 11 FCM 0,75 0,169 21,1 0,72 0,95 0,59 0.85 0.82 19 FCoC 0,95 0,023 7,0 0,98 0,84 0,59 0.96 0.93 15 Dim1024 IVFCoC 0,95 0,022 3,9 0,98 0,78 0,52 0.98 0.99 12 HFCoC 0,96 0,018 6,0 0,98 0,79 0,56 0,97 0,97 10 MHFCoC 0,98 0,009 4,0 0,98 0,70 0,59 0.99 0.99 11
14 Hình 2.8: Kết quả phân cụm a) NVDI, b) FCM, c) FCoC, d) IVFCoC, e) HFCoC và f) MHFCoC. Bảng 2.10: Các kết quả phân lớp ảnh về tinh đa phổ sử dụng các thuật toán FCM, FCoC, IVFCoC, HFCoC và MHFCoC Thuật toán PC PE MSE IQI DB-I XB-I  FCM 0,79 0,137 11,2 0,83 3,50 1,18 21 FCoC 0,95 0,0278 9,2 0,94 1,26 0,98 18 IVFCoC 0,97 0,006 7,1 0,97 1,05 0,67 12 HFCoC 0,97 0,007 8,5 0,96 1,59 0,84 9 MHFCoC 0,98 0,002 6,5 0,96 0.93 0,56 5 2.2.6. Phân tích và đánh giá hiệu quả của thuật toán MHFCoC Theo kết quả phân cụm, thuật toán MHFCoC được xem là hội tụ nhanh hơn, hiệu suất phân cụm cao hơn so với FCM, FCoC, IVFCoC và HFCoC. Ngoài ra, để tăng tốc đồng phân cụm, luận án đã cài đặt các thuật toán phân cụm trên các mô hình lập trình song song khác nhau. Kết quả thực nghiệm trong bảng 2.11 cho thấy các thuật toán đồng phân cụm mờ
15 có thể tăng tốc bằng cách cài đặt trên các mô hình lập trình song song. Bảng 2.11: Thời gian xử lý trên các mô hình lập trình song song và các mô hình phân cụm khác nhau Mô hình lập Mô hình phân cụm Dữ liệu FCM FCoC IVFCoC HFCoC MHFCoC trình Tuần tự 45,08 5,78 79,60 6,23 4,61 Dim256 Đa vi xử lý 14,54 1,65 25,68 2,15 1,44 MPI 7,91 0,95 14,21 1,13 0,82 GPU 1,50 1,21 2,16 2,08 1,68 Tuần tự 69,83 9,78 96,75 11,22 7,85 Dim512 Đa vi xử lý 23,28 3,06 33,36 3,87 2,45 MPI 8,20 1,69 18,25 2,24 1,51 GPU 2,42 2,02 2,64 2,99 2,16 Tuần tự 118,89 21,32 137,45 29,59 21,01 Dim1024 Đa vi xử lý 41,00 6,88 44,34 10,20 6,37 MPI 21,23 3,61 26,43 5,58 3,82 GPU 3,68 3,03 4,32 5,07 3,60 Tuần tự 1.235,23 985,27 1.587,16 2.560,54 2.120,38 Ảnh đa phổ Đa vi xử lý 398,46 281,51 495,99 825,98 605,82 MPI 224,59 156,39 299,46 492,41 400,07 GPU 205,87 151,58 255,99 406,43 326,21 2.3. Kết luận chương 2 Chương II đã đề xuất hai thuật toán đồng phân cụm mờ cải tiến nâng cao chất lượng và ổn định phân cụm. Thứ nhất, thuật toán IVFCoC được đề xuất bằng cách kết hợp FCoC với IVFs [3], [4]. Thứ hai, thuật toán MHFCoC được đề xuất bằng cách lai ghép thuật toán PSO với thuật toán FCoC để khắc phục hạn chế về nhạy cảm với khởi tạo tâm cụm và độ phức tạp tính toán. Ngoài ra, thuật toán MHFCoC được cài đặt song song trên GPU để tăng tốc đồng phân cụm mờ. Thực nghiệm được tiến hành trên các bộ dữ liệu đa chiều, nhiều đặc trưng và ảnh đa phổ cho thấy các thuật toán IVFCoC và MHFCoC đạt hiệu quả tốt hơn so với một vài thuật toán đã được đề xuất trước đó.
16 Chương 3 ĐỒNG PHÂN CỤM MỜ GIẢM CHIỀU ẢNH SIÊU PHỔ 3.1. Thuật toán đánh giá xu hướng cụm Đánh giá xu hướng cụm là một phương pháp xác định xem một bộ dữ liệu có chứa các cụm có ý nghĩa hay không. Các câu hỏi thường được đặt ra là: Có bao nhiêu cụm? Dữ liệu được phân bố như thế nào? Trong mục này, luận án đề xuất một phương pháp đánh giá xu hướng cụm mới dựa vào chỉ số Silhouette được gọi là thuật toán SACT. 3.1.1. Phương pháp đánh giá xu hướng cụm bằng trực quan 3.1.2. Thuật toán đánh giá xu hướng cụm tự động SACT Ý tưởng của thuật toán SACT như sau: Xây dựng cây khung tối thiểu. Sau đó, từng bước băm cây khung tối thiểu theo lần lượt các cạnh lớn nhất. Mỗi lần băm hình thành một nhánh mới tương ứng với một cụm mới được tách ra, với một phương án cụm ứng viên. Sử dụng chỉ số đánh giá cụm Silhouette để định lượng chất lượng cụm cho từng phương án. Cuối cùng, xác định số cụm tương ứng với chỉ số Silhouette cao nhất. Thuật toán 3.2. Thuật toán đánh giá xu hướng cụm SACT Đầu vào: Bộ dữ liệu kích thước N để xây dựng ma trận tương quan R kích thước NxN, số cụm tối đa Cmax. Đầu ra: Số cụm phù hợp và các trung tâm cụm tương ứng. 1. Khởi tạo K={1, 2, …, N}; Lựa chọn (i, j) arg max{dpq} với p, q K. Gán E={(i,j)}; I={i} và J=K-{i}. 2. Lặp đối với t=2, 3, …, N Lựa chọn (i, j) arg max{dpq} với pI, qJ; Gán E=E{(i,j)}; thay thế II{j} và JJ-{j}. 3. Khởi tạo T={E}, S0=0. Lặp đối với c=2, …, Cmax 3.1. Lựa chọn (k, i, ni) với T={T1, …, Ti, …Tc} và ekarg min{T}, ekTi. 3.2. Gán Tc+1=. Di chuyển ek+1, ek+2, …, eniTi tới Tc+1. Băm ekTi; gán T=TTc+1. 3.3. Tính chỉ số Silhouette Sc. Nếu Sc>Sc-1 lưu số cụm co=c và trạng thái phân bố cụm T, ngược lại quay về bước 3.1. 4. Xây dựng biểu đồ chỉ số Silhouette với số cụm. 5. Xác định số cụm dựa vào biểu đồ chỉ số Silhouette với số cụm.
17 3.1.3. Thực nghiệm đánh giá xu hướng cụm Luận án đã tiến hành một số thực nghiệm đánh giá xu hướng cụm sử dụng thuật toán SACT trên một số bộ dữ liệu mẫu, dữ liệu được gán nhãn và ảnh mầu. Đồng thời, luận án đánh giá hiệu suất của các thuật toán phân cụm sử dụng tâm cụm thu được từ thuật toán SACT so sánh với tâm cụm khởi tạo ngẫu nhiên. Kết quả thực nghiệm được chỉ ra trong các bảng 3.2, 3.3, 3.4 và các hình 3.3 và 3.4 cho thấy thuật toán SACT đạt được hiệu quả tốt trong việc xác định số cụm dữ liệu và tâm cụm khởi tạo so với một vài phương pháp đã đề xuất trước đây. Hình 3.3: Kết quả thực nghiệm tìm số cụm trên các bộ dữ liệu Dim032- Dim1024 sử dụng thuật toán SACT và phương pháp trong [39].
18 Bảng 3.4: Kết quả phân cụm sử dụng các thuật toán FCM, FCoC, IVFCoC và SACT với tâm cụm khởi tạo ngẫu nhiên và tâm cụm khởi tạo từ SACT Thuật toán FCM FCM- SACT FCoC FCoC- SACT IVFCoC IVFCoC- SACT PC 0.80 0.89 0.90 0.95 0.98 0.99 Dim1024 Dim512 Dim256 MSE 19.10 12.20 8.22 6.43 0.66 0.62 IQI 0.75 0.85 0.97 0.98 0.99 0.99 PC 0.78 0.90 0.93 0.95 0.91 0.98 MSE 11.23 9.45 6.42 4.32 0.84 0.53 IQI 0.86 0.92 0.98 0.99 0.99 0.99 PC 0.75 0.91 0.95 0.97 0.97 0.99 MSE 21.12 15.13 7.02 5.17 3.9 1.89 IQI 0.72 0.89 0.98 0.98 0.99 0.99 3.1.4. Mô hình ảnh siêu phổ thưa 3.2. Thuật toán đồng phân cụm mờ giảm đặc trưng Trong các ứng dụng phân tích dữ liệu đa chiều, nhiều đặc trưng như ảnh siêu phổ, thường phát sinh các vấn đề như giảm chiều, giảm đặc trưng, lựa chọn kênh,… để nâng cao hiệu quả về chất lượng cũng như tốc độ xử lý. Trong mục này, luận án đề xuất thuật toán đồng phân cụm mờ giảm đặc trưng, ký hiệu là FRFCoC. 3.2.1. Kỹ thuật giảm đặc trưng trong phân cụm mờ Hàm mục tiêu của thuật toán FRFCM được chỉ ra trong công thức (3.5). C N D D J (U ,V , W)   ucim j w j (x ij  pcj ) 2  Tw  ( w j log j w j ) (3.5) c 1 i 1 j 1 j 1 3.2.2. Thuật toán đồng phân cụm mờ giảm đặc trưng Luận án đã đề xuất thuật toán đồng phân cụm mờ giảm chiều FRFCoC. Hàm mục tiêu của thuật toán FRFCoC được đề xuất như sau, C N D C N J FRFCoC (U ,V , P, W,  )   uci vcj j w j d cij  Tu  uci log uci  C D D c 1 i 1 j 1 c 1 i 1 (3.11) Tv  vcj log vcj  Tw  w j log  j w j c 1 j 1 j 1 Thuật toán FRFCoC được chỉ ra như sau.