Linear discriminant analysis (LDA) 线性判别分析也是机器学习中常用的一种降维算法，与 PCA 相比，
LDA 是属于supervised 的一种降维算法。PCA考虑的是整个数据集在高维空间的分散性，PCA降维之后依然要让数据在低维空间尽可能地分散。而LDA考虑的是类与类之间的差别(用距离来衡量)。
我们考虑两类情况下的LDA，
给定一个训练集 D={xi∈Rd},i=1,2,...N<script type="math/tex" id="MathJax-Element-49">D=\{ \mathbf{x}_{i} \in R^{d}\}, i=1,2,...N</script>, 假设其中有 n1<script type="math/tex" id="MathJax-Element-50">n_{1}</script> 个属于第一类 c1<script type="math/tex" id="MathJax-Element-51">c_{1}</script>，n2<script type="math/tex" id="MathJax-Element-52">n_{2}</script> 个属于第二类c2<script type="math/tex" id="MathJax-Element-53">c_{2}</script>，N=n1+n2<script type="math/tex" id="MathJax-Element-54">N=n_{1}+n_{2}</script>， LDA 希望可以找到一个投影关系，使得原来的特征向量 xi<script type="math/tex" id="MathJax-Element-55">\mathbf{x}_{i}</script> 投影到低维空间之后，类间的距离尽可能地大，而类内距离尽可能地小。
我们可以计算每一类的均值向量：
u1=1n1∑x∈c1xu2=1n2∑x∈c2x
<script type="math/tex; mode=display" id="MathJax-Element-56">\mathbf{u}_{1}= \frac{1}{n_{1}}\sum_{\mathbf{x} \in c_{1}} \mathbf{x} \quad \mathbf{u}_{2}= \frac{1}{n_{2}}\sum_{\mathbf{x} \in c_{2}} \mathbf{x}</script>
假设投影为 w<script type="math/tex" id="MathJax-Element-57">\mathbf{w}</script>，投影后为 y<script type="math/tex" id="MathJax-Element-58">y</script>, 那么 y=wTx<script type="math/tex" id="MathJax-Element-59"> y=\mathbf{w}^{T}\mathbf{x}</script>, 我们也可以求出投影后的均值：
v1=1n1∑y∈c1y=1n1∑x∈c1wTx=wTu1
<script type="math/tex; mode=display" id="MathJax-Element-60">v_{1}= \frac{1}{n_{1}}\sum_{y\in c_{1}} y =\frac{1}{n_{1}}\sum_{\mathbf{x} \in c_{1}} \mathbf{w}^{T}\mathbf{x} =\mathbf{w}^{T}\mathbf{u}_{1} </script>
v2=1n2∑y∈c2y=1n2∑x∈c2wTx=wTu2
<script type="math/tex; mode=display" id="MathJax-Element-61"> v_{2}= \frac{1}{n_{2}}\sum_{y\in c_{2}} y=\frac{1}{n_{2}}\sum_{\mathbf{x} \in c_{2}} \mathbf{w}^{T}\mathbf{x} =\mathbf{w}^{T}\mathbf{u}_{2}</script>
那么，我们可以设立如下的目标函数：
J=|v1−v2|=|wTu1−wTu2|
<script type="math/tex; mode=display" id="MathJax-Element-62">J=| v_{1}-v_{2} |= | \mathbf{w}^{T}\mathbf{u}_{1}-\mathbf{w}^{T}\mathbf{u}_{2}| </script>
上面的目标函数，保证了映射之后类间距离尽可能大，但是无法保证类内距离尽可能小，为了让类内距离尽可能小，我们可以进一步定义：
s21=∑y∈c1(y−v1)2<script type="math/tex" id="MathJax-Element-63">s_{1}^{2}=\sum_{y\in c_{1}} (y-v_{1})^2 </script>
s22=∑y∈c2(y−v2)2<script type="math/tex" id="MathJax-Element-64">s_{2}^{2}=\sum_{y\in c_{2}} (y-v_{2})^2 </script>
s21,s22<script type="math/tex" id="MathJax-Element-65"> s_{1}^{2}, s_{2}^{2} </script> 可以用来度量映射后每一类与类中心的分散程度。所以，最终的目标函数是：
J=|v1−v2|2s21+s22
<script type="math/tex; mode=display" id="MathJax-Element-66">J=\frac{| v_{1}-v_{2} |^{2}}{ s_{1}^{2}+s_{2}^{2} } </script>
我们可以定义投影前的向量 x<script type="math/tex" id="MathJax-Element-67">\mathbf{x}</script> 与类中心的分散程度：
Si=∑x∈ci(x−ui)(x−ui)T<script type="math/tex" id="MathJax-Element-68">S_{i}=\sum_{\mathbf{x} \in c_{i}} (\mathbf{x} -\mathbf{u}_{i}) (\mathbf{x} -\mathbf{u}_{i})^{T} </script>
SW=S1+S2<script type="math/tex" id="MathJax-Element-69">S_{W}=S_{1}+S_{2}</script>
我们可以看到:
s2i=∑y∈ci(y−vi)2=∑x∈ci(wTx−wTui)2=wTSiw
<script type="math/tex; mode=display" id="MathJax-Element-70"> s_{i}^{2}=\sum_{y\in c_{i}} (y-v_{i})^2=\sum_{\mathbf{x} \in c_{i}} (\mathbf{w}^{T}\mathbf{x}-\mathbf{w}^{T}\mathbf{u}_{i})^{2} =\mathbf{w}^{T} S_{i} \mathbf{w} </script>
s21+s22=wTSWw
<script type="math/tex; mode=display" id="MathJax-Element-71"> s_{1}^{2}+s_{2}^{2}=\mathbf{w}^{T} S_{W} \mathbf{w} </script>
同样的，我们有:
(v1−v2)2=(wTu1−wTu2)2=wT(u1−u2)(u1−u2)Tw=wTSBw
<script type="math/tex; mode=display" id="MathJax-Element-72"> (v_{1}-v_{2})^{2}=(\mathbf{w}^{T}\mathbf{u}_{1}-\mathbf{w}^{T}\mathbf{u}_{2})^{2}=\mathbf{w}^{T}(\mathbf{u}_{1}-\mathbf{u}_{2}) (\mathbf{u}_{1}-\mathbf{u}_{2})^{T}\mathbf{w}=\mathbf{w}^{T}S_{B}\mathbf{w} </script>
SB=(u1−u2)(u1−u2)T
<script type="math/tex; mode=display" id="MathJax-Element-73"> S_{B}=(\mathbf{u}_{1}-\mathbf{u}_{2}) (\mathbf{u}_{1}-\mathbf{u}_{2})^{T} </script>
所以最终的目标函数是：
J(w)=wTSBwwTSWw
<script type="math/tex; mode=display" id="MathJax-Element-74"> J(\mathbf{w})=\frac{\mathbf{w}^{T}S_{B}\mathbf{w}}{\mathbf{w}^{T} S_{W} \mathbf{w}} </script>
最终得到的投影w⋆<script type="math/tex" id="MathJax-Element-75"> \mathbf{w}^{\star}</script>:
w⋆=argmax[wTSBwwTSWw]=S−1W(u1−u2)
<script type="math/tex; mode=display" id="MathJax-Element-76"> \mathbf{w}^{\star}=argmax \left[ \frac{\mathbf{w}^{T}S_{B}\mathbf{w}}{\mathbf{w}^{T} S_{W} \mathbf{w}} \right]=S_{W}^{-1}(\mathbf{u}_{1}-\mathbf{u}_{2}) </script>
对于多类的LDA, 我们不能简单地将原来的向量 x<script type="math/tex" id="MathJax-Element-77"> \mathbf{x} </script> 投影到一个标量y<script type="math/tex" id="MathJax-Element-78"> y </script>，我们需要投影到一个低维的向量 y<script type="math/tex" id="MathJax-Element-79">\mathbf{y}</script> 上。一个有C<script type="math/tex" id="MathJax-Element-80">C</script>类的训练集 D={x∈Rd}<script type="math/tex" id="MathJax-Element-81">D=\{ \mathbf{x} \in R^{d}\}</script> 含有N<script type="math/tex" id="MathJax-Element-82">N</script> 个样本, N=∑ni<script type="math/tex" id="MathJax-Element-83">N=\sum{n_i}</script>. 我们需要找到一个投影矩阵W<script type="math/tex" id="MathJax-Element-84">W</script>, 使得 y=WTx<script type="math/tex" id="MathJax-Element-85"> \mathbf{y}=W^{T}\mathbf{x} </script>。
我们可以先定义
Sw=∑i=1cSiSi=∑x∈ci(x−ui)(x−ui)T
<script type="math/tex; mode=display" id="MathJax-Element-86"> S_{w}=\sum_{i=1}^{c} S_{i} \quad S_{i}=\sum_{\mathbf{x} \in c_{i}} (\mathbf{x} -\mathbf{u}_{i}) (\mathbf{x} -\mathbf{u}_{i})^{T} </script>
SB=∑i=1cNi(ui−u)(ui−u)Tu=1N∑x
<script type="math/tex; mode=display" id="MathJax-Element-87"> S_{B}=\sum_{i=1}^{c} N_{i} (\mathbf{u}_{i}-\mathbf{u})(\mathbf{u}_{i}-\mathbf{u})^{T} \quad \mathbf{u}=\frac{1}{N} \sum \mathbf{x} </script>
那么目标函数可以写成:
J(W)=|WTSBW||WTSWW|
<script type="math/tex; mode=display" id="MathJax-Element-88"> J(W)= \frac{| \mathbf{W}^{T}S_{B}\mathbf{W} | }{ | \mathbf{W}^{T} S_{W} \mathbf{W} |} </script>
最后的投影矩阵可以表示为: W=[w1,w2,...wk]<script type="math/tex" id="MathJax-Element-89">W=[\mathbf{w}_{1}, \mathbf{w}_{2}, ... \mathbf{w}_{k} ]</script>, 其中 wi<script type="math/tex" id="MathJax-Element-90">\mathbf{w}_{i}</script> 满足如下关系:
SBwi=λiSWwi→S−1WSBwi=λiwi
<script type="math/tex; mode=display" id="MathJax-Element-91"> S_{B}\mathbf{w}_{i}=\lambda_{i} S_{W}\mathbf{w}_{i} \rightarrow S_{W}^{-1}S_{B}\mathbf{w}_{i}=\lambda_{i} \mathbf{w}_{i} </script>
wi<script type="math/tex" id="MathJax-Element-92">\mathbf{w}_{i}</script> 是矩阵 S−1WSB<script type="math/tex" id="MathJax-Element-93">S_{W}^{-1}S_{B}</script> 的特征向量, 所以简单来说，可以先对矩阵 S−1WSB<script type="math/tex" id="MathJax-Element-94">S_{W}^{-1}S_{B}</script> 做特征值分解，然后取前 k<script type="math/tex" id="MathJax-Element-95">k</script> 个大的特征值所对应的特征向量，组成投影矩阵。但是由于 S_{B} 的秩不会超过 c−1<script type="math/tex" id="MathJax-Element-96">c-1</script>，所以 k<script type="math/tex" id="MathJax-Element-97">k</script> 最大也就是 c−1<script type="math/tex" id="MathJax-Element-98">c-1</script>，取前面k<script type="math/tex" id="MathJax-Element-99">k</script> 个特征向量组成投影矩阵。对于两类的情况, c=2<script type="math/tex" id="MathJax-Element-100">c=2</script>, k=1<script type="math/tex" id="MathJax-Element-101">k=1</script>, 所以两类的情况下，LDA投影得到的是一个标量。
1
0
已为社区贡献16条内容
所有评论(0)