단어 클러스터링 프로그램 Civciv 개발기 - 편집거리와 클러스터링 알고리즘

발단

외국 나가있는 아는 후-배가 하는 프로젝트가 하나 있다는데, 거기서 하는 일이 근대 사람의 일기 자료를 분석하는 일이랍니다. "아 재미있는 일을 하는구나!" 하고선 넘어가려했는데, 일기가 사람이 쓰는것이다보니 철자오류도 잦고, 같은 대상을 이형태로 기록해두는 경우가 많아서 그걸 일일히 찾아내는게 귀찮다는 이야기를 들었습니다.

예를 들자면, Arab을 Ahrab이라 적는다던가 Arahb이라 쓴다던지 하는 철자 실수에서부터, America를 쓰다가 오타를 내서 Amecira라고 쓰는 경우도 있다는 거지요. 문제는 이렇게 철자 한 두개가 달라버리면, 단순히 검색하는 방식으로는 해당 단어가 어디서 얼마나 나타나는지를 통계내기가 곤란해진다는 거죠. 그래서 그동안 이런걸 찾는 작업을 사람이 수작업으로 했다는 겁니다.

단순 반복 노동은 컴퓨터에게 시키고, 사람은 창의적인 일을 해야한다!

는 개발철학에 입각하면 그냥 지나칠 수 없는 사건이었죠. 그래서 위처럼 철자가 한 두개 다른, 유사한 단어들을 하나로 묶어서 통계처리를 해주는 프로그램을 짜게 되었습니다.

작전을 세워보면 다음과 같이 되겠네요.

1. 텍스트를 단어 단위로 쪼갠다. (띄어쓰기, 특수문자 등을 기준으로 Split)
2. 할 수 있으면 각 단어의 어간을 추출한다. (영어의 경우 포터 스테머를 적용하면 끝)
3. 모든 어간끼리의 유사도를 계산한다.
4. 유사도가 높은것부터 묶어서 그룹화한다.
5. 결과를 이쁘게 보여준다.
6. ????
7. PROFIT!!

전개(유사도 계산방식 선택)

단순 문자열 비교는 두 문자열이 완전히 같은 경우 참, 그렇지 않을 경우 거짓의 결과를 내놓습니다. Arab과 Ahrab를 비교하면 "다름"이라는 결과가 나오는거죠. 얼마나 비슷한지는 전혀 신경 쓰지 않구요... 얼마나 유사한지 비교하려면 다른 방법을 사용해야 합니다. 이런 경우 사용할 수 있는 방법에는 N-Gram 비교(문자열을 n길이의 조각으로 분해하여 겹치는 개수를 세는것), 편집거리(한 문자열을 다른 문자열로 바꾸기 위해, 최소 몇번의 삽입/삭제/수정을 해야하는지를 세는 것) 등이 있습니다. Arab - Ahrab에 대해 두 방법을 적용해보도록 하지요.

N-Gram 비교

Arab을 Bigram으로 쪼개면 {^A, Ar, ra, ab, b$}

Ahrab을 Bigram으로 쪼개면 {^A, Ah, hr, ra, ab, b$} 인데

둘이 겹치는 요소가 4개이므로 Arab과 Ahrab은 4의 일치도를 보인다고 할수 있습니다. 이 숫자는 길이에 따라 크기 범위가 달라지므로, 정규화해서 0~1 범위에 들어오게 합집합의 크기로 나눠주면 좋겠죠.

두 집합 전체 요소는 7개이므로 둘의 비율을 따지면 4/7 = 0.57...

이 방법에서 Arab과 Ahrab의 유사도는 0.57입니다.

편집거리

Arab이 Ahrab이 되려면 A와 r 사이에 h가 하나 들어가야하므로, 편집거리는 1이 됩니다. 편집거리 역시 문자열 길이에 따라 크기 범위가 달라지므로, 두 문자열 길이의 합으로 나눠주면 0~1 범위에 들어갈수 있겠죠. (편집거리는 두 문자열이 완전히 일치할때 0이 되고, 두 문자열이 aaa, bbbbb 와 같이 아예 다른 경우 두 문자열 길이의 합으로 최대가 되기 때문이죠!)

Arab과 Ahrab의 길이 합은 9이므로 나눠주면 1/9 = 0.11... 두 문자열은 약 0.11 정도만큼 다르다고 볼수 있겠죠. 유사도로 변환하기 위해 1에서 빼주면, 약 0.89이란 값을 얻을수 있겠죠.

이 방법에서 Arab과 Ahrab의 유사도는 0.89입니다.

예시를 보면 알수 있다시피 글자가 한 두개 누락되거나 변경된 경우 편집거리가 더 높은 유사도를 냅니다. 우리는 이 경우를 검출하여 묶어주는게 주목표이므로 편집거리를 채용하기로 했습니다.

편집거리 소스코드는 https://en.wikipedia.org/wiki/Levenshtein_distance에 친절하게 나와있습니다. (편집거리를 Levenshtein distance라고도 한답니다.) 감사히 가져다 쓰면 되겠죠. n길이의 두 문자열의 편집거리를 계산하는데에는 보통 O(n^2)의 시간복잡도가 소요된다고 알려져 있습니다만 어차피 단어의 길이는 그리 길지 않으므로 이 부분은 크게 신경쓰지 않아도 될듯하군요.

+ 그리고 유사도가 높더라도 첫 글자가 다른 경우에는 묶지 않도록 했습니다. there랑 where, mere랑 here 등 앞 글자 빼고 나머지가 다 같아서 같은 단어 그룹으로 묶이는 경우가 생각보다 많았거든요. 대게 사람이 단어를 인지할때 첫글자와 마지막 글자를 제일 중요하게 본다고 알려져 있으므로, 이 부분에서는 잘못 적는일이 발생할 확률이 낮다고 보고, 아예 첫 글자가 다른 경우는 유사하지 않다고 보기로 했습니다.

위기

유사도 알고리즘을 위에서 선택했으므로, 이제 클러스터링을 실시하면 됩니다. 그 기법은 예전 포스팅에서 잘 설명해뒀으니 참조하시면 되겠습니다. 어떤 메소드를 골라야할지 모를때에는 평균 기법을 고르는게 평균적으로 제일 좋은 결과를 낸답니다. 집단평균기법으로 Bottom-Up 클러스터링을 실시하기로 했습니다.

문서 내에 N개의 단어가 있다고 할 경우, 먼저 단어간의 유사도를 위 방식으로 구합니다. 유사도가 가장 높은 두 그룹을 묶어 새 그룹으로 만들고, 또 새로운 유사도를 구합니다. 다음으로 유사도가 높은 두 그룹을 묵어 새 그룹으로 만들고... 이 작업을 특정 기준치까지 수행하면, 유사한 단어끼리 적당히 묶인 클러스터들을 얻을 수 있겠죠.

이 작업이 얼마나 걸릴까요? 대충 추정해봅시다. 일단 편집거리를 매번 구하는것을 비효율적이므로, 처음에 한 번만 구해두고, 다음부터는 재활용하는 전략을 쓴다하고 유사도를 O(1)에 구한다고 합시다.

1. 그룹 간 유사도가 가장 높은 한 쌍을 찾는 작업: 총 T개의 그룹이 있다고 할 경우 T*(T-1)/2번의 탐색이 필요하겠죠.
2. 유사도가 가장 큰 한 쌍을 통합시켜서 그룹의 개수가 1 줄어듬: 총 T-1개의 그룹
3. 다시 그룹 간 유사도가 가장 높은 한 쌍을 찾는 작업: (T-1)*(T-2)/2번의 탐색이 필요하겠죠.
4. 또 그룹의 개수가 1 줄어듬: 총 T-2개의 그룹
5. 다시 그룹 간 유사도가 가장 높은 한 쌍을 찾는 작업: (T-2)*(T-3)/2번의 탐색이 필요하겠죠.
6. ...

유사도가 고르게 분포한다고 가정했을때, 특정 기준치보다 유사도가 높은 쌍 역시 전체 개수 T에 비례해서 존재한다고 가정할 수 있겠죠. 이때 그 비율을 r이라고 하면, 유사도 최고 쌍을 찾고 합치는 작업을 약 r*T번 반복하게 될겁니다. 그럼 전체의 시간복잡도를 추정해보죠.

기나긴 수식이었지만, 사실 고등학생 때 배우는 수열의 합 공식을 좀 이용한 것일뿐입니다. 마지막 줄을 보시면 알수 있듯이 클러스터링 전체 작업에 걸리는 시간은 전체 단어 갯수 T의 세제곱에 비례합니다. O(N^3)의 시간복잡도를 가집니다. 이 말은 즉 단어가 2배로 늘어나면 클러스터링 작업은 8배 오래걸리게 된다는 거지요. 텍스트 내 단어의 종류는 텍스트 길이의 제곱근에 비례한다고 알려져 있습니다. 따라서 텍스트 길이가 2배로 늘어나면 클러스터링 작업은 약 2.8배로, 4배로 늘어나면 8배로 불어납니다. 이런 방법으로는 큰 텍스트에 대해 단어 간 클러스터링을 할수가 없어요!

절정

Divide Et Impera!

분할하여 정복하라!

고대 로마에서 흔히 나왔던 이 말은 지금 컴퓨터 과학자들에게도 매우 유용합니다. 문제 크기를 작게 쪼갤경우 해결이 쉬워지거든요. 위의 클러스터링 알고리즘 역시 마찬가지입니다. 만약 절대로 같은 그룹으로 묶이지 않을 단어들을 알고 있다면 둘을 부분으로 분리해서 각각 처리하면 좋겠죠. 이 경우 전체 크기가 N일때 클러스터링 작업 F 전체의 시간 복잡도는

F(N) = O(N^3) 이지만

F(N/2) + F(N/2) = O(N^3 / 8) + O(N^3 / 8) = O(N^3) / 4 = F(N) / 4

전체 단어를 둘로 쪼개어 각각의 부분에 대해서 클러스터링을 실시할 경우 전체 소요 시간은 1/4이 됩니다. 더 쪼개면 쪼갤수록 속도는 더욱 빨라지겠죠. 다만 서로 확실히 묶이지 않을 것이라고 알수 있는 단어에 대해서만 분리가 가능하겠죠. 엮일 수 있는 단어를 강제로 쪼개버리면 안되니까요.

처음에 첫 글자가 다른 경우는 아예 유사하지 않다고 정의하기로 앞서 밝혔으므로, 첫 글자를 보면 해당 단어가 첫 글자가 다른 단어와 엮이지 않을 것이라는 걸 확실히 알수 있습니다. 따라서 첫글자에 따라 각각의 바구니에 단어들을 나누어 담고, 해당 바구니에서 클러스터링을 실시하도록 하면 되겠군요.

결말

텍스트가 담긴 여러 포맷의 파일을 입력받을 수 있게 하고 싶었던 지라, 예전 수업시간에 배웠던 Apache Tika를 이용하기로 했습니다. 그래서 자바를 덥썩 물었는데, 자바가 생각보다 좀 느려서 맵더군요. 그래서 Tika를 이용해서 텍스트 추출하는 부분만 자바에게 맡기고, 실제 클러스터링 알고리즘은 C++에게 맡겼습니다. 그리고 PHP로 이 둘을 차례로 실행해서 입력받는 작업을 수행하도록 했지요.

짜잔! 그래서 나온게 이겁니다.

https://lab.bab2min.pe.kr/civciv/ 

Civciv는 터키어로 병아리라는 뜻이라는데, 뭐 좋은 이름 없냐고 후배에게 물었더니 이 프로그램하는게 병아리 감별사가 병아리 구분하는거 같다며 병아리라는 이름을 지어주더군요.

아무 텍스트를 입력하면 아래처럼 유사한 단어끼리 묶어서 통계를 내줍니다. 별도의 형태소 분석기가 들어가지 않았음에도 형태상의 유사성만 가지고 아래와 같은 결과를 보여주네요. 만-족스럽습니다!

Word	N	Similar forms
알고리즘	8	알고리즘, 알고리즘을, 알고리즘들의
시간을	8	시간을, 시간이, 시간은
결과를	8	결과를, 결과로, 결과가
A가	8	A가
의	7	의
소요한다	6	소요한다, 소요하여
데이터는	6	데이터는, 데이터를, 데이터가
분할정복	6	분할정복, 분할정복으로, 분할정복이, 분할정복을, 분할정복의
정렬된	5	정렬된, 정도로
있다	5	있다
수	5	수
posted	4	posted, Post, Posted, post
적용할	4	적용할
하면	4	하면, 하는, 하며
문제를	4	문제를, 문제에, 문제의
A를	4	A를, A라
를	3	를
보면	3	보면
얻을	3	얻을, 얻은

별도의 형태소 분석기를 사용하지 않았다는 말은, 다시 말하자면 어떤 언어에도 사용할 수 있다는 것입니다. 영어나 한국어는 말할것도 없고 단어의 형태가 다양하게 바뀌는 언어들에 대해서 사용해도 그럭저럭한 결과를 얻을 수 있겠죠. (다만 스와힐리어처럼 단어 앞에 접미사가 붙어 단어의 문법적 역할을 바꾸는 경우는 안되겠군요. 첫 글자가 다른 경우는 묶어주지 않으니까요)