问题标签 [locality-sensitive-hash]

对 KNN 而言，局部敏感散列似乎是一种很棒的技术，没有任何缺点。但是，如果有人在工业中将局部敏感散列用于实际应用，那么它的缺点是什么？LSH在什么情况下会失败或表现不佳？还是编码/调整需要很长时间？

我尝试应用 LSH（https://github.com/soundcloud/cosine-lsh-join-spark）来计算某些向量的余弦相似度。对于我的真实数据，我有 2M 行（文档）和属于它们的 30K 特征。此外，该矩阵非常稀疏。举个例子，假设我的数据如下：

在相关代码中，特征被放在一个密集向量中，如下所示：

我想要做的是使用稀疏矩阵而不是使用密集矩阵。如何调整“Vectors.dense(features)”？

我正在使用一种算法，该算法可以索引已知固定大小（例如 64 位或 128 位）的任意大的无符号整数。我也希望能够将它应用于 utf-8 字符串，但为了做到这一点，我需要有一种可靠的方法来将任意长度的给定字符串映射到固定大小的无符号字节数组。至少保留字符串前缀的字典顺序的方式。

天真的方法是简单地获取字符串的第一个X字符并给每个字符一个完整的四个字节，根据需要在实际值前面加上零。但是，这将占用X * 4字节。我希望有一种方法可以更节省空间。

- - 编辑 - -

非常重要的是：发生碰撞是可以接受的。

使用上面描述的简单方法并给出字符串：

如果我们设置X为 3，“Alabama”、“Alaska”和“Alakazam”将发生冲突——映射只会产生三个唯一的 12 字节值（“Ala”的每个字符 4 字节表示、“方舟”和“Cor”）。但是，这三个值保持其字典顺序非常重要。

我们必须使用 4 个字节，因为（我相信）这是 utf-8 中单个字符可以占用的最大大小。为了保证我们的映射给我们一个固定大小的字节数组（至少在这个方案中），我们必须让通常只占用一个字节的 ASCII 字符最多占用四个字节。

'A' => 01100001，用零填充：00000000000000000000000001100001

'l' => 01101100，用零填充：00000000000000000000000001101100

'a' => 01100001，用零填充：00000000000000000000000001100001

因此，在X= 4 的示例中，任何以 'Ala' 开头的字符串都将映射到：

当被视为 96 位无符号整数时，它的值将小于我们示例中其他前缀（'Ark' 和 'Cor'）的映射值，因此将满足映射保留我们的字典顺序的要求.

此方案有效，但将任何字符串的大小要求提高了 4 倍。希望是找到一种映射方案，以少于X * 4字节的方式完成 utf-8 前缀索引。

我们正在尝试使用局部敏感算法来实现问题相似性检测。我们正在使用lshash python 包。

我们的目标是实现类似的“问题建议如何在 Stackvoerflow 上发挥作用”

以下是我们的示例数据文本文件。

以下是python代码

但是这个实现给出了不好的结果。有人可以指导我们在上下文中使用哪种类型的局部敏感哈希算法？我对参数感到困惑：INPUT_DIMENSION。

我正在尝试使用 LSH 构建类似的产品，并且有以下查询。

我的数据具有以下架构

我是否应该分别对单个特征执行 LSH，然后以某种方式组合它们，可能是加权平均？

或者

我是否应该一起在所有功能上构建 LSH（基本上在创建诸如 title_iphone、title_nexus、price_1200.25、active_1 之类的带状疱疹时附加功能名称）然后使用词袋方法在这个包上执行 LSH？

如果有人可以将我引导到一个文档，我可以在其中弄清楚如何对电子商务等结构化数据执行 LSH，那就太好了。

PS 我打算在 LSH 中使用 spark 和 min-hash 函数。如果您需要更多详细信息，请告诉我。

MatrixM是签名矩阵，它是通过对实际数据进行 Minhashing 生成的，将文档作为列，将单词作为行。所以一列代表一个文档。

现在它说每个条带（b在数量上，r在长度上）都有其列的散列，因此一列落入桶中。如果两列落在同一个桶中，对于 >= 1 个条带，那么它们可能是相似的。

所以这意味着我应该创建b哈希表并找到b独立的哈希函数？或者只有一个就足够了，每个条带将其列发送到相同的桶集合（但这不会取消条带）？

在这种情况下，字典是否足以用于哈希表^*？

* _{Python 字典是哈希表的一个例子吗？}

根据这个问题，我们知道两个不同的字典，dict_1例如dict_2，使用完全相同的哈希函数。

有没有办法改变字典使用的哈希函数？_{否定答案也被接受！}

我正在尝试实现一个通用的指纹记忆器：我们有一个可以通过智能指纹表示的文件（如图像的pHash或音频的色度图），如果我们想要的（昂贵的）函数已经在类似的文件上计算，然后我们返回相同的结果（避免昂贵的计算）。

局部敏感哈希(LSH) 是一种流行且性能良好的解决方案，用于解决昂贵的多维空间中的近似最近邻问题。

pHash是一个很好的库，它实现了图像的感知散列。

因此 pHash 将多维输入（图像）转换为一维对象（哈希码），这与 LSH（同样，LSH 中的多维对象）有所不同。

所以我想知道我们如何为 pHash 哈希值实现一维 LSH？或者简而言之：我们如何将相似的 pHash 值分组？它可以替代经典的 LSH 方法（如果不是为什么）？

列表不可散列。但是，我正在实现 LSH，并且我正在寻找一个哈希函数，它将正整数列表（在 [1, 29.000] 中）对应于 k 个存储桶。列表的数量是 D，其中 D > k（我认为）和 D = 40.000，其中 k 尚不清楚（欢迎提出建议）。

示例（D = 4，k = 2）：

第一列应作为散列函数的输入并返回桶的编号。

让我困惑的是，我们不是在寻找一个函数来散列一个数字，而是一个列，即一个正整数列表。

请问有什么想法吗？

_{如果这很重要，我正在使用python}

在 LSH 中，您将文档的切片散列到存储桶中。这个想法是，落入相同存储桶的这些文档可能是相似的，因此可能是最近的邻居。

对于 40.000 个文档，存储桶的数量（几乎）是多少？

我有它：number_of_buckets = 40.000/4现在，但我觉得它可以减少更多。

有什么想法吗？

相对：如何在局部敏感散列中将向量散列到桶中（使用杰卡德距离）？