第四章統(tǒng)計(jì)分類器及其學(xué)習(xí)

第四講

PrincipalComponentAnalysis

Fisher線性判別準(zhǔn)則第四章統(tǒng)計(jì)分類器及其學(xué)習(xí)

第四講

Principal1問題的提出在建立識別系統(tǒng)時(shí)，抽取的原始特征往往比較多，特征的維數(shù)比較大，這會給識別器的訓(xùn)練帶來很大的困難，因此希望能夠采用某種方法降低特征的維數(shù)。這些方法可以稱作成分分析的方法。主成分分析；尋找最小均方意義下，最能代表原始數(shù)據(jù)的投影方法多重判別分析；尋找最小均方意義下，最能分開各類數(shù)據(jù)的投影方法問題的提出在建立識別系統(tǒng)時(shí)，抽取的原始特征往往比較多，特征的2人臉識別舉例人臉識別舉例31主成分分析

（PCA，PrincipalComponentAnalysis）PCA是一種最常用的線性成分分析方法；PCA的主要思想是尋找到數(shù)據(jù)的主軸方向，由主軸構(gòu)成一個新的坐標(biāo)系（維數(shù)可以比原維數(shù)低），然后數(shù)據(jù)由原坐標(biāo)系向新的坐標(biāo)系投影。PCA的其它名稱：離散K-L變換，Hotelling變換；1主成分分析

（PCA，PrincipalCompone4問題：有n個d維樣本，x1,x2,..xn,如何僅用一個樣本x0代表這些樣本，使誤差準(zhǔn)則函數(shù)最小？不依賴于x0x0=m時(shí)取得最小值問題：有n個d維樣本，x1,x2,..xn,如何僅用一個樣本5樣本均值是樣本數(shù)據(jù)集的零維表達(dá)。將樣本數(shù)據(jù)集的空間分布，壓縮為一個均值點(diǎn)。簡單，但不能反映樣本間的差異零維表達(dá)改為“一維”表達(dá)，將數(shù)據(jù)集空間，壓縮為一條過均值點(diǎn)的線。每個樣本在直線上存在不同的投影，可以反映樣本間的差異e為直線的單位向量a為直線上的點(diǎn)到m的距離0維平方誤差1維平方誤差樣本均值是樣本數(shù)據(jù)集的零維表達(dá)。簡單，但不能反映樣本間的差異6只需把向量向過的直線垂直投影就能得到最小方差如何找到直線的最優(yōu)方向？只需把向量向過的直線垂直投影就能得到7協(xié)方差矩陣的n-1倍：散布矩陣協(xié)方差矩陣的n-1倍：散布矩陣8Lagrange乘子法散布矩陣散布矩陣的特征值為了最大化選取散布矩陣最大特征值選取對應(yīng)的特征向量作為投影直線的方向Lagrange乘子法散布矩陣散布矩陣的特征值為了最大化92,選取對應(yīng)的特征向量作為直線方向PCA算法——從0維，1維到d’

維有n個d維樣本，x1,x2,..xn,

零維表達(dá)：僅用一個樣本x0代表這些樣本，使誤差最??？一維表達(dá)：將這些樣本，映射到過m的一條直線上使誤差最??？簡單，但不能反映樣本間的差異1,選取散布矩陣最大特征值3,將樣本向直線做垂直投影d’維表達(dá)：將這些樣本，映射到以m為原點(diǎn)的d’維空間中，使誤差準(zhǔn)則函數(shù)最?。?,選取對應(yīng)的特征向量作為直線方向PCA算法10PCA算法d’維表達(dá)：有樣本集合，其中，以樣本均值為坐標(biāo)原點(diǎn)建立新的坐標(biāo)系，則有：，其中為標(biāo)準(zhǔn)正交向量基：因此有：將特征維數(shù)降低到，則有對的近似：

誤差平方和準(zhǔn)則函數(shù)：。

PCA算法d’維表達(dá)：有樣本集合，其中，以樣本均值為坐標(biāo)原11PCA算法d’維表達(dá)：

散布矩陣使用拉格朗日乘數(shù)法：

PCA算法d’維表達(dá)：散布矩陣使用拉格朗日乘數(shù)法：12

為的特征值，為的特征矢量。

要使最小，只需將的特征值由大到小排序，選擇最大的前個特征值對應(yīng)的特征向量構(gòu)成一個新的維坐標(biāo)系，將樣本向新的坐標(biāo)系的各個軸上投影，計(jì)算出新的特征矢量

其中為的特征值，為的特征矢量。要使最小，只需將的特征值由大到13PCA算法利用訓(xùn)練樣本集合計(jì)算樣本的均值m和散布矩陣S；計(jì)算S的特征值，并由大到小排序；選擇前d’個特征值對應(yīng)的特征矢量作成一個變換矩陣E=[e1,e2,…,ed’]；訓(xùn)練和識別時(shí)，每一個輸入的d維特征矢量x可以轉(zhuǎn)換為d’維的新特征矢量y：

y=Et(x-m)。PCA算法利用訓(xùn)練樣本集合計(jì)算樣本的均值m和散布矩陣S；14PCA的討論由于S是實(shí)對稱陣，因此特征矢量是正交的；將數(shù)據(jù)向新的坐標(biāo)軸投影之后，特征之間是不相關(guān)的；特征值描述了變換后各維特征的重要性，特征值為0的各維特征為冗余特征，可以去掉。PCA的討論由于S是實(shí)對稱陣，因此特征矢量是正交的；15例有兩類問題的訓(xùn)練樣本：

將特征由2維壓縮為1維。例有兩類問題的訓(xùn)練樣本：16x1x2e1e2x1x2e1e217特征人臉

e1e2e3e4e5e6e7e8特征人臉e1e2e318PCA重構(gòu)原圖像d’=15102050100200PCA重構(gòu)原圖像d’=15192多重判別分析

（MDA,MultipleDiscriminantAnalysis）x1x2e1e22多重判別分析

（MDA,MultipleDiscri20MDA與PCAPCA將所有的樣本作為一個整體對待，尋找一個均方誤差最小意義下的最優(yōu)線性映射，而沒有考慮樣本的類別屬性，它所忽略的投影方向有可能恰恰包含了重要的可分性信息；MDA則是在可分性最大意義下的最優(yōu)線性映射，充分保留了樣本的類別可分性信息；MDA還被稱為：FDA(FisherDiscriminantAnalysis)或LDA(LinearDiscriminantAnalysis)。MDA與PCAPCA將所有的樣本作為一個整體對待，尋找一個均21Fisher線性判別準(zhǔn)則如何選擇直線方向W，使樣本可分性最好？Fisher線性判別準(zhǔn)則如何選擇直線方向W，使樣本可分性最22樣本點(diǎn)在W方向上的投影W兩類樣本均值M1,M2投影之差：第i類投影的內(nèi)類散布：總體內(nèi)類散布：可分性準(zhǔn)則函數(shù)：（Fisher線性判別準(zhǔn)則）二分類問題可分性準(zhǔn)則函數(shù)的構(gòu)造樣本點(diǎn)在W方向上的投影W兩類樣本均值M1,M2投影之差23Fisher線性判別準(zhǔn)則：樣本x在w方向上的投影：類間散布矩陣：總類內(nèi)散布矩陣：廣義瑞利商準(zhǔn)則函數(shù)的廣義瑞利商形式Fisher線性判別準(zhǔn)則：樣本x在w方向上的投影：類間散布矩24瑞利商與廣義瑞利商設(shè)A是n階實(shí)對稱矩陣，稱R(x)為A的瑞利商

設(shè)A，B是n階實(shí)對稱矩陣，且B正定，稱R(x)為A相對于B的廣義瑞利商

R(x)具有以下特性

1，R(x)是x的連續(xù)函數(shù)。3，時(shí)，R(x)為一常數(shù),4，R(x)的最大，最小值存在，能在單位球面上找到2，R(x)是x的0次齊次函數(shù)：瑞利商與廣義瑞利商設(shè)A是n階實(shí)對稱矩陣，25瑞利商特性R(x)的最大、最小值為：

X展開為pi的線性組合瑞利商特性R(x)的最大、最小值為：X展開為pi的線性組合26廣義瑞利商特性廣義特征向量廣義瑞利商特性廣義特征向量27Fisher線性判別準(zhǔn)則：類間散布矩陣：總類內(nèi)散布矩陣：最大化必須滿足：為：相對于的特征值，為對應(yīng)的特征向量當(dāng)非奇異時(shí)Fisher線性判別準(zhǔn)則：類間散布矩陣：總類內(nèi)散布矩陣：最大28FDA算法利用訓(xùn)練樣本集合計(jì)算類內(nèi)散布矩陣Sw和類間散度矩陣SB；計(jì)算Sw-1SB的特征值；選擇非0的c-1個特征值對應(yīng)的特征矢量作成一個變換矩陣W=[w1,w2,…,wc-1]；訓(xùn)練和識別時(shí)，每一個輸入的d維特征矢量x可以轉(zhuǎn)換為c-1維的新特征矢量y：

y=Wtx。FDA算法利用訓(xùn)練樣本集合計(jì)算類內(nèi)散布矩陣Sw和類間散度矩陣293類問題FDA3類問題FDA30FDA的討論經(jīng)FDA變換后，新的坐標(biāo)系不是一個正交坐標(biāo)系；新的坐標(biāo)維數(shù)最多為c-1，c為類別數(shù)；只有當(dāng)樣本數(shù)足夠多時(shí)，才能夠保證類內(nèi)散度矩陣Sw為非奇異矩陣（存在逆陣），而樣本數(shù)少時(shí)Sw可能是奇異矩陣。FDA的討論經(jīng)FDA變換后，新的坐標(biāo)系不是一個正交坐標(biāo)系；31成分分析的其它問題獨(dú)立成分分析(ICA,IndependentComponentAnalysis)：PCA去除掉的是特征之間的相關(guān)性，但不相關(guān)不等于相互獨(dú)立，獨(dú)立是更強(qiáng)的要求。ICA試圖使特征之間相互獨(dú)立。多維尺度變換(MDS,MultidimensionalScaling)典型相關(guān)分析(CCA,CanonicalCorrelationAnalysi