Parallel bisecting <Emphasis Type="Italic">k</Emphasis>-means with prediction clustering algorithm |
| |
Authors: | Yanjun Li Soon M Chung |
| |
Affiliation: | (1) Department of Computer Science and Engineering, Wright State University, Dayton, Ohio 45435, USA |
| |
Abstract: | In this paper, we propose a new parallel clustering algorithm, named Parallel Bisecting k-means with Prediction (PBKP), for message-passing multiprocessor systems. Bisecting k-means tends to produce clusters of similar sizes, and according to our experiments, it produces clusters with smaller entropy
(i.e., purer clusters) than k-means does. Our PBKP algorithm fully exploits the data-parallelism of the bisecting k-means algorithm, and adopts a prediction step to balance the workloads of multiple processors to achieve a high speedup. We implemented PBKP on a cluster of Linux
workstations and analyzed its performance. Our experimental results show that the speedup of PBKP is linear with the number
of processors and the number of data points. Moreover, PBKP scales up better than the parallel k-means with respect to the dimension and the desired number of clusters.
This research was supported in part by AFRL/Wright Brothers Institute (WBI). |
| |
Keywords: | Clustering Bisecting k-means Parallel processing Performance analysis |
本文献已被 SpringerLink 等数据库收录! |
|