降维

#降维/UMAP #降维/t-SNE #降维/PCA

矩阵特征值与主成分分析（PCA(Principal Component Analysis)）

特征值和特征向量

主成分分析

PCA的主要思想是将n维特征映射到k维上，这k维是全新的正交特征也被称为主成分，是在原有n维特征的基础上重新构造出来的k维特征。PCA的工作就是从原始的空间中顺序地找一组相互正交的坐标轴，新的坐标轴的选择与数据本身是密切相关的。其中，第一个新坐标轴选择是原始数据中方差最大的方向，第二个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的，第三个轴是与第1,2个轴正交的平面中方差最大的。依次类推，可以得到n个这样的坐标轴。通过这种方式获得的新的坐标轴，我们发现，大部分方差都包含在前面k个坐标轴中，后面的坐标轴所含的方差几乎为0。于是，我们可以忽略余下的坐标轴，只保留前面k个含有绝大部分方差的坐标轴。事实上，这相当于只保留包含绝大部分方差的维度特征，而忽略包含方差几乎为0的特征维度，实现对数据特征的降维处理。

我们如何得到这些包含最大差异性的主成分方向呢？

答案：事实上，通过计算数据矩阵的协方差矩阵，然后得到协方差矩阵的特征值特征向量，选择特征值最大(即方差最大)的k个特征所对应的特征向量组成的矩阵。这样就可以将数据矩阵转换到新的空间当中，实现数据特征的降维。

由于得到协方差矩阵的特征值特征向量有两种方法：特征值分解协方差矩阵、奇异值分解协方差矩阵，所以PCA算法有两种实现方法：基于特征值分解协方差矩阵实现PCA算法、基于SVD分解协方差矩阵实现PCA算法。

PCA 、t-SNE、UMAP

PCA为线性降维方法，对数据量少，结构简单的情况效果好

t-SNE 、UMAP为非线性降维，对数据结构复杂的情况有效，UMP的损失函数对高维远但低维近或高维近但低维远的情况均有良好的惩罚（梯度），其通过调节参数NN(n_neighbors)平衡局部与整体

奇异值分解（SVD）

是一种矩阵分解方法，它可以将一个矩阵分解为三个矩阵的乘积。它有许多用途，包括数据降维、图像压缩存储、主成分分析等。例如，在机器学习中，SVD可以用来寻找数据分布的主要维度，将原始的高维数据映射到低维子空间中实现数据降维。

最近邻查找（Nearest Neighbor,AN）

在很多应用领域中，我们面对和需要处理的数据往往是海量并且具有很高的维度，怎样快速地从海量的高维数据集合中找到与某个数据最相似（距离最近）的一个数据或多个数据成为了一个难点和问题。如果是低维的小数据集，我们通过线性查找（Linear Search）就可以容易解决，但如果是对一个海量的高维数据集采用线性查找匹配的话，会非常耗时，因此，为了解决该问题，我们需要采用一些类似索引的技术来加快查找过程，通常这类技术称为最近邻查找（Nearest Neighbor,AN），

例如K-d tree；

K-d树（k-dimensional tree）是一种用于在k维空间中存储实例点以便快速检索的树形数据结构。它主要用于多维空间关键数据的搜索，如范围搜索和最近邻搜索。

或近似最近邻查找（Approximate Nearest Neighbor, ANN），

例如K-d tree with BBF, Randomized Kd-trees, Hierarchical K-means Tree。

而LSH（局部敏感哈希(Locality-Sensitive Hashing, LSH)）是ANN中的一类方法。

https://zhuanlan.zhihu.com/p/538605686

https://www.nature.com/articles/s41598-019-41695-z/

https://cran.r-project.org/web/packages/leiden/vignettes/run_leiden.html