基于超图切割的半监督学习和聚类算法

Semi-supervised Learning and Clustering Algorithms Based onHypergraph Cutting

对超图切割上的半监督学习和聚类算法进行了研究;通过对超图切割和超边展开法及其切割函数的讨论,引入了超图上的总变异作为超图切割的洛瓦兹扩展,并在此基础上提出了一组正则化函数,它对应于图上的拉普拉斯型正则化;基于正则化函数族提出了半监督学习方法,并基于平衡超图切割提出了谱聚类方法;为了求解这两个学习问题,将它们转化为求解凸优化问题,并为此提出了一种主要组成部分为近端映射的可扩展算法,从而实现半监督学习和聚类;仿真实验结果表明,提出的基于超图切割实现的半监督学习和聚类方法相比于经典的超边展开法和其他图切割方法有更好的标准偏差和聚类误差性能。

Semi-supervised learning and clustering algorithms on hypergraph cutting are conducted a research;By discussing hypergraph cutting and hyperedge expansion methods as well as its cutting function,the total variation on hypergraph is introduced as a Lovasz extension of hypergraph cutting.Based on this,this paper puts forward a set of regularization functions related to the Laplacian regularization on the graph,presents a semi-supervised learning method based on regularization function family,and proposes a spectral clustering method based on balanced hypergraph cutting;In order to solve these two learning problems,they are transformed into solving the convex optimization problem,and a scalable algorithm whose main component is proximal mapping is proposed to realize the semi-supervised learning and clustering;Simulation results show that the proposed semi-supervised learning and clustering method based on hypergraph cutting has a better standard deviation and clustering error performance than the classical hyperedge expansion and other graph cutting methods.