TextRank 기법을 이용한 핵심 어구 추출 및 텍스트 요약

훌륭한 알고리즘이라고 꼭 다 복잡하거나 이해하기 어려운건 아닙니다. 오히려 정말 단순한 절차로 큰일을 해내는게 진짜 훌륭한 알고리즘이라고 할 수 있을텐데요, TextRank (또는 PageRank)가 바로 그런 알고리즘인듯 합니다.

구글을 만든 알고리즘으로 널리 알려진 페이지 랭크는 매우 단순한 반복 계산을 통해서 각 페이지의 중요도를 매깁니다. 알고나면 단순한 알고리즘이지만 처음 이를 고안해내기는 정말 어려웠을 겁니다. 여기서는 간략하게 페이지 랭크 알고리즘을 소개하면서, 이를 텍스트에 응용한 텍스트 랭크를 설명하도록 하겠습니다.

PageRank 소개

페이지 랭크는 각각의 페이지를 정점(Node)으로, 페이지와 페이지를 연결하는 링크를 간선(Edge)으로하여 만들어진 그래프를 대상으로 하는 알고리즘입니다. 웹 페이지의 링크는 방향성이 있지만(A -> B로 링크가 걸려있다고 해서 꼭 B->A 인것은 아니기 때문이죠) 설명의 단순화를 위해 여기서는 방향성이 없다고 가정하겠습니다. (즉 A->B이면 B->A라고 가정)

(예전 글은 오해하기 쉽게 쓰여있었다고 판단되어 2019.07.26에 다음 부분을 수정하여 다시 작성하였음을 알리는 바입니다.)

A, B, C, D 4개의 페이지가 있고, A-B, A-D, B-C, B-D, C-B 가 연결되어 있다고 합시다.

그래프로 그리면 위와 같은 모양이 될 겁니다. 먼저 모든 정점에 균등하게 1의 가중치를 나눠줍니다. 각각의 정점은 0.25씩을 나눠받게 됩니다.

다음 단계로 각 정점이 가지고 있는 가중치를 연결된 이웃에게 나눠줍니다. 

A의 가중치는 0.25이었죠. B와 D에게 연결되어있으므로 각각 0.125, 0.125씩 넘겨줍니다.

마찬가지로 B의 가중치도 0.25이었는데, A, D에게 0.125씩 넘겨줍니다. (그림에선 생략)

C는 D에게만 연결되어있으므로 D에게 0.25 전체를 넘겨줍니다. (그림에선 생략)

D는 A, B, C에게 연결되어있으므로 0.083 씩 각각 넘겨줍니다.

정점의 새로운 가중치 값은 이웃으로부터 넘겨받은 가중치들의 합과 각각의 정점을 임의로 선택할 확률을 합하여 계산합니다. 이를 랜덤서퍼모형(Random Surfer Model)이라고 합니다. 보통 15% 확률로 임의의 정점을 선택한다고 설정합니다. 

B의 예시를 들어봅시다. B는 A로부터 0.125를 받고, D로부터 0.083을 받습니다. 따라서 0.125 + 0.083인 0.208이 그 가중치 값이 되어야 하지만, 여기에 랜덤 서퍼를 추가합니다. 기존의 0.208에는 85%를 곱해주고, 정점 B가 임의로 선택될 확률인 0.25에 15% 곱한 값을 더해줍니다.

(0.125 + 0.083) * 0.85 + 0.25 * 0.15 => 0.214

따라서 B의 새로운 가중치는 0.214가 됩니다.

나머지 정점에 대해서도 마찬가지로 계산을 해서 모든 정점의 가중치를 업데이트합니다.

그러면 새로운 가중치는 위와 같이 바뀝니다. 이 과정을 수렴할 때까지 계속 반복합니다.

이 과정을 반복합니다. (2회 반복)

또 반복합니다. (3회 반복)

4회 반복

계속 반복하다보면 가중치들이 일정한 값으로 빠르게 수렴하는 걸 확인할 수 있습니다. 

최종적으로 A, B는 0.245, C는 0.139, D는 0.371의 가중치를 갖게 됩니다. 이 값이 각각의 정점의 페이지랭크값이 됩니다. D가 제일 높은 랭크값이 나왔으므로 제일 중요한 정점이라고 판단할 수 있습니다. 실제로 네트워크 상에서도 A, B, C가 모두 D를 거쳐서 연결되는 걸 보면 D가 핵심이 맞는듯 합니다. 본 예시에서는 간단한 설명을 위해 방향성이 없는 경우를 예로 들었지만 실제로는 방향성이 있는 그래프에 대해서도 사용할 수 있고 아주 잘 작동합니다.

페이지 랭크의 장점은 정점 간 연결상태를 가지고 쉽게 중요한 정점을 계산해 낼 수 있다는 것입니다. (구글 검색엔진이 강력한 이유 중의 하나기도 하지요.) 페이지 랭크는 정점과 간선을 가지는 그래프라면 어떤 것에도 적용할 수 있는 알고리즘이기 때문에 다른 곳에도 그대로 사용할 수 있는데요, 2004년에 이를 텍스트 처리에 사용할 생각을 한 사람이 나타났습니다. Rada Mihalcea와 Paul Tarau였구요, 그들의 논문은 여기에서 확인할 수 있습니다. https://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf

위 논문에 제시된 알고리즘을 한국어 텍스트를 대상으로 직접 구현해 보고 어느정도의 성능이 나오는지 확인해보기로 했어요.

PageRank를 텍스트에 적용한 TextRank

앞에서 설명했다시피 페이지 랭크는 그래프를 대상으로 하는 알고리즘입니다. 그렇기 때문에 텍스트에서 정점이 될만한 단위(text unit)를 뽑아내고, 이 단위들끼리 어떻게 연결이 되는지를 지정해 줄 수만 있다면, 여기에도 PageRank를 적용할 수 있겠죠. 논문에서 제시한 텍스트 단위에는 크게 단어와 문장이 있습니다.

텍스트 단위로써의 단어

각각의 단어를 정점으로 잡고, 한 문장 내에서 같이 등장하는 동시 출현 빈도를 가지고 간선을 구축할 수 있습니다. 이 경우 텍스트 랭크 값은 각 단어의 중요도를 표현하게 되므로, 중요도가 높은 단어를 추출하게 되면 주요 키워드 추출(Keyword Extraction)이 됩니다.

텍스트 단위로써의 문장

단위를 더 크게 잡아서 각각의 문장을 정점으로 잡고, 문장 간의 유사도를 가지고 간선을 구축할 수도 있겠죠. 이 경우 텍스트 랭크 값은 각 문장의 중요도를 표현하게 됩니다. 중요도가 높은 문장을 추려내서 새로운 글을 만들게 되며 이는 텍스트 요약(Text Summarization)이 됩니다.

이를 위해서 논문의 저자는 페이지랭크 알고리즘을 조금 확장했는데요, 간선의 가중치를 다르게 매길 수 있게 한 것이죠. 이 구현 역시 매우 간단합니다. 

한국어 텍스트에 적용해보기

한국어 텍스트에 적용하기 위해서 먼저 형태소 분석 작업이 필요합니다. 조사나 어미 등 불용어를 제거하고 명사 / 동사 / 형용사만 남기고, 단어 거리가 5이하인 경우를 동시 출현 빈도로 카운팅하였습니다. 이렇게 만들어진 그래프를 대상으로 TextRank 값을 구해봤습니다.

테스트에 사용한 텍스트는 위키백과 문서의 외계 행성 항목입니다.

단어	TR	TF		단어	TR	TF
행성	0.089849	80		결과	0.008138	6
외계	0.026183	24		방법	0.007693	6
질량	0.017231	13		배	0.007574	4
발견	0.016848	18		경우	0.00746	6
궤도	0.014767	12		왜성	0.007317	6
항성	0.014466	12		따르다	0.006874	6
대부분	0.013122	11		천체	0.006789	5
관측	0.011835	9		가능	0.006524	4
돌다	0.011573	12		생명체	0.006251	4
지구	0.010591	8		가깝	0.006164	6
존재	0.01043	8		수	0.006035	3
가스	0.009728	9		목성	0.006027	5
별	0.009624	8		같다	0.005822	3
작다	0.009568	8		가벼운	0.005665	3
무겁다	0.009263	9		실제	0.005562	4

TF는 단어 빈도, TR은 TextRank값입니다. 표에서 볼수 있듯이 자주 등장하는 단어일수록 TR 값 역시 높지만 둘이 완전 일치하지는 않는다는 것을 알 수 있습니다. 근데 키워드로 뽑아낼 어구가 토큰화 과정에서 단어별로 쪼개져 버렸습니다. '외계 행성'이 '외계'와 '행성'으로 나눠져 나오기보다는 하나로 묶여 나오는게 좋겠죠. 그렇기 때문에 연속해서 같이 등장하는 단어는 합쳐줄 필요가 있습니다. 이 부분은 논문에 제대로 설명되어 있지 않아서, 적당히 제 맘대로 만들어 보았습니다.

어떤 단어가 어떻게 같이 등장하는지를 확인하기 위해서 window 크기를 1로 잡고선 PMI를 계산하기로 했습니다. PMI가 높을수록 같이 등장할 확률이 높은거니깐, 높은 값을 가진 녀석들을 하나로 합쳐주면 되겠죠. PMI가 낮은 값들은 제거해서 단어쌍을 추려내니 다음과 같은 결과가 나왔습니다.

앞 단어	뒷 단어	PMI
수	배	5.493061
존재	가능	4.512232
질량	수	4.314406
가벼운	지구	4.106767
지구	질량	4.026724
실제	지구	3.819085
실제	질량	3.333577
관측	결과	3.295837
발견	방법	3.295837
가스	행성	2.902794
외계	행성	2.815783
외계	생명체	2.720473
대부분	항성	2.402019
외계	가스	1.909543
가벼운	행성	1.804182
경우	행성	1.804182
행성	대부분	1.198046
행성	발견	0.012423

단어열을 합쳐서 어구를 만들기 위해 한 번 체인을 이어봅시다. 

'외계 행성 대부분'을 키워드로 해야 할지, '외계 행성'을 키워드로 해야할지, '행성 대부분'을 키워드로 해야할지 고민이군요. 체인으로 이어지는 단어를 다 붙인다고 좋은 키워드가 되는건 아닐테니깐, 적절한 지점에서 끊어주는게 필요합니다. 정점 안에는 TextRank값, 간선에는 PMI값을 넣었는데, 이를 이용해 좋은 키워드 후보를 계산해봅시다.

제가 선택한 식은

TextRank값들의 기하평균 * PMI값들의 산술평균 * 경로 길이 였습니다. (이론적인 바탕이 있는 것도, 실험적인 검증이 있는것도 아니어서 좀더 살펴봐야할거 같긴 합니다.)

이렇게 계산할 경우 외계-행성이 0.27로 외계-행성-대부분(0.18)보다 높게 나오므로, 외계-행성까지만 연결하여 키워드 어구를 만들어냅니다. 마찬가지로 지구-질량(0.11)이 지구-질량-수 나 질량-수 등등 나머지 경로보다 높게 나오므로 지구-질량을 키워드 어구로 선정하는 것이지요.

비슷하게 중요 문장을 추출하는 것도 할 수 있습니다. 이 경우는 좀더 간단합니다. 단어를 묶어주는 작업 같은건 필요없고, 문장 간 유사도 계산만 하면 되니깐요.

문장번호	TR	문장 내용
49	0.033228	발견된 행성들 대부분의 궤도는 크게 찌그러져 있다.
36	0.031045	적지 않은 행성들은 목성보다도 훨씬 무겁다.
14	0.029547	갈색 왜성을 도는 외계 행성들도 있으며 어떤 항성에도 속박되지 않고 우주를 떠도는 행성도 있다.
44	0.027747	시선속도법은 작은 궤도를 도는 행성들을 보다 잘 찾아낸다.
13	0.026234	최근 지구와 비슷하거나 작은 질량의 행성들도 발견되고 있으며 이들 중 일부는 질량 외의 여러 속성이 지구와 비슷한 것도 있다.
3	0.026126	발견된 외계 행성들 중 지구에서 가장 가까운 것은 프록시마 b이다.
34	0.026114	지금까지 발견된 외계 행성 대부분은 목성 또는 그 이상으로 매우 무거운 질량을 지녔다.
11	0.025895	단지 무거운 행성들은 쉽게 눈에 띄기 때문이며 선택 편향의 결과이다.
0	0.024962	외계 행성 또는 계외 행성은 태양계 밖의 행성으로, 태양이 아닌 다른 항성 주위를 공전하고 있는 행성이다.
38	0.024328	지금까지 개발된 발견 방법으로는 작고 가벼운 행성보다는 무겁고 덩치 큰 행성들을 발견하기가 훨씬 쉽다.
1	0.024123	지금까지 1800개가 넘는 외계 행성이 발견되었으며 모두 우리 은하 내에 있다.

문장 간 유사도를 간선으로 그래프를 구축한뒤 텍스트 랭크를 계산한 결과입니다. (상위 20%) 이걸 순서대로 정렬하여 합치면 초보적이지만 텍스트 요약을 수행한 결과가 됩니다.

외계 행성 또는 계외 행성은 태양계 밖의 행성으로, 태양이 아닌 다른 항성 주위를 공전하고 있는 행성이다. 지금까지 1800개가 넘는 외계 행성이 발견되었으며 모두 우리 은하 내에 있다. 발견된 외계 행성들 중 지구에서 가장 가까운 것은 프록시마 b이다. 단지 무거운 행성들은 쉽게 눈에 띄기 때문이며 선택 편향의 결과이다. 최근 지구와 비슷하거나 작은 질량의 행성들도 발견되고 있으며 이들 중 일부는 질량 외의 여러 속성이 지구와 비슷한 것도 있다. 갈색 왜성을 도는 외계 행성들도 있으며 어떤 항성에도 속박되지 않고 우주를 떠도는 행성도 있다. 지금까지 발견된 외계 행성 대부분은 목성 또는 그 이상으로 매우 무거운 질량을 지녔다. 적지 않은 행성들은 목성보다도 훨씬 무겁다. 지금까지 개발된 발견 방법으로는 작고 가벼운 행성보다는 무겁고 덩치 큰 행성들을 발견하기가 훨씬 쉽다. 시선속도법은 작은 궤도를 도는 행성들을 보다 잘 찾아낸다. 발견된 행성들 대부분의 궤도는 크게 찌그러져 있다.

<매우 어설프지만, 나름대로 중요한 문장들만 뽑혀있습니다.>

직접 실험해 볼 수 있도록 Python3로 코드를 작성하여 웹 페이지에서 서비스하고 있으니, 직접 테스트해보시길 바랍니다. Komoran 형태소 분석기를 사용하였고, 기타 전처리는 최소화하여 TextRank의 성능을 살필 수 있게 해놓았습니다.

찾아보니 같은 기법을 이용해서 세줄요약기를 만든 분이 계시더라구요. 개발기를 링크해드리니 참고해보시면 좋을듯 합니다.

글이 길어지는 관계로 구현 코드는 나중에 따로 올리도록 할게요!

==============================

코드는 이 게시물에서 확인가능합니다.