단일 목록 내에서 일치하는 대략적인 문자열 - r

Question

긴 목록에있는 수천 개의 이름의 데이터 프레임에 목록이 있습니다. 많은 사람들이 약간 다른 점이있어 이름이 약간 다릅니다. 나는이 이름들을 일치시킬 방법을 찾고 싶다. 예를 들어 :

names <- c('jon smith','jon, smith','Jon Smith','jon smith et al','bob seger','bob, seger','bobby seger','bob seger jr.') 

나는 stringdist 기능에 amatch뿐만 아니라 agrep을 검토 한 결과,하지만이 모두에 대한 이름의 또 다른 목록과 일치하는 데 사용되는 master list of names을 필요로한다. 필자의 경우에는 그러한 마스터리스트가 없기 때문에 매우 비슷한 패턴을 가진 이름을 식별하여 데이터에서 하나를 만들려고합니다. 그래서 나는 그것들을보고 그들이 동일한 사람인지를 결정할 수 있습니다 (많은 사람들이 그들이있는 경우). 필자는 이들이 가능성있는 일치인지, 그리고 Levenshtein 거리 또는 무언가에 기초한 일종의 유사성 스코어인지 알 수 있도록 도와주는 새로운 칼럼의 결과를 원합니다. 아마도 다음과 같은 것일 수 있습니다 :

  names match  SimilarityScore 
1  jon smith  a    9 
2  jon, smith  a    8 
3  Jon Smith  a    9 
4 jon smith et al  a    5 
5  bob seger  b    9 
6  bob, seger  b    8 
7  bobby seger  b    7 
8 bob seger jr.  b    5 

이게 뭔가요?

Answer 1

게시물에 대한 그림 찾기 here 나는 계층 적 텍스트 클러스터링이 내가 원하는 것을 할 것이라는 것을 발견했다. (이 경우 세) 올바른 클러스터의 수를 선택하는 경우

names <- c('jon smith','jon, smith','Jon Smith','jon smith et al','bob seger','bob, seger','bobby seger','bob seger jr.','jake','jakey','jack','jakeyfied') 

# Levenshtein Distance 
e <- adist(names) 
rownames(e) <- names 
hc <- hclust(as.dist(e)) 
plot(hc) 
rect.hclust(hc,k=3) #the k value provides the number of clusters 
df <- data.frame(names,cutree(hc,k=3)) 

이 출력은 정말 좋아 보인다 :

     names    cutree.hc..k...3. 
jon smith    jon smith     1 
jon, smith   jon, smith     1 
Jon Smith    Jon Smith     1 
jon smith et al jon smith et al     1 
bob seger    bob seger     2 
bob, seger   bob, seger     2 
bobby seger   bobby seger     2 
bob seger jr.  bob seger jr.     2 
jake      jake     3 
jakey      jakey     3 
jack      jack     3 
jakeyfied    jakeyfied     3 

그러나, 이름이 자주 이것보다 더 복잡, 그리고 몇 가지 더를 추가 한 후

names <- c('jon smith','jon, smith','Jon Smith','jon smith et al','bob seger','bob, seger','bobby seger','bob seger jr.','jake','jakey','jack','jakeyfied','1234 ranch','5678 ranch','9983','7777') 

d <- adist(names) 
rownames(d) <- names 
hc <- hclust(as.dist(d)) 
plot(hc) 
rect.hclust(hc,k=6) 

: 어려운 이름, 나는 기본 adist 옵션은 최적의 클러스터링을 포기하지 않았다 발견

대체 값을 2로 늘리고 삽입 및 삭제 비용을 1로 유지하고 대소 문자를 무시함으로써이 문제를 개선 할 수있었습니다.내가 더 잘 예 : "목장 같은 일반적인 용어를 제거하여 클러스터링을 조정

d <- adist(names,ignore.case=TRUE, costs=c(i=1,d=1,s=2)) #i=insertion, d=deletion s=substitution 
rownames(d) <- names 
hc <- hclust(as.dist(d)) 
plot(hc) 
rect.hclust(hc,k=6 

: 이것은 내가 그룹화 싶지 않았다 완전히 다른 네 개의 문자 숫자 문자열의 잘못된 그룹화를 최소화하는 데 도움이 "와"등의 "grep 패키지의 gsub 도구를 사용하여 하나의 클러스터의 수를 증가 :

names<-gsub("ranch","",names) 
names<-gsub("et al","",names) 
d <- adist(names,ignore.case=TRUE, costs=c(i=1,d=1,s=2)) 
rownames(d) <- names 
hc <- hclust(as.dist(d)) 
plot(hc) 
rect.hclust(hc,k=7) 

를

수작업으로 숫자를 선택하는 대신 데이터 수가 가장 많은 클러스터를 정렬 할 수있는 방법이 있지만 실제로는 시행 착오를 사용하는 것이 가장 쉬운 것으로 나타났습니다 (정보는 here about that approach 임).

Answer 2

로마에서 자연어 처리에 대한 의견을 제안하는 것이 가장 좋은 방법 일 것입니다. 그러나 접근 방식의 백 - 중 - 봉투 유형 당신은 아스키 코드의 관점에서 거리를 볼 수 있습니다 :

mynames = c("abcd efghijkl mn","zbcd efghijkl mn","bbcd efghijkl mn","erqe") 
asc <- function(x) { strtoi(charToRaw(x),16L) } 
namesToChar= sapply(mynames, asc) 
maxLength= max(unlist(lapply(namesToChar,length))) 
namesToChar =lapply(namesToChar, function(x) { c(x, rep(-1, times = maxLength-length(x))) }) 
namesToChar = do.call("rbind",namesToChar) 
dist(namesToChar,method="euclidean") 
dist(namesToChar,method="canberra") 

는 샘플에 대한 확인 충분히 번호를주고 보이지만,

> dist(namesToChar,method="manhattan") 
       abcd efghijkl mn zbcd efghijkl mn bbcd efghijkl mn 
zbcd efghijkl mn    25         
bbcd efghijkl mn    1    24     
erqe       257    274    256 

이 접근 방법은 원하는 것을 위해 dist 함수에 적절한 거리 메소드가없는 것처럼 보입니다. 엘리먼트 와이즈 바이너리 비교와 아마 더 표준 거리가 뒤 따른다. ('맨해튼'은 니즈에 가장 가까운 것 같다.) 당연히 직접 구현할 수 있습니다. 또한 -1을 채우는 것은 해킹입니다.이 경로를 선택하기로 한 경우 샘플의 평균 ASCII 코드로 바꿔야합니다.

전체 점수와 유사성 점수에 대해 서로 다른 단어에 대한 평균 거리를 역으로 취할 수 있습니다.