문헌 클러스터링 기술을 이용한 유의어 분류(PHP, MySQL)

정보검색론을 공부하면서 예전에 문헌 클러스터링 기법에 대해서 공부한 적이 있습니다. 그 당시에는 이걸 어디 쓸데가 있으려나 반신반의하면서 공부했는데, 드디어 실제로 이 기법을 활용하게 되었네요. 라틴어 사전 작업을 하던 도중 단어 검색이나 번역 작업 등을 할때 사용할 수 있게 유의어(synonym; 비슷한 의미의 단어) 정보를 제공할 수 있으면 좋겠다고 생각했습니다. 문제는 비슷한 의미의 단어를 일일히 수작업으로 추려내기엔 너무 비효율적이고 (심지어 제 군생활 안에 끝나지도 않을 정도로) 오래걸린다는거였습니다. 그러던 중 클러스터링 기술이 문뜩 떠올라 한번 적용해보았는데 생각보다 결과가 깔끔하게 나와서 작업 내용도 정리하고 정보도 공유할겸 오랜만에 포스팅해봅니다.

이 글에 앞서 아래 내용들을 미리 숙지하고 있으면 쉽게 아래 내용들을 이해하실수있을거에요.

텍스트 자동색인

문헌 클러스터링

문헌 클러스터링은 문헌들간의 유사도를 계산해서 유사한 문헌들을 한 덩어리로 묶어주는 작업을 말합니다. 이때 유사도를 계산하기 위해서는 문헌에 속해있는 색인어를 이용합니다. 두 문헌이 같은 색인어를 많이 가지고 있을수록 유사한 문헌이 될 가능성이 높은건 당연하겠죠?

사전 표제어에서 유의어를 추출하는데 이 알고리즘이 이용될 수 있다는 걸 아는건 어렵지 않습니다. 문헌을 사전의 표제어라고 생각하고, 문헌 속 색인어는 표제어의 뜻풀이라고 생각하면 되는 것이지요. 이렇게 해서 사전 표제어에 문헌 클러스터링 알고리즘을 적용할 수 있게 되었습니다.

쉬운 설명을 위해 단어 3개를 뽑아 예를 들어보겠습니다. 비슷해보이지만 조금씩은 다른 의미의 명사 3개가 있습니다.

dictum: 격언, 속담

verbum: 단어, 격언, 말, 언어

lingua: 혀, 언어, 말

이 명사들을 먼저 (표제어, 뜻풀이) 쌍으로 분해해서 나타내 봅시다.

dictum	격언	verbum	단어	lingua	혀
dictum	속담	verbum	격언	lingua	언어
		verbum	말	lingua	말
		verbum	언어

dictum과 verbum이 얼마나 유사한지 계산해보기 위해서는 뜻풀이가 얼마나 일치하는지 확인해보면 됩니다. '격언' 하나만 일치합니다. dictum과 lingua는 일치하는 뜻풀이가 없죠. verbum과 lingua는 '언어', '말' 2개가 일치합니다.

문제는 단순히 일치하는 뜻풀이 갯수만 세면 원치 않는 결과가 나타날 수 있다는 겁니다. 뜻풀이 중 여기저기 자주 등장하는 녀석이 있을 수도 있고, 비중이 중요한 녀석도 있을텐데 모두를 같은 가중치로 계산하면 결과가 왜곡될 수 있다는 거죠. 이쯤에서 TF * IDF가 생각난다면 훌륭한 문헌정보학도라고 할수있겠습니다. TF는 Term Frequency의 약자로, 용어빈도, 즉 색인어가 등장하는 횟수를 가리키며, IDF는 Inverse Document Frequency로 역문헌빈도, 색인어가 등장하는 문헌 횟수의 역수를 가리킵니다. 이 기법을 이용해서 색인어 빈도수에 적절히 가중치를 주어 계산하면 더 고품질의 결과를 얻을 수 있겠죠?

그러면 실제 코딩을 위해 좀더 수학적으로 접근해봅시다.

는 표제어 A의 뜻풀이들이 담긴 집합, 는 표제어 B의 뜻풀이들이 담긴 집합이라고 하고, 는 색인어(TF) i가 A 집합에서 등장하는 횟수, 는 색인어 가중치(IDF)라고 정의합시다. 이제 표제어 A가 표제어 B와 얼마나 유사한지 계산하는 식을 세워봅시다.

표제어 A에 등장하는 색인어 가중치는 위처럼 색인어 빈도와 색인어 가중치의 곱을 모든 i에 대해서 더해서 얻을수 있습니다. 마찬가지로 W(B)도 계산할 수 있겠죠. 그런데 사전의 특징상 뜻풀이로 등장하는 색인어는 한 표제어에 많아 봐야 1개입니다. (상식적으로 dictum의 뜻풀이가 "속담, 속담, 속담, 격언"이면 이상하잖아요?) 따라서 

이고, W(A) 계산식은 더 단순해져서

가 됩니다.

A가 B와 얼마나 일치하는지 계산하기 위해서는 A와 B에 동시에 등장하는 색인어의 비중을 살펴보아야합니다. 즉,

를 계산하면 되겠죠. 동시에 등장하는 색인어가 많을 수록 이 식은 1에 가까워질 것이고, 적을수록 0에 가까워질 것입니다.

또한 W(A)는 집합 B와는 독립적인 계산식이므로, 사전에 계산해둘수 있고, 집합 B만 바꿔가면서 여러 표제어들과 유사성을 비교할 수 있겠죠.

역문헌빈도 가중치는 아래와 같이 계산하도록 할게요. (왜 log를 쓰는지 모르겠는데, 다들 log많이 쓰길래 저도 썼습니다. log없이 그냥 역수로 계산하면 고빈도 색인어의 가중치가 급격하게 떨어지기 때문일거라고 추측해봅니다.)

앞서 말했듯 표제어에 등장하는 색인어 빈도는 0이거나 1이기 때문에 전체 표제어 수를 세면, 그게 당연히 문헌빈도와 일치할겁니다.

빈도수에 1을 더해준건 빈도수가 0일 경우 로그가 계산이 불가능해지기 때문에 그냥 더해준겁니다.

자, 이제 실제로 PHP와 MySQL을 이용해서 코딩을 해보지요.

먼저 SQL에서 사용할 테이블을 간단하게 소개합니다.

테이블 word : 사전 내용이 들어있는 테이블입니다.

pid	eng	class	syn
표제어 id	표제어 뜻풀이	표제어 품사	유의어 분석이 완료됐는지 체크하기 위한 필드

테이블 le : (표제어, 뜻풀이) 쌍을 저장할 임시 테이블입니다.

l	e
표제어 id	표제어 뜻풀이

테이블 lec : 뜻풀이별 색인어 가중치를 저장할 임시 테이블입니다.

e	n
표제어 뜻풀이	가중치

테이블 tsyn : 표제어별 색인어 목록이 저장될 임시 테이블입니다.

l	e	n
표제어 id	색인어	가중치

테이블 syn : 표제어별 유의어 분석 결과가 저장될 결과 테이블입니다.

pid	l	n
표제어 id	유의어 id	유사도

준비작업 개요는 다음과 같습니다.

1. word 테이블에서 데이터를 가져와 eng 필드를 잘게 쪼개 색인어로 만든다.

2. 1에서 만들어진 데이터를 le 테이블에 (표제어, 색인어) 쌍으로 넣는다.

3. 2에서 만들어진 데이터에서 색인어별로 갯수를 세어 색인어별 IDF를 계산해 lec 테이블에 넣는다.

SQL 알못을 위한 SQL 해설

TRUNCATE TABLE `le`

: le 테이블을 꺠끗이 비워줍니다.

SELECT `eng`, `pid` FROM `word`

: word 테이블에서 모든 eng, pid 필드를 가져옵니다.

INSERT INTO `le` VALUES ('dictum', '격언'), ('dictum', '속담') ...

: le 테이블에 (dictum, 격언), (dictum, 속담) 데이터를 삽입합니다. 쉼표를 붙여서 여러개 더 삽입할 수도 있습니다.

INSERT INTO `lec` SELECT `e`, 1/LOG(COUNT(`e`)+1) FROM `le` GROUP BY  `e`

: le 테이블의 데이터를 같은 e끼리 묶어서 그 e와 1/log(e의 갯수 + 1) 한 결과를 lec 테이블에 넣습니다.

function initData() { $stoplist = array('alternative', 'form', 'pertaining', 'for', 'out', 'with', 'the', 'from', 'and', 'off', 'that', 'having'); // 불용어 목록입니다. 여기있는 단어는 분석에서 아예 제외시켜버립니다. $s = "TRUNCATE TABLE `le`"; $result = mysql_query($s); $s = "SELECT `eng`, `pid` FROM `word`"; $result = mysql_query($s); while($row = mysql_fetch_assoc($result)) { $str = preg_replace('/\([^)]*\)|\[\[[^\]]+\]\]/', '', $row['eng']); // ()나 [] 안에 있는 텍스트를 지워버립니다. 분석에 필요없으니까요 $l = explode('//', $str); // 갈래뜻을 구분하는데 '//'기호를 사용하고 있어서... $data = array(); foreach($l as $m) { $ms = preg_split("/[,;!?. '-]/", $m); // 뜻풀이를 잘게잘게 쪼개서 색인어 목록을 만듭니다. foreach($ms as $mean) { $tt = strtolower(trim($mean)); // 소문자로 통일하고 if(in_array($tt, $stoplist)) continue; // 불용어일경우 패스 if(strlen($tt) > 2) $data[$tt] = true; /* 3글자 이상부터만 취급합니다. 2글자 이하인경우는 쓸모없는 단어가 많아서.. (a, an, to, of, or, if, in ...) */ } } $s = "INSERT INTO `le` VALUES "; foreach($data as $k => $v) { $s .= "('".$row['pid']."', '".$k."'),"; } mysql_query(substr($s, 0, -1)); // (표제어, 색인어) 쌍을 테이블에 삽입 } $s = "TRUNCATE TABLE `lec`"; $result = mysql_query($s); $s = "INSERT INTO `lec` SELECT `e`, 1/LOG(COUNT(`e`)+1) FROM `le` GROUP BY `e`"; $result = mysql_query($s); // 만든 le테이블을 이용해서 색인어별 가중치를 계산해서 삽입 }

자, 이렇게 해서 먼저 유의어 분류를 위한 밑작업을 완료했습니다. 이제 이 가중치 테이블을 이용해서 쉽게 유의어를 추출해낼수 있습니다!

4. word에서 표제어 하나를 가져온다.

5. le테이블에서 word의 색인어를 찾고, 이 색인어를 가지고 있는 다른 유의어 후보을 찾는다.

6. 5에서 얻은 결과에 lec에 저장해둔 색인어별 가중치를 합쳐 tsyn 테이블에 넣는다.

7. tsyn 테이블에서 유의어 후보별로 가중치 필드의 총합을 계산해 그 값이 특정 값보다 크면 syn 테이블에 넣는다.

이 짓을 모든 표제어에 대해서 반복하면 됩니다. 

SQL 알못을 위한 SQL 해설

SELECT GROUP_CONCAT(CONCAT('\'', e, '\'') SEPARATOR ',') FROM `le` WHERE l = 'dictum'

: le 테이블에서 l이 dictum인 모든 데이터에 대해 e에 앞뒤에 따옴표를 붙인 녀석들을 모두 합친 결과를 가져옵니다.

즉 '격언', '속담' 과 같은 형태로 결과물이 나옵니다.

INSERT INTO `tsyn` SELECT `le`.`e`, `le`.`l`, `lec`.`n` FROM `le`, `lec`, `word` WHERE `le`.`e` IN ('격언', '속담') AND `le`.`e` = `lec`.`e` AND `word`.`pid` = `le`.l AND `word`.`class` LIKE 'n%'

: le 테이블에서 e가 '격언'이거나 '속담'이고, 그 e가 lec의 e와도 같으며, l의 품사(word.class)가 n인 모든 자료를 가져와 tsyn에 넣습니다. (좀 많이 복잡하죠? 찬찬히 살펴보면 어려운거 없습니다.)

SELECT SUM(`n`) FROM `tsyn` WHERE `l` = 'dictum'

: tsyn 테이블에서 l이 dictum인 녀석들의 모든 가중치(n)를 더한 값을 가져옵니다.

INSERT INTO `syn` (SELECT 'dictum', `l`, SUM(`n`) / (W+1) FROM `tsyn` WHERE `l` <> 'dictum' GROUP BY `l` HAVING SUM(`n`) / (W+1) > 0.2 ORDER BY SUM(`n`) DESC)

: tsyn 테이블을 같은 l끼리 묶어서 그 l이 dictum이 아니고, 그 그룹에 속한 모든 가중치의 합(SUM(n))을 (W+1)로 나눈값이 0.2 이상인 녀석들에 대해 syn 테이블에 dictum과 l(유의어 후보), SUM(n) / (W+1) (:유사도 계수)를 넣습니다. 이때 넣는 순서는 유사도 계수가 큰 순서로.

function calcSim() { $s = "SELECT `pid`, `class` FROM `word` WHERE `syn` < 0"; // 유의어 분류 작업이 안된 syn이 음수인 녀석들을 모두 뽑아옵니다. $br= mysql_query($s); while($r = mysql_fetch_assoc($br)) { $pid = $r['pid']; $cl= substr($r['class'], 0, 1); // 품사가 같은 녀석들만 유의어로 고를거에요. 품사의 첫 글자를 저장해둡니다. $s = "TRUNCATE TABLE `tsyn`"; $result = mysql_query($s); // 임시 테이블 깨끗이 비우고 $s = "SELECT GROUP_CONCAT(CONCAT('\\'', e, '\\'') SEPARATOR ',') FROM `le` WHERE l = '".$pid."'"; $result = mysql_query($s); $row = mysql_fetch_array($result); // 동일한 색인어를 가진 표제어 목록을 가져옵니다. 이 값은 바로 다음 쿼리에서 사용됩니다. $s = "INSERT INTO `tsyn` SELECT `le`.`e`, `le`.`l`, `lec`.`n` FROM `le`, `lec`, `word` WHERE `le`.`e` IN (" . $row[0] . ") AND `le`.`e` = `lec`.`e` AND `word`.`pid` = `le`.l AND `word`.`class` LIKE '$cl%'"; $result = mysql_query($s); // 가져온 색인어 목록중 겹치는 걸 가지고 있는 모든 표제어 중 품사가 같은 녀석들에 대해 tsyn 테이블에 쑤셔넣고 $s = "SELECT SUM(`n`) FROM `tsyn` WHERE `l` = '".$pid."'"; $result = mysql_query($s); $w = mysql_fetch_array($result); // W(A) 값을 계산합니다. (표제어가 pid인 모든 가중치의 합을 구함) $s = "INSERT INTO `syn` (SELECT '".$pid."', `l`, SUM(`n`) / ".($w[0]+1) ." FROM `tsyn` WHERE `l` <> '".$pid."' GROUP BY `l` HAVING SUM(`n`) / ".($w[0]+1)." > 0.2 ORDER BY SUM(`n`) DESC)"; $result = mysql_query($s); // 유의어 후보들의 가중치를 계산합니다. W(A)에 1을 더한이유는 아래에서 설명. 유사도가 0.2 이상인 녀석들은 유의어 목록에 삽입 $s = "UPDATE`word` SET `syn` = 0 WHERE `pid` = '".$pid."' LIMIT 1"; $result = mysql_query($s); // 유의어 처리가 끝났으니, syn을 0으로 설정하여 처리가 끝났다고 표시. } }

처음 

를 유사도로 해서 계산해본 결과 생각보다 품질이 좋지 못했습니다. 뜻풀이가 적은 표제어 일수록 W(A)값이 작아지므로, 공통으로 존재하는 색인어가 1, 2개만 있어도 바로 유의어로 분류되어버리더라구요. (심지어 공유하는 색인어가 have, make 처럼 흔한 녀석인데도...) 역으로 뜻풀이가 다양한 표제어는 W(A)가 커지는데 상대적으로 W(AnB)가 작을 경우 유의어인데도 유의어가 아니라고 분류되는 경우도 있었습니다...

그래서 

처럼 분모에 상수항을 넣어서 분모가 한없이 작아지는 경우를 막고, 분모를 키운만큼 threshold 값을 줄여서 유의어 분류 품질을 향상시켰습니다.

PHP는 느려터져서 이런 대규모 작업은 어려울거라고 생각했었는데, 대규모 처리는 MySQL에게 적절히 떠넘긴 결과 2만여개의 표제어에 대해 유의어 분류 작업을 시행하는데 1분도 걸리지 않아 끝나버렸습니다... 생각보다 나쁘지 않군요. (물론 코딩하는데 몇십분이 걸리긴했지만)

자동색인이나 클러스터링 작업의 경우 처리보다 중요한 것은 품질 검증입니다. 과연 제대로 분류가 되었는지 확인해봐야겠죠. 이때 필요한 것은 사람이 직접 분류한 결과물입니다. 수작업으로 분류한 결과와 자동으로 분류한 결과가 얼마나 일치하는지를 확인해서 품질을 검증하는거죠. 그런데 문제는 사지방 시간이 넉넉하지 않아서 제대로된 품질검증을 할 시간이 없었다는거...

그러니 야비하지만 품질 검증은 이용자에게 떠넘기는걸로.

유의어 분류 결과물을 보시죠.

http://latina.bab2min.pe.kr/xe/lk?pid=femina

femina(여성)의 유의어 : mulier(여성) puella(소녀) nūpta(신부) mātrōna(부인, 아내) marīta(결혼한 여성) sexus(성, 성별) genus(성, 성별)

http://latina.bab2min.pe.kr/xe/lk?pid=accedo

accedo(다가가다)의 유의어 : attingo(접근하다, 나아가다, 도착하다)

추가 내용이 있습니다.

눈치 빠른분들은 아까 아셨겠지만, 여기서 사용한 유사도 계산방식은 비대칭적입니다. 즉 A가 B와 유사한 정도랑, B가 A와 유사한 정도가 다르다는거죠. 대칭적 결과를 원한다면

와 같은 식을 이용해도 되겠네요. 사실 이걸 쓰려고도 고민했었지만, 품질이 크게 달라지지는 않아서...

유의어와 비유의어를 가리는 유사도 값 기준을 정하는것도 어려운 일입니다. 이 기준이 너무 높으면 유의어인 녀석들도 비유의어로 분류될 것이고, 낮으면 비유의어가 유의어로 분류되겠죠. 제가 정한 0.2라는 값은 유사도 계산을 미리 해보고 잘못된 결과가 너무 많이 나오지 않는 적절한 값을 경험적으로 찾은것입니다.

그리고 문헌에서 색인어를 추출할때 Stemming을 해주면 더욱 고품질의 결과를 얻을수 있습니다. (Stemming: 어간 추출, fly, flies, flied 등 다 같은 단어지만 굴절 형태의 차이때문에 다른 색인어로 분류되는걸 막기 위해 어간을 찾아주는것.) Stemming 구현은 클러스터링 주제를 넘어서서, 언어학적 내용이 들어가므로 여기서는 다루지 않았습니다.

곰곰히 TF*IDF 유사도를 이용한 클러스터링은 굉장히 쓸모가 많은거 같아요. 포스팅을 작성하면서 떠오른 것만 적어봐도

문헌	문헌	사전 표제어	SNS 계정	SNS 계정
색인 타겟	색인어	사전 뜻풀이	친구 목록	취미, 좋아하는 것들
클러스터링 결과	유사 문헌 분류	유의어 추출	알수도 있는 친구 (공유하는 친구가 많을 수록 아는 사람일 가능성이 높은건 당연지사.)	취향이 비슷한 사람

문헌/색인 타겟에 문헌과 색인어 말고 다른 것들을 넣는다면 이렇게 다양한 용도로 사용할수 있을거같아요! 페북의 알수도 있는 친구 기능이 정확히 어떤 알고리즘을 쓰는진 모르겠지만, 클러스터링 기법을 일부 쓰고 있는건 확실합니다.

이런 짓도 가능하죠.

한자를 유사도로 클러스터링 (예전에 한자 공부하다 말고 헷갈리는 한자들 집중적으로 공부하려고 비슷하게 생긴 한자를 뽑아낸적이 있습니다. 이때도 클러스터링 기법을 사용했죠.)

유의어 추출이 기계적으로 어느정도 가능하다는걸 확인했으니, 시간이 나면 국립국어원에서 국어사전 데이터 가져와서 한국어 유의어 목록좀 뽑아놔야겠습니다. 한국어-라틴어 사전에 한국어 표제어가 적다보니 검색에 실패하는경우가 잦아서, 유의어 기반 검색어 추천 기능을 넣으면 좋을거같거든요.

또한 비슷한 기법을 응용해서 동음이의어 구분 기능도 할수 있을거같아요! 성공하면 또 포스팅 올리도록 하겠습니다.