使Sim Hash (局部性敏感散列)算法更精确？

Question

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

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

对于SimHash部分，我有参数，可以定义数据报大小(基本上是大小为n的滑动窗口)和用于确定SimHash计算所需的多少(随机)散列的迭代次数。到目前为止，数据报大小为4，并使用4个散列来计算SimHash。我尝试过其他各种组合，但这个组合产生了迄今为止最好的效果。

我遇到的问题是，这个方法在我拥有的数据集中找到了大约80%的副本。我之所以知道这一点，是因为我已经根据上面提到的非常慢的O(n^2)完全匹配验证了整个数据集。对于小于10^4的数据集，O(n^2)匹配器是可以的，但是由于我需要运行大小为10^8的集合，所以很快就变得不可操作了。

有什么想法，建议或想法，我如何可以提高SimHash的准确性，以便更多的“相似的”记录被标记为相同的SimHash号码？

编辑:在使用SimHashing之前，我会大写并删除所有字符。应该匹配的东西的例子(拼写错误是故意的)：

• 约翰·史密斯( JOHN )，123岁，任何一条街道
• 约翰尼·史密斯，123岁
• 罗伯特·帕克( ROBERT )，任何一条街道

在这里，1和2是相似的，3不是。产出应为:1+2

Answer 1

在尝试更改sim散列之前，您是否尝试过将特定领域的知识应用于此问题？

你有算法漏掉的一对的列表吗？他们有什么共同点吗？

你有没有试过做一些事情，比如去掉大写，把名字转换成全名，去掉中间名，把N，E，S，W和北，南，东，西，扩大到街道，等等？

Answer 2

(我会在评论中加入下面的内容，但还没有得到代表。)

你到底想做什么？找到所有的副本？你是如何定义副本的？案件敏感性很重要吗？类似的措辞？

我对您是如何处理这个问题感到有点困惑--找到类似的记录并创建一个集合，但是随后O(n^2)检查我假设的完全相等的内容。如果您正在检查是否完全相等，那么这似乎没有达到查找类似记录的目的(除非您将其用作O(n^2)的筛选器，以节省时间。

一些随机的想法:运行每一个记录通过一种消毒液，试图将每个记录转换为最一般的形式(如果你关心/这很重要)。

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

生成的HashSet将没有重复项(正如.equals() / .hashCode()实现所定义的)。

或者，如果要查找副本，那么在添加到HashSet之前，先检查它是否包含记录，如果包含了，则找到一个副本。

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

为每条记录做散列的缺点是开发一个具有良好分布的好散列生成的挑战，当然，对于散列，您必须担心有冲突的假阳性。但是，如果您的哈希算法是坚实的，那么碰撞的机会应该是非常罕见的，你不应该真的担心它。

对于散列，您可以做一些简单的事情，比如连接所有字段的MD5。你可以做个检查。或者，您可以为每个字段取hashCode之和。我不是一个超级数学天才，所以我不能告诉你，哪一个会有最好的分布行为，从而导致发生碰撞的可能性最小。如果你决定走这条路，也许值得研究。

Answer 3

Simhash不是一个适合这一目的的算法，因为它只适用于几乎重复的检测，在这些检测中，差异非常小，而且大部分特征是相同的。请参阅我关于simhash与求解hamming距离问题的教程。

一个更好的方法是minhash，可能与LSH一起使用。看起来，您的散列特性最好是以字符块(长度可能为4)的形式生成，而不是由字条组成。

考虑到这样短的文本字段，并且考虑到词序可能不会发生太大的变化，您也应该考虑包括终止板条:从文本字段的开头和结尾开始和结束，其中包含的字符数少于正常的字符数，再加上一个结束标记。这往往是比较宽容的拼写差异的短文运行，例如。"Whitmore“和"Whitemore”如果不终止板条，就会屈服。

WHIT，HITM，ITMO，TMOR，MORE和WHIT，HITE，ITEM，TEMO，EMOR，较低的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；

罗布·纽豪斯关于预正常化的建议是非常明智的。我会把长形词标准化成缩略语。“圣詹姆斯街”将标准化为“圣詹姆斯街”)。用有时含糊不清的缩略语("St“--> "Street”或“St”？)来规范另一个方向可能很困难，而且，缩写形式有助于减少板子，因此对整体相似性的影响较小，这是很好的，因为人们经常把“路”错误为“街”等，而且它并没有改变意思。