聚类分析是一种重要的数据分析技术,其旨在将数据集划分成不同的子集,并且同一个子集中的数据元素具有较高相似度。经过研究者多年的研究,众多性能高效的聚类算法相继被提出,包括基于划分的聚类、层次聚类、密度聚类、网格聚类、模糊聚类等。聚类分析同时具有广泛的应用场景,如图像分割、推荐系统、异常值检测、信息检索等。某些场景对聚类结果的平衡度提出了要求,然而传统聚类算法通常未对聚类结果的平衡度,即未对任意两个簇之间的数据元素个数最大差值做出约束,所以生成的簇平衡性往往较差,经常出现簇过大或者过小簇情形。因此,如何保证聚类结果质量的同时进一步约束结果簇的平衡性具有重要的研究和应用价值。本文针对平衡聚类算法及其性能优化展开研究,主要工作包括:(1)提出一种基于模拟退火与贪心策略的平衡聚类算法。为了提高现有平衡聚类算法的聚类效果与时间性能,提出了一种低时间复杂度的平衡聚类算法。该算法采用模拟退火策略在数据集中首先快速找到合适的平衡聚类初始点,模拟退火作为一种近似算法可以在较短时间内获得NP-Hard问题的一个高质量的解决方案代替最优解,降低了算法的时间复杂度。然后,基于模拟退火选择出的初始点,算法使用一种贪心的策略形成K个簇,具有较低的时间复杂度。然而,该算法只能够产生几乎绝对平衡的聚类结果,很难生成相对平衡尤其是满足用户自定义平衡度的聚类结果,不能够精确约束聚类结果中任意两个簇数据元素数目差的最大值。(2)提出一种基于K-means算法的τ-平衡聚类算法。针对现有相关工作以及第(1)点中的提到的算法的不足,提出了一种能够精确约束聚类结果任意两个簇规模差的τ-平衡约束聚类算法。其中,τ表示聚类结果中任意两个簇规模的差的最大值,支持用户自定义。随后,算法设计了两层过滤器对数据元素分配步骤中的中间多余的距离计算进行过滤,同时优化了质心更新步骤。实验结果表明,所提出的τ-平衡聚类算法具有较好的平衡聚类性能和时间效率,相关的优化机制也进一步提升了算法效率。(3)面向CPU-GPU异构计算平台的平衡聚类算法加速。随着硬件技术的不断发展,GPU逐渐从处理专业图形计算领域开始往通用计算领域发展。由于底层工作原理的不同,GPU相比CPU更擅于处理同时具有重复、简单、大规模特性的计算任务。因此,协调CPU与GPU共同处理计算任务比单纯CPU下执行这些任务通常可以取得更高的执行效率。在现有的平衡聚类算法的工作中,也还未有针对CPU与GPU异构计算方面来进行算法优化的工作。本文对在第(2)点中提出的τ-平衡聚类算法及其相关优化版本算法在CPU-GPU异构平台上进行了性能优化,实验结果表明算法效率有了更进一步地提升。