11

我在SQL Server 2008Persons中有表。

我的目标是找到地址几乎相似的人。

state地址用、town、street、house、apartment、postcode和列描述phone。

由于某些州（不是美国）和人为因素（地址错误等）的某些特定差异，地址没有以相同的模式填写。

地址中最常见的错误

  1. 区分大小写
  2. 有人写“apt.”，另一个写“apartment”或“ap”。（虽然地址不是用英文写的）
  3. 空格、点、逗号
  4. 写街道名称的差异，例如“Dr. Jones str.”或“Doctor Jones street”或“D. 乔恩。圣。”或“琼斯博士圣”等。

主要问题是数据的模式不同，因此很难找到相似的地址。

有没有针对此类问题的算法？

提前致谢。

更新

  1. 正如我提到的，地址被分成不同的列。我应该生成一个连接列的字符串还是为每列执行您的步骤？我假设我不应该连接列，但是如果我要分别比较列，我应该如何组织它？我应该为每列找到相似之处，将它们合并或相交或其他任何东西吗？
  2. 我应该收集一些统计数据还是某种教育算法？
4

15 回答 15

7

建议这样接近它：

  1. 从各种条目创建单词级别的 n-gram（一个 trigram/4-gram 可能会这样做）

  2. 对字符串比较进行多 x 多比较，并按字符串距离对它们进行聚类。有人建议Levenshtein；这类任务有更好的方法，Jaro-Winkler Distance 和 Smith-Waterman 效果更好。像 SimMetrics 这样的库会让生活变得更轻松

  3. 一旦你有了 n-gram 的集群，你就可以使用组成子图来解析整个字符串，即 D.Jones St => Davy Jones St. => DJones St。

不应该太难，这是一个太常见的问题。

更新：根据您上面的更新，这里是建议的步骤

  1. 将您的列连接成一个字符串，也许创建一个 db "view" 。例如，

    创建视图 vwAddress 作为选择前 10000 个州镇、街道、房屋、公寓、邮政编码、州+城镇+街道+房屋+公寓+邮政编码作为地址来自 ...

  2. 编写一个单独的应用程序（例如在 Java 或 C#/VB.NET 中）并使用 JaroWinkler 之类的算法来估计组合地址的字符串距离，以创建多 x 多比较。并写入单独的表地址1 | 地址 n | 相似

您可以使用 Simmetrics 来获得相似度：

 JaroWinnkler objJw = new JaroWinkler()
double sim =  objJw.GetSimilarity (address1, addres n);

  1. 您还可以对它进行三元组合，使诸如“1 Jones Street, Sometown, SomeCountry”之类的地址变为“1 Jones Street”、“Jones Street Sometown”等等......并比较这些三元组。（甚至 4 克）以获得更高的准确性。

  2. 最后，您可以按相似度排序以获得最相似地址的集群并确定适当的阈值。不知道为什么你被卡住了

于 2010-07-08T09:41:12.223 回答
5

我会尝试执行以下操作：

  • 将地址拆分为多个单词，同时去掉标点符号
  • 检查所有通常以不同方式书写的模式的单词并将它们替换为通用名称（例如，将公寓、ap.、...替换为 apt，将 Doctor 替换为 Dr.，...）
  • 将所有单词按字母顺序放回一个字符串中
  • 使用模糊字符串比较算法比较所有地址，例如 Levenshtein
  • 调整 Levenshtein 算法的参数（例如，您希望在较长的字符串上允许更多差异）
  • 最后手动检查字符串

当然，保持数据“正常”的解决方案是在数据库中为每个特征设置明确的字段。否则，您最终将每隔几个月进行一次此练习。

于 2010-07-08T08:08:53.567 回答
2

我在这里看到的主要问题是准确定义平等。即使有人写乔恩。和另一个琼斯。- 你永远无法说它们是否相同。(Jon-Jonethan,Joneson,Jonedoe 随便 ;)

我在一家公司工作，我们必须准确地处理这个问题——恐怕我不得不告诉你，这种检查导航系统地址列表的方式大部分时间都是“手工”完成的。缩写有时取决于上下文，还有其他一些事情使这变得困难。Ofc 替换字符串等是用 python 完成的 - 但会告诉你这样一个缩写的含义。在少数情况下只能通过脚本完成。（“St.” -> 可以是“Saint”和“Street”。如何决定？不可能……这是人类的工作。）。

另一个大问题是，正如你所说的“有一条街“DJones”还是一个人？或两者兼而有之？哪一个是这里的？这个DJones是和Dr Jones一样还是和Don Jones一样？不可能决定！

您可以使用此处另一个答案提供的列表进行一些工作 - 但它会给您足够的“误报”左右。

于 2010-07-08T09:18:11.280 回答
2

你有一个邮政编码字段！！！

那么，您为什么不为您的国家/地区购买一个邮政编码表，然后用它来清理您的街道/城镇/地区/省信息？

于 2010-07-08T09:47:07.440 回答
2

我在上个世纪做了一个这样的项目。基本上，这是合并后两个客户文件的合并，涉及来自三个不同来源的名称和地址。

首先，正如许多海报所建议的那样，将所有常见的单词、缩写和拼写错误转换为常见的形式“Apt”。“Apatment”等到“Apt”。

然后查看姓名并确定名字的第一个字母，加上第一个姓氏。（考虑“医学博士。亨利·德·巴斯克维尔·斯迈思爵士”并不那么容易）但不要担心哪里有歧义，两者兼而有之！所以如果你幸运的话，你会得到 HBASKERVILLE 和 HSMYTHE。现在去掉所有的元音，因为这是大多数拼写变化发生的地方，所以现在你有了 HBSKRVLL HSMTH。

您还可以从“H. Baskerville”、“Sir Henry Baskerville Smith”和不幸的是“Harold Smith”中获得这些字符串，但我们在这里讨论的是模糊匹配！

在街道、公寓和邮政编码字段中执行类似的练习。但不要丢弃原始数据！

您现在来到有趣的地方，首先比较每个原始字符串，并为每个完全匹配的字符串打 50 分。然后检查你的“标准化”字符串，并为每个完全匹配的字符串给出 20 分。然后遍历所有字符串，并为它们共有的每个四个字符或更多子字符串打 5 分。对于比较的每一对，您最终会得到一些分数 > 150 的分数，您可以将其视为某个匹配，一些分数小于 50 的分数您可以认为不匹配，而介于两者之间的一些分数具有一定的匹配概率。

您需要进行更多调整以通过添加各种规则来改进这一点，例如“减去 20 分的姓氏 'smith'”。您确实必须继续运行和调整，直到您对结果匹配感到满意，但是，一旦您查看结果，您就会很好地感觉到哪个分数可以考虑为“匹配”，哪些是您需要摆脱的误报的。

于 2010-07-08T10:36:13.277 回答
1

我认为数据量可能会影响哪种方法最适合您。从与不同艺术家的合辑中索引音乐时，
我遇到了类似的问题。有时是艺术家在前，有时是歌曲名，有各种分隔符样式。

我所做的是计算具有相同值的其他条目的出现次数，以便有根据地猜测它是歌曲名称还是艺术家。

也许您可以使用soundex或类似的算法来查找类似的东西。

编辑：（也许我应该澄清一下，我认为艺术家姓名比歌曲名称更容易出现。）

于 2010-07-08T09:16:57.423 回答
1

您在评论中提到的一件重要的事情是您将以交互方式执行此操作。

这允许解析用户输入，同时验证对任何缩写的猜测并纠正许多错误（例如电话号码输入的方​​式适用于某些联系人管理系统 - 系统尽最大努力解析和纠正国家代码、区号和号码，但最终会向用户展示猜测并有机会更正输入）

如果你想做得很好，那么保留邮政编码、城镇、街道、缩写及其变体的数据库/字典可以改进数据验证和预处理。

所以，至少你会有完全合格的地址。如果您可以对所有输入执行此操作，您将对所有数据进行分类，然后可以在某些字段上严格匹配，对其他字段不那么严格，匹配分数根据您分配的权重计算。

在您始终如一地对输入进行预处理之后，n-gram 应该能够找到相似的地址。

于 2010-07-08T13:07:11.097 回答
1

您是否为此查看过 SQL Server 集成服务？模糊查找组件允许您查找“接近匹配”：http: //msdn.microsoft.com/en-us/library/ms137786.aspx

对于新输入，您可以从 .Net 代码调用包，将要检查的值行作为一组参数传递，但您可能需要保留令牌索引，以使其足够快以进行用户交互。

这里有一个地址匹配的例子：http: //msdn.microsoft.com/en-us/magazine/cc163731.aspx

于 2010-07-13T12:51:30.077 回答
1

我假设响应时间并不重要，问题是在数据库中查找现有地址，而不是合并重复项。我还假设数据库包含大量地址（例如 300 万个），而不是可以手动或通过Amazon 的 Mechanical Turk经济地清理的数字。

预计算——识别信息含量高的地址片段。

  1. 识别每个数据库字段中使用的所有唯一词并计算它们的出现次数。
  2. 消除非常常见的单词和缩写。（街道、街道、appt、apt 等）

当出现输入地址时，

  1. 识别最独特的单词并搜索（Street LIKE '%Jones%'）以查找包含这些单词的现有地址。
  2. 使用预先计算的统计信息来估计结果集中将有多少地址
  3. 如果估计的结果集太大，则选择第二个最独特的词并将其组合在搜索中（Street LIKE '%Jones%' AND Town LIKE '%Anytown%'）
  4. 如果估计的结果集太小，请选择第二个最独特的单词并将其组合在搜索中（Street LIKE '%Aardvark%' OR Town LIKE '%Anytown'）
  5. 如果实际结果集太大/太小，请像以前一样重复查询添加更多术语。

这个想法是在地址中找到足够多的信息含量高的片段，这些片段可以被搜索以给出合理数量的替代方案，而不是找到最佳匹配。为了更好地容忍拼写错误，可以使用 trigrams、tetra-grams 或 soundex 代码来代替单词。

显然，如果您有实际州/城镇/街道的列表，则可以在数据库和搜索地址中进行一些数据清理。（我很惊讶亚美尼亚邮政服务没有提供这样的清单，但我知道一些邮政服务对这些信息收取过高的费用。）

实际上，我在使用中看到的大多数系统都尽可能通过电话号码查找人们的帐户：显然，这是否是一个实用的解决方案取决于数据的性质及其准确性。

（还要考虑横向思维的方法：您能找到一家邮购邮件列表代理公司来为您清理数据库吗？他们甚至可能愿意为使用地址向您付费。）

于 2010-07-13T21:24:21.950 回答
1

我发现了一篇很棒的文章。

添加一些 dll 作为sql 用户定义函数，我们可以使用SimMetrics库使用字符串比较算法。

核实

http://anastasiosyal.com/archive/2009/01/11/18.aspx

于 2010-07-14T07:28:11.900 回答
0

这种变化的可能性是无数的，即使存在这样的算法，它也永远不会是万无一失的。毕竟你不能有名词拼写检查器。您可以做的是提供以前输入的字段值的下拉列表，以便他们可以选择一个，如果特定名称已经存在。最好为每个值（例如公寓等）设置单独的字段。

于 2010-07-08T07:18:27.087 回答
0

你可以把所有地址扔到像谷歌地图这样的网络服务上（不过我不知道这个是否合适），看看它们是否提供相同的 GPS 坐标。

于 2010-07-08T09:05:11.427 回答
0

一种可能性是在数据库中有一个字典表，将所有变体映射到单词的“正确”版本：

*Value* | *Meaning*
Apt.    | Apartment
Ap.     | Apartment
St.     | Street

然后在比较之前通过字典运行每个单词。

编辑：仅此一项就太天真了，不实用（见评论）。

于 2010-07-08T09:12:10.333 回答
0

另一个想法是使用学习。例如，您可以了解每个缩写词及其在句子中的位置，缩写词的含义。

3 Jane Dr. -> Dr (in 3rd position (or last)) means Drive
Dr. Jones St -> Dr (in 1st position) means Doctor

例如，您可以使用决策树并让用户训练系统。可能每个使用的几个例子就足够了。您不会对可能是 David Jones 或 Dr. Jones 的 D.Jones 等单字母缩写进行分类。但是在第一级翻译之后，您可以查找该镇的街道索引，看看您是否可以将 D. 扩展为街道名称。

同样，您将在存储之前通过决策树运行每个地址。

感觉应该有一些商业产品可以做到这一点。

于 2010-07-08T09:48:16.607 回答
0

一种方法是将Levenshtein 距离算法应用于地址字段。这将允许您比较字符串的相似性。

编辑 查看您正在处理的地址差异类型后，这可能没有帮助。

于 2010-07-08T09:58:00.380 回答