—25—
基于流形学习的维数约简算法
姜 伟1,2，杨炳儒1
(1. 北京科技大学信息工程学院，北京 100083；2. 辽宁师范大学数学学院，大连 116029)
摘 要：介绍线性维数约简的主成分分析和多维尺度算法，描述几种经典的能发现嵌入在高维数据空间的低维光滑流形非线性维数约简算法，包括等距映射、局部线性嵌入、拉普拉斯特征映射、局部切空间排列、最大方差展开。与线性维数约简算法相比，非线性维数约简算法通过维数约简能够发现不同类型非线性高维数据的本质特征。 关键词：流形学习；谱图理论；局部切空间；特征映射
Dimensionality Reduction Algorithm Bad on Manifold Learning
JIANG Wei 1,2, YANG Bing-ru 1
(1. School of Information Engineering, University of Science and Technology Beijing, Beijng 100083;
2. School of Mathematics, Liaoning Normal University, Dalian 116029)
【Abstract 】This paper reviews Principal Components Analysis(PCA) and Multidimensional Scaling(MDS) methods for linear dimensionality reduction. Several classical nonlinear dimensional reduction methods that can find a smooth low-dimensional manifold embedded in the high-dimensional space are described and a number of improvement of the algorithms are introduced, including Isometric Feature Mapping (ISOMAP), Locally Linear Embedding(LLE), Laplacian Eigenmaps, Local Tangent Space Alignment(LTSA), Maximum Variance Unfolding (MVU). Compared with linear methods, nonlinear dimensionality reduction methods in manifold can extract the intrinsic characteristics of different types of high-dimensional data performing nonlinear dimensionality reduction.
【Key words 】manifold learning; spectral graph theory; local tangent space; eigenmaps
计 算 机 工 程 Computer Engineering 第36卷 第12期
Vol.36 No.12 2010年6月
June 2010
·博士论文·
文章编号：1000—3428(2010)12—0025—03
文献标识码：A
中图分类号：TP312
1 概述
在人脸识别、计算机视觉、信息检索和文本挖掘等领域中，经常要处理线性高维、非线性高维数据，数据的高维导致维数灾难并且不能被人的感知所理解，因此，需要对高维数据进行降维处理。降维包括特征选择和特征提取[1]2种方法，特征选择是在所有特征中选择最有代表性的特征，而特征提取是通过对原始特征进行某种操作获取有意义的投影。特征提取从谱分解的角度又可分为线性降维和非线性降维。线性降维方法包括主成分分析(Principal Components Analysis, PCA)、多维尺度变换(Multidimensional Scaling, MDS)和独立成分分析(Independent Component Analysis, ICA)等。线性降维对嵌入在一个低维流形的非线性高维数据是无效的，因此，基于流形学习的非线性高维数据降维算法引起了广泛的关注，2000年文献[2]和文献[3]介绍的ISOMAP, LLE 被认为是流形学习研究热潮开始的标志。
2 经典的维数约简算法
2.1 线性算法
(1)主成分分析
给定一个D 维数据集，PCA 的目的是寻找高维数据低维表示，使数据最大限度地“保持协方差结构”。
设()ij =X x 为一个n ×D 的数据集，记X=(x 1, x 2, …, x n )T =(x (1), x (2), …, x (n ))，其中，i x 为X 的第i 行，)(j x 为X 的第j 列，均值为0，即1
10n
i i x n ==∑，设输入向量i x 被投影到d 维子空间()d R d D <<，令T 12(,,,)d e e e =U "，则有x U y ⋅=，即
X U Y ⋅=，定义重构误差为
2
2
T 1()()d j PCA i i j j
i i i
i
e e ε==−⋅=−∑∑∑x x x U Ux
=UU I
以上问题可以转化为求解特征值分解问题：
T i i i e e λ=X X
所求的低维空间的正交基即为样本方差矩阵的前d 个最大特征值对应特征向量。
算法步骤如下：
have怎么读步骤1 将X 中心标准化，即1−←X HXD 。其中，
T 1
n
=−H I ，(1)(2)(){||||,||||,,||||}p =D diag Hx Hx Hx "，变换
后的数据仍为X 。
步骤2 求T X X 的特征值120D λλλ"≥≥≥≥和对应的标准正交特征向量12,,,D u u u "，这由对T X X 的谱分解完成，即T T =ΛX X U U 。
前面d 个特征值所对应的特征向量及由d 个特征向量张成的子空间为所求的投影空间。
(2)多维尺度
多维尺度的基本思想是：寻找高维数据的低维表示，最忠实地保持不同输入模式间的内积低维描述。关于MDS 的更多细节见文献[4]。
基金项目：国家自然科学基金资助项目“基于大规模复杂结构知识库的知识发现机理、模型与算法研究”(60675030)
作者简介：姜 伟(1969－)，男，副教授、博士研究生，主研方向：数据挖掘，流形学习，模式识别；杨炳儒，教授、博士生导师 收稿日期：2009-11-22 E-mail ：
—26—
算法步骤如下：
步骤1 由矩阵D 构造矩阵A =(a ij )，其中，2
1
2
ij ij d =−a 。
步骤2 构造矩阵HAH B =，其中，T 1n
=−H I ，这里，
1111
111
n
n
n
n
ij ij ij ij ij j i i j b n n n =====−
−+∑∑∑∑a a a a 。 步骤3 由谱分解得T T ===B HAH XX ΓΛΓ，其中，
12{,,,}d λλλ=Λdiag "，12d λλλ"≥≥≥为B 的d 个正特征值，相应的特征向量即为所求的正交特征向量。
在PCA 中需要对T X X 求解特征值分解问题，而在MDS 中需要对T XX 求解特征值分解问题，显然MDS 与PCA 互为对偶形式。MDS 线性降维方法可以发现高维线性空间上数据集的真实几何结构。对于非线性流形上的数据，MDS 不能发现其低维结构，因此，需要引入非线性的降维方法。 2.2 非线性算法
基于流形学习非线性降维算法可分成2类：(1)全局方法。在降维时将流形上邻近的点映射到低维空间中的邻近点，同时保证将流形上距离远的点映射到低维空间中的远距离的点。(2)局部方法。这类方法只是将流形上近距离的点映射到低维空间中的邻近点。 2.2.1 全局方法
(1)等距映射算法(ISOMAP)[2]
英文字母26个字母表等距映射算法的基本思想建立在经典的多维尺度方法的基础上，通过修改MDS 算法中的步骤1，用“测地距离”(geodesic distance)代替原MDS 方法中的欧式距离。
ISOMAP 算法步骤如下：
步骤1 建立领域关系图(,)G V E ：对每个(1,2,,)i i n =x "计算其k 近邻(1)(2)(),,,k i i i x x x "，记为j N ，以点i x 为顶点，欧氏距离(,)i j d x x 为边，建立邻域关系图(,)G V E 。
确定近邻点有2种简单的方法：
1)利用ε−近邻方法，即考虑点对,i j x x 是近邻点，如果
2
i j
ε−x x ≤。
2)利用k −近邻方法，事先给定k ，然后确定近邻点。
步骤2 计算测地距离矩阵n n ij d D ×=)(：在邻域关系图
diphtheria
(,)G V E 中寻找最短径，即
riskyor min{,}otherwi ij j i i j ij ij ik kj k
d x N x N d d d d ∀∈∈⎧⎪
=⎨
+⎪⎩ 步骤3 在距离矩阵n n ij d D ×=)(运行古典MDS 上，寻找
低维构造点12{,,,}n =Y y y y "。
ISOMAP 要求测地线距离矩阵D 是欧氏的，所以，ISOMAP 算法只能应用于嵌入流形是可展曲面的情况。
(2)最大方差展开(MVU)
最大方差展开保持降维前后近邻间的距离和角度不变，通过“拖拉”输入模式“展开”数据集。算法步骤如下：
步骤1 对于给定的数据集12{,,,}n =X x x x "，选出数据
集中任意一点i x ，记近邻数据集()()()
12{,,,}i i i i k x x x =x "为包含creek
数据点i x 本身在内的k 个近邻。然后根据邻近点构造二进制矩阵n n ×Γ，如果j x 是i x 的近邻点，则1ij =Γ，否则，0ij =Γ。 步骤 2 通过求解如下的SDP 问题构造核矩阵)))()(((j i ij x x K K φφ•=，令()ij i j G =⋅x x 。
Maximize :()Tr K
ferry是什么意思s.t.0K ≥
0ij ij K =∑
ii jj ij ji ii jj ij ji K K K K G G G G +−−=+−−
1ij =Γ
步骤3 根据核矩阵的主特征值计算低维嵌入。 2.2.2 局部方法
(1)局部线性嵌入
局部线性嵌入(Locally Linear Embedding, LLE)算法[2]的
基本思想是：对于每一个数据点i x ，利用位于其邻域内的数据点线性地表达i x ，计算一个权值能最佳重构高维空间中的数据点的权值，将流形的局部几何信息从高维空间携带到低维空间。算法步骤如下：
步骤 1 设i x 的k 最近邻为()()()()
(1)(2)(){,,,}i i i i N N N N i x x x χ=", ()()(1,2,,)i D N j x R j k ∈="，对于一个向量i x 和权重)
(i j w ，重建
错误由下列代价函数计算：
2
()()()()
1
()()k
i i i I
j
i N j j W w x x
ε==−∑
步骤2 通过最小化下面的代价函数固定权重w ：
2
()()T ()
1
1
()()n k
i i II i j
N j i j tr Y ε===−=∑∑Y y w y
YM
1
<0n
i i ==∑y ,T n =YY I
其中，T ()()=−−M I W I W 。
最优解*Y 是由矩阵M 最小第1d +个到最小第2个特征值对应的特征向量组成的，因为最小的特征值是0。 LLE 算法最终归结为稀疏矩阵的特征向量求解问题，计算量相对较小，但算法不能提供从高维空间到低维空间投影映射。
(2)拉普拉斯特征映射算法
拉普拉斯特征映射 (Laplacian Eigenmap, LE)[5]算法的基本思想是：对于高维空间的点构建连通的无向赋权图，通过求解图拉普拉斯算子的广义特征值实现映射。
Laplacian Eigenmap 算法步骤如下：
步骤1 确定每个m i R ∈x 的近邻，如采用k -近邻或ε−近邻求算法，构建邻域关系图(,)G V E 。
步骤2 选择权值：
1)热核：在邻域关系图(,)G V E 中，如果数据点i x 与j x 相连接，则设2
i j
t
ij W e
−=x x ，否则，0ij W =。
2)简单方法：在邻域关系图(,)G V E 中，如果数据点i x 与
pierrotj x 相连接，则设 1ij W =，否则，0ij W =。
步骤3 寻找映射12:(,){,,,}d N G V E R ψ→=⊂Y y y y "，即从加权图(,)G V E 到低维欧氏空间d R 中的一组像点
12{,,,}N =Y y y y "的映射，定义最小化目标函数：
(
)2
,N
ij i j
i j w y y ε=−∑
令W D L def
−=，D 是对角阵，0
c
ij
j
ij W i j D i j
⎧=∑⎪=⎨⎪≠⎩。
矩阵L 又叫作图的拉普拉斯矩阵，则优化问题写成更整
齐的形式：
—27—
T arg max ()Y
r T Y LY
这样约束的目的是防止降维后的图坍塌到一点。 LE 是基于局部保序，从而要求在高维空间中离得很近的点投影到低维空间中的像也应该离得很近。
(3)局部切空间排列(LTSA)
局部切空间排列[6]的基本思想：通过逼近每一样本点的切空间构建低维流形的局部几何，观测数据点在局部切空间的投影获得局部低维坐标，交叠的局部低维坐标被局部仿射变换后获得全局低维嵌入坐标。
LTSA 算法步骤如下：
步骤1 对于样本点j x ，记近邻数据集()1{,i i x =x
()()2,,}i i k x x "为包含数据点j x 本身在内k 个近邻。
步骤2 在j x 处，计算l 维切空间的正交基i Q ，)(i j
x 到切
空间的正交投影()T ()i i j i j i x θ=−Q x ，其中，i x 为近邻的均值。
步骤3 通过局部仿射变换整合得到全局坐标1{}n i i =y ，通过最小化全局排列的重构误差得到全局坐标：22
,min i i
i
L Y i
E =∑
T 2
2
,1min ||()||i i
i i i L Y i
i
ee L k −
−Θ∑Y I ，优化问题等价于：min ||||Y =YSW T T T min ()Y
r T YSWW S Y 。
在规范约束T =YY I 的条件下，最优d 维低维坐标Y 由
T T SWW S 的第2个到第1d +最小特征值对应的特征向量
231,,,d u u u +"构成，即T 231[,,,]d u u u +=Y "。
3 其他算法
线性维数约简方法还包括独立成分分析、Fisher 判别分
析(Fisher Discriminant Analysis, FDA)。大多数线性维数约简方法都有对应的基于核的非线性维数约简方法，如KPCA 、KICA 、KFDA 。围绕ISOMAP 算法，文献[7]提出通过构造最小k 连通图保证图的连通度；文献[8]在LLE 的基础上提出一个从低维嵌入空间向高维空间映射的方法。
4 结束语
数据降维包括特征选择和特征提取2种方法，特征提取
方法可以分为线性降维和非线性降维，非线性降维方法又可
分为全局方法和局部方法2类。非线性降维方法首先构造流形上样本点的局部邻域，然后用这些局部
邻域将样本点全局地映射到低维空间。不同之处在于构造的局部邻域不同以及利用这些局部邻域构造全局的低维嵌入方式的不同。维数约简方法需要利用现代数学的最新研究成果，尤其是数学中微分几何、黎曼流形。如何充分利用这些新的成果解决高维复杂数据的信息提取需进行深入研究。流形学习的研究目前正处于自身完善和发展阶段，作为高维数据分析方面的最新进展，它必将引起模式识别概念和理论层面的革命。
参考文献
[1] Sergios T, Konstantinos K. Pattern Recognition[M]. 3rd ed. [S. l.]:
Academic Press, 2007.
[2] Tenenbaum J B, Silva V D, Langford J C. A Global Geometric
Framework for Nonlinear Dimensionality Reduction[J]. Science, 2000, 290(5550): 2319-2323.
[3] Roweis S T, Saul L K. Nonlinear Dimensionality Reduction by
Locally Linear Embedding[J]. Science, 2000, 290(5550): 2324- 2326.
opportunity复数[4] Cox M. Multidimensional Scaling[M]. London, UK: Chapman &hei
Hall, 1994.
[5] Belkin M, Niyogi P. Laplacian Eigenmaps for Dimensionality
Reduction and Data Reprentation[J]. Neural Computation, 2003, 15(6): 1373-1396.
[6] Zhang Zhenyue, Zha Hongyuan. Principal Manifolds and Nonlinear
Dimension Reduction via Local Tangent Space Alignment[J]. Sci. Comput. SIAM, 2004, 26(1): 319-338.
[7] Li Yang. Building k-edge-connected Neighborhood Graphs for
Distance-bad Data Projection[J]. Pattern Recognition Letters, 2005, 26(13): 2015-2021.
[8] Zhang Changshui, Wang Jun, Zhao Nanyuan, et al. Reconstruction
and Analysis of Multi-po Face Images Bad on Nonlinear Dimensionality Reduction[J]. Pattern Recognition, 2004, 37(1): 325-336.
编辑 张正兴
2013专八~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
(上接第24页)
参考文献
[1] Yang Yiming, Pederson J O. A Comparative Study on Feature
Selection in Text Categorization[C]//Proceedings of the 14th International Conference on Machine Learning. Nashville, Tenne: [s. n.], 1997: 412-420.
[2] 周 茜, 赵明生, 扈 旻. 中文文本分类中的特征选择研究[J].
中文信息学报, 2004, 18(3): 17-23.
[3] Rogati M, Yang Yiming. High-performing Feature Selection for
Text Classification[C]//Proc. of the 11th International Conference on Information and Knowledge Management. Mclean, VA, USA: ACM Press, 2002: 659-661.
[4] Zheng Zhaohui, Wu Xiaoyun, Srihari R. Feature Selection for Text
Categorization on Imbalanced Data[J]. ACM SIGKDD Explorations Newsletter, 2004, 6(1): 80-89.
[5] Wang Lin, Jiang Minghu, Liao Shasha, et al. A Feature Selection
Method Bad on Concept Extraction and SOM Text Clustering Analysis[J]. International Journal of Computer Science and Network Security, 2006, 6(1): 20-28.
[6] Qiu Liqing, Zhao Ruyi, Zhou Gang. An Extensive Empirical Study
of Feature Selection for Text Categorization[C]//Proceedings of the 7th IEEE/ACIS International Conference on Computer and Information Science. Portland, Oregon, USA: IEEE Press, 2008: 312-315.
[7] Navidi W. Statistics for Engineers and Scientists[M]. [S. l.]:
McGraw-Hill, 2006.
[8] 贾 泂, 梁久祯. 基于支持向量机的中文网页自动分类[J]. 计算
机工程, 2005, 31(10): 145-147.
编辑 张正兴
