图形处理器在分层聚类算法中的通用计算研究  

Research of general purpose computation on hierarchical clustering algorithm using graphics processing unit

作　　者：李琳[1] 李肯立[1] 朱雅丽[1] 

机构地区：[1]湖南大学计算机与通信学院

出　　处：《计算机应用研究》2008年第8期2319-2321,2327,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(60603053,60274026,60373089,60403002);衡阳师范学院教学研究资助项目(A267);衡阳师范学院青年科研基金资助项目(07A29)

摘　　要：ROCK是一种采用数据点间的公共链接数来衡量相似度的分层聚类方法,该方法对于高维、稀疏特征的分类数据具有高效的聚类效果。其邻接度矩阵计算是影响时间复杂度的关键步骤,将图形处理器(GPU)强大的浮点运算和超强的并行计算能力应用于此步骤,而其余步骤由CPU完成。基于GPU的ROCK算法的运算效率在AMD 643500+CPU和NVIDIAGeForce 6800 GT显卡的硬件环境下经过实验测试,证明其运算速度比完全采用CPU计算速度要快。改进的分层聚类算法适合在数据流环境下对大量数据进行实时高效的聚类的操作。This paper proposed a novel algorithm named robust clustering algorithm for categorical （ROCK） model to improve clustering quality and it was efficient for the data of high dimensionality, sparsity and categorical nature. A novel concept called common neighbors（ links）, an appropriate selection of nearest neighbors, was adopted as similarity measure between a pair of points. The key step of computing adjacency matrix, which had a significant effect on the time complexity, could be implemented by GPU＇ s excellent performance such as the number of floating-point operations per second and the parallel processing on fragment vector processing, and the others could be finished by central processing units （CPU）. Some experiments conducted in a PC with AMD 643500 ＋ CPU and NVIDIA GeForce 6800 GT graphic card demonstrate that the presented algorithm is faster than the previous CPU-based algorithms, thus it is applicable for the clustering data stream that requiring for high speed processing and high quality clustering results.

关 键 词：聚类分析 图形处理器 通用计算 分层聚类 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]