模式识别是人类的一项基本技能,随着计算机的出现和人工智能的兴起,人们希望利用计算机来替代和扩展人的部分脑力技能。因此,从20世纪60年代起,模式识别迅速发展并成为一门新兴的学科。模式识别是一门多领域交叉的学科,它与数学、计算机科学、机器学习、心理学、生物学、控制论和图像处理等的研究都有关系；同时,它的应用领域广泛,包括DNA序列分析、化学气味识别、图像理解、人脸检测、表情识别、手势识别、语音识别、图像信息检索和数据挖掘等等。聚类和分类是模式识别中两个基本问题,本文研究基于图论的聚类和分类算法,以及分别在图像分割和图像识别上的应用。主要内容和创新点如下：研究基于特征向量选择的谱聚类算法,推广了积分平方误差散度,提出了基于广义积分平方误差的特征向量选择方法及相应的谱聚类算法。对于真实世界的数据,由于都含有噪声,采用谱聚类算法聚类,特征向量的选择十分必要,而特征向量的模态在一定程度上反映了其是否包含聚类信息。用高斯混合模型对特征向量建模,并用EM算法计算其中参数,进而通过测量每个特征向量的广义积分平方误差散度,可以反映其模态信息并作为选择的标准。通过图像分割的实验验证了提出算法的有效性。根据分裂一融合框架,构建了一种在区域邻接图上进行核密度估计的图像分割算法。首先采用均值漂移算法对图像进行初始分割；然后把初始分割的每个区域视作顶点,区域之间的纹理相似度作为顶点之间边的权值,构造区域邻接图；接着用核密度估计算法计算每个顶点的概率密度；最后在概率密度空间进行区域合并完成最后的分割。提出的算法对复杂图像(如受相干斑噪声污染的SAR图像)分割效果良好,而且适合进行实时处理应用。研究了图的点积表示及其在聚类中的应用,提出了图的广义点积表示模型,并构建了一种相应的图像分割方法。作为一种新的非线性降维算法,图的点积表示把数据映射为点积空间中的向量,把角度作为向量间的相似性测度。为了增大类间角度(距离),提高聚类效果,我们引入了负的相似度,提出了图的广义点积表示模型。我们在理论上证明了这种推广的合理性,在人工合成数据的实验上验证了其有效性。结合上面提出的分裂一融合框架的图像分割方法,在区域合并阶段采用图的广义点积表示,提出了一种图像分割方法,真实的SAR图像分割实验显示了方法的有效性。研究了一种线性降维算法：近邻保持嵌入(NPE),在二维图像矩阵上的扩展及其图像识别应用。同一些其他算法一样,NPE要把图像拉直成向量处理,我们提出二维近邻保持嵌入算法(2DNPE),它直接在二维图像矩阵上进行运算,克服了矩阵奇异性问题,同时加快了计算速度。2DNPE实质上只对图像矩阵的行方向进行降维,通过同步对图像矩阵的列方向也进行降维,提出双向二维近邻保持嵌入算法(B2DNPE),它用于表示和识别图像的系数个数要少很多。我们还揭示了NPE和LPP在图像矩阵上扩展算法的关系：其实也是对流形上Laplace Beltrami算子特征函数不同的线性逼近。人脸识别、字符识别的实验显示了所提算法的有效性和优势。