Lựa chọn các ràng buộc cho thuật toán phân cụm nửa giám sát

Bài viết đề xuất một thuật toán mới mở rộng từ thuật toán MMFFQS nhằm thu thập các ràng buộc từ người sử dụng, thuật toán mới được đặt tên là KMMFFQS dựa trên K-Means và phương pháp Min-Max. Kết quả thực nghiệm với các tập dữ liệu thực từ UCI chỉ ra tính hiệu quả của thuật toán đề xuất
Nội dung trích xuất từ tài liệu:
Lựa chọn các ràng buộc cho thuật toán phân cụm nửa giám sát Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018 DOI: 10.15625/vap.2018.00032 LỰA CHỌN CÁC RÀNG BUỘC CHO THUẬT TOÁN PHÂN CỤM NỬA GIÁM SÁT Vũ Việt Vũ1, Nguyễn Anh Tuấn2, Lê Thị Kiều Oanh3 1 Viện Công nghệ Thông tin, Đại học Quốc gia Hà Nội 2 Công ty Hệ thống Thông tin (FPT) 3 Trường Đại học Kinh tế Kỹ thuật Công Nghiệp vuvietvu@vnu.edu.vn, tuanna2@fpt.com.vn, oanhlk2004@gmail.com TÓM TẮT: Thuật toán phân cụm dựa trên các ràng buộc là một dạng của thuật toán phân cụm nửa giám sát nhằm tích hợp một tập các ràng buộc để cải tiến quá trình phân cụm. Trên thực tế rất nhiều thuật toán phân cụm nửa giám sát đã được giới thiệu. Tuy nhiên hầu hết các ràng buộc sử dụng được sinh ngẫu nhiên hoặc giả thiết rằng có sẵn từ ban đầu. Hơn nữa, một số tập ràng buộc thậm chí có thể làm giảm chất lượng của quá trình phân cụm nếu chúng không được lựa chọn cẩn thận. Trong bài báo này, chúng tôi đề xuất một thuật toán mới mở rộng từ thuật toán MMFFQS nhằm thu thập các ràng buộc từ người sử dụng, thuật toán mới được đặt tên là KMMFFQS dựa trên K-Means và phương pháp Min-Max. Kết quả thực nghiệm với các tập dữ liệu thực từ UCI chỉ ra tính hiệu quả của thuật toán đề xuất. Từ khóa: Phân cụm nửa giám sát, ràng buộc, học tích cực, K-Means. I. GIỚI THIỆU Thuật toán phân cụm (clustering) nhằm phân tách một tập dữ liệu X có n phần tử trong không gian m chiều thành các cụm sao cho các phần tử trong mỗi cụm thì tương tự nhau theo một độ đo nào đó. Thuật toán phân cụm đóng vai trò quan trọng trong lĩnh vực khai phá dữ liệu và phát hiện tri thức từ dữ liệu. Mục đích của quá trình phân cụm là phát hiện ra cấu trúc của tập dữ liệu đang xét, tìm ra mối liên hệ giữa các phần tử và thậm chí trong một số trường hợp phát hiện ra các phần tử dị thường (outlier). Các thuật toán phân cụm được nghiên cứu và giới thiệu từ những năm 50 của thế kỷ XX. Các thuật toán điển hình có thể kể đến như K-Means, Fuzzy C-Means, thuật toán phân cụm dựa trên đồ thị (GC), thuật toán phân cụm dựa trên mật độ (DBSCAN) [1],… Mặc dù đã có nhiều thuật toán phân cụm được đề xuất, tuy nhiên hiện nay chủ đề phân cụm vẫn thu hút nhiều nhà nghiên cứu với mục đích cải tiến chất lượng phân cụm, đáp ứng với các loại dữ liệu thực tế và phù hợp với các yêu cầu của người sử dụng. Từ những năm 2000 trở lại đây, phương pháp phân cụm nửa giám sát (semi-supervised clustering) bắt đầu được nghiên cứu và phát triển mạnh mẽ [2]. Một trong những dạng cơ bản của phân cụm nửa giám sát là các thuật toán sử dụng ràng buộc. Các ràng buộc là các cặp dữ liệu có dạng must-link hoặc cannot-link trong đó must-link(u,v) với u, v là các phần tử thuộc tập dữ liệu X thể hiện u và v nên nhóm vào cùng một cụm, trong khi cannot-link(u,v) cho biết u và v nên thuộc về hai cụm khác nhau. Hình 1 minh họa ví dụ về dữ liệu với các ràng buộc. Một dạng khác của bài toán phân cụm nửa giám sát cũng được quan tâm đó chính là bài toán phân cụm nửa giám sát sử dụng một số điểm hạt giống (seed). Các seed ở đây chính là một số điểm đã được gán nhãn sẵn các nhãn của cụm. Hình 1. Ví dụ về tập dữ liệu (bên trái) và dữ liệu với các ràng buộc (bên phải); các dữ liệu must-link được biểu diễn bằng các đường nét liền, cannot-link được biểu diễn bằng các đường nét đứt. Tính đến nay hầu hết các thuật toán phân cụm cơ bản đều đã có các thuật toán phân cụm nửa giám sát tương ứng, các thuật toán này sử dụng một trong hai dạng hoặc thậm chí cả hai dạng là ràng buộc và seed vào trong cùng một thuật toán. Chúng tôi có thể kể ra đây thuật toán phân cụm nửa giám sát cho K-Means [3], Fuzzy C-Means [4], DBSCAN [5], GC [6],… Thuật toán có thể tích hợp cả hai dạng là ràng buộc và seed có thể kể đến như thuật toán MCSSGC [7] và thuật toán MCSSDBS [8]. Phương pháp sử dụng các ràng buộc tích hợp vào bài toán phân cụm thường có hai dạng là tích hợp trực tiếp vào quá trình tìm kiếm các cụm hoặc dùng các ràng buộc để huấn luyện một độ đo khoảng cách sao cho khi chuyển sang không gian độ đo mới thì các điểm thuộc các ràng buộc must-link sẽ xích gần nhau và các điểm thuộc các ràng buộc cannot-link sẽ xa nhau ra. 240 LỰA CHỌN CÁC RÀNG BUỘC CHO THUẬT TOÁN PHÂN CỤM NỬA GIÁM SÁT Một vấn đề quan trọng phát sinh trong quá trình nghiên cứu các thuật toán phân cụm nửa giám sát là việc lựa chọn các ràng buộc. Một số kết quả nghiên cứu đã chỉ ra rằng việc lựa chọn các ràng buộc tốt sẽ tăng đáng kể chất lượng phân cụm tuy nhiên nếu tập các ràng buộc không lựa chọn tốt có thể làm giảm chất lượng phân cụm [9]. Việc lựa chọn các cặp để gán nhãn nhằm thu thập các ràng buộc sao cho tốt nằm trong khuôn khổ của bài toán học tích cực (active learning). Một số thuật toán học tích cực đã được phát triển như thuật toán FFQS [10], thuật toán MMFFQS [11], thuật toán ASC [12], thuật toán AFCC [13], thuật toán dựa trên hàm hạt nhân [14],… Các nghiên cứu này đều cho thấy việc lựa chọn tốt các ràng buộc không những làm tăng chất lượng của quá trình phân cụm mà còn giảm được số lượng các ràng buộc cần thu thập. Trong bài báo này, chúng tôi đề xuất một thuật toán mới mở rộng từ thuật toán MMFFQS nhằm thu thập các ràng buộc từ người sử dụng, thuật toán mới được đặt tên là KMMFFQS dựa trên K- Means và phương pháp Min-Max. Kết quả thực nghiệm với các tập dữ liệu thực từ UCI [15] chỉ ra tính hiệu quả của thuật toán đề xuất. Phần tiếp theo của bài báo được cấu trúc như sau: Phần II sẽ trình bày các n ...