문서 요약 하기 (with textrank)

구글은 pagerank 라는 알고리즘을 통해 검색의 품질을 높혔다.

 

pagerank 알고리즘을 설명해보자면

"더 중요한 페이지는 더 많은 사이트로부터 링크를 받는다" 는 관찰에 기조해 만들어진 알고리즘이다.

 

위키피디아에 써져있는 예를 보자면

페이지 A가 페이지 B,C,D 로 총 3개의 링크를 걸었다면 B는 A의 페이지 랭크 값의 (1/3) 만큼을 가져온다(?)

 

풀어서 써보자면 특정 페이지 A 에 B, C, D 의 링크를 걸었다면

( B 페이지의 중요도(pageRank) + C 페이지의 중요도 + D 페이지의 중요도 ) / 3(=A페이지에 걸린 링크 수)

의 페이지 중요도 (pageRank A)를 가지게 되는 것이다.

 

또 알고리즘은 인터넷 서핑하는 가상의 인물(random surfer)를 정의 하고,

해당 사용자가 현재 페이지에 만족하고 계속 보는 확률(damping factor)를 정의해 알고리즘에 포함 시켰다.

(만족하지 못하고 떠나는 확률은 자연적으로 (1-damping factor) 가 된다)

 

위 식을 수정하자면

A_pageRank = 만족하지 못하고 떠나는 확률 + ( 만족하고 보는 확률 * 페이지 중요도 )

= (1-damping_factor) + damping_factor * (B_pageRank + C_pageRank + D_pageRank ) / (Link_num)

라고 할 수 있다.

 

이 알고리즘을 문서에 적용한게 textrank 다.

문서에 나타난 문장(or 단어) 를 위 페이지 처럼 여겨서 중요도를 계산하는 방법이다.

하지만 문장(or 단어)의 경우,

페이지 처럼 방향성을 가진 링크를 가지고 있는 것이 아니기 때문에 문장(or 단어)간 어떤 값을 가진 graph로 표현해야 한다.

 

textrank 를 제안한 논문에서 문장간 유사도를 통해 graph를 만드는데 이때 사용하는 문장간 유사도는 아래식으로 표현된다.

문장 간 유사도 계산식

위 식은 문장 안에 등장하는 요소(음절, 어절, 형태소 등)을 통해 계산하는데

문장간 유사도 = 두 문장에 동시에 등장하는 요소의 개수 / (log(문장_i 의 요소 개수) + log(문장_j 의 요소 개수))

라고 정리 된다.

 

실제 코드로 요약이 되는지 해보자.

https://news.naver.com/main/read.naver?mode=LSD&mid=shm&sid1=105&oid=092&aid=0002236934 

애플, 11월 블랙프라이데이 특수 앞두고 반도체 쇼티지로 울상

해당 기사의 내용을 ctrl + c,v 해서 사용한다.

기사를 복붙!

기사를 문장 단위로 나눈다.

import re
text = re.sub(r"\n+", " ", text)
sentences = re.split("[\.?!]\s+", text)

문장단위로 나뉜 기사

각 문장을 요소 단위로 나눈다.

import pandas as pd

data = []
for sentence in sentences:
    if(sentence == "" or len(sentence) == 0):
        continue
    temp_dict = dict()
    temp_dict['sentence'] = sentence
    temp_dict['token_list'] = sentence.split() #가장 기초적인 띄어쓰기 단위로 나누자!
    
    data.append(temp_dict)

df = pd.DataFrame(data) #DataFrame에 넣어 깔끔하게 보기

기사의 문장들과 해당 문장의 요소들

문장들 간의 유사도를 계산해준다.

# sentence similarity = len(intersection) / log(len(set_A)) + log(len(set_B))
similarity_matrix = []
for i, row_i in df.iterrows():
    i_row_vec = []
    for j, row_j in df.iterrows():
        if i == j:
            i_row_vec.append(0.0)
        else:
            intersection = len(set(row_i['token_list']) & set(row_j['token_list']))
            log_i = math.log(len(set(row_i['token_list'])))
            log_j = math.log(len(set(row_j['token_list'])))
            similarity = intersection / (log_i + log_j)
            i_row_vec.append(similarity)
    similarity_matrix.append(i_row_vec)

문장 간 유사도를 나타낸 weighted graph(matrix)

문장 유사도 그래프를 통해 문장의 rank를 계산해준다.

코드를 적기 전 해당 코드는 textrank를 정리한 https://lovit.github.io/nlp/2019/04/30/textrank/ 블로그의 글을 참고 했다.

def pagerank(x, df=0.85, max_iter=30):
    assert 0 < df < 1

    # initialize
    A = normalize(x, axis=0, norm='l1')
    R = np.ones(A.shape[0]).reshape(-1,1)
    bias = (1 - df) * np.ones(A.shape[0]).reshape(-1,1)
    # iteration
    for _ in range(max_iter):
        R = df * (A * R) + bias

    return R

나도 참고 했기 때문에 해당 코드를 이해하는데 시간이 좀 걸렸다.

먼저 normalize 는 pagerank 알고리즘의 페이지 중요도를 다 더해서 1로 만들어주는 작업이다.

normalize 예시

R 의 경우, 각 문장의 rank값을 의미하고 맨처음은 1로 초기화 되어있다.

R = np.ones(A.shape[0]).reshape(-1,1)

bias의 경우, 만족하지 못하고 페이지를 떠나는 확률로 (1 - damping factor)를 의미한다.

bias = (1 - df) * np.ones(A.shape[0]).reshape(-1,1)

각 rank는 weighted graph * rank*damping factor + (1-damping factor)로 계산한다.

(원래 pagerank에서는 각 랭크 값이 어느정도 수렴할때까지 무한 루프를 돌리는데 이건 간단한 테스트이기 때문에 max iteration 만큼 동작한다.)

# iteration
for _ in range(max_iter):
    R = df * (A * R) + bias

pagerank 계산 결과

R은 각 문장별 다른 문장으로 부터 rank을 나눠 받은 상태라고 할 수 있다.

그림으로 표현하자면,

그림으로 설명...

그렇다면 row별로 sum을 하면 각 문장 당 최종 rank 값이 나오고, rank 높은 순으로 문장을 뽑아 나열하면 요약이 된다는 말이다

R = pagerank(weightedGraph) # pagerank를 돌려서 rank matrix 반환
R = R.sum(axis=1) # 반환된 matrix를 row 별로 sum 
indexs = R.argsort()[-3:] # 해당 rank 값을 sort, 값이 높은 3개의 문장 index를 반환

# rank값이 높은 문장을 프린트
for index in sorted(indexs): # sorted 하는 이유는 원래 문장 순서에 맞춰 보여주기 위함
    print(df['sentence'][index])

요약 알고리즘 결과

네이버는 각 기사마다 요약봇 서비스를 하고 있는데, 요약봇이 요약한 결과와 비교해보자.

네이버 요약봇 결과

한문장 빼고 전부 다른것을 확인할 수 있다.

문장 요소를 단순히 띄어쓰기로 나눠서 많이 다른걸까 싶어, python 한국어 형태소 분석기 중 komoran을 이용해 분해후 적용시켜 보았다.

python 형태소 분석기 komoran

komoran 사용 결과

역시 네이버 요약봇과의 다른점이 보이는데 요약봇은 기사내 문장을 가공해 보여준다!

(그래도 원래 문장과 많이 다르진 않네...)

띄어쓰기로 요소를 만들었을때보다 형태소 분석기를 사용했을때 요약봇의 결과와 조금 더 비슷한 결과를 보여준다.

 

기사 하나로만 하기엔 아쉽기에 하나 더 테스트 해봤다.

https://news.naver.com/main/ranking/read.naver?mode=LSD&mid=shm&sid1=001&oid=092&aid=0002236968&rankingType=RANKING 

카카오페이, 공모가 9만원 확정...25일 일반 공모 시작

테스트 하려는 기사

# 위에서 사용한 코드를 전부 합쳐서 
text = re.sub(r"\n+", " ", text)
sentences = re.split("[\.?!]\s+", text)

data = []
for sentence in sentences:
    if(sentence == "" or len(sentence) == 0):
        continue
    temp_dict = dict()
    temp_dict['sentence'] = sentence
    temp_dict['token_list'] = komoran.nouns(sentence)
    
    data.append(temp_dict)

df = pd.DataFrame(data)

similarity_matrix = []
for i, row_i in df.iterrows():
    i_row_vec = []
    for j, row_j in df.iterrows():
        if i == j:
            i_row_vec.append(0.0)
        else:
            intersection = len(set(row_i['token_list']) & set(row_j['token_list']))
            log_i = math.log(len(set(row_i['token_list'])))
            log_j = math.log(len(set(row_j['token_list'])))
            similarity = intersection / (log_i + log_j)
            i_row_vec.append(similarity)
    similarity_matrix.append(i_row_vec)
    
weightedGraph = np.array(similarity_matrix)
R = pagerank(weightedGraph)
R = R.sum(axis=1)
indexs = R.argsort()[-3:]

for index in sorted(indexs):
    print(df['sentence'][index])
    print()

코드로 돌려본 결과

결과가 꽤! 좋게 나오는걸 확인할 수 있다.

네이버 요약봇과 비교했을때 단순한 코드임에도 그렇게 나쁘지 않을 결과를 보여주는걸 확인 할 수 있었다.

해당 알고리즘을 java 버전으로 만들어서 회사에서 써먹어야지...언젠가...

이번 코딩도 재밌었다~

 

 

%%%아이디어%%%%

저번에 minhash를 이용해 clustering 할때 textrank를 통해 문서의 중요문장만을 남겨 놓는다면 문서 벡터를 구성할때 좀 더 적은 용량으로도 결과를 향상시키는데 도움을 주지 않을까 싶다

(document → New (textrank → sentences(3~5)) → vector → minhash&LSH → cluster)

뉴스 문서 군집화 하기.ver2 ( document clustering using Minhash & LSH)

뉴스 문서 군집화 하기.ver2 ( document clustering using Minhash & LSH)

 

참고

https://lovit.github.io/nlp/2019/04/30/textrank/

https://joolib.tistory.com/21

https://ko.wikipedia.org/wiki/페이지랭크

https://sungmooncho.com/2012/08/26/pagerank/

https://www.aclweb.org/anthology/W04-3252.pdf