创新实训（6）——有关博客的摘要抽取的算法实现（TextRank）

标题由于进行数据抽取时&＃xff0c;必须顺便清洗数据&＃xff0c;所以实现一个简单的抽取式摘要生成算法&＃xff0c;来进行摘要的生成&＃xff0c;这里我用java实现了TextRank算法。

TextRank算法思想

与PageRank一样&＃xff0c;textrank算法给每一个句子一个权重&＃xff0c;然后根据一个句子与其他句子的相似程度&＃xff0c;将自己的权重按相似程度分配给其他句子&＃xff0c;为了避免某一个句子的权重变为0&＃xff0c;则需要加一个调和参数&＃xff0c;进行平滑。
具体的公式为&＃xff1a;

等式左边表示一个句子的权重&＃xff08;WS是weight_sum的缩写&＃xff09;&＃xff0c;右侧的求和表示每个相邻句子对本句子的贡献程度。与提取关键字的时候不同&＃xff0c;一般认为全部句子都是相邻的&＃xff0c;不再提取窗口。

求和的分母wji表示两个句子的相似程度&＃xff0c;分母又是一个weight_sum&＃xff0c;而WS(Vj)代表上次迭代j的权重。整个公式是一个迭代的过程。

相似程度的计算BM25算法

BM25算法常用来做搜索相关性的评分&＃xff0c;对Query进行语素解析&＃xff0c;生成语素qi;然后&＃xff0c;对于每个搜索结果D&＃xff0c;计算每个语素qi与D的相关性得分&＃xff0c;最后&＃xff0c;将qi相 对于D的相关性得分进行加权求和&＃xff0c;从而得到Query与D的相关性得分。

其中&＃xff0c;Q表示Query&＃xff0c;qi表示Q解析之后的一个语素(对中文而言&＃xff0c;我们可以把对Query的分词作为语素分析&＃xff0c;每个词看成语素qi。);d表示一个搜索结果文档;Wi表示语素qi的权重; R(qi&＃xff0c;d)表示语素qi与文档d的相关性得分。
下面用IDF来定义权重&＃xff1a;

其中&＃xff0c;N为索引中的全部文档数&＃xff0c;n(qi)为包含了qi的文档数
根据IDF的定义可以看出&＃xff0c;对于给定的文档集合&＃xff0c;包含了qi的文档数越多&＃xff0c;qi的权重则越低。也就是说&＃xff0c;当很多文档都包含了qi时&＃xff0c;qi的区分度就不高&＃xff0c;因此使用qi来判断相关性时的重要度就较低。

通过计算即可得到一句查询与一个文本的相似程度

BM25算法的实现

import java.util.List;
import java.util.Map;
import java.util.TreeMap;public class BM25 {/*** 文档句子的个数*/int D;/*** 文档句子的平均长度*/double avgdl;/*** 拆分为[句子[单词]]形式的文档*/List<List<String>> docs;/*** 文档中每个句子中的每个词与词频*/Map<String, Integer>[] f;/*** 文档中全部词语与出现在几个句子中*/Map<String, Integer> df;/*** IDF*/Map<String, Double> idf;/*** 调节因子*/final static float k1 &＃61; 1.5f;/*** 调节因子*/final static float b &＃61; 0.75f;public BM25(List<List<String>> docs){this.docs &＃61; docs;D &＃61; docs.size();//计算文档中句子的平均长度 总词数/句子总数for (List<String> sentence : docs){avgdl &＃43;&＃61; sentence.size();}avgdl /&＃61; D;f &＃61; new Map[D];df &＃61; new TreeMap<String, Integer>();idf &＃61; new TreeMap<String, Double>();init();}/*** 在构造时初始化自己的所有参数**/private void init(){int index &＃61; 0;//index表示现在是文档中的第几句话for (List<String> sentence : docs){//对于每个句子的分词结果 计算 分词在这个句子中出现的频率 为tf 存成String int的映射形式Map<String, Integer> tf &＃61; new TreeMap<String, Integer>();for (String word : sentence){//计算每个值出现的频数 作为tfInteger freq &＃61; tf.get(word);freq &＃61; (freq &＃61;&＃61; null ? 0 : freq) &＃43; 1;tf.put(word, freq);}f[index] &＃61; tf;//存储每句话对应的tf值Map//根据tf值算df值 计算每个词出现在几个句子中for (Map.Entry<String, Integer> entry : tf.entrySet()){String word &＃61; entry.getKey();Integer freq &＃61; df.get(word);freq &＃61; (freq &＃61;&＃61; null ? 0 : freq) &＃43; 1;df.put(word, freq);}&＃43;&＃43;index;}//根据df计算idf 公司为log(D - freq &＃43; 0.5) - Math.log(freq &＃43; 0.5) D为文档中句子个数 0.5为平滑项for (Map.Entry<String, Integer> entry : df.entrySet()){//计算逆文档频率 idfString word &＃61; entry.getKey();Integer freq &＃61; entry.getValue();idf.put(word, Math.log(D - freq &＃43; 0.5) - Math.log(freq &＃43; 0.5));}}/*** 计算相似度 最终得到一个句子 与对应index句子的相关性得分* &＃64;param sentence* &＃64;param index* &＃64;return*/public double sim(List<String> sentence, int index){double score &＃61; 0;//对于一句话中的每一个单词 计算这个单词 与其他句子的相关性得分 这个得分用BM25计算出for (String word : sentence){if (!f[index].containsKey(word)) {continue;}int d &＃61; docs.get(index).size();//index对应句子的词的个数Integer wf &＃61; f[index].get(word);//在index对应句子中 词word出现的次数//&＃xff0c;参数b的作用是调整文档长度对相关性影响的大小。b越大&＃xff0c;文档长度的对相关性得分的影响越大&＃xff0c;反之越小。而文档的相对长度越长&＃xff0c;K值将越大&＃xff0c;则相关性得//分会越小。这可以理解为&＃xff0c;当文档较长时&＃xff0c;包含qi的机会越大&＃xff0c;因此&＃xff0c;同等fi的情况下&＃xff0c;长文档与qi的相关性应该比短文档与qi的相关性弱。score &＃43;&＃61; (idf.get(word) * wf * (k1 &＃43; 1)/ (wf &＃43; k1 * (1 - b &＃43; b * d/ avgdl)));}//最终得到一个句子 与对应index句子的相关性得分return score;}/*** 计算整体的相似度 计算每一个句子与其他所有句子的相似度* &＃64;param sentence* &＃64;return*/public double[] simAll(List<String> sentence){double[] scores &＃61; new double[D];for (int i &＃61; 0; i < D; &＃43;&＃43;i){scores[i] &＃61; sim(sentence, i);}return scores;}
}

&＃xff08;1&＃xff09;我们将一段文字&＃xff0c;首先通过标点切分成句子&＃xff0c;然后将句子分词&＃xff0c;就可以得到[句子[单词]]形式的文档docs&＃xff0c;
然后对于句子中的每一个次计算tf值和idf值&＃xff08;tf值为某个分词在某句话中出现的频率 df为每个词出现在几个句子中 idf为df计算得出的逆文档频率&＃xff09;
&＃xff08;2&＃xff09;我们计算两句话之间的相似程度&＃xff0c;得到两个句子的相关性得分&＃xff0c;使用BM25算法。
&＃xff08;3&＃xff09;最终我们计算一个句子与其他所有句子的相似程度。

实现TextRank算法

import com.hankcs.hanlp.HanLP;
import com.hankcs.hanlp.dictionary.stopword.CoreStopWordDictionary;
import com.hankcs.hanlp.seg.common.Term;import java.util.*;/*** TextRank 自动摘要*/
public class TextRankSummary {/*** 阻尼系数&＃xff0c;一般取值为0.85*/final double d &＃61; 0.85f;/*** 最大迭代次数*/final int maxIter &＃61; 200;final double min_diff &＃61; 0.001f;/*** 文档句子的个数*/int docSentenceCount;/*** 拆分为[句子[单词]]形式的文档*/List<List<String>> docs;/*** 排序后的最终结果 score <-> index* 使用treemap 因为treemap自动按key排序*/TreeMap<Double, Integer> top;/*** 句子和其他句子的相关程度*/double[][] weight;/*** 该句子和其他句子相关程度之和*/double[] weightSum;/*** 迭代之后收敛的权重*/double[] vertex;/*** BM25相似度*/BM25 bm25;public TextRankSummary(List<List<String>> docs){this.docs &＃61; docs;bm25 &＃61; new BM25(docs);docSentenceCount &＃61; docs.size();// 句子和其他句子的相关程度weight &＃61; new double[docSentenceCount][docSentenceCount];weightSum &＃61; new double[docSentenceCount];//该句子和其他句子相关程度之和vertex &＃61; new double[docSentenceCount];//选出排名靠前的句子top &＃61; new TreeMap<Double, Integer>(Collections.reverseOrder());solve();}/*** 构造矩阵计算最相似的内容*/private void solve(){int cnt &＃61; 0;//对于文档中的每一句话 都要计算他与其他每一句话的相似程度 以及他与其他所有句子的总相似程度for (List<String> sentence : docs){//对于文档中的每一个句子 计算它与文档中其他所有句子的相似程度double[] scores &＃61; bm25.simAll(sentence);//将计算结果存储在矩阵中weight[cnt] &＃61; scores;// 减掉自己&＃xff0c;自己跟自己肯定最相似weightSum[cnt] &＃61; sum(scores) - scores[cnt];//所有句子权重初始化都为1vertex[cnt] &＃61; 1.0;&＃43;&＃43;cnt;}//开始使用textrank算法进行迭代 200轮for (int iter &＃61; 0; iter < maxIter; &＃43;&＃43;iter){double[] m &＃61; new double[docSentenceCount];double maxDiff &＃61; 0;for (int i &＃61; 0; i < docSentenceCount; &＃43;&＃43;i){m[i] &＃61; 1 - d;for (int j &＃61; 0; j < docSentenceCount; &＃43;&＃43;j){if (j &＃61;&＃61; i || weightSum[j] &＃61;&＃61; 0) {continue;}m[i] &＃43;&＃61; (d * weight[j][i] / weightSum[j] * vertex[j]);}double diff &＃61; Math.abs(m[i] - vertex[i]);if (diff > maxDiff){maxDiff &＃61; diff;}}vertex &＃61; m;if (maxDiff <&＃61; min_diff) {break;}}// 然后进行排序 输出权重最大的那个for (int i &＃61; 0; i < docSentenceCount; &＃43;&＃43;i){top.put(vertex[i], i);}}/*** 获取前几个关键句子* &＃64;param size 要几个* &＃64;return 关键句子的下标*/public int[] getTopSentence(int size){Collection<Integer> values &＃61; top.values();size &＃61; Math.min(size, values.size());int[] indexArray &＃61; new int[size];Iterator<Integer> it &＃61; values.iterator();for (int i &＃61; 0; i < size; &＃43;&＃43;i){indexArray[i] &＃61; it.next();}return indexArray;}/*** 简单的求和* &＃64;param array* &＃64;return*/private static double sum(double[] array){double total &＃61; 0;for (double v : array){total &＃43;&＃61; v;}return total;}/*** 将文章分割为句子 分割依据为标点符号* &＃64;param document* &＃64;return*/static List<String> spiltSentence(String document){List<String> sentences &＃61; new ArrayList<String>();if (document &＃61;&＃61; null) {return sentences;}String regex1 &＃61; "[\r\n]";String regex2 &＃61; "[&＃xff0c;,。:&＃xff1a;“”&＃xff1f;?&＃xff01;!&＃xff1b;;]";for (String line : document.split(regex1)) {line &＃61; line.trim();if (line.length() &＃61;&＃61; 0) {continue;}for (String sent : line.split(regex2)){sent &＃61; sent.trim();if (sent.length() &＃61;&＃61; 0) {continue;}sentences.add(sent);}}return sentences;}/*** 是否应当将这个term纳入计算&＃xff0c;词性属于名词、动词、副词、形容词* &＃64;param term* &＃64;return 是否应当*/public static boolean shouldInclude(Term term) {return CoreStopWordDictionary.shouldInclude(term);}/*** 一句话调用接口* &＃64;param document 目标文档* &＃64;param size 需要的关键句的个数* &＃64;return 关键句列表*/public static String getTopSentenceList(String document, int size) {List<String> sentenceList &＃61; spiltSentence(document);//存储句子分词后的结果List<List<String>> docs &＃61; new ArrayList<List<String>>();for (String sentence : sentenceList) {//利用HanLP的接口将句子进行分词List<Term> termList &＃61; HanLP.segment(sentence);List<String> wordList &＃61; new LinkedList<String>();//是否应当将这个term纳入计算&＃xff0c;词性属于名词、动词、副词、形容词for (Term term : termList) {if (shouldInclude(term)) {wordList.add(term.word);}}docs.add(wordList);}TextRankSummary textRankSummary &＃61; new TextRankSummary(docs);//然后获取排名最高的几个句子int[] topSentence &＃61; textRankSummary.getTopSentence(size);List<String> resultList &＃61; new LinkedList<String>();for (int i : topSentence) {resultList.add(sentenceList.get(i));}String result &＃61; String.join("-",resultList);return result;}}


&＃xff08;1&＃xff09;首先&＃xff0c;输入目标文本和需要生成的摘要个数&＃xff0c;然后我们现将文本&＃xff0c;通过标点符号切分成句子&＃xff0c;然后对每句话进行分词&＃xff0c;这里分词使用了HanLP库&＃xff08;https://github.com/hankcs/hanlp&＃xff09;&＃xff0c;最后得到文档docs。
&＃xff08;2&＃xff09;然后通过docs使用BM25算法&＃xff0c;计算每句话相互之间的文本相似度
&＃xff08;3&＃xff09;有了每句话的相似度之后&＃xff0c;就可以给每个句子一个初始的权重&＃xff0c;使用textrank算法&＃xff0c;结合句子之间的相似度进行迭代&＃xff0c;迭代200轮之后&＃xff0c;停止迭代&＃xff0c;输出权重最高的句子作为这篇文本的摘要。
&＃xff08;与pagerank算法思想相同&＃xff0c;将自己的权重通过文本相似度的不同按比例分给不同的其他文本&＃xff0c;自己也获得其他文本传来的权重&＃xff0c;然后逐渐收敛&＃xff09;

最终的效果为

他只是抽取了几句&＃xff0c;在文本中权重比较大的句子&＃xff0c;语义之间没有连贯性&＃xff0c;效果很不好。

明天准备尝试以下深度学习的方法来进行摘要的生成。