師 昕, 趙雪青

?

新型的面向新聞評論摘要采集算法①

師 昕, 趙雪青

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

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

評論摘要; BorderFlow算法; PageRank算法; MMR算法

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

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

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

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

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

1 算法描述

1.1 變量定義

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

1.2 評論相似性

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

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

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

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

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

1.3 評論聚類

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

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

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

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

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

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

1234 10101 21010 30100 41000

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

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

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

1.5 聚類間評論排序

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

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

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

令為2.4中選出的評論集;

令為候選的評論向量.

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

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

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

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

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

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

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

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

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

表2 評論摘要

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

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

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

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

表3 本文算法和MMR算法的NDCG、MAP值對比

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

3 結(jié)論

本文提出一種面向新聞評論的摘要采集算法. 首先對所有評論進(jìn)行聚類, 為此我們設(shè)計了一個新的CF-ICF算法來獲取評論向量; 另外為了避免BorderFlow算法出現(xiàn)的類間重疊, 文中對其進(jìn)行改進(jìn), 加入了一種超強(qiáng)化策略; 其次, 使用基于評論圖的類PageRank算法對每個聚類中的評論進(jìn)行排名, 選出最有代表性的幾條評論作為每個熱點(diǎn)話題的代表; 最后, 對上一步選出的所有評論使用MMR算法進(jìn)行再次排序, 選擇出名次最高的K條評論作為最終的評論摘要. 仿真實(shí)驗(yàn)表明, 文中提出的算法能夠代表評論者不同的觀點(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 榮秋生,顏君彪,郭國強(qiáng).基于DBSCAN聚類算法的研究與實(shí)現(xiàn).計算機(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;收到修改稿時間:2016-05-19

[10.15888/j.cnki.csa.005530]