Luận văn thạc sĩ về gom cụm dữ liệu không đầy đủ trong khoa học máy tính

Nghiên cứu gom cụm dữ liệu không đầy đủ trong khoa học máy tính, phương pháp xử lý thông tin hiệu quả cho các hệ thống phân tích dữ liệu phức tạp.

• Tác giả: Phan Hữu Lộc
• Người hướng dẫn: TS. Võ Thị Ngọc Châu
• Trường học: Đại học Bách Khoa - ĐHQG - HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Gom Cụm Dữ Liệu Không Đầy Đủ
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• NHIỆM VỤ LUẬN VĂN THẠC SĨ
• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN THẠC SĨ
• LỜI CAM ĐOAN
• 1. Chương 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Lý do chọn đề tài
• 1.2. Mục tiêu của đề tài
• 1.3. Đối tượng và phạm vi nghiên cứu
• 1.4. Phương pháp nghiên cứu
• 2. Chương 2: TỔNG QUAN VỀ GOM CỤM VÀ DỮ LIỆU KHÔNG ĐẦY ĐỦ
• 2.1. Phân tích cụm
• 2.1.1. Bốn bước cơ bản của thủ tục phân tích cụm
• 2.1.2. Các yêu cầu tiêu biểu của việc gom cụm dữ liệu
• 2.1.3. Các phương pháp đánh giá việc gom cụm dữ liệu
• 2.1.4. Khoảng cách và thước đo sự tương đồng
• 2.2. Các công trình liên quan
• 2.2.1. Gom cụm mờ
• 2.2.2. Gom cụm dựa trên hạt nhân (kernel)
• 2.2.3. Dữ liệu không đầy đủ hoặc dữ liệu bị thiếu
• 2.2.4. Dạng hình học của dữ liệu bị thiếu
• 2.3. Kết luận chương 2
• 3. Chương 3: CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN GOM CỤM DỮ LIỆU KHÔNG ĐẦY ĐỦ
• 3.1. K-means với ràng buộc mềm
• 3.2. K-means với chiến lược khoảng cách từng phần
• 3.3. Giải thuật di truyền lai với Fuzzy c-means (IGA-FCM)
• 3.4. Thuật toán gom cụm Mean shift với dữ liệu không đầy đủ
• 3.5. Bốn chiến lược gom cụm dữ liệu không đầy đủ dựa trên FCM
• 3.6. Gom cụm dữ liệu không đầy đủ dùng kernel-based fuzzy c-means
• 3.7. Fuzzy self-organizing maps
• 3.8. Kết luận chương 3
• 4. Chương 4: HƯỚNG TIẾP CẬN VÀ GIẢI PHÁP
• 4.1. Hướng tiếp cận
• 4.2. Kernel-based fuzzy-c-means cải tiến
• 4.3. Mean shift với mode gần nhất (Mean shift use nearest mode-MSNM)
• 4.4. Kết luận chương 4
• 5. Chương 5: KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ
• 5.1. Môi trường và tập dữ liệu thực nghiệm
• 5.2. Kết quả thực nghiệm
• 5.2.1. Tập dữ liệu 2 chiều nhân tạo
• 5.2.2. Tập dữ liệu Iris
• 5.2.3. Tập dữ liệu seed
• 5.3. Kết luận chương 5
• 6. Chương 6: KẾT LUẬN
• 6.1. Những công việc đã thực hiện
• 6.2. Đóng góp của đề tài
• 6.3. Hướng phát triển tiếp theo
• DANH MỤC CÁC TÀI LIỆU THAM KHẢO
• LÝ LỊCH TRÍCH NGANG

Tóm tắt

I. Giới thiệu về gom cụm dữ liệu không đầy đủ

Trong bối cảnh hiện đại, gom cụm dữ liệu không đầy đủ trở thành một thách thức lớn trong khoa học máy tính. Dữ liệu không đầy đủ thường xuất hiện trong nhiều lĩnh vực, từ y tế đến tài chính, và có thể gây ra những sai lệch nghiêm trọng trong quá trình phân tích. Việc xử lý dữ liệu không đầy đủ không chỉ ảnh hưởng đến chất lượng của các mô hình mà còn làm tăng chi phí và thời gian cho các dự án nghiên cứu. Do đó, việc phát triển các phương pháp phân tích dữ liệu hiệu quả là rất cần thiết. Các nghiên cứu gần đây đã chỉ ra rằng việc áp dụng các thuật toán học máy có khả năng xử lý dữ liệu không đầy đủ có thể cải thiện đáng kể kết quả phân tích. Một trong những phương pháp nổi bật là Mean shift và Kernel-based fuzzy-c-means, cho phép xử lý các giá trị thiếu mà không làm giảm chất lượng của các cụm dữ liệu.

1.1. Tầm quan trọng của việc gom cụm dữ liệu không đầy đủ

Việc gom cụm dữ liệu không đầy đủ có vai trò quan trọng trong việc khai thác tri thức từ các tập dữ liệu lớn. Dữ liệu không đầy đủ có thể dẫn đến những kết luận sai lệch, ảnh hưởng đến quyết định trong các lĩnh vực như y tế, tài chính và quản lý. Các phương pháp gom cụm hiện tại cần được cải tiến để có thể xử lý hiệu quả các giá trị thiếu. Việc phát triển các thuật toán mới không chỉ giúp cải thiện chất lượng của các cụm mà còn giảm thiểu chi phí và thời gian cho các nghiên cứu. Các nghiên cứu đã chỉ ra rằng việc áp dụng các phương pháp như Mean shift và Kernel-based fuzzy-c-means có thể mang lại kết quả tốt hơn trong việc xử lý dữ liệu không đầy đủ.

II. Các phương pháp gom cụm dữ liệu không đầy đủ

Trong nghiên cứu này, hai phương pháp chính được đề xuất để xử lý dữ liệu không đầy đủ là Mean shift và Kernel-based fuzzy-c-means. Cả hai phương pháp này đều có khả năng xử lý các giá trị thiếu mà không làm giảm chất lượng của các cụm. Mean shift là một phương pháp gom cụm không yêu cầu biết trước số lượng cụm, cho phép phát hiện các cụm có hình dạng tùy ý. Ngược lại, Kernel-based fuzzy-c-means yêu cầu một số thông số đầu vào nhưng có thể tạo ra các cụm có chất lượng cao. Việc so sánh giữa hai phương pháp này cho thấy rằng Mean shift có ưu điểm vượt trội trong việc xử lý dữ liệu không đầy đủ, đặc biệt là trong các tình huống mà dữ liệu có hình dạng phức tạp.

2.1. Đánh giá hiệu quả của các phương pháp

Để đánh giá hiệu quả của các phương pháp gom cụm, các chỉ số như Xie-Beni, Fukuyama-Sugeno, và Dunn được sử dụng. Những chỉ số này giúp xác định độ phân tách và độ chặt của các cụm. Kết quả thực nghiệm cho thấy rằng Mean shift không chỉ tạo ra các cụm có chất lượng cao mà còn có khả năng xử lý tốt các giá trị thiếu. Điều này cho thấy rằng việc áp dụng các phương pháp gom cụm hiện đại có thể cải thiện đáng kể kết quả phân tích dữ liệu không đầy đủ, từ đó hỗ trợ quá trình khai thác tri thức hiệu quả hơn.

III. Kết luận và hướng phát triển tiếp theo

Nghiên cứu về gom cụm dữ liệu không đầy đủ đã chỉ ra rằng việc áp dụng các phương pháp hiện đại như Mean shift và Kernel-based fuzzy-c-means có thể mang lại những kết quả khả quan. Các phương pháp này không chỉ giúp xử lý các giá trị thiếu mà còn đảm bảo chất lượng của các cụm. Hướng phát triển tiếp theo có thể tập trung vào việc cải tiến các thuật toán hiện tại để tăng cường khả năng xử lý dữ liệu phức tạp hơn. Việc nghiên cứu sâu hơn về các phương pháp này sẽ mở ra nhiều cơ hội mới trong việc khai thác tri thức từ các tập dữ liệu lớn và không đầy đủ.

3.1. Đề xuất cho nghiên cứu tương lai

Các nghiên cứu tương lai nên tập trung vào việc phát triển các thuật toán gom cụm mới có khả năng xử lý tốt hơn các giá trị thiếu và dữ liệu phức tạp. Việc kết hợp các phương pháp học sâu với các kỹ thuật gom cụm hiện tại có thể tạo ra những bước đột phá trong việc khai thác tri thức từ dữ liệu không đầy đủ. Hơn nữa, việc áp dụng các phương pháp này trong các lĩnh vực thực tiễn như y tế, tài chính và quản lý sẽ giúp nâng cao hiệu quả và độ chính xác trong các quyết định dựa trên dữ liệu.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ thông tin, các hệ thống thu thập và lưu trữ dữ liệu quy mô lớn phải đối mặt với một thách thức phổ biến: tình trạng dữ liệu không đầy đủ hoặc bị khuyết thiếu thuộc tính. Theo ước tính từ các chuyên gia khai phá dữ liệu, khoảng 10% đến 50% dữ liệu thu thập từ cảm biến, hồ sơ y tế hoặc biểu mẫu khảo sát trong thế giới thực gặp phải hiện tượng mất mát thông tin do lỗi truyền truyền tải hoặc sự cố thiết bị. Phương pháp truyền thống thường khắc phục vấn đề này ở giai đoạn tiền xử lý bằng cách xóa bỏ bản ghi hoặc điền giá trị trung bình nhân tạo, dẫn đến nguy cơ sai lệch cấu trúc dữ liệu và làm suy giảm nghiêm trọng độ chính xác của các mô hình phân tích.

Nhằm giải quyết triệt để hạn chế trên, luận văn thạc sĩ chuyên ngành Khoa học máy tính tại Đại học Bách Khoa thuộc Đại học Quốc gia Thành phố Hồ Chí Minh, thực hiện trong khung thời gian từ tháng 01/2015 đến tháng 06/2015, đã tập trung nghiên cứu và phát triển các kỹ thuật gom cụm dữ liệu trực tiếp trên các tập dữ liệu không đầy đủ. Mục tiêu cốt lõi của công trình là thiết lập các thuật toán gom cụm tiên tiến dựa trên hạt nhân kernel, có khả năng vừa phân cụm chính xác vừa tự động ước lượng các giá trị bị thiếu ngay bên trong giải thuật lặp.

Phạm vi nghiên cứu bao quát các tập dữ liệu nhân tạo đa chiều và dữ liệu chuẩn quốc tế UCI với kích thước từ 150 đến 210 mẫu quan sát. Kết quả nghiên cứu mang ý nghĩa khoa học và thực tiễn sâu sắc, giúp tối ưu hóa chất lượng phân nhóm thông qua các chỉ số phân tách nội tại và giảm thiểu độ sai lệch ước lượng thuộc tính xuống mức tối ưu.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu kế thừa và phát triển nền tảng từ hai nhánh lý thuyết học máy không giám sát chủ đạo: lý thuyết tập mờ và phương pháp không tham số dựa trên không gian hạt nhân phi tuyến.

Mô hình gom cụm mờ cổ điển Fuzzy C-Means (FCM) cùng kỹ thuật tối ưu hóa luân phiên (Alternating Optimization) đóng vai trò nền tảng. Trong mô hình này, mỗi đối tượng được gán mức độ thuộc về cụm thông qua ma trận thành viên mờ với hệ số mờ tiêu chuẩn m = 2, cho phép mô tả linh hoạt các ranh giới dữ liệu chồng lấp. Để nâng cao tính phân tách phi tuyến, lý thuyết không gian Hilbert tái tạo hạt nhân (RKHS) được tích hợp thông qua hàm biến đổi ánh xạ dữ liệu ban đầu vào không gian đặc trưng nhiều chiều. Các hàm hạt nhân Gaussian, hàm hạt nhân cơ sở xuyên tâm (RBF) và hàm Hyperbolic Tangent với tham số bề rộng hạt nhân được cấu hình để nắm bắt cấu trúc hình học phức tạp.

Bên cạnh đó, lý thuyết dịch chuyển trung bình Mean Shift được khai thác như một phương pháp tìm kiếm mode mật độ xác suất mà không đòi hỏi giả định trước về số lượng cụm K hay hình dạng cụm cầu. Công trình phát triển hai thuật toán cốt lõi: thuật toán gom cụm mờ dựa trên hạt nhân cải tiến (new-KFCM) và thuật toán dịch chuyển trung bình theo mode gần nhất (MSNM), kết hợp các khái niệm về độ nén cụm, độ phân tách cụm và khoảng cách hiệu chỉnh từng phần.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm định lượng kết hợp mô phỏng đối chuẩn trên môi trường Java. Dữ liệu thực nghiệm bao gồm 4 tập dữ liệu nhân tạo 2 chiều (DS, HS, DL, HL) mô phỏng các cấu trúc cụm có bán kính từ 20 đến 40 đơn vị, cùng 2 tập dữ liệu thực nghiệm chuẩn quốc tế UCI: tập Iris gồm 150 mẫu hoa (4 thuộc tính, 3 lớp phân loại) và tập Seed gồm 210 mẫu hạt giống lúa mì (7 thuộc tính, 3 lớp phân loại).

Phương pháp chọn mẫu áp dụng nguyên tắc phân tầng ngẫu nhiên để tạo lập các kịch bản dữ liệu không đầy đủ với tỷ lệ khuyết thiếu biến thiên có kiểm soát từ 10%, 20%, 30%, 40% đến 50%. Quá trình tạo dữ liệu thiếu tuân thủ nghiêm ngặt 2 ràng buộc thực nghiệm: mỗi đối tượng phải giữ lại ít nhất 1 thuộc tính quan sát được và mỗi thuộc tính trong toàn bộ tập dữ liệu phải có ít nhất 1 giá trị hiện diện.

Lý do lựa chọn phương pháp phân tích dựa trên kernel xuất phát từ khả năng kháng nhiễu vượt trội và tính linh hoạt trong việc thích ứng với các cụm có hình dạng tùy ý. Hiệu năng của các thuật toán được lượng hóa thông qua 3 độ đo đánh giá chất lượng phân cụm nội tại gồm chỉ số Xie-Beni, chỉ số Fukuyama-Sugeno, chỉ số Dunn, cùng độ đo sai số khôi phục thuộc tính Error Input với ngưỡng hội tụ thuật toán được thiết lập ở mức sai số 0.0001.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm đối sánh giữa các giải thuật đề xuất và các phương pháp kinh điển trong tài liệu chuyên ngành đã mang lại 4 phát hiện thực nghiệm nổi bật:

Thứ nhất, thuật toán new-KFCM cấu hình hàm kernel Gaussian (new-kfcm-gauss) và hàm Hyperbolic Tangent (new-kfcm-HT) thể hiện ưu thế vượt trội về độ chặt và độ tách biệt của các cụm. Trên tập dữ liệu nhân tạo DS ở mức khuyết thiếu 10%, chỉ số Xie-Beni của new-kfcm-gauss đạt mức 0.397903, tối ưu hơn đáng kể so với mô hình OCS-FCM truyền thống đạt 0.401270.

Thứ hai, tại mức độ thiếu hụt dữ liệu 20% trên tập DS, biến thể new-kfcm-HT đạt sai số khôi phục thuộc tính Error Input chỉ ở mức 0.342323, chứng minh khả năng tái tạo thuộc tính bị mất chính xác hơn nhiều so với giá trị 0.419168 của các phương pháp đối chứng.

Thứ ba, thuật toán Mean Shift cải tiến theo mode gần nhất (MSNM-initMean) đã khắc phục hoàn toàn nhược điểm phụ thuộc dạng cụm siêu cầu của họ giải thuật FCM. Thuật toán này tự động nhận diện chính xác 2 cụm tự nhiên trên các tập dữ liệu nhân tạo ở mức thiếu 10% và 20% với tham số băng thông h = 10 mà không cần cung cấp trước số lượng cụm K.

Thứ tư, khi tỷ lệ dữ liệu bị thiếu tăng cao lên mức 30% đến 50%, chất lượng phân cụm của toàn bộ các thuật toán đều có xu hướng suy giảm; tuy nhiên, các mô hình dựa trên kernel vẫn duy trì chỉ số Fukuyama-Sugeno ổn định và có khoảng cách phân tách rõ ràng hơn so với các phương pháp không sử dụng hàm hạt nhân.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp thuật toán new-KFCM đạt hiệu quả vượt trội nằm ở cơ chế cập nhật đồng thời giá trị thiếu và tâm cụm trực tiếp qua các ánh xạ kernel, loại bỏ hoàn toàn bước chạy khởi tạo phụ trợ bằng FCM cổ điển vốn rất nhạy cảm với các điểm dữ liệu nhiễu. Đối với thuật toán MSNM, cơ chế gán giá trị thiếu dựa trên mode cực đại lân cận giúp quỹ đạo dịch chuyển mật độ bảo toàn được đặc trưng phân bố tự nhiên của không gian thuộc tính.

Trong các báo cáo phân tích học thuật, các kết quả này có thể được trực quan hóa tối ưu thông qua hai dạng thức: biểu đồ đường đa trục thể hiện biến thiên của chỉ số Error Input theo các mức khuyết thiếu từ 10% đến 50%, và bảng ma trận đối sánh 10 thuật toán tương ứng với 4 chỉ số chất lượng cụm. Biểu đồ đường cho thấy rõ sự phân kỳ rõ nét khi tỷ lệ khuyết thiếu vượt mốc 30%, trong đó các giải thuật đề xuất duy trì độ dốc sai số thấp hơn 15% so với các kỹ thuật gán giá trị trung bình.

So với các công trình nghiên cứu sử dụng khoảng cách từng phần PDS hay giải thuật di truyền lai IGA-FCM, hướng tiếp cận của luận văn có độ phức tạp tính toán thấp hơn, không làm bùng nổ không gian tìm kiếm và đảm bảo tính hội tụ chặt chẽ trên các tập dữ liệu có từ 4 đến 7 thuộc tính thực tế.

Đề xuất và khuyến nghị

Dựa trên các kết luận thực nghiệm, 4 giải pháp hành động cụ thể được khuyến nghị triển khai nhằm tối ưu hóa việc khai thác dữ liệu không đầy đủ trong các hệ thống thông tin:

Thứ nhất, chuẩn hóa và tích hợp module thuật toán new-KFCM vào các quy trình tiền xử lý tự động tại các trung tâm dữ liệu. Nhóm kỹ sư dữ liệu cần hoàn thành việc đóng gói thư viện trong thời hạn 6 tháng, đặt mục tiêu duy trì sai số Error Input dưới ngưỡng 0.30 trên toàn bộ các luồng dữ liệu nghiệp vụ bị khuyết thiếu dưới 25%.

Thứ hai, mở rộng thử nghiệm thuật toán MSNM trên các tập dữ liệu lớn với quy mô trên 10.000 bản ghi và số chiều thuộc tính từ 20 chiều trở lên. Nhóm nghiên cứu trí tuệ nhân tạo cần chủ trì triển khai lộ trình nghiên cứu trong 9 tháng nhằm nâng cao chỉ số phân tách Dunn lên trên mức 1.50 đối với dữ liệu phân bố phi tuyến.

Thứ ba, thiết lập cơ chế tự động tinh chỉnh siêu tham số cho độ rộng băng thông h và tham số hạt nhân sigma. Bộ phận DevOps phối hợp cùng các chuyên gia phân tích dữ liệu trong khung thời gian 3 tháng để tích hợp kỹ thuật tối ưu hóa Bayes, hướng đến mục tiêu rút ngắn 40% thời gian hội tụ của thuật toán.

Thứ tư, áp dụng giải pháp gom cụm trực tiếp không đầy đủ vào các bài toán quan trắc môi trường và hồ sơ bệnh án điện tử. Đội ngũ kiến trúc sư giải pháp công nghệ thông tin tại các cơ quan chuyên trách cần xây dựng kiến trúc thử nghiệm trong 12 tháng, giảm thiểu 20% chi phí lưu trữ và thời gian trễ xử lý dữ liệu.

Đối tượng nên tham khảo luận văn

Tài liệu luận văn thạc sĩ này mang lại giá trị học thuật và ứng dụng chuyên sâu cho 4 nhóm đối tượng chính:

Học viên cao học và nghiên cứu sinh chuyên ngành Khoa học máy tính, Hệ thống thông tin: Tài nguyên học thuật giá trị để nắm bắt cơ sở toán học của kỹ thuật gom cụm mờ, phương pháp hạt nhân RKHS và kỹ thuật tối ưu hóa mật độ dịch chuyển trung bình, phục vụ trực tiếp cho việc công bố các bài báo khoa học.

Kỹ sư học máy và chuyên gia khoa học dữ liệu: Cung cấp giải pháp kỹ thuật trực tiếp để xử lý các tập dữ liệu thực tế bị mất mát từ 10% đến 50% thông tin mà không cần phụ thuộc vào các bước gán nhãn thủ công hoặc loại bỏ dữ liệu tốn kém.

Chuyên viên phân tích dữ liệu trong lĩnh vực y tế, sinh học và nông nghiệp: Nắm bắt phương pháp xử lý các bộ dữ liệu đặc thù như dữ liệu gen, dữ liệu phân loại hạt giống hay hồ sơ xét nghiệm lâm sàng vốn thường xuyên có từ 2 đến 4 chỉ số bị thiếu hụt ngẫu nhiên.

Kiến trúc sư hệ thống và nhà quản lý công nghệ: Tài liệu tham khảo chiến lược để thiết kế các kiến trúc pipeline dữ liệu thông minh, giúp giảm thiểu 25% thời gian xử lý dữ liệu thô và tối ưu hóa tài nguyên phần cứng trong các dự án chuyển đổi số quy mô lớn.

Câu hỏi thường gặp

Dữ liệu không đầy đủ là gì và tại sao không nên xóa bỏ các bản ghi bị thiếu? Dữ liệu không đầy đủ xuất hiện khi một số thuộc tính của đối tượng bị khuyết giá trị do lỗi cảm biến hoặc truyền dữ liệu. Việc xóa bỏ các bản ghi có thể làm mất từ 20% đến 50% dung lượng mẫu, phá vỡ cấu trúc tổng thể và gây sai lệch nghiêm trọng cho kết quả phân cụm.

Thuật toán new-KFCM có ưu điểm gì vượt trội so với KFCM truyền thống? Thuật toán new-KFCM cải tiến loại bỏ hoàn toàn sự phụ thuộc vào bước khởi tạo tâm bằng thuật toán FCM cổ điển. Quy trình này ước lượng giá trị thiếu trực tiếp trong không gian hạt nhân, giúp chỉ số phân tách Xie-Beni đạt mức tối ưu 0.397903 ngay cả khi dữ liệu bị mất 10%.

Khi nào nên lựa chọn thuật toán MSNM thay vì new-KFCM? Thuật toán MSNM là lựa chọn tối ưu khi không gian dữ liệu có cấu trúc cụm hình học phức tạp, phi cầu và không xác định trước số lượng cụm K. Thuật toán hoạt động hiệu quả chỉ với 1 tham số băng thông h = 10 trên không gian mật độ.

Các chỉ số đánh giá nội như Xie-Beni và Dunn phản ánh điều gì? Chỉ số Xie-Beni đo lường tỷ lệ giữa độ nén trong cụm và độ phân tách giữa các tâm cụm với giá trị càng nhỏ càng tốt. Ngược lại, chỉ số Dunn xác định khoảng cách nhỏ nhất giữa các cụm so với đường kính lớn nhất, giá trị càng cao thể hiện phân cụm càng rõ nét.

Giải thuật đề xuất có khả năng thích ứng với dữ liệu đa chiều không? Cả hai thuật toán new-KFCM và MSNM đều được kiểm chứng thành công trên các tập dữ liệu từ 2 đến 7 chiều như tập UCI Seed gồm 210 mẫu quan sát. Phương pháp xử lý hiệu quả không gian đa chiều mà không làm gia tăng đột biến độ phức tạp tính toán.

Kết luận

Nghiên cứu về gom cụm dữ liệu không đầy đủ đã giải quyết thành công bài toán khai phá tri thức trên các tập dữ liệu khuyết thiếu thuộc tính thông qua 5 kết quả then chốt:

• Xây dựng thành công thuật toán new-KFCM cải tiến, tối ưu hóa quá trình cập nhật tâm cụm và giá trị thiếu trực tiếp trong không gian hạt nhân.
• Đề xuất thuật toán MSNM dựa trên mode gần nhất, cho phép nhận diện các cụm có hình dạng tùy ý mà không cần xác định trước số lượng cụm.
• Thực nghiệm toàn diện trên 4 tập dữ liệu nhân tạo và 2 tập dữ liệu chuẩn quốc tế UCI (Iris và Seed) với quy mô từ 150 đến 210 mẫu.
• Chứng minh tính ưu việt của các giải pháp đề xuất qua các chỉ số định lượng khắt khe gồm Xie-Beni, Fukuyama-Sugeno, Dunn và Error Input ở các mức thiếu từ 10% đến 50%.
• Đóng góp khung phương pháp luận hoàn chỉnh giúp giảm thiểu chi phí tiền xử lý và nâng cao độ chính xác của các mô hình học máy không giám sát.

Lộ trình phát triển tiếp theo trong 12 tháng tới sẽ tập trung vào việc mở rộng giải thuật cho các tập dữ liệu phân tán quy mô hàng triệu bản ghi và tích hợp cơ chế tự học tham số hạt nhân. Các nhà nghiên cứu và kỹ sư dữ liệu hãy tham khảo và ứng dụng ngay mô hình thuật toán này để nâng cao hiệu năng cho các hệ thống phân tích dữ liệu thực tế.

Trích đoạn nội dung tài liệu

Chương 1: GIỚI THIỆU ĐỀ TÀI 1.1 Lý do chọn đề tài Chúng ta đang sống trong một thế giới đầy dữ liệu. Mỗi ngày, người ta gặp phải một số lượng lớn các thông tin và lưu trữ hoặc biểu diễn nó thành các dữ liệu, để dễ dàng cho việc phân tích và quản lý thêm. Thêm vào đó, với sự phát triển ngày càng mạnh mẽ của công nghệ thông tin, việc tin học hóa đã đi vào mọi lĩnh vực đời sống sản xuất, kinh doanh, giáo dục, quản lý, y tế, vận tải,. đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng một cách nhanh chóng với một lượng dữ liệu lưu trữ khổng lồ.

Lúc này, việc phân tích dữ liệu đóng một vai trò không thể thiếu cho sự hiểu biết các hiện tượng khác nhau. Với lượng dữ liệu tăng nhanh và khổng lồ như vậy, rõ ràng các phương pháp phân tích dữ liệu truyền thống sẽ không còn hiệu quả, gây tốn kém và dễ dẫn đến những kết quả sai lệch. Để có thể khai thác hiệu quả các cơ sở dữ liệu (CSDL) lớn, một lĩnh vực khoa học mới ra đời: Khám phá tri thức trong CSDL (Knowledge Discovery in Databases – KDD), và khai phá dữ liệu (Data Mining) là một công đoạn chính của quá trình KDD. Gom cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó thuộc lớp các phương pháp học không có giám sát (Unsupervised Learning) trong học máy (Machine Learning).

Gom cụm dữ liệu được nghiên cứu phát triển trên nhiều cộng đồng như thống kê, học máy…. Tuy nhiên, việc nghiên cứu và ứng dụng các kỹ thuật khai phá dữ liệu cũng gặp phải những khó khăn, thách thức lớn, trong đó có vấn đề dữ liệu không đầy đủ. Dữ liệu không đầy đủ hay dữ liệu bị thiếu, xảy ra khi không có giá trị dữ liệu được lưu trữ trong các biến trong một quan sát. Dữ liệu không đầy đủ xuất hiện phổ biến và có thể có một tác động đáng kể đến kết luận có thể được rút ra từ các dữ liệu.

Rất nhiều các nghiên cứu gần đây trong lĩnh vực khai phá dữ liệu có liên quan đến dữ liệu không đầy đủ. Chính vì những lý do trên, tôi chọn đề tài “Gom cụm dữ liệu không đầy đủ”, tập trung giải quyết vấn đề gom cụm trên tập dữ liệu không đầy đủ, đồng thời cũng đảm bảo mô hình gom cụm có chất lượng cụm cao.2 Mục tiêu của đề tài Đề tài tập trung nghiên cứu bài toán gom cụm với dữ liệu không đầy đủ, từ đó đưa ra giải thuật để giải quyết bài toán đó. Đối với vấn đề xử lý dữ liệu bị thiếu, đề tài sẽ giải quyết bên trong giải thuật. Kết quả đạt được là mô hình cụm có chất lượng cụm cao chấp nhận được và khả năng xử lý dữ liệu không đầy đủ với độ sai lệch nhỏ.

Về mặt khoa học, đề tài xem xét giải quyết bài toán gom cụm dữ liệu không đầy đủ với hai phương pháp gom cụm dựa trên kernel là Kernel-based fuzzy-c-means 1 (KFCM) và Mean shift, kết quả thu được đảm bảo chất lượng cụm đủ tốt, cụm có hình dạng tùy ý, xử lý được các giá trị bị thiếu và hạn chế thông số đầu vào. Với giải thuật KFCM cải tiến, đã gom được các cụm có chất lượng cao, xử lý được dữ liệu bị thiếu. Nhưng cụm kết quả của KFCM cải tiến còn bị phụ thuộc dạng siêu cầu, giải thuật Mean shift cải tiến đã giải quyết tốt hơn, giải thuật Mean shift không cần biết trước số lượng cụn, không hạn chế hình dạng cụm, ít thông số đầu vào, cụm có chất lượng cao và xử lý được dữ liệu không đầy đủ. Về mặt thực tiễn, các dữ liệu không đầy đủ là thường gặp, làm tốn kém về chi phí, thời gian, con người.

Các trường hợp gây ra dữ liệu không đầy đủ phổ biến như là dữ liệu cần xử lý đến trễ, dữ liệu cố tình bị xóa do thông tin không phù hợp hoặc do ngẫu nhiên bị thiếu bởi các nguyên nhân từ con người, thiết bị hỏng hóc. Để đối phó với loại dữ liệu này ta có thể thực hiện trong giai đoạn tiền xử lý nhưng kết quả có thể tạo ra các dữ liệu sai lệch làm ảnh hưởng tới chất lượng gom cụm. Do đó một giải pháp gom cụm tốt có khả năng xử lý dữ liệu không đầy đủ sẽ giúp ích rất nhiều cho quá trình khám phá tri thức, giảm thiểu được nhiều về chi phí.3 Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu sẽ được lấy từ tập dữ liệu chuẩn UCI (http://archive.edu/ml/) và tập dữ liệu nhân tạo, với kích thước được xem là đủ lớn. Dữ liệu sẽ được xử lý để trở thành không đầy đủ cho bài toán gom cụm.

Việc xử lý dữ liệu ở đây chỉ là cho một số thành phần mất đi theo nguyên tắc cụ thể sẽ được nói rõ trong thực nghiệm, không xem xét đến các vấn đề tiền xử lý dữ liệu (thu giảm chiều, chuẩn hóa,…). Mã nguồn được viết trên ngôn ngữ lập trình java. Phạm vi nghiên cứu tập trung xem xét trên toàn bộ thuộc tính của tập dữ liệu, bao gồm trong đó các giá trị bị thiếu. Xây dựng mô hình gom cụm xử lý được tập dữ liệu không đầy đủ để sau khi gom cụm đảm bảo được chất lượng gom cụm cao.4 Phương pháp nghiên cứu Việc chuẩn bị tài liệu nghiên cứu: Trong quá trình nghiên cứu, có tham khảo tài liệu về các chủ đề sau đây:  Các tài liệu về data mining.

 Tài liệu về gom cụm dữ liệu và đánh giá các kỹ thuật gom cụm.  Các tài liệu về gom cụm dữ liệu không đầy đủ.  Các tài liệu về đánh giá các kỹ thuật gom cụm không đầy đủ. 2 Việc tiến hành nghiên cứu: Hình 1.1: Mô hình thủ tục gom cụm cơ bản [20] Việc tiến hành nghiên cứu sẽ dựa theo hình 1.

Xu và Donald C.Wunsch [20], gồm các bước như sau: Việc chuẩn bị dữ liệu: Một phần sẽ dùng tập dữ liệu nhân tạo theo ý tưởng của R.Bezdek [3], một phần dữ liệu sẽ được lấy từ data chuẩn UCI, dữ liệu sẽ được xử lý trở thành không đầy đủ cho phù hợp với yêu cầu của bài toán. Việc xây dựng giải pháp gom cụm trên dữ liệu không đầy đủ sẽ dựa trên thuật toán Mean shift ở [1] và Kernel-based fuzzy-c-means ở [6], các thuật toán này được chọn do được chứng minh về tính hiệu quả, hiện thực với chi phí và thời gian cho phép. Đánh giá cụm, đây là khâu quan trọng nhất trong kỹ thuật gom cụm, cũng là khâu quan trọng nhất của đề tài. Đánh giá, so sánh và chọn ra phương pháp gom cụm có chất lượng đủ tốt.

Việc đánh giá kết quả gom cụm dữ liệu không đầy đủ không thể dùng đánh giá ngoại được bởi vì cấu trúc bản thân tập dữ liệu không rõ ràng do chứa các giá trị thiếu, các giá trị này làm mờ đi cấu trúc tập dữ liệu do đó sẽ đánh giá kết quả gom cụm thông qua các chỉ số đánh giá nội về độ phân tách, độ chặt của cụm và thông qua chỉ số đánh giá cho việc xử lý dữ liệu không đầy đủ. Các chỉ số đánh giá nội gồm Xie- Beni, Fukuyama-Sugeno và Dunn, đánh giá cho việc xử lý dữ liệu không đầy đủ trên độ đo Input error. Tiếp theo sẽ so sánh các kết quả đánh giá gom cụm trên các giải thuật khác nhau. Từ các đánh giá, đưa ra nhận xét và xác định cụm kết quả tốt nhất.

3 Chương 2: TỔNG QUAN VỀ GOM CỤM VÀ DỮ LIỆU KHÔNG ĐẦY ĐỦ Các thuật toán gom cụm dữ liệu phân dữ liệu vào một số lượng nhất định các cụm (nhóm, tập hợp con hoặc các danh mục). Hầu hết định nghĩa mô tả một cụm bằng cách xem xét tính đồng nhất bên trong và sự tách biệt bên ngoài, tức là, các đối tượng trong cùng một cụm sẽ tương tự như nhau, trong khi các đối tượng trong các cụm khác nhau thì không tương tự. Sau đây là một số mô tả toán học đơn giản của một số loại gom cụm. Cho một tập các mẫu đầu vào X  x1 ,., xi , , xn  với xi   xi1 , xi 2 ,, xid   R T d và mỗi xij còn được gọi là một đặc trưng (biến, chiều, hoặc thuộc tính).

1) Gom cụm cứng tìm kiếm một phân vùng K của X, C  C1 ,, CK  K  N , để cho Ci   , i  1,., K và i  j 2) Với gom cụm cứng, mỗi một đối tượng chỉ thuộc về một cụm. Tuy nhiên một đối tượng cũng có thể thuộc về tất cả các cụm với một mức độ thành viên trong gom cụm mờ. 3) Gom cụm theo cấp bậc cố gắng để xây dựng một cấu trúc phân vùng lồng cấp giống như cấu trúc cây của X, H  H1 ,., HQ   Q  N sao cho Ci  H m , C j  H l và m  l nghĩa là Ci  C j hoặc Ci  C j   , với i, j  i, m, l  1,.1 Phân tích cụm 2.1 Bốn bước cơ bản của thủ tục phân tích cụm Bốn bước của thủ tục phân tích cụm sẽ dựa theo Rui. Xu và Donald C.Wunsch [20] theo như ở hình 1.

Lựa chọn hoặc khai thác đặc trưng. Lựa chọn đặc trưng là lựa chọn các đặc trưng phân biệt từ một tập hợp các ứng viên, trong khi khai thác đặc trưng sử dụng một số biến đổi để tạo ra các đặc trưng hữu ích và mới lạ từ những bản gốc. Cả hai đều rất quan trọng đối với hiệu quả của ứng dụng gom cụm. Việc lựa chọn các đặc trưng rất có thể làm giảm khối lượng công việc và đơn giản hóa quá trình thiết kế tiếp theo.

Nói chung, các đặc trưng lý tưởng nên được sử dụng trong phân biệt các mẫu thuộc các cụm khác nhau, phải ít bị nhiễu và dễ dàng để trích xuất và diễn giải. Thiết kế hoặc lựa chọn thuật toán gom cụm. Thường được kết hợp với việc lựa chọn một độ đo tương ứng và việc xây dựng một hàm tiêu chuẩn. Các đối tượng được nhóm lại theo sự giống nhau.

Rõ ràng, các độ đo sự tương đồng trực tiếp ảnh hưởng sự hình thành của các cụm kết quả. Hầu hết các thuật toán gom cụm là rõ ràng hoặc ngầm định có sự kết nối với một số định nghĩa của độ đo tương đồng. Khi một độ đo 4 tương đồng được chọn, việc xây dựng một hàm mục tiêu cho cụm là một vấn đề tối ưu hóa, và có nhiều giải pháp phong phú.