Một phiên bản cải tiến của thuật toán MMR gom cụm dữ liệu phân loại

Bài viết đề xuất một phiên bản cải tiến của thuật toán MMR để gom cụm dữ liệu phân loại, gọi là IMMR (Improved Minimum-Minimum Roughness). Ngoài việc duy trì tất cả các ưu điểm của MMR, thuật toán IMMR có hai cải tiến đáng chú ý.
Nội dung trích xuất từ tài liệu:
Một phiên bản cải tiến của thuật toán MMR gom cụm dữ liệu phân loạiKỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021DOI: 10.15625/vap.2021.0061 MỘT PHIÊN BẢN CẢI TIẾN CỦA THUẬT TOÁN MMR GOM CỤM DỮ LIỆU PHÂN LOẠI Đỗ Sĩ Trường, Phạm Công Xuyên, Trần Thanh Phương, Nguyễn Thanh Tùng Lac Hong University truongds@lhu.edu.vn, pcxuyen@lhu.edu.vn, thanhphuong@lhu.edu.vn, nttung@lhu.edu.vn TÓM TẮT: Một trong những thuật toán gom cụm dữ liệu phân loại sử dụng lý thuyết tập thô tiên phong và thành công nhấtlà thuật toán MMR (Minimum-Minimum Roughness) do Parmar đề xuất. MMR là một thuật toán gom cụm phân cấp từ trên xuống.Nó là một thuật toán gom cụm mạnh cho phép xử lý sự không chắc chắn. Tuy nhiên, MMR có hai hạn chế. Thứ nhất, nó có xu hướngchọn thuộc tính có ít giá trị hơn làm thuộc tính phân chia cụm các đối tượng tại mỗi thời điểm. Do đó, nếu một thuộc tính chỉ có mộtgiá trị đơn lẻ, nó sẽ được chọn, dẫn đến quá trình gom cụm sẽ bị chặn. Thứ hai, thuật toán MMR chọn nút lá có nhiều đối tượng hơnđể phân chia tiếp, do đó có thể tạo ra kết quả gom cụm không mong muốn. Trong bài báo này, chúng tôi đề xuất một phiên bản cải tiến của thuật toán MMR để gom cụm dữ liệu phân loại, gọi làIMMR (Improved Minimum-Minimum Roughness). Ngoài việc duy trì tất cả các ưu điểm của MMR, thuật toán IMMR có hai cải tiếnđáng chú ý. Thứ nhất, ở mỗi bước của quá trình gom cụm, IMMR loại bỏ tất cả các thuộc tính chỉ nhận một giá trị đơn lẻ. Thứ hai,IMMR xác định nút phân chia tiếp theo bằng cách xem xét tổng entropy của tất cả các thuộc tính trên các nút, đây là một phươngpháp hợp lý hơn so với phương pháp được sử dụng trong thuật toán MMR. Kết quả thử nghiệm trên các tập dữ liệu thực lấy từ khodữ liệu UCI cho thấy thuật toán IMMR có thể được sử dụng thành công trong phân tích gom cụm dữ liệu phân loại, vì nó cho kếtquả gom cụm tốt hơn. Từ khóa: Khai phá dữ liệu, dữ liệu phân loại, gom cụm, gom cụm phân cấp, lý thuyết tập thô, lựa chọn thuộc tính gom cụm. I. MỞ ĐẦU Gom cụm là một kỹ thuật cơ bản trong khai phá dữ liệu và học máy. Bài toán gom cụm có thể được phát biểunhư sau: Cho ? = {?1 , ?2 , … , ?? } là một tập gồm ? đối tượng mẫu, trong đó mỗi đối tượng ?? được mô tả bằng mộtvéc tơ ? chiều trong không gian đặc trưng đã cho. Gom cụm là việc tìm ra các cụm/nhóm các đối tượng sao cho cácđối tượng trong cùng một cụm thì có độ tương tự cao, còn các đối tượng trong các cụm khác nhau thì có độ tương tựthấp [6]. Bài toán gom cụm xuất hiện trong nhiều lĩnh vực khác nhau như Khai phá dữ liệu, Học máy, Nhận dạng mẫu,Tin-sinh học,... Cho đến nay, có nhiều kỹ thuật gom cụm đã được đề xuất và giới thiệu trong các tài liệu. Các kỹ thuậtnày có thể được phân đại thể thành hai loại: phân hoạch (partional) và phân cấp (hierarchical). Kỹ thuật gom cụm phânhoạch tạo ra một phân hoạch duy nhất của tập dữ liệu, tối ưu hóa một tiêu chuẩn nào đó. Kỹ thuật phân cấp sinh ra mộtdãy các phân hoạch lồng nhau. Kỹ thuật gom cụm phân cấp lại có thể được thực hiện theo hai phương thức: kết tụ dần(agglomerative) và phân chia dần (divisive). Kỹ thuật gom cụm kết tụ dần bắt đầu với các cụm chứa các đối tượng đơnlẻ rồi sau đó hợp nhất dần chúng cho đến khi tất cả các đối tượng nằm trong cùng một cụm hoặc đạt được số cụm thỏamãn yêu cầu. Tại mỗi lần lặp, hai cụm tương tự nhất sẽ được hợp nhất. Gom cụm phân chia dần bắt đầu bằng cụm baogồm tất cả các đối tượng rồi từng bước phân chia nó thành các cụm nhỏ hơn cho đến khi mỗi đối tượng là một cụm. Hầu hết các kỹ thuật gom cụm trong các tài liệu đều tập trung vào các tập dữ liệu số, trong đó mỗi thuộc tínhmô tả các đối tượng đều có miền giá trị là một khoảng giá trị thực liên tục, mỗi đối tượng dữ liệu số được coi là mộtđiểm trong không gian metric đa chiều với một metric đo khoảng cách giữa các đối tượng, chẳng hạn như metricEuclide hoặc metric Mahalanobis. Tuy nhiên, trong các ứng dụng thực tiễn thường gặp phải những tập dữ liệu với cácthuộc tính là những thuộc tính phân loại hay phạm trù (categorical), tức là những thuộc tính có miền giá trị ? hữu hạnvà không có thứ tự; (chẳng hạn như màu tóc, quốc tịch …); trong ? chỉ được phép so sánh giữa các giá trị, với bất kỳ?, ? ∈ ? hoặc ? = ? hoặc ? ≠ ?. Với dữ liệu phân loại ta không thể định nghĩa hàm khoảng cách một cách tự nhiên. Gần đây, gom cụm dữ liệu phân loại đã thu hút nhiều sự chú ý từ cộng đồng nghiên cứu khai phá dữ liệu. Mộtsố thuật toán gom cụm dữ liệu phân loại đã được đề xuất [1-5,14, 20]. Mặc dù những thuật toán này có những đónggóp quan trọng cho vấn đề gom cụm dữ liệu phân loại, nhưng chúng không được thiết kế để xử lý sự không chắc chắntrong quá trình gom cụm. Xử lý sự khôn ...