机器学习——特征工程之数据降维

机器学习——特征工程之数据降维:低维嵌入（一）前言低维嵌入（MDS）主成分分析（PCA）前言前面关于特征工程已经可以将大部分数据集转成期望的纯数字形式，但是有时数据维数太多会造成维数灾难，，所以需要降维。降维有几种方法：低维嵌入(MDS)、主成分分析(PCA）、线性判别分析(LDA)、核化线性降维（KPCA）、局部线性嵌入（LLE）、SVD。如果有可能，会一一说明（此部分内容大部分来自西瓜书）..

macan_dct

2093人浏览 · 2019-09-05 19:01:35

macan_dct · 2019-09-05 19:01:35 发布

机器学习——特征工程之数据降维

前言

前面关于特征工程已经可以将大部分数据集转成期望的纯数字形式，但是有时数据维数太多会造成维数灾难，，所以需要降维。降维有几种方法：低维嵌入(MDS)、主成分分析(PCA）、线性判别分析(LDA)、核化线性降维（KPCA）、局部线性嵌入（LLE）、SVD。如果有可能，会一一说明（此部分内容大部分来自西瓜书）。

一、低维嵌入（MDS）

解释什么是低维嵌入：观测或者收集到的数据样本虽然是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维嵌入。
下面开始推导：

假定m个样本在原始空间的距离矩阵为:
$D\in \mathbb{R}^{m\ast m}$

其第 i 行 j 列的元素dist_i,j为样本x_i到x_j的距离。

举例说明距离矩阵D：
原始空间数据长下面这样(m =4)：
	属性1	属性2	属性3	
x1   a 		  b		 c
x2   d        e      f 
x3   g        h      i
x4   j        k      l
那么距离矩阵D如下：
[dist(x1,x1)  dist(x1,x2)  dist(x1,x3)	dist(x1,x4)] 
[dist(x2,x1)  dist(x2,x2)  dist(x2,x3)	dist(x2,x4)]
[dist(x3,x1)  dist(x3,x2)  dist(x3,x3)	dist(x3,x4)]
[dist(x4,x1)  dist(x4,x2)  dist(x4,x3)	dist(x4,x4)]

低维嵌入降维的终极目的：获得样本在d^`维空间的表示，即

$z\in \mathbb{R}^{d^{`}*m},d^{`}\leq d$
并且任意两个样本在d^`维空间中的欧式距离等于原始空间中的距离(这也是整个算法的核心，下面的推导过程是以此为约束条件的)：
$\left \| z_{i}- z_{j} \right \|= dist_{ij}\tag{1}$
(1)式两边取平方：
$dist_{ij}^{2} = \left \|z _{i} \right \|^{2}+\left \|z _{j} \right \|^{2}-2z_{i}^{T}z_{j} \tag{2}$

$令B=Z^{T}Z\in \mathbb{R^{m*m}}，其中B为降维后样本的内积矩阵，b_{ij}=z_{i}^{T}z_{j}，带人2式中，得：$

$dist_{ij}^{2} = \left \|z _{i} \right \|^{2}+\left \|z _{j} \right \|^{2}-2z_{i}^{T}z_{j}=b_{ii}+b_{jj}-2b_{ij}\tag{3}$

将降维后的样本Z中心化： $\sum_{i=1}^{m}z_{i}=0\tag{4}$
则有：矩阵B的行与列之和均为零，即
$\sum_{i=1}^{m}b_{ij}=b_{1j}+b_{2j}+...+b_{mj}= z_{1}^{T}z_{j}+z_{2}^{T}z_{j}+...+z_{m}^{T}z_{j}\\=(z_{1}^{T}+z_{2}^{T}+...+z_{m}^{T})z_{j}=(\sum_{i=m}^{m}(z_{i})^{T})z_{j}=0\tag{5}$
$同理\sum_{j=1}^{m}b_{ij}=0\tag{6}$
$\sum_{i=1}^{m}dist_{ij}^{2}=\sum_{i=1}^{m}(b_{ii}+b_{jj}-2b_{ij})=b_{11}+b_{jj}-2b_{1j}+b_{22}+b_{jj}-2b_{2j}+...+b_{mm}+b_{jj}-2b_{mj}\\=tr(B)+mb_{jj}+\sum_{i=m}^{m}b_{ij}=tr(B)+mb_{jj}\tag{7}$

$同理\sum_{j=1}^{m}dist_{ij}^{2}=\sum_{j=1}^{m}(b_{ii}+b_{jj}-2b_{ij}) =b_{ii}+b_{11}-2b_{i1}+b_{ii}+b_{22}-2b_{i2}+...+b_{mm}+b_{mm}-2b_{im}\\=tr(B)+mb_{ii}+\sum_{j=m}^{m}b_{ij}\tag{8}$
$\sum_{i=1}^{m}\sum_{j=1}^{m}dist_{ij}^{2}=\sum_{i=1}^{m}(\sum_{j=1}^{m}dist_{ij}^{2})=\sum_{i=1}^{m}(tr(B)+mb_{ii})\\=mtr(B)+m(b_{11}+b_{22}+...+b_{mm})\\=mtr(B)+mtr(B)=2mtr(B)\tag{9}$
$其中tr(.)表示矩阵的迹（trace），tr(B)=\sum_{i=1}^{m}\left \| z_{i} \right \|^{2}$
令
$dist_{i·}^{2}=\frac{1}{m}\sum_{j=1}^{m}dist_{ij}^{2}\tag{10}$ $dist_{·j}^{2}=\frac{1}{m}\sum_{i=1}^{m}dist_{ij}^{2}\tag{11}$
$dist_{··}^{2}=\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}dist_{ij}^{2}\tag{12}$
由(3)式和(4)~(12)可知：
$b_{ij}=-\frac{1}{2}(dist_{ij}^{2}-dist_{i·}^{2}-dist_{·j}^{2}+dist_{··}^{2})\tag{13}$
推导出（13）式的目的就是使用降维前后保持不变的距离矩阵求内积矩阵B。怎么求？就是用（13）式一个一个地求！

到此为止，已经获得样本在d^`维空间中的表示（内积形式）。
下面对内积矩阵B做特征值分解（eigenvalue decomposition）

令 $\Lambda =diag(\lambda_{1},\lambda_{1},...,\lambda_{d})$ 表示内积矩阵B的特征值构成的特征矩阵其中， $\lambda_{1}\geq \lambda_{2}\geq \lambda_{3}...\geq \lambda_{d}$ ,V为其特征值对应的特征向量组成的特征矩阵，则内积矩阵可以表示成：
$B=V\Lambda V^{T}$
$假定在d个特征值中有d^{*}个非零特征值，构成对角矩阵 \Lambda_{*}=diag(\Lambda_{1},\Lambda_{2},...,\Lambda_{d^{*}})，令V_{*}表示对应的特征向量矩阵，则由B=Z^{T}Z，可得:$
$Z=\Lambda_{*}^{\frac{1}{2}}V_{*}^{T}\in \mathbb{R}^{d^{*}*m}$

Z就是新样本空间的新样本。
算法流程（直接截图了）：
在这里插入图片描述代码实现：

sklearn.manifold.MDS(n_components=2,metric=True,n_init=4,max_iter=300,verbose=0,eps=0.001,n_jobs=1,random_state=None,dissimilarity=’euclidean’)
##自己实现：
def MDS(X,n_component=None):
	dist = np.zeros((X.shape[0],X.shape[0],))
	m = dist.shape[0]
	B = np.zeros((X.shape[0],X.shape[0],))
 	#计算距离矩阵,大小为m*m
	for i in range(m):
    for j in range(m):
        #得到距离矩阵
        dist[i,j] = np.linalg.norm(X[i] - X[j])
	#计算内积矩阵,大小为m*m
	for i in range(m):
    	for j in range(m):
        	B[i,j] = -(np.square(dist[i,j]) - np.square(dist[i,:]).sum()/ m - np.square(dist[:,j]).sum()/ m + np.square(dist.reshape(1,-1)).sum()/ m**2)
	V,lamda = np.linalg.eig(B)
	V = np.diag(V)
	Z = np.dot(np.sqrt(V),lamda.T)
	return Z

二、主成分分析（PCA）

主成分分析（Principal Component Analysis,PCA）是最常用的数据降维算法。
算法思想引导（就是说PCA是怎么来的）：
对于正交属性空间中的样本点，可从如下两个方面考虑用一个超平面对所有样本进行表达：

最近重构性：样本点到这个超平面的距离都足够近；
最大可分性：样本点在这个超平面上的投影能尽可能分开
先记住这两个要求，这里不得不说协方差和散度矩阵
目标：提取最有价值的信息（基于方差）
个人对PCA算法的理解：比如原始数据在一个维度上的分布是非常密集的，PCA则是找出一个轴，将密集的点分布到这个轴上，将密集程度降低，也是找到轴中方差最大的方向，这样样本就会变得稀疏，所以更适合去做分类等任务。（可能看不懂，后面慢慢解释）

1、基本概念

向量的表示及基变换

解释“基”：举例，任意一个坐标，取（1,2），在“正常的”坐标系下，它表示一个向量，如下图（灵魂画手）：
在这里插入图片描述
这里面说的“正常”坐标系就是上面的基，若改变这个坐标系：

那么上面的向量就不是（1,2）了。
举这个例子就是为了说明基表示的是一种对数据的衡量的标准，那么基变换就是由原来的基映射到另外的基。
内积:

$有两个向量：A=(a_{1},a_{2},...,a_{n}),B=(b_{1},b_{2},...,b_{n})，则其内积为：$
$A^{T}B^{T} = (a_{1},a_{2},...,a_{n})^{T}·(b_{1},b_{2},...,b_{n})=a_{1}b_{1}+a_{2}b_{2}+...+a_{n}b_{n}$
解释内积: $A \cdot B = ∣ A ∣ ∣ B ∣ c o s (a)$
设向量B的模为1，则A和B的内积值等于A向B所在直线投影的矢量长度。
在这里插入图片描述
基: 以坐标（3,2）为例，实际上表示线性组合： $x(1,0)^{T}+y(0,1)^{T}$ ，(1,0)和(0,1)叫做二维空间中的一组基
强调一点：基是正交的（即内积为0，或者直观说相互垂直），正交能保证基是线性无关的。

基变换:数据与一个基做内积运算，结果作为第一个新的坐标分量，然后与第二个基做内积运算，结果作为第二个新坐标分量
举例：数据（3,2）映射到基中坐标：
$\begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{pmatrix}\begin{pmatrix} 3\\2 \end{pmatrix}=\begin{pmatrix} \frac{5}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}} \end{pmatrix}$
一定要理解这块的变换所包含的数学意义，原基就是图中黑色的坐标系，做内积运算后将（3,2）投影到另一个基坐标上。

在这里插入图片描述 $\begin{pmatrix} p_{1}\\ p_{2}\\ ...\\ p_{R}\\ \end{pmatrix}\begin{pmatrix} a_{1} &a_{2} &... &a_{M} \end{pmatrix} =\begin{pmatrix} p_{1}a_{1}& p_{1}a_{2} & ... & p_{1}a_{M}\\ p_{2}a_{1}& p_{2}a_{2} &... &p_{2}a_{M}\\ ...& ... &... &... \\ p_{r}a_{1}& p_{R}a_{2} &... &p_{R}a_{M} \end{pmatrix}$
两个矩阵相乘的意义是将右边矩阵中的每一列列向量变换到左边向量矩阵中每一行行向量为基所表示的空间中去——————PCA算法的中心思想。

2、怎样找基

嗯？听着怪怪的。
上面已经说了基和基变换的意义，那么为了实现PCA，应该怎样找基？
这块就得说协方差矩阵了：

方差矩阵和协方差

在说协方差矩阵之前，先考虑一个问题：向量与基相乘，可以实现基变换（说映射，改变方向都行），那么如何选择这个基（或者说方向）才能尽量保留最多的原始信息？

答：一种直观的方法——希望投影后的投影值尽可能分散（西瓜书的一个算法推导方向）

那么问题又来了，怎样定义上面呢说的分散？

答：用方差

方差：
$Var(x)=\frac{1}{m-1}\sum_{i=1}^{m}(x_{i} - \mu)^{2},其中\mu=\frac{1}{m}\sum_{i=1}^{m}x_{i} ，为样本均值$
PCA算法推导的终极目标：寻找一个一维基，使得所有数据变换为这个基上的坐标表示后，方差最大
协方差：（假设均值为0时）： $Cov(x,y)=\frac{1}{m-1}\sum_{i=1}^{m}(x_{i}-\mu)(y_{i}-\mu),其中\mu=\frac{1}{m}\sum_{i=1}^{m}x_{i} ，为样本均值$
问题：但是单纯只选择方差最大的方向，后续方向应该会和方差最大的方向重合，这样的话会使特征线性相关，线性相关是无法表现出原始样本的特征的。
解决办法：为了让两个字段尽可能表示出更多的原始信息，不希望他们之间存在（线性）相关的。为了解决这个这个问题，可以使用协方差表示其相关性（公式如上，具体数学意义详见：https://blog.csdn.net/GoodShot/article/details/79940438）
当协方差为0时，表示两个字段完全独立。为了让协方差为0，选择第二个基时，只能在与第一个基正交的方向上选择。因此最终选择的两个方向一定是正交的。
好了，到这里就知道了应该用方差和协方差来找基。

3、优化目标

目标：将一组N维向量降为K维（K大于0，小于N），目标是选择K个单位正交基。使原始数据变换到这组基上后，各字段两两协方差为0，字段的方差尽可能大。
定义协方差矩阵
上面已经说过了方差和协方差，这块举例说明（注：下面的y不是数据集中的标签，它仅仅是数据集中的一个样本），以一个有两个样本的数据集为例：
$X=\begin{pmatrix} x_{1} & x_{2} &... &x_{m} \\ y_{1}& y_{2} & ... & y_{m} \end{pmatrix}$
为了得到其方差和协方差，可以作如下变换：
$协方差矩阵：\frac{1}{m}XX^{T}=\begin{pmatrix} \frac{1}{m}\sum_{i=1}^{m}a_{i}^{2} & \frac{1}{m}\sum_{i=1}^{m}a_{i}b_{i}\\ \frac{1}{m}\sum_{i=1}^{m}a_{i}b_{i}& \frac{1}{m}\sum_{i=1}^{m}b_{i}^{2} \end{pmatrix}$
这样变换后，矩阵对角线上的两个元素分别是两个字段的方差，而其他元素是x和y的协方差。

前面说到，为了更好地降维并保持原始样本特征，应该让方差最大，协方差为0，那么观察上面的协方差矩阵，需要将其对角线最大化（可按照从大到小排列），非对角线上的元素等于0。

############################这部分属于线代知识，如果了解请跳过########################
那么就会想到线性代数这门课里的矩阵对角化了：
$PXP^{T}=\Lambda =\begin{pmatrix} \lambda_{1} & & & \\ & \lambda_{2} & & \\ & & ...& \\ & & &\lambda_{n} \end{pmatrix}$
什么样的矩阵可以进行对角化？
实对称矩阵：一个n行n列的实对称矩阵一定可以找到n个单位正交特征向量 $E=(e_{1},e_{2},...,e_{n})$ ，使得 $E^{T}XE=\Lambda =\begin{pmatrix} \lambda_{1} & & & \\ & \lambda_{2} & & \\ & & ...& \\ & & &\lambda_{n} \end{pmatrix},其中\lambda_{1} ,\lambda_{2},...\lambda_{n}为X的特征值$
根据特征值的从大到小，将特征向量从上到下排列，则用前K行组成的矩阵乘原始数据矩阵X，就得到了我们需要的降维后的矩阵Y。
！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
说完了原理，再举个实际的计算例子：
$原始数据：X=\begin{pmatrix} -1 &-1&0&2&0 \\ -2 &0&0&1&1 \end{pmatrix}$
$协方差矩阵：C=\frac{1}{m}XX^{T}=\frac{1}{5}\begin{pmatrix} -1 &-1&0&2&0 \\ -2 &0&0&1&1 \end{pmatrix}\begin{pmatrix} -1 &-2\\ -1 &0\\ 0&0\\ 2&1\\ 0&1 \end{pmatrix}=\begin{pmatrix} \frac{6}{5} &\frac{4}{5}\\ \frac{4}{5} &\frac{6}{5} \end{pmatrix}$

$特征值：\lambda_{1}=2,\lambda_{2}=\frac{2}{5},对应的特征向量：c_{1}=\begin{pmatrix} 1 \\ 1 \end{pmatrix},c_{2}=\begin{pmatrix} -1 \\ 1 \end{pmatrix}$
$=\begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}} \end{pmatrix}$
$对角化：PCP^{T}=\begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}} \end{pmatrix}\begin{pmatrix} \frac{6}{5} & \frac{4}{5}\\ -\frac{4}{5}&\frac{6}{5} \end{pmatrix}\begin{pmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}} \end{pmatrix}=\begin{pmatrix} 2&0\\ 0&\frac{2}{5} \end{pmatrix}$
$降维：Y=\begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{pmatrix}\begin{pmatrix} -1 &-1&0&2&0 \\ -2 &0&0&1&1 \end{pmatrix}=\begin{pmatrix} -\frac{3}{\sqrt{2}} & -\frac{1}{\sqrt{2}}&0&\frac{3}{\sqrt{2}}&-\frac{1}{\sqrt{2}} \end{pmatrix}$

！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
代码实现：

##库函数API不多说，直接调用：
sklearn.decomposition.PCA(n_components=None, copy=True, whiten=False)
#自己手写
def PCA(X,n_component= None):
	m = X.shape[0]
	#先去中心化
    mean_vec = X - np.mean(X,axis = 0)
    X = X - mean_vec
    #得到协方差矩阵
    cov_mat = np.dot(X,X.T)/ (m -1)
    #计算特征值和对应的特征向量
    lamda, V = np.linalg.eig(cov_mat)
    #按照特征值的从大到小，将特征向量排序
    descent_index = np.argsort(-lamda)
    #用n_component选择最大的n个特征值对应的特征向量，与原数据相乘
    V = V[:,descent_index][:,:n_component]
    Y = np.dot(V,X)
    return Y

三、核化线性降维、核主成分分析（KPCA）

前面说到的PCA属于线性降维方法，但它存在缺点，用下图来说明其缺点：
在这里插入图片描述有一个三维的数据，它的真实分布长成(a)的样子，“不失真”地映射到二维它长成(b)的样子，如果用PCA降到二维，它长成©的样子，对比(b)和©，则可以发现原样本数据在线性降维下会丢失低维结构。
为了解决这个问题，提出了非线性降维，是基于核技巧对线性降维方法进行“核化(kernelized)”，下面开始推导核主成分分析(Kernelized PCA，简称KPCA)
算法主要分两步：

第一步：将样本映射到高维空间
第二步：对样本在高维空间进行PCA

$首先引入映射函数\varphi：它将原样本x_{i}映射到高维z_{i}，即\varphi(x_{i})=z_{i}，其中z_{i}为样本点x_{i}在高维特征空间中的像$
假定在高维特征空间把数据投影到由W确定的超平面上，即PCA欲求：
$(\sum_{i=1}^{m}z_{i}z_{i}^{T})W = \lambda W \tag{1}$
作下变换：
$W=\frac{1}{\lambda}(\sum_{i=1}^{m}z_{i}z_{i}^{T})W=\sum_{i=1}^{m}z_{i} \frac{z_{i}^{T}W}{\lambda}=\sum_{i=1}^{m}z_{i}\alpha_{i}\tag{2}$

$将\varphi(x_{i})=z_{i}带入(1)式：$
$(\sum_{i=1}^{m}\varphi(x_{i})\varphi(x_{i})^{T})W=\lambda W \tag{3}$
$将\varphi(x_{i})=z_{i}带入(2)式：$
$W=\sum_{i=1}^{m}\varphi(x_{i})\alpha_{i}\tag{4}$
一般情况下，需要依靠经验才能设计出 $\varphi$ ，所以这里使用核函数：
$k(x_{i},x_{j}) = \varphi(x_{i})^{T}\varphi(x_{j})\tag{5}$
将(5)和(4)带入(3)，化简得（这块自己动手）：
$KA=\lambda A\tag{6}$
$其中K为核矩阵，(K)_{ij} = K(x_{i},x_{j})，A=(a_{1};a_{2}:...:a_{m})$
从(6)式中可以看出，与PCA相同，取K最大的 $d^{`}个特征值对应的特征向量即可（参照PCA）$

代码（调库）：
form sklearn.decomposition import KernelPCA

以PCA为基础的算法演变还有增量PCA(Incremental PCA)、基于随机化SVD的PCA、稀疏主成分分析 ( SparsePCA 和 MiniBatchSparsePCA )…以后用到哪个再说哪个吧。

四、线性判别分析（Linear Discriminant Analysis,LDA)

说在该算法的前面：PCA和LDA都可以作为降维的方法，但PCA属于无监督，LDA属于有监督，注意区分。
算法思想：给定训练集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远;在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的来确定新样本点的类别。这个思想在西瓜书上的图上已经说的很清晰了。
在这里插入图片描述
知道了算法思想，下面开始推导算法（note：这是有监督算法）：
给定数据集 $D=\{(x_{i},y_{i})\}_{i=1}^{m}，y_{i}\in\{0,1\} (这是标签，有监督，这块以二分类为例)$
定义一些变量：
令 $X_{i}，表示第i\in\{0,1\}类示例的集合$
$\mu_{i}= \frac{1}{d}\sum_{k=1}^{d}x_{ik}，表示第i\in\{0,1\}类的均值向量，属于第i类的样本个数为d$
$\Sigma_{i}= \begin{pmatrix} x_{1}x_{1} &x_{1}x_{2}&...&x_{1}x_{d}\\ x_{2}x_{1} &x_{2}x_{2}&...&x_{2}x_{d}\\ ...&...&...&...\\ x_{d}x_{1} &x_{d}x_{2}&...&x_{d}x_{d} \end{pmatrix},表示第i\in\{0,1\}类示例的协方差矩阵，属于第i类的样本个数为d$
找到一个基，这里记为w，将数据投影到w上，则两类样本的中心在直线上的投影分别为 $w^{T}\mu_{0}和w^{T}\mu_{1}$ ;将所有样本点都投影到直线上，则两类样本的协方差分别为 $w^{T}\Sigma_{0}w和w^{T}\Sigma_{1}w$ 。
上面说过了，这也是LDA算法的核心，即：

(1)欲使同类样例的投影点尽可能接近，可以让同类样例投影点的协方差尽可能小，即： $w^{T}\Sigma_{0}w+w^{T}\Sigma_{1}w$ 尽可能小:
(2)欲使异类样例的投影点尽可能远离，可以让类中心之间的距离尽可能大，即： $||w^{T}\mu_0-w^{T}\mu_{1}||_{2}^{2}$ 尽可能大
同时考虑上面的两种情况，便得到了LDA算法的优化目标：
最大化优化目标： $J=\frac{||w^{T}\mu_0-w^{T}\mu_{1}||_{2}^{2}}{w^{T}\Sigma_{0}w+w^{T}\Sigma_{1}w}=\frac{\left \| (w^{T}\mu_{0}-w^{T}\mu_{1}) \right \|_{2}^{2} }{w^{T}(\Sigma_{0}+\Sigma_{1})w}=\frac{\left\| (\mu_{0}-\mu_{1})^{T}w \right\|_{2}^{2}}{w^{T}(\Sigma_{0}+\Sigma_{1})w}\\= \frac{[(\mu_{0}-\mu_{1})^{T}w]^{T}(\mu_{0}-\mu_{1})^{T}w}{w^{T}(\Sigma_{0}+ \\Sigma_{1})w}=\frac{w^{T}(\mu_0-\mu_1)^{T}(\mu_{0}-\mu_{1})^{T}w}{w^{T}(\Sigma_{0}+\Sigma_{1})w}\tag{1}$

为了化简上式，定义两个矩阵：
a、类内散度矩阵(within_class scatter matrix)：
$S_{w}=\Sigma_{0}+\Sigma_{1}=\sum_{x\in X_{0}}(x-\mu_{0})(x-\mu_{0})^{T}+\sum_{x\in X_{1}}(x-\mu_{1})(x-\mu_{1})^{T}\tag{2}$
b、类间散度矩阵(between-class scatter matrix):
$S_{b}=(\mu_{0}-\mu_{1})(\mu_{0}-\mu_{1})^{T}\tag{3}$
将(2)和(3)带入(1)中，得到LDA欲最大化的目标，即 $S_{b}和S_{w}$ 的广义瑞利商（也不需要知道是啥玩意，就记住这怎么来的就行了）
$J=\frac{w^{T}S_{b}w}{w^{T}S_{w}w}\tag{4}$

为了确定w(基)，将问题转成最优化问题，书上说：式(4)的分子与分母都是关于w的二次项，因此解与w的长度无关，只与方向有关，不是一般性，令 $w^{T}S_{w}w=1$ ，则(4)式等价于：
$min_{w} -w^{T}S_{b}w \\ s.t. w^{T}S_{w}w=1\tag{5}$
下面开始解(5)定义的最优化问题。
引入拉格朗日函数（一般这种约束问题都用拉格朗日乘子法，要不就是EM算法）：
$l(w)=-w^{T}S_{b}w+\lambda (w^{T}S_{w}w-1)\tag{6}$
对w求导：
$\frac{\partial l(w)}{\partial w} = -\frac{\partial (w^{T}S_{b}w)}{\partial w} +\lambda \frac{\partial (w^{T}S_{w}w-1)}{\partial w}=-(S_{b}+S_{b}^{T})w+\lambda (S_{W}+S_{W}^{T})w\tag{7}$
由(2)和(3)式，可知 $S_{b} =S_{B}^{T},S_{w} =S_{w}^{T}$ ,则上式可化简为：
$\frac{\partial l(w)}{\partial w}=-2S_{b}w+2\lambda S_{w}w\tag{8}$
令(8)式等于0，可得：
$S_{b}w=\lambda S_{w}w\tag{9}$
因 $S_{b}w的方向恒为\mu_{0}-\mu_{1},令S_{b}w= \lambda (\mu_{0}-\mu_{1})$ ,带入(9)式中：
$w=S_{w}^{-1}(\mu_{0}-\mu_{1})\tag{10}$
注意到上面需要求矩阵的逆，求逆必须要保证矩阵是可逆的，若不可逆则需要用SVD求奇异值，这块后面会说。
这是针对二分类的任务做了推导，对于多分类，添加了一个全局散度矩阵，但是大同小异，这块就不多介绍了。
LDA关键步骤：

    对d维数据进行标准化处理（d为特征数量）
    对于每一类别，计算d维的均值向量
    构造类间的散布矩阵 SB以及 类内散布矩阵 SW
	计算矩阵 S−1W 、SB的特征值以及对应的特征向量
	选取前k个特征值所对应的特征向量，构造一个 d∗k维的转换矩阵 W,其中特征向量以列的形式排列
	使用转换矩阵 W将样本映射到新的特征子空间上

代码实现：

这块发现了一篇很好的博客：https://blog.csdn.net/weixin_40604987/article/details/79615968

五、局部线性嵌入（Locally Linear Embedding,LLE）

算法思想：LLE算法希望在降维后的低维空间中依然能保持高维空间中的线性关系
假定某个样本点x_i的坐标能通过它的领域样本x_j，x_k,x_l的坐标通过线性组合重构出来，即：
$x_{i}=w_{ij}x_{j}+w_{ik}x_{k}+w_{il}x_{l}\tag{1}$
目标：LLE希望(1)式的关系在低维空间中得以保持。
LLE先为每个样本x_i找到其近邻下标集合Q_i，然后计算出基于Q_i中的样本点对x_i进行线性重构的系数w_i，优化目标就是使变换前后的领域内的样本的差别最小：
优化目标： $\underset{w_{1},w_{2},...,w_{m}}{min}\sum_{i=1}^{m}\left \| x_{i}-\sum_{j\in Q_{i}} w_{ij}x_{j} \right \|_{2}^{2}\\ s.t.\sum_{j \in Q_{i}}w_{ij}=1\tag{2}$
化简下上述约束问题：
在这里插入图片描述求出了样本在原空间中的线性表达关系，为了使这个线性关系在降维后的低维空间依然保持，w_i依然保持不变，令z_i表示x_i在低维空间坐标，于是第二个优化目标如下：
$\underset{z_{1},z_{2},...,z_{m}}{min}\sum_{i=1}^{m}\left \| z_{i}-\sum_{j\in Q_{i}} w_{ij}z_{j} \right \|_{2}^{2}\\ s.t.\sum_{j \in Q_{i}}w_{ij}=1\tag{3}$
(3)和(2)基本相同，唯一的区别是(2)式中需要确定w_i，而(3)式需要确定x_i对应的低维空间坐标z_i
还是化简下(3)中的优化目标：
$令Z=(z_{1},z_{2},...,z_{m})\in \mathbb{R}^{d^{`}*m},\\(W)_{ij} = w_{ij},\\M=(I-W)^{T}(I-W)$
在这里插入图片描述可将优化目标化简为：
$\underset{Z}{min} tr(ZMZ^{T})\\ s.t.ZZ^{T}=I\tag{4}$

M最小的 $d^{`}个特征值对应的特征向量组成的矩阵即为Z^{T}$

有点乱哈，看下算法伪代码吧：

输入：样本集 $D={x_{1},x_{2},...,x_{m}};$
近邻参数k;
低维空间维数d^`
过程：
1 for i = 1,2,…,m do
2 ----确定x_i的k近邻；
3 ----从式(2)求出w_ij， $j\in Q_{i}$
4 ----对于 $\notin Q_{i},令w_{ij}=0$
5 end for
6 从 $M = (I-W)^{T}(I-M)$ 得到M
7 对M进行特征值分解
8 returnM的最小d^~个特征向量对应的特征值
输出：样本集D在低维空间的投影 $Z=\{z_{1},z_{2},...,z_{m}\}$

六、奇异值分解（SVD）

对矩阵进行分解，有两种办法一个是求特征值和特征矩阵，但必须保证矩阵可逆；另一个办法就是SVD，并不要求矩阵可逆。
前面介绍的几个方法，都存在求特征值和特征向量的步骤，有时矩阵不可逆，要用到SVD。
至于SVD的原理，矩阵分析这门课讲过了，同时我写到这也很累了，比打算扣细节了，下面只说下用法和用处。
目标是将矩阵A分解成如下形式：
$A=U\Sigma V^{T}$
下面说各项是怎么来的：
U：求 $AA^{T}$ 的特征值和特征向量，用单位化的特征向量构成U（左奇异向量）;
V:求 $A^{T}A$ 的特征值和特征向量，用单位化的特征向量构成V（右奇异向量）;
$\Sigma$ :求 $AA^{T}$ 或者 $A^{T}A$ 的特征值的平方根，构成 $\Sigma$ （奇异值）