李 芳，何婷婷,2

(1. 國(guó)家數(shù)字化學(xué)習(xí)工程技術(shù)研究中心，湖北 武漢 430079; 2. 華中師范大學(xué) 計(jì)算機(jī)科學(xué)系，湖北 武漢 430079)

1 引言

隨著Internet的飛速發(fā)展，越來(lái)越豐富的信息出現(xiàn)在網(wǎng)絡(luò)中，文本數(shù)量以指數(shù)級(jí)的速度增長(zhǎng)，這極大方便了人們對(duì)信息的獲取和使用。但是，隨著網(wǎng)絡(luò)上信息的逐漸增多，在這些海量信息中快速準(zhǔn)確地找到所需要的信息也越來(lái)越困難[1]。

自動(dòng)文摘技術(shù)是解決當(dāng)前信息過(guò)載問(wèn)題的一種輔助手段，正日益受到國(guó)內(nèi)外學(xué)術(shù)界和工業(yè)界的密切關(guān)注。該技術(shù)將文檔的主要內(nèi)容在較短時(shí)間內(nèi)提供給用戶，可以提高人們獲取信息的效率，給用戶判斷和瀏覽感興趣的內(nèi)容提供幫助。

面向查詢的多文檔自動(dòng)文摘技術(shù)是將查詢返回的文檔集合中的相關(guān)內(nèi)容濃縮為一個(gè)包含查詢主題各個(gè)方面的、內(nèi)容簡(jiǎn)潔、組織良好、冗余低、滿足個(gè)性化需求的摘要。其研究目的在于解決從海量數(shù)據(jù)中獲取有用信息的困難，提高信息獲取及瀏覽的速度、適應(yīng)不同用戶對(duì)信息的個(gè)性化需求，從而提高用戶獲取和利用信息的效率，提高用戶在信息社會(huì)中的競(jìng)爭(zhēng)實(shí)力。目前，國(guó)內(nèi)面向查詢多文檔文摘的研究大多都是圍繞DUC(Document Understanding conference)、 TAC(Text Analysis Conference)比賽的。Prasad Pingali、Florian Boudin、李素建、何婷婷、滕沖[2-6]等提出了一系列的自動(dòng)文摘生成方法，這些方法生成的最終摘要都力求既滿足用戶的查詢需要，又盡可能覆蓋文檔集合的所有內(nèi)容。但是，有時(shí)用戶可能只想大致了解文檔集合中的信息分類或用戶可能只對(duì)查詢結(jié)果集合中的某一個(gè)方面的內(nèi)容感興趣等等，對(duì)于這些個(gè)性化的需求，傳統(tǒng)的摘要模式就很難給出滿意的結(jié)果。為此，本文除傳統(tǒng)的摘要模式外又設(shè)計(jì)了概括摘要、局部摘要、全局摘要和詳細(xì)摘要四種摘要模式，以更好地滿足用戶的個(gè)性化需求，提供盡可能豐富、實(shí)用、方便的文摘結(jié)果。

2 文檔的復(fù)雜網(wǎng)絡(luò)表示與子主題發(fā)現(xiàn)

首先，我們將查詢返回的文檔集合表示為帶權(quán)的復(fù)雜網(wǎng)絡(luò)，然后，利用復(fù)雜網(wǎng)絡(luò)中的抱團(tuán)發(fā)現(xiàn)思想來(lái)發(fā)現(xiàn)文檔集合中的子主題。

2.1 文檔的復(fù)雜網(wǎng)絡(luò)表示

這里，我們用帶權(quán)復(fù)雜網(wǎng)絡(luò)來(lái)重構(gòu)查詢返回的文檔集合，邊的權(quán)值是兩個(gè)節(jié)點(diǎn)之間的相似度值。首先將每個(gè)文本表示成向量,計(jì)算相似度矩陣W，再來(lái)構(gòu)建帶有權(quán)重的網(wǎng)絡(luò)圖：P=(V，E)，其中V= {S1，S2，…，Sn}是網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，對(duì)應(yīng)所有的文本；E= {(Si，Sj)|Si和Sj的相似度值wij大于某個(gè)閾值}是邊的集合，邊的權(quán)重是網(wǎng)絡(luò)兩個(gè)節(jié)點(diǎn)的相似度值wij。

為了方便后續(xù)的子主題發(fā)現(xiàn)和降低計(jì)算復(fù)雜度，文檔集合的網(wǎng)絡(luò)拓?fù)鋱D表示是通過(guò)兩個(gè)階段表示的。在第一階段，網(wǎng)絡(luò)結(jié)構(gòu)中的每個(gè)節(jié)點(diǎn)表示一個(gè)文本，邊的權(quán)值為兩個(gè)文本的相似度，每個(gè)網(wǎng)絡(luò)抱團(tuán)對(duì)應(yīng)于一個(gè)文本類。第二階段的文檔表示是在文本聚類之后，網(wǎng)絡(luò)結(jié)構(gòu)中包含多個(gè)子網(wǎng)，每個(gè)子網(wǎng)表示第一階段中的一個(gè)文本類。子網(wǎng)中的每個(gè)節(jié)點(diǎn)表示一個(gè)段落，邊的權(quán)值為兩個(gè)段落的相似度。每個(gè)網(wǎng)絡(luò)抱團(tuán)將對(duì)應(yīng)一個(gè)子主題。這樣，文檔集合的網(wǎng)絡(luò)拓?fù)鋱D就形成了上下對(duì)應(yīng)的兩層結(jié)構(gòu)，如圖1所示。這個(gè)結(jié)構(gòu)是文本聚類和段落聚類的基礎(chǔ)，也是后面多種摘要模式設(shè)計(jì)的基礎(chǔ)。

圖1 文檔集合的網(wǎng)絡(luò)拓?fù)鋱D

2.2 子主題發(fā)現(xiàn)

子主題發(fā)現(xiàn)的基本方法是聚類，每個(gè)類是一個(gè)子主題。基于聚類的子主題發(fā)現(xiàn)過(guò)程就是在計(jì)算相似度的基礎(chǔ)上把聚類單元聚合成不同主題類別。

2.2.1 基于抱團(tuán)發(fā)現(xiàn)的聚類方法

對(duì)于復(fù)雜網(wǎng)絡(luò)抱團(tuán)結(jié)構(gòu)分析，Newman、Clauset等[7-8]提出了基于貪婪算法思想的凝聚算法：Newman快速算法和CNM算法。他們先假設(shè)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)為一個(gè)抱團(tuán)，然后再來(lái)合并有邊相連的抱團(tuán)對(duì)，合并的原則是使模塊度Q增大最多或者減少最小，直到整個(gè)網(wǎng)絡(luò)都合并成為一個(gè)抱團(tuán)。此方法是建立在非帶權(quán)網(wǎng)絡(luò)上，將每條邊看作是相等的。而我們的文檔集合表示為一個(gè)帶權(quán)網(wǎng)絡(luò)，所以我們必須重新定義節(jié)點(diǎn)度和模塊度。

那么，在文檔集合的復(fù)雜網(wǎng)絡(luò)表示基礎(chǔ)之上，利用CNM算法思想，就可以得到自動(dòng)發(fā)現(xiàn)社區(qū)結(jié)構(gòu)的聚類算法。

自動(dòng)發(fā)現(xiàn)社區(qū)結(jié)構(gòu)的聚類算法流程如下：

輸入：P(原始網(wǎng)絡(luò)圖)

輸出：Gp(P下的抱團(tuán)組成的集合)

1 初始化Gp={P}，即每個(gè)節(jié)點(diǎn)就是一個(gè)獨(dú)立的抱團(tuán)。初始的eij,ai為：

2 初始化模塊性增量矩陣：

3 初始化最大堆H為ΔQ每一行的最大元素。

4 從最大堆H中選擇最大的ΔQij,合并相應(yīng)的抱團(tuán)i和j，標(biāo)記合并后的抱團(tuán)的標(biāo)號(hào)為j；

更新ΔQ：刪除第i行和第i列的元素,更新第j行和第j列的元素:

更新最大堆H：更新ΔQij后,就要更新最大堆中相應(yīng)的行和列的最大元素。

5 重復(fù)步驟4,直到模塊性增量矩陣ΔQ中最大的元素由正變到成負(fù)后。

6 結(jié)束并返回Gp。

算法輸出的每個(gè)抱團(tuán)即為一個(gè)類，這是一種自適應(yīng)的聚類方法，可以自動(dòng)確定類的個(gè)數(shù)，自動(dòng)發(fā)現(xiàn)文本集合中包含的子主題。它在理論上能夠較好地解決一些聚類方法對(duì)初始解敏感、易陷于局部最優(yōu)的缺點(diǎn)，能在全局進(jìn)行搜索。

2.2.2 文本、段落兩階段聚類策略

在文檔集合的雙層復(fù)雜網(wǎng)絡(luò)表示的基礎(chǔ)上，我們提出文本、段落兩階段聚類的策略來(lái)識(shí)別文本集合中的潛在子主題。先對(duì)文本進(jìn)行聚類， 然后再對(duì)每個(gè)文本類分別進(jìn)行段落聚類，每個(gè)段落類為一個(gè)子主題。這樣既可以避免因?yàn)榫垲悊卧《斐傻氖ノ谋緝?nèi)容的許多關(guān)聯(lián)的缺點(diǎn)，又不會(huì)因?yàn)榫垲悊卧^(guò)大而帶來(lái)太多冗余信息。

復(fù)雜網(wǎng)絡(luò)抱團(tuán)發(fā)現(xiàn)方法的效果會(huì)隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的增加而變差。采用文本、段落兩階段聚類的策略可以有效地控制網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目，段落聚類時(shí)，只考慮屬于某個(gè)文本類的段落，而不是所有的段落。這樣，網(wǎng)絡(luò)中的節(jié)點(diǎn)就不至于太多，從而在一定程度上提高了聚類的效果。

3 個(gè)性化摘要模式

面向查詢的多文檔自動(dòng)文摘的一個(gè)重要特征是要能滿足用戶的個(gè)性化查詢需求。在文檔集合的網(wǎng)絡(luò)拓?fù)鋱D的支持下，除傳統(tǒng)的摘要模式外，又產(chǎn)生了局部摘要、概括摘要等多種摘要模式。

3.1 個(gè)性化摘要模式設(shè)計(jì)

由于我們對(duì)查詢返回的文檔集合進(jìn)行了兩個(gè)層次的復(fù)雜網(wǎng)絡(luò)表示，一層為文本網(wǎng)絡(luò)拓?fù)鋱D，另一層為段落網(wǎng)絡(luò)拓?fù)鋱D，因此我們能夠方便地應(yīng)用這雙層網(wǎng)絡(luò)結(jié)構(gòu)，以多種策略構(gòu)成摘要，更好地服務(wù)于用戶的個(gè)性化需求，提供盡可能豐富、實(shí)用、方便的文摘模式。

(1) 文檔摘要

文檔摘要以段落類為子主題，把文本集合的所有段落類作為一個(gè)整體，從每個(gè)段落類中選擇文摘句來(lái)構(gòu)成摘要。

文檔摘要是最基本、最常見(jiàn)的文摘模式，摘要內(nèi)容對(duì)查詢主題覆蓋全面且文字簡(jiǎn)潔、冗余低、可讀性強(qiáng)。用戶可以在短時(shí)間內(nèi)全面概括地了解查詢對(duì)象，達(dá)到查詢目的。

(2) 概括摘要

概括摘要以文本類為子主題，從每個(gè)文本類分別選擇若干句子來(lái)生成摘要。

概括摘要是所有文檔集合整體上的概述，把每個(gè)文本類所描述的內(nèi)容簡(jiǎn)要地提供給用戶。這樣就利于用戶對(duì)信息做快速瀏覽和分類，選擇自己真正感興趣的內(nèi)容，在下面將要介紹的局部摘要的支持下，用戶可以作進(jìn)一步的了解，還可以使用詳細(xì)摘要模式了解更詳細(xì)的信息。

(3) 局部摘要

局部摘要只單獨(dú)從一個(gè)文本類的各個(gè)段落類中提取文摘句，產(chǎn)生一個(gè)較完整的摘要。

通常，用戶只是對(duì)查詢結(jié)果集合中的某一個(gè)方面的內(nèi)容感興趣，因此我們?cè)O(shè)計(jì)了局部摘要，這是一種偏重摘要，它只與當(dāng)前文本類中每個(gè)段落子主題密切相關(guān)，生成的文摘內(nèi)容更加集中，能夠比較詳細(xì)地描述當(dāng)前文本類的主要內(nèi)容。這樣用戶就可以只瀏覽自己感興趣的內(nèi)容，從而節(jié)省了大量的時(shí)間和精力。

(4) 全局摘要

所有局部摘要構(gòu)成整個(gè)文本集合的全局摘要。

全局摘要也是對(duì)查詢返回集合的全面描述，需要從每個(gè)段落類中抽取文摘句，但與文檔摘要相比，由所有局部摘要合并而成的全局摘要對(duì)每個(gè)文本類來(lái)說(shuō)，其內(nèi)容也更加集中，有利于提高文摘句排序的質(zhì)量，提高文摘的可讀性。在技術(shù)上，當(dāng)文本集合很大時(shí)，采用這種自底向上的模式可以降低文摘生成的難度。

(5) 詳細(xì)摘要

詳細(xì)摘要是從每個(gè)段落類中提取核心段落，構(gòu)成以段落為單位的摘要。

這種形式的文摘，可以讓用戶更準(zhǔn)確、更詳細(xì)地掌握和理解這一個(gè)子主題的主要信息，可以彌補(bǔ)單純追求簡(jiǎn)潔性的以句子為單位的文摘的一些不足。

圖2給出了五種摘要模式的整體示意圖。在文檔集合的網(wǎng)絡(luò)拓?fù)鋱D的支持下，用戶可以以主題為線索自主漫游，從文摘句、核心段落、子主題(段落類)到文本類多層次擴(kuò)展，按照一定的邏輯順序?yàn)g覽信息，從而更準(zhǔn)確、快速地把握信息，滿足查詢需要。

圖2 五種摘要模式示意圖

3.2 文摘單元抽取策略

從摘要模式示意圖中可以看出，本文抽取的文摘單元有兩種：句子和核心段落。對(duì)于文摘句的抽取，我們利用了一種基于關(guān)鍵詞提取的文摘句提取策略[9]。對(duì)于核心段落，可以借鑒復(fù)雜網(wǎng)絡(luò)中挖掘重要節(jié)點(diǎn)的理論和方法，下面將重點(diǎn)介紹核心段落的提取方法。

如果某個(gè)段落跟當(dāng)前子主題下的其他很多段落都具有一定的相似度，那么這個(gè)段落就可能覆蓋了此子主題的大部分內(nèi)容，因此應(yīng)該把它作為一個(gè)核心段落。在網(wǎng)絡(luò)中就表現(xiàn)為這個(gè)節(jié)點(diǎn)與網(wǎng)絡(luò)中的其他節(jié)點(diǎn)都有邊相連。我們所構(gòu)建的網(wǎng)絡(luò)是帶權(quán)網(wǎng)絡(luò)，邊的權(quán)值是兩個(gè)段落之間的相似度值，因此，節(jié)點(diǎn)加權(quán)度也應(yīng)該納入考慮。這樣當(dāng)兩個(gè)節(jié)點(diǎn)度相同時(shí)，就可以用節(jié)點(diǎn)加權(quán)度衡量它們的重要性。另外，核心段落必須與查詢具有較大的相關(guān)性。由此，給出了節(jié)點(diǎn)重點(diǎn)性公式：

在得出每個(gè)節(jié)點(diǎn)的重要性值后，得分最高的節(jié)點(diǎn)所表示的段落就是該段落類的核心段落。

4 實(shí)驗(yàn)結(jié)果及分析

我們收集了十個(gè)查詢主題共200篇文章，對(duì)于每個(gè)主題，把從搜索引擎上返回的前20篇左右的文本作為與查詢相關(guān)的文檔集合，再分別進(jìn)行聚類發(fā)現(xiàn)子主題，生成各種模式的摘要。這十個(gè)查詢主題分別是奧巴馬就任美國(guó)總統(tǒng)、臺(tái)灣選舉馬蕭獲勝，“入聯(lián)公投”失敗、“神七”發(fā)射，中國(guó)航天員首次太空行走、汶川5·12特大地震災(zāi)害、中國(guó)火車出軌相撞、陳水扁家族海外洗錢(qián)案、美國(guó)次債問(wèn)題造成世界金融危機(jī)、第29屆奧運(yùn)會(huì)在北京拉開(kāi)帷幕、三鹿奶粉事件、全球華人反“藏獨(dú)”反暴力。

4.1 聚類效果分析

我們對(duì)十個(gè)查詢主題下的200篇文本進(jìn)行了文本聚類，正確率是84.5%。然后在此基礎(chǔ)上又進(jìn)行了段落聚類，正確率是92%，可見(jiàn)應(yīng)用文本、段落兩階段聚類策略可以提高聚類的效果。

實(shí)驗(yàn)中，我們是逐步加入每個(gè)主題下的文檔集合來(lái)進(jìn)行聚類的，我們發(fā)現(xiàn)隨著文本數(shù)即網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)的增加，聚類的效果會(huì)有所下降，具體情況如圖3 所示。

圖3 主題數(shù)與準(zhǔn)確率的關(guān)系

在面向查詢自動(dòng)文摘中，查詢返回文本的初始類別本身就不會(huì)很多，文本聚類效果就有可能比較好，再加上段落聚類對(duì)文本聚類效果的彌補(bǔ)，可以得出：基于復(fù)雜網(wǎng)絡(luò)抱團(tuán)發(fā)現(xiàn)的文本、段落兩階段聚類方法用于面向查詢自動(dòng)文摘領(lǐng)域是完全可行的。

4.2 摘要效果分析

我們給出了十個(gè)查詢主題下每種摘要模式的平均召回率(壓縮比為10%)，召回率的計(jì)算是基于人工標(biāo)準(zhǔn)摘要的。如果人工摘要包含m個(gè)句子，機(jī)器摘要包含n個(gè)句子，機(jī)器摘要和人工摘要重合的句子數(shù)為k，則召回率為R=k/m，這里的重合是指兩個(gè)句子的相似度值超過(guò)某個(gè)閾值，并不要求它們完全相同。具體結(jié)果如圖4所示。

圖4 每個(gè)查詢主題五種摘要模式的平均召回率

從圖中可以看出，所有的召回率都在50%以上，說(shuō)明了系統(tǒng)得到的文摘效果是可以接受的，基本上能夠滿足每種摘要模式的要求。

但是，還可以看到，文檔摘要和全局摘要的效果稍微要差一些，主要是因?yàn)槎温漕愔貜?fù)，造成文摘結(jié)果的冗余偏大，而人工摘要?jiǎng)t會(huì)選取不同的句子。本文的摘要結(jié)果并沒(méi)有進(jìn)行文摘句排序，這些都是以后需要改進(jìn)的地方。

5 小結(jié)

本文針對(duì)面向查詢的多文檔自動(dòng)文摘的相關(guān)技術(shù)展開(kāi)了討論。首先，提出了文檔集合的復(fù)雜網(wǎng)絡(luò)表示方法，將整個(gè)文檔集合表示為以文本、段落為節(jié)點(diǎn)的雙層網(wǎng)絡(luò)結(jié)構(gòu)。重新定義了模塊度增量矩陣，采用CNM算法思想對(duì)文本、段落進(jìn)行自適應(yīng)聚類，自動(dòng)發(fā)現(xiàn)文本集合中包含的子主題。接著，充分利用了文檔的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，除了傳統(tǒng)的摘要模式外，我們又設(shè)計(jì)了概括摘要、局部摘要、全局摘要和詳細(xì)摘要四種摘要模式，更好地滿足用戶的個(gè)性化需求，提供盡可能豐富、實(shí)用、方便的文摘結(jié)果，支持用戶以主題為線索自主漫游，按照一定的邏輯順序?yàn)g覽信息。

本文是對(duì)面向查詢的多文檔摘要技術(shù)的一個(gè)初步探索，還有很多需要進(jìn)一步研究的問(wèn)題。摘要模式在一定程度上滿足了用戶的要求，但是抽取的文摘單元只有句子和段落。而我們認(rèn)為面向查詢的文摘單元也可以是若干個(gè)關(guān)鍵詞、文本的一個(gè)區(qū)域等等。另外，我們還將試驗(yàn)利用其他的文摘單元抽取策略，以得到更好的摘要結(jié)果。另外，為了取得更好的效果，需要對(duì)文本或句子進(jìn)行深入理解，從句子整體的語(yǔ)義信息對(duì)相似度和重要性進(jìn)行更好的刻畫(huà)。

[1] Lynette Hirschman, R.Gaizauskas. Natural Language Question Answering: The View from Here[R]. Natural Language Engineering, 2001， 7(4):275-300.

[2] Prasad Pingali, Rahul K, Vasudeva Varma. IIIT Hyderabad at DUC 2007[C]//Proceedings of DUC2007.

[3] B.Florian, B.Fréderic, M.El-Bèze,et al. The LIA summarization system at DUC2007[C]//Proceedings of DUC2007.

[4] Sujian Li, You Ouyang, Bin Sun, Peking University at DUC 2006[C]//Proceedings of DUC2006.

[5] 邵偉,何婷婷,胡珀，等. 一種面向查詢的多文檔文摘句選擇策略[C]//第九屆全國(guó)計(jì)算語(yǔ)言學(xué)學(xué)術(shù)會(huì)議, 2007: 637-642.

[6] 滕沖,何炎祥,劉德喜,等.基于基本要素的用戶聚焦型文摘內(nèi)容選擇[C]//2007年中文信息處理國(guó)際會(huì)議,2007:513-519.

[8] Newman MEJ. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004;69(6): (066133-1)- (066133-5).

[9] 馬亮,何婷婷,李芳,等. 以關(guān)鍵詞抽取為核心的文摘句選擇策略[J]. 中文信息學(xué)報(bào),2008，22(6):50-54.