图形处理器在分层聚类算法中的通用计算研究摘要：ROCK是一种采用数据点间的公共链接数来衡量相似度的分层聚类方法,该方法对于高维、稀疏特征的分类数据具有高效的聚类效果。其邻接度矩阵计算是影响时间复杂度的关键步骤,将图形处理器(GPU)强大的浮点运算和超强的并行计算能力应用于此步骤,而其余步骤由CPU完成。基于GPU的ROCK算法的运算效率在AMD643500+CPU和NVIDIAGeForce6800GT显卡的硬件环境下经过实验测试,证明其运算速度比完全采用CPU计算速度要快。改进的分层聚类算法适合在数据流环境下对大量数据进行实时高效的聚类的操作。关键词：聚类分析;图形处理器；通用计算；分层聚类：TP311文献标志码：A：1001-3695(2008)08-2319-03ResearchofgeneralpurposecomputationonhierarchicalclusteringalgorithmusinggraphicsprocessingunitLILin??1,2??,LIKen-li??1,ZHUYa-li??1,2??(1.CollegeofComputerCommunication,HunanUniversity,Changsha410082,China;2.Dept.ofComputerScience,HengyangNormalUniversity,HengyangHunan421008,China)Abstract:Thispaperproposedanovelalgorithmnamedrobustclusteringalgorithmforcategorical(ROCK)modeltoimproveclusteringqualityanditwasefficientforthedataofhighdimensionality,sparsityandcategoricalnature.Anovelconceptcalledcommonneighbors(links),anappropriateselectionofnearestneighbors,wasadoptedassimilaritymeasurebetweenapairofpoints.Thekeystepofcomputingadjacencymatrix,whichhadasignificanteffectonthetimecomplexity,couldbeimplementedbyGPU’sexcellentperformancesuchasthenumberoffloating-pointoperationspersecondandtheparallelprocessingonfragmentvectorprocessing,andtheotherscouldbefinishedbycentralprocessingunits(CPU).SomeexperimentsconductedinaPCwithAMD643500+CPUandNVIDIAGeForce6800GTgraphiccarddemonstratethatthepresentedalgorithmisfasterthanthepreviousCPU-basedalgorithms,thusitisapplicablefortheclusteringdatastreamthatrequiringforhighspeedprocessingandhighqualityclusteringresults.Keywords：clusteringanalysis;graphicsprocessingunits(GPU);generalpurposecomputation;hierarchicalclustering数据聚类是将具体或抽象的数据集划分为若干组或类,同一类中的数据具有尽可能大的相似性,而不同类中的数据具有尽可能大的相异性。在聚类过程中无须用户提供先验的分类知识,而是根据数据实际的分布情况得到自然的聚集结果。聚类分析能够从研究对象的特征数据中挖掘出关联规则，发现在数据库中未知的对象类，为数据挖掘提供有力的支持,是数据挖掘的重要分支，作为一种强有力的信息处理方法而被广为研究。当前主要的聚类算法有[1]基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法、基于模型的方法等。早期的聚类算法是采用距离来度量两个数据点间的相似程度,如K-平均算法和K中心点算法。但是这种度量函数不适合分类属性数据集的聚类,分类属性的属性值之间通常不存在大小等顺序关系,而且分类属性数据集通常具有高维、稀疏特征,所以采用数据点间的公共链接数来衡量相似度,笔者提出了ROCK(robustclusteringalgorithmforcategorical)分层聚类算法[2]。然而,随着传感器和计算机网络技术的发展,在越来越多的实际应用中,当数据是以流的形式出现时,在数据流环境下研究数据聚类方法除了需要考虑聚类质量以外,聚类处理速度往往也是数据流挖掘算法的一个重要指标。由于GPU图形处理器为图形渲染设计,超长流水线及并行计算[3，4]和可编程性的出现使其运算速度越来越快。于是越来越多的人开始用其做一些非绘制方面的通用计算[5]，如代数计算、流体模拟、数据库操作、频谱变换和滤波等。本文在分析现有的数据流聚类方法[6]的同时,提出了一种使用GPU进行计算的ROCK算法,利用GPU强大的浮点运算能力来处理ROCK聚类算法中表示点间连接度的邻接矩阵计算,通过将连接度计算操作转移到GPU,提升了聚类挖掘速度。若将其应用到数据流聚类操作，可满足流聚类对实时高效处理速度的要求。同时,考...