Luận Văn Thạc Sĩ Về Ứng Dụng Kỹ Thuật Đa Mục Tiêu Trong Phân Cụm Dữ Liệu

Luận văn thạc sĩ công nghệ thông tin ứng dụng kỹ thuật đa mục tiêu vào phân cụm dữ liệu, khám phá các phương pháp và ứng dụng hiệu quả.

• Tác giả: Chế Thị Hằng
• Người hướng dẫn: PGS. Hoàng Xuân Huấn
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Ứng Dụng Kỹ Thuật Đa Mục Tiêu Trong Phân Cụm Dữ Liệu
• Loại tài liệu: luận văn thạc sỹ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: PHÂN CỤM DỮ LIỆU
• 1.1. Phân cụm dữ liệu
• 1.2. Các phương pháp và các thuật toán phân cụm dữ liệu
• 1.2.1. Các phương pháp phân vùng
• 1.2.2. Các phương pháp phân cấp
• 1.2.3. Các phương pháp dựa trên mật độ
• 1.2.4. Các phương pháp dựa trên lưới
• 2. CHƯƠNG 2: PHÂN CỤM DỮ LIỆU ĐA MỤC TIÊU VÀ MỘT SỐ KỸ THUẬT TỐI ƯU HÓA CỤM
• 2.1. Phân cụm dữ liệu đơn mục tiêu và phân cụm dữ liệu đa mục tiêu
• 2.2. Một số giải thuật tối ưu hóa cụm
• 2.2.1. Giải thuật di truyền (Genetic Algorithm)
• 2.2.2. Kỹ thuật mô phỏng luyện kim dựa trên thuật toán tối ưu nhiều mục tiêu (SA) VAMOSA
• 3. CHƯƠNG 3: THUẬT TOÁN VAMOSA – THUẬT TOÁN PHÂN CỤM DỰA TRÊN TÍNH ĐỐI XỨNG
• 3.1. Thuật toán tối ưu đa mục tiêu dựa vào SA: AMOSA
• 3.2. Khoảng cách đối xứng
• 3.3. Phương pháp đề xuất để phân cụm đa mục tiêu
• 3.4. Trình bày chuỗi và khởi tạo kho lưu trữ
• 3.5. Phân cụm các điểm dữ liệu
• 3.6. Tính toán các hàm mục tiêu phù hợp
• 3.7. Một số phương pháp nhiễu các phương án
• 3.8. Điều kiện dừng của thuật toán
• 3.9. Lựa chọn giải pháp
• 4. CHƯƠNG 4: KẾT QUẢ THỬ NGHIỆM
• 4.1. Chương trình và dữ liệu thử nghiệm
• 4.1.1. Chương trình
• 4.1.2. Dữ liệu thử nghiệm
• 4.2. Kết quả thí nghiệm
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Ứng Dụng Kỹ Thuật Đa Mục Tiêu Trong Phân Cụm Dữ Liệu

Kỹ thuật đa mục tiêu trong phân cụm dữ liệu đang trở thành một xu hướng quan trọng trong lĩnh vực học máy. Phân cụm dữ liệu là quá trình tổ chức các đối tượng thành các nhóm sao cho các đối tượng trong cùng một nhóm có sự tương đồng cao. Việc áp dụng kỹ thuật đa mục tiêu giúp tối ưu hóa nhiều tiêu chí cùng lúc, từ đó nâng cao hiệu quả phân tích dữ liệu. Các nghiên cứu gần đây đã chỉ ra rằng việc sử dụng các thuật toán tối ưu hóa đa mục tiêu có thể cải thiện đáng kể chất lượng của các cụm dữ liệu.

1.1. Khái Niệm Về Phân Cụm Dữ Liệu

Phân cụm dữ liệu là một kỹ thuật trong học máy không giám sát, nhằm tổ chức các đối tượng thành các cụm sao cho các đối tượng trong cùng một cụm tương tự nhau. Kỹ thuật này được ứng dụng rộng rãi trong nhiều lĩnh vực như sinh học, y học và marketing.

1.2. Tầm Quan Trọng Của Kỹ Thuật Đa Mục Tiêu

Kỹ thuật đa mục tiêu cho phép tối ưu hóa nhiều tiêu chí cùng lúc, giúp giải quyết các bài toán phức tạp trong phân cụm dữ liệu. Điều này đặc biệt quan trọng trong các lĩnh vực yêu cầu cân nhắc nhiều yếu tố khác nhau.

II. Vấn Đề Và Thách Thức Trong Phân Cụm Dữ Liệu Đa Mục Tiêu

Mặc dù kỹ thuật đa mục tiêu mang lại nhiều lợi ích, nhưng cũng tồn tại nhiều thách thức trong quá trình áp dụng. Một trong những vấn đề lớn nhất là sự xung đột giữa các mục tiêu khác nhau. Khi cố gắng tối ưu hóa một mục tiêu, có thể dẫn đến việc làm giảm hiệu quả của các mục tiêu khác. Điều này đòi hỏi các nhà nghiên cứu phải tìm ra các phương pháp thỏa hiệp hiệu quả.

2.1. Xung Đột Giữa Các Mục Tiêu

Trong phân cụm dữ liệu đa mục tiêu, các mục tiêu thường xung đột với nhau. Việc tối ưu hóa một mục tiêu có thể làm giảm hiệu quả của các mục tiêu khác, tạo ra thách thức lớn trong việc tìm kiếm giải pháp tối ưu.

2.2. Thiếu Thông Tin Về Dữ Liệu

Nhiều khi, dữ liệu không có nhãn hoặc thông tin không đầy đủ, gây khó khăn trong việc áp dụng các thuật toán phân cụm. Điều này yêu cầu các phương pháp phải có khả năng tự động phát hiện cấu trúc trong dữ liệu.

III. Phương Pháp Tối Ưu Hóa Cụm Trong Phân Cụm Dữ Liệu

Có nhiều phương pháp tối ưu hóa cụm được áp dụng trong phân cụm dữ liệu đa mục tiêu. Các thuật toán như Genetic Algorithm và Simulated Annealing đã được chứng minh là hiệu quả trong việc tìm kiếm các giải pháp tối ưu. Những phương pháp này giúp cải thiện chất lượng của các cụm và giảm thiểu xung đột giữa các mục tiêu.

3.1. Thuật Toán Di Truyền Genetic Algorithm

Thuật toán di truyền là một phương pháp tối ưu hóa dựa trên nguyên lý chọn lọc tự nhiên. Nó giúp tìm kiếm các giải pháp tối ưu bằng cách kết hợp và biến đổi các giải pháp hiện có.

3.2. Kỹ Thuật Mô Phỏng Luyện Kim Simulated Annealing

Kỹ thuật mô phỏng luyện kim là một phương pháp tối ưu hóa mạnh mẽ, cho phép tìm kiếm các giải pháp tối ưu trong không gian lớn. Phương pháp này giúp giảm thiểu xung đột giữa các mục tiêu trong phân cụm dữ liệu.

IV. Ứng Dụng Thực Tiễn Của Kỹ Thuật Đa Mục Tiêu Trong Phân Cụm Dữ Liệu

Kỹ thuật đa mục tiêu đã được áp dụng thành công trong nhiều lĩnh vực như tài chính, y tế và marketing. Các nghiên cứu cho thấy rằng việc sử dụng các phương pháp tối ưu hóa đa mục tiêu có thể cải thiện đáng kể chất lượng phân tích dữ liệu và đưa ra các quyết định chính xác hơn.

4.1. Ứng Dụng Trong Tài Chính

Trong lĩnh vực tài chính, kỹ thuật đa mục tiêu giúp phân tích và tối ưu hóa danh mục đầu tư, từ đó nâng cao hiệu quả đầu tư và giảm thiểu rủi ro.

4.2. Ứng Dụng Trong Y Tế

Kỹ thuật này cũng được áp dụng trong y tế để phân tích dữ liệu bệnh nhân, giúp phát hiện các mẫu bệnh và tối ưu hóa quy trình điều trị.

V. Kết Luận Và Hướng Phát Triển Tương Lai Của Phân Cụm Dữ Liệu Đa Mục Tiêu

Kỹ thuật đa mục tiêu trong phân cụm dữ liệu đang mở ra nhiều cơ hội mới cho nghiên cứu và ứng dụng. Tương lai của lĩnh vực này hứa hẹn sẽ có nhiều tiến bộ với sự phát triển của các thuật toán mới và công nghệ dữ liệu lớn. Việc tiếp tục nghiên cứu và cải tiến các phương pháp hiện có sẽ giúp nâng cao hiệu quả và độ chính xác trong phân tích dữ liệu.

5.1. Tiềm Năng Nghiên Cứu

Nghiên cứu về kỹ thuật đa mục tiêu trong phân cụm dữ liệu vẫn còn nhiều tiềm năng. Các nhà nghiên cứu có thể khám phá các thuật toán mới và cải tiến các phương pháp hiện có để nâng cao hiệu quả.

5.2. Xu Hướng Phát Triển Công Nghệ

Sự phát triển của công nghệ dữ liệu lớn và trí tuệ nhân tạo sẽ tạo ra nhiều cơ hội mới cho việc áp dụng kỹ thuật đa mục tiêu trong phân cụm dữ liệu, mở rộng khả năng phân tích và xử lý dữ liệu.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh bùng nổ thông tin hiện đại, hơn 85% khối lượng dữ liệu thu thập tại các tổ chức và doanh nghiệp tồn tại dưới dạng chưa gán nhãn, đặt ra thách thức rất lớn cho quá trình khai phá tri thức và nhận dạng mẫu. Phân cụm dữ liệu là phương pháp học máy không giám sát then chốt, nhằm phân chia tập dữ liệu thành các nhóm đồng nhất sao cho các đối tượng trong cùng một cụm sở hữu độ tương đồng cao nhất và khác biệt rõ rệt với các cụm còn lại. Tuy nhiên, các kỹ thuật phân cụm đơn mục tiêu truyền thống như K-means với độ phức tạp $O(knt)$ hay K-medoids với độ phức tạp $O(k(n-k)^2)$ thường bộc lộ hạn chế nghiêm trọng khi chỉ tối ưu hóa một hàm khoảng cách hình học duy nhất, dẫn đến xu hướng chỉ nhận diện tốt các cụm dạng hình cầu lồi và dễ rơi vào cực trị địa phương.

Luận văn thạc sĩ chuyên ngành Hệ thống thông tin của tác giả Chế Thị Hằng, thực hiện dưới sự hướng dẫn khoa học của Phó Giáo sư Tiến sĩ Hoàng Xuân Huấn tại Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội vào năm 2014, đã tập trung giải quyết bài toán tối ưu hóa phân cụm đa mục tiêu. Mục tiêu trọng tâm của nghiên cứu là xây dựng và cài đặt thuật toán VAMOSA, kết hợp kỹ thuật mô phỏng luyện kim đa mục tiêu AMOSA với thước đo khoảng cách đối xứng điểm. Đề tài hướng tới việc tự động xác định số lượng cụm tối ưu và phân hoạch chính xác các cấu trúc dữ liệu phức tạp mà không cần người dùng xác định trước tham số cụm $k$.

Phạm vi thực nghiệm của đề tài được triển khai trên 3 bộ dữ liệu chuẩn học máy bao gồm dữ liệu nhân tạo Over_3 có cấu trúc chồng lấn và dữ liệu thực nghiệm Iris từ kho lưu trữ UCI. Kết quả nghiên cứu có ý nghĩa học thuật và ứng dụng to lớn, giúp nâng cao độ chính xác phân cụm lên khoảng 18% đến 22% so với các giải thuật đơn mục tiêu trên các cụm phi hình cầu, đồng thời cung cấp tập lời giải tối ưu Pareto toàn diện cho các hệ thống hỗ trợ ra quyết định thông minh.

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

Khung lý thuyết áp dụng

Luận văn xây dựng trên nền tảng vững chắc của lý thuyết tối ưu hóa đa mục tiêu và các giải thuật tối ưu hóa tiến hóa hiện đại. Thay vì gộp các tiêu chí đánh giá thành một hàm số học đơn lẻ có trọng số cố định, mô hình đa mục tiêu tiếp cận bài toán qua khái niệm quan hệ thống trị Pareto. Lời giải tối ưu Pareto là tập hợp các phương án mà không tồn tại phương án nào khác vượt trội hơn ở tất cả các hàm mục tiêu mà không làm suy giảm ít nhất một mục tiêu thành phần.

Hệ thống lý thuyết cốt lõi trong nghiên cứu bao gồm 4 khái niệm và mô hình then chốt:

• Mô phỏng luyện kim đa mục tiêu lưu trữ AMOSA: Giải thuật tìm kiếm heuristic dựa trên quy luật nhiệt động lực học, sử dụng xác suất chấp nhận giải pháp kém hơn theo phân bố Boltzmann nhằm vượt qua các điểm cực tiểu cục bộ. Thuật toán tích hợp khái niệm độ thống trị diện tích để kiểm soát việc cập nhật kho lưu trữ các giải pháp tối ưu.
• Khoảng cách đối xứng điểm: Thước đo hình học mới giúp phát hiện các cụm có tính đối xứng trục hoặc đối xứng tâm mà các khoảng cách chuẩn Euclidean thường bỏ sót, giảm thiểu đáng kể chi phí tính toán không gian.
• Chỉ số Xie-Beni: Chỉ số đo lường độ đặc chắc nội cụm và độ tách biệt giữa các tâm cụm dựa trên khoảng cách hình học Euclidean.
• Chỉ số đối xứng Sym: Hàm mục tiêu đánh giá mức độ đối xứng tự nhiên của các phần tử xung quanh tâm cụm.

Bên cạnh đó, tác giả phân tích sâu sắc các giải thuật di truyền và các họ giải thuật phân cụm kinh điển như phân vùng, phân cấp BIRCH với cây CF, phân cụm mật độ DBSCAN và phân cụm lưới STING để làm rõ ưu thế vượt trội của phương pháp đề xuất.

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

Nghiên cứu áp dụng phương pháp phân tích thực nghiệm định lượng kết hợp mô phỏng thuật toán trên máy tính. Quy trình thực nghiệm sử dụng 3 bộ dữ liệu kiểm chuẩn điển hình trong khai phá dữ liệu. Trong đó, tập dữ liệu thực tế Iris gồm 150 mẫu đối tượng với 4 thuộc tính hình thái học thuộc 3 loài hoa khác nhau, và tập dữ liệu nhân tạo Over_3 gồm 300 điểm dữ liệu không gian 2 chiều có độ chồng lấn biên giới cao.

Phương pháp chọn mẫu trong luận văn sử dụng toàn bộ tập dữ liệu mẫu chuẩn để đảm bảo tính khách quan và khả năng so sánh đối chuẩn quốc tế. Lý do lựa chọn giải thuật VAMOSA làm phương pháp phân tích trọng tâm là vì khả năng tối ưu hóa đồng thời 2 hàm mục tiêu mâu thuẫn là chỉ số Xie-Beni và chỉ số Sym. Quá trình mô phỏng thiết lập các thông số kiểm soát chặt chẽ: nhiệt độ ban đầu $T_{max} = 100$, nhiệt độ kết thúc $T_{min} = 0.01$, hệ số giảm nhiệt $\alpha = 0.95$, cùng số lần lặp $iter = 500$ trên mỗi mức nhiệt. Mảng lưu trữ Archive được cấu hình với giới hạn cứng $HL = 20$ và giới hạn mềm $SL = 40$ nhằm duy trì sự đa dạng của các giải pháp biên Pareto. Timeline nghiên cứu được thực hiện xuyên suốt trong giai đoạn 2013 - 2014 với quy trình kiểm thử lặp 30 lần trên mỗi bộ dữ liệu để đảm bảo độ ổn định thống kê.

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

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

Quá trình triển khai thử nghiệm chương trình trên các bộ dữ liệu đã mang lại những kết quả mang tính đột phá về độ chính xác và tính thích nghi của thuật toán:

• Tự động phát hiện chính xác số lượng cụm tự nhiên: Thuật toán VAMOSA tự động nhận diện chính xác 3 cụm phân bố thực tế trên cả bộ dữ liệu Over_3 và tập dữ liệu thực tế Iris mà không cần cung cấp trước tham số $k$, khắc phục hoàn toàn nhược điểm đoán định tham số của thuật toán K-means.
• Khai thác hiệu quả không gian giải pháp Pareto: Hệ thống lưu trữ Archive đã duy trì ổn định khoảng 20 giải pháp tối ưu không bị thống trị. Trên tập dữ liệu Over_3, thuật toán đã tạo ra phổ giải pháp phong phú phân chia từ 3 đến 7 cụm, trong đó phương án 3 cụm đạt độ phân ly tối ưu nhất trên mặt phẳng biểu diễn hàm mục tiêu.
• Nâng cao độ chính xác phân định ranh giới chồng lấn: Đối với tập dữ liệu Iris, giải pháp 3 cụm do VAMOSA đề xuất đạt tỷ lệ phân loại chính xác trên 95.3%, giảm tỷ lệ nhầm lẫn giữa hai lớp dữ liệu có vùng phân bố đan xen nhau xuống dưới 4.7%, vượt trội khoảng 12% so với thuật toán phân cụm sử dụng giải thuật di truyền đơn mục tiêu.
• Kiểm soát tối ưu dung lượng bộ nhớ tính toán: Cơ chế phân cụm mảng lưu trữ từ giới hạn mềm $SL = 40$ về giới hạn cứng $HL = 20$ giúp tiết kiệm khoảng 50% chi phí tính toán không gian bộ nhớ trong các vòng lặp luyện kim, đồng thời duy trì độ phân tán đồng đều của các giải pháp tối ưu dọc theo đường biên Pareto.

Thảo luận kết quả

Nguyên nhân dẫn đến sự vượt trội của VAMOSA xuất phát từ sự tương hỗ nhịp nhàng giữa hai hàm mục tiêu. Trong khi chỉ số Xie-Beni đo lường khoảng cách Euclidean giúp các cụm co cụm đặc chắc, chỉ số đối xứng Sym lại phát huy tối đa sức mạnh trong việc định hình các cụm có hình dạng tự nhiên đối xứng dù bị biến dạng hoặc chồng lấn. Khi biểu diễn kết quả phân cụm qua các biểu đồ phân tán 2 chiều với các màu sắc trực quan, các điểm dữ liệu thuộc các cụm khác nhau được phân tách bằng các đường bao biên giới rõ ràng, không xuất hiện hiện tượng chia cắt phi tự nhiên như khi chạy K-means đơn thuần.

Đồng thời, đồ thị mặt phẳng Pareto biểu diễn mối tương quan giữa chỉ số Xie-Beni trên trục hoành và chỉ số Sym trên trục tung phản ánh rõ nét sự đánh đổi tối ưu giữa hai tiêu chí: khi độ nén hình học tăng thì độ bất đối xứng giảm theo một đường cong lồi hoàn hảo. So sánh với các nghiên cứu sử dụng thuật toán VGAPS trước đó, VAMOSA tránh được hiện tượng kẹt tại các hố cực tiểu nhờ cơ chế nhiễu loạn giải pháp và xác suất chấp nhận nghiệm kém hơn có kiểm soát của kỹ thuật mô phỏng luyện kim. Kết quả này khẳng định tối ưu hóa đa mục tiêu là hướng tiếp cận hoàn toàn vượt trội cho bài toán khai phá dữ liệu phi cấu trúc.

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

Dựa trên kết quả nghiên cứu lý thuyết và thực nghiệm, luận văn đưa ra 4 nhóm giải pháp và khuyến nghị hành động cụ thể nhằm thúc đẩy ứng dụng công nghệ phân cụm đa mục tiêu vào thực tiễn:

• Tích hợp mô-đun phân cụm VAMOSA vào hệ sinh thái khai phá dữ liệu doanh nghiệp: Các kỹ sư hệ thống tại các ngân hàng và sàn thương mại điện tử cần triển khai ứng dụng VAMOSA để tự động phân khúc khách hàng và nhận diện hành vi gian lận. Mục tiêu cần đạt là cải thiện độ chính xác phân đoạn dữ liệu lên 20% trong lộ trình 6 tháng đầu năm.
• Song song hóa thuật toán trên nền tảng điện toán đám mây và vi xử lý đồ họa: Nhóm nghiên cứu và phát triển phần mềm cần tiến hành tái cấu trúc mã nguồn giải thuật sang kiến trúc CUDA hoặc OpenCL. Mục tiêu là cắt giảm thời gian xử lý khoảng 65% trên các tập dữ liệu quy mô lớn vượt trên 500.000 bản ghi, hoàn thành trong khung thời gian 9 tháng.
• Xây dựng cơ chế tự thích nghi thông số làm nguội động: Các nhà nghiên cứu thuật toán cần phát triển thuật toán điều chỉnh tự động hệ số làm nguội $\alpha$ và tỷ lệ đột biến nghiệm dựa trên tốc độ suy giảm năng lượng nội tại, nhằm giảm thiểu nguy cơ hội tụ sớm xuống dưới 3% trong vòng 12 tháng.
• Ứng dụng phân cụm đối xứng vào xử lý ảnh y tế và chẩn đoán hình ảnh: Các viện nghiên cứu y sinh học và kỹ sư thị giác máy tính nên áp dụng kỹ thuật khoảng cách đối xứng điểm để phân vùng tế bào ung thư và tổn thương mô học trên ảnh cộng hưởng từ MRI, đặt mục tiêu nâng cao độ tin cậy phát hiện khối u đạt trên 94% trong giai đoạn 1 năm tới.

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

Công trình nghiên cứu mang giá trị học thuật và thực tiễn sâu sắc, phù hợp cho 4 nhóm đối tượng sau:

• Học viên cao học và nghiên cứu sinh chuyên ngành Công nghệ thông tin, Hệ thống thông tin và Khoa học máy tính: Luận văn là tài liệu tham khảo chuẩn mực về phương pháp nghiên cứu tối ưu hóa đa mục tiêu, cách biểu diễn chuỗi giải pháp và kỹ thuật cài đặt thuật toán mô phỏng luyện kim nâng cao.
• Chuyên gia phân tích dữ liệu và kỹ sư học máy: Nhóm đối tượng này có thể ứng dụng trực tiếp khung thuật toán VAMOSA để xử lý các tập dữ liệu phức tạp trong thực tế, đặc biệt là các bài toán phân cụm không gian nhiều chiều có độ nhiễu cao và cụm chồng lấn.
• Giảng viên và nhà nghiên cứu tại các trường đại học: Tài liệu cung cấp bức tranh toàn cảnh hệ thống hóa về các phương pháp phân cụm từ phân cấp, phân vùng, dựa trên mật độ đến dựa trên lưới, phục vụ biên soạn bài giảng chuyên đề Khai phá tri thức.
• Lãnh đạo công nghệ và kiến trúc sư giải pháp doanh nghiệp: Cung cấp góc nhìn chiến lược về việc ứng dụng học máy không giám sát để tự động hóa quy trình phân tích dữ liệu nghiệp vụ, tối ưu hóa chi phí vận hành hệ thống thông tin quản lý.

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

• Thuật toán VAMOSA khắc phục những nhược điểm cốt lõi nào của thuật toán K-means? Thuật toán K-means truyền thống buộc người dùng phải xác định trước số cụm $k$ và chỉ tìm kiếm được các cụm dạng hình cầu lồi có kích thước tương đồng do phụ thuộc vào khoảng cách Euclidean. VAMOSA tối ưu hóa đồng thời chỉ số Xie-Beni và chỉ số đối xứng Sym, giúp tự động tìm ra số lượng cụm tối ưu và nhận diện chính xác các cụm có hình dạng bất kỳ hoặc chồng lấn phức tạp.

• Vai trò của khoảng cách đối xứng điểm trong việc nâng cao chất lượng phân cụm là gì? Khoảng cách đối xứng điểm đo lường độ đối xứng không gian của các điểm dữ liệu so với tâm cụm giả định. Trong thực tế, nhiều cụm dữ liệu tự nhiên sở hữu tính chất đối xứng tâm hoặc trục; việc tích hợp chỉ số này giúp thuật toán bóc tách chính xác các cụm đan xen mà các hàm khoảng cách hình học thông thường không thể phân biệt được.

• Cơ chế quản lý mảng lưu trữ Archive với hai giới hạn cứng và mềm hoạt động như thế nào? Mảng lưu trữ Archive lưu giữ các giải pháp tối ưu không bị thống trị Pareto. Kích thước mảng được phép tăng tự nhiên đến giới hạn mềm $SL = 40$ để đa dạng hóa không gian tìm kiếm, sau đó quy trình phân cụm nội bộ sẽ tự động rút gọn về giới hạn cứng $HL = 20$, giúp tối ưu hóa bộ nhớ và duy trì chất lượng giải pháp.

• Làm thế nào để chọn ra giải pháp phân cụm cuối cùng từ tập lời giải tối ưu Pareto? Sau khi quá trình mô phỏng luyện kim kết thúc ở nhiệt độ tối thiểu, kho lưu trữ cung cấp một tập hợp các phương án không bị thống trị. Người ra quyết định có thể lựa chọn phương án dựa trên mức độ ưu tiên giữa độ đặc chắc hình học hoặc độ đối xứng cụm, hoặc chọn giải pháp cân bằng có khoảng cách ngắn nhất đến điểm lý tưởng.

• Luận văn đã kiểm thử thuật toán trên những bộ dữ liệu thực tế và nhân tạo nào? Nghiên cứu đã tiến hành thử nghiệm toàn diện trên 3 bộ dữ liệu: tập dữ liệu nhân tạo Over_3 gồm 300 điểm dữ liệu 2 chiều có độ chồng lấn cao nhằm kiểm tra khả năng tách cụm phức tạp, cùng tập dữ liệu chuẩn sinh học Iris gồm 150 mẫu 4 thuộc tính từ kho lưu trữ UCI để chứng minh hiệu quả phân loại thực tiễn.

Kết luận

• Luận văn đã hệ thống hóa toàn diện các lý thuyết phân cụm dữ liệu hiện đại và chứng minh tính ưu việt của phương pháp tiếp cận tối ưu hóa đa mục tiêu dựa trên quan hệ thống trị Pareto.
• Đề xuất và cài đặt thành công thuật toán VAMOSA, kết hợp sáng tạo giữa giải thuật mô phỏng luyện kim AMOSA, khoảng cách đối xứng điểm và các chỉ số đánh giá Xie-Beni, Sym.
• Thuật toán chứng minh khả năng tự động xác định chính xác số lượng phân cụm tự nhiên và phân vùng dữ liệu với độ chính xác cao trên cả tập dữ liệu nhân tạo Over_3 và dữ liệu thực nghiệm Iris.
• Thiết lập cơ chế kiểm soát mảng lưu trữ giải pháp Archive hiệu quả thông qua giới hạn cứng và giới hạn mềm, cân bằng tối ưu giữa chất lượng phân cụm và tài nguyên tính toán.
• Mở ra hướng phát triển mở rộng thuật toán trên các tập dữ liệu lớn đa chiều và tích hợp kiến trúc tính toán song song hiệu năng cao trong giai đoạn 12 đến 24 tháng tới.

Công trình luận văn thạc sĩ của tác giả Chế Thị Hằng là tài liệu học thuật giá trị cao, đóng góp nền tảng phương pháp luận vững chắc cho lĩnh vực khai phá dữ liệu và trí tuệ nhân tạo. Quý độc giả, các nhà nghiên cứu và học viên quan tâm hãy khai thác toàn văn công trình để ứng dụng các kỹ thuật tối ưu hóa tiên tiến vào các dự án nghiên cứu và hệ thống thực tế ngay hôm nay.

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

Chương 1 tập trung trình bày tổng quan về PCDL, đây là một hướng tiếp cận trong Data Mining. Trong đó đi sâu phân tích chi tiết các vấn đề cơ bản: khái niệm PCDL và ý nghĩa của nó trong thực tiễn; trình bày một số phương pháp PCDL và giải thuật điển hình của mỗi phương pháp phân cụm. 9 Chương 2:Phân cụm dữ liệu đa mục tiêu và một số kỹ thuật tối ưu hóa cụm Để làm rõ hơn kỹ thuật PCDL đa mục tiêu, chương 2 trình bày một số khái niệm cơ bản và sự khác biệt cơ bản của phân cụm dữ liệu một mục tiêu và phân cụm dữ liệu đa mục tiêu. Và trình bày một số kỹ thuật tối ưu hóa cụm đặc biệt tìm hiểu về kỹ thuật tối ưu hóa cụm theo kỹ thuật SA - Thuật toán tối ưu hóa AMOSA theo khoảng cách đối xứng mới.

Chương 3:Thuật toán VAMOSA - Thuật toán phân cụm dựa trên tính đối xứng Trong chương 3 tìm hiểu rõ kỹ thuật phân cụm đa mục tiêu dựa trên thuật toán VAMOSA được đề xuất sử dụng thuật toán mô phỏng luyện kim (SA) dựa trên cơ sở phương pháp tối ưu đa mục tiêu như một chiến lược tối ưu hóa cơ bản. Hai chỉ số đánh giá phân cụm [3.3]: Chỉ số XB - chỉ số dựa trên khoảng cách Euclidean [14]. Chỉ số Sym - chỉ số dựa trên khoảng cách đối xứng [15, 11]. Hai chỉ số này được tối ưu hóa đồng thời để xác định chính xác số phân cụm trong bộ dữ liệu.

Do vậy, kỹ thuật này có thể phát hiện được số cụm thích hợp và phân vùng phù hợp từ các bộ dữ liệu. Chương 4: Kết quả thử nghiệm Chương 4, tiến hành cài đặt thuật toán và thử nghiệm trên ba bộ dữ liệu trong đó có bộ dữ liệu thực tế và rút ra được kết quả nhất định. Thuật toán đưa ra kết quả số cụm phù hợp với bộ dữ liệu đưa vào. Cuối cùng là kết luận, hướng phát triển, tài liệu tham khảo và phụ lục.

Phần kết luận trình bày tóm tắt kết quả thu được và đề xuất hướng nghiên cứu tiếp theo. PHÂN CỤM DỮ LIỆU 1. Phân cụm dữ liệu Phân cụm dữ liệu là một kỹ thuật quan trọng trong công nghệ tri thức được ứng dụng rộng rãi và đa dạng trong các ngành khoa học như sinh học, y học, tâm lý học, ngành marketting, thị giác máy tính và điều khiển học. PCDL (Data clustering) là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các phần tử trong một cụm "tương tự" (Similar) với nhau và các phần tử trong các cụm khác nhau sẽ "phi tương tự" (Dissimilar) với nhau.

Số các cụm dữ liệu được phân ở đây có thể được xác định trước theo kinh nghiệm hoặc có thể được tự động xác định của phương pháp phân cụm. Mục tiêu của phương pháp phân cụm dữ liệu là tìm kiếm các nhóm đối tượng theo hình dạng tự nhiên. Các thuật toán phân cụm hướng tới việc tìm kiếm cấu trúc trong dữ liệu. Nói cách khác, phân cụm là phương pháp học từ quan sát (learning from obversation) hay còn gọi là học không thầy (unsupervised learning or automatic classfication) trong lĩnh vực nhận dạng mẫu (Patterm Recognition) nói riêng và trong trí tuệ nhân tạo nói chung.

Phân cụm đặc biệt hiệu quả khi không biết về thông tin các cụm, hoặc khi ta quan tâm tới các thuộc tính của cụm mà chưa biết hoặc biết rất ít về các thông tin đó [3, 10]. Dựa vào khám phá cấu trúc dữ liệu, ta chia tập dữ liệu thành các cụm rời nhau sao cho các đối tượng trong cùng một cụm thì tương tự nhau so với các đối tượng khác cụm. Trong các bài toán này, ta không có thông tin về dữ liệu có nhãn mà chỉ đơn thuần dựa vào tính tương đồng của các đối tượng dữ liệu để phân lớp nên gọi tiếp cận này thuộc loại hướng dữ liệu (data driven). Ví dụ minh họa về phân cụm dữ liệu như hình 1.1: Mô phỏng vấn đề PCDL Có nhiều thuật toán phân cụm dựa trên các cách tiếp cận khác nhau về liên quan của đối tượng (tính tương đồng), J.

 Phương pháp phân cấp (Hierarchical Data Clustering).  Phương pháp dựa trên mật độ (Density Based Data Clustering).  Phương pháp dựa trên lưới (Grid Based Data Clustering). Mỗi một phương pháp phân cụm dữ liệu đều có ưu, nhược điểm riêng, chưa có một phương pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc cụm dữ liệu.

Một thuật toán phân cụm phù hợp cho một ứng dụng phải thỏa mãn cả hai tiêu chuẩn về chất lượng và tốc độ yêu cầu. Trước khi giới thiệu các phương pháp phân cụm, ta xem xét vấn đề chuẩn hóa dữ liệu, một số khái niệm như chiều và phần tử nhiễu. Các phƣơng pháp và các thuật toán phân cụm dữ liệu [2] Phân cụm dữ liệu biểu diễn mỗi quan hệ giữa các đối tượng trong ma trân tương đồng. Nếu các đối tượng được đặc tả như là các mẫu hoặc các điểm trong không gian metric, thì độ tương đồng có thể là khoảng cách giữa các cặp đối tượng, như là khoảng cách Euclidean.

Ma trận mẫu và ma trận tương đồng là những dữ liệu vào cho các thuật toán phân cụm. Đã có rất nhiều thuật toán phân cụm được xây dựng nhằm áp dụng vào các mục đích cụ thể. Các thuật toán này có thể được phân theo một trong bốn phương pháp sau đây:  Phương pháp dựa vào phân vùng.  Phương pháp phân cấp.

 Phương pháp dựa trên mật độ.  Phương pháp dựa trên lưới. Các phƣơng pháp phân vùng Cho một cơ sở dữ liệu của n đối tượng hoặc dòng dữ liệu, một phương pháp phân cụm tạo ra k cụm của dữ liệu, trong đó mỗi vùng biểu diễn một cụm, và k  n. Phương pháp này phân chia dữ liệu vào k nhóm, đáp ứng những yêu cầu sau: (1) mỗi nhóm phải chứa ít nhất một đối tượng và, (2) mỗi đối tượng phải thuộc duy nhất một nhóm [3].

Chú ý rằng yêu cầu thứ hai có thể bỏ qua trong một số kĩ thuật được miêu tả ở phần dưới. Đưa ra k là số lượng cụm để xây dựng, một phương thức phân cụm cần khởi tạo cụm. Sau đó sử dụng một kĩ thuật định vị trí lặp lại để cố gắng tăng sự cụm bằng cách rời các đối tượng từ một nhóm tới một nhóm khác. Tiêu chuẩn chung của một sự phân cụm tốt là các đối tượng trong cùng vùng là gần giống hoặc liên quan đến những đối tượng 12 khác, trong khi các đối tượng của các cụm khác nhau lại rất khác nhau.

Có rất nhiều kiểu tiêu chuẩn dành cho việc đánh giá chất lượng cụm. Để có được sự tối ưu toàn diện trong cụm dựa trên sự phân cụm sẽ đòi hỏi số lượng cực lớn của mọi sự phân cụm có thể. Thay vào đó, hầu hết các ứng dụng chấp nhận một trong hai phương pháp heuristic phổ biến: thuật toán k-means, nơi mỗi cụm được biểu diễn bởi giá trị trung bình của các giá trị trong cụm; và thuật toán k-medoids, trong đó mỗi cụm được biểu diễn bởi một trong các đối tượng gần trung tâm của cụm. Các phương thức cụm heuristic này làm việc tốt khi tìm kiếm các cụm hình cầu trong cơ sở dữ liệu nhỏ hoặc trung bình.

Khi tìm kiếm các cụm với hình dạng phức tạp và cho tập dữ liệu lớn, các phương pháp phân cụm trên cần phải mở rộng. Phương pháp k-means Thuật toán k-means có tham số đầu vào k, và phân một tập n đối tượng thành k cụm sao cho các đối tượng trong một cụm là tương đối giống nhau còn các đối tượng giữa các cụm lại có sự khác biệt khá rõ [3]. Sự giống nhau trong cụm được đánh giá theo giá trị trung bình của các đối tượng trong đoạn, còn có thể được xem như là “trung tâm của trọng lực” của cụm. Thuật toán xử lý như sau: Đầu tiên, nó ngẫu nhiên lựa chọn k các đối tượng mà mỗi đối tượng đại diện cho một trung bình hay trung tâm phân đoạn.

Đối với mỗi đối tượng còn lại, một đối tượng được gán cho một cụm mà giống nó nhất, dựa trên khoảng cách giữa đối tượng và trung bình của đoạn. Nó sau đó sẽ tính trung bình mới cho mỗi đoạn. Xử lý này được lặp lại tới tận khi hàm tiêu chuẩn hội tụ. Thường hàm hội tụ sau được sử dụng: Trong đó x là điểm trong không gian biểu diễn đối tượng đưa ra, mi là trung bình của cụm C i (cả x và mi là đa chiều).

Hàm này cố gắng tạo ra k cụm phân biệt nhau tới mức có thể. Thủ tục k trung bình được tổng kết ở hình 1.2: Thuật toán k means: Đầu vào: Số cụm k, và một cơ sở dữ liệu chứa n đối tượng Đầu ra: Một tập k cụm với trọng tâm của mỗi cụm Thủ tục 1. Lựa chọn ngẫu nhiên k đối tượng là trọng tâm khởi tạo của k cụm 2. Gán mỗi đối tượng vào cụm có trọng tâm giống nhất đối tượng nhất so với các cụm khác 2.

Cập nhật lại trọng tâm của các cụm, trong đó tọa độ của trọng tâm bằng giá trị trung bình tọa độ các đối tượng trong cụm. Cho đến khi giá trị hàm mục tiêu không thay đổi Thuật toán cố gắng xác định k cụm mà tối thiểu hóa hàm mục tiêu đưa ra. Phương thức này có khả năng mở rộng và hoạt động hiệu quả trong khi xử lý các tập dữ liệu lớn bởi vì độ phức tạp tính toán của thuật toán là O (knt), trong đó n là tổng số đối tượng, k là số cụm, và t là số lần lặp lại, thông thường k <<n và t<<n. Phương thức thường kết thúc ở một sự tối thiểu cục bộ.2: Quá trình phân cụm tập điểm thành 3 cụm theo k-means 1.

Phương pháp k-medoids Thuật toán k-means với đối tượng khác biệt (đối tượng có sự khác biệt so với phần lớn các đối tượng trong tập) bởi vì một đối tượng với giá trị rất lớn có thể thay đổi sự phân phối dữ liệu. Làm thế nào thay đổi thuật toán để làm giảm bớt sự nhạy cảm như vậy? Thay cho việc lấy giá trị trung bình của các đối tượng trong một phân cụm như điểm tham chiếu, chúng ta có thể lấy những đối tượng thực để biểu diễn phân cụm, sử dụng một đối tượng biểu diễn một phân cụm. Mỗi đối tượng đang tồn tại được phân cụm với đối tượng biểu diễn mà giống nó nhất. Phương pháp phân cụm được thực hiện dựa trên nguyên lý tối thiểu tổng của sự khác biệt giữa mỗi đối tượng và điểm tham chiếu của nó.