图模型-随机游走算法

文章目录

推荐基本概念
PageRank
PersonalRank
TextRank
SimRank

PageRank

它的基本思想是，假设网页之前通过超链接相互连接，互联网上的所有网页便构成了一张图。用户随机的打开一个网页，并通过超链接跳转到另一个网页。每当用户到达一个网页，他都有两种选择，停留在当前网页或者通过继续访问其他网页。如果用户继续访问网页的概率为d，那么用户停留在当前网页的概率便是1-d。如果用户继续访问其他网页，则会以均匀分布的方式随机访问当前网页指向的另一网页，这是一个随机游走的过程。当用户多次访问网页后，每一个网页被访问到的概率便会收敛到某个值，而计算出来的结果便可以用于网页排名，我们用以下的公式来表示：

在这里插入图片描述

其中PR(i)是网页i被访问到的概率，d代表用户继续访问网页的概率，N为所有网页的数量，in(i)代表所有指向网页i的网页集合，out(j)代表网页j指向的其他网页集合。

接下来我们分析一下这个公式，网页i被访问到的概率由两部分组成：

第一部分是网页i作为起点，第一个被用户点击后停留在当前页面的概率，即:
第二部分是用户点击其他网页后(无论网页i是不是起点)，再次跳转回到网页i的概率:

这两部分的和便是网页i被点击到的概率

PersonalRank

在pageRank算法中计算出来的是每一个顶点相对其他顶点的相关性，代入到我们的用户物品二分图中，这显然不是我们想要的，我们需要的是所有物品相对于特定某个用户的相关性。

将用户行为表示为二分图模型。假设给用户u进行个性化推荐，要计算所有节点相对于用户u的相关度，则PersonalRank从用户u对应的节点开始游走，每到一个节点都以1−d的概率停止游走并从u重新开始，或者以d的概率继续游走，从当前节点指向的节点中按照均匀分布随机选择一个节点往下游走。这样经过很多轮游走之后，每个顶点被访问到的概率也会收敛趋于稳定，这个时候我们就可以用概率来进行排名了。在执行算法之前，我们需要初始化每个节点的初始概率值。如果我们对用户u进行推荐，则令u对应的节点的初始访问概率为1，其他节点的初始访问概率为0，然后再使用迭代公式计算。有公式如下：

在这里插入图片描述

对比pageRank，不同点只在于r的值不同，u代表根节点，即我们的目标用户节点，意思便是我们每次都是从目标用户节点出发，进行随机游走，而不同于pageRank的起点是随机从所有网页中进行选择，personalRank算法得出的结果便是所有顶点相对于目标用户结点的相关性

TextRank

1. TextRank 算法是一种用于文本的基于图的排序算法，通过把文本分割成若干组成单元（句子），构建节点连接图，用句子之间的相似度作为边的权重，通过循环迭代计算句子的TextRank值，最后抽取排名高的句子组合成文本摘要

抽取型摘要：这种方法依赖于从文本中提取几个部分，例如短语、句子，把它们堆叠起来创建摘要。因此，这种抽取型的方法最重要的是识别出适合总结文本的句子。
抽象型摘要：这种方法应用先进的NLP技术生成一篇全新的总结。可能总结中的文本甚至没有在原文中出现

现在我们已经掌握了PageRank，让我们理解TextRank算法。我列举了以下两种算法的相似之处：

用句子代替网页
任意两个句子的相似性等价于网页转换概率
相似性得分存储在一个方形矩阵中，类似于PageRank的矩阵M

在这里插入图片描述

2. 基于TextRank的文本关键词抽取是利用局部词汇关系，即共现窗口，对候选关键词进行排序，该方法的步骤如下：

（1）对于给定的文本D进行分词、词性标注和去除停用词等数据预处理操作。本分采用结巴分词，保留'n','nz','v','vd','vn','l','a','d'这几个词性的词语，最终得到n个候选关键词，即D=[t1,t2,…,tn] ；
（2）构建候选关键词图G=(V,E)，其中V为节点集，由候选关键词组成，并采用共现关系构造任两点之间的边，两个节点之间仅当它们对应的词汇在长度为K的窗口中共现则存在边，K表示窗口大小即最多共现K个词汇；
（3）根据公式迭代计算各节点的权重，直至收敛；
（4）对节点权重进行倒序排列，得到排名前TopN个词汇作为文本关键词。