随机投影森林中点分布对 k-nn 搜索的影响

Feb, 2023

随机投影森林中点分布对 k-nn 搜索的影响

The Effect of Points Dispersion on the $k$-nn Search in Random Projection Forests

Mashaan Alshammari, John Stavrakakis, Adel F. Ahmed, Masahiro Takatsuka

TL;DR本文探讨了两种影响随机投影森林中 k - 最近邻搜索 (K-NN 搜索) 性能的因素（数据点的分散性和 rpForest 中树的数量），研究表明随机投影森林的数量较大时，数据点的分散性对 K-NN 搜索影响非常有限。因此，在选择随机方向时，应使用原始 rpTree 算法，而不考虑数据点的分散性。

Abstract

partitioning trees are efficient data structures for $k$-nearest neighbor search. Machine learning libraries commonly use a special type of partitioning trees called $k$d-trees to perform $k$-nn search. Unfortunately, $k$d-trees can be ineffective in high dimensions because they need m

partitioning trees kd-trees random projection trees rpforest nearest neighbor search

发现论文，激发创造

用于精确最近邻搜索的随机划分树

通过分析三种 k-d 树的变体，我们确定了一个简单的潜在函数，该函数能直接反映数据集和查询点难度，并在正增长测度和主题模型中限制了该潜在函数。

Feb, 2013

SpectralNet 的随机投影树相似度度量

本研究利用神经网络分离数据内嵌，提出了一种基于 rpTree 相似性度量的 SpectralNet 相似性度量方法来进行图聚类，实验证明，与基于距离度量的 $k$-nn 图相比，基于 rpTrees 的 SpectralNet 能够获得更好的聚类准确性。

Feb, 2023

图卷积网络的随机投影森林初始化

本文介绍了一种新的构建图形和初始化 GCN 的方法，基于 rpForest，并通过谱分析来设置该参数的正确范围，实验结果表明，使用 rpForest 初始化 GCN 比 $k$-nn 初始化方法提供更好的结果。

Feb, 2023

哪些空间分区树对于固有维度具有适应性？

本研究通过理论与实验结合的方法，探讨了更广泛的树类组合，以了解空间划分可以利用数据的内在低维结构的程度，对于回归、向量量化和最近邻搜索等标准统计任务的影响，并证实了随机投影树是适应数据固有维数的。

May, 2012

近似主方向树

介绍了一种新的高维数据的空间数据结构 - 近似主方向树 (APD) 树，该算法确保了与计算复杂的 PCA 树相似的向量量化精度，且时间复杂度与低精度 RP 树相当。

Jun, 2012

向量量化的随机投影树

提出了一种简单且计算效率高的树形结构向量量化方案，与以往方法不同的是，其量化误差仅取决于数据分布的内在维度，而不是数据所处空间的表观维度。

May, 2008

基于动态连续索引的快速 K 最近邻搜索

提出一种新的无需数据空间分割的随机化算法来避免由于数据维度过高而导致的数据检索问题，并通过理论分析和实验结果来证明这种算法在数据近似性、速度和空间效率等方面优于传统的局部敏感哈希算法（LSH）

Dec, 2015

近似最近邻搜索中超参数的高效自动调整

本研究提出了一种使用随机空间划分树自动调整索引方法超参数的算法，相较于现有方法，该算法在查询时间上表现优异，且建立速度更快。

Dec, 2018