降维与度量学习

第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。

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

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

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

  • Page229: 线性降维

    基于线性变换来进行降维的方法。

  • Page229: 主成分分析

    同PCA。

  • Page231: 奇异值分解(402)

    任意的实矩阵都可以进行分解,如ARm×nA\in \mathbb{R}^{m\times n}可以分解为A=UΣVTA=U\Sigma V^T,其中U是m×m阶酉矩阵;Σ是半正定m×n阶对角矩阵;而VTV^T,即V的共轭转置,是n×n阶酉矩阵。$u_i$称为A的左奇异值,viv_i称为A的右奇异值。Σ对角线上的元素为A的奇异值。矩阵A的秩是非零奇异值的个数。

  • Page232: 本真低维空间

    对原始低维空间和降维后的低维空间进行区分,称原始采样的低维空间为本真低维空间。

  • Page232: 非线性降维

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

  • Page232: 核化线性降维

    对线性降维方法进行核化,以保持其原本的低维结构。

  • Page232: 核主成分分析

    Kernelized PCA,在高维特征空间将数据投影到由d维的W确定的超平面上,z是x在高维空间上的像,假设zi=ϕ(xi)z_i=\phi (x_i),引入核函数κ(xi,xj)=ϕ(xi)Tϕ(xj)\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: 流形正则化

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