TextRank算法

TextRank是一种用来做关键词提取的算法，也可以用于提取短语和自动摘要。因为TextRank是基于PageRank的，所以首先简要介绍下PageRank算法。

(1)PageRank

PageRank设计之初是用于Google的网页排名的，以该公司创办人拉里·佩奇（Larry Page）之姓来命名。Google用它来体现网页的相关性和重要性，在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。PageRank通过互联网中的超链接关系来确定一个网页的排名，其公式是通过一种投票的思想来设计的：如果我们要计算网页A的PageRank值（以下简称PR值），那么我们需要知道有哪些网页链接到网页A，也就是要首先得到网页A的入链，然后通过入链给网页A的投票来计算网页A的PR值。这样设计可以保证达到这样一个效果：当某些高质量的网页指向网页A的时候，那么网页A的PR值会因为这些高质量的投票而变大，而网页A被较少网页指向或被一些PR值较低的网页指向的时候,A的PR值也不会很大，这样可以合理地反映一个网页的质量水平。那么根据以上思想，佩奇设计了下面的公式：

$PR(V_i) = (1-d) + d * sum_{j in In(V_i)} frac{1}{|Out(V_j)|}PR(V_j)$

该公式中，V_i表示某个网页，V_j表示链接到Vi的网页（即V_i的入链），S(V_i)表示网页V_i的PR值，In(V_i)表示网页V_i的所有入链的集合,Out(V_j)表示网页，d表示阻尼系数，是用来克服这个公式中“d *”后面的部分的固有缺陷用的：如果仅仅有求和的部分，那么该公式将无法处理没有入链的网页的PR值，因为这时，根据该公式这些网页的PR值为0，但实际情况却不是这样，所有加入了一个阻尼系数来确保每个网页都有一个大于0的PR值，根据实验的结果，在0.85的阻尼系数下，大约100多次迭代PR值就能收敛到一个稳定的值，而当阻尼系数接近1时，需要的迭代次数会陡然增加很多，且排序不稳定。公式中S(V_j)前面的分数指的是V_j所有出链指向的网页应该平分V_j的PR值，这样才算是把自己的票分给了自己链接到的网页.

(2)TextRank算法提取关键词

TextRank是由PageRank改进而来，其公式有颇多相似之处，这里给出TextRank的公式：

$WS(V_i) = (1-d) + d * sum_{j in In(V_i)} frac{w_{ji}}{sum_{V_k in Out(V_j)} w_{jk}} WS(V_j)$

可以看出，该公式仅仅比PageRank多了一个权重项W_ji，用来表示两个节点之间的边连接有不同的重要程度。TextRank用于关键词提取的算法如下：

　　 (1）把给定的文本T按照完整句子进行分割;
　　（2）对于每个句子，进行分词和词性标注处理，并过滤掉停用词，只保留指定词性的单词，如名词、动词、形容词;
　　（3）构建候选关键词图G = (V,E)，其中V为节点集，由（2）生成的候选关键词组成，然后采用共现关系（co-occurrence）构造任两点之间的边，两个节点之间存在边仅当它们对应的词汇在长度为K的窗口中共现，K表示窗口大小，即最多共现K个单词。
　　（4）根据上面公式，迭代传播各节点的权重，直至收敛。
　　（5）对节点权重进行倒序排序，从而得到最重要的T个单词，作为候选关键词。
　　（6）由（5）得到最重要的T个单词，在原始文本中进行标记，若形成相邻词组，则组合成多词关键词。例如，文本中有句子“Matlab code for plotting ambiguity function”，如果“Matlab”和“code”均属于候选关键词，则组合成“Matlab code”加入关键词序列。

实现细节,具体可以看看源码.下面是源码中的一些细节:

首先定义一个无向有权图，然后对句子进行分词；依次遍历分词结果，如果某个词i满足过滤条件（词性在词性过滤集合中，并且词的长度大于等于2，并且词不是停用词），然后将这个词之后窗口长度为5范围内的词j（这些词也需要满足过滤条件），将它们两两（词i和词j）作为key，出现的次数作为value，添加到共现词典中；

然后，依次遍历共现词典，将词典中的每个元素，key = （词i，词j），value = 词i和词j出现的次数，其中词i，词j作为一条边起始点和终止点，共现的次数作为边的权重，添加到之前定义的无向有权图中。

然后对这个无向有权图进行迭代运算textrank算法，最终经过若干次迭代后，算法收敛，每个词都对应一个指标值；

如果设置了权重标志位，则根据指标值值对无向有权图中的词进行降序排序，最后输出topK个词作为关键词；

其中，无向有权图的的定义及实现是在UndirectWeightedGraph类中实现的。根据UndirectWeightedGraph类的初始化函数__init__，我们可以发现，所谓的无向有权图就是一个词典，词典的key是后续要添加的词，词典的value，则是一个由（起始点，终止点，边的权重）构成的三元组所组成的列表，表示以这个词作为起始点的所有的边。

无向有权图添加边的操作是在addEdge函数中完成的，因为是无向图，所以我们需要依次将start作为起始点，end作为终止点，然后再将start作为终止点，end作为起始点，这两条边的权重是相同的。

def textrank(self, sentence, topK=20, withWeight=False, allowPOS=('ns', 'n', 'vn', 'v'), withFlag=False):

    self.pos_filt = frozenset(allowPOS)
    # 定义无向有权图
    g = UndirectWeightedGraph()
    # 定义共现词典
    cm = defaultdict(int)
    # 分词
    words = tuple(self.tokenizer.cut(sentence))
    # 依次遍历每个词
    for i, wp in enumerate(words):
        # 词i 满足过滤条件
        if self.pairfilter(wp):
            # 依次遍历词i 之后窗口范围内的词
            for j in xrange(i + 1, i + self.span):
                # 词j 不能超出整个句子
                if j >= len(words):
                    break
                # 词j不满足过滤条件，则跳过
                if not self.pairfilter(words[j]):
                    continue
                # 将词i和词j作为key，出现的次数作为value，添加到共现词典中
                if allowPOS and withFlag:
                    cm[(wp, words[j])] += 1
                else:
                    cm[(wp.word, words[j].word)] += 1
    # 依次遍历共现词典的每个元素，将词i，词j作为一条边起始点和终止点，共现的次数作为边的权重
    for terms, w in cm.items():
        g.addEdge(terms[0], terms[1], w)
    
    # 运行textrank算法
    nodes_rank = g.rank()
    
    # 根据指标值进行排序
    if withWeight:
        tags = sorted(nodes_rank.items(), key=itemgetter(1), reverse=True)
    else:
        tags = sorted(nodes_rank, key=nodes_rank.__getitem__, reverse=True)

    # 输出topK个词作为关键词
    if topK:
        return tags[:topK]
    else:
        return tags
其中，无向有权图的的定义及实现是在UndirectWeightedGraph类中实现的。根据UndirectWeightedGraph类的初始化函数__init__，我们可以发现，所谓的无向有权图就是一个词典，词典的key是后续要添加的词，词典的value，则是一个由（起始点，终止点，边的权重）构成的三元组所组成的列表，表示以这个词作为起始点的所有的边。
无向有权图添加边的操作是在addEdge函数中完成的，因为是无向图，所以我们需要依次将start作为起始点，end作为终止点，然后再将start作为终止点，end作为起始点，这两条边的权重是相同的。
def addEdge(self, start, end, weight):
    # use a tuple (start, end, weight) instead of a Edge object
    self.graph[start].append((start, end, weight))
    self.graph[end].append((end, start, weight))
执行textrank算法迭代是在rank函数中完成的。
首先对每个结点赋予相同的权重，以及计算出该结点的所有出度的次数之和；
然后迭代若干次，以确保得到稳定的结果；
在每一次迭代中，依次遍历每个结点；对于结点n，首先根据无向有权图得到结点n的所有
入度结点（对于无向有权图，入度结点与出度结点是相同的，都是与结点n相连的结点），在前面我们已经计算出这个入度结点的所有出度的次数，而它对于结点n的权值的贡献等于它本身的权值 乘以 它与结点n的共现次数 / 这个结点的所有出度的次数 ，将各个入度结点得到的权值相加，再乘以一定的阻尼系数，即可得到结点n的权值；
迭代完成后，对权值进行归一化，并返回各个结点及其对应的权值。
def rank(self):
    ws = defaultdict(float)
    outSum = defaultdict(float)

    wsdef = 1.0 / (len(self.graph) or 1.0)
    # 初始化各个结点的权值
    # 统计各个结点的出度的次数之和
    for n, out in self.graph.items():
        ws[n] = wsdef
        outSum[n] = sum((e[2] for e in out), 0.0)

    # this line for build stable iteration
    sorted_keys = sorted(self.graph.keys())
    # 遍历若干次
    for x in xrange(10):  # 10 iters
        # 遍历各个结点
        for n in sorted_keys:
            s = 0
            # 遍历结点的入度结点
            for e in self.graph[n]:
                # 将这些入度结点贡献后的权值相加
                # 贡献率 = 入度结点与结点n的共现次数 / 入度结点的所有出度的次数
                s += e[2] / outSum[e[1]] * ws[e[1]]
            # 更新结点n的权值
            ws[n] = (1 - self.d) + self.d * s

    (min_rank, max_rank) = (sys.float_info[0], sys.float_info[3])

    # 获取权值的最大值和最小值
    for w in itervalues(ws):
        if w < min_rank:
            min_rank = w
        if w > max_rank:
            max_rank = w

    # 对权值进行归一化
    for n, w in ws.items():
        # to unify the weights, don't *100.
        ws[n] = (w - min_rank / 10.0) / (max_rank - min_rank / 10.0)

    return ws

完结