基于SWN理論的關(guān)鍵字抽取策略

趙 峰

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

1 文本預(yù)處理和分詞

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

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

根據(jù)每次匹配時優(yōu)先考慮長詞還是優(yōu)先考慮短詞，將基于字符串匹配的分詞法又分為最大匹配法和最小匹配法。由于大多數(shù)漢字均可構(gòu)成單字詞，所以按最小匹配法分詞的結(jié)果往往因分得太細(xì)而不合要求。反之，當(dāng)待分詞文本中出現(xiàn)“詞中含詞”的情況時，最大匹配法就可能因分得太粗而不合要求。本設(shè)計采用最大匹配算法進行分詞。

2 共現(xiàn)分析

共現(xiàn)分析[5]是詞語網(wǎng)絡(luò)構(gòu)建和分析的基礎(chǔ)理論和方法論。

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

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

3 SWN理論

3.1 平均最短路徑長度

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

我們用G表示一個網(wǎng)絡(luò)所對應(yīng)的拓?fù)浣Y(jié)構(gòu)圖，N和K分別表示圖中的結(jié)點總數(shù)和邊的總數(shù)，k為從每個結(jié)點引出的平均邊數(shù)。Ki是從第i個結(jié)點引出的邊的個數(shù)（第i個結(jié)點的度）。則：

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

下面給出圖的平均最短路徑變化量的數(shù)學(xué)定義：

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

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

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

3.2 簇系數(shù)

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

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

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

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

3.3 SWN理論

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

4 本文抽取算法步驟

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

5 結(jié)論

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

[1]楊暉.基于標(biāo)簽分類內(nèi)容共享平臺的網(wǎng)頁自動文摘模型[M].北京：清華大學(xué)出版社，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]李蕾，鐘義信，郭祥昊.面向領(lǐng)域的理解型中文自動文摘系統(tǒng)[J].計算機研究與發(fā)展，2000(2)：23-28.

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

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

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