数据降维方法综述 马小龙(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§ù êâÏ~vkNÑêâ 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) "ÄuA5ü {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)Ìg0 Xe"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" bCp,=rank(C) = p§@oCkp"A§P λ1 ≥ λ2 ≥ · · · ≥ λp > 0 ·ckA¤éAAþv1, v2, · · · , vk·ÝK,@ oéu?Û x§·Oyi = 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§·±wPCAÌ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)Ìg0 Xe" LDAlêâ©aÝ5įK§§´iÒ ª©a{" kca ℜ1, ℜ2, · · · , ℜc, áunm§1kakNk §¤k oÚN"30 `zOKc§·k½ÂA7Ä ëþ" 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éÝKwi , i = 1, 2, · · · , c,¦ eªzµ J(wi) = w T i Sbwi wT i Siwi ,«´¤kaOéÓÝKw,¦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)4w ∗"·^Lagrange¦f{¦)"-©1 u "~ê§=- 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 −1SbA¤éAAþ" ·£5¯K§XJIzaÑÏéÝKþwi§@ owiÒ´S −1 i SbA¤éAAþ¶XJI¤kaÏé ÓÝKþw§@owÒ´S −1 w SbA¤é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©OwiþÝ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§©aIòþª¥wiw=" ^ã25`²LDAg´" ã 2. LDA«¿ã(S.Balakrishnama,A.GanapathirajuJø) 2.1.3 PCAÚLDA' PCA´l*:?1êâü§=§z §¦þ3 &E¶ LDAl ª©a*:Ñu§z amå"ã3 ±éÐ /`²PCAÚLDA«O" ÏXd§@§3©a§LDAJÐuPCA"´§© z[7]¥Ñ§ ê½ö ¿vkþ!æ§= ØUéÐ/ Lyêâý¢©Ù§PCA©aJkUÐuLDA§ù±^ã45` ²" e¡©O0 ePCAÚ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§,0 KPCAÚKLDA" b·kmêâx1, x2, . . . , xm,Ù¥xi ∈ Rn"ù êâ3nm¥ 5Ø©§·F"ÏLNΦòêâlnmNN(N > n) m¥,¦êâ3Nm¥´5©,ù,·¦^PCA½öLDA3N m¥éêâ?1üÒ±Ð(J"´XÛÀΦâU¦ êâ3Nm¥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Φòê âN5AmF§½Â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éα5z§¦α 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