> For the complete documentation index, see [llms.txt](https://blog.cweihang.io/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blog.cweihang.io/ml/zzh_ml_notes/melon/ch10.md).

# 降维与度量学习

## 第10章 降维与度量学习

* Page225: k近邻

  k近邻是常用的监督学习方法，主要是用某种距离度量方法来找出与测试样本最靠近的k个点，根据这k位邻居的信息来预测其分类。是“懒惰学习”。
* Page225: 急切学习

  这种学习方法在训练阶段就对样本进行学习处理。
* Page225: 平均法

  将这k个样本的实值的平均值作为预测的输出。
* Page225: 最近邻分类器

  k=1，即是最近邻分类器。
* Page226: 密采样

  训练样本的采样密度足够大，保证任意小的距离内都能找到一个训练样本，即为“密采样”。
* Page227: 多维缩放

  多维缩放是指多维空间的样本转换到低维空间上，能够继续保持其距离。
* Page227: 降维

  通过数学变换将高维空间投射到低维子空间。
* Page227: 维数约简

  即降维。
* Page227: 维数灾难(247)

  即高维情况下带来的距离计算量大、样本稀疏等问题，比如随着维度增加，计算量会呈指数增长的趋势。
* Page229: PCA

  PCA(Principal Component Analysis，即主成分分析)，可从最近重构性和最大可分性来思考PCA。

  最近重构性则是希望样本点到超平面的距离足够小，优化目标是$$\min\_W -tr(W^TXX^TW)$$ $$s.t. W^TW=I$$

  最大可分性则是希望样本点在该超平面的投影尽可能分开，优化目标是$$\max\_W tr(W^TXX^TW)$$ $$s.t. W^TW=I$$

  PCA的步骤是对所有样本进行中心化，然后计算协方差矩阵，再对协方差矩阵做特征值分解，然后取最大的d'个特征值所对应的特征向量。
* Page229: 线性降维

  基于线性变换来进行降维的方法。
* Page229: 主成分分析

  同PCA。
* Page231: 奇异值分解(402)

  任意的实矩阵都可以进行分解，如$$A\in \mathbb{R}^{m\times n}$$可以分解为$$A=U\Sigma V^T$$,其中U是m×m阶酉矩阵；Σ是半正定m×n阶对角矩阵；而$$V^T$$，即V的共轭转置，是n×n阶酉矩阵。$u\_i$称为A的左奇异值，$$v\_i$$称为A的右奇异值。Σ对角线上的元素为A的奇异值。矩阵A的秩是非零奇异值的个数。
* Page232: 本真低维空间

  对原始低维空间和降维后的低维空间进行区分，称原始采样的低维空间为本真低维空间。
* Page232: 非线性降维

  非线性降维即是采用非线性变换的方法对数据进行降维，常用的是基于核技巧对线性降维方法进行核化。
* Page232: 核化线性降维

  对线性降维方法进行核化，以保持其原本的低维结构。
* Page232: 核主成分分析

  Kernelized PCA，在高维特征空间将数据投影到由d维的W确定的超平面上，z是x在高维空间上的像，假设$$z\_i=\phi (x\_i)$$，引入核函数$$\kappa (x\_i,x\_j)=\phi(x\_i)^T\phi(x\_j)$$，进一步用矩阵K替代，进而计算出投影矩阵。主要作用是将线性不可分的数据，映射到高维后进行划分。
* Page234: 本真距离

  即为在原始空间上的距离。
* Page234: 测地线距离

  测地线距离是两点之间的本真距离。
* Page234: 等度量映射

  等度量映射认为高维空间的直线距离不能很好地衡量其距离，所以等度量映射试图让“流形”距离在降维后仍能很好保持。
* Page234: 流形学习

  流形是在局部与欧式空间同胚的空间，所以局部可以利用欧氏距离来计算。
* Page235: 局部线性嵌入

  保持邻域内样本的线性关系的一种方法。
* Page237: 度量学习

  通过学习，得到合适的距离度量方法。
* Page238: 近邻成分分析

  NCA(Neighbourhood Component Analysis，即近邻成分分析)是和KNN关联的距离度量方法，在原数据集上进行NCA距离测量，并且完成降维，然后使用KNN在低维空间上对数据进行分类。NCA主要是随机选择近邻，然后通过LOO(Leave one out)的交换检验结果来求马氏距离的变换矩阵。通过优化目标可以得到最大化正确率的距离度量矩阵。
* Page239: 必连约束(307)

  样本必属于一个簇。
* Page239: 勿连约束

  样本必不属于同一个簇。
* Page240: 半监督聚类(307)

  半监督聚类的先验知识主要是样本相似度约束条件，将必连关系和勿连关系作为学习任务优化目标的约束。约束条件主要是基于约束和基于距离。前者主要是依靠用户提供的约束来实现监督指导作用，后者主要是自适应距离度量。
* Page240: 多视图学习

  多视图学习可以看成是从多个角度去学习，比如对同一个事物用多种方法去提取其特征，就能得到其多模态的特征，然后再对多模态特征进行学习。
* Page240: 流形假设(294)

  流行假设是指在很小的一个领域内的样本具有相似的特性，则其标签也相似。
* Page240: 流形正则化

  在正则化项加入与流形相关的项。