基于分割Bregman方法的非负稀疏图构建算法∗

摘要

In graph-based machine learning algorithms, the construction of the graph representing the data structure is the key issue. In this paper, a non-negative and sparse graph construction algorithm based on split Bregman method is presented. A weight matrix is learned by solving an equality formulation of the sparse representation through split Bregman method. In the weight matrix, each data sample can be represented by a non-negative linear combination of other samples. The constructed graph of the proposed algorithm can capture the linear relationship between data samples. Experimental results under semi-supervised learning framework demonstrate that the proposed algorithm can capture the latent structure information of data well.%在基于图的机器学习算法中，构造一个能较好反映数据内在结构信息的图尤为重要。文中提出一种基于分割Bregman方法的非负稀疏图构建算法。该算法通过使用分割Bregman方法求解稀疏表示优化问题的一个等价形式，以此得到一个能将每个数据样本表示成其他样本的非负线性组合的图的边权矩阵。算法构建的稀疏图能较好描述数据之间存在的线性关系。在半监督学习的框架下进行测试的实验表明，文中算法能较好反映数据内部潜在的结构信息。