TextRank 演算法介紹

7 min readAug 15, 2019

在自然語言處理的領域中，自動抽取摘要(Automatic Text Summarization)是很重要的一塊次領域。若能自動化地從文章中抽取出有意義的摘要，也可以這些特徵進行匹配或是應用於問答系統上(也許用來看論文就很有幫助了)。在自動摘要的相關做法上，主要分為兩種：

- 抽取法(Extractive Method)：從原文中抽取部分內容作為摘要。
- 抽象法(Abstractiva Method)：了解文章大意後，自動產生摘要。

可以想見抽取法所得到的摘要一定是原文有出現過的(句子、字詞)，而抽象法則可能產生出原本沒看過的語句(類似換句話說)。今天要介紹的TextRank演算法是屬於抽取法中常被使用的方法。

TextRank 簡介

TextRank是受到google團隊發展的PageRank演算法啟發，原先是使用在計算網頁的相關性與重要程度上，作為排序搜尋結果的依據。然而相似概念可用於計算文章中句子的重要程度(用以摘要)。

在TextRank的概念中，能夠作為摘要的句子條件為與文章中其他句子相似度最高，在使用上可以特別注意任務特性是否也符合這個假設。

TextRank 演算法內容

在講TextRank的概念下，單一篇文章中句子與句子之間的關聯會以網路做呈現。每一句句子為一個節點(vertices)、而句子與句子之間會相連，連接的權重則為句子之間的相似程度。

(下圖為graph的範例)

TextRank的演算法如下：

其中

- $V_i$為節點
- h(V_i)為某個節點的TextRank分數
- $d$為阻尼係數，為定值且介於0~1之間，常被設定成0.85
- $W_{ji}$為節點之間相連的權重

可以看到TextRank分數主要可以拆成兩個部分，在d已被確定的情況下，前面的部分是很單純的常數(1-d)，而後面的部分則為從其他節點所分配到的重要度。

第二部分的意義為針對每一個其他的節點 j ，計算節點 i 與此節點 j 的權重所占比例，再乘上節點 j 的TextRank分數。代表其他節點所貢獻的重要程度(節點 j 本身越重要或是彼此之間的連結權重比例越高，提供的數值就越高)

在實際的計算上，將會初始化每個節點的TextRank分數，並依照上面的公式迭代更新節點的TextRank數值$h(V_i)$直到收斂。

註：在此呈現的是weighted & undirected 版本的公式，然而只要做簡單的公式變換就可以應用到無權重的狀況或是有向圖上。

TextRank 計算範例

假設我們有一篇文章並包含四個句子，且四個句子的相似性矩陣(權重)如下(這邊假設相似程度只有相似/不相似兩種狀況)。

若畫成網路圖的樣子則如下，可以發現A句與其他句子的相似度較低，而B句與其他句子的相似程度都很高。

初始每個句子的TextRank數值皆為1，並且訂定 d=0.85，迭代的結果如下，經過迭代後各句的TextRank數值會將會收斂到特定的一個數值。依照此演算法，B句子為重要程度最高的句子，可用於摘要。

關聯程度計算方式

在TextRank的使用上，最重要的莫過於決定句子間關聯程度的計算方式為何。在最原始的版本上，句子之間的相似程度計算方式如下：

其中
- $S_i$為句子
- $w_k$為詞

以文字描述則為”兩句子中交集的字詞數量除以兩句子log(字詞數量)相加”。然而除了以這樣的方式計算句子的相似度，也可以使用其他相似程度的計算方式例如編輯距離、餘弦相似度、甚至是將句子以詞嵌入進行轉換後再做相關的運算皆可。

TextRank用於關鍵詞選取

如先前所述，此概念同樣也可以給予每個詞一個重要程度並以此作為關鍵詞的選取依據，此時字詞之間的關聯程度則常以字詞的共現性作為指標，會以移動窗格的方式做計算。

另外，由於字詞之間可以有順序性的關係，因此除了選取目標詞左右的詞當作共同出現的詞之外，也有只擷取目標詞右方(接續)的其他字詞的作法(此時圖形會改變為有向圖)。

TextRank 在 Python 上的實作

目前個人已知在Python上有支援TextRank的套件有gensimsumma、pytextrank、jieba、TextRank4ZH、snownlp。然而各自的實作仍然有些差異，以下僅以所知道或嘗試過的部分進行整理。

註：由於pytextrank個人並未使用過，因此在這邊不會特別提到，然下方將會提供相關連結讓有興趣的讀者做參考

gensim套件

gensim套件的textrank演算法包含摘要與關鍵詞萃取兩個功能，放在gensim.summarization模組中。

gensim.summarisation.summarizer
gensim.summarisation.keywords

可給定一個字串並自動進行分句、摘要、或是關鍵詞萃取，使用的相似度計算方式為BM25。然而不支援中文分句與斷詞，因此若欲應用在中文文章上必須事先做處理使得文章的格式與英文雷同(詞與詞之間以空白鍵分隔，且每句以半形標點符號做結尾)。

summa套件

summa與gensim套件不同，是專門實作TextRank演算法的套件，用法跟模組命名與gensim相同，但針對關聯程度的函數做優化，且提供不同的函數(預設為jaacard相似度)與多語言可選擇(但還是不支援中文)。

summanlp

jieba套件

jieba的TextRank只提供關鍵詞抽取的方法，除了指定抽取出的關鍵詞數量外，也可以只選取特殊的詞性(預設為名詞與動詞)作為候選詞。

jieba

TextRank4ZH套件

TextRank4ZH如其名，是針對中文文本做TextRank的套件，提供關鍵詞與摘要兩功能，除了回傳關鍵詞/摘要外，另一個特色是也會回傳TextRank權重出來。(相似程度以原論文的算法做計算)

TextRank4ZH

snownlp套件

snownlp也是針對中文文本分析的套件，算是除了jieba以外也蠻常被提起的套件之一，除了最基本的斷詞之外，也提供了簡繁轉換、詞性標註、情感分析、文本分類、關鍵詞提取、文本摘要、文本相似度判斷等多項功能。上述提到的關鍵詞提取與文本摘要就直接對應到了TextRank的演算法。

snownlp

以上大略說明了在python中可以尋找到的套件資源，但可以發現TextRank演算法在實作上還是有很多可以調整的地方，關鍵點仍然在於文字的前處理(如斷詞精確度)或是相似度的計算上，另外，由於TextRank演算法複雜度並不高，也可以考慮自己實作並作客製化的調整。