Giải thuật K-Means xử lý song song với mô hình MapReduce

Authors

  • Khoa CNTT
  • Trần Thiên Thành
  • Nguyễn Thị Như

Abstract


Tóm tắt nội dung –  K-Means là giải thuật phân cụm dữ liệu khá nổi tiếng và được sử dụng phổbiến trong lĩnh vực khai phá dữ liệu, nó cho phép chia n đối tượng thành k cụm sao cho tổng bìnhphương khoảng cách giữa các đối tượng đến tâm nhóm là nhỏ nhất. Tuy nhiên, phương pháp này cònnhiều hạn chế do việc tính khoảng cách giữa các đối tượng đến các tâm và việc xác định lại tâm đượcthực hiện lặp lại nhiều lần khiến giải thuật mất nhiều thời gian xử lý và khó triển khai trên tập dữ liệulớn. Nhằm cải tiến nhược điểm trên, trong bài báo này, chúng tôi chọn giải pháp triển khai phân cụmdữ liệu bằng giải thuật K-Means dựa trên mô hình lập trình song song MapReduce được cài đặt trên hệthống Hadoop. Cuối bài báo chúng tôi đưa ra một số kết quả thực nghiệm cho thấy giải thuật phân cụmK-Means trên mô hình MapReduce đạt được hiệu suất cao hơn khi phân loại tự động dữ liệu lớn và nóchứng tỏ tính hiệu quả và tính chính xác của giải thuật.

Keywords – Data mining, K-Means, MapReduce;

References

J. D. a. S. Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters," 2004.

"Apache Mahout," [Online]. Available: http://mahout.apache.org. [Accessed 15 4 2015].[3] "Maven," [Online]. Available: http://maven.apache.org/. [Accessed 10 4 2015].

W. Tom, Hadoop_The definitive Guide - 3rd edition, O'reilly, 2012.

J. A. Hartigan. and. M. A. Wong, "A k-means clustering algorithm," Applied Statistics, vol. 28, pp. 100-108, 1979.

D. M. a. N. S. Kehar Singh, "Evolving limitations in K-means algorithm in data mining and their removal," International Journal of Computational Engineering &Management, vol. 12, 2011.

Published

2015-09-04