摘  要  文章旨在研究数据分布未知的高维、 小样本问题的特征抽取算法. 基于支持向量机原理和特征统计不相关思想, 提出基于散度支持向量机(SSVM)的递归统计不相关特征抽取算法, 解决现有算法抽取特征之间存在相关性、算法受到样本分布影响等问题. 针对高维小样本问题, 使用 PCA 把 SSVM 优化问题变换到同构低维空间; 给出边界鉴别向量集的递归求取方法, 把模式高维特征投影到边界鉴别向量集, 实现了统计不相关特征的抽取; 分析了算法的收敛性和终止条件. 文中使用核方法把线性 SSVM 推广到非线性 SSVM, 通过 KPCA 方法把非线性 SSVM 优化问题转换到低维空间中的等价优化问题, 在低维空间抽取不相关非线性特征. 仿真结果证明了文中算法的有效性.

关键词  散度支持向量机(SSVM); 分类; 特征抽取; 统计不相关边界鉴别向量; 主元分析(PCA)

    1  引  言

特征抽取方法能够降低数据存储空间以及消除样本中冗余信息和噪声, 便于人们对数据进行分析和理解, 解决了因样本维数过高而导致分类器训练代价过大、 泛化性能低等问题[ 1 -3]. 常见的特征抽取算法有主元分析( PCA) 、 线性鉴别分析( LDA) 、 独立主元分析( ICA) 和基于支持向量机( SVM) 方法等 [ 2 -6] , 其中, LDA 和 SVM 在机器学习领域中引起了人们极大关注. LDA 能够求取反映样本集全局信息的鉴别向量, 具有较高的分类性能, 被认为是目前最为有效的特征抽取算法, LDA 及其改进算法的基本思想就是根据 Fisher 鉴别准则求取多个最佳鉴别向量, 然后再将模式高维特征向量投影到该最佳鉴别向量集上, 构成低维鉴别特征空间 [6] . 鉴于 LDA 算法不支持高维小样本数据以及 F -S LDA 算法抽取的特征分量之间存在统计相关等问题, 人们提出了很多改进算法, 如广义 LDA、 零子空间( Nul- l subspace)LDA、 基于广义SVD的LDA、 统计不相关LDA等 [ 6 -9] .然而 LDA 存在单类样本为高斯分布时才能取得最优解、 不能准确区分线性可分样本等问题[ 10 -11].SVM 是基于结构风险最小化原理的有监督分类方法, 具有支持小样本数据、 无需假定样本分布、计算量与维数无关等优点[ 5, 12]. 然而 SVM 只能抽取样本集局部信息, 存在超平面法线方向与样本分布不一致的问题, 影响了泛化性能的提高 [ 11] . 对二分类问题, SVM 超平面法向量与 LDA 最佳鉴别向量具有相同的物理意义.

基于上述考虑, 文献[ 4] 通过把样本高维特征投影到 SVM 分类超平面法线方向上, 构成一维特征空间, 取得了较好的分类性能;类似 F -S LDA 算法[ 6], 文献[ 5] 提出基于SVM 的递归提取正交边界鉴别向量方法, 其性能优于 SVM算法. 然而上述算法性能受到 SVM 性能和抽取特征之间存在相关性的影响. 其原因是: ( 1) SVM 只利用了样本集的局部信息, 影响了其泛化性能, 因此与常见的特征抽取算法相比, 文献[ 4] 算法性能并没有显著的提高. 理论分析和实验证明, 利用样本集全局信息能够有效提高SVM 的性能[ 11, 13]; ( 2) 基于统计不相关的鉴别向量集优于正交鉴别向量集的模式识别理论 [ 6 -7, 14] , 文献[ 5] 抽取的特征之间存在相关性, 影响了算法性能的提高.基于上述分析, 本文提出基于散度支持向量机( Scatter Support Vector Machine, SSVM) 的统计不相关特征抽取算法. 首先提出了SSVM, 该方法实现了SVM 与 LDA 之间的折中, 保证了 SSVM 性能的优越性; 给出基于 SSVM 的递归抽取统计不相关边界鉴别向量集算法, 证明了算法的收敛性结论以及算法终止条件; 并通过核方法把线性抽取算法推广到非线性抽取算法.

本文算法继承了 SVM 和 LDA 的优点, 通过使用 PCA/ KPCA 把高维空间的 SSVM优化问题变换到同构低维空间中等价优化问题, 解决了小样本情况下 SSVM 优化问题求解的问题, 有效地克服现有算法的缺点. 使用 UCI 数据集和XM2VT S 人脸图像进行了仿真实验, 结果说明本文算法是可行有效的. 下面首先介绍 SSVM 原理.

2  散度支持向量机( SSVM)

LDA 通过如下形式的 Fisher 准则求取鉴别向量, 即maxww T S b ww T S w w(1)其中, S b 和 S w 分别为类间、 类内散度矩阵. 设样本总体散度矩阵为 S t , 满足关系: S t = S b + S w ; w为鉴别向量. 上面优化问题具有如下等价形式 [ 15] :maxw, bwTS b ww T S t w(2)由于 LDA 充分利用样本集全局信息以及类别信息, 鉴别向量方向与样本分布一致. 受 LDA 和文献[ 16] 启发, 文献[ 11] 提出 MCSVM ( MinimumClass variance, SVM) , 其优化问题通过 w T S w w代替SVM 优化问题 wTw项得到. MCSVM 考虑了样本集局部和全局信息, 实现 FLDA 与 SVM 之间的折衷, 具有更 优的分 类性 能 [ 11] . 对 两类样 本集{( x j , y j )}Nj= 1 , x j = [ x j 1 , x j2 , ,, x j d ]T ; y jI { - 1,+ 1}, 假设分类超平面模型具有如下形式:y= wTx+ b.受文献[ 11, 13] 的启发, 本文通过求解如下改进SVM 优化问题 P 1 得到 w和b 的最优解, 即P 1 : minw, b, Nj12w T S t w+ CENj = 1N js. t.y j (w T x j + b) E1- N jN j E 0, j = 1, 2, ,, N(3)这里, N 1 , N 2 , ,, N N 是非负松弛变量; C 为误差惩罚因子; S t =1NENj = 1x j - m x j - mT为样本总体散度矩阵, 需要满足 wTS t w> 0. 从上式可以看出, 优化问题P 1 就是使用 w T S t w代替传统SVM 优化问题的w T w,且满足约束条件 wTS t w> 0. 由于式(1)和(2)所示优化问题的等价关系, 优化问题 P 1 表示的改进 SVM具有与 MCSVM 类似特性, 因而 在理论上保证SSVM 具有更优的分类性能. 由于 S t 为样本集的总体散度矩阵, 代表样本的全局信息, 因此, 本文把这种改进的 SVM 称作散度支持向量机( SSVM) .根据式(3) 所示优化问题 P 1 的目标函数和约束条件构造 Lagrange 方程, 即L= minw, b, Aj , B j12wTS t w+ C ENj = 1N j -ENj = 1A j (y j ( wTi x j + b i )- 1+ N j )-ENi= 1B j N j ( 4)其中, A j 和 B j ( j = 1, 2, ,, N ) 是 Lagrange 乘子.式(4)对 w, b, A j , B j 求导并等于 0 得9L9w = St w-ENj = 1A j y j x j = 0 ( 5)9L9b=ENj = 1A j y j = 0 ( 6)9L9N j= C- A j - B j = 0 ( 7)把式(5)~ (7)代入优化问题 P 1 , 根据 KKT 条件, 优化问题 P 1 转换为如下形式, 即P 2 : maxAjL = ENj = 1A j -12 ENj = 1ENK = 1 yj y K A j A k xTj S- 1t x ks. t.0FA j FC, j= 1, 2, ,, NENj = 1A j y j = 0( 8)对于 SSVM, 其决策函数为g(x)= sign(wTx+ b)= sign12 ENj = 1a j y j xTj S- 1t x+ b .根据 KKT 条件, 支持向量 x k 其对应的a k X 0,N k = 0. 设支持向量集为 SV, 对支持向量 x k I SV有下式成立:y k12 ENj = 1y j a j x T j S- 1t x k + b = 1,那么 b 的最优值可由下式求取, 即b=1SVEx k I SVy k -12ENj = 1y j a j xTj S- 1t x k .需要注意的是, 对于高维小样本数据集, 即样本数据维数 d E N, S t 是往往是奇异的, 这样就不能直接通过优化问题 P 1 求取向量 w i 的最优解. 然而, 对于高维小样本数据集, 在第 3 节将证明, 通过 PCA对数据集进行维数约简, 把优化问题 P 1 转换为低维空间上等价的优化问题, 从而求取 SSVM 的最优解. 下面讨论小样本情况下的 SSVM 优化问题求解问题.

3  小样本情况下 SSVM 的求解

由函数分析理论可知, S t 在空间 R d 是有界、 紧的、 正定的算子, 根据 Hilbert -Schmidt 定理, 矩阵 S t的特征向量是 Rd上的正交基[ 17]. 令 D 表示 S t 非零特征值对应特征向量张成的空间, D L 表示 S t 的零特征值对应特征向量张成的空间, 则空间D L 表示空间D 的补空间. 因此, 对任意向量wI R d 可以表示为 [ 16]w= v+ V, vI D, V I D L (9)定义映射 L: R d yD, 对任意的 wI Rd , 均存在唯一的映射 v 使得下式成立, 即v= L w (10)这样, 映射 L 把优化问题 P 1 从空间 Rd转换为低维空间D 的优化问题 P 3 . 很显然, 如果优化问题 P 1 和P 3 等价, 那么对高维空间 P 1 的求解就转化为对低维空间D 上P 3 进行求解, 解决了小样本情况下因 S t 奇异而导致的 SSVM 难以求解的问题. 定理 1 给出优化问题 P 1 等价于 P 3 的结论.定理 1.  设 S t 为奇异散度矩阵, 设 D 和D L 分别表示 S t 非零、 零特征值对应特征向量张成的空间, 那么空间 R d 上的优化问题 P 1 等价于如下所示空间 D 上的优化问题 P 3 , 即P 3 : minv, b, Fj12vTS t v+ C ENj = 1 Njs. t.y j (v T x j + b) E 1- N jN j E 0, j= 1, 2, ,, Nv i I D(11)其中, v T S t v> 0.证明.  根据式(9), 对任意 wI R d 可以表示为w= v+ V , v I D, V I D L .根据函数理论 [ 17] , 显然有下式成立, 即vTS t v> 0, VTS t V= 0, vTS t V= 0.因此有w T S t w= v+ VT S tv+ V = v T S t v (12)则式(4)所示的 Lagrange 方程转化为L = minw i , b, A j , Bj12w T S t w+ CENj = 1N j -ENj = 1A j y j w T x j + b - 1+ N j -ENj = 1B j N j= v T S t v+ CENj = 1N j -ENj = 1B j N j - ENj = 1A j y j vTx j + VTi x j + b - 1+ N j (13)如果对 V I Rd 有 V T S tV= 0 成立, 那么对任意不同样本 x j , x k 均有 V T x j = V T x k 成立, 即所有样本在 V 上的投影均为常数. 令 c= VTx j , Pj, 则有下式成立:ENj = 1A j y j VTx j = c ENj = 1A j y j = 0 (14)根据上式, 式(13)可以写为L= minw, b, Aj, B j12vTS t v+ C ENj = 1N j -ENj = 1A j (y j ( vTx j + b)- 1+ N j )-ENj = 1B j N j (15)从式(14)可以看出, 上式与优化问题 P 3 对应的Lagrange 方程完全一致, 而式(14)表示的 Lagrange方程又与优化问题 P 1 等价. 因此, 优化问题 P 3 与优化问题 P 1 是等价的. 证毕.令 S t 非零特征值对应的特征向量作为变换矩阵 P, 且特征向量的数目 K Fd- 1. 在很多情况下,可以假定训练样本是独立、 同分布的, 此时K = d-1. 由于 P 的列向量是空间Rd 的正交基, 变换矩阵 P就是空间D 到RK的一对一映射, 根据函数分析理论, 在 PCA 变换矩阵 P 下空间 D 与 RK同构 [ 17] ,即 v= Pu, u I R K (16)根据式(16)、 式(11) 所示的优化问题 P 3 可以转换为如下所示的等价优化问题 P 4 , 即P 4 : minv, b, F12uT‰ S t u+ C ENj = 1N j , uT‰ S t u> 0s. t.y j (u T x~j + b) E1- N jN j E0, j = 1, 2, ,, Nu I R d- 1(17)其中, ‰ S t = P T S t P; x~j = P T x j 为样本x j 在 PCA 变换矩阵上的投影, 且 x~j I R N - 1 .类似第 3节, 优化问题 P 4 的对偶问题为P 5 : maxa j-12 ENj = 1ENk = 1a j a k y j y k x~ Tj ‰ S- 1t x~k +ENj = 1a js. t.ENj = 1a j y j = 00Fa j FC, j = 1, 2, ,, N(18)根据上面的讨论, 对小样本问题, 为求出优化问题 P 1 的最优解, 首先把样本通过 PCA 变换矩阵 P映射到空间 RK上, 然后在低维特征空间 RK中求取优化问题的最优解. 然而, 如何在空间 R K 求取统计不相关的边界鉴别向量集以及算法是否收敛, 是本文需要研究的关键问题. 下节给出算法实现以及收敛性分析.

4  递归统计不相关特征抽取算法分析

4. 1  算法的实现设训练样本集{( x i , y i ) }Ni= 1 , x i I Rd, y i I {- 1,1} , SSVM 的分类超平面为 y= w T 1 x+ b 1 . 分类超平面法向量 w 1 包含了样本类别边界信息, 具有区分不同类别数据的能力. 对二分类样本, w 1 与 LDA 鉴别向量具有相同的物理意义, 因此, 本文把 w 1 称作边界鉴别向量. 设 w 1 为规格化向量, 即 w 1 = 1, 样本(x i , y i )在向量 w 1 方向上的投影为y ^ i = w T 1 x i (19)对上式左边同乘 w 1 可得y ^ i C w 1 y ^ i = w 1 wT1 x i (20)很显然, w 1 w T 1 x i 为在向量 w 1 方向上对 x i 的逼近. 根据 PCA 理论, 假设在向量 w 1 方向上样本集 X的逼近X ^ 构成空间S W 1 , 样本集 X 与逼近X ^ 之间的误差 Ž X 构成残差空间 S r , 满足下面等式:X= X ^ + Ž X,它们之间的几何关系如图 1 所示.图 1  X、 逼近 X ^ 和残差 Ž X 的几何关系令 w 1 w T 1 = I+ I w 1 , I 是 d @ d 单位矩阵, I w 1 是非零矩阵, 那么式(20)可写为x ^ i = w 1 w T 1 x i = x i + I T w 1 x i (21)根据图 1 所示, 样本 x i 与逼近 x ^ i 及其误差x~i 之间满足如下关系, 即x i = x ^ i + x~i (22)根据式(21)、 (22) , x~i 重新写为如下形式:x~i = I- w 1 w T 1 x i (23)根据训练样本{( x~i , y i )}Ni = 1 , 使用 SSVM 算法可求取边界鉴别向量 w 2 ; 然后根据式( 23) 递归求取边界鉴别向量 w 3 , w 4 , ,, w l ; 最后把空间 R d 模式高维特征投影到边界鉴别向量集{ w 1 , w 2 , ,, w l }上, 构成低维特征空间 R l . 在定理 2 给出低维空间中的特征之间是否存在相关性的结论.定理 2.  对训练样本集{(x k , y k )}Nk= 1 , x k I R d ,y k I {- 1, 1}, 基于上述方法使用 SSVM 递归求取边界鉴别向量 w 1 , w 2 , ,, w l , 且 w i = 1, i = 1,2, ,, l. 对任意两个边界鉴别向量 w i , w j , 样本 X=[ x 1 , x 2 , ,, x N ] 在 w i , w j 方向上投影得到的特征是不相关的, 即cov w T i X, w T j X = w T i S t w j = 0, i, j = 1, 2, ,, l, i X j(24)证明.  根据训练样本集, 由 SSVM 算法求取的 w 1 作为第 1 个边界鉴别向量. 根据式(23), x k 在w 1 方向上逼近残差为x~ 1k = I- w 1 wT1 x k (25)对残差样本集{ (x~ 1k , y k )}Nk= 1 , 使用 SSVM 算法求取 w 2 作为第 2 个边界鉴别向量. 然后基于式(25)递归求取边界鉴别向量 w 1 , w 2 , ,, w l , w i = 1, i=1, 2, ,, l. 对式(25)左边乘以 w T 1 , 有下面等式成立:w T 1 x~ 1k = wT1 I- w 1 wT1 x k = 0 (26)即 w 1 正交于样本残差空间. 根据式(5) 可知, w 2 =S - 1 tENk = 1A k y k x~ 1k , 对w 2 上式左边乘以w T 1 S t 并根据式(26)可得wT1 S t w 2 = wT1 S t S- 1tENk= 1a~2k x~ 1k = 0.对任意的 w i , w j , i Xj , i, j= 1, 2, ,, l, 同理可证明有下式成立:w T i S t w j = 0. 证毕.定理 2 证明了本文算法能够从样本集抽取统计不相关的特征,综合以上所述, 本文给出如下递归统计不相关特征抽取算法实现步骤:假设有 N 个训练样本{ (x j , y j )}Nj = 1 I Rd@ R,其中 d 是输入数据的维数, 根据 SSVM 原理, 本文提出的算法实现步骤如下:1. 初始化. 给出算法终止条件, 迭代次数 r= 1, 令 w r 表示迭代计算得到的边界鉴别向量.2. 确定本文 SSVM 模型参数. 基于第 2 节 SSVM 算法, 使用交叉校验方法确定 SSVM 的模型参数, 根据上述样本训练 SSVM , 并把求取得到的超平面法向量 w作为第 1 个边界鉴别向量 w r ; r z r+ 1.3. 求取边界鉴别向量w r . 使用式 x~ ri = ( I- w 1 wT1 ) x~ r - 1i计算逼近 残差样本集 {( x~ rj , y j )}Nj= 1 , 根据 残差样 本集对SSVM 优化问题求解, 把求取的超平面法向量作为第 r 个边界鉴别向量w r . 成低维特征空间 R l . 在定理 2 给出低维空间中的特征之间是否存在相关性的结论.定理 2.  对训练样本集{(x k , y k )}Nk= 1 , x k I R d ,y k I {- 1, 1}, 基于上述方法使用 SSVM 递归求取边界鉴别向量 w 1 , w 2 , ,, w l , 且 w i = 1, i = 1,2, ,, l. 对任意两个边界鉴别向量 w i , w j , 样本 X=[ x 1 , x 2 , ,, x N ] 在 w i , w j 方向上投影得到的特征是不相关的, 即cov w T i X, w T j X = w T i S t w j = 0, i, j = 1, 2, ,, l, i X j(24)证明.  根据训练样本集, 由 SSVM 算法求取的 w 1 作为第 1 个边界鉴别向量. 根据式(23), x k 在w 1 方向上逼近残差为x~ 1k = I- w 1 wT1 x k (25)对残差样本集{ (x~ 1k , y k )}Nk= 1 , 使用 SSVM 算法求取 w 2 作为第 2 个边界鉴别向量. 然后基于式(25)递归求取边界鉴别向量 w 1 , w 2 , ,, w l , w i = 1, i=1, 2, ,, l. 对式(25)左边乘以 w T 1 , 有下面等式成立:w T 1 x~ 1k = wT1 I- w 1 wT1 x k = 0 (26)即 w 1 正交于样本残差空间. 根据式(5) 可知, w 2 =S - 1 tENk = 1A k y k x~ 1k , 对w 2 上式左边乘以w T 1 S t 并根据式(26)可得wT1 S t w 2 = wT1 S t S- 1tENk= 1a~2k x~ 1k = 0.对任意的 w i , w j , i Xj , i, j= 1, 2, ,, l, 同理可证明有下式成立:w T i S t w j = 0. 证毕.定理 2 证明了本文算法能够从样本集抽取统计不相关的特征,综合以上所述, 本文给出如下递归统计不相关特征抽取算法实现步骤:假设有 N 个训练样本{ (x j , y j )}Nj = 1 I Rd@ R,其中 d 是输入数据的维数, 根据 SSVM 原理, 本文提出的算法实现步骤如下:1. 初始化. 给出算法终止条件, 迭代次数 r= 1, 令 w r 表示迭代计算得到的边界鉴别向量.2. 确定本文 SSVM 模型参数. 基于第 2 节 SSVM 算法, 使用交叉校验方法确定 SSVM 的模型参数, 根据上述样本训练 SSVM , 并把求取得到的超平面法向量 w作为第 1 个边界鉴别向量 w r ; r z r+ 1.3. 求取边界鉴别向量w r . 使用式 x~ ri = ( I- w 1 wT1 ) x~ r - 1i计算逼近 残差样本集 {( x~ rj , y j )}Nj= 1 , 根据 残差样 本集对SSVM 优化问题求解, 把求取的超平面法向量作为第 r 个边界鉴别向量w r . 而对样本集{(xli , y i )}Ni = 1 不满足约束条件, 因此下式成立:12w T l - 1 S t w l - 1 + C ENj = 1 Nl - 1j F12w T l S t w l + C ENj = 1Nlj .上式表明, 随着抽取特征数量 l 的递增, 结构风险也随之增加, 边界鉴别向量 w l 包含的分类信息也减少, 算法逐渐收敛. 证毕.定理 3 虽然给出了算法的收敛性结论, 但不能直接作为算法终止条件. 定理 4 给出算法终止的条件.定理 4.  对本文递归不相关特征抽取算法, 设每次使用的训练样本集为{ (xli , y i )}Ni = 1 , 其中, l= 1,2, ,, m 为抽取特征的数量, 有如下关系成立:xli2 <x l - 1 i2(31)对PE > 0, 必存在一个正整数m 使得下式成立:maxix m i FE (32)证明.  根据式(28) 有下式成立:xl - 1i2 -xli2= wTl- 1 xl - 1i2 > 0,即 x l i2 <x l - 1 i2 , 可以看出 x li 随着 l 的增大而单调递减.注意到 x i = x1i , 根据 SSVM 算法可知w 1 = S- 1tENj = 1A j y j x j .由于 S- 1t 是常数矩阵, 那么 w 1 I S= sp an{ x11 ,x 1 2 , ,, x 1 N }. 从式( 28)可知:x 2 i = I- w 1 w T 1 x i ,很显然 x2i I S, i= 1, 2, ,, N. 同理可以证明 w 2 I S.由于 S 是有限维空间, 一定存在一个正整数 m使得下式成立:xmi2= x i2 -Em- 1j = 1wTj x i2 = 0.显然, 上式等价于式(32). 很明显, 式(32) 成立时, 根据本节的分析可知, 算法是收敛的. 证毕.本文提出 3 种算法终止条件: ( 1) 确定抽取的特征数量. 该方法难以确定合适的特征数量; (2) 根据定理 4, 设定阈值 E> 0, 当 maxi= 1, 2, ,, Nx~ li < E时算法终止, 其中, x~ li 为第l - 1 次递归计算后求取的样本残差; (3) 基于分类精度不会随着统计不相关特征增加而下降的原理[ 5], 首先设定分类精度变化阈值H spe , 分类精度变换小于阈值 H sp e 时算法终止, 避免了抽取太多特征付出计算代价太大的问题.

5  非线性特征抽取算法

对大量的非线性模式数据, 需要把上述线性特征抽取算法推广到非线性特征抽取算法. 本文首先通过核方法把上面线性 SSVM 推广到非线性 SSVM,然后基于非线性 SSVM 递归抽取特征. 首先把上面训练样本{( x i , y i )}Ni= 1 映射到 Hilbert 空间{(<( x i ),y i )}Ni= 1 , 其中<(#): RdyH 为高维非线性映射, H空间表示 Hilbert 空间, 满足 关系 <( x i )T<( x j )=K H (x i , x j ) , K H ( x i , x j ) 为满足 Mercer 条件的核函数. 在 ' 空间内散度函数定义为S < t =1NENi = 1(<(x i )- m)( <( x i ) - m)T ,其中, m=1NENj = 1< x j 是总体样本的均值.在 H 空间内, SSVM 的优化问题具有如下形式, 即P 6 : minw i , b i , N j12w T S < t w+ C ENj = 1N j , w T S < t w> 0s.t.y j (w T <( x j )+ b) E 1- N jN j E0, j = 1, 2, ,, N(33)众所周知, ' 空间的维数很高, S < t 几乎总是奇异的, 不能满足条件 wTi S<t w i > 0, 因此无法由优化问题P 6 直接求取 w的最优解. 由于 S<t 是 H 空间中的有界、 正定紧的自伴算子, 根据 Hilbert-Schmidt 定理[ 17], S<t 的特征向量组成 H 空间的正交基. 令 D< 、D<L 分别为 S<t 非零、 零特征值对应特征向量张成的互补空间, 那么 ' 空间的向量w 可以表示为w= u+ v, uI D< , vI D <L (34)类似定理 2, 可以证明, 线性 SSVM 优化问题P 6 可以转化为空间 D < 的等价优化问题. 设 S < t 的非零特征向量的数目为 K, 且 K FN- 1, 那么 D< 的维数也为 K . 根据函数分析理论, D < 与欧氏空间 R K 同构, 存在同构映射u i = Pq i , q i I RN - 1(35)其中, 变换矩阵 P 的列向量由 S < t 的非零特征向量组成. 优化问题 P 6 转化到 RK等价优化问题 P 7 , 即P 7 : minw, b, Nj12q T S)t q+ C ENj = 1N j , q T S)t q> 0, qI R Ks.t.y j q T z j + b E1- N jN j E0, j = 1, 2, ,, N(36)这里, S)t = P T S<t P; z j = P T < x j 是通过 KPCA 变换矩阵把 < x j 投影到RK, 有关 KPCA 的详细介绍可参考文献[ 18] . 这样对非线性 SSVM 优化问题 P 6 的求解问题可转化为如式(36)所示 R K 中优化问题 P 7进行求解. 由于S)<t 非奇异, 最优分类超平面法向量为征抽取算法推广到非线性特征抽取算法. 本文首先通过核方法把上面线性 SSVM 推广到非线性 SSVM,然后基于非线性 SSVM 递归抽取特征. 首先把上面训练样本{( x i , y i )}Ni= 1 映射到 Hilbert 空间{(<( x i ),y i )}Ni= 1 , 其中<(#): RdyH 为高维非线性映射, H空间表示 Hilbert 空间, 满足 关系 <( x i )T<( x j )=K H (x i , x j ) , K H ( x i , x j ) 为满足 Mercer 条件的核函数. 在 ' 空间内散度函数定义为S < t =1NENi = 1(<(x i )- m)( <( x i ) - m)T ,其中, m=1NENj = 1< x j 是总体样本的均值.在 H 空间内, SSVM 的优化问题具有如下形式, 即P 6 : minw i , b i , N j12w T S < t w+ C ENj = 1N j , w T S < t w> 0s.t.y j (w T <( x j )+ b) E 1- N jN j E0, j = 1, 2, ,, N(33)众所周知, ' 空间的维数很高, S < t 几乎总是奇异的, 不能满足条件 wTi S<t w i > 0, 因此无法由优化问题P 6 直接求取 w的最优解. 由于 S<t 是 H 空间中的有界、 正定紧的自伴算子, 根据 Hilbert-Schmidt 定理[ 17], S<t 的特征向量组成 H 空间的正交基. 令 D< 、D<L 分别为 S<t 非零、 零特征值对应特征向量张成的互补空间, 那么 ' 空间的向量w 可以表示为w= u+ v, uI D< , vI D <L (34)类似定理 2, 可以证明, 线性 SSVM 优化问题P 6 可以转化为空间 D < 的等价优化问题. 设 S < t 的非零特征向量的数目为 K, 且 K FN- 1, 那么 D< 的维数也为 K . 根据函数分析理论, D < 与欧氏空间 R K 同构, 存在同构映射u i = Pq i , q i I RN - 1(35)其中, 变换矩阵 P 的列向量由 S < t 的非零特征向量组成. 优化问题 P 6 转化到 RK等价优化问题 P 7 , 即P 7 : minw, b, Nj12q T S)t q+ C ENj = 1N j , q T S)t q> 0, qI R Ks.t.y j q T z j + b E1- N jN j E0, j = 1, 2, ,, N(36)这里, S)t = P T S<t P; z j = P T < x j 是通过 KPCA 变换矩阵把 < x j 投影到RK, 有关 KPCA 的详细介绍可参考文献[ 18] . 这样对非线性 SSVM 优化问题 P 6 的求解问题可转化为如式(36)所示 R K 中优化问题 P 7进行求解. 由于S)<t 非奇异, 最优分类超平面法向量为332个样本, 非正常情况包括性能超过平均值的正常情况、 低输入的正常情况、 二沉池故、 暴雨以及固体溶度过负荷, 分别对应的样本数量为 116、 65、 7、3、 4. UCI 数据集统计特性如表 1 所示. XM2VT S数据库共有 2360 幅图像, 其中 1518 幅人脸图像有镜片, 842 幅无镜片. 人脸图像的分辨率 720 @ 576,每个图像被旋转和缩放, 使得所有眼睛中心放置在特定像素上, 然后修剪为 85 @ 156, 通过直方图均衡化技术把图像强度规格化到均值为 0、 方差为 1, 部分图像如图4 所示. 实验中, 如果某个人出现在训练样本集中, 则从测试数据中剔除此人图片. 所有算法采用高斯核函数, 使用交叉验证法确定 SVM、 RSSVM以及SSVM 正则化参数 R和C, KRDA 与 KFDA 参数确定方法参考文献[ 20] . 实验中, UCI 数据集所有的数据属性被规格化为[ - 1, 1] , 在低维特征空间中使用最近邻分类器估计精度. 样本选取方法同上,测试样本的平均精度如表 2 所示. 从表 2 可以看出, 本文算法明显优于 SVM、RSVM 和 KFDA 算法, 对绝大部分数据集优于KRDA 算法, 只有个别数据集分类精度低于 KRDA算法. 出现上述现象的原因是, 一方面 SSVM 具有类似 MCSVM 的特点, 因而具有更高的分类性能;其次, 本文算法抽取的特征之间不存在冗余信息, 可以有效提高分类样本精度.

7  结  语

本文提出了一种基于 SSVM 的递归统计不相关特征抽取算法, 基于核方法把线性特征抽取方法推广到非线性特征抽取, 通过 PCA/ KPCA 变换解决了高维特征空间中因散度矩阵奇异性导致 SSVM优化问题无法求解的问题, 证明了算法的收敛性以及抽取的特征具有统计不相关性, 给出了算法终止条件. 文中还给出了递归非线性特征抽取算法的实现方法. 本文给出的线性、 非线性特征抽取方法能够抽取不相关特征, 有效地提高分类器的性能, 克服了现有算法存在的问题, 具有重要的理论和应用价值.需要指出的是, 本文算法计算代价较大, 如何使用现有的快捷优化算法, 提高算法的速度, 对于算法的实际应用具有重要的意义.

参 考 文 献[ 1] Li Junhong, Cui Peiling. Improved kernel fisher discriminantanalysis for fault diagnosis. Expert Systems with Applica -tions, 2009, 36: 1423 -1432 [ 2] Yang J, Frangi A F, Zhang D, Jin Z. KPCA plus LDA: Acomplete kernel Fisher discriminant framework for featureextraction and recognition. IEEE T ransactions on PatternAnalysis and Machine Intelligence, 2005, 27( 2) : 230 - 244[ 3] Sergios T heodorridis, Konstantinos Koutroumbas. PatternRecognition. 3rd Edition. Beijing: Publishing House of Elec -tronic Industry, 2006[ 4] Ying Z- i Lu, Tang Jing - Hai, Li Jing-Wen, Zhang You -Wei.Support vector discriminant analysis and it s application to fa -cial expression recognition. Acta Electronica Sinica, 2008,36( 4) : 725 -730( in Chinese)( 应自炉, 唐京海, 李景文, 张有为. 支持向量鉴别分析及在人脸表情识别中的应用. 电子学报, 2008, 36( 4) : 725 -730)[ 5] Qing Tao, Chu Dejun, Wang Jue. Recursive support vectormachines for dimensionality reduction. IEEE Transactions onNeural Networks, 2008, 19( 1) : 189 -193[ 6] Yang Jing -Yu, Jin Zhong, Hu Zhong -Shan. A theorem ondimensionality of the uncorrelated optimal discriminant fea -ture space. Chinese Journal of Computers, 2003, 26 ( 1) :110 - 115( in Chinese)( 杨静宇, 金忠, 胡钟山. 具有统计不相关性的最佳鉴别特征空间的维数定理. 计算机学报, 2003, 26( 1) : 110 -115)[ 7] Ye Jieping, Janardan Ravi, Qi Li et al. Feature reduction viageneralized uncorrelated linear discriminant analysis. IEEET ransactions on Knowledge and Data Engineering, 2006, 18( 10) : 1312 -1322[ 8] Xiong J, Ye T. Computational and theoretical analysis ofnull space and orthogonal linear discriminant analysis. Jour -nal of Machine Learning Research, 2006, 7: 1183 -1204[ 9] Howland P, Park H. Generalizing discriminant analysisusing the generalized singular value decomposition. IEEET ransactions on Pattern Analysis and Machine Intelligence,2004, 26( 8): 995 - 1006 [ 10] Ye Jieping. L east squares linear discriminant analysis/ / Pro-ceedings of the 24th International Conference on MachineLearning, 2007: 1087 -1093[ 11] Stefanos Zafeiriou, Anastasios T efas, Ioannis Pitas. Min- imum class variance support vector machines. IEEE Transac -tions on Imag e Processing, 2007, 16( 10) : 2551 -2564[ 12] Widodo Achmad, Yang Bo -Su. Support vector machine inmachine condition monitoring and fault diagnosis. MechanicalSystems and Signal Processing, 2007, 21: 2560 -2574[ 13] Huang Kaizhu, Yang Haiqin, King Irwin et al. Max- i Minmargin machine: Learning large margin classifiers locally andglobally. IEEE T ransactions on Neural Networks, 2008, 19( 2): 260 - 272[ 14] Jin Zhong, Yang Jingyu, Hu Zhongshan. Face recognitionbased on the uncorrelated discriminant transformation. Pat-tern Recognition, 2001, 34: 1405 -1416[ 15] Liu K, Yang J Y et al. An efficient algorithm for Foley -sammon optimal set of discriminant vectors by alg ebranic method. International Journal of Pattern Recognition andArtificial Intelligence, 1992, 6( 5) : 817 -829[ 16] Cevikalp H, Neamtu M, Wilkes M Barkana et al. Discrim- inative common vectors for face recognition. IEEE T ransac -tions on Pattern Analysis and Machine Intelligence, 2005,27( 1) : 4 -13[ 17] Kreyszig E. Introductory Functional Analysis with Applica -tions. New York: Wiley, 1978[ 18] Smola A J. Learning with kernels [ Ph. D. dissertation] .Berlin, Germany: Technischen U niversitsit¾t, 1998[ 19] Moghaddam B, Yang Ming - Hsuan. Learning gender withsupport faces. IEEE Transactions on Pattern Analysis andMachine Intelligence, 2002, 24( 5) : 707 -711[ 20] Ji Shuiwang, Ye Jieping. Kernel uncorrelated and regularizeddiscriminant analysis: A theoretical and computational study.IEEE Transactions on Knowledge and Data Engineering,2008, 20( 10) : 1131 - 1142