乐趣区

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

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

一、引言

  后面学习了一种用回归的形式来做分类的算法——对数几率回归算法,上面再来学习另一种分类算法——线性判别分析算法 1(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 的 ” 狭义瑞利商 2(generalized Rayleigh quotient)”

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

(3)能够使用拉格朗日乘数法 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-learn4 实现线性判别分析:

from sklearn.discriminant_analysis import LinearDiscriminantAnalysis

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

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

七、数据演示

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

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

八、思维导图

九、参考文献

  1. https://en.wikipedia.org/wiki…
  2. https://en.wikipedia.org/wiki…
  3. https://en.wikipedia.org/wiki…
  4. https://scikit-learn.org/stab…

残缺演示请点击这里

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

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

退出移动版