[解決済み] 2つのデータセットからファジーマッチ文字列をマッチングするにはどうすればよいですか？

質問

会社名などの不完全な文字列に基づいて、2つのデータセットを結合する方法を考えています。以前は、名前と財務情報を持つリストと、名前と住所を持つリストという、非常に汚い2つのリストをマッチングさせる必要がありました。どちらも照合するためのユニークなIDを持っていませんでした。 すでにクリーニングが施されており、タイプミスや挿入があるかもしれないと仮定します。

今のところ、AGREPは私が見つけた中で最も近いツールで、使えるかもしれません。AGREPパッケージのlevenshtein距離は、2つの文字列間の削除、挿入、置換の数を測定するもので、使用できます。AGREPは距離が最も小さい（最も似ている）文字列を返します。

しかし、このコマンドを1つの値からデータフレーム全体に適用するのに苦労しています。私はAGREP関数を繰り返すために粗雑にforループを使用しましたが、より簡単な方法があるはずです。

以下のコードをご覧ください。

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 から b . もし1対1なら、上の3つの最も近いマッチを得ることができます。 多対一なら、6個になります。

1対1の場合（割り当てアルゴリズムが必要）。

以前これをやらなければならなかったとき、私は距離行列と割り当てヒューリスティック（以下、貪欲割り当てを使用）を使って割り当て問題として扱いました。 もし、最適解を求めるのであれば、次のような方法が良いでしょう。 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")