1、kNN
kNN算法即k近邻算法，是常用的有监督学习算法。它是懒惰学习的代表算法，没有显式的训练过程。kNN在收到训练样本时只是将样本存储起来，当需要做预测的时候再进行处理。其思路非常简单，就是找到距离预测样本最近的k个训练样本，根据这k个样本的分类进行投票得到预测样本的分类。
西瓜书上给出了kNN算法泛化错误率的一个上界，可见其泛化效果是非常好的：
当然kNN算法能发挥效果也是建立在一些隐含假设之上的。首先k的选取要恰当，k太大可能导致欠拟合，k太小可能导致过拟合。然后是距离度量是恰当的，距离的计算在高维空间将面临困难，即我们在聚类中提到过的维度灾难。为了解决维度灾难，通常需要先对特征进行降维，然后再利用kNN算法进行分类。
2、多维缩放（MDS）
多维缩放（Multiple Dimensional Scaling，MDS）要求原始空间中的距离在低维空间中得以保持。西瓜书上对MDS做了完整的推导：
从而我们就通过简单的数学推导直接得到了高维空间中的原特征的一个低维嵌入。
3、PCA
主成分分析（Principal Component Analysis，PCA）是最常用的降维方法。它是一种线性降维方法，所谓线性降维，就是直接对原始高维空间进行线性变换，得到样本在低维空间中的表达：
主成分分析的思路就是寻找一个超平面对所有样本进行恰当的表达，具体来说，就是使样本点在这个超平面上的投影尽可能分开（即尽可能保留样本之间的差异性）：
这里的分别表示的其实是对应的特征向量方向上的方差。具体的推导过程见http://blog.codinglabs.org/articles/pca-tutorial.html，写的非常通俗和详细。
从而我们就可以利用各个的值来确定降维后的维数
：
4、核化线性降维
PCA是线性的，对于非线性数据往往显得无能为力。为了那么我们如何解决非线性数据的降维呢？反其道而行之，先升维！
回忆之前学过的Kernel SVM，我们想找一个超平面把数据完全分开，面对线性不可分的数据，我们做的事情是先将数据升维，使得在映射到的高维空间当中存在一个超平面将数据分开。这里我们的非线性降维也是一样，先将数据升维，使其线性可分，然后再利用和PCA类似的过程降维。
这里我们同样使用核方法，并与PCA相结合，得到核主成分分析算法（KPCA）：
5、流形学习
流形学习是一大类基于流形的框架。数学意义上的流形比较抽象，不过我们可以认为LLE中的流形是一个不闭合的曲面。这个流形曲面有数据分布比较均匀，且比较稠密的特征，有点像流水的味道。基于流行的降维算法就是将流形从高维到低维的降维过程，在降维的过程中我们希望流形在高维的一些特征可以得到保留。西瓜书上简要介绍了两种流形学习方法。
Isomap算法的出发点就是计算高维空间中的距离时能够计算曲面上的距离，而非直线距离。方法也很简单，就是对每个样本点，只计算和其近邻之间的距离，于是样本之间出现一些连线构造成图，接下来我们使用最短路算法即可获得两点之间在曲面上的近似距离。获得近似距离后，再通过MDS算法求解即可。
西瓜书上介绍的另一种算法是局部线性嵌入（Locally Linear Embedding，LLE），LLE算法的出发点是试图保持邻域之间样本的线性关系：
LLE首先假设数据在较小的局部是线性的，也就是说，某一个数据可以由它邻域中的几个样本来线性表示。
LLE算法主要分为三步：
- 第一步是求K近邻的过程，这个过程使用了和KNN算法一样的求最近邻的方法
- 第二步是对每个样本求它在邻域里的K个近邻的线性关系，得到线性系数W
- 第三步就是利用权重系数来在低维里重构样本数据
6、度量学习
