谱聚类算法是近年来机器学习和模式识别领域最重要也是最热门的基础算法之一。谱聚类算法将聚类问题转换为图的分割问题,通过对相应的拉普拉斯矩阵的特征向量进行聚类,找到对图的最优划分。凭借其良好的聚类结果和简单的实现细节,谱聚类算法越来越广泛地被研究人员运用在图像分割、人脸识别、语音分析等领域。然而由于在计算过程中需要维护一个大小与样本数量二次相关的拉普拉斯矩阵并对其进行特征值分解,谱聚类在处理大量样本时需要耗费过多的时间和内存空间。谱聚类性能上的缺陷限制了其从实验室走向工业化应用的步伐。本文分析了当前主流的谱聚类加速算法的优缺点,从改进谱聚类在大数据集下的运行性能的角度出发,根据稀疏编码理论,提出了一种基于标记点和子空间迭代的快速谱聚类算法。本文提出的算法在普通样本与随机抽取的标记样本之间建立相似度关系,利用稀疏编码的方式将这种关系重新定义为样本的特征,并将该特征存储在稀疏的扁平矩阵内。该方法继而结合子空间迭代算法,能够在不生成拉普拉斯矩阵的前提下计算出拉普拉斯矩阵的主要特征向量。理论分析和实验显示,本文提出的算法能够在保证甚至改进聚类准确率的前提下达到与样本数量线性相关的时间复杂度和空间复杂度,在多个数据集上能够比目前主流的谱聚类加速算法更快地得到更高准确率的结果。本文还对该算法在图像分割领域进行了实验,并对算法未来进一步的发展进行了讨论。