title: 机器学习笔记(六)两种降维方法：LDA和PCA

机器学习笔记(六)两种降维方法：LDA和PCA

date: 2015-08-09 10:18:55

MachineLearning

1. 线性判别分析（LDA，Linear Discrimination Analysis）

1.1. 思想

LDA是一种线性分类算法，思想非常简单，它是将训练集中的点映射到一条直线上，使得相同类别中的点尽可能靠在一起，属于不同类别的点尽可能离得比较远。我们的目标就是找到一条直线，尽可能满足上面的要求。下面的分析都是二分类情况。

1.2. 目标函数

设数据集$D = \{(x_i,y_i)\}_{i = 1}^{m}$,投影向量为$w$，则点$x_{i}$经过投影后为$y = w^{T}x_{i}$，投影前的样本中心点为$u$，投影后的中心店为$\tilde{u} = w^Tu$。

我们希望投影后不同类别的样本尽量离得较远：使用度量值

$$||\tilde{u_0} - \tilde{u_1}||_2^2$$

我们同时希望投影后相同类别的样本之间尽量离得较近：使用度量值

$$\sum_{ y \in Y_i}{(y - \tilde{u_i})^2}$$ ，这个值其实就是投影后样本的方差乘以此类样本集合中样本的数量。

所以总的优化目标函数为：

$$J(W) =\frac{||\tilde{u_0} - \tilde{u_1}||_2^2}{\sum_{ y \in Y_i}{(y - \tilde{u_i})^2}} = \frac{||\tilde{u_0} - \tilde{u_1}||_2^2}{\sum_0(y - \tilde u_0)^2 + \sum_1(y - \tilde u_1)^2}$$ ，目标$J(W)$当然是越大越好。

定义类内散度矩阵为：${S_w = \Sigma_0 + \Sigma_1 = \sum_{X_0}{(x - u_0)(x - u_0)^T} + \sum_{X_1}(x - u_1)(x - u_1)^T}$

定义类间散度矩阵：$\mathbf{S_b = (u_0 - u_1)(u_0 - u_1)^T}$

分子：$||\tilde{u_0} - \tilde{u_1}||_2^2 = w^T(u_0 - u_1)(u_0 - u_1)^Tw = w^T {S_b}w$

分母：$\sum_0(y - \tilde u_0)^2 + \sum_1(y - \tilde u_1)^2 = w^T{S_w} w$

所以$J(W) = \frac{w^T{S_b}w}{ w^T {S_w}w}$,因为向量w的长度成比例改变不影响J的取值，所以我们令$w^T{S_w} w = 1$，那么原优化目标就变为

$$min_w J(W) = - w^T {S_b}w$，$s.t. $ $w^T{S_w} w = 1$$ ,这里直接使用拉格朗日乘子法就可以了，解得
$$S_bw = \lambda wS_w$$ ，因为$S_bw = (u_0 - u_1)(u_0 - u_1)^Tw = (u_0 - u_1)\lambda_t$，所以$(u_0 - u_1)\lambda _t = \lambda wS_w$,可以得到 $$w = S_w^{-1}(u_0 - u_1)$$ 。

2. 主成分分析（PCA，Principal Component Analysis）

2.1. 主成分分析求解步骤：

设数据集是$N*M$的数据集，N是数据集中样本个数，M是每个样本的特征维数。主成分分析的目标就是将特征的维数从M降到K，$K<M$。

• 计算每一维的均值，$u_i = \frac{1}{N}\sum_{j = 1}^{N}x_{ji}$；
• 将样本数据每一维减去对应的均值，$x_j = {(x_{j1} - u_1,...,x_{ji} - u_i,...)}$；
• 由新的数据集计算协方差矩阵$C_{ij} = cov(x_i,x_j),M*M$；
• 求协方差矩阵的特征值和特征向量，假设求得T个特征向量，$T*M$
• 取特征值前K个大所对应的向量，将特征向量作为列向量构成新矩阵，EigenVectors,$M*K$`
• 减去均值后的样本矩阵为DataAdjust(N*M)，投影后的数据FinalData为
  $FinalData(N*K) = DataAdjust(N*M)*EigenVectors(M*K)$

很容易就可以看出来，通过上述步骤的变换，数据样本从M维降到了K维。

2.2. 最大化方差理论解释

这里的最大化方差指的是每一维特征上的样本方差很大。因为只有特征对应的方差很大，这样的特征才是具有很好的区分性的，设想一下，假如在某一维的特征上，所有样本取值都是相同的，显然该特征对应的方差为0，那么这个特征就是无用的，因为它无法对样本做出任何区分。

首先我们对数据进行中心化处理（$x_i - u$），中心化处理后的数据集均值为0，对应的投影集合的均值也为0。设直线的方向向量为$w$，并且$w$是单位向量。那么投影点就是$w^Tx_i$，我们的目标就是将投影点的方差最大化（下面公式中的数据都是已经中心化，并且特征方差已经归一化的）。投影点的方差形式化表达为：

$$\lambda = \frac{1}{N}\sum_{i = 1}^{N}{(w^Tx_i)^2} = \frac{1}{N}\sum_{i = 0}^{N}(w^Tx_ix_i^Tw) = w^T(\frac{1}{N}\sum_{i = 0}^{N}(x_ix_i^T))w$$ ，中间的部分其实就是协方差矩阵，因此
$\lambda = w^T{\Sigma}w$ ,因为w是单位向量，公式两边同时左乘w得到 $${\Sigma}w = {\lambda}w$$ ,所以，可以看出来这里投影后的数据集的方差就是协方差矩阵的特征值，所以我们可以根据特征值从大到小来选择对应的特征向量w，使得方差最大，假设将M维降到K维，选择的特征向量依次是 $$w_1,w_2,...,w_k$$ ，得到新特征为$y_i,y_{ij} = x_i^Tw_j,j = 1,2,...k\quad$。