Textrank演算法原理詳解

一、什麼是Textrank演算法

Textrank演算法是一種用於文本關鍵詞提取和摘要生成的演算法。它是PageRank演算法在文本領域的應用，基於圖的排序演算法。它通過建立文本關鍵詞之間的相似度計算圖，然後利用PageRank的思想對圖中的節點進行排序，最終得到文本中最重要的關鍵詞或句子。

它的優點在於不需要訓練語料庫，適用於各種語言和領域的文本，而且能夠捕捉文本的核心信息，提取出最具有代表性的關鍵詞或句子。

二、Textrank演算法的原理

Textrank演算法的原理可以分為以下幾個步驟：

1. 文本預處理

對原始文本進行分詞、去除停用詞、詞性標註和詞幹提取等預處理操作，得到文本單詞集合。

import jieba
import jieba.analyse

# 分詞
words = jieba.cut(text)

# 關鍵詞提取
keywords = jieba.analyse.extract_tags(text, topK=10)

2. 構建關鍵詞共現矩陣

統計文本中所有單詞之間的共現次數，構建關鍵詞共現矩陣。

import numpy as np

# 構建共現矩陣
matrix = np.zeros((len(words_dict), len(words_dict)))
for i in range(len(words_list)-window_size):
    for j in range(i+1, i+window_size):
        if words_list[i] in words_dict and words_list[j] in words_dict:
            matrix[words_dict[words_list[i]], words_dict[words_list[j]]] += 1
            matrix[words_dict[words_list[j]], words_dict[words_list[i]]] += 1

3. 計算節點之間的相似度

利用餘弦相似度計算所有節點之間的相似度。

# 計算餘弦相似度
def cosine_similarity(x, y):
    return np.dot(x, y) / (np.linalg.norm(x) * np.linalg.norm(y))

similarities = np.zeros((len(words_dict), len(words_dict)))
for i in range(len(words_dict)):
    for j in range(i+1, len(words_dict)):
        if matrix[i][j] > 0:
            similarities[i][j] = cosine_similarity(matrix[i], matrix[j])
            similarities[j][i] = similarities[i][j]

4. 利用PageRank思想對節點進行排序

利用PageRank的思想，將所有節點賦予初始權重，然後依次迭代更新節點的權重，直至收斂。

# 迭代計算節點權重
scores = np.ones(len(words_dict)) / len(words_dict)
for _ in range(max_iter):
    new_scores = np.zeros(len(words_dict))
    for i in range(len(words_dict)):
        for j in range(len(words_dict)):
            if similarities[i][j] > 0:
                new_scores[i] += similarities[i][j] * scores[j]
    scores = new_scores

三、Textrank演算法的應用

Textrank演算法可以應用於文本摘要、關鍵詞提取、主題識別等場景。

1. 文本摘要

在文本摘要中，我們可以將每個句子看成一個節點，構建句子相似度圖，然後利用Textrank演算法抽取出最重要的句子，組成摘要。

# 構建句子相似度圖
sentences = list(filter(lambda x: len(x)>5, re.split('[。！？]', text)))
graph = np.zeros((len(sentences), len(sentences)))
for i in range(len(sentences)):
    for j in range(i+1, len(sentences)):
        graph[i][j] = cosine_similarity(sentence_embedding[i], sentence_embedding[j])
        graph[j][i] = graph[i][j]

# 計算句子權重
scores = pagerank(graph)

# 抽取前k個句子組成摘要
summary_sentences = [sentences[i] for i in np.argsort(-scores)[:k]]
summary = ''.join(summary_sentences)

2. 關鍵詞提取

在關鍵詞提取中，我們可以利用Textrank演算法抽取出文本中的重要關鍵詞，作為文本的主題。

# 計算每個單詞的權重
word_scores = np.sum(similarities, axis=0)

# 抽取前k個關鍵詞
keywords = [words_list[i] for i in np.argsort(-word_scores)[:k]]

3. 主題識別

在主題識別中，我們可以將文本看成一個節點，根據與其他文本的相似度來衡量該文本的主題。

# 構建文本相似度圖
corpus = [text1, text2, text3, ...]
embeddings = [get_embedding(corpus[i]) for i in range(len(corpus))]
graph = np.zeros((len(corpus), len(corpus)))
for i in range(len(corpus)):
    for j in range(i+1, len(corpus)):
        graph[i][j] = cosine_similarity(embeddings[i], embeddings[j])
        graph[j][i] = graph[i][j]

# 計算文本權重
scores = pagerank(graph)

# 選擇得分最高的幾個文本作為該主題的代表
topic_docs = [corpus[i] for i in np.argsort(-scores)[:k]]

四、Textrank演算法的優化

Textrank演算法存在一些缺點，比如對長度較短的文本表現不佳、對詞頻較高的詞重視程度較低等。為了解決這些問題，可以採取以下優化措施：

1. 基於BM25演算法的權重計算

對於不同的辭彙，在計算權重的時候考慮它們在文檔中出現的次數和文檔集合中出現的頻率，這樣可以更好地反映辭彙的重要性。

import math

k1 = 1.2
b = 0.75

# 計算TF-IDF
def tf(word, doc):
    return doc.count(word) / len(doc)

def idf(word, corpus):
    return math.log(len(corpus) / sum([1 for doc in corpus if word in doc]))

def tf_idf(word, doc, corpus):
    return tf(word, doc) * idf(word, corpus)

# 計算BM25
def bm25(word, doc, corpus):
    idf = idf(word, corpus)
    tf = tf(word, doc)
    return idf * (tf * (k1+1)) / (tf + k1 * (1-b+b*len(doc)/avg_doc_len))

# 基於BM25計算節點權重
scores = np.zeros(len(words_dict))
for i in range(len(words_dict)):
    for j in range(len(words_dict)):
        if matrix[i][j] > 0:
            scores[i] += bm25(words_list[i], doc, corpus) * cosine_similarity(matrix[i], matrix[j])

2. 根據詞性過濾關鍵詞

對於一些詞性不太相關的辭彙，可以通過詞性過濾的方式來去除它們的影響。

# 構建詞性字典
pos_dict = {
    'n': ['n', 'ng', 'nr', 'nr1', 'nr2', 'nrj', 'nrf', 'ns', 'nsf', 'nt', 'nz'],
    'v': ['v', 'vg', 'vd', 'vn', 'vshi', 'vyou', 'vf', 'vx', 'vi']
}

# 根據詞性過濾
keywords = []
for w in words_list:
    pos = pseg.lcut(w)[0].flag[0]
    if len(w) > 1 and pos in pos_dict and pos_dict[pos]:
        if pos in ['n', 'ns', 'nz']:
            keywords.append(w)
        elif w in pos_dict[pos]:
            keywords.append(w)

五、總結

Textrank演算法是一種基於圖的排序演算法，通過構建文本關鍵詞相似度圖，利用PageRank的思想對關鍵詞節點進行排序，從而抽取出文本中最具有代表性的關鍵詞或句子。在文本摘要、關鍵詞提取、主題識別等場景中都有廣泛的應用。