ABSTRACT -- Despite its simplicity and its linear time, a serial K-means algorithm's time complexity remains expensive when it is applied to a problem of large size of multidimensional vectors. In this paper we show an improvement by a factor of O(K/2), where K is the number of desired clusters, by applying theories of parallel computing to the algorithm. In addition to time improvement, the parallel version of K-means algorithm also enables the algorithm to run on larger collective memory of multiple machines when the memory of a single machine is insufficient to solve a problem. We show that a problem size can be scaled up to O(K) times a problem size on a single machine.
Keywords -- Clustering algorithms, K-means algorithms, Parallel Algorithms, Computational Geometry, Data Mining

บทคัดย่อ -- ถึงแม้ว่าอัลกอริทึมเคมีนจะง่ายและทำงานในเวลาเชิงเส้น แต่เมื่อใช้ในการแก้ปัญหาเวกเตอร์แบบหลายมิติขนาดใหญ่ก็จะใช้เวลาในการทำงานที่มากและซับซ้อน ในบทความนี้ได้มีการนำเสนอวิธีการปรับปรุงอัลกอริธึมเคมีนโดยการนำการคำนวณแบบขนานเข้ามาร่วมด้วย ผลที่ได้แสดงให้เห็นว่าได้ผลดีขึ้นด้วยปัจจัย O(K/2) โดยที่ K คือจำนวนกลุ่มที่ต้องการ นอกจากนี้อัลกอริธึมเคมีนรุ่นที่ใช้การคำนวณแบบขนานยังสามารถทำงานในเครื่องหลายๆ เครื่องที่มีหน่วยความจำแบบสะสมได้ขนาดใหญ่ เมื่อหน่วยความจำของเครื่องใดเครื่องหนึ่งไม่เพียงพอต่อการแก้ปัญหาอีกด้วย ผลการทดลองแสดงให้เห็นว่าขนาดของปัญหาสามารถเพิ่มขึ้นในขนาด O(K) เท่าของขนาดปัญหาบนเครื่องเดี่ยว
คำสำคัญ -- อัลกอริทึมแบบกลุ่ม อัลกอริทึมเคมีน อัลกอริทึมแบบขนาน เรขาคณิตเชิงคำนวณ เหมืองข้อมูล