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 thứ bậc
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 lý thuyết đồ thị
Phân cụm dựa trên mật độ
Phân cụm dựa trên phân vùng
Phân cụm dựa trên phân bố
Phân cụm dựa trên mô hình
Phân cụm dựa trên lý thuyết mờ
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ựa lý thuyết lượng tử
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 dựa lý thuyết đồ thị phổ
Phân cụm dữ liệu lớn
Phân cụm dựa lan truyền nhân tạo
Phân cụm luồng dữ liệu
Phân cụm dựa trí tuệ bầy đàn
Phân cụm dựa trên nhâ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 Phân cụm mờ
Thuật toán Đồng phân cụm mờ
Phân cụm mờ bán giám sát
Phân cụm mờ dựa trên nhân
Phân cụm mờ trực cảm
Phân cụm mờ loại 2
Đồng phân cụm mờ loại 2
Đồng phân cụm mờ giảm chiều
Đồng phân cụm mờ bán giám sát
Đồng phân cụm mờ trọng số
Phân cụm mờ trọng số
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
Pha 1
Xác định số cụm
Dữ liệu Tiền xử lý dữ liệu Xác định tâm cụm khởi tạo
Pha 2
Phân cụm dữ liệu
Cụm C
Cụm 1
Cụm 2
Đánh giá chất lượng phân cụm và hợp nhất các cụm
Kết quả đánh giá cụm
Kết quả hợp nhất các cụm
Pha 3
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).
(1.14)
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.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:
(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:
(2.4)
(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.
công thức (2.4) và
trong công thức (2.5) đạt được
cực
tiểu cục bộ khi
,
,
,
,
và
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
,
trong đó
và
thỏa mãn các điều kiện ràng buộc
và
là tối ưu
(với i=1, 2,..., N), chúng ta có dcij>0, m2>m1>1 thì
cục bộ của
và
là tối ưu của
, nếu và chỉ nếu
và
(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 , số cụm C, các tham số mờ Đầu vào: Dữ liệu
ε, 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),
, τ=1.
và pcj sử dụng (2.36), (2.37) và (2.38);
và vcj sử dụng (2.33), (2.34) và (2.35); và uci sử dụng (2.30), (2.31) và (2.32);
2. DO 3. Cập nhật 4. Tính toán dcij sử dụng (2.1); 5. Cập nhật 6. Cập nhật 7. τ=τ+1; 8. UNTILL
.
Độ 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á
IQI DB-I XB-I Thuật toán PE
FCM
0,78 0,47 18 PC 0,56 0,371 MS E 25,3 0,9
1 2 0 9 1
0,77 0,42 15 0,96 0,014 26,7 0,79
8 0,76 0,40 22,3 0,96
FCM
0,74 20 0,40 FCoC IVFCoC 0,98 0,013 0,62 0,307 24,6 0,91
8 8 0 0 1 2
0,46 17 0,73 0,97 0,012 25,3 0,93
0,44 9 0,73 23,2 0,95
FCM
0,67 0,44 18 FCoC IVFCoC 0,98 0,012 0,52 0,387 45,6 0,86
1 8 0 6 1 2
14 0,56 0,32 0,86 0,003 42,6 0,8
0,67 0,39 7 34,3 0,95
FCM
0,48 19 0,77 FCoC IVFCoC 0,99 0,002 0,58 0,337 34,5 0,88
5 7 0 0 2 2
0,78 0,49 14 0,94 0,010 35,9 0,81
8 0,77 0,47 30,8 0,95
FCM
0,27 17 0,48 FCoC IVFCoC 0,98 0,007 0,78 0,196 20,9 0,98
4 0 0 1 4 2
0,49 12 0,25 0,83 0,003 36,3 0,92
0,49 6 0,25 18,5 0,99 FCoC IVFCoC 0,99 0,002
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
FCM
Thuật toán PC PE MSE IQI DB-I XB-I Prec. Rec.
0,80 0,095 19,1 0,75 0,97 0,62 0.79 0.82 27
i
6 5 2 m D
FCoC 0,90 0,046 8,2 0,97 0,91 0,49 0.97 0.96 18
FCM
IVFCoC 0,98 0,008 0,7 0,99 0,88 0,44 0.98 0.99 15
0,78 0,151 11,2 0,86 1,20 0,47 0.91 0.93 17
i
2 1 5 m D
FCoC 6,4 0,98 0,93 0,43 0.93 0.95 13 0,93 0,037
FCM
0,92 0,048 0.98 10 IVFCoC 0,8 0,99 0,83 0,35 0.99
0,75 0,169 21,1 0,72 0,95 0,59 0.85 0.82 19
i
4 2 0 1 m D
FCoC 0,023 7,0 0,98 0,84 0,59 0.96 0.93 15 0,95
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 FCM FCoC IVFCoC
25 17 11
PC PE MSE IQI DB-I XB-I 0,83 0,93 0,82 0,21 0,583 5,7 0,85 0,89 0,80 0,97 0,014 5,6 0,91 0,75 0,68 0,98 0,008 4,7
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.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
liệu
Đầu vào: Bộ dữ
.
, Phân bố PSO , 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),
2. While (
) do
) then Pbest-i=Xi; fPbest-i=fi; ) then
; PGbest= Pbest-i;
3. For k=1 to Np do 4. Tính toán uci; và fi; 5. If ( 8. If ( 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(
)
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 0.93 19 FCM 0,61 0,271 12,02 0,73 1,59 1,11 0.95
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
e s a b m a p S
HFCoC 0,92 0,016 7,48 0,91 0,92 0,96 0,98 0,97 10
8 MHFCoC 0,94 0,011 5,18 0,95 0,67 0,69 0.98 0.98
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
i l o c E
IVFCoC 0,98 0,002 9,60 0,98 1,83 0,57 0.97 0.97 10
HFCoC 0,96 0,005 0,97 9 9,60 0,97 1,54 0,93 0,98
5 MHFCoC 0,98 0,001 9,61 0,99 1,36 0,86 0.98 0.98
FCM 0,55 0,312 0.94 18 6,36 0,96 1,55 0,38 0.93
FCoC 0,88 0,069 7,47 0,89 1,79 0,54 0.95 0.96 15
t a s d n a L
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
8 MHFCoC 0,99 0,001 6,18 0,96 1,21 0,68 0.98 0.98
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
i
6 5 2 m D
0,88 0,44 0.98 IVFCoC 0,98 0,008 0,7 0,99 0.99 15
HFCoC 0,95 0,023 7,5 0,98 0,93 0,98 0,97 13 0,42
5,3 0,47 MHFCoC 0,98 0,008 0,99 0,52 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
i
2 1 5 m D
0,92 0,048 0,83 0.98 10 IVFCoC 0,8 0,99 0,35 0.99
HFCoC 2,9 0,96 0,88 0,39 0,96 0,95 9 0,95 0,023
1,0 0,40 MHFCoC 0,95 0,023 0,99 0,78 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,84 0,59 0.96 0.93 15 0,98
i
4 2 0 1 m D
0,95 0,022 0,78 0.98 IVFCoC 3,9 0,98 0,52 0.99 12
HFCoC 0,96 0,018 6,0 0,79 0,56 0,97 0,97 10 0,98
4,0 0,59 MHFCoC 0,98 0,009 0,98 0,70 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
PE MSE IQI DB-I XB-I
0,83 0,94 0,97 0,96 0,96 Thuật toán FCM FCoC IVFCoC HFCoC MHFCoC PC 0,79 0,137 0,95 0,027 8 0,97 0,006 0,97 0,007 0,98 0,002 11,2 9,2 7,1 8,5 6,5 3,50 1,26 1,05 1,59 0.93 1,18 0,98 0,67 0,84 0,56 21 18 12 9 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 phân cụm
Dữ liệu
FCM
FCoC
IVFCoC HFCoC MHFCoC
Mô hình lập trình
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
i
MPI
7,91
0,95
14,21
1,13
0,82
6 5 2 m D
GPU
1,50
1,21
2,16
2,08
1,68
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
i
MPI
8,20
1,69
18,25
2,24
1,51
2 1 5 m D
GPU
2,42
2,02
2,64
2,99
2,16
Tuần tự
29,59
21,01
118,89
21,32
137,45
Đa vi xử lý
41,00
6,88
44,34
10,20
6,37
MPI
i
21,23
3,61
26,43
5,58
3,82
4 2 0 1 m D
GPU
3,03
4,32
Tuần tự
3,68 1.235,23
5,07 985,27 1.587,16 2.560,54
3,60 2.120,38
ổ h p
Đa vi xử lý
398,46
281,51
495,99
825,98
605,82
a đ
MPI
224,59
156,39
299,46
492,41
400,07
h n Ả
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.
Băm ekTi; gán T=TTc+1.
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 pI, qJ; Gán E=E{(i,j)}; thay thế II{j} và JJ-{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à ekarg min{T}, ekTi. 3.2. Gán Tc+1=. Di chuyển ek+1, ek+2, …, eniTi tới 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
FCoC- SACT
i
6 5 2 MSE m IQI D PC
i
2 1 5 MSE m IQI D PC
Thuật toán PC
MSE
FCM FCM- SACT FCoC 0.90 0.89 8.22 12.20 0.97 0.85 0.93 0.90 6.42 9.45 0.98 0.92 0.95 0.91 7.02 15.13
0.80 19.10 0.75 0.78 11.23 0.86 0.75 21.12
0.95 6.43 0.98 0.95 4.32 0.99 0.97 5.17
i
IVFCoC 0.98 0.66 0.99 0.91 0.84 0.99 0.97 3.9 IVFCoC- SACT 0.99 0.62 0.99 0.98 0.53 0.99 0.99 1.89
IQI
0.98
0.72
0.89
0.98
0.99
0.99
4 2 0 1 m D
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).
(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,
(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
, số cụm C, các tham số mờ
ε, 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 (
hoặc τ≥ τmax).
Độ phức tạp tính toán của thuật toán FRFCoC là O(CD2Nτ).
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
FRFCM
FRFCoC
Dim256 Dim512 Dim1024
Số đặc trưng ban đầu 256 512 1024
49(19,14%) 87(16,99%) 105(10,25%)
53(20.7%) 92(17.9%) 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.
0,75 FCM 0,80 0,095 19,1 0,97 0,62 0.79 0.82 27
0,96 FRFCM 0,91 0,040 11,4 0,97 0,45 0.92 0.95 7
i
6 5 2 m D
0,97 FCoC 0,90 0,046 8,2 0,91 0,49 0.97 0.96 18
0,88 0,44 0.98 0,99 IVFCoC 0,98 0,008 0,7 0.99 15
0,98 1,6 0.98 4 FRFCoC 0,98 0,009 0,41 0,07 0.99
0,86 FCM 0,78 0,151 11,2 1,20 0,47 0.91 0.93 17
0,93 FRFCM 0,91 0,039 8,4 0,99 0,48 0.96 0.92 9
i
2 1 5 m D
0,98 FCoC 0,93 0,037 6,4 0,93 0,43 0.93 0.95 13
0,92 0,048 0,83 0,35 0.98 10 0,99 IVFCoC 0,8 0.99
2,2 0.98 0,99 FRFCoC 0,96 0,020 0,53 0,15 0.99 3
0,72 FCM 0,75 0,169 21,1 0,95 0,59 0.85 0.82 19
0,92 FRFCM 0,93 0,037 14,9 0,90 0,55 0.97 0.90 9
i
4 2 0 1 m D
0,98 FCoC 0,95 0,023 7,0 0,84 0,59 0.96 0.93 15
0,95 0,022 0,78 0,52 0.98 0,99 IVFCoC 3,9 0.99 12
4,3 3 0,17 0.99 0.99 FRFCoC 0,98 0,011 0,99 0,56
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
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
W M o G
FCoC 0,92 76,8 0,94 1,15 2,15 14
FRFCoC 0,97 73,8 0,98 0,28 0,75 3
FCM 0,3 238,1 0,78 1,15 2,03 21
s G
FRFCM 0,58 231,3 0,94 1,76 8 0,35
FCoC 0,91 240,1 0,85 1,1 1,94 19
FRFCoC 0,96 215,2 0,95 0,35 1,43 3
FCM 0,23 163,1 0,84 0,71 1,26 17
FRFCM 0,48 145,9 0,95 0,88 9 0,16
FCoC 0,87 159,2 0,91 0,93 0,96 9
s V & A
FRFCoC 0,97 136,5 0,95 0,16 0,82 3
