基于通配符模式與隨機游走的關鍵詞提取方法

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

(1.西北師范大學 計算機科學與工程學院,蘭州 730070; 2.桂林電子科技大學 廣西可信軟件重點實驗室,廣西 桂林 541004)

0 概述

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

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

1 通配符模式

序列S是有序的項目列表,用S=s1s2…sn表示,Σ是序列S中所有可能項的集合,通配符是一種能夠將Σ中的任意項進行匹配的符號,g[N,M]表示具有最小間隙N和最大間隙M的間隙。模式P=p1g[N,M]p2g[N,M]…g[N,M]pd是項目和間隙的序列,其中,模式長度用|P|表示,為P中的項目數。

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

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

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

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

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

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

圖1 水平實例圖

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

2 關鍵詞提取方法

2.1 關聯圖生成

模式P=p1p2…pd表示d個詞滿足間隙約束的關系,d取正整數。在構建關聯圖時,以詞語之間存在的語義關系來確定節點之間的關系,因為只需要已知項目兩兩之間的關系,所以模式長度d取2。間隙約束為g[N,M],則P=p1g[N,M]p2。給定序列S,最小支持度閾值min_sup,計算出所有滿足間隙約束和一次性條件的序列模式集合,并且計算出每個模式的支持度Sup(P)。將模式P中的所有不重復的項作為圖的節點,當且僅當模式P的支持度Sup(P)大于等于最小支持度閾值min_sup時節點之間有邊,邊的權重為支持度的值,由于可能存在p1g[N,M]p2≠p2g[N,M]p1,因此節點之間的邊是有向邊。

已知序列S=bcabccabcacdbdda,間隙約束g[0,2],最小支持度閾值min_sup=2,所有可能項的集合Σ={a,b,c,d},計算Σ集合中任意兩項的模式支持度如表1所示。將模式中所有不重復的項作為圖的節點,圖的節點集合為{a,b,c,d},當支持度大于等于2時節點之間有邊,生成的節點關聯圖如圖2所示。

表1 模式支持度

圖2 節點關聯圖

2.2 引入先驗信息的隨機游走算法

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

(1)

在式(1)中,節點之間的跳轉概率是相同的,而理論上相似節點之間跳轉的可能性會更大。節點之間邊的權值越大,節點之間跳轉的概率越大。在構建關聯圖時,將節點之間的支持度作為邊的權重,因為支持度的取值為正整數,不利于隨機游走計算,所以將支持度進行歸一化處理,節點Ni跳轉到節點Nk的概率如式(2)所示:

(2)

sim(Ni,Nj)=

(3)

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

式(3)表示2個節點Ni和Nj之間的語義相似度,在隨機游走時需要節點Ni的先驗分數,所以分別計算節點Ni與其他節點的相似度。為了更形式化地度量一個節點的先驗分數,對節點Ni的先驗分數進行歸一化,如式(4)所示:

(4)

其中,ri表示節點Ni的先驗分數,r=(r1,r2,…,r|N|)即為關聯圖中所有節點的先驗概率分布。式(2)修正了節點之間的跳轉概率,式(4)引入了知識庫中的先驗信息。結合式(2)和式(4)修正PageRank公式,如式(5)所示:

(5)

根據式(5)在關聯圖上隨機游走,迭代計算每個節點的PR值,直至滿足式(6)[18-19],使節點分數達到收斂狀態,其中δ為隨機游走終止閾值,并且使用圖中的排名分數PR對關鍵詞進行排序,將排名TopK個詞作為關鍵詞。

(6)

3 實驗結果與分析

3.1 實驗數據與評價指標

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

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

(7)

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

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

(8)

3.2 關聯圖模型參數分析

本節對最大間隙M、最小支持度閾值min_sup和衰減系數α這3個參數進行分析。在分析min_sup時,最大間隙M取3,在中文數據上的準確率如圖3所示,在英文數據上的準確率如圖4所示。圖3結果表明,在min_sup取5時,Fβ具有最高的準確率,所以在中文數據上min_sup的最優取值為5。

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

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

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

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

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

在分析衰減系數α時,采用中文數據,當min_sup取5、最大間隙M取4時,得出的MAP如圖7所示。當α取0.55時,MAP達到峰值。

圖7 衰減系數α對MAP的影響

3.3 關鍵詞提取性能對比及分析

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

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

表3 3種關鍵詞提取方式的結果對比(英文)

表4 3種關鍵詞提取方式的性能對比結果

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

圖8 3種方式的運行時間比較

4 結束語

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