2019-03-06

作者: jessica涯 | 来源:发表于2019-03-09 08:55 被阅读0次

ML——降维与度量学习

KNN学习

k近邻（KNN）学习是一种常用的监督学习方法，可用于分类与回归任务中。基本思想是：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息进行预测。

KNN分类

通常，在分类任务中使用“投票法”，即选择k个样本中出现最多的类别标记作为预测结果；在回归任务中使用“平均法”，即将k个样本的实值输出标记的平均值作为预测结果。还可基于距离远近加权平均或加权投票。距离越近样本权重越大。

k近邻法三要素

距离度量、k值的选择及分类决策规则是k近邻法的三个基本要素。距离度量可计算测试实例与每个训练实例的距离，根据k值选择k个最近邻点，最后根据分类决策规则将测试实例分类。

距离度量：特征空间中两个样本点的距离可看成是两个样本点相似程度的反映。样本点 $x_i,x_j$ 的 $L_p$ 距离定义为：

$L_p(x_i,x_j)=(\sum_{l=1}^n\vert x_{i}^{(l)} -x_{j}^{(l)} \vert^p )^{\frac{1}{p} }$

当p=1时，称为曼哈顿距离（Euclidean distance）；当p=2时，称为欧氏距离（Euclidean distance）；当p=∞时，它是各个坐标距离的最大值。

k值选择：k值的选择会对k近邻法的结果产生重大影响。一般k值取一个比较小的数值，通常采用交叉验证法选取最优的k值。

k值选取对knn的影响

分类决策规则：KNN中的分类决策规则往往是多数表决，即由输入样本的k个近邻的训练样本中的多数类，决定输入样本的类。

KNN算法流程：

优点：1）理论成熟，思想简单，既可做回归也可做分类，且适用于非线性分类；2）训练时间复杂度低，仅为O(n)(n为特征数)；3）与NB相比对数据没有假设，准确度高，对异常点不敏感等。

缺点：1）当特征数很多时，计算量巨大；2）样本不平衡时，对稀有类别的预测准确率降低；3）使用懒惰学习，预测时速度要慢于LR之类的算法等。

低维嵌入

样本的特征数称为维数，在高维情形下出现的样本数据稀疏、距离计算困难等问题常会导致“维数灾难”。而缓解维数灾难的一个重要途径就是降维（维数约简），即通过某种数学变换将原始高维属性空间转变为一个低维子空间。在这个子空间中，样本密度大幅提高，同时简化距离计算，高维空间中的样本点在低维嵌入子空间中更易学习。

低维嵌入表示

MDS算法

多维缩放（MDS）算法是一种经典的降维方法，它要求原始空间样本之间的距离在降维后的低维空间中得以保持。

假设m个样本在原始空间距离矩阵为 $D\in R^{m\times m}$ ，其第i行j列元素 $dist_{ij}$ 为样本 $x_i$ 到 $x_j$ 的距离，要获得样本在d'维空间的表示Z(d'×m维，d'<=d)，且任意两样本在d'维空间的欧氏距离等于原始空间中的距离， $||z_i-z_j||=dist_{ij}$ 。令 $B=Z^TZ$ ，其中B为降维后样本的内积矩阵， $b_{ij}=z_{i}^Tz_j$ ，有

(1)

为便于讨论，令降维后的样本Z被中心化，即 $\sum\nolimits_{i=1}^m z_i=0$ 。显有B的行与列之和均为0，即 $\sum\nolimits_{i=1}^mb_{ij}=\sum\nolimits_{j=1}^mb_{ij} =0$ ，易知

由上式可得 $b_{ij}=(1)-\frac{1}{m} (2)-\frac{1}{m} (3)+\frac{1}{m^2} (4)$ 。逐一计算，就得到降维后低维空间中内积矩阵B，只需对B进行特征值分解就可得到Z。MDS算法流程如下：

MDS算法

主成分分析（PCA）

PCA是最常用的一种线性降维方法，如图要将数据从二维降到一维，用某一个维度方向代表这两个维度的数据。图中列出的两个向量方向u1和u2，直观来看u1更好，因为样本点到它的距离更近，或者说样本点在这个直线上的投影能尽可能的分开。这也就得到了PCA两种等价推导：

最近重构性：样本点到这个超平面的距离都足够近；

最大可分性：样本点在超平面上的投影尽可能分散开来。

虽然以上两种方法从不同的出发点来定义优化问题中的目标函数，但最终它们都得到了相同的优化问题：

优化目标

使用Lagrange乘子法求解上述优化问题得：

故只需对协方差矩阵进行特征值分解求解出W。PCA算法流程如下：

PCA算法流程

有时候不指定降维后d'的值，而是指定一个降维到主成分比重阈值t， $t\in (0,1]$ 。若d个特征值为 $\lambda _1\geq \lambda _2\geq ...\geq \lambda _n$ ，则d'可通过下式取得：

优点：1）仅以方差衡量信息，不受数据集以外因素的影响；2）各主成分之间正交，消除原始数据成分间相互影响的因素；3）计算方法简单，易于实现。

缺点：1）主成分各特征维度含义解释性差；2）丢弃的方差小的非主成分可能含有样本差异的重要信息。

核化线性降维

线性降维方法假设从高维空间到低维空间的函数映射是线性的，然而现实任务中可能需要非线性映射才能找到恰当的低维嵌入，核主成分分析（KPCA）就是一种基于核技巧的非线性降维方法。

若核函数形式已知，即知晓如何将低维的坐标变换为高维坐标，此时只需先将数据映射到高维特征空间，再在高维空间中运用PCA即可。但一般情形下并不知道核函数具体映射规则，只知如何计算高维空间中的样本内积。对此，KPCA的创新之处在于：空间中的任一向量，都可由该空间中的所有样本线性表示。

假定 $z_i$ 是由原始特征空间中的样本点 $x_i$ 通过映射产生，即 $z_i=\phi (x_i),i=1,2,...,m$ ，高维特征空间中的投影向量 $w_i$ 可用所有高维样本点线性表出，接着代入PCA求解问题：

由上式发现只需对核矩阵K进行特征分解，便可得出投影向量wi对应的系数向量 $\alpha$ ，因此取K最大的d'个特征值对应的特征向量即可。对新样本x，其降维后的坐标为：

由上式也可以看出，为获得投影后的坐标，KPCA需对所有样本求和，其计算开销较大。

流形学习

设 $Y\subset R^d$ 是一个低维流形， $f:Y\rightarrow R^D$ 是一个光滑嵌入，其中 $D>d$ 。数据集 $\left\{ y_i \right\}$ 是随机生成的，且经过f映射为观察空间的数据 $\left\{ x_i=f(y_i) \right\}$ 。流形学习就是在给定观察样本集 $\left\{ x_i \right\}$ 的条件下重构f和 $\left\{ y_i \right\}$ ，以实现维数约简或者数据可视化。下面介绍几种代表算法。