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

SLLE算法在计算点与点之间的距离时有两种方法。

SLLE1：第一种方法是采用下式来修正点与点之间的距离公式如下所示

D??D??max(D)?

其中：D?是计算后的距离D是最初采用的距离；max(D)是表示类与类之间的最大距离；?取0或者1，当两点属于同类时，?取为0，否则取1；?是控制点集之间的距离参数，??[0,1]，是一个经验参数。当?取为零时，此时的SLLE

和 LLE 算法相同。这个方法引入了一个参数?，它是一种经验参数，对实验的结果有很大的影响，下面介绍一种非参数的方法。

SLLE2：求解点与点之间的距离，目的在于是寻找样本点的近邻点。SLLE2的方法在寻找近邻点时，不是在全局样本中寻找近邻点，而是在每个点所在类的样本中寻找近邻点，也就是说，在类内中寻找样本点的近邻点。这个方法固然没有采用参数的方法，但是如果某一类的样本个数小于k，那么这种方法必将失败，则每个类的样本个数在相当多的情况下 可以采用这种方法。

RLLE算法[8]

当在做聚类分析且采用LLE算法对数据进行降维时，如果数据中存在着许多离异点的情况，那么降维后的结果将会发生变异，通常是第一维或者是第二维的数据发生跳跃式的变化，或者分布在某几条直线上，这将会给聚类带来很大的麻烦，其实当离异点超过LLE算法中的k值时，这种现象将会发生。

A.Hadid和M.Pietik?inen提出一种 Robust Locally Linear Embedding (RLLE)方法。它是针对存在有离异点的情况下，对样本的一种无监督的非线性降维方法。

邻域保持嵌入算法NPE算法[9]

NPE从本质上说是局部线性嵌入(local linear embedding，LLE)的线性逼近。给定数据集X，采用与LLE相同的方法构建数据集上的近邻图。NPE针对LLE算法的out-of-sample问题提出的，该算法通过最小化局部相似离散度寻找投影方向，有效的保持了数据间的相似几何结构，取得了不错效果，已被广泛地应用到文档分析、机器学习和模拟识别等领域。NPE假定每个局部近邻都是线性的。

算法步骤：

1近邻选择，构造邻接图G 2计算近邻重建权W

3计算投影向量：

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

nk??Min?yi??Wijyij?Yi?1j?1?T?S.t.:YY?I2

b代入线性变换y??x,得

Tnk?TT?Min?xi??Wijxij???i?1j?1?TT?S.t.:?XX??I2

c

??M?in?XMX??TT??S.t.:?XX??ITTT

其中M?(I?W)(I?W)d求解下列广义特征方程的d个最小特征值对应的特征向量作为d个投影向量：

XMX?=?XX?TT

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

?1,?2,?,?d，构成保持近邻重建特性的线性变换矩阵。

缺点：NPE在保持数据空间的局部相似信息时，不能较有效地保持差异信息，特别是高维非线性数据间的差异信息。如在人脸识别应用中，人脸图像的识别容易受光照、表情等非理想条件变化的影响，这些非理想情况会使得同一个人的不同图像之间的差异大于不同人图像之间的差异，从而导致识别错误。

NPE算法通过式xi?yi?AxiT实现了数据到新空间的线性变换。显然，这

种线性变换实现的数据变换是一种显式形式，这样就解决了LLE算法没有显式映射函数的问题。

LLE算法是非监督的学习方法，没有充分利用类别信息，为了提高算法的识别能力，于是有了LLE的正交线性化扩展，orthogonal neighborhood preserving projections(ONPP)[10][ 11]。

张长水等人[12]在LLE的基础上提出一种从低维嵌入空间向高维空间映射

的方法，并在多姿态人脸图像的重构实验中得到有效的验证，进一步完善了非线性降维方法。

2. 等距映射法 ISOMAP (Isometric Map) [13]

ISOMAP认为当数据集具有嵌入流形结构时，可以根据保距映射来获得观测空间数据集在低维结构的对应描述。

基本思想：ISOMAP通过测地线距离来描述各点之间的相互关系，在全局意义下，通过寻找各点在图意义下的最短路径来获得点与点之间的距离，然后利用经典的MDS算法得到低维的嵌入坐标。因此．ISOMAP可认为是MDS算法的变种。（5）

图3 ISOMAP算法示意图

使用前提条件：高维数据所在的低维流形与欧氏空间的一个子集是整体等距的；与数据所在的流形等距的欧氏空问的子集是一个凸集。

主要步骤：

(1)构造局部邻域。首先对数据集Xxi??x1,x2,?,xn?，计算任意两个样本向量

和xj的欧式距离dx(xi,xj)，将每一个点与所有的点进行比较，当两点之间的距

离小于固定的半径?（或i是j的K-邻域）时，我们就认为它们是相邻的，将其连接起来，该边的长度dx(xi,xj),则得到邻域图G。

(2)计算最短距离。在图G中，设任意两个样本向量xi和xj之间的最短距离为dG(xi,xj)。若xi和xj之间存在连线，dG(xi,xj)的初始值为dx(xi,xj)，否则令

dG(xi,xj)??。对所有的k=1,2,…,n

dG(xi,xj)?min{dG(xi,xj),dG(xi,xk)?dG(xk,xj)}

这样得到矩阵DG?{dG(xi,xj)}，它是图

G中所有点对的最短路径组成的。

(3)构造d维嵌入。用MDS方法构造一个保持本征几何结构的d维嵌入到空间Y。

?(DG)??H*(DG)*H22

H是与DG同阶的单位矩阵，对?(DG)进行特征分解，取最大的前d个特征值?1,?2,?,?d和对应的特征向量V1,V2,?,Vd，令Vpi为第p个特征向量的第i个成分，则对应的数据低维表示为yi??pVp1/2i。

优点： 适用于学习内部平坦的低维流形，ISOMAP结合了线性算法(如PCA和MDS)的主要特征——计算的有效性、全局的优化性和渐进收敛性等。这种用测地距离来代替传统的欧氏距离的方法，可更有效的在低维空间来表达高维空间的数据，减少降维后损失的数据信息。

缺点：不适于学习有较大内在曲率的流形。在噪声干扰下，Isomap用于可视化会有不稳定现象，取较大的邻域会产生短路现象，即低维流形中不同邻域部分的点投影后出现明显的混杂现象。选取较小的邻域，虽然能够保证整体结构的稳定，但低维投影结果会产生大量“空洞”，或使最短路径算法重构的图不连通。降维维数的确定通常是在本质维数未知的情况下进行的，经多次实验绘制残差曲线观察得到。Isomap算法计算图上2点间的最短距离可采用Dijkstra算法，但执行起来仍然比较慢。（12）

(l)当与高维流形等距的欧氏空间的子集不是凸型时，即当高维空间存在“空洞”时，要计算高维观测空间上任意样本点之间的距离很有可能发生弯曲异常，如果这样就会影响低维嵌入结果的表示。

(2)等距特征映射算法在数据拓扑空间有可能是不稳定的。因为如果选择的邻域过小，就会导致邻域图不连通，如果选择的邻域太大，又可能导致短路。

(3)使用Isomap算法恢复非线性流形的几何结构的时候，所需的计算时间比较多，这主要是花在计算样本点之间的最短路径上。

由于已有的流形学习算法对噪音和算法参数都比较敏感，詹德川、周志华[14]针对Isomap算法，提出了一种新方法，通过引入集成学习技术，扩大了可以产

生有效可视化结果的输入参数范围，并且降低了对噪音的敏感性。另外，赵连伟[15]等人完善了Isomap的理论基础，给出了连续流形与其低维参数空间等距映射的存在性证明，并区分了嵌入空间维数、高维数据的固有维数与流形维数这些容易混淆的概念，证明如果高维数据空间存在环状流形，流形维数则要小于嵌入空间维数．他们还给出一种有效的环状流形发现算法，以得到正确的低维参数 …… 此处隐藏：2166字，全部文档内容请下载后查看。喜欢就下载吧 ……