두 행 데이터 간의 유사성을 찾는 방법

Question

프로그래밍 방식으로 데이터 세트에서 거의 중복 된 데이터 중 하나를 제거하려고합니다. 내 데이터 세트는 논리적으로 아래 테이블과 같습니다. 데이터 세트에 두 개의 행이 있고 인간은이 두 데이터가 관련되어 있고 아마도 같은 사람이 추가했음을 쉽게 이해할 수 있습니다.

이 문제에 대한 내 솔루션은 별도 필드 (이름, 주소, 전화 번호)를 비교하고 자신의 유사성 비율을 찾기 위해 Levenshtein을 사용하고 있습니다. 그런 다음 평균 비율을 0.77873으로 계산합니다. 이 유사성 결과는 낮아 보인다. 내 파이썬 코드는

from Levenshtein import ratio 
name  = ratio("Game of ThOnes Books for selling","Selling Game of Thrones books") 
address = ratio("George Washington street","George Washington st.") 
phone = ratio("555-55-55","0(555)-55-55") 

total_ratio = name+address+phone 
print total_ratio/3 #Average ratio 

내 질문에 두 행의 데이터를 비교하는 가장 좋은 방법이 무엇처럼입니까? 이 작업을 수행하는 데 필요한 알고리즘 또는 방법은 무엇입니까?

Answer 1

행 사이의 거리 행렬을 계산하고 클러스터를 형성하고 비슷한 행의 후보로 클러스터 구성원 을 선택할 수 있습니다.

R 및 stringdistmatrix 기능을 stringdist에서 사용하면 문자열 입력 사이의 거리 계산이 가능합니다.

stringdist에서 지원하는 거리 메서드는 다음과 같습니다. 자세한 사항

#Method name; Description 
#osa ; Optimal string aligment, (restricted Damerau-Levenshtein distance). 
#lv ; Levenshtein distance (as in R's native adist). 
#dl ; Full Damerau-Levenshtein distance. 
#hamming ; Hamming distance (a and b must have same nr of characters). 
#lcs ; Longest common substring distance. 
#qgram ;q-gram distance. 
#cosine ; cosine distance between q-gram profiles 
#jaccard ; Jaccard distance between q-gram profiles 
#jw ; Jaro, or Jaro-Winker distance. 
#soundex ; Distance based on soundex encoding (see below) 

데이터에 대한 package manual :

library("stringdist") 

#have modified the data slightly to include dissimilar datapoints 
Date = c("07-Jan-17","06-Feb-17","03-Mar-17") 
name  = c("Game of ThOnes Books for selling","Selling Game of Thrones books","Harry Potter BlueRay") 
address = c("George Washington street","George Washington st.","Central Avenue") 
phone = c("555-55-55","0(555)-55-55","111-222-333") 
DF = data.frame(Date,name,address,phone,stringsAsFactors=FALSE) 

DF 
#  Date        name     address  phone 
#1 07-Jan-17 Game of ThOnes Books for selling George Washington street 555-55-55 
#2 06-Feb-17 Selling Game of Thrones books George Washington st. 0(555)-55-55 
#3 03-Mar-17    Harry Potter BlueRay   Central Avenue 111-222-333 

계층 클러스터링 :

rowLabels = sapply(DF[,"name"],function(x) paste0(head(unlist(strsplit(x," ")),2),collapse="_")) 

#create string distance matrix, hierarchical cluter object and corresponding plot 
nameDist = stringdistmatrix(DF[,"name"]) 
nameHC = hclust(nameDist) 

plot(nameHC,labels = rowLabels ,main="HC plot : name") 

addressDist = stringdistmatrix(DF[,"address"]) 
addressDistHC = hclust(addressDist) 

plot(addressDistHC ,labels = rowLabels, main="HC plot : address") 

phoneDist = stringdistmatrix(DF[,"phone"]) 
phoneHC = hclust(phoneDist) 

plot(phoneHC ,labels = rowLabels, main="HC plot : phone") 

유사 행 :

행이 지속적으로,이 데이터 집합에서 두 개의 클러스터를 형성하는 클러스터의 구성원이 우리가 할 수있는 식별

clusterDF = data.frame(sapply(DF[,-1],function(x) cutree(hclust(stringdistmatrix(x)),2))) 
clusterDF$rowSummary = rowSums(clusterDF) 

clusterDF 
# name address phone rowSummary 
#1 1  1  1   3 
#2 1  1  1   3 
#3 2  2  2   6 


#row frequency 

rowFreq = table(clusterDF$rowSummary) 
#3 6 
#2 1 

#we filter rows with frequency > 1 
similarRowValues = as.numeric(names(which(rowFreq>1))) 


DF[clusterDF$rowSummary == similarRowValues,] 
#  Date        name     address  phone 
#1 07-Jan-17 Game of ThOnes Books for selling George Washington street 555-55-55 
#2 06-Feb-17 Selling Game of Thrones books George Washington st. 0(555)-55-55 

이 데모는 간단한/장난감 데이터 세트와 잘 작동하지만 실제 데이터 세트에서는 문자열 거리 계산 방법, 클러스터 수 등을 조정해야 할 것입니다. 그러나이 방법이 올바른 방향으로 사용자에게 도움이되기를 바랍니다.