一種基于HITS算法的Blog文摘方法

苗 家,馬 軍,陳竹敏

(山東大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250101)

1 前言

文檔摘要一直是信息檢索中的一個(gè)重要課題。自動文檔摘要對一個(gè)數(shù)據(jù)源(單個(gè)文檔或是文檔集)進(jìn)行分析，通過抽取數(shù)據(jù)源的主要信息，組成一篇簡潔的能夠表達(dá)數(shù)據(jù)源相關(guān)內(nèi)容的文章。對于自動文檔摘要方法的研究，人們已結(jié)合信息檢索和自然語言處理等領(lǐng)域的技術(shù)提出了一些自動摘要方法，并根據(jù)這些方法構(gòu)建了一些成功的自動摘要的系統(tǒng)[1-3]，但以往提出的一些文摘的方法一般針對于新聞文章，而對Blog、論壇等交互式社區(qū)網(wǎng)絡(luò)文章的相關(guān)摘要技術(shù)研究較少。隨著Web2.0交互式社區(qū)的發(fā)展，人們對交互式社區(qū)網(wǎng)絡(luò)中信息獲取的需求日益增長，這樣就有必要對這些特殊類型的文體進(jìn)行深入的研究。

本文基于一些已有的自動文摘方法，針對Blog文章的特點(diǎn)，提出了一種面向Blog的自動摘要方法。本方法首先采用Blog評論的一些統(tǒng)計(jì)特征和文本特征來計(jì)算評論的重要性權(quán)值，然后基于HITS模型結(jié)合評論與正文句子的重要性權(quán)值來選擇正文句子得到目標(biāo)文摘。實(shí)驗(yàn)表明本文方法在20%和30%壓縮比上的ROUGE值相對已有的方法均有較好的提升。

2 相關(guān)工作

目前，自動文摘方法按照研究的技術(shù)路線大體可以分為兩類，即抽取式摘要方法和描述式摘要方法。其中抽取式摘要方法主要分為三個(gè)部分： 計(jì)算句子相似度、抽取文章句子和對抽取出的句子進(jìn)行排序[4]。而描述式摘要方法則需要通過信息的融合、句子的壓縮以及重組生成摘要。本文討論研究的是抽取式的摘要方法。

抽取式摘要方法按照句子相似度的計(jì)算方式大體可以分為三類[5]： 基于詞匯鏈的方法、基于圖模型的方法以及基于特征的方法。其中基于詞匯鏈的方法[1,6]提取文檔的名詞、復(fù)合名詞等，基于WordNet或其他語義詞典建立詞匯鏈來描述文檔的主題，最終結(jié)合句子所屬詞匯鏈的相關(guān)信息得到句子權(quán)重?；趫D模型的方法[2,7]將文檔句子抽象為圖中節(jié)點(diǎn)，根據(jù)句子之間存在的相似度關(guān)系構(gòu)建圖中的邊，并以構(gòu)建的圖表示文檔或文檔集，然后運(yùn)用PageRank或HITS算法計(jì)算句子權(quán)重?；谔卣鞯姆椒╗3,8]則認(rèn)為句子的權(quán)重由文檔的一些統(tǒng)計(jì)特征或語義特征決定，通過結(jié)合這些特征的相關(guān)測度來得到句子權(quán)重。

目前關(guān)于Blog的自動摘要研究進(jìn)行的還不是很多。Zhou等人[9]將Blog文章看作是其鏈接到的新聞文章的摘要，只是融合了作者的一些意見，通過去除Blog文章中與新聞文章不相關(guān)的句子得到Blog的摘要。這種方法完全忽略了評論對正文句子權(quán)重的影響，而評論是Blog的一個(gè)非常重要的組成特征。Hu等人[5]根據(jù)評論間存在的引用、提及和相關(guān)三種關(guān)系建立評論間的關(guān)系圖，使用PageRank以及三階張量的PARAFAC分解兩種方法分別計(jì)算了評論重要性權(quán)重并進(jìn)一步得到評論中關(guān)鍵詞的權(quán)重，然后根據(jù)正文中出現(xiàn)的關(guān)鍵詞的相關(guān)信息得到正文句子的權(quán)重。這種方法雖然考慮了評論對正文摘要的影響，但卻忽略了評論內(nèi)容以及評論者信息對評論重要性的影響。基于當(dāng)前的研究現(xiàn)狀，本文提出了一種使用評論內(nèi)容以及評論者信息相關(guān)特征計(jì)算評論權(quán)重并基于HITS算法結(jié)合評論與正文相關(guān)信息得到正文句子權(quán)重的方法。

3 Blog特點(diǎn)分析

Weblog是Web Log的縮寫，國內(nèi)普遍譯為博客，后來縮寫為Blog，Blogger是創(chuàng)作更新Blog的人，通常被稱為這個(gè)Blog的博主，創(chuàng)作Blog的活動稱為Blogging。一個(gè)Blog可以被定義成一個(gè)網(wǎng)頁，它通常是由簡短且經(jīng)常更新的文章(Post)組成，這些張貼的文章按照年份和日期排列。文獻(xiàn)[10]中給出了Blog的站點(diǎn)結(jié)構(gòu)及鏈接關(guān)系： Blog 站點(diǎn)由站點(diǎn)URL，RSS，Blog作者，站點(diǎn)名，Blog條目等信息組成。其中Blog條目包含永久鏈接，Blog作者，發(fā)表時(shí)間，Blog標(biāo)題，正文描述，評論等信息。評論中含有Blog作者，發(fā)表時(shí)間及評論內(nèi)容等信息。Blog站點(diǎn)之間以及Blog與其他類型站點(diǎn)之間存在著鏈接關(guān)系。

相對于網(wǎng)絡(luò)上其他信息實(shí)體(論壇，新聞網(wǎng)頁等)來說，Blog最重要的一個(gè)特征就是Blog文章有與其相應(yīng)的讀者評論信息。Mishne等人[11]進(jìn)行了大范圍的Blog評論研究，他們收集了36 044個(gè)Blog的相關(guān)信息，經(jīng)過統(tǒng)計(jì)表明其中有28%的Blog包含讀者評論，在所有包含讀者評論的Blog中，平均每篇博文(Post)擁有6.3個(gè)相應(yīng)的評論。Blog文章正文部分主要表達(dá)的是文章作者對某個(gè)事件或者事物的看法和主張等信息，評論中的信息則可能包含了讀者對作者提出觀點(diǎn)的理解及反饋，而這些信息大部分是其他潛在的讀者可能感興趣并希望關(guān)注的信息。使用評論可以提高Blog檢索效率，提高Blog文檔的信息抽取的準(zhǔn)確性。

我們對Blog評論進(jìn)行統(tǒng)計(jì)分析得到如下特點(diǎn)：

1. 主題漂移現(xiàn)象。評論是每個(gè)評論者非常主觀的意見表達(dá)，每個(gè)人理解同一個(gè)事物或是事件的角度或深度各不相同，評論者討論的話題也涉及文章多個(gè)不同的方面。

2. 評論的質(zhì)量很大程度上與評論者以及評論內(nèi)容相關(guān)[12]。通常，在以往能給出較高質(zhì)量評論的評論者，其給出高質(zhì)量評論的可能性就越大，同時(shí)評論本身的一些文本特征也會影響評論的質(zhì)量。

3. Blog評論存在大量的噪聲。有些評論與主題無關(guān)，而隨著評論數(shù)量的增加，前面偏離主題的評論可能會影響后面評論的質(zhì)量。

4 文摘算法

4.1 Blog文檔描述

本文主要針對單Blog文檔進(jìn)行摘要，評論中的句子不參與最終摘要句子的選取。對于一個(gè)Blog正文文檔D，定義S={s1,s2,…,sm}為D中句子的集合，其中si(1≤i≤m)表示D中的第i個(gè)句子，m為D中句子的總數(shù)，句子si可以被表示為句子中詞的集合Tsi={t1,t2,…,th}，h為句子si中不同詞的個(gè)數(shù)。定義C={c1,c2,…,cn}為與D相對應(yīng)的評論的集合，其中cj(1≤j≤n)表示第j條評論，n為評論的總數(shù)，評論cj可以被表示成為評論中詞的集合Tcj={t1,t2,…,tr}，r為評論cj中不同詞的個(gè)數(shù)。我們采用向量空間模型表示文檔單元、句子單元以及評論單元這三種文本單元。我們?yōu)樗形谋締卧谐霈F(xiàn)的詞建立一個(gè)詞典L，任意一個(gè)文本單元U都可以用一個(gè)向量(w1,w2,…,wl)表示，其中l(wèi)為詞典L中的詞條數(shù)，向量維度i(1≤i≤l)上的權(quán)值使用基于標(biāo)準(zhǔn)TF-IDF的算法得出如下：

wi=tfi×idfi

(1)

4.2 評論排名

根據(jù)第3節(jié)中分析的評論特點(diǎn)，本文考慮選取如下特征來衡量評論的重要性。

1. 評論者Blog的月訪問量，記為f1。評論者Blog月訪問量反映了這個(gè)評論者在整個(gè)Blog網(wǎng)站中受歡迎的程度，一個(gè)博主所發(fā)表的文章越受歡迎，表明這個(gè)博主的一些觀點(diǎn)就越能被讀者認(rèn)同，其發(fā)表的評論的重要性就有可能越高。

2. 評論者發(fā)表文章的數(shù)目，記為f2。評論者發(fā)表文章的數(shù)目反映了該評論者在Blog網(wǎng)站中的活躍程度，一個(gè)博主的活躍程度越高，表明這個(gè)博主參與意見表達(dá)的能力越強(qiáng)，從側(cè)面反映了其發(fā)表評論的重要性就有可能越高。

3. 評論者Blog以往收到的評論總數(shù)，記為f3。評論者Blog收到的評論歷史統(tǒng)計(jì)數(shù)量反映出評論者的觀點(diǎn)態(tài)度等信息，博主的文章觀點(diǎn)越鮮明深入，就越能引發(fā)讀者對文中觀點(diǎn)的熱議，這樣的博主在評價(jià)其他人的文章時(shí)給出的評論的重要性就有可能越高。

4. 評論的長度，即評論中出現(xiàn)的詞的個(gè)數(shù)，記為f4。評論越長，表明評論者投入的時(shí)間和精力越多，則評論的重要性就有可能越高。

5. 評論內(nèi)容的復(fù)雜度，記為f5。評論的內(nèi)容越復(fù)雜，說明評論中包含的觀點(diǎn)信息越多，評論重要性就有可能越高。本文用信息熵[12]作為度量評論內(nèi)容復(fù)雜度的測度，如下式：

(2)

其中entropy(cj)表示評論cj的信息熵，λ為cj中詞的總個(gè)數(shù)，n表示cj中不同詞的個(gè)數(shù)，pi表示cj中詞ti的詞頻數(shù)。

6. 評論觀點(diǎn)的獨(dú)特性，記為f6。評論觀點(diǎn)越獨(dú)特表明評論者看待問題的深度或廣度越突出，這樣的評論的重要性就有可能越高。我們引入如下測度[12](式(3))來度量獨(dú)特性：

(3)

其中pi為評論cj中詞ti的詞頻數(shù)，λ為cj中詞的總個(gè)數(shù)，|C|為cj對應(yīng)的Blog文章包含的評論總數(shù)，|{c:ti∈c}|表示cj對應(yīng)的Blog文章包含的評論中含有詞ti的評論個(gè)數(shù)。

基于如上提出的6個(gè)特征，我們使用多特征值的方法計(jì)算評論的權(quán)重，如下式：

(4)

score(cj)表示評論cj的重要性分?jǐn)?shù)，ωk表示cj的第k個(gè)特征的權(quán)重，score(fk, j)表示cj的第k個(gè)特征的相關(guān)測度值，n為特征數(shù)目。在量化評論各特征的權(quán)重ωk時(shí)，我們隨機(jī)選取了20篇Blog文章，人工為相應(yīng)的評論標(biāo)注重要度(我們選用了0, 0.2, 0.4, 0.6, 0.8和1共六種標(biāo)注值)，通過線性回歸學(xué)習(xí)得到各特征的權(quán)重ωk。

4.3 結(jié)合評論的blog文摘算法

本節(jié)我們提出了一種基于HITS模型的Blog正文句子評分算法。HITS模型將節(jié)點(diǎn)分為兩類即： 中心節(jié)點(diǎn)(hub)和權(quán)威節(jié)點(diǎn)(authority)，中心節(jié)點(diǎn)連接了許多優(yōu)秀的權(quán)威節(jié)點(diǎn)，權(quán)威節(jié)點(diǎn)的內(nèi)容質(zhì)量較高并被較多中心節(jié)點(diǎn)連接[7]。

本文中我們將單個(gè)的評論作為權(quán)威節(jié)點(diǎn)，Blog正文中的單個(gè)句子作為中心節(jié)點(diǎn)，如圖1所示，二分圖中上面的節(jié)點(diǎn)代表正文中的句子，下面的節(jié)點(diǎn)代表評論。圖中邊的關(guān)系可以被認(rèn)定為一種生成關(guān)系，即評論由與之相連的多個(gè)句子共同衍生出來，我們基于如下的假設(shè)來選取摘要句子： 能衍生出多個(gè)重要評論的句子包含更多潛在讀者感興趣的信息，其重要性就越高，同樣由多個(gè)包含重要信息的句子所衍生出來的評論，其重要性也就越高。這樣經(jīng)過HITS算法相互增強(qiáng)式的迭代計(jì)算，中心值較高的句子，其重要性就越高。

圖1 HITS模型

我們用G={Vs,Vc,E}來表示該模型，其中Vs={si|si∈S}為Blog正文句子的集合，Vc={cj|cj∈C}為評論的集合，E為兩個(gè)頂點(diǎn)集之間邊的集合。若節(jié)點(diǎn)si和cj之間的余弦相似度大于預(yù)設(shè)閾值α，則兩節(jié)點(diǎn)間存在邊ei,j，該邊被賦予一個(gè)權(quán)重ωi,j，該權(quán)重為si和cj的余弦相似度，該相似度表示句子si在衍生出評論cj的過程中提供的貢獻(xiàn)值。這樣通過閾值的設(shè)定可以有效地過濾噪聲評論，在對正文句子進(jìn)行評分時(shí)只考慮與正文相似度較高的評論與相關(guān)句子之間的相互影響。

第x次迭代計(jì)算時(shí)，句子節(jié)點(diǎn)的中心值和評論節(jié)點(diǎn)的權(quán)威值的計(jì)算方法[2]如下：

由公式(5)和公式(6)我們可以很自然地將評論與正文的文本相似度特征結(jié)合到正文句子的評分過程當(dāng)中，并以這種相似度關(guān)系為紐帶將評論重要性對正文句子重要性的影響以及正文句子重要性對評論重要性的影響有效地結(jié)合起來。我們將句子中心值的初值設(shè)為正文句子與正文文檔的余弦相似度，評論權(quán)威值的初值設(shè)為評論的重要性分?jǐn)?shù)score(cj)。經(jīng)過多次迭代計(jì)算，直至中心值與權(quán)威值收斂即迭代前后數(shù)值之差小于預(yù)設(shè)閾值(本文取0.000 1)。最后得到句子的重要性分?jǐn)?shù)如下：

score(si)=hub(si)

(9)

此處應(yīng)注意到當(dāng)Blog文章沒有相應(yīng)評論時(shí)，本文算法中正文句子的分?jǐn)?shù)就由句子與文檔的余弦相似度決定。

在對正文句子進(jìn)行評分之后，為了去除生成摘要中的冗余信息，避免選取出內(nèi)容近似的句子，本文通過計(jì)算剩余句子和選定句子之間的相似度，降低剩余句子中與已選出句子之間相似度較高的句子的權(quán)值來降低摘要冗余度。最后按照摘要壓縮比選取分值最高的句子，按照正文中出現(xiàn)的順序組成blog摘要。

5 實(shí)驗(yàn)

據(jù)我們所知，已公開發(fā)表的文獻(xiàn)中并不存在標(biāo)準(zhǔn)的中文Blog數(shù)據(jù)集，我們從鳳凰播報(bào)(http://Blog.ifeng.com/)收集數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集。鳳凰網(wǎng)作為傳統(tǒng)媒體的代表，擁有大量的具有一定知識水平的受眾，他們大都是以中年人和專家為主，鳳凰網(wǎng)Blog文章內(nèi)容大都與事實(shí)新聞相關(guān)，而且觀點(diǎn)很獨(dú)到，也很犀利。我們?nèi)斯な占锁P凰博客中涉及財(cái)經(jīng)、文化、歷史、軍事、娛樂、科技、情感、生活等方面內(nèi)容的100篇文章，其中包含了4 891條評論。根據(jù)本文提出的方法，我們設(shè)計(jì)了兩組實(shí)驗(yàn)，第一組用于確定HITS二分圖中邊存在的條件閾值α的取值，第二組用于評測本文提出的文摘方法。

5.1 評論過濾閾值設(shè)定實(shí)驗(yàn)

我們從鳳凰博客數(shù)據(jù)集中隨機(jī)抽取20篇文章，對抽取的文章相對應(yīng)的評論進(jìn)行人工標(biāo)注，將評論標(biāo)注為噪聲評論及非噪聲評論，并使用查全率、查準(zhǔn)率和F值來評測過濾效果。

(10)

(11)

(12)

對每條評論，我們計(jì)算其與正文中每個(gè)句子的相似度，并保留其中的最大值。同時(shí)我們將α的取值范圍限定在區(qū)間(0,0.3)上并以0.05為步長對α進(jìn)行掃描(實(shí)驗(yàn)證明當(dāng)α取值大于0.3時(shí)，過濾效果并不理想)。實(shí)驗(yàn)觀測到的α對查全率、查準(zhǔn)率以及F值的影響如表1。

表1 不同α值對應(yīng)的查全率、查準(zhǔn)率和F值

閾值α的設(shè)定要在能過濾掉噪聲評論的同時(shí)，保證非噪聲評論的錯(cuò)誤過濾最少，這樣在具體的閾值設(shè)定時(shí)，相對于查全率我們更注重查準(zhǔn)率，F(xiàn)值中的系數(shù)w本文取3。由表1可知當(dāng)α取0.15時(shí)，F(xiàn)取最大值0.877 3，查準(zhǔn)率為0.938 6，查全率也達(dá)到了一個(gè)較高值0.733 6，于是我們將α設(shè)定為0.15。

5.2 文摘算法實(shí)驗(yàn)

文摘算法試驗(yàn)中，我們從鳳凰博客數(shù)據(jù)集中抽取三次，每次隨機(jī)抽取30篇文章，平均每篇文章包含50到60篇相對應(yīng)的評論。實(shí)驗(yàn)設(shè)定兩個(gè)Baseline，其中Baseline1按照正文句子與正文文檔的余弦相似度抽取摘要句子，此方法不考慮評論信息僅使用句子與文檔之間的相似關(guān)系得到文摘；Baseline2使用Hu等人設(shè)計(jì)的Blog摘要算法[5]，此方法使用評論間的引用、提及和相關(guān)三種評論間的關(guān)系得到評論分?jǐn)?shù)，再結(jié)合正文得到文摘。本文設(shè)定了20%和30%兩種文章摘要壓縮比，我們選擇了3名志愿者對選取的文章進(jìn)行人工摘要，作為實(shí)驗(yàn)的專家摘要(ground truth)。

本文采用ROUGE值[13]對摘要算法進(jìn)行評測。ROUGE是對文摘質(zhì)量進(jìn)行評測時(shí)廣泛使用的測度，該測度通過統(tǒng)計(jì)n-gram、詞語序列以及詞組等文本單元在算法生成摘要和專家摘要之間的共現(xiàn)信息，對文摘方法進(jìn)行評測。ROUGE-N的計(jì)算方式如下：

ROUGE-N

(13)

其中n表示n-gram的長度，Count(n-gram)為專家摘要中的出現(xiàn)的n-gram數(shù)，Countmatch(n-gram)為算法生成的候選摘要與專家摘要中共現(xiàn)的n-gram數(shù)。ROUGE工具在評測時(shí)提供了多種評測值，其中ROUGE-1和ROUGE-2這兩種評測值的評測性能在多個(gè)測度上均優(yōu)于其他評測值[14]，因此本文采用ROUGE-1和ROUGE-2進(jìn)行評測，結(jié)果如表2所示。

表2 壓縮比為20%和30%的實(shí)驗(yàn)結(jié)果

由表2可知，在20%和30%兩個(gè)壓縮比上，相對于兩個(gè)Baseline本文提出的方法在ROUGE-1和ROUGE-2上的評分均為最優(yōu)值。其中Baseline2與本文方法均優(yōu)于Baseline1，說明Blog評論信息在提取Blog正文信息時(shí)起了比較大的作用。本文方法優(yōu)于Baseline2，這是由于Baseline2在處理評論信息時(shí)未考慮評論內(nèi)容與評論者信息對文摘的影響，而僅使用評論間的引用提及與相關(guān)關(guān)系無法較好的挖掘出評論的重要性信息。

6 結(jié)論與下一步的工作

本文提出了一種面向Blog的文摘方法。本方法通過分析Blog評論的特點(diǎn)，采用了適合Blog評論的一些特征，使用HITS算法模型結(jié)合單篇blog文章正文與評論的相關(guān)信息得到文摘句子。實(shí)驗(yàn)效果表明在處理Blog文章時(shí)，本文方法在20%和30%兩個(gè)壓縮比上的ROUGE值相對已有的方法均有較好的提升。

在下一步工作中，我們將對單個(gè)Blog中不同主題下的Blog文章進(jìn)行聚類，結(jié)合同類別Blog文章相應(yīng)的評論信息對同一主題下的多個(gè)Blog文章進(jìn)行研究，提出相應(yīng)的面向Blog的多文檔摘要方法。

[1] Li J, Sun L, Kit C,et al. A query-focused multi-document summarizer based on lexical chains[C]//Proc. of Document Understanding Conference. 2007.

[2] Wan X. Document-based HITS model for multi-document summarization[J]. Lecture Notes in Computer Science, 2008, 5351: 454-465.

[3] Radev D, Jing H, Sty? M, et al. Centroid-based summarization of multiple documents[J]. Information Processing and Management, 2004, 40(6):919-938.

[4] 秦兵，劉挺，李生. 多文檔自動文摘綜述[J]. 中文信息學(xué)報(bào)，2005，19(6)： 13-20.

[5] Hu M, Sun A, Lim E. Comments-oriented document summarization: understanding documents with readers’ feedback [C]//Proc of SIGIR’08, NY USA: ACM, 2008: 291-298.

[6] Brunn M., Y. Chali, C.J. Pinchak. Text summarization using lexical chains[C]//the Proceedings of the Document Understanding Conference (DUC-2001) 2001:135-140.

[7] Wan X, Yang J. Multi-document summarization using cluster-based link analysis[C]//Proc of SIGIR’08, NY USA: ACM, 2008: 299-306.

[8] Wang D, Li T, Zhu S, Ding C. Multi-document summarization via sentence-level semantic analysis and symmetric matrix factorization[C]//Proc. of SIGIR’08, NY USA: ACM, 2008. 307-314.

[9] Zhou L, Hovy E. On the summarization of dynamically introduced information: Online discussions and blogs[C]//Proc. of AAAI’06 Spring Symposium on Computational Approaches to Analyzing Weblogs, Stanford, California: AAAI, 2006: 237-242.

[10] 楊宇航，趙鐵軍，于浩，等. Blog研究綜述[J]. 軟件學(xué)報(bào)，2008，19(4)： 902-9l4.

[11] Mishne G, Glance N. Leave a Rep1y: An analysis of weblog comments[C]//3rd Annual workshop on the Web1ogging Ecosystem. Edinburgh, UK, 2006.

[12] Hsu C, Khabiri E, J Caverlee. Ranking comments on the social web[C]//Proc of CSE’09, Washington, DC, USA: IEEE Computer Society, 2009.90-97.

[13] Lin C. ROUGE: A package for automatic evaluation of summaries[C]//Workshop on Text Summarization Branches Out, Spain: Association for Computational Linguistics, 2004: 74-81.

[14] Lin C, Hovy E. Automatic evaluation of summaries using n-gram co-occurrence statistics [C]//Proceedings of 2003 Language Technology Conference (HLT-NAACL2003),Edmonton,CA:Association for Computational Linguistics Morristown, 2003:71-78.