如何在两个数据集中模糊匹配字符串？

Question

如何在两个数据集中模糊匹配字符串？

rstring-matchingfuzzy-searchfuzzy-comparison

42

我一直在研究一种方法，可以基于一个不完整的字符串（比如公司名称）来合并两个数据集。过去，我不得不匹配两个非常混乱的列表，一个列表包含名称和财务信息，另一个列表包含名称和地址。两个列表都没有唯一的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))
}

- A L

7

根据大家的反馈和我的一些探索，我创建了一个函数来解决我的确切问题。代码可以在这里找到：https://github.com/Adamishere/Fuzzymatching/blob/master/Fuzzy%20String%20Match%20FunctionV1.R - A L

谢谢这个函数。它非常有用。但是我无法将我的列传递给string1、string2和id2。我的数据在data.table中，所以不确定在调用函数时应该如何传递它们。请问您能否提供建议？如果我的问题太基础，请见谅，我刚开始学习R，还有很长的路要走。 - user1412

我会使用data.frame()，然后一旦匹配完成，再转换为data.table()。 - A L

1

模糊连接包(fuzzyjoin package)可能会有所帮助 - 请参见下面的答案，使用fuzzyjoin::stringdist_left_join。 - Arthur Yip

如果不仅仅是一个变量数据框，这个函数如何工作？在我的情况下，当我有两个具有多个列的数据框时，它无法正常工作。 - jvalenti

7个回答

25

解决方案取决于您匹配 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")

- C8H10N4O2

谢谢！这非常有帮助。虽然我很好奇，在多对一的情况下，结果似乎不正确，因为它们在第一行之后没有返回最佳匹配项。 - A L

@Adam Lee，这取决于您如何定义“最佳”匹配。请参阅?stringdist或?adist以了解有关默认距离度量的更多信息。使用这些函数中的任何一个和默认参数，“Bayes”与“asdf”的编辑距离比它与“Bayes Inc.”的编辑距离更近一步。 - C8H10N4O2

啊，我明白了！谢谢你，所以这是由于使用的距离度量引起的问题。再次感谢你的帮助！ - A L

@C8H10N4O2，我正在寻求一些关于如何从第二个数据集中获取与匹配的特定等效列相对应的数据的建议。我已经在以下网址发布了这个问题 - http://stackoverflow.com/questions/42749447/r-fuzzy-string-match-to-return-specific-column-based-on-matched-string 如果您能提供一些帮助，那将是非常有益的。 - user1412

1

这非常有帮助 - 谢谢。我发现如果在调用greedyAssign函数之前对d $ dist进行过滤（例如d <- d[d$dist < 0.2,]），则可扩展到更大程度。在对样本运行上述代码（无过滤器）后，通常可以选择一个粗略的截止点，超过该点，建议匹配可能无效。 - Mike Honey

@C8H10N4O2 在 expand.grid() 中，我需要将我的 ID 列与模糊匹配（a_name）和 b 的 ID 以及 b_name 一起保留。这里是否可能？我会非常感激。 - pyeR_biz

3

我不确定这对你有没有用，John Andrews，但它提供了另一个工具（来自RecordLinkage包），可能会有所帮助。

install.packages("ipred")
install.packages("evd")
install.packages("RSQLite")
install.packages("ff")
install.packages("ffbase")
install.packages("ada")
install.packages("~/RecordLinkage_0.4-1.tar.gz", repos = NULL, type = "source")

require(RecordLinkage) # it is not on CRAN so you must load source from Github, and there are 7 dependent packages, as per above

compareJW <- function(string, vec, cutoff) {
  require(RecordLinkage)
  jarowinkler(string, vec) > cutoff
}

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))
a$name <- as.character(a$name)
b$name <- as.character(b$name)

test <- compareJW(string = a$name, vec = b$name, cutoff = 0.8)  # pick your level of cutoff, of course
data.frame(name = a$name, price = a$price, test = test)

> data.frame(name = a$name, price = a$price, test = test)
    name price  test
1 Ace Co    10  TRUE
2  Bayes    13  TRUE
3    asd     2  TRUE
4    Bcy     1 FALSE
5   Baes    15  TRUE
6   Bays     1 FALSE

- lawyeR

RecordLinkage在2015年重新上架了CRAN：https://cran.r-project.org/web/packages/RecordLinkage/index.html - Kayle Sawyer

3

模糊匹配

近似字符串匹配是将一个字符串近似地匹配到另一个字符串。例如：banana和bananas。
模糊匹配是在一个字符串中查找近似的模式。例如：在字符串“bananas in pyjamas”中查找模式“banana”。

	方法	R 实现
基本	Bitap≈Levenshtein	`b$name <- lapply(b$name, agrep, a$name, value=TRUE); merge(a,b)`
高级	`?stringdist::stringdist-metrics`	`fuzzyjoin::stringdist_join(a, b, mode='full', by=c('name'), method='lv')`
模糊匹配	TRE	`agrep2 <- function(pattern, x) x[which.min(adist(pattern, x, partial=TRUE))]; b$name <- lapply(b$name, agrep2, a$name); merge(a, b)`

Run yourself

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

# Basic
c <- b
c$name.b <- c$name
c$name <- lapply(c$name, agrep, a$name, value=TRUE)
merge(a, c, all.x=TRUE)

# Advanced
fuzzyjoin::stringdist_join(a, b, mode='full')

# Fuzzy Match
c <- b
c$name.b <- c$name
c$name <- lapply(c$name, function(pattern, x) x[which.min(adist(pattern, x, partial=TRUE))], a$name)
merge(a, c)

- A. West

2

在这种情况下，我使用lapply：

yournewvector: lapply(yourvector$yourvariable, agrep, yourothervector$yourothervariable, max.distance=0.01),

然后将其写成CSV格式并不那么简单：

write.csv(matrix(yournewvector, ncol=1), file="yournewvector.csv", row.names=FALSE)

- user3909910

1

Agreed with above answer "Not familiar with AGREP but here's example using stringdist for your distance matrix." but adding the signature function as below from Merging Data Sets Based on Partially Matched Data Elements will be more accurate since the calculation of LV is based on position/addition/deletion.

##Here's where the algorithm starts...
##I'm going to generate a signature from country names to reduce some of the minor differences between strings
##In this case, convert all characters to lower case, sort the words alphabetically, and then concatenate them with no spaces.
##So for example, United Kingdom would become kingdomunited
##We might also remove stopwords such as 'the' and 'of'.
signature=function(x){
  sig=paste(sort(unlist(strsplit(tolower(x)," "))),collapse='')
  return(sig)
}

- YummyLin Yang

-1

以下是我用来获取公司在列表中出现次数的方法，尽管公司名称不完全匹配：

步骤1 安装音码包

步骤2 在“mylistofcompanynames”中创建一个名为“soundexcodes”的新列

步骤3 使用音码函数返回“soundexcodes”中公司名称的音码代码

步骤4 将公司名称和相应的音码代码复制到一个新文件中（称为“companysoundexcodestrainingfile”），其中有两列称为“companynames”和“soundexcode”

步骤5 从“companysoundexcodestrainingfile”中删除音码代码的重复项

步骤6 浏览剩余公司名称的列表，并根据您想要在原始公司中显示的方式更改名称

例如： Amazon Inc A625 可以变成 Amazon A625 Accenture Limited A455 可以变成 Accenture A455

步骤6 在companysoundexcodestrainingfile$soundexcodes和mylistofcompanynames$soundexcodes之间执行一个left_join或（简单的vlookup），通过“soundexcodes”进行匹配。

步骤7 结果应该有原始列表和一个名为“co.y”的新列，其中包含在训练文件中保留的公司名称。

步骤8 对“co.y”进行排序并检查大部分公司名称是否正确匹配。如果是，则用vlookup的声学代码给出的新名称替换旧的公司名称。

- Nikhil Muthukrishnan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Arthur Yip · Accepted Answer

这里提供了一个使用fuzzyjoin包的解决方案。它使用类似于dplyr的语法，以及可能的模糊匹配类型之一stringdist。

正如@C8H10N4O2所建议的那样，stringdist方法="jw"可以为您的示例创建最佳匹配。

正如fuzzyjoin的开发者@dgrtwo所建议的那样，我使用了一个大的max_dist，然后使用dplyr::group_by和dplyr::slice_min来仅获取具有最小距离的最佳匹配。（slice_min替换了旧的top_n，如果原始顺序很重要且不是字母顺序，请使用mutate(rank = row_number(dist)) %>% filter(rank == 1)）

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) %>%
  slice_min(order_by = dist, n = 1)

#> # 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