降维方法
1. 主成分分析
1.1 算法分析
已知样本$\pmb a_1,\pmb a_2,…,\pmb a_N,\pmb a_i \in \mathbb{R}^n$，则按列组成的矩阵:
矩阵的弗罗贝尼乌斯范数：
$tr$代表矩阵的迹函数$trace$（主对角线元素求和，$A^TA$一定是个方阵）。
给定一组标准正交基$\pmb w_1,\pmb w_2,…,\pmb w_N,\pmb w_i \in \mathbb{R}^n$，$\mathbb{R}^n$中的某个向量$\pmb a$可以表示为：
$<,>$表示向量的内积操作，可以看出$<\pmb a,\pmb w_j>$即$\pmb a$在空间中的坐标。现在我们考虑，是否可以将$\pmb a$表示在由$\pmb w_1,\pmb w_2,…,\pmb w_m,m \mathbb{<<} n$，生成的子空间$\mathbb{R}^m$中，使得$<\pmb a,\pmb w_{m+1}>=0,…,<\pmb a, \pmb w_n> = 0$ ?也就是说只需要前$m$个基就可以表示$\pmb a$。
降维准则： 找到一组基，使得数据在这组基表示下，$m+1,…n$维的坐标都是0。
注意：$\pmb w_i$仍然是包含$n$个分量的向量，$m$个包含$n$个元素基向量构成了$n$维空间的一个$m$维子空间（空间的维数等于基向量个数）。
这就可以将问题转化为一个优化问题：
写为矩阵形式即：
其中，$A$为数据的特征矩阵，$W_{n \times m}$为前$m$个正交基按列组成的矩阵，它是半正交的。
tips：因为有$m$个基向量，两两相乘，最后矩阵是一个$m \times m$的单位阵。
由于$tr(A^TA)$这一项与优化目标无关，因此目标函数变为：
求出最忧$W$后，降维数据：
以上推导过程从基向量、最优化角度解释了主成分分析算法。
注意：主成分分析是无监督、线性的降维方法。线性判别分析是有监督的线性降维方法。
说明：降维后的空间与原空间没有对应关系，主成分是原始维度的线性组合得到。
1.2 算法描述
1.3 sklearn中的PCA
PCA位于$sklearn.decomposition$包下。
注意“explained_variance_ratio_”这个指标，表示了原始数据在不同主成分上的方差占比（保留了多少原始数据的方差信息）。
扩展的PCA：Incremental PCA，当数据量特别大无法一次性加载至内存进行奇异值分解时，可以将数据划分为多个mini-batch，然后进行降维。
Kernel PCA：非线性降维。
Question: Can PCA be used to reduce the dimensionality of a highly nonlinear dataset？
Answer: PCA can be used to significantly reduce the dimensionality of most datasets, even if they are highly nonlinear, because it can at least get rid of useless dimensions. However, if there are no useless dimensions — for example, the Swiss roll — then reducing dimensionality with PCA will lose too much information. You want to unroll the Swiss roll, not squash it
2. 非负矩阵分解
非负矩阵分解：Nonnegative Matrix Factorization
3. 局部线性嵌入
局部线性嵌入：Locally Linear Embedding（LLE），属于非线性降维
参考： https://www.cnblogs.com/pinard/p/6266408.html
流形学习（manifold learning）第一次听说”manifold”是在学习生成对抗网络的时候看到的。
推导过程中需要注意的地方：
下图中由$(1)\rightarrow(2)$过程中，因为$\sum_{j\in Q(i)}w_{ij} = 1$，所以$x_i = x_i \times 1 = \sum_{j\in Q(i)}w_{ij}x_i$。
算法描述：
4. 线性判别分析
线性判别分析：Linear Discriminate Analysis（LDA）
降维原则：投影后最小化类内方差，最大化类间方差。属于线性、有监督的降维方法。
参考：https://www.jianshu.com/p/13ec606fdd5f （二分类为例）
样本集：$\{(\pmb x_1,y_1),(\pmb x_2,y_2),…,(\pmb x_N,y_N)\},\pmb x_i \in \mathbb{R}^n$形成的样本矩阵$X_{n \times N}$，降维后数据$\pmb y$是一个$N \times 1$的向量
各个类的均值向量：
降维后的均值向量：
$\pmb w_{n \times 1}$就是我们要求的降维变换，同理：
类内方差：
即：
说明：因为$(\pmb x -\pmb \mu_i)^T\pmb w$与$\pmb w^T(\pmb x-\pmb \mu_i)$ 结果分别是两个实数，可以交换。
令
根据投影后类内方差小（$\tilde s_1^2 + \tilde s_0^2$ 两个都要小总体才能小），类间方差大（$||\pmb \mu_1 - \pmb \mu_2||^2$）。可以写出目标函数：
并且根据上面的式子有：
$S_W$：类内方差（with class）维度：$n \times n$
对于分子，我们有：
令：
$S_B$：类间方差（between class）维度：$n \times n$
所以：
目标函数变为：
对$J(\pmb w)$对$\pmb w$求导并令其等于0即：
注意：$\pmb w^TS_W\pmb w,\pmb w^TS_B\pmb w$结果都是实数，因此等式两边同除$\pmb w^TS_B\pmb w$可得：
注意到：
且$(\pmb \mu_1-\pmb \mu_2)^T\pmb w$结果是一个实数，C也是实数，我们要求的最关键的是$\pmb w$的方向，这些实数并不会改变方向，因此
5. 多维尺度分析
Multidimensional Scaling
基本思想：尽量满足原始高维度空间中样本之间的距离在低维空间中得以保持。
“metric” or “non-metric”
给定样本$(\pmb x_1,\pmb x_2,…,\pmb x_N),\pmb x_i \in \mathbb{R}^n$构成的样本矩阵$X_{n \times N}$，降维后的样本矩阵$Y_{m \times N}$。根据多维尺度分析的基本思想：保持样本间距离不变，原始样本间距离$d_{ij}=||\pmb x_i - \pmb x_j||$构成的矩阵$D_{N \times N}$。
可知$X^TX = -\frac{1}{2}HD_xH, Y^TY = \frac{1}{2}HD_yH$，我们想让$D_x=D_y$，等价的可以通过以下目标函数来求得：
目标函数：
特征值分解：
那么降维后的数据$Y$：
6. 典型关联分析
Canonical correlation analysis
参考：https://www.cnblogs.com/pinard/articles/6288716.html
具体思想：相关系数 $\rho$ 可以分析两组一维数据$X,Y$的线性相关性，$\rho$取值越接近1则$X,Y$的线性相关性越高。虽然相关系数可以很好的帮我们分析一维数据的相关性，但是对于高维数据就不能直接使用了。比如$X$是2维数据，$Y$是三维数据，就不能用相关系数进行分析。那么有没有变通的方法呢？典型关联分析给出了思路，具体就是将多维的$X,Y$分别用线性变换为1维的$X^\prime,Y^\prime$，然后使用相关系数分析1维$X^\prime,Y^\prime$的相关性。问题又来了，如何把$X,Y$变换为$X^\prime，Y^\prime$呢？也就是说降维的准则是什么？典型关联分析使用的准则是变换到1维后，$X^\prime,Y^\prime$的相关系数最大。
亦即：
算法描述：
7. 字典学习
参考：https://zhuanlan.zhihu.com/p/46085035
基本思想：
在人类发展的近几千年历史中，文字对人类文明的推动起着举足轻重的作用。人类用文字记述了千年的历史，用文字留下了各种思想火花，用文字抒发了各种各样的情感等等。但是这一切的内容，只需要一本字典就能表述完。因为人在这环节中的功能，无非就是使用字典当中的字词进行了适当的排列了而已。
基于这种思想，先前的大佬提出了字典学习——Dictionary Learning。
字典学习的目标，就是提取事物最本质的特征（类似于字典当中的字或词语）。如果我们能都获取这本包括最本质的特征的字典，那我们就掌握了这个事物的最本质的内涵。换言之，字典学习将我们的到的对于物体的信息降维，减少了该物体一些无关紧要信息对我们定义这个物体的干扰。
模型建立：
$\lambda_i$称为表示系数，要求尽可能稀疏；$\pmb w_i$被称为”字典“。
问题是如何找到表示系数与字典？可转化为如下优化问题：
其中：$y$即为表示系数，约束条件对应要求表示系数尽可能稀疏。$m >>N$。
写成矩阵形式（有点类似非负矩阵分解形式，W是基，Y是系数）：
由于上述优化问题含有两个优化变量，可采用坐标优化方法，即先固定系数$y$，求出最优的$\pmb w$；然后在求出系数。