TextRank, PageRank

PageRank, TextRank 

 

TextRank는 Mihalcea(2004)이 제안한 알고리즘으로 텍스트에 관한 graph-based ranking model 입니다.

이는 Google의 PageRank를 활용한 알고리즘입니다. PageRank는 Brin and Page(1998)이 제안한 알고리즘으로 하이퍼링크를 가지는 웹 문서에 상대적 중요도에 따라 가중치를 부여하는 방법입니다. 서로간의 인용과 참조로 연결된 임의의 묶음으로 정의 할 수 있습니다. 예를 들어 소셜 네트워크에서 각 사람은 그래프의 node가 되고, 사람 간의 친밀도 혹은 영향럭은 edge로 표현된다고 생각하시면 됩니다.  ex formula) G = (N, E), N은 node를 의미하고 E는 edge를 의미합니다. 텍스트 데이터도 그래프로 표현할 수 있습니다.

 

이러한 방식으로 PageRank는 첫 페이지를 클릭할 확률 및 해당 전체 링크에서 다른 페이지로 가는 링크를 클릭할 확률 등 확률적으로 계산될 수 있습니다. 따라서 TextRank 또한 여러 문장에서 참조를 받는 형식으로 문장의 Ranking을 계산하는 알고리즘입니다. 

 

결과적으로는 어떤 마디가 그래프 내에서 중요한 마디가 될 수 있는가를 나타냅니다. 소셜 네트워크에서는 어떤 사람이 제일 큰 영향력을 가질 수 있는가에 대한 문제에 대답할 수 있으며, 단어 그래프에서는 그래프를 대표하는 핵심 단어를 선택할 수 있으며, 문단에서는 가장 핵심적인 문장을 선택할 수 있는 것이 바로 TextRank입니다.

 

TextRank

 

TextRank는 키워드 추출 기능과 핵심 문장 추출 기능이 있습니다. 키워드를 추출하기 위해서는 단어 그래프를 만들어야 합니다. 한 node로 표현되는 단어는 주어진 문서 집합에서 최소 빈도수 min_count 이상 등장한 단어들로 구성됩니다. 그리고 문장에서 이러한 단어들을 나누어줍니다.

 

그런 다음 TextRank에서 두 단어 간의 유사도를 정의하기 위해서는 두 단어 간의 co-occurrence를 계산합니다. 문장 내에서 두 단어의 간격이 사용자가 입력한 횟수입니다. TextRank 논문에서는 2~8 사이의 값을 이용하기를 추천했습니다. 추가적으로 전체 문장에 대해서는 -1로 입력할 수 있습니다.

 

TextRank에서는 명사, 동사, 형용사와 같은 단어만 단어 그래프를 만드는데 이용합니다. 모든 종류의 단어를 이용하면 전체적으로 실제로 밀접한 연관이 있지만 a와 the와 같이 큰 의미가 없는 단어들과의 연관성까지 높아져 단어들간의 연관도를 자세히 알 수 없기 때문입니다. 

 

TextRank based key-sentence extraction

 

TextRank를 이용하여 핵심 문장을 추출하기 위해서는 문장 그래프를 만들어야합니다. 이 때에는 각 문장이 node가 되며, 이때 edge는 문장 간 유사도 입니다. 일반적으로 문서, 문장 유사도를 측정하기 위해서는 Cosine similarity를 이하는데 두 문장에 공통으로 등장한 단어의 개수를 각 문장의 단어 개수의 log값의 합으로 나눈 것입니다.

 

이 결과는 최대값이 1이 아니며, 문장의 길이가 길수록 높은 유사도를 지닙니다. 문장 길이에 log를 부여하기 때문에 분모의 값이 커지는 것에 비해 분자의 값이 커지는 비율이 더 높기 때문에 다른 문장과 중복된 단어가 등장할 가능성이 높아집니다. 따라서 길이가 긴 문장을 선호합니다.

 

여러 문장과 높은 유사도를 지니기 위해서는 자주 등장한 단어들을 여러 개 포함해야 하는데 명사, 동사, 형용사와 같은 단어만 사용하였기 때문에 높은 유사도를 지니는 문장은 주어진 데이터에 자주 등장한 명사, 동사, 형용사 들로 이루어진 문장입니다. 이 때 반복적으로 사용되는 의미있는 단어들은 핵심 문장일 확률이 높아집니다.

 

하지만 이러한 측정의 단점은 문장의 길이가 길면 긴대로 짧으면 짧은 대로 문제가 있습니다. 대표적으로 짧은 경우를 살펴보면 2개의 단어 중 하나만 공통된 단여여도 절반이 넘는 단어가 공통으로 등장하였기 때문에 문제가 됩니다. 이러한 문제로 다른 문장 간 유사도를 이용하는 방법들이 제안되었지만 결과는 크게 다르지 않았습니다.

 

요약

• TextRank는 PageRank를 참고로 만든 알고리즘이다.
• 데이터에서 핵심 문장, 핵심 단어를 뽑아낼 수 있다.
• 하지만 문장의 길이에 대한 보완점이 필요하다.