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

Parallel clustering algorithm by deterministic annealing

作　　者：杨广文[1] 史树明[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《清华大学学报（自然科学版）》2003年第4期480-483,共4页Journal of Tsinghua University(Science and Technology)

基　　金：国家教育振兴计划

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

关 键 词：确定性退火 并行聚类算法 划分聚类 全局最优解 机群系统 并行计算 

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构]