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의 성능을 살필 수 있게 해놓았습니다.


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


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


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


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

이 댓글을 비밀 댓글로
  1. 안녕하세요 텍스트랭크를 공부하고 있는 학생입니다.
    특히 제가 한글문서에서 키워드 추출 공부를 하고 있는데 링크를 걸어주신 논문도 보고 했지만
    텍스트랭크를 이용해서 키워드 추출하는 코드를 짜는데 실패했습니다..ㅠㅠ

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

    죽여주는군요. 이런게 세상에 있었구나... 전혀 모르고 있었습니다.
  2. 윈도우 사이즈를 1보다 크게 하고 PMI를 계산할 수도 있나요?

    저는 이 단어가 나왔을 때 뒤로 3개정도의 단어가 나오도록 하고 싶은데 혹시 그런 것이 가능한지 궁금합니다.
    • 네 당연히 가능합니다. 3으로 잡으시면 해당 단어 주변의 3개(대칭일 경우 총 6개, 뒷쪽만 볼경우 3개)를 사용하여 PMI를 계산할 수 있죠.
      다만 이는 동시출현 카운트를 세는 단위가 주변 3 단어라는 것이지, 결국 PMI 계산시에는 단어쌍 별로 (즉, 단어와 단어) 계산이 진행됩니다.
      그게 아니라 혹여나 연속된 3단어 이상의 PMI를 구하고 싶으신 거라면 다변수
      상호정보량을 사용하셔야 됩니다. 이에 대해서는
      http://bab2min.tistory.com/574 포스팅을 참조하시면 되겠습니다.
    • 답변 너무 감사드립니다. 예전 LDA 글을 보고도 이해를 얻었었는데 이번 Textrank 또한 큰 이해가 되었습니다.

      제가 하고 싶은 것에 대해 간략하게 설명드리고 가능한 작업인지 여쭙고 싶습니다. 시간 되시면 답변해주시면 감사하겠습니다.

      감성분석에 있어서 키워드를 서비스라고 했을 때 서비스 뒤로 window 5 정도를 보면 서비스에 대한 감성어가 나올 것을 생각이 되는데요. 이를 찾고 싶습니다. textrank를 통해 서비스라는 키워드를 찾고 PMI를 계산하여 서비스에 대한 연관 감성어를 찾아낼 수 있는지 궁금합니다.

      예를 들어 서비스 만족스럽다 <- 처럼 묶을 수 있는지 궁금합니다.

      글에서 나온 것을 예로 들면
      목성 가볍다 <- 처럼 묶을 수 있는지 궁금합니다. 다시한번 감사드립니다.
    • 그것은 텍스트의 성격에 따라서 다를 것 같습니다. TextRank는 일반적으로 텍스트 내에서 가장 중심이 되는 어구를 뽑는데에 사용할 수 있습니다. 따라서 TextRank를 통해 "서비스"가 뽑혀나오려면 해당 텍스트가 "서비스"와 관련된 주제여야 하겠죠.
      만약 해당 텍스트가 특정 식당에 관한 것이고, "서비스"라는 단어는 주제 중 한 측면으로 등장한 것이라면, TextRank를 통해 "서비스"를 추출하기 어려울 것으로 예상됩니다.

      하지만 아무튼 "서비스"라는 단어가 선택되고 난 뒤에는, 그 뒤의 어구들과 PMI를 구하는것은 어렵지 않을듯 합니다.
    • 답변 감사드립니다.

      바쁘신 걸 알면서도 추가로 질문을 드리고 싶은데요 혹시 메일을 알려주실 수 있을까요?
    • bab2min@gmail.com 입니다.
    • ShinoRIn
    • 2018.05.30 21:20 신고
    글에서 텍스트 랭크를 단어에 적용 할 때, 한 문장에서의 동시 출현 빈도를 가지고 간선을 구축한다고 하셨는데 구체적으로 어떻게 간선을 만드는 것인지 알 수 있을까요?
    • 예를 들어 A B C D A라는 문장이 등장했다고 합시다. (A~D는 각기 다른 단어) window 크기를 좌우로 2개씩으로 설정할 경우 동시 출현 단어쌍은 A-B, A-C, B-C, B-D, C-D, C-A, D-A로 계산할 수 있습니다. 이때 각 단어 쌍의 빈도를 계산하여 edge의 weight로 주고(a-b, b-a는 같은걸로 계산), 각각의 단어를 node로 주면 네트워크가 구축되게 되겠죠.
      위의 예시에서는
      A-B: 1,
      A-C: 2,
      A-D: 1,
      B-C: 1,
      B-D: 1,
      C-D: 1
      이 됩니다. 이를 가지고 그래프를 그리면 동시출현 네트워크가 되는 것이구요, 여기에 PageRank를 적용한다는 것이 TextRank의 아이디어입니다.