EXCELSIOR

TextRank를 이용한 문서요약 본문

Machine_Learning(ML)

TextRank를 이용한 문서요약

Excelsior-JH 2017. 6. 12. 01:59

이번 포스팅은 구글의 PageRank를 Text에 적용시킨 TextRank 알고리즘에 대한 내용이다. TextRank 알고리즘을 알아본 후 다음 포스팅에서 TextRank를 이용하여 문서를 요약해주는 시스템 구현을 포스팅할 예정이다.

TextRank 란?

TextRank는 Mihalcea(2004)이 제안한 알고리즘으로 텍스트에 관한 graph-based ranking model 로써, Google의 PageRank를 활용한 알고리즘이다. PageRank는Brin and Page(1998)이 제안한 알고리즘으로 하이퍼링크를 가지는 웹 문서에 상대적 중요도에 따라 가중치를 부여하는 방법이다. 서로간의 인용과 참조로 연결된 임의의 묶음에 적용할 수 있다.(wikipedia) PageRank가 높은 웹페이지는 다른 웹 사이트로 부터 링크를 받는다 즉 다른 사이트가 참조를 많이한것으로 해석할 수 있다. 예를 들어, 아래 그림의 Page A의 PageRank는 B,C,D 각각의 PageRank(PR)를 해당 B, C, D의 전체링크(L)로 나눈 값의 합으로 나타낼 수 있다. 아래의 식에서 ddamping factor웹 서핑을 하는 사람이 해당 페이지를 만족하지 못하고 다른 페이지로 가는 링크를 클릭할 확률이다. PageRnak의 자세한 내용은 조성문님의 블로그에서 확인할 수 있다.

PR(A)=(1d)+d(PR(B)L(B)+PR(C)L(C)+PR(D)L(D))

[그림 1] PageRank 예시

이러한 PageRank 알고리즘을 활용한 것이 바로 TextRank이다. TextRankPageRank중요도가 높은 웹 사이트는 다른 많은 사이트로 부터 링크를 받는다는 점에 착안하여 문서 내의 문장(or 단어)를 이용하여 문장의 Ranking을 계산하는 알고리즘이다.

[그림 2] PageRank > TextRank 적용


TextRank 식은 아래와 같다.

TR(Vi)=(1d)+dVjIn(Vi)wjiVkOut(Vj)wjkTR(Vj)

  • TR(Vi): 문장 또는 단어(V)i에 대한 TextRank값
  • wij: 문장 또는 단어 ij 사이의 가중치
  • d:dampingfactor, PageRank에서 웹 서핑을 하는 사람이 해당 페이지를 만족하지 못하고 다른페이지로 이동하는 확률로써, TextRank에서도 그 값을 그대로 사용(0.85로 설정)
  • TextRank TR(Vi)를 계산 한 뒤 높은 순으로 정렬

TextRank 구현 해보기

TextRank를 적용하여 문서를 요약해주는 시스템을 구현 해본다. 전체 프로세스는 아래 그림3 과 같다.



[그림 3] TextRank를 이용한 문서 요약 프로세스

Step 0. 필요한 패키지 설치하기

  1. Newspaper: 사용자가 입력한 url에서 text를 크롤링 해주는 패키지이다. 자세한 내용은 Newspaper모듈을 이용하여 뉴스 기사 크롤링하기에서 확인 할 수 있다.
  • python 3 : pip install newspaper3k
  • python 2 : pip install newspaper
  1. KoNLPy: 한글형태소 분석기로 TextRank를 적용하기 위한 전처리 과정으로 사용된다. Python에 KoNLPy 설치 및 예제 실행에서 확인할 수 있다. KoNLPy를 설치하기 위해서는 JPype1을 설치해야한다.
  • JPype1 설치: pip install jpype1
  • KoNLPy 설치: pip install konlpy
  1. Scikit-learn: Python의 대표적인 머신러닝 패키지 중 하나로 TF-IDF 모델을 생성하는데 사용한다.
  • scikit-learn 설치: pip install scikit-learn
    이제 문서 요약 시스템을 구현하기 위해 필요한 패키지 설치가 끝났다. 이제 각 세부 프로세스와 소스코드를 알아보도록 하자.
from newspaper import Article
from konlpy.tag import Kkma
from konlpy.tag import Twitter
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.preprocessing import normalize
import numpy as np

Step 1. 문서 타입에 따른 문장 단위로 분리하기(텍스트 크롤링 > 문장 단위 분리 > 명사 추출)

  1. 텍스트 크롤링
    현재, 구현하고자 하는 문서요약시스템은 사용자가 입력값을 url 혹은 text 2가지로 입력할 수 있게 구현할 것이다. 사용자가 url을 입력했을 때, Step 0에서 설치한 newspaper 패키지를 이용하여 text를 크롤링한다.

  2. 문장 단위 분리
    문장 단위로 분리하기 위해 여러가지 방법을 생각하던 중 KoNLPy꼬꼬마(Kkma) 분석기 함수 중 문장을 추출하는 sentences()라는 함수를 이용하여 문장을 분리한다.

  3. 명사 추출(POS-Tagging)
    TF-IDF 모델을 만들기 위한 전처리 과정으로 문장으로 분리 한 뒤 문장을 형태소 단위로 나눈 후 품사 태깅을 통해 명사들만 추출한다. KoNLPyTwitter를 이용하여 명사를 추출해 준다.

<SentenceTokenizer Class>

[텍스트 크롤링, 문장 단위 분리, 명사 추출] 과정을 SentenceTokenizer 클래스로 만들었다.

  • 아래의 코드에서 stopwords는 불용어로써 문장 내에서 내용을 나타내는데 의미를 가지지 않는 단어들의 집합을 의미한다. stopwords는 사용 목적에 맞게 적절히 추가, 삭제를 해주면 된다.
  • url2sentences(url) : url 주소를 받아 기사내용(article.text)을 추출하여 Kkma.sentences()를 이용하여 문장단위로 나누어 준 후 senteces를 return 해 준다.
  • text2sentences(text) : text(str)를 입력받아 Kkma.sentences()를 이용하여 문장단위로 나누어 준 후 senteces를 return 해 준다.
  • get_nouns(sentences) : sentences를 받아 Twitter.nouns()를 이용하여 명사를 추출한 뒤 nouns를 return해 준다.
class SentenceTokenizer(object):
def __init__(self):
self.kkma = Kkma()
self.twitter = Twitter()
self.stopwords = ['' ,'', '', '', "", "", "", "", "", ""
,"", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "",]
def url2sentences(self, url):
article = Article(url, language='ko')
article.download()
article.parse()
sentences = self.kkma.sentences(article.text)
for idx in range(0, len(sentences)):
if len(sentences[idx]) <= 10:
sentences[idx-1] += (' ' + sentences[idx])
sentences[idx] = ''
return sentences
def text2sentences(self, text):
sentences = self.kkma.sentences(text)
for idx in range(0, len(sentences)):
if len(sentences[idx]) <= 10:
sentences[idx-1] += (' ' + sentences[idx])
sentences[idx] = ''
return sentences
def get_nouns(self, sentences):
nouns = []
for sentence in sentences:
if sentence is not '':
nouns.append(' '.join([noun for noun in self.twitter.nouns(str(sentence))
if noun not in self.stopwords and len(noun) > 1]))
return nouns

Step 2. TF-IDF 모델 생성 및 그래프 생성

  1. TF-IDF
    TF-IDF(Term Frequency - Inverse Document Frequency)는 정보 검색(Information Retrieval)과 텍스트 마이닝에서 사용하는 단어의 상대적인 가중치이다. 여러 문서로 이루어진 문서 군이 있을 때 어떤 단어가 특정 문서 내에서 얼마나 중요한 것인지를 나타내는 통계적 수치이다. 자세한 내용은 Wikipedia에서 확인할 수 있다.
  • TF(Term Frequency) : 단어 빈도, 특정 단어가 문서 내에 얼만큼의 빈도로 등장하는지를 나타내는 척도
  • IDF(Inverse Document Frequency) : 역문헌 빈도수, 문서 빈도의 역수로써 전체 문서 개수를 해당 단어가 포함된 문서의 개수로 나눈 것을 의미한다.
  • TF-IDF 식 : Wi,j=tfi,j×log(N/dfi)
    TF-IDF를 계산하기 위해 Python의 머신러닝 패키지인 Scikit-learn을 이용하여 TF-IDF모델링을 수행한다. TF-IDF를 구하고 난 뒤 그래프를 생성하기 위해 Sentence - Term Matrix(원래는 Document-Term Matrix)를 아래의 그림4 처럼 생성한다.

[그림 4] Sentence-Term Matrix 생성
  1. 그래프 생성
    Sentence-Term Matrix를 이용하여 전치행렬을 구한뒤 서로 곱해준다. 즉, Correlation Matrix 를 생성한다. 이렇게 생성한 Correlation Matrix를 Graph의 Adjancey Matrix로 생각해 줄 수 있다. (Correlation Matrix의 대각행렬 원소 1을 0으로 치환 해줘야함) 따라서, 아래 그림5 처럼 Correlation Matrix를 통해 문장(or 단어) 간의 가중치 그래프(Weighted graph)로 나타낼 수 있다.

[그림 5] Correlation Matrix를 이용한 가중치 그래프 생성

<GrpahMatrix Class>

[TF-IDF 모델, 그래프 생성] 과정을 GraphMatrix 클래스로 구현했다.

  • build_sent_graph(sentence) : 명사로 이루어진 문장을 입력받아 sklearn의 TfidfVectorizer.fit_transform을 이용하여 tfidf matrix를 만든 후 Sentence graph를 return 한다.
  • build_words_grahp(sentnece) : 명사로 이루어진 문장을 입력받아 sklearn의 CountVectorizer.fit_transform을 이용하여 matrix를 만든 후 word graph와 {idx: word}형태의 dictionary를 return한다.
class GraphMatrix(object):
def __init__(self):
self.tfidf = TfidfVectorizer()
self.cnt_vec = CountVectorizer()
self.graph_sentence = []
def build_sent_graph(self, sentence):
tfidf_mat = self.tfidf.fit_transform(sentence).toarray()
self.graph_sentence = np.dot(tfidf_mat, tfidf_mat.T)
return self.graph_sentence
def build_words_graph(self, sentence):
cnt_vec_mat = normalize(self.cnt_vec.fit_transform(sentence).toarray().astype(float), axis=0)
vocab = self.cnt_vec.vocabulary_
return np.dot(cnt_vec_mat.T, cnt_vec_mat), {vocab[word] : word for word in vocab}

Step 3. TextRank 알고리즘 적용

이제 드디어, TextRank 알고리즘을 구현하는 단계이다.
앞에서 생성된 문장(or 단어)의 가중치 그래프를 이용하여 TextRank 알고리즘을 적용한다. TextRank 알고리즘을 통해 Ranking값이 높은 순으로 정렬한 뒤 요약할 문장(or 단어)의 개수 만큼 출력 해준다.

<Rank class>

TextRank 알고리즘을 구현한 클래스이다.

TR(Vi)=(1d)+dVjIn(Vi)wjiVkOut(Vj)wjkTR(Vj)

  • get_ranks(graph): 위의 식을 구현한 부분이며, {idx : rank 값} 형태의 dictionary를 return 한다.
  • spookyQubit/TextRank 를 참고함
class Rank(object):
def get_ranks(self, graph, d=0.85): # d = damping factor
A = graph
matrix_size = A.shape[0]
for id in range(matrix_size):
A[id, id] = 0 # diagonal 0
link_sum = np.sum(A[:,id]) # A[:, id] = A[:][id]
if link_sum != 0:
A[:, id] /= link_sum
A[:, id] *= -d
A[id, id] = 1
B = (1-d) * np.ones((matrix_size, 1))
ranks = np.linalg.solve(A, B) # Ax = b
return {idx: r[0] for idx, r in enumerate(ranks)}

Step 4. TextRank Class 구현

Step1 ~ Step3 까지의 클래스를 조합하여 TextRank 클래스를 구현했다. 사용자는 이 TextRank class를 이용하여 문서의 요약 또는 키워드들을 확인한다.

  • summarize(sent_num=3): Default로 3줄 요약 가능하게 구현했다.
  • keywords(word_num=10): Default로 10개의 키워드를 출력하도록 구현했다.
class TextRank(object):
def __init__(self, text):
self.sent_tokenize = SentenceTokenizer()
if text[:5] in ('http:', 'https'):
self.sentences = self.sent_tokenize.url2sentences(text)
else:
self.sentences = self.sent_tokenize.text2sentences(text)
self.nouns = self.sent_tokenize.get_nouns(self.sentences)
self.graph_matrix = GraphMatrix()
self.sent_graph = self.graph_matrix.build_sent_graph(self.nouns)
self.words_graph, self.idx2word = self.graph_matrix.build_words_graph(self.nouns)
self.rank = Rank()
self.sent_rank_idx = self.rank.get_ranks(self.sent_graph)
self.sorted_sent_rank_idx = sorted(self.sent_rank_idx, key=lambda k: self.sent_rank_idx[k], reverse=True)
self.word_rank_idx = self.rank.get_ranks(self.words_graph)
self.sorted_word_rank_idx = sorted(self.word_rank_idx, key=lambda k: self.word_rank_idx[k], reverse=True)
def summarize(self, sent_num=3):
summary = []
index=[]
for idx in self.sorted_sent_rank_idx[:sent_num]:
index.append(idx)
index.sort()
for idx in index:
summary.append(self.sentences[idx])
return summary
def keywords(self, word_num=10):
rank = Rank()
rank_idx = rank.get_ranks(self.words_graph)
sorted_rank_idx = sorted(rank_idx, key=lambda k: rank_idx[k], reverse=True)
keywords = []
index=[]
for idx in sorted_rank_idx[:word_num]:
index.append(idx)
#index.sort()
for idx in index:
keywords.append(self.idx2word[idx])
return keywords

Step 5. 결과 확인

결과 확인을 위해 [다음 뉴스]에서월급쟁이 65%, 신용카드 소득공제 못받는다 기사를 요약해보자.

url = 'http://v.media.daum.net/v/20170611192209012?rcmd=r'
textrank = TextRank(url)
for row in textrank.summarize(3):
print(row)
print()
print('keywords :',textrank.keywords())
◇ 연 봉 5000만원 대가 84% 로 카드 공제 가장 많이 받아 신용카드 소득 공제를 받으려면 총소득의 4분의 1 이상을 카드로 써야 한다.

2015년 기준으로 근로 소득세를 내는 사람 중에서 카드 소득 공제를 받는 비율이 가장 많은 소득 구간은 연봉 5000만 ~6000 만원이었다.

연봉 4000만원 대는 81%, 3000만원 대는 73%, 2000만원 대는 55% 만 카드 소득 공제를 받은 것으로 나타났다.

keywords : ['소득', '공제', '카드', '사람', '사용', '한도', '만원', '신용카드', '경우', '문턱']

이상으로 TextRank를 직접 구현하여 문서요약시스템을 만들어 보았다. 전처리 과정에서 불용어 처리나, 품사태깅에 대한 부족한 부분이 있지만 직접 구현해보는것 자체가 큰 의미가 있는거 같다. 현재 gensim을 비롯한 다양한 패키지들이 TextRank알고리즘을 활용하여 문서를 요약해주고 있다. 역시 코딩은 있는거 잘 가져다 쓰는 것이 최고인거 같다.


Comments