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

Semi-supervised Learning and Clustering Algorithms Based on Hypergraph Cutting

摘要:

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

Abstract:

In this paper, semi-supervised learning and clustering algorithms on hypergraph cutting are studied; Firstly, 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, a set of regularization functions are proposed, which correspond to Laplacian regularization on graph; Then, a semi-supervised learning method based on regularization function family is proposed, and a spectral clustering method based on balanced hypergraph cutting is proposed; In order to solve these two learning problems, they are transformed into solving convex optimization problems, and a scalable algorithm whose main component is proximal mapping is proposed to realize semi-supervised learning and clustering; Simulation results show that the proposed semi-supervised learning and clustering methods based on hypergraph cutting has better standard deviation and clustering error performance than the classical hyperedge expansion and other graph cutting methods.