LDA與PCA資料降維算法理論與實作（基于python）

資料降維

一、 線性判别分析（LDA）

linear Discriminant Analysis

用途：

資料預進行中的降維，分類任務

目标：

LDA關心的是能夠最大化類間區分度的坐标軸成分

将特征空間（資料集中的多位樣本）投影到一個次元更加小的Kw維子空間中，同時保持區分類别的資訊

原理

投影到次元更低的空間，使得投影後的點，會形成按照類别區分，一簇一簇的情況，相同類别的點，将會在投影後的空間中更接近方法

監督性：LDA是‘有監督’的，它的計算是另一類特定的方向

投影：找到更合适分類的空間

與PCA不同，更關心分類而不是方差

數學原理

原始資料

變換資料

目标

找到投影該投影： y = w T ∗ x y = w^{T} * x y=wT∗x

LDA分類的一個目标是使得不同類别之間的距離越遠越好，

同一個類别之間的距離越近越好

每類樣例的均值： μ i = 1 N i ∑ x ∈ ω i x \mu_{i} = \frac{1}{N_{i}}\sum_{x \in \omega_{i}} x μi​=Ni​1​∑x∈ωi​​x

投影後的均值： μ i ~ = 1 N i ∑ x ∈ ω i y = 1 N i ∑ x ∈ ω i w T ∗ x = w T μ i \widetilde{\mu_{i}}=\frac{1}{N_{i}}\sum_{x \in \omega_{i}} y = \frac{1}{N_{i}}\sum_{x \in \omega_{i}} w^{T} * x = w^{T}\mu_{i} μi​

​=Ni​1​∑x∈ωi​​y=Ni​1​∑x∈ωi​​wT∗x=wTμi​

投影後的兩類樣本中心點盡量分離：

J ( w ) = ∣ μ 1 ~ − μ 2 ~ ∣ = ∣ w T ( μ 1 − μ 2 ) ∣ J(w) = |\widetilde{\mu_{1}}-\widetilde{\mu_{2}}| = |w^T(\mu_{1}-\mu_{2})| J(w)=∣μ1​

​−μ2​

​∣=∣wT(μ1​−μ2​)∣

不僅是要考慮最大化 J ( w ) J(w) J(w)

還有 散列值 μ i \mu_{i} μi​（樣本的密集程度，值越大，越分散，反之，越集中）

同類之間應該越密集些： μ i = 1 N i ∑ x ∈ ω i ( y − μ i ~ ) 2 \mu_{i} = \frac{1}{N_{i}}\sum_{x \in \omega_{i}}(y-\widetilde{\mu_{i}})^2 μi​=Ni​1​∑x∈ωi​​(y−μi​

​)2

如下圖，如果映射到X1軸上，資料較為分散，而且紅色的資料簇和藍色的資料簇會重合，無法分開，而投影到X2軸上雖然 J ( w J(w J(w小了，可是資料卻比較集中，分類效果相對于X1軸會比較好

目标函數： j ( w ) = ∣ μ 1 ~ − μ 2 ~ ∣ 2 S 1 ~ 2 + S 2 ~ 2 {j(w)}=\frac{|\widetilde{\mu_{1}}-\widetilde{\mu_{2}}|^2}{\widetilde{S_{1}}^2+\widetilde{S_{2}}^2} j(w)=S1​

​2+S2​

​2∣μ1​

​−μ2​

​∣2​

散列值公式展開： S i ~ 2 = ∑ y ∈ ω i ( y − μ i ~ ) 2 = ∑ x ∈ ω i ( w T x − w T μ i ) 2 = ∑ x ∈ ω i ( x − μ i ) ( x − μ i ) T w \widetilde{S_{i}}^2=\sum_{y \in \omega_{i}}(y-\widetilde{\mu_{i}})^2=\sum_{x\in\omega_{i}}(w^Tx-w^T\mu_{i})^2=\sum_{x\in\omega_{i}}(x-\mu_{i})(x-\mu_{i})^Tw Si​

​2=∑y∈ωi​​(y−μi​

​)2=∑x∈ωi​​(wTx−wTμi​)2=∑x∈ωi​​(x−μi​)(x−μi​)Tw

散列矩陣（scatter matrices）：

S i = ∑ x ∈ ω i ( x − μ i ) ( x − μ i ) T S_{i}=\sum_{x\in\omega_{i}}(x-\mu_{i})(x-\mu_{i})^T Si​=∑x∈ωi​​(x−μi​)(x−μi​)T

**類内散布矩陣 S w = S 1 + S 2 S_{w}=S_{1}+S_{2} Sw​=S1​+S2​：

S i ~ 2 = w T S i w \widetilde{S_{i}}^2=w^TS_{i}w Si​

​2=wTSi​w ======> s 1 ~ 2 + s 2 ~ 2 = w T S w w \widetilde{s_{1}}^2+\widetilde{s_{2}}^2=w^TS_{w}w s1​

​2+s2​

​2=wTSw​w

目标函數： J ( w ) = ∣ μ 1 ~ − μ 2 ~ ∣ 2 = w T ( μ 1 − μ 2 ) ( μ 1 − μ 2 ) T w = w T S B w J(w)=|\widetilde{\mu_{1}}-\widetilde{\mu_{2}}|^2=w^T(\mu_{1}-\mu_{2})(\mu_{1}-\mu_{2})^Tw=w^TS_{B}w J(w)=∣μ1​

​−μ2​

​∣2=wT(μ1​−μ2​)(μ1​−μ2​)Tw=wTSB​w

S B S_{B} SB​稱為類間散布矩陣

最終目标函數： J ( w ) = w T S B w w T S w w J(w)=\frac{w^TS_{B}w}{w^TS_{w}w} J(w)=wTSw​wwTSB​w​

不過，如果分子分母都是可以取任意值的，那就會使得有無窮解，我們将分母限制為長度為1

根據拉格朗日乘子法：

c ( w ) = w T S B w − λ ( w T S w w − 1 ) = > d c d w = 2 S B w − 2 λ S w w = = > S b w = λ S w w c(w)=w^TS_{B}w-\lambda(w^TS_{w}w-1) =>\frac{dc}{dw}=2S_{B}w-2\lambda S_{w}w==>S_{b}w=\lambda S_{w}w c(w)=wTSB​w−λ(wTSw​w−1)=>dwdc​=2SB​w−2λSw​w==>Sb​w=λSw​w

兩邊都乘以 S w 的 逆 ： S_{w}的逆： Sw​的逆： S w − 1 S B w = λ w S_{w}^{-1}S_{B}w=\lambda w Sw−1​SB​w=λw(w就是矩陣 S w − 1 S B S_{w}^{-1}S_{B} Sw−1​SB​的特征向量）

二、主成分分析（PCA）

PCA(Principal Component Analysis)降維中最常用的一種手段為了提取最有價值的資訊（基于方差）降維後，資料的實體意義就被模糊化了，此時可以通過資料降維來隐藏資料的真實資訊。

基本數學概念

向量的表示及基變換

内積： ( a 1 , a 2 , . . . , a n ) ⋅ ( b 1 , b 2 , . . . , b n ) = a 1 b 1 + a 2 b 2 + . . . + a n b n (a_{1},a_{2},...,a_{n})\cdot(b_{1},b_{2},...,b_{n})=a_{1}b_{1}+a_{2}b_{2}+...+a_{n}b_{n} (a1​,a2​,...,an​)⋅(b1​,b2​,...,bn​)=a1​b1​+a2​b2​+...+an​bn​

也就是: A ⋅ B = ∣ A ∣ ∣ B ∣ c o s ( a ) A\cdot B=|A||B|cos(a) A⋅B=∣A∣∣B∣cos(a) ,設向量B的模為1，則A與B的模為1,則A與B的内積等于A所在直線投影的矢量長度

向量可以表示為（3,2）實際上表示線性組合： x ( 1 , 0 ) T + y ( 0 , 1 ) T x(1,0)^T+y(0,1)^T x(1,0)T+y(0,1)T

基：（0,1）和（1,0）叫做二維空間中的一組基

基變換: 基是正交的（即内積為0，或者直覺的說互相垂直）且線性無關

變換: 資料與一個基做内積運算，結果作為第一個新的坐标分量，然後與第二個基做内積運算，結果作為第二個新坐标的分量如資料（3,2）映射到基中坐标：

( 1 2 1 2 − 1 2 1 2 ) ( 3 2 ) = ( 5 2 − 1 2 ) ( \begin{matrix} \frac{1}{ \sqrt{2}} & \frac{1}{ \sqrt{2}} \\ -\frac{1}{ \sqrt{2}} & \frac{1}{ \sqrt{2}} \end{matrix}) (\begin{matrix}3\\2\end{matrix})=(\begin{matrix} \frac{5}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{matrix}) (2

​1​−2

​1​​2

​1​2

​1​​)(32​)=(2

​5​−2

​1​​)

兩個矩陣相乘的意義是将右邊矩陣中你的每一列列向量變換到左邊矩陣中每一行行向量為基表示的空間去

協方差矩陣

方向: 如何選擇這個方向（基）才能盡量保留最多的原始資訊呢？一種直覺的看法是：洗完投影值盡可能分散

方差： V a r ( a ) = 1 m ∑ i = 1 m ( a i − μ ) 2 Var(a)=\frac{1}{m}\sum_{i=1}^{m}(a_{i}-\mu)^2 Var(a)=m1​∑i=1m​(ai​−μ)2

尋找一個一維基，使得所有資料變換為這個基上的坐标表示後，方內插補點最大

協方差

協方差（假設均值為0時）： C o v ( a , b ) = 1 m ∑ i = 1 m a i b i Cov(a,b)=\frac{1}{m}\sum_{i=1}^{m}a_{i}b_{i} Cov(a,b)=m1​∑i=1m​ai​bi​

如果單純隻選擇方差最大的方向，後續方向應該會和方差最大的方向接近重合。

解決方法： 為了讓兩個字段盡可能的表示更加多的原始資訊，不希望他們之間存在（線性）相關性的，可以使用兩個字段的協方差表示其相關性 C o v ( a , b ) = ∑ i = 1 m a i b i Cov(a,b)=\sum_{i=1}^{m}a_{i}b_{i} Cov(a,b)=∑i=1m​ai​bi​

當協方差為0時，表示兩個字段完全獨立。為了讓協方差為0,選擇第二個基時隻能在與第一個基正交的方向上選擇。是以最終選擇兩個方向一定是正交的（第一個2基在方差最大的方向上。第二個基與第一個基正交）。

優化目标

将一組N維向量降為K維（K大于0,小于N）,目标是選擇K個機關正交基，使原始資料變換到這組基後，各字段兩兩間協方差為0，字段的方差盡可能大

協方差矩陣： X = ( a 1 a 2 . . . a m b 1 b 2 . . . b m ) X=\left(\begin{matrix} a_{1}&a_{2}&...&a_{m}\\b_{1}&b_{2}&...&b_{m}\end{matrix}\right) X=(a1​b1​​a2​b2​​......​am​bm​​)

1 m X X T = ( 1 m ∑ i = 1 m a i 2 1 m ∑ i = 1 m a i b i 1 m ∑ i = 1 m a i b i 1 m ∑ i = 1 m b i 2 ) \frac{1}{m}XX^T=\left(\begin{matrix} \frac{1}{m}\sum_{i=1}^{m}a_{i}^{2}& \frac{1}{m}\sum_{i=1}^{m}a_{i}b_{i}\\ \frac{1}{m}\sum_{i=1}^{m}a_{i}b_{i}& \frac{1}{m}\sum_{i=1}^{m}b_{i}^{2}\end{matrix}\right) m1​XXT=(m1​∑i=1m​ai2​m1​∑i=1m​ai​bi​​m1​∑i=1m​ai​bi​m1​∑i=1m​bi2​​)

矩陣對角線的兩個元素分别是兩個字段的方差，而其它元素是a和b的協方差。

協方差矩陣對角化： 即除對角線外其它的元素化為0，并且在對角線上将元素按大小從上到下排列

協方差矩陣對角化： P C P T = Λ = ( λ 1 λ 2 ⋱ λ n ) PCP^T=\Lambda=\left(\begin{matrix}\lambda_{1}& &\\&&\lambda_{2}\\&& &\ddots\\&&&&\lambda_{n}\end{matrix}\right) PCPT=Λ=⎝⎜⎜⎛​λ1​​​λ2​​⋱​λn​​⎠⎟⎟⎞​

實對稱矩陣：一個n行n列的實對稱矩陣一定可以找到n個機關正交特征向量

E = ( e 1 e 2 ⋯ e n ) E=\left(\begin{matrix}e_{1}&e_{2}&\cdots&e_{n}\end{matrix}\right) E=(e1​​e2​​⋯​en​​)

實對稱矩陣可進行對角化：

E C E T = Λ = ( λ 1 λ 2 ⋱ λ n ) ECE^T=\Lambda=\left(\begin{matrix}\lambda_{1}& &\\&&\lambda_{2}\\&& &\ddots\\&&&&\lambda_{n}\end{matrix}\right) ECET=Λ=⎝⎜⎜⎛​λ1​​​λ2​​⋱​λn​​⎠⎟⎟⎞​

根據特征值得我從大到小，将特征向量從上到下排列，則用前K行組成的矩陣乘以原始資料矩陣X，就得到了我們需要降維後的資料矩陣Y

三、python實作

基于python的LDA和PCA執行個體（自己實作和調用現成的庫）jupyter源碼：

https://download.csdn.net/download/qq_37135484/11579884

LDA

PCA