TextRank系列之关键词提取算法

用TextRank提取来提取关键词&＃xff0c;用PageRank的思想来解释它&＃xff1a;

• 如果一个单词出现在很多单词后面的话&＃xff0c;那么说明这个单词比较重要
• 一个TextRank值很高的单词后面跟着的一个单词&＃xff0c;那么这个单词的TextRank值会相应地因此而提高

  其思想非常简单&＃xff1a;通过词之间的相邻关系构建网络&＃xff0c;然后用PageRank迭代计算每个节点的rank值&＃xff0c;排序rank值即可得到关键词。PageRank本来是用来解决网页排名的问题&＃xff0c;网页之间的链接关系即为图的边&＃xff0c;迭代计算公式如下:

    PR(Vi)&＃61;(1−d)&＃43;d∗∑j∈In(Vi)1∣Out(Vj)∣PR(Vj)PR\left(V_{i}\right)&＃61;(1-d)&＃43;d * \sum_{j \in I n\left(V_{i}\right)} \frac{1}{\left|Out\left(V_{j}\right)\right|} PR\left(V_{j}\right)PR(Vi​)&＃61;(1−d)&＃43;d∗∑j∈In(Vi​)​∣Out(Vj​)∣1​PR(Vj​)

  其中&＃xff0c;PR(Vi)PR\left(V_{i}\right)PR(Vi​)表示结点ViV_{i}Vi​的 rank 值&＃xff0c;In(Vi)In(V_{i})In(Vi​)表示结点ViV_{i}Vi​的前驱结点集合&＃xff0c;Out(Vj){Out\left(V_{j}\right)}Out(Vj​)表示结点VjV_{j}Vj​的后继结点集合&＃xff0c;d为damping factor用于做平滑。

  网页之间的链接关系可以用图表示&＃xff0c;那么怎么把一个句子&＃xff08;可以看作词的序列&＃xff09;构建成图呢&＃xff1f;TextRank将某一个词与其前面的N个词、以及后面的N个词均具有图相邻关系&＃xff08;类似于N-gram语法模型&＃xff09;。具体实现&＃xff1a;设置一个长度为N的滑动窗口&＃xff0c;所有在这个窗口之内的词都视作词结点的相邻结点&＃xff1b;则TextRank构建的词图为无向图。下图给出了由一个文档构建的词图&＃xff08;去掉了停用词并按词性做了筛选&＃xff09;&＃xff1a;

  考虑到不同词对可能有不同的共现&＃xff08;co-occurrence&＃xff09;&＃xff0c;TextRank将共现作为无向图边的权值。那么&＃xff0c;TextRank的迭代计算公式如下&＃xff1a;

  WS(Vi)&＃61;(1−d)&＃43;d∗∑j∈In(Vi)wji∑Vk∈Out(Vj)wjkWS(Vj)W S\left(V_{i}\right)&＃61;(1-d)&＃43;d * \sum_{j \in I n\left(V_{i}\right)} \frac{w_{j i}}{\sum_{V_{k} \in O u t\left(V_{j}\right)} w_{j k}} W S\left(V_{j}\right)WS(Vi​)&＃61;(1−d)&＃43;d∗∑j∈In(Vi​)​∑Vk​∈Out(Vj​)​wjk​wji​​WS(Vj​)

评估&＃xff1a;

接下来将评估TextRank在关键词提取任务上的准确率、召回率与F1-Measure&＃xff0c;并与TFIDF做对比&＃xff1b;准确率计算公式如下&＃xff1a;

      Precision &＃61;1N∑i&＃61;0N−1∣Pi∩Ti∣∣Pi∣&＃61;\frac{1}{N} \sum_{i&＃61;0}^{N-1} \frac{\left|P_{i} \cap T_{i}\right|}{\left|P_{i}\right|}&＃61;N1​∑i&＃61;0N−1​∣Pi​∣∣Pi​∩Ti​∣​

其中&＃xff0c;N为文档数量&＃xff0c;PiP_{i}Pi​ 为文档i所提取出的关键词&＃xff0c;TiT_{i}Ti​为文档的标注关键词。召回率与F1的计算公式如下&＃xff1a;

      Precision &＃61;1N∑i&＃61;0N−1∣Pi∩Ti∣∣Ti∣&＃61;\frac{1}{N} \sum_{i&＃61;0}^{N-1} \frac{\left|P_{i} \cap T_{i}\right|}{\left|T_{i}\right|}&＃61;N1​∑i&＃61;0N−1​∣Ti​∣∣Pi​∩Ti​∣​

      F1&＃61;2∗Precision ∗RecallPrecision &＃43;Recall F 1&＃61;\frac{2 * \text { Precision } * \text { Recall}}{\text { Precision }&＃43;\text { Recall }}F1&＃61; Precision &＃43; Recall 2∗ Precision ∗ Recall​

  测试集是由刘知远老师提供的网易新闻标注数据集&＃xff0c;共有13702篇文档。Jieba完整地实现了关键词提取TFIDF与TextRank算法&＃xff0c;基于Jieba-0.39的评估实验代码如下&＃xff1a;

import jieba.analyse
import json
import codecsdef precision_recall_fscore_support(y_true, y_pred):"""evaluate macro precision, recall and f1-score."""doc_num &＃61; len(y_true)p_macro &＃61; 0.0r_macro &＃61; 0.0for i in range(doc_num):tp &＃61; 0true_len &＃61; len(y_true[i])pred_len &＃61; len(y_pred[i])for w in y_pred[i]:if w in y_true[i]:tp &＃43;&＃61; 1p &＃61; 1.0 if pred_len &＃61;&＃61; 0 else tp / pred_lenr &＃61; 1.0 if true_len &＃61;&＃61; 0 else tp / true_lenp_macro &＃43;&＃61; pr_macro &＃43;&＃61; rp_macro /&＃61; doc_numr_macro /&＃61; doc_numreturn p_macro, r_macro, 2 * p_macro * r_macro / (p_macro &＃43; r_macro)file_path &＃61; &＃39;data/163_chinese_news_dataset_2011.dat&＃39;
with codecs.open(file_path, &＃39;r&＃39;, &＃39;utf-8&＃39;) as fr:y_true &＃61; []y_pred &＃61; []for line in fr.readlines():d &＃61; json.loads(line)content &＃61; d[&＃39;content&＃39;]true_key_words &＃61; [w for w in set(d[&＃39;tags&＃39;])]y_true.append(true_key_words)# for w in true_key_words:# jieba.add_word(w)key_word_pos &＃61; [&＃39;x&＃39;, &＃39;ns&＃39;, &＃39;n&＃39;, &＃39;vn&＃39;, &＃39;v&＃39;, &＃39;l&＃39;, &＃39;j&＃39;, &＃39;nr&＃39;, &＃39;nrt&＃39;, &＃39;nt&＃39;, &＃39;nz&＃39;, &＃39;nrfg&＃39;, &＃39;m&＃39;, &＃39;i&＃39;, &＃39;an&＃39;, &＃39;f&＃39;, &＃39;t&＃39;,&＃39;b&＃39;, &＃39;a&＃39;, &＃39;d&＃39;, &＃39;q&＃39;, &＃39;s&＃39;, &＃39;z&＃39;]extract_key_words &＃61; jieba.analyse.extract_tags(content, topK&＃61;2, allowPOS&＃61;key_word_pos)# trank &＃61; jieba.analyse.TextRank()# trank.span &＃61; 5# extract_key_words &＃61; trank.textrank(content, topK&＃61;2, allowPOS&＃61;key_word_pos)y_pred.append(extract_key_words)prf &＃61; precision_recall_fscore_support(y_true, y_pred)print(&＃39;precision: {}&＃39;.format(prf[0]))print(&＃39;recall: {}&＃39;.format(prf[1]))print(&＃39;F1: {}&＃39;.format(prf[2]))


  其中&＃xff0c;每个文档提取的关键词数为2&＃xff0c;并按词性做过滤&＃xff1b;span表示TextRank算法中的滑动窗口的大小。评估结果如下&＃xff1a;

  其中&＃xff0c;每个文档提取的关键词数为2&＃xff0c;并按词性做过滤&＃xff1b;span表示TextRank算法中的滑动窗口的大小。评估结果如下&＃xff1a;

  如果将标注关键词添加到自定义词典&＃xff0c;则评估结果如下&＃xff1a;

  直观感受下关键词提取结果&＃xff08;添加了自定义词典&＃xff09;&＃xff1a;

// TFIDF, TextRank, labelled
[&＃39;文强&＃39;, &＃39;陈洪刚&＃39;] [&＃39;文强&＃39;, &＃39;陈洪刚&＃39;] {&＃39;文强&＃39;, &＃39;重庆&＃39;}
[&＃39;内贾德&＃39;, &＃39;伊朗&＃39;] [&＃39;伊朗&＃39;, &＃39;内贾德&＃39;] {&＃39;制裁&＃39;, &＃39;世博&＃39;, &＃39;伊朗&＃39;}
[&＃39;调控&＃39;, &＃39;王珏林&＃39;] [&＃39;调控&＃39;, &＃39;楼市&＃39;] {&＃39;楼市&＃39;, &＃39;调控&＃39;}
[&＃39;罗平县&＃39;, &＃39;男子&＃39;] [&＃39;男子&＃39;, &＃39;罗平县&＃39;] {&＃39;被砍&＃39;, &＃39;副局长&＃39;, &＃39;情感纠葛&＃39;}
[&＃39;佟某&＃39;, &＃39;黄玉&＃39;] [&＃39;佟某&＃39;, &＃39;黄现忠&＃39;] {&＃39;盲井&＃39;, &＃39;伪造矿难&＃39;}


从上述两组实验结果&＃xff0c;可以发现&＃xff1a;

• TextRank与TFIDF均严重依赖于分词结果——如果某词在分词时被切分成了两个词&＃xff0c;那么在做关键词提取时无法将两个词黏合在一起&＃xff08;TextRank有部分黏合效果&＃xff0c;但需要这两个词均为关键词&＃xff09;。因此是否添加标注关键词进自定义词典&＃xff0c;将会造成准确率、召回率大相径庭。
• TextRank的效果并不优于TFIDF。
• TextRank虽然考虑到了词之间的关系&＃xff0c;但是仍然倾向于将频繁词作为关键词。

此外&＃xff0c;由于TextRank涉及到构建词图及迭代计算&＃xff0c;所以提取速度较慢。

参考作者&＃xff1a;

作者&＃xff1a;Treant
出处&＃xff1a;http://www.cnblogs.com/en-heng/