Как я могу сопоставить строки нечеткого соответствия из двух наборов данных?

Question

Я работаю над тем, чтобы присоединиться к двум наборам данных на основе несовершенной строки, например, имени компании. Раньше мне приходилось сопоставлять два очень грязных списка, один список имел имена и финансовую информацию, другой список - имена и адреса. Также не было уникальных идентификаторов! ПРИНИМАЙТЕ, ЧТО ЧИСТКА УЖЕ ПРИМЕНЯЕТСЯ И МОЖЕТ БЫТЬ ТИПО И ВСТАВКИ.

До сих пор AGREP является ближайшим инструментом, который я нашел, что может работать. Я могу использовать расстояния levenshtein в пакете AGREP, которые измеряют количество удалений, вставок и замен между двумя строками. 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

Я не уверен, что это полезное направление для вас, Джон Эндрюс, но оно дает вам еще один инструмент (из пакета 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 

Answer 3

Согласовано над ответом "не знакомы с AGREP, но вот пример использования stringdist для матрицы расстояний. ", но добавление функции подписи, как показано ниже от Merging Data Sets Based on Partially Matched Data Elements будет более точным, поскольку расчет LV основан на 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) 
} 

Answer 4

Я использую 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) 

Answer 5

Вот решение, использующее пакет fuzzyjoin. Он использует dplyr-подобный синтаксис и stringdist как один из возможных типов нечеткого соответствия.

Как suggested от C8H10N4O2, метод stringdist method = "jw" создает наилучшие соответствия для вашего примера.

Как suggested по dgrtwo, разработчик fuzzyjoin, я использовал большую 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 

Answer 6

Вот что я использовал для получения сколько раз компания появляется в списке, хотя названия компаний являются неточными матчи,

Шаг 1. Установите фонетических пакет

step.2 создать новый столбец под названием «звуковые коды» в «mylistofcompanynames»

step.3 Используйте функцию Саундэкс вернуть SOUNDEX коды названий компаний в «soundexcodes»

Шаг 4. Копирование названия компании и соответствующий код SOUNDEX в новый файл (2 колонки под названием «companynames» и "soundexcode") под названием "companysoundexcodestrainingfile"

step.5 Удалить дубликаты soundexcodes в "companysoundexcodestrainingfile"

step.6 Пройдите список оставшихся с Имена и п е к т изменить имена, как вы хотите, чтобы появиться в оригинальной компании

пример: Amazon Inc A625 может быть Amazon A625 Accenture Limited A455 может быть Accenture A455

step.6 Выполните left_join или (простой ВПР) между companysoundexcodestrainingfile $ soundexcodes и mylistofcompanynames $ soundexcodes на "soundexcodes"

step.7 Результат должен иметь исходный список с новым столбцом под названием «co.y», который имеет название компании так, как вы его оставили в учебном файле.

step.8 Сортировка «co.y» и проверьте правильность соответствия большинства имен компаний, заменив старые названия компаний новыми, указанными vlookup кода soundex.