Поиск частичных совпадений со строками в R

Question

У меня есть очень большая база данных с именами, как это:

names <- c("William Gates", "Bill Gates", "Gates, William H. III", 
    "Gates, William III", "William H Gates", "William H. Gates", 
    "Carlos Slim Helu & family", "Carlos Slim Helu", 
    "Carlos Slim & Family", "Carlos Slim") 

, который я хотел бы «очистить» автоматически, как это:

new_names <- c("William Gates", "William Gates", "William Gates", 
    "William Gates", "William Gates", "William Gates", 
    "Carlos Slim Helu & family", "Carlos Slim Helu & family", 
    "Carlos Slim Helu & family", "Carlos Slim Helu & family") 

где я (произвольно) использовали первое вхождение имени для замены других его вариантов.

В этом примере names является символьным вектором длины 10. Я хотел бы создать матрицу «» с «частичными значениями соответствия». Эта матрица сохранит «меры» между 0 и 1 степени частичного совпадения. Например, сравнение names[1] с names[1] дает идеальное соответствие, поэтому значение будет 1; сравнение names[1] с names[2] даст что-то вроде 5/12 = 0,41667, что отражает тот факт, что Гейтс является общим для обеих строк и что (игнорируя пустые строки) names[1] имеет 12 букв; по той же логике, сравнение names[2] с names[1] даст что-то вроде 5/9 = 0,55556.

я бы, вероятно, игнорировать случаи (семья и семья будет идеальный матч) и сосредоточиться только на соответствие подстрок (но если кто-то комментарий о том, как соответствовать, скажем, тонкий и Сельма, это было бы отлично тоже.

В качестве второго шага я создам треугольную матрицу максимальных значений (в примере значение 5/9 = 0,55556). Затем я использовал бы эту матрицу для наблюдения за ситуацией и для выбора порога, такого как 0,95 выше которого строки заменяются, постепенно понижая пороговое значение, пока не почувствую, что данные были очищены.

Я ожидаю, что такого рода вещи были выполнены раньше и что кто-то сможет h elp меня начать. Я прочитал о пакете compare Пауля Мурелла и ожидаю, что это будет отличный инструмент для использования, но я не видел слишком много примеров, которые можно было бы легко адаптировать, поэтому, если вы знаете учебник или примеры, отличные от виньетирования пакета, пожалуйста, укажите мне их.

Я понимаю, что от хорошего вопроса ожидалось больше кода, и я приношу свои извинения за то, что не смог предоставить много. Хотя я достаточно хорошо знаком с R, я не отвечаю за строку. Если кто-то указывает мне на какое-то место, чтобы начать работу, я могу попытаться перефразировать мой вопрос некоторым примером кода.

Answer 1

Полного ответ, основанного на adist и кластеризации.

С аргументами partial=TRUE и ignore.case=TRUE, функция adist от основания R, кажется, работает с этой проблемой.Для длинной линии библиотека stringdist, которую указал Крис С., кажется перспективной, но может также работать с этим подходом.

Это решение использует кластеризацию с помощью hclust, применяя «» единственной связи метода, который принимает "друг друзей подхода подходит к этой проблеме.

Обратите внимание, что для этого требуется выбрать пороговое значение, основанное на высоте кластера (в данном случае накопленное обобщенное расстояние Левенштейна между именами , если смотреть по однонитевому критерию). Если кластеризация не слишком велика для вашей проблемы, то визуализация или проверка вывода hclust тоже не должно быть слишком плохо.

## renamed to avoid overwriting names() function 
    raw_names <- c("William Gates", "Bill Gates", "Gates, William H. III", 
     "Gates, William III", "William H Gates", "William H. Gates", 
     "Carlos Slim Helu & family", "Carlos Slim Helu", 
     "Carlos Slim & Family", "Carlos Slim") 

lev_dist <- adist(raw_names, raw_names, partial=TRUE, ignore.case=TRUE) 

#use single linkage method as it suits the problem 
hc <- hclust(as.dist(lev_dist), method='single') 

## cluster vis for picking threshold 
plot(hc, labels=raw_names) 
threshold <- 6 ## in terms of cluster height -- 

## based on threshold, get clusters and make labels 
cluster <- cutree(hc, h=threshold) 
cluster_labels <- sapply(unique(cluster), function(i) raw_names[min(which(cluster == i))]) 
(new_names <- cluster_labels[cluster]) 

## [1] "William Gates" "William Gates" "William Gates" 
## "Carlos Slim Helu & family" "Carlos Slim Helu & family" [6] 
## "William Gates" "William Gates" "William Gates" 
## "Carlos Slim Helu & family" "Carlos Slim Helu & family" 

Answer 2

Простейшая попытка. просто используя встроенную функцию и не создавая никакой матрицы, но, похоже, она работает на этом простом примере.

names <- c("William Gates", "Bill Gates", "Gates, William H. III", 
      "Gates, William III", "William H Gates", "William H. Gates", 
      "Carlos Slim Helu & family", "Carlos Slim Helu", 
      "Carlos Slim & Family", "Carlos Slim") 

new_names <- c("William Gates", "William Gates", "William Gates", 
       "William Gates", "William Gates", "William Gates", 
       "Carlos Slim Helu & family", "Carlos Slim Helu & family", 
       "Carlos Slim Helu & family", "Carlos Slim Helu & family") 

nn <- c('Bill Gates','Carlos Slim') 


cbind(names, sapply(nn, function(x) 
    ifelse(agrepl(x, names, max.distance = 5), x, NA))) 

#  names      Bill Gates Carlos Slim 
# [1,] "William Gates"    "Bill Gates" NA   
# [2,] "Bill Gates"    "Bill Gates" NA   
# [3,] "Gates, William H. III"  "Bill Gates" NA   
# [4,] "Gates, William III"  "Bill Gates" NA   
# [5,] "William H Gates"   "Bill Gates" NA   
# [6,] "William H. Gates"   "Bill Gates" NA   
# [7,] "Carlos Slim Helu & family" NA   "Carlos Slim" 
# [8,] "Carlos Slim Helu"   NA   "Carlos Slim" 
# [9,] "Carlos Slim & Family"  NA   "Carlos Slim" 
# [10,] "Carlos Slim"    NA   "Carlos Slim" 

редактировать

names <- c("William Gates", "Bill Gates", "Gates, William H. III", 
      "Gates, William III", "William H Gates", "William H. Gates", 
      "Carlos Slim Helu & family", "Carlos Slim Helu", 
      "Carlos Slim & Family", "Carlos Slim") 

names <- gsub('[[:punct:]]', '', names) 
nn <- sort(table(unlist(strsplit(names, ' ')))) 
nn <- names(nn[nn >= 4]) 

cbind(names, sapply(nn, function(x) 
    ifelse(agrepl(x, names, max.distance = 1), x, NA))) 

#  names      Carlos Slim William Gates 
# [1,] "William Gates"   NA  NA  "William" "Gates" 
# [2,] "Bill Gates"    NA  NA  NA  "Gates" 
# [3,] "Gates William H III"  NA  NA  "William" "Gates" 
# [4,] "Gates William III"  NA  NA  "William" "Gates" 
# [5,] "William H Gates"   NA  NA  "William" "Gates" 
# [6,] "William H Gates"   NA  NA  "William" "Gates" 
# [7,] "Carlos Slim Helu family" "Carlos" "Slim" NA  NA  
# [8,] "Carlos Slim Helu"   "Carlos" "Slim" NA  NA  
# [9,] "Carlos Slim Family"  "Carlos" "Slim" NA  NA  
# [10,] "Carlos Slim"    "Carlos" "Slim" NA  NA 

Answer 3

Пакет stringdist может помочь получить матрицу - это также описано в 2014 июня R journal. Обновление: один из методов qgram могут работать лучше для обоих последних, первых или первых, фамилий

library(stringdist) 
stringdistmatrix(names, names, "jaccard") 
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] 
[1,] 0.0000 0.273 0.286 0.167 0.0909 0.1667 0.632 0.562 0.647 0.571 
[2,] 0.2727 0.000 0.467 0.385 0.3333 0.3846 0.684 0.625 0.706 0.643 
[3,] 0.2857 0.467 0.000 0.143 0.2143 0.1429 0.636 0.579 0.714 0.667 
[4,] 0.1667 0.385 0.143 0.000 0.2308 0.2857 0.667 0.611 0.684 0.625 
[5,] 0.0909 0.333 0.214 0.231 0.0000 0.0833 0.579 0.500 0.667 0.600 
...