文章快速检索     高级检索
  山东大学学报(工学版)  2018, Vol. 48 Issue (1): 8-14  DOI: 10.6040/j.issn.1672-3961.0.2017.401
0

引用本文 

钱文光, 李会民. 一种相似子空间嵌入算法[J]. 山东大学学报(工学版), 2018, 48(1): 8-14. DOI: 10.6040/j.issn.1672-3961.0.2017.401.
QIAN Wenguang, LI Huimin. A similarity subspace embedding algorithm[J]. Journal of Shandong University (Engineering Science), 2018, 48(1): 8-14. DOI: 10.6040/j.issn.1672-3961.0.2017.401.

基金项目

河北省科技计划资助项目(12210317);河北省科学技术研究与发展计划专项资助项目(15K55403D); 廊坊市科技支撑计划资助项目(2014011021)

作者简介

钱文光(1980—), 男, 河北邯郸人, 讲师, 工学硕士, 主要研究方向为高维数据降维算法. E-mail:wgqian1980@163.com

文章历史

收稿日期:2017-08-23
网络出版时间:2017-10-29 19:21:32
一种相似子空间嵌入算法
钱文光, 李会民     
北华航天工业学院计算机与遥感信息技术学院, 河北 廊坊 065000
摘要:通过对经典的线性判别分析(Linear Discriminant Analysis, LDA)及最大边界准则(Maximum Margin Criterion, MMC)方法的分析, 提出一种类内子空间深入学习的监督降维方法——相似子空间嵌入(Similarity Subspace Embedding, SSE), 对类内离散度矩阵进行深入学习, 得到每类的类内离散度子空间, 通过对所有类内离散度子空间的学习, 获得信息更为丰富的类间离散度矩阵, 进而得到更好的低维空间。与MMC方法相比, SSE方法对类内数据学习更充分, 同时避免了LDA方法存在的小样本问题。在AR人脸图像、Coil数据集及手写体上的试验结果表明, 与其它三种相关的经典方法相比, SSE方法具有较高的识别率, 说明了该方法的有效性。
关键词降维    线性判别分析    最大边界准则    离散度矩阵    子空间    小样本问题    
A similarity subspace embedding algorithm
QIAN Wenguang, LI Huimin     
School of Computer and Remote Sensing Information Technology, North China Institute of Aerospace Engineering, Langfang 065000, Hebei, China
Abstract: By the analysis of the classical Linear Discriminant Analysis (LDA) and Maximum Margin Criterion (MMC) methods, a supervised dimensionality reduction by in-depth learning within scatters of classes which called Similarity Subspace Embedding (SSE) was proposed. A deep study on the within class scatter matrix was made. The divergences of the subspace of each class were obtained by subspace learning. This approach could get abundant information between class scatter matrixes, and then get a better low dimensional space. Compared with the MMC method, the SSE method was more adequate for the class of data learning, while avoiding the small sample problem of the LDA method. Experimental results on AR face image, Coil data set and handwriting showed that the proposed method had a higher recognition rate compared with other three classic methods, which showed the effectiveness of the proposed method.
Key words: dimensionality reduction    LDA    MMC    scatter matrix    subspace    small-sample-size problem    
0 引言

近年来, 随着网络、信息技术及多媒体技术的迅速发展, 处理高维数据成为亟待解决的问题, 降维成为解决这一问题的主要途径, 例如经典的主成分分析(Principal Component Analysis, PCA)[1]、多维尺度变换(Multidimensional Scaling, MDS)[2]等方法, 但这些方法很难处理非线性数据。Roweis等人[3]提出的局部线性嵌入(Locally Linear Embedding, LLE)降维方法可以处理非线性数据。LLE假设数据在局部是线性分布, 每个数据点可由其近邻线性表示出来, 在降维过程中, 尽可能保持局部线性的拓扑结构。利用局部线性的思想, Zhang等人[4]提出了局部切空间排列(Local Tangent Space Alignment, LTSA)算法, LTSA的局部线性由切空间实现, 并将局部的切坐标进行全局排列, 实现非线性降维。但这些方法都无法处理新样本, 使得非线性方法在实际应用中受到限制。为了处理新样本, 子空间投影方法逐步得到了关注, 考虑局部结构的线性降维算法迅速发展起来, 如局部保持投影(Locality Preserving Projections, LPP)[5]、邻域保持嵌入(Neighborhood Preserving Embedding, NPE)[6]、邻域保持映射(Neighborhood Preserving Projections, NPP)[7]以及局部寻求嵌入(Locality Pursuit Embedding, LPE)[8]等算法都是通过全局的线性映射实现降维。由于投影的优良特性, 这些方法在实际应用中取得了较好的效果。然而, 在许多实际问题中都要考虑监督的降维方法, 例如, 医学图像的分类[9]、人脸识别[10]、指纹分类[11]、文本分类[12]等。

线性的监督算法容易理解、效率高。例如, 线性判别分析[13](Linear Discriminant Analysis, LDA)是一种典型的监督降维方法, 已成功应用于指纹识别、图像检索等许多实际应用领域。LDA定义了类内离散度及类间离散度矩阵, 希望在投影空间中, 类间离散度尽可能大, 同时类内离散度尽可能小, 进而得到最优的子空间。LDA仅考虑了两类情况[14], Rao等人在此基础上, 将LDA推广到了多类情况[15]。为了提高LDA算法的性能, 近些年提出了许多LDA的改进算法及基于LDA的监督学习方法。线性边界判别分析(Linear Boundary Discriminant Analysis, LBDA)[16]将数据集分为边界集及非边界集, 同样, 利用LDA类间离散度最大及类内离散度最小的思想, 寻找低维子空间, LBDA希望类内非边界样本离散度最小, 类间的边界样本及类均值向量离散度最大。该方法计算类间离散度具有更强的鲁棒性。Loog等人[17]提出了一种加权的成对费舍准则(Pairwise Fisher Criteria, PFC)对LDA进行改进, 利用马氏距离定义不同两个类别对的权重函数, 使类间判别信息多于LDA, 然后利用LDA的思想寻找低维子空间。为了解决实际应用问题, Li等人[18]针对图像提出了监督的降维算法——2DLDA, 该算法尽可能保留图像中像素间的二维关系信息, 避免了图像向量化造成的信息损失, 在图像降维及分类中, 可得到优于LDA的低维空间。为了实现非线性数据的学习, 二次判别分析(Quadratic Discriminant Analysis, QDA)[19]假设每类样本服从正态分布, 该算法在处理正态分布的数据集时明显好于LDA, 但需要稠密的训练样本描述数据分布, 使得QDA的应用受到了限制。以上方法从不同角度对LDA进行了改进。但基于LDA的结构都要解决小样本问题, 使得以上方法都需要正则化或其他方法解决该问题。

最大边界准则(Maximum Margin Criterion, MMC)[20]改变了传统LDA的结构, 解决了小样本问题。在此基础上, 考虑到数据的鲁棒性, Fu等人[21]提出了相关嵌入分析(Correlation Embedding Analysis, CEA)算法, 该算法利用样本的余弦作为相似度度量, 将高维数据映射到单位超球面上, 利用图理论刻画样本间的关系, 最终获得样本的低维嵌入。但CEA需要解决一个广义的特征分解问题, 因此, 无法避免小样本问题。为了解决小样本问题, 同时考虑类内离散度及类间离散度的平衡问题, Liu等人[22]提出了离散度平衡的监督降维方法(Angle Linear Discriminant Embedding, ALDE), 解决了离群类及离群点的问题。

通过分析以上监督降维方法, 本研究提出一种类内子空间深入学习的监督降维方法, 记为相似子空间嵌入(Similarity Subspace Embedding, SSE)方法, 该方法继承了MMC的思想, 利用MMC的结构解决小样本问题。同时, 充分学习数据集中每类的类内离散度, 实现鲁棒的监督降维。在技术上, SSE方法首先对每类的类内离散度矩阵进行特征分解, 使每类的类内离散度得到统一表示。同时, 提出的方法所要寻找的子空间希望不同类的类内离散度尽可能小, 通过对所有类内离散度子空间的学习, 获得信息更为丰富的类间离散度矩阵, 进而得到最优子空间。在AR人脸图像、Coil数据集及手写体上的试验结果表明, 提出的方法具有较高的识别率, 说明了该方法的有效性。

1 SSE方法 1.1 相关的监督降维方法分析

与提出的SEE相关的算法为LDA、MMC以及ALDE算法。首先分析LDA算法。考虑含有$N$个样本的数据集$\boldsymbol{X}$=[$\boldsymbol{x}_{1}$, …, $\boldsymbol{x}_{N}$]∈$\mathbf{R}^{D×N}$$D$维空间的数据。$\boldsymbol{X}$含有$c$类数据, 且满足$N$=$∑\limits^{c}_{i=1}N_{i}$, 其中, $N_{i}$为每类样本的个数。现欲将$\boldsymbol{X}$降至$d$维, 希望寻找如下线性投影:$\boldsymbol{W}$=[$\boldsymbol{w}_{1}$, $\boldsymbol{w}_{2}$, …, $\boldsymbol{w}_{d}$]∈$\mathbf{R}^{D×d}$, 则LDA的优化过程可通过如下的优化函数实现:

$ \mathit{\boldsymbol{W}}_{{\rm{opt}}}^{{\rm{LDA}}} = \mathop {\arg \max }\limits_\mathit{\boldsymbol{W}} \frac{{{\rm{tr}}\left( {\mathit{\boldsymbol{W}}{\mathit{\boldsymbol{S}}_{\rm{b}}}{\mathit{\boldsymbol{W}}^{\rm{T}}}} \right)}}{{{\rm{tr}}\left( {\mathit{\boldsymbol{W}}{\mathit{\boldsymbol{S}}_{\rm{w}}}{\mathit{\boldsymbol{W}}^{\rm{T}}}} \right)}}, $

式中:$\boldsymbol{S}_{\text{b}}$=$\boldsymbol{X}_{\text{b}}\boldsymbol{X}^{\text{T}}_{\text{b}}$为类间离散度矩阵, 其中$\boldsymbol{X}_{\text{b}}$=$\frac{1}{\sqrt{N}}[\sqrt{N_{1}}\hat{\mathbf{μ}}_{1},…,\sqrt{N_{c}}\hat{\mathbf{μ}}_{c}$], $\hat{\mathbf{μ}}_{i}$=$\mathbf{μ}_{i}$-$\mathbf{μ}$, $\mathbf{μ}$为全局的均值向量, $\mathbf{μ}_{i}$为第$i$类的均值向量; $\boldsymbol{S}_{\text{w}}$为类内离散度矩阵, $\boldsymbol{S}_{\text{w}}$=$\frac{1}{N}∑\limits^{c}_{i=1}∑\limits^{N_{i}}_{j=1}$($\boldsymbol{x}_{ij}$-$\mathbf{μ}_{i}$)($\boldsymbol{x}_{ij}$-$\mathbf{μ}_{i}$)$^{\text{T}}$=$\boldsymbol{X}_{\text{w}}$($\boldsymbol{X}_{\text{w}}$)$^{\text{T}}$, 其中$\boldsymbol{X}_{i}$=[$\boldsymbol{x}_{i1}$, …, $\boldsymbol{x}_{iN_{i}}$]为第$i$类的样本矩阵, $\boldsymbol{X}_{\text{w}}$=$\frac{1}{\sqrt{N}}[\boldsymbol{X}_{1}$-$\mathbf{μ}_{1}\boldsymbol{e}_{1}$, …, $\boldsymbol{X}_{c}$-$\mathbf{μ}_{c}\boldsymbol{e}_{c}$], $\boldsymbol{e}_{i}$=(1, …, 1)∈$\mathbf{R}^{1×N_{i}}$$\boldsymbol{W}^{\text{LDA}}_{\text{opt}}$可通过$\boldsymbol{S}^{-1}_{\text{w}}$ $\boldsymbol{S}_{\text{b}}$特征分解前$d$个最大特征值对应的特征向量得到。在LDA算法中, 若$\boldsymbol{S}_{\text{w}}$不可逆, 则$\boldsymbol{W}^{\text{LDA}}_{\text{opt}}$很难得到满意的降维效果, 此时, 需要对$\boldsymbol{S}_{\text{w}}$实施正则化操作。

MMC与LDA的想法不同, 但最终的技术类似。两个不同类的距离

$ d\left( {{\mathit{\boldsymbol{c}}_i},{\mathit{\boldsymbol{c}}_j}} \right) = d\left( {{\mathit{\boldsymbol{\mu }}_i},{\mathit{\boldsymbol{\mu }}_j}} \right) - \left( {S\left( {{\mathit{\boldsymbol{c}}_i}} \right) + S\left( {{\mathit{\boldsymbol{c}}_j}} \right)} \right), $ (1)

式中:$d$($\mathbf{μ}_{i}$, $\mathbf{μ}_{j}$)为$\mathbf{μ}_{i}$$\mathbf{μ}_{j}$之间的距离; $S$($\boldsymbol{c}_{i}$)和$S$($\boldsymbol{c}_{j}$)为不同类数据的离散度矩阵的迹。根据公式(1), MMC的低维基底$\boldsymbol{W}^{\text{MMC}}_{\text{opt}}$可通过如下最优化函数得到:

$ \mathit{\boldsymbol{W}}_{{\rm{opt}}}^{{\rm{MMC}}} = \mathop {\arg \max }\limits_\mathit{\boldsymbol{W}} {\rm{tr}}\left[ {\mathit{\boldsymbol{W}}\left( {{\mathit{\boldsymbol{S}}_{\rm{b}}} - {\mathit{\boldsymbol{S}}_{\rm{w}}}} \right){\mathit{\boldsymbol{W}}^{\rm{T}}}} \right], $

$\boldsymbol{W}^{\text{MMC}}_{\text{opt}}$可通过$\boldsymbol{S}_{b}$-$\boldsymbol{S}_{\text{w}}$特征分解前$d$个最大特征值对应的特征向量得到, 具体细节可参见文献[20]。

在以上两个算法的基础上, 为了增强监督降维算法的鲁棒性, 文献[22]提出ALDE方法, 其类内离散度最小, 最大类间离散度可表示为:$\max\limits_{\boldsymbol{W}}$[$\text{cos}^{2}β$+(1-$\text{cos}^{2}α$)]。令Co-Angle $α_{ij}$=$α_{ij}$($\boldsymbol{W}$)=〈$\boldsymbol{x}_{ij}$-$\mathbf{μ}_{i}$, $\boldsymbol{W}\boldsymbol{W}^{\text{T}}$($\boldsymbol{x}_{ij}$-$\mathbf{μ}_{i}$)〉, $β_{i}$=$β_{i}$($\boldsymbol{W}$)=〈$\mathbf{μ}_{i}$-$\mathbf{μ}$, $\boldsymbol{W}^{\text{T}}$($\mathbf{μ}_{i}$-$\mathbf{μ}$)〉, 其中, $i$=1, 2, …, $c$, $j$=1, 2, …, $N_{i}$。类内离散度可写为:

$ \sum\limits_{i = 1}^c {\left[ {\frac{{{N_i}}}{N}\frac{1}{{{N_i}}}\sum\limits_{j = 1}^{{N_i}} {\left( {1 - {{\cos }^2}{\alpha _{ij}}} \right)} } \right] = \frac{1}{N}\left[ {N - \sum\limits_{i = 1}^c {\sum\limits_{j = 1}^{{N_i}} {\frac{{{{\left( {{\mathit{\boldsymbol{x}}_{ij}} - {\mathit{\boldsymbol{\mu }}_i}} \right)}^{\rm{T}}}\mathit{\boldsymbol{W}}{\mathit{\boldsymbol{W}}^{\rm{T}}}\left( {{\mathit{\boldsymbol{x}}_{ij}} - {\mathit{\boldsymbol{\mu }}_i}} \right)}}{{\left\| {{\mathit{\boldsymbol{x}}_{ij}} - {\mathit{\boldsymbol{\mu }}_i}} \right\|_2^2}}} } } \right]} = {\rm{tr}}\left[ {{\mathit{\boldsymbol{W}}^{\rm{T}}}\left( {\frac{1}{d}\mathit{\boldsymbol{I}} - {{\mathit{\boldsymbol{S'}}}_w}} \right)\mathit{\boldsymbol{W}}} \right], $

式中:$\boldsymbol{S}^′{\text{w}}$=$\frac{1}{N}∑\limits^{c}_{i=1}∑\limits^{N_{i}}_{j=1}(\boldsymbol{x}_{ij}$-$\mathbf{μ}_{i}$)$_{e}$($\boldsymbol{x}_{ij}$-$\mathbf{μ}_{i}$)$^{\text{T}}_{e}$=$\boldsymbol{X}_{\text{we}}$($\boldsymbol{X}_{\text{we}}$)$^{\text{T}}$, $\boldsymbol{X}_{\text{we}}$=$\frac{1}{\sqrt{N}}[(\boldsymbol{x}_{11}$-$\mathbf{μ}_{1}$)$_{e}$, …, ($\boldsymbol{x}_{1N_{1}}$-$\mathbf{μ}_{1}$)$_{e}$, …, ($\boldsymbol{x}_{c1}$-$\mathbf{μ}_{c}$)$_{e}$, …, ($\boldsymbol{x}_{cN_{c}}$-$\mathbf{μ}_{c}$)$_{e}$]。

类间离散度可写为:

$ \sum\limits_{i = 1}^c {\left( {\frac{{{N_i}}}{N}{{\cos }^2}{\beta _i}} \right)} = \frac{{{N_i}}}{N}\sum\limits_{i = 1}^c {\frac{{{{\left( {{\mathit{\boldsymbol{\mu }}_i} - \mathit{\boldsymbol{\mu }}} \right)}^{\rm{T}}}\mathit{\boldsymbol{W}}{\mathit{\boldsymbol{W}}^{\rm{T}}}\left( {{\mathit{\boldsymbol{\mu }}_i} - \mathit{\boldsymbol{\mu }}} \right)}}{{\left\| {{\mathit{\boldsymbol{\mu }}_i} - \mathit{\boldsymbol{\mu }}} \right\|_2^2}}} = {\rm{tr}}\left[ {{\mathit{\boldsymbol{W}}^{\rm{T}}}{{\mathit{\boldsymbol{S'}}}_\text{b}}\mathit{\boldsymbol{W}}} \right], $

式中:$\boldsymbol{S}^′_{\text{b}}$=$\frac{1}{N}∑\limits^{c}_{i=1}N_{i}$($\mathbf{μ}_{i}$-$\mathbf{μ}$)$_{e}$($\mathbf{μ}_{i}$-$\mathbf{μ}$)$^{\text{T}}_{e}$=$\boldsymbol{X}_{\text{be}}$($\boldsymbol{X}_{\text{be}}$)$^{\text{T}}$, $\boldsymbol{X}_{\text{be}}$=$\frac{1}{\sqrt{N}}[\sqrt{N_{1}}(\mathbf{μ}_{1}$-$\mathbf{μ}$)$_{e}$, …, $\sqrt{N_{c}}$($\mathbf{μ}_{c}$-$\mathbf{μ}$)$_{e}$]。

根据$\max\limits_{\boldsymbol{W}}$[$\text{cos}^{2}β$+(1-$\text{cos}^{2}α$)]的结构, ALDE算法的优化函数

$ J\left( \mathit{\boldsymbol{W}} \right) = \sum\limits_{i = 1}^c {\frac{{{N_i}}}{N}\left[ {{{\cos }^2}{\beta _i} + \frac{1}{{{N_i}}}\sum\limits_{j = 1}^{{N_i}} {\left( {1 - {{\cos }^2}{\alpha _{ij}}} \right)} } \right]} = {\rm{tr}}\left[ {{\mathit{\boldsymbol{W}}^{\rm{T}}}\left( {\frac{1}{d}\mathit{\boldsymbol{I}} - {{\mathit{\boldsymbol{S'}}}_{\rm{w}}} + {{\mathit{\boldsymbol{S'}}}_{\rm{b}}}} \right)\mathit{\boldsymbol{W}}} \right], $

显然, $J$($\boldsymbol{W}$)的结构使ALDE算法自然避开小样本问题。因此, ALDE算法转化为解决一个约束的最优化问题:

$ \left\{ \begin{array}{l} \mathop {\max }\limits_\mathit{\boldsymbol{W}} {\rm{tr}}\left[ {{\mathit{\boldsymbol{W}}^{\rm{T}}}\mathit{\boldsymbol{MW}}} \right]\\ {\rm{s}}.{\rm{t}}.\;{\mathit{\boldsymbol{W}}^{\rm{T}}}\mathit{\boldsymbol{W}} = \mathit{\boldsymbol{I}} \end{array} \right., $

式中$\boldsymbol{M}=\frac{1}{d}\boldsymbol{I}$-$\boldsymbol{S}^′_{\text{w}}$+$\boldsymbol{S}^′_{\text{b}}$$\boldsymbol{W}^{\text{ALDE}}_{\text{opt}}$可通过$\boldsymbol{S}^′_{\text{b}}$-$\boldsymbol{S}^′_{\text{w}}$特征分解前$d$个最大特征值对应的特征向量得到, 具体细节可参见文献[22]。

1.2 SSE算法

由于优化函数的结构及边界决定了LDA及MMC带有倾向性的选择最优子空间, 因此希望提出一种监督的降维算法, 尽可能消除优化函数的结构及边界对最优子空间选择的影响, 同时, 远离点对整体数据的影响有较好的鲁棒性。本研究提出一种类内子空间深入学习的监督降维方法——相似子空间嵌入(SSE), 目的是对类内离散度矩阵进行深入学习, 得到每类的类内离散度子空间, 通过对所有类内离散度子空间的进一步学习, 获得信息更为丰富的类间离散度矩阵, 进而得到更好的低维空间。

根据LDA及MMC对类内离散度及类间离散度的定义, 对类内离散度进行再一次的充分学习。对任意的第$i$类离散度

$ \mathit{\boldsymbol{S}}_{\rm{w}}^i = \sum\limits_{j = 1}^{{N_i}} {\left( {{\mathit{\boldsymbol{x}}_{ij}} - {\mathit{\boldsymbol{\mu }}_i}} \right){{\left( {{\mathit{\boldsymbol{x}}_{ij}} - {\mathit{\boldsymbol{\mu }}_i}} \right)}^{\rm{T}}}} = \mathit{\boldsymbol{X}}_{\rm{w}}^i{\left( {\mathit{\boldsymbol{X}}_{\rm{w}}^i} \right)^{\rm{T}}}, $ (2)

式中$\boldsymbol{X}^{i}_{\text{w}}$=$\boldsymbol{X}_{i}$-$\mathbf{μ}_{i}\boldsymbol{e}_{i}$。根据该定义, 可对每类的类内离散度进行充分学习, 即求得矩阵$\boldsymbol{S}^{i}_{\text{w}}$$\bar{d}$个最小特征值对应的特征向量$\boldsymbol{U}_{i}$=[$u_{i1}$, …, $u_{i\bar{d}}$], 其中, $\bar{d}$=min{$d_{i}$}, $d_{i}$为第$i$类的类内离散度矩阵分解后所取的最小特征值的数量。根据以上分析, 类间离散度

$ {{\mathit{\boldsymbol{\bar S'}}}_{\rm{b}}} = \sum\limits_{i = 1}^c {\sum\limits_{j = i}^c {{\mathit{\boldsymbol{U}}_i}{{\left( {{\mathit{\boldsymbol{U}}_j}} \right)}^{\rm{T}}}} } 。$

这意味着通过对所有类内离散度子空间的进一步充分学习, 以获得信息更为丰富的类间离散度矩阵, 进而得到最优子空间。为计算可行性, 令$\bar{S}_{\text{b}}=\frac{\bar{S}^′_{\text{b}}+(\bar{S}^′_{\text{b}})^{\text{T}}}{2}$, 该表示避免了传统类间离散度矩阵信息量过小的问题。这里, $\boldsymbol{S}_{\text{b}}$仅含有$c$-1个非零特征值, 当类别量较小时, 类间的信息量不足以表示低维空间。

若利用LDA的思想, 则考虑$\boldsymbol{W}_{\text{opt}}$由优化函数比的形式得到, 约束条件为$\boldsymbol{W}^{\text{T}}\boldsymbol{W}$=$\boldsymbol{I}$。但这样的优化函数结构同样会面临小样本问题。因此, 利用MMC的减法结构, 构造SSE算法的优化函数

$ J\left( \mathit{\boldsymbol{W}} \right) = {\mathit{\boldsymbol{W}}^{\rm{T}}}\left( {{{\mathit{\boldsymbol{\bar S}}}_{\rm{b}}} - {\mathit{\boldsymbol{S}}_{\rm{w}}}} \right)\mathit{\boldsymbol{W}}, $

则SSE最终的子空间可通过如下优化函数表示:

$ \left\{ \begin{array}{l} \mathop {\max }\limits_\mathit{\boldsymbol{W}} {\rm{tr}}\left[ {{\mathit{\boldsymbol{W}}^{\rm{T}}}\mathit{\boldsymbol{\bar MW}}} \right]\\ {\rm{s}}.{\rm{t}}.\;{\mathit{\boldsymbol{W}}^{\rm{T}}}\mathit{\boldsymbol{W}} = \mathit{\boldsymbol{I}} \end{array} \right., $ (3)

式中$\bar{\boldsymbol{M}}=\bar{\boldsymbol{S}}_{\text{b}}$-$\boldsymbol{S}_{\text{w}}$。以上优化问题可通过引入$\boldsymbol{W}$拉格朗日函数解决:

$ L\left( {\mathit{\boldsymbol{W}},\lambda } \right) = {\rm{tr}}\left[ {{\mathit{\boldsymbol{W}}^{\rm{T}}}\mathit{\boldsymbol{\bar MW}}} \right] + \lambda \left( {\mathit{\boldsymbol{I}} - {\mathit{\boldsymbol{W}}^{\rm{T}}}\mathit{\boldsymbol{W}}} \right), $ (4)

使$L$($\boldsymbol{W}$, $λ$)达到最大值的$\boldsymbol{W}$可通过$L$($\boldsymbol{W}$, $λ$)对$\boldsymbol{W}$求偏导函数得到:

$ \frac{{\partial L}}{{\partial \mathit{\boldsymbol{W}}}} = 2\mathit{\boldsymbol{\bar MW}} - 2\lambda \mathit{\boldsymbol{W}} = 0。$

$\bar{\boldsymbol{M}}\boldsymbol{W}$=$λ\boldsymbol{W}$。SSE算法最优的低维子空间可通过$\bar{\boldsymbol{M}}$$d$个最大特征值$λ_{1}$$λ_{2}$…≥$λ_{d}$所对应的特征向量$\boldsymbol{w}_{1}$, …, $\boldsymbol{w}_{d}$给出。SSE算法如下:

算法1 相似子空间嵌入SSE算法
输入:原始高维数据$\boldsymbol{X}$;
输出:降维后的最优的低维子空间$\boldsymbol{W}$;
$\mathbf{Step}$ 1 初始类内离散度矩阵$\boldsymbol{S}_{\text{w}}$;
$\mathbf{Step}$ 2 根据式(2)计算矩阵$\boldsymbol{S}^{i}_{\text{w}}$$\bar{d}$个最小特征值对应的特征向量$\boldsymbol{U}_{i}$;
$\mathbf{Step}$ 3 利用$\boldsymbol{U}_{i}$计算类间离散度$\bar{S}_{\text{b}}$;
$\mathbf{Step}$ 4 通过优化问题(3)计算SSE最优的低维子空间$\boldsymbol{W}$

2 试验结果与分析

采用手工及真实数据集进行试验, 为了比较不同算法的性能, 试验中识别率均采用学习效果较好的极端学习机(ELM)分类器[23]。用于试验的电脑配置为2.66GHz CPU, 2GB内存, 操作系统为Windows XP sp3 32Bit, 安装Matlab 2011a软件用于试验。

2.1 图像识别试验

使用3组图像数据集AR、Coil-20和MNIST评估提出算法的性能。AR数据包含120余人(70男56女)4000余幅图像, 采用其子集进行试验:除去遮挡样本共包含120人的1680幅图像(每人14幅)。Coil-20数据库包含20个物体的1440幅灰度图像(每个物体72幅), 图像是由物体0~360°每水平旋转5°采集一次得到。MNIST手写体数字数据库是MNIST数据库的一个子集, 包含60000个训练样本和10000个测试样本。数据集的一些参数及试验设置见表 1

表 1 数据描述及实验设置 Table 1 Data description and experimental setup

试验中随机选取训练集和测试集样本, 在3个数据库中得到的训练集样本以及利用LDA[13]、MMC[20]、ALDE[22]和提出的SSE算法得到的识别率结果如图 1~3所示。

图 1 AR数据集试验结果 Figure 1 Experiment results of AR dataset
图 2 Coil-20数据集试验结果 Figure 2 Experiment results of Coil-20 dataset
图 3 MNIST数据集实验结果 Figure 3 Experiment results of MNIST dataset

不同算法在3组图像数据库中试验得到的最大识别率$R_{\text{max}}$、平均识别率$R_{\text{av}}$和平均运行时间结果, 如表 23所示。

表 2 不同图像数据集上的最大和平均识别率比较 Table 2 Comparison of maximum and average recognition rates on different image datasets
表 3 不同图像数据集上的平均运行时间比较 Table 3 Comparison of average run time on different image datasets
2.2 试验分析

图 1b)、2b)、3b)及表 2可以看出, SSE算法在3组试验下均可达到最优识别率。与LDA、ALDE和MMC相比, SSE充分学习了类内离散度, 因而可得到较高的识别率。

在Coil-20数据集中, Coil-20每类的类内离散度较小, 降维后, SSE(平均识别率99.75%)和ALDE(平均识别率99.79%)算法均可以获得比较好的低维子空间。因此, 在后续的分类识别工作中, SSE和ALDE获得了比MMC和LDA更高的识别率。此外, SSE对类内离散度进行了再学习, 因此SSE算法获得了最优的试验结果。SEE算法在运行时间上也有优势, 在Coil-20数据集上运行时间最短, 在其余两个数据集上的运行时间均位于第二位。

在AR数据集中, 数据的类内离散度分布并没有Coil-20数据集好, 人脸的类内方差也比人造物体复杂的多, 因此SSE取得了最优效果。而在MNIST数据集中, 手写体数据集的类间方差较复杂, 不同数字手写体有时会大不同, 有时也很相似, 而MMC、LDA及ALDE都不擅长处理这样的数据。SSE在构建类间离散度时有更多的类间信息, 因此, 可以取得最优的学习效果(平均识别率68.79%)。

3 结语

本研究提出一种相似子空间嵌入SSE算法, 利用数据每类的类内离散度提取数据的判别信息, 获得了更好的低维空间。在AR人脸图像、Coil数据集及手写体上的试验结果表明, 充分学习类内离散度对子空间选择是重要的, 在试验中采用其设置在大多数数据集下是有效的, 得到了更好的识别精度和运行速度。监督降维的子空间选择问题是一个值得深入研究的课题。

参考文献
[1] JOLLIFFE I T. Principal component analysis[M]. New York: Springer-Verlag, 1986.
[2] COX T, COX M. Multi-dimensional scaling[M]. London: Chapman & Hall, 1994.
[3] ROWEIS S T, SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290(5500): 2323-2326 DOI:10.1126/science.290.5500.2323
[4] ZHANG Z, ZHA H. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J]. SIAM Journal of Scientific Computing, 2004, 26(1): 313-338 DOI:10.1137/S1064827502419154
[5] HE X F, YAN S C, HU Y X, et al. Face recognition using Laplacian faces[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI), 2005, 27(3): 328-340 DOI:10.1109/TPAMI.2005.55
[6] HE X F, CAI D, YAN S C, et al. Neighborhood preserving embedding[C]// Proceedings of the 10th IEEE International Conference on Computer Vision (ICCV). Beijing, China: IEEE, 2005: 1208-1213.
[7] PANG Y W, ZHANG L, LIU Z K, et al. Neighborhood preserving projections (NPP): A novel linear dimension reduction method[C]// Proceedings of IEEE International Conference on Advances in Intelligent Computing. Hefei, China: ACM, 2005: 117-125.
[8] MIN W L, LU K, HE X F. Locality pursuit embedding[J]. Pattern Recognition, 2004, 37(4): 781-788 DOI:10.1016/j.patcog.2003.09.005
[9] SONG Y, CAI W, HUANG H, et al. Large margin local estimate with applications to medical image classification[J]. IEEE Transactions on Medical Imaging, 2015, 34(6): 1362-1377 DOI:10.1109/TMI.2015.2393954
[10] SCHROFF F, KALENICHENKO D, PHILBIN J. Facenet: a unified embedding for face recognition and clustering[C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Boston, USA: IEEE, 2015: 815-823.
[11] VALSESIA D, COLUCCIA G, BIANCHI T, et al. Compressed fingerprint matching and camera identification via random projections[J]. IEEE Transactions on Information Forensics and Security, 2015, 10(7): 1472-1485 DOI:10.1109/TIFS.2015.2415461
[12] NASSIRTOUSSI A K, AGHABOZORGI S, WAH T Y, et al. Text mining of news-headlines for FOREX market prediction: A multi-layer dimension reduction algorithm with semantics and sentiment[J]. Expert Systems with Applications, 2015, 42(1): 306-324 DOI:10.1016/j.eswa.2014.08.004
[13] BELHUNEUR P N, HESPANHA J, KRIEGMAN D J. Eigenfaces vs. fisherfaces: recognition using class specific linear projection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI), 1997, 19(7): 711-720 DOI:10.1109/34.598228
[14] FISHER R A. The use of multiple measurements in taxonomic problems[J]. Annual of Eugenics, 1936, 7(2): 179-188 DOI:10.1111/j.1469-1809.1936.tb02137.x
[15] RAO C R. The utilization of multiple measurements in problems of biological classification[J]. Journal of the Royal Statistical Society, 1948, 10(2): 159-203
[16] NA J H, PARK M S, CHOI J Y. Linear boundary discriminant analysis[J]. Pattern Recognition, 2010, 43(3): 929-936 DOI:10.1016/j.patcog.2009.09.015
[17] LOOG M, DUIN R P W, HAEB-UMBACH R. Multi-class linear dimension reduction by weighted pairwise fisher criteria[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI), 2001, 23(7): 762-766 DOI:10.1109/34.935849
[18] LI M, YUAN B Z. 2D-LDA: a statistical linear discriminant analysis for image matrix[J]. Pattern Recognition Letters, 2005, 26(5): 527-532 DOI:10.1016/j.patrec.2004.09.007
[19] WALD P, KRONMAL R. Discriminant functions when covariance are unequal and sample sizes are moderate[J]. Biometrics, 1977, 33(3): 479-484 DOI:10.2307/2529362
[20] LI H, JIANG T, ZHANG K. Efficient and robust feature extraction by maximum margin criterion[J]. IEEE Transactions on Neural Networks, 2006, 17(1): 157-165 DOI:10.1109/TNN.2005.860852
[21] YUN F, YAN S C, HUANG T S. Correlation metric for generalized feature extraction[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI), 2008, 30(12): 2229-2235 DOI:10.1109/TPAMI.2008.154
[22] LIU S L, FENG L, QIAO H. Scatter balance: an angle-based supervised dimensionality reduction[J]. IEEE Transactions on Neural Networks and Learning Systems, 2015, 26(2): 277-289 DOI:10.1109/TNNLS.2014.2314698
[23] LIU S L, FENG L, WANG H B, et al. Extend semi-supervised ELM and a frame work[J]. Neural Computing and Applications, 2016, 27(1): 205-213 DOI:10.1007/s00521-014-1713-y