10. TextRank

TextRank

TextRank는 각 문서를 토큰화 -> 그래프 생성 (서로 간의 관계를 이용) -> 중요도 계산하여 핵심 키워드 추출

그래프 기반 Ranking 모델, 키워드와 문장추출을 위한 비지도 학습 방법 제안(문서만 있으면 키워드나 문장 추출)

Graph-based ranking algorithms -> 구글 PageRank에서 사용됨, 그래프 기반 각 노드의 중요성을 결정하는 방법

많은 득표를 한 노드가 중요한 노드임을 의미. 

https://icim.nims.re.kr/post/easyMath/837

구글 페이지 랭크 원리를 보면, c,b는 웹페이지 

나를 참조로 하고 있는 링크가 많을 때 중요한 웹페이지라고 간주 -> 가중치가 올라감

S(Vi): 아래 PR(A) 와 같은 역할

나와 인접하고 있는 노드가 가지고 있는 링크 만큼 분해하여 스코어를 받음

 

키워드 추출의 TextRank 

1단계: 텍스트는 품사가 태깅하여 토큰화됨

2단계: 단어 윈도에 동시 등장한 토큰 사이는 엣지를 추가하여 그래프 생성

3단계: 각 스코어의 변화가 0.0001을 임계값으로 20-30회 반복, 스코어의 변화가 없을때 반복 멈춤

절대적으로 저 하이퍼파라미터가 옳다고 판단하기 보다는, 실험을 통해서 결과를 보고 판단을통해 파라미터 조정

결과적으로 나와 인접해있는 노드 뿐 아니라, 인접하지 않은 노드까지 정보를 고려하기 때문에 textRank가 좋음

TextRank 과정

딸기 바나나 사과 딸기 파인애플일때, 딸기 바나나의 노드를 만들어준다. 스코어는 1.0으로 할당해줌 

처

각 노드별 스코어 1로 세팅, damping factor은 0.85

바나나는 사과와 딸기에서 들어오는 엣지가 있음.

사과는 2개의 엣지가 있다. 1.0스코어를 0.5씩 분배, 딸기는 3개 엣지라 0.333씩 분배 

바나나는 사과로부터 0.5, 딸기 0.333씩 받음

즉, S(바나나) = 0.15+ 0.85 *(0.5+0.333)=0.858

textrank 계산을 반복하여 최적값을 찾는다, 엣지가 많이 연결된 노드가 스코어가 높을것임.

주변에 영향력 있는 노드가 있다면 내 스코어가 올라갈 것임. 

pagerank 알고리즘 

A: 계산을 하는 대상이 되는 웹페이지

T: A를 링크하고 있는 웹페이지

PR(T): PageRank 점수

C(T): 웹페이지 T에서 연결된 링크 수

PR(T)/C(T) : T를 PageRank를 링크수로 나눈값

d: Damping factor (pagerank 알고리즘에서 나오는 상수), 15%의 사람이 링크를 타고 웹페이지에 접속함

예를 들어 PR(A)가 D 일때, D와 인접한 웹페이지 E가 있다.

이렇게 되면 E가 T가 되고, PR(T1)은 8.1, C(T)는 3, d는 0.15가 된다. 

 

tokens = ['딸기', '바나나', '사과', '딸기', '파인애플']
nodes = ['바나나', '사과', '파인애플', '딸기']


vocab2idx = {nodes[i]:i for i in range(0, len(nodes))} #vocab을 인덱스로 변환
idx2vocab = {i:nodes[i] for i in range(0, len(nodes))} #인덱스를 vocab으로 변환
vocab2idx
#단어를 넣으면 인덱스, 인덱스를 넣으면 단어로 반환이됨

{'바나나': 0, '사과': 1, '파인애플': 2, '딸기': 3}

import numpy as np
vocab_len = len(nodes)

#가중치 행렬 초기
weighted_edge = np.zeros((vocab_len,vocab_len),dtype=np.float32)

#노드별 스코어 1로 초기화
score = np.ones((vocab_len),dtype=np.float32)

window_size = 2 #토큰의 갯수-윈도우+1만큼 반복

for window_start in range(0,len(tokens)-window_size+1):
    window = tokens[window_start: window_start+window_size]
    for i in range(window_size):
        for j in range(i+1,window_size):
            if (window[i] in vocab2idx.keys()) & (window[j] in vocab2idx.keys()) : #윈도 내 단어가 노드에 속하는 경우만 엣지로 연결
                index_of_i = window_start + i
                index_of_j = window_start + j #14분 11초
                
                weighted_edge[vocab2idx[window[i]], vocab2idx[window[j]]]=1 #window i 번째로 vocab의 index 찾음
                weighted_edge[vocab2idx[window[j]],vocab2idx[window[i]]]=1
                #covered_coocurrences.append([index_of_i,index_of_j])

                
for i in range(0,vocab_len):
  sumi = weighted_edge[i].sum() #각 노드별 보유한 edge 수
  weighted_edge[i] = weighted_edge[i]/sumi if sumi > 0 else 0 #0이 이상인 경우에 한해 가중치/ 엣지

#weighted_edge

score

array([1., 1., 1., 1.], dtype=float32)

weighted_edge #서로간의 노드가 연결된 것에 한함

array([[0.        , 0.5       , 0.        , 0.5       ],
       [0.5       , 0.        , 0.        , 0.5       ],
       [0.        , 0.        , 0.        , 1.        ],
       [0.33333334, 0.33333334, 0.33333334, 0.        ]], dtype=float32)

#각 노드와 연결된 weighted edge값 합산
MAX_ITERATIONS = 50
d=0.85
threshold = 0.0001 #얼마나 수렴하는지 값의 변화가 없는 경우 연산을 멈춘다

for iter in range(0,MAX_ITERATIONS):
    prev_score = np.copy(score)
    
    for i in range(0,vocab_len):        
        summation = 0
        for j in range(0,vocab_len):
            if weighted_edge[j][i] != 0:
                summation += weighted_edge[j][i]*score[j]#엣지 스코어/ 가중치
                
        score[i] = (1-d) + d*(summation) #스코어 갱신  #반복조건 1: 이터레이션만큼 2: threshold 달성할때까지
    
    if np.sum(np.fabs(prev_score-score)) <= threshold: #이전스코어= 이후스코어 임계값보다 적으면 stop
        break

score

array([0.98364776, 0.98365426, 0.5656039 , 1.4668667 ], dtype=float32)

#핵심단어 추출
sorted_index = np.flip(np.argsort(score),0) 
n=4

for i in range(0,n):
    print(str(idx2vocab[sorted_index[i]])+" : " + str(score[sorted_index[i]]))

딸기 : 1.4668667
사과 : 0.98365426
바나나 : 0.98364776
파인애플 : 0.5656039

#그래프 활용
tokens = ['ST', 'BN', 'APP', 'ST', 'PIN']
nodes = ['BN', 'APP', 'PIN', 'ST']

vocab2idx = {nodes[i]:i for i in range(0, len(nodes))} #vocab을 인덱스로 변환
idx2vocab = {i:nodes[i] for i in range(0, len(nodes))}

import numpy as np
import math
import networkx as nx
#vocab_len = len(vocab)

# 토큰별로 그래프 edge를 Matrix 형태로 생성
weighted_edge = np.zeros((vocab_len,vocab_len),dtype=np.float32)

# 각 토큰 노드별로 스코어 1로 초기화
score = np.ones((vocab_len),dtype=np.float32)

# coocurrence를 판단하기 위한 window 사이즈 설정
window_size = 2
edges = []

for window_start in range(0,(len(tokens)-window_size+1)):
    window = tokens[window_start : window_start+window_size]
    for i in range(window_size) :
        for j in range(i+1, window_size) : 
            if (window[i] in vocab2idx.keys()) & (window[j] in vocab2idx.keys()) : #윈도 내 단어가 노드에 속하는 경우만 엣지로 연결
                edges.append((window[i],window[j])) #window i와 window j의 엣지 연결
                #index_of_i = window_start + i
                #index_of_j = window_start + j
g= nx.diamond_graph()
g.clear()

g.add_nodes_from(list(set(tokens))) #리스트 형태로 노드 추가
g.add_edges_from(edges) #엣지 추가 하기 위해서 서로 연결해줘야함

 

edges

[('ST', 'BN'), ('BN', 'APP'), ('APP', 'ST'), ('ST', 'PIN')]

import networkx as nx
from IPython.core.display import Image
from networkx.drawing.nx_pydot import to_pydot

d = to_pydot(g)
d.set_dpi(600)
d.set_rankdir("LR")
Image(d.create_png(), width=600)

scores = nx.pagerank(g) #pagerank 계산
sorted(scores.items(), key=lambda x: x[1], reverse=True)[:4] #score 역순 정렬

[('ST', 0.3667352990529791),
 ('BN', 0.2459279727012903),
 ('APP', 0.2459279727012903),
 ('PIN', 0.1414087555444403)]

 

이론은 이해가나,, 코드 따라는 했지만 개발환경에서 너무 많은 오류가 나서 이것을 해결하느라 오래걸렸다,,

쉽지 않은 인생 코드 이해는 천천히

 

 

GitHub - insightcampus/sesac-nlp: 실무형 인공지능 자연어처리

출처: https://github.com/insightcampus/sesac-nlp