基于SWN理論的關鍵字抽取策略

趙 峰

同濟大學電子與信息工程學院，上海 201804

1 文本預處理和分詞

文本預處理[1]是進行關鍵字抽取的第一個步驟。文本預處理操作，一般包括去除文檔中的格式標記、過濾非法字符、字母大小寫轉換、去除停用詞和稀有詞、詞干化處理和中文分詞處理等處理步驟。

基于字符串匹配的分詞方法通常又稱為機械分詞法或詞典法，這種方法是基于一個相對完備的詞典，對待分詞文本按照特定的規則逐個進行字符串匹配，如果匹配則認為是一個詞，一般在機械分詞法中用少量詞法、語法和語義信息等對分詞系統輔助，使其達到最佳效果，由于其實現簡單，目前幾乎所有的分詞方法都屬于這一種。

根據每次匹配時優先考慮長詞還是優先考慮短詞，將基于字符串匹配的分詞法又分為最大匹配法和最小匹配法。由于大多數漢字均可構成單字詞，所以按最小匹配法分詞的結果往往因分得太細而不合要求。反之，當待分詞文本中出現“詞中含詞”的情況時，最大匹配法就可能因分得太粗而不合要求。本設計采用最大匹配算法進行分詞。

2 共現分析

共現分析[5]是詞語網絡構建和分析的基礎理論和方法論。

由于文本的半結構化特性，現有的成熟的數據挖掘技術無法發現文本中蘊含的大量信息；針對文本數據庫內容的特殊性，提出許多文本挖掘方法。在眾多文本挖掘方法中，共現分析以科學的分析原理、簡便的操作流程和客觀的分析結果，逐漸受到文本知識挖掘人員的青睞。該方法以文本的最小內容單位－詞匯為分析對象，挖掘詞匯語義，以此為基礎實現文本內容的有效表示；并能對大規模文本集合進行文本精練和知識提取，可完成文本總結、文本分類、文本聚類、關聯分析、分布分析及趨勢預測等多種文本挖掘任務。

共現窗口是共現分析中一種非常重要的研究，即在同一共現窗口中出現的詞是有關聯的，具體到商品信息中，共現窗口可以選擇一個自然段，也可以選擇一個句子，即在一句話中出現的分詞是有關聯的。

3 SWN理論

3.1 平均最短路徑長度

在網絡中，兩點間的距離被定義為連接兩點的最短路所包含的邊的數目，把所有結點對的距離求平均，就得到了網絡的平均距離（average distance，也叫平均最短路徑變化量）L。L表示網絡的有效大小，代表兩個結點間的最典型的分離距離。

我們用G表示一個網絡所對應的拓撲結構圖，N和K分別表示圖中的結點總數和邊的總數，k為從每個結點引出的平均邊數。Ki是從第i個結點引出的邊的個數（第i個結點的度）。則：

為了說明圖的特性，又設dij 表示點vi和vj之間的平均最短路徑，用|E（G＇）|表示任意一個圖的G＇中邊的個數。

下面給出圖的平均最短路徑變化量的數學定義：

我們把圖G中所有點之間的距離的平均值叫圖G的平均最短路徑長度，可表示為：

其中L（G）表示圖G的平均最短路徑長度。

設L為圖G的平均路徑長度，即所有邊的權值之和和與頂點個數的比，L（i）為圖Gi的平均路徑長度，則在圖G中去掉頂點i后形成的圖Gi的平均路徑變化量ΔLi為

3.2 簇系數

另外一個叫做簇系數（clustering coefficient）的參數，專門用來衡量網絡節點聚類的情況。比如在朋友關系網中，你朋友的朋友很可能也是你的朋友；你的兩個朋友很可能彼此也是朋友。簇系數就是用來度量網絡的這種性質的。用數學化的語言來說，對于某個節點，它的簇系數被定義為它所有相鄰節點之間連邊的數目占可能的最大連邊數目的比例，網絡的簇系數C則是所有節點簇系數的平均值。

假設無向網絡中頂點i與其他頂點相連的邊數為ki條，這ki個頂點稱為頂點i的鄰居。顯然，這ki個頂點之間最多可能有ki（ki-l）/2條邊。而ki個頂點之間實際存在的邊數為Ei，將實際存在的邊數Ei與可能的邊數ki（ki-l）/2相比得到頂點i的聚類系數Ci，公式如下：

圖G的簇系數C是所有頂點簇系數Ci的平均值，用C（G）來表示：

設C為圖G的簇系數平均值，C（i）為圖Gi的簇系數平均值，則在圖G中去掉頂點i后所形成的圖Gi的簇系數變化量為ΔCi為

3.3 SWN理論

近年來復雜網絡研究的興起，學者們關注網絡結構復雜性以及網絡行為之間的關系。為研究不同復雜網絡的結構共性，需要一種描述網絡的統一工具，數學上稱為圖。任何一個網絡都可以看作是由一些頂點按某種方式連接在一起而構成的圖。復雜網絡所構成的圖普遍具有較大的簇系數和較小的平均最短路徑長度，此時高聚類性和小世界效應會在網絡中同時呈現，我們把這種網絡叫做小世界網絡（Small World Network），經過大量實驗證實：SWN能客觀準確的反映現實世界中的很多的復雜系統，在很多領域得到了廣泛的應用。因此我們也可以將該理論用在關鍵字的抽取策略之中。

4 本文抽取算法步驟

首先對一篇待抽取關鍵字文本進行文本預處理，得到一個分詞集合。然后由共現分析理論得到該文本的圖結構，該圖顯然具有SWN理論所需的基本要素，即為一個小世界網絡。在圖中依次刪除每一個結點，即每一個分詞，然后計算該圖的平均最短路徑長度和簇系數變化量，如果兩者變化值越大，則說明對該圖的影響越大，即對文本的影響程度越大，則應該成為文本的關鍵字，否則不列為關鍵字。抽取關鍵字的數目可以根據具體情況而定。

5 結論

現階段，文本挖掘領域并沒有一種固定的、非常有效的從文本中提取關鍵詞語的算法。其他的抽取算法也有很多，比如先計算文本各項的權重，以關鍵項及權重來表示文本特征，然后按照這些文本特征將多文本聚類，計算相似度，對每一聚類賦以關鍵字，以此來達到每篇文本的關鍵字抽取。隨著越來越多的研究人員進入該領域研究，相信關鍵字抽取領域一定會有更好的進展。

[1]楊暉.基于標簽分類內容共享平臺的網頁自動文摘模型[M].北京：清華大學出版社，2007：121-125.

[2]Van Charles.Information Retrieval.London：Butterworths，1979：54-59.

[3]H.P.Luhn.The automatic creation of literature abstracts.Sebastopol CA：IBM Journal of Research and Development，1958：34-38.

[4]李蕾，鐘義信，郭祥昊.面向領域的理解型中文自動文摘系統[J].計算機研究與發展，2000(2)：23-28.

[5]季姮，羅振聲，萬敏等.基于概念統計和語義層次分析的英文自動文摘研究[J].中文信息學報，2003(12)：36-42.

[6]姜賢塔，陳根才.利用語料庫技術的中文自動文摘系統[J].中文信息學報，1999(4)：13-18.

[7]萬敏，羅振聲，季姮，等.基于概念統計的英文自動文摘研究[J].計算機工程與應用，2002(12)：14-19.