问题标签 [approximate-nn-searching]

在所有 Locality Sensitive Hashing 解释中（即http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search）

他们描述了生成了 k 个哈希函数，但在哈希表中只使用了 l (l < k) 来对值进行哈希处理。

为什么要生成 k 而不仅仅是生成 l？

为什么要使用单独的因子 k 和 l？

我不明白。

I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also I've read that in general, all space-partitioning data structures tends to perform exhaustive search with high dimensional data.

Additionally, there are two important facts to be considered (ordered by relevance):

• Precision: The nearest neighbors must be found (not approximations).
• Speed: The search must be as fast as possible. (The time to create the data structure isn't really important).

So, I need some advice about:

1. The data structure to perform k-NN.
2. If it will be better to use an aNN (approximate nearest neighbor) approach, setting it as accurate as possible?.

我的摇摆应用程序中有一个JXTable。当我在桌子上按 ctrl+F 时，默认搜索面板正在打开。

此面板仅查找子字符串。我需要用我的 InputText 找到相似的词。例如，我写“test”结果可能是“tost”、“tests”、“est”、“tst”等。我如何将这种搜索方法更改为我自己的算法？可能吗 ？或者我应该禁用默认搜索并创建自己的搜索吗？

我正在研究近似最近邻算法。

我最近发现了Annoy Library，它在以合理的速度找到 KNN 方面做得非常出色。要进行更深入的分析，您可以浏览聚会幻灯片。

在阅读了幻灯片并检查了源代码之后，我看不出这个算法比 KD-Tree 更好地处理高维数据的原因。

KD-Tree 是一种很棒的 NN 算法，但是在高维中它实现的运行时间几乎与蛮力搜索 [O(n^2)] 相同，因此它需要检查许多相邻的叶子。

原因是在高维中，单位球体的体积变得更小（你可以看看这里）。

我在 Annoy 库中发现的唯一区别是空间的划分是通过使用超平面而不是一次划分一个维度来完成的。

有没有人分析过这个算法并能解释为什么它比 KD-Tree 快得多？

我已经阅读了关于 Locality Sensitive Hashing的原始论文。

复杂性是参数 ε 的函数，但我不明白它是什么。

你能解释一下它的含义吗？

我试图理解本文关于 LSH 的第 5 节，特别是如何存储生成的哈希。引用链接的论文：

给定每个由 d 位组成的位向量，我们选择 N = O(n 1/(1+epsilon) ) 位的随机排列。对于每个随机排列 σ，我们维护位向量的排序顺序 O σ，按照由 σ 排列的位的字典顺序。给定一个查询位向量 q，我们通过执行以下操作找到近似最近邻： 对于每个排列 σ，我们对 O σ 执行二进制搜索，以定位最接近 q 的两个位向量（按获得的字典顺序）由 σ 置换的位）。我们现在按照与 q 匹配的最长前缀的长度的顺序在每个排序顺序 O σ 中搜索由二分搜索返回的位置上方和下方的元素。这可以通过为每个排序顺序 O σ 维护两个指针来完成（一个向上移动，另一个向下移动）。在每一步中，我们向上或向下移动与具有最长匹配前缀的元素相对应的指针之一。（这里 O σ 中最长匹配前缀的长度是相对于 q 计算的，其位由 σ 置换）。我们以这种方式检查 2N = O(n 1/(1+epsilon) ) 位向量。在检查的所有位向量中，我们将具有最小汉明距离的位向量返回到 q。

我对这个算法感到困惑，我认为我不明白它是如何工作的。

我已经在该主题上找到了这个问题，但我不明白评论中的答案。同样在第 2 点的这个问题中，描述了相同的算法，但同样，我不明白它是如何工作的。

你能试着向我解释它是如何工作的，并尽可能地简单吗？

我什至试着把我看不懂的东西列个清单，但实际上写得太糟糕了，我看不懂大部分句子！

在 gsamaras 回答后编辑：

我基本上明白了答案，但我仍然有一些疑问：

1. 是否正确地说执行N排列的总成本是O(Nnlogn)，因为我们必须对它们中的每一个进行排序？

2. 上述排列+排序过程在预处理期间或每个查询中只执行一次q？O(Nnlogn)即使在预处理中，它似乎已经相当昂贵，如果我们必须在查询时这样做，那将是一场灾难：D

3. 在最后一点，我们比较v0和v4，q我们比较它们的置换版本还是原始版本（在它们置换之前）？

我想利用 FLANN 库进行多标签分类。我知道 FLANN 库用于计算最近邻，但我不确定如何将其用于分类目的。有什么方法可以将它插入 Scikit-Learn 或其他库中。

我正在寻找使用欧几里得距离的python 3中LSH的有效实现。

有“in-python”LSHForest实现，但它使用余弦距离。

此外，即使使用此实现，我也没有找到查看每个篮子内容的方法，例如，如果使用 LSH 进行聚类 - 它只返回一定半径内的一定数量的近似邻居。但是如果我想查看所有邻居，我看不到它是如何完成的（我不想使用任意的搜索半径，我真的不确定使用这个非常大或无限的半径是什么意思执行）。

将欣赏任何见解。非常感谢。

我才刚刚开始学习特征散列，所以我需要帮助来理解我是否可以应用以数学方式表示为https://en.wikipedia.org/wiki/Tent_map的散列函数。

Tent map 的一个这样的应用是在密码学中——论文 1：基于神经密码学的哈希函数的实现下载链接。

在特征散列中，设x为 D 维的数据点，即它有 D 个元素。在特征散列中，使用线性散列函数将 D 维数据点转换为较低的 k 维数据点，从而保留降维特征空间中的距离。哈希位 k 是通过运算得到的， h_k(x) = sign(y(x)) = sign(f(w_k^Tx +b))。输出h(x)为 0 或 1 位。

本质上，我们通过创建随机超平面来对数据点 x 属于 0 类还是 1 类进行分类。

在特征散列中，有多种散列函数可供选择以降低维数：f = tanh()或简单地随机采样以获得超平面。另一种选择是在数据不是线性可分时使用核函数。这种散列函数/技术是使用内核实现的，一种流行的选择是使用高斯 RBF 作为内核函数。

• 问题：在论文 1 中，作者使用了在单位间隔上分段线性的非对称帐篷地图https://en.wikipedia.org/wiki/Tent_map作为传递函数。对我来说，本文中使用 Tent Map 的散列公式看起来类似于散列方程 (1)。如何应用分段线性函数，即应用此地图创建超平面以进行特征散列？

  还是我混合了这两个概念？

LSH 是一种流行的人工神经网络算法。

kd 树可能是精确求解 NN 的最流行的解决方案。

但是，阅读本调查后，我发现了这些结构，但我不明白哪些结构用于解决 NN 或 ANN：

• 四叉树/八叉树
• 球树
• R-树
• M-树

我没有找到任何专门针对 ANN 的调查，所以我认为所有这些都是针对 NN 和度量空间的（它们不能用于非度量空间）。