Как сопоставить строки нечетких совпадений из двух наборов данных?
Я работал над способом объединения двух наборов данных, основанных на несовершенной строке, такой как название компании. В прошлом мне приходилось сопоставлять два очень грязных списка, в одном списке были имена и финансовая информация, в другом списке были имена и адреса. Ни у одного не было уникальных идентификаторов, чтобы соответствовать! Предположим, что очистка уже была применена, и там могут быть TYPOS и вставки.
Пока что AGREP - самый близкий инструмент, который я нашел, который мог бы работать. Я могу использовать расстояния Левенштейна в пакете 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))
}
7 ответов
Решение зависит от желаемой мощности вашего соответствия 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")
Вот решение с использованием fuzzyjoin пакет. Оно использует dplyr-подобный синтаксис и stringdist как один из возможных типов нечеткого соответствия.
Как предложено C8H10N4O2, stringdist method="jw" создает лучшие совпадения для вашего примера.
Как предположил 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
Я не уверен, что это полезное направление для вас, Джон Эндрюс, но оно дает вам другой инструмент (из 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
Нечеткое соответствие
Приблизительное сопоставление строк - это приблизительное сопоставление одной строки с другой. например и
bananas.
Нечеткое соответствие - это поиск приблизительного шаблона в строке. например
banana в
bananas in pyjamas.
Беги сам
# 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)
Я использую 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)
Согласен с приведенным выше ответом "Не знаком с AGREP, но вот пример использования stringdist для вашей матрицы расстояний", но дополнительная функция сигнатуры, приведенная ниже в разделе " Объединение наборов данных на основе частично совпадающих элементов данных", будет более точной, поскольку расчет LV основан на на позиции / добавление / удаление
##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)
}
Вот то, что я использовал для получения количества раз, когда компания появляется в списке, хотя названия компаний не совпадают,
Шаг 1. Установите пакет фонетики
Шаг 2. Создайте новый столбец с именем "soundexcodes" в "mylistofcompanynames".
step.3 Используйте функцию soundex, чтобы вернуть soundex коды названий компаний в "soundexcodes"
Шаг 4. Скопируйте названия компаний И соответствующий код soundex в новый файл (2 столбца с именами "companynames" и "soundexcode") с именем "companysoundexcodestrainingfile"
Шаг 5. Удалите дубликаты soundexcodes в "companysoundexcodestrainingfile"
Шаг 6. Просмотрите список оставшихся названий компаний и измените названия так, как вы хотите, чтобы они отображались в исходной компании.
пример: Amazon Inc A625 может быть Amazon A625 Accenture Limited A455 может быть Accenture A455
Шаг 6. Выполните left_join или (простой vlookup) между compounysoundexcodestrainingfile$soundexcodes и mylistofcompanynames$soundexcodes с помощью "soundexcodes"
Шаг 7. Результат должен иметь исходный список с новым столбцом с именем "co.y", в котором указано название компании, как вы ее оставили в файле обучения.
Шаг 8. Сортируйте "co.y" и проверьте, правильно ли сопоставлены большинство названий компаний, если это так, замените старые названия компаний новыми, заданными vlookup кода soundex.