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

趙 峰

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

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

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

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

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

2 共現(xiàn)分析

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

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

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

3 SWN理論

3.1 平均最短路徑長(zhǎng)度

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

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

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

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

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

其中L（G）表示圖G的平均最短路徑長(zhǎng)度。

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

3.2 簇系數(shù)

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

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

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

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

3.3 SWN理論

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

4 本文抽取算法步驟

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

5 結(jié)論

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

[1]楊暉.基于標(biāo)簽分類(lèi)內(nèi)容共享平臺(tái)的網(wǎng)頁(yè)自動(dò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)域的理解型中文自動(dòng)文摘系統(tǒng)[J].計(jì)算機(jī)研究與發(fā)展，2000(2)：23-28.

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

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

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