问题标签 [minhash]

我有一个名为的类FindSimilar，它使用 minHash 来查找 2 个集合之间的相似性（对于这个目标，它工作得很好）。我的问题是我需要比较两个以上的集合，更具体地说，我需要将给定set1的集合与未知数量的其他集合进行比较。这是课程：

我需要similarity在超过 2 套上使用该方法。问题是我无法找到一种方法来遍历所有这些。如果我创建一个for，我不能说我想比较set1和seti。我不确定我是否有道理，我必须承认我有点困惑。

该程序的目标是比较用户。一个用户有一个联系人列表（其他用户），相似的用户有相似的联系人。每个集合都是一个用户，集合的内容将是他们的联系人。

我有一个包含 10,000,000 个字符串的列表，每个字符串都是一个项目的名称。3 到 5 个单词，最多 80 个字符。

然后我有一个包含 5,000 个字符串的列表来匹配。这意味着，对于 5,000 个潜在匹配规则中的每一个，我需要确定它与 10,000,000 个字符串中的多少个匹配。

到目前为止，我已经使用以下内容进行了成对迭代：

我让它在 10,000,000 个字符串的一个子集上工作得很好，但我不知道如何扩展算法。使用概率数据结构有什么建议吗？我知道 MinHash 或 BloomFilter 可能有一些潜力，但我无法理解它将如何应用于此问题。

bucket_count 设置对应什么？这是否意味着 minhashes 被进一步散列到 1 和 bucket_count-1 之间的值？

在以下情况下生成 minhashes 会导致任何加速吗？

案例：索引 1000 万个文档，其中每个文档只是一组特征索引。可能的索引总数为 10000。因此文档可能看起来像 A={1,5,7,500,750...9800} 此外，所有文档/集的长度都是固定的（假设是 196）。在这种情况下，检索与文档 A 最相似的文档意味着遍历所有 1000 万个文档以找到那些索引重叠最多的文档。

使用 minhashes 会加速上述相似度检索吗？这令人困惑的原因是原始文档/集都相当小——196 个特征。

默认存储桶大小为 528 的 Minhash 标记化将生成一个长度为 528 的标记集——比原始文档长（如上所述，为 196）

在这种情况下，minhash 真的会以任何方式帮助加快检索速度吗？

I am new to spark but I am attempting to produce network clusters using user supplied tags or attributes. First I am using the jaccard minhash algorithm to produce similarity scores then running it through power iteration clustering algorithm but as soon as it starts there is no CPU activity and will run for some time with zero progress. Wondering how to configure the cluster or change the code to get this to run. Below is my code

我有以下两个文本：

text0 = "AAAAAAAAAAAA";

text1 = "AAAAAAAAAAAAA";

我使用 4 瓦。因此，text0 = {AAAA}，text1 = {AAAA，AAAB，AABA，ABAA，BAAA}。

那么，Jaccard 相似度为 sim = 1/5 = 0.2。

我不想要这个结果。因为这两个文本似乎具有很高的相似性。

我想使用袋相似度如下：

text0 = {AAAA，AAAA，AAAA，AAAA，AAAA，AAAA，AAAA，AAAA，AAAA}，

text1 = {AAAA，AAAA，AAAA，AABA，ABAA，BAAA，AAAA，AAAA，AAAA}。

如果使用这两个袋子，它的相似之处是 sim = 5/9。这远高于 0.2。

MinHash可以做到这一点吗？

假设我有两个时间戳系列事件：

每个时间戳表示它发生的时间。

他们可能看起来像

我们可以看出，T2 只是 T1 的时移，所以它们属于同一模式。相似度应为 100%。

它们也可能看起来像

这里的相似度应该是 50%。

我读过一篇论文说我们可以应用 LSH（Locality-Sensitive Hashing）来检测相似性。但我不知道如何详细做到这一点。任何想法？

我在文档及其带状疱疹上使用了 minhash，以从这些文档中生成签名矩阵。我已经验证了签名矩阵在比较已知相似文档（例如，关于同一支球队的两篇文章或关于同一世界赛事的两篇文章）的 Jaccard 距离方面很好，可以给出正确的读数。

我的问题是：使用这个签名矩阵来执行 k-means 聚类有意义吗？

我尝试使用文档的签名向量并在迭代 kmeans 算法中计算这些向量的欧几里得距离，但我总是对我的集群感到无意义。我知道应该有两个集群（我的数据集是关于体育或商业的几千篇文章），最后我的两个集群总是随机的。我确信将单词散列成整数的随机性每次都会使距离函数产生偏差，并压倒两个签名矩阵中的相似散列值。

[编辑以突出问题]

如果我有 2 个系列对象，如下所示： [0,0,1] [1,0,0] 如何获得两者的交集和并集？它们只包含布尔值，这意味着它们是非唯一值。

我有一个大的布尔矩阵。我已经对其进行了minhashed，现在我试图找到误报和误报，我认为这意味着我必须获得每个原始对的 Jaccard 相似性。

我正在尝试使用.approxSimilarityJoinSpark MLlib LSH: MinHash for Jaccard Distance例如

我知道 numHashTables 越高，系统越准确，计算越复杂/越慢。我有两个关于参数的问题：

• numHashTables 和 MinHash 指纹大小有什么关系？
• 如何正确设置值？

注意：我相信该算法已被 Uber 添加到 MLlib：https ://eng.uber.com/lsh/

假设我必须估计文档 A 和 B 之间的 jaccard 相似性，并且我使用这些集合/文档的并集的 k 个随机排列来确定文档的签名。

我应该如何设置我的 k 值？因为将它设置为一个非常高的值会显着增加计算时间，所以可以给我一个好的 jaccard 指数估计值的 k 的最小值是多少？

给定容错 e>0 和 delta，我如何确定 k 的最小值，使得 jaccard 索引介于 (1-e)jaccard_estimate 和 (1+e)jaccard_estimate 之间，概率大于或等于 (1-delta) ?

我相信这可以使用 chernoff 不等式界限得出，但我无法弄清楚如何去做。任何帮助，将不胜感激。提前致谢！