高维数据的低维表示综述 - 图文(2)

局分布。然而对于嵌入在高维空间中具有非线性流形结构的数据，PCA很难学习出隐含在数据集中的低维流形结构。

PCA假设数据之间的关系是线性的。它在保存原始高维数据协方差结构的基础上计算低维表达，也就是最大化总体方差。它的目标函数可以写为：

N2UPCA=argmaxUPCAN?i?1Tyi?ym2

?argmaxtr(UPCASTUPCA)s.t.UUPCATTPCA?argmaxUPCA?i?1mUPCA(xi?x)?1NTmUPCA?Id其中，

Ny?yi，

xm?1N?xi，且

ST为总体离散矩阵：

?dST=?(xi?x)(xi?x)i=1TUPCA=Id，其中Id为d。对转换矩阵做尺度约束UPCA单

位矩阵。则目标函数可以写为：

argmaxtr(UPCASTUPCA)UPCATTUPCA，s.t.UPCA?Id

上式问题可以转化为ST的标准的特征值问题：PCA的最优转换矩阵为ST的d个最大的特征值所对应的d个m维特征向量。

2.线性判别法(Linear Discriminant Analysis LDA) [2]

其基本思想是投影，首先找出特征向量，把这些数据投影到一个低维的方向，使得投影后不同的组之间尽可能的分开，而同一组内的的样本比较靠拢，然后在新空间中对样本进行分类。

通过最小化类内离散矩阵SW的秩而最大化类间离散矩阵SB的秩，来寻找一个子空间来区分不同的类别。SW和SB分别定义如下：

CNiSW=?i=1?(xj?1(i)j?m(i))(xj(i)?m(i))T

CSB??i?1Ni(m(i)?m)(m(i)?m)

T其中，Ni是第i个类中样本的个数；xj(i)是第i个样本中第j个样本。m(i)为第i个类的质心；m用来表示所有样本的质心，C为样本的类别数。LDA则有以下的优化准则：

argmaxtr(Utr(UTLDATLDASBUSWULDALDA))

s.t.ULDAULDA?IdT

上述的优化可以转化为求解一个广义的特征分解问题：

SB???SW?

且最优的解为d个特征向量其对应于d个最大的非零特征值。

3.投影寻踪(Projection Pursuit PP) [3]

基本思想主要来源人们对低维空间几何图形的直观理解，它包含俩个方面的含义：其一是投影(Projection)，把高维空间中数据投影到低维空间；其二是寻踪(Pursuit)，利用低维空间投影数据的几何分布形念，发现人们感兴趣的数据内在特征和相应的投影方向，同时排除与数据结构和特征无关的或关系比较小的变量干扰。

4. 多维尺度分析(Multidimensional Scalar ，MDS) [4]

主要思想是：根据数据点间的欧氏距离，构造关系矩阵，为了尽可能地保持每对观测数据点之间的欧氏距离，只需对此关系矩阵进行特征分解，从而获得每个数据在低维空间中的低维坐标。

算法步骤：

1计算观测空间中任意两点欧式距离，构造n阶平方欧式距离矩阵A 2将矩阵A进行双中心化计算，即计算B若设n?n阶矩阵H=I?ee/nT??12HAH。

（常称之为中心化矩阵），将矩阵H左乘和右

乘A的两边（常称之为双中心化）。

3计算低维坐标Y。即将B奇异值分解，设B的最大的d个特征值

?=diag(?1，??d)，对应特征向量U?[v1,?vd]，则

d维坐标为Y??UT。

（二）非线性

流形学习旨在发现高维数据集分布的内在规律性，其基本思想是：高维观测空间中的点由少数独立变量的共同作用在观测空间张成一个流形，如果能有效地展开观测空间卷曲的流形或发现内在的主要变量，就可以对该数据集进行降维。