论文部分内容阅读
谱聚类作为极具竞争力的聚类算法,目前已经取得了较广泛的应用。谱聚类算法本质是通过特征分解,将原始的高维数据空间映射到特征向量空间,即低维的线性测度空间,然后对特征向量空间中的数据点进行聚类,所以谱聚类方法相对简单,对复杂分布的数据也十分有效。但是作为一种新发展的聚类算法,谱聚类算法本身仍存在许多值得深入研究的问题,在如何构造相似矩阵W、如何处理特征向量、如何自动确定聚类数目、如何选取Laplacian矩阵、如何运用到大规模学习问题中几个方面尤为明显。在如今普遍的海量信息面前,谱聚类适用于大规模学习的问题亟待解决。随着当代科学与工程、制造业的需求驱动,高性能计算近些年来得到迅猛发展。相对于CPU的发展放缓,图形处理单元(GPU,Graph Processing Unit)在高性能计算方面的卓越表现受到越来越多人的瞩目。GPU优秀的计算性能以及高速的访存带宽为谱聚类在应用到大规模数据时,提高计算效率和节省内存空间提供了良好的平台支持。 为了解决利用谱聚类进行大规模数据处理时计算和空间复杂度较大的问题,本文在CPU/GPU异构编程模型上实现了一个基于t近邻相似矩阵的谱聚类方法(HSC)。同时针对数据规模过大时设备内存受限导致HSC不能正常工作的问题,本文提出了将数据分块后形成流水机制并在CPU/GPU异构编程模型上进行实现(HBSC)。在配有GTX480的单个计算节点和配有4个计算节点的MPI集群环境下,使用rcv1、covtypes、kddb和url等不同规模的数据集进行了实验。实验结果表明,HSC和HBSC均达到了较好的聚类质量,并且取得了较高的计算性能。对于较小规模的数据集rcv1,HSC是4个CPU计算节点(4核4线程)组成的集群计算环境下(MPI4*4)并行谱聚类算法(PSC)性能的4倍左右,而对于较大规模的数据集url,HBSC的计算性能则能达到PSC在MPI4*4工作模式下的7倍。