데이터 사이언스 - 자연어 처리
텍스트 거리
xwMOOC
2020-04-12
1 문자열 거리 1 2 3
단어 혹은 문장의 거리를 파악할 때 많이 사용되는 것이 레빈스타인 편집 거리(levenshtein edit distance)다. 영화와 애니메이션은 다른 것과 비교하여 의미론적으로 유사하지만 형태적 유사성은 거의 없다. 의미론적 유사성을 따지는데 도움이 되는 것이 Word2Vec이라면 형태론적 유사성을 따지는 대표적인 것이 레빈스타인 편집 거리(levenshtein edit distance)다.
영어와 한글의 유사성을 따지는데 차이가 있기 때문에 영어를 대상으로 먼저 형태론적 유사성을 따져보자. stringdist 팩키지에 문자열 거리와 관련된 대부분의 기능이 구현되어 있다.
stringdist 팩키지의 철학은 Base R의 다양한 함수 match, adist, nchar, agrep 등을 포괄하는 인터페이스를 목적으로 제작되었다.
stringdist: 두 입력 문자열 벡터 사이 거리 계산stringdistmatrix: 하나 혹은 두개 벡터에 대한 거리 행렬 계산stringsim:stringdist에 기반하여 0과 1 사이 문자열 유사도 계산amatch: R 내장match함수에 대응되는 퍼지 매칭ain: R 내장%in%연산자에 대응되는 퍼지 매칭seq_dist,seq_distmatrix,seq_amatch,seq_ain: 정수 순열에 매칭되는 거리 (hashr팩키지 참조).
1.1 사전 찾기
가장 먼저 사전 찾기(dictionary lookup)을 사례로 들어본다. Base R에 포함된 문자열 찾기 관련 함수를 사례로 들어본다.
[1] 2[1] NA[1] 2[1] FALSE[1] TRUE1.2 거리계산
문자열 s가 문자열 t로 변환시키는데 필요한 최소 연산수를 계산하는 다양한 알고리즘이 존재한다. 많이 사용되는 알고리즘은 치환(substitution), 삭제(deletion), 삽입(insertion), 전치(transposition) 지원여부에 따라 다양한 알고리즘이 지원된다.
library(magick)
edit_pdf <- image_read_pdf("data/stringdistuser2014-140704113415-phpapp01.pdf", pages=13)
edit_pdf %>%
image_crop(geometry="1350x400+100+350")
앞서 언급된 알고리즘은 stringdist 팩키지에 구현되어 있다.
library(tidyverse)
string_df <- tribble(~"typing",
"Cosmo Kramer",
"Kosmo Kramer",
"Comso Kramer",
"Csmo Kramer",
"Cosmo X. Kramer",
"Kramer, Cosmo",
"Jerry Seinfeld",
" CKaemmoorrs",
"Cosmer Kramo",
"Kosmoo Karme",
"George Costanza",
"Elaine Benes",
"Dr. Van Nostren",
"remarK omsoC",
"Mr. Kramer",
"Sir Cosmo Kramer",
"C.o.s.m.o. .K.r.a.m.e.r",
"CsoKae",
"Coso Kraer")
string_df <- string_df %>%
mutate(name = "Cosmo Kramer") %>%
mutate(lv_dist = map2_dbl(typing, name, stringdist, "lv"),
osa_dist = map2_dbl(typing, name, stringdist, "osa"),
dl_dist = map2_dbl(typing, name, stringdist, "dl"),
jw_dist = map2_dbl(typing, name, stringdist, "jw"),
ham_dist = map2_dbl(typing, name, stringdist, "hamming"))
string_df# A tibble: 19 x 7
typing name lv_dist osa_dist dl_dist jw_dist ham_dist
<chr> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
1 "Cosmo Kramer" Cosmo Kram~ 0 0 0 0 0
2 "Kosmo Kramer" Cosmo Kram~ 1 1 1 0.0556 1
3 "Comso Kramer" Cosmo Kram~ 2 1 1 0.0278 2
4 "Csmo Kramer" Cosmo Kram~ 1 1 1 0.0732 Inf
5 "Cosmo X. Kramer" Cosmo Kram~ 3 3 3 0.0667 Inf
6 "Kramer, Cosmo" Cosmo Kram~ 11 11 11 0.466 Inf
7 "Jerry Seinfeld" Cosmo Kram~ 12 12 12 0.623 Inf
8 " CKaemmoorrs" Cosmo Kram~ 11 11 11 0.315 12
9 "Cosmer Kramo" Cosmo Kram~ 4 4 4 0.211 8
10 "Kosmoo Karme" Cosmo Kram~ 5 4 4 0.144 7
11 "George Costanza" Cosmo Kram~ 12 12 12 0.506 Inf
12 "Elaine Benes" Cosmo Kram~ 11 11 11 0.722 11
13 "Dr. Van Nostren" Cosmo Kram~ 13 13 13 0.506 Inf
14 "remarK omsoC" Cosmo Kram~ 10 10 10 0.373 12
15 "Mr. Kramer" Cosmo Kram~ 5 5 5 0.358 Inf
16 "Sir Cosmo Kramer" Cosmo Kram~ 4 4 4 0.25 Inf
17 "C.o.s.m.o. .K.r.a.m.e~ Cosmo Kram~ 11 11 11 0.202 Inf
18 "CsoKae" Cosmo Kram~ 6 6 6 0.222 Inf
19 "Coso Kraer" Cosmo Kram~ 2 2 2 0.0556 Inf1.3 ngram 거리
qgrams() 함수의 문자열 쪼개는 것을 q=2로 변화를 주어 차이나는 것을 확인하고 거리도 계산할 수 있다.
Ma ar ri ry ya ia ah
V1 1 1 1 0 0 1 1
V2 1 1 0 1 1 0 0qgrams() 함수
V1 V2
0.7142857 0.5714286 2 퍼지조인(fuzzy join)
2.1 데이터셋
대한민국 제21대 국회의원 선거, “출마자 신상정보: 데이터” 데이터를 얻었으나 문제는 선거구를 지도와 연결하는데 문제가 있다는 점이다. 즉, 선거구별로 몇명 출마했는지 단순한 정보를 지도상에 표현하는데 있어 퍼지조인이 유용하다.
library(tidyverse)
library(sf)
## 대구 선거구 지도
대구_선거구 <- st_read("../election/data/shapefile/2020_21_elec_253_simple.json") %>%
filter(str_detect(SGG_1, "대구"))Reading layer `2020_21_elec_253_simple' from data source `C:\docs\election\data\shapefile\2020_21_elec_253_simple.json' using driver `GeoJSON'
Simple feature collection with 253 features and 4 fields
geometry type: MULTIPOLYGON
dimension: XY
bbox: xmin: 124.6098 ymin: 33.16123 xmax: 130.9175 ymax: 38.61369
epsg (SRID): 4326
proj4string: +proj=longlat +datum=WGS84 +no_defs# 대구 선거구별 출마자수
candidate_df <- read_rds("../election/data/candidate_253_df.rds")
대구_출마자 <- candidate_df %>%
filter(str_detect(시도명, "대구")) %>%
group_by(선거구명, 시도명) %>%
summarise(출마자수 = n()) %>%
ungroup() %>%
arrange(desc(출마자수)) %>%
mutate(SGG_2 = glue::glue("{시도명} {선거구명}"))
대구_출마자# A tibble: 12 x 4
선거구명 시도명 출마자수 SGG_2
<chr> <chr> <int> <glue>
1 동구을 대구광역시 7 대구광역시 동구을
2 달서구갑 대구광역시 6 대구광역시 달서구갑
3 달서구을 대구광역시 6 대구광역시 달서구을
4 북구갑 대구광역시 6 대구광역시 북구갑
5 달서구병 대구광역시 5 대구광역시 달서구병
6 달성군 대구광역시 5 대구광역시 달성군
7 북구을 대구광역시 5 대구광역시 북구을
8 서구 대구광역시 5 대구광역시 서구
9 수성구갑 대구광역시 5 대구광역시 수성구갑
10 동구갑 대구광역시 4 대구광역시 동구갑
11 수성구을 대구광역시 4 대구광역시 수성구을
12 중구남구 대구광역시 3 대구광역시 중구남구2.2 매칭 작업
대구_선거구 지도에서 “SGG_3” 칼럼과 대구_출마자 데이터프레임에서 “선거구명”간 stringdist 거리를 계산해서 max_dist가 3인 경우 매칭이 원활이 됨을 확인할 수 있다.
library(fuzzyjoin)
joined <- stringdist_join(
대구_선거구,
대구_출마자,
by = c("SGG_3" = "선거구명"),
max_dist = 3,
distance_col = "distance"
)
대구_선거구_sf <- joined %>%
select(SGG_Code, 시도명, 선거구명, 출마자수, distance, geometry)
대구_선거구_sfSimple feature collection with 7 features and 5 fields
geometry type: MULTIPOLYGON
dimension: XY
bbox: xmin: 128.5041 ymin: 35.80771 xmax: 128.7619 ymax: 36.0163
epsg (SRID): 4326
proj4string: +proj=longlat +datum=WGS84 +no_defs
SGG_Code 시도명 선거구명 출마자수 distance geometry
1 2270202 대구광역시 동구을 7 3 MULTIPOLYGON (((128.6602 35...
2 2270101 대구광역시 중구남구 3 3 MULTIPOLYGON (((128.5907 35...
3 2270501 대구광역시 북구갑 6 3 MULTIPOLYGON (((128.6103 35...
4 2270502 대구광역시 북구을 5 3 MULTIPOLYGON (((128.552 35....
5 2270301 대구광역시 서구 5 3 MULTIPOLYGON (((128.5481 35...
6 2270301 대구광역시 중구남구 3 3 MULTIPOLYGON (((128.5481 35...
7 2270201 대구광역시 동구갑 4 3 MULTIPOLYGON (((128.6147 35...하지만, 전체 대구 선거구 10곳에 대해서 제대로 매칭을 하지 못하고 있는 것이 확인 되어 이에 대한 보완작업이 필요한 것도 사실이다.
2.3 사용자 정의 매칭
사용자 정의 함수(calc_sgg_distance)를 지정한 후에 match_fun에 fuzzy_left_join을 걸어 출마자수를 지도에 연결시킬 수 있다.
library(stringdist)
calc_sgg_distance <- function(map, data) {
stringdist(map, data) < 1
}
대구_fuzzy_join_sf <- fuzzy_left_join(
대구_선거구,
대구_출마자,
by = "SGG_2",
match_fun = calc_sgg_distance)
대구_fuzzy_join_sf %>%
ggplot(aes(fill=출마자수)) +
geom_sf() +
theme_void() +
theme(panel.grid.major = element_line(color = "white")) +
scale_fill_gradientn(colors = viridis::viridis(7)) +
geom_sf_label(aes(label = 선거구명))
3 Record Linkage
3.1 데이터셋
Duplicate Detection, Record Linkage, and Identity Uncertainty: Datasets 웹사이트에 중복 레코드 탐지와 Record Linkage와 관련된 데이터셋이 있다.
그중 Fodor and Zagat 식당 데이터셋은 112개의 중복이 내재되어 있다. 참고로 저갯 서베이(zagat survey)는 미국에서 발간되는 세계적인 레스토랑 안내서로 1979년 미국 뉴욕에서 저갯 부부가 창업했다.
library(reclin)
download.file(url="http://www.cs.utexas.edu/users/ml/riddle/data/restaurant.tar.gz", destfile = "data/restaurant.tar.gz")
untar("data/restaurant.tar.gz", exdir = "data")total 220
drwxrwxrwx 1 statkclee statkclee 512 Apr 12 19:08 .
drwxrwxrwx 1 statkclee statkclee 512 Apr 12 18:15 ..
-rwxrwxrwx 1 statkclee statkclee 360 Oct 6 2003 README
-rwxrwxrwx 1 statkclee statkclee 41775 Apr 12 18:14 fodors.csv
-rwxrwxrwx 1 statkclee statkclee 69580 Oct 6 2003 fz-nophone.arff
-rwxrwxrwx 1 statkclee statkclee 83432 Oct 6 2003 fz.arff
drwxrwxrwx 1 statkclee statkclee 512 Apr 12 19:08 original
-rwxrwxrwx 1 statkclee statkclee 23281 Apr 12 18:14 zagat.csvFodors 데이터셋와 Zagat 데이터셋을 일별하면 다음과 같다.
Fodors 데이터셋
Observations: 533
Variables: 7
$ id <dbl> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,...
$ name <chr> "arnie morton's of chicago", "art's delicatessen", "hotel bel...
$ addr <chr> "435 s. la cienega blv .", "12224 ventura blvd.", "701 stone ...
$ city <chr> "los angeles", "los angeles", "los angeles", "los angeles", "...
$ phone <chr> "310-246-1501", "818-762-1221", "310-472-1211", "818-788-3536...
$ type <chr> "american", "american", "californian", "french", "american", ...
$ class <dbl> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,...Zagat 데이터셋
Observations: 310
Variables: 7
$ id <dbl> 0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 15, 16, 17, 18, 19, 20...
$ name <chr> "apple pan the", "asahi ramen", "baja fresh", "belvedere the"...
$ addr <chr> "10801 w. pico blvd.", "2027 sawtelle blvd.", "3345 kimber dr...
$ city <chr> "los angeles", "los angeles", "los angeles", "los angeles", "...
$ phone <chr> "310-475-3585", "310-479-2231", "805-498-4049", "310-788-2306...
$ type <chr> "american", "noodle shops", "mexican", "pacific new wave", "f...
$ class <dbl> 534, 535, 536, 537, 538, 539, 540, 542, 543, 545, 546, 547, 5...3.2 1단계: 짝 생성(Generate Pairs)
가장 먼저 짝을 생성한다. 이를 위해서 reclin 팩키지 pair_blocking() 함수를 사용하는데 fodors_df가 533 개 식당, zagat_df가 310개 식당을 보유하고 있어 이를 짝짓게 되면 \(533 \times 310 = 165,230\) 경우의 수가 나오게 된다.
Simple blocking
No blocking used.
First data set: 533 records
Second data set: 310 records
Total number of pairs: 165 230 pairs
ldat with 165 230 rows and 2 columns
x y
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
6 6 1
7 7 1
8 8 1
9 9 1
10 10 1
: : :
165221 524 310
165222 525 310
165223 526 310
165224 527 310
165225 528 310
165226 529 310
165227 530 310
165228 531 310
165229 532 310
165230 533 310경우의 수가 너무 많아 격리변수를 두어 평개해야될 수를 줄인다. 이를 블로킹(blocking)이라고 하고 blocking_var 변수를 지정하면 경우의 수를 획기적으로 줄일 수 있다.
Simple blocking
Blocking variable(s): city, type
First data set: 533 records
Second data set: 310 records
Total number of pairs: 1 052 pairs
ldat with 1 052 rows and 2 columns
x y
1 1 1
2 1 10
3 1 25
4 1 27
5 1 37
6 2 1
7 2 10
8 2 25
9 2 27
10 2 37
: : :
1043 525 184
1044 525 309
1045 526 184
1046 526 309
1047 527 173
1048 527 190
1049 527 196
1050 531 195
1051 533 182
1052 533 3033.3 2단계: 짝 평가
두번째 단계는 앞서 생성된 경우의 수에 대해서 평가를 진행하는 것이다. 이를 위해서 compare_pairs() 함수를 사용하고 음식점 이름(name) 뿐만 아니라 주소(addr), 전화번호(phone)에 대해서 평가 작업을 수행하고 앞서 문자열 거리 비교를 위해서 사용된 다양한 거리 측정 함수를 사용한다.
identical()jaro_winkler(threshold = 0.95)lcs(threshold = 0.8)jaccard(threshold = 0.8)
pair_blocking(fodors_df, zagat_df, blocking_var = c("city", "type")) %>%
compare_pairs(by = c("name", "addr", "phone"), default_comparator = jaro_winkler())Compare
By: name, addr, phone
Simple blocking
Blocking variable(s): city, type
First data set: 533 records
Second data set: 310 records
Total number of pairs: 1 052 pairs
ldat with 1 052 rows and 5 columns
x y name addr phone
1 1 1 0.4871062 0.5703661 0.6746032
2 1 10 0.5533333 0.6023793 0.7222222
3 1 25 0.5976313 0.5743393 0.7407407
4 1 27 0.5779125 0.5228048 0.5833333
5 1 37 0.5555556 0.6255242 0.6944444
6 2 1 0.5234025 0.6140351 0.5555556
7 2 10 0.4490741 0.5680470 0.5555556
8 2 25 0.4626323 0.5263803 0.6111111
9 2 27 0.3619529 0.4729102 0.4722222
10 2 37 0.4994709 0.6787803 0.5833333
: : : : : :
1043 525 184 0.5509507 0.7035361 0.6666667
1044 525 309 0.5221755 0.6088235 0.7152778
1045 526 184 0.5643616 0.6294872 0.7361111
1046 526 309 0.5787037 0.5401961 0.7361111
1047 527 173 0.4305556 0.6841737 0.6507937
1048 527 190 0.3412698 0.5070962 0.6746032
1049 527 196 0.5092593 0.5364146 0.8333333
1050 531 195 0.5106516 0.7022792 0.8333333
1051 533 182 0.4424837 0.6295815 0.6111111
1052 533 303 0.4487628 0.6365079 0.73611113.4 3단계: 점수매기기
다음 단계로 점수를 매기는데 단순합산하는 score_simsum() 방식과 EM-알고리즘을 구현한 problink_em() 을 이용하여 점수를 구하는 score_problink()을 활용한다.
pair_blocking(fodors_df, zagat_df, blocking_var = c("city", "type")) %>%
compare_pairs(by = c("name", "addr", "phone"), default_comparator = jaro_winkler()) %>%
score_problink()Compare
By: name, addr, phone
Simple blocking
Blocking variable(s): city, type
First data set: 533 records
Second data set: 310 records
Total number of pairs: 1 052 pairs
ldat with 1 052 rows and 6 columns
x y name addr phone weight
1 1 1 0.4871062 0.5703661 0.6746032 0.8470803
2 1 10 0.5533333 0.6023793 0.7222222 1.3810215
3 1 25 0.5976313 0.5743393 0.7407407 1.5461442
4 1 27 0.5779125 0.5228048 0.5833333 0.6421708
5 1 37 0.5555556 0.6255242 0.6944444 1.3288149
6 2 1 0.5234025 0.6140351 0.5555556 0.6071855
7 2 10 0.4490741 0.5680470 0.5555556 0.2312956
8 2 25 0.4626323 0.5263803 0.6111111 0.3798816
9 2 27 0.3619529 0.4729102 0.4722222 -0.6064343
10 2 37 0.4994709 0.6787803 0.5833333 0.8521354
: : : : : : :
1043 525 184 0.5509507 0.7035361 0.6666667 1.4595335
1044 525 309 0.5221755 0.6088235 0.7152778 1.2622462
1045 526 184 0.5643616 0.6294872 0.7361111 1.5718598
1046 526 309 0.5787037 0.5401961 0.7361111 1.3603529
1047 527 173 0.4305556 0.6841737 0.6507937 0.9280344
1048 527 190 0.3412698 0.5070962 0.6746032 0.2201402
1049 527 196 0.5092593 0.5364146 0.8333333 1.6891540
1050 531 195 0.5106516 0.7022792 0.8333333 2.2188427
1051 533 182 0.4424837 0.6295815 0.6111111 0.6149125
1052 533 303 0.4487628 0.6365079 0.7361111 1.21491333.5 4단계: 선택과 연결
마지막 단계로 점수를 바탕으로 선택하여 데이터에 연결하는 과정을 select_n_to_m() 함수와 link() 함수로 구현하면 된다.
3.6 5단계: 검증
RWeka 팩키지 read.arff() 함수를 사용해서 중복된 음식점에 대한 사항을 확인한다.
library(RWeka)
fz_df <- read.arff("data/restaurant/fz.arff")
fz_dup_df <- fz_df %>%
filter(class %in% factor(c(0, seq(1:111)))) %>%
tbl_df %>%
arrange(name)
fz_dup_df# A tibble: 224 x 6
name addr city phone type class
<chr> <chr> <chr> <chr> <chr> <fct>
1 21 club 21 w. 52nd st. new york 212/582~ american 23
2 21 club 21 w. 52nd st. new york ~ 212-582~ american~ 23
3 abruzzi 2355 peachtree rd. peachtree~ atlanta 404/261~ italian 74
4 abruzzi 2355 peachtree rd. ne atlanta 404-261~ italian 74
5 alain ron~ 126 clement st. san franc~ 415/387~ french 94
6 alain ron~ 126 clement st. san franc~ 415-387~ french (~ 94
7 aqua 252 california st. san franc~ 415/956~ seafood 95
8 aqua 252 california st. san franc~ 415-956~ american~ 95
9 aquavit 13 w. 54th st. new york 212/307~ continen~ 24
10 aquavit 13 w. 54th st. new york ~ 212-307~ scandina~ 24
# ... with 214 more rows전화번호를 키값으로 추출하여 일치여부를 파악한다. 110개로 112개 중복된 음식점을 찾아낸 것으로 파악된다.
fz_dup_phone <- fz_dup_df %>%
mutate(phone = str_replace_all(phone, "/", "-") %>% str_remove(., " ")) %>%
pull(phone) %>%
unique()
reclin_df %>%
filter(!is.na(id.y)) %>%
tbl_df() %>%
arrange(name.x)# A tibble: 310 x 14
id.x name.x addr.x city.x phone.x type.x class.x id.y name.y addr.y city.y
<dbl> <chr> <chr> <chr> <chr> <chr> <dbl> <dbl> <chr> <chr> <chr>
1 74 abruz~ 2355 ~ atlan~ 404-26~ itali~ 74 292 abruz~ 2355 ~ atlan~
2 423 anton~ 3700 ~ las v~ 702-25~ itali~ 423 126 fiore~ 3700 ~ las v~
3 383 atlan~ 265 p~ atlan~ 404-26~ ameri~ 383 174 origi~ 4330 ~ atlan~
4 426 batti~ 4041 ~ las v~ 702-73~ itali~ 426 135 piero~ 355 c~ las v~
5 384 beesl~ 260 e~ atlan~ 404-26~ conti~ 384 300 hedge~ 490 e~ atlan~
6 385 berto~ 3500 ~ atlan~ 404-23~ itali~ 385 156 eats 600 p~ atlan~
7 427 berto~ 3570 ~ las v~ 702-73~ itali~ 427 140 tre v~ 3799 ~ las v~
8 386 bista~ 1100 ~ atlan~ 404-72~ medit~ 386 177 rivie~ 519 e~ atlan~
9 429 bistro 3400 ~ las v~ 702-79~ conti~ 429 130 micha~ 3595 ~ las v~
10 118 bistr~ 176 n~ los a~ 310-55~ calif~ 115 9 brist~ 1570 ~ los a~
# ... with 300 more rows, and 3 more variables: phone.y <chr>, type.y <chr>,
# class.y <dbl>