PageRank算法与TextRank算法

PageRank

PageRank 是一种用于计算网页重要性的算法，其核心思想源自随机浏览模型。这个模型假设一个网络中的用户通过随机点击链接在网页之间跳转，并根据网页的链接结构计算每个网页的重要性。

假设三个网页按以下方式连接，计算每个网页的PR值。
PR公式：若A被B、C网页链接，则A的PR值为：B的PR值/B的链出总数，C的PR值/C的链出总数 ，再求和
 

import torch
 
 
def compute_page_rank(tol=1e-6, max_iter=100):
    # 定义网页之间的连接关系矩阵
    adjacency_matrix = torch.tensor([[1, 1, 0],
                                     [0, 0, 1],
                                     [0, 0, 0]], dtype=torch.float32)
 
    # 计算每个网页的出链总数，并进行归一化
    out_link_counts = torch.sum(adjacency_matrix, dim=0, keepdim=True)  # dim=0 按列计算出链总数
    normalized_adjacency_matrix = adjacency_matrix / out_link_counts
    normalized_adjacency_matrix[torch.isnan(normalized_adjacency_matrix)] = 0
 
    # 根据公式计算每个网页的 PageRank 值
    num_pages = adjacency_matrix.size(0)
    initial_page_rank = torch.tensor([[1.0 / num_pages]] * num_pages, dtype=torch.float32)
    page_rank = initial_page_rank
 
    damping_factor = 0.85
 
    # 开始迭代计算每个网页的 PageRank 值
    for _ in range(max_iter):
        new_page_rank = (1 - damping_factor) * initial_page_rank + damping_factor * (
                    normalized_adjacency_matrix @ page_rank)
 
        # 检查是否收敛
        if torch.norm(new_page_rank - page_rank, p=1) < tol:
            print(_)
            break
 
        page_rank = new_page_rank
    # 打印最终的 PageRank 值
    print('最终的 PageRank 值--->', page_rank.reshape(1, -1))
 
 
if __name__ == '__main__':
    compute_page_rank()

 2
最终的 PageRank 值---> tensor([[0.8575, 0.0925, 0.0500]])

 从结果得出，网页重要性

TextRank

TextRank 是一种用于文本中的关键词提取和摘要生成的算法，灵感来自于 PageRank 算法。TextRank 通过图论的方法来评估词或句子的相对重要性。

生活如同一杯苦酒，不会苦一辈子，但会苦一阵子

分词结果：['生活', '一杯', '酒’, '苦', '一辈子', ‘但会’, '苦', '一阵子']

去重结果：['生活', '一杯', '酒', '苦', '一辈子', '但会', '一阵子'] 

TR公式：若词A与B、C共现，则A的PR值为：AB的共现值/B的链出总数，AC的共现值/C的链出总数 ，再求和

import torch
import networkx as nx
import matplotlib.pyplot as plt
 
 
def compute_text_rank():
 
    # 构建词与其他词的共现矩阵
    co_occurrence_matrix = torch.tensor([[0, 1, 0, 0, 0, 0, 0],
                                         [1, 0, 1, 0, 0, 0, 0],
                                         [0, 1, 0, 1, 0, 0, 0],
                                         [0, 0, 1, 0, 1, 1, 1],
                                         [0, 0, 0, 1, 0, 1, 0],
                                         [0, 0, 0, 1, 1, 0, 0],
                                         [0, 0, 0, 1, 0, 0, 0]], dtype=torch.float32)
 
    # 计算每个词的链出总数，并对共现矩阵进行归一化处理
    outgoing_links_sum = torch.sum(co_occurrence_matrix, dim=0, keepdim=True)
    normalized_co_occurrence_matrix = co_occurrence_matrix / outgoing_links_sum
 
    # 绘制词之间的共现关系图
    graph = nx.from_numpy_array(normalized_co_occurrence_matrix.numpy())
    node_labels = {idx: word for idx, word in enumerate(['生活', '一杯', '酒', '苦', '一辈子', '但会', '一阵子'])}
    nx.draw_networkx(graph, labels=node_labels)
    plt.rcParams['font.sans-serif'] = ['SimHei']
    plt.show()
 
    # 每个词的初始 TextRank 值
    initial_text_rank = torch.tensor([[1/7],
                                      [1/7],
                                      [1/7],
                                      [1/7],
                                      [1/7],
                                      [1/7],
                                      [1/7]], dtype=torch.float32)
 
    # 阻尼系数
    damping_factor = 0.85
 
    # 迭代求解
    text_rank = initial_text_rank
    for _ in range(100):
        text_rank = (1 - damping_factor) * initial_text_rank + damping_factor * (normalized_co_occurrence_matrix @ text_rank)
 
    # 打印每个词的 TextRank 值
    print("每个词的 TextRank 值：", text_rank.reshape(1, -1))
 
 
if __name__ == '__main__':
    compute_text_rank()

每个词的 TextRank 值： tensor([[0.0887, 0.1582, 0.1445, 0.2627, 0.1344, 0.1344, 0.0773]])

 基于结果，'一杯', '酒', '苦', '一辈子', '但会'适合做关键词