Tóm tắt Luận án 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

Luận án đã đề xuất ba thuật toán đồng phân cụm mờ cải tiến và một thuật toán đánh giá xu hướng cụm để khắc phục một số hạn chế tồn tại của đồng phân cụm mờ. Thứ nhất, luận án đã đề xuất thuật toán đồng phân cụm mờ giá trị khoảng IVFCoC để cải thiện chất lượng phân cụm. Dựa vào lý thuyết giải tích, luận án đã đề xuất một định lý và một bổ đề để chứng minh tính đúng đắn của thuật toán đã đề xuất. Thực nghiệm đã được tiến hành trên ảnh mầu, ảnh đa phổ và dữ liệu nhiều đặc trưng. Kết quả thực nghiệm đã chứng tỏ thuật toán IVFCoC đạt được hiệu quả tốt hơn một vài thuật toán đã được đề xuất trước đó như FCM và FCoC

pdf28 trang | Chia sẻ: tueminh09 | Ngày: 25/01/2022 | Lượt xem: 441 | Lượt tải: 1download
Bạn đang xem trước 20 trang tài liệu Tóm tắt Luận án 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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. Hình 1.1: Sơ đồ phân nhóm các thuật toán phân cụm truyền thống Hình 1.2: Sơ đồ phân nhóm các thuật toán phân cụm hiện đại Các thuật toán phân cụm truyền thống Phân cụm dựa trên phân vùng Phân cụm dựa thứ bậc Phân cụm dựa trên lý thuyết mờ Phân cụm dựa trên phân bố Phân cụm dựa trên mật độ Phân cụm dựa trên lý thuyết đồ thị Phân cụm dựa trên lưới Phân cụm dựa trên lý thuyết hình học Phân cụm dựa trên mô hình Các thuật toán phân cụm hiện đại Phân cụm dựa lan truyền nhân tạo Phân cụm dựa lan truyền ngược Phân cụm dữ liệu không gian Phân cụm luồng dữ liệu Phân cụm dữ liệu lớn Phân cụm dựa trên nhân Phân cụm dựa trí tuệ bầy đàn Phân cụm dựa lý thuyết lượng tử Phân cụm dựa lý thuyết đồ thị phổ 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. 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. Các kỹ thuật phân cụm mờ Phân cụm mờ trọng số Phân cụm mờ bán giám sát Phân cụm mờ dựa trên nhân Thuật toán Phân cụm mờ Phân cụm mờ trực cảm Đồng phân cụm mờ trọng số Đồng phân cụm mờ giảm chiều Đồng phân cụm mờ bán giám sát Thuật toán Đồng phân cụm mờ Đồng phân cụm mờ loại 2 Phân cụm mờ loại 2 5 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). 2 1 1 ( ; ; ) C N m FCM ci ci c i J U P X u d    (1.14) Dữ liệu Xác định tâm cụm khởi tạo Phân cụm dữ liệu Đánh giá chất lượng phân cụm và hợp nhất các cụm Hiển thị kết quả Cụm 1 Kết quả đánh giá cụm Kết quả hợp nhất các cụm Cụm 2 Cụm C Tiền xử lý dữ liệu Xác định số cụm Pha 1 Pha 2 Pha 3 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: 1 1 1 1 1 1 1 ( , , ) log log C N D C N C D FCoC ci cj cij U ci ci V cj cj c i j c i c j J U V P u v d T u u T v v             (1.16) 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: 1 1 1 1 1 1 1 ( , , ) log log C N D C N C D m m m m m m GFCoC ci cj cij U ci ci V cj cj c i j c i c j J U V P u v d T u u T v v             (2.2) 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: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ( , , log log C N D C N C D m m m m m m m ci cj cij u ci ci v cj cj c i j c i c j J U V P u v d T u u T v v             (2.4) 2 2 2 2 2 2 2 1 1 1 1 1 1 1 ( , , ) log log C N D C N C D m m m m m m m ci cj cij u ci ci v cj cj c i j c i c j J U V P u v d T u u T v v             (2.5) Đị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. 1m J công thức (2.4) và 2m J trong công thức (2.5) đạt được cực tiểu cục bộ khi 1 1( ) ( )ci x m m C N U u    , 2 2( ) ( ) ci x m m C N U u    , 1 1( ) ( ) cj x m m C D V v    , 2 2( ) ( ) cj x m m C D V v    , 1 1( ) ( ) cj x m m C D P p    và 2 2( ) ( ) cj x m m C D P p    thỏa mãn các công thức (2.6)- 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 ( ) ( ) ( )1 1 1( ) ( , )1 m m mU J U Vm  , ( ) ( ) ( )2 2 2( ) ( , )2 m m mU J U Vm  trong đó ( )( ) 11 ci mmU u CxN      và ( )( ) 22 ci mmU u CxN      thỏa mãn các điều kiện ràng buộc ( )1 1 1 C m uci c   và ( )2 1 1 C m uci c   (với i=1, 2,..., N), chúng ta có dcij>0, m2>m1>1 thì ( )1mU là tối ưu cục bộ của ( )1( )mU và ( )2mU là tối ưu của ( )2( )mU , nếu và chỉ nếu ( )1muci và ( )2muci (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  , , =1..Di iX x x R i N  , số cụm C, các tham số mờ 1 2 1 2 ,(, ) , , 1u vT T m m m m    ε, 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), ci ci ciu u u  , τ=1. 2. DO 3. Cập nhật ,L Rcj cjp p 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 ,cj cjv v và vcj sử dụng (2.33), (2.34) và (2.35); 6. Cập nhật ,ci ciu u và uci sử dụng (2.30), (2.31) và (2.32); 7. τ=τ+1; 8. UNTILL (( ( [ ] [ 1]) )|| (= ))ci ci MaxMax u u      . Độ phức tạp tính toán của IVFCoC là O(CD 2 Nτ). 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 E IQI DB-I XB-I  1 9 0 2 1 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 2 1 0 0 8 8 FCM 0,62 0,307 24,6 0,91 0,74 0,40 20 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 2 1 6 0 8 1 FCM 0,52 0,387 45,6 0,86 0,67 0,44 18 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 2 2 0 0 7 5 FCM 0,58 0,337 34,5 0,88 0,77 0,48 19 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 2 4 1 0 0 4 FCM 0,78 0,196 20,9 0,98 0,48 0,27 17 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.  D im 2 5 6 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 IVFCoC 0,98 0,008 0,7 0,99 0,88 0,44 0.98 0.99 15 D im 5 1 2 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 IVFCoC 0,92 0,048 0,8 0,99 0,83 0,35 0.99 0.98 10 D im 1 0 2 4 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 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: 2 1 1 1 ( ) C N ci c i N f X PC u      (2.39) 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  , , i=1,Di iX x x R N  , Phân bố PSO   ( ) ,1 ,2 ,K, ( , , ..., ) ; =1, t T i i i i i pP P P p p p i N  , 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), (0) Gbestf . 2. While ( ( ) 1 Gbest PSO f         ) do 3. For k=1 to Np do 4. Tính toán uci; và fi; 5. If ( i Pbest if f  ) then Pbest-i=Xi; fPbest-i=fi; 8. If ( ( )i Gbestf f  ) then ( )Gbest if f   ; PGbest= Pbest-i; 9. Tính vận tốc a={ a1, a2, , aC}, 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(  ( ) 1 ( or )FCCI FCCI f P      ) 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ữ liệu Thuật toán PC PE MSE IQI DB-I XB-I Prec. Rec.  S p am b as e 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 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 E co li 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 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 L an d sa t 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 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.  D im 2 5 6 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 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 D im 5 1 2 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 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 D im 1 0 2 4 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 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 8 11,2 0,83 3,50 1,18 21 FCoC 0,95 0,027 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 Dữ liệu Mô hình lập trình Mô hình phân cụm FCM FCoC IVFCoC HFCoC MHFCoC D im 2 5 6 Tuần tự 45,08 5,78 79,60 6,23 4,61 Đ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 D im 5 1 2 Tuần tự 69,83 9,78 96,75 11,22 7,85 Đ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 D im 1 0 2 4 Tuần tự 118,89 21,32 137,45 29,59 21,01 Đ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 Ả n h đ a p h ổ Tuần tự 1.235,23 985,27 1.587,16 2.560,54 2.120,38 Đ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 D im 2 5 6 PC 0.80 0.89 0.90 0.95 0.98 0.99 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 D im 5 1 2 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 D im 1 0 2 4 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). 2 ij w 1 1 1 1 ( , , W) w (x ) ( ) C N D D m ci j j cj j j j c i j j J U V u p T w log w          (3.5) 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, RFCoC 1 1 1 1 1 w 1 1 1 ( , , , W, ) w log log w log w C N D C N F ci cj j j cij u ci ci c i j c i C D D v cj cj j j j c j j J U V P u v d T u u T v v T                    (3.11) Thuật toán FRFCoC được chỉ ra như sau. 19 Thuật toán 3.4. Thuật toán đồng phân cụm mờ giảm chiều FRFCoC Đầu vào: Bộ dữ liệu  , , i=1..NDi iX x x R  , số cụm C, các tham số mờ w,, , u v TT T ε, số vòng lặp tối đa τmax. Đầu ra: Kết quả phân cụm. 1. τ=1. 2. Khởi tạo uci thỏa mãn (3.12); 3. DO 4. Tính toán j sử dụng (3.10); 5. Cập nhật pcj sử dụng (3.21); 6. Cập nhật vcj sử dụng (3.19); 7. Cập nhật uci sử dụng (3.18); 8. Cập nhật wj sử dụng (3.23); 9. Ước lượng Dr ; 10. Cập nhật D (new) = D − Dr; 11. τ=τ+1; D=D (new) 12. UNTIL ( ( ) ( 1)W Wt t   hoặc τ≥ τmax). Độ phức tạp tính toán của thuật toán FRFCoC là O(CD 2 Nτ). 3.2.3. Kết quả thực nghiệm Mục này trình bày các kết quả thực nghiệm trên các bộ dữ liệu tổ hợp số và ảnh siêu phổ sử dụng các mô hình thuật toán phân cụm FCM, FRFCM, FCoC, IVFCoC, MHFCoC và HFRFCoC. Để đánh giá chất lượng của các thuật toán phân cụm này, luận án sử dụng các chỉ số đánh giá PC, MSE, IQI, DI, DB-I, XB-I. Kết quả thực nghiệm được chỉ ra trong các bảng 3.5, 3.6, 3.8, 3.9 và hình 3.8. Bảng 3.5: Kết quả giảm đặc trưng sử dụng thuật toán FRFCM, FRFCoC Dữ liệu Số đặc trưng ban đầu FRFCM FRFCoC Dim256 256 49(19,14%) 53(20.7%) Dim512 512 87(16,99%) 92(17.9%) Dim1024 1024 105(10,25%) 112(10.9%) 20 Bảng 3.6: Kết quả phân cụm trên các bộ dữ liệu Dim032-Dim1024 sử dụng các thuật toán FCM, FRFCM, FCoC, IVFCoC và FRFCoC Thuật toán PC PE MSE IQI DB-I XB-I Prec. Rec.  D im 2 5 6 FCM 0,80 0,095 19,1 0,75 0,97 0,62 0.79 0.82 27 FRFCM 0,91 0,040 11,4 0,96 0,97 0,45 0.92 0.95 7 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 FRFCoC 0,98 0,009 1,6 0,98 0,41 0,07 0.98 0.99 4 D im 5 1 2 FCM 0,78 0,151 11,2 0,86 1,20 0,47 0.91 0.93 17 FRFCM 0,91 0,039 8,4 0,93 0,99 0,48 0.96 0.92 9 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 FRFCoC 0,96 0,020 2,2 0,99 0,53 0,15 0.98 0.99 3 D im 1 0 2 4 FCM 0,75 0,169 21,1 0,72 0,95 0,59 0.85 0.82 19 FRFCM 0,93 0,037 14,9 0,92 0,90 0,55 0.97 0.90 9 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 FRFCoC 0,98 0,011 4,3 0,99 0,56 0,17 0.99 0.99 3 Bảng 3.8: Kết quả phân cụm ảnh siêu phổ sử dụng các thuật toán FCM, FRFCM, FCoC, và FRFCoC Dữ liệu PC MSE IQI XB-I DB-I  G o M W s FCM 0,42 76,4 0,85 0,69 1,98 18 FRFCM 0,61 75,3 0,96 0,43 1,75 6 FCoC 0,92 76,8 0,94 1,15 2,15 14 FRFCoC 0,97 73,8 0,98 0,28 0,75 3 G s FCM 0,3 238,1 0,78 1,15 2,03 21 FRFCM 0,58 231,3 0,94 0,35 1,76 8 FCoC 0,91 240,1 0,85 1,1 1,94 19 FRFCoC 0,96 215,2 0,95 0,35 1,43 3 A & V s FCM 0,23 163,1 0,84 0,71 1,26 17 FRFCM 0,48 145,9 0,95 0,16 0,88 9 FCoC 0,87 159,2 0,91 0,93 0,96 9 FRFCoC 0,97 136,5 0,95 0,16 0,82 3 21 Bảng 3.9: Kết quả giảm đặc trưng dữ liệu ảnh siêu phổ sử dụng FRFCM và FRFCoC Dữ liệu Số đặc trưng ban đầu FRFCM FRFCoC GoMWs 360 37(10,28%) 41 (11.4%) Gs 357 29(8,12%) 32 (8,9%) A&Vs 360 30(8,33%) 31(8.6%) Hình 3.8: Kết quả phân cụm ảnh siêu phổ a) Tổ hợp mầu ENVI; b)FCM; c) FRFCM; d) FCoC; e) FRFCoC 22 3.2.4. Phân tích và đánh giá hiệu quả thuật toán FRFCoC Theo các kết quả phân cụm, thuật toán FRFCoC được đánh giá là hiệu quả hơn các thuật toán FCM, FRFCM, IVFCoC và FCoC, hiệu suất giảm đặc trưng của FRFCoC đạt được từ 8% đến 20%. Ngoài ra, số vòng lặp để FRFCoC hội tụ ít hơn so với các thuật toán không sử dụng kỹ thuật giảm chiều. Ngoài ra, kết quả thực nghiệm cũng cho thấy hiệu quả của SACT và mô hình ảnh siêu phổ thưa trong việc đánh giá xu hướng cụm ảnh siêu phổ. Tuy nhiên, đối với các bộ dữ liệu có số đặc trưng thấp, thuật toán FRFCoC chưa thể hiện tốt hơn so với thuật toán IVFCoC. Mặc dù thuật toán FRFCM sử dụng kỹ thuật giảm chiều đạt được hiệu suất tốt hơn thuật toán FCM. Nhưng hiệu suất của FRFCM vẫn thấp hơn so với FCoC. Điều này càng chứng tỏ các thuật toán đồng phân cụm mờ nói chung phù hợp hơn các thuật toán Phân cụm mờ trong phân cụm dữ liệu đa chiều, nhiều đặc trưng. 3.3. Kết luận chương 3 Trong chương này, luận án đã đề xuất thuật toán đồng phân cụm mờ giảm đặc trưng ứng dụng phân đoạn ảnh siêu phổ FRFCoC [5]. Thuật toán FRFCoC sử dụng phương pháp Entropy trong lý thuyết xác suất thống kê để hình thành kỹ thuật giảm đặc trưng đối với dữ liệu đa chiều, nhiều đặc trưng. Thuật toán đánh giá xu hướng cụm SACT [6], [7] cũng được đề xuất cùng với mô hình biểu diễn ảnh siêu phổ thưa để xác định số cụm phù hợp trên dữ liệu ảnh siêu phổ. Thực nghiệm được tiến hành trên các bộ dữ liệu ảnh siêu phổ. Kết quả thực nghiệm đã chứng tỏ các thuật toán được đề xuất đạt được hiệu suất tốt hơn so với một vài thuật toán đã đề xuất trước đó. Ngoài ra, thực nghiệm cũng được tiến hành trên một số bộ dữ liệu tổ hợp số gán nhãn để chứng tỏ tính đúng đắn và chính xác của thuật toán SACT về xác định số cụm phù hợp; hiệu suất giảm chiều của thuật toán FRFCoC trên các bộ dữ liệu đa chiều, nhiều đặc trưng. 23 KẾT LUẬN Kết quả nghiên cứu của luận án: Luận án đã đề xuất ba thuật toán đồng phân cụm mờ cải tiến và một thuật toán đánh giá xu hướng cụm để khắc phục một số hạn chế tồn tại của đồng phân cụm mờ. Thứ nhất, luận án đã đề xuất thuật toán đồng phân cụm mờ giá trị khoảng IVFCoC để cải thiện chất lượng phân cụm. Dựa vào lý thuyết giải tích, luận án đã đề xuất một định lý và một bổ đề để chứng minh tính đúng đắn của thuật toán đã đề xuất. Thực nghiệm đã được tiến hành trên ảnh mầu, ảnh đa phổ và dữ liệu nhiều đặc trưng. Kết quả thực nghiệm đã chứng tỏ thuật toán IVFCoC đạt được hiệu quả tốt hơn một vài thuật toán đã được đề xuất trước đó như FCM và FCoC. Thứ hai, luận án đã đề xuất thuật toán đồng phân cụm mờ lai ghép MHFCoC để 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. Trong thuật toán MHFCoC, thuật toán PSO được sử dụng để khởi tạo tâm cụm và thuật toán FCoC được sử dụng để đồng phân cụm dữ liệu. Luận án đã cải tiến hàm thích nghi của các thuật toán PSO và FCoC bằng cách sử dụng chỉ số PC để xác định hàm thích nghi Fitness. Ngoài ra, luận án cũng nghiên cứu để tăng tốc độ đồng phân cụm mờ bằng cách sử dụng kỹ thuật truyền thông điệp MPI và kỹ thuật xử lý đồ họa GPU. Thực nghiệm được tiến hành trên ảnh đa phổ và dữ liệu nhiều đặc trưng. Kết quả thực nghiệm đã chứng tỏ thuật toán MHFCoC đạt được hiệu quả tốt hơn các thuật toán đã được đề xuất trước đó như FCM, FCoC và HFCoC. Thứ ba, luận án đã đề xuất thuật toán đồng phân cụm mờ giảm chiều FRFCoC để phân cụm ảnh siêu phổ. Ngoài ra, thuật toán đánh giá xu hướng cụm SACT cũng được đề xuất để xác định số cụm phù hợp và tâm cụm khởi tạo đồng thời. Thực nghiệm được tiến hành trên bộ dữ tổ hợp số và ảnh siêu phổ. Kết quả thực nghiệm đã chứng tỏ thuật toán FRFCoC đạt được hiệu suất tốt hơn so với các thuật toán FCM, FRFCM và FCoC về giảm chiều và chất lượng phân cụm. 24 Đóng góp mới của luận án: Đóng góp của luận án bao gồm: 1. Đề xuất thuật toán đồng phân cụm mờ loại 2 khoảng [CT3], đồng phân cụm mờ giá trị khoảng [CT4], để nâng cao chất lượng phân cụm dữ liệu đa chiều. 2. Đề xuất thuật toán đồng phân cụm mờ lai ghép nâng cao ổn định chất lượng phân cụm sử dụng thuật toán tối ưu bầy đàn PSO. 3. Đề xuất thuật toán đánh giá xu hướng cụm SACT để xác định số cụm phù hợp [CT6], [CT7]. 4. Đề xuất thuật toán giảm đặc trưng cho đồng phân cụm mờ trên dữ liệu đa chiều, nhiều đặc trưng [CT5]. 5. Tăng tốc đồng phân cụm mờ sử dụng kỹ thuật MPI [CT1] và GPU [CT2]. Hướng nghiên cứu tiếp theo: Một số định hướng nghiên cứu như sau: 1. Nghiên cứu cải tiến nâng cao chất lượng và tăng tốc thuật toán SACT trong đánh giá xu hướng cụm dữ liệu kích thước lớn. 2. Nghiên cứu áp dụng các thuật toán đồng phân cụm mờ cải tiến để phát hiện đối tượng và nhận dạng mục tiêu trong ảnh siêu phổ. DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ CT1. Ngô Thành Long và Phạm Văn Nhã, Phân tích và thiết kế thuật toán đồng phân cụm mờ song song sử dụng MPI để phân đoạn ảnh, Tạp chí Khoa học và Kỹ thuật 179, trang 369-379, 2016. CT2. V.N. Pham, L. T. Ngo, V. H. Vu, Speedup of Fuzzy Co-Clustering algorithm for image segmentation on Graphic Processing Unit, SoICT 15, pp. 83-89, 2015 (DOI: 10.1145/2833258.2833306). CT3. V.N. Pham, L.T. Ngo, Interval Type-2 Fuzzy Co-Clustering Algorithm, 2015 IEEE International Conference on Fuzzy Systems, pp. 83-89, 2015 (DOI: 10.1109/FUZZ-IEEE.2015.7337960). CT4. V.N. Pham, L. T. Ngo, W. Pedrycz, Interval-valued fuzzy set approach to fuzzy co-clustering for data classification, Knowledge-Based Systems (SCI, Q1, IF: 4.529), Vol. 107, pp. 1–13, 2016 (DOI: https://doi.org/10.1016/j.knosys.2016.05.049). CT5. V.N. Pham, L.T. Ngo, D.T. Nguyen, Feature-Reduction Fuzzy Co- Clustering algorithm for hyperspectral image clustering, IEEE Conference on Fuzzy Systems, pp. 1-6, 2017 (DOI: 10.1109/FUZZ-IEEE.2017.8015643). CT6. Pham Van Nha, Ngo Thanh Long, Pham The Long, A new cluster tendency assessment method for simultaneous appropriate number of cluster and centroids determining, Hội thảo quốc gia lần thứ XX: Một số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông, pp. 6-11, 2017. CT7. V. N. Pham, L. T. Pham, D.T. Nguyen, L. T. Ngo, A new cluster tendency assessment method for fuzzy co-clustering in hyperspectral image analysis, Neurocomputing (SCIE, Q1, IF: 3.317), pp. 1-30, 2018 (In Press, Available online 7 May 2018).

Các file đính kèm theo tài liệu này:

  • pdftom_tat_luan_an_nghien_cuu_mot_so_thuat_toan_dong_phan_cum_m.pdf
  • pdfTomTat LuanAn NCS PhamVanNha_English.pdf
Luận văn liên quan