基于布谷鳥搜索優化算法的多文檔摘要方法

周詩源,王英林

(上海財經大學 信息管理與工程學院,上海 200433)

0 概述

隨著移動互聯網的快速發展,網絡中的信息量呈指數級增長,大量資訊、知識、視頻、音樂等資源可供用戶選擇,信息過載問題日益突出,而文檔摘要是解決信息過載的有效方式。文檔摘要[1]是指在不丟失原文主要內容的前提下創建摘要的過程[2],其能夠提供相關信息的快速導向,幫助用戶確定文檔是否具備可讀性,因此成為近年來研究的熱點問題。

根據摘要生成過程中的文檔數量,可將摘要分為單文檔摘要[3]和多文檔摘要[4],由于多文檔摘要的搜索空間大于單文檔摘要,因此提取重要句子的難度更大。為生成包含原始文檔重要信息句的最優摘要,文獻[5]設計基于整數線性規劃的概括式多文檔自動摘要方法,優選出每個主題下的重要主題語義信息,生成新的摘要句,并對候選摘要句進行潤色加工,解決了生成概括式摘要的信息覆蓋和可讀性問題。文獻[6]提出一種基于K最近鄰句子-圖模型的動態文本摘要方法,根據K近鄰規則構建一個雙層句子圖模型,使用基于密度劃分的增量圖聚類方法對句子進行子主題劃分,并結合時間因素提高句子新穎度以抽取動態文摘。文獻[7]使用粒子群優化(Particle Swarm Optimization,PSO)算法設計單文檔摘要器,通過內容覆蓋度和冗余度特征的加權平均,獲得目標函數,進而設計文檔摘要器。文獻[8]提出一種句子話題重要性計算方法,通過分析句子與話題的語義關系,判斷句子是否描述了話題的重要信息,同時設計一種基于排序學習的半監督訓練框架。此外,現有研究采用PSO算法[9]、差分進化(Differential Evolution,DE)算法[10]、遺傳算法(Genetic Algorithm,GA)[11]、LDA主題模型[12]及子主題劃分模型[13]等自動生成文檔摘要。鑒于布谷鳥搜索(Cuckoo Search,CS)算法[14-15]在多目標優化問題中的性能優勢,本文提出基于CS算法的多文檔摘要方法,主要過程包括預處理、輸入表示和摘要表示。

1 多文檔摘要

多文檔摘要是從多個文檔中自動創建一個簡明文檔(稱為摘要)的過程。多文檔摘要過程具體包括預處理、輸入表示和摘要表示3個步驟,處理流程如圖1所示。摘要系統的輸入為多個文檔,先對這些文檔進行預處理,再通過輸入表示和摘要表示提取最終摘要。

圖1 多文檔摘要處理流程

1.1 預處理

預處理流程如圖2所示,具體步驟如下:

1)句子分割:從輸入的文檔集合中,將每個文檔D單獨分割為D={S1,S2,…,Sn},其中,Sj表示文檔中的第j個句子,n表示文檔中的句子數量。

2)分詞:將每個句子的術語標記為T={t1,t2,…,tm},其中,tk(k=1,2,…,m)表示D中出現的不同術語,m表示術語數量。

3)停用詞移除:將文檔中出現頻率較高但沒有實際檢索作用的詞進行移除,如“的”“了”“在”等。

4)詞干化:將句子轉換為詞的基本形式。

圖2 預處理流程

1.2 輸入表示

在輸入表示階段,使用預處理后的數據計算每個句子的權重(術語頻率之和),即句子信息量得分,將句子信息量得分作為算法輸入,其流程如圖3所示。

圖3 輸入表示流程

1.3 摘要表示

摘要表示的目的是為文檔集合生成包含有用信息的摘要。在最優句子的選擇過程中,基于預定義閾值對CS優化算法得出的句子信息量得分進行比較,選出能夠代表摘要的重要句子,其流程如圖4所示。

圖4 摘要表示流程

2 基于CS優化算法的多文檔摘要

2.1 CS優化算法

CS算法[16]是一種啟發式進化算法。布谷鳥是一種具有激進繁育策略的鳥,成年布谷鳥將卵產在其他鳥類的鳥巢中,由宿主鳥代為孵化和育雛。CS算法將鳥巢視為候選解,每個布谷鳥僅可產一枚卵,表示一個新的候選解。標準CS算法包含3個理想化規則:1)每個布谷鳥在一個隨機鳥巢中產一枚卵,代表一個解集;2)鳥巢中包含的最優卵將傳遞至下一代;3)可用鳥巢數量固定,一只宿主鳥發現一枚寄生卵的概率為Pa。當滿足條件時,宿主鳥可以丟棄寄生卵或放棄其鳥巢并在其他地方新建一個鳥巢。

在實際應用時可使用CS算法的最簡單形式,其中每個鳥巢只有一枚卵,在此情況下無需區分鳥巢、卵和布谷鳥,因為鳥巢、卵和布谷鳥均為一一對應關系,而且該算法可擴展至更復雜的情況,其中每個鳥巢中存在多個卵,代表一個解集。

(1)

另外,使用萊維飛行執行全局隨機游走,其全局收斂性已得到證明[16]。萊維飛行包含連續隨機步[17],其特征為一連串快速跳躍,計算公式為:

(2)

其中,α表示步長,其與優化問題的規模成正比(即α>0),?表示乘法中的逐項移動,Levy(λ)表示從萊維分布中提取的隨機數。

本文基于CS優化算法的多文檔摘要方法具體步驟如下:

步驟1采集一個多文檔集合M,M={D1,D2,…,DN},其中,每個Di表示集合M的單個文檔,Di的長度表示為句數,不同文檔包含不同句數。

步驟2使用句子分割、分詞、停用詞移除和詞干化對每個文本文檔Di進行預處理。

步驟3使用式(3)計算出每個預處理后文檔Di的句子Sj的信息量得分ISjk,即通過詞頻之和推導出的句子權重。

ISjk=tfjk×loga(n/nk)

(3)

其中:ISjk表示每個句子Sj相對于術語tk的信息量得分;tfjk表示術語頻率,即術語tk在句子Sj中的出現次數;nk表示包含術語tk的句子數量;loga(n/nk)表示用于句子檢索的向量空間模型中的逆句頻率。

步驟4使用式(4)計算出預處理后文檔Di的句間相似度。

(4)

步驟5基于相似度閾值,選擇每個Di中相似度最低的句子。

步驟6將選出的每個Di中所有相似度最低的句子合并為單個文檔Dinput。

步驟7初始化CS參數,例如種群大小、寄生卵被發現率(Pa)、步長因子(Sf)和萊維指數(λ)。

步驟8在指定搜索空間內,將句子信息量得分作為每只布谷鳥的鳥巢信息,每個鳥巢對應給定優化問題的一個候選解。

步驟9使用式(3)針對給定問題計算每個鳥巢的適應度函數fi。

步驟10利用式(2)得到新的鳥巢種群。

步驟11計算出與新鳥巢相對應的適應度函數fj,并將其與舊鳥巢的適應度函數fi進行比較。

步驟12若fj優于fi,則使用新候選解替換舊候選解。

步驟13在新種群中,選擇Pa性能較差的一部分鳥巢,將這些鳥巢替換為指定搜索空間內隨機生成的新鳥巢。

步驟14為新鳥巢計算適應度函數。

步驟15基于適應度數值,記錄當前種群集合中性能最優的鳥巢。之后,將這些鳥巢與前代最優鳥巢相比,選擇其中性能最優的鳥巢。

步驟16若未達到最大迭代次數,則返回步驟9。

步驟17基于預定義的句子相似度閾值從文檔中按時間順序選擇句子。

CS算法的時間復雜度計算主要集中于適應度函數f的計算[18],在本文中對文檔預處理過程為步驟1～步驟6,適應度函數包括舊鳥巢的適應度函數fi(步驟9)以及新鳥巢相對應的適應度函數fj(步驟10、步驟14)。當適應度函數f的自變量階數比n高時(n表示文檔中的句子數量),算法執行一次的時間復雜度為O(f(n)),當適應度函數f的自變量階數與n相同或低于n時,時間復雜度為O(n)。在考慮終止條件的情況下,總體時間復雜度為O(f(n)+n)。CS算法的空間復雜度較低,假設一個句子的存儲空間為一個存儲單元,對于包含n個句子的文檔,執行文檔摘要操作的空間復雜度為O(n)。

2.2 目標函數建立

文本摘要的目標是最大化生成摘要的信息量,降低冗余并保持可讀性。因此,本文基于多個目標,從文檔集合中建立摘要,通過內容覆蓋度、銜接性和可讀性以優化摘要,即創建3個子函數fcov(S)、fcoh(S)和fread(S),構成目標函數f(S)。

f(S)=fcov(S)+fcoh(S)+fread(S)

(5)

一個摘要中應包含相關句子集合以覆蓋文檔集合的主要內容,并通過信息量得分最高的句子反映文檔的主要內容,因此摘要的內容覆蓋度fcov(S)定義為:

fcov(S)=Sim(Si,O),i=1,2,…,n

(6)

其中,O表示句子集的主要內容中心,O={O1,O2,…,On},Oi為每個文檔的句子加權平均數。通過對Si和O之間的相似度進行評價,以衡量句子的重要程度。若相似度數值越高,則內容覆蓋度越高。

摘要句子之間的銜接性是指句子層面和段落層面的概念聯系,有助于更好地理解全文。若摘要銜接性fcoh(S)數值越高,則意味著句子間的聯系越緊密,其定義為:

fcoh(S)=1-Sim(si,sj),i,j=1,2,…,n且i≠j

(7)

摘要可讀性是指從集合D中選出能夠最大化句間關系的子集S。若fread(S)的數值越高,則摘要的可讀性越強,其定義為:

fread(S)=Sim(si,sj),i,j=1,2,…,n且i≠j

(8)

3 實驗結果與分析

通過實驗對本文多文檔摘要方法進行性能測試,并在DUC開源基準數據集(DUC2006和DUC2007)上比較本文方法與基于雙層K最近鄰(Double-layer K Nearest Neighbor,DKNN)算法[6]和PSO算法[9]的多文檔摘要方法的性能。實驗環境為MATLAB 2011b,實驗平臺為4核Intel酷睿i5處理器,3.2 GHz內存,Windows 7操作系統,并且使用ROUGE工具對摘要結果的ROUGE得分進行分析。

3.1 實驗數據集

本文使用DUC開源基準數據集對文本摘要結果進行評價。DUC數據集的參數設置如表1所示。在數據預處理階段,通過比較可用的停用詞表,從原始文檔中移除不重要的詞語,并使用詞干分析器提取術語詞干。

表1 DUC數據集參數設置

3.2 實驗控制參數

由于控制參數以應用為導向,因此不存在固定賦值,而是通過大量仿真實驗推導出參數值,本文方法、基于DKNN和PSO的多文檔摘要方法的參數設置如表2所示,其中:Vmin、Vmax分別表示粒子群的最小速度和最大速度;C1、C2為加速系數,分別表示粒子向自身極值和全局極值推進的加速權值;W表示慣性權值;SMP表示DKNN的最優k值;CDC表示步長因子;SRD表示距離因子;MR表示兩層KNN的混合率;w表示DKNN的近鄰樣本權重;C表示默認近鄰對象個數。

表2 3種多文檔摘要方法的參數設置

3.3 摘要評價指標

本文使用敏感度(Sen,又稱真陽性率)、陽性預測值(Positive Predictive Value,PPV)和摘要準確度(Sacc)指標對摘要方法進行評價。指標的定義基于候選摘要Candsum(使用本文方法生成的摘要)、參考摘要Refsum(人工生成的摘要)、真實句子Truesen(Candsum和Refsum中共同出現的句子)和不重要句子LSsen(Candsum或Refsum中均未出現的句子)。

敏感度定義為:

(9)

其中,|Truesen|表示真實句子的長度,|Refsum|表示參考摘要的總長度,參考摘要為人工生成,可信度高,用于評估來源摘要。式(9)還可看作是真陽性樣本數與真陽性樣本數和假陰性樣本數的比值。敏感度反映了摘要方法生成的摘要質量,其值越大表示質量越高。

陽性預測值定義如下:

(10)

其中,|Truesen|表示真實句子的長度,|Candsum|表示候選摘要的總長度。式(10)還可以看作是真陽性樣本數與真陽性樣本數和假陽性樣本數的比值。陽性預測值表示生成的摘要與原始文檔集合相同的概率,高相似度和低相似度的摘要均不會被記錄在內,因此該指標為針對特定情況。

摘要準確度用于綜合評價本文方法生成摘要的準確性,是最重要的評價指標。摘要準確度越高,表明生成的摘要與原始文檔集合的相似性越高,其定義如下:

(11)

3.4 ROUGE評價

本文使用文獻[19]開發的ROUGE-1.5.5工具包作為文本摘要的評價度量工具。ROUGE包括ROUGE-L、ROUGE-N和ROUGE-S等多種工具,用于衡量生成摘要與人工摘要之間的文法(N-gram)匹配。在工具包中,ROUGE-N度量與比較兩種摘要的N-gram并計算匹配數量:

(12)

其中,N表示N-gram的長度,Countmatch(N-gram)表示候選摘要和參考摘要中同時出現的N-gram最大數量,Count(N-gram)表示參考摘要中的N-gram數量。

本文使用ROUGE-N(ROUGE-1和ROUGE-2)度量對摘要性能進行評價,其度量與人工判斷存在高度相關性。ROUGE-1衡量系統生成摘要和人工創建摘要之間的一元分詞的重疊情況,ROUGE-2則比較二元分詞的重疊情況[20],通過摘要的內容覆蓋度、銜接性和文本可讀性完成ROUGE-N的評價。ROUGE度量值越高,表明其生成的摘要與原始文檔集合的相似度越高。

表3給出了基于PSO的多文檔摘要方法、基于DKNN的多文檔摘要方法和本文多文檔摘要方法在DUC2006和DUC2007數據集上,ROUGE-N(ROUGE-1和ROUGE-2)的F度量值的最差值、平均值和最優值統計結果。通過比較DUC2006數據集的F度量值可以看出,對于這3種方法,ROUGE-1的最優F度量值為0.411 27～0.431 10,ROUGE-2的最優F度量值為0.078 40～0.139 86。在DUC2007數據集上,ROUGE-1的最優F度量值為0.409 67～0.424 30,ROUGE-2的最優F度量值為0.076 20～0.103 40。雖然該數值取決于所使用的數據,但是可以明顯看出,本文多文檔摘要方法在兩個數據集的ROUGE得分中均得到了較高的F度量值,這充分說明了CS算法在摘要表示過程中的特征搜索優勢,相比于PSO算法,可以得到更優的搜索解。

表3 3種多文檔摘要方法基于ROUGE-N的F度量值比較

表4給出了基于PSO的多文檔摘要方法、基于DKNN的多文檔摘要方法和本文多文檔摘要方法在DUC2006和DUC2007數據集上,ROUGE-N(ROUGE-1和ROUGE-2)度量的召回率、精度和F度量值比較。表5給出了基于PSO的多文檔摘要方法、基于DKNN的多文檔摘要方法和本文多文檔摘要方法在DUC2006和DUC2007數據集上的敏感度、PPV和摘要準確度比較。通過對ROUGE-N的文檔摘要度量和指標進行分析得出,與基于PSO的多文檔摘要方法和基于DKNN的多文檔摘要方法相比,本文多文檔摘要方法在兩個數據集上均得到了更好的ROUGE-1和ROUGE-2結果,其原因為本文所采用的CS算法更加適用于多文檔摘要的特征搜索,ROUGE-N的F度量值不受召回率和精度的影響,并且摘要準確度也不受敏感度和PPV的影響。

表4 3種多文檔摘要方法的精度、召回率和F度量值比較

表5 3種多文檔摘要方法的敏感度、PPV和準確度比較

3.5 銜接性分析

銜接性是自動摘要的重要屬性,一般是指句子之間(甚至一個句子的不同部分)的聯系程度能夠支持讀者理解其中的含義。摘要中的銜接性并不僅指句子的語法正確性,還包括句子層面和段落層面的聯系。由此可知,前后句的銜接有助于更好地理解完整文本,通常使用余弦相似度計算摘要銜接性得分。圖5給出了3種多文檔摘要方法在DUC2006和DUC2007數據集上的銜接性得分。可以看出,在兩個數據集上,本文多文檔摘要方法的銜接性得分均高于基于DKNN[6]和PSO[9]的多文檔摘要方法。

圖5 3種多文檔摘要方法的銜接性得分比較

3.6 可讀性分析

可讀性是內容的可辨識和理解程度,取決于句子平均長度、句中包含的新詞數量以及文章中使用語言的語法復雜度等因素。常用的可讀性評價指標有Flesh Kincaid難度級數(FKGL)、Gunning fog(FOG)得分、SMOG指數、Coleman Liau(CL)指數和自動易讀性指數(Automatic Readability Index,ARI)等[21]。以上評價指標都是數值越高,可讀性得分越高,即生成的摘要更易于閱讀和理解。圖6和圖7分別給出了在DUC2006和DUC2007數據集上3種多文檔摘要方法的可讀性得分。可以看出,在DUC2006數據集上,本文多文檔摘要方法在CL、FOG、SMOG和ARI指標上的得分均優于基于PSO和DKNN的多文檔摘要方法,在FKGL指標上3種多文檔摘要方法得到了幾乎相同的結果。在DUC2007數據集上,本文多文檔摘要方法的可讀性得分均高于其他兩種方法。

圖6 3種多文檔摘要方法在DUC2006數據集上的可讀性得分比較

圖7 3種多文檔摘要方法在DUC2007數據集上的可讀性得分比較

4 結束語

本文提出一種基于布谷鳥搜索優化算法的多文檔摘要方法,先對輸入的多個文檔進行預處理,再通過輸入表示和摘要表示提取文檔摘要,并對摘要的內容覆蓋度、銜接性和可讀性進行優化。實驗結果表明,與基于PSO和DKNN的多文檔摘要方法相比,本文多文檔摘要方法能最大化摘要信息量,降低冗余并保持可讀性。后續將優化布谷鳥搜索算法的參數設置,并使用模擬退火算法、蟻群算法等啟發式算法進一步提升本文多文檔摘要方法的整體性能。