談起自動摘要演算法，常見的並且最易實現的當屬TF-IDF，但是感覺TF-IDF效果一般，不如TextRank好。 TextRank是在 Google的PageRank演算法啟發下，針對文本里的句子設計的權重演算法，目標是自動摘要。它利用投票的原理，讓每一個單詞給它的鄰居（術語稱視窗） 投贊成票，票的權重取 ...
談起自動摘要演算法，常見的並且最易實現的當屬TF-IDF，但是感覺TF-IDF效果一般，不如TextRank好。
TextRank是在 Google的PageRank演算法啟發下，針對文本里的句子設計的權重演算法，目標是自動摘要。它利用投票的原理，讓每一個單詞給它的鄰居（術語稱視窗） 投贊成票，票的權重取決於自己的票數。這是一個“先有雞還是先有蛋”的悖論，PageRank採用矩陣迭代收斂的方式解決了這個悖論。TextRank也 不例外：
PageRank的計算公式：
正規的TextRank公式
正規的TextRank公式在PageRank的公式的基礎上，引入了邊的權值的概念，代表兩個句子的相似度。
但是很明顯我只想計算關鍵字，如果把一個單詞視為一個句子的話，那麼所有句子（單詞）構成的邊的權重都是0（沒有交集，沒有相似性），所以分子分母的權值w約掉了，演算法退化為PageRank。所以說，這裡稱關鍵字提取演算法為PageRank也不為過。
另外，如果你想提取關鍵句（自動摘要）的話，請參考姊妹篇《TextRank演算法自動摘要的Java實現》。
TextRank的Java實現
先看看測試數據：
程式員(英文Programmer)是從事程式開發、維護的專業人員。一般將程式員分為程式設計人員和程式編碼人員，但兩者的界限並不非常清楚，特別是在中國。軟體從業人員分為初級程式員、高級程式員、系統分析員和項目經理四大類。
我取出了百度百科關於“程式員”的定義作為測試用例，很明顯，這段定義的關鍵字應當是“程式員”並且“程式員”的得分應當最高。
首先對這句話分詞，這裡可以藉助各種分詞項目，比如Ansj分詞，得出分詞結果：
[程式員/n, (, 英文/nz, programmer/en, ), 是/v, 從事/v, 程式/n, 開發/v, 、/w, 維護/v, 的/uj, 專業/n, 人員/n, 。/w, 一般/a, 將/d, 程式員/n, 分為/v, 程式/n, 設計/vn, 人員/n, 和/c, 程式/n, 編碼/n, 人員/n, ，/w, 但/c, 兩者/r, 的/uj, 界限/n, 並/c, 不/d, 非常/d, 清楚/a, ，/w, 特別/d, 是/v, 在/p, 中國/ns, 。/w, 軟體/n, 從業/b, 人員/n, 分為/v, 初級/b, 程式員/n, 、/w, 高級/a, 程式員/n, 、/w, 系統/n, 分析員/n, 和/c, 項目/n, 經理/n, 四/m, 大/a, 類/q, 。/w]
然後去掉裡面的停用詞，這裡我去掉了標點符號、常用詞、以及“名詞、動詞、形容詞、副詞之外的詞”。得出實際有用的詞語：
[程式員, 英文, 程式, 開發, 維護, 專業, 人員, 程式員, 分為, 程式, 設計, 人員, 程式, 編碼, 人員, 界限, 特別, 中國, 軟體, 人員, 分為, 程式員, 高級, 程式員, 系統, 分析員, 項目, 經理]
獲取下載地址 java大數據 高併發 系統框架 springmvc mybatis Bootstrap html5 shiro maven SSM
之後建立兩個大小為5的視窗，每個單詞將票投給它身前身後距離5以內的單詞：
{開發=[專業, 程式員, 維護, 英文, 程式, 人員],
軟體=[程式員, 分為, 界限, 高級, 中國, 特別, 人員],
程式員=[開發, 軟體, 分析員, 維護, 系統, 項目, 經理, 分為, 英文, 程式, 專業, 設計, 高級, 人員, 中國],
分析員=[程式員, 系統, 項目, 經理, 高級],
維護=[專業, 開發, 程式員, 分為, 英文, 程式, 人員],
系統=[程式員, 分析員, 項目, 經理, 分為, 高級],
項目=[程式員, 分析員, 系統, 經理, 高級],
經理=[程式員, 分析員, 系統, 項目],
分為=[專業, 軟體, 設計, 程式員, 維護, 系統, 高級, 程式, 中國, 特別, 人員],
英文=[專業, 開發, 程式員, 維護, 程式],
程式=[專業, 開發, 設計, 程式員, 編碼, 維護, 界限, 分為, 英文, 特別, 人員],
特別=[軟體, 編碼, 分為, 界限, 程式, 中國, 人員],
專業=[開發, 程式員, 維護, 分為, 英文, 程式, 人員],
設計=[程式員, 編碼, 分為, 程式, 人員],
編碼=[設計, 界限, 程式, 中國, 特別, 人員],
界限=[軟體, 編碼, 程式, 中國, 特別, 人員],
高級=[程式員, 軟體, 分析員, 系統, 項目, 分為, 人員],
中國=[程式員, 軟體, 編碼, 分為, 界限, 特別, 人員],
人員=[開發, 程式員, 軟體, 維護, 分為, 程式, 特別, 專業, 設計, 編碼, 界限, 高級, 中國]}
然後開始迭代投票：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
for (int i = 0; i < max_iter; ++i)
{
Map<String, Float> m = new HashMap<String, Float>();
float max_diff = 0;
for (Map.Entry<String, Set<String>> entry : words.entrySet())
{
String key = entry.getKey();
Set<String> value = entry.getValue();
m.put(key, 1 - d);
for (String other : value)
{
int size = words.get(other).size();
if (key.equals(other) || size == 0) continue;
m.put(key, m.get(key) + d / size * (score.get(other) == null ? 0 : score.get(other)));
}
max_diff = Math.max(max_diff, Math.abs(m.get(key) - (score.get(key) == null ? 0 : score.get(key))));
}
score = m;
if (max_diff <= min_diff) break;
}
|
排序後的投票結果：
[程式員=1.9249977,
人員=1.6290349,
分為=1.4027836,
程式=1.4025855,
高級=0.9747374,
軟體=0.93525416,
中國=0.93414587,
特別=0.93352026,
維護=0.9321688,
專業=0.9321688,
系統=0.885048,
編碼=0.82671607,
界限=0.82206935,
開發=0.82074183,
分析員=0.77101076,
項目=0.77101076,
英文=0.7098714,
設計=0.6992446,
經理=0.64640945]
程式員果然榮登榜首，並且分數也有區分度，嗯，勉勉強強。
