聚类分析是探索数据内在关系的一种最重要的技术,其应用范围包括统计学、计算机科学、生物信息学等。迄今为止,许多学者,针对不同的问题和应用环境,提出了不同的聚类算法。在这些已有的聚类算法当中,谱聚类算法,作为一种基于谱图理论的聚类算法,相比较于基于欧式空间几何分布的算法(如k-means等),往往可以取得更好的聚类效果。不仅如此,谱聚类算法还可以很好地解决数据线性不可分的问题或数据存在非凸结构的问题。虽然谱聚类拥有上述优点,但是其高昂的计算复杂度使得其在大规模数据下的应用捉襟见肘。为了在大规模数据下加速谱嵌入的速度,并且能够尽可能少地损失原始数据所包含的信息,我们试图进一步的完善现有的谱聚类的改进算法。粗略地来讲,给定一个数据集合X,一种数据间相似度的度量函数和聚类个数k,谱聚类首先使用度量函数S,计算每对数据的相似度并构造相合度矩阵A,接下来,构造该相似度矩阵A所对应的拉普拉斯矩阵L,并求解该拉普拉斯矩阵L的前k小个特征值所对应的特征向量,这一步也被称之为谱嵌入(Spectral Embedding)。最后,将所得到的k个特征向量的每一行作为一个样本,对其使用k-means算法得到最后的聚类结果。首先,本文提出了一种精度更高的锚点表示算法。现有的基于锚点表示算法使用非参数回归的方法(Nadaraya-Watson估计,N-W估计)来求解原始数据样本从标准正交基下到锚点基下的坐标转换。作为一种核估计方法,N-W估计缺乏较好的可解释性并且对参数敏感。在有些极端的情况下,N-W估计的误差较大。本文使用局部约束线性编码来求解数据在锚点基下的坐标,与现有可扩展的谱聚类算法相比,该算法具有较高的精度和更好的可解释性。考虑到局部约束线性编码并不能保证基坐标变换后的坐标是非负的,即无法保证任意一对数据坐标的内积是非负的,进而无法保证拉普拉斯矩阵的半正定性。针对上述问题,本文提出了一种改进的局部线性编码的目标优化式。该方法首先查找与数据样本最“相似”锚点,并使用改进的局部约束线性编码得到数据样本的锚点表示。然后,以内积的形式来描述数据样本间的相似度关系,最后根据奇异值分解的性质,快速地得到谱嵌入后的数据样本并对其进行k-means聚类得到最后的聚类结果。其次,本文提出了一种基于局部相似度表示的谱聚类方法。现有的基于锚点表示的谱聚类算法没有运用到嵌入在给定相似性函数中的先验知识,与现有的算法相比,该算法仅需要进行近邻搜索操作,而非对每个数据样本进行一次回归问题求解,故该方法可以有效地降低锚点表示的时间复杂度。这种方法首先随机从数据样本中选取一些数据样本作为锚点,接下来查找与数据样本最“相似”锚点,并使用相似性函数来重新描述原始数据。然后,以内积的形式来描述数据样本间的相似度关系,最后根据奇异值分解的性质,快速地得到谱嵌入后的数据样本并对其进行k-means聚类得到最后的聚类结果。最后,本文提出了一种基于最小生成树的度启发锚点选取方法。考虑到使用k-means进行锚点选取的时间复杂度是O(tpnd),其中t是k-means执行的迭代次数。在原始数据的分布可能存在非凸结构或是线性不可分时,t的增大导致使用基于k-means的锚点选取算法的时间复杂度必然会比基于随机选取的锚点选取算法的时间复杂度高,虽然这会带来更好的聚类精度。然而,基于随机选取的锚点选取算法在一定程度上会造成精度损失。该方法的提出就是为了能够平衡这种锚点选取方法所带了的精度和速度上的问题。