免费作文网站,东莞热点网络技术有限公司,邢台专业做网站公司,做免费网站怎么赚钱的Linear Discriminant Analysis#xff08;LDA#xff09;
输入#xff1a; 原始数据$D((x_1,y_1),(x_2,y_2),...,(x_m,y_m)$ 、 类别标签$Y[y_1,y_2,...,y_n]$、 降维到的维度d输出#xff1a;
投影矩阵W、投影后的样本$Z$、算法步骤#xff1a;
1.计算类内散度…Linear Discriminant AnalysisLDA
输入 原始数据$D((x_1,y_1),(x_2,y_2),...,(x_m,y_m)$ 、 类别标签$Y[y_1,y_2,...,y_n]$、 降维到的维度d输出
投影矩阵W、投影后的样本$Z$、算法步骤
1.计算类内散度矩阵 S w S_w Sw2.计算类间散度矩阵 S b S_b Sb3.计算矩阵 S w − 1 S b S_w^{-1}S_b Sw−1Sb4.计算 S w − 1 S b S_w^{-1}S_b Sw−1Sb的最大的d个特征值和对应的d个特征向量 ( w 1 , w 2 , . . . , w d ) (w_1,w_2,...,w_d) (w1,w2,...,wd)得到投影矩阵W5.对样本集中的每一个样本特征 x i x_i xi,转换为新的样本 z i W T x i z_iW^Tx_i ziWTxi6.得到输出样本集 D ′ ( ( z 1 , y 1 ) , ( z 2 , y 2 ) , . . . , ( z m , y m ) ) D ((z_1,y_1),(z_2,y_2),...,(z_m,y_m)) D′((z1,y1),(z2,y2),...,(zm,ym))
二类LDA
对于两个类别的中心点 μ 0 , μ 1 μ_0,μ_1 μ0,μ1,在直线 w w w的投影为 w T μ 0 w^Tμ_0 wTμ0和 w T μ 1 w^Tμ_1 wTμ1。
让不同类别的数据的类别中心之间的距离尽可能的大也就是我们要最大化 ∣ ∣ w T μ 0 − w T μ 1 ∣ ∣ 2 2 ||w^Tμ_0−w^Tμ_1||_2^2 ∣∣wTμ0−wTμ1∣∣22希望同一种类别数据的投影点尽可能的接近 Σ x ∈ w i ( w T x − w T μ i ) 2 Σ_{x∈w_i}(w^Tx-w^Tμ_i)^2 Σx∈wi(wTx−wTμi)2尽可能小也就是要同类样本投影点的协方差 w T Σ 0 w 和 w T Σ 1 w w^TΣ_0w和w^TΣ_1w wTΣ0w和wTΣ1w尽可能的小即最小化 w T Σ 0 w w T Σ 1 w w^TΣ_0ww^TΣ_1w wTΣ0wwTΣ1w。
优化的目标函数 J ( w ) ∣ ∣ w T μ 0 − w T μ 1 ∣ ∣ 2 2 w T Σ 0 w w T Σ 1 w w T ( μ 0 − μ 1 ) ( μ 0 − μ 1 ) T w w T ( Σ 0 Σ 1 ) w J(w)\frac{||w^Tμ_0-w^Tμ_1||_2^2}{w^TΣ_0ww^TΣ_1w} \frac{w^T(μ_0-μ_1)(μ_0-μ_1)^Tw}{w^T(Σ_0Σ_1)w}\\ J(w)wTΣ0wwTΣ1w∣∣wTμ0−wTμ1∣∣22wT(Σ0Σ1)wwT(μ0−μ1)(μ0−μ1)Tw 定义类内散度矩阵 S w Σ 0 Σ 1 ∑ x ∈ X 0 ( x − μ 0 ) ( x − μ 0 ) T ∑ x ∈ X 1 ( x − μ 1 ) ( x − μ 1 ) T \\ S_w Σ_0Σ_1\\ ∑_{x∈X_0}(x−μ_0)(x−μ_0)^T∑_{x∈X_1}(x−μ_1)(x−μ_1)^T\\ SwΣ0Σ1x∈X0∑(x−μ0)(x−μ0)Tx∈X1∑(x−μ1)(x−μ1)T 定义类间散度矩阵 S b ( μ 0 − μ 1 ) ( μ 0 − μ 1 ) T S_b(μ_0−μ_1)(μ_0−μ_1)^T Sb(μ0−μ1)(μ0−μ1)T 对此目标函数的优化 J ( w ) ∣ ∣ w T μ 0 − w T μ 1 ∣ ∣ 2 2 w T Σ 0 w w T Σ 1 w w T ( μ 0 − μ 1 ) ( μ 0 − μ 1 ) T w w T ( Σ 0 Σ 1 ) w J(w)\frac{||w^Tμ_0-w^Tμ_1||_2^2}{w^TΣ_0ww^TΣ_1w} \frac{w^T(μ_0-μ_1)(μ_0-μ_1)^Tw}{w^T(Σ_0Σ_1)w}\\ J(w)wTΣ0wwTΣ1w∣∣wTμ0−wTμ1∣∣22wT(Σ0Σ1)wwT(μ0−μ1)(μ0−μ1)Tw 方法一使用拉格朗日乘子法
可以将分母进行归一化如果分子分母都可以任意取值那将会有无穷解故将分母限制长度为1。
此时 { J ( w ) w T S b w w T S w w s . t . w T S w w 1 \begin{cases} J(w) \frac{w^TS_bw}{w^TS_ww}\\ s.t.\ w^TS_ww 1 \end{cases} {J(w)wTSwwwTSbws.t. wTSww1 使用拉格朗日乘子法 c ( w ) w T S b w − λ ( w T S w w − 1 ) → d c ( w ) d w 2 S b w − 2 λ S w w 0 → S b w λ S w w → S w − 1 S b w λ w c(w) w^TS_bw - \lambda(w^TS_ww-1)\\ →\frac{dc(w)}{dw}2S_bw-2\lambda S_ww 0\\ →S_bw \lambda S_ww\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ →S_w^{-1}S_bw\lambda w\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ c(w)wTSbw−λ(wTSww−1)→dwdc(w)2Sbw−2λSww0→SbwλSww →Sw−1Sbwλw 由上式得求解的w就是矩阵 S w − 1 S b S_w^{-1}S_b Sw−1Sb的特征向量
方法二使用瑞利商的结论
瑞利商是指这样的函数
R ( A , x ) x H A x x H x R(A,x)\frac{x^HAx}{x^Hx} R(A,x)xHxxHAx
它有性质
它的最大值等于矩阵A最大的特征值而最小值等于矩阵A的最小的特征值也就是满足 λ m i n ≤ x H A x x H x ≤ λ m a x λ_{min}≤\frac{x^HAx}{x^Hx}≤λ_{max} λmin≤xHxxHAx≤λmax
广义瑞利商。广义瑞利商是指这样的函数 R ( A , B , x ) R(A,B,x) R(A,B,x):
R ( A , x ) x H A x x H B x R(A,x)\frac{x^HAx}{x^HBx} R(A,x)xHBxxHAx
我们令 x B − 1 / 2 x ′ xB−1/2x′ xB−1/2x′,则分母转化为 x H B x x ′ H ( B − 1 2 ) H B B − 1 2 x ′ x ′ H B − 1 2 B B − 1 2 x ′ x ′ H x ′ x^HBxx′H(B^{\frac{−1}2})^HBB^{\frac{−1}2}x′x′^HB^{\frac{−1}2}BB^{\frac{−1}2}x′x′^Hx′ xHBxx′H(B2−1)HBB2−1x′x′HB2−1BB2−1x′x′Hx′
而分子转化为
x H A x x ′ H B − 1 / 2 A B − 1 / 2 x ′ x^HAxx′^HB^{−1/2}AB^{−1/2}x′ xHAxx′HB−1/2AB−1/2x′
此时我们的 R ( A , B , x ) R(A,B,x) R(A,B,x)转化为 R ( A , B , x ′ ) R(A,B,x′) R(A,B,x′):
R ( A , B , x ′ ) x ′ H B − 1 / 2 A B − 1 / 2 x ′ x ′ H x ′ R(A,B,x′)\frac{x′^HB^{−1/2}AB^{−1/2}x′}{x′^Hx′} R(A,B,x′)x′Hx′x′HB−1/2AB−1/2x′
利用前面的瑞利商的性质我们可以很快的知道 R ( A , B , x ′ ) R(A,B,x′) R(A,B,x′)的最大值为矩阵 B − 1 / 2 A B − 1 / 2 B^{−1/2}AB^{−1/2} B−1/2AB−1/2的最大特征值或者说矩阵 B − 1 A B^{-1}A B−1A的最大特征值而最小值为矩阵 B − 1 A B^{-1}A B−1A的最小特征值。这里用到了对矩阵进行标准化。
方法三直接对w进行求偏导 ∂ J ( w ) ∂ w ∂ ∂ w ( w T S b w w T S w w ) w T S w w ∂ ( w T S b w ) ∂ w − w T S b w ∂ ( w T S w w ) ∂ w 0 → ( w T S w w ) 2 S b w − ( w T S b w ) 2 S w w 0 除以 w T S w w : → ( w T S w w w T S w w ) S b w − ( w T S b w w T S w w ) S w w 0 → S b w − J S w w 0 → S w − 1 S b w − J w 0 → J w S w − 1 S b w → J w S w − 1 ( μ 0 − μ 1 ) ( μ 0 − μ 1 ) T w → J w S w − 1 ( μ 0 − μ 1 ) ( ( μ 0 − μ 1 ) T w ) ) ⏟ c ∈ R → J w c S w − 1 ( μ 0 − μ 1 ) → w c J S w − 1 ( μ 0 − μ 1 ) \frac {\partial J(w)}{\partial w} \frac {\partial }{\partial w}(\frac{w^TS_bw}{w^TS_ww})w^TS_ww\frac{\partial (w^TS_bw)}{\partial w} - w^TS_bw\frac{\partial (w^TS_ww)}{\partial w} 0 \\ →(w^TS_ww)2S_bw - (w^TS_bw)2S_ww0\\ 除以w^TS_ww:\\ →(\frac{w^TS_ww}{w^TS_ww})S_bw - (\frac{w^TS_bw}{w^TS_ww})S_ww0\\ →S_bw-JS_ww0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ →S_w^{-1}S_bw-Jw0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ →JwS_w^{-1}S_bw\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ →JwS_w^{-1}(μ_0-μ_1)(μ_0-μ_1)^Tw\ \ \ \ \ \ \ \ \\ →JwS_w^{-1}(μ_0-μ_1)\underbrace{((μ_0-μ_1)^Tw))}_{\text c∈R}\ \\ →JwcS_w^{-1}(μ_0-μ_1)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ →w\frac cJS_w^{-1}(μ_0-μ_1)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ∂w∂J(w)∂w∂(wTSwwwTSbw)wTSww∂w∂(wTSbw)−wTSbw∂w∂(wTSww)0→(wTSww)2Sbw−(wTSbw)2Sww0除以wTSww:→(wTSwwwTSww)Sbw−(wTSwwwTSbw)Sww0→Sbw−JSww0 →Sw−1Sbw−Jw0 →JwSw−1Sbw →JwSw−1(μ0−μ1)(μ0−μ1)Tw →JwSw−1(μ0−μ1)c∈R ((μ0−μ1)Tw)) →JwcSw−1(μ0−μ1) →wJcSw−1(μ0−μ1) Fisher’s linear discirminant
多类LDA
优化的目标函数 J ( w ) W T S b W W T S w W J(w)\frac{W^TS_bW}{W^TS_wW}\\ J(w)WTSwWWTSbW 其中 S b ∑ j 1 k N j ( μ j − μ ) ( μ j − μ ) T , μ 为所有样本的均值向量、 N j 为第 j 类样本的个数 S w ∑ j 1 k S w j ∑ j 1 k ∑ x ∈ X j ( x − μ j ) ( x − μ j ) T S_b\sum_{j1}^kN_j(μ_j-μ)(μ_j-μ)^T,μ为所有样本的均值向量、N_j为第j类样本的个数\\ S_w\sum_{j1}^kS_{wj}\sum_{j1}^k\sum_{x∈X_j}(x-μ_j)(x-μ_j)^T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Sbj1∑kNj(μj−μ)(μj−μ)T,μ为所有样本的均值向量、Nj为第j类样本的个数Swj1∑kSwjj1∑kx∈Xj∑(x−μj)(x−μj)T 有一个问题就是 W T S b W W^TS_bW WTSbW和 W T S w W W^TS_wW WTSwW都是矩阵不是标量无法作为一个标量函数来优化
常见的一个LDA多累优化目标函数定义为 a r g m a x ⏟ w J ( W ) ∏ d i a g ( W T S b W ) ∏ d i a g ( W T S w W → J ( W ) ∏ i 1 d ( w i T S b w i ) ∏ i 1 d ( w i T S w w i ) ∏ i 1 d w i T S b w i w i T S w w i \underbrace{arg\ max\ }_{\text w} J(W)\frac{∏diag(W^TS_bW)}{∏diag(W^TS_wW}\\ →J(W) \frac{∏_{i1}^d(w_i^TS_bw_i)}{∏_{i1}^d(w_i^TS_ww_i)}∏_{i1}^d\frac{w_i^TS_bw_i}{w_i^TS_ww_i} w arg max J(W)∏diag(WTSwW∏diag(WTSbW)→J(W)∏i1d(wiTSwwi)∏i1d(wiTSbwi)i1∏dwiTSwwiwiTSbwi 广义瑞利商
最大值是矩阵 S w − 1 S b S^{−1}_wS_b Sw−1Sb的最大特征值,最大的d个值的乘积就是矩阵 S w − 1 S b S^{−1}_wS_b Sw−1Sb的最大的d个特征值的乘积,此时对应的矩阵W为这最大的d个特征值对应的特征向量张成的矩阵。
