One PUNCH Man——降维_上一节的讨论是基于一个重要假设:任意测试样本

k 近邻（KNN）

KNN是通过测量不同特征值之间的距离进行分类。它的思路是：给定某个测试样本，kNN基于某种距离度量在训练集中找出与其距离最近的k个带有真实标记的训练样本，然后给基于这k个邻居的真实标记来进行预测。如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别，其中K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

kNN虽然是一种监督学习方法，但是它却没有显式的训练过程，而是当有新样本需要预测时，才来计算出最近的k个邻居，因此kNN是一种典型的懒惰学习方法，再来回想一下朴素贝叶斯的流程，训练的过程就是参数估计，因此朴素贝叶斯也可以懒惰式学习，此类技术在训练阶段开销为零，待收到测试样本后再进行计算。相应地我们称那些一有训练数据立马开工的算法为“急切学习”，可见前面我们学习的大部分算法都归属于急切学习。

低维嵌入

上一节的讨论是基于一个重要假设：任意测试样本x附近任意小的$\delta$距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，或称为“密采样”(dense sample)。
事实上，在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”(curse of dimensionality)。
缓解维数灾难的一个重要途径是降维(dimension reduction)，亦称“维数约简”，即通过某种数字变换将原始高维属性空间转变为一个低维“子空间”(subspace)，在这个子空间中样本密度大幅提高，距离计算也变得更为容易。

震惊，降维打击！原理竟然是这样的？

MDS算法原理：
假设有$m$个样本，其样本空间如下：
T = { x 1 , x 2 , . . . , x m } , x i ∈ R m T=\{x_1,x_2,...,x_m\},x_i∈R^m T={x1​,x2​,...,xm​},xi​∈Rm
令$D$表示样本间的距离，其中$D\in R^{m\times m}$，在矩阵$R^{m\times m}$中，第$i$行第$j$列的元素用$dis{t}_{ij}$表示，也就是样本$x_i$到样本$x_j$之间的距离。
容易知道矩阵$D$是一个对称矩阵，MDS算法的目的在于不改变样本之间的距离的前提下，实现数据降维。
所以，我们最终要获得降维的新样本空间$Z\in R^{m^{\prime }\times m},m^{\prime }⩽m$，且任意两个样本在$d^{\prime }$维空间中的欧氏距离等于原始空间的距离，即满足$||z_i-z_j||=dis{t}_{ij}$ 1⃣️。
令$B=Z^{T}Z\in R^{d\times d}$，其中$B$是降维过后样本的内积矩阵，其中$b_{ij}=z_i^T{z}_j$，那么，我们可以知道，将1⃣️式平方得到下面的公式2⃣️：

为了便于讨论，中心化降维后的样本$Z$，即使用下面的方式中心化矩阵。

中心化的$Z$具有如下特征：${\sum }_{i=1}^m{z}_i=0$，所以由于$B=Z^{T}Z$，得出${\sum }_{i=1}^m{b}_{ij}={\sum }_{j=1}^m{b}_{ij}=0$，即矩阵$B$的行与列的和均为0。

从而，公式2⃣️可以推导出如下的三个公式3⃣️4⃣️5⃣️：

其中$tr(\cdot )$表示矩阵的迹（trace），$tr(B)={\sum }_{i=1}^m||z_i|{|}^2$。由公式3⃣️4⃣️5⃣️得公式6⃣️7⃣️8⃣️：

再由公式2⃣️-8⃣️可得：

通过上述公式，我们知道，可以通过$b_{ij}$求到矩阵$B$每一行每一列的值，从而得出整体的矩阵$B$。
曾经有个哲人说过，冬天到了春天还会远么？
所以由于$B=Z^{T}Z$，要想办法通过B得到Z。

由于B是对称矩阵，对其进行特征分解，即：
$B=V\Lambda V^T$
其中$\Lambda =diag({\lambda }_1,{\lambda }_2,...{\lambda }_m)$为特征值构成的对角矩阵。
假定特征值构成的对角矩阵中，有$m^{\ast }$个非零特征值，那么它们构成对角矩阵${\Lambda }_{\ast }=diag({\lambda }_1,{\lambda }_2,...{\lambda }_{m^{\ast }})$，令$V_{\ast }$表示其相应的特征向量矩阵，那么$B$也可以表达为：
$B=V_{\ast }{\Lambda }_{\ast }{V}_{\ast }^T$
结合公式$B=Z^{T}Z$，得：
$Z={\Lambda }_{\ast }^{\frac{1}{2}}{V}_{\ast }^T$
也就是说，我们已经知道了$B$，现在我们只需要对矩阵B做特征值分解即可。

不过，在现实应用中为了有效降维，往往仅需降维后的距离与原始空间中的距离尽可能接近，而不必严格相等。此时可以取$m^{\prime }<<m$个最大特征值构成对角矩阵$\Lambda$以及其特征向量矩阵$V$

到此，MDS算法介绍完毕。

主成分分析

之前在深度学习入门（ https://blog.csdn.net/No_Game_No_Life_/article/details/89876063#_42 ）里，数据输入层通常就会用PCA做一个降维，这里我们来介绍一下这个降维的方法。

首先考虑一个问题：对于正交属性空间中的样本点，如何用一个超平面（直线的高维推广）对所有样本进行恰当的表达？
可以想到，若存在这样的超平面，那么它大概具有这样的性质：

• 最近重构性：样本点到这个超平面的距离足够近
• 最大可分性：样本点在这个超平面上的投影能尽可能的分开

基于最近重构性和最大可分性能分别得到主成分分析的两种等价推导，我看了看公式推导过程，哎，实在看不下去了，大学数学课本里都没见过的公式，告辞。
所以，我们这里直接用结论把。

输入：
样本集 D = { x 1 , x 2 , . . . , x m } D=\{x_1,x_2,...,x_m\} D={x1​,x2​,...,xm​}
低维空间维度$d^{\prime }$
过程：

1. 对所有样本进行中心化：$x_i^{\prime }=x_i+\frac{1}{m}{\sum }_{i=1}^m{x}_i$
2. 计算样本的协方差矩阵$X{X}^T$
3. 对样本的协方差矩阵$X{X}^T$做特征值分解
4. 取最大的$d^{\prime }$个特征值所对应的特征向量$w_1,w_2,...,w_{d^{\prime }}$
5. 输出投影矩阵$W=(w_1,w_2,...,w_{d^{\prime }})$