一種基于信息熵的關鍵詞提取算法?

吳 華 羅 順 孫偉晉

（上海通用識別技術研究所 上海 201112）

1 引言

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

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

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

2 信息熵

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

若一個離散隨機變量Y，其值域記為Sy，對Sy中狀態值 y∈Sy，其概率分布函數為與隨機變量X的聯合概率分布函數為則變量X、Y的聯合熵為

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

變量X和變量Y的互信息，即兩者的統計依存關系為［7～8］

考慮到

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

3 基于信息熵的關鍵詞提取

3.1 詞邊界識別

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

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

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

其中 f（ ）αiS 表示字符串在樣本中出現的次數。

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

3.2 詞匯完整性識別

在3.1節中，我們獲得了字符串S的左右邊界，在此基礎上，根據信息熵的方法，如果一個字符串是一個完整詞匯，那么其內部各字符間的相互關聯應較為緊密，即該字符串內部各子字符串具有較高的互信息值。

舉例來說，“中國工商銀行”這一字符串在詞邊界識別的過程中，可能被識別成“中國”、“工商”、“銀行”三個詞匯，而事實上，當“中國”、“工商”、“銀行”三個詞匯連續出現時，我們更傾向將其作為一個完整詞匯。

互信息有多種計算表達式，同樣通過樣本統計數據給出互信息計算表達式：

3.3 關鍵詞提取

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

選取詞頻、詞長、詞位置、詞跨度四種統計特征［5］，并通過權重配置實現歸一化。

詞頻因子計算模型如下：

詞長因子計算模型如下：

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

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

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

為詞頻、詞長、詞位置、詞跨度四種統計特征配置權重w=（ ）w0，w1，w2，w3如下：

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

4 算法描述

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

step2：計算當前字符串的左右鄰接熵；

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

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

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

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

step7：計算所有被召回的詞匯權重，并按權重排序，取出權重較大的詞匯作為當前語料的關鍵詞。

5 算例

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

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

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

6 結語

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