Cải tiến thuật Toán K-means và ứng dụng phân cụm dữ liệu tự động

Bài báo đưa ra cải tiến thuật toán K-means trong phân cụm tài liệu web, thay vì chọn số điểm làm trọng tâm thì không chọn số điểm làm trọng tâm cho số cụm mà sẽ tăng số cụm từ 1 lên k cụm bằng cách đưa trung tâm cụm mới vào cụm có mức độ biến dạng Max và tính lại trọng tâm các cụm.
Nội dung trích xuất từ tài liệu:
Cải tiến thuật Toán K-means và ứng dụng phân cụm dữ liệu tự độngNguyễn Văn Huân và csTạp chí KHOA HỌC & CÔNG NGHỆ61(12/2): 102 - 106CẢI TIẾN THUẬT TOÁN K-MEANS VÀ ỨNG DỤNGPHÂN CỤM DỮ LIỆU TỰ ĐỘNGNguyễn Văn Huân 1, Phạm Việt Bình1, Trương Mạnh Hà1, Vũ Xuân Nam1, Đoàn Mạnh Hồng212Khoa Công nghệ thông tin – Đại học Thái Nguyên,Trường Đại học Kinh tế và Quản trị Kinh doanh – Đại học Thái NguyênTÓM TẮTPhân cụm dữ liệu tự động là một bài toán phức tạp và được nhiều nhà khoa học nghiên cứu, bướcđầu họ đã đưa ra được một số thuật toán như: K-means, K-medoids,.. và đã đạt được những kếtquả nhất định trong tìm kiếm, phân loại dữ liệu. Tuy nhiên, hầu hết những thuật toán này, khi phâncụm đều yêu cầu xác định số cụm cần thực thi đặc biệt là với thuật toán K-means hoặc yêu cầumức độ khác biệt trong việc xác định các thành phần có tính chất giống nhau. Ngoài ra, các kỹthuật này còn đòi hỏi phải chọn trước số điểm làm trọng tâm, với số điểm chọn ngẫu nhiên làmtrọng tâm này sẽ cho các kết quả khác nhau. Do vậy, các kết quả có thể là không chính xác, vớimức độ sai số có thể rất lớn.Bài báo đưa ra cải tiến thuật toán K-means trong phân cụm tài liệu web, thay vì chọn số điểm làmtrọng tâm thì không chọn số điểm làm trọng tâm cho số cụm mà sẽ tăng số cụm từ 1 lên k cụm bằngcách đưa trung tâm cụm mới vào cụm có mức độ biến dạng Max và tính lại trọng tâm các cụm.Từ khoá: K-Means, phân cụm, Data mining, Web mining, K-Medoids.GIỚI THIỆUSự phát triển nhanh chóng của mạng Internetđã sinh ra một khối lượng khổng lồ các dữliệu dạng siêu văn bản (dữ liệu Web). Các tàiliệu siêu văn bản chứa đựng văn bản vàthường nhúng các liên kết đến các tài nguyênkhác phân bố trên Web. Ngày nay, Web baogồm hàng tỷ tài liệu của hàng triệu tác giảđược tạo ra và được phân tán qua hàng triệumáy tính được kết nối qua đường dây điệnthoại, cáp quang, sóng radio v.v.. Web đã vàđang được sử dụng phổ biến trong nhiều lĩnhvực như báo chí, phát thanh, truyền hình, hệthống bưu điện, trường học, các tổ chứcthương mại, chính phủ v.v.. Chính vì vậy lĩnhvực Web mining hay tìm kiếm tự động cácthông tin phù hợp và có giá trị trên Web làmột chủ đề quan trọng trong Data Mining vàlà vấn đề quan trọng của mỗi đơn vị, tổ chứccó nhu cầu thu thập và tìm kiếm thông tin trênInternet.Hiện nay, các hệ thống tìm kiếm thông tin haynói ngắn gọn là các máy tìm kiếm Web thôngthường trả lại một danh sách các tài liệu đượcphân hạng mà người dùng sẽ phải tốn côngTel: 0987 118 623, Email: nvhuan@ictu.edu.vnSố hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên102chọn lọc trong một danh sách rất dài để cóđược những tài liệu phù hợp. Ngoài ra cácthông tin đó thường rất phong phú, đa dạngvà liên quan đến nhiều đối tượng khác nhau.Điều này tạo nên sự nhập nhằng gây khó khăncho người sự dụng trong việc lấy được cácthông tin cần thiết.Có nhiều hướng tiếp cận khác nhau để giảiquyết vấn đề này. Các hướng này thường chúý giảm sự nhập nhằng bằng các phương pháplọc hay thêm các tùy chọn để cắt bớt thông tinvà hướng biểu diễn các thông tin trả về bởicác máy tìm kiếm thành từng cụm để chongười dùng có thể dễ dàng tìm được thông tinmà họ cần. Đã có nhiều thuật toán phân cụmtài liệu dựa trên phân cụm ngoại tuyến toànbộ tập tài liệu. Tuy nhiên việc tập hợp tài liệucủa các máy tìm kiếm là quá lớn và luôn thayđổi thì khó có thể phân cụm ngoại tuyến. Dođó, việc phân cụm phải được ứng dụng trêntập các tài liệu nhỏ hơn được trả về từ cáctruy vấn và thay vì trả về một danh sách rấtdài các thông tin gây nhập nhằng cho ngườisử dụng cần có một phương pháp tổ chức lạicác kết quả tìm kiếm một cách hợp lý.Hiện nay, đã có nhiều kỹ thuật, thuật toán vềthu thập, phân cụm dữ liệu tự động [2, 5, 6,http://www.Lrc-tnu.edu.vnNguyễn Văn Huân và csTạp chí KHOA HỌC & CÔNG NGHỆ11, 12], tuy nhiên hầu hết các kỹ thuật này khiphân cụm đều yêu cầu xác định số cụm cầnthực thi đặc biệt là với thuật toán K-meanshoặc yêu cầu mức độ khác biệt trong việc xácđịnh các thành phần có tính chất giống nhau.Ngoài ra, các kỹ thuật này còn đòi hỏi phảichọn trước số điểm làm trọng tâm, với sốđiểm chọn ngẫu nhiên làm trọng tâm này sẽcho các kết quả khác nhau. Do vậy, các kếtquả trên có thể là không chính xác, với mứcđộ sai số có thể rất lớn. Để khắc phục nhượcđiểm trên, nhóm tác giả cải tiến thuật toán Kmeans trong thu thập, phân cụm tài liệu Webvà thay vì chọn số điểm làm trọng tâm, chúngta không chọn số điểm làm trọng tâm cho sốcụm mà sẽ tăng số cụm từ 1 lên k cụm bằngcách đưa trung tâm cụm mới vào cụm có mứcđộ biến dạng lớn nhất và tính lại trọng tâmcác cụm.MỘT SỐ THUẬT TOÁN PHÂN CỤMDỮ LIỆUThuật toán K-meansTư tưởng: Đầu tiên chọn ngẫu nhiên K mẫu,mỗi mẫu này coi như biểu diễn 1 cluster, lúcnày trong mỗi cluster thì đối với mỗi mẫu đócũng là tâm của cluster. Các mẫu còn lại đượcgán vào một nhóm nào đó trong K nhóm đãcó sao cho tổng khoảng cách từ nhóm mẫu đóđến tâm của nhóm là min. Rồi ...