聚类分析是数据挖掘和机器学习研究领域的一个重要的分支,是人们探索事物内在规律的有效工具。谱聚类是聚类算法之一,它将数据集中的数据对象转化为图中的顶点。谱聚类算法以谱图划分理论为基础,把对数据集的聚类问题转化为对图的最优划分问题,使子图内部相似度最大,而子图之间的相似度最小。与传统聚类算法相比,谱聚类算法不仅思想简单易懂,操作简单,同时还克服了传统算法容易陷入局部最优解的缺点,可以收敛到全局的最优解。传统谱聚类算法首先定义一个相似性度量,然后基于此度量构造出相似矩阵W,将相似矩阵W转化为合适的Laplacian矩阵L,由Laplacian矩阵的特征值和相应的特征向量,选择一个或者多个特征向量进行聚类。本文的具体研究内容如下:首先,本文在经典切割准则的基础上引入了平均密度,提出了基于平均密度的最小最大切割准则(MDcut),并从理论上证明了MDcut的相关性质。由于高斯核函数不能全面的描述数据之间的相似关系,因此本文通过构造一种新的相似性度量,提出了一种基于密度的谱聚类方法(DSC)。将该方法与三种常用的聚类方法在五个UCI数据集上进行对比实验。实验结果表明,该方法不仅能有效地描述数据之间的相似性,还大大提高了聚类效果。为了处理增量数据,本文定义了基于密度的增量数据谱聚类方法。对于静态数据集,不需要考虑新增加的数据对象对已有数据对象的密度的影响,但是对于动态数据集来说,当有新的数据对象进入数据集,可能会对数据集中一些数据对象的密度产生影响。因此本文在高斯核函数的基础上,构造了基于密度变化的相似性度量。在该度量的基础上,通过考虑新增的数据对象对原数据集的特征值以及相似度的影响,提出了一种基于特征值变化的谱聚类方法。将该方法与两种谱聚类方法进行对比实验,实验结果证明该方法不仅可以应用于增量数据,还可以对增量数据进行有效的聚类。