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

Posted by 적분 ∫2tdt=t²+c
2017.02.20 21:49 그냥 공부

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


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


PageRank 소개

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

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

그래프로 그리면 위와 같은 모양이 될 겁니다. 먼저 모든 정점에 1의 가중치를 줍니다.


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

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

마찬가지로 B의 가중치도 1이었는데, A, D에게 0.5씩 넘겨줍니다.

C는 D에게만 연결되어있으므로 D에게 1 전체를 넘겨줍니다.

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


정점의 새로운 가중치 값은 이웃으로부터 넘겨받은 가중치들의 합이 됩니다. 

A는 B로부터 0.5를 받았고, D로부터 0.333을 받았으므로 0.833이 되는거죠.

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


더보기

계속 반복하다보면 가중치들이 일정한 값으로 수렴하는 걸 확인할 수 있습니다. 수학자들이 위와 같은 계산을 반복하면 수렴한다는 것을 증명해놓았으므로 믿고 사용하면 됩니다.

최종적으로 A, B는 1, C는 0.5, D는 1.5의 가중치를 갖게 됩니다. 이 값이 각각의 정점의 페이지랭크값이 됩니다. D가 제일 중요한 정점이므로 제일 높은 랭크값이 나왔습니다. 랜덤서퍼모델(Random Suffer Model)이라고 해서 간선을 따르지 않고 임의의 정점으로 넘어가는 가중치를 주기도 하는데, 이는 크게 중요하지 않고 간단하므로 설명을 생략했습니다.


위에서는 계산 편의를 위해 모든 점의 가중치를 1로 두고 시작했지만, 실제 이용에서는 1/n으로 두어 모든 점의 가중치 합이 1이 되도록 하는 편입니다.


페이지 랭크의 장점은 정점 간 연결상태를 가지고 쉽게 중요한 정점을 계산해 낼 수 있다는 것입니다. (구글 검색엔진이 강력한 이유 중의 하나기도 하지요.) 페이지 랭크는 정점과 간선을 가지는 그래프라면 어떤 것에도 적용할 수 있는 알고리즘이기 때문에 다른 곳에도 그대로 사용할 수 있는데요, 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의 성능을 살필 수 있게 해놓았습니다.


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


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


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


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

저작자 표시 비영리 동일 조건 변경 허락
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
이 댓글을 비밀 댓글로
  1. 안녕하세요 텍스트랭크를 공부하고 있는 학생입니다.
    특히 제가 한글문서에서 키워드 추출 공부를 하고 있는데 링크를 걸어주신 논문도 보고 했지만
    텍스트랭크를 이용해서 키워드 추출하는 코드를 짜는데 실패했습니다..ㅠㅠ

    혹시 가능하시면 깃허브에 키워드 추출에 대한 소스코드도 올려주실 수 있으신지요....
    • 올리기로 마음먹어놓고선 바빠서 계속 못 올리고 있었네요.
      깃헙에 올릴만큼 어마어마한 코드는 아니라서... 잘 정리해서 블로그에 올리도록 할게요.
    • Cloudy
    • 2017.05.27 11:41 신고
    우와... 쩌...쩐다!!

    죽여주는군요. 이런게 세상에 있었구나... 전혀 모르고 있었습니다.

티스토리 툴바