关键词: 谱聚类, 图构建, K近邻图

Abstract: Graph construction is a fundamental step of spectral clustering. Traditional K-Nearest Neighbor Graph（KNNG） disregards if the neighborhoods are geometrically symmetric which might lead to low clustering accuracy in some cases. A new method of Graph construction using Min-Max neighboring orders（called KMMG） is proposed which takes the relative symmetry of neighborhoods into account. A notion called neighboring order is defined and an interesting insight is found that the construction of KNNG depends on the minimal neighboring orders whereas that of KMMG depends on the min-max neighboring orders. Theoretical analysis shows that the relative symmetry of KMMG is higher than KNNG, and the mutual KNNG is contained in KMMG which can ensure the connection tightness of edges. Experimental results over a set of public datasets show that the proposed method can induce higher clustering accuracy than KNNG.

Key words: spectral clustering, graph construction, K-Nearest Neighbor Graph