0 引言

目前，监督学习、无监督学习以及半监督学习算法为三大热门学习算法。基于现实中图像、模型等领域具有的海量数据中只有小部分标记样本的现状，充分利用标记数据以及无标记数据进行分类学习，成为更主流的研究方式，这也造就了半监督学习算法在分类算法中炙手可热的地位。半监督学习算法拥有两个分支，即归纳学习算法和转导学习算法，其中，是否生成分类器是两种算法最大的区别。具体而言，归纳学习是利用标记数据和未标记数据学习得到分类器，进而通过分类器进行数据分类的方法，而图转导(Graph Transduction, GT)学习并不需要形成分类器，直接利用整个数据集便可以进行分类。相比而言，图转导算法更为经济。在图转导算法中，聚类假设、流形假设以及局部和全局一致性假设是比较常用的假设方法，其中，聚类假设保障了图转导算法中，数据在相邻位置上相似度较高时，对应节点趋于相似的标记。因此，本文重点研究基于聚类假设的图转导学习方法，使用图结构来表示输入的数据集，图的每个顶点分别对应数据集中的一个样本数据信息，每条边的权重代表样本数据之间的相似程度，并且在进行构图前，提前进行无标记样本的预选取，结合半监督算法实现大量未标记样本的分类。

1 相关工作

目前，国内外已有很多学者对图转导算法进行研究，并提出诸多算法。标签传播(Label Propagation, LP)算法^[1]是图转导算法的基础，通过图的边将标记信息传播到未标记节点，由于图转导算法是基于聚类假设，所以权重大的边比权重小的边标记传播更容易一些，在权重为0的边终止标记传播。在此基础上衍生出调和高斯场(Harmonic Gaussian Field, HGF)^[2]、局部与全局一致性(Learning with Local and Global Consistency, LLGC)^[3]、极大极小标签传播(MiniMax Label Propagation, MMLP)算法^[4]、最小代价路径标签传播(Label Propagation through Minimum Cost Path, LPMCP)算法^[5]等方法。不论是HGF还是LLGC算法都过于依赖初始标记集，若图中含有噪声，或者因为其他因素使得输入数据集不可划分类别时，通过图转导方法得到的分类结果缺乏准确性。

实际中并不是所有的无标记样本都能对分类提供帮助，因此挑选出对分类有用的无标记样本会提高分类准确性，也会提高构图的效率。文献[6]中采用主动学习人工标注的方式初选未标记样本，但是人工标注样本会增加时间开销。为了解决该问题本文利用模糊C均值(Fuzzy C-means, FCM)聚类算法对无标记样本进行聚类，然后在聚类结果基础上进行无标记样本的选取，得出最好的选取方式；将无标记样本中部分含有对分类有用信息的样本加入到训练样本集^[7]，避免了人工参与标注。

传统图转导(GT)算法构建全相连图，需要将所有的边都存储计算，而本文构建k近邻稀疏图，可以自适应样本特征空间中的密度，得到真实的权重，不仅阻止了相似度低节点信息的传递，也提高了算法运算速度。为了能更进一步提高分类的精度，本文进一步利用半监督学习(Semi-Supervised Learning, SSL)算法^[8-9]得出最后的分类结果。具体的思路如图 1所示。

2 算法描述

假设有n个样本点的数据集参与分类，即X={x₁, x₂, …, x_n}，已标记数据集X_l={x₁, x₂, …, x_l}，未标记数据集为X_u={x_l+1, x_l+2, …, x_n}，其中n=l+u，且l≪u，类别数量已知为c。Y_l={y₁, y₂, …, y_l}, y_i∈{1, 2, …, c}为已标记数据集X_l所对应的标记集，并且假设Y_l中包含所有的类别标记。

在此定义的基础之上，本文算法主要分为3步：

步骤1  使用FCM聚类算法对未标记样本进行聚类，根据聚类结果选取聚类的边界点作为训练集的未标记样本集；

步骤2  对训练集样本使用GT算法进行构图，得出训练集中未标记样本类别信息；

步骤3  采用半监督流形学习框架^[10]对步骤1中没有选入训练集的未标记样本进行分类。

2.1 FCM聚类算法

参与FCM聚类的数据为X_u中的所有样本数据，c为预定类别数，u_i(i=1, 2, …, c)为每一个聚类的中心，准则函数定义为：

$ {\rm{min}}\;J(\mathit{\boldsymbol{U}}, V) = \sum\limits_{i = 1}^c {\sum\limits_{j = l + 1}^n {u_{ij}^m} } {\left\| {{\mathit{\boldsymbol{x}}_j} - \left. {{\mathit{\boldsymbol{u}}_i}} \right\|} \right.^2} $

(1)

其中：‖x_j-u_i‖表示样本点x_j与u_i之间的欧氏距离，模糊加权幂指数m，依据经验取m=2，U是样本集X_u的隶属度矩阵；u_ij代表样本x_j对于u_i的隶属度；V是样本集X_u的u_i组成的聚类中心集合；通过使J(U, V)达到最小来获得U和V。

式(1) 必须满足$\sum\limits_{i = 1}^c {{u_{ij}}} = 1, \;\forall j = l + 1, \;l + 2, \cdots, n$的限制，即样本对各个聚类的隶属度之和等于1，令J(U, V)对u_i和u_ij偏导数等于0，可得：

$ {{\mathit{\boldsymbol{u}}}_{i}}=({\sum\limits_{j=1}^{n}{u_{ij}^{m}{{\mathit{\boldsymbol{x}}}_{j}}}})/({\sum\limits_{j=1}^{n}{u_{ij}^{m}}});\;i=1, 2, \cdots, c $

(2)

$ \begin{align} & {{u}_{ij}}=\frac{1}{\sum\limits_{k=1}^{c}{{{(\frac{\left\| {{\mathit{\boldsymbol{x}}}_{j}}-\left. {{\mathit{\boldsymbol{u}}}_{i}} \right\| \right.}{\left\| {{\mathit{\boldsymbol{x}}}_{j}}-\left. {{\mathit{\boldsymbol{u}}}_{k}} \right\| \right.})}^{\frac{2}{m-1}}}}}; \\ & \ \ \ \ \ \ \ i=1, 2, \cdots , c,j=l+1, l+2, \cdots, n \\ \end{align} $

(3)

依据迭代的方法得到最终的聚类结果。由于不能保证FCM聚类得到的解是全局最优解，需要运行多次，来选择最优解^[11]。

这里y_i∈{+1, -1}，选取聚类边界的未标记样本，具体选取步骤如下：

第1步  所有未标记样本进行FCM聚类；

第2步  根据第1步得到的聚类结果，计算每一个样本到聚类中心的距离，存储于数组A中，并将数组A进行排序，由大到小存储；另外计算这些样本到另一聚类中心的距离，并存储于数组B，并将数组B按从小到大的顺序存储。

第3步  选择数组A和数组B中前m个共同的样本作为预选样本集合X_u′中的元素。

如图 2以正标记样本聚类中心附近的无标记样本为例，其一无标记样本a，距离正标记样本聚类中心的距离为a2，距离负聚类中心的距离为a1，将a2存储于数组A，a1存储于数组B；无标记样本b，距离正标记样本聚类中心的距离为b2，距离负标记样本聚类中心的距离为b1，将b2存储于数组A，b1存储于数组B。依次计算出所有未标记样本到达正、负聚类中心的距离，依据第2步、第3步的步骤选择聚类边界的无标记样本，作为初选未标记样本集中的元素。

2.2 图转导算法

图转导算法定义了一个无向图G={X′, E}，图中的节点为数据集X′={X_l, X_u′}，节点间通过E={(x_i, x_j)}连接。X′代表一个新组合的集合，其中包含原已标记集合X_l和预选出的未标记集合X_u′，则剩余的未标记样本集为{ X_u -X_u′}。由于稀疏图得到的稀疏相似度矩阵中节点间的虚假连接较少，更利于真实权重的获得，所以文中采用稀疏的k近邻图来构建图^[12]，生成的相似度矩阵为W={w_ij}。使用高斯核函数来计算得到W，即：

$ {{w}_{ij}}=\rm{exp}(-{{\left\| {{\mathit{\boldsymbol{x}}}_{\mathit{i}}}-{{\mathit{\boldsymbol{x}}}_{\mathit{j}}} \right\|}^{2}}/{{\sigma }^{2}}) $

(4)

其中，σ为带宽参数，且满足σ > 0。

建立图结构后，利用已有样本标记信息预测出未标记样本隐含的标记信息，期间通过将标记信息按照样本之间的相似度进行传递^[13]。样本之间的相似度越大，即边上的w_ij值越大，越容易传递。

同时，转移概率矩阵为P_n×n，具体i行j列的元素为：

$ {{P}_{ij}}=P(i\to j)={{{w}_{ij}}}/{\sum\limits_{k=1}^{n}{{{w}_{ik}}}}\; $

(5)

表示样本x_i将标记信息传递到样本x_j的概率。定义矩阵f_L，大小为l×c，f_U大小为u×c，其中l表示标记样本的数目，u表示未标记样本的数目，c表示类别数目。f_L，f_U的第j个元素定义为：

$ {{f}_{ij}}=\left\{ \begin{matrix} =1, \ \ \ \ \ j=c, {{\mathit{\boldsymbol{x}}}_{i}}\in L \\ =0, \ \ \ \ \ j\ne c, \ {{\mathit{\boldsymbol{x}}}_{i}}\in L \\ \in (0,1), \ \ \ \ \ \ {{\mathit{\boldsymbol{x}}}_{i}}\in U \\ \end{matrix} \right. $

(6)

表示只有当与样本x_i类别相同的序列号对应元素为1，其余均为0。L、U分别表示标记数据集和未标记数据集。用n×c的矩阵f_X表示所有数据的类别：

$ {{\mathit{\boldsymbol{f}}}_{X}}=\left[\begin{matrix} {{\mathit{\boldsymbol{f}}}_{L}} \\ {{\mathit{\boldsymbol{f}}}_{U}} \\ \end{matrix} \right] $

(7)

由于未标记样本的标记信息来源于近邻样本的传递，则可表示为：

$ \mathit{\boldsymbol{f}}_{X}^{(i)}=\mathit{\boldsymbol{P}}\times \mathit{\boldsymbol{f}}_{X}^{(i-1)} $

(8)

具体步骤描述如下：

第1步  初始化i=1，f_U⁽ⁱ⁾=0；

第2步  根据式(5) 计算出概率转移矩阵P；

第3步  i=i+1，然后根据式(8) 计算f_U⁽ⁱ⁾；

第4步  重复步骤第2步，第3步, 直到f_U⁽ⁱ⁾=f_U^(i-1)；

第5步  标记出未标记样本的类别，其值为$\begin{eqnarray*}{{y}_{i}}=\arg \underset{k}{\mathop{\max }}\, {{f}_{ik}}\end{eqnarray*}$。

2.3 半监督流形学习框架

假设决策函数为f，半监督流形学习框架定义如下：

$ \mathit{\boldsymbol{f}}^*=\underset{f\in H}{\mathop{\arg \min }}\, \frac{1}{l}\sum\limits_{i=1}^{l}{V({{\mathit{\boldsymbol{x}}}_{i}}, {{y}_{i}}, \mathit{\boldsymbol{f}})}+{{\gamma }_{1}}\left\| \mathit{\boldsymbol{f}} \right\|_{H}^{2}+{{\gamma }_{2}}\left\| \mathit{\boldsymbol{f}} \right\|_{M}^{2} $

(9)

其中:V表示损失函数，用于计算在x_i点预测函数值与实际值之间的损失值；有两个正则化项，‖f‖_H²是在再生核希尔伯特空间(Reproducing Kernel Hilbert Space, RKHS)的范数，建立于聚类假设的基础之上，‖f‖_M²建立于流形假设的基础之上，由标记样本和未标记样本共同决定；γ₁控制‖f‖_H²在RKHS函数的复杂性，γ₂控制‖f‖_M²内在几何结构的函数复杂性，γ₁、γ₂二者均是常数。

Belki等^[14]证明γ₂‖f‖_M²近似为：

$ \frac{{{\gamma }_{2}}}{(u+l)}\sum\limits_{i, j=1}^{l+u}{{{(f({{\mathit{\boldsymbol{x}}}_{i}})-f({{\mathit{\boldsymbol{x}}}_{j}}))}^{2}}}{{W}_{ij}}=\frac{{{\gamma }_{2}}}{(u+l)}{{\mathit{\boldsymbol{f}}}^{\rm{T}}}\mathit{\boldsymbol{Lf}} $

(10)

将式(10) 代入式(9) 中，得：

$ {{\mathit{\boldsymbol{f}}}^{*}}=\underset{f\in H}{\mathop{\arg \min }}\, \frac{1}{l}\sum\limits_{i=1}^{l}{{{({{y}_{i}}-f({{\mathit{\boldsymbol{x}}}_{i}}))}^{2}}}+{{\gamma }_{1}}\left\| \mathit{\boldsymbol{f}} \right\|_{H}^{2}+\frac{{{\gamma }_{2}}}{{{(u+l)}^{2}}}{{\mathit{\boldsymbol{f}}}^{\rm{T}}}\mathit{\boldsymbol{Lf}} $

(11)

其中，当二次损失函数(y_i-f(x_i))²的值达到最小时，保证了预测函数值与实际值之间的损失值达到最小。L是图拉普拉斯矩阵L=D-W，这里对对角阵D定义为${{D}_{ij}}=\sum\limits_{j=1}^{l+u}{{{W}_{ij}}}$。

根据定理(文献[14]中已证明)，式(11) 的解可由如下形式表示：

$ {{\mathit{\boldsymbol{f}}}^{*}}(x)=\sum\limits_{i=1}^{l+u}{a_{i}^{*}}K(\mathit{\boldsymbol{x}}, {{\mathit{\boldsymbol{x}}}_{i}}) $

(12)

将式(12) 代入式(5) 中，得到：

$ \begin{align} & {{\mathit{\boldsymbol{a}}}^{*}}=\arg \min \frac{1}{l}{{(\mathit{\boldsymbol{Y}}-\mathit{\boldsymbol{JKa}})}^{\rm{T}}}(\mathit{\boldsymbol{Y}}-\mathit{\boldsymbol{JKa}})+{{\gamma }_{1}}{{\mathit{\boldsymbol{a}}}^{\rm{T}}}\mathit{\boldsymbol{Ka}}+ \\ & \ \ \ \ \ \ \ \ \ \frac{{{\gamma }_{2}}}{{{(u+l)}^{2}}}{{\mathit{\boldsymbol{a}}}^{\rm{T}}}\mathit{\boldsymbol{KLKa}} \\ \end{align} $

(13)

对式(13) 求导并等于0，进一步得到：

$ {{\mathit{\boldsymbol{a}}}^{*}}={{(\mathit{\boldsymbol{JK}}+{{\gamma }_{1}}l\mathit{\boldsymbol{I}}+\frac{{{\gamma }_{2}}l}{{{(u+l)}^{2}}}\mathit{\boldsymbol{LK}})}^{-1}}\mathit{\boldsymbol{Y}} $

(14)

其中：a是拉格朗日乘子，且a=[a₁  a₂ … a_l+u]^T；K是大小为(l+u)×(l+u)的核矩阵；Y是(l+u)维的向量，且Y=[y₁, y₂, …, y_l, 0, …, 0]；J是(l+u)×(l+u)维的对角矩阵，J=diag(1, …, 1, 0, …, 0)，其中有l个1；I是大小为(l+u)×(l+u)的单位矩阵；γ₁、γ₂二者均是实数。因此可得分类器$\mathit{\boldsymbol{f}}=\sum\limits_{i=1}^{l+u}{{{\mathit{\boldsymbol{a}}}^{*}}}K(\mathit{\boldsymbol{x}}, {{\mathit{\boldsymbol{x}}}_{i}})$。

3 实验及结果 3.1 数据及参数选择

首先使用Weizmann Horse数据集对算法进行验证，选取horse322(250×205)、horse288(350×276)、horse238(800×571)、horse074(627×800) 图像。因为Weizmann Horse数据集本身有理想分类，所以本文对各种分类方法的效果和理想分类效果进行比较。为了验证本算法实际应用效果，本文进一步选取西北大学可视化所兵马俑数据集中G3-I-a-16俑(322×359)、84L864唐胡人俑(545×691)、569彩色骑马俑(1 023×849)、556彩色马俑(690×517)、557彩色马俑(690×517) 进行实验验证。

本实验以这些数据的二维图像模型为对象，对本文提出的分类算法进行验证。对这些二维图像本身进行分类，分为背景和目标对象。每幅图像以画线方式选取已标记点，具体选取结果如表 1所示。

实验具体过程如下：

首先运用FCM聚类算法进行聚类，由于FCM聚类算法选取的聚类中心会对实验产生影响，所以进行10次实验，取平均结果作为最后的聚类结果。

然后在聚类结果基础上选取聚类边界(Border)的100个未标记点加入训练集，接着使用GT算法进行构建k近邻图，确定出未标记点的类别信息，加入到已标记数据集，需要确定k近邻图的近邻数N，以及参数高斯核函数的带宽σ，其中根据多次实验的经验值，将近邻数N取值为10；选取加入训练集的未标记样本的方式还可以采用随机(Random, R)、靠近聚类中心(Center, C)的方式，本文对比了这三种效果。

最后采用半监督算法对其余未标记点进行分类，得到分类结果。需要确定控制在希尔伯特空间(RKHS)函数复杂性的参数γ₁，控制内在几何结构的函数复杂性参数γ₂。本文采用三层网格搜索^[15-16]的方式，将找到的分类正确率最高的参数格点作为最优的参数对，即在lb σ={-10：1：10}、lg γ₁={-5：1：5}和lg γ₂={-5：1：5}参数范围内的三层网格中搜索得到。参数值的设定如表 2所示。

3.2 结果及对比分析

本文采用三种评价方式对文中方法的分类效果进行评价：

1) PCR评价方式。

本文所述算法的分类效果使用图像中被正确分类的像素数与总像素数的比值进行评价，如以下公式：

$ \rm{PCR}=正确分类像素数/图像总像素数 $

其中，PCR(Pixel Classification Rate)即像素分类正确率。

2) APCR评价方式。

使用每个类的像素分类正确率的均值，作为第二个衡量算法分类效果的指标^[17]，公式如下：

$ \rm{APCR}=(背景分类正确率+目标对象分类正确率)/2 $

其中，APCR(Average Pixel Classification Rate)表示两类分类正确率的平均正确率。

3) Time评价方式。

进一步依据算法的执行时间，对算法效率进行评估。

几种分类方法的分类效果如图 3、图 4所示。

利用Weizmann Horse数据集验证的分类效果如图 3所示，通过各分类算法的分类结果与理想分类结果进行直观比较，可以看出GT(B)+SSL算法的分类效果更接近于理想分类效果。如图 4所示，本文算法实际运用于兵马俑数据时，仍保持了很好的分类效果。

表 3具体从PCR、APCR、Time三种评价角度对几种分类方法进行对比。由表 3可知：1) 传统的图转导方法没有对未标记样本进行初选操作，直接对所有的样本进行构图分类得到最终分类结果，运行时间低，但是分类效果不佳。2) GT(B)+SSL算法运行时间较GT算法而言明显加长，是因为本文算法对标记样本进行了预选取，增加了运行时间，虽然选取结束后还需要构建k近邻图以及半监督分类两个阶段，但是由于构建的是稀疏图，训练样本数大大减少，所以后两个阶段并不会对运行时间产生多大影响，但是极大地提高了分类的准确率。3) GT(B)+SSL与GT(C)+SSL、GT(R)+SSL相比，由于执行的阶段相同，所以运行时间相近，但是选取聚类边界的数据作为构图前的未标记样本集，比随机选取数据或靠近聚类中心选取数据的方式，更能找到含有隐含信息的数据，所以GT(B)+SSL分类准确率明显高于其他两种方法。4) 不论从PCR指标，还是APCR指标对几种算法评估，GT(B)+SSL算法分类准确率都优于其他几种分类算法。

此外标记样本数量的多少也会对分类的准确度产生影响，分别选取horse238、horse074、556俑图像进行以下分类实验。表 4分别给出不同标记样本数的实验结果对比。

分类结果较优的数据已在表格中加粗显示，从表 4知：随着标记像素数的增多，分类准确度也会随着提高。GT(B)+SSL算法与其他几种分类算法相比，即使在标记像素数稀少的情况下，也具有较好的分类准确度。

4 结语

通过对未标记样本进行预选，挑出携带对分类有帮助的未标记样本加入训练集，然后构建k近邻稀疏图，使得构图的数据节点大大减少，提高构图的效率。利用图转导的方式将未标记样本进行分类，得到更多可靠的标记样本数据，再使用半监督方式利用增多的标记样本和剩余未标记样本进行分类器的训练，这样得到的训练分类器分类精度更好。此外，本文算法不论对于背景单一的图像，还是背景复杂的图像，分类准确率都明显高于其他三种分类算法。目前本文算法只针对二分类问题，未来研究将二分类问题延伸到多分类问题。