一種基于信息熵的關(guān)鍵詞提取算法?

吳 華 羅 順 孫偉晉

（上海通用識別技術(shù)研究所 上海 201112）

1 引言

隨著互聯(lián)網(wǎng)信息的爆炸式增長，如何提高信息的訪問效率、降低信息的閱讀成本，已成為信息處理的關(guān)鍵技術(shù)之一。而關(guān)鍵詞提取就是其中一種有效的應(yīng)對手段，關(guān)鍵詞作為信息的主要承載單元，其提取效果和性能直接決定了信息檢索、自然語言處理、本體構(gòu)建等技術(shù)和應(yīng)用的效果［1］。

當(dāng)前廣泛使用的關(guān)鍵詞提取算法大多是基于字典、語言規(guī)則、統(tǒng)計的經(jīng)典算法［2～4］。這些經(jīng)典算法在進行關(guān)鍵詞提取之前大多需要先進行分詞［5］，這就意味無法對缺乏語法等背景知識的小語種語料進行分析處理，此外，經(jīng)典算法對于特定領(lǐng)域的新概念、新術(shù)語、新話題的處理能力也較差。

本文在基于信息熵的方法，以詞匯內(nèi)部各字符的互信息作為詞匯內(nèi)部關(guān)聯(lián)性特征，以詞匯鄰接字符的分布作為詞匯外部獨立性特征，以及詞匯的頻次、長度等統(tǒng)計特征，構(gòu)建了一種無監(jiān)督的關(guān)鍵詞提取算法。該算法克服了經(jīng)典算法對字典、分詞等先驗知識的依賴，同時，能較好地識別出未登錄詞和支持多語種混合的語料環(huán)境。

2 信息熵

根據(jù)Shannon的信息理論，熵（entropy）用來度量隨機變量的不確定性［6］。一個離散隨機變量X，其值域記為Sx，對Sx中狀態(tài)值x∈Sx，其概率分布函數(shù)為則變量X的熵為

若一個離散隨機變量Y，其值域記為Sy，對Sy中狀態(tài)值 y∈Sy，其概率分布函數(shù)為與隨機變量X的聯(lián)合概率分布函數(shù)為則變量X、Y的聯(lián)合熵為

當(dāng)變量Y已知，則變量X的條件熵，即變量X中剩余的不確定性為

變量X和變量Y的互信息，即兩者的統(tǒng)計依存關(guān)系為［7～8］

考慮到

即變量X和變量Y的互信息可由熵計算得到

3 基于信息熵的關(guān)鍵詞提取

3.1 詞邊界識別

設(shè)樣本字符串S=t1t2…tn，則稱t1為t2的左鄰接字符，t2為t1的右鄰接字符。根據(jù)信息熵的方法，如果一個字符串是一個詞匯，那么其左右鄰接字符應(yīng)具有較大的不確定性，即該字符串獨立于左右鄰接字符，而鄰接字符的分布是較為分散的。

舉例來說，“吃肯德基套餐”、“去肯德基門店”、“搶肯德基優(yōu)惠券”、“上肯德基官網(wǎng)”等字符串中，子字符串“德基”的左鄰接字符只有唯一確定的一個“肯”，而“肯德基”的左鄰接字符卻有“吃”、“去”、“搶”、“上”四種，不確定性較大，同樣的，子字符串“肯德”的右鄰接字符只有唯一確定的一個“基”，而“肯德基”的右鄰接字符卻有“套”、“門”、“優(yōu)”、“官”四種，不確定性較大。

記字符串S左鄰接字符分布集為αl，右鄰接字符分布集為αr，計算字符串S左右鄰接熵模型如下：

其中 f（ ）αiS 表示字符串在樣本中出現(xiàn)的次數(shù)。

對于給定閾值h，若 Hl（）S＜h即認(rèn)為字符t1為字符串S的左邊界，若 Hr（）S＜h即認(rèn)為字符tn為字符串S的右邊界。

3.2 詞匯完整性識別

在3.1節(jié)中，我們獲得了字符串S的左右邊界，在此基礎(chǔ)上，根據(jù)信息熵的方法，如果一個字符串是一個完整詞匯，那么其內(nèi)部各字符間的相互關(guān)聯(lián)應(yīng)較為緊密，即該字符串內(nèi)部各子字符串具有較高的互信息值。

舉例來說，“中國工商銀行”這一字符串在詞邊界識別的過程中，可能被識別成“中國”、“工商”、“銀行”三個詞匯，而事實上，當(dāng)“中國”、“工商”、“銀行”三個詞匯連續(xù)出現(xiàn)時，我們更傾向?qū)⑵渥鳛橐粋€完整詞匯。

互信息有多種計算表達式，同樣通過樣本統(tǒng)計數(shù)據(jù)給出互信息計算表達式：

3.3 關(guān)鍵詞提取

根據(jù)3.1節(jié)和3.2節(jié)、對于給定鄰接熵閾值h、互信息閾值 m，若且 Hr（）S ＜h，且MI（）S＞m，則將字符串S=t1t2…tn作為獨立詞匯召回。

選取詞頻、詞長、詞位置、詞跨度四種統(tǒng)計特征［5］，并通過權(quán)重配置實現(xiàn)歸一化。

詞頻因子計算模型如下：

詞長因子計算模型如下：

詞位置因子計算模型如下：

其中 p=（ ）p0，p1，p2，p3表示字符串S在語料中標(biāo)題、首段、段首句、其他位置出現(xiàn)的頻率，a=（ ）a0，a1，a2，a3表示在每一個位置上的權(quán)重。該詞位置因子計算模型認(rèn)為，詞匯在不同的位置上對反映語料主題的重要性是不一致的，權(quán)重以標(biāo)題、首段、段首句、其他位置依次遞減，即a0≥a1≥a2≥a3。同樣的，add（）S也向1收斂。

詞跨度因子計算模型如下：

為詞頻、詞長、詞位置、詞跨度四種統(tǒng)計特征配置權(quán)重w=（ ）w0，w1，w2，w3如下：

我們即得到字符串S作為語料主題的影響因子。

4 算法描述

step1：從當(dāng)前位置pos=0開始讀入預(yù)定長度的字符串（如2漢字長度）；

step2：計算當(dāng)前字符串的左右鄰接熵；

step3：若左或右鄰接熵小于指定閾值h，則字符串向左或右擴展一個字符長度（遇到標(biāo)點或文章邊界則停止），回到step2；

step4：若左和右鄰接熵均大于指定閾值h，則計算當(dāng)前字符串中個字符的互信息；

step5：若互信息大于指定閾值m，則將當(dāng)前字符串作為獨立完整詞匯召回；

step6：當(dāng)前位置pos右移一個字符長度，若語料剩余長度大于擬讀入字符串的預(yù)定長度，則回到step1；

step7：計算所有被召回的詞匯權(quán)重，并按權(quán)重排序，取出權(quán)重較大的詞匯作為當(dāng)前語料的關(guān)鍵詞。

5 算例

以《環(huán)球時報》2015年3月30日報道的《“一帶一路”點燃世界熱情》為例。

配置鄰接熵閾值h=1、互信息閾值m=0.05，配置詞位置權(quán)重 a=（0.4，0.3，0.2，0.1）、配置詞頻、詞長、詞位置、詞跨度權(quán)重 w=（0.4，0.2，0.2，0.2），利用第4節(jié)中算法，最終提取出的前十個關(guān)鍵詞為“一帶一路”、“絲綢之路”、“海上絲綢之路”、“中國”、“沿線國家”、“亞投行”、“經(jīng)濟”、“習(xí)近平”、“路線圖”、“俄羅斯”。

實驗結(jié)果表明，算法能識別“一帶一路”、“亞投行”等新詞和術(shù)語，能識別“海上絲綢之路”、“沿線國家”等復(fù)合詞，能將“絲綢之路”、“海上絲綢之路”等具有重復(fù)字符的詞匯作為兩個獨立詞匯召回，關(guān)鍵詞提取效果令人滿意。

6 結(jié)語

本文提出的基于信息熵的關(guān)鍵詞提取算法，是一種無監(jiān)督的提取算法。由于該方法的處理對象為二進制字符，從而具有以下三方面特點，一是不需要字典等先驗知識；二是不需要分詞運算而直接進行關(guān)鍵詞提??；三是能處理多語種混合的語料。