机器学习（三）— LDA(线性判别分析)理论与代码详解

1. 概要

线性判别分析是有监督的降维算法，也是一个分类算法，核心思想是：寻找一个投影矩阵使得类内样本的的投影尽可能近，类间样本投影尽可能远。

2. 理论基础

2.1 二分类

首先，先看该算法流程，再进一步理解，以下介绍均在二分类中考虑

结合线性判别分析的重要思想，我们的目标是

$$J=\frac{\Vert {\mathbf{w}}^{\mathrm{T}}{\mathbf{\mu }}_0-{\mathbf{w}}^{\mathrm{T}}{\mathbf{\mu }}_1{\Vert }_2^2}{{\mathbf{w}}^{\mathrm{T}}{\Sigma }_0\mathbf{w}+{\mathbf{w}}^{\mathrm{T}}\Sigma {}_1\mathbf{w}}=\frac{{\mathbf{w}}^{\mathrm{T}}({\mathbf{\mu }}_0-{\mathbf{\mu }}_1)({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\mathbf{w}}{{\mathbf{w}}^{\mathrm{T}}({\Sigma }_0+{\Sigma }_1)\mathbf{w}}\text{\hspace{1em}(1)}$$

类内散度矩阵：

$$S_w={\Sigma }_0+{\Sigma }_1=\sum _{\mathbf{x}\in X_0}(\mathbf{x}-{\mathbf{\mu }}_0)(\mathbf{x}-{\mathbf{\mu }}_0{)}^{\mathrm{T}}+\sum _{\mathbf{x}\in X_1}(\mathbf{x}-{\mathbf{\mu }}_1)(\mathbf{x}-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\text{\hspace{1em}(2)}$$

类间散度矩阵：

$$S_b=({\mathbf{\mu }}_0-{\mathbf{\mu }}_1)({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\text{\hspace{1em}(3)}$$

因此公式（1）可以改写为：

$$J=\frac{{\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_{\mathbf{b}}\mathbf{w}}{{\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_{\mathbf{w}}\mathbf{w}}\text{\hspace{1em}(4)}$$

求解该问题具体细节参考西瓜书，直接给出结果：$\mathbf{w}=S_w^{-1}({\mathbf{\mu }}_0-{\mathbf{\mu }}_1)$.

西瓜书中介绍这里的矩阵求逆，考虑到数值解的稳定性，通常采用奇异值分解进行求解：

$$S_w=\mathrm{U}\mathrm{\Sigma }{\mathrm{V}}^{\mathrm{T}}\text{\hspace{1em}(5)}$$

因此，$S_w^{-1}=\mathrm{V}{\mathrm{\Sigma }}^{-1}{\mathrm{U}}^{\mathrm{T}}$，带入公式即可求解$\mathbf{w}$.

2.1 多分类

当应用到多分类时，定义全局散度矩阵：

$$S_t=S_b+S_w=\sum _{i=1}^m({\mathbf{x}}_{\mathbf{i}}-\mathbf{\mu })({\mathbf{x}}_{\mathbf{i}}-\mathbf{\mu }{)}^{\mathrm{T}}\text{\hspace{1em}(6)}$$

$\mathbf{\mu }$ 指的全部示例的均值向量

定义类内散度矩阵：

$$S_w=\sum _{i=1}^N{S}_{w_i}\text{\hspace{1em}(7)}$$

直接理解为全局的散度矩阵就是每一类的散度矩阵求和即可

定义全局类间散度矩阵：

$$S_b=S_t-S_w\text{\hspace{1em}(8)}$$

总体优化目标：

$$\underset{\mathrm{W}}{\max }\frac{\mathrm{t}\mathrm{r}({\mathrm{W}}^{\mathrm{T}}{S}_w\mathrm{W})}{\mathrm{t}\mathrm{r}({\mathrm{W}}^{\mathrm{T}}{S}_b\mathrm{W})}\text{\hspace{1em}(9)}$$

tr表示矩阵的迹

广义特征值问题求解：

$$S_b\mathrm{W}=\lambda S_w\mathrm{W}\text{\hspace{1em}(10)}$$

$\mathrm{W}$ 的闭式解为 $S_w^{-1}{S}_b$ 的 $d^{\prime }$ 个最大非零广义特征值对应的特征向量组成的矩阵，$d^{\prime }\le N-1$代码实现就是使用直接的矩阵运算求解，构建投影矩阵，最后得到投影后的样本矩阵。注意：进行线性判别分析时，降低的维度最大是（类别数-1），如果类别数是10，样本数是100，则降低的最高维数是9.

**理解：**起初，可以理解二分类的线性判别分析，多分类难以理解，我选择这样理解，多分类就是多个w拼成一个W，求解的问题也变成了求W矩阵而不是求解w向量问题，从这里可以直接印证二分类问题将样本维度降低到1，就是样本矩阵乘以一个投影向量即得到投影后的维度为1，也就是将样本全部投影到一条直线上使得类间的距离尽可能大，使得类内距离尽可能小

3. 代码详解

算法流程：

1. 计算全局散度矩阵 $S_t$.
2. 计算类内散度矩阵 $S_w$.
3. 计算类间散度矩阵 $S_b$.
4. 计算矩阵 $S_w^{-1}{S}_b$.
5. 计算 $S_w^{-1}{S}_b$ 的最大的d个特征值和对应的d个特征向量$({\mathbf{w}}_1,{\mathbf{w}}_2,\cdots ,{\mathbf{w}}_d)$.
6. 对样本集中每个样本进行变换，构建新的样本集 $Z=W^{\mathrm{T}}X$.

朴素版本：

import numpy as np
from sklearn import datasets
# 准备数据
iris = datasets.load_iris()
X = iris.data
Y = iris.target
target_names = iris.target_names

# 1. 全局散度矩阵
mean = X.mean(axis=0)
St = np.dot((X - mean).T, X-mean)

# 2. 计算类内散度矩阵
Sw = np.zeros((X.shape[1], X.shape[1]))
for i in set(Y):
  Sw += np.dot((X[Y==i, :] - X[Y==i, :].mean(axis=0)).T, X[Y==i, :] - X[Y==i, :].mean(axis=0))

# 3. 类间散度矩阵
Sb = St - Sw

# 4. Sw^-1Sb矩阵
temp = np.dot(mat(Sw).I, Sb)

# 5. 求特征值与特征向量
eigenvalue, featurevector = np.linalg.eig(temp)

# 6. 直接得到特征向量组成投影矩阵W进行样本矩阵投影变换
temp_index = np.argsort(eigenvalue)             # 从小到大排序
W = featurevector[:, temp_index[-3:-1]]         # 取最大的两个特征值对应的特征向量构成投影矩阵
trans_X = np.array(np.dot(X, W))                # 得到降维结果

高级版本：

from sklearn import datasets
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
# 准备数据
iris = datasets.load_iris()
X = iris.data
y = iris.target
target_names = iris.target_names
# 直接使用api
lda = LinearDiscriminantAnalysis(solver="eigen")
X_r2 = lda.fit(X, y).transform(X)

如果感兴趣可以查看sklearn源码，说明的非常详细，其中关于线性判别分析部分使用了三种方法，分别是特征值分解，svd求解，最小二乘求解。简单版本是参考西瓜书进行梳理产生，仅供参考。

参考链接：《机器学习（西瓜书）》