標(biāo)簽：演示uil排除疑問ringrodpaptrylis

HanLP 關(guān)鍵詞提取算法分析

參考論文：《TextRank: Bringing Order into Texts》

TextRank算法提取關(guān)鍵詞的Java實(shí)現(xiàn)

TextRank算法自動摘要的Java實(shí)現(xiàn)這篇文章中作者大概解釋了一下TextRank公式

1. 論文

In this paper, we introduce the TextRank graphbased ranking model for graphs extracted from natural

language texts

TextRank是一個(gè)非監(jiān)督學(xué)習(xí)算法，它將文本中構(gòu)造成一個(gè)圖，將文本中感興趣的東西(比如分詞)當(dāng)成一個(gè)個(gè)頂點(diǎn)召耘，然后應(yīng)用TextRank算法來抽取文本中的一些信息赫冬。

Such keywords may constitute useful entries for building an automatic index for a document collection, can be used to classify a text, or may serve as a concise summary for a given document.

提取出來的關(guān)鍵詞善榛，可用來作為文本分類浅蚪，或者概括文本的中心思想。

TextRank通過不斷地迭代來提取關(guān)鍵詞，每一輪迭代亩冬，算法給圖中的頂點(diǎn)打分。直到滿足某個(gè)條件（比如說迭代次數(shù)克到200次硼身，或者設(shè)置的某個(gè)參數(shù)達(dá)到一個(gè)閾值）為止硅急。

For loosely connected graphs, with the number of edges proportional with the number of vertices,

undirected graphs tend to have more gradual convergence curves.

對于稀疏圖而言覆享，邊的數(shù)目與頂點(diǎn)的數(shù)目成線性關(guān)系，對這樣的圖進(jìn)行關(guān)鍵詞提取营袜，有著更平緩的收斂曲線（或者叫收斂得慢吧）

It may be therefore useful to indicate and incorporate into the model the “strength”

of the connection between two vertices $V_i$ and $V_j$ as a weight $w_{ij}$ added to the corresponding edge that connects the two vertices.

有時(shí)撒顿，圖中頂點(diǎn)之間的關(guān)系并不完全平等，比如某些頂點(diǎn)之間關(guān)系密切连茧，這里可用邊的權(quán)重來衡量頂點(diǎn)之間的相關(guān)性重要程度核蘸，而這就是帶權(quán)圖模型。

2. 源碼實(shí)現(xiàn)

2.1 關(guān)鍵詞提取流程

給定若干個(gè)句子啸驯，提取關(guān)鍵詞客扎。而TextRank算法是 graphbased ranking model，因此需要構(gòu)造一個(gè)圖罚斗，要想構(gòu)造圖徙鱼，就需要確定圖中的頂點(diǎn)如何構(gòu)造，于是就把句子進(jìn)行分詞针姿，將分得的每個(gè)詞作為圖中的頂點(diǎn)袱吆。

在選取某個(gè)詞作為圖的頂點(diǎn)的時(shí)候，可以應(yīng)用一些過濾規(guī)則：比如說距淫，去除掉分詞結(jié)果中的停用詞绞绒、根據(jù)詞性來添加頂點(diǎn)（比如只將名詞和動詞作為圖的頂點(diǎn)）……

The vertices added to the graph can be restricted with syntactic filters, which select only lexical units of a certain part of speech. One can for instance consider only nouns and verbs for addition to the graph, and consequently draw potential edges based only on relations that can be established between nouns and verbs.

在確定好哪些詞作為圖的頂點(diǎn)之后，另一個(gè)是確定詞與詞之間的關(guān)系榕暇，也即：圖中的哪些頂點(diǎn)有邊蓬衡？比如說設(shè)置一個(gè)窗口大小，落在這個(gè)窗口內(nèi)的詞彤枢，都添加一條邊狰晚。

it is the application that dictates the type of relations that are used to draw connections between any two such vertices,

確定了邊的關(guān)系后，接下來是確定邊上權(quán)值缴啡。這個(gè)也是根據(jù)實(shí)際情況而定壁晒。

2.2 根據(jù)窗口大小確定詞的鄰接點(diǎn)

前面提到，若干句話分詞之后业栅，得到的一個(gè)個(gè)的詞秒咐，或者叫Term。假設(shè)窗口大小為5碘裕。解釋一下TextRank算法提取關(guān)鍵詞的Java實(shí)現(xiàn)文章中提到的如何確定某個(gè)Term有哪些鄰接Term反镇。

比如說：‘程序員‘ 這個(gè)Term，它在多個(gè)句子中出現(xiàn)了娘汞，因此分詞結(jié)果‘程序員‘ 出現(xiàn)在四個(gè)地方：

索引0處：‘程序員‘的鄰接點(diǎn)有：

英文、programmer夕玩、從事你弦、程序

索引9處：‘程序員‘的鄰接點(diǎn)有：

開發(fā)惊豺、維護(hù)、專業(yè)禽作、人員尸昧、分為、程序旷偿、設(shè)計(jì)烹俗、人員

索引26處，‘程序員‘的鄰接點(diǎn)有：

中國萍程、軟件幢妄、從業(yè)人員、分為茫负、高級蕉鸳、程序員、系統(tǒng)分析員忍法、項(xiàng)目經(jīng)理

索引28處潮尝，‘程序員‘的鄰接點(diǎn)有：

從業(yè)人員、分為饿序、程序員勉失、高級、系統(tǒng)分析員原探、項(xiàng)目經(jīng)理乱凿、四大

結(jié)合這四處窗口中的所有的詞，得到‘程序員‘的鄰接點(diǎn)如下：

因此踢匣，當(dāng)窗口大小設(shè)置為5時(shí)告匠，Term的前后四個(gè)Term都將視為它的鄰接點(diǎn)，并且當(dāng)這個(gè)Term出現(xiàn)多次時(shí)离唬，則是將它各次出現(xiàn)位置處的前后4個(gè)Term合并后专，最終作為這個(gè)Term的鄰接點(diǎn)。

從這里可看出：如果某個(gè)Term在句子中出現(xiàn)了多次输莺，意味著該Term會比較重要戚哎。因?yàn)樗泥徑狱c(diǎn)會比較多，也即有很多其他Term給它投了票嫂用。這就有點(diǎn)類似于Term Frequency來衡量Term的重要性型凳。

2.3 得分(score)的更新算法

m.put(key, m.get(key) + d / size * (score.get(element) == null ? 0 : score.get(element)));代碼的解讀：

m.get(key)如果是第一次進(jìn)入for (String element : value)，則是拿到公式前半部分1-d的結(jié)果嘱函；如果是已經(jīng)在for (String element : value)進(jìn)行了迭代甘畅，for循環(huán)相當(dāng)于求和：\(\Sigma_{v_j\in In(v_i)}\)

for(String element : value) {intsize = words.get(element).size();? ? m.put(key, m.get(key) + d / size * (score.get(element) ==null?0: score.get(element)));}

以”他說的確實(shí)在理“ 舉例來說：，選取窗口大小為5，經(jīng)過分詞并去除停用詞后：

構(gòu)造的無向圖如下：（每條邊的權(quán)值都為1）

以頂點(diǎn)‘理‘為例疏唾，來看一下‘理‘的得分是如何被更新的蓄氧。在for (String element : value)一共有兩個(gè)頂點(diǎn)對 ‘理‘進(jìn)行投票，首先是 ‘確實(shí)‘頂點(diǎn)槐脏，與‘確實(shí)‘頂點(diǎn)鄰接的頂點(diǎn)有兩個(gè)喉童，因此：int size = words.get(element).size();中size=2。接下來顿天，來分解一下這行代碼：

m.put(key, m.get(key) + d / size * (score.get(element) ==null?0: score.get(element)))

m.get(key)為1-d堂氯，因?yàn)樵谕鈱觙or循環(huán)中，m.put(key, 1 - d)已經(jīng)公式的前半分部(1-d)存儲了牌废。

score.get(element) == null ? 0 : score.get(element)這個(gè)是獲取上一輪迭代的結(jié)果咽白。對于初始第一輪迭代而言，score.get(element)為0.8807971畔规，這個(gè)值是每個(gè)頂點(diǎn)的得分初始值：

//依據(jù)TF來設(shè)置初值,? words 代表的是 一張 無向圖for(Map.Entry> entry : words.entrySet()) {? ? ? ? ? ? ? score.put(entry.getKey(),sigMoid(entry.getValue().size()));//無向圖的每個(gè)頂點(diǎn) 得分值 初始化}

score.get(element)相當(dāng)于公式中的\(WS(V_j)\)

最后來分析一個(gè) size局扶，size是由代碼int size = words.get(element).size()獲得的，由于每條邊權(quán)值為1叁扫，size其實(shí)相當(dāng)于：\(\Sigma_{V_k\in Out(V_j)}w_{jk}\)三妈。

In(‘理‘)={‘確實(shí)‘，‘說‘}

當(dāng)\(V_j\)為‘確實(shí)‘時(shí)莫绣，\(Out(V_j)\)為{‘說‘畴蒲，‘理‘}，因此：\(\Sigma_{V_k\in Out(V_j)}w_{jk}=2\)对室。于是模燥，更新頂點(diǎn)‘理‘的得分：\(1-d+d*(1/2)*0.8807971=0.5243387\)。然后再通過m.put將臨時(shí)結(jié)果保存起來掩宜。

接下來蔫骂，for (String element : value)繼續(xù)，此時(shí)：\(V_j\)為頂點(diǎn)‘說‘牺汤，由于頂點(diǎn)‘說‘也有兩條鄰接邊辽旋，因此有：\(\Sigma_{V_k\in Out(V_j)}w_{jk}=2\)。于是更新頂點(diǎn)‘理‘的得分：\(0.5243387+d*(1/2)*0.8807971=0.89867747\)檐迟。而這就是第一輪迭代時(shí)补胚，頂點(diǎn)‘理‘的得分。

根據(jù)上面的1追迟、2中的步驟溶其，for (String element : value)就相當(dāng)于：\(\Sigma_{V_j\in In(V_i)}\)，因?yàn)槊看味及延?jì)算好的結(jié)果再put回HashMap m中敦间。

因此瓶逃，在第一輪迭代中束铭，頂點(diǎn)‘理‘的得分就是：0.89867747

類似于，經(jīng)過：max_iter次迭代厢绝，或者達(dá)到閾值：

if(max_diff <= min_diff)break;

時(shí)纯露，就不再迭代了。

下面再來對代碼作個(gè)總體說明：

這里是構(gòu)造無向圖的過程

for(String w : wordList) {if(!words.containsKey(w)) {//排除了 wordList 中的重復(fù)term, 對每個(gè)已去重的term, 用 TreeSet<String> 保存該term的鄰接頂點(diǎn)words.put(w,newTreeSet());? ? ? ? ? ? }// 復(fù)雜度O(n-1)if(que.size() >=5) {//窗口的大小為5,是寫死的. 對于一個(gè)term_A而言, 它的前4個(gè)term代芜、后4個(gè)term 都屬于term_A的鄰接點(diǎn)que.poll();? ? ? ? ? ? }for(String qWord : que) {if(w.equals(qWord)) {continue;? ? ? ? ? ? ? ? }//既然是鄰居,那么關(guān)系是相互的,遍歷一遍即可words.get(w).add(qWord);? ? ? ? ? ? ? ? words.get(qWord).add(w);? ? ? ? ? ? }? ? ? ? ? ? que.offer(w);? ? ? ? }

這里是對圖中每個(gè)頂點(diǎn)賦值一個(gè)初始score過程：

Map score =newHashMap();//保存最終每個(gè)關(guān)鍵詞的得分//依據(jù)TF來設(shè)置初值,? words 代表的是 一張 無向圖for(Map.Entry> entry : words.entrySet()) {? ? ? ? ? ? score.put(entry.getKey(),sigMoid(entry.getValue().size()));//無向圖的每個(gè)頂點(diǎn) 得分值 初始化}

接下來，三個(gè)for循環(huán)：第一個(gè)for循環(huán)代表迭代次數(shù)浓利；第二個(gè)for循環(huán)代表：對無向圖中每一個(gè)頂點(diǎn)計(jì)算得分挤庇；第三個(gè)for循環(huán)代表：對某個(gè)具體的頂點(diǎn)而言，計(jì)算它的每個(gè)鄰接點(diǎn)給它的投票權(quán)重贷掖。

for(inti =0; i < max_iter; ++i) {//....for(Map.Entry> entry : words.entrySet()) {//...for(String element : value) {

這樣嫡秕，就實(shí)現(xiàn)了論文中公式：

\[WS(v_i)=(1-d)+d*\Sigma_{V_j\in In(V_i)}\frac{w_{ji}}{\Sigma_{V_k\in Out(V_j)}w_{jk}}*WS(V_j)\]

而最終提取出來的關(guān)鍵詞是：

[理, 確實(shí), 說]

上面只是用 ”他說的確實(shí)在理“ 這句話 演示了TextRank算法的具體細(xì)節(jié)，在實(shí)際應(yīng)用中可能不合理苹威。因?yàn)闀嬖冢?/p>

現(xiàn)有統(tǒng)計(jì)信息不足以讓TextRank支持 某個(gè)詞 的重要性昆咽，算法有局限性。

可見：TextRank提取關(guān)鍵詞是受到分詞結(jié)果的影響的牙甫；其次掷酗，也受窗口大小的影響。雖然說代碼是大致看懂了窟哺，但是還是有一些疑問的：比如泻轰，為什么用上面那個(gè)公式計(jì)算，得分高的詞語就是關(guān)鍵詞了且轨？根據(jù)TextRank求關(guān)鍵詞與Term Frequency求關(guān)鍵詞有什么優(yōu)勢浮声？選取文本中的哪些詞建立模型作為圖的頂點(diǎn)？基于文本之間的什么樣的關(guān)系作為圖的邊旋奢？

文章來源于網(wǎng)絡(luò)