【作者】 孔敏；

【导师】 罗斌；

【作者基本信息】 安徽大学 ， 计算机应用技术， 2006， 博士

【摘要】 随着聚类分析应用的领域扩展和深入，高维聚类问题成为当前聚类分析研究的重点。近年来，大量图的聚类问题研究相当活跃。聚类研究中如何衡量样品间的亲疏程度的数量指标通常归纳为相似系数和距离两种。图的聚类尤其是大量关联图的聚类问题的难点在于图的表达方法，图的距离函数的定义等方面。本文以图的谱理论和统计理论为基础，研究关联图的谱及谱分解特征、关联图的低维空间的表达和聚类分析。主要的内容包括四个方面：1) 图的谱分析及其图的谱分解；2) 图的谱降维及低维空间的视觉化显示；3) 图的谱聚类；4) 基于图的谱编辑距离的聚类研究。本文的研究内容和创新之处如下： 图像的关联图描述研究。图像的图的数据化表达可根据图像的几何特征来构成，图像几何特征包括角点、顶点、拐点、边缘和纹理等，通过这些特征又可以构成关联图，如区域邻接图、线段构成的图、特征点构成的图和角点构成的图等。正是由于几何特征在抗噪声方面的优势，再加上图像几何特征提取技术的日益发展，使得关联图在图像处理及模式识别方面的研究日趋活跃。文中对每幅图像提取相应的角点特征，并以此构成不同的关联图。实验中用Delaunay图构成相应的矩阵，研究的矩阵主要有二值邻接矩阵、加权邻接矩阵和拉普拉斯矩阵等。 图的谱及图的谱分解研究。一个图的邻接矩阵的特征值是该图的谱，将特征值按降序排列，以此为索引指数，由此构成模特征矩阵。文中用模特征矩阵进行图的谱分解从而得到新的谱特征，它们包括：主分量特征值、特征模体积、特征模周界、Cheeger常数、模间邻接矩阵和模间距离。同时用拉普拉斯矩阵的特征值和特征向量构成拉普拉斯特征值、谱系数夹角两个新的谱特征。它们从不同的方面描述了图中点和边等的关联关系，表达了图的结构分布情况，使得一个图的结构信息通过这些特征向量来表达，为进一步的研究奠定了很好的基础。 图的谱降维研究。图的谱及谱分解后的谱特征具有较高的维数，为提高聚类的性能和显示高维数据，便于在低维空间发现关联图的图之间的固有结构相似性。本文实现了一些谱特征降维方法，它们包括线性内嵌方法和非线性内嵌方法，分别是主成分分析(PCA)、独立成分分析(ICA)、局部保持投影(LPP)、多维尺度变换(MDS)和局部线性内嵌(LLE)诸方法。同时给出拉普拉斯矩阵的特更多还原

【Abstract】 As the application of clustering is extended and further investigated, the problems of clustering in high dimensions become the hot topic of clustering research. In the last few years, clustering of graphs in huge database is also an active research problem. In clustering, metric features which measure the friendliness relationships are often classified into similarity coefficients and distances. The difficulty of clustering of graphs, especially the clustering of large amount of relational graphs, lies on the representation of graphs and the definition of distance function. This dissertation is based on spectra theory of graphs and statistical theories. In this dissertation, we investigate graph spectra and spectral features, relational graph representation and clustering in low dimensional spaces. There are four research aspects: 1) Graph spectra and spectral decomposition; 2) Dimensionality reduction of spectra features and the visualization of graph sets in low dimensional spaces; 3) Spectral clustering of graphs; 4) Graph clustering analysis based on spectral edit distance. The contributions of this dissertation are as follows:Relational graph description of images. The relational graph representation of images can be constructed by geometrical features in images, such as corner points, vertex points, inflection points, boundaries and textures. Using these features, we can construct relational graphs, such as regional adjacent graphs, graphs built by line segments, feature points and corner points. Because of the superiority in anti-noising of geometrical features, and the great development of segmentation of geometrical features in images, the research on relational graphs becomes more and more active. We extract features of corner points in images, and construct different types of relational graphs. Delaunay graphs are used to construct the corresponding matrices in experiments, Matrices in research mainly include binary adjacent matrix, weighted adjacent matrix and Laplacian matrix.Graph spectra and spectral decomposition. The eigenvalues of the adjacency matrix of a relational graph is its spectra. Each eigenvalue has its corresponding eigenvector. These eigenvalues are arranged in descending order. Using the ordered更多还原