局部鉴别投影

局部鉴别投影（精选4篇）

局部鉴别投影 篇1

1 引言

在互联网金融高速发展的形势下,要鉴别远程操作者是否是人,是哪个人? 成为了一个亟待解决的问题。 人脸,作为生物特征之一,为这一问题提供新的解决思路。人脸识别中的重点和难点是对人的面部信息进行有效的特征抽取。 人脸图像是一种高维数据,直接处理海量的高维大数据会带来复杂的计算和系统的不稳定。 在尽量保持数据信息完整的前提下,把数据投影到一个合适的子空间中,以满足数据存储与算法的需要,成为生物识别技术研究中的热点。

经典的线性子空间投影的方法主要包含主成分分析(Principle Component Analysis, PCA)以及线性鉴别分析(Linear Discriminant Analysis, LDA)。PCA是基于主分量方向上映射,根据均方误差最小原则的,生成不相关的正交向量。 PCA算法简单方便,Matthew Turk等人最先将PCA应用于人脸识别, 并提出了Eigenface概念。这种方法是一种无监督的人脸特征抽取方法,没有用到人脸图像的类别信息。 LDA算法通过引入标签信息,使投影后样本的类内离散度最小、类间离散度最大,从而生成最佳可分的子空间。 Peter等人最先采用PCA算法解决了类内离散度矩阵奇异的问题, 结合LDA提出了Fisherfaces算法应用于人脸识别,取得比PCA算法更优的分类效果。

2000 年,Seung等人在 《Science》上发表的文章把研究者的目光吸引到流形学习(Manifold Learning)领域。 人脸被认为是一种由某些内在变量控制形成的非线性流形结构,更能体现现实中数据的本质,因此在人脸识别领域效果更优。 Tenenbaum等人基于多维尺度变换(MDS), 提出了等度规映射(Isometric Mapping,ISOMAP)算法。该算法通过保持样本点的内在局部几何结构, 在降维的过程中保持样本间的测地距离不变。Sam等人提出的局部线性嵌入(Locality LinearEmbedding, LLE)算法。 在局部意义下,降维后的数据的结构是线性的,即是说局部意义下的样本点在一个超平面上。 因此任意样本点都可以通过邻域内样本点的线性加权表示得到,并在降维时保留权值不变,得到最小重构误差。 Belkin等人提出的Laplacian特征映射(Laplacian Eigenmap, LE)有着很直观的维数约简目标,即在高维空间中临近的样本点在低维度投影子空间中的样本也是邻近的。 为了提高对训练样本以外的样本求取低维的投影向量,He对LE进行线性化扩展为局部保持投影(Locality Preserving Projection, LPP)以及对LLE的线性化扩展为邻域保持嵌入(Neighborhood PreservingEmbedding, NPE), 从而解决了非线性方法难以获得新样本点低维投影的缺点。 对于上述算法,都可以在图嵌入框架下进行表示,通过图嵌入框架的应用还可以设计出新的降维算法。

LPP算法中需要把2D人脸图像1D向量, 导致转换后图像维度很高, 破坏了图像原有空间结构。 Niu等人提出的二维局部保持投影(2DLPP)算法直接对2D图像进行运算,得到了更加易于求解的特征矩阵。Cai等人提出了正交局部保持投影方法(OLPP),在求解过程中增加了正交约束条件,与LPP算法相比,具有更好的局部保持效果。

针对LPP算法没有有效地使用样本标签信息,大量的半监督以及监督算法被提出。 Zhao等人采用了局部类别信息构造权重矩阵, 提出了一种有监督的局部结构鉴别投影(LSDP)。 该算法能够保持局部结构的情况下使邻域内的同类样本靠近,异类样本远离,但未能充分利用全局类别信息,导致有利于分类信息的丢失。 本文算法通过线性判别分析的加权类间离散度矩阵, 来描述样本的全局类间信息。 通过最大程度地使得异类间中心相互远离来带动异类间样本的整体分散。 最终得到保持了内在流形信息又使样本类间的距离最大化的线性投影矩阵。

2 线性判别分析

不同于无监督的PCA算法,LDA算法通过引入标签信息, 从而达到使投影后样本的类内离散度最小、类间离散度最大。 通过最大化Fisher准则函数,生成具有最佳可分性的子空间投影。

对于训练样本N个D维样本{x1,x2,…,xN}∈RD,类Ck的个数为Nk(k = 1,2,…,c)。

则样本的总体均值向量为:

其中mk为每类样本的均值向量,表示为,

样本的类内离散度矩阵:

样本的类间离散度矩阵:

同时,待求的空间投影矩阵W∈RD×d,通过投影y =ATx,得到投影后的d维样本{y1,y2,…,yN}∈RD。

投影后总样本均值向量:

投影后类内离散度矩阵:

投影之后类间离散度矩阵:

Fisher准则函数: 能够使降维后样本具有最大的类间距离与类内距离之比:

通过对JF(A)对变量A进行求导,并使为零。

则:

令JF(W)≡λ,则

若Sw非奇异,Sw-1Sb的d个最大特征值 λ1≥λ2≥…≥λd对应的特征向量{a1, a2, … , ad} 作为最佳投影方向A。

3 局部鉴别投影

基于在高维空间中临近的样本点,在低维度投影子空间中的样本也应该相邻。 为了提高LE算法的泛化学习能力,He等人将LE方法中从原始高维空间到低维空间的映射看拓展为线性映射,即y = ATx,提出了局部保持投影算法(LPP)。 该算法的本质是拉普拉斯特征映射的线性逼近。

LPP算法首先需要建立一个图G=(V,E,W)来描述个样本点之间的近邻关系。 其中V表示图中的一个样本结点,E表示两个结点间相连接的一条边,W表示权值矩阵。 然后通过图G的权值矩阵表示流形的局部机构,数据降维的过程中引入了一个目标函数,具体步骤如下:

Step1:创建邻接图

如果样本结点xi和xj是近邻关系, 那么xi和xj之间则有一条边,判断近邻关系的两种方法如下:

a) ε- 近邻:如果结点xi和xj满足,那么xi和xj是近邻的,否则不是近邻。

b) k- 近邻: 如果结点xi是结点xj的k个最近邻的结点之一,表示为xi∈Njk;或者结点xj是结点xi的k个最近邻的结点之一, 表示为xj∈Nik。 那么xi和xj近邻,否则不是近邻。

Step2:确定权重

a)热核方法:

b) 0-1 原则

Step3:最小化如下目标函数:

将式(14)展开可得:

其中,L=D-W为Laplacian矩阵。 D为一对角矩阵,表示样本点的自然尺度,即Dii越大,表示对于的yi越重要,因此有下面约束:

最小化如下目标函数改为:

Step4:完成映射.

由拉格朗日乘子法,最小化目标函数式(17)等价于求解下式广义特征方程:

求解前d个最小非零特征值 λ1≥λ2≥…≥λd对应的特征向量为{a1, a2, …, ad}。

4 最大类间相斥的局部鉴别投影

局部保持投影未能有效的利用样本的判别信息,属于无监督的降维算法。 而判别信息对于人脸图像识别精度的提升来说至关重要。 为了在保持流形局部结构的同时引入类别信息,局部鉴别投影对权重矩阵进行了重新构造。

其中,表示两个样本点的欧式距离,β 表示控制参数。

改进的权值矩阵式(9)引入了类别信息,实现了有监督的鉴别投影。 可以看出,当样本属于同一类别时,权重值大于LPP时的权值;当样本属于不同类别时,权重值小于LPP时的权值。 通过上述权值的改变,使投影后的相同类别邻域样本点聚集, 不同类别的样本点远离。当dij相同时,同类的权值大于不同类的权值,表明同类的样本获得更大的相似性。 同时,仅对权值进行了优化,没有破坏样本的邻域选择,从而保持局部流形结构。

但局部鉴别投影仅考虑了样本k邻域内类别信息,也即是局部类别信息; 未能充分利用全局类别信息,导致有利于分类信息的丢失。 本文算法引入加权类间散度矩阵,通过最大程度地使得异类间中心相互远离来带动异类间样本的整体分散。

样本的总体加权均值向量为

每类的加权均值

其中,Dii为局部鉴别投影中所求的的对角矩阵。 此类样本均值不同于线性判别分析直接求得样本均值,本文算法考虑到了不同样本点间的权重关系,对于图中拉普拉斯对角矩阵值越大(即Dii值越大)的点赋予了一个相应较大的权重值。

投影之前类内离散度矩阵:

投影之后类内离散度矩阵:

需要满足式(24)的优化条件。

目标函数为最小化类内离散度矩阵Sw与类间离散度矩阵Sb之比。 然而比值的形式常使算法在求解中遭遇到小样本问题的困扰。 因为本文采用了与线性鉴别分析类似的加权类间离散度矩阵, 其秩小于c-1。 若采用PCA算法先对样本矩阵进行降维到c-1 维,会导致大部分有用的分类信息流失。 为克服小样本问题的困扰,我们的目标函数为最小化相似散布矩阵和差异散布矩阵之差的形式。 其描述如下:

通过式(25)引入拉格朗日乘子,使J(A)对A求偏导,并使之为零,得:

由此可知最优映射矩阵A由矩阵的前d个最小的非零特征值 λ1≤λ2≤…≤λd对应的特征向量组成{a1, a2, …, ad}。

MRLDP算法总体步骤描述如下:

Step1:采用k- 近邻准则,创建邻接图

Step2:确定权重Wij以及加权的类间离散度矩阵

Step3:求解矩阵的d个最小特征相对的特征向量{a1, a2, …, ad}组成投影矩阵A

Step4:完成样本投影y = ATx

Step5:利用欧式距离进行分类实验

4 实验结果及分析

通过在ORL人脸库与Yale人脸库上实验,对比经典的算法PCA、LDA、LPP、LDP;来评价本文提出的算法MRLDP。 实验环境:CPU主频为1.80GHz,双核四线程;操作系统Windows8.1; 算法通过Visual Studio 2010 以及Opencv244 库实现。

4.1 ORL库上的实验结果

ORL人脸库由40 人的人脸图像组成,每人包含10幅图像。 其中,图像的特点包括不同时期、不同表情、不同姿态与不同面部细节,同时包含平面内或垂直平面的不超过20°的偏转以及不超过10%的尺度改变。 每幅图像为灰度级256 的112×92 灰度图像。 首先对图像进行预处理, 将图像剪辑、 归一化成为32×22 的灰度图像。 从每个人的图片中随机抽取L(L=2,3,…,5)张图片作训练样本,剩下的10-L张图片用作测试样本。

从表1 可以看出:

(1)随着学习样本数目的增加,所有的算法的识别精度都得到了提升。 这表明训练样本信息直接影响着算法的识别精度,更丰富的已知样本信息才能得到更佳的投影矩阵。

(2)基于流形学习的特征抽取方法(如LPP)的最高识别精度比传统的特征抽取方法(如PCA)取得了更好的效果。 这主要是由于人脸图像受光线、表情等变化的影响,导致人脸图像是非线性不可分;因而,保存的全局欧氏距离的PCA算法难以有效地表示图像空间的内在流形结构。 而基于流形学习的特征抽取算法能够探索数据内部的本质结构,并在降维过程中保持数据的本质结构。 通过局部k- 邻域有效地保存了隐藏在图像空间内的局部结构,从而反映了图像空间分布的内在属性。

(3)有监督的特征抽取方法(如LDA)总体上要比无监督方法(如PCA)更优。 主要是由于自然获取的图像或多或少受到外在变化的影响,从而导致姿态、光照的变化。 使得无监督特征抽取方法所保存的局部属性难以有效地区分不同类别的人脸图像。 相反, 由于监督特征抽取方法考虑到了图像的类别信息,从而尽量的避免了这个缺点。 在同类人脸变化不大的ORL数据库中,流形算法LPP与有监督的算法LDA取得了相近的效果。

(4)MRLDP优于其他算法;因为MRLDP既考虑了流形结构,又加入了类别信息。 同时,克服了LDP算法仅考虑了样本k邻域内类别信息, 也即是局部类别信息;未能充分利用全局类别信息的缺点,通过最大程度地使得异类间中心相互远离来带动异类间样本的整体分散。 最终得到更具有区分性的投影向量。

从图1 可以看出,算法识别效果随着特征维数的增加而增加。 因为有监督的算法抽取的是有利于分类的投影矩阵;有监督的算法(如LDA,LDP)能够利用较少的特征维数得到较好的识别效果。 基于流形结构的算(LPP)优于仅考虑全局最优的算法(PCA);在维数较低时效果稍逊有监督的算法LDA;但随着样本的增加,最终取得了优于LDA的效果。 本文算法(MRLDP)同时考了到了流形结构与类别标签信息。 结合局部类别信息与全局类别信息,得到更了更好的识别效果。

4.2 Yale库上的实验结果

通过Yale数据库进行对比实验可以进一步验证本文算法的有效性。 作为人脸识别研究过程中常用的数据库之一,Yale人脸库由15 个人组成,每人含有三种不同光照方向、六种表情变化的11 幅灰度人脸图像。 这些图像光照条件变化比较大,而且面部表情(正常、悲伤、愉快、惊讶、困乏与眨眼)和脸部细节也有较为明显的改变。每张图片对面部图像进行剪裁,并归一化为32×32。

从每个人的图片中随机抽取L(L=3,4,…,6)张图像用于训练,余下的10-L张图片用作测试。 由于参数选取问题至今为止仍然不能从理论上给出最佳参考,所以通过实验对参数进行调节,采用识别效果最佳时的参数值。 同时通过随机交叉验证,保证实验的客观性。

文中所列的方法在Yale库上的精度比较低,这是因为Yale库的图像受光照、姿态、表情变化的干扰较大。 由于LDA没有考虑局部流形结够, 识别精度低于LPP和LDP,而LDP方法没有考虑全局类别信息,识别精度低于本文算法。

5 结束语

局部鉴别投影算法考虑了样本k邻域内类别信息,使同类的样本聚集,异类的样本远离从而实现了有监督的分类。 本文提出的算法MRLDP结合了类间加权的离散度矩阵,从而利用全局类别信息,通过最大程度地使得异类间中心相互远离来带动异类间样本的整体分散。最终得到了更具有的分类意义的子空间投影矩阵,使在原有空间中无法区分的人脸图像在子空间中能够得到区分。 实验证明,该算法可以更好地发现嵌入在高维空间中有意义的低维流形,能更好地实现复杂情况下的人脸识别。

基于改进邻域的局部保持投影方法 篇2

关键词：类别信息,局部保持投影,k近邻,监督

0 引 言

随着科学技术的进步,信息量爆炸性地增长,伴随着大量高维数据的产生,如何从海量的高维数据中寻找高维数据的本质信息,实现维数的约简化或者数据的可视化,解决信息资源巨大浪费而知识极端匮乏之间的矛盾,是近年来一直备受关注的问题。

数据降维方法分为非线性方法和线性方法,非线性降维方法(即流形学习方法)的典型代表包括等距映射Isomap[1](Isometric map)和拉普拉斯特征映射LE[2](Laplacian Eigenmaps)等,线性降维方法的典型代表包括主分量分析法PCA[3](Principal Component Analysis)和多维尺度变换MDS[4](Multi-dimensional Scaling)。线性降维方法虽然对具有线性结构的数据集能够进行一定的维数约简,但是对于非线性数据无能为力,而流形学习方法虽能有效学习非线性流形的本质,但对学习新数据时,却因需要对所有数据重新计算获得低维特征而导致计算效率低下。

为了兼顾线性降维和流形学习方法的优点,近年来学者提出了一系列的线性化流形学习方法,如局部线性嵌入算法LLE[5](Locally Linear Embedding)、局部保持投影算法LPP[6](Locality Preserving Projections)、线性局部切空间排列算法LLTSA[7](Linear Local tangent space alignment)等。局部保持投影方法(LPP),作为拉普拉斯特征映射的线性化方法,由于其在图像识别等领域的有效应用,受到了各方面学者们的广泛关注,如利用局部保持投影算法分析基因表达数据[8]、对超光谱图像进行降维提取特征[9]等等。

最初提出的局部保持投影方法是无监督的,在构造近邻图时,利用k近邻方法,将每个数据点与其距离最近的k个点之间用边相连,从而得到相邻无向图。但在分类或识别问题中,部分数据的类别信息往往是已知的。传统的LPP算法是无监督的学习方法,并没有利用数据已知的类别信息。采用k近邻方式构造的局部邻域可能包含异类点,而同一邻域内异类点在低维空间的投影仍将很近。显然,这种情况下,LPP算法对数据的分类和识别并没有改进。对此,李君宝等人在局部保持投影的思想上做了改进,提出了一种基于类别信息的监督局部保持投影算法CLPP[10](Class-wise Locality Preserving Projections),即在已知类别信息的情况下,当且仅当两点属于同类别,两点之间有边相连。当同类点距离相近时,采用这种同类别方式构造邻域,能确保局部邻域不包含异类点,从而改进分类效果。但是,对于许多流形数据,同类点的距离可能较远,这时,采用同类别方式构造的邻域完全忽略了数据之间的欧式距离,无法保持流形的局部几何性质,从而导致分类识别的失败。

对此,我们提出了一种基于改进邻域的局部保持投影ILPP(Improved Locality Preserving Projections)方法,采用一种新的构造近邻图的方式,有效利用已知信息的同时也不会丢失局部的几何性质。最后,通过和传统的LPP方法及CLPP方法进行对比实验,验证ILPP的有效性。

1 局部保持投影(LPP)和相关算法

假设高维空间上的一组样本数据集X=[x1,x2,…,xn],xi∈RM,其在低维嵌入空间Rm上的映射数据集为Y=[y1,y2,…,yn],yi∈Rm,m<<M。LPP算法的目的就是寻找一个投影矩阵A,使得高维空间中较近的样本点xi和xj,在低维空间上的投影坐标yi=ATxi,yj=ATxj也比较近。

LPP算法的主要步骤如下:

Step1 构造相邻无向图,主要有两种方式:

(i) k近邻方式:即当且仅当两点中,一点在另一点最近的k个点中,两点之间有边相连。

(ii) ε近邻方式:即当且仅当两点之间的距离小于常数ε,两点之间有边相连。

在ε近邻方式中,由于常数ε的取值需要多次实验取得,此外,ε近邻方式并不适用于数据分布不均匀的情况,因此,大多数论文中LPP采用k近邻方法构造近邻图。本文中,也只与k近邻方式进行比较。

Step2 构造权值矩阵W:

$w{}_{ij}=\{\begin{array}{cc}\text{e}{}^{-\frac{\parallel x{}_i-x{}_j\parallel {}^2}{t}}& x{}_i\text{与}x{}_j\text{之}\text{间}\text{有}\text{边}\text{相}\text{连}\\ 0& x{}_i\text{与}x{}_j\text{之}\text{间}\text{无}\text{边}\text{相}\text{连}\end{array}$

Step3 计算投影矩阵A:$\underset{\begin{array}{l}Y=A{}^{{\rm T}}X\\ y{}^{{\rm T}}Dy=1\end{array}}{{\displaystyle \min }}({\displaystyle \sum _{i,j=1}^n\parallel }y{}_i-y{}_j\parallel {}^{2}w{}_i{}_j)=\underset{a{}^{{\rm T}}XDX{}^{{\rm T}}a=1}{{\displaystyle \min }}A{}^{{\rm T}}XLX{}^{{\rm T}}A$

其中,a是变换向量:yT=aTX;D是一个对角矩阵:$D{}_{ii}={\displaystyle \sum _{j=1}^{n}w}{}_{ij}$;L是拉普拉斯矩阵:L=D-W。

基于类别信息的CLPP算法思想大致和传统的LPP算法思想相同,区别在于构造相邻无向图的方式上,即当且仅当两点属于同一类别,两点之间有边相连,这导致构造权值矩阵采取以下方法:假设样本点xi的类标为li,则:

$w{}_i{}_j=\{\begin{array}{cc}\text{e}{}^{-\frac{\parallel x{}_i-x{}_j\parallel {}^2}{t}}& \text{i}\text{f}l{}_i=l{}_j\\ 0& \text{i}\text{f}l{}_i\ne l{}_j\end{array}$

2 改进的局部保持投影(ILPP)算法

传统的LPP算法只考虑保持流形的局部几何特征,忽略了已有的类别信息;CLPP算法利用了已有的信息,同时也忽略了流形的局部几何性质,两种方法各有缺点,不能兼顾。在本节中,我们将提出一种新的构造近邻图的方法,同时保留了k近邻方式和同类别方式的优点,充分考虑了两种邻域构造方式的平衡。

记$\tilde{D}=[d(x{}_i,x{}_j)]{}_{i,j=1}^n$为所有样本点之间的欧式距离构造的矩阵,其中d(xi,xj)=‖xi-xj‖2。在k近邻方法中,对每个样本点xi选取最近k个点作为邻域点。对于无噪声而且样本分布均匀的理想流形,k近邻方法能较好地选取出局部线性邻域。但在实际问题中,由于数据噪声和样本数据分布的不一致,k近邻方法选取的局部邻域并不能保证具有流形的局部几何特征。针对这些问题,学者们已经提出一些选取流形邻域的改进方法,如文献[11]提出了构造k条边非相交最小生成树的等距数据嵌入方法,采用最小生成树的组合来创建邻域图,可避免邻域大小的选择问题;文献[12]提出的邻域参数动态确定的新局部线性嵌入方法,自适应地为每个数据点选择合适的邻域大小;等等。但是,这些工作都是基于流形自身结构进行邻域选取,并没有利用数据的类别信息。

在监督学习中,我们可以获知样本点xi的类标li,由此可以重新定义样本点距离:

$\tilde{d}(x{}_i,x{}_j)=\{\begin{array}{cc}\frac{\parallel x{}_i-x{}_j\parallel {}_2}{\beta }& \text{i}\text{f}l{}_i=l{}_j\\ \beta \parallel x{}_i-x{}_j\parallel {}_2& \text{i}\text{f}l{}_i\ne l{}_j\end{array}(1)$

其中,β(β≥1)为用户给定的参数。利用式(1)重新计算样本点距离,我们仍可以在新定义的距离中选取最近的k个点构造邻域。显然,当β=1时,$\tilde{d}(x{}_i,x{}_j)=d(x{}_i,x{}_j)$,所选取的邻域与k近邻方法选取邻域一致。当β→∞,所有同类点间距离趋于0,而异类点间距离趋于无穷,与基于类别的CLPP选取的邻域一致。因此,通过适当的β构造新距离,在有效利用类别信息的同时,能充分考虑数据的局部几何性质。

在式(1)中,参数β的选取决定了新定义样本点的距离。我们给出了一种β的选取策略:

$\beta =\alpha \frac{\underset{i,j,l{}_i=l{}_j}{{\displaystyle \max }}\parallel x{}_i-x{}_j\parallel {}_2}{\underset{i,j,l{}_i\ne l{}_j}{{\displaystyle \min }}\parallel x{}_i-x{}_j\parallel {}_2}$

其中,$\underset{i,j,l{}_i=l{}_j}{{\displaystyle \max }}\parallel x{}_i-x{}_j\parallel {}_2$表示最远的同类点距离,$\underset{i,j,l{}_i\ne l{}_j}{{\displaystyle \min }}\parallel x{}_i-x{}_j\parallel {}_2$表示最近的异类点距离,α≥1为用户参数(本文的所有实验中,α均为6)。显然,这种选取策略可以保证在构造的邻域中,不会包含已知分类信息的异类点。

基于我们新定义的距离式(1)和选取的邻域,我们提出了一种基于改进邻域的LPP方法。算法的基本步骤如下:

输入:数据集X=[x1,x2,…,xn],类别标号l={l1,l2,…,lm},邻域参数k,热核参数t;

输出:投影矩阵A。

Step1 构造相邻无向图:

利用式(1)计算所有样本点之间的距离$\tilde{d}$(xi,xj),即对每个数据点xi,将其与距离最近的k个点相连。

Step2 构造权值矩阵W:

$w{}_{ij}=\{\begin{array}{cc}e{}^{-\frac{\tilde{d}(x{}_i,x{}_j){}^2}{t}}& x{}_i\text{与}x{}_j\text{之}\text{间}\text{有}\text{边}\text{相}\text{连}\\ 0& x{}_i\text{与}x{}_j\text{之}\text{间}\text{无}\text{边}\text{相}\text{连}\end{array}$

Step3 计算投影矩阵A,构造如下极小化目标函数:

$\underset{\begin{array}{l}Y=A{}^{{\rm T}}X\\ y{}^{{\rm T}}Dy=1\end{array}}{{\displaystyle \min }}({\displaystyle \sum _{i,j=1}^n\parallel }y{}_i-y{}_j\parallel {}^{2}w{}_{ij})=\underset{a{}^{{\rm T}}XDX{}^{{\rm T}}a=1}{{\displaystyle \min }}A{}^{{\rm T}}XLX{}^{{\rm T}}A(2)$

其中,a是变换向量:yT=aTX;D是一个对角矩阵:Dii=∑${}_{j=1}^n$wij;L是拉普拉斯矩阵:L=D-W。求解极小化问题式(2)可以转化为广义特征值问题:XLXTA=λXDXTA,其中投影矩阵A=[a1,a2,…,ad]为d个最小的特征值对应的非零特征向量。

3 数值实验

在本节中,我们对纹理图片、手写数字库和人脸库,将分别采用LPP、CLPP和ILPP算法以及PCA算法进行对比实验,从而说明ILPP算法在分类问题中的有效性。

在实验中,我们首先将数据随机分成训练集和测试集,再将四种算法分别应用于训练集,从而学习投影矩阵A。然后,我们利用投影矩阵A将训练点和测试点投影到低维空间,并对低维结果采用最近邻分类器获得测试点的分类信息,最终计算测试点的识别率。常见的分类器有最近邻分类器、支持向量机[13]分类器、Fisher线性鉴别分析[14]方法等,虽然不同的分类器会产生不同的识别率,可是并不会改变不同降维方法之间的识别率大小关系,因此所有实验均只列出最近邻分类器所计算的识别率。

LPP和ILPP两种算法都涉及到目标维数d和热核参数t。在实验中,为了避免参数选取对算法评估的影响,我们统一采用相同的参数。在所有实验中,除特别指出外,目标维数为数据的类别数,热核参数t=107。此外,为了得到相对比较稳定的实验数据,所有实验结果为100次实验的平均结果。

3.1 纹理分类实验

我们将进行两组纹理图像的分类实验来说明LPP和CLPP的缺点,本实验所用的纹理图片取值于SIPI(Signal and Image Processing Institute)纹理图片库,整个纹理图片库包含154个单色图片,其中129张大小为512×512的纹理图片,25张大小为1024×1024的纹理图片。

第一组实验选取大小为512×512的原始木材纹理图片,分别经过0°、45°和90°旋转并裁剪处理,得到3张图片,图片大小为350×350,如图1所示;第二组实验选取大小均为512×512的木材、树皮和塑料气泡三张纹理图片,如图2所示。对于每组实验的每张原始图片均进一步进行区域选择并容许部分重叠,得到500张大小为16×16的图片,这样,得到了两个纹理图片数据集,且每个数据集总共由1 500张维数为256的图片组成,同时所有数据点属于所对应的原始的三个类别之一。图3为第一组实验对应的裁剪后的0°、45°和90°木材纹理三个类别图片实例,大小为16×16;图4为第二组实验对应的裁剪后的木材、树皮、塑料泡沫三个类别纹理图片实例,大小为16×16。

图5为固定邻域k取值为15,训练图片数目与测试图片数目均为750,在不同目标维数下,两组实验数据对应的识别结果,其中图5(a)为在第一组纹理图片上的实验结果,图5(b)为在第二组纹理图片上的实验结果。两张实验结果图都明显地展现了CLPP算法的劣势,在两组纹理实验上识别效果均不佳,同时,LPP算法在纹理实验中识别效果不稳定,图5(a)中,LPP算法的识别效果明显优于PCA算法,而图5(b)中,这一优势不再存在,ILPP算法在两组纹理图片上不同目标维数下识别效果稳定且理想。由图5(a)可知,随着目标维数的增大,对比的四种算法(PCA、LPP、CLPP和ILPP)的识别率都呈逐渐上升趋势,特别是ILPP算法始终保持识别率最高,显著地体现了ILPP算法对纹理图片具有良好的识别效果;图5(b)中,随着目标维数的增大,四种算法的识别率大体上也稳定增长,但是当目标维数超过类别数时,ILPP算法的识别率略为下降;虽然随着目标维数的增大,PCA算法的识别率逐渐高于ILPP算法,但是两种算法相对比,PCA算法不稳定,最高与最低识别率相差11.59%,而ILPP算法的识别率最大相差6.578%,对目标维数不是很敏感,且在两组纹理实验下识别效果都突出。

为了了解训练点数对四种算法的不同影响,利用第一组实验数据,固定目标维数为类别数(即为3),测试点为450,改变训练点数进行实验,得到图6的实验结果。由此图可以看出,ILPP、LPP算法的识别效果比较好,PCA和CLPP算法的识别率受训练点个数的影响较小,识别率一直比较平稳,但是识别效果不好;随着训练点数目的逐渐增多,ILPP、LPP算法的识别率均逐渐增大,且ILPP算法的识别率始终保持最高。

3.2 手写数字识别实验

本实验中,采用USPS_ALL手写数字库进行实验。此数字库包括10组数字(0-9)图像,每组数字有1 100张16×16图片构成。将每张图像转化成256维向量,这样手写数据集共包含11 000个256维的数据点。具体数据描述见表1。

表2列出了固定近邻参数k为25,测试点数为2 500时,不同训练点下,四种方法(PCA、CLPP、LPP和ILPP)的识别结果。从表2可以看出,随着训练点的增多,四种方法的识别效果都逐渐变好,且相同训练点情况下,ILPP的识别率均最高;同时可以看出,CLPP算法和LPP算法对训练点的数目比较敏感,CLPP算法在训练点数大于2 000时,识别率才略高于LPP,而ILPP算法对训练点数并不敏感,即使在训练点最少即1 500时,识别效果也很好。

PCA算法通过计算高维样本的协方差矩阵的本征矢量,将样本集的输入维数转化为主分量数,算法的实现与近邻参数无关;而CLPP算法利用有监督的方式构造邻域图,即当且仅当两点属于同一类别,两点之间有边相连,显然也与近邻参数无关。LPP算法和ILPP算法涉及近邻参数k,为了进一步考察近邻参数对这两种算法的影响,通过固定训练点为300×10,测试点为700×10进行实验,得到图7。为了便于比较,将CLPP算法的结果也同时绘出。从图7可以清晰地看出,LPP算法对k比较敏感,且LPP算法识别率呈逐渐下降趋势;而ILPP算法对k取值并不敏感,最大幅度为0.696%,并且随着k的取值变化,其识别率均高于CLPP和LPP算法,识别结果显著。

3.3 人脸识别实验

本实验中,采用ORL人脸库进行实验。具体数据描述见表1。对于人脸数据来说,数据维数比较高,计算量比较大,此外,当数据维数大于样本点数时导致LPP算法中广义特征值的求解很不稳定,因此,对于人脸数据库,我们利用PCA算法进行预降维处理。记APCA为利用PCA算法降维得到的投影矩阵,Xnew为利用PCA算法,将原始数据集X降维处理得到的新的实验数据集,A2为采用CLPP、LPP和ILPP算法,对Xnew进行降维后得到新的投影矩阵,那么,最终的投影矩阵为A=APCA·A2,降维后的结果为Y=ATX。

在本实验中,利用PCA进行初始降维,初始目标维数为100。表3列出了在ORL人脸库上,固定近邻参数k为25,测试点为120,四种方法在不同训练点条件下的识别结果。从此表可以看出,四种算法均受训练点影响,随着训练点逐渐增多,识别率都在不断提高,并且CLPP算法的识别率始终最低,LPP算法受训练点影响较大,仅在训练点数大于200时,识别率高于PCA算法,因此对于ORL人脸库,LPP和CLPP算法的识别效果比较差;同样可以看出,ILPP算法识别效果很显著且稳定,均比其他三种算法的识别率高,且最高识别率达到99.990%,同时对训练点数不敏感,即使在训练点数最小即120时,也具有较高的识别率。

4 结 语

局部保持投影最初的提出没有利用已知的类别信息,完全是无监督的算法,随之对其的进一步研究出现了利用类别信息构造邻域图的改进方法,但是这种方法完全忽略了数据的局部几何性质。针对这些问题,本文提出了一种新的构造邻域图的方式,将其应用于局部保持投影方法中,在保持流形局部几何特征的同时也有效利用了已知信息。该方法利用传统的欧式距离计算出数据点彼此之间的距离,然后利用类别信息,对于同类点之间或异类点之间的距离分别除以或乘以同一个大于1的常数,得到新的距离矩阵,从而构造权值矩阵,计算出投影矩阵,最终建立模型,即可得到高维数据在低维空间的本质信息。

通过对比实验,可以看出,我们利用新的构造邻域图的方法得到的ILPP算法与传统的k近邻方式构造的LPP算法和同类别方式构造的CLPP算法相比,有着明显的优势:第一,对于不同的实验数据,ILPP算法的识别效果都比较稳定,而CLPP算法对于人脸识别并不理想,且LPP算法对于纹理图片的识别效果不稳定;第二,对于受近邻参数k影响的两个算法ILPP和LPP来说,ILPP算法对于近邻参数不敏感,始终保持最好的识别效果,而LPP算法受近邻参数影响很大;第三,ILPP算法对训练数据要求不高,基本上在训练点较少的情况下,也能表现出较好的识别效果。此外,需要指出的是,涉及计算样本点之间新距离的控制参数的选取有着不同的方式,本文中的方法只是其一,对于不同的应用领域,可以根据实际情况获取更好的控制参数以达到最好的效果。

局部鉴别投影 篇3

Image matching is a searching procedure for a same or similar image from an image based on a given image[1].Image matching has already been used in modern information processing fields such as missile terrain matching guidance,airplane navigation,terminal guidance and target homing of weapon projection system,resource analyze,weather report,medical diagnose and word reading.

Matching algorithm plays an important role in the image matching system.Generally,there are two methods of correlation matching algorithms.One is based on the gray distribution,analyzing the two-dimensional image and judging the relevance matching through gray relevance and similarity.This method can result in high positioning accuracy and dense parallax surface,but is also very sensitive to the surface structure,light reflection and component geometry due to the dependency on statistic features of image gray distribution.The second method is based on the image features and selectively chooses the features that representative the features of scenery and consequently solve the ambiguity in matching.

The combination of concept of entropy and the features of projection into image matching is adopted to define the entropy of sectional projection and propose a new image matching method based on the entropy difference.This method is not only good at anti-gray reversion and easy at calculation,but also can be antigeometric distortion and anti-noise under strong light.Experiment results prove that this is an easy and effective matching algorithm used in the real-time tracking system.

1 Partial Projection Entropy

1.1 Projection features

Projection transformation is a common linear transformation.For a M×N image,suppose the image gray function is f(x,y)andf(x,y)≥0,and it could be defined that one-dimensional matrix U with the length M is the row projection feature[2]while the one-dimensional matrix V with the length N is the column projection feature,where:

The above definition formulas show that if M×N image is the set of M×N feature points,the features set is reflected into M×N feature points through projection transformation.Projection transformation reduces feature dimension and changes the characters of feature points.The direction employment of projection transformation,on the one hand,decreases the matching accuracy under certain conditions,but,on the other hand,increases the matching precise when the real-time images are distorted and improves the matching capability under strong light.The more important is,the image matching is much faster thanks to the smaller calculation amount.

1.2 Partial entropy based on image projection fea-tures

Entropy is usually used in the image coding in the digital image-processing field.The definition is:suppose image pixel gray set is(ω1,ω2,…,ωM)and the corresponding probability is(P1,P2,…,PM),then,the digital image has an entropy H[3]:

However,the above entropy is a kind of one-dimensional histogram features.Since the probability Pk is irrelevant to the relative position structure information of the scenery in the image,the image matching is low in accuracy and might fail in matching.In order to adopt the concept of entropy into the image matching,the image entropy needs to be redifined[4]:for a M×N image,suppose the image gray function is f(x,y)and f(x,y)≥0,and then we have:

Hfis called to be entropy of the image and is called to be partial entropy when only one part of the image is concerned.

The above image entropy is defined on the image two-dimensional gray function f(x,y)[5].The definition formula shows that image partial entropy reflects the amount of information in the image part and characterizes the partial feature of the image[6].If there is radiation distortion in a certain part the image,the partial entropy doesn’t change.Entropy is not sensitive to geometric distortion at certain degree.Therefore,the matching method based on the partial entropy will have a very good capability on anti-geometric distortion.

Despite of the above advantages,the entropy matching method also has some disadvantages.On the one hand,the size of entropy depends on the whole partial area and the gray value of a single pixel influences a little on the entropy.The normalization processing of the entropy also helps in the ease noise.Therefore,partial entropy is not sensitive to the impulsive noise.The anti-noise of the partial entropy needs improvement.On the other hand,the probability Pijis the ration of single pixel gray value and the whole partial gray sum,so mismatching easily happens when Pij is very low and calculation error rises.Apart from that,when adopting the image entropy as the only feature model,the calculating amount is not larger than that with traditional gray relevance model.As a result,we combine the projection features and the image entropy in order to improve the anti-noise and matching speed while remaining the excellent anti-geometric distortion.As have discussed above,the image projection features are U[i]and V[j],and then the projection entropy can be defined as:

HRPis called to be the row projection entropy while HCPto be the column projection entropy.They are called to be partial entropy when only one part of the image is concerned.For the convenience in the engineering usage,formula(6)and formula(7)can be expanded into the following formulas through Taylor expansion:

2 Matching algorithm based on the partial projection entropy difference

A matching algorithm based on the partial projection entropy difference is set up.Suppose the size of reference masterplate is M×M,and the real-time image is N×N with N>M and both M and N are powers of 2,and then the following will be the basic procedures to match images.

First step:divide the reference masterplate into several plates with smaller size.

Second step:calculate the partial projection entropy of every plates by using the above partial projection entropy and save the row and column projection entropy in sequence by using couples of sequence arrays.

Third step:rough matching.the following matching strategies should be employed for more effective results.

(1)Saltatory searching:usually the salutatory searching uses scanning line by line on the real-time image.Here,we use interlaced scanning(usually every 2—3 pixels).

(2)Sequential checking:the usual matching methods calculate all the real-time images and reference masterplages.Here,sequential checking method is used,to be more exact,calculating plate matching while checking threshold to decide whether there is necessity to continue calculating plates.

Matching procedure is as follows:

(1)Take the scanning point as central point(or as top left corner),and find the candidate matching image with the same size as that of reference masterplate and then make the division on the candidate matching image.

(2)Pick every candidate matching image entropy array from the sequent real-time images and correspondingly minus the partial projection entropy on the reference masterplate.Entropy difference will be the progressive accumulation of absolute value.If the difference is larger than a threshold,the following projection entropy calculation stops and turns to the next matching.

(3)Pick the candidate matching image with the smallest projection entropy difference as the matching image in the rough matching phrase.

Fourth step:precise matching.

(1)take the coordinate of the rough matching image as the center,and expand 3M/4 into a 3M/2×3M/2 searching area on the real-time image[7].

(2)Match pixel by pixel,and get the final matching image.

3 Algorithm simulation and experiment re-sult

During the experiment,the traditional gray relevance algorithm and the algorithm based on the partial projection entropy are compared.Fig.1 is the reference image and the real-time image,the left of which is reference image with the size being 64×64 while the right real-time image 512×512.Fig.2 are real-time images under strong light and in sphere geometrical distortion.Fig.3 and Fig.4 are comparison between the two algorithms,among which(a)s are results from the discussed algorithm and(b)s are from traditional algorithm.The result shows that the matching result is much better when algorithm based on the partial projection entropy is adopted while the traditional gray relevance leads to an obvious failure.re.

4 Conclusion

All the experiment results show that neither traditional gray relevance algorithm or edge relevance algorithm can lead to a right matching under certain geometric distortion or certain strong light.However,algorithm based on the partial projection entropy can get a right match.This algorithm is good at anti-geometric distortion and anti-noise.Additionally,this algorithm is found from a structure analysis to be good at parallelism and will promote the parallel programming in engineering realization.A high-speed DSP device will be fully satisfied for a real-time tracking demand.

参考文献

[1] 沈庭芝,方子文.数字图像处理及模式识别.北京:北京理工大学 出版社,1998

[2] 桂志国,等.基于投影特征的图像匹配的快速算法.华北工学院 测试技术学报,2000;14(1):18—20

[3] 夏良正.数字图像处理.南京:东南大学出版社,1999

[4] Pal N.et al. Object-background segmentation using new definitions of entropy. IEEE Proc Pt E,1989;136(4):284—295

[5] 田金文,等.基于局部熵差的图像匹配方法——算法及计算机仿 真.宇航学报,1999;20(1):28—32

[6] Shiozaki A. Edge extraction using entropy operator. CVGIP Proc, 1986;36:1—9

局部鉴别投影 篇4

关键词：局部保持投影,特征提取,半监督,高光谱

0 引 言

高光谱遥感技术利用成像光谱仪纳米级的光谱分辨率,以几十或几百个波段同时对地物成像,能够获得地物接近连续的光谱信息,成为高分辨对地观测系统的重要组成部分之一。然而,高光谱传感器为地物分类和识别提供细致光谱特征的同时也带来了大量的冗余数据,给后续分类处理带来了难度。为了去除这些冗余数据,通常需对高光谱数据进行特征提取。

局部保持投影[1](Locality Preserving Projections, LPP)是最近提出的一种线性特征提取算法,它是Laplacian Eigenmap[2] 流形学习算法的线性近似,该算法既克服了主成分分析和Fisher判别分析[3]等线性特征提取算法难以保持原始数据非线性流形的缺点,同时又解决了非线性流形学习方法[4]难以直接映射新样本的问题,因此在模式分类领域得到广泛应用[5,6]。然而,LPP算法仅能保持近邻样本对的局部结构,对原本相互远离的样本,LPP算法并未加以约束。对此,Yang等提出无监督鉴别保持投影算法[7],其在建模的同时考虑局部和非局部散度,从一定程度上克服了LPP存在的问题,但该算法在小样本条件下会出现矩阵奇异,导致算法无法求解。王建国等则利用非局部散度和局部散度之差作为鉴别准则,避免了矩阵奇异问题,然而分类精度有所降低[8]。

上述算法虽对LPP性能有一定改善作用,但其仅能够保证经过特征提取后样本的相对位置能够得到保持,无法保证提取的特征更容易分类。 针对这一缺点,本文提出一种改进算法,该算法在LPP算法的目标函数中加入标记样本信息,通过标记样本所携带的类别信息来约束未标记样本的相对位置;同时,还通过在目标函数中加入正则项以避免矩阵奇异问题。由于这种算法在训练过程中同时用到了标记样本和未标记样本——这是一种介于有监督学习和无监督学习之间的半监督学习思想[9],故将这种改进算法称为半监督保持投影(Semi-supervised Preserving Projections,SPP)算法。实验结果表明,经过改进的SPP算法进行特征提取后,不同类别样本的区分性增强,分类精度比LPP算法有较大提高。

1 局部保持投影算法

局部保持是一种典型的线性流形学习算法,其原理可用谱图理论进行解释。设X=[x1,x2,…,xN]是由m维向量构成的数据集合,x1,x2,…,xN∈Rm。LPP目标是寻找一个投影矩阵W,该矩阵可以将位于高维空间的数据映射至一个低维子空间Rd(d≪m)中,并同时尽可能使数据的局部相对位置保持不变,即:如果样本对在原始高维空间中是相互靠近的,那么经投影矩阵变换至低维子空间后,该数据对仍然保持相互靠近。令数据集在低维子空间Rd中表示为Z=[z1,z2,…,zN],则Z=WTX。

为了使数据的局部相对位置保持不变,LPP算法的目标函数定义如下:

$\min \left(\frac{1}{2}{\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{j=1}^{{\rm N}}\parallel }}\mathit{y}{}_i-\mathit{y}{}_j\parallel {}^2\mathit{S}{}_{ij}\right)(1)$

式中:yi=WTxi,且W=[w1,w2,…,wd];Sij是权重矩阵,采用k近邻法来定义:

$\mathit{S}{}_{ij}=\{\begin{array}{l}\exp \left(-\frac{\parallel \mathit{x}{}_i-\mathit{x}{}_j\parallel {}^2}{t}\right),\mathit{x}{}_i\in {\rm N}{}_k(x{}_j)\\ 0,\text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\end{array}(2)$

式中:t为大于0常数;Nk(xi)表示由xi的k个最近邻样本点组成的集合。

对式(1)进行简单的变量代换,可得到下式:

$\begin{array}{l}\frac{1}{2}{\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{j=1}^{{\rm N}}\parallel }}\mathit{y}{}_i-\mathit{y}{}_j\parallel {}^2\mathit{S}{}_{ij}\\ =\frac{1}{2}{\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{j=1}^{{\rm N}}\parallel }}\mathit{W}{}^{\text{Τ}}\mathit{x}{}_i-\mathit{W}{}^{\text{Τ}}\mathit{x}{}_j\parallel {}^2\mathit{S}{}_{ij}\\ ={\displaystyle \sum _i\mathit{W}}{}^{\text{Τ}}\mathit{x}{}_{i}d{}_{ii}\mathit{x}{}_i^{\text{Τ}}\mathit{W}-{\displaystyle \sum _{i,j}\mathit{W}}{}^{\text{Τ}}\mathit{x}{}_i\mathit{S}{}_{ij}\mathit{x}{}_j^{\text{Τ}}\mathit{W}\\ =\mathit{W}{}^{\text{Τ}}\mathit{X}(\mathit{D}-\mathit{S})\mathit{X}{}^{\text{Τ}}\mathit{W}\\ =\mathit{W}{}^{\text{Τ}}\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}}\mathit{W}(3)\end{array}$

式中:D=diag(d11,d22,…,dNN)为对角矩阵,其对角线上的元素的矩阵S中对应的列(或行)元素之和,即$d{}_{ii}={\displaystyle \sum _{j=1}^{{\rm N}}\mathit{S}}{}_{ij}‚\mathit{L}=\mathit{D}-\mathit{S}$,矩阵L为Laplacian矩阵。

2 半监督保持投影算法

局部保持投影算法能够使近邻样本对在低维子空间中仍然保持相互邻近,然而由于其没有利用标记样本所携带的类别信息,无法保证原始数据投影至低维空间后更有利于进行分类判别。为了克服LPP算法的这一缺点,本文提出一种同时利用大量未标记样本和少量标记样本的半监督保持投影(SPP)算法。在SPP算法中,为了利用标记样本的类别信息,在目标函数中引入了类似于Fisher判别思想[10]的类内散布矩阵和类间散布矩阵;并且定义了非局部结构信息,使非近邻样本对的相对结构在低维空间中也能得到保持;同时还在目标函数中增加一正则项,克服了矩阵奇异问题。

2.1 算法描述

假定标记样本集为L={xi,yi}${}_{i=1}^{{\rm N}}$,类别标签yi∈{1,2,…,c},其中c为样本类别总数; Nk为第k类的样本数目;x${}_i^k$为属于第k个类别的第i类样本。令S(w)和S(b)分别代表样本的类内散布矩阵和类间离散度矩阵,其定义分别如式(4)和式(5)所示:

$\begin{array}{l}\mathit{S}{}^{(w)}={\displaystyle \sum _{k=1}^c{\displaystyle \sum _{i=1}^{{\rm N}{}_k}(}}\mathit{x}{}_i^k-\mathit{\mu }{}^k)(\mathit{x}{}_i^k-\mathit{\mu }{}^k){}^{\text{Τ}}(4)\\ \mathit{S}{}^{(b)}={\displaystyle \sum _{k=1}^c{\rm N}}{}_k(\mathit{\mu }{}^k-\mathit{\mu })(\mathit{\mu }{}^k-\mathit{\mu }){}^{\text{Τ}}(5)\end{array}$

式中:μk为第k类样本的均值向量;μ为所有样本的均值向量,其定义如式(6)和式(7)所示:

$\begin{array}{l}\mathit{\mu }{}^k=\frac{1}{{\rm N}{}_k}{\displaystyle \sum _{i=1}^{{\rm N}{}_k}\mathit{x}}{}_i^k(6)\\ \mathit{\mu }=\frac{1}{{\rm N}}{\displaystyle \sum _{i=1}^{{\rm N}}\mathit{x}}{}_i(7)\end{array}$

通过求解式(8)所示的Fisher准则,即可实现同类样本在低维子空间中相互聚拢,非同类样本相互远离。

$J(\mathit{W})=\text{a}\text{r}\text{g}\text{m}\text{a}\text{x}\frac{\mathit{W}{}^{\text{Τ}}\mathit{S}{}^{(b)}\mathit{W}}{\mathit{W}{}^{\text{Τ}}\mathit{S}{}^{(w)}\mathit{W}}(8)$

式(8)的求解方法与式(3)类似,采用Lagrange乘子法求解,因此可将类内散布矩阵和类间散布矩阵加入目标函数式(3)中。最佳投影矩阵W的求解方法等同于求解如式(9)的特征值问题:

$\mathit{S}{}^{(b)}\mathit{W}=\lambda (\alpha \mathit{S}{}^{(w)}+(1-\alpha )\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}})\mathit{W}(9)$

利用式(9)求解出投影矩阵W,样本在低维子空间不仅能够保持局部结构;而且还利用标记样本的类别信息,使得同类样本聚集在一起,不同类样本相互远离。参数α控制着标记样本对投影矩阵的影响,由其取值范围为[0,1]:当α=1时,投影矩阵完全由标记样本确定;当α=0时,式(13)退化为LPP算法。

然而,仅保持样本在低维子空间中的局部结构不变并不能达到最佳的效果;对于原本相互远离的样本,应该在其投影到低维空间后也保持相互远离。为此,本文参照式(3)局部结构的定义,又定义了非局部结构的目标函数:

$\begin{array}{l}\max (\frac{1}{2}{\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{j=1}^{{\rm N}}\parallel }}\mathit{y}{}_i-\mathit{y}{}_j\parallel {}^2\tilde{\mathit{S}}{}_{ij})\\ =\max ({\displaystyle \sum _i\mathit{W}}{}^{\text{Τ}}\mathit{x}{}_i\tilde{d}{}_{ii}\mathit{x}{}_i^{\text{Τ}}\mathit{W}-{\displaystyle \sum _{i,j}\mathit{W}}{}^{\text{Τ}}\mathit{x}{}_i\tilde{\mathit{S}}{}_{ij}\mathit{x}{}_j^{\text{Τ}}\mathit{W})\\ =\max (\mathit{W}{}^{\text{Τ}}\mathit{X}\tilde{\mathit{L}}\mathit{X}{}^{\text{Τ}}W)(10)\end{array}$

式中:$\tilde{\mathit{L}}=\tilde{\mathit{D}}-\tilde{\mathit{S}}‚\tilde{\mathit{D}}=\text{d}\text{i}\text{a}\text{g}$$(\tilde{d}{}_{11},\tilde{d}{}_{22},\cdots ,\tilde{d}{}_{{\rm N}{\rm N}})‚\tilde{d}{}_{ii}={\displaystyle \sum _{j=1}^{{\rm N}}\tilde{\mathit{S}}}{}_{ij}$。$\tilde{\mathit{S}}$ij的定义如下:

$\tilde{\mathit{S}}{}_{ij}=\{\begin{array}{l}1-\exp \left(-\frac{\parallel \mathit{x}{}_i-\mathit{x}{}_j\parallel {}^2}{t}\right),\mathit{x}{}_i\notin {\rm N}{}_k(\mathit{x}{}_j)\\ 0,\text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\end{array}(11)$

将式(10)也加入式(9)中,得到式(12):

$(\alpha \mathit{S}{}^{(b)}+(1-\alpha )\mathit{X}\tilde{\mathit{L}}\mathit{X}{}^{\text{Τ}})\mathit{W}=\lambda (\alpha \mathit{S}{}^{(w)}+(1-\alpha )\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}})\mathit{W}(12)$

此时,利用式(12)得到投影矩阵W后,样本在低维子空间中不仅能够保持近邻样本的局部结构,并且可以保持非近邻样本对的非局部结构;同时,在式(12)中,标记样本的类别信息也得到利用,这使样本投影到低维空间后,属于同一类别的样本会更加靠近,属于不同类别的样本彼此远离。因此从分类角度考虑,利用该算法进行特征提取比原始的LPP算法更加适合进行后续分类处理。但是,在小样本条件下,式(12)等式右端的S(w)+XLXT可能为奇异矩阵,从而导致该特征值问题无法正常求解。为此,本文依照文献[11]的处理方法,通过添加一正则项从而使其变为非奇异矩阵:

$\begin{array}{l}(\alpha \mathit{S}{}^{(b)}+(1-\alpha )\mathit{X}\tilde{\mathit{L}}\mathit{X}{}^{\text{Τ}})\mathit{W}=\\ \lambda (\alpha \mathit{S}{}^{(w)}+(1-\alpha )\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}}+\gamma {\rm I}{}^m)\mathit{W}(13)\end{array}$

最终,本文提出的SPP算法的投影矩阵由式(13)求解,该式是一个特征值求解问题,投影矩阵W为前r个最大特征值对应的特征向量组成的矩阵,r为子空间维数。

2.2 算法步骤

综上所述,SPP算法步骤可以归纳如下:

输入:N个m维原始空间数据组成的N×m矩阵X;

输出: N个d维特征空间数据组成的N×d矩阵Y,m≥d;

(1) 在原始空间中计算样本点之间的距离,找出每个未标记样本点的k个最近样本点;

(2) 计算未标记样本对间的权重矩阵Sij和$\tilde{\mathit{S}}$ij,由此可以分别计算未标记样本的局部结构XLXT和非局部结构X$\tilde{\mathit{L}}$XT;

(3) 对于标记样本,分别计算其类内散度S(w)和类间散布矩阵S(b);

(4) 根据式(13)求解投影矩阵W;

最终,原始高维数据在特征空间中的投影为Y=WTX。

3 实验结果与分析

实验采用机载可见/红外成像光谱仪AVIRIS获取的佛罗里达州肯尼迪中心(KSC)高光谱数据作为本文算法的验证数据(如图1所示)。该数据共有224个波段,实验中去除了受大气水分影响以及低信噪比的波段,保留了155个信噪比较高的波段构成数据集合。该数据集中有13类地物,本文选取数量较多的10类地物作为实验的样本集(见表1)。实验平台为Matlab 7.8,Pentium 4处理器 1.8 GHz,1 GB RAM,操作系统为Windows XP。

由第2节可知,本文提出的SPP算法有k,t,α,γ四个参数待定。由于这四个参数取值并无理论指导,故先通过实验确定这四个参数的最优取值。实验发现,参数k的取值对算法性能影响较小,故本文中直接给出该参数的取值k=5。实验选取表1中每类样本的20%作为训练样本集,其余样本作为测试集,采用K-近邻分类器对特征提取后的数据进行分类,实验结果如图2和图3所示。由实验结果可以看出:参数t,α,γ的取值对算法性能有极大影响,在该实验中,当α=0.8,t=0.1,γ=0.5时,算法SPP可以达到最优的特征提取效果。

为了验证SPP算法的有效性,实验还给出了在不同训练样本数量条件下SPP算法的分类精度,并与PCA,LPP以及文献[10]提出的半监督特征提取算法LGSSDR进行性能比较。实验采用K-近邻分类器(K-NN),使用分类结果精度衡量4种特征提取算法性能。实验选取表1所示样本集中的β%作为训练样本,剩余样本作为测试样本,β的取值范围为5～50。降维后的子空间维数取 [12]10。图4给出了在不同训练样本数量情况下4种特征提取算法在K-NN(k=1)分类器下的分类精度。

由图4的分类结果可以看出,由于PCA和LPP均为无监督特征提取算法,无法利用标记样本带来的监督信息,因此分类精度很低,难以满足实际应用要求。而本文提出的半监督保持投影算法SPP在原有LPP基础上加入了类内散度和类间散度,能够充分利用标记样本的类别信息来约束未标记样本点;使得样本投影到特征空间后,同类样本相互靠近,非同类相互远离,降低了分类难度,因此分类精度LPP算法有显著提高。同时,SPP算法的求解类似于Fisher判别分析,在标记样本数量较少时也会出现奇异矩阵,导致算法无法求解。为此,在目标函数的分母上增加了正则项,保证了算法在所有条件下均能够正常求解。

与LGSSDR算法相比:在标记样本数目较少时,本文提出的SPP算法的分类精度与LGSSDR算法相当;但是,随着标记样本数目的增加,SPP算法逐渐显现出其优势,分类精度高于LGSSDR算法。表2给出了4种特征提取算法在10种地物类型上的分类精度。由该表可以看出,在大多数地物类型中SPP算法的分类精度均高于其他三种算法,特别是在第2,3,5类中,SPP算法的分类精度得到显著提高。

4 结 论

LPP算法是基于样本的局部性进行建模,无法保证其提取出的特征有利于后续分类处理。对这一问题,本文提出了一种半监督保持映射(SPP)的特征提取算法。该算法充分利用标记样本的类别信息来约束未标记样本,使样本经SPP算法提取特征后,分类精度显著提高;同时正则项的加入避免了算法出现矩阵奇异问题。最后,通过实际KSC高光谱数据进行对比实验表明了SPP算法的有效性。

参考文献

[1]HE Xiao-fei,NIYOGI P.Locality preserving projections[J].Advance in Neural Information Processing Systems,2004,16:153-160.

[2]BELKIN M,NIYOGI P.Laplacian eigenmaps for dimen-sionality reduction and data representation[J].NeuralComputation,2003,15(6):1373-1396.

[3]DUDA R,HART P.Pattern classification and scene analy-sis[M].New York:Wiley,1973.

[4]宋欣,叶世伟.基于局部线性逼近的流形学习算法[J].计算机仿真,2008,25(7):86-89.

[5]郭金玉,苑玮琦.基于局部保持投影的掌纹识别[J].光学学报,2008,28(10):1920-1924.

[6]TANG Y,RICHARD R.A study of using locality preser-ving projections for feature extraction in speech recognition[C]//Proceedings of IEEE International Conference on A-coustics,Speech and Signal Processing.[S.l.]:IEEE,2008:159-1572.

[7]王建国,杨万扣,杨静宇.基于保持投影的最大散度差的特征抽取方法[J].模式识别与人工智能,2009,22(4):610-613.

[8]YANG Jian,ZHANG D,YANG Jing-yu,et al.Globallymaximizing locally minimizing unsupervised discriminantprojection with applications to face and palm biometrics[J].IEEE Trans.on Pattern Analysis and Machine Intelli-gence,2007,29(4):650-664.

[9]CHAPELLE O,SCHOLKOPF B.Semi-supervised learning[M].Cambridge,MIT Press:2006.

[10]韦佳,彭宏.基于局部与全局保持的半监督维数约减方法[J].软件学报,2008,19(11):2833-2842.

[11]KUO B C,LI C H,YANG J M.Kernel nonparametricweighted feature extraction for hyperspectral image classi-fication[J].IEEE Trans.on Geoscience and RemoteSensing,2009,47(4):1139-1155.