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

師 昕, 趙雪青

?

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

師 昕, 趙雪青

(西安工程大學計算機學院, 西安 710048)

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

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

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

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

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

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

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

1 算法描述

1.1 變量定義

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

1.2 評論相似性

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

抽取關鍵字: 關鍵字選擇在聚類中是非常重要的一步, 不同的關鍵字常常會導致不同的聚類結果. 在本文設計的系統中, 隨著評論數量的上升, 評論詞語的數量也在增多, 而使用所有詞語作為關鍵字會導致數據量非常大, 非常耗費空間和時間. 因此, 為了減少數據量, 我們選用在一個評論文件中出現過四次以上的詞語作為關鍵字.

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

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

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

1.3 評論聚類

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

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

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

1.4 聚類內評論排序

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

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

1234 10101 21010 30100 41000

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

代表衰減系數, 本試驗中將其設為0.15, |c|表示與一篇新聞相關的評論數量,代表評論圖中評論C到C的邊值.

在本系統中, 我們依據公式(2)計算出的分數來對每個聚類中的評論進行排名, 并取分數最高的幾個評論.

1.5 聚類間評論排序

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

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

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

令為2.4中選出的評論集;

令為候選的評論向量.

某一條評論的分數由公式(3)確定.

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

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

2 仿真實驗及結果

2.1 仿真實驗數據庫

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

2.2 實驗結果

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

表1 評論聚類結果

表2 評論摘要

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

2.3 數據對比

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

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

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

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

3 結論

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

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 榮秋生,顏君彪,郭國強.基于DBSCAN聚類算法的研究與實現.計算機應用,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]