-
摘要: 主成分分析(Principal component analysis, PCA) 是处理高维数据的重要方法. 近年来, 基于各种范数的PCA模型得到广泛研究, 用以提高PCA对噪声的鲁棒性. 但是这些算法一方面没有考虑重建误差和投影数据描述方差之间的关系; 另一方面也缺少确定样本点可靠性(不确定性)的度量机制. 针对这些问题, 本文提出一种新的鲁棒PCA模型. 首先采用$L_{2, p}$模来度量重建误差和投影数据的描述方差. 基于重建误差和描述方差之间的关系建立自适应概率误差极小化模型, 据此计算主成分对于数据描述的不确定性, 进而提出了鲁棒自适应概率加权PCA模型(RPCA-PW). 此外, 本文还设计了对应的求解优化方案. 对人工数据集、UCI数据集和人脸数据库的实验结果表明, RPCA-PW在整体上优于其他PCA算法.Abstract: Principal component analysis (PCA) is an important method for processing high-dimensional data. In recent years, PCA models based on various norms have been extensively studied to improve the robustness. However, on the one hand, these algorithms do not consider the relationship between reconstruction error and covariance; on the other hand, they lack the uncertainty of considering the principal component to the data description. Aiming at these problems, this paper proposes a new robust PCA algorithm. Firstly, the $L_{2, p}$-norm is used to measure the reconstruction error and the description variance of the projection data. Based on the reconstruction error and the description variance, the adaptive probability error minimization model is established to calculate the uncertainty of the principal component's description of the data. Based on the uncertainty, the adaptive probability weighting PCA is established. The corresponding optimization method is designed. The experimental results of artificial data sets, UCI data sets and face databases show that RPCA-PW is superior than other PCA algorithms.
-
Key words:
- Principle component analysis (PCA) /
- weighted principal component analysis (WPCA) /
- dimensionality reduction /
- robustness
-
随着技术的进步, 数据采集的效率逐渐提高, 使得数据的规模越来越大、复杂性越来越高. 在大多数情况下, 这些高维数据都存在着能够保留大部分有效信息的低维子空间, 如何移除高维空间中的噪声和无关信息, 提高后续学习算法的性能和效率一直是模式识别和机器学习领域的研究热点. 在过去的几十年中涌现出了许多优秀的算法, PCA[1]是其中最经典的方法之一, 它通过线性变换把数据投影到一个新的坐标空间中, 希望用较少的变量来表示原数据所提供的大部分信息. PCA逐渐发展为多种应用的预处理技术方法, 如图像识别、生物信息和数据挖掘[2-4]. 由于其用途广泛且原理简单, 研究者们陆续提出了各种改进的PCA算法. Koren等[5]提出的WPCA使用了加权距离来减轻离群点对投影方向的影响, 突出了与主成分相关的特征; Schölkopf等[6]通过非线性映射将原始数据映射到高维特征空间, 再执行kernel-PCA以提取特征; 李春娜等[7]极大化带有稀疏正则项的$L{_{p}}$模样本方差, 同时赋予算法鲁棒性和稀疏性.
衡量算法的优劣, 一个重要的指标就是鲁棒性, 尽管基于$L$2模的PCA能够解决许多问题, 但并不能有效地处理小样本问题中的离群点[8], 因为$L$2模的非线性变化特征会放大离群点所带来的影响, 使算法倾向于保留外围结构. 为了减轻异常点的负面影响, 目前已经提出了各种增强鲁棒性的解决方案. $L$1模被认为是增强算法鲁棒性的有效手段之一. Ke等[9]提出了$L$1-PCA算法, 通过极小化基于$L$1模的重建误差来提取主成分; Kwak[10]则在特征空间中极大化对应的$L$1模并利用贪婪算法求解模型; 在此基础上, Nie等[11]提出了一种非贪婪迭代算法能够得到比贪婪算法更好的结果.
尽管基于$L$1模的PCA鲁棒性较强, 但是由于计算代价大, 而且不具有旋转不变性[12]. 因此, 大量具有旋转不变性的鲁棒PCA算法相继出现, 这些方法通过采用不同的准则函数或者优化算法来降低异常点对损失函数的影响, 以提高主成分分析过程中对于异常点的鲁棒性. He等在文献[13]中将PCA的均方误差(MSE)准则修改为最大熵(MaxEnt)准则来尽可能地保留数据的不确定性; 进而在文献[14]中提出HQ-PCA, 使用最大相对熵准则(MCC)代替MSE, 并采用半二次(Half-Quadratic)优化将原问题转换为一系列二次规划问题进行求解. HQ-PCA提高了算法对于噪声的鲁棒性, 同时保留了平移与旋转不变性; He等在文献[15]中基于数据的子空间属性, 分析了鲁棒低秩矩阵恢复方法和基于$M$估计的鲁棒主成分分析方法之间的联系, 提高主成分提取过程中对任意噪声的处理能力; Ding等[16]使用旋转不变的R1模构造重建误差, 在一定程度上抑制了离群点的影响, 但是该方法依赖于投影空间中的维数; Nie等[17]在此基础上提出了RPCA-OM, 计算了在R1范数下的最优均值并能够自动删除最优的数据均值; 受此启发, 许多鲁棒PCA采用$L$21模作为鲁棒降维的有效手段. Nie等[18]基于$L$21范数最大化在理论上与重构误差最小化的关联性提出了PCA-$L$21, 并设计了一种有效的非贪婪优化算法来求解相关的最大化问题; Wang等[19]将$L$21模的距离度量扩展为$L{_{2, p}}$, 可针对不同的数据选择适当的$p$以达到更好的效果; 但以上鲁棒PCA算法缺乏考虑重建误差和投影数据描述方差之间的关系, 在主成分提取的过程中容易造成判别信息的丢失. 对此, Wang等[20]提出的Angle PCA方法通过最大化每个样本点的描述方差和重建误差之间的比率来确定主成分空间, 通过每个数据点与主成分方向的偏移角度进行加权, 但其权值的变化呈余切函数的快速非线性变化特征, 导致其过度强调局部特征, 所提取的主成分泛化性能弱.
基于此, 本文提出了鲁棒自适应概率加权主成分分析(RPCA-PW). RPCA-PW基于样本点的重建误差与描述方差在$L{_{2, p}}$模下的变化关系确定每个样本点的可靠性程度. 其核心是选择主成分空间及其补空间作为参考, 通过分析样本点与这两个描述空间的相似度来确定主成分空间及其补空间对数据描述的不确定性, 结合交替迭代的优化算法, 从而能够在降维过程中自适应地降低噪声和异常样本点的影响. 本文提出的方法不仅对离群点具有鲁棒性, 并可针对不同数据集选择合适的$p$以达到更好的效果, 本文将在人工数据集、UCI数据集和人脸图像数据库上进行实验, 进而证明本文所提出算法的有效性.
1. 相关工作
1.1 PCA
考虑如下样本矩阵: ${X}=[{{{\boldsymbol{x}}}_{1}}, {{{{\boldsymbol{x}}}}_{2}}, \cdots, {{{\boldsymbol{x}}}_{n}}]\in {{{\textbf {R}}}^{d\times n}}$, 其中$n$和$d$分别为样本数量和维数. 不失一般性, 这里假设${X}=[{{{\boldsymbol{x}}}_{1}}, {{{\boldsymbol{x}}}_{2}}, \cdots, {{{\boldsymbol{x}}}_{n}}]$已经去中心化, 即$\sum_{i=1}^{n}{{{{\boldsymbol{x}}}_{i}}}=0$, 定义投影矩阵${W}\in {{{\textbf {R}}}^{d\times m}}\left( m<d \right)$, 其中$m$是降维后的维数. 从均方差的角度来看, PCA通过求解以下优化问题, 使得投影空间中样本点的方差最大化:
$$ \begin{align}\label{1} \underset{{{{W}}^{\rm {T}}}{W}={I}}{\mathop{\max }} \sum\limits_{i=1}^{n}{\left\| {{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{2}} \end{align} $$ (1) 其中, $I$是单位矩阵, 因为$\left\| {{{\boldsymbol{x}}}_{i}}-{W}{{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{2}+\left\| {{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{2}=\left\| {{{\boldsymbol{x}}}_{i}} \right\|_{2}^{2}$, 因此通过简单的变换可以得到式(1)的另一种等价形式:
$$ \begin{align}\label{2} \underset{{{{W}}^{\rm {T}}}{W}={I}}{\mathop{\min }} \sum\limits_{i=1}^{n}{\left\| {{{\boldsymbol{x}}}_{i}}-{W}{{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{2}} \end{align} $$ (2) 由式(1)和式(2)可知, 由于$L$2模对离群点敏感, 传统PCA对噪声的鲁棒性不强, 噪声的存在会使得PCA的计算结果会出现很大的误差.
1.2 ${L_{2, p}}$-PCA
$L{_{2, p}}$-PCA采用$L{_{2, p}}$模作为重建误差的距离度量, 可针对不同的数据选择适当的$p$以达到更好的效果. $L{_{2, p}}$-PCA不仅能在一定程度上削弱噪声点的影响, 而且还保留了PCA所需的特性, 如旋转不变性. 此外, 基于$L{_{2, 1}}$模的鲁棒PCA可作为$L{_{2, p}}$-PCA的特例. $L{_{2, p}}$-PCA的目标函数定义为:
$$ \begin{align}\label{3} \underset{{{{W}}^{\rm {T}}}{W}={I}}{\mathop{\min }} \sum\limits_{i=1}^{n}{\left\| {{{\boldsymbol{x}}}_{i}}-{W}{{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{p}} \end{align} $$ (3) $L{_{2, p}}$模的非线性函数特征在一定程度上降低了噪声和异常样本点的影响力, 但是仍然不能完全剔除噪声和异常样本点的影响. 究其原因, $L{_{2, p}}$-PCA的根本特征在于仅考虑了样本点与数据簇整体统计特征的偏差程度(bias), 但没有考虑噪声点与可靠数据点在不同的子空间属性下潜在的可分性, 从而造成判别信息的丢失.
1.3 Angle PCA
Angle PCA采用$L{_{2}}$模来构造投影数据的重建误差和描述方差, 通过最大化方差和重构误差之比来确定投影矩阵, 即Angle PCA通过求解以下目标函数来确定主成分:
$$ \begin{align}\label{5} \underset{{{{W}}^{\rm {T}}}{W}={I}}{\mathop{\max }} \sum\limits_{i=1}^{n}{\frac{\left\| {{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{1}}{\left\| {{{\boldsymbol{x}}}_{i}}-{W}{{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{1}}} \end{align} $$ (4) 根据$\left\| {{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{2}+\left\| {{{\boldsymbol{x}}}_{i}}-{W}{{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{2}=\left\| {{{\boldsymbol{x}}}_{i}} \right\|_{2}^{2}$, 若将$\left\| {{{\boldsymbol{x}}}_{i}} \right\|_{2}^{1}$视为直角三角形的斜边, 则$\left\| {{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{1}$和$\left\| {{{\boldsymbol{x}}}_{i}}-{W}{{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{1}$分别为直角三角形的两条直角边, 令直角边$\left\| {{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{1}$与斜边$\left\| {{{\boldsymbol{x}}}_{i}} \right\|_{2}^{1}$的夹角为${{\alpha }_{i}}$, 观察模型(4)可知, 求和函数中的每一项是第$i$个数据的重建误差与协方差之间角度的余切值, 即
$$ \begin{align}\label{6} \frac{\left\| {{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{1}}{\left\| {{{\boldsymbol{x}}}_{i}}-{W}{{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{1}}=\cot {{\alpha }_{i}} \end{align} $$ (5) 因此, 目标函数(4)被称为Angle PCA. 通过对样本点迭代加权的方式来降低噪声和异常样本的影响. 这种建模方式的核心是能够减少重建误差较大样本点产生的损失, 从而提升对噪声的鲁棒性. 但$\cot {{\alpha }_{i}}$的非线性快速衰减特征造成了Angle PCA对数据的全局结构特征提取能力差. 例如: 当样本点与主成分方向之间的夹角增大时, $\cot {{\alpha}_{i}}$迅速减小, 使得主成分对数据的局部结构特征描述能力强, 但是对数据的全局结构特征描述能力差. 这一特征造成Angle PCA最优解的稳定性差, 对初始投影矩阵$W$的选取依赖性很强. 例如: 当模型的初始$W$选择恰当时, 则Angle PCA对噪声点具有很强的鲁棒性, 若初始$W$确定的投影方向与实际主成分方向垂直的时候, 式(5)起到的作用则正好相反, 表现为突出非主成分样本点在模型中所占的比重(此时非主成分样本点的重建误差很小).
2. 鲁棒自适应概率加权主成分分析
为了能够充分考虑重建误差和投影数据描述方差之间的联系, 并根据数据主要统计特征及其互补信息确定各样本点的可靠程度, 在提取主成分的过程中, 提高可靠度较高样本点的影响力, 同时削弱可靠度较低样本点的影响程度, 本文建立以下RPCA-PW模型:
$$ \begin{align}\label{7} \underset{{{W}^{\rm {T}}}\!W=I}{\mathop{\max }} \!\sum\limits_{i=1}^{n}\!\left( \!\left\| \!{{W}^{\rm T}}\!{{\boldsymbol{x}}_{i}} \right\|_{2}^{p}-\frac{1-{{a}_{i}}}{{{a}_{i}}+\varepsilon }\left\| {{\boldsymbol{x}}_{i}}-WW^{\rm {T}}\!{{\boldsymbol{x}}_{i}} \right\|_{2}^{p} \right) \end{align} $$ (6) 其中, $0\le {{a}_{i}}\le 1$, $\varepsilon$为一个较小的正数常数, 目的是防止分母为0. 令$\displaystyle\frac{1-{{a}_{i}}}{{{a}_{i}}+\varepsilon}=\delta_{i}$, 则式(6)变为:
$$ \begin{align}\label{8} \underset{{{W}^{\rm {T}}}W=I}{\mathop{\max }} \sum\limits_{i=1}^{n}{\left( \left\| {{W}^{\rm T}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p}-\delta_{i}\left\| {{\boldsymbol{x}}_{i}}-W{{W}^{\rm {T}}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p} \right)} \end{align} $$ (7) 模型(7)中采用了$L{_{2, p}}$模作为度量标准, 不仅可以降低噪声的影响, 而且具有旋转不变性, 改变$p$值的大小可应用于不同类型的数据集, 大大提高了算法的灵活性和鲁棒性.
为了提高RPCA-PW对数据全局结构特征的描述能力和对噪声的鲁棒性, 需要模型(7)中$\delta_{i}$满足以下要求:
1) 能够反映出样本点的可靠性(不确定性). 对于可靠样本点, $\delta_{i}$应取较大的值, 对于噪声和异常样本点, $\delta_{i}$应取较小的值, 通过分析样本点的不确定性削弱噪声和异常值的影响.
2) 在主成分空间所确定的一个较大的邻域内, $\delta_{i}$的取值应保持稳定, 以提高主成分对数据全局结构特征的提取能力, 从而提高主成分的泛化性能.
3) 能够根据数据受噪声污染的实际情况动态调整各局部邻域的大小, 即能够动态调整主成分局部邻域和主成分互补空间局部邻域的划分界限.
为了满足上述要求, 本文通过以下模型确定权值:
$$ \begin{align}\label{9} \underset{0\le {{a}_{i}}\le 1}{\mathop{\min }} {{a}_{i}}\left\| {{W}^{\rm {T}}} {{\boldsymbol{x}}_{i}} \right\|_{2}^{p}&+\left( 1-{{a}_{i}} \right)\left\| {{\boldsymbol{x}}_{i}}-W{{W}^{\rm {T}}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p}+{\lambda_{i}} \left( {{a}_{i}}^{2}+{{\left( 1-{{a}_{i}} \right)}^{2}} \right) \end{align} $$ (8) 其中, $\left\| {{W}^{\rm {T}}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p}(\left\| {{\boldsymbol{x}}_{i}}-{W{W}^{\rm T}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p})$表示主成分空间(主成分空间的补空间)对数据的描述能力, $\left\| {{W}^{\rm {T}}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p}$越大($\left\| {{\boldsymbol{x}}_{i}}-{W{W}^{\rm T}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p}$越小), 代表样本点隶属于主成分空间的程度越大, 该样本点越可靠, 反之亦然. 令式(8)中的${\lambda_{i}} =0$, 有${{a}_{i}}\in \left\{ 0, 1 \right\}$, 上述模型类似于$1NN$规则, 即对于每个样本点要么选择主成分空间, 要么选择其补空间来描述. 但是这种"非此即彼"结果大大降低了算法的泛化性能, 也使得算法在验证集上的实验结果缺乏鲁棒性. 如何软化模型对于样本点的判定结果使得结果更加契合主成分提取的过程是我们重点考虑的一个问题. 基于以上的分析, 在模型中添加基于$L$2-norm的正则化项$\lambda \left( {{a}_{i}}^{2}+{{\left( 1-{{a}_{i}} \right)}^{2}} \right)$. 因此${{a}_{i}}$可以理解为把第$i$个样本点划分到主成分空间的错误概率, 通过$L$2-norm的正则化项, 上述模型考虑了每个样本点划分到主成分空间和其补空间的错分概率所带来的误差.
令${{u}_{1, i}}=\left\| {{W}^{\rm {T}}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p}, {{u}_{2, i}}=\left\| {{\boldsymbol{x}}_{i}}-W{{W}^{\rm T}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p}$, 则式(8)可写成:
$$ \begin{align}\label{91} \underset{0\le {{a}_{i}}\le 1}{\mathop{\min }} {{a}_{i}}{{u}_{1, i}}+\left( 1-{{a}_{i}} \right){{u}_{2, i}}+{\lambda_{i}}\left( {{a}_{i}}^{2}+{{\left( 1-{{a}_{i}} \right)}^{2}} \right) \end{align} $$ (9) 由于${{a}_{i}}$对于不同$i$的取值相互独立, 因此通过简单的数学变换:
$$ \begin{array}{l} \mathop {\min }\limits_{0 \le {a_i} \le 1} {\mkern 1mu} {a_i}{u_{1, i}} + \left( {1 - {a_i}} \right){u_{2, i}} + \\ {\lambda _i}\left( {{a_i}^2 + {{(1 - {a_i})}^2}} \right) \Rightarrow \mathop {\min }\limits_{0 \le {a_i} \le 1} {\mkern 1mu} 2\lambda {a_i}^2 - 2{\lambda _i}{a_i} + \\ {\lambda _i} + {a_i}{u_{1, i}} + \left( {1 - {a_i}} \right){u_{2, i}} \Rightarrow \mathop {\min }\limits_{0 \le {a_i} \le 1} {\mkern 1mu} 2{a_i}^2 - \\ 2{a_i} + \frac{{{a_i}{u_{1, i}} + \left( {1 - {a_i}} \right){u_{2, i}}}}{{{\lambda _i}}} \end{array} $$ (10) 求得${{a}_{i}}$最优解的解析形式为:
$$ \begin{equation}\label{93} {{a}_{i}}=\begin{cases} \frac{2{\lambda_{i}} -{{u}_{1, i}}+{{u}_{2, i}}}{4{\lambda_{i}} }, &0\le \frac{2{\lambda_{i}} -{{u}_{1, i}}+{{u}_{2, i}}}{4{\lambda_{i}} } \le 1 \\ 0, & \frac{2{\lambda_{i}} -{{u}_{1, i}}+{{u}_{2, i}}}{4{\lambda_{i}} }<0 \\1, & \frac{2{\lambda_{i}} -{{u}_{1, i}}+{{u}_{2, i}}}{4{\lambda_{i}} }>1 \end{cases} \end{equation} $$ (11) 式(11)中基于${{a}_{i}}$最优解的稀疏性结构特征使得在主成分周围的邻域内, $\delta_{i}$为某个固定的较大正数, 在重建误差相对大的噪声样本局部邻域内, $\delta_{i}$为某个固定的非常小的正数或等于零. 另外式(11)中的参数${\lambda_{i}}$, 决定了局部稀疏邻域的大小, 即决定了主成分样本的局部邻域与异常样本局部邻域的划分, 通过调节${\lambda_{i}}$可以动态调整各自局部邻域的大小.
下面通过与PCA、Angle PCA的比较实例来说明RPCA-PW对离群点的鲁棒性:
如图 1所示, 图 1 (a)中是一组由500个数据点组成的服从高斯分布的数据簇, 在图 1 (b)中将随机插入10个与原分布差异很大的离群点. 结果显示, PCA对样本点的分布非常敏感, 主方向计算结果误差非常大; 因为$\cot \left( {{\alpha }_{i}} \right)$函数非线性快速衰减的加权方式, 使Angle PCA在离群点的影响之下, 投影方向也发生了一定程度的偏离, 图 1 (c)显示了$\cot \left( {{\alpha }_{i}} \right)$的变化过程; 而RPCA-PW的投影方向不受离群点的影响, 主成分空间仍然很好地保留了原数据的全局结构特征, 有效排除少数离群点造成的影响. 这是因为RPCA-PW充分考虑了数据在描述空间中的分布特征, 可以将脱离数据集的异常样本造成的影响降到最低. 图 1 (d)中显示了权重系数$\delta_{i}$的变化过程, 根据$\delta_{i}$的变化趋势, 可以分为三个阶段, 分别代表着RPCA-PW为主成分点、过渡点和离群点所属的三个局部区域所分配的不同权重(对于离群点, 有$\delta_{i}=0$), 通过调节参数${\lambda_{i}} $可以控制两个跳变点的位置, 即(138, 10)与(500, 0)的位置, 进而调整三类区域的范围.
3. 优化算法
本节中利用优化理论中的交替优化算法求解模型(7), 通过简单的数学代换, 可得:
$$ \begin{align} \sum\limits_{i=1}^{n}{\left( \left\| {{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{p}-\delta_{i}\left\| {{{\boldsymbol{x}}}_{i}}-{{W}}{{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{p} \right)}= \\\sum\limits_{i=1}^{n}{\left\| {{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{2}\left\| {{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{p-2}} -\\\sum\limits_{i=1}^{n}{ \delta_{i} \left\| {{{\boldsymbol{x}}}_{i}}-{{{W}}}{{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{2}\left\| {{{\boldsymbol{x}}}_{i}}-{{W}}{{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{p-2}} \end{align} $$ (12) 令${{d}_{1, i}}=\left\| {{W}^{\rm {T}}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p-2}$, ${{d}_{2, i}}=\left\| {{\boldsymbol{x}}_{i}}-{W}{{{W}}^{\rm {T}}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p-2}$, 并代入式(12)可得
$$ \begin{align}{l} \sum\limits_{i=1}^{n}{\left\| {{W}^{\rm {T}}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{2}\left\| {{W}^{\rm {T}}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p-2}} -\\ \sum\limits_{i=1}^{n}{\delta_{i}\left\| {{\boldsymbol{x}}_{i}} -{W}{{{W}}^{\rm {T}}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{2}\left\| {{\boldsymbol{x}}_{i}}- {W}{{{W}}^{\rm {T}}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p-2}}= \\ \sum\limits_{i=1}^{n}\!\Big( {{d}_{1, i}}Tr\left( {{{\boldsymbol{x}}}_{i}}^{\rm {T}} {W}{{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right)-\\ \delta_{i} {{d}_{2, i}}Tr\left( {{{\boldsymbol{x}}}_{i}}^{\rm {T}}\!{W}\!{{{W}}^{\rm {T}}} {{{\boldsymbol{x}}}_{i}} \right) \Big)= \\ \sum\limits_{i=1}^{n}{Tr\left( {{W}^{\rm {T}}}\left( {{d}_{1, i}}+ \delta_{i}{{d}_{2, i}} \right){{\boldsymbol{x}}_{i}}{{\boldsymbol{x}}_{i}}^{\rm {T}}W \right)} \end{align} $$ (13) 将式(13)代入模型(7)中, 模型(7)最后变为:
$$ \begin{align}\label{12} \underset{{{W}^{\rm {T}}}W=I}{\mathop{\max }} \sum\limits_{i=1}^{n}{ Tr\left( {{W}^{\rm {T}}}\left( {{d}_{1, i}}+ \delta_{i} {{d}_{2, i}} \right){{\boldsymbol{x}}_{i}}{{\boldsymbol{x}}_{i}}^{\rm {T}}W \right)} \end{align} $$ (14) RPCA-PW的目标是找到一个投影矩阵$W$, 以最大化目标函数(14)的值, 其中有三个与$W$相关的未知变量分别是$W$、${{d}_{1, i}}$和${{d}_{2, i}}$. 因此, 目标函数没有闭式解, 难以直接求解目标函数(14). 本文采用文献[20]中的算法来交替地更新$W$、${{d}_{1, i}}$和${{d}_{2, i}}$, 具体来说, 是在第$i$次迭代中, 当${{d}_{1, i}}$和${{d}_{2, i}}$已知时, 通过最小化目标函数(14)更新投影矩阵$W$. 在这种情况下, 将目标函数(14)简化为:
$$ \begin{align}\label{13} \underset{{{{W}}^{{\rm {T}}}}{W}={I}}{\mathop{\max }} Tr\left( {{{W}}^{\rm {T}}}{XD}{{{X}}^{\rm {T}}}{W} \right) \end{align} $$ (15) 其中, $D$是对角矩阵, 对角线上的元素为${{{D}}_{ii}}={{d}_{1, i}}+\delta_{i} {{d}_{2, i}}$, ${{a}_{i}}$可由式(11)获得. 根据矩阵理论, 目标函数(15)中投影矩阵$W$的列向量由矩阵${XD}{{{X}}^{\rm T}}$的前$m$个最大特征值所对应的特征向量组成, 随后再使用得到的$W$来更新${{d}_{1, i}}$和${{d}_{2, i}}$, 重复该迭代过程直至算法收敛. 算法1中给出了求解RPCA-PW的具体算法.
算法 1. RPCA-PW算法
输入: ${X}\in {{{\textbf {R}}}^{d\times n}}$, $k=1$, $m$, $p$, $\varepsilon$, 其中$\sum_{i=1}^{n}{{{{\boldsymbol{x}}}_{i}}}=0$
初始化: ${{{{W}}^{0}}}\in {{{\textbf {R}}}^{d\times m}}$且${{{{{{W}}^{0}}}}^{\rm {T}}}{{{{W}}^{0}}}={I}$, 目标函数大小$J({{{W}}^{0}})$
1: While not converge
2: 对于所有的样本点, 计算${{d}_{1, i}}=\left\| {{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{p-2}$, ${{d}_{2, i}}=\left\| {{{\boldsymbol{x}}}_{i}}-{{W}}{{W}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{p-2}; $
3: 对于每个$i$, 通过式(11)来更新权值${{a}_{i}}$;
4: 计算对角矩阵$D$, 其中对角线上的元素为${{{D}}_{ii}}={{d}_{1, i}}+ \delta_{i} {{d}_{2, i}}$;
5: 更新投影矩阵$W$, 其中$W$的列向量由矩阵${XD}{{{X}}^{\rm T}}$的前$m$个最大特征值所对应的特征向量组成;
6: 若$J({{{W}}^{k}})\ge J({{{W}}^{k-1}})$, 转到第8步, 否则转到第7步;
7: 通过线搜索Armijo算法确定步长的子梯度下降法[21]找到满足$J({{{W}}^{k}})\ge J({{{W}}^{k-1}})$的${{{W}}^{k}}$, 如果没有解决方案, 转到步骤9, 否则, 转到步骤8;
8: $k\leftarrow k + 1;$
9: End while
输出: ${W}\in {{{\textbf {R}}}^{d\times m}}$
4. 讨论
本节中讨论了RPCA-PW算法的收敛性以及$L{_{2, p}}$范数下不同$p$值所对应的损失函数变化情况, 并给出本文算法与其他相关鲁棒PCA算法的关系.
4.1 算法收敛性
本文的基本思路是对于给定的主成分空间, 通过模型(8)学习每个样本点的误差极小化概率描述, 将学习到的概率描述反馈到模型(7)中, 从而自适应地修改模型(7)中描述误差项的权重, 从而达到提高PCA鲁棒性的目的. 因此算法1的收敛性应该从以下三个方面考虑:
1) 给定$W$条件下, 对模型(8)的优化
对于$W$已经给定的条件下, 模型(8)存在解析解, 其最优解由式(11)给出.
2) 给定${{\delta }_{i}}$条件下, 对模型(7)的优化
模型(7)的拉格朗日函数为:
$$ \begin{align} {{L}_{1}}(W)= \sum\limits_{i=1}^{n}{\left( \left\| W^{\rm T}\!{{\boldsymbol{x}}_{i}} \right\|_{2}^{p}-{{\delta }_{i}}\left\| {{\boldsymbol{x}}_{i}}-{{W}_{{}}}W^{\rm {T}}{{\boldsymbol{x}}_{i}} \right\|_{2}^{p} \right)}- Tr\left( \Lambda \left( {{W}^{\rm {T}}}W-I \right) \right) \end{align} $$ (16) 其中, 拉格朗日乘子$\Lambda $是用于强制正交约束${{W}^{\rm T}}W=I$的对角矩阵. 在第$k$次迭代中, 当${{\delta }_{i}}$已知时, 为了满足KKT条件, 式(16)的梯度必须等于零, 即
$$ \begin{align} \frac{\delta {{L}_{1}}}{\delta W}=XD{X}^{\rm {T}}W-\Lambda W =0 \end{align} $$ (17) 根据算法1中的步骤5, 能够找到式(17)的最优解. 因此, 算法1的收敛解决方案满足问题的KKT条件. 式(16)的拉格朗日方程为:
$$ \begin{align} {{L}_{2}}(W)= Tr({{W}^{\rm {T}}}XD{X}^{\rm {T}}W)- Tr\left( \Lambda \left( {{W}^{\rm {T}}}W-I \right) \right) \end{align} $$ (18) 对$W$求导可得到关于式(18)的KKT条件:
$$ \begin{align} XD{X}^{\rm {T}}W-\Lambda W =0 \end{align} $$ (19) 注意到在式(19)中, 矩阵$D$与${{W}_{k-1}}$有关. 假设在第$k$次迭代中获得局部最优解${{W}^{*}}$, 即${{W}^{*}}={{W}_{k}}={{W}_{k-1}}$. 在这种情况下, 式(17)与式(19)保持一致, 这意味着算法1的收敛解决方案满足模型(7)的KKT条件, 即
$$ \begin{align} {{\left. \frac{\delta {{L}_{1}}}{\delta W} \right|}_{W={{W}^{*}}}}=0 \end{align} $$ (20) 上述分析保证了算法1的最优解是模型的一个驻点. 此外, 算法1中的步骤6和步骤7说明RPCA-PW的目标函数值在每次迭代中都是非递减的, 这样就保证了算法具有单调收敛的特性.
3) 迭代更新$W$和${{\delta }_{i}}$, 算法1的收敛性验证
这里通过实验验证迭代更新$W$和${{\delta }_{i}}$时算法1的收敛性, 具体内容见实验部分第5.3.5节.
4.2 不同p值下的损失函数
图 2绘制了$p$在不同取值下的目标函数取值变化曲线. 从图中可以看出, 当$p$为2时, 具有大重建误差的样本点将会显着地支配目标函数, 因此传统的基于MSE的PCA算法对于噪声敏感. 与$p=2$相比, $p=0.5$或1可以在一定程度上减弱大距离样本点的影响, 对于噪声点具有更强的鲁棒性, 此外, 与$p=1$或2相比, $p=0.5$可以进一步削弱异常样本点的影响, 同时提高主成分邻域中的样本点在求解最优解时的影响.
4.3 与相关算法之间的联系
基于对于$p$的不同取值的分析, 下面将讨论RPCA-PW与几种鲁棒PCA算法之间的相互联系, 从模型的角度出发分析各自算法的特点, 包括PCA, R1-PCA, $L{_{2, p}}$-PCA和Angle PCA.
4.3.1 与PCA的联系
经典PCA算法建立在均方差或者重建误差意义上, 目的是使得投影空间中样本点协方差最大或者重建误差最小, 本质是在最小均方差意义下寻找最能代表数据特征的投影向量子空间, 因此有:
1) 若模型(6)中的${{a}_{i}}=1~(i=1, \cdots, n)$, $p=2$, 得到:
$$ \begin{align} \underset{{{{W}}^{\rm {T}}}{W}={I}}{\mathop{\max }} \sum\limits_{i=1}^{n}{\left\| {{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{2}} \end{align} $$ (21) 2) 若模型(6)中的${{a}_{i}}=0~(i=1, \cdots, n)$, $p=2$, 得到:
$$ \begin{align} \underset{{{{W}}^{\rm {T}}}{W}={I}}{\mathop{\min }} \sum\limits_{i=1}^{n}{\left\| {{{\boldsymbol{x}}}_{i}}-{W}{{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{2}} \end{align} $$ (22) 模型(21)和(22)是PCA的两种标准等价形式.
4.3.2 与R1-PCA的联系
一个数据矩阵的R1模就是每个数据点的$L$2模之和, R1-PCA将原PCA模型中的$L$2模改成R1模进行求解, R1模在降低噪声影响的同时能保持旋转不变性. 若模型(6)中的${{a}_{i}}=0~(i=1, \cdots, n)$, $p=1$, 可得
$$ \begin{align} \underset{{{{W}}^{\rm {T}}}{W}={I}}{\mathop{\min }} \sum\limits_{i=1}^{n}{\left\| {{{\boldsymbol{x}}}_{i}}-{W}{{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{1}} \end{align} $$ (23) 模型(23)即为R1-PCA的目标函数.
4.3.3 与${L_{2, p}}$的联系
$L{_{2, p}}$-PCA采用$L{_{2, p}}$模构造每个样本点的重建误差, 与大多数现有的PCA-$L$1方法相比, $L{_{2, p}}$-PCA直接最小化了样本点的重建误差, 与$L$1-PCA方法相比, $L{_{2, p}}$-PCA保留了PCA的旋转不变性. 若模型(6)中的${{a}_{i}}=0~(i=1, \cdots, n)$, 则它的形式简化为:
$$ \begin{align} \underset{{{{W}}^{\rm {T}}}{W}={I}}{\mathop{\min }} \sum\limits_{i=1}^{n}{\left\| {{{\boldsymbol{x}}}_{i}}-{W}{{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|_{2}^{p}} \end{align} $$ (24) 模型(24)即为$L{_{2, p}}$-PCA的目标函数.
4.3.4 与Angle PCA的联系
Angle PCA采用最大化每个样本点的协方差和重建误差之比的总和所得到的结果作为投影矩阵, 根据文献[22]中的定理1, 模型(4)可以等价转换为以下形式:
$$ \begin{align} \underset{{{{W}}^{\rm T}}{W}={I}}{\mathop{\max}} \sum\limits_{i=1}^{n}{\left( {{\left\| {{{W}}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|}_{2}^{1}}-{{\mu }_{i}}{{\left\| {{{\boldsymbol{x}}}_{i}}-{W}{{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|}_{2}^{1}} \right)} \end{align} $$ (25) 其中, $\mu _{i}^{k}=\frac{{{\left\| {{\left( {{{W}}^{k-1}} \right)}^{\rm {T}}}{{{\boldsymbol{x}}}_{i}} \right\|}_{2}^{1}}}{{{\left\| {{{\boldsymbol{x}}}_{i}}-{W}{{\left( {{{W}}^{k-1}} \right)}^{\rm T}}{{{\boldsymbol{x}}}_{i}} \right\|}_{2}^{1}}}$, $k$表示优化算法中当前的迭代次数, 根据第2节中的定义, 可以认为$\mu_{i}^{k}=\cot\left(\alpha_{i}^{k-1}\right)$ (${{\alpha}_{i}}$为直角边${{\left\|{{{W}}^{\rm T}}{{{\boldsymbol{x}}}_{i}}\right\|}_{2}^{1}}$与斜边${{\left\| {{{\boldsymbol{x}}}_{i}} \right\|}_{2}^{1}}$的夹角). 若令模型(6)中
$$ \begin{align} \frac{1-{{a}_{i}}}{{{a}_{i}}+\varepsilon}=\frac{{{\left\|{{\left({{{W}}^{k-1}}\right)}^{\rm T}}{{{\boldsymbol{x}}}_{i}}\right\|}_{2}^{1}}}{{{\left\|{{{\boldsymbol{x}}}_{i}}-{W}{{\left({{{W}}^{k-1}}\right)}^{\rm T}}{{{\boldsymbol{x}}}_{i}}\right\|}_{2}^{1}}} \end{align} $$ (26) 则它与模型(4)中的加权效果相同.
5. 实验结果与分析
本节将文中所提算法在人工数据集、UCI数据集和人脸数据库上进行实验, 并将其性能与传统PCA和相关鲁棒PCA算法进行比较, 例如: PCA-$L$21、RPCA-OM、Angle PCA、MaxEnt-PCA、HQ-PCA和$L{_{2, p}}$-PCA. 其中式(6)中的参数$\varepsilon$是为了防止除零, 本文在实验中统一设置为0.05, 另一参数${\lambda_{i}}$的取值决定主成分及非主成分的局部邻域大小, 实验中根据不同的数据集动态地进行调整, 为了方便超参数设置, 本文在实验中统一置${\lambda_{i}}$为:
$$ \begin{align} {{\lambda }_{i}}=\lambda =\frac{1}{2n}\sum\limits_{i=1}^{n}{\left| \left\| {\boldsymbol{x}_{i}}-W{{W}^{\rm {T}}}{\boldsymbol{x}_{i}} \right\|_{2}^{p} -\left\| {{W}^{\rm {T}}}{\boldsymbol{x}_{i}} \right\|_{2}^{p} \right|} \end{align} $$ (27) 在实验中使用最近邻域(1-NN)分类器[23]进行分类以计算识别准确率, 在人脸重构实验中, 平均重建误差由原始未被遮挡的图像与重构图像之间的平均距离定义, 如下所示:
$$ \begin{align} error=\frac{1}{n}\sum\limits_{i=1}^{n}{{{\left\| \boldsymbol{x}_{i}^{org}-W{{W}^{\rm {T}}}{{\boldsymbol{x}}_{i}} \right\|}_{2}}} \end{align} $$ (28) 其中, $n$为图片总数, $\boldsymbol{x}_{i}^{org}$为未加入噪声块的原始图像, $\boldsymbol{x}_{i}$为加入噪声块后的图像.
5.1 人工数据集实验
为了验证本文所提算法在进行特征提取时能够有效挖掘数据集中的底层结构, 实验选用的人工数据集是一组随机生成的双高斯数据集. 在该数据集中, 存在两个服从高斯分布的数据簇, 目标是找到一个合适的低维投影空间, 使得两组数据簇在低维子空间中能够明显分开. 然后将RPCA-PW与PCA和Angle PCA进行比较, 结果如图 3所示.
图 3 三种算法在双高斯人工数据集上的投影结果Fig. 3 Projection result of three algorithms on two-Gaussian artificial dataset从图 3中可以看出, 当这两组数据簇相距很远时, 三种PCA方法都能够找到一个合适的投影方向使得数据集在一维空间中保留绝大多数的信息. 随着两个数据簇之间的距离逐渐减少, PCA变得不再有效, 具体表现为在一维投影空间中, 两组数据簇互相重叠, 完全丢失判别信息. 随着两个集群变得更加接近, PCA与Angle PCA都无法得到最佳的投影方向. 而RPCA-PW所找到的一维投影在各种情况下都能将两组数据簇明显分开. 实验结果说明PCA由于倾向于保留数据集整体的外围结构, 受到大距离样本的干扰明显; Angle PCA更加注重保留局部结构, 但是它采用的快速衰减加权方式将过多的样本点当成劣点处理, 丢失了过多的全局结构判别信息; RPCA-PW在提取主成分的过程中, 在突出样本点主成分与互补子空间的区域性差异的同时, 能够有效揭示数据集中的底层结构.
5.2 UCI数据集实验
为了验证本文提出算法的特征提取能力, 本实验选用了UCI数据集中常用的几个数据集, 如: Australian、Cars、Cleve和Solar等, 这些数据集已被用于许多研究, 具体信息在表 1中列出. 为了消除随机影响, 实验时采用了十折交叉验证法, 将每个数据集降至$c-1$维, 其中$c$为类别数, 然后采用最近邻分类器对每一数据集求出识别正确率并计算出对应的重建误差. 其中对于采用$L{_{2, p}}$-norm的作为距离度量算法, 实验中分别将$p$设为0.5, 1, 1.5, 2四个值进行实验. 最终得到8种算法在10个数据集上的平均识别正确率和重建误差大小. 实验结果如表 2和表 3所示.
表 1 实验中使用的UCI数据集Table 1 UCI data sets used in the experiment数据集 维数 类别数 样本数 Australian 14 2 690 Cars 8 3 392 Cleve 13 8 303 Solar 12 6 323 Zoo 19 7 101 Control 60 6 600 Crx 15 2 690 Glass 9 6 214 Iris 4 3 150 Wine 13 3 178 表 2 UCI数据集上各算法的平均分类正确率(%)Table 2 Average classification accuracy of each algorithm on UCI data sets (%)数据集 Australian Cars Cleve Solar Zoo Control Crx Glass Iris Wine PCA 57.32 69.27 52.16 64.11 96.00 91.83 54.93 74.35 96.00 73.04 PCA-$L$21 62.41 69.17 52.74 64.44 95.60 92.50 53.39 75.33 97.33 74.13 RPCA-OM 63.04 69.93 52.16 65.27 95.00 92.83 56.96 74.35 96.00 74.15 Angle PCA 60.39 69.43 52.16 65.60 94.00 84.28 59.59 73.94 95.53 74.15 MaxEnt-PCA 60.14 69.17 52.45 64.76 95.10 92.15 59.32 74.42 95.33 73.59 HQ-PCA 60.77 69.27 52.46 65.46 95.80 91.50 60.87 76.16 92.00 75.55 $L{_{2, p}}$-PCA $p=0.5$ 60.68 69.60 52.84 65.42 93.40 92.10 60.29 73.56 96.47 73.59 $p=1$ 62.39 69.58 52.16 64.51 94.90 92.50 59.43 73.73 96.67 73.59 $p=1.5$ 62.81 69.43 52.16 65.28 95.00 92.50 58.20 75.57 96.33 73.04 $p=2$ 62.32 69.43 52.16 64.11 96.00 91.83 54.93 75.82 96.00 73.59 RPCA-PW $p=0.5 $ 63.77 71.21 53.76 66.85 95.00 92.50 58.84 74.35 95.33 74.15 $p=1 $ 63.04 69.43 52.49 65.94 95.00 91.67 60.14 73.94 96.00 74.15 $p=1.5$ 62.17 69.43 52.16 64.72 95.00 97.83 61.16 76.28 96.67 74.15 $p=2$ 62.32 69.43 52.16 64.11 96.00 92.33 54.93 75.82 96.00 73.59 表 3 UCI数据集上各算法的重建误差Table 3 Reconstruction error of each algorithm on UCI data sets数据集 Australian Cars Cleve Solar Zoo Control Crx Glass Iris Wine PCA 197.53 1 979.82 5.47 2.97 1.43 115.06 6 265.42 37.91 0.67 24.49 PCA-$L$21 197.21 1 979.16 6.90 2.90 1.56 132.84 6 545.72 38.59 1.56 34.44 RPCA-OM 193.23 1 977.98 5.61 2.65 1.51 108.13 5 684.38 38.64 0.64 24.85 Angle PCA 197.96 1 981.34 13.27 2.95 2.04 123.62 6 583.82 38.42 0.59 25.85 MaxEnt-PCA 203.82 1 976.70 6.24 2.61 1.44 113.01 6 805.98 38.12 0.58 25.01 HQ-PCA 195.79 1 929.26 5.92 2.37 1.39 131.35 6 987.68 36.38 4.31 25.85 $L_{2, p}$-PCA $p=0.5$ 193.29 1 978.76 9.22 2.93 2.05 106.69 6 601.74 38.33 1.04 26.14 $p=1$ 193.71 1 978.33 5.60 2.75 1.72 108.06 6 588.17 38.37 0.84 25.44 $p=1.5 $ 193.50 1 977.93 5.50 2.69 1.44 109.69 6 807.38 37.82 0.72 25.05 $ p=2$ 193.53 1 977.82 5.47 2.97 1.43 115.06 5 865.42 37.91 0.67 24.49 RPCA-PW $p=0.5$ 192.93 1 976.94 5.75 2.95 1.57 106.11 6 467.83 38.43 0.52 24.12 $p=1$ 193.27 1 979.96 6.84 2.84 1.83 110.46 6491.19 38.17 0.70 24.36 $p=1.5$ 193.36 1 977.82 5.06 2.83 1.46 110.45 6 073.11 37.91 0.71 25.26 $p=2$ 193.53 1 977.82 5.47 2.97 1.43 115.06 5 865.42 37.91 0.67 24.49 通过观察发现, 在完全相同且随机的实验条件下RPCA-PW能够在8组UCI数据集上取得更高的平均识别正确率, 同时在5组UCI数据集上有着最小的重建误差. 此外, HQ-PCA在4组UCI数据集上取得最小的重建误差, 也展现出了优越的性能. 在$p$取不同值的情况下, 对应$L{_{2, p}}$-PCA和RPCA-PW算法的识别正确率也有所区别, 其中当$p=0.5$的时候, $L{_{2, p}}$-PCA和RPCA-PW在总体上拥有更好的降维性能, 这是因为与$p=1$或2相比, $p=0.5$可以进一步削弱异常样本点的影响, 同时提高主成分邻域中的样本点在求解最优解时的影响. 因此在UCI真实数据集上的实验表明RPCA-PW在拥有更高精度的基础上, 还通常具有更小的重建误差.
5.3 人脸识别与重建实验
5.3.1 人脸数据库
本节中运用两个人脸数据库的人脸图像进行实验, 其中Extended Yale B人脸数据库由2 414个正面人脸图像组成, 这些正面人脸图像是从38个具有不同光照的个体中采样的, 其中每人有65张图像.AR数据库包含超过4 000张126人(70名男性和56名女性)的面部图像, 包括不同的面部表情、光照强度与遮挡范围.
5.3.2 人脸识别实验
实验中, 将每张图像的大小调整为32×32像素, 这样每幅图像就被转化为了一个1 024维的向量, 并且让所有数据被归一化至均值为0. 为消除随机影响, 实验方法选择十折交叉验证法, 并在训练集图像中添加遮挡噪声块、高斯噪声和椒盐噪声三种不同类型的噪声以测试各算法的鲁棒性, 其中噪声块的位置是随机的, 遮挡噪声像素与图像像素数的比率为0.05$ \sim $0.10.图 4 (a)$ \sim $(b)分别列出了两个数据库的原始图像以及添加噪声后对应的图像.
图 4 Extended Yale B和AR人脸数据库原始图像与加入三种不同噪声后对应的图像(从上至下分别为黑白噪声块、高斯噪声和椒盐噪声Fig. 4 Original images in Extended Yale B and AR face database and the corresponding images with three different noise types (top to bottom are noise block, Gaussian noise and salt-and-pepper noise respectively)比较结果如图 5所示, 不同的噪声类型添加到同一数据库上表现出各不相同的实验结果. 从图中不难发现本文算法对不同维度降维后的分类性能总体上要优于其他的鲁棒PCA算法. 此外, 从图中可以得到两个结论: 1)特征空间中的分类结果要优于原始空间中的分类结果, 特别是当特征空间的维数增加时. 这是因为噪声可能发生在原始空间中, 而降维方法可以找到具有大部分判别信息的主成分空间并抛弃补空间中的冗余信息, 从而更准确和快速地分类. 2)在不同的情况下, RPCA-PW在总体上要优于其他方法. 因为RPCA-PW能够有效地排除少数异常样本的不良影响, 最终收敛到正确结果并且保持很高的识别精度, 所以当图像保留足够的空间信息时, 它具有更好的性能并且取得更高的平均识别率.
5.3.3 人脸重构实验
为了直观观察使用特征空间对遮盖噪声图进行重构之后的效果图, 本节在Extended Yale B和AR两个人脸数据库中进行人脸重构实验. 为了方便观察, 将每张图片的大小调整为64×64像素, 并在训练集图像中添加遮挡噪声块以测试各算法的鲁棒性, 遮挡噪声块的位置是随机的, 噪声像素与图像像素数的比率为0.05$ \sim $0.10. 实验中首先使用各算法提取出前30个特征值所对应的特征向量组成的特征空间, 再使用这些特征对遮盖噪声图像进行重构. 图 6是各算法的人脸重构效果图.
图 6 人脸重构效果图, 每一列从左到右依次是原图、PCA、PCA-L21、RPCA-OM、Angle PCA、HQ-PCA、$L{_{2, p}}$-PCA $p=0.5$、$L_{2, p}$-PCA $p=1$、RPCA-PW $p=0.5$、RPCA-PW $p=1$Fig. 6 Face reconstruction pictures, each column represents original image, PCA, PCA-L21, RPCA-OM, Angle PCA, HQ-PCA, $L_{2, p}$-PCA $p=0.5$, $L_{2, p}$-PCA $p=1$, RPCA-PW $p=0.5$ and RPCA-PW $p=1$ from left to right从图中可以看出, 经典PCA算法对原始图片的重构效果最差, 因为基于均方误差的PCA算法, 其重构性能易受噪声点影响, 导致质量差. PCA-$L$21、Angle PCA和RPCA-OM三种算法能够较为清晰地还原人脸的轮廓, 但是对于噪声块遮挡部位的还原效果并不理想. 而HQ-PCA与基于$L_{2, p}$-norm的RPCA-PW和$L_{2, p}$-PCA对于遮盖部分的还原更加清晰, 表现出对噪声有更好的鲁棒性. 而本文算法在降维过程中对于图片全局结构特征的提取能力强, 因此在图像重构中能够获得更为清晰的人脸轮廓, 尤其是对于遮盖部分的还原几乎不受影响.
5.3.4 算法时间比较结果
为了比较本文提出的RPCA-PW算法和其他算法的运行效率, 这里统计了各算法在不同数据集上的平均运行时间, 其中包括10个UCI数据集和2个人脸图像数据集. 实验结果如图 7所示.
图 7 各算法对不同数据集的平均时间比较结果Fig. 7 Comparison of average iteration time for different data sets by different algorithms从实验结果可以看出, PCA由于只需要进行一次特征分解, 因此运行时间远远低于其他的PCA算法; PCA-L21采用的是非贪婪优化算法, 整体上优化了迭代过程从而减少了运行时间; 相比之下, RPCA-PW虽然需要更长的平均迭代时间, 但是算法拥有更好的分类性能和鲁棒性, 而且从总体而言, 平均运行时间也要低于各算法的平均值.
5.3.5 算法收敛性实验
为了测试RPCA-PW算法的收敛性能, 本文进行如下的实验以验证算法在不同类型标准数据集上的收敛性能. 这里选取了6个标准数据集进行相关的收敛性实验(包括4个不同类型的UCI数据集与2个人脸图像数据集). 所提算法在标准数据集上的收敛曲线如图 8所示.
从图 8的实验结果可以看出, 相比较于只需要进行一次特征分解即可得到结果的传统PCA算法, RPCA-PW虽然需要更多的迭代次数, 但是通常能够保证在迭代十次之内收敛, 而且在迭代的过程中, 稳定性也没有受到破坏. 因此所提算法能够在仅仅增加少量计算量的前提下, 大大提高算法的鲁棒性和泛化性能.
6. 结论
本文提出了一种新的PCA模型, 称为鲁棒自适应概率加权PCA. RPCA-PW较经典PCA算法在鲁棒性上有了明显的改进, 具体表现在采用$L{_{2, p}}$模降低离群点对于模型的影响, 并且基于投影空间中数据的结构信息与重建误差之间的关系, 在提取主成分的过程中加强对识别关键的样本点的影响, 削弱那些与识别过程关系不大或者冗余大的样本点来提高精度. 从而在计算过程中能够自动识别异常点样本, 有效地降低了样本中离群点的干扰, 这一点在实际应用中也有着一定的意义. 此外, 所提出的模型可作为广义公式, 几种现有的算法都能作为其特例. 在人工数据集、UCI数据集和人脸数据库上与其他PCA方法进行了对比实验, 结果表明本文提出的模型拥有更好的识别精度, 并且对噪声有显著高的鲁棒性.
-
图 3 三种算法在双高斯人工数据集上的投影结果
Fig. 3 Projection result of three algorithms on two-Gaussian artificial dataset
图 4 Extended Yale B和AR人脸数据库原始图像与加入三种不同噪声后对应的图像(从上至下分别为黑白噪声块、高斯噪声和椒盐噪声
Fig. 4 Original images in Extended Yale B and AR face database and the corresponding images with three different noise types (top to bottom are noise block, Gaussian noise and salt-and-pepper noise respectively)
图 6 人脸重构效果图, 每一列从左到右依次是原图、PCA、PCA-L21、RPCA-OM、Angle PCA、HQ-PCA、$L{_{2, p}}$-PCA $p=0.5$、$L_{2, p}$-PCA $p=1$、RPCA-PW $p=0.5$、RPCA-PW $p=1$
Fig. 6 Face reconstruction pictures, each column represents original image, PCA, PCA-L21, RPCA-OM, Angle PCA, HQ-PCA, $L_{2, p}$-PCA $p=0.5$, $L_{2, p}$-PCA $p=1$, RPCA-PW $p=0.5$ and RPCA-PW $p=1$ from left to right
图 7 各算法对不同数据集的平均时间比较结果
Fig. 7 Comparison of average iteration time for different data sets by different algorithms
表 1 实验中使用的UCI数据集
Table 1 UCI data sets used in the experiment
数据集 维数 类别数 样本数 Australian 14 2 690 Cars 8 3 392 Cleve 13 8 303 Solar 12 6 323 Zoo 19 7 101 Control 60 6 600 Crx 15 2 690 Glass 9 6 214 Iris 4 3 150 Wine 13 3 178 
下载: 导出CSV
表 2 UCI数据集上各算法的平均分类正确率(%)
Table 2 Average classification accuracy of each algorithm on UCI data sets (%)
数据集 Australian Cars Cleve Solar Zoo Control Crx Glass Iris Wine PCA 57.32 69.27 52.16 64.11 96.00 91.83 54.93 74.35 96.00 73.04 PCA-$L$21 62.41 69.17 52.74 64.44 95.60 92.50 53.39 75.33 97.33 74.13 RPCA-OM 63.04 69.93 52.16 65.27 95.00 92.83 56.96 74.35 96.00 74.15 Angle PCA 60.39 69.43 52.16 65.60 94.00 84.28 59.59 73.94 95.53 74.15 MaxEnt-PCA 60.14 69.17 52.45 64.76 95.10 92.15 59.32 74.42 95.33 73.59 HQ-PCA 60.77 69.27 52.46 65.46 95.80 91.50 60.87 76.16 92.00 75.55 $L{_{2, p}}$-PCA $p=0.5$ 60.68 69.60 52.84 65.42 93.40 92.10 60.29 73.56 96.47 73.59 $p=1$ 62.39 69.58 52.16 64.51 94.90 92.50 59.43 73.73 96.67 73.59 $p=1.5$ 62.81 69.43 52.16 65.28 95.00 92.50 58.20 75.57 96.33 73.04 $p=2$ 62.32 69.43 52.16 64.11 96.00 91.83 54.93 75.82 96.00 73.59 RPCA-PW $p=0.5 $ 63.77 71.21 53.76 66.85 95.00 92.50 58.84 74.35 95.33 74.15 $p=1 $ 63.04 69.43 52.49 65.94 95.00 91.67 60.14 73.94 96.00 74.15 $p=1.5$ 62.17 69.43 52.16 64.72 95.00 97.83 61.16 76.28 96.67 74.15 $p=2$ 62.32 69.43 52.16 64.11 96.00 92.33 54.93 75.82 96.00 73.59
下载: 导出CSV
表 3 UCI数据集上各算法的重建误差
Table 3 Reconstruction error of each algorithm on UCI data sets
数据集 Australian Cars Cleve Solar Zoo Control Crx Glass Iris Wine PCA 197.53 1 979.82 5.47 2.97 1.43 115.06 6 265.42 37.91 0.67 24.49 PCA-$L$21 197.21 1 979.16 6.90 2.90 1.56 132.84 6 545.72 38.59 1.56 34.44 RPCA-OM 193.23 1 977.98 5.61 2.65 1.51 108.13 5 684.38 38.64 0.64 24.85 Angle PCA 197.96 1 981.34 13.27 2.95 2.04 123.62 6 583.82 38.42 0.59 25.85 MaxEnt-PCA 203.82 1 976.70 6.24 2.61 1.44 113.01 6 805.98 38.12 0.58 25.01 HQ-PCA 195.79 1 929.26 5.92 2.37 1.39 131.35 6 987.68 36.38 4.31 25.85 $L_{2, p}$-PCA $p=0.5$ 193.29 1 978.76 9.22 2.93 2.05 106.69 6 601.74 38.33 1.04 26.14 $p=1$ 193.71 1 978.33 5.60 2.75 1.72 108.06 6 588.17 38.37 0.84 25.44 $p=1.5 $ 193.50 1 977.93 5.50 2.69 1.44 109.69 6 807.38 37.82 0.72 25.05 $ p=2$ 193.53 1 977.82 5.47 2.97 1.43 115.06 5 865.42 37.91 0.67 24.49 RPCA-PW $p=0.5$ 192.93 1 976.94 5.75 2.95 1.57 106.11 6 467.83 38.43 0.52 24.12 $p=1$ 193.27 1 979.96 6.84 2.84 1.83 110.46 6491.19 38.17 0.70 24.36 $p=1.5$ 193.36 1 977.82 5.06 2.83 1.46 110.45 6 073.11 37.91 0.71 25.26 $p=2$ 193.53 1 977.82 5.47 2.97 1.43 115.06 5 865.42 37.91 0.67 24.49
下载: 导出CSV
-
[1] Jolliffe I. Principal Component Analysis. New York: Springer-Verlag, 1986. 115-128 [2] 高全学, 潘泉, 梁彦, 张洪才, 程咏梅. 基于描述特征的人脸识别研究. 自动化学报, 2006, 32(3): 386-392 http://www.aas.net.cn/article/id/15824Gao Quan-Xue, Pan Quan, Liang Yan, Zhang Hong-Cai, Cheng Yong-Mei. Face recognition based on expressive features. Acta Automatica Sinica, 2006, 32(3): 386-392 http://www.aas.net.cn/article/id/15824 [3] 张先鹏, 陈帆, 红杰. 结合多种特征的高分辨率遥感影像阴影检测. 自动化学报, 2016, 42(2): 290-298 doi: 10.16383/j.aas.2016.c150196Zhang Xian-Peng, Chen Fan, He Hong-Jie. Shadow detection in high resolution remote sensing images using multiple features. Acta Automatica Sinica, 2016, 42(2): 290-298 doi: 10.16383/j.aas.2016.c150196 [4] Gao Q X, Ma L, Liu Y, Gao X B, Nie F P. Angle 2DPCA: A new formulation for 2DPCA. IEEE Transactions on Cybernetics, 2018, 48(5): 1672-1678 doi: 10.1109/TCYB.2017.2712740 [5] Koren Y, Carmel L. Robust linear dimensionality reduction. IEEE Transactions on Visualization & Computer Graphics, 2004, 10(4): 459-470 doi: 10.1109/TVCG.2004.17 [6] Schölkopf B, Smola A, Müller K R. Nonlinear component analysis as a kernel eigenvalue problem. MIT Press, 1998, 10(5): 1299-1319 http://icesjms.oxfordjournals.org/external-ref?access_num=10.1162/089976698300017467&link_type=DOI [7] 李春娜, 陈伟杰, 邵元海. 鲁棒的稀疏$L_{p}$模主成分分析. 自动化学报, 2017, 43(1): 142-151 https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO201306024.htmLi Chun-Na, Chen Wei-Jie, Shao Yuan-Hai. Robust sparse $L_{p}$-norm principal component analysis. Acta Automatica Sinica, 2017, 43(1): 142-151 https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO201306024.htm [8] Xu L, Yuille A L. Robust principal component analysis by self-organizing rules based on statistical physics approach. IEEE Transactions on Neural Networks, 1995, 6(1): 131-143 doi: 10.1109/72.363442 [9] Ke Q, Kanade T. Robust ${\rm{L}}_1$-norm factorization in the presence of outliers and missing data by alternative convex Programming. In: Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego, CA, USA: IEEE, 2005, 1: 739-746 [10] Kwak N. Principal component analysis based on L1-norm maximization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(9): 1672-1680 doi: 10.1109/TPAMI.2008.114 [11] Nie F, Huang H, Ding C, Luo D, Wang H. Robust principal component analysis with non-greedy L1-norm maximization. In: Proceedings of IJCAI International Joint Conference on Artificial Intelligence. Barcelona, Catalonia, Spain: AAAI, 2011, 22(1): 1433 [12] Ng A Y. Feature selection, L1 vs. L2 regularization, and rotational invariance. In: Proceedings of the 21st international conference on Machine learning. Banff, Canada: ACM, 2004, 78 [13] He R, Hu B, et al. Principal component analysis based on non-parametric maximum entropy. Neurocomputing, 2010, 73(10): 1840-1852 http://www.sciencedirect.com/science/article/pii/S092523121000144X [14] He R, Hu B, et al. Robust principal component analysis based on maximum correntropy criterion. IEEE Transactions on Image Processing, 2011, 20(6): 1485-1494 doi: 10.1109/TIP.2010.2103949 [15] He R, Tan T, Wang L. Robust recovery of corrupted low-rank matrix by implicit regularizers. IEEE Transactions on Patteren Analysis and Machine Intelligence, 2014, 36(4): 770-783 doi: 10.1109/TPAMI.2013.188 [16] Ding C, Zhou D, He X F, Zha H Y. R1-PCA: Rotational invariant L1-norm principal component analysis for robust subspace factorization. In: Proceedings of the 23rd International Conference on Machine Learning. Pittsburgh, USA: ACM, 2006. 281-288 [17] Nie F, Yuan J, Huang H. Optimal mean robust principal component analysis. In: Proceedings of 31st International Conference on Machine Learning. Beijing, China: ACM 2014. 2755-2763 [18] Nie, F, Huang, H. Non-greedy L21-norm maximization for principal component analysis. arXiv 2016, arXiv: 1603.08293 [19] Wang Q, Gao Q, Gao X, Nie F. ${{\rm{L}}_{2, p}}$-norm based PCA for image recognition. IEEE Transactions on Image Processing, 2018, 27(3): 1336-1346 doi: 10.1109/TIP.2017.2777184 [20] Wang Q, Gao Q, Gao X, Nie F. Angle principal component analysis. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence. Melbourne, Australia: AAAI, 2017. 2936-2942 [21] Liu Y, Gao Q, Miao S, et al. A non-greedy algorithm for L1-norm LDA. IEEE Transactions on Image Processing, 2016, 1-1 http://ieeexplore.ieee.org/document/7707468 [22] Guo Y F, Li S J, Yang J Y, Shu T T, Wu L D. A generalized Foley--Sammon transform based on generalized fisher discriminant criterion and its application to face recognition. Pattern Recognition Letters, 2003, 24(1-3): 147-158 doi: 10.1016/S0167-8655(02)00207-6 [23] Cover T, Hart P. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 1967, 13(1): 21-27 doi: 10.1109/TIT.1967.1053964 期刊类型引用(4)
1. 管耀，王清辉，冯进，杨清，石磊. 基于机器学习的蚀变火成岩测录井综合岩性识别——以南海北部珠江口盆地惠州26-6井区为例. 吉林大学学报(地球科学版). 2024(01): 345-358 . 
百度学术2. 尚歌，王雁飞. FBG传感器在起重机械局部损伤监测中的应用研究. 传感技术学报. 2024(07): 1285-1289 . 百度学术3. 裴正中，赵旭俊. 基于同构化角度的离群检测方法. 计算机工程与设计. 2024(12): 3622-3630 . 百度学术4. 梁志贞，张磊. 面向Kullback-Leibler散度不确定集的正则化线性判别分析. 自动化学报. 2022(04): 1033-1047 . 本站查看其他类型引用(2)
-
下载:
计量
- 文章访问数: 1549
- HTML全文浏览量: 299
- PDF下载量: 253
- 被引次数: 6
