问题标签 [minhash]

我有一个大小为 (160000,3200) 的数据集，其中所有元素都是零或一。我想找到类似的候选人。我已经使用 Minhash 使用一个 for 循环将它散列到 (160000,200) 并且花了大约两分钟，我很满意。我已经使用从“海量数据集挖掘”的第 3 章中学习的 AND-OR 模式实现了局部敏感哈希（LSH），以在 for 循环中使用 for 循环查找候选对，但花了 30 分钟。我想减少这个时间。有没有更快的方法？

这是我如何完成 LSH - Minhash 签名长度 (n) = 200，子签名长度 (r) = 5，波段数 (b) = 40。

大小为 (160000,200) 的 Minhash 签名矩阵是一个 numpy 数组。我的想法是，如果我可以便宜地将其转换为 (160000,40) 数组，其中新数组的每个元素由 minhash 数组的 5 个元素组成，那么也许我可以使用 numpy.unique() 为每列获取唯一的 r_signature用作候选ID字典的键。我是 python 和编码的新手。我想不出一种方法来优化它以使其运行得更快。

这是代码和数据的链接： https ://colab.research.google.com/drive/1HetBrWFRYqwUxn0v7wIwS7COBaNmusfD

注意：我观察到 Minhash 部分所花费的时间随着数据（在这种情况下为用户数）线性增加，而对于 LSH 部分，它是非线性增加的（对于前 6.25%，它花费了 20.15 秒，对于最后 6.25% 用时 132.3 秒）。我认为有必要优化这部分，如果可能的话，用数据正确扩展。我相信检查字典中是否已经存在密钥是负责此问题的代码部分。

更新：我已经通过避免检查字典中键的存在来解决这个问题，尽管我最终在 for 循环中使用了 for 循环两次。现在，160000 个候选人需要 310 秒，并且所花费的时间与数据呈线性关系。我已经更新了 google-colab notebook 中的相应代码。

我有一个学术论文数据集，它有 27770 篇论文（节点）和另一个文件（图形文件），原始边长为 352807 个条目。我想计算 minHashLSH 以找到相似的文档并预测两个节点之间的链接！下面你可以看到我尝试用 scala 在 spark 上实现这个。我面临的问题是我不知道如何评估结果！

原始图是具有nodeAId、nodeBId 格式的文件。我的结果是 nodeAId、nodeBId、JaccardSimilarity 的形式。它们都是数据框。如何评估我的结果并获得准确度或 F1 分数？

我已经阅读了如何找到准确度和 F1 分数，所以我尝试制作一个函数来计算它们。我的方法是下面的代码。

但是，当我尝试运行它时，它永远不会结束！我不知道如何改进或修复它以获得准确度和 F1 分数。有没有更简单的方法来做到这一点？

感谢大家！

我有一个数据集，其中包含从许多不同来源收集的数百万个项目。每个项目都包含从五十到一千个属性的列表。可用的特定属性因项目而异。

我正在寻找找到与集合中给定目标成员项目最相似的项目的最佳方法。（我显然想在不与集合中的所有项目进行蛮力比较的情况下完成此操作。）

我想使用类似 Locality Sensitive Hashing 和 MinHash 的东西。但是，如果目标项目有 50 个属性，而较大数据集中可能匹配的项目有 200 个，即使具有 200 个属性的项目包含目标项目的所有属性，MinHash 也会认为这些是不相似的。

用于比较具有不同数量属性的项目的最佳技术或算法是什么？

我已经使用 MinHashLSH 和approximateSimilarityJoin 以及 Scala 和 Spark 2.4 来查找网络之间的边缘。基于文档相似度的链接预测。我的问题是，当我增加 MinHashLSH 中的哈希表时，我的准确性和 F1 分数正在下降。我已经为这个算法阅读的所有内容都表明我有一个问题。

我尝试了不同数量的哈希表，并提供了不同数量的 Jaccard 相似度阈值，但我遇到了同样的问题，准确度正在迅速下降。我也尝试过对我的数据集进行不同的采样，但没有任何改变。我的工作流程是这样进行的：我正在连接我的数据框的所有文本列，其中包括标题、作者、期刊和摘要，接下来我将连接的列标记为单词。然后我使用 CountVectorizer 将这个“词袋”转换为向量。接下来，我在 MinHashLSH 中为该列提供一些哈希表，最后我正在做一个近似相似性连接来查找低于我给定阈值的类似“论文”。我的实现如下。

我忘了告诉你，我在一个有 40 个内核和 64g RAM 的集群中运行这段代码。请注意，近似相似连接（Spark 的实现）适用于 JACCARD DISTANCE 而不是 JACCARD INDEX。因此，我提供了 JACCARD DISTANCE 作为相似度阈值，在我的情况下，它是 jaccardDistance = 1 - 阈值。（阈值 = Jaccard 指数）。

我希望在增加哈希表时获得更高的准确性和 f1 分数。你对我的问题有任何想法吗？

提前感谢大家！

我正在寻找一个 node.js / Javascript 模块，它将 minhash 算法应用于字符串或更大的文本，并为我返回该文本的“识别”或“特征”字节字符串或十六进制字符串。如果我将该算法应用于另一个相似的文本字符串，则哈希字符串也应该相似。这样的模块是否已经存在？

到目前为止，我正在检查的模块只能直接比较文本并直接计算与比较文本的某种 jaccard 相似度，但我想为每个文档存储某种哈希字符串，以便以后可以如果我有相似的文本，比较字符串的相似性......

本质上，我正在寻找的是这里的代码（Java）：在 Javascript 中： https ://github.com/codelibs/elasticsearch-minhash

例如，对于像：这样的字符串 "The quick brown fox jumps over the lazy dog"，"The quick brown fox jumps over the lazy d"它会为第一句话创建一个哈希，例如：

对于第二个字符串，例如：

两个哈希字符串差别不大......这就是minhash算法的重点，但是，我不知道如何创建类似的哈希字符串......到目前为止我发现的所有库，只直接比较2个文档和创建一个相似系数，但它们不会创建文档特征的哈希字符串...与所有算法的相似之处在于，它们为其单词标记数组（或带状疱疹）创建散列 crc32（或类似）散列值. 但我仍然不知道他们如何将这些哈希相互比较......

我正在使用 Python 3.7.1 使 minhash 成为字符串列表。代码如下。

为了加快速度，我正在使用 datasketch.Minhash文档中提到的 mmh3.hash （mmh3.hash32 不再可用），这会产生以下错误

TypeError：输入类型不支持 ufunc 'bitwise_and'，并且根据转换规则 ''safe'' 无法安全地将输入强制转换为任何支持的类型

我没有找到具体的原因这个原因和解决方法。我应该如何解决这个问题？或者有没有其他方法可以加快 minhash 计算。提前感谢您的宝贵时间——如果我遗漏了任何内容、过分强调或过分强调某个具体点，请在评论中告诉我。

我在弹性搜索中存储了许多带有 minhashed 字段（基于内容相似性）的文档。现在，我要么使用 Elasticsearch API 将它们相互比较以获得相似的（散列）文档，但我不能进行模糊查询，因为它只允许编辑距离为 2，因此无用。

如果不能在 Elasticsearch 中完成，我也在寻找可能的 Node.js 实现。我的第一种方法是检索 Elasticsearch 中每个文档的所有 id 和 minhash-values (=hex-strings)，然后将它们存储在一个数组中并按字典顺序对它们进行排序。然后，我只需要根据编辑距离比较最近的邻居 k 文档，而不是

n*(n-1)/2比较，所以我只会n*k比较。您如何看待这种方法？

我为某些文本生成了一个 minhash 字段（基于 minhash 算法），现在我的问题是，是否可以用通配符以某种方式补充或添加前缀查询？因为问题是，散列字符串值基于带状疱疹/令牌的内容（文本）位置。所以前几个字符（前缀）可能并不总是完全匹配相似的内容。是否可以在查询的前缀前添加通配符，例如 *3AF8659GJ？

编辑：我想我对这个问题的思考不够深入。哈希差异可以在哈希字符串中的任何位置（基于文本差异的内容位置的文本差异）。所以我猜“最好”的唯一方法是编辑距离和一些阈值。

例如，将所有哈希放入一个数组中并按词法顺序对它们进行排序（或者你将如何对十六进制字符串进行排序？）然后你只比较下一个 k 文档直到达到编辑距离阈值，并将重复项放在一个单独的数组中..

我想使用 MinHash LSH 将大量文档放入相似文档的桶中（Jaccard 相似度）。

问题：是否可以在不知道其他文档的 MinHash 的情况下计算 MinHash 的桶？

据我了解，LSH“只是”计算 MinHashes 的哈希值。所以应该可以吧？

我觉得很有希望的一种实现是datasketch。在知道所有文档的 MinHash 后，我可以在 LSH 中查询与给定文档相似的文档。但是，在了解其他文档之前，我认为没有办法获取单个文档的存储桶。 https://ekzhu.github.io/datasketch/index.html

我在 x 和 y 轴上绘制了 personID 和 VaccinationsID。我想将那些接种疫苗选择最相似的 personID 分组。我正在尝试使用聚类机器学习算法。但是我不确定我应该使用这个算法还是用户协同过滤。

我的目标是实现 Jaccard 索引，即找到 10000 个人之间的交叉点或相似点，并形成聚类并标记它们。根据相似程度，我需要对personsID进行分组。谁能告诉我哪种方法有效？如果对数百万数据使用聚类是可行的

我添加了图表的屏幕截图