线性判别分析 LDA
LDA 是一种无监督学习的降维技术.
思想: 投影后类内方差最小, 类间方差最大, 即期望同类实例投影后的协方差尽可能小, 异类实例的投影后的类中心距离尽量大.
二分类推导
给定数据集 \(D=\{(x_i,y_i)\}_{i=1}^m\), 令 \(X_i,\mu_i,\sum_i\)分别表示第 \(i\in \{0,1\}\)类实例的集合, 均值, 和协方差矩阵
则两类样本中心点在 \(w\)方向直线的投影分别为 \(w^Tu_0,w^Tu_1\); 若将所有的样本点都投影到 \(w\)方向直线上, 则两类样本的协方差分别是 \(w^T\sum_0 w,w^T\sum_1 w\)
此处推导用到的知识点
根据投影后类内方差最小, 类间方差最大, 欲最大化的目标为:
\(J=\frac{||w^Tu_0-w^Tu_1||^2}{w^T\sum_0 w+w^T\sum_1 w}\)
类内散度矩阵:
\(S_w=\sum_{x \in Y_i}(x-u_i)(x-u_i)^T\)
类间散度矩阵:
\(S_b=(u_0-u_1)(u_0-u_1)^T\)
则目标重写为 \(S_w,S_b\)的广义瑞利商
\(J=\frac{w^TS_bw}{w^TS_ww}\)
解与 w 只与方向有关与长度无关, 令,\({w^TS_ww}=1\)
目标函数等价于
- min\(\quad -w^TS_bw\)
- \(s.t. \quad {
- w^TS_ww
- }=1\)
引入拉格朗日乘子法
\(S_bw = \lambda S_ww\)
\(S_bw\)方向恒为 \((u_0-u_1)\)
\(S_bw = \lambda (u_0-u_1)\) 带入上式得:
\(w = S_w^{-1}(u_0-u_1)\)
奇异值分解:
- \(S_w=U\sum V^T\)
- \(S_w^{
- -1
- }=V\sum^{
- -1
- } U^T\)
从贝叶斯决策理论的角度阐释: 当两类满足数据同先验, 满足高斯分布且协方差相等时, LDA 达到最优
N 分类
全局散度矩阵:
- \(S_t=S_b+S_w=\sum^m_{
- i=1
- }(x_i-u)(x_i-u)^T\)
- \(S_w=\sum^N_{
- i=1
- }\sum_{
- x \in X_i
- }(x-u_i)(x-u_i)^T\)
- \(S_b=S_t-S_w=\sum^N_{
- i=1
- }m_i(u_i-u)(u_i-u)^T\)
根据 LDA 思想, 目标函数为:
- \(J(W)=\frac{
- tr(W^TS_bW)
- }{
- tr(W^TS_wW)
- }\)
- \(S_bw = \lambda S_ww\)
- PCA
PCA 的主要思想是将 n 维特征映射到 k 维上, 这 k 维是全新的正交特征也被称为主成分, 是在原有 n 维特征的基础上重新构造出来的 k 维特征
信号领域: 信号具有较大方差, 噪音具有较大方差, 信噪比越大意味着数据质量越高. 所以 PCA 的目标就是最大化投影误差.
第一步: 将数据进行去中心化:
第二步: 方差:
x 在单位向量上的投影为 \(x^Tw\)
- \(D(x)=\frac{
- 1
- }{
- n
- }\sum_{
- i=1
- }^m(x_i^Tw)^2\)
- = \(\frac{
- 1
- }{
- n
- }\sum_{
- i=1
- }^mw^Tx_ix_i^Tw\)
- = \(w^T(\frac{
- 1
- }{
- n
- }\sum_{
- i=1
- }^mx_ix_i^T)w\)
- = \(w^T\sum w\)
第三步: 目标函数:
- \(max \quad w^T\sum w\)
- \(max \quad w^Tw=1\)
第四步: 拉格朗日
\(D(x)=w^T\sum w=\lambda w^Tw=\lambda\)
投影后的方差就是投影后的协方差特征值, 将特征值由大到小排列, 取前 d 个主成分(主成分间相互正交)
由于得到协方差矩阵的特征值特征向量有两种方法: 特征值分解协方差矩阵, 奇异值分解协方差矩阵, 所以 PCA 算法有两种实现方法: 基于特征值分解协方差矩阵实现 PCA 算法, 基于 SVD 分解协方差矩阵实现 PCA 算法
降维后的信息占比:
\(\eta=\sqrt{\frac{\sum_{i=1}^d\lambda_i^2}{\sum_{i=1}^n \lambda_i^2}}\)
PCA 和 LDA 的相同点
PCA 和 LDA 都是经典的降维算法;
PCA 和 LDA 都假设数据是符合高斯分布的;
PCA 和 LDA 都利用了矩阵特征分解的思想.
PCA 和 LDA 的不同点
PCA 是无监督 (训练样本无标签) 的, LDA 是有监督 (训练样本有标签) 的;
PCA 去除原始数据集中冗余的维度, 让投影子空间的各个维度的方差尽可能大, 也就是熵尽可能大. LDA 是通过数据降维找到那些具有判断力的维度, 使得原始数据在这些维度上的投影, 不同类别尽可能区分开来.
LDA 最多可以降到 k-1 维(k 是训练样本的类别数量, k-1 是因为最后一维的均值可以由前面的 k-1 维的均值表示); 而 PCA 没有这个限制
LDA 还可以用于分类.
LDA 可能会过拟合数据.
来源: https://www.cnblogs.com/yunp-kon/p/11146813.html