Przetwarzając dane tekstowe można zetknąć się z problemem duplikatów przybliżonych. Każdemu na pewno przydarzyło się zrobić literówkę wprowadzając dane do jakiegoś formularza. Formularz może zawierać także pytanie o dane adresowe i na przykład ulicę 3 maja można zapisać na wiele sposobów:
- 3 maja
- trzeciego maja
- 3-go maja
Podobnych przykładów można mnożyć, niemniej rezultat jest zawsze ten sam - jedna informacja i wiele jej wariantów.
Miary podobieństwa
W takiej sytuacji można skorzystać z pewnych miar podobieństwa tekstów (ang. fuzzy matching), które w R oprogramowane są w pakiecie stringdist.
Najczęściej wykorzystywane algorytmy to:
- odległość Levenshteina - odległość to liczba kroków wymaganych do przekształcenia jednego ciągu znaków w drugi. Działania jakie można wykonywać to wstawienie nowego znaku, usunięcie znaku lub zamianę znaku na nowy znak.
- odległość Damerau-Levenshteina - podobnie jak odległość Levenshteina, ale wprowadza działanie polegające na zamianie miejscami sąsiadujących znaków.
- najdłuższy wspólny podłańcuch (ang. longest common substring) - znajduje najdłuższy ciąg elementów leżących obok siebie w obu ciągach, natomiast odległość to liczba niesparowanych znaków.
- odległość Jaro - średnia z odsetka wspólnych znaków w pierwszym ciągu, odsetka wspólnych znaków w drugim ciągu oraz odsetka wspólnych znaków nie wymagających transpozycji. Przyjmuje wartości od 0 do 1, gdzie 0 to teksty identyczne, a 1 zupełnie różne.
- odległość Jaro-Winklera - zwiększenie podobieństwa ciągów, które według odległości Jaro są do siebie podobne.
Na podstawie wyżej opisanych algorytmów można stwierdzić, że im mniejsza wartość danej odległości tym ciągi tekstowe będą do siebie bardziej podobne. Pakiet stringdist
zawiera implementację jeszcze kilku miar, niemniej w tym poście skupiłem się na tych najbardziej popularnych.
Analiza imion męskich w 2015 roku
Z racji tego, że nie dysponuję bazą zawierającą takie nieuporządkowane dane tekstowe to wykorzystamy statystyki dotyczące najczęściej nadawanych imion dzieciom dostępne na stronach Ministerstwa Cyfryzacji. Wiemy przecież, że niektóre imiona występują w kilku wariantach np. Angelika i Andżelika, więc spróbujemy je znaleźć.
W pierwszej kolejności wczytuję pakiety oraz dane. Pakiet chorddiag przyda nam się do wizualizacji uzyskanych wyników na wykresie strunowym.
# devtools::install_github("mattflor/chorddiag")
library(tidyverse) # przetwarzanie
library(stringdist) # odległości pomiędzy tekstami
library(chorddiag) # wykres strunowy
library(grDevices) # kolory
library(RColorBrewer) # kolory
kolory <- grDevices::colorRampPalette(RColorBrewer::brewer.pal(9, "Set3"))
load("data/imiona.RData")
Liczba nadawanych unikalnych imion z roku na rok prawie się podwaja, co świadczy o coraz większej wyobraźni rodziców i chęci wyróżnienia dziecka już na starcie.
imiona %>%
group_by(plec, rok) %>%
count() %>%
ungroup() %>%
mutate(plec=factor(plec, labels=c("Kobiety", "Mężczyźni")),
rok=as.factor(rok)) %>%
ggplot(., aes(x=plec, y=n, fill=rok)) +
geom_bar(position = position_dodge(), stat = "identity") +
theme_light() +
xlab("Płeć") + ylab("Liczba unikalnych imion") +
theme(legend.position = "bottom") +
guides(fill=guide_legend(title="Rok"))
Z tego względu analizie poddamy imiona męskie nadane w 2015 roku. Mniejszy zbiór danych umożliwi wizualizację w czytelniejszy sposób.
d <- imiona %>%
filter(rok == 2015, plec == "m")
Poniżej znajduje się gotowa funkcja, która zwraca zbiór z parami porównywanych tekstów i odległościami pomiędzy nimi oraz macierz, którą można przedstawić na wykresie strunowym.
Funkcja przyjmuje trzy argumenty:
- dane - wektor tekstów, które zostaną porównane ze sobą parami,
- metoda - identyfikator metody z pakietu
stringdist
, - granica - przyjęty poziom podobieństwa.
Rezultatem działania funkcji są dwa obiekty:
- zbior - zawiera pary porównywalnych tekstów oraz wybraną odległość pomiędzy nimi,
- macierz - macierz zawierająca wartości poniżej przyjętej granicy.
podobne_teksty <- function(dane, metoda, granica){
# policzenie odległości dla wszystkich par
m <- as.matrix(stringdistmatrix(a = dane, b = dane, method = metoda))
rownames(m) <- dane
colnames(m) <- dane
# wybór obserwacji z odległością poniżej określonej granicy
m_g <- as.data.frame(which(m <= granica, arr.ind=TRUE)) %>%
mutate(tekst1=rownames(.)) %>%
filter(!row==col) %>%
mutate(tekst2=colnames(m)[col])
d <- numeric(nrow(m_g))
for(i in 1:length(d)){
d[i] <- m[m_g$row[i],m_g$col[i]]
}
m_g$d <- d
# usunięcie duplikatów
m_g_bd <- as.data.frame(unique(t(apply(m_g[,1:2], 1, sort))))
names(m_g_bd) <- c("row", "col")
m_g_bd_tekst <- inner_join(m_g_bd, m_g, by=c("row"="row", "col"="col"))
# utworzenie macierzy do funkcji chorddiag
# wybór unikalnych numerów kolumn i wierszy
rc <- unique(c(m_g_bd_tekst$row, m_g_bd_tekst$col))
m_g_tekst <- m[rc, rc]
# zamiana odległości większej niż podana granica na 0
m_g_tekst0 <- m_g_tekst
m_g_tekst0[m_g_tekst0 > granica] <- 0
wynik <- list(zbior=m_g_bd_tekst[-c(1,2)],
macierz=m_g_tekst0)
return(wynik)
}
W pierwszej kolejności zobaczmy jak z podobieństwem imion poradzi sobie odległość Damerau-Levenshteina. Jako granicę przyjąłem 2, co oznacza, że dopuszczam maksymalnie dwie modyfikacje pierwszego ciągu w celu otrzymania ciągu drugiego.
dl <- podobne_teksty(dane = d$imie, metoda = "osa", granica = 2)
dl_df <- dl$zbior
dl_m <- dl$macierz
head(dl_df) %>%
knitr::kable()
tekst1 | tekst2 | d |
---|---|---|
KASPER.1 | KACPER | 1 |
JONATHAN.1 | JONATAN | 1 |
JONATHAN.2 | NATHAN | 2 |
JANUSZ.1 | JONASZ | 2 |
OSCAR.1 | OSKAR | 1 |
AMADEUSZ.1 | MATEUSZ | 2 |
Następnie sprawdzam, które imię cechuje się największą liczbą sąsiadów i jak oni wyglądają. W przypadku tej odległości jest to imię ALAN, które ma 10 bliskich sąsiadów. Oznacza to, że zmieniając w imieniu ALAN maksymalnie dwa znaki można uzyskać 10 różnych imion.
liczebnosc <- colSums(dl_m != 0)
tekst_max <- liczebnosc[which(liczebnosc==max(liczebnosc))]
tekst_max
## ALAN
## 10
dl_df %>%
filter(tekst1 %in% names(tekst_max) | tekst2 %in% names(tekst_max)) %>%
knitr::kable()
tekst1 | tekst2 | d |
---|---|---|
ALEK.4 | ALAN | 2 |
ARON.2 | ALAN | 2 |
MILAN.1 | ALAN | 2 |
ALEX.3 | ALAN | 2 |
Do przedstawienia uzyskanych relacji najlepszy będzie wykres strunowy (ang. chord diagram). W pakiecie chorddiag
znajduje się eRowa implementacja tego wykresu pochodząca z biblioteki d3.js. Większa wersja tego wykresu znajduje się tutaj.
sort <- order(liczebnosc)
chorddiag(dl_m[sort, sort],
margin = 60,
palette = "Set3",
showTicks = F,
groupPadding = 2,
groupnameFontsize = 10,
groupnamePadding = 5,
groupThickness = .05,
showZeroTooltips = F,
chordedgeColor = "gray90",
groupColors = kolory(nrow(dl_m)))
Zobaczmy jak zadziała metoda najdłuższego wspólnego podłańcucha. Tutaj granicę ustalam na poziomie 3 niepasujących liter. Imiona JAN oraz BRIAN cechują się występowaniem aż 8 najbliższych sąsiadów.
lcs <- podobne_teksty(dane = d$imie, metoda = "lcs", granica = 3)
lcs_df <- lcs$zbior
lcs_m <- lcs$macierz
liczebnosc <- colSums(lcs_m != 0)
tekst_max <- liczebnosc[which(liczebnosc==max(liczebnosc))]
tekst_max
## BRIAN JAN
## 8 8
lcs_df %>%
filter(tekst1 %in% names(tekst_max) | tekst2 %in% names(tekst_max)) %>%
knitr::kable()
tekst1 | tekst2 | d |
---|---|---|
JANUSZ.1 | JAN | 3 |
ADRIAN.1 | BRIAN | 3 |
ARON.3 | JAN | 3 |
BRAJAN.3 | JAN | 3 |
JULIAN.1 | JAN | 3 |
ALAN.3 | JAN | 3 |
Wyniki także przedstawione są na wykresie strunowym (większa wersja).
sort <- order(liczebnosc)
chorddiag(lcs_m[sort, sort],
margin = 60,
palette = "Set3",
tickInterval = 10,
showTicks = F,
groupPadding = 1,
groupnameFontsize = 10,
groupnamePadding = 5,
groupThickness = .05,
chordedgeColor = "gray90",
groupColors = kolory(nrow(lcs_m)))
W przypadku odległości Jaro jako próg klasyfikacji sąsiada przyjąłem wartość 0.2. W tym przypadku mamy aż trzy najliczniejsze imiona - BRIAN, NATHAN oraz NATAN mają po pięciu sąsiadów.
jd <- podobne_teksty(dane = d$imie, metoda = "jw", granica = 0.2)
jd_df <- jd$zbior
jd_m <- jd$macierz
liczebnosc <- colSums(jd_m != 0)
tekst_max <- liczebnosc[which(liczebnosc==max(liczebnosc))]
tekst_max
## BRIAN NATHAN NATAN
## 5 5 5
jd_df %>%
filter(tekst1 %in% names(tekst_max) | tekst2 %in% names(tekst_max)) %>%
knitr::kable()
tekst1 | tekst2 | d |
---|---|---|
JONATHAN.2 | NATHAN | 0.0833333 |
JONATHAN.4 | NATAN | 0.1250000 |
ADRIAN.1 | BRIAN | 0.1777778 |
JONATAN.2 | NATHAN | 0.1507937 |
JONATAN.3 | NATAN | 0.0952381 |
NATHAN.5 | NATAN | 0.0555556 |
NATHANIEL.4 | NATAN | 0.1481481 |
NATANIEL.3 | NATAN | 0.1250000 |
Uzyskane wyniki przedstawione na wykresie strunowym (większa wersja).
sort <- order(liczebnosc)
chorddiag(jd_m[sort, sort],
margin = 60,
palette = "Set3",
tickInterval = 10,
showTicks = F,
groupPadding = 1,
groupnameFontsize = 10,
groupnamePadding = 5,
groupThickness = .05,
chordedgeColor = "gray90",
groupColors = kolory(nrow(jd_m)))
Analiza imion żeńskich w 2017 roku
Można jeszcze pokusić się o analizę dla roku 2017. Wybierając imiona kobiece najwięcej sąsiadów z wykorzystaniem odległości Jaro i progu podobieństwa 0.2 uzyskamy dla imienia MARINA - 45.
d <- imiona %>%
filter(rok == 2017, plec == "k")
jd <- podobne_teksty(dane = d$imie, metoda = "jw", granica = 0.2)
jd_df <- jd$zbior
jd_m <- jd$macierz
liczebnosc <- colSums(jd_m != 0)
tekst_max <- liczebnosc[which(liczebnosc==max(liczebnosc))]
tekst_max
## MARINA
## 45
jd_df %>%
filter(tekst1 %in% names(tekst_max) | tekst2 %in% names(tekst_max)) %>%
head(n=12) %>%
knitr::kable()
tekst1 | tekst2 | d |
---|---|---|
MARIETTA.8 | MARINA | 0.1805556 |
MALWINA.7 | MARINA | 0.1507937 |
KARINA.9 | MARINA | 0.1111111 |
ROMINA.5 | MARINA | 0.1777778 |
MARIKA.11 | MARINA | 0.1111111 |
ALINA.17 | MARINA | 0.1777778 |
MARIAME.8 | MARINA | 0.1507937 |
MARIE.6 | MARINA | 0.1777778 |
MARIJA.11 | MARINA | 0.1111111 |
AMIRA.7 | MARINA | 0.1888889 |
MARZENA.3 | MARINA | 0.1507937 |
AMNA.5 | MARINA | 0.1944444 |
Macierz odległości dla podobnych imion męskich w 2015 roku miała rozmiar 124 x 124, natomiast imiona kobiece w 2017 roku znajdują się w macierzy wielkości 686 na 686. W związku z tym przedstawienie tych danych na wykresie strunowym czyni ten wykres mało czytelnym. Wobec tego pozostaje analiza wyłącznie w oparciu o dane liczbowe.
Podsumowanie
Wykorzystane miary odległości pomiędzy tekstami różnią się między sobą jeśli chodzi o główną ideę, stąd trudno wskazać najlepszą z nich. Każda pozwala na identyfikację najbardziej zbliżonych tekstów, ale ze względu na różne kryteria. W praktyce warto zastosować kilka miar i ocenić zaproponowane obserwacje.
Z zastosowaniem opisanych metryk można analizować duże zbiory danych, niemniej w takim przypadku wizualizacja takich danych z wykorzystaniem wykresu strunowego staje się problematyczna i należałoby się skupić wyłącznie na analizie liczbowej bądź poszukać alternatywnych sposobów wizualizacji takich danych.
Bibliografia
- Data Steve - d3/R Chord Diagram of White House Petition Data
- Krzysztof Jankiewicz - Hurtownie Danych, ETL – wybrane zagadnienia
Kod i dane dostępne są także na githubie