线性降维方法优化

一张1024×1024像素的8位灰度图像需要大概1M字节的存储空间，并且，从图像中提取出的颜色、纹理、形状等视觉特征，所构成的特征向量其维数往往达到几百维，造成“维数灾难”的问题，不利于图像的检索、压缩、模式识别等应用。特征降维技术的提出正是为了解决“维数灾难”的问题。

传统的特征降维方法大多是基于线性变换技术，如:主成分分析方法(Principal Component Analysis)、独立成分分析方法(Independent Component Analysis)、典型相关性分析(Canonical Correlation Analysis)、奇异值分解(Singular Value Decomposition)、多维尺度分析(Multi-dimensional Scaling)，等等。近些年来，非线性的特征降维技术成为图像特征分析领域的新热点。线性和非线性的特征降维技术将高维向量的图像表达模型转换为较低维数的几何结构，去除了噪音，同时保持了一些原有的信息，如:内积不变性、距离不变性、相关系数不变性，等等。

需要注意的是，盲目的维数约减可能会导致有用信息的丢失。然而，目前还没有直接的算法用于计算最佳维度，一般是在后继的实验中利用检索效率等指标来衡量维数缩减的最优性。

1.主成分分析

在统计学中，主成分分析方法^[2](Principal Component Analysis，PCA)是一种简化数据集的线性变换技术。主成分又称为主分量、主元素，该方法研究如何通过原来变量的少数几个线性组合，来描述随机向量的方差，广泛应用于特征降维和数据压缩等领域。

PCA方法的核心思想是将高维向量变换到一个新的坐标系下，同时满足，数据集中任何数据投影的最大方差在第一个坐标轴(又称为第一主成分)上，第二大方差在第二个坐标轴上，依此类推。更进一步地，PCA方法在降低向量维数的同时，保留了低阶主成分、忽略高阶主成分，从而保持了特征向量中对方差贡献最大的特征值。其原理和数学推导描述如下:

设列向量xp＝(x1，x2，…，xp)T是从图像中提取的p维特性向量，通过正交投影到较低维数的q维子空间S，得到列向量xq＝(x1，x2，…，xq)T，(q＜p)，对应数学公式为

式中，F表示正交投影矩阵；T表示向量的转置。主成分分析给出了q维子空间S的定义为S＝span{s1，s2，…，sq}，以及矩阵F的选择方法，如下所示:

式中，Sq＝[s1，s2，…，sq]，且s1，s2，…，sq为向量x的共轭矩阵~X的前q个标准化特征向量，也称为基向量。

综合上述公式可以得到

如果令上面公式中的(s1，s2，…，sq)Txp＝(κ1，κ2，…，κq)T，则可以得到

于是，向量xp在q维子空间S中的坐标xq是基向量s1，s2，…，sq的线性组合。那么在保存新坐标的时候，只需要存储对应的线性组合系数，而基向量是整个样本集公用的。从能量的角度来看，投影后的向量xq只保留了原向量一定比例的能量(或信息)，其余部分作为误差被舍弃。可以推出，误差的大小与q的选择直接相关，在实际应用中，并没有一定的标准来计算q的值，通常是根据实际情况进行取舍。例如:在基于内容的图像检索应用中，可以根据检索性能的高低来决定最优的q值。

PCA方法不但降低了数据维数，而且提取成分与原始数据的误差达到均方差最小。PCA方法在各个学科和工程领域中获得了广泛地应用，包括:人脸识别、图像检索、图像压缩等。

2.独立成分分析

独立成分分析^[3](Independent Component Analysis，ICA)起源于盲源信号分离(Blind Source Separation，BSS)的研究，BSS主要研究在未知信号混合模型的情况下，从观测到的混合信号中分离出源信号的过程。ICA的基本思想是将观测到的多通道信号，根据统计独立的原则，使用优化算法将其分解为若干个独立分量，观测信号可以用这些独立分量进行线性重建。

ICA方法使用基于高阶统计特性的分析方法，在很多应用领域中得到了较好的应用，如:音频信号分离、人脸识别、生物医学信号分析、图像的视觉特征降维等领域。PCA方法强调分解出来的各个分量是彼此不相关的，而ICA方法则要求各分量相互独立。目前，ICA方法具有比PCA、SVD(详见3.3.4小节)方法更为广泛的应用价值，是一种比较优越的信号处理技术。ICA方法的形式化描述如下所示。

假设观测信号X和未知的源信号S之间有如下关系:

式中，观测信号X包括m个样本；S包括n个信号源；A为未知的混合矩阵，表示观测信号X是由源信号S中的独立分量线性组合而成。ICA方法就是要找到一个分离矩阵W，使得观测信号经过分离后得到矩阵Y＝WX，其中，Y的各个分量尽可能地相互独立，也就是说，Y是源信号S的估计值。

在求解上述问题时，由于源信号和混合矩阵均未知，如果无其他前提条件，而仅由观测信号估计出源信号，则这种盲分离问题就会有很多解。因此，需要对源信号和混合矩阵增加约束条件:①观测信号的数目m不小于源信号的数目n，为了方便起见，一般取m＝n；②混合矩阵A为可逆的；③源信号S的各分量相互统计独立，且最多只有一个分量服从高斯分布。

在上述假设的基础上，ICA算法的基本原理可以简单归纳为:根据独立性度量的准则建立目标函数，使得分离出的独立分量最大限度地逼近各个源信号。针对ICA问题的求解，已经有学者提出了不同的算法，这些算法的主要区别在于独立性度量准则的选取，以及目标函数的优化方法。最早的ICA算法是在神经网络领域由Jutten和Herault提出来的，采用了带有反馈结构的神经网络，缺点在于收敛性不够理想。目前，ICA算法主要包括信息最大化法、互信息最小方法以及最大似然估计方法等。(www.xing528.com)

3.典型相关性分析

典型相关性分析(Canonical Correlation Analysis，CCA)方法源于经典的多元统计理论，用于分析从两组不同的信号源得到的观测信号之间的内在统计关系。两个信号源X与Y之间的相关性定义如下:

设有n个样本、p个变量组成的观测信号，记为X(n×p)，另有n个样本、q个变量组成的观测信号Y(n×q)，以最大限度地提取X与Y之间相关性的主要特征为准则，从X中提取组合变量L，从Y中提取组合变量M，如下所示:

式中，Wx，Wy为空间特征向量，又称为典型变量。上述公式把具有较多个变量的观测信号X与Y之间的相关化为较少组合变量L与M间的相关，通过Wx，Wy的数值分布来确定X与Y的空间相关分布形式，而Wx，Wy的数值大小则表示了所对应变量的重要程度。于是问题归结为如何求解典型变量Wx，Wy。

定义相关系数为ρ＝r(L，M)，计算公式如下:

式中，Cxy表示X(n×p)和Y(n×q)构成的协方差矩阵。

接着求取相关系数ρ的最优解，即在下列约束条件下求最优值:

求解方法为:使用拉格朗日乘子法构造G函数

根据相关系数r(L，M)＝r(M，L)，可以证明λ1＝λ2，于是从上述方程组转换为

于是，最优化求解问题转换为形如Ax＝λBx的广义特征根问题，求解出特征根，即可得出Wx，Wy的值。

4.奇异值分解

主成分分析方法在计算过程中与奇异值分解(Singular Value Decomposition，SVD)方法有着密切的联系，下面介绍SVD方法的基本原理。假设X为m×n阶的矩阵，则X的奇异值分解表示如下

式中，U，V分别是XXT和XTX的特征向量构成的矩阵；Σ是由XTX的特征根组成的对角阵。取前r个非零的最大特征根所对应的U，V，Σ，对X进行逼近，可以得到

X＇是秩为r的X在最小二乘意义上的近似矩阵，并提取了X中的主要结构，消除了噪声。相应地，SVD方法计算低维子空间的映射方式为X*(i，∶)≈X(i，∶)·(Vn×r)，其中X(i，∶)表示矩阵X的第i行。

5.多维尺度分析

多元尺度分析(Multi-dimensional Scaling，MDS)方法在已知样本之间的距离矩阵的情况下，求解一个低维的子空间，以及样本在子空间中的坐标值，使得样本在这个低维坐标系中的距离与之前已知的距离矩阵中的值保持一致。假设矩阵D＝[dij]，i∈[1，…，n]，j∈[1，…，n]表示样本之间的距离矩阵，其中n为样本个数，MDS方法主要包括以下几个步骤:

(2)计算内积矩阵:B＝XXT＝[bij]＝[aij-ai.-a.j+a..]，其中X＝[x1，…，xn]T表示n个样本在p维的子空间中的坐标构成的n×p矩阵，且有

(3)计算矩阵B的n-1个特征值λ1，…，λn-1，及其对应的特征向量，进行归一化操作后表示为υ1，…，υn-1；

(4)求得样本点在p维子空间中的坐标xik＝υkj；i＝1，…，n；k＝1，…，p。