首先我們來看幾個公式
variance公式:
covariance公式, 即:
當(dāng)隨機(jī)變量x和y相同時, covariance等同于variance:
如果協(xié)方差covariance等于0說明這兩個隨機(jī)變量不相關(guān)
協(xié)方差矩陣:
均值中心化(mean centering): 指得是將一系列的樣本點的均值置0,也就是每個樣本點的值減去所有樣本點的均值, 這樣新生成的所有樣本點的均值即為0撵割。
現(xiàn)在我們設(shè)z:
其中z的每一行都是mean centred后的特征向量feature vector, 此時, 之前的協(xié)方差矩陣就可表示為 (因為均值都變?yōu)?, 所以原來
直接變?yōu)榱藊*y )
1. ****Principal axes of variation (變化主軸)
Principal axes of variation指的是對于高維數(shù)據(jù)而言, 變化率最顯著的數(shù)據(jù)所在維度, 為了理解這一概念, 首先介紹基向量(basis)
一組基是由n維空間中n個線性獨立的向量組成, 這些向量之間是垂直的, 它們構(gòu)成了一個坐標(biāo)系統(tǒng), 而n維空間中有無限組基向量
**
**
第一主成分軸(****The ?rst principal axis****):
第一主成分軸指的是對在n維空間中的數(shù)據(jù)點, 指向最大variance方向的軸
**
**
第二主成分軸是指垂直于第一主成分軸同時指向最大variance方向的軸
以此類推, 第三主成分軸是垂直于第一和第二的前提下, 指向有著最大variance的軸
2. ****特征向量和特征根
最多有n對 特征向量-特征根對
其中若A是對稱矩陣(對于任何方形矩陣X错英,是對稱矩陣)的話, 則特征向量的集合是正交的
如果A是協(xié)方差矩陣的話, 那這些特征根就是主成分坐標(biāo)軸(principal axes)
對于的情況, 可以通過代數(shù)的方法解得特征根和特征方程池颈。
但對于更大的矩陣, 就需要特征分解(Eigendecomposition,簡寫為EVD)了。
3. ****特征分解
特征值分解(EVD)蜓竹,在這里互例,選擇一種特殊的矩陣——對稱陣(酉空間中叫hermite矩陣即厄米陣)敷钾。對稱陣有一個性質(zhì):它總能相似對角化,對稱陣不同特征值對應(yīng)的特征向量兩兩正交娱两。一個矩陣能相似對角化即說明其特征子空間即為其列空間,若不能對角化則其特征子空間為列空間的子空間〗鹇穑現(xiàn)在假設(shè)存在mxm的滿秩對稱矩陣A十兢,它有m個不同的特征值,設(shè)特征值為,對應(yīng)的單位特征向量為
則有:
將上面的式子用矩陣形式表示, 進(jìn)而:
令式子兩邊各除以一個U, 則有(由于對稱陣特征向量兩兩正交摇庙,所以U為正交陣旱物,正交陣的逆矩陣等于其轉(zhuǎn)置):
這里假設(shè)A有m個不同的特征值,實際上卫袒,只要A是對稱陣其均有如上分解宵呛。
如果A是對稱矩陣(譬如協(xié)方差矩陣), 此時 (即特征向量是正交的), 所以此時
將eigenvector和對應(yīng)的eigenvalue排序, PCA取前k個
要明確的是,一個矩陣其實就是一個線性變換夕凝,因為一個矩陣乘以一個向量后得到的向量宝穗,其實就相當(dāng)于將這個向量進(jìn)行了線性變換。比如說下面的一個矩陣:
因為這個矩陣M乘以一個向量(x,y)的結(jié)果是:
它其實對應(yīng)的線性變換是下面的形式:
上面的矩陣是對稱的码秉,所以這個變換是一個對x逮矛,y軸的方向一個拉伸變換, 當(dāng)矩陣不是對稱的時候,假如說矩陣是下面的樣子:
它所描述的變換是下面的樣子:
在圖中转砖,藍(lán)色的箭頭是一個最主要的變化方向(變化方向可能有不止一個)橱鹏,如果我們想要描述好一個變換,那我們就描述好這個變換主要的變化方向就好了。反過頭來看看之前特征值分解的式子莉兰,分解得到的Σ矩陣是一個對角陣挑围,里面的特征值是由大到小排列的,這些特征值所對應(yīng)的特征向量就是描述這個矩陣變化方向(從主要的變化到次要的變化排列), 當(dāng)矩陣是高維的情況下糖荒,那么這個矩陣就是高維空間下的一個線性變換杉辙,我們通過特征值分解得到的前N個特征向量,那么就對應(yīng)了這個矩陣最主要的N個變化方向捶朵。我們利用這前N個變化方向蜘矢,就可以近似這個矩陣(變換)。也就是之前說的:提取這個矩陣最重要的特征综看。
總結(jié)一下品腹,特征值分解可以得到特征值與特征向量,特征值表示的是這個特征到底有多重要红碑,而特征向量表示這個特征是什么
4. ****PCA流程
輸入:n維樣本集舞吭,要降維到的維數(shù)n'.
輸出:降維后的樣本集
- 對所有的樣本進(jìn)行中心化:
- 計算樣本的協(xié)方差矩陣
, 注意, 協(xié)方差矩陣就等于
- 對矩陣
進(jìn)行特征值分解
- 取出最大的n'個特征值對應(yīng)的特征向量
, 將所有的特征向量標(biāo)準(zhǔn)化后,組成特征向量矩陣W析珊。
- 對樣本集中的每一個樣本
, 轉(zhuǎn)化為新的樣本
- 得到輸出樣本集
有時候羡鸥,我們不指定降維后的n'的值,而是換種方式忠寻,指定一個降維到的主成分比重閾值t惧浴。這個閾值t在(0,1]之間。假如我們的n個特征值為, 則n'可以通過下式得到:
這里對PCA算法做一個總結(jié)奕剃。作為一個非監(jiān)督學(xué)習(xí)的降維方法衷旅,它只需要特征值分解,就可以對數(shù)據(jù)進(jìn)行壓縮纵朋,去噪芜茵。因此在實際場景應(yīng)用很廣泛。為了克服PCA的一些缺點倡蝙,出現(xiàn)了很多PCA的變種九串,比如第六節(jié)的為解決非線性降維的KPCA,還有解決內(nèi)存限制的增量PCA方法Incremental PCA寺鸥,以及解決稀疏數(shù)據(jù)降維的PCA方法Sparse PCA等猪钮。
PCA算法的主要優(yōu)點有:
1)僅僅需要以方差衡量信息量,不受數(shù)據(jù)集以外的因素影響胆建。
2)各主成分之間正交烤低,可消除原始數(shù)據(jù)成分間的相互影響的因素。
3)計算方法簡單笆载,主要運算是特征值分解扑馁,易于實現(xiàn)涯呻。
PCA算法的主要缺點有:
1)主成分各個特征維度的含義具有一定的模糊性,不如原始樣本特征的解釋性強(qiáng)腻要。
2)方差小的非主成分也可能含有對樣本差異的重要信息复罐,因降維丟棄可能對后續(xù)數(shù)據(jù)處理有影響。
5. ****奇異值分解
奇異值分解是一個有著很明顯的物理意義的一種方法雄家,它可以將一個比較復(fù)雜的矩陣用更小更簡單的幾個子矩陣的相乘來表示效诅,這些小矩陣描述的是矩陣的重要的特性。
特征值分解是一個提取矩陣特征很不錯的方法趟济,但是它只是對方陣而言的乱投,在現(xiàn)實的世界中,我們看到的大部分矩陣都不是方陣, 比如說有N個學(xué)生顷编,每個學(xué)生有M科成績戚炫,這樣形成的一個N * M的矩陣就不可能是方陣, 此時即用到了奇異值分解, 奇異值分解是一個能適用于任意的矩陣的一種分解的方法:
其中p是矩陣M的秩, 秩代表線性不相關(guān)的行或者列的數(shù)量
U是一個m * p的方陣(里面的向量是正交的,U里面的列向量稱為左奇異向量)媳纬,Σ是一個p * p的矩陣(除了對角線的元素都是0双肤,對角線上的元素稱為奇異值),V’(V的轉(zhuǎn)置)是一個p * n的矩陣层宫,里面的行向量也是正交的杨伙,V里面的向量稱為右奇異向量其监。
左奇異向量集合是的特征向量集合
右奇異向量集合是的特征向量集合
The singular values are the square roots of the eigenvalues of the corresponding eigenvectors of and
如果M是mean centred的特征向量矩陣的話, V的列向量是的特征向量, 它們是M的主成分(principle components)萌腿。
那么奇異值和特征值是怎么對應(yīng)起來的呢?首先抖苦,我們將一個矩陣M的轉(zhuǎn)置乘以M毁菱,將會得到一個方陣,我們用這個方陣求特征值可以得到:
這里得到的v锌历,就是我們上面的右奇異向量贮庞。此外我們還可以得到:
這里的σ就是上面說的奇異值,u就是上面說的左奇異向量
奇異值σ跟特征值類似究西,在矩陣Σ中也是從大到小排列窗慎,而且σ的減少特別的快,在很多情況下卤材,前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上了遮斥。也就是說,我們也可以用前r大的奇異值來近似描述矩陣扇丛,這里定義一下部分奇異值分解:
右邊的三個矩陣相乘的結(jié)果將會是一個接近于M的矩陣术吗,在這兒,r越接近于p帆精,則相乘的結(jié)果越接近于M较屿。而這三個矩陣的面積之和(在存儲觀點來說隧魄,矩陣面積越小,存儲量就越邪)要遠(yuǎn)遠(yuǎn)小于原始的矩陣M购啄,我們?nèi)绻胍獕嚎s空間來表示原矩陣A,我們存下這里的三個矩陣:U末贾、Σ闸溃、V就好了。
SVD流程:
至于為什么要用基于SVD的PCA是因為:
計算可行性
SVD的速度比EVD更快
除此之外, SVD適用的場合有:
求偽逆(Pseudoinverse)
解homogeneous linear equations, 如Ax=0
數(shù)據(jù)挖掘: 如基于CF的推薦系統(tǒng)
SVD求偽逆的一個例子
A矩陣的偽逆代表其與A的乘積等于單位矩陣
我們來具體算一個矩陣A的偽逆:
易知拱撵,rank(A*A)=2辉川。下面來求矩陣A*A的特征值,于是有
接下來求對應(yīng)的特征向量拴测,因為
所以可知當(dāng)λ1=5時乓旗,對應(yīng)的特征向量(注意結(jié)果要正交歸一化):
同理還有當(dāng)λ2=1時,對應(yīng)的特征向量
如此便得到了SVD中需要的U矩陣
為了求出矩陣V集索,先求W:
于是可知
所以根據(jù)公式A的偽逆就是, 其中V*代表其轉(zhuǎn)置矩陣
6. ****SVD和EVD的計算方法
普遍來說, 這些計算方法都是迭代的:
- Power Iteration
-Repeated for each E.V. by rotating and truncating the input to remove the effect of the previous E.V.
- “Arnoldi Iteration” and the “Lanczos Algorithm”
-Move ef?cient variants of Power Iteration
-use the “Gram-Schmidt” process to ?nd the orthonormal basis of the top-r E.Vs