数据降维方法综述 马小龙(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