利用确定性退火技术的并行聚类算法

划分聚类和分级聚类是两种基本的聚类手段。划分聚类常常可以转换为一个全局最优化问题 ,传统的划分聚类方法很难得到全局最优解。基于确定性退火技术 ,给出了解决划分聚类问题的一种算法 ,并给出了在集群系统上的并行化方案 ,推导出了参与并行计算的最佳处理机数目 ,给出了加速比的估算公式。通过模拟算例可知 ,该算法的特殊结构适合在机群系统上进行并行计算 ,特别对聚类点集相当大的聚类问题 ,由于任务间的通信开销与计算量相比很小 ,能够达到很好的并行效果

Parallel clustering algorithm by deterministic annealing

Partition clustering and hierarchical clustering are two fundamental clustering methods. Partition clustering is often implemented as an optimization problem, but traditional partition clustering algorithms have difficulty achieving global optimization. This paper describes a parallel partition clustering algorithm that uses deterministic annealing to avoid the disadvantages of traditional methods and to improve performance. The algorithm was then implemented in parallel on cluster of workstations (COW). The optimal processor number and the speedup ratio were evaluated. Theoretical analysis and the simulation results show that COW is a good choice for the parallel clustering algorithm with deterministic annealing. High speedup ratios are achieved for clustering problems with large clusters with relatively low communication to computation ratios.