最小最大邻域阶构图方法  

Graph construction using min-max neighboring orders

作　　者：张钧伟[1] 齐鸣鸣[1,2] 许淑华[1] 

机构地区：[1]绍兴文理学院元培学院,浙江绍兴312000 [2]同济大学计算机科学与技术系,上海201800

出　　处：《计算机工程与应用》2012年第12期202-205,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.10871226);浙江省教育厅科研项目(No.Y201122544);浙江省新世纪教改项目(No.yb2010092)

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]