新型的面向新聞評(píng)論摘要采集算法①

師 昕, 趙雪青

?

新型的面向新聞評(píng)論摘要采集算法①

師 昕, 趙雪青

(西安工程大學(xué)計(jì)算機(jī)學(xué)院, 西安 710048)

為了讓讀者可以更快地獲取所有新聞評(píng)論中最有代表性的觀點(diǎn), 提出一種新的新聞評(píng)論摘要采集算法, 并依此設(shè)計(jì)出評(píng)論摘要采集系統(tǒng). 該算法將有效地結(jié)合聚類算法和排序算法, 首先, 使用改進(jìn)的Borderflow算法對(duì)所有評(píng)論聚類; 其次, 采用類PageRank算法對(duì)聚類中的評(píng)論進(jìn)行排序, 選出排名最前的幾條評(píng)論; 最后, 利用MMR算法對(duì)PageRank算法選出的所有評(píng)論進(jìn)行再次排序, 并選取名次最高的K條評(píng)論作為評(píng)論摘要. 通過仿真實(shí)驗(yàn)得到的NDCG和MAP數(shù)據(jù)表明, 使用本文算法得到的評(píng)論摘要具有更好的有效性和準(zhǔn)確性, 更符合讀者直觀感覺.

評(píng)論摘要; BorderFlow算法; PageRank算法; MMR算法

隨著web2.0技術(shù)的發(fā)展, 在閱讀新聞后, 讀者可以隨意地在網(wǎng)頁(yè)新聞文章后留下自己的評(píng)論并閱讀他人留下的評(píng)論, 以此獲得不同的觀點(diǎn)和信息. 這也成為讀者表達(dá)自己觀點(diǎn)的途徑之一, 這些評(píng)論中有一些是非常有見地的, 而且不僅僅表達(dá)了讀者的觀點(diǎn), 有時(shí)也會(huì)包含一些時(shí)下熱門話題的信息和討論, 因此讀者十分熱衷于閱讀帶有評(píng)論的新聞文章. 根據(jù)文獻(xiàn)[1]中所做的用戶調(diào)查, 讀者閱讀的新聞評(píng)論, 有可能影響甚至改變他們的觀點(diǎn)或看法.

但是, 在線新聞文章的評(píng)論數(shù)量, 特別是在那些比較大的網(wǎng)站中, 是非常龐大且實(shí)時(shí)增長(zhǎng)的. 根據(jù)調(diào)查, 雅虎新聞頁(yè)面每篇新聞的平均評(píng)論數(shù)量為1059條, 而這些評(píng)論中有很大一部分是沒有意義或者重復(fù)的, 這就導(dǎo)致讀者要想閱讀完所有的評(píng)論會(huì)花費(fèi)很多時(shí)間在沒有意義的內(nèi)容上. 因此, 如何幫助讀者在短時(shí)間內(nèi)更有效地從大量評(píng)論中獲取有用的信息就成為一項(xiàng)研究熱點(diǎn).

近年來, 提出了一些針對(duì)減輕讀者閱讀負(fù)擔(dān)的評(píng)論向?qū)Х椒? 一類是依賴網(wǎng)站讀者的評(píng)分系統(tǒng), 比如豆瓣網(wǎng)允許讀者對(duì)所有評(píng)論評(píng)分并將得分最高的評(píng)論顯示在最前面. 這種系統(tǒng)需要大量的讀者參與, 而且由于每個(gè)人的觀點(diǎn)都不盡相同, 因此最終的結(jié)論可能并不具代表性; 另一類方法是系統(tǒng)自動(dòng)生成最熱門的關(guān)鍵字, 比如CSDN網(wǎng)站使用一系列標(biāo)簽來引導(dǎo)讀者, 盡管這種方法可以生成比較具有代表性的關(guān)鍵字, 但是由于關(guān)鍵字本身缺少足夠的文本信息, 讀者很難從抽象的關(guān)鍵字中獲得對(duì)整個(gè)評(píng)論的詳盡理解.

目前, 將聚集算法和排序算法結(jié)合的評(píng)論摘要采集系統(tǒng)具有明顯優(yōu)勢(shì), 該領(lǐng)域內(nèi)有許多學(xué)者在進(jìn)行研究, 如文獻(xiàn)[2]和文獻(xiàn)[3], 且該方法被證明是非常有效的. 因此, 本文旨在尋找一種可以幫助讀者快速得到所有評(píng)論中具有代表性信息的方法, 提出了一個(gè)新的針對(duì)新聞評(píng)論的摘要采集系統(tǒng).

為了從大量的評(píng)論中很快得到最有代表性的評(píng)論, 以便訪客可以在較短時(shí)間內(nèi)得到最有效的信息, 考慮到訪客評(píng)論觀點(diǎn)種類的多樣性, 使用聚集算法可以將最相似的評(píng)論聚集成類, 這樣就可以認(rèn)為同一個(gè)類的評(píng)論代表一個(gè)主題. 文中提出的針對(duì)新聞評(píng)論的摘要采集算法, 選取一篇文章及其所有評(píng)論并最終顯示出最有代表性的K條評(píng)論作為評(píng)論摘要. 首先, 該系統(tǒng)對(duì)所有評(píng)論使用BorderFlow聚集算法[4], 根據(jù)余弦相似度把它們分別聚集為類; 其次, 使用PageRank算法[5]對(duì)每一類中的所有評(píng)論進(jìn)行排名, 選出最有代表性的N條評(píng)論; 最后, 使用MMR算法[6]對(duì)每一類中選出的代表性評(píng)論再進(jìn)行排名, 并最終選出若干條最有代表性的K條評(píng)論, 并將這些評(píng)論作為這篇文章的評(píng)論摘要. 由于聚集算法的使用, 每一類中的評(píng)論可以代表一種相近的觀點(diǎn), 因此最終選出的K條評(píng)論可以近似代表評(píng)論中不同的K種觀點(diǎn).

1 算法描述

1.1 變量定義

根據(jù)給出的數(shù)據(jù)庫(kù), 我們定義為數(shù)據(jù)庫(kù)中所有新聞文章的集合,{}. 每一篇新聞文章中的評(píng)論集合定義為,{}. 那么就代表新聞集合中的所有評(píng)論(即是的集合). 本文提出方法的目標(biāo), 則是提取出一個(gè)集合的子集{}, 這個(gè)集合包含有個(gè)最具有代表性的評(píng)論, 也即是新聞文章的評(píng)論摘要, 其中是由用戶設(shè)定的變量.

1.2 評(píng)論相似性

本文中介紹的算法中的第一步是對(duì)所有評(píng)論根據(jù)內(nèi)容相似度聚類, 其中最直接的方法是計(jì)算基于評(píng)論向量的余弦相似度. 為了得到評(píng)論向量, 首先需要抽取關(guān)鍵字并計(jì)算其特征值.

抽取關(guān)鍵字: 關(guān)鍵字選擇在聚類中是非常重要的一步, 不同的關(guān)鍵字常常會(huì)導(dǎo)致不同的聚類結(jié)果. 在本文設(shè)計(jì)的系統(tǒng)中, 隨著評(píng)論數(shù)量的上升, 評(píng)論詞語(yǔ)的數(shù)量也在增多, 而使用所有詞語(yǔ)作為關(guān)鍵字會(huì)導(dǎo)致數(shù)據(jù)量非常大, 非常耗費(fèi)空間和時(shí)間. 因此, 為了減少數(shù)據(jù)量, 我們選用在一個(gè)評(píng)論文件中出現(xiàn)過四次以上的詞語(yǔ)作為關(guān)鍵字.

計(jì)算特征值: TD-IDF加權(quán)法[7]是最常用的計(jì)算評(píng)論向量特征值的方法. 該方法僅考慮了一條評(píng)論中關(guān)鍵字的信息, 但是事實(shí)上, 出自于同一個(gè)新聞資源的新聞和評(píng)論之間, 互相是有聯(lián)系的, 它們有可能討論同一個(gè)話題, 因此使用TD-IDF加權(quán)法就會(huì)忽視掉它們之間的聯(lián)系. 此外, 在評(píng)論數(shù)量非常大的情況下, 單條評(píng)論的長(zhǎng)度可能會(huì)非常短, 因此使用TF-IDF加權(quán)法計(jì)算每條評(píng)論的評(píng)論向量并不是很合適.

基于以上考慮, 本文提出一種新的加權(quán)法CF-ICF來計(jì)算評(píng)論向量. 給出一個(gè)評(píng)論中的單詞, CF指該單詞在本篇文章的所有評(píng)論集合中出現(xiàn)的次數(shù), ICF指在所有文章的評(píng)論集合中該單詞的反轉(zhuǎn)頻率. 根據(jù)該方法, 如果單詞在集合中出現(xiàn)了很多次, 那么就說明它對(duì)當(dāng)前文章很重要; 如果單詞僅在集合中出現(xiàn)了很多次, 那么就說明它對(duì)當(dāng)前文章并不是很重要. 因此單詞的特征值就依據(jù)其在中的詞頻和在中的反轉(zhuǎn)頻率計(jì)算, 其定義如公式(1).

其中,()代表在中出現(xiàn)的次數(shù),代表所有關(guān)鍵字在中出現(xiàn)的總次數(shù),代表所有包含關(guān)鍵字的集合,代表新聞集合中的所有評(píng)論數(shù)量.

1.3 評(píng)論聚類

用于評(píng)論聚類的算法有許多種, 如基于密度的DBSCAN算法[8], 基于分割的k-means算法[9], 基于連通性的分層算法[10]等等. 本文使用基于局部圖的BorderFlow算法, 該算法使用兩條評(píng)論間的余弦相似度作為連接邊的權(quán)重. 這樣屬于同一類的評(píng)論會(huì)有更相近的距離和更多的聯(lián)系從而完成評(píng)論的聚類. 本文中選取評(píng)論數(shù)量最多的三個(gè)聚類作為代表性評(píng)論. 在文獻(xiàn)[4]中證明了BorderFlow算法可以達(dá)到更好的聚類效果和更有效地聚類純度.

在BorderFlow算法應(yīng)用的過程中注意到, 有一些評(píng)論非常短, 或者不具有代表性, 這樣的評(píng)論產(chǎn)生的聚類也會(huì)非常小, 無法代表熱議的話題. 因此本文在BorderFlow算法的基礎(chǔ)上忽略這種聚類.

此外, BorderFlow算法有時(shí)會(huì)返回重疊的聚類. 為了克服這個(gè)問題, 本文使用一種超強(qiáng)化策略. 令()代表一張圖表, 其中代表一組評(píng)論的序號(hào);代表評(píng)論間的連接邊;代表連接邊的權(quán)重, 即兩個(gè)評(píng)論間的余弦相似度. 使用BorderFlow算法, 可以得到一組類{},,代表一組評(píng)論. 但是可能. 而在使用過超強(qiáng)化策略后, 就將個(gè)評(píng)論集合轉(zhuǎn)變成’個(gè)評(píng)論集合, 并且.

1.4 聚類內(nèi)評(píng)論排序

在完成評(píng)論的聚類后, 本文使用類PageRank算法在每個(gè)類中對(duì)評(píng)論進(jìn)行排名, 并選出最有代表性的評(píng)論. PageRank是Google網(wǎng)頁(yè)搜索引擎研發(fā)的一款基于網(wǎng)絡(luò)圖的網(wǎng)頁(yè)排名分析算法. 在本文中, 我們使用了基于評(píng)論圖的類PageRank算法對(duì)評(píng)論進(jìn)行排名, 以數(shù)據(jù)庫(kù)中的評(píng)論作為節(jié)點(diǎn), 評(píng)論間的余弦相似度作為連接邊.

獲取評(píng)論圖: 評(píng)論代表了讀者的觀點(diǎn)和反饋, 而不同讀者的觀點(diǎn)有可能是相似的, 因此評(píng)論間應(yīng)該存在某種聯(lián)系. 考慮到同一個(gè)聚類中的評(píng)論互相聯(lián)系最緊密, 它們間一定有共同的內(nèi)容. 我們定義如果兩個(gè)評(píng)論的余弦相似度大于一個(gè)值(是一個(gè)預(yù)設(shè)值, 如0.5), 則兩個(gè)評(píng)論間存在聯(lián)系, 這樣兩個(gè)評(píng)論間的聯(lián)系是雙向的. 圖1中給出的評(píng)論圖中, 評(píng)論1和2,2和3,1和4間是存在聯(lián)系的, 對(duì)于余弦相似度大于的, 在評(píng)論圖中設(shè)為1, 代表兩個(gè)評(píng)論間有聯(lián)系; 小于的設(shè)為0, 代表兩個(gè)評(píng)論間無聯(lián)系.

1234 10101 21010 30100 41000

PageRank算法: 根據(jù)評(píng)論圖, 我們使用PageRank算法對(duì)評(píng)論評(píng)分, 如公式(2)中定義.

代表衰減系數(shù), 本試驗(yàn)中將其設(shè)為0.15, |c|表示與一篇新聞相關(guān)的評(píng)論數(shù)量,代表評(píng)論圖中評(píng)論C到C的邊值.

在本系統(tǒng)中, 我們依據(jù)公式(2)計(jì)算出的分?jǐn)?shù)來對(duì)每個(gè)聚類中的評(píng)論進(jìn)行排名, 并取分?jǐn)?shù)最高的幾個(gè)評(píng)論.

1.5 聚類間評(píng)論排序

在使用了PageRank算法完成了每個(gè)聚類中的評(píng)論排名后, 就可以獲得每個(gè)類中最具代表性的K個(gè)評(píng)論, 并且這些評(píng)論代表的是同一個(gè)討論話題. 接下來, 要對(duì)每個(gè)類間的評(píng)論再次進(jìn)行排序, 以獲得所有話題中最具有代表性的評(píng)論, 并最終生成評(píng)論摘要.

這一步我們使用MMR算法, 這是一種在盡量保持查詢相關(guān)性和減少冗余的前提下, 重新確定文檔序值并最選取最有代表性的幾條句子的方法. 本文中, MMR算法被如下定義:

令為新聞文章的查詢向量;

令為2.4中選出的評(píng)論集;

令為候選的評(píng)論向量.

某一條評(píng)論的分?jǐn)?shù)由公式(3)確定.

在公式(3)中, 當(dāng)λ設(shè)為1時(shí), 計(jì)算的是C和Cq間的最大關(guān)聯(lián)性; 當(dāng)λ設(shè)為0時(shí), 計(jì)算的是C和Cs間的最大差異性. 在本文中, sim(c1, c2)函數(shù)是根據(jù)每個(gè)向量集合C的余弦相似度計(jì)算的, 且λ被設(shè)為0.8.

將1.4中的所有備選評(píng)論用該MMR算法計(jì)算評(píng)分后, 再進(jìn)行排名, 就可以得到所有討論話題中最具有代表性的評(píng)論, 并可以據(jù)此生成評(píng)論摘要.

2 仿真實(shí)驗(yàn)及結(jié)果

2.1 仿真實(shí)驗(yàn)數(shù)據(jù)庫(kù)

本實(shí)驗(yàn)中用的數(shù)據(jù)庫(kù)是從雅虎新聞網(wǎng)上摘取出的1000多條新聞及其評(píng)論集合, 其中每條新聞平均有1059條評(píng)論, 整個(gè)數(shù)據(jù)庫(kù)約有100萬(wàn)條評(píng)論. 此外, 整個(gè)數(shù)據(jù)集合中包含有四個(gè)的文件夾, 分別為News, newsTXT, Comments, commentsTXT, 每個(gè)文件夾中相同文件名的文件是互相關(guān)聯(lián)的. 其中News文件夾中包含HTML格式的新聞文章, Comments文件夾中包含HTML格式的對(duì)應(yīng)文章評(píng)論, newsTXT和commentsTXT文件夾中則包含新聞文章和評(píng)論的TXT格式文件.

2.2 實(shí)驗(yàn)結(jié)果

選擇數(shù)據(jù)庫(kù)中一篇名為“Magnitude 3.8 earthquake shakes Southern California, no damage reported”的文章作為測(cè)試, 該文章共有108條評(píng)論. 最終的聚類結(jié)果如表1所示, 表2顯示的是系統(tǒng)自動(dòng)選出的10條評(píng)論摘要.

表1 評(píng)論聚類結(jié)果

表2 評(píng)論摘要

從表2中可以看出, 選出的10條評(píng)論摘要基本可以代表讀者不同的觀點(diǎn).

2.3 數(shù)據(jù)對(duì)比

考慮到我們所提出的方法核心是對(duì)評(píng)論聚類, 然后對(duì)聚類中選出來的評(píng)論先進(jìn)行聚類內(nèi)排序, 再進(jìn)行聚類間排名. 這種方法對(duì)評(píng)論需要進(jìn)行兩次排序, 這樣做是否有意義? 從理論上進(jìn)行分析, 根據(jù)BorderFlow算法得到的評(píng)論數(shù)量最多的三個(gè)聚類中, 如果任意從中選取幾條評(píng)論作為該聚類的代表進(jìn)行聚類間排序, 則很有可能因?yàn)樵撛u(píng)論在聚類內(nèi)部的代表性不足而導(dǎo)致整個(gè)聚類在參與類間排序時(shí)無法得到準(zhǔn)確的結(jié)果. 而使用本文中的算法. 先對(duì)每個(gè)聚類內(nèi)部的評(píng)論進(jìn)行排序, 得到最有代表性的幾條評(píng)論, 再用這些評(píng)論進(jìn)行聚類間排序, 則可以保證每個(gè)聚類的排名不會(huì)因?yàn)槠鋬?nèi)部評(píng)論的代表性而受到影響.

為了進(jìn)行實(shí)驗(yàn)驗(yàn)證, 我們采取了另外一種方法, 即僅適用MMR算法對(duì)所有評(píng)論進(jìn)行排序. 這兩種方法, 我們首先選取20名志愿者, 讓他們依據(jù)評(píng)論是否具有代表性對(duì)選出的評(píng)論摘要進(jìn)行從1到5的打分, 5分代表所有志愿者都認(rèn)為該評(píng)論摘要非常有代表性, 1分代表所有志愿者都認(rèn)為該評(píng)論摘要沒有代表性. 其次再根據(jù)志愿者的打分情況, 使用NDCG和MAP兩種評(píng)價(jià)方法分別對(duì)兩種算法生成的4條、6條、8條、10條評(píng)論摘要進(jìn)行數(shù)據(jù)有效性分析. NDCG(normalized DCG)和MAP(Mean Average Precision)是最常用的評(píng)價(jià)排名的指標(biāo), 在本文中這兩個(gè)指標(biāo)用來衡量志愿者排名和系統(tǒng)生成排名之間的相關(guān)度, 數(shù)值越高代表與志愿者的排名結(jié)果越接近. 實(shí)驗(yàn)中的數(shù)據(jù)是對(duì)數(shù)據(jù)庫(kù)中任意選出的50條新聞的評(píng)論進(jìn)行摘要采集, 并取其平均值得到. 結(jié)論如表3.

表3 本文算法和MMR算法的NDCG、MAP值對(duì)比

根據(jù)表3可以看出, 本文提出的算法其NDCG值和MAP值均高于僅使用MMR的算法, 說明本文提出的對(duì)評(píng)論進(jìn)行兩次排名可以提取出符合讀者直觀感受的更有代表性的評(píng)論, 實(shí)驗(yàn)結(jié)果表明本文提出的算法有效性和準(zhǔn)確性更高.

3 結(jié)論

本文提出一種面向新聞評(píng)論的摘要采集算法. 首先對(duì)所有評(píng)論進(jìn)行聚類, 為此我們?cè)O(shè)計(jì)了一個(gè)新的CF-ICF算法來獲取評(píng)論向量; 另外為了避免BorderFlow算法出現(xiàn)的類間重疊, 文中對(duì)其進(jìn)行改進(jìn), 加入了一種超強(qiáng)化策略; 其次, 使用基于評(píng)論圖的類PageRank算法對(duì)每個(gè)聚類中的評(píng)論進(jìn)行排名, 選出最有代表性的幾條評(píng)論作為每個(gè)熱點(diǎn)話題的代表; 最后, 對(duì)上一步選出的所有評(píng)論使用MMR算法進(jìn)行再次排序, 選擇出名次最高的K條評(píng)論作為最終的評(píng)論摘要. 仿真實(shí)驗(yàn)表明, 文中提出的算法能夠代表評(píng)論者不同的觀點(diǎn), 相比于僅使用MMR算法進(jìn)行排序的系統(tǒng), 本文提出的兩次排序可以提供更好的有效性和準(zhǔn)確性, 更符合讀者直觀感受.

1 Hu M, Sun A, Lim EP. Comments-oriented document summarization: Understanding documents with readers’ feedback. Proc. of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM. 2008. 291–298.

2 Ma Z, Sun A, Yuan Q, et al. Topic-driven reader comments summarization. Proc. of the 21st ACM International Conference on Information and Knowledge Management. ACM. 2012. 265–274.

3 Khabiri E, Caverlee J, Hsu CF. Summarizing user-contributed comments. Fifth International AAAI Conference on Weblogs and Social Media. 2011.

4 Ngomo ACN, Schumacher F. BorderFlow: A local graph clustering algorithm for natural language processing. Lecture Notes in Computer Science, 1970, 5449: 547–558.

5 Page L. The PageRank citation ranking: Bringing order to the web. Stanford InfoLab. 1999: 1–14.

6 Goldstein J, Carbonell J. Summarization: (1) using MMR for diversity - based reranking and (2) evaluating summaries. Proc. of a Workshop on Held at Baltimore. Association for Computational Linguistics. Maryland. 1998. 181–195.

7 Salton G, Buckley C. Term-weighting approaches in automatic text retrieval. Information Processing & Management an International Journal, 1988, 24(5): 513–523.

8 榮秋生,顏君彪,郭國(guó)強(qiáng).基于DBSCAN聚類算法的研究與實(shí)現(xiàn).計(jì)算機(jī)應(yīng)用,2004,24(4):45–46.

9 Hartigan JA, Wong MA. Algorithm AS 136: A k-means clustering algorithm. Applied Statistics, 1979, 28(1): 100–108.

10 Johnson SC. Hierarchial clustering schemes. Psychometrika, 1967, 32(3): 241–248.

Novel News Article Comments Summarization Algorithm of Computer Engineering and Applications

SHI Xin, ZHAO Xue-Qing

(Department of Computer Science, Xi’an Polytechnic University, Xi’an 710032, China)

In order to make the readers get the most informative and representative opinions efficiently among the news comments, this paper proposes a novel news article comments summarization algorithm and then designs an article summarization system, which combines the clustering algorithm with the ranking algorithm. First, it groups comments using the modified BorderFlow clustering algorithm. Second, for each group, it uses the similar PageRank algorithm to score and rank comments, and selects top comments in each cluster as representation. At last, it ranks the selected comments by MMR algorithm and displays the top-K comments as the comments summarization. According to the experimental statics of NDCG and MAP data, the proposed method meets the intuitive sense of readers more. Meanwhile, it shows the better effectiveness and accuracy theoretically.

comments summarization; BorderFlow algorithm; PageRank algorithm; MMR algorithm

2016-04-12;收到修改稿時(shí)間:2016-05-19

[10.15888/j.cnki.csa.005530]