计算上下文相关的文本关联

好的 基线 可能是一个不切实际的,因为它的计算成本相对较高,更重要的是它产生了许多假阳性,将是通用的字符串距离算法,如

• Edit distance (又名Levenshtein距离)
• Ratcliff/Obershelp

取决于所需的精度水平(btw,应根据其 recall and precision 也就是说,通常表示遗漏相关性是否比错误识别相关性更重要, 一个基于以下启发式和思想的自主开发的过程可以做到这一点。 :

• 标记化输入,即将输入视为单词数组而不是字符串
• 标记化技术还应保留行号信息
• 使用常用替换的简短字典(例如,行尾的“dr”=“drive”,“jack”=“john”,“bill”=“william”…,“w.”等)规范输入,行首的“west”等。
• 识别(有点像标记,如在POS标记中)一些实体的性质(例如邮政编码、扩展邮政编码,以及城市
• 确定(查找)其中一些实体(例如,相对较短的数据库表可以包括目标区域中的所有城市/城镇)
• 确定(查找)一些与域相关的实体(如果所有/许多地址都与法律专业人士打交道,则查找律师事务所名称或联邦大楼可能会有所帮助。
• 通常,对来自地址最后一行的令牌施加更多的权重
• 对具有特定实体类型(例如:“Drive”、“Street”、“Court”)的代币施加更多(或更少)的权重,其权重应远小于前面的代币。
• 考虑修改 SOUNDEX 帮助规范化的算法

基于上述考虑,实施 基于规则的评价者 . 暂时,规则可以作为树/数组结构的访问者来实现,在这种结构中,输入最初被解析。( Visitor design pattern )
基于规则的框架的优点是,每个启发式算法都有自己的功能,并且规则可以被优先化,即在链的早期放置一些规则,允许通过一些强大的启发式(例如:不同的城市=>相关度=0,置信度=95%等)提前中止评估。

寻找相关性的一个重要考虑因素是 需要 先验的 将每个项目(此处地址)与其他项目进行比较 ,因此需要 1/2 n^2 项目级别比较。因此,以预先处理(解析、规范化…)的方式存储引用项,以及可能具有 摘要/排序键 这可以用作可能相关性的[非常粗糙]指示器(例如,由5位邮政编码组成的键,后跟“primary”名称的soundex值)。

我将考虑生成一个相似性比较度量,在给定两个对象(可能是字符串)的情况下,返回它们之间的“距离”。

如果您满足以下标准,那么它将有助于:

1. 物体与 本身是零。(自反)
2. 从A到B的距离在 双向(可传递)
3. 从A到C的距离不远 比从A到B的距离加上 从A到C的距离(三角形 规则

如果您的度量符合这些要求,那么您可以将对象安排在度量空间中,这意味着您可以运行以下查询:

• 哪个物体最像 这一个
• 给我5件物品 最喜欢这个。

有一本关于它的好书 here . 一旦为托管对象和运行查询设置了基础结构,您就可以简单地插入不同的比较算法,比较它们的性能,然后对它们进行优化。

我在大学为地理数据做了这个,尝试调整比较算法是很有趣的。

我相信你可以想出一些更高级的方法,但是你可以从一些简单的方法开始,比如把地址行减少到每个单词的数字和第一个字母,然后用最长的公共子序列算法比较结果。

希望在某种程度上有所帮助。

你可以用 Levenshtein edit distance 查找只有几个字符不同的字符串。 BK Trees 有助于加快匹配过程。

免责声明: 我不知道有什么算法能做到这一点,但如果它存在的话,我真的很想知道它。这个答案是一个天真的尝试,试图解决这个问题,没有任何先前的知识。欢迎评论,请不要笑得太好。

如果您尝试手工操作,我建议您对字符串应用某种“规范化”:小写、删除标点符号,或者用完整的单词(dr.=>drive、st=>street等)替换常见的缩写。

然后,您可以尝试比较两个字符串之间的不同对齐方式,并通过平均相应字母之间的绝对差异(例如A=1、B=2等)来计算相关性。和 corr(a, b) = |a - b| = 1 ):

west lawnmover drive
   w lawnmower street

因此,即使某些字母不同,相关性也会很高。然后,只需保持找到的最大相关性,并确定如果相关性高于给定阈值,它们是相同的。

早在90年代初,当我不得不修改一个专用程序时,它在多个模块中花费了数千行代码,这些代码是经过多年积累的。现代机器学习技术应该使学习更容易,也许你不需要表现得很好(这是我雇主的面包和黄油)。

所以如果你说的是合并实际邮寄地址的列表,如果可以的话,我会通过外包来实现。

USPS进行了一些测试来衡量地址标准化计划的质量。我不记得这是如何工作的,但是你可以检查他们是否仍然这样做——也许你可以得到一些好的培训数据。