使Sim Hash(Locality Sensitive Hashing)算法更准确？

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之前,我大写并删除所有![0-9A-Z]字符.应该匹配的事情的例子(拼写错误是有意的):

---

• 约翰史密斯,123任何街道的东西邮编
• 约翰尼史密斯,123任何一个角落
• SOMETOWNE ZIP ROBERT PARKER,442 ANY STREET SOMETOWN ZIP

---

这里1和2是相似的,3不是.输出应为:1 + 2

Answer 1

在你尝试花哨地改变 sim 哈希值之前，你是否尝试过应用特定领域的知识来解决问题？

您的算法有丢失配对的列表吗？他们有什么共同点吗？

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