알고리즘따위 1도 모르는 코딩초보자, TextRank에 TF-IDF적용 분투기

이름이 매우 거창하지만 사실 들여다보면 아무것도 없는 분투기 시작하겠읍니다.

---

01. TextRank가 뭐야

저번 시간에 WIKI에서 마드리드 거리를 구역별로 크롤링해서 본문 텍스트를 모조리 SCRAPY로 따왔다. 내가 원하는 것은 크롤링 결과 중 어떤 내용이 번역할 만한 재밌는 내용을 가지고 있을까를 보려는 것이다. 내가 230개의 거리 위키 문서를 모두 읽을 순 없으니 핵심 키워드를 뽑으면 재밌어보이는 것들을 구분할 수 있지 않겠나. 자 그러면, 어떻게 해야 키워드를 뽑을 수 있을까. 구글링한다.

 

영어와 한글로 구글링!!

한글로 검색하니 konlpy로 명사 추출하여 빈도 계산하는 코드가 뜬다. 내가 원하는 건 텍스트 요약이지 최다 빈도를 뽑는 건 아니다. 최다 빈도는 엑셀로도 충분히 가능하지. 영어로 검색하니 TextRank라는 키워드가 많이 보이는데 첫 번째 검색 결과로 들어가보니 ranking 알고리즘을 설명하는 수많은 수학 수식들이 무자비하게 나를 괴롭힌다.바-로 깔끔하게 포기! 

 

그러면 TextRank를 구글링해본다.

호오... 영어로 검색했음에도 한글 결과를 반환해주는 구글신...

뭔가 문서/요약/핵심/추출/유사도 이런 단어들이 보이는 것 보니 길을 잘 찾아온 것 같다. 모두 클릭해서 들어가본다음 나같은 수학 1도 모르는 코더가 보기에 가장 설명이 친절하게 되어 있으며 그나마 덤빌 만해 보이는 게시물을 잡고 머리를 박아보기로 한다.

 

정말 이해가 하나도 가지 않는다 ㅋ_ㅋ. 그래도 한글과 파이썬을 읽을 줄은 아니까 찬찬히 읽어보면

 

1) TextRank는 구글의 PageRank 알고리즘을 이용한 것이다.

2) PageRank는 페이지의 링크를 계산하여 페이지의 랭크를 계산하는 알고리즘이다.

3) 따라서 Tf-Idf 라는 문장 간의 모델을 이용하여 TextRank를 적용하면 중요 문장이 나온다.

 

(이렇게 1도 모르겠는 문장을 무턱대고 읽을 용기는 칸트와 플라톤을 열심히 읽어대서일까... 차라리 이런 문서는 읽을 수라도 있지 라깡이나 데리다의 문장은 도저히 읽기조차 힘드니까...라고 스스로를 대견해한다)

 

우선 TF-IDF 모델로 문서를 분석하기 전에 해야할 일은

 

1. 텍스트 크롤링 : 이미 했다.
2. 텍스트를 문장으로 이루어진 리스트로 만들기
3. 텍스트 전처리(NLP) : 기호 뺴고 숫자 빼고 불용어* 빼고 소문자로 만들고 단어 단위로 만들고 등등 텍스트를 TF-IDF 모델에 적용할 수 있는 형태로 만들기 *불용어('은는이가', 'is are' 처럼 겁나 자주 쓰이지만 의미 없는 단어들)
4. TF-IDF 모델 만들기 : 내가 절대 못하는 것(언젠가는.. 가능쓰?)
5. 전처리된 텍스트를 모델에 적용하기 위한 그래프(내가 알기론 벡터화? 그런거)로 만들기
6. TF-IDF 모델 적용해서 키워드 추출

와... 갈 길 겁나 멀어... 그러나 시도는 해보자.

 

패키지는
1. 한국어 분석을 위한 konlpy(내 경우에는 스페인어니까 nltk)
2. TF-IDF 모델 생성을 위한 라이브러리인 sklearn(Scikit-learn)
3. 외에 벡터 계산을 위한 numpy / csv파일을 읽어올 pandas / 텍스트 클렌징을 위한 정규표현식 re 정도가 있다.

---

02. 텍스트 전처리

위 프로세스에서 1번 크롤링은 끝냈으니 2번과 3번으로 바로 시작한다.

# 예시로 돌려볼 data를 크롤링데이터에서 불러온다
df = pd.read_csv('/Users/franc/study_python/pandas/wikitest.csv')
contents = df['content']
data = contents[0]

어우야.. [1] 이랑 \로 시작하는 이상한 것들부터 지워보자. 하지만 사실 나 정규표현식 제대로 이해 못했다 ㅠㅠ 점프투파이썬 정규표현식을 구글링해서 또 읽는다(또 까먹겠지만). 처음에는 [1] 이렇게 된 것을 지우고 숫자는 그대로 남겨두려고 했다. 그런데 결국엔 숫자도 필요없다는 걸 알게되서 둘다 지우게됐다. 

이거 하는데 진짜 오래걸렸수다...

정말 코딩공부 열심히 해야겠다는 생각이 드는 순간이었다. 그래도 항상 정규표현식 하면서 [ ] 대괄호는 왜 쓰이는지 몰랐는데 대괄호를 쓰면 안에 있는 문자들 중 하나라도 매치되는게 있으면 매치한다. 그래서 위에는 대괄호가 없으니까 [로 시작되고 숫자가 하나라도 등장하며 ]로 끝나는 모든 데이터를 지웠고 밑에는 대괄호가 있으니까 '[', 숫자, ']'를 모두 지운다.

정규표현식을 잘 아시는 여러분은 "이 멍청이가 왜 이렇게 뻘짓을 하지?" 라고 생각하실 포인트가 있다. 그것은 :

from nltk.tokenize import RegexpTokenizer

#문장 단위로 짤라 리스트로 반환
#언어마다 문장구성이 다르기 때문에 spanish를 꼭 붙여줘야 한다
sentences = sent_tokenize(data, "spanish")

#regexp토크나이저는 단어단위로 가능하기 때문에 
retokenize = RegexpTokenizer("[a-zA-Z]+")
sentences = [' '.join(retokenize.tokenize(sentence)) for sentence in sentences]

정규표현식을 적용해서 토크나이징 해주는 함수가 nltk에 있고, [a-zA-Z]+ : 문자가 하나라도 있으면 단어로 짤라라라고 명령할 수 있는 간편한 함수다. 하지만 여러분이 간과한 점은 spnaish에는 "ñ, í, á" 등 영어에서 특수기호로 처리되는 알파벳들이 있다는 것이다. 그래서 다음과 같은 코드가 완성된다.

#숫자와 []기호를 짤라주고
p = re.compile('[\[\]\d]')
data = p.sub(' ', data)
#문장 단위로 리스트를 만든 후
sentences = sent_tokenize(data, "spanish")
#정규표현식으로 클렌징을 한 후 다시 문장으로 만든다
retokenize = RegexpTokenizer("[\w]+")
sentences = [' '.join(retokenize.tokenize(sentence)) for sentence in sentences]
#마지막으로 word 토크나이저로 토큰화 후 다시 문장으로 만든다.
swordrs = stopwords.words("spanish")
nouns = []
for sentence in sentences:
    if sentence is not '':
    #token.lower()로 소문자로 바꿔주고 불용어 리스트에 포함되진 않는지 체크
        nouns.append(' '.join([noun.lower() for noun in word_tokenize(str(sentence), "spanish") 
                                          if noun.lower() not in swords and len(noun) >1]))

토큰화에서 stemmer와 lemmatizer 중 어느 것을 사용해야할지 몰라서 두 개다 돌려봤더니:
lemmatizer(word_tokenize): calle desengaño pequeña vía distrito centro madrid españa situada calle valverde concepción arenal costado gran vía
stemmer(SnowballStemmer): call desengañ pequeñ via distrit centr madr españ situ call valverd concepcion arenal cost gran via
비교 결과 스테머는 단어가 너무 뭉개져서 안하느니 못하다. 역시 르마타이저를 쓴다.
왜 문장 단위를 계속 유지하는지는 다음 단계에 이유가 있다.

---

03. Tf-Idf 모델링

 

TF-IDF란 어떤 단어가 특정 문서에서 얼마나 중요한지를 수치화하는 모델이다. TF(term frequency)란 어떤 단어가 특정 문서에서 얼마나 많이 등장하는지의 값이다. IDF(inverse document frequency)란 어떤 단어가 전체 문서에서 얼마나 많이 등장하는지의 값의 역수다. TF-IDF란 TF와 IDF를 곱한 것이다.

 

전 단계인 텍스트전처리 단계에서 계속해서 문장 형태를 유지해 온 이유는 간단하다. 비교 단위를 단어로 쪼개는 것보다 문장 단위로 하는게 훨-씬 간단해지기 때문이다. 우리가 하는 것은 문장을 단위로 문장 안의 단어들에 값을 줘서 그것을 정점(노드)와 간선(엣지)로 연결하는 그래프를 만드는 것이다. 후우.. 내가 써놨지만 정말 터무니 없는 문장이니까 우리 그냥 코드를 보면서 이해해보도록 하자.

 

먼저 사이킷런의 tfidif 벡터라이저는 각 단어에 tf-idf값을 매긴 문장 벡터를 만든다. (다시금 말하지만 수학내용은 저도 모릅니당)

from sklearn.feature_extraction.text import TfidVectorizer
corpus = [
	'This is the first document.',
	'This document is the second document.',
   	 'And this is the third one.',
	'Is this the first document?'
]

vectorizer = TfidVectorizer
#문장을 벡터화하여 매트릭스 구성
x = vectorizer.fit_transform(corpus)
#정수 인덱스의 이름 불러오기
vectorizer.get_feature_names()
#결과 : ['and', 'document', 'first', 'is', 'one', 'second', 'the', 'third', 'this']
#매트릭스 크기 확인
x.shape
#결과 : (4,9)

4개의 문장/9개의 단어로 이루어진 문서를 tfidf벡터라이저로 돌리면 (4,9)짜리 배열을 내놓는다. 음음 뭔지 알겠다. 자세히 알아보도록 하자

X는 (1,9)짜리 4개의 배열로 이루어져있으며 X[0]를 print로 출력하면 다음과 같다.

  (0, 8)	0.38408524091481483
  (0, 3)	0.38408524091481483
  (0, 6)	0.38408524091481483
  (0, 2)	0.5802858236844359
  (0, 1)	0.46979138557992045

위에서 X[0]는 (1, 9)의 배열에 5개의 원소가 저장되어 있다고 했으니 왼쪽의 (0, 숫자)는 뭔가 인덱스인거 같고 오른쪽의 float은 tf-idf 값인 것 같다. 즉, X[0]는 corpus에서 첫 번째 문장의 ti-idf 벡터이고 X는 이러한 4개의 벡터가 모인 매트릭스(벡터가 모인 것을 매트릭스라고 부르는 것 같다)이다. 공식 doc을 찾아보자.

 

tf-idf가 단어의 중요도를 나타내는 수치라는 것과 Vectorizer는 벡터화해주는 모듈이라는 것을 종합할 때 TfidfVectorizer는 문장을 넣으면 문장 단위로 tf-idf 수치로 벡터화 해주는 것으로 알 수 있다. 그렇다면 어떻게 벡터화하는 걸까. CountVectorizer 가 무엇일지 알아봐야겠다.

 

CountVectorizer는 텍스트를 토큰 매트릭스로 변환한다. sparse representation 이라는 뜻모를 단어가 튀어나온다. 역시나 코드를 통해 알아보는 것이 좋겠다.

from sklearn.feature_extraction.text import CountVectorizer

vectorizer = CountVectorizer()
corpus = [
	'This is the first document.',
	'This document is the second document.',
   	 'And this is the third one.',
	'Is this the first document?'
]
x = vectorizer.fit_transform(corpus)
print(x)
print(x[0])
print(x[0].shape)
#결과
<4x9 sparse matrix of type '<class 'numpy.int64'>'
	with 21 stored elements in Compressed Sparse Row format>    
    
  (0, 1)	1
  (0, 2)	1
  (0, 6)	1
  (0, 3)	1
  (0, 8)	1
  
 (1, 9)

음.. TfidfVectorizer와 동일하게 왼쪽은 인덱스로 보이는 것과 오른쪽은 수치로 보이는 (4, 9)형태의 넘파이 배열이 나온다. 이제는 sparse가 무엇인지 알아봐야겠다.

 

sparse의 사전적 정의는 small in numbers or amount, often spread over a large area이다. 즉, 적은 값이 넓게 퍼져있다는 것인데 이를 보니 x[0]의 형태가 (1,9)인데 왜 출력값 5개만 나오는지 추측이 가능해진다. 아마 0이 나온 값은 데이터 처리 효율을 위해서든 계산을 위해서든 적혀있는 것처럼 압축된 형태(compressd sparse row format)로 저장이 되어 출력되지 않나보다. 

 

그렇다면 이제 어떻게 1을 도출해내는지만 알면 된다. 

vectorizer.get_feature_names()
vectorizer.vocabulary_.get('and')
vectorizer.vocabulary_.get('document')
x.toarray()

#출력 결과
['and', 'document', 'first', 'is', 'one', 'second', 'the', 'third', 'this'] 

0
1

array([[0, 1, 1, 1, 0, 0, 1, 0, 1],
       [0, 2, 0, 1, 0, 1, 1, 0, 1],
       [1, 0, 0, 1, 1, 0, 1, 1, 1],
       [0, 1, 1, 1, 0, 0, 1, 0, 1]], dtype=int64)

4개의 문장으로 문자열 변수 corpus를 CountVectorizer에 넣고 돌리면 이렇게 9개의 feature가 생성되고 각 feature간의 연결에 0 또는 1의 값을 추가하면서 전체 매트릭스를 만든다. 문장의 각 token이 feature에 있는지 없는지 확인하고 있으면 1 없으면 0을 준다. 이 과정에서 0의 값이 매우 많기 때문에 scipy의 sparse.csr_matrix 모듈로 압축된 포맷을 입히는 것!

 

tfidf 벡터라이저는 countvectorizer에서 한 걸음 나아가 단어 빈도 수(term frequency)만 계산하는 것이 아니라 idf값을 구하여 매트릭스의 값을 조정한다.*가중치는 각 feature에 할당되는 값이다.

 

전처리한 텍스트를 tfidf벡터라이저에 넣어 (문장의 수, 단어 종류 수)의 sparse 매트릭스를 만든 후에 그의 역행렬(역매을 곱하여 문장과 문장간의 관계를 나타내는 매트릭스로 만든다.

tfidf = TfidfVectorizer()
tfidf_mat = tfidf.fit_transform(nouns).toarray()
sent_graph = np.dot(tfidf_mat, tfidf_mat.T)
sent_graph.shape
#결과
(21, 21)

내가 이해하는 것은 여기까지다. 어떻게 해서 이 그래프가 문장들의 관계를 수치로 나타낼 수 있다는 수학적 증명은 내가 알지 못한다. 

 

 

궁금하신 분들을 위해 유투브에서 발견한 정말 정리가 잘 된 자료가 있어 공유한다.

__

여기까지가 TextRank 알고리즘 적용 전까지 텍스트 전처리~ 벡터화 내용이다. 코드가/ 영어가/ 수학이 이해 안가더라도 계속 주피터 노트북으로 요리저리 돌려보고 모르는 용어가 나오면 구글링하면서 진행하면 어떻게든 이해는 간다.

 

__

이렇게 TEXTRANK 알고리즘을 적용할 문장 간 관계를 벡터값으로 나타내는 매트릭스를 만들었다.

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)}

그리고 이것이  TEXTRANK 알고리즘이다. 이해 시작!
* https://github.com/spookyQubit/TextRank/blob/master/textSummarization.ipynb

spookyQubit/TextRank

 

처음부터 매개변수부터 damping factor란 처음 보는 용어가 나온다. 구글링을 해보니 엉뚱하게 오디오, 케이블에 관한 글들이 상위에 있다. 뭐지?

http://blog.naver.com/PostView.nhn?blogId=andyinsight&logNo=220301981754&redirect=Dlog&widgetTypeCall=true

댐핑팩터(Damping Factor)란? - 그리고 케이블의 영향

으..응??

원하는 소리를 얻기 위해 신호를 준 다음에도 남아있는 진동?반영?찌꺼기? 이런 것들을 감소시키기 위한 것이 딤팽팩터라고한다. 음.. 구글링해도 좋은 결과를 얻기 힘들어서 TextRank 논문에서 찾아서 번역기를 돌렸다.
http://hrcak.srce.hr/file/207669

d는 0과 1 사이에서 설정할 수있는 감쇠 계수로, 그래프에서 주어진 정점에서 다른 임의의 정점으로 점프 할 확률을 모델에 통합하는 역할을합니다. 웹 서핑과 관련하여이 그래프 기반 순위 알고리즘은 "랜덤 서퍼 모델"을 구현합니다.여기서 d는 0과 1 사이에서 설정할 수있는 감쇠 계수이며, 그래프에서 주어진 정점에서 다른 임의의 정점으로 점프 할 확률을 모델에 통합하는 역할을합니다. 웹 서핑과 관련하여이 그래프 기반 순위 알고리즘은 사용자가 확률 d로 무작위로 링크를 클릭하고 확률 1-d로 완전히 새로운 페이지로 이동하는 "랜덤 서퍼 모델"을 구현합니다. 요소 d는 일반적으로 0.85 (BrinandPage, 1998)로 설정되며 이는 구현에 사용하는 값입니다.

어이가 없지만 오디오에서의 댐핑팩터의 정의와 논문에서의 내용에 따라 추론한 damping factor는 확률을 계산하는 데 있어 현실에서 발생하는 예상 외의 요인들로 인해 확률이 변동되는 것을 계산하기 위한 것 같다. 아닐 수도 있다. 근데 맞는 것 같다. ㅋ_ㅋ

이어서 알고리즘 구현 코드를 풀이해보자면

[1]

A[id, id] = 0 # diagonal 부분을 0으로
link_sum = np.sum(A[:,id]) # A[:, id] = A[:][id]
if link_sum != 0:
A[:, id] /= link_sum

1. 먼저 S1 노드 자신에 해당하는 링크에 0 값을 준 뒤 
2. S1 문장에 연결된 링크의 모든 값을 더하고
3. 그 값을 모든 링크에 나눈다.
* 자신의 값에 0을 주는 이유는 자신에 연결된 링크를 모두 더한 값에 영향을 끼치지 않기 위해서다.

[2]

A[:, id] *= -d
A[id, id] = 1

1. 이어 -d값을 전체에 곱하고
2. 다시 자기 자신에게 1값을 준다. 
* 식을 보면 TR(V1) = (1-d) + d*(쏼라쏼라) 인데 1은 여기서 1*TR(V1) 의 1이다.

[3]

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)}

위의 for문이 모든 문장 칼럼에 대하여 실행되고 난 뒤 식의 나머지 부분을 구현한다.
나는 여기가 왜 도대체 문장그래프와 1-d의 (n, 1)행렬을 numpy의 linalg.solve 모듈을 이용해 연립방정식으로 구하는 지 이해하기가 정말 힘들었다. 갑자기? 그래도 며칠간의 고민 끝에(수학 잘하는 사람들이 보면 바보로 보이겠지만) 내가 내린 결론은 다음과 같다.

4개의 문장에 대한 매트릭스에 textrank 알고리즘 적용하기

알고리즘에서 (1-d)를 우변에 나머지를 좌변에 놓은 뒤 각 문장을 구하는 식을 4번을 반복한다.
좌변에는 변수 4개와 상수들이 있고 우변의 1-d는 정해진 값이니까 이는 하나의 연립방정식과 같다.
따라서 상수로 이루어진 (4, 4) 행렬과 변수로 이루어진 (4, 1)행렬을 곱한 것을 연립방정식으로 풀면 각 문장의 중요도를 도출할 수 있다.

위 알고리즘 구현 코드가 도저히 이해가 가지 않아 머리가 빡칠 떄복잡할 때 다른 코드들도 살펴봤다 
https://towardsdatascience.com/textrank-for-keyword-extraction-by-python-c0bae21bcec0

TextRank for Keyword Extraction by Python

여기선 tf-idf를 구하진 않지만 문장 간의 관계도를 매트릭스로 나타내는 것은 똑같다. 그리고 코드 구현도 그냥 바로 이해할 수 있다.

import numpy as np
g = [[0, 0, 0.5, 0],
     [0, 0, 0.5, 1],
     [1, 0.5, 0, 0],
     [0, 0.5, 0, 0]]
g = np.array(g)
pr = np.array([1, 1, 1, 1]) # initialization for a, b, e, f is 1
d = 0.85
for iter in range(10):
    pr = 0.15 + 0.85 * np.dot(g, pr)
    print(iter)
    print(pr)

위의 코드와 이 코드의 차이점이 뭘까?
내 결론은 위 코드는 각 문장의 rank 를 변수로 놓고 그것을 구하는 과정이고,
이 코드는 각 문장의 rank를 1로 두고 매트릭스(가중치)값을 곱하면서 rank를 조정해나가는 것 같다.

두 개의 코드를 모두 돌렸을 때 같은 문장에서 중요하다고 말하는 순서가 약간씩 다르다.

1번째 코드

2번째 코드

첫 번째는 가장 중요한 문장 3개를 0, 1, 4를 뽑았고 두 번째는 0, 1, 7을 뽑았다. 여러 글들을 돌려본 결과 대부분 첫 번째와 두 번째 값은 동이랗나 세 번째 문장을 판단하는 데서 차이를 보인다.

**

훠우... 머리 아픈데 재밌다.