降维算法：线性判别分析LDA

祺哥让我做的笔记……

1.背景介绍

• 用途：用作数据预处理中的降维。

  （为什么要降维？当样本个数多、特征个数多时，计算、调参和评估时候效率会很低；而且不一定所有的特征都有用，所以仅保留重要的信息进行建模）

• 历史：Ronald A.Fisher 于1936提出的线性判别分析方法

• 目标：最大化类间区分度的坐标轴成分，即将特征空间（数据集中的多维样本）投影到一个维度更小的K维子空间中，同时保持区分类别的信息。

• 原理：投影到维度更低的空间中，使得投影后的点，会形成按类别区分。

• 难点和核心点：如何找投影？即更合适分类的空间。

• 与PCA区别：LDA更关心分类而不是方差；LDA是有监督问题，PCA是无监督的问题。

2.数学原理：

2.1目标：

• 找到该投影 y=wTx
• 使不同类别之间的距离越远越好，同一类别之中的距离越近越好
• 每类别的均值 μi=1/Ni∑x∈wix
• 投影后的均值 μ˜i=1/Ni∑y∈wiy=1/Ni∑x∈wiwTx=wTμi
• 投影后的两类样本中心点尽量分离
  J(w)=|μ˜1−μ˜2|=∣∣wT(μ1−μ2)∣∣

只要J(w)越大就可以了吗？如下图：μ1，μ2映射到x1还是x2？
不，还要考虑类间样本点的密集程度

• 散列值：
  样本点的密集程度，值越大，越分散；反之，越集中
  

  S˜2i=∑y∈wi(y−μ˜i)2=∑x∈wi(wTx−wTμi)2=∑x∈wiwT(x−μi)(x−μi)Tw

  Si越小越好。

• 目标函数： J(w)=∣∣μ˜1−μ˜2∣∣2S21+S22

• 散列矩阵：Si=∑x∈wi(x−μi)(x−μi)T
• 类内散布矩阵：Sw=S1+S2，其中，S˜2i=wTSiw，S˜21+S˜22=wTSww
• 分子展开：
  
  (μ˜1−μ˜2)2=(wTμ1−wTμ2)2=wT(μ1−μ2)(μ1−μ2)Tw=wTSBw
• 类间散布矩阵：SB=(μ1−μ2)(μ1−μ2)T
• 最终目标函数：J(w)=wTSBwwTSww
• 分母进行归一化：wTSww=1

• 拉格朗日乘子法：
  

  c(w)=wTSBw−λ(wTSww−1)

  dcdw=2SBw−2λ(Sww)=0
  SBw=λSww

• 两边都乘以的逆：S−1wSBw=λw

  w就是矩阵S−1wSB的特征向量
  因此，先求Sw和SB
  再求，S−1wSB的特征向量即可
  注：特征向量：表示映射方向
  注：特征值：表示特征向量的重要程度