5

我有两个名称和一个地址的“记录”（基本上是 CSV 字符串）。我需要找到彼此相似的记录：基本上名称和地址部分看起来都“相似”，就好像它们是由人类解释的一样。

我使用了这篇出色的博客文章中的想法：http: //knol.google.com/k/simple-simhashing#编写了一个简单的 SimHash。如果两个或多个字符串的 SimHash 结果相同，我会将这个子集的所有记录传递给一个细粒度的匹配程序，该程序是 O(n^2)，它将集合中的每条记录与其他每条记录进行比较。

对于 SimHash 部分，我有一些参数，我可以在其中定义数据报大小（基本上是字符串上大小为 n 的滑动窗口）和用于确定 SimHash 计算需要使用多少（随机）哈希的迭代次数. 到目前为止，数据报大小为 4 并使用 4 个哈希来计算 SimHash。我尝试了各种其他组合，但到目前为止，这个组合产生了最好的结果。

我遇到的问题是这种方法在我拥有的数据集中找到了大约 80% 的重复项。我知道这一点是因为我已经根据上面提到的极其缓慢的 O(n^2) 完全匹配验证了整个数据集。O(n^2) 匹配器适用于小于 10^4 的数据集，但很快变得不可行，因为我需要运行大小为 10^8 的集。

关于如何提高 SimHash 的准确性以便更多“相似”记录被标记为相同的 SimHash 编号的任何想法、建议或想法？

编辑：在 SimHashing 之前，我将所有 ![0-9A-Z] 字符大写并删除。应该匹配的例子（拼写错误是故意的）：

  • JOHN SMITH, 123 ANY STREET Sometown ZIP
  • 约翰尼·史密斯，123 岁
  • SOMETOWNE ZIP ROBERT PARKER, 442 ANY STREET SOMETOWN ZIP

这里1和2是相似的，3不是。输出应该是：1 + 2

4

3 回答 3

3

在您尝试花哨并更改 sim 哈希之前，您是否尝试过将特定领域的知识应用于问题？

您的算法是否有遗漏对的列表？他们有什么共同点吗？

您是否尝试过删除大写、将昵称转换为全名、删除中间名、扩展 N、E、S、W 和北、南、东、西、将 st 扩展为街道等操作？

于 2011-11-30T15:02:44.770 回答
0

（我会将以下内容放在评论中，但还没有代表。）

你最终想要做什么？查找所有重复项？您如何定义重复项？区分大小写很重要吗？类似的写法？

我对你如何处理这件事有点困惑——找到相似的记录并创建一个集合，但后来 O(n^2) 检查我认为是完全相等的。如果您正在检查是否完全相等，那么这似乎违背了查找相似记录的目的（除非您将其用作 O(n^2) 的过滤器以节省时间。

一些随机的想法：通过一种尝试将每条记录转换为最一般形式的消毒剂运行每条记录（如果你关心/这很重要）。

如果您感兴趣的是完全相等，并且内存不是限制，但您正在寻找速度，那么您可以为每条记录创建一个 Java 对象。为每条记录定义 .equals() （您始终可以自定义它以不执行完全相等）。然后，您需要为此对象定义一个 hashCode()。然后，您可以将每条记录粘贴到 HashSet 中。

生成的 HashSet 将没有重复项（由您的 .equals() / .hashCode() 实现定义）。

或者，如果您想查找重复项，则在添加到 HashSet 之前，首先检查它是否包含记录，如果包含，则您找到了重复项。

这种实现会非常快，但可能会使用大量内存，因为您会将整个数据集存储在内存中。替代方法是为每条记录创建一个散列，然后将其存储在 HashSet 中，并检查每条记录的散列是否相等。

对每条记录进行哈希处理的缺点是开发具有良好分布的良好哈希生成的挑战，当然，对于哈希，您必须担心碰撞的误报。但是，如果您的散列算法是可靠的，那么发生冲突的机会应该非常少，以至于您不必真正担心它。

你可以做的一些关于哈希的想法就像所有字段连接的 MD5 一样简单。你可以做一个校验和。或者您可以取每个字段的 hashCode 总和。我不是一个超级数学天才，所以我不能告诉你哪个具有最好的分布行为，从而导致发生碰撞的可能性最小。如果您决定走这条路，可能值得研究。

于 2011-11-30T15:30:51.367 回答
0

Simhash 不是用于此目的的合适算法，因为它仅适用于差异非常小且大部分特征相同的近似重复检测。请参阅我关于simhash 和解决汉明距离问题的教程。

更好的方法是minhash，可能使用 LSH。看起来您的散列特征最好生成为字符的带状疱疹（长度可能为 4），而不是单词的带状疱疹。

鉴于如此短的文本字段，并且考虑到词序可能不会发生太大变化，您应该考虑包括终止带状疱疹：从包含少于正常字符数的文本字段的开头和结尾开始的带状疱疹，加上终止标记。这往往对短文本的拼写差异更加宽容，例如没有终止带状疱疹的“Whitmore”和“Whitemore”会产生

[ WHIT, HITM, ITMO, TMOR, MORE ] 和 [ WHIT, HITE, ITEM, TEMO, EMOR, MORE ] Jaccard 相似度低至 2/9；

而在包括终止带状疱疹的情况下，这些将产生

[#W、#WH、#WHI、WHIT、HITM、ITMO、TMOR、MORE、ORE#、RE#、E#] 和 [#W、#WH、#WHI、WHIT、HITE、ITEM、TEMO、EMOR、MORE , ORE#, RE#, E# ] 具有较高的 Jaccard 相似度 8/15；

Rob Neuhaus 关于预标准化的建议非常明智。我会将长形式的单词规范化为它们的缩写（例如，“Saint James Street”将规范化为“ST JAMES ST”）。有时使用模棱两可的缩写（“St”->“STREET”或“SAINT”？），在另一个方向上进行规范化可能很困难，而且，缩写形式有助于减少带状疱疹，因此对整体相似性的影响较小，即很好，因为人们经常将“路”误写成“街道”等，但它的含义并没有太大变化。

于 2019-08-12T04:55:56.117 回答