[PHP, MySQL] 클러스터링을 이용한 동음이의어 분리

오랜만에 글을 올리네요. 최근 작업한 부분은 도치 색인을 이용해서 만들어진 한국어-라틴어 사전의 내용을 개선하는 일이었습니다. 라틴어-한국어 사전을 편찬하면서 자동으로 생성되는 (라틴어, 한국어) 단어쌍을 뒤집으면 (한국어, 라틴어) 단어쌍이 되겠죠. 이 뒤집힌(도치된) 단어쌍을 모으면 한국어-라틴어 사전이 자동으로 만들어집니다. 문제는 기계적으로 만들어진 사전이다보니, 실제 활용하기에 번거로운점이 많다는 것입니다.

기존 한-라사전의 내용을 예로 들어보겠습니다.

눈

calyx, calycis; gemma, gemmae; oculus, oculī; cilium, ciliī; gena, genae; lūmen, lūminis; ninguis, ninguis; nix, nivis

뜻이 '눈'인 라틴어 단어를 모두 모아놓은 모습입니다. 근데 눈이 하늘에서 내리는 눈인지, 앞을 보게해주는 신체기관인지 알 수 없습니다.

여기서 ninguis, nix는 snow 눈이고, oculus는 eye 눈입니다. 그래서 개선이 시급했지요. 다행히도 위 단어들을 의미 유사도를 바탕으로 클러스터링하면 동음이의어가 서로 분리되지 않을까하는 아이디어가 떠올랐습니다. 여기서 유사도는 영어 뜻풀이를 기반으로 계산되었습니다. 한국어로 똑같이 눈으로 해석되는 말이어도, 영어 뜻풀이는 snow, eye로 다릅니다. 만약 한국어 뜻도 같고, 영어 뜻풀이도 같다면 아예 같은 의미의 단어로 판단해도 되겠죠. 바로 실험해보기로 했죠.

유사도는 이미 유의어 추출(문헌 클러스터링 기술을 이용한 유의어 분류)에서 계산해둔 것을 재활용하겠습니다. 

간단한 알고리즘 소개

N: 전체 어휘의 개수

G: 유사한 어휘들의 인덱스가 담길 배열

S: 어휘 간의 유사도가 담길 2차원 배열(행렬)

T: 최소 유사도값. 이 값보다 유사도가 낮을 경우 유사하지 않은 것으로 간주합니다.

G의 초기값은 [[0], [1], [2], ... [N-1]]으로 설정합니다. 각각 1개의 어휘가 담긴 배열 N개가 있음을 의미합니다.

S[i,j]는 어휘 i가 어휘 j와 유사한 정도를 담으며, 미리 계산된 유사도 데이터베이스에서 가져옵니다. 정의상 S[i,j]는 S[j,i]와 같으므로 j>i인 경우만 저장하도록 하겠습니다.

통합 알고리즘

1. S에서 최대값을 찾아 그 값을 s, 그 인덱스를 i, j에 담습니다.
2. (유사도값 미달로 인한 종료) 만약 s < T이면 알고리즘을 종료하고 G를 결과로 반환합니다.
3. (유사도 행렬 재계산) 클러스터링 알고리즘에 의해 S를 수정합니다.
4. (클러스터 통합) G[i]와 G[j]를 합쳐서 새로운 G[i]로 설정하고, G[j]는 빈 배열로 설정합니다.
5. G의 요소 수가 1보다 크면 1번로 돌아갑니다.

클러스터링 알고리즘(집단 평균 연결 방법)

1. S에서 요소 하나를 가져와 그 값을 t, 그 인덱스를 x, y에 담습니다.
2. (통합되어 재계산이 필요한 어휘인가?) x = j이고 y > i이면 새 유사도값인 u = (S[i,y]*n(G[i]) + t*n(G[j])) / (n(G[i]) + n(G[j]))를 계산하고, S[i,y] = u로 설정합니다.
3. (통합되어 재계산이 필요한 어휘인가?) y = j이고 x < i이면 새 유사도값인 u = (S[x,i]*n(G[i]) + t*n(G[j])) / (n(G[i]) + n(G[j]))를 계산하고, S[x,i] = u로 설정합니다.
4. (통합된 유사도 계수 제거) x = j이거나 y = j이면 S[x, y]를 S에서 제거합니다.
5. 순회하지 않은 S 요소가 남았으면 1번으로 돌아갑니다.

클러스터링 알고리즘(완전 연결 방법)

1. S에서 요소 하나를 가져와 그 값을 t, 그 인덱스를 x, y에 담습니다.
2. (통합되어 재계산이 필요한 어휘인가?) x = j이고 y > i이면 새 유사도값인 u = min(S[i,y], t)를 계산하고, S[i,y] = u로 설정합니다.
3. (통합되어 재계산이 필요한 어휘인가?) y = j이고 x < i이면 새 유사도값인 u = min(S[x,i], t)를 계산하고, S[x,i] = u로 설정합니다.
4. (통합된 유사도 계수 제거) x = j이거나 y = j이면 S[x, y]를 S에서 제거합니다.
5. 순회하지 않은 S 요소가 남았으면 1번으로 돌아갑니다.

클러스터링 알고리즘은 연결기법에 따라 다양하게 선택할 수 있습니다. 여기에서는 두 가지만 제시했는데, 새 유사도값을 계산하는 부분만 바뀐다고 생각하시면 쉽습니다.

가능하면 빠르게 연산을 수행하기 위해 PHP 내장 함수들을 최대한 활용하는 방향으로 코드를 구성했습니다. 유사도 행렬 S도 NxN개의 모든 원소를 담는것이 아니라 값이 0보다 큰 원소만 담도록 했죠. 이는 실제로 값이 0인 원소들이 많이 등장하기 때문입니다.

이제 실제 코드를 보시죠.

function groupCluster($sim, $n, $S) { // group 변수 초기화 $group = array(); for($i = 0; $i < $n; $i++) { $group[] = array($i); } // 클러스터 통합 루프 while(count($group) > 1 && count($sim)) { $maxS = max($sim); // 최대값 maxS가 S보다 작으면 클러스터링을 멈추고 결과를 반환 if($maxS < $S) return array_values($group); // i, j 인덱스를 얻어옴 $maxIJ = array_search($maxS, $sim); $maxI = $maxIJ % $n; $maxJ = (int)($maxIJ / $n); // 유사도 행렬 재계산 mergeSim($sim, $n, $group[$maxI], $group[$maxJ]); // 클러스터 통합 $group[$maxI] = array_merge($group[$maxI], $group[$maxJ]); unset($group[$maxJ]); } return array_values($group); } function mergeSim(&$sim, $n, $g1, $g2) { $cg1 = count($g1); $cg2 = count($g2); foreach($sim as $k=>&$v) { $i = $k % $n; $j = (int)($k / $n); // 통합되어 재계산이 필요한 요소인가 if($i == $g2[0]) { $ov = $sim[$g1[0] + $j*$n]; // 유사도 재계산 if($j > $g1[0]) $sim[$g1[0] + $j*$n] = ($cg1*$ov + $cg2*$v)/($cg1+$cg2); // 통합 완료된 유사도 계수 행렬에서 제거 unset($sim[$k]); } else if($j == $g2[0]) { $ov = $sim[$g1[0] + $i*$n]; // 유사도 재계산 if($i < $g1[0]) $sim[$g1[0] + $i*$n] = ($cg1*$ov + $cg2*$v)/($cg1+$cg2); // 통합 완료된 유사도 계수 행렬에서 제거 unset($sim[$k]); } } }

코드만 보면 머리가 아프니, '가다'라는 뜻으로 쓰일수 있는 라틴어 단어를 가지고 실제로 유사도 클러스터링을 진행해보죠. 위쪽과 왼쪽에는 단어의 ID와 인덱스 넘버가 있고, 각 칸에는 유사도가 들어있습니다. 유사도는 i < j 인 부분만 표시하였고, 0인 부분은 -로 지웠습니다. 유사도가 가장 큰 녀석은 굵게 처리해놓았습니다. 최소 유사도 요구값은 0.2로 설정해보았습니다.

단계1

	0 admeo	1 bacchor	2 badisso	3 cedo	4 concedo	5 congredior	6 curro	7 eo	8 gradior	9 proveho	10 vado2
0 admeo	-	-	-	-	-	0.2847645	-	-	-	-	-
1 bacchor	-	-	-	-	-	-	0.0906024	0.0538119	-	-	-
2 badisso	-	-	-	0.2767627	-	-	0.2981522	0.2573954	0.34399	0.289018	0.374469
3 cedo	-	-	-	-	0.35417	-	0.270063	0.372249	-	0.383329	-
4 concedo	-	-	-	-	-	-	-	-	-	-	-
5 congredior	-	-	-	-	-	-	-	-	-	-	-
6 curro	-	-	-	-	-	-	-	0.1369196	-	0.29124	-
7 eo	-	-	-	-	-	-	-	-	0.1872523	0.2334187	-
8 gradior	-	-	-	-	-	-	-	-	-	0.2133929	0.347079
9 proveho	-	-	-	-	-	-	-	-	-	-	-
10 vado2	-	-	-	-	-	-	-	-	-	-	-

S[3,9]가 0.383329로 가장 크므로, 3과 9를 통합하고 유사도 행렬을 재계산합니다.

단계2

	0 admeo	1 bacchor	2 badisso	3,9 cedo,proveho	4 concedo	5 congredior	6 curro	7 eo	8 gradior	10 vado2
0 admeo	-	-	-	-	-	0.2847645	-	-	-	-
1 bacchor	-	-	-	-	-	-	0.0906024	0.0538119	-	-
2 badisso	-	-	-	0.28289035	-	-	0.2981522	0.2573954	0.34399	0.374469
3,9 cedo,proveho	-	-	-	-	0.35417	-	0.14562	0.11670935	0.10669645	-
4 concedo	-	-	-	-	-	-	-	-	-	-
5 congredior	-	-	-	-	-	-	-	-	-	-
6 curro	-	-	-	-	-	-	-	0.1369196	-	-
7 eo	-	-	-	-	-	-	-	-	0.1872523	-
8 gradior	-	-	-	-	-	-	-	-	-	0.347079
10 vado2	-	-	-	-	-	-	-	-	-	-

S[2,10]이 제일 크므로, 2와 10을 통합.

단계3

	0 admeo	1 bacchor	2,10 badisso,vado2	3,9 cedo,proveho	4 concedo	5 congredior	6 curro	7 eo	8 gradior
0 admeo	-	-	-	-	-	0.2847645	-	-	-
1 bacchor	-	-	-	-	-	-	0.0906024	0.0538119	-
2,10 badisso,vado2	-	-	-	0.28289035	-	-	0.2981522	0.2573954	0.1735395
3,9 cedo,proveho	-	-	-	-	0.35417	-	0.14562	0.11670935	0.10669645
4 concedo	-	-	-	-	-	-	-	-	-
5 congredior	-	-	-	-	-	-	-	-	-
6 curro	-	-	-	-	-	-	-	0.1369196	-
7 eo	-	-	-	-	-	-	-	-	0.1872523
8 gradior	-	-	-	-	-	-	-	-	-

S[{3,9},4]이 제일 크므로, 3,9와 4를 통합.

단계4

	0 admeo	1 bacchor	2,10 badisso,vado2	3,9,4 cedo,proveho,concedo	5 congredior	6 curro	7 eo	8 gradior
0 admeo	-	-	-	-	0.2847645	-	-	-
1 bacchor	-	-	-	-	-	0.0906024	0.0538119	-
2,10 badisso,vado2	-	-	-	0.28289035	-	0.2981522	0.2573954	0.1735395
3,9,4 cedo,proveho,concedo	-	-	-	-	-	0.14562	0.11670935	0.10669645
5 congredior	-	-	-	-	-	-	-	-
6 curro	-	-	-	-	-	-	0.1369196	-
7 eo	-	-	-	-	-	-	-	0.1872523
8 gradior	-	-	-	-	-	-	-	-

S[{2,10}, 6]이 제일 크므로, 2,10과 6을 통합.

단계5

	0 admeo	1 bacchor	2,10,6 badisso,vado2,curro	3,9,4 cedo,proveho,concedo	5 congredior	7 eo	8 gradior
0 admeo	-	-	-	-	0.2847645	-	-
1 bacchor	-	-	0.0302008	-	-	0.0538119	-
2,10,6 badisso,vado2,curro	-	-	-	0.04854	-	0.2172368	0.1735395
3,9,4 cedo,proveho,concedo	-	-	-	-	-	0.11670935	0.10669645
5 congredior	-	-	-	-	-	-	-
7 eo	-	-	-	-	-	-	0.1872523
8 gradior	-	-	-	-	-	-	-

S[0,5]이 제일 크므로, 0와 5을 통합.

단계6

	0,5 admeo,congredior	1 bacchor	2,10,6 badisso,vado2,curro	3,9,4 cedo,proveho,concedo	7 eo	8 gradior
0,5 admeo,congredior	-	-	-	-	-	-
1 bacchor	-	-	0.0302008	-	0.0538119	-
2,10,6 badisso,vado2,curro	-	-	-	0.04854	0.2172368	0.1735395
3,9,4 cedo,proveho,concedo	-	-	-	-	0.11670935	0.10669645
7 eo	-	-	-	-	-	0.1872523
8 gradior	-	-	-	-	-	-

S[{2,10,6}, 7]이 제일 크므로, 2,10,6과 7를 통합.

단계7

	0,5 admeo,congredior	1 bacchor	2,10,6,7 badisso,vado2,curro,eo	3,9,4 cedo,proveho,concedo	8 gradior
0,5 admeo,congredior	-	-	-	-	-
1 bacchor	-	-	0.036103575	-	-
2,10,6,7 badisso,vado2,curro,eo	-	-	-	0.0291773375	0.1769677
3,9,4 cedo,proveho,concedo	-	-	-	-	0.10669645
8 gradior	-	-	-	-	-

S[{2,10,6,7}, 8]이 제일 크지만 그 값이 최소 유사도 요구값인 0.2보다 작으므로 여기에서 클러스터링을 중단하고 결과를 반환합니다. 결과는

{0,5}, {1}, {2,10,6,7}, {3,9,4}, {8}입니다.

그룹별로 비슷한 단어끼리 묶였으면, 이제 묶인 단어군에 적절한 설명을 붙여줘야하겠죠. 이는 한-라 단어쌍에서 가중치를 종합하여 구할 수 있을겁니다. 가중치는 라틴어 사전에서 뜻풀이로 등장하는 순서를 기준으로 계산되었습니다. 사전 갈래뜻풀이를 달 때, 그 단어의 가장 기본적인 의미를 1번으로 하고, 2, 3, 4 등 번호가 커져갈수록 부수적인 갈래뜻이 될거라는 가정이 바탕이 되었습니다. 따라서 의미 번호의 역수를 가중치로 한다면 가장 기본적인 의미일수록 가중치가 커지고, 부수적인 의미일수록 가중치가 낮아질거라는 추정을 해볼 수 있습니다. (물론 실제 실험결과를 통해 검증을 해보아야하는 사실이지만, 그건 여기서 다루기에는 복잡하므로 패스하죠.)

admeo와 congredior가 들어간 단어군을 예로 들어보죠.

kor	lat	n
가다	admeo	1
나아가다	admeo	1
접근하다	admeo	1
다가가다	admeo	1
가다	congredior	1
오다	congredior	1
만나다	congredior	1
접근하다	congredior	1
방문하다	congredior	1
싸우다	congredior	0.5
논쟁하다	congredior	0.5
옹호하다	congredior	0.333333
분투하다	congredior	0.333333

위와 같은 한국어-라틴어 단어쌍이 디비에 들어있습니다. 한국어 단어를 기준으로 묶어서 가중치인 n값이 높은 녀석들을 뽑아봅시다.

kor	SUM(n)
가다	2
접근하다	2
방문하다	1
만나다	1
다가가다	1
오다	1
나아가다	1
논쟁하다	0.5
싸우다	0.5
분투하다	0.333333343267441
옹호하다	0.333333343267441

'가다'는 이미 원래 단어였으므로 제거하고, 다음 순위의 뜻풀이를 보면, "접근하다, 방문하다, 만나다" 등이 있습니다. 따라서 admeo, congredior 단어군에게는 접근하다, 방문하다, 만나다 라는 세부 의미 설명을 덧붙여줄 수 있겠습니다.

이런 식으로 모든 단어군에 의미를 덧붙여서 한-라 사전의 내용을 개선했습니다. 생각보다 PHP로는 시간이 오래 걸렸습니다. (17000개의 표제어를 처리하는데 몇 시간 걸린것으로 기억합니다.) 

개선된 사전 모습 보실까요.

눈

1. (컵, 싹) calyx, calycis; gemma, gemmae; oculus, oculī
2. (뺨, 볼) cilium, ciliī; gena, genae
3. (빛, 눈빛) lūmen, lūminis
4. (백설, 눈보라) ninguis, ninguis; nix, nivis

기존의 모습보다 보기에는 훨씬 좋아졌지만, 여전히 이해할수 없는 설명들이 많습니다. 신체기관이라는 의미의 눈 eye인 oculus에는 컵, 싹이라는 설명이 붙어있고, 뺨, 볼은 눈이랑 무슨 연관이 있는지 모르겠습니다. 아마도 라틴어 사전에 해석된 표제어 데이터가 부족해 잘못된 의미를 기본으로 추정하는 듯합니다. (혹은 기본적인 의미일수록 앞에 나올것이라는 가정이 잘못되었을 수도 있구요.)

위 예제로 나온 '가다' 에 어떻게 의미 설명이 달렸는지 궁금하시다면 여기에서 직접확인해보세요.