计算科学 - K近邻在高维空间的子空间中搜索 - 吾爱随笔录 - 问答

K近邻在高维空间的子空间中搜索

计算科学计算几何高维数据结构

2021-11-28 19:01:52

我正在寻找一种分割大型、相当高维数据集的好方法，以便不仅在完整的维空间中，而且在该空间的低维子空间中执行快速 kNN 搜索。 $N$

例如，考虑3 维空间中。一方面，我想找到它最近的邻居： $p$ $\{X, Y, Z\}$ $i$

\underset{i}{argmin} m a x {‖ x_{p} - x_{i} ‖, ‖ y_{p} - y_{i} ‖, ‖ z_{p} - z_{i} ‖}

$\DeclareMathOperator*{\argmin}{argmin} \argmin_{i} max{\{\| x_p - x_i \|, \|y_p - y_i\|, \|z_p - z_i\| }\}$

但我也希望能够在，即： $j$ $\{X, Y\}$

\underset{j}{argmin} m a x {‖ x_{p} - x_{j} ‖, ‖ y_{p} - y_{j} ‖}

$\DeclareMathOperator*{\argmin}{argmin} \argmin_{j} max{\{\| x_p - x_j \|, \|y_p - y_j\|}\}$

在我的情况下，通常有超过 3 个维度，我希望能够在考虑这些维度的多个不同子集的情况下找到 $k^{th}$

为您提供更多背景知识，我的目标是使用 kNN 距离从连续数据中估计条件互信息，而无需对其进行离散化并计算直方图。

对我的数据进行分区的合适方法是什么？

更多信息：

我的维度将在 3 到 30 之间变化
数据点的数量可能约为 200000

3个回答

由于目前您的维度只有 3，我想一个天真的方法是为每个子空间创建单独的树。

我建议您使用 Flann ( http://www.cs.ubc.ca/research/flann/ )，因为它实现得非常好，并且据报道对于您关注的数据集来说速度非常快 ( http://www. cs.ubc.ca/research/flann/uploads/FLANN/flann_visapp09.pdf，http://www.cs.ubc.ca/research/flann/uploads/FLANN/binary_matching_crv2012.pdf）。_

Flann 以并行方式实现（它甚至支持 MPI），但您可以对其进行调整以检索每个子空间的并行查询，但这将显着减少计算时间。因此，已经有可供您尝试的选项。

由于子空间被简单地定义为维度的子集，因此可以使用降维(1)中的数据投影和欧几里德距离方法对其进行分区。在与您类似的数据问题中，我使用 SVD 和 kmeans 取得了一些不错的结果。服用

$A = U \Sigma V^{T}$

$A_{k} = \Sigma_{k}V_{k}^{T}$

并将 kmeans 应用于矩阵。 $A_{k}$

参考

infolab.stanford.edu/~ullman/mmds/ch11.pdf

Spatial库允许定义自定义Metric，它可以忽略一些特定的维度，或者更一般地在计算差异之前将点投影到指定的子空间上。

其它你可能感兴趣的问题

上一篇带立柱旋转的螺纹 QR 下一篇数值球面积分