摘要
图之间的距离度量一直是研究的难点之一。文中提出了一种基于图谱归一化编辑距离的聚类方法。首先利用图的谱方法实现图中点的排序,再用串编辑距离进行两图之间的相似性度量,以此距离构成的不相似矩阵,应用基于矩阵理论的聚类算法实现序列图的聚类研究。考虑到图中点的多少差异,给出归一化串编辑距离的方法解决长短谱序列间距离差异误差问题。实验表明,基于图谱归一化编辑距离的聚类方法是有效的。
Distance metric between graphs is a difficult issue. A clustering method based on spectral normalized edit distance is proposed. Firstly vertices in graphs are sorted by graph spectra, them similarity metric between graphs is defined based on string edit distance, a dissimilarity matrix is constructed by these distances and clustering of sequence graph is realized by matrix theory. Due to the number variation of vertices between graphs, normalized string edit distance is proposed to solve the distance variation between graphs with different length of spectra. Experiments show that the clustering based on normalized edit distance of spectra is feasible.
出处
《皖西学院学报》
2007年第5期13-16,共4页
Journal of West Anhui University
基金
安徽省教育厅自然科学研究重点项目(KJ2007A072)
皖西学院校级应用项目(WXZY0608)
关键词
算法
谱聚类
图谱编辑距离
图的谱
algorithm
spectral clustering
spectral edit distance of graphs
graph spectra
