如何匹配来自两个数据集的模糊匹配字符串？

Question

我一直在研究一种基于不完美字符串连接两个数据集的方法,例如公司名称.在过去,我必须匹配两个非常脏的列表,一个列表有名称和财务信息,另一个列表有名称和地址.没有唯一的ID匹配!假设清洁已经应用,并且可能有类型和插入.

到目前为止,AGREP是我发现的最接近的工具.我可以在AGREP包中使用levenshtein距离,它测量两个字符串之间的删除,插入和替换的数量.AGREP将返回距离最小的字符串(最相似).

但是,我一直无法从单个值转换此命令以将其应用于整个数据帧.我粗略地使用了for循环来重复AGREP函数,但是必须有一个更简单的方法.

请参阅以下代码:

a<-data.frame(name=c('Ace Co','Bayes', 'asd', 'Bcy', 'Baes', 'Bays'),price=c(10,13,2,1,15,1))
b<-data.frame(name=c('Ace Co.','Bayes Inc.','asdf'),qty=c(9,99,10))

for (i in 1:6){
    a$x[i] = agrep(a$name[i], b$name, value = TRUE, max = list(del = 0.2, ins = 0.3, sub = 0.4))
    a$Y[i] = agrep(a$name[i], b$name, value = FALSE, max = list(del = 0.2, ins = 0.3, sub = 0.4))
}

Answer 1

该解决方案取决于您的匹配的期望基数a来b.如果它是一对一的,你将得到上面三个最接近的匹配.如果它是多对一的,你会得到六个.

一对一案例(需要分配算法):

当我把它作为带有距离矩阵和赋值启发式(下面使用的贪婪赋值)的赋值问题处理之前我必须这样做.如果你想要一个"最佳"的解决方案,你会更好optim.

不熟悉AGREP,但这里是stringdist用于距离矩阵的示例.

library(stringdist)
d <- expand.grid(a$name,b$name) # Distance matrix in long form
names(d) <- c("a_name","b_name")
d$dist <- stringdist(d$a_name,d$b_name, method="jw") # String edit distance (use your favorite function here)

# Greedy assignment heuristic (Your favorite heuristic here)
greedyAssign <- function(a,b,d){
  x <- numeric(length(a)) # assgn variable: 0 for unassigned but assignable, 
  # 1 for already assigned, -1 for unassigned and unassignable
  while(any(x==0)){
    min_d <- min(d[x==0]) # identify closest pair, arbitrarily selecting 1st if multiple pairs
    a_sel <- a[d==min_d & x==0][1] 
    b_sel <- b[d==min_d & a == a_sel & x==0][1] 
    x[a==a_sel & b == b_sel] <- 1
    x[x==0 & (a==a_sel|b==b_sel)] <- -1
  }
  cbind(a=a[x==1],b=b[x==1],d=d[x==1])
}
data.frame(greedyAssign(as.character(d$a_name),as.character(d$b_name),d$dist))

产生作业:

       a          b       d
1 Ace Co    Ace Co. 0.04762
2  Bayes Bayes Inc. 0.16667
3    asd       asdf 0.08333

我确信有一个更优雅的方式来做贪婪的任务启发式,但上面的工作对我来说.

多对一案例(不是分配问题):

do.call(rbind, unname(by(d, d$a_name, function(x) x[x$dist == min(x$dist),])))

产生结果:

   a_name     b_name    dist
1  Ace Co    Ace Co. 0.04762
11   Baes Bayes Inc. 0.20000
8   Bayes Bayes Inc. 0.16667
12   Bays Bayes Inc. 0.20000
10    Bcy Bayes Inc. 0.37778
15    asd       asdf 0.08333

编辑:用于method="jw"产生所需的结果.看到help("stringdist-package")

Answer 2

这是使用该fuzzyjoin包的解决方案.它使用类似dplyr语法并stringdist作为模糊匹配的可能类型之一.

根据C8H10N4O2的建议,stringdistmethod ="jw"为您的示例创建最佳匹配.

正如模糊连接的开发者dgrtwo 所建议的那样,我使用了一个大的max_dist,然后使用dplyr::group_by并dplyr::top_n获得最小距离的最佳匹配.

a <- data.frame(name = c('Ace Co', 'Bayes', 'asd', 'Bcy', 'Baes', 'Bays'),
                price = c(10, 13, 2, 1, 15, 1))
b <- data.frame(name = c('Ace Co.', 'Bayes Inc.', 'asdf'),
                qty = c(9, 99, 10))

library(fuzzyjoin); library(dplyr);

stringdist_join(a, b, 
                by = "name",
                mode = "left",
                ignore_case = FALSE, 
                method = "jw", 
                max_dist = 99, 
                distance_col = "dist") %>%
  group_by(name.x) %>%
  top_n(1, -dist)

#> # A tibble: 6 x 5
#> # Groups:   name.x [6]
#>   name.x price     name.y   qty       dist
#>   <fctr> <dbl>     <fctr> <dbl>      <dbl>
#> 1 Ace Co    10    Ace Co.     9 0.04761905
#> 2  Bayes    13 Bayes Inc.    99 0.16666667
#> 3    asd     2       asdf    10 0.08333333
#> 4    Bcy     1 Bayes Inc.    99 0.37777778
#> 5   Baes    15 Bayes Inc.    99 0.20000000
#> 6   Bays     1 Bayes Inc.    99 0.20000000