基于通配符模式與隨機(jī)游走的關(guān)鍵詞提取方法

馬慧芳,李 苗,童海斌,詹子俊

(1.西北師范大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,蘭州 730070; 2.桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004)

0 概述

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展與上網(wǎng)用戶的增加,網(wǎng)頁新聞與各類電子文檔逐漸融入人們的生活中,文本關(guān)鍵詞提取技術(shù)可以幫助用戶從海量文檔中獲取有價(jià)值的信息,快速理解文檔的核心內(nèi)容。關(guān)鍵詞提取在文本挖掘中主要是根據(jù)詞項(xiàng)對文本內(nèi)容的相關(guān)程度進(jìn)行排序,因此單篇文檔的關(guān)鍵詞提取算法應(yīng)運(yùn)而生,并且廣泛應(yīng)用于推薦系統(tǒng)[1-2]、網(wǎng)絡(luò)廣告[3-5]及語義導(dǎo)航[6]等技術(shù)中。

關(guān)鍵詞提取方法主要分為基于特征的關(guān)鍵詞提取方法[7-9]、基于圖的關(guān)鍵詞提取方法[10-11]和基于語義的關(guān)鍵詞提取方法[12-13]。基于特征的關(guān)鍵詞提取方法使用句子位置、長度、簽名詞等度量為每個(gè)句子分配一個(gè)分?jǐn)?shù),如文獻(xiàn)[8]研究頻率對關(guān)鍵詞提取的影響。基于圖的關(guān)鍵詞提取方法將文檔表示為密集連接的圖,其中每個(gè)節(jié)點(diǎn)表示一個(gè)句子,邊連接兩個(gè)句子,邊的權(quán)重值表示兩個(gè)句點(diǎn)之間的相似性,然后使用PageRank[14]等圖算法對句子進(jìn)行重要性評(píng)分。基于語義的關(guān)鍵詞提取方法通過考慮文檔內(nèi)容的潛在語義,生成準(zhǔn)確的關(guān)鍵詞,如文獻(xiàn)[12]利用詞匯鏈表示文本的詞匯連貫結(jié)構(gòu),將提取出包含高出現(xiàn)頻次的鏈詞的句子作為文檔關(guān)鍵詞。本文提出一種基于通配符模式和隨機(jī)游走算法的關(guān)鍵詞提取方法,利用深度優(yōu)先模式搜索策略發(fā)現(xiàn)具有通配符模式的所有實(shí)例,通過數(shù)據(jù)結(jié)構(gòu)層次實(shí)例圖將模式支持度計(jì)算嵌入深度優(yōu)先模式搜索過程中。

1 通配符模式

序列S是有序的項(xiàng)目列表,用S=s1s2…sn表示,Σ是序列S中所有可能項(xiàng)的集合,通配符是一種能夠?qū)ⅵ仓械娜我忭?xiàng)進(jìn)行匹配的符號(hào),g[N,M]表示具有最小間隙N和最大間隙M的間隙。模式P=p1g[N,M]p2g[N,M]…g[N,M]pd是項(xiàng)目和間隙的序列,其中,模式長度用|P|表示,為P中的項(xiàng)目數(shù)。

定義1(模式出現(xiàn)和實(shí)例)給定模式P=p1p2…pd,序列S=s1s2…sn和間隙約束g=[N,M],如果存在位置序列1≤l1

定義2(一次性條件) 假設(shè)occ=(l1,l2,…,ld)和occ′=(l′1,l′2,…,l′d)是序列S中模式P的2個(gè)實(shí)例。如果對于所有1≤p≤d,1≤q≤d,有l(wèi)p≠l′q,則這兩個(gè)實(shí)例滿足一次性條件。

定義3(支持度和支持集) 序列S中模式P的支持度被定義為所有可能的實(shí)例集的最大值,其中任何兩個(gè)實(shí)例都滿足一次性條件。用Sup(P)表示P的支持度,具有Sup(P)大小的實(shí)例集被稱為P的支持集。

定義4(非重復(fù)模式) 給定模式P=p1p2…pd,如果?1≤i,j≤d,pi≠pj,則將P稱為非重復(fù)模式。

定義5(子模式與超模式) 對于兩種模式P=p1p2…pm和P′=p′1p′2…p′n(n≥m),如果存在位置序列1≤i1

在挖掘序列模式時(shí),本文引入SPMW算法[15-16]。給定序列S=s1s2…sn,模式P=p1p2…pm,間隙約束g[N,M],模式P的水平實(shí)例圖表示為二元組,其中,V是節(jié)點(diǎn)集,E是邊集。將節(jié)點(diǎn)集劃分為m層,第i(1≤i≤m)層節(jié)點(diǎn)對應(yīng)于pi的位置。假設(shè)A和B是pi和pi+1的兩個(gè)節(jié)點(diǎn),如果A和B的位置在同一個(gè)序列上,且滿足間隙約束,則有一個(gè)從A到B的父子邊和一個(gè)從B到A的子父邊。圖1是一個(gè)水平實(shí)例圖,其中,實(shí)線表示父子邊緣,虛線表示子父邊緣,并且使用虛線連接相同的級(jí)別節(jié)點(diǎn)。

圖1 水平實(shí)例圖

在圖1中,已知序列S=bcabccabcacdbdda和間隙約束g[0,5]。模式“b”在序列S中出現(xiàn)4次,分別在節(jié)點(diǎn)1、4、8和13處。第二層節(jié)點(diǎn)是項(xiàng)目a的4個(gè)位置,在滿足間隙約束g[0,5]時(shí),連接第一層節(jié)點(diǎn)。由前2個(gè)層級(jí)節(jié)點(diǎn)組成的圖是模式Q=ba的實(shí)例圖。類似地,模式R=baa的實(shí)例圖由3個(gè)層級(jí)節(jié)點(diǎn)組成。實(shí)例圖第二層中的節(jié)點(diǎn)16沒有子節(jié)點(diǎn)。當(dāng)計(jì)算模式R的支持度時(shí),通過對節(jié)點(diǎn)7、10和16的深度優(yōu)先遍歷策略掃描實(shí)例圖,其中<1,3,7>和<4,10,16>的出現(xiàn)次數(shù)為2。

2 關(guān)鍵詞提取方法

2.1 關(guān)聯(lián)圖生成

模式P=p1p2…pd表示d個(gè)詞滿足間隙約束的關(guān)系,d取正整數(shù)。在構(gòu)建關(guān)聯(lián)圖時(shí),以詞語之間存在的語義關(guān)系來確定節(jié)點(diǎn)之間的關(guān)系,因?yàn)橹恍枰阎?xiàng)目兩兩之間的關(guān)系,所以模式長度d取2。間隙約束為g[N,M],則P=p1g[N,M]p2。給定序列S,最小支持度閾值min_sup,計(jì)算出所有滿足間隙約束和一次性條件的序列模式集合,并且計(jì)算出每個(gè)模式的支持度Sup(P)。將模式P中的所有不重復(fù)的項(xiàng)作為圖的節(jié)點(diǎn),當(dāng)且僅當(dāng)模式P的支持度Sup(P)大于等于最小支持度閾值min_sup時(shí)節(jié)點(diǎn)之間有邊,邊的權(quán)重為支持度的值,由于可能存在p1g[N,M]p2≠p2g[N,M]p1,因此節(jié)點(diǎn)之間的邊是有向邊。

已知序列S=bcabccabcacdbdda,間隙約束g[0,2],最小支持度閾值min_sup=2,所有可能項(xiàng)的集合Σ={a,b,c,d},計(jì)算Σ集合中任意兩項(xiàng)的模式支持度如表1所示。將模式中所有不重復(fù)的項(xiàng)作為圖的節(jié)點(diǎn),圖的節(jié)點(diǎn)集合為{a,b,c,d},當(dāng)支持度大于等于2時(shí)節(jié)點(diǎn)之間有邊,生成的節(jié)點(diǎn)關(guān)聯(lián)圖如圖2所示。

表1 模式支持度

圖2 節(jié)點(diǎn)關(guān)聯(lián)圖

2.2 引入先驗(yàn)信息的隨機(jī)游走算法

PageRank是一種計(jì)算網(wǎng)頁重要程度的算法,該算法認(rèn)為如果一個(gè)網(wǎng)頁被很多其他網(wǎng)頁鏈連到,則說明該網(wǎng)頁比較重要。模型定義如式(1)所示:

(1)

在式(1)中,節(jié)點(diǎn)之間的跳轉(zhuǎn)概率是相同的,而理論上相似節(jié)點(diǎn)之間跳轉(zhuǎn)的可能性會(huì)更大。節(jié)點(diǎn)之間邊的權(quán)值越大,節(jié)點(diǎn)之間跳轉(zhuǎn)的概率越大。在構(gòu)建關(guān)聯(lián)圖時(shí),將節(jié)點(diǎn)之間的支持度作為邊的權(quán)重,因?yàn)橹С侄鹊娜≈禐檎麛?shù),不利于隨機(jī)游走計(jì)算,所以將支持度進(jìn)行歸一化處理,節(jié)點(diǎn)Ni跳轉(zhuǎn)到節(jié)點(diǎn)Nk的概率如式(2)所示:

(2)

sim(Ni,Nj)=

(3)

其中,Ei是連接到Ni的文檔集,|W|是文件總數(shù)。

式(3)表示2個(gè)節(jié)點(diǎn)Ni和Nj之間的語義相似度,在隨機(jī)游走時(shí)需要節(jié)點(diǎn)Ni的先驗(yàn)分?jǐn)?shù),所以分別計(jì)算節(jié)點(diǎn)Ni與其他節(jié)點(diǎn)的相似度。為了更形式化地度量一個(gè)節(jié)點(diǎn)的先驗(yàn)分?jǐn)?shù),對節(jié)點(diǎn)Ni的先驗(yàn)分?jǐn)?shù)進(jìn)行歸一化,如式(4)所示:

(4)

其中,ri表示節(jié)點(diǎn)Ni的先驗(yàn)分?jǐn)?shù),r=(r1,r2,…,r|N|)即為關(guān)聯(lián)圖中所有節(jié)點(diǎn)的先驗(yàn)概率分布。式(2)修正了節(jié)點(diǎn)之間的跳轉(zhuǎn)概率,式(4)引入了知識(shí)庫中的先驗(yàn)信息。結(jié)合式(2)和式(4)修正PageRank公式,如式(5)所示:

(5)

根據(jù)式(5)在關(guān)聯(lián)圖上隨機(jī)游走,迭代計(jì)算每個(gè)節(jié)點(diǎn)的PR值,直至滿足式(6)[18-19],使節(jié)點(diǎn)分?jǐn)?shù)達(dá)到收斂狀態(tài),其中δ為隨機(jī)游走終止閾值,并且使用圖中的排名分?jǐn)?shù)PR對關(guān)鍵詞進(jìn)行排序,將排名TopK個(gè)詞作為關(guān)鍵詞。

(6)

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與評(píng)價(jià)指標(biāo)

為驗(yàn)證本文方法的有效性,本文選取《物種起源》作為中文實(shí)驗(yàn)數(shù)據(jù)。經(jīng)過預(yù)處理操作后有71 923個(gè)詞項(xiàng)。選取MEHRI與DAROONEH合著的“The role of entropy in word ranking”文獻(xiàn)(MD’paper)作為英文實(shí)驗(yàn)數(shù)據(jù)。經(jīng)過預(yù)處理操作后有1 180個(gè)詞項(xiàng)。選取維基百科知識(shí)庫作為先驗(yàn)信息,使用工具包Wikipedia-Miner獲得詞語相似度。根據(jù)《物種起源》重要詞匯注解表,選取15個(gè)重要詞項(xiàng)作為評(píng)價(jià)關(guān)鍵詞提取是否有效的基準(zhǔn),提取MD’paper中的9個(gè)重要詞項(xiàng)作為評(píng)價(jià)英文關(guān)鍵詞提取是否有效的基準(zhǔn)。

綜合平均精度均值(Mean Average Precision,MAP)、召回率(R)和Fβ作為關(guān)鍵短語提取的性能指標(biāo)。設(shè)Mret表示本文關(guān)鍵詞提取結(jié)果序列,Mrel表示真實(shí)詞匯表序列,MAP定義如式(7)所示:

(7)

其中,Mret(j)表示關(guān)鍵詞返回序列Mret的第j個(gè)詞項(xiàng),g(t,Mrel)表示指示函數(shù),若詞項(xiàng)t出現(xiàn)在原詞匯表序列Mrel中則返回1,否則返回0,P(i)與AP(i)分別表示Mret中前i個(gè)詞項(xiàng)的準(zhǔn)確率與平均準(zhǔn)確率。

Fβ準(zhǔn)確率是由MAP和R相結(jié)合計(jì)算得到,其中β取值為0.5。Fβ定義如式(8)所示:

(8)

3.2 關(guān)聯(lián)圖模型參數(shù)分析

本節(jié)對最大間隙M、最小支持度閾值min_sup和衰減系數(shù)α這3個(gè)參數(shù)進(jìn)行分析。在分析min_sup時(shí),最大間隙M取3,在中文數(shù)據(jù)上的準(zhǔn)確率如圖3所示,在英文數(shù)據(jù)上的準(zhǔn)確率如圖4所示。圖3結(jié)果表明,在min_sup取5時(shí),Fβ具有最高的準(zhǔn)確率,所以在中文數(shù)據(jù)上min_sup的最優(yōu)取值為5。

圖3 最小支持度閾值對準(zhǔn)確率的影響(中文)

圖4 最小支持度閾值對準(zhǔn)確率的影響(英文)

在分析最大間隙M時(shí),min_sup取5,在中文數(shù)據(jù)上的準(zhǔn)確率如圖5所示,在英文數(shù)據(jù)上的準(zhǔn)確率如圖6所示。圖5結(jié)果表明MAP和Fβ都在M取4時(shí)達(dá)到峰值。圖6結(jié)果表明,當(dāng)M取3時(shí),MAP具有最高的平均精度均值。造成中英文數(shù)據(jù)上M的最優(yōu)取值不同的原因是中文數(shù)據(jù)《物種起源》是一個(gè)較長的文本,而MD’paper英文數(shù)據(jù)相比于中文數(shù)據(jù)來說較短。

圖5 最大間隙對準(zhǔn)確率的影響(中文)

圖6 最大間隙對準(zhǔn)確率的影響(英文)

在分析衰減系數(shù)α?xí)r,采用中文數(shù)據(jù),當(dāng)min_sup取5、最大間隙M取4時(shí),得出的MAP如圖7所示。當(dāng)α取0.55時(shí),MAP達(dá)到峰值。

圖7 衰減系數(shù)α對MAP的影響

3.3 關(guān)鍵詞提取性能對比及分析

為驗(yàn)證本文關(guān)鍵詞提取算法的準(zhǔn)確性與優(yōu)越性,選取TextRank、GraphSum算法與本文算法進(jìn)行比較分析。實(shí)驗(yàn)結(jié)果如表2、表3所示,其中陰影部分表示該算法提取出的關(guān)鍵詞在關(guān)鍵詞參考集中不存在。可見,在中文數(shù)據(jù)及英文數(shù)據(jù)上,GraphSum算法得到的關(guān)鍵詞與TextRank算法得到的關(guān)鍵詞相比更為準(zhǔn)確。然而,與本文方法相比,使用GraphSum、TextRank算法得到的結(jié)果均有所欠缺。3種方式在中文數(shù)據(jù)和英文數(shù)據(jù)進(jìn)行關(guān)鍵詞提取時(shí)得到的MAP、R和Fβ如表4所示。本文方法在中文數(shù)據(jù)和英文數(shù)據(jù)上進(jìn)行關(guān)鍵詞提取得到的MAP均大于其他兩種算法。

表2 3種關(guān)鍵詞提取方式的結(jié)果對比(中文)

表3 3種關(guān)鍵詞提取方式的結(jié)果對比(英文)

表4 3種關(guān)鍵詞提取方式的性能對比結(jié)果

為驗(yàn)證本文方法運(yùn)行效率,在Celeron 1.40 GHz處理器的Windows 10操作系統(tǒng)下,給出本文方法在不同詞量規(guī)模下的運(yùn)行時(shí)間,如圖8所示。由于本文考慮了語義信息和先驗(yàn)信息,因此本文方法的執(zhí)行效率會(huì)比其他算法更低。但隨著詞量規(guī)模的擴(kuò)大,本文方法的運(yùn)行時(shí)間接近于線性增長。

圖8 3種方式的運(yùn)行時(shí)間比較

4 結(jié)束語

本文提出一種基于通配符模式和隨機(jī)游走算法的關(guān)鍵詞提取方法。該方法基于通配符約束和一次性條件來挖掘序列模式,使用深度優(yōu)先搜索策略計(jì)算模式支持度,挖掘出具有間隙約束的所有模式實(shí)例,并在模式支持度大于等于最小支持度閾值時(shí)構(gòu)建關(guān)聯(lián)圖,同時(shí)通過引入先驗(yàn)信息的PageRank算法獲取排名前TopK個(gè)詞語作為關(guān)鍵詞。實(shí)驗(yàn)結(jié)果表明,本文方法相比傳統(tǒng)關(guān)鍵詞提取算法具有更高的準(zhǔn)確率和穩(wěn)定性。后續(xù)可將句子位置、簽名詞、圖結(jié)構(gòu)等信息引入到隨機(jī)游走算法中,進(jìn)一步降低關(guān)鍵詞提取算法復(fù)雜度并提高執(zhí)行效率。