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