标题：层次化最近邻图嵌入以高效降维
作者来自德国，代码开源好用。
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方向上再转回为什么几乎是等价的？请看懂的读者们评论区指教】