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

摘要： 图构建是谱聚类的一个基本步骤。经典的K近邻构图法不关心边的几何对称性，这一点可能给聚类带来负面影响。针对这个问题，提出了一种新型的近邻构图方法，称之为最小最大邻域阶构图法，它在邻域选择时考虑了边的相对几何对称性。更具体一点，定义了一个邻域阶的概念，发现K近邻图的构建是由最小邻域阶决定的，而提出的构图方法是基于最小最大邻域阶进行的。理论分析表明：一方面，提出的构图方法可以达到更高的相对几何对称性；另一方面，该图包含着互K近邻图，保证了边连接的紧密性。在一组公开数据上的谱聚类实验表明，提出的方法可以带来更高的聚类准确率。

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