美文网首页
CVPR'22(基于1NN图可视化降维)-Hierarchica

CVPR'22(基于1NN图可视化降维)-Hierarchica

作者: Caucher | 来源:发表于2023-08-16 23:32 被阅读0次

标题:层次化最近邻图嵌入以高效降维
作者来自德国,代码开源好用。
https://github.com/koulakis/h-nne

编者的总结

  1. 本文基于之前的1-NN graph tree的聚类方法,将聚类信息作为原始数据的分布,以PCA做初始化降维,按照簇内调整,簇间间隔的方式优化降维后位置。
  2. 优势很显著,快,无参数,可解释。
  3. 另一个优点是这是一个广义的降维方法,可以降到任意维度,使用不同数量的PCA特征向量即可。

编者的思考

  1. 缺点是可视化后数据被分的特别细,每个小簇都很小,没有连续的区域,对于类别较少的数据集,看起来区分性没有很好
  2. 降维后的性质可以再看看,毕竟是线性的,所以可能有一些很好的性质。

Abstract & 1. Introduction

  • 问题:高维数据的可视化(2/3维降维)
  • 本文方法(h-nne)基本思路:构建层次化1-NN图,得到原始空间的一个聚类,在降维过程中保持聚类特征
  • h-nne优势:快,参数少(几乎没有),可解释性强,不需要优化(训练)过程。
  • 可视化的问题的两个衡量指标:局部结构保留和全局结构保留。
    • 局部结构讲的是本来的KNN在降维之后最好还是KNN。
    • 全局结构讲的是不同的类别,或者说簇,部分,他们之间的相对距离关系最好保持不变。
image.png

3. The h-NNE algorithm

本文方法分三步:

  1. 第一步构建1-NN图的树,捕捉数据集的全局和局部分布;
  2. PCA或者近似PCA降维所有的点和锚点(簇的中心);
  3. 根据降维后的簇中心和锚点的位置关系重新把簇内的点排列到锚点周边。

3.1. Nearest neighbor graph based hierarchy

自下而上建立1-NN图树

  1. 首先建立有向1-NN图, 根据连通性聚类,即每个簇是一个连通部分,这些簇就是树的叶子节点;
  2. 每个簇算出中心,提到上一层,再次建立1-NN图,重复上一步的操作,直到该层的点的数量比较少。
image.png

3.2. Preliminary linear embedding

  • 通过PCA或者对倒数第二层的锚点们PCA,对数据降维;
  • 这个降维相当于一个初始化,其实也可以随机初始化,但是PCA收敛的会好一些。

3.3. Hierarchical point translation

自上而下在低维空间对数据位置优化调整:

  1. 考虑第一层和第二层,一个簇在降维后的中心,和该簇的中心(锚点)降维后产生的点,是有一定差距的。【编者:因为降维的锚点是代表原始分布,降维后的簇中心代表的是降维后的分布,我们要将降维后的分布向原始分布校正】
  2. 对于这个簇的某一个点,找出它和簇中心的偏差,将其长度和簇半径相除作归一化(这样簇中心离最远的点长度是1),然后长度上再乘一个scale放缩【后面讲为什么】(这样簇中心离最远的点长度是scale),调整后的残差向量和降维后的锚点向量相加,就是这个点的新位置了。
  3. 上层的点是下层簇的中心,因此算到最后一层,所有点的新位置就找到了。
  • 关于Scale,算法的一个目标是保持局部特征,原来在一个簇里的点,降维后还在一个簇里,这就要求簇内的点和簇中心或者簇锚点围绕的更近一些,准确点说,需要在一个voroni cell里面,如下图。
  • 要保证降维后的点和簇内的点离得更近离簇外的点离得更远,我们就要控制所有点都在以簇中心为球心,和最近voroni cell的距离1/3的大小为半径的球里面,这个1/3的距离就是scale。
  • 实际很少需要理论上那么极端的Scale,0.4倍的最近距离放缩一般就够了,放缩的太小会导致局部太密。
image.png
  • Point cluster inflation for visualization purposes
    当点簇没有和特征向量对齐时,对所有点的单一线性变换会导致各个簇很乱。
    因此最后一个可选步骤是簇的膨胀,这一步对性能的影响小,但是对视觉体验的影响比较大。
    需要将点簇旋转到PCA的特征向量方向上去然后再转回来。
    为了保证性能,可以分别随机旋转6次,使用0, 90°之间的6个角度,并转回,这和旋转到PCA方向上再转回为什么几乎是等价的。

【编者:机械翻译了一下,没看明白这样做的原因,比如“对齐”是想说什么? 为什么没对齐会让各个簇很乱?为什么最后要再把点簇旋转到PCA的特征向量方向上去然后再转回来?随机旋转再转回和旋转到PCA方向上再转回为什么几乎是等价的?请看懂的读者们评论区指教】

相关文章

  • 逻辑分析

    图的表示 情况逻辑分析2维22(二维图)222(三维图)2222(四维图)….降维的方式 二进制数的表示方法 牛逼...

  • R可视化:PCA图的可视化修改

    PCA图的可视化修改 PCA是降维方法之一,对PCA结果进行可视化的方法有很多,现在总结如下几种可视化方法。更多知...

  • 高维数据可视化方法——T-SNE

    用途 用于高维数据的降维,可视化展示,相比较pca的线性降维,再可视化显示方面显示更加友好。相似的样本由附近的点建...

  • 吴恩达机器学习-Chapter 15 降维

    目的:降维的应用、概念、及算法。降维的3个目的:数据压缩、加速算法(缩小特征变量)、数据可视化。降维本身也是一种无...

  • 主成分分析-原理

    1、降维是什么 降维简单直接的说就是减少自变量的个数,利于分类结果的可视化。 2、降维的两种方法 降低自变量个数的...

  • 数据降维——PCA、SVD

    1. 数据降维 数据降维的目的:数据降维,直观地好处是维度降低了,便于计算和可视化,其更深层次的意义在于有效信息的...

  • 93-非监督学习之PCA线性降维

    为何要降维?方便可视化探索;减轻维度诅咒;缓解共线性。降维方法:PCA, t-SNE, UMAP, SOM, LL...

  • R语言可视化(十七):tSNE图绘制

    17. tSNE图绘制 清除当前环境中的变量 设置工作目录 查看示例数据 使用tsne包进行tSNE降维可视化分析...

  • R语言可视化(十八):UMAP图绘制

    18. UMAP图绘制 清除当前环境中的变量 设置工作目录 查看示例数据 使用umap包进行UMAP降维可视化分析...

  • 数据降维与可视化工具——t-SNE实践教程

    姓名:张国帅 学号:19021110506 【嵌牛导读】t-SNE是一种集降维与可视化于一体的技术,它是基于SNE...

网友评论

      本文标题:CVPR'22(基于1NN图可视化降维)-Hierarchica

      本文链接:https://www.haomeiwen.com/subject/zenkmdtx.html