機(jī)器學(xué)習(xí)：主成份分析和特征提取

1、主成份分析和特征提取,提綱,前言 主成份分析的基本原理 基于主成份分析人臉識(shí)別,主成分分析的例子（一）,原始數(shù)據(jù)空間中，其中一維數(shù)據(jù)的方差為0，沒(méi)有信息，可以完全去掉，而沒(méi)有任何損失！,主成分分析的例子（一）,投影：利用點(diǎn)積實(shí)現(xiàn)影射關(guān)系 XTY,主成份分析的例子（二）,人世間找不兩張完全一樣的臉！ 人臉是人類(lèi)賴(lài)以區(qū)分不同人的基本途徑 誰(shuí)決定了你的長(zhǎng)相？ 基因 + 成長(zhǎng)環(huán)境 夫妻相 世間一切盡在臉上！,人臉識(shí)別的定義,生物特征識(shí)別的一種 計(jì)算機(jī)以人的臉部圖像或者視頻作為研究對(duì)象，從而進(jìn)行人的身份確認(rèn),一項(xiàng)十分著名的工作是美國(guó)的統(tǒng)計(jì)學(xué)家斯通(stone)在1947年關(guān)于國(guó)民經(jīng)濟(jì)的研究。他曾利用美國(guó)

2、1929一1938年各年的數(shù)據(jù)，得到了17個(gè)反映國(guó)民收入與支出的變量要素，例如雇主補(bǔ)貼、消費(fèi)資料和生產(chǎn)資料、純公共支出、凈增庫(kù)存、股息、利息外貿(mào)平衡等等。,主成份分析的例子（三）,在進(jìn)行主成份分析后，竟以97.4的精度，用三新變量就取代了原17個(gè)變量。根據(jù)經(jīng)濟(jì)學(xué)知識(shí)，斯通給這三個(gè)新變量分別命名為總收入F1、總收入變化率F2和經(jīng)濟(jì)發(fā)展或衰退的趨勢(shì)F3。,1、若A是p階實(shí)對(duì)稱(chēng)陣，則一定可以找到正交陣U，使,其中 是A的特征根。,特征值分解簡(jiǎn)單回顧,2、若上述矩陣的特征根所對(duì)應(yīng)的單位特征向量為,令,提綱,前言 主成份分析的基本原理 基于主成份分析的人臉識(shí)別方法,表示方法,實(shí)際問(wèn)題總是變成數(shù)學(xué)問(wèn)題，然

3、后才是用機(jī)器去解決 X 表示變量 Xi表示變量的第i個(gè)分量 Xij表示第j個(gè)樣本的第i個(gè)分量,主成分分析試圖在力保數(shù)據(jù)信息丟失最少的原則下，對(duì)這種多變量的數(shù)據(jù)進(jìn)行最佳縮減，也就是說(shuō)，對(duì)高維變量空間進(jìn)行降維處理。 很顯然，識(shí)別系統(tǒng)在一個(gè)低維空間要比在一個(gè)高維空間容易得多。,2.1 PCA基本思想,(1) 基于協(xié)方差矩陣的主成分分析。該方法的思想在低維空間能夠保持原始空間的是最大化數(shù)據(jù)分布的方差,在力求數(shù)據(jù)信息丟失最少的原則下，對(duì)高維的變量空間降維，而在信息方面關(guān)注的是一組數(shù)據(jù)的變化信息，。要討論的問(wèn)題是：,在我們所討論的問(wèn)題中都有一個(gè)近似的假設(shè)，那就是數(shù)據(jù)滿足高斯分布，我們討論數(shù)據(jù)假定高斯分布或

4、者近似滿足高斯分布 一個(gè)問(wèn)題：高斯分布需要幾個(gè)參數(shù)據(jù)刻畫(huà)？ 均值，方差,思考問(wèn)題：為什么主成分分析最大化中涉及到協(xié)方差矩陣？,（2） 選擇幾個(gè)主成份。主成份分析的目的是簡(jiǎn)化變量，一般情況下主成份的個(gè)數(shù)應(yīng)該小于原始變量的維數(shù)。關(guān)于保留幾個(gè)主成份，應(yīng)該權(quán)衡主成份個(gè)數(shù)和保留的信息。 （3）如何解釋主成份所包含的意義。,2.2 數(shù)學(xué)模型與幾何解釋,假設(shè)我們所討論的實(shí)際問(wèn)題中，X是p維變量，記為X1，X2，Xp，主成分分析就是要把這p個(gè)變量的問(wèn)題，轉(zhuǎn)變?yōu)橛懻損個(gè)變量的線性組合的問(wèn)題，而這些新的分量F1，F(xiàn)2，F(xiàn)k(kp），按照保留主要信息量的原則充分反映原變量的信息，并且相互獨(dú)立。,這種由討論多維變量降

5、為維數(shù)較低的變量的過(guò)程在數(shù)學(xué)上就叫做降維。主成份分析通常的做法是，尋求向量的線性組合Fi。,滿足如下的條件：,主成份之間相互獨(dú)立，即無(wú)重疊的信息。即,主成份的方差依次遞減，重要性依次遞減，即,每個(gè)主成份的系數(shù)平方和為1。即,為了方便，我們?cè)诙S空間中討論主成份的幾何意義。 設(shè)有n個(gè)樣本，每個(gè)樣本有兩個(gè)觀測(cè)變量xl和x2，在由變量xl和x2 所確定的二維平面中，n個(gè)樣本點(diǎn)所散布的情況如橢圓狀。,主成份分析的幾何解釋,平移、旋轉(zhuǎn)坐標(biāo)軸,由圖可以看出這n個(gè)樣本點(diǎn)無(wú)論是沿著Fl 軸方向或F2軸方向都具有較大的離散性，其離散的程度可以分別用觀測(cè)變量xl 的方差和x2 的方差定量地表示。 顯然，如果只考慮

6、Fl和F2 中的任何一個(gè)，那么包含在原始數(shù)據(jù)中的信息將會(huì)有較大的損失。,主成份分析的幾何解釋,變換的目的是為了使得n個(gè)樣本點(diǎn)在Fl軸方向上的離散程度最大，即Fl的方差最大。 變量Fl代表了原始數(shù)據(jù)的絕大部分信息。經(jīng)過(guò)上述投影變換原始數(shù)據(jù)的大部分信息集中到Fl軸上，對(duì)數(shù)據(jù)中包含的信息起到了濃縮作用。,Fl，F(xiàn)2除了可以對(duì)包含在Xl，X2中的信息起著濃縮作用之外，還具有不相關(guān)的性質(zhì)，這就使得在研究復(fù)雜的問(wèn)題時(shí)避免了信息重疊所帶來(lái)的冗余性。 二維平面上的個(gè)點(diǎn)的方差大部分都?xì)w結(jié)在Fl軸上，而F2軸上的方差很小。Fl和F2稱(chēng)為原始變量x1和x2的綜合變量。 F簡(jiǎn)化了系統(tǒng)結(jié)構(gòu)，抓住了主要矛盾。,2.3 主

7、成份的數(shù)學(xué)上的計(jì)算,一、兩個(gè)線性代數(shù)的結(jié)論,1、若A是p階正定或者半正定實(shí)陣，則一定可以找到正交陣U，使,其中 是A的特征根。,2、若上述矩陣的特征根所對(duì)應(yīng)的單位特征向量為,則實(shí)對(duì)稱(chēng)陣 屬于不同特征根所對(duì)應(yīng)的特征向量是正交的，即有,令,理論推導(dǎo),利用特征分解求解投影方向，將詳細(xì)推導(dǎo),轉(zhuǎn)化成,二、主成份的推導(dǎo),設(shè)X的協(xié)方差陣為,由于x為對(duì)稱(chēng)陣，則有利用線性代數(shù)的知識(shí)可得，存在正交陣U，使得,其中1， 2， p為x的特征根，不妨假設(shè)1 2 p 。而U恰好是由特征根相對(duì)應(yīng)的特征向量所組成的正交陣。,主成份分析具體實(shí)例,選擇3個(gè)點(diǎn)(1,1)(2,2)(3,3),已知兩類(lèi)問(wèn)題的訓(xùn)練樣本：,將特征由2維壓

8、縮為1維。,x1,x2,2.4 主成份的性質(zhì),一、均值,二、方差為所有特征根之和,說(shuō)明主成分分析把P維隨機(jī)變量的總方差分解成為P個(gè)不相關(guān)的隨機(jī)變量的方差之和。 協(xié)方差矩陣的對(duì)角線上的元素之和等于特征根之和。,三、精度分析,1）貢獻(xiàn)率：第i個(gè)主成份的方差在全部方差中所占比重 ，稱(chēng)為貢獻(xiàn)率 ，反映了原來(lái)i個(gè)特征向量的信息，有多大的提取信息能力 。,2）累積貢獻(xiàn)率：前k個(gè)主成份共有多大的綜合能力，用這k個(gè)主成分的方差和在全部方差中所占比重 來(lái)描述，稱(chēng)為累積貢獻(xiàn)率。,我們進(jìn)行主成份分析的目的之一是希望用盡可能少的主成分F1，F(xiàn)2，F(xiàn)k（kp）代替原來(lái)的P維向量。 到底應(yīng)該選擇多少個(gè)主成份，在實(shí)際工作中

9、，主成分個(gè)數(shù)的多少取決于能夠反映原來(lái)變量95%以上的信息量為依據(jù)，即當(dāng)累積貢獻(xiàn)率95%時(shí)的主成分的個(gè)數(shù)就足夠了。,四、原始變量與主成份之間的相關(guān)系數(shù),五、原始變量被主成份的提取率,前面我們討論了主成份的貢獻(xiàn)率和累計(jì)貢獻(xiàn)率，他度量了F1，F(xiàn)2，F(xiàn)m分別從原始變量X1，X2，XP中提取了多少信息。那么X1，X2，XP各有多少信息分別F1，F(xiàn)2，F(xiàn)m被提取了。應(yīng)該用什么指標(biāo)來(lái)度量？我們考慮到當(dāng)討論F1分別與X1，X2，XP的關(guān)系時(shí)，可以討論F1分別與X1，X2，XP的相關(guān)系數(shù)，但是由于相關(guān)系數(shù)有正有負(fù)，所以只有考慮相關(guān)系數(shù)的平方。,如果我們僅僅提出了m個(gè)主成分，則第i 原始分量信息的被提取率為：,是

10、Fj 能說(shuō)明的第i 原始分量的方差,是Fj 提取的第i 原始分量信息的比重,例 設(shè) 的協(xié)方差矩陣為,解得特征根為 ， ，,，,第一個(gè)主成分的貢獻(xiàn)率為5.83/（5.83+2.00+0.17）=72.875%，盡管第一個(gè)主成分的貢獻(xiàn)率并不小，但在本題中第一主成分不含第三個(gè)原始變量的信息，所以應(yīng)該取兩個(gè)主成分。,2.5 主成份分析的步驟,第一步：由X的協(xié)方差陣x，求出其特征根，即解方程 ，可得特征根 。,一、基于協(xié)方差矩陣,第二步：求出分別所對(duì)應(yīng)的特征向量U1，U2，Up，,第三步：計(jì)算累積貢獻(xiàn)率，給出恰當(dāng)?shù)闹鞒煞謧€(gè)數(shù)。,第四步：計(jì)算所選出的k個(gè)主成份的得分。將原始數(shù)據(jù)的中心化值: 代入前k個(gè)主成

11、分的表達(dá)式，分別計(jì)算出各單位k個(gè)主成分的得分，并按得分值的大小排隊(duì)。,Eigenface-經(jīng)典人臉識(shí)別方法,其具體的計(jì)算過(guò)程跟其他領(lǐng)域的主成分分析一樣,人臉識(shí)別的核心問(wèn)題是提取特征,這里主要介紹一種統(tǒng)計(jì)學(xué)習(xí)方法 主成分分析方法 通過(guò)觀察圖像可以看出來(lái)很多冗余信息 如何去掉? 主成分或者PCA,Eigenface-計(jì)算方法,計(jì)算過(guò)程為：,計(jì)算樣本均值 m,中心平移每個(gè)訓(xùn)練樣本 xi,變換 重構(gòu),Eigenface-協(xié)方差矩陣計(jì)算,輸入訓(xùn)練樣本集合的協(xié)方差矩陣定義為： 其中 是樣本均值。 記： 則上述公式變?yōu)椋?PCA：用于降維,PCA: Reduce space dimensionality w

12、ith minimum loss of description information.,原始高維數(shù)據(jù),PCA降維: Theory,在變換后的特征空間中，每個(gè)特征向量wi對(duì)應(yīng)的特征值i的大小代表該特征向量所描述的方向上的方差的大小 所以 從W中去掉那些對(duì)應(yīng)較小特征值的特征向量，意味著在信息丟失最小的意義上降維!,PCA降維: Practice,按照其所相應(yīng)的特征值的大小對(duì)特征向量排序 選擇頭d個(gè)對(duì)應(yīng)最大特征值的特征向量構(gòu)成變換矩陣Wnxd,人臉識(shí)別,特征人臉,數(shù)據(jù)約減：理想情況圖示,原始數(shù)據(jù)空間中，其中一維數(shù)據(jù)的方差為0，沒(méi)有信息，可以完全去掉，而沒(méi)有任何損失！,提綱,前言 主成分分析的基本原

13、理 基于主成份分析人臉識(shí)別方法,前端攝像頭,圖像采集,主成份分析特征提取,支持向量機(jī)分類(lèi)器,基于主成分和支持向量機(jī)人臉識(shí)別系統(tǒng),人臉識(shí)別的界面,總結(jié)和作業(yè),深刻理解特征值分解與特征提取之間的關(guān)系 如何計(jì)算協(xié)方差矩陣 推導(dǎo)協(xié)方差矩陣得到主成份和特征值 計(jì)算各個(gè)特征向量或者主成份的提取率,PCA方法的優(yōu)缺點(diǎn),從壓縮能量的角度看，PCA方法是最優(yōu)的。從高維空間降到低維空間后，它不僅使得和原樣本的均方誤差最小，而且變換后的低維空間有很好的人臉表達(dá)能力 但是沒(méi)有考慮到人臉的類(lèi)別信息 PCA用于人臉識(shí)別并不是一個(gè)很好的方法，它只是起了信息壓縮減少特征的降維作用，提高了以后的識(shí)別效率。,PCA方法的解,每個(gè)

14、特征值都代表了相應(yīng)的特征向量保留總體散度（方差）的能力。,的各列向量是下面特征方程的解：,PCA和LDA產(chǎn)生的兩個(gè)不同的線性投影方向,Fisher線性投影方向Linear Discriminant Analysis(LDA),Fisher方法推導(dǎo),最大化Fisher的判別準(zhǔn)則：,線性變換之后使得不同類(lèi)的樣本（平均類(lèi)間距離）盡可能遠(yuǎn)，同類(lèi)樣本（平均類(lèi)內(nèi)距離）盡可能近。,為什么這么定義？,Fisher方法推導(dǎo),線性變換或者投影之后使得不同類(lèi)的樣本（平均類(lèi)間距離）盡可能遠(yuǎn),同類(lèi)樣本（平均類(lèi)內(nèi)距離）盡可能近,類(lèi)間散度矩陣,i類(lèi)與j類(lèi)之間的類(lèi)間散度矩陣：,總的類(lèi)間散度矩陣：,類(lèi)內(nèi)散度矩陣,i類(lèi)的類(lèi)內(nèi)散度

15、矩陣：,總的類(lèi)內(nèi)散度矩陣：,Fisher方法推導(dǎo),最大化如下表達(dá)式，可以滿足我們的要求：,如何計(jì)算？,定義Lagrange函數(shù)為：,Fisher方法推導(dǎo),如何計(jì)算？,則可以利用線性代數(shù)中的方法求解,Fisher基本過(guò)程,Fisher的投影方向是下面方程的解：,可以證明 的秩最大為N-C，所以當(dāng)N-Cd時(shí)， 一定是奇異的。N訓(xùn)練樣本的個(gè)數(shù),Fisherface方法 = PCA+Fisher,用PCA降維。運(yùn)用PCA方法將Sw降至p=N-C維。,為St最大的前N-C個(gè)特征值對(duì)應(yīng)的特征向量。,運(yùn)用上述Fisher方法求,最后求出理想的投影矩陣為:,參數(shù)選取,這是因?yàn)樵谟?xùn)練的人臉圖像中可能有些比較相像

16、，Sw的秩不一定能達(dá)到最大（N-C），或者降到N-C維時(shí)仍然很接近奇異，所以在PCA方法中采取多降幾維。,這是因?yàn)镾b的秩最大為C-1，前C-1個(gè)特征向量已經(jīng)代表了全部的類(lèi)間散度的信息，L取太大并不能保留更多的類(lèi)間散度，反而會(huì)保留更多的類(lèi)內(nèi)散度，對(duì)分類(lèi)無(wú)益。,經(jīng)典文章結(jié)論,Belhumeur對(duì)用特征臉?lè)椒ê虵isher臉?lè)椒ǚ謩e求出來(lái)的一些特征臉進(jìn)行比較后得出結(jié)論，認(rèn)為特征臉?lè)椒ê艽蟪潭壬戏从沉斯庹盏炔町?，而Fisher臉?lè)椒▌t能去掉圖像之間的與識(shí)別信息無(wú)關(guān)的差異。 Belhumeur的實(shí)驗(yàn)是通過(guò)對(duì)160幅人臉圖像（一共16人，每個(gè)人10幅不同條件下的圖像）進(jìn)行測(cè)試的，采用特征臉?lè)椒ǖ淖R(shí)別率為

17、81%，而采用Fisher臉?lè)椒ǖ淖R(shí)別率為99.4%。顯然，F(xiàn)isher臉?lè)椒ㄓ辛撕艽蟮母倪M(jìn)。,作業(yè),簡(jiǎn)要描述特征臉?lè)椒ê虵isher臉?lè)椒ǖ漠愅c(diǎn)。,PCA,Regular PCA:Find the direction u s.t. projecting n points in d dimensions onto u gives the largest variance. u is the eigenvector of covariance matrix Cu=u.,Kernel PCA,Kernel PCA is used for: De-noising Compression Inter

18、pretation (Visualization) Extract features for classifiers,Why Use Kernel,Why Use Kernel,涉及到樣本之間的內(nèi)積運(yùn)算(xixj), 在高維空間中只需進(jìn)行內(nèi)積運(yùn)算 , 很難知道變換的形式。根據(jù)Hibert-Schmidt原理,只要一種運(yùn)算滿足Mercer條件,就可以作為內(nèi)積使用。,Hibert,Hibert-Schmidt 希爾伯特，D.(Hilbert,David，18621943)德國(guó)數(shù)學(xué)家 1880年,他不顧父親讓他學(xué)法律的意愿,進(jìn)入哥尼斯堡大學(xué)攻讀數(shù)學(xué)。 1893年被任命為正教授 1942年成為柏林科學(xué)

19、院榮譽(yù)院士。 希爾伯特是一位正直的科學(xué)家,他敢于公開(kāi)發(fā)表文章悼念“敵人的數(shù)學(xué)家”達(dá)布,Kernel PCA,Extension to feature space: compute covariance matrix based 0-mean data solve eigenvalue problem CV=V,Kernel PCA,Define in terms of dot products: Then the problem becomes: where,l xd rather than d x d,Kernel PCA,(1,1) (2,2)(3,3) For example, k(x1

20、,x2)=(1*2+1*2+1)q k(x1,x3)=(1*3+1*3+1)q k(x2,x3)=(2*3+2*3+1)q,Applications Kernel PCA,Kernel PCA Pattern Reconstruction via Approximate Pre-Images B. Schlkopf, S. Mika, A. Smola, G. Rtsch, and K.-R. Mller. In L. Niklasson, M. Bodn, and T. Ziemke, editors, Proceedings of the 8th International Confere

21、nce on Artificial Neural Networks, Perspectives in Neural Computing, pages 147-152, Berlin, 1998. Springer Verlag.,Applications Kernel PCA,Input toy data: 3 point sources (100 points each) with Gaussian noise =0.1 (-0.5,-0.1) (0,0.7) (0.5,0.1) Using RBF,Applications Kernel PCA,Applications Kernel PC

22、A,Applications Kernel PCA,Applications Kernel PCA,Compare to the linear PCA,Fisher Linear Discriminant,Finds a direction w, projected on which the classes are “best” separated,Fisher Linear Discriminant,Equivalent to finding w which maximizes:where,Kernel Fisher Discriminant,Kernel formulation:where

23、,Kernel Fisher Discriminant,From the theory of reproducing kernels: Substituting it into the J(w) reduces the problem to maximizing:,Kernel Fisher Discriminant,Details refer to b. zhangs cvpr 2005 paper,Kernel Fisher Discriminant Toy Example,KFDA,KPCA 1st eigenvector,KPCA 2nd eigenvector,the feature value (indicated by grey level) and contour lines of identical feature value. Each class consists of two noisy parabolic shapes mirrored at the x and 9 axis respectively. We see, that the KFD feature discriminates the two classes in a nearly