问题标签 [approximate-nn-searching]

我正在尝试在大型 3D 点数据集中找到确切数量的相邻节点。目标是让数据集的每个点检索具有给定半径的区域中的所有可能邻居。FLANN 确保对于低维数据可以检索确切的邻居，而与蛮力搜索相比，情况似乎并非如此。邻居对于进一步计算至关重要，因此我需要确切的数字。我测试了一点点增加半径，但似乎不是这个问题。有谁知道如何用 FLANN 或其他 C++ 库计算确切的邻居？

编码：

我想实现一个缓存最流行查询的系统，并给定一个新查询尝试在缓存中找到类似的查询并返回相同的结果。由于我想尽可能通用（查询可以是短文本、图像甚至音轨），我将使用近似最近邻 (ANN) 方法，该方法基于在向量空间中表示查询。

我的问题是：将查询表示为向量（将用作 ANN 中的输入）的最有效方法是什么？

Disclamer：我对神经网络或深度学习一无所知。

VLAD 和 Fisher Vectors with Product Quantization 是Approximate Nearest Neighbor如何用于良好图像检索的一个很好的例子。然而，已经证明神经网络方法比 Bag of Words 或 VLAD 更精确。

我的问题是：

1. 创建 NN 描述符比经典方法（例如 VLAD 或 Fisher Vectors）更快？
2. 我们可以使用带有 NN 代码的经典 ANN 方法来查找相似图像吗？如果不是，如何索引 NN 代码？
3. 我们可以使用度量距离来测量 NN 代码之间的相似性吗？

众所周知，ANN 搜索在效率方面优于 NN 搜索，并且一些技术减少了紧凑表示的存储空间。但是在有效性方面会发生什么？是否有可能在不通过详尽搜索找到最近邻居的情况下达到相同的性能？

我正在使用来自https://github.com/karlhigley/spark-neighbors的 Locality Sensitive Hashing 与 ANN 合作。我尝试了不同的距离：汉明、欧几里得和余弦；但是当我真的想查看调用方法的结果时，collect()这只适用于汉明距离的情况，其他两个在使用 collect() 时会抛出错误。尽管输出的格式始终相同 org.apache.spark.rdd.RDD[(Long, Array[(Long, Double)])]

如何获得可读格式的输出，例如数组、火花数据框等？

下面是代码：

在查看汉明距离的结果时可以看到所需的输出

但在欧几里得或余弦距离neighbors_euclidean.collect()或 neighbors_cosine.collect()

在这两种情况下，我都会收到以下错误：

java.lang.IllegalArgumentException：要求失败：A 的列与 x 的元素数不匹配。答：20，x：100

以下是完整的错误：

在非常高的层次上，这类似于最近邻搜索问题。

来自维基：“给定空间 M 中的一组点 S 和一个查询点 q ∈ M，找到 S 中离 q 最近的点”。

但有些显着差异。规格：

• 每个点由 k 个变量描述。
• 变量并不都是数字的。混合数据类型：字符串、整数等。
• 所有变量的所有可能值都不知道——但它们来自相当小的集合。
• 在要搜索的数据集中，对于所有 k 个变量，将有多个具有相同值的点。
• 另一种看待这个的方式是会有很多重复的点。
• 对于每个点，我们将重复的数量称为频率。
• 给定一个查询点 q 需要找到最近的邻居 p 使得 p 的频率至少为 15

似乎有各种各样的算法围绕 NNS 和统计分类以及最佳 bin 匹配。

我对所有的变化都有点迷失了。是否已经有我可以使用的标准算法。还是我需要修改一个？

我正在尝试从我正在阅读的 .txt 中填充一个数组。我正在使用此代码作为读取文件的函数：

现在，当我读取文件时，我试图从 1D 数据数组中获取元素并将它们存储到 2D 数组中。

我试图在公共类中创建一个数组，但是我不知道如何将我正在读取的数据移动到二维数组。

我知道这不是很清楚，但基本上我正在做最近邻搜索算法来比较 2 张图像。我已经拍摄了一张图像并使用上面的这段代码将其转换为值。但是现在我正在尝试将正在读取的数据存储到 2D 公共数组中？

我有兴趣使用深度强化学习，以便在（太多）可能性和一些（必需的）中间采场（例如，购买咖啡或加油）中找到一条独特的最佳回家路径。

此外，我想在代理不知道环境的“模型”并且代理根本无法尝试所有可能的状态和动作组合的情况下应用它。即需要在 Q 值函数（和/或策略）中使用近似技术。

我已经阅读过处理此类案例的方法——如果有的话，奖励是稀疏的和二元的——比如蒙特卡洛树搜索（根据我的理解，这意味着某种建模和规划）或事后经验回放（HER） ，应用DDPG的思想。

但是有这么多不同类型的算法需要考虑，我有点困惑什么是最好的开始。我知道这是一个难题，也许问这个问题太天真了，但是有没有什么明确、直接、众所周知的方法来解决我想面对的问题？

非常感谢！

马蒂亚斯

我已经编译了ANN 库，需要在 C++ 文件中使用它来进行分段评估

我已经设置了使用 ITK 和 ANN 库的 CMakeList.txt，如下所示：

但是，一旦我编译 C++ 文件，它就会引发错误：

似乎问题与链接库有关。我应该添加任何特定的行或模块CMakeList.txt吗？

我在 C++ 方面相对缺乏经验，并且正在尝试将库编译为 DLL 以在 Unity 中使用。至于生成 DLL 并与之交互，我已经成功地让下面的函数在 Unity 中调用并返回一个虚拟值，不用担心。

我正在努力研究如何与这个Approximate Nearest Neighbor库交互，并且可以使用一些指针。（如果不下载上面链接的源代码并自己看一下，这可能是一个很难定义的问题，但我会尽量让它简单）

在 Unity 中，我有一个三维数组（points[] = float[x,y,z]）和一个空间中的查询点（float[x,y,z]）。我希望将这些数据输入到类似下面的函数中（我已经从 ann_sample.cpp 修改过 - 原始链接在底部），并将最近的邻居返回到这一点。

我的功能

原始函数 （这需要命令行输入 - 即 ann_sample [-d dim] [-max mpts] [-nn k] [-e eps] [-df data] [-qf query]）

正如您在我的评论中看到的那样，我无法确定我可能在哪里以及如何实际输入输入数据，也就是说 - 我上面提到的点数组。

通过使用“istream”类，似乎正在使用以下代码填充数据（在参考函数中），但我不明白这是如何工作的，或者我将如何模拟它。