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

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

• TextRank算法自動(dòng)摘要的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算法來(lái)抽取文本中的一些信息。

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.

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

TextRank通過(guò)不斷地迭代來(lái)提取關(guān)鍵詞，每一輪迭代，算法給圖中的頂點(diǎn)打分。直到滿足某個(gè)條件（比如說(shuō)迭代次數(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.

對(duì)于稀疏圖而言，邊的數(shù)目與頂點(diǎn)的數(shù)目成線性關(guān)系，對(duì)這樣的圖進(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)重來(lái)衡量頂點(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ò)濾規(guī)則：比如說(shuō)，去除掉分詞結(jié)果中的停用詞、根據(jù)詞性來(lái)添加頂點(diǎn)（比如只將名詞和動(dòng)詞作為圖的頂點(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)有邊？比如說(shuō)設(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)系后，接下來(lái)是確定邊上權(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。

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

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

英文、programmer、從事、程序

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

開(kāi)發(fā)、維護(hù)、專業(yè)、人員、分為、程序、設(shè)計(jì)、人員

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

中國(guó)、軟件、從業(yè)人員、分為、高級(jí)、程序員、系統(tǒng)分析員、項(xiàng)目經(jīng)理

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

從業(yè)人員、分為、程序員、高級(jí)、系統(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會(huì)比較重要。因?yàn)樗泥徑狱c(diǎn)會(huì)比較多，也即有很多其他Term給它投了票。這就有點(diǎn)類似于Term Frequency來(lái)衡量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_jin In(v_i)})

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

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

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

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

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)存儲(chǔ)了。

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

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

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

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

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

1. 當(dāng)(V_j)為‘確實(shí)‘時(shí)，(Out(V_j))為{‘說(shuō)‘，‘理‘}，因此：(Sigma_{V_kin Out(V_j)}w_{jk}=2)。于是，更新頂點(diǎn)‘理‘的得分：(1-d+d*(1/2)*0.8807971=0.5243387)。然后再通過(guò)m.put將臨時(shí)結(jié)果保存起來(lái)。

2. 接下來(lái)，for (String element : value)繼續(xù)，此時(shí)：(V_j)為頂點(diǎn)‘說(shuō)‘，由于頂點(diǎn)‘說(shuō)‘也有兩條鄰接邊，因此有：(Sigma_{V_kin 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_jin In(V_i)})，因?yàn)槊看味及延?jì)算好的結(jié)果再put回HashMap m中。

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

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

??????????????if?(max_diff?<=?min_diff)??????????????????break;

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

下面再來(lái)對(duì)代碼作個(gè)總體說(shuō)明：

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

????????for?(String?w?:?wordList)?{????????????if?(!words.containsKey(w))?{????????????????//排除了?wordList?中的重復(fù)term,?對(duì)每個(gè)已去重的term,?用?TreeSet?保存該term的鄰接頂點(diǎn)
????????????????words.put(w,?new?TreeSet());
????????????}????????????//?復(fù)雜度O(n-1)
????????????if?(que.size()?>=?5)?{????????????????//窗口的大小為5,是寫死的.?對(duì)于一個(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);
????????}

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

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

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

for?(int?i?=?0;?i?>?entry?:?words.entrySet())?{????????//...
????????for?(String?element?:?value)?{

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

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

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

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

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

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

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

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