关于人工智能:机器学习算法系列十线性判别分析算法一Linear-Discriminant-Analysis-Algorithm

浏览本文须要的背景知识点：拉格朗日乘数法、一丢丢编程常识

后面学习了一种用回归的形式来做分类的算法——对数几率回归算法，上面再来学习另一种分类算法——线性判别分析算法 ¹（Linear Discriminant Analysis Algorithm/LDA），该算法由罗纳德·艾尔默·费希尔在 1936 年提出，所以也被称为费希尔的线性鉴别方法（Fisher’s linear discriminant）

先来看下图，假如有二分类的数据集，“+”示意正例，“-”示意反例。线性判别分析算法就是要设法找到一条直线，使得同一个类别的点在该直线上的投影尽可能的靠近，同时不同分类的点在直线上的投影尽可能的远。该算法的次要思维总结来说就是要“类内小、类间大”，十分相似于在软件设计时说的“低耦合、高内聚”。

起源：《机器学习》- 周志华

当有新的样本点须要分类时，计算该点在直线上的投影，依据投影的地位来判断新样本点的分类。那么如何用数学公式来示意上述说法呢？

假如有样本数为 N 的数据集，X_i 示意第 i 个样本点的特征向量，y_i 示意第 i 个样本点的标签值，w 示意直线的权重系数。

样本点到直线的投影向量

（1）投影向量为样本点乘以与直线夹角的余弦值

（2）带入夹角余弦值的公式

（3）由上图能够看到，咱们只须要关系该直线的斜率即可，也就是 w 的方向。无妨令 w 为单位向量，即 |w| = 1，带入后整顿可得

（4）能够看到（3）式中的第一项即为单位向量，后两项乘积为实数。投影的方向必然与 w 的方向雷同，所以无妨将第一项用 w 向量代替

$$
\begin{aligned}
p_i &= X_i \cos \theta & (1)\\
&= X_i \frac{w^TX_i}{\mid w \mid \mid X_i \mid} & (2) \\
&= \frac{X_i}{\mid X_i \mid} w^TX_i & (3) \\
&= w^TX_iw & (4) \\
\end{aligned}
$$

均值向量与协方差矩阵

（1）样本为二分类，N_1 示意第一类样本数量，N_2 示意第二类样本数量

（2）第一类样本点投影的均值向量

（3）第一类样本点投影的协方差矩阵

（4）第二类样本点投影的均值向量

（5）第二类样本点投影的协方差矩阵

$$
\begin{aligned}
N &=N_{1}+N_{2} & (1)\\
\mu_{p_{1}} &=\frac{1}{N_{1}} \sum_{i=1}^{N_{1}} p_{i} & (2)\\
\sigma_{p_{1}} &=\frac{1}{N_{1}} \sum_{i=1}^{N_{1}}\left(p_{i}-\mu_{p_{1}}\right)\left(p_{i}-\mu_{p_{1}}\right)^{T} & (3)\\
\mu_{p_{2}} &=\frac{1}{N_{2}} \sum_{i=1}^{N_{2}} p_{i} & (4)\\
\sigma_{p_{2}} &=\frac{1}{N_{2}} \sum_{i=1}^{N_{2}}\left(p_{i}-\mu_{p_{2}}\right)\left(p_{i}-\mu_{p_{2}}\right)^{T} & (5)
\end{aligned}
$$

代价函数

咱们晓得样本点的协方差能够用于掂量两个变量的总体误差，那么能够应用协方差的大小来示意类内。而样本点的均值点能够用来示意绝对地位，那么能够应用均值点来示意类间。咱们的指标是让投影的“类内小、类间大”，那么能够写出对应的代价函数如下：

$$
\operatorname{Cost}(w)=\frac{\left(w^{T} \mu_{p_{1}}-w^{T} \mu_{p_{2}}\right)^{2}}{w^{T} \sigma_{p_{1}} w+w^{T} \sigma_{p_{2}} w}
$$

分子为均值向量大小之差的平方，该值越大代表类间越大。分母为两类样本点的协方差之和，该值越小代表类内越小，咱们的指标就是求使得该代价函数最大时的 w：

$$
w=\underset{w}{\operatorname{argmax}}\left(\frac{\left(w^{T} \mu_{p_{1}}-w^{T} \mu_{p_{2}}\right)^{2}}{w^{T} \sigma_{p_{1}} w+w^{T} \sigma_{p_{2}} w}\right)
$$

咱们先来看下代价函数分子的局部：

（1）将投影的均值向量带入分子中

（2）能够将公共的 w 的转置与 w 提出来，察看后能够写成两类样本点的均值向量之差

（3）两头两项为实数能够提到后面，w 为单位向量，与本人相乘为 1

（4）将平方写成向量乘积的模式

$$
\begin{aligned}
\left(w^{T} \mu_{p_{1}}-w^{T} \mu_{p_{2}}\right)^{2} &=\left(w^{T}\left(\frac{1}{N_{1}} \sum_{i=1}^{N_{1}} w^{T} X_{i} w\right)-w^{T}\left(\frac{1}{N_{2}} \sum_{i=1}^{N_{2}} w^{T} X_{i} w\right)\right)^{2} & (1)\\
&=\left(w^{T}\left(w^{T}\left(\mu_{1}-\mu_{2}\right) w\right)\right)^{2} & (2) \\
&=\left(w^{T}\left(\mu_{1}-\mu_{2}\right)\right)^{2} & (3) \\
&=w^{T}\left(\mu_{1}-\mu_{2}\right)\left(\mu_{1}-\mu_{2}\right)^{T} w & (4)
\end{aligned}
$$

再来看下其中一类的协方差矩阵的局部：

（1）协方差矩阵的定义

（2）带入投影向量与投影的均值向量

（3）能够将公共的 w 的转置与 w 提出来，两头改写成样本点向量与样本点均值向量之差

（4）开展后一项的转置，将实数局部写到后面

（5）将两个实数相乘写成向量的乘法并将公共的 w 的转置与 w 提出来

（6）察看中括号中的局部，能够写成样本点的协方差矩阵的模式

$$
\begin{aligned}
\sigma_{p_{1}} &=\frac{1}{N_{1}} \sum_{i=1}^{N_{1}}\left(p_{i}-\mu_{p_{1}}\right)\left(p_{i}-\mu_{p_{1}}\right)^{T} & (1)\\
&=\frac{1}{N_{1}} \sum_{i=1}^{N_{1}}\left(w^{T} X_{i} w-\frac{1}{N_{1}} \sum_{j=1}^{N_{1}} w^{T} X_{j} w\right)\left(w^{T} X_{i} w-\frac{1}{N_{1}} \sum_{j=1}^{N_{1}} w^{T} X_{j} w\right)^{T} & (2) \\
&=\frac{1}{N_{1}} \sum_{i=1}^{N_{1}}\left(w^{T}\left(X_{i}-\mu_{1}\right) w\right)\left(w^{T}\left(X_{i}-\mu_{1}\right) w\right)^{T} & (3) \\
&=\frac{1}{N_{1}} \sum_{i=1}^{N_{1}}\left(w^{T}\left(X_{i}-\mu_{1}\right)\right)\left(w^{T}\left(X_{i}-\mu_{1}\right)\right) w w^{T} & (4)\\
&=\left(w^{T}\left(\frac{1}{N_{1}} \sum_{i=1}^{N_{1}}\left(X_{i}-\mu_{1}\right)\left(X_{i}-\mu_{1}\right)^{T}\right) w\right) w w^{T} & (5)\\
&=w^{T} \sigma_{1} w w w^{T} & (6)
\end{aligned}
$$

代价函数的分母局部：

（1）带入上式中协方差矩阵

（2）将实数局部提到后面，前面 w 为单位向量，与本人相乘为 1

（3）化简可得

（4）提出公共局部

$$
\begin{aligned}
w^{T} \sigma_{p_{1}} w+w^{T} \sigma_{p_{2}} w &=w^{T}\left(w^{T} \sigma_{1} w w w^{T}\right) w+w^{T}\left(w^{T} \sigma_{2} w w w^{T}\right) w & (1)\\
&=w^{T} \sigma_{1} w\left(w^{T} w\right)\left(w^{T} w\right)+w^{T} \sigma_{2} w\left(w^{T} w\right)\left(w^{T} w\right) & (2)\\
&=w^{T} \sigma_{1} w+w^{T} \sigma_{2} w & (3)\\
&=w^{T}\left(\sigma_{1}+\sigma_{2}\right) w & (4)
\end{aligned}
$$

代价函数：

（1）代价函数的定义

（2）带入下面推出的分子分母局部

（3）应用 S_b、S_w 来代替两头局部，失去新的代价函数

（4）其中 S_b 被称为 ” 类间散度矩阵 ”（between-class scatter matrix）

（5）其中 S_w 被称为 ” 类内散度矩阵 ”（within-class scatter matrix）

$$
\begin{aligned}
\operatorname{Cost}(w) &=\frac{\left(w^{T} \mu_{p_{1}}-w^{T} \mu_{p_{2}}\right)^{2}}{w^{T} \sigma_{p_{1}} w+w^{T} \sigma_{p_{2}} w} & (1)\\
&=\frac{w^{T}\left(\mu_{1}-\mu_{2}\right)\left(\mu_{1}-\mu_{2}\right)^{T} w}{w^{T}\left(\sigma_{1}+\sigma_{2}\right) w} & (2)\\
&=\frac{w^{T} S_{b} w}{w^{T} S_{w} w} & (3) \\
S_{b} &=\left(\mu_{1}-\mu_{2}\right)\left(\mu_{1}-\mu_{2}\right)^{T} & (4)\\
S_{w} &=\sigma_{1}+\sigma_{2} & (5)
\end{aligned}
$$

代价函数最优化

（1）代价函数的新模式，为 S_b 与 S_w 的 ” 狭义瑞利商 ²（generalized Rayleigh quotient）”

（2）能够看到代价函数分子分母都是 w 的二次项，所以代价函数与 w 的长度无关，即缩放 w 不影响代价函数，无妨令分母为 1。能够将问题转化为当分母为 1 时，求分子后面加一个负号的最小值。

（3）能够使用拉格朗日乘数法 ³，引入一个新的变量 λ，能够将（2）式改写成新的模式

（4）对（3）式求偏导并令其等于零向量

（5）察看后发现 S_b* w 的方向恒为两类样本点的均值向量之差的方向，无妨令其为 λ 倍的两类样本点的均值向量之差

（6）这样就能够求出了 w 的方向

$$
\begin{aligned}
\operatorname{Cost}(w) &=\frac{w^{T} S_{b} w}{w^{T} S_{w} w} & (1)\\
\Rightarrow & \begin{aligned}
\min _{w} \quad-w^{T} S_{b} w \\
s . t . \quad w^{T} S_{w} w=1
\end{aligned} & (2)\\
L(w, \lambda) &= -w^{T} S_{b} w+\lambda\left(w^{T} S_{w} w-1\right) & (3)\\
\frac{\partial L(w, \lambda)}{\partial w} &= -2 S_{b} w+2 \lambda S_{w} w=0 & (4)\\
S_{b} w &=\lambda\left(\mu_{1}-\mu_{2}\right) & (5)\\
w &=S_{w}^{-1}\left(\mu_{1}-\mu_{2}\right) & (6)
\end{aligned}
$$

线性判别分析的核心思想在后面也介绍过——“类内小、类间大”，依照最初求得的公式间接计算即可。

（1）别离计算每一类的均值向量

（2）别离计算每一类的协方差矩阵

（3）计算每类协方差矩阵之和的逆矩阵，能够应用 SVD 矩阵合成来简化求逆的复杂度

（4）带入公式求出权重系数 w

求新样本的分类时，只需判断新样本点离哪一个分类的均值向量更近，则新样本就是哪个分类，如下所示：

$$
k=\underset{k}{\operatorname{argmin}}\left|w^{T} x-w^{T} \mu_{k}\right|
$$

应用 Python 实现线性判别分析（LDA）：

def lda(X, y):
   """
   线性判别分析（LDA）args:
       X - 训练数据集
       y - 指标标签值
   return:
       w - 权重系数
   """
   # 标签值
   y_classes = np.unique(y)
   # 第一类
   c1 = X[y==y_classes[0]][:]
   # 第二类
   c2 = X[y==y_classes[1]][:]
   # 第一类均值向量
   mu1 = np.mean(c1, axis=0)
   # 第二类均值向量
   mu2 = np.mean(c2, axis=0)
   sigma1 = c1 - mu1
   # 第一类协方差矩阵
   sigma1 = sigma1.T.dot(sigma1) / c1.shape[0]
   sigma2 = c2 - mu2
   # 第二类协方差矩阵
   sigma2 = sigma2.T.dot(sigma2) / c2.shape[0]
   # 求权重系数
   return np.linalg.pinv(sigma1 + sigma2).dot(mu1 - mu2), mu1, mu2

def discriminant(X, w, mu1, mu2):
   """
   判断新样本点
   args:
       X - 训练数据集
       w - 权重系数
       mu1 - 第一类均值向量
       mu2 - 第二类均值向量
   return:
       分类后果
   """
   a = np.abs(X.dot(w) - mu1.dot(w))
   b = np.abs(X.dot(w) - mu2.dot(w))
   return np.argmin(np.array([a, b]), axis=0)

scikit-learn⁴ 实现线性判别分析：

from sklearn.discriminant_analysis import LinearDiscriminantAnalysis

# 初始化线性判别分析器
lda = LinearDiscriminantAnalysis()
# 拟合线性模型
lda.fit(X, y)
# 权重系数
w = lda.coef_
# 截距
b = lda.intercept_

如果你应用 sklearn 提供的线性判别分析的办法，会发现求解进去的后果与下面本人实现的后果不同，这是因为 sklearn 应用的是另一种办法，并有没应用狭义瑞利商的模式，而是从概率分布的角度来做分类，前面一节再来介绍该办法。

下图展现了存在二种分类时的演示数据，其中红色示意标签值为 0 的样本、蓝色示意标签值为 1 的样本：

下图为拟合数据的后果，其中浅红色示意拟合后依据权重系数计算出预测值为 0 的局部，浅蓝色示意拟合后依据权重系数计算出预测值为 1 的局部：

https://en.wikipedia.org/wiki…
https://en.wikipedia.org/wiki…
https://en.wikipedia.org/wiki…
https://scikit-learn.org/stab…

残缺演示请点击这里

注：本文力求精确并通俗易懂，但因为笔者也是初学者，程度无限，如文中存在谬误或脱漏之处，恳请读者通过留言的形式批评指正

本文首发于——AI 导图 ，欢送关注

关于人工智能:机器学习算法系列十线性判别分析算法一Linear-Discriminant-Analysis-Algorithm

一、引言

二、模型介绍

三、代价函数

四、算法步骤

五、代码实现

六、第三方库实现

七、数据演示

八、思维导图

九、参考文献