《线性代数》课程教学资源（文献资料）数据降维方法综述（清华大学：马小龙）

数据降维方法综述 马小龙(2005210988) 清华大学自动化系信息所 摘要 在科学研究中，我们经常遇到对大量高维数据进行分析的问题，例如图 像序列、恒星光谱等等。对于大量高维数据进行分析的需求导致人们对这 样一个问题的关注：如何在低维的空间中表示数据，以便于我们对数据进 行有效的分析。本文概括了在数据降维中常用的方法，对它们进行了简要 的分析。 关键字：PCA, LDA, KPCA, KLDA, Metric MDS, ISOMAP, LLE 1背景介绍 在科学研究中，我们经常要对数据进行处理。而这些数据通常都位于维数 很高的空间，例如，当我们处理256×256的图片序列时，通常我们将图片拉成 一个向量，这样，我们得到了4096维的数据序列，如果直接对这些数据进行处 理，会有以下问题：首先，会出现所谓的“维数灾难”问题，巨大的计算量将 使我们无法忍受；其次，这些数据通常没有反映出数据的本质特征，如果直接 对他们进行处理，不会得到理想的结果。所以，通常我们需要首先对数据进行 降维，然后对降维后的数据进行处理。 通常，我们进行数据降维主要是基于以下目的： 1.压缩数据以减少存储量 2.去处噪声的影响 3.从数据中提取特征以便于进行分类 4.将数据投影到低维可视空间，以便于看清数据的分布 数据降维的方法可以分为线性降维和非线性降维，而非线性降维又分为基 于核函数的方法和基于特征值的方法。线性降维方法有主成分分析(PCA)、独 立成分分析(ICA)、线性决策分析(LDA)、局部特征分析(LFA)等等。基于核函 数的非线性降维方法有基于核函数的主成分分析(KPCA)、基于核函数的独立 成分分析(KICA)、基于核函数的决策分析(KDA)等等。基于特征值的非线性降 维方法有ISOMAP和LLE。 1

êâü‘{nã ê9(2005210988) uŒÆgÄzX&E¤ Á ‡ 3‰ÆïÄ¥§·‚²~‘éŒþp‘êâ?1©Û¯K§~Xã S!ð(1Ì"éuŒþp‘êâ?1©ÛI¦<‚éù ‡¯K'5µXÛ3$‘m¥L«ê⧱Bu·‚éêâ? 1k©Û"©V) 3êâü‘¥~^{§é§‚?1 {‡ ©Û" '…iµPCA, LDA, KPCA, KLDA, Metric MDS, ISOMAP, LLE 1 µ0 3‰ÆïÄ¥§·‚²~‡éêâ?1?n" ù êâÏ~Ñ u‘ê épm§~X§·‚?n256 × 256ã¡Sž§Ï~·‚òã¡.¤ ‡•þ§ù§·‚ 4096‘êâS§XJ†éù êâ?1? n§¬k±e¯KµÄk§¬Ñy¤¢/‘ê/J0¯K§ãŒOŽþò ¦·‚Ã{=ɶÙg§ù êâÏ~vk‡NÑêâŸA§XJ† 馂?1?n§Ø¬nŽ(J"¤±§Ï~·‚I‡Äkéêâ?1 ü‘§,￾éü‘￾êâ?1?n" Ï~§·‚?1êâü‘̇´Äu±e8µ 1. Ø êâ±~;þ 2. ?D(K 3. lêâ¥JA±Bu?1©a 4. òêâÝK$‘ŒÀm§±Buwêâ©Ù êâü‘{Œ±©‚5ü‘Úš‚5ü‘§ š‚5ü‘q©Ä uؼê{ÚÄuAŠ{"‚5ü‘{k̤©©Û(PCA)!Õ á¤©©Û(ICA)!‚5ûü©Û(LDA)!ÛÜA©Û(LFA)"Äuؼ êš‚5ü‘{kÄuؼê̤©©Û(KPCA)!ÄuؼêÕá ¤©©Û(KICA)!Äuؼêûü©Û(KDA)"ÄuAŠš‚5ü ‘{kISOMAPÚLLE" 1

2降维方法 下面分别介绍各种比较常用的降维方法。 2.1线性降维方法 2.1.1PCA PCA(Principal Component Analysis)的主要思想介绍如下。假设我们有m个 数据x1,x2,,工m,其中x:∈R”。假设这些数据已经被中心归零化，即 2 4=0 定义协方差矩阵 c=∑ m-1 因为C为半正定矩阵，对其进行对角化，得： C=VAVT 其中，A=diag(A1,2,…,入n)VVT=1。 假设C的秩为p,即rank(C)=p,那么C有p个非零的特征值，记为 入1≥2≥…2入p>0 我们取前k个特征值所对应的特征向量1,2，·，，作为我们的投影方向，那 么对于任何一个样本x,我们计算：=xT,i=1,2,·,k,那么我们可以 用[，2，·，]T来表示样本x,这样可以将数据从n维降到k维。 当k=p=n,即C满秩，并且我们取n个基进行投影时，PCA就相当于对坐 标系进行了正交变换。 在PCA中，C的特征值是有明确的物理意义的，它表示了将数据在此特征 值对应的特征向量上投影后所得到的投影系数的方差，推导见下面。 Ah=w=FCw=∑5o =1 式中x表示了x在上的投影，由于样本的中心已经被放到了原点，那么这 些投影的中心也在零点，显然： m =0 所以，λ：的确代表了样本在：上投影的方差。 上式推导用到了公式=1C贴=入 那么，我们可以看到PCA的主要思想：将数据向使得投影方差较大的方向 投影，这样可以尽可能的保留数据信息。可以用图1来进行说明。 2

2 ü‘{ e¡©O0ˆ«'~^ü‘{" 2.1 ‚5ü‘{ 2.1.1 PCA PCA(Principal Component Analysis)̇gŽ0Xe"b·‚km‡ êâx1, x2, . . . , xm,Ù¥xi ∈ Rn"bù ê⮲¥%8"z§= Xm i=1 xi = 0 ½ÂÝ C = 1 m Xm i=1 xix T i ϏCŒ½Ý §éÙ?1éz§µ C = V ΛV T Ù¥§Λ = diag(λ1, λ2, · · · , λn) V V T = 1" bCp,=rank(C) = p§@oCkp‡š"AŠ§P λ1 ≥ λ2 ≥ · · · ≥ λp > 0 ·‚ck‡AŠ¤éAA•þv1, v2, · · · , vkŠ·‚ÝK•,@ oéu?ۇx§·‚OŽyi = x T vi , i = 1, 2, · · · , k§@o·‚Œ± ^[y1, y2, · · · , yk] T 5L«x§ùŒ±òêâln‘ük‘" k = p = n,=C÷§¿…·‚n‡Ä?1ÝKž§PCA҃ué‹ IX?1 C†" 3PCA¥§CAŠ´k²(Ôn¿Â§§L« òêâ3dA ŠéAA•þþÝK￾¤ÝKXꐧí„e¡" λi = v T i λivi = v T i Cvi = 1 m Xm j=1 (v T i xj )(v T i xj ) T ª¥v T i xjL« xj3viþÝK§du¥%®² :§@où ÝK¥%3":§w,µ Xm j=1 v T i xj = 0 ¤±§λi(L 3viþÝK" þªí^ úªv T i vi = 1 Cvi = λivi @o§·‚Œ±wPCȦgŽµòê╦ÝKŒ• ÝK§ùŒ±¦ŒU3êâ&E"Œ±^ã1 5?1`²" 2

PC1 PC2 图1.PCA示意图(Randy Julian,Lilly Research Laboratories提供) 2.1.2LDA LDA(Linear Discriminate Analysis)的主要思想介绍如下。 LDA从数据分类的角度来考虑问题，它是监督的模式分类方法。 设有c类样本沉1,2，·，咒c,样本属于n维空间，第k类有Nk个样本，所有样 本的总和为N。在介绍优化准则之前，我们先定义几个必要的基本参量。 1.各类样本均值向量m 21>x,i=1,2,…c mi= N 2 ∈R 2.总样本均值向量m m= 3.样本类内离散度矩阵S: S三e-me-mT2=12…0 x∈R 4.总类内离散度矩阵Su i1 5.样本类间离散度矩阵S6 6=0(m-n)m4-)T 3

ã 1. PCA«¿ã(Randy Julian,Lilly Research LaboratoriesJø) 2.1.2 LDA LDA(Linear Discriminate Analysis)̇gŽ0Xe" LDAlêâ©aÝ5įK§§´iÒª©a{" kcaℜ1, ℜ2, · · · , ℜc,áun‘m§1kakNk‡§¤k oڏN"30`zOKƒc§·‚k½ÂA‡7‡Äëþ" 1. ˆaþŠ•þmi mi = 1 Ni X x∈ℜi x , i = 1, 2, · · · , c 2. oþŠ•þm m = Xc i=1 Ni N mi 3. aSlÑÝÝ Si Si = 1 Ni X x∈ℜi (x − mi)(x − mi) T , i = 1, 2, · · · , c 4. oaSlÑÝÝ Sw Sw = Xc i=1 Ni N Si 5. amlÑÝÝ Sb Sb = Xc i=1 Ni N (mi − m)(mi − m) T 3

有两种优化准则的定义，一种是为每类找到一个投影方向，i=1,2,·,c,使 得下式最大化： (,)=S四 wSiwi 另一种是为所有的类别找到同一投影方向心，使得下式最大化： J(w)= wT Sow WTSww 上面两个准则很类似，只不过前者要找c个投影方向，而后者只需要找1个 投影方向。 下面通过求解下面的优化问题得到上述两个问题的解。 求w,使得 F(w)=wTS.w wTSw 取值最大。 下面求使F(w)取极大值的w*。我们用Lagrange乘子法求解。令分母等于 非零常数，即令 wTSw=a≠0 定义Lagrange函数为 L(w,X)=wTSow-A(wT Sw-a) 式中入为Lagrangez乘子。将上式对w求偏导数，得 ∂L(w,N=56w-λSw dw 令偏导数为零，得 S6w*-入Sw*=0 即 Sbw*=λSw* 当样本足够多时，S一般是满秩的，由此可知 S-1S6w*=λw* 可见，w*是S-1S6的特征向量。由此可知 F(w）=oTS%w* =(w)TSw (w*)TSw* (0*PS=入 可见，w*是S-1S6的最大的特征值所对应的特征向量。 我们回到原来的问题，如果需要为每一类都寻找一个投影向量心，那 么w:就是S,1S的最大的特征值所对应的特征向量；如果需要为所有的类寻找 同一个投影向量w,那么w就是S,1S%的最大的特征值所对应的特征向量

kü«`zOK½Â§«´zaé‡ÝK•wi , i = 1, 2, · · · , c,¦ eªŒzµ J(wi) = w T i Sbwi wT i Siwi ,«´¤kaOéÓÝK•w,¦eªŒzµ J(w) = w T Sbw wT Sww þ¡ü‡OKéaq§ØLcö‡éc‡ÝK•§ ￾öI‡é1‡ ÝK•" e¡ÏL¦)e¡`z¯Kþãü‡¯K)" ¦w§¦ F(w) = w T Sbw wT Sw ŠŒ" e¡¦¦F(w)4ŒŠw ∗"·‚^Lagrange¦f{¦)"-©1u š"~ê§=- w T Sw = a 6= 0 ½ÂLagrange¼ê L(w, λ) = w T Sbw − λ(w T Sw − a) ª¥λLagrange¦f"òþªéw¦ ê§ ∂L(w, λ) ∂w = Sbw − λSw - ê"§ Sbw ∗ − λSw∗ = 0 = Sbw ∗ = λSw∗ v õž§S„´÷§ddŒ S −1Sbw ∗ = λw∗ Œ„§w ∗´S −1SbA•þ"ddŒ F(w ∗ ) = (w ∗ ) T Sbw ∗ (w∗) T Sw∗ = λ (w ∗ ) T Sw∗ (w∗) T Sw∗ = λ Œ„§w ∗´S −1SbŒAŠ¤éAA•þ" ·‚£5¯K§XJI‡zaÑÏé‡ÝK•þwi§@ owiÒ´S −1 i SbŒAŠ¤éAA•þ¶XJI‡¤kaÏé ӇÝK•þw§@owÒ´S −1 w SbŒAŠ¤éAA•þ" 4

在分类时，我们将测试样本x分别向w:上投影，得到投影=xT心，计算它 和第类样本的投影中心m,间的距离|(z-m)T,那么样本所属的类别k满 足如下条件 k=ag驶.lz-m)严l 对于第二种优化准则，分类时只需将上式中的心，换为w即可。 可用图2来说明LDA的思路。 vector set2 图2.LDA示意图(S.Balakrishnama,A.Ganapathiraju提供) 2.1.3PCA和LDA的比较 PCA是从重构的观点进行数据降维的，即它最大化样本方差，尽量保留样 本的信息；而LDA从模式分类的观点出发，最大化样本类间距。图3可以很好 地说明PCA和LDA的区别。 正因为如此，一般认为，在分类时，LDA的效果要好于PCA。但是，文 献[⑦]中指出，当样本数较少或者样本并没有被均匀采样时，即样本不能很好地 表现数据的真实分布时，PCA的分类效果有可能好于LDA,这可以用图4来说 明。 下面分别介绍一下PCA和LDA的缺陷。 因为PCA是向使得投影方差最大的方向进行投影，那么在图5所示的情况 下，PCA会破坏数据原来的信息。 LDA有如下缺陷： 1.隐含了数据是高斯分布的假设。当数据不是高斯分布时，效果会很差， 如图6所示。 2.样本中心是决定因素，而不是样本方差。如图7所示。 尽管PCA和LDA具有上述的缺陷，但是，由于它们易于实现，并且可以达 到全局最优解，所有它们仍然是非常流行的数据降维的方法。 5

3©až§·‚òÿÁx©O•wiþÝK§ÝKyi = x T wi ,OŽ§ Ú1iaÝK¥%mT i wimål|(x − mi) T wi |,@o¤áaOk÷ vXe^‡ k = arg min 1≤i≤c |(x − mi) T wi | éu1«`zOK§©ažIòþª¥wi†w=Œ" Œ^ã25`²LDAg´" ã 2. LDA«¿ã(S.Balakrishnama,A.GanapathirajuJø) 2.1.3 PCAÚLDA' PCA´l­*:?1êâü‘§=§Œz§¦þ3 &E¶ LDAlª©a*:Ñu§Œzamå"ã3 Œ±éÐ /`²PCAÚLDA«O" ϏXd§„@§3©až§LDAJ‡ÐuPCA"´§© z[7]¥Ñ§ê½ö¿vkþ!枧=ØUéÐ/ Lyêâý¢©Ùž§PCA©aJkŒUÐuLDA§ùŒ±^ã45` ²" e¡©O0ePCAÚLDA"€" ϏPCA´•¦ÝKŒ•?1ÝK§@o3ã5¤«œ¹ e§PCA¬»€êâ5&E" LDAkXe"€µ 1. Û¹ êâ´pd©Ùb"êâØ´pd©Ùž§J¬é§ Xã6¤«" 2. ¥%´û½Ïƒ§ Ø´"Xã7¤«" ¦+PCAÚLDAäkþã"€§´§du§‚´u¢y§¿…Œ±ˆ ہ`)§¤k§‚E,´š~61êâü‘{" 5

222 品 1 m 22 2 1 Signal representation (PCA) Classification (LDA) > Feature 图3.PCA和LDA的区别(Vikipedia提供) LDA PCA DLDA 4 。 图4.有两类不同的类别分别代表两个不同的高斯分布。然 而，每类只选出两个样本来用PCA或LDA来进行处理。直观 上感觉，相对于LDA的分类结果，PCA的分类结果是我们更期 望得到的。DPCA和DLDA分别表示了用最近邻算法得到的决策 面。(A.M.Martinez and A.C.Kak提供) 6

ã 3. PCAÚLDA«O(WikipediaJø) ã 4. küaØÓaO©OLü‡ØÓpd©Ù", §zaÀÑü‡5^PCA½LDA 5?1?n"†* þaú§ƒéuLDA©a(J§PCA©a(J´·‚Ï ""DP CAÚDLDA©OL« ^CŽ{ûü ¡"(A.M. Martinez and A.C. KakJø) 6

图5.图中有三类呈棒状平行分布的数据。此时 用PCA降维会破坏数据的信息(Vikipedia提供) 01 02 图6.当数据不是高斯分布时，投影后混叠很严 重(Wikipedia提供) 7

ã 5. ã¥kna¥•G²1©Ùêâ"dž ^PCAü‘¬»€êâ&E(WikipediaJø) ã 6. êâØ´pd©Ùž§ÝK￾·Uéî ­(WikipediaJø) 7

PCA X 图7.PCA投影的决定因素是方差，而LDA投 影的决定因素是中心(Wikipedia提供) 2.2基于核函数的非线性数据降维方法 核函数的理论较为复杂，而核函数的思想却很简单。这里只简要地介绍一 下核函数的思想，然后介绍KPCA和KLDA。 假设我们有m个数据x1,x2,·,xm,其中x∈R”。当这些数据在n维空间中 线性不可分时，我希望通过一个映射Φ将数据从n维空间映射到N(N>n)维空 间中，使得数据在N维空间中是线性可分得，这样，当我们使用PCA或者LDA在N 维空间中对数据进行降维时就可以得到较好的结果。但是如何选取Φ才能使得 数据在N维空间中线性可分？并且，即使我们找到了一个映射Φ，可能N太大 以致于无法进行有效的计算。然而，在实践中人们发现，当对数据处理时，经 常会出现求两个向量点积的形式，即出现 ④(x:)PΦ(x) 的形式，于是，我们可以用一个函数来代替这种点积计算，即寻找一个函 数K(c,x,使得 K(x,x)=Φ(z)T(a) 这样可以把求点积的运算转化为求函数值的问题。这里的函数K(x,工，便称为 核函数。 在实际应用中，我们往往是直接指定K(x,x)的形式，我们无需知道④()的 具体形式。所以，只要问题最后可以转化为向量之间的点积问题，都可以用一 个核函数来代替点积，这样得到的方法就是基于核函数的方法。 常用的核函数有以下三种： 1.多项式核函数 K(,i)=[Tz;+1]d 8

ã 7. PCAÝKû½Ïƒ´§ LDAÝ Kû½Ïƒ´¥%(WikipediaJø) 2.2 Äuؼêš‚5êâü‘{ ؼên؏E,§ ؼêgŽ%é{ü"ùp{‡/0 eؼêgŽ§,￾0KPCAÚKLDA" b·‚km‡êâx1, x2, . . . , xm,Ù¥xi ∈ Rn"ù êâ3n‘m¥ ‚5،©ž§·F"ÏL‡NΦòêâln‘mNN(N > n)‘ m¥,¦êâ3N‘m¥´‚5Œ©,ù,·‚¦^PCA½öLDA3N ‘m¥éêâ?1ü‘žÒŒ±Ð(J"´XÛÀΦâU¦ êâ3N‘m¥‚5Œ©º¿…§=¦·‚é ‡NΦ§ŒUNŒ ±uÃ{?1kOŽ", §3¢‚¥<‚uy§éêâ?nž§² ~¬Ñy¦ü‡•þ:È/ª§=Ñy Φ(xi) T Φ(xj ) /ª§u´§·‚Œ±^‡¼ê5Où«:ÈOŽ§=Ï釼 êK(xi , xj ,¦ K(xi , xj ) = Φ(xi) T Φ(xj ) ùŒ±r¦:È$Ž=z¦¼êŠ¯K"ùp¼êK(xi , xjB¡ ؼê" 3¢SA^¥§·‚ ´†½K(xi , xj )/ª§·‚ÃIΦ(xi) äN/ª"¤±§‡¯K￾Œ±=z•þƒm:ȯK§ÑŒ±^ ‡Ø¼ê5O:ȧù{Ò´Äuؼê{" ~^ؼêk±en«µ 1. õ‘ªØ¼ê K(x, xi) = [x T xi + 1]d 8

2.径向基核函数 K(,i)=e-ll-ll2 3.神经网络核函数 K(I,Ii)=S[v(xTzi)+d S(u)是sigmoid函数。 2.2.1 KPCA 假设我们有m个数据x1,x2,.·,xm,其中x∈R”,我们定义一个映射Φ将数 据映射到非线性特征空间F,定义如下： Φ：R”→F,x→X 我们对数据④(x1),④（红2），.·，④(xm)用PCA进行处理。 m 0=- >()( m j=1 我们希望找到入>0和特征向量v∈F\{0}满足u=Cv。由此可知： U= 1 入m 6e,P=∑”g =1 =1 入m 可见，存在一组系数a1,·,am使得 m v=∑a() 1 我们定义 K=Φ(x)Φ(x) 将v和C的表达式代入下式， A(④(xk)Tv)=(重(xk)TCu),k=1,2,…,m 可得 mλKa=K2a 其中a=[a1,·,amT。为了找到a的解，我们求解如下的特征值问题 m入a=Ka 9

2. »•Äؼê K(x, xi) = e −γ||x−xi||2 3. ²äؼê K(x, xi) = S[v(x T xi) + c] S(u)´sigmoid¼ê" 2.2.1 KPCA b·‚km‡êâx1, x2, . . . , xm,Ù¥xi ∈ Rn ,·‚½Â‡NΦòê âNš‚5AmF§½ÂXeµ Φ : R n → F, x 7→ X ·‚éêâΦ(x1), Φ(x2), . . . , Φ(xm)^PCA?1?n" C = 1 m Xm j=1 Φ(xj )Φ(xj ) T ·‚F"éλ > 0ÚA•þv ∈ F\{0}÷vλv = Cv"ddŒµ v = 1 λm Xm j=1 Φ(xj )(Φ(xj ) T v) = Xm j=1 Φ(xj ) T v λm Φ(xj ) Œ„§3|Xêα1, · · · , αm¦ v = Xm j=1 αjΦ(xj ) ·‚½Â Kij := Φ(xi) T Φ(xj ) òvÚCLˆª\eª§ λ(Φ(xk) T v) = (Φ(xk) T Cv), k = 1, 2, · · · , m Œ mλKα = K2α Ù¥α = [α1, · · · , αm] T" éα)§·‚¦)XeAŠ¯K mλα = Kα 9

在求C的特征向量v时，我们需要将u归一化，即vTv=1。于是可得 1= a,a,Φ(x,)TΦ(z)=aTKa=mAaTa i,j=1 可见，我们需要对a规范化，使得aTa=: 1 m入 对于一个测试样本，我们要得到它在上的投影，可用下面的表达式计算 ar=∑ma,aP4e)=a,Ke,) 可见，所有的问题都转化为核函数K(工，x)的计算。 2.2.2 KLDA 在前面提到的LDA算法中，我们需要求解 J(w)= wTSpw WTSw 现在，假设 w=∑a() 那么上式可以变为 a)- aTSa aTSa 其中 Sg=∑sekT-KKT] S语=K2-∑NK日 Kij rie-Ne hee s=∑ 这样，我们将问题核函数化了，因为J(α)的形式与J(w)的形式相似，所 以a对应于(S)一1S的最大的特征值对应的特征向量。 当S密奇异时，我们用S+BI代替S吧，选择一个合适的B,我们可以保 证S+BI是非奇异的。 10

3¦CA•þvž§·‚I‡òv8z§=v T v = 1"u´Œ 1 = Xm i,j=1 αiαjΦ(xi) T Φ(xj ) = α T Kα = mλαT α Œ„§·‚I‡éα5‰z§¦α T α = 1 mλ" éu‡ÿÁ§·‚‡§3vþÝK§Œ^e¡LˆªOŽ Φ(x) T v = X i=1 mαiΦ(x) T Φ(xi) = Xm i=1 αiK(x, xi) Œ„§¤k¯KÑ=zØ¼êK(xi , xj )OŽ" 2.2.2 KLDA 3c¡JLDAŽ{¥§·‚I‡¦) J(w) = w T Sbw wT Sww y3§b w = X i αiΦ(xi) @oþªŒ±C J(α) = α T S Φ b α αT SΦ wα Ù¥ S Φ b = X c [κcκ T c − κκT ] S Φ w = K2 − X c Ncκcκ T c κc = 1 Nc X i∈c Kij κ = 1 N X i Kij ù§·‚ò¯Kؼêz §ÏJ(α)/ª†J(w)/ªƒq§¤ ±αéAu(S Φ w ) −1S Φ b ŒAŠéAA•þ" S Φ wÛɞ§·‚^S Φ w + βIOS Φ w ,ÀJ‡Ü·β§·‚Œ± yS Φ w + βI´šÛÉ" 10