基于最小生成树的并行分层聚类算法  

An Adaptive Parallel Hierarchical Clustering Algorithm without Memory Conflicts

作　　者：李朝健[1] 李朝鹏[2] 李肯立[2] 

机构地区：[1]湖南工程学院,湖南湘潭411101 [2]湖南大学计算机与通信学院,湖南长沙410082

出　　处：《微电子学与计算机》2008年第9期196-198,共3页Microelectronics & Computer

基　　金：国家自然科学基金项目(90715029)

摘　　要：分层聚类技术在图像处理、入侵检测和生物信息学等方面有着极为重要的应用,是数据挖掘领域的研究热点之一.针对目前基于SIMD模型的并行分层聚类算法存在的无法解决存储冲突问题,提出一种基于最小生成树无存取冲突的并行分层聚类算法.算法使用O(p)个并行处理单元,在O(n2/p)的时间内对n个输入数据点进行聚类,与现有文献结论进行的性能对比分析表明,本算法明显改进了现有文献的研究结果,是一种无存储冲突的并行分层聚类算法.Hierarchial clustering technology plays a very important role in image processing, intrusion detection and bioinfonnatics applications, which is one of the most extensively studied branch in data mining. Presently the parallel hierarchical algorithms based on SIMD can not process memory conflicts among different processors. To overcome this shortcomings, a new parallel algori：thm based on minimum spanning tree is proposed in this paper. The proposed algorithms can cluster n objects with O（p） processors in O（n^2/p） time, Performance comparisons show that it is the first/xu-alld hierarchical clustering algorithm algorithms without memory conflicts, and thus it is an improved result over the past researches.

关 键 词：分层聚类 并行算法 存储冲突 

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