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

Nội dung text: 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

1. 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à
2. 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
3. 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ặp lại. Trong mỗi lần lặp, tổng số các phép tính khoảng cách phải thực hiện là D*k trong đó D là số đối tượng, k là số lượng các cụm. Với bộ dữ liệu lớn, đòi hỏi cần cải tiến để đáp ứng được yêu cầu về thời gian. 2.3 Thuật toán K-means cải tiến của Weizhong Zhao (PK-means) Để phân cụm dữ liệu lớn, Weizhong Zhao đề xuất một cải tiến theo hướng xử lý song song [5]. Theo ý tưởng của Weizhong Zhao dữ liệu sau khi được chia nhỏ và phân tán, sẽ thực hiện song song việc xác định cụm cho các điểm. Nhờ mô hình MapReduce, các điểm cùng cụm trong các bộ dữ liệu phân tán sẽ được nhóm chung lại với nhau để thực hiện việc tính toán lại tâm và kiểm tra độ hội tụ. Thuật toán cũng tiến hành lặp quá trình xác định cụm và tính toán tâm tương tự như K-means cổ điển. Hình 2 thể hiện quá trình thực hiện MapReduce trên ý tưởng của Weizhong Zhao. Hình 2. Thuật toán PK-means Hàm Map: Đối với mỗi hàm Map, PK-means xây dựng một mảng chứa thông tin về các tâm cụm. Với mảng này, hàm Map có thể tính tâm gần nhất cho mỗi đối tượng. Kết quả trả về của hàm Map là các cặp: . Hàm Combine: Được xây dựng để kết hợp các dữ liệu trung gian của cùng một Map. Khi kết quả trả về được lưu trữ trong bộ nhớ cục bộ của máy thực hiện hàm Map, hệ thống sẽ thực hiện hàm Combine tổng hợp các điểm được gán cho cùng một cụm lại với nhau, tính tọa độ trung bình cho mỗi cụm và ghi lại số lượng các mẫu trong cùng một cụm nhằm thu gọn kết quả, giảm chi phí truyền thông đến Reduce.
4. Trần Hoàng Việt, Nguyễn Thị Tuyết, Trần Thiên Thành 199 Hàm Reduce: Đầu vào là số liệu thu được từ hàm Combine của mỗi máy. Như mô tả trong hàm Combine, dữ liệu bao gồm tổng số các mẫu có trong cùng một cụm và số lượng mẫu trong cụm đó. Hàm Reduce tổng hợp tất cả các mẫu, tính toán và xác định các tâm mới để sử dụng cho lần lặp tiếp theo. Về lý thuyết, việc xử lý song song trên các bộ dữ liệu được chia nhỏ sẽ tăng tốc độ của thuật toán. Tuy nhiên, trong thực tế, thuật toán lại tồn tại một nhược điểm của mô hình MapReduce là mất thời gian chuẩn bị dữ liệu, khởi chạy và truyền tải giữa các máy tính hệ thống. Thuật toán của Weizhong Zhao lại lặp đi lặp lại việc sử dụng MapReduce làm thời gian thực tế tăng lên rất lớn. Trong thực nghiệm của chúng tôi trên R, thậm chí còn chậm hơn K-means cổ điển. 3 Thuật toán K-means cải tiến bằng phương pháp lấy mẫu (SK-meansMR) Ý tưởng PK-means vừa thực hiện việc lặp đi lặp lại quá trình xử lý song song để xác định các tâm cụm vừa lưu trữ liên tục các tâm để xác định độ hội tụ dẫn đến thời gian thực hiện thuật toán tăng lên rất lớn. Để loại bỏ sự phụ thuộc lặp quá trình xử lý song song của thuật toán, chúng tôi sử dụng phương pháp lấy mẫu nhằm xác định các tập con đại diện cho tập dữ liệu lớn. Sau đó sử dụng thuật toán phân cụm cổ điển trên các tập con để xác định k tâm cuối cùng [8]. Quá trình thực hiện phân cụm qua 2 Job MapReduce thể hiện trong hình 3. Hình 3. Quá trình thực hiện phân cụm của thuật toán SK-meansMR Thuật toán: Xác định k tâm sử dụng phương pháp lấy mẫu Input : tập dữ liệu D, k Output : k tâm cụm Map(k1, v1){ Xử lý dữ liệu đầu vào; Chuyển đổi dữ liệu sang kiểu số thực; Output(1, K-means(v1, 2*k)). } Reduce(k2, v2) Output(K-means(v2, k))
5. 200 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” Hình 4. Sơ đồ thể hiện thuật toán xác định tâm SK-meansMR Trong thuật toán trên, chúng tôi thực hiện việc lấy mẫu trên từng tập dữ liệu phân tán. Việc thực hiện lấy mẫu dựa trên phương pháp xác định tâm cụm với số lượng tâm bất kỳ sao cho số lượng tâm có thể đại diện cho tập dữ liệu và tổng số tâm không vượt quá khả năng xử lý của một node. Giả sử, với n hàm Map được xử lý song song và k' tâm là các điểm sẽ đại diện cho tập dữ liệu đầu vào mỗi hàm Map. Tập đại diện sẽ có kích thước n*k' phần tử, phải đảm bảo không vượt quá khả năng xử lý của một Node. Chúng tôi chọn số lượng mẫu là 2*k tâm trong thực nghiệm của mình. Hàm Reduce nhận kết quả từ hàm Map, thực hiện thuật toán K-means để xác định k tâm. 4 Kết quả thực nghiệm Chúng tôi thực nghiệm thuật toán trên 5 máy tính Core 2 Duo E8400 3.00GHz, hệ điều hành Ubuntu 14.04, Hadoop 2.7.3, R 3.3.3 gồm 1 MasterNode và 4 NameNode. Bộ dữ liệu thực nghiệm gồm có KddCup (1999) 42 thuộc tính, 2.155.000 điểm, kích thước 197,6 MB; Individual Household Electric Power Consumption (House) 14 thuộc tính, 4.098.559 điểm, kích thước 226,5 MB. Các bộ dữ liệu được tải về tại UCI Machine Learning Repository 4.1 Đánh giá chất lượng Việc đánh giá chất lượng phân cụm rất khó khăn. Theo [6] [7], có 3 loại độ đo chất lượng phân cụm: đánh giá trong (internal evaluation), đánh giá ngoài (external evaluation), đánh giá quan hệ (relative evalution). Để so sánh chất lượng phân cụm của hai thuật toán, chúng tôi sử dụng chỉ số Davies-Bouldin (DBI) của kỹ thuật đánh giá trong.
6. Trần Hoàng Việt, Nguyễn Thị Tuyết, Trần Thiên Thành 201 Theo [13] chỉ số Davies-Bouldin (DBI) (được David L. Davies và Donald W. Bouldin đưa ra vào năm 1979) xác nhận tính hợp lệ của việc phân cụm đã được thực hiện bằng cách sử dụng các số liệu và các đặc tính vốn có của bộ dữ liệu. Chỉ số Davies-Bouldin được tính theo công thức: 1 n   DB Max ()i j i 1 i j n d(,) ci c j Trong đó: + n là số cụm; + cx là trọng tâm của cụm x; + σx là trung bình khoảng cách của tất cả các phần tử trong cụm x tới trọng tâm cx; + d(ci,cj) là khoảng cách giữa hai trọng tâm của cụm i và j. Giá trị DBI càng nhỏ thì chất lượng phân cụm càng tốt. Bộ dữ liệu KddCup(1999) 42 thuộc tính, 2.155.000 điểm: Bảng 1. Chỉ số DB của K-means và SK- meansMR trên bộ dữ liệu KddCup K K-means SK-meansMR 5 1,578 0,239 6 1,829 0,231 7 0,813 0,263 8 2,069 0,268 Hình 5. Biểu đồ chất lượng phân cụm 9 0,741 0,431 K-means và SK-meansMR trên bộ DL KddCup Bộ dữ liệu House 14 thuộc tính, 4.098.559 điểm: Bảng 2. Chỉ số DB của K-means và SK-meansMR trên bộ dữ liệu House K K-means SK-meansMR 10 1,514 1,091 11 1,252 1,157 12 1,552 1,225 13 1,562 1,279 Hình 6. Biểu đồ chất lượng phân cụm K-means 14 1,438 1,373 và SK-meansMR trên bộ DL House Qua thực nghiệm, có thể thấy chỉ số DBI của thuật toán SK-meansMR thấp hơn K-means cổ điển. Chứng tỏ thuật toán cải tiến SK-meansMR có chất lượng phân cụm tốt hơn K-means. Với mỗi số lượng cụm nhất định, chỉ số DBI của K-means thay đổi rất lớn. Điều này cũng chứng minh việc chọn tâm ảnh hưởng đến chất lượng cụm. Ngược lại, so với K-means, thuật toán SK-meansMR có chất lượng phân cụm rất tốt và ít thay đổi. Qua hai bộ dữ liệu thực nghiệm có thể thấy số lượng điểm lớn cũng ảnh hưởng đến chất lượng phân cụm của thuật toán SK-meansMR.
7. 202 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” 4.2 Đánh giá tốc độ Để đánh giá hiệu năng của thuật toán, chúng tôi tiến hành thực nghiệm so sánh thuật toán SK-meansMR với thuật toán K-means cổ điển trên hai bộ dữ liệu: KddCup và House. Đối với thuật toán SK-meansMR, chúng tôi thực nghiệm với số lượng mẫu đại diện cho mỗi tập con dữ liệu là 2*k tâm. Bộ dữ liệu KddCup(1999) 42 thuộc tính, 2.155.000 điểm: Bảng 3. Thời gian chạy của K-means và SK-meansMR trên bộ dữ liệu KddCup K K-means SK-meansMR 5 119,76 56,44 6 122,06 56,50 7 146,18 56,50 8 155,37 57,59 Hình 7. Biểu đồ tốc độ của K-means và 9 190,33 58,30 SK-meansMR trên bộ dữ liệu KddCup Bộ dữ liệu House 14 thuộc tính, 4.098.559 điểm: Bảng 4. Thời gian chạy (s) của K-means và SK-meansMR trên bộ dữ liệu House K K-means SK-meansMR 10 65,07 56,82 11 67,91 57,73 12 68,56 58,84 13 74,93 58,09 Hình 8. Biểu đồ tốc độ của K-means và 14 81,28 59,40 SK-meansMR trên bộ dữ liệu House Qua thực nghiệm, có thể thấy thời gian thực hiện thuật toán SK-meansMR giảm đáng kể so với thời gian thực hiện thuật toán K-means cổ điển. Với số lượng tâm cụm k = 10, k = 11 đối với House và k = 5, k = 6 đối với KddCup, thời gian thực hiện thuật toán K-means tăng không đáng kể. Tuy nhiên, với số lượng tâm cụm lớn hơn, thời gian thực hiện thuật toán K-means bắt đầu tăng rất nhanh. Ngược lại, thuật toán SK-meansMR của chúng tôi cho kết quả tăng đều về mặt thời gian khi thay đổi số lượng cụm trên cả hai bộ dữ liệu. 5 Kết luận và hướng nghiên cứu trong tương lai Trong nghiên cứu chúng tôi đã trình bày thuật toán SK-meansMR, thực nghiệm và đánh giá để chứng minh chất lượng phân cụm và tốc độ của thuật toán cải tiến tốt hơn K-means cổ điển. Bài toán phân cụm dữ liệu ứng dụng rất nhiều trong thực tế. Trong thời gian đến, chúng tôi tiếp tục nghiên cứu ứng dụng trên bài toán phân cụm dữ liệu điểm sinh viên và thực nghiệm trên bộ dữ liệu điểm của trường Đại học Quy Nhơn. Sau đó mô hình hóa kết quả thực nghiệm và phân tích từng cụm dữ liệu để đưa ra các tư vấn phù hợp cho sinh viên đồng thời tiếp tục cập nhật và phân cụm dữ liệu các khóa tiếp theo để chứng minh tính đúng đắn trong các phân tích và tư vấn của mình.
8. Trần Hoàng Việt, Nguyễn Thị Tuyết, Trần Thiên Thành 203 Tài liệu tham khảo 1. George Karypis, Eui-Hong (Sam) Han, and Vipin Kumar. “Multilevel Refinement for Hierarchical Clustering”. 1999. 2. Graham J. Williams, Simeon J. Simoff, “Data Mining: Theory, Methodology, Techniques, and Applications”, Springer-Verlag, 2006. 3. Huang, Z., “Clustering Large Data Sets with Mixed Numeric and Categorical Values, In Proceedings of The First Pacific-Asia Conference on Knowledge Discovery and Data Mining”, Singapore, World Scientific, 1997. 4. J. A. Hartigan and M. A. Wong, “A K-means clustering algorithm”, Applied Statistics, Vol. 28, pp. 100-108, 1979. 5. Weizhong Zhao, Huifang Ma, and Qing He, “Parallel K-Means Clustering Based on MapReduce”, 2009. 6. Darius Pfitzner, Richard Leibbrandt, David M. W. Powers (2009): “Characterization and evaluation of similarity measures for pairs of clusterings”. Knowl. Inf. Syst. 361-394. 7. Maria Halkidi, Yannis Batistakis, Michalis Vazirgiannis: “On Clustering Validation Techniques”. J. Intell. Inf. Syst. 17(2-3): 107-145, 2001. 8. Trần Thiên Thành, Nguyễn Thị Tuyết, Hồ Văn Lâm, Trần Hoàng Việt, “Cài đặt thuật toán K-means cải tiến bằng phương pháp lấy mẫu áp dụng mô hình lập trình MapReduce trên công cụ R”, bài báo đăng trong Kỷ yếu “Hội thảo Một số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông” lần thứ 20, 11/2017. 9. Oyelade O. J, Oladipupo O. O, Obagbuwa I. C, “Application of k-Means Clustering algorithm for prediction of Students’ Academic Performance”, (IJCSIS) International Journal of Computer Science and Information Security, Vol. 7, No. 1, 2010. 10. Md.H.I.Shovon, M. Haque, “An Approach of Improving Student’s Academic Performance by using K-means clustering algorithm and Decision tree”, (IJACSA) International Journal of Advanced Computer Science and Applications, Vol.3, No. 8, 2012. 11. Byoungwook Kim, JaMee Kim, Gangman Yi, “Analysis of Clustering Evaluation Considering Features of Item Response Data Using Data Mining Technique for Setting Cut-Off Scores”, Symmetry 2017, 9, 62. 12. Tom White, Hadoop, The Definitive Guide, 4th Edition, O’Reilly Media, Inc, 2015. 13. Wikipedia, “Cluster analysis”, Website: