半监督判别分析

半监督判别分析

摘要

线性判别分析（LDA）已经成为特征提取的常用方法，此方法可保存类可分性。通常投影向量通过最大化类间协方差，同时最大限度地减少类内协方差的方式获得的。在实践中，当没有足够的训练样本，每个类的协方差矩阵的估计可能不准确。在本文中，我们提出了一种新的方法，称为半监督判别分析（SDA），这种方法既使用的标记样本有使用未标记的样本。标记的数据点是用来最大化不同类别之间的可分性，而未标记的数据点用来估计数据的内在的几何结构。具体来说，我们的目标是学习的一个判别函数，使其尽可能平稳地表示数据流形。单训练图像的人脸识别和相关反馈图像检索的实验结果可以证明我们算法的有效性。 1.介绍

在许多可视化分析应用中，如图像检索、人脸识别等，它们都会遭遇高维数据的问题。然而，有理由怀疑，自然产生的高维数据可能驻留在一个低维流形。这导致我们去考虑降维方法，这种方法允许高维数据代表一个较低维空间中的数据。要达到此目的，有两个最流行的方法，分别是是主成分分析（PCA）和线性判别分析（LDA）。主成分分析法是一种无监督的方法。 该方法是通过将原来的N维数据投影到高维的线性子空间的方式来实现降维，而线性子空间通过数据的协方差矩阵的主要特征向量来跨越。它的目标是找到一组相互正交的基函数，用于捕获数据中最大方差的方向，因此，成对的欧氏距离可以最好地保存。如果数据被嵌入在一个线性子空间，主成分分析可以保证挖掘出子空间的维数，并产生一个简洁的表示。 LDA是一种有监督的方法。它搜索项目轴，在该轴上，不同类别的数据点相距很远，同时要求同一类的数据点彼此接近。当标签信息可获得时，例如，用于分类任务，LDA可以实现的 性能优于PCA。然而，当相对于维度数量没有足够的训练样本的时，每个类的协方差矩阵的估计可能不准确。在这种情况下，测试样品的泛化能力不能得到保证。一个可行的解决方案可以应对培训（标记）样本不足的情况，该方法既学习标记得数据又未标记的数据（半监督和直推式学习）。这种方法既时自然的也是合理的，因为在现实中，我们通常只有一部分的输入数据被标记，以及大量的未标记的数据。

在过去的几十年中，半监督学习（或直推式学习）吸引了越来越多的关注。两个众所周知的算法分别是直推式支持向量机（TSVM）和协同训练。最近，基于半监督学习算法的图像分析有相当大的兴趣和成功，这种方法考虑将所有的样本的图形作为前提来指导决策。所有这些算法考虑的都是分类问题，要么直推法，要么归纳法。

在本文中，我们的目标是在半监督的情况下的降维。我们提出了一种半监督降维算法，称为半监督判别分析（SDA）。SDA的目的是找到一个投影，这个投影代表从标记的数据点中推断出的判别结构，以及代表从标记和未标记的数据点中推断出的固有的几何结构。具体而言，这些结合未标记的数据点标记的数据点，被用于建立一个包含数据集邻域信息的图。该图提供了一个相对于数据流形局部几何的离散的近似值。利用拉普拉斯图的概念，图上的一个平滑可以纳入目标函数。这样，我们的SDA算法可以优化保留流形结构。

本文的其余部分组织如下。在第2节中，我们提供LDA简要回顾。在第三部分中，我们介绍我们的半监督判别分析（SDA）的降维算法。在第4节，称述实验结果。最后在第5节，我们总结本文，并为今后的工作提供建议。 2.LDA的图视角

线性判别分析（LDA）寻求某种方向，再次方向上的不同类别的数据点相距很远，同时要求同一类的数据点彼此接近。假设我们有一组L样本x1,x2,...,xl?R，属于C类。LDA的目标

n函数如下：

aoptcaTSba ?argamaxTaSWa，

（1）

Sb??lk??k?????k???k?1????T，（2）

?lk?k??k??k??k?Sw???x??x???ii?k?1?i?1c???????T?,（3）

?其中，

lk是总样本的均值向量，是k类样本数，

??k?是第k个类的平均向量，

xi?k?是

Sw在第k个类的第i个样本。我们称

lSb为类内散布矩阵，称

T为类间散布矩阵。

确定的总散射矩阵

St??i?1?xi????xi???St?Sw?Sb,我们有

，那么公式（1）中

的线性判别分析的目标函数就等于

aoptaTSba?argamaxTaSta，

（4）

最佳的a是与本征问题的非零特征值对应的特征向量：

Sba??Sta ，（5）

Sb由于

的阶是由C?1限制，所以最多的有C?1个非零特征值对应的特征向量。

??01无一般性损失，我们假设

。我们有

Sb??lk??k???k?k?1c?????k??xi???i?1?lkTT?1??lk??k?1?lkcck?1

??X?k?W?k?X?k?其中，W?k???T是一个lk?lk的矩阵，他的所有元素都等于1lk，同时X?k??k??x1,...,xl?kk?，它

??表示k类的数据矩阵。 让数据矩阵X?X,...,X??1??c??并且定义一个l?l的矩阵Wl?l为

?W?1?0...0????2?0W...0?（6） Wl?l??????????c??0...W???0?我们有

cSb??X?k?W?k?X?k?k?1??T?XWl?lXT（7）

因此，在方程式（4）中线性判别分析的目标函数可以改写为

aoptaTSbaaTXWl?lXTa（8） ?argamaxT?argamaxTTaStaaXXaLDA目标函数的公式将对发展我们的算法是非常有帮助的。他第一次被介绍在14

3.半监督判别分析

LDA考虑者正寻求完全基于训练集的最优预测。在现实中，获得一个大规模未标记的数据集是有可能的。在这部分中，我们试图扩展LDA模型去涵盖由未标记的数据表示的流形结构。 3.1.目标函数

LDA的目的是找到一个投影向量a，以至于aTSba和aTSta之间的比例最大化。当没有足够的训练样本时，过拟合将发生。一个防止过拟合的E典型方法来是加强规范化。LDA的规范化版本的优化问题可以写成如下：

aTSbamaxTaaSt??J?a?（9）

其中，J?a?控制假设群的学习复杂度，而系数α控制模型复杂度与实验误差之间的平衡。一个最流行的正则化是Tiknonov正则化[ 21 ]

J?a??a

2

带有Tikhonov 正则化的 LDA模型通常被称为正则化判别分析（RDA）[ 8 ]。

正则化项J?a?为我们提供了一定的灵活性，帮助我们吸收特定应用的先验知识。当可获得一组未标记样本时，我们的目标是建立一个结合的流形结构的J?a?。半监督学习算法的关键是一致性的先验假设。对于分类，它意味着附近的点有可能有相同的标签[ 26 ]。对于降维，它可以解释为附近的点将有类似的嵌入（低维表示）。给出一组例子?xi?i?1，我们可以

m用一个p最邻近的图G模拟附近的数据点之间的关系。具体来说，如果xi和xj是“关闭”，我们在节点i和j之间设置一个界限，换言之，xi和xj是近邻之间的相互。让相应的权重矩阵为S，定义为

?1,ifxi?Np?xj?orxj?Np?xi?（10） Sij??0,otherwise?其中，Np?xi?表示P最近邻的集合。在一般情况下，映射函数在图上应该是尽可能光滑的。具体来说，如果两个数据点是由一个边缘连接的，它们很可能是在同一个类中的。此外，那些与子图紧密联系的子图可能有相同的标签。因此，一个自然的正交化矩阵可以定义如下：

J?a???aTxi?aTxjSij（11）

ij??2

这一公式由光谱数据降维[ 2，13 ]引出，它也在谱聚类算法[ 17 ]和多种的基于半监督学习算法[ 3，6，20 ]图表中起着关键的作用。 让X??x1,x2,...,xm?，我们有

J?a???aTxi?aTxjSijij??2?2?aTxiDiixiTa?2?aTxiSijxTjaiij

?2aTX?D?S?XTa?2aTXLXTa其中，D是一个对角矩阵；其条目是S的列（或行，因为S是对称的）的总和，Dii??jSij，

L?D?S是拉普拉斯矩阵[ 7 ]

这个数据依赖于的正规化矩阵，我们得到半监督判别分析的目标函数：

aTSba（12） maxTTaaSt??XLXa??最大化目标函数的的投影向量a由解决广义特征值问题的最大特征值求得：

Sba??St??XLXTa（13）

3.2算法

给定一个属于c类的标记集xi,yi??????和一个为标记集?xi?i?l?1。第k类有lk个样品，i?1lm?ck?1kl?l。不失一般性，我们假设在?xi,...,xl?中的数据点根据自己的标签来排序。

半监督判别分析的算法程序如下：

1.构造邻接图：构建P的近邻图矩阵S，正如公式（10）所示，计算该图的拉普拉斯矩阵L = D?S. 2.构建标记图：为标记图构建权重矩阵Wl?l?Rm?m，如下：

?Wl?lW???0其中，Wl?l?Rm?m0? 0??矩阵就是在公式6中所定义的，即定义