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

Nguyễn Văn Huân và cs<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 61(12/2): 102 - 106<br /> <br /> CẢI TIẾN THUẬT TOÁN K-MEANS VÀ ỨNG DỤNG<br /> PHÂN CỤM DỮ LIỆU TỰ ĐỘNG<br /> Nguyễ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ồng2<br /> 1<br /> <br /> 2<br /> <br /> Khoa Công nghệ thông tin – Đại học Thái Nguyên,<br /> Trường Đại học Kinh tế và Quản trị Kinh doanh – Đại học Thái Nguyên<br /> <br /> TÓM TẮT<br /> Phâ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<br /> đầu họ đã đưa ra được một số thuật toán như: K-means, K-medoids,.. và đã đạt được những kết<br /> quả 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ân<br /> cụ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ầu<br /> 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ỹ<br /> 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àm<br /> trọ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ới<br /> mức độ sai số có thể rất lớn.<br /> 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<br /> 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<br /> 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.<br /> Từ khoá: K-Means, phân cụm, Data mining, Web mining, K-Medoids.<br /> <br /> <br /> GIỚI THIỆU<br /> Sự phát triển nhanh chóng của mạng Internet<br /> đã sinh ra một khối lượng khổng lồ các dữ<br /> liệu dạng siêu văn bản (dữ liệu Web). Các tài<br /> liệu siêu văn bản chứa đựng văn bản và<br /> thường nhúng các liên kết đến các tài nguyên<br /> khác phân bố trên Web. Ngày nay, Web bao<br /> gồm hàng tỷ tài liệu của hàng triệu tác giả<br /> được tạo ra và được phân tán qua hàng triệu<br /> máy tính được kết nối qua đường dây điện<br /> thoại, cáp quang, sóng radio v.v.. Web đã và<br /> đang được sử dụng phổ biến trong nhiều lĩnh<br /> vực như báo chí, phát thanh, truyền hình, hệ<br /> thống bưu điện, trường học, các tổ chức<br /> thương mại, chính phủ v.v.. Chính vì vậy lĩnh<br /> vực Web mining hay tìm kiếm tự động các<br /> thông tin phù hợp và có giá trị trên Web là<br /> một chủ đề quan trọng trong Data Mining và<br /> là vấn đề quan trọng của mỗi đơn vị, tổ chức<br /> có nhu cầu thu thập và tìm kiếm thông tin trên<br /> Internet.<br /> Hiện nay, các hệ thống tìm kiếm thông tin hay<br /> nói ngắn gọn là các máy tìm kiếm Web thông<br /> thường trả lại một danh sách các tài liệu được<br /> phân hạng mà người dùng sẽ phải tốn công<br /> <br /> <br /> Tel: 0987 118 623, Email: nvhuan@ictu.edu.vn<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> 102<br /> <br /> chọn lọc trong một danh sách rất dài để có<br /> được những tài liệu phù hợp. Ngoài ra các<br /> thông tin đó thường rất phong phú, đa dạng<br /> và liên quan đến nhiều đối tượng khác nhau.<br /> Điều này tạo nên sự nhập nhằng gây khó khăn<br /> cho người sự dụng trong việc lấy được các<br /> thông tin cần thiết.<br /> Có nhiều hướng tiếp cận khác nhau để giải<br /> quyết vấn đề này. Các hướng này thường chú<br /> ý giảm sự nhập nhằng bằng các phương pháp<br /> lọc hay thêm các tùy chọn để cắt bớt thông tin<br /> và hướng biểu diễn các thông tin trả về bởi<br /> các máy tìm kiếm thành từng cụm để cho<br /> người dùng có thể dễ dàng tìm được thông tin<br /> mà họ cần. Đã có nhiều thuật toán phân cụm<br /> tài liệu dựa trên phân cụm ngoại tuyến toàn<br /> bộ tập tài liệu. Tuy nhiên việc tập hợp tài liệu<br /> của các máy tìm kiếm là quá lớn và luôn thay<br /> đổi thì khó có thể phân cụm ngoại tuyến. Do<br /> đó, việc phân cụm phải được ứng dụng trên<br /> tập các tài liệu nhỏ hơn được trả về từ các<br /> truy vấn và thay vì trả về một danh sách rất<br /> dài các thông tin gây nhập nhằng cho người<br /> sử dụng cần có một phương pháp tổ chức lại<br /> các kết quả tìm kiếm một cách hợp lý.<br /> Hiện nay, đã có nhiều kỹ thuật, thuật toán về<br /> thu thập, phân cụm dữ liệu tự động [2, 5, 6,<br /> <br /> http://www.Lrc-tnu.edu.vn<br /> <br /> Nguyễn Văn Huân và cs<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 11, 12], tuy nhiên hầu hết các kỹ thuật này khi<br /> phân cụm đều yêu cầu xác định số cụm cần<br /> thực thi đặc biệt là với thuật toán K-means<br /> hoặc yêu cầu mức độ khác biệt trong việc xác<br /> định các thành phần có tính chất giống nhau.<br /> Ngoài ra, các kỹ thuật này còn đòi hỏi phải<br /> chọn trước số điểm làm trọng tâm, với số<br /> điểm chọn ngẫu nhiên làm trọng tâm này sẽ<br /> cho các kết quả khác nhau. Do vậy, các kết<br /> quả trên có thể là không chính xác, với mức<br /> độ sai số có thể rất lớn. Để khắc phục nhược<br /> đ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 Web<br /> và thay vì chọn số điểm làm trọng tâm, chúng<br /> ta không chọn số điểm làm trọng tâm cho số<br /> cụm mà sẽ tăng số cụm từ 1 lên k cụm bằng<br /> cách đưa trung tâm cụm mới vào cụm có mức<br /> độ biến dạng lớn nhất và tính lại trọng tâm<br /> các cụm.<br /> MỘT SỐ THUẬT TOÁN PHÂN CỤM<br /> DỮ LIỆU<br /> Thuật toán K-means<br /> Tư tưởng: Đầu tiên chọn ngẫu nhiên K mẫu,<br /> mỗi mẫu này coi như biểu diễn 1 cluster, lúc<br /> này trong mỗi cluster thì đối với mỗi mẫu đó<br /> cũng là tâm của cluster. Các mẫu còn lại được<br /> gán vào một nhóm nào đó trong K nhóm đã<br /> có sao cho tổng khoảng cách từ nhóm mẫu đó<br /> đến tâm của nhóm là min. Rồi, tính lại tâm<br /> cho các nhóm và lặp lại quá trình đó cho đến<br /> khi hàm tiêu chuẩn hội tụ. Hàm tiêu chuẩn<br /> hay được dùng nhất là hàm tiêu chuẩn sai-số<br /> vuông. Thuật toán này, có thể áp dụng được<br /> đối với cơ sở dữ liệu (CSDL) đa chiều, nhưng<br /> để dễ minh họa chúng tôi mô tả thuật toán<br /> trên dữ liệu hai chiều.<br /> Thuật toán k-means được mô tả như sau:<br /> Input: K, và dữ liệu về n mẫu của 1 CSDL.<br /> Output: Một tập gồm K cluster sao cho cực tiểu<br /> về tổng sai-số vuông.<br /> Các bước thuật toán:<br /> Bước 1: Chọn ngẫu nhiên K mẫu vào K cluster.<br /> Coi tâm của cluster chính là mẫu có trong cluster.<br /> Bước 2: Tìm tâm mới của cluster.<br /> Bước 3: Gán các mẫu vào từng cluster sao cho<br /> khoảng cách từ mẫu đó đến tâm của cluster đó là<br /> nhỏ nhất.<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> 103<br /> <br /> 61(12/2): 102 - 106<br /> <br /> Bước 4: Nếu các cluster không có sự thay đổi nào<br /> sau khi thực hiện bước 3 thì chuyển sang bước 5,<br /> ngược lại sang bước 2.<br /> Bước 5: Dừng thuật toán.<br /> <br /> Ví dụ: Trong không gian hai chiều, cho 12<br /> điểm (n = 12) cần phân 12 điểm này thành<br /> hai cluster (k=2).<br /> Đầu tiên, chọn hai điểm ngẫu nhiên vào hai<br /> cluster (chọn 2 điểm màu đỏ: (1,3); (9,4))<br /> Coi điểm (1,3) là tâm của cluster 1 và điểm<br /> (9,4) là tâm của cluster 2. Tính toán khoảng<br /> cách từ các điểm khác đến hai điểm này và<br /> gán được các điểm còn lại này vào một trong<br /> hai cluster, những điểm có màu trắng vào<br /> cluster 1, những điểm có màu đen vào cluster<br /> 2. Hiệu chỉnh lại tâm của hai cluster, điểm<br /> màu xám là tâm mới của hai cluster. Tính lại<br /> các khoảng cách các điểm đến tâm mới và<br /> gán lại các điểm này. Tiếp tục hiệu chỉnh lại<br /> tâm của hai cluster. Rồi, lặp lại cho đến khi<br /> không còn sự thay đổi nữa thì dừng.<br /> <br /> Hình 1. Minh họa thuật toán K-means<br /> <br /> Độ phức tạp của thuật toán này là O(tKn).<br /> Trong đó n là số mẫu trong CSDL, K là số<br /> cluster, t là số lần lặp. Thông thường t,k 1: thêm trung tâm của cụm mới vào cụm<br /> có biến dạng max.<br /> Bước 2.2: Gán từng điểm vào cụm có trung tâm<br /> gần nhất với điểm đang xét và cập nhật lại trung<br /> tâm cụm<br /> Bươc 2.3: Nếu trung tâm cụm không thay đổi,<br /> chuyển sang bước 3.<br /> Ngược lại, quay trở lại bước 2.2 (bước 2).<br /> Bước 3: (Tăng số cụm)<br /> Nếu K≤ giá trị ấn định số cụm thì K:=K+1, quay trở<br /> lại bước 2.1 (bước 2).<br /> Ngược lại, thuật toán dừng.<br /> <br /> Với thuật toán K-means cải tiến: đưa ra sự<br /> khác biệt, đó là mức độ biến dạng của các<br /> cụm (dựa trên biến dạng để phân cụm).Mức<br /> độ biến dạng của các cụm được tính như sau:<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> 105<br /> <br /> 61(12/2): 102 - 106<br /> <br /> I=S-N(d(w,x ))<br /> Trong đó: w: trung tâm của cụm, N: Số các thành<br /> phần trong cụm; S: Tổng bình phương khoảng<br /> cách giữa các thành phần trong cụm và trung tâm<br /> của không gian Euclidean; I: Mức độ biến dạng<br /> của cụm; d(w,x): là khoảng cách giữa trung tâm w<br /> của cụm và trung tâm của không gian Euclidean x.<br /> <br /> Nhận xét:<br /> + Một cụm có mức độ biến dạng lớn thì trung<br /> tâm cụm đó có vị trí không thích hợp.<br /> + Việc xác định các cụm cũng như xác định<br /> trung tâm của cụm, như vậy thuật toán chủ<br /> yếu tìm trung tâm cụm chính xác và xác định<br /> lại các thành phần trong cụm.<br /> Với thuật toán K-means cải tiến:<br /> + Bước 2: như K-means nhưng khác là:<br /> không xác định trước k điểm mà tăng k lên<br /> dần từ 1. Và chọn cụm có mức độ biến dạng<br /> lớn để phân ra 2 cụm (khi đó 2 cụm này có<br /> mức độ biến dạng giảm, nhỏ hơn).<br /> + Thuật toán cải tiến K-means có độ phức tạp<br /> là O( k 2 nt), như vậy so với thuật toán K-means<br /> có độ phức tạp O(tkn) thì: O( k 2 nt)>O(tkn),<br /> <br /> nhưng không bằng K-mendoids, do k