随着数字传感器、高性能计算与通信、大容量数据存储等技术的飞速发展，现代社会每时每刻都在产生着大量数据。机器学习是分析原始数据、提取有价值信息的一种有效方法。机器学习算法可分为有监督算法与无监督算法两类。与前者相比，后者不需要人工标记的训练数据，因此适用面更广。聚类分析是无监督机器学习的一种常用方法。传统的聚类分析算法在众多领域都得到成功的应用，但是它通常要求全体输入数据被一次性载入物理主机的内存。鉴于这种特性，本文将传统聚类分析算法称为批处理聚类分析算法。然而，在某些应用背景下，批处理算法无法高效地完成聚类分析任务，例如：反应时间受限型应用、内存容量受限型应用、检测与祛除冗余数据，等等。在上述应用背景下，全体输入数据被划分成若干个子集，聚类算法需要逐步推进、逐个处理每个数据子集、最终得到全体输入数据的聚类结果。能够完成这种任务的算法被称作增量式聚类算法。增量式聚类算法通常需要应对高实时性、大数据量问题，对硬件平台的计算能力提出较高要求，并行计算是满足这一要求的常用方法。通用计算图形处理器(General Purpose Graphic Processing Unit, GPGPU)是一种具有诸多优势的新型并行计算器件。只有以单指令多数据(Single Instruction Multiple Data,SIMD)的方式并发执行大量线程(线程数量明显多于处理器核心的数量)，才有可能比较充分地发挥GPGPU的计算能力。如果某种算法能够以上述方式执行，那么本文就称该算法具有较好的GPGPU并行性、或者称该算法是GPGPU友好的。本文研究的是并行计算领域与机器学习领域的一项交叉课题，其主要目的是：分析GPGPU给设计并行增量式聚类算法带来了怎样的挑战，设计聚类精度与GPGPU并行性相平衡的增量式聚类算法，并基于统一计算设备架构(Compute Unified DeviceArchitecture, CUDA)优化所设计的算法。本文的主要贡献如下：1.分析并指出现有的增量式聚类算法所面临的“聚类精度-GPGPU并行性”两难困局。本文归纳出现有增量式聚类算法所采取的两种处理方式：逐个数据块处理方式(简称逐块处理方式)与逐个数据点处理方式(简称逐点处理方式)。通过分析，指出现有增量式聚类算法面临的“聚类精度-GPGPU并行性两难困局”：逐块处理算法为了较好的GPGPU并行性而牺牲了聚类精度；逐点处理算法则恰恰相反。2.基于高斯混合模型提出了一种自顶向下的逐块处理增量式聚类算法(Top-DownIncremental Gaussian Mixture Model clustering algorithm,TDIGMM算法)。TDIGMM算法采用自顶向下的方式推进聚类结果的演化：算法在处理完当前一步新到来数据块之前即可预先近似估计全部已到来数据(包括新到来数据块)中包含簇的数量；以预估的簇数量作为约束条件，可使用更具弹性的方法辨识来自同一个簇的数据点，显著减少相同至不同的错误隶属(即实际上隶属同一个簇的数据点被归入不同的簇)。TDIGMM算法较好的GPGPU并行性体现在：其最耗时部分是GPGPU友好的。3.提出了一种非参数化的、以演进粒度为中心的增量式聚类算法(Evolving-Granularity-Centered incremental clustering algorithm, EGC算法)。本文给出了增量式聚类算法演进粒度的定义；指出演进粒度越大则发生不同至相同错误隶属(即实际上属于不同簇的数据点被归入相同的簇)的概率越高，反之亦然；并针对这一结论给出了形式化证明。EGC算法力图整合逐块处理方式与逐点处理方式的优势，以介于两者之间的演进粒度——微型簇——来推动聚类结果的演进。微型簇可以通过GPGPU友好的方式被生成；它们被逐个处理，以得到当前最新的聚类结果。微型簇的总数一般远远小于数据点的总数，这有助于减少串行操作的总数、显著缩短GPGPU处于低利率状态的时长。4.基于CUDA优化TDIGMM算法和EGC算法。为了保证并行计算系统的计算能力得到充分利用，数据传输和访问延迟也可能是一个不可忽视的因素，增量式聚类算法需要持续地载入新到来数据，尤其需要考虑这个因素。本文使用CUDA架构下的流水线模式隐藏EGC算法的数据传输延迟；TDIGMM和EGC算法的数据访问操作分别通过数据预读取和数据重排序得到了优化。本文通过实验验证了TDIGMM算法和EGC算法的聚类精度、GPGPU并行性，及其优化方法的性能。最后，总结全文，并对未来的工作进行展望。