单个列表中的近似字符串匹配-r

Question

我在长列表中的数千个名称的数据框中有一个列表。许多名称之间的差异很小，因此略有不同。我想找到一种匹配这些名称的方法。例如：

names <- c('jon smith','jon, smith','Jon Smith','jon smith et al','bob seger','bob, seger','bobby seger','bob seger jr.')

我已经amatch在stringdist函数以及中进行了研究agrep，但是所有这些都需要一个主名称列表，用于与另一个名称列表进行匹配。就我而言，我没有这样的主列表，因此我想通过识别具有高度相似模式的姓名从数据中创建一个主列表，以便我可以查看它们并确定它们是否是同一个人（在很多情况下，的情况下）。我想要一个新列中的输出，可以帮助我知道这些是可能的匹配，也许是基于Levenshtein距离之类的某种相似性得分。也许是这样的：

            names   match      SimilarityScore
1       jon smith     a               9
2      jon, smith     a               8
3       Jon Smith     a               9
4 jon smith et al     a               5
5       bob seger     b               9
6      bob, seger     b               8
7     bobby seger     b               7
8   bob seger jr.     b               5

这样的事情可能吗？

Answer 1

利用在这里找到的帖子，我发现分层文本聚类将满足我的需求。

  names <- c('jon smith','jon, smith','Jon Smith','jon smith et al','bob seger','bob, seger','bobby seger','bob seger jr.','jake','jakey','jack','jakeyfied')

# Levenshtein Distance
e  <- adist(names)
rownames(e) <- names
hc <- hclust(as.dist(e))
plot(hc)
rect.hclust(hc,k=3) #the k value provides the number of clusters
df <- data.frame(names,cutree(hc,k=3))

如果选择正确数量的集群（在这种情况下为三个），则输出看起来非常好：

                       names             cutree.hc..k...3.
jon smith             jon smith                 1
jon, smith           jon, smith                 1
Jon Smith             Jon Smith                 1
jon smith et al jon smith et al                 1
bob seger             bob seger                 2
bob, seger           bob, seger                 2
bobby seger         bobby seger                 2
bob seger jr.     bob seger jr.                 2
jake                       jake                 3
jakey                     jakey                 3
jack                       jack                 3
jakeyfied             jakeyfied                 3

但是，名称通常比这更复杂，在添加了一些较难的名称之后，我发现默认adist选项无法提供最佳的聚类效果：

names <- c('jon smith','jon, smith','Jon Smith','jon smith et al','bob seger','bob, seger','bobby seger','bob seger jr.','jake','jakey','jack','jakeyfied','1234 ranch','5678 ranch','9983','7777')

d  <- adist(names)
rownames(d) <- names
hc <- hclust(as.dist(d))
plot(hc)
rect.hclust(hc,k=6)

通过将替换值的成本增加到2，而将插入和删除成本保持为1，而忽略大小写，我可以对此进行改进。这有助于将完全不同的四个字符数字字符串的错误分组减至最少，而我不想将其分组：

d  <- adist(names,ignore.case=TRUE, costs=c(i=1,d=1,s=2)) #i=insertion, d=deletion s=substitution
rownames(d) <- names
hc <- hclust(as.dist(d))
plot(hc)
rect.hclust(hc,k=6

我通过使用软件包中的gsub工具删除了诸如“ ranch”和“ et al”之类的常用术语，grep并将集群数增加了一个，从而进一步优化了集群：

names<-gsub("ranch","",names)
names<-gsub("et al","",names)
d  <- adist(names,ignore.case=TRUE, costs=c(i=1,d=1,s=2))
rownames(d) <- names
hc <- hclust(as.dist(d))
plot(hc)
rect.hclust(hc,k=7)

尽管有一些方法可以让数据整理出最佳的簇数，而不是手动尝试选择簇数，但我发现使用试验和错误是最容易的，尽管此处提供了有关该方法的信息。