论文部分内容阅读
聚类分析作为一种新兴的数据处理技术,近年来已成为数据挖掘中一个非常活跃的研究方向。同时随着实际应用中数据流的广泛出现,不仅需要考虑提高聚类质量,如何提升聚类处理速度也是一个亟需解决的问题。由于目前各种聚类算法均是采用CPu进行计算实现,聚类效率无法完全满足实际需要。图形处理器(graphics processing unit:以下简称GPU)具有很高的并行计算能力、超常的浮点运算速度。本文将目前几种典型聚类算法在CPU上执行的部分关键计算步骤转移到GPu上,进行非图形绘制的通用计算处理,以提高聚类速度。
与经典K-means算法相比,enhanced K-means算法只需处理部分点集的距离计算和比较操作,因而可使聚类效率得到较大提高。以此算法为基础,提出了基于此算法的CPU+GPU的协同处理模式,利用GPU多个子素处理器可以进行并行计算的特性,将算法中处理比较耗时的距离计算与比较、每次参与循环计算的点集合判断步骤由GPu实现,而初始化、中心点计算、聚类结束判定步骤仍由CPU实现,在这种协同计算模式下,可使enhanced K-means算法的聚类效率提高约35%。
其次,对经典ROCK和VBACC层次聚类算法及改进的基于动态近邻选择模型的DNNS算法进行分析比较。在此基础上,借鉴Larsen提出的利用GPU进行矩阵快速相乘的思想,将此思想和GPU多子素处理器并行处理特点结合起来,应用在DNNS算法中,即将算法中的主要运算步骤连接度矩阵计算用GPu实现,而建堆及合并操作由CPu完成,这样可使DNNs算法的聚类时间减少25%左右。
在一台配有Pentium IV 3.4G CPu和NVIDIA GeForce 6800 GT显卡的计算机上实现了上述基于GPU的算法和·完全由CPU完成的算法,实现过程中注意到CPU与GPU之间较小总线带宽,将CPU与GPU之间的数据传输最小化。实验结果表明:在具有相同聚类质量的前提下,基于GPU的聚类算法的运算速度明显快于传统的基于CPU的聚类算法的处理速度。因此,这种GPu和CPU的协同处理模式将对数据流的快速聚类实现具有一定的借鉴意义。