Một cải tiến thuật toán K-Means song song sử dụng phương pháp lấy mẫu

Nghiên cứu này trình bày ý tưởng cải tiến thuật toán phân cụm dữ liệu PK-means, phân tích ưu và nhược điểm của thuật toán này, sau đó trình bày thuật toán cải tiến của chúng tôi SK-meansMR và thực nghiệm đánh giá chất lượng, tốc độ của thuật toán trên dữ liệu lớn.
Nội dung trích xuất từ tài liệu:
Một cải tiến thuật toán K-Means song song sử dụng phương pháp lấy mẫu 196 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” Một cải tiến thuật toán K-Means song song sử dụng phương pháp lấy mẫu Trần Hoàng Việt1, Nguyễn Thị Tuyết1, Trần Thiên Thành1 1 Khoa Công nghệ thông tin, Đại học Quy Nhơn tranhoangviet92@gmail.com, nguyenthituyet@qnu.edu.vn,thanhtranthien@gmail.com Tóm tắt: Phân cụm dữ liệu là một kỹ thuật ứng dụng trong nhiều lĩnh vực khác nhau. K-means là thuật toán kinh điển trong phân cụm dữ liệu. Hiện tại, trong thời điểm bùng nổ dữ liệu, K-means cũng như các thuật toán khác không đáp ứng yêu cầu về tốc độ. Việc cải tiến thuật toán để xử lý dữ liệu lớn là nhu cầu cấp thiết. Trong nghiên cứu này, chúng tôi trình bày ý tưởng cải tiến thuật toán phân cụm dữ liệu PK-means, phân tích ưu và nhược điểm của thuật toán này, sau đó trình bày thuật toán cải tiến của chúng tôi SK-meansMR và thực nghiệm đánh giá chất lượng, tốc độ của thuật toán trên dữ liệu lớn. Keywords: K-means cải tiến, MapReduce, PK-means, SK-meansMR. 1 Mở đầu “Chúng ta đang tràn ngập trong thông tin nhưng lại khát tri thức”, nhận định của John Naisbett’s đã thể hiện được nhu cầu rất lớn về khai phá dữ liệu. Đặc biệt trong thời điểm bùng nổ thông tin, việc khai phá dữ liệu lớn càng trở nên cấp thiết hơn nữa. Các bài toán hiện tại thường gắn liền với tập dữ liệu lớn nhưng các thuật toán truyền thống không đáp ứng yêu cầu về thời gian. Xử lý song song trên môi trường phân tán là một giải pháp để giải quyết vấn đề này. Phân cụm dữ liệu là một bước quan trọng trong khai phá dữ liệu, được ứng dụng trong nhiều lĩnh vực khác nhau như: thiên văn học, tin sinh học, thương mại điện tử, phát hiện lừa đảo, quảng cáo, quản lý quan hệ khách hàng, chăm sóc sức khỏe, viễn thông, đầu tư. Trong phân cụm dữ liệu, thuật toán K-means là thuật toán kinh điển nhưng không thể giải quyết tập dữ liệu lớn. Để khắc phục một số nhược điểm của K-means khi xử lý dữ liệu lớn, các cải tiến thường sử dụng mô hình lập trình MapReduce để tăng hiệu suất thuật toán. Một trong những thuật toán cải tiến nổi tiếng của K-means là PK-means của Weizhong Zhao [5]. Ý tưởng của thuật toán là chia nhỏ dữ liệu rồi thực hiện xác định cụm trên từng phần dữ liệu đó. Kế tiếp tổng hợp các điểm cùng cụm lại với nhau thực hiện tính toán lại tâm cụm, kiểm tra độ hội tụ, quá trình này cũng được lặp đi lặp lại tương tự như K-means cổ điển. Tuy nhiên, quá trình chuẩn bị dữ liệu, truyền và nhận dữ liệu trong hệ thống phân tán mất một khoảng thời gian nhất định. Vì vậy, nếu áp dụng mô hình này cần hạn chế việc gọi lại cả quá trình nhiều lần. Đối với ý tưởng của Weizhong Zhao, thuật toán cần lặp đi lặp lại quá trình phân tán và xử lý song song làm cho thuật toán trở nên kém hiệu quả. Để cải tiến thuật toán PK-means, chúng tôi thực hiện chọn một số lượng mẫu nhất định đại diện cho từng bộ dữ liệu. Sau đó thực hiện phân cụm trên tập mẫu đó để xác định k tâm cụm cuối cùng. Khi có được k tâm cụm, chúng tôi xác định các điểm trong từng cụm. Đây cũng là Trần Hoàng Việt, Nguyễn Thị Tuyết, Trần Thiên Thành 197 kết quả phân cụm của thuật toán. Số lần thực hiện MapReduce trong giải thuật của chúng tôi luôn luôn là hai lần. Như vậy, trong thuật toán này, rõ ràng giảm thời gian chuẩn bị, truyền và nhận dữ liệu hơn so với thuật toán PK-means. Để chứng minh hiệu quả thuật toán của mình, chúng tôi cũng tiến hành thực nghiệm trên hai khía cạnh. Một là, việc lấy mẫu có ảnh hưởng đến chất lượng phân cụm hay không. Hai là, so sánh tốc độ với thuật toán K-means cổ điển. Nghiên cứu gồm 5 phần. Sau phần mở đầu, chúng tôi trình bày các kiến thức liên quan về mô hình lập trình MapReduce, về các thuật toán K-means và PK-means. Phần ba trình bày về một cải tiến thuật toán K-means bằng phương pháp lấy mẫu (SK-meansMR). Phần bốn là kết quả thực nghiệm để chứng minh hiệu quả thuật toán SK-meansMR. Cuối cùng là phần kết luận và hướng nghiên cứu trong tương lai. 2 Kiến thức liên quan 2.1 Mô hình lập trình song song MapReduce MapReduce là mô hình lập trình song song được Google đề xuất để xử lý dữ liệu lớn trong môi trường phân tán. Theo [12] MapReduce gồm hai bước Map và Reduce thực hiện hoàn toàn độc lập, song song trên các cặp dữ liệu (key, value): Hàm Map Nhận dữ liệu đầu vào (input) dưới dạng (key1, value1), thực hiện xử lý lọc (filter) và phân loại (sort) trên dữ liệu rồi trả về danh sách các cặp dữ liệu (key2, value2): map(key1,value1)  list(key2,value2) Hàm Reduce Hệ thống nhóm các value theo key từ kết quả của các hàm Map, tạo thành tập các cặp dữ liệu với cấu trúc (key, tập các value cùng key). Hàm Reduce nhận các cặp dữ liệu này, thực hiện xử lý trên từng cặp dữ liệu và trả kết quả về cho người dùng: reduce(key2, list (value2))  list(value3) Hình 1. Mô hình lập trình MapReduce 2.2 Thuật toán K-means Thuật toán K-means [4] là một thuật toán quan trọng và được sử dụng phổ biến trong kỹ thuật phân cụm. K-means chia một tập D đối tượng thành k cụm sao cho kết quả tương đồng 198 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” trong cùng cụm tương đối cao, ngược lại là sự tương đồng thấp giữa các cụm khác nhau. Ý tưởng thuật toán: Bước 1: Thuật toán xác định k tâm ngẫu nhiên. Bước 2: Thuật toán lặp lại quá trình: - Xác định cụm cho các điểm; - Xác định tâm cụm mới; - Nếu đạt ngưỡng hội tụ giữa tâm cụm cũ và mới hoặc qua một số lần lặp nhất định thì kết thúc thuật toán. Nhược điểm của K-means là lặp lại việc tính khoảng cách để xác định cụm cho các điểm lặp đi lặ ...