当前,聚类分析是国际数据挖掘和机器学习领域中的研究热点之一。作为一种较新的聚类分析方法的谱聚类方法具有传统聚类方法不具有的许多优点,如谱聚类方法简单直观、容易实现、能得到全局最优解和能对任意形状的数据空间进行聚类分析等等。传统谱聚类方法以关联矩阵为基础,构建Laplacian矩阵,从而计算出矩阵的特征值和特征向量,接下来根据某种规则选取一个或多个特征向量进行聚类分析。然而,上述过程至少存在两个亟需解决的问题,一是,如何设置构造关联矩阵所需的尺度参数;二是,直接对Laplacian矩阵进行特征值分解的计算复杂度高达O(n3)。这两个问题制约了传统谱聚类方法在实际中的应用。为了改进谱聚类算法,本文作了如下工作:(1)研究表明,低秩逼近技术和采样技术一样可以解决矩阵的特征值分解的计算复杂度高的问题,而且低秩逼近技术的逼近误差要低于采样技术。为此,本文将低秩逼近技术与传统谱聚类算法结合起来提出了一个新的谱聚类算法,命名为基于低秩逼近技术的谱聚类算法。实验结果表明,新的算法能够在降低算法的逼近误差的同时,取得较高的执行效率和较好的聚类效果。(2)虽然低秩逼近技术和采样技术可以大大的降低谱聚类算法的计算复杂度,但是二者均基于抽样技术。众所周知,在抽样技术中无论样本点是被随机抽取或是采用其它较复杂的方法抽取,这些样本点均不能够完全地代表整个数据集合且不能正确地捕获到整个数据集合的几何结构。因而,需要引入不涉及采样技术的其它手段来获得谱聚类的特征空间。为此,本文将通勤时间与传统谱聚类算法结合起来提出了一个新的谱聚类算法,命名为基于通勤时间的谱聚类算法。实验结果表明,新的算法能够在保证有较高的执行效率的同时取得更好的聚类效果。(3)本文对一个基于Nystrom逼近技术的谱聚类算法作了改进,使其理论基础更加完善,执行效率更高。