机器学习-线性判别分析LDA

2021-03-14 本文已影响0人升不上三段的大鱼

判别分析方法是对后验概率进行估计的判别模型方法。如果样本属于某个类的条件概率密度符合高斯分布，对于贝叶斯分类器，决策边界在一般情况下是二次的曲线；如果所有的类别有同样的协方差，决策边界为线性的；当协方差矩阵为对角矩阵时，就是朴素贝叶斯分类器了。

1. 特征转换

对于一个特征空间，我们能否找到一个转换关系，使得被转换后的特征有着相同的协方差矩阵，从而获得线性的决策边界呢？

对于一个协方差矩阵 $\Sigma$ ，可以使用奇异值分解：
$\Sigma = UDU^T=(UD^{\frac{1}{2}}) \cdot I \cdot (UD^{\frac{1}{2}})^T$

带入到高斯分布中，得到：
$N (x; \mu, \Sigma) = \frac{1}{\sqrt(det2 \pi \Sigma)}e^{- \frac{1}{2}(x-mu)^T \Sigma^{-1}(x-\mu)}$
$\quad = \frac{1}{\sqrt(det2 \pi \Sigma)}e^{- \frac{1}{2}(x-mu)^T (UD^{\frac{1}{2}}) \cdot I \cdot (UD^{\frac{1}{2}})^T (x-\mu)}$
$\quad = \frac{1}{\sqrt(det2 \pi \mathbf{\Sigma})}e^{- \frac{1}{2}(((D^{- \frac{1}{2}}U^T)x-(D^{- \frac{1}{2}}U^T)\mu)^TI((D^{- \frac{1}{2}}U^T)x-(D^{- \frac{1}{2}}U^T)\mu)}$

所以 $x' = D_y^{- \frac{1}{2}}U_y^T x$ ，还是一个线性变换。
在经过这样的转换之后，决策边界是线性的，缺点就是这个特征转换与分类 $y$ 有关。

2. 线性判别分析LDA

对于数据集 $S=(x_1,y_1),(x_2,y_2), \cdots,(x_m,y_m)$

估计联合协方差矩阵
$\hat{\Sigma} = \frac{1}{m}\sum_{i=1}^m (x_i-\mu_{yi})(x_i-\mu_{yi})^T$
计算SVD: $\hat{\Sigma} = UDU^T$
计算得到变换: $\phi = D^{\frac{1}{2}}U^T$
计算得到均值: $\mu' = \phi(u_y) = D^{\frac{1}{2}}U^T \mu_y$

经过变换之后，分类的决策规则
$y* = \mathop{argmax}_{y} p(y|\phi(x))$
$\quad = \mathop{argmin}_{y} \frac{1}{2}||\phi(x)-\phi(\mu_y)||_2^2-\log p(y)$

$log(p(y))$ 是个常数，所以需要最小化的第一项，而其中的 $\phi$ 并不会减少特征的维度。

从几何角度来看，样本会被分到与样本自己距离最近的类别里。所有的样本点都可以投影到 $\mu_0-\mu_1$ 上，而依旧可以进行分类。一个二分类的问题可以被减小到以为上的最近邻分类。

对于K分类问题，将样本投影到较小维度的空间里，可以减小样本的维数。

用于降维的LDA主要目标是寻找将特征投影到子空间中，同时使得投影特征的方差最大，也就是是所有样本的投影尽可能分开。子空间的维度为 $L<K-1$ ，对于数据集 $S=(x_1,y_1),(x_2,y_2), \cdots,(x_m，y_m)$

计算变换过的均值向量的协方差矩阵
$\hat{\Sigma}_{inter} = \frac{1}{K}\sum_{y=1}^K (\mu_i'-\overline{\mu}')(\mu_i'-\overline{\mu}')^T$ ，其中 $\overline{\mu}'=\frac{1}{K} \cdot \sum_{y=1} ^K \mu_y'$
计算协方差矩阵的前L个最大的特征值对应的特征向量
这L个特征向量组成降维变换矩阵 $\phi$ 的每一行

上面的分析都是从贝叶斯分类出发的，当数据先验相同，满足高斯分布且协方差相等时，LDA可达到最优分类。

3. Fisher变换

从另一个角度来看，对于二分类的问题，对于给定的数据集，我们设法将样本点投影到一条线上，并且使得同类别的样本尽可能接近，而不同样本的距离尽可能远，再根据投影位置来确定样本类别。

LDA

给定数据集 $S=(x_1,y_1),(x_2,y_2), \cdots,(x_m,y_m)$ ，每个类的中心在 $w$ 方向上的投影向量为 $\tilde{\mu_k} = w^T \mu_k$

需要最大化的目标为类间散度与类内散度的比值：
$w^* = \mathop{argmax}_w J(w) = \mathop{argmax}_w \frac{|\tilde{\mu_1} - \tilde{\mu_2}|^2}{\tilde{s_1}^2 + \tilde{s_2}^2}$

为了求解 $r^*$ ，对于每个类别，均值和散度分别为
$\mu_k = \frac{1}{m_k} \sum_{i=1,y_i=k}^{m_k} x_i$
$\mathbf{S_k} = \sum_{i=1,y_i=k}^{m_k} (\mathbf{x_i-\mu_k})(\mathbf{x_i-\mu_k})^T$