2

我对检测相似文档的技术有一个合理的理解，该技术首先计算它们的 minhash 签名（从它们的 shingles 或 n-gram），然后使用基于 LSH 的算法来有效地对它们进行聚类（即避免二次复杂度，这将需要一个简单的成对穷举搜索）。

我正在尝试做的是桥接三种不同的算法，我认为这些算法都与这个 minhash + LSH 框架有关，但以非显而易见的方式：

（1） Mining of Massive Datasets（Rajaraman and Ullman）一书第3章第3.4.3节勾勒的算法，似乎是minhashing的规范描述

(2) Ryan Moulton 的Simple Simhashing文章

（3）Charikar所谓的SimHash算法，本文介绍

我觉得这很令人困惑，因为我假设虽然 (2) 使用术语“simhashing”，但它实际上是以类似于 (1) 的方式进行 minhashing，但关键区别在于集群只能由单个签名表示（甚至可能涉及复杂的多个哈希函数），而两个文档有更多与（1）相似的机会，因为签名可以在多个“带”中发生冲突。(3) 似乎完全不同，因为签名是根据它们的汉明距离进行比较的，而 LSH 技术意味着对签名进行多次排序，而不是对它们进行捆绑。我还看到（在其他地方）最后一种技术可以包含加权的概念，它可以用来更加强调某些文档部分，而这似乎在 (1) 和 (2) 中缺乏。

所以最后，我的两个问题：

(a) 是否有一种（令人满意的）方法可以连接这三种算法？

(b) 有没有办法将权重概念从 (3) 导入到 (1)？

4

1 回答 1

0

第 2 条实际上是在讨论 minhash，但错误地称之为 simhash。这可能就是它现在被删除的原因（它在此处存档）。此外，令人困惑的是，它谈到了“连接”多个 minhashes，正如您正确地观察到的那样，它减少了找到两个相似文档的机会。它似乎规定了一种只产生一个“带”的方法，这将产生非常糟糕的结果。

算法可以桥接/组合吗？

可能不是。要了解原因，您应该了解不同哈希的属性是什么，以及如何使用它们来避免文档之间的 n 2比较。

minhash 和 simhash 的属性：

本质上，minhash为每个文档生成多个哈希，当有两个相似的文档时，这些哈希的子集很可能是相同的。Simhash 为每个文档生成一个哈希，如果有两个相似的文档，它们的 simhash 可能会相似（具有较小的汉明距离）。

他们如何解决 n 2问题：

使用 minhash 您可以将所有哈希索引到包含它们的文档；因此，如果您为每个文档存储 100 个散列，那么对于每个新传入的文档，您需要在索引中查找其 100 个散列中的每一个，并找到至少（例如）50% 共享它们的所有文档。这可能意味着建立大量的临时统计，因为成千上万的文档可以共享至少一个哈希值。

使用 simhash 有一种巧妙的技术，可以将每个文档的散列存储在多个排序表中的多个排列中，这样任何类似的散列达到一定的汉明距离（3、4、5，可能高达 6 或 7，具体取决于散列大小和表结构）保证可以在这些表中的至少一个中找到附近，不同之处仅在于低位。这使得搜索相似文档变得高效，但限制您只能查找非常相似的文档。请参阅此simhash 教程。

因为 minhash 和 simhash 的使用是如此不同，所以我看不到桥接/组合它们的方法。从理论上讲，您可以拥有一个生成 1 位哈希并将它们连接成类似 simhash 的 minhash，但我认为这没有任何好处。

可以在minhash中使用加权吗？

是的。将 minhashes 视为插槽：如果每个文档存储 100 个 minhashes，则可以填充 100 个插槽。这些插槽不必全部从相同的文档特征选择中填充。您可以将一定数量的插槽用于仅根据特定特征计算的哈希值（但应注意始终以在相似文档中选择相同特征的方式选择特征）。

因此，例如，如果您正在处理期刊文章，您可以为文档标题的 minhashes 分配一些插槽，为文章摘要的 minhashes 分配一些插槽，为文档正文的 minhashes 分配其余插槽。您甚至可以为作者姓氏等事物的直接哈希留出一些单独的插槽，而无需担心 minhash 算法。

它不像 simhash 那样优雅，实际上你只是创建所有单个特征哈希的按位加权平均值，然后将每个位向上舍入到 1 或向下舍入到 0。但它非常可行。

于 2019-02-13T01:03:29.173 回答