CN108805155A - 同时学习关联矩阵和拉普拉斯正则化最小二乘的半监督分类方法 - Google Patents

Abstract

本发明公开了一种同时学习关联矩阵和拉普拉斯正则化最小二乘的半监督分类方法，主要包括以下步骤：首先根据训练样本建立一种同时学习关联矩阵和拉普拉斯正则化最小二乘的联合模型；其次采用块坐标下降法对模型中的各类变量进行迭代优化；最后用拉普拉斯正则化最小二乘分类器获取样本的软标签，并选取标签向量中元素最大的那个维度作为样本的类别。该发明将样本的稀疏自表示问题和拉普拉斯正则化最小二乘分类器有效地融合在一起，并在学习过程中实现样本关联矩阵和拉普拉斯正则化最小二乘分类器的同时优化及相互改善。本发明具有显式的分类器函数，从而能够有效地处理外来样本的问题。相对于其它的半监督分类方法，该方法具有更准确的分类正确率，有很好的应用前景。

Description

同时学习关联矩阵和拉普拉斯正则化最小二乘的半监督分类 方法

技术领域

本发明涉及计算机模式识别领域，具体是涉及一种同时学习关联矩阵(AffinityMatrix)和拉普拉斯正则化最小二乘(Laplacian Regularized Least Square，Lap-RLS)的半监督分类方法。

背景技术

在现实应用中，分类方法的性能主要依赖于训练样本中有标签样本的个数，然而在现实生活中获取有标签样本是非常困难、昂贵和耗时的，且需要领域内专家的大量努力。另一方面，得益于数据采样技术和计算机硬件技术的快速发展，获取大量的无标签样本已非常容易，这样使得利用少量的有标签样本和大量的无标签样本进行训练的半监督学习(Semi-Supervised Learning，SSL)成为计算机模式识别和机器学习领域中的研究热点，现已被广泛应用于图像分类、人脸识别等领域。

在处于相同类簇或数据流形中的邻近样本有较大的可能性拥有相同的标签这一假设下，基于图的半监督学习(Graph based Semi-Supervised Learning,G-SSL)引起了广大研究者的密切关注。它的核心思想是利用给定的部分标签和成对关联样本之间的一致性来预测无标签样本的标签，即通过成对关联数据传播标签的过程。总的来说，基于图的半监督学习算法主要解决两个关键性问题：(1)构造样本间的关联矩阵；(2)预测无标签样本的标签。

关联这个概念是在定义数据图中的权重矩阵时被提出的。权重矩阵，即用来表示样本之间相似度的矩阵。Zhou等人基于欧式距离来选取k个近邻点来构造邻接图，然后通过热核(heat kernel)来计算边缘权重矩阵。Wang等人用一系列重叠的线性邻域补丁来逼近整个图，使用邻域线性投影计算每个补丁的边缘权重。Liu等人提出了有效的锚图，通过将每个样本表示为其邻近锚点的线性组合来构造关联。为了避免邻域图参数的选择问题及获得自适应图，学者们提出了稀疏表示(Sparse Represention，SR)和低秩表示(Low-RankRepresentation，LRR)等全局自表示方法，其主要思想是计算每一个样本在其它样本下的稀疏或低秩表示系数，然后用表示系数来构造关联矩阵。全局自表示方法能够更好地获取数据的全局结构，是半监督学习的一个有效工具。

当获得关联矩阵后，则可以基于关联矩阵通过不同的预测机制来估计无标签样本的标签，例如高斯场与调和函数(Gaussian Fields and Harmonic Functions，GFHF)，局部和全局一致性学习(Learning with Local and Global Consistency，LLGC)，流形正则化(Manifold Regularization，MR)，马尔科夫随机游走(Markov Random Walks，MRW)，特殊标签传播(Special Label Propagation，SLP)，谱图直推器(Spectral Graph Transducer，SGT)等。

以上基于图的半监督学习方法尽管在分类任务中表现出优良的性能，但是它们在训练过程中一般是先构造关联矩阵，然后基于关联矩阵通过某种预测机制来估计样本标签，即关联矩阵的构造和标签预测机制是分两步单独进行的，这样不能充分利用关联矩阵和样本标签之间潜在的联系。

为了克服这一缺点，Li等人将这两个独立的过程合并为一个联合优化模型进行求解，称为自学半监督学习(Self-Taught Semi-Supervised Learning，STSSL)。它可以同时学习关联矩阵和未知样本的标签，其优点在于能够充分利用给定的标签以及预测的标签来不断改善关联矩阵，从而进一步提高标签传播(Label Propagation，LP)的精度。然而这个方法属于直推式学习方法，即没有显式的决策函数来预测无标签样本的标签，故不能有效地处理外来样本的问题。除此之外，其优化过程中所用的标签传播方法也不适应于具有复杂结构的数据集。

发明内容

本发明的目的是为了克服现有技术存在的缺点和不足，而提供一种同时学习关联矩阵和拉普拉斯正则化最小二乘的半监督分类方法。该方法将样本的稀疏自表示问题和拉普拉斯正则化最小二乘分类器有效地融合在一起，建立了自学的拉普拉斯正则化最小二乘(Self-taught Laplacian Regularized Least Square,ST-LapRLS)模型，并在学习过程中实现样本关联矩阵和拉普拉斯正则化最小二乘分类器的同时优化及相互改善。更重要的是，该发明具有显式的分类器函数，从而能够有效地处理外来样本问题。

5.为实现上述目的，本发明的技术方案是该方法包括：

S1:根据训练样本构建同时学习关联矩阵和拉普拉斯正则化最小二乘的联合模型；

S2:采用块梯度下降算法对所述的联合模型中的各类变量进行迭代优化，直到收敛；

S3:用拉普拉斯正则化最小二乘分类器计算待分类样本的软标签，并选取软标签向量中元素最大的那个维度作为待分类样本所属的类别。

进一步设置是所述的步骤S1包括以下步骤：

S11：通过稀疏自表示来构建训练样本之间的关联矩阵，即若某个样本能用其它几个样本稀疏表示的话，则表示此样本与这几个样本之间存在着较大的关联性；

S12:构建样本标签之间的拉普拉斯图关系，即关联性很大的样本应该具有相似的标签；

S13：将样本的稀疏自表示问题有效嵌入到拉普拉斯正则化最小二乘分类器中，建立同时学习关联矩阵和拉普拉斯正则化最小二乘的联合模型。

进一步设置是所述的步骤S2包括以下子步骤：

S21:将建立的所述联合模型分解为拉普拉斯正则化最小二乘分类器子问题以及稀疏自表示子问题，并运用迭代的方式对两个子问题进行轮流优化求解；

S22:对于拉普拉斯正则化最小二乘分类器子问题，运用梯度为零的方法对分类器的系数矩阵变量进行解析求解；

S23:对于稀疏自表示相关的子问题，为了消除稀疏自表示系数变量在优化过程中的相关性，引入辅助变量，并运用交替方向乘子算法求解。

进一步设置是所述的步骤S3包括以下子步骤：

S31：用拉普拉斯正则化最小二乘分类器计算待分类样本的软标签；

S32：找出软标签向量中元素最大的那个维度，并以该维度作为待分类样本所属的类别。

本发明的有益效果是：

1、本发明提出了一种全新的并且通用的半监督分类方法，对任意分类数据类型(如人脸识别、物体分类等)都适用。具体地说，充分利用所估计的标签去生成良好的数据关联矩阵，良好的关联矩阵又可进一步提高分类器的性能，即分类器和关联矩阵在学习过程中能够达到相互促进的效果。

2、本发明提出的分类器是显式的，它可以方便地处理外来样本问题。

3、本发明通过拉普拉斯正则化最小二乘分类器获得的软标签相比于标签传播方法获得的硬标签更适应于半监督学习中的流形假设，故本发明可以处理复杂数据的分类任务。

4、本发明通过块梯度下降算法对所建半监督分类模型进行快速有效求解。特别地，对于拉普拉斯正则化最小二乘分类器中的系数矩阵变量，采用梯度为零的方法获得解析解；对于稀疏自表示问题中的相关变量，本发明提出用交替方向乘子算法进行迭代求解。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，根据这些附图获得其他的附图仍属于本发明的范畴。

图1本发明的方法流程图；

图2为本发明的整体流程运行图

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步地详细描述。

如图1至图2所示，为本发明实施例中，本发明为一种同时学习关联矩阵和拉普拉斯正则化最小二乘的半监督分类方法，本发明的方法具体运行的硬件和编程语言并不限制，用任何语言编写都可以完成，为此其它工作模式不再赘述。

本发明的实施例采用一台具有Intel Xeon-E5中央处理器和16G字节内存的计算机，并用Matlab语言编制了同时学习关联矩阵和拉普拉斯正则化最小二乘的半监督分类的工作程序，实现了本发明的方法。

本发明的同时学习关联矩阵和拉普拉斯正则化最小二乘的半监督分类方法主要包括联合模型的建立、块坐标下降优化算法以及样本的分类策略三个步骤。

在介绍具体步骤之前，本发明介绍下面所要用到的符号的意义。

给定一个包含C类样本的数据集不失一般性，假设数据集S中前l个元素为有标签样本，剩余的u个元素为无标签样本。有标签样本与无标签样本所形成的矩阵分别记为X_l和X_u，即X_l＝[x₁,…,x_l]，X_u＝[x_l+1,…,x_l+u]。相应地，Y_l＝[y₁,…,y_l]和Y_u＝[y_l+1,…,y_l+u]分别是已知标签矩阵和未知标签矩阵，其中标签y_i是一个C维0-1向量，即如果x_i属于第j类样本，则y_i的第j个位置上的元素值为1，其他位置上的元素值为0。全部样本所形成的矩阵记为X，即X＝[X_l,X_u]，其标签矩阵为Y，即Y＝[Y_l,Y_u]。||A||₁表示矩阵A的范数，即||A||₁＝∑∑|α_ij|。

针对包含C类样本的分类问题，具体步骤如下：

S1构建同时学习关联矩阵和拉普拉斯正则化最小二乘的联合模型。其主要包含：

a)构建训练样本之间的关联矩阵。经典的稀疏自表示问题如下所示：

其中E是误差矩阵，A是稀疏自表示矩阵，diag(A)＝0表示矩阵A的对角线元素都为零，这是为了避免出现平凡解，即样本用其自身来线性表示。

记问题①的最优解为其中是样本x_i在其他样本下的稀疏

表示系数。如果x_i能用其它样本稀疏表示，即则说明样本x_i和样本之间存在着较大的关联性，因此样本之间的关联矩阵可以由稀疏表示系数来构造，即

W＝(|A|+|A^T|)/2 ②

b)构建样本标签之间的拉普拉斯图关系。关联性大的样本应该具有相似的标签，因此构造样本标签的拉普拉斯图关系为

其中L是拉普拉斯矩阵，L＝D-W，D为对角矩阵，其对角线元素为

c)将样本的稀疏自表示问题与拉普拉斯正则化最小二乘分类器相结合，建立自学的拉普拉斯正则化最小二乘模型

s.t.X＝XA+E，diag(A)＝0

在这里，β为一个正的参数，是核矩阵，B是拉普拉斯正则化最小二乘分类器系数矩阵，是一个前l个元素为1其余元素为0的对角矩阵，其中是一个零向量。

S2采用块梯度下降算法对所提出的联合模型中的各个变量进行迭代优化，直到收敛。其主要包含：

a)将优化问题分解为拉普拉斯正则化最小二乘分类器子问题以及稀疏自表示子问题，并运用迭代的方式对以下两个子问题进行轮流优化求解

在⑤中，L^(t)是由A^(t)诱导出的拉普拉斯矩阵；在⑥中，Y^(t+1)＝B^(t+1)K，即分类器所预测的样本的软标签矩阵。

b)固定稀疏自表示矩阵A^(t)和误差矩阵E^(t)，求解拉普拉斯正则化最小二乘分类器系数矩阵B^(t+1)。由于子优化问题⑤关于变量B是凸函数且连续可导，故对变量B求梯度并令其为零，可获得解析解为：

其中I是单位矩阵。

c)给定拉普拉斯正则化最小二乘分类器系数矩阵B^(t+1)，求解稀疏自表示矩阵A^{(t +1)}和误差矩阵E^(t+1)。由于

定义矩阵则子优化问题⑥可重新写为

其中⊙为矩阵的Hadmard积。为了消除稀疏自表示系数变量在优化过程中的相关性，引入辅助变量Z，同时为了符号简便起见，将变量中的上标去掉，则优化问题⑧等价为：

其增广拉格朗日函数为

其中Λ⁽¹⁾，Λ⁽²⁾表示拉格朗日矩阵乘子，<·，·>表示矩阵的内积。运用交替方向乘子算法对优化问题⑨中的各个变量进行迭代求解，具体步骤如下：

关于A的子优化问题的求解为

其中S_η(·)为阈值算子满足S_η(x)＝sgn(x)max(|x|-η,0)。

关于Z的子优化问题的求解为

对上式关于Z求梯度并令其为零，可得到变量Z的解析解为

关于E的子优化问题的求解为

更新拉格朗日乘子矩阵

Λ_κ+1 ⁽¹⁾＝Λ_κ ⁽¹⁾+μ(X-XZ_κ+1-E_κ+1)，

Λ_κ+1 ⁽²⁾＝Λ_κ ⁽²⁾+μ(Z_κ+1-A_κ+1+diag(A_κ+1))。

S3提出一种判别样本类别标签的方法，具体主要包含：

a)对于需要判别类别的样本z，通过拉普拉斯正则化最小二乘分类器计算出样本z的软标签，即

y_z＝F(z)＝Bk_z,

其中k_z＝[k(x₁,z),k(x₂,z),…,k(x_l+u,z)]^T。

b)找出软标签向量中元素最大的那个维度，并以该维度作为样本所属的类别，即

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，所述的程序可以存储于一计算机可读取存储介质中，所述的存储介质，如ROM/RAM、磁盘、光盘等。

以上所揭露的仅为本发明较佳实施例而已，当然不能以此来限定本发明之权利范围，因此依本发明权利要求所作的等同变化，仍属本发明所涵盖的范围。

Claims (4)

1.一种同时学习关联矩阵和拉普拉斯正则化最小二乘的半监督分类方法，其特征在于，该方法包括：

S1:根据训练样本构建同时学习关联矩阵和拉普拉斯正则化最小二乘的联合模型；

S2:采用块梯度下降算法对所述的联合模型中的各类变量进行迭代优化，直到收敛；

S3:用拉普拉斯正则化最小二乘分类器计算待分类样本的软标签，并选取软标签向量中元素最大的那个维度作为待分类样本所属的类别。

2.根据权利要求1所述的半监督分类方法，其特征在于：所述的步骤S1包括以下步骤：

S11：通过稀疏自表示来构建训练样本之间的关联矩阵，即若某个样本能用其它几个样本稀疏表示的话，则表示此样本与这几个样本之间存在着较大的关联性；

S12:构建样本标签之间的拉普拉斯图关系，即关联性很大的样本应该具有相似的标签；

S13：将样本的稀疏自表示问题有效嵌入到拉普拉斯正则化最小二乘分类器中，建立同时学习关联矩阵和拉普拉斯正则化最小二乘的联合模型。

3.根据权利要求1所述的半监督分类方法，其特征在于：所述的步骤S2包括以下子步骤：

S21:将建立的所述联合模型分解为拉普拉斯正则化最小二乘分类器子问题以及稀疏自表示子问题，并运用迭代的方式对两个子问题进行轮流优化求解；

S22:对于拉普拉斯正则化最小二乘分类器子问题，运用梯度为零的方法对分类器的系数矩阵变量进行解析求解；

S23:对于稀疏自表示相关的子问题，为了消除稀疏自表示系数变量在优化过程中的相关性，引入辅助变量，并运用交替方向乘子算法求解。

4.根据权利要求1所述的半监督分类方法，其特征在于：所述的步骤S3包括以下子步骤：

S31：用拉普拉斯正则化最小二乘分类器计算待分类样本的软标签；

S32：找出软标签向量中元素最大的那个维度，并以该维度作为待分类样本所属的类别。