KNN算法和低维嵌入

K近邻学习

K-Nearest Neighbor, 一种常用的监督学习方法,其工作机制为:给定测试样本,基于某种距离度量找出训练集中和其靠近的 $k$​​ 个训练样本,并基于邻居的信息进行预测。属于典型的懒惰学习。

懒惰学习:训练阶段仅仅将样本保存起来,待收到测试样本后进行处理。

急切学习:训练阶段就对样本进行学习处理的学习方法。

给定测试样本$x$, 若其最近邻样本为$z$,则最近邻分类器出错的概率就是$x$, $z$标注不同的概率,即 $$ P(e r r)=1-\sum_{c \in \mathcal{Y}} P(c \mid \boldsymbol{x}) P(c \mid \boldsymbol{z}) $$ 现在,假设样本独立同分布,且对任意 $x$ 和任意小数 $\delta$, 在$x$附近$\delta$ 距离内总能找到一个训练样本,令$c^{*}=\arg \max _{c \in \mathcal{Y}} P(c \mid \boldsymbol{x})$​表示贝叶斯最优分类器的结果,则:

$$ \begin{aligned} P(e r r) &=1-\sum_{c \in \mathcal{Y}} P(c \mid \boldsymbol{x}) P(c \mid \boldsymbol{z}) \\ & \simeq 1-\sum_{c \in \mathcal{Y}} P^{2}(c \mid \boldsymbol{x}) \\ & \leqslant 1-P^{2}\left(c^{*} \mid \boldsymbol{x}\right) \\ &=\left(1+P\left(c^{*} \mid \boldsymbol{x}\right)\right)\left(1-P\left(c^{*} \mid \boldsymbol{x}\right)\right) \\ & \leqslant 2 \times\left(1-P\left(c^{*} \mid \boldsymbol{x}\right)\right) \end{aligned} $$
可以看出,最近邻分类器虽然十分简单,但是其泛化错误率不超过贝叶斯分类器的两倍。

低维嵌入

高维情形下出现的数据样本稀疏和距离计算困难等问题统称为维数灾难(curse of dimensionality),是所有机器学习算法共同面临的困难。

一个重要的解决办法是降维,即通过数学变换将原始高维属性空间转化为一个低维的子空间,因此可以在这个子空间里样本密度大幅提高。

**那么,为什么能够做到降维呢?**很多时候,学习任务所需要的只是某个低维分布,即高维空间内的一个低维嵌入(embedding)。

MDS算法,即多维尺度变换算法,可以通过对象在高维空间里的相似性给定从而确定这些对象在低维空间里的表示。两个相似的对象在高维空间中由两个距离相近的点所表示,两个不相似的对象在高维空间中由两个距离比较远的点表示。具体上有两种:

  • Classic MDS:采用欧式距离
  • no-Classic MDS : 采用非欧式距离

数学推导如下: 要求任意两个对象在$Z$​维空间中的距离于原始空间的距离相同: $$ d_{i j}^{2}=\left|z_{i}-z_{j}\right|^{2}=\left|z_{i}\right|^{2}+\left|z_{j}\right|^{2}-2 z_{i}^{T} z_{j} $$ 假设$Z$ 维空间中的点是中心化的,即: $$ \sum_{i=1}^{N} z_{i}=0 $$ 第一个公式左右两边求和:

$$ \sum_{i=1}^{N} d_{i j}^{2}=\sum_{i=1}^{N}\left|z_{i}\right|^{2}+N\left|z_{j}\right|^{2} $$

$$ \sum_{j=1}^{N} d_{i j}^{2}=\sum_{j=1}^{\mathrm{N}}\left|z_{j}\right|^{2}+N\left|z_{j}\right|^{2} $$

对上面两个公式再次求和: $$ \sum_{i=1}^{N} \sum_{j=1}^{N} d_{i j}^{2}=\sum_{i=1}^{N} \sum_{j=1}^{N}\left|z_{j}\right|^{2}+N \sum_{i=1}^{N}\left|z_{i}\right|^{2}=2 N \sum_{i=1}^{N}\left|z_{i}\right|^{2} $$ 定义内积矩阵 :$ B = Z^T Z$, 联立上式: $$ B_{i j}=-\frac{1}{2}\left(\frac{1}{N^{2}} \sum_{i=1}^{N} \sum_{j=1}^{N} d_{i j}^{2}-\frac{1}{N} \sum_{i=1}^{N} d_{j j}^{2}-\frac{1}{N} \sum_{j=1}^{N} d_{i j}^{2}+d_{i j}^{2}\right) $$ 矩阵$B$是一个对称矩阵,因此对矩阵$B$特征分解可以得到 $B=V \Lambda V^{T}$

由于将数据降维到$Z$​维度空间中,则选择前$Z$​个最大的特征值和特征向量。数据点表示为: $$ Z = V_2 \Lambda_z^{1/2} $$ 算法流程如下:

(1)计算原始空间中数据点的距离矩阵。 (2)计算内积矩阵 $B_{\circ}$ (3)对矩阵 $B$ 进行特征值分解,获得特征值矩阵 $\Lambda$ 和特征向量矩阵 $V$ 。 (4)取特征值矩阵最大的前 $Z$ 项及其对应的特征向量 $Z=V_{z} A_{z}^{1 / 2}$​ 。

使用sklearnmds算法对iris数据集降维,效果如下:

image-20210810164425637

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn.manifold import MDS

iris = load_iris()
clf2 = MDS(2)
clf2.fit(iris.data)
iris_t2 = clf2.fit_transform(iris.data)
plt.scatter(iris_t2[:, 0], iris_t2[:, 1], c=iris.target)
plt.show()
updatedupdated2021-08-102021-08-10