问题标签 [minhash]

据我所知，simhash 和 minhash 可用于此任务。但是所有这些算法都必须遍历整个文本数据库，这将是非常可怕的。是否有任何优化或其他算法可以加速任务？我想出的只是将文本数据库分成几个部分并并行获得成对相似度。我的文本数据库有大约 10 亿条记录。

我在 Octave/Matlab 中创建 MinHash 和 LSH。但是我试图从给定的文档中获取一组大小为 k 的带状疱疹（单元数组或数组），但我不知道该怎么做。

我现在拥有的是这个简单的代码：

这将创建一个包含文档每一行中所有单词的单元格数组，这是我正在尝试执行的函数的一个参数。

假设我们有两个集合的 minhash 签名，我们想要计算两个集合的 Jaccard 相似度。我们有：

-> S1 S2

h1 0 1

h2 1 2

h3 2 0

h4 3 3

S1 和 S2 具有相同的签名，但顺序不同。Jaccard 相似度是 1/8 还是 1（大约）？

我正在使用 simhash，但也看到 minhash 更有效。
但我不明白。
请为我解释一下：minhash 比 simhash 有什么优势？

结果是固定数量的数组，比方说python中的列表（所有相同的长度） 。

人们也可以将其视为矩阵，因此在c中我将使用一个数组，其中每个单元格都指向另一个数组。如何在 Python 中做到这一点？

一个列表，其中每个项目都是一个列表或其他东西？

我想到了一本字典，但键很简单，1、2、...、M，所以我不确定这是否是 pythonic 的方式。

我对实现不感兴趣，我感兴趣的是我应该遵循哪种方法，应该做出哪种选择！

我对使用 MinHash 和 banding 技术对集合进行聚类的方式存在很大疑问。

我假设阅读的每个人都对 MinHash 有很好的了解，所以我不会定义我使用的大多数术语。

我的目标是使用 MinHash 根据签名的相似性对用户进行聚类。在本地的非带状设置中，这将是微不足道的：如果它们的签名哈希相同，则它们进入同一个集群。

如果我们将签名分成带状并独立处理它们，我可以像我之前所说的那样对待一个带，并为每个带生成一组集群。我的问题是：我应该如何聚合这些集群？如果它们至少有一个共同元素，就合并它们？还是我应该做一些不同的事情？

谢谢

我正在尝试根据视觉词（图像中标记的关键点）匹配图像。在将模拟结果与我的理论结果进行比较时，我得到了很大的偏差，因此我猜我的理论概率计算中一定有错误。

您可以将两个图像想象为一组视觉词（视觉词名称范围从 A 到 Z）：

您已经可以看到一些视觉词出现在两个集合中（例如 A、Z、Y、...）。现在我们将视觉词分为主要词和次要词（参见提供的图像）。每个主要词都有一个次要词的邻域。您可以看到主要单词（红色矩形）和它们的次要单词（椭圆内的单词）。对于我们的示例，主要单词集如下：

我们现在从集合 SP1 中随机选择一个视觉词img1VAL1和从 的邻域中选择一个词img1VAL1，即img1VAL2=SelFromNeighborhood(img1VAL1)产生一对PairImage1={img1VAL1, img1VAL2}。我们对第二张图片做同样的事情并得到PairImage2={img2VAL1, img2VAL2}.

示例：从Image1我们选择A作为主要视觉词和C作为次要词，因为C在 的邻域内A。我们得到了这对{A, C}

从 Image2 我们也选择A作为主要视觉词和Z作为辅助词。我们得到了这对{A, Z}

{A,C} != {A,Z}因此我们没有对手。但是随机选择的对相等的概率是多少？

我有大量（15 亿）个整数对，其中每一对都与一个文档 ID 相关联。我现在的目标是搜索具有相同对的文档。

我的第一个想法是使用哈希映射（std::map），使用对值作为键，将文档 ID 作为关联值，即map<pair<int,int>, unordered_set<int>>

例如：

会导致

我现在的问题是这需要大量内存，超过了我可用的 24 GB RAM。因此，我需要一个具有良好插入和查找性能的替代方案，以适应我的记忆。理论上我在1500 Million * 3 (PairVal1, PairVal2, Document-ID) * 4 (bytes per Integer) = 18GB不考虑间接费用时使用。那么我的问题有什么好的选择吗？

我正在尝试在 Spark 中尽可能简单地实现第 3 章中描述的 MinHash 算法。我到处搜索了很多。好吧，我决定按照 Bill Dim 的建议遵循这个博客的实现：https://blog.cluster-text.com/tag/minhash/ 我只是觉得我的实现有问题或者我误解了。到目前为止我所做的是：

• document => n-grams（我使用书中所说的 9-grams（字母），但可以按照 Bill Dim 的建议将其更改为 5-words）
• n-grams => MurMurHash3（这就是每个文档的 NGrams）
• HashedNGramsRDD => 为每个文档查找 Min(NGram)
• HashedNGramsRDD ^ (199 个随机数) 并取 min = 199 个 Xored HashedMurMurNGrams 的最小值。
• 所以我总共有200个最小值。这就是我的 MinHash 签名。这个对吗？请帮忙！提前致谢。

对于我的 minhashing 算法的实现，我需要对整数进行许多随机排列，这将通过使用随机散列函数（尽可能多）来模拟。目前我使用以下形式的哈希函数：

其中a和b是随机生成的数字，c是大于b最大值的素数。无论如何，代码运行得太慢了，不可能在合理的运行时间内使用超过 15 个这样的哈希函数。任何人都可以推荐其他在 Python 中对整数使用随机散列函数的方法吗？在其他帖子中，我遇到了使用按位混洗和XOR操作的建议，但我并不完全理解应该如何实现这样的东西（我对 Python 比较陌生）。