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

域点，构成矩阵Xi?[xi,?,xi]。

1k第二步：局部线性投影。对于每个样本点的邻域

Xi(I?ee/k)的最大

TXi，计算中心化矩阵

d个奇异值对应的左奇异向量，并将这d个左奇异向量组成

矩阵Qi。 1由Xi(I?ee/k)?U?VTQi计算得出左奇异向量U，取出U的前d列构成矩阵Q（i即为xi点的切空间的近似）；

2计算各个邻域点在该切空间Qi的投影：

?i?QiXi(I?ee/k)?[?1,?,?k]

TT(i)(i)?(i)j?Qi(xi?xi)

Tj第三步：局部坐标系统的排列。对每个邻域的局部切空间坐标

?i?(?1,?2,?,?k)(i?1,2,?,N)(i)(i)(i)，构造转换矩阵Li??i?R?d?d。通过最小化

?Ti(I?ee/k)?Li?iT2的求解，最后化解可通过计算一个矩阵从第2小到第d+1

小的特征值所对应的特征向量。其中?i?是?的广义Moor-Penrose逆。

优缺点：LTSA能够有效地学习体现数据集低维流形结构的整体嵌入坐标，但它也存在两方面的不足：一方面算法中用于特征值分解的矩阵的阶数等于样本数，样本集较大时将无法处理；另一方面算法不能有效处理新来的样本点。（12）对此，提出了一些相应的改进算法。

但LTSA也面临着同HLLE类似的一些问题：LTSA所反映的局部结构是它的局部d维坐标系统，因此，由于噪声等因素的影响，当数据集的局部低维特征不明显或者不是d维的时候，它的局部邻域到局部切空间的投影距离往往并不小。此时，构造的重建误差也不会小，这样LTSA可能就无法得到理想的嵌入结果。此外，LTSA对样本点的密度和曲率的变化的影响比较敏感，样本点的密度和曲率的变化使得样本点到流形局部切空间的投影产生偏差，而LTSA构造排列矩阵的模型并没有将这种偏差计入考虑范围。这使得对于样本点密度和曲率变化较大的流形，LTSA的嵌入结果可能会出现扭曲现象。

线性局部切空问排列(LLTSA)

针对LTSA算法不能为新的测试样本提供一个明确的从高维到低维的映射，也就是所谓的“Out of Sample”问题。提出了一个新的线性算法，线性局部切空问排列(LLTSA)[20]。该算法运用切信息作为数据的局部表达，然后将这些局部信息在可以用线性跌射得到的低维空间中排列。它先将每一个样本点邻域的切空间表示为流形的局部几何，再经线性映射实现样本数据从高维空间降维到低维空间，最终将整体嵌入坐标的求解问题转化为矩阵的广义特征值的求解问题。

算法步骤：

1近邻选择，构造邻接图G 2计算局部切坐标? 3计算投影向量：

a求低维坐标对应近邻重建的目标函数最小化，即

??Min?YiHk?Li?i?Li,Tii?T?S.t.:YY?I2

Hk是k阶中心化矩阵且Hk?I?ee/k。

Tb代入线性变换Yi??(XiH)，且由HT22?H得

?T?Min??(XiHk)?Li?i?Li,Tii?TT?S.t.:?XX??I

c

??M?in?XHBHX??TT??S.t.:?XHX??IB?SWWSTTTT

S?[S1,?,Si,?,Sn]使得YSi?Y，并且i?其中,近邻选择矩阵

W?diag(W1,W2,?,Wn),且Wi?Hk(I??i?i)。

d求解下列广义特征方程的d个最小特征值对应的特征向量作为d个投影向量：

XHBHX?=?XHX?TT

故由上述特征方程的d个最小特征值?1,?2,?,?d对应特征向量?1,?2,?,?d，

构成保持近邻重建特性的线性变换矩阵。

数据样本的类别信息对于入脸识别是非常重要的资源，但是LLTSA算法是非监督的学习方法，没有充分利用类别信息。为了提高算法的识别能力，需要对LLTSA算法的目标函数进行修改，以增加有关判别信息的限定，使原来无监督的学习方法发展为有监督的学习方法。而且为了提高数据的重建能力，算法应将解出的人脸子空间正交化，可称这种流形学习算法为正交判别的线性局部切空间排列(orthogonal discriminant linear local tangent space alignment，ODLLTSA)。[21]

由于用于特征值分解的矩阵的阶数等于样本点数，因此，当样本点集较大时将无法处理，此外，该方法不能有效处理新来的样本点。一种基于划分的局部切空间排列方法（partitional local tangent space alignment ,PLTSA）[22]被提出以改善这些缺点，它建立在主成分分析算法和LTSA方法的基础上，解决了主成分分析算法不能求出整体低维坐标和 LTSA 中大规模矩阵的特征值分解问题，能够有效处理新来的样本点。

PLTSA是一种非监督的流形学习方法，不能充分利用数据的类别信息，而在人脸识别中数据样本的类别信息是非常重要的资源。为了提高算法的识别能力，需要对PLTSA算法进行改进，以增加判别信息的限定，使无监督的学习方法发展为有监督的学习方法。因此提出了一种基于划分的有监督局部切空间排列法（partitional supervised local tangent space alignment PSLTSA）[23]。

4.拉普拉斯特征映射法 LE (Laplacian Eigenmap) [24]

LE方法将微分流形、谱图论的知识应用于降维之中，使人们对降维过程的认识产生了又一个新的飞跃，拓展了实际中降维方法的应用。

基本思想是：在高维空间中距离相隔很近的点投影到低维空间中像也应该相距很近，最终求解归结到求拉普拉斯算子的广义特征值问题。（8）实际上是使用有权图的 Laplace矩阵来逼近 最优投影的降维算法

算法步骤：

第一步，构造近邻图G。在数据集X中，计算每个样本点xi同其余样本点之间的欧式距离，构造近邻图。寻找相对于每个样本点xi的欧式距离最近的k个

RD 空间中的 Laplace Beltrami 算子，以期达到

样本点规定为所求点的近邻点，若数据点xi与xj是邻接的，则图中点xi与xj之间存在一条边。

第二步，选择权值，构造权值矩阵W。在近邻图中，为每一条边选择一个权值wi,j，构造权值矩阵W。权值的选择有两种选择方式：

1）若点xi与xj是邻接的，则设边的权值为wi,jwi,j=0；t

?exp(?||xi?xj||/t)，否则设

2是一个比例参数。

2）若点xi与xj是邻接的，则设变得权值为wi,j=1，否则设wi,j=0。 在方法1）中，需要选择比例参数t，方法2）不用选择比例参数t，比较简单。

第三步，进行特征映射，计算d维嵌入。对数据集X构造的近邻图G，映射到一条直线，用y表示，使得邻接的点尽可能的靠近。设y?(y1,y2,?,yN)T是

一个未知的投影，可以通过在一定约束下，使得下面的目标函数达到最小来求解。

?ij(yi?yj)wij

2用D表示对一个对角矩阵，它的每个对角元素为权值矩阵W的每行所有元素的和，即Di,i??jwi,j2i，L=D-W是邻接图的Laplacian矩阵。对任意的y有

2T?ij(yi?yj)wij?2?(yij?yj?2yiyj)wij?2yLy

给定约束条件yTDy=1，以消除坐标尺度对映射y的影响，最小化上式的和函数，利用矩阵迹的性质和拉格朗日乘子法，即可求解。相当于利用下式计算特征值和特征向量的问题Ly??Dy

上述特征方程的最小的d个非零特征值对应的特征向量y1,y2,?,yd，则数据X的低维嵌入表示为Y?[y1,y2,?,yd]T

LE是局部的非线性方法，其突出特点是与谱图理论有着很紧密的联系。从算法描述中可以看到，拉普拉斯映射和LLE算法类似，待定参数相同，求解的是稀疏矩阵的广义特征值问题，它能使输入空间中离得很近的点在低维空间也离

得很近，故可用于聚类。（12）缺点类似LLE。

LPP局部保留投影（Locality preserving projection，LPP）

LPP局部保留投影（Locality preserving projection，LPP）作为LE的线性化是其中最早提出的算法。[25]

LPP算法的主要问题在于建立k近邻域图，使它能很好地表现 …… 此处隐藏：2368字，全部文档内容请下载后查看。喜欢就下载吧 ……