官賽萍,靳小龍,徐學可,伍大勇,賈巖濤,王元卓,劉 悅

(1. 中國科學院計算技術研究所 中國科學院網(wǎng)絡數(shù)據(jù)科學與技術重點實驗室，北京 100190；2. 中國科學院大學 計算機與控制學院，北京 100049)

基于WMD距離與近鄰傳播的新聞評論聚類

官賽萍1,2,靳小龍1,2,徐學可1,2,伍大勇1,2,賈巖濤1,2,王元卓1,2,劉 悅1,2

(1. 中國科學院計算技術研究所 中國科學院網(wǎng)絡數(shù)據(jù)科學與技術重點實驗室，北京 100190；2. 中國科學院大學 計算機與控制學院，北京 100049)

隨著新聞網(wǎng)站的快速發(fā)展，網(wǎng)絡新聞和評論數(shù)據(jù)激增，給人們帶來了大量有價值的信息。新聞讓人們了解發(fā)生在國內(nèi)外的時事，而評論則體現(xiàn)了人們對事件的觀點和看法，這對輿情分析和新聞評論推薦等應用很重要。然而，新聞評論數(shù)據(jù)又多又雜,而且通常比較簡短，因此難以快速直觀地從中發(fā)現(xiàn)評論者的關注點所在。為此，該文提出一種面向新聞評論的聚類方法EWMD-AP，用以自動挖掘社會大眾對事件的關注點。該方法利用強化了權重向量的Word Mover’s Distance(WMD)計算評論之間的距離，進而用Affinity Propagation(AP)對評論進行聚類，從雜亂的新聞評論中得到關注點簇及其代表性評論。特別地，該文提出利用強化權重向量替代傳統(tǒng)WMD中的詞頻權重向量。而強化權重由三部分組成，包括結合詞性特征與文本表達特征的詞重要度系數(shù)、新聞正文作為評論背景的去背景化系數(shù)和TFIDF系數(shù)。在24個新聞評論數(shù)據(jù)集上的對比實驗表明，EWMD-AP相比Kmeans和Mean Shift等傳統(tǒng)聚類算法以及Density Peaks等當前最新算法都具有更好的新聞評論聚類效果。

新聞評論聚類；強化權重向量；去背景化；Word Mover’s Distance；近鄰傳播

1 引言

互聯(lián)網(wǎng)的快速發(fā)展使得各個領域的網(wǎng)絡信息和用戶評論迅速增長。用戶評論中蘊含大量用戶的看法和觀點，這對各個領域來說都是很有價值的信息。譬如，對服務行業(yè)來說，用戶評論既是用戶做決策的重要參考，又是商家提升服務質(zhì)量和用戶體驗的重要依據(jù)。對社交網(wǎng)絡來說，用戶評論可以用于代表性評論選擇、話題檢測和觀點抽取等；對新聞來說，對用戶評論的分析既可以讓有關機構了解人們對新聞主體的關注點所在，又可以優(yōu)化新聞推薦，針對特色需求，進行個性化推薦。因此，從大量評論數(shù)據(jù)中挖掘上述信息具有重要的研究意義和應用價值。近年來，服務行業(yè)網(wǎng)站(如購物網(wǎng)站、酒店等)與社交網(wǎng)絡的評論等已受到廣泛關注。

對于服務行業(yè)的評論，Hai等[1]提出聯(lián)合屬性和情感的有監(jiān)督模型，在商品級和細粒度的商品屬性級選擇最有用的評論，這有助于顧客做出購買決策，同時有助于商家提升商品質(zhì)量和服務。Dayan等[2]提出一種基于文本評論抽取特性信息的方法。該方法采用權重機制進行兩輪迭代： 第一輪將提供相似食物類別的酒店聚在一起，第二輪在此基礎上去除簇中的共同項，找出各酒店的特性，發(fā)現(xiàn)酒店之間有意思的關聯(lián)。酒店評論網(wǎng)站可以根據(jù)這些特性提供個性化服務。Zhou等[3]提出一種表達學習方法，通過詞向量上的神經(jīng)網(wǎng)絡得到深層和混合的特征，識別給定酒店評論討論的主題，包括環(huán)境、食物、價格等。

對于社交網(wǎng)絡的評論，Nguyen等[4-5]利用詳細冗長的全文本評論和簡短集中的微博評論尋找有效覆蓋微博評論的全文本評論子集。整個過程包含兩步： 第一步匹配全文本評論句子和微博評論，第二步選擇覆蓋盡可能多的微博評論，以及句子數(shù)少的全文本評論子集。Chong等[6]設計了一個話題模型SAMR(sparse additive micro-review)，發(fā)現(xiàn)地點相關的微博評論話題，最終得到意想不到的微博評論，幫助業(yè)主進行事件發(fā)現(xiàn)、管理顧客關系、提升服務和識別競爭對象等。Lu等[7]提出基于LDA(latent dirichlet allocation)的概率模型，從用戶到新地點的微博評論中抽取話題，進而在幫助其他用戶做決策的同時，還能幫助業(yè)主個性化用戶體驗。

盡管目前已有大量針對服務行業(yè)網(wǎng)站和社交網(wǎng)絡評論的研究，但還沒有針對新聞評論的研究工作。而相比于服務行業(yè)評論，社交網(wǎng)絡評論和新聞評論更加多元化。服務行業(yè)評論關注質(zhì)量、價格、服務等相對比較有限的屬性，而社交網(wǎng)絡評論和新聞評論的關注點比較多樣化，數(shù)據(jù)本身也沒有明確的屬性特征。但新聞評論又不同于社交網(wǎng)絡評論，社交網(wǎng)絡存在明確的用戶關系(如朋友關系、關注關系等)，這些用戶關系在評論中常常有很好的體現(xiàn)。而在新聞評論中不存在顯式的用戶關系，所以文本信息成為最主要的分析依據(jù)。由于新聞評論具有自身的特點，所以現(xiàn)有針對服務行業(yè)網(wǎng)站與社交網(wǎng)絡評論進行聚類的方法，不適用于新聞評論的聚類。

對于新聞評論，在雜亂的文本信息中，識別評論的關注點，可以更便捷地了解評論者的意見，提取有價值的信息。因此本文提出一種面向新聞評論聚類的方法EWMD-AP。該方法基于強化權重的Word Mover’s Distance(WMD)[8]來計算評論之間的距離，用近鄰傳播(affinity propagation，AP)算法[9]對新聞評論進行聚類。其中，WMD距離通過計算從一個文檔表達到另一個文檔表達所需要的最小代價得到。本文利用詞性特征和文本表達特征制定規(guī)則得到詞的重要度系數(shù)，由新聞正文信息得到去背景化系數(shù)，再結合TFIDF系數(shù)組成強化權重向量，有效計算評論文本之間的距離。進一步，通過將距離轉(zhuǎn)化為相似度，再采用AP算法進行聚類最終得到評論關注點簇及各自的代表性評論。在人工標注的24個新聞評論數(shù)據(jù)集上的對比實驗表明，EWMD-AP相比Kmeans和Mean Shift等傳統(tǒng)聚類算法及Density Peaks等當前最新算法都具有更好的新聞評論聚類效果。

接下來本文將按以下展開，第二節(jié)描述本文的相關工作，第三節(jié)描述EWMD-AP方法，第四節(jié)展示實驗及評估結果，第五節(jié)對全文進行總結及展望。

2 相關工作

本文針對還沒有挖掘新聞評論關注點研究的現(xiàn)狀，對新聞評論關注點進行聚類，相關工作主要包括文本表達、文檔相似度計算和文檔聚類。

文本表達最直觀的是One-Hot詞向量，這種表達方式非常稀疏，不考慮語義信息，存在“語義鴻溝”問題。因此將語義信息融入文本表達成為關注重點。Harris提出分布假說： 上下文相似的詞，詞義相似[10]。Hinton提出分布式詞向量，引入詞間距離概念，相似的詞距離上更接近[11]。基于分布式表達的方法，從方法思路看發(fā)展為三類，基于聚類、基于統(tǒng)計信息和基于神經(jīng)網(wǎng)絡的分布式表達。目前這三類的代表性方法分別為： 布朗聚類、Global Vectors(Glove)和Word2vec。Brown等[12]提出布朗聚類，通過多層類別體系構建詞與上下文的關系，根據(jù)詞的公共類別層級判斷語義相似度。Pennington等[13]提出Glove，Glove是基于計數(shù)的模型，引入了全局統(tǒng)計信息，通過維規(guī)約詞共現(xiàn)矩陣，最小化重構誤差建模得到詞表達。Mikolov等[14-15]提出Word2vec，用一個淺層神經(jīng)網(wǎng)絡語言模型學習詞的向量表達。在大規(guī)模數(shù)據(jù)集上訓練的能力使得模型可以學習復雜的詞間關系。

文檔相似度計算基于詞的相似度或距離進行。田堃等[16]通過語義角色標注、語義角色分析、標注句型的相似匹配、標注句型間相似度計算等步驟，以動詞為分析核心，實現(xiàn)漢語句子的相似度計算。這一系列的步驟過于復雜，容易造成級聯(lián)誤差，即中間某個步驟的錯誤將傳遞到后續(xù)步驟，導致結果的嚴重錯誤。更直觀、簡單的方法是將文檔表達為向量，通過向量相似度計算方法得到文檔相似度。這種方法沒有考慮單個詞之間的語義相似度。如何通過詞間語義相似度有效計算文檔相似度？從模型結構看，目前代表性研究大致分為基于圖、基于神經(jīng)網(wǎng)絡和基于詞權重轉(zhuǎn)移三類。Wang等[17]提出KnowSim，表達文檔為類型異構信息網(wǎng)絡，將文檔相似度問題轉(zhuǎn)化為圖距離問題。該方法依賴外部實體、關系知識庫。詹志建和楊小平[18]提出構建短文本的復雜網(wǎng)絡模型，選取復雜網(wǎng)絡特征，將短文本建模為特征向量，基于詞語之間的相似度得到短文本之間的相似度。該方法容易受選取的特征的影響。Sun等[19]基于神經(jīng)網(wǎng)絡建立詞向量模型，通過特征詞的語義相似度計算文本語義相似度。該方法計算文檔相似度時只考慮特征詞，忽略了其他詞。Kusner等[8]提出一種新的文檔距離計算算法： WMD。該算法基于Word2vec詞嵌入，表達文檔為標準詞袋向量，定義詞權重，通過最小化詞權重轉(zhuǎn)移量和詞間轉(zhuǎn)移代價乘積的加和得到文檔轉(zhuǎn)移的最小代價，由此衡量文檔距離。WMD是Earth Mover’s Distance(EMD)[20]的一個特例，EMD計算兩個簽名(分布)的距離，簽名由特征量和權重表達。EMD主要用于圖像處理等領域，而Kusner等巧妙地將EMD應用于文檔距離提出WMD。

文檔聚類在文本表達和相似度計算的基礎上進行。早在1967年，MacQueen就提出了Kmeans算法[21]，每個類別用該類中對象的平均值表示。Kmeans是僅支持球類聚類的基本聚類算法。對于非球類聚類，Comaniciu等[22]提出Mean Shift，它是基于核密度估計的爬山算法，適用于聚類數(shù)較多，簇樣本大小不均勻的場景。從建模角度看，目前代表性研究大致分為基于空間分布、基于神經(jīng)網(wǎng)絡和基于信息傳播三類。Rodriguez和Laio[23]提出Density Peaks聚類算法，假設同一類別的樣本距離比較近，而且與其他類別的樣本距離比較遠，選取比鄰居樣本密度高同時與其他高密度樣本距離比較遠的樣本作為聚類中心，其他樣本根據(jù)選定的聚類中心指定簇。Density Peaks算法只需要計算數(shù)據(jù)點對之間的距離，不需要參數(shù)化一個概率分布。但該算法需要手動選擇聚類中心。蔣旦等[24]提出基于語義和完全子圖的短文本聚類算法。該算法將文檔表示成節(jié)點，距離小于閾值的文檔之間連邊，同時距離作為邊的權值構建圖，然后不斷從圖中提取團(完全子圖)作為自然簇。該算法基于圖操作完成聚類，計算復雜。Xie等[25]提出DEC(deep embedded clustering)，用深度神經(jīng)網(wǎng)絡學習特征表達和聚類。DEC學習從數(shù)據(jù)空間到更低維特征空間的映射，在特征空間中迭代優(yōu)化聚類目標。該方法需要選定初始聚類中心和優(yōu)化參數(shù)。Frey和Dueck[9]提出AP近鄰傳播聚類算法。AP是一種通過樣本間消息傳播不斷迭代更新直至收斂的算法，最終數(shù)據(jù)集用少量的聚類中心樣本表示，這些樣本被認為最具代表性。AP算法不需要提供初值，不關注數(shù)據(jù)分布，可以處理非歐拉分布的數(shù)據(jù)集，允許各種相似度度量方法。

3 EWMD-AP方法

針對新聞評論多樣化的特性，本文提出EWMD-AP新聞評論聚類方法，挖掘評論關注點。通過用強化權重向量替代傳統(tǒng)WMD的詞頻權重向量，將詞的“主體性”信息嵌入距離計算。進一步，用1減去WMD距離得到相似度，再采用AP算法進行新聞評論聚類，最終得到評論關注點簇及其代表性評論。

3.1 WMD算法及強化權重向量

本文基于新聞評論關注點聚類的目標，在原始WMD算法的基礎上，制定新的權重機制，用強化權重向量替代傳統(tǒng)WMD的詞頻權重向量。

3.1.1 WMD算法

WMD是計算文檔間距離的算法，它通過文檔表達的最小轉(zhuǎn)移代價衡量文檔之間的距離。這其中詞間轉(zhuǎn)移代價和權重轉(zhuǎn)移量是文檔表達轉(zhuǎn)移的關鍵。詞間轉(zhuǎn)移代價用Word2vec嵌入空間的歐式距離度量，由此引入詞間語義相似度。每個詞可轉(zhuǎn)移的總權重轉(zhuǎn)移量為詞的權重，由此引入詞在文檔中的貢獻信息。算法中權重用詞頻度量。

令D和D′為分別有m和n個詞的兩個文本文檔的標準詞袋向量表達，文檔D和D′之間的距離定義如下[8]：

算法通過最小化文檔表達D轉(zhuǎn)移到文檔表達D′的累積代價得到文檔之間的距離。最小化文檔表達轉(zhuǎn)移代價是一個雙向的過程，既要求D到D′的轉(zhuǎn)移代價最小，又要求D′到D的轉(zhuǎn)移代價最小。

本文的詞間轉(zhuǎn)移代價用1減去歸一化Cosine相似度計算。

3.1.2 強化權重向量

Kusner等[8]在流量轉(zhuǎn)移的過程中，對詞的權重只考慮了詞頻，所有詞同等對待，沒有考慮不同詞的貢獻差別。顯然，不同詞對句子的貢獻度不同。因此本文引入強化權重向量，包含三部分： 結合詞性特征和文本表達特征的詞重要度系數(shù)、參考新聞正文提取的去背景化系數(shù)及TFIDF系數(shù)。強化權重向量同時考慮詞的數(shù)量特征和質(zhì)量特征，引入了詞的“主體性”信息。

根據(jù)本文評論關注點聚類的宗旨，將與主體相關聯(lián)的詞賦予更高的權重，這里的主體又包括事物和人物兩大方面。因此某些與事物相關的名詞、與人物相關的人名等具有更高的貢獻度，而普通名詞和其他詞貢獻度較低。本文根據(jù)詞性及評論文本表達的特點，設置了四級優(yōu)先級規(guī)則，優(yōu)先級別、詞t在評論D中的重要度系數(shù)It,D及規(guī)則如表1所示。

通常人們總是希望評論中的每個詞都是最重要的詞，不存在其他詞，這樣可以方便地直接利用評論進行各種應用，因此優(yōu)先級最高的詞重要度系數(shù)設為評論的有效長度，其他級別的詞重要度系數(shù)根據(jù)經(jīng)驗設置，如表1所示，這里只是一個比例值，最終的權重將進行歸一化。

計算詞的權重時，將新聞正文看成評論短文本的擴展內(nèi)容，賦予出現(xiàn)在正文中的詞較低的權重，一方面利用了正文信息，另一方面在一定程度上去背景化，詞t的去背景化系數(shù)αt定義如式(2)所示：

其中C1、C2、C3分別對應正文的1級、2級和3級優(yōu)先級詞集合。

由于新聞評論針對正文內(nèi)容展開，評論中往往包含正文中重要度系數(shù)大的詞，在正文這一大背景下，聚類效果受到很大影響。因此對于評論聚類，降低在正文中出現(xiàn)的重要度系數(shù)大的詞的權重很有必要，一定程度上去背景化。在正文中出現(xiàn)的優(yōu)先級越高的詞，去背景化系數(shù)取值相對地越小，意味著它在評論中重要度相對地降低，實驗中按式(2)進行設置。式(2)中的取值是一個經(jīng)驗性的比例關系。

計算詞的TFIDF系數(shù)時，由于不同新聞主題的評論用詞差異比較大，不適合用一個整體語料庫計算詞的權重，因此詞的TFIDF系數(shù)基于該篇新聞的所有評論。計算時，不考慮正文，將每條新聞評論看成一篇文檔。文檔D中詞t的TFIDF系數(shù)如式(3)所示：

詞t在文檔D中的權重wft,D采用式(4)進行計算：

其中tft,D表示詞t在文檔D中的詞頻率。

詞t的逆文檔頻率idft采用式(5)進行計算：

其中N表示文檔數(shù)目，dft表示詞t的文檔頻率。

參考TFIDF的定義(如式(3)所示)，本文的強化權重由詞重要度系數(shù)、去背景化系數(shù)與TFIDF系數(shù)三者相乘得到。形式化地，詞t在文檔D中的強化權重Wt,D如式(6)所示。

3.2 EWMD-AP新聞評論聚類

本文提出的EWMD-AP方法基于強化權重向量的WMD計算新聞評論之間的距離，通過AP算法進行新聞評論聚類。用歸一化的強化權重向量替代單獨的歸一化詞頻權重向量，通過WMD算法得到新聞評論之間的距離。AP是基于信息傳播的文本聚類算法。將新聞評論看作網(wǎng)絡節(jié)點，通過網(wǎng)絡節(jié)點的信息傳播不斷迭代更新直至收斂，得到各新聞評論的聚類中心。傳播的信息有兩種： responsibilityr(i,k)——新聞評論k為新聞評論i的聚類中心的累積置信度；availabilitya(i,k)——新聞評論i選擇新聞評論k為聚類中心的累積置信度。因此新聞評論被選為聚類中心需同時滿足兩個條件： 與許多新聞評論足夠相似，被許多新聞評論選為代表。r(i,k)和a(i,k)的計算公式如式(7)所示。

其中s(i,k)是新聞評論i和新聞評論k的相似度，它通過1減去WMD距離得到。AP算法的兩個重要參數(shù)是偏向參數(shù)和阻尼系數(shù)，前者控制了聚類數(shù)，默認選取新聞評論相似度的中值，后者控制算法的收斂速度。算法輸入為新聞評論之間的兩兩相似度，不關注評論數(shù)據(jù)的分布情況。

WMD基于詞間轉(zhuǎn)移距離計算評論之間的距離，很容易嵌入詞的權重信息，加大重要詞的權重，使得得到的評論距離更好地體現(xiàn)語義距離。并且AP算法基于評論之間的信息傳播聚類，評論之間傳遞信息，很好地進行語義“交互”，使得聚類更好地考慮語義信息，得到理想的聚類結果。

4 實驗及評估

4.1 數(shù)據(jù)集

原始數(shù)據(jù)集為各大中文新聞網(wǎng)站2015年4月12日至2016年1月18日隨機爬取的一批新聞及評論數(shù)據(jù)。在原始數(shù)據(jù)集的基礎上進行篩選，剔除全標點、全英文的評論后選出評論字數(shù)大于等于10個字、合并文字完全相同的評論為一條評論后評論數(shù)超過100條的新聞。字數(shù)過少的評論一方面可能是評論者隨意評論，如“呵呵。。?！钡?，另一方面字數(shù)過少的評論價值不高，不能很好地代表評論者的意見，因此本文過濾評論長度小于10個字的評論。將得到的新聞及評論數(shù)據(jù)進行繁簡轉(zhuǎn)換。在這些預處理后的新聞及評論中，選取四大中文新聞網(wǎng)站： 網(wǎng)易新聞網(wǎng)、新浪新聞網(wǎng)、騰訊新聞網(wǎng)和鳳凰新聞網(wǎng)各六條新聞的評論共24個數(shù)據(jù)集進行人工標注，標注的評論數(shù)達5 989條，內(nèi)容涉及政治、政策、生活、娛樂、體育、旅游、交通、氣候、醫(yī)療、科研等方面，每條新聞的評論數(shù)從155到386不等。

替換評論中的表情符為漢字后用NLP分詞，根據(jù)詞性去除助詞、介詞、量詞，得到有效詞。NLP分詞把一些單字副詞和緊接著的動詞/形容詞分成了兩個詞，本文將它們合并成一個有效詞。

為了將有效詞映射到向量空間，需要進行詞向量學習，本文結合中文維基百科數(shù)據(jù)和搜狗全網(wǎng)新聞數(shù)據(jù)進行訓練，互為補充，同時在實驗中添加缺少的數(shù)據(jù)信息。實驗中分別訓練Word2vec、Glove模型，得到有效詞400維的詞向量。

4.2 評估標準

本文采用兩個指標評估聚類結果，一個是同質(zhì)性(純度)指標和完整性指標的調(diào)和平均V-measure，另一個是標準互信息NMI。

同質(zhì)性(homogeneity)衡量每個簇只包含單一類別成員的程度，完整性(completeness)則衡量一個給定類的所有成員分配到單一簇的程度。形式地有：

其中H(C|K)是給定簇，類的條件熵：

H(C)是類的熵：

這里n是樣本總數(shù)，nc和nk分別表示屬于類c和簇k的樣本數(shù)，nc,k為類c中的樣本分配給簇k的數(shù)量。

給定類，簇的條件熵H(K|C)及簇的熵H(K)定義類似。

Vmeasure為同質(zhì)性和完整性指標的調(diào)和平均：

標準互信息衡量預測標簽和標注標簽的一致程度，是一種能在聚類質(zhì)量和簇數(shù)目之間維持均衡的指標，假定n個樣本的兩組標簽為U和V,U和V的標準互信息定義如下：

其中MI是互信息：

H(U)和H(V)分別是U和V的熵：

H(V)的定義類似。其中P(i)=|Ui|/n表示從U中隨機選擇的樣本落在類Ui的概率，P′(j)定義類似。P(i,j)=|Ui∩Vj|/n表示隨機選擇的樣本同時落在類Ui和Vj的概率。

4.3 實驗設置及結果評估

本文提出的面向新聞評論的聚類方法EWMD-AP由三個主要部分組成： AP聚類、WMD距離和強化權重，為了說明EWMD-AP方法的有效性，本文設置三組對比實驗，依次替換三個組成部分，分別用于比較不同聚類方法，比較不同相似度度量及不同權重組成方法。本節(jié)將展示三組對比實驗的實驗設置及實驗結果，并列舉兩個聚類實例。

4.3.1 不同聚類方法對比實驗

該組實驗涉及的方法及說明如表2所示。其中涉及評論向量表達的方法，如Kmeans和Mean Shift，每條評論的向量表達通過評論中每個有效詞的400維詞向量和對應的強化權重的乘積加和得到。對于Density Peaks算法，參考Zhang等[26]給出的參數(shù)的設置，通過參數(shù)調(diào)優(yōu)設置距離閾值為0.36。

表2 不同聚類方法說明及簡稱

各聚類方法在24個數(shù)據(jù)集上Vmeasure和NMI指標的均值與方差結果如圖1所示。圖(a)為Vmeasure指標結果，圖(b)為NMI指標結果。

圖1 不同聚類方法的Vmeasure和NMI均值與方差

從圖1中可以看出本文EWMD-AP方法在Vmeasure和NMI指標上均表現(xiàn)最優(yōu)。同樣基于強化權重，EWMD-AP優(yōu)于傳統(tǒng)的Kmeans和Mean Shift等算法，以及Density Peaks等當前最新算法。各方法的方差很小，說明各方法的穩(wěn)定性較好。針對本文的新聞評論數(shù)據(jù)集，除了Density Peaks方法Glove詞表達的結果略優(yōu)于Word2vec詞表達的結果，其他方法Word2vec詞表達的結果比Glove更優(yōu)，說明本文的數(shù)據(jù)集更適合采用Word2vec詞表達。這可能是因為新聞評論之間往往沒有明顯的關系，較為獨立，因此引入全局統(tǒng)計信息的Glove不一定能優(yōu)化結果，反而甚至對結果造成影響。

4.3.2 不同相似度度量對比實驗

該組實驗通過替換本文EWMD-AP方法中的相似度度量： 1減去WMD距離構造對比方法。對比方法的相似度度量分別為負的平方歐式距離和歸一化Cosine相似度，分別記為Euclidean-AP和Cosine-AP。

各相似度度量在24個數(shù)據(jù)集上Vmeasure和NMI指標的均值與方差結果如圖2所示。圖(a)為Vmeasure指標結果，子圖(b)為NMI指標結果。

從圖2中可以看出各方法比較穩(wěn)定，同樣Word2vec詞表達優(yōu)于Glove詞表達。EWMD-AP方法在兩個指標上均取得最大值，表明WMD距離算法優(yōu)于傳統(tǒng)的歐式距離和Cosine計算方法，WMD與AP結合有效地提高了聚類質(zhì)量。

4.3.3 不同權重組成對比實驗

該組實驗涉及的方法及說明如表3所示。

表3 不同權重組成方法說明及簡稱

續(xù)表

圖2 不同相似度度量的Vmeasure和NMI均值與方差

由于針對本文的新聞評論數(shù)據(jù)集，Word2vec詞表達的結果比Glove更優(yōu)，因此該組實驗只用Word2vec詞表達進行。由于各方法比較穩(wěn)定，為了更清晰地展示各方法的差別，該組實驗省去了穩(wěn)定性分析。各方法在24個數(shù)據(jù)集上Vmeasure和NMI指標的均值與方差結果如圖3所示。

圖3 不同權重組成方法的Vmeasure和NMI指標的均值與方差

從圖3中可以看出TFIDF權重一定程度上優(yōu)于詞頻權重，而強化權重優(yōu)于傳統(tǒng)的TFIDF權重和詞頻權重，優(yōu)于單獨的詞重要度系數(shù)和去背景化系數(shù)，同時優(yōu)于TFIDF權重、詞重要度系數(shù)和去背景化系數(shù)的兩兩乘積，說明本文提出的強化權重向量的有效性，三個組成要素都不可或缺。

進一步，可以觀察到在TFIDF系數(shù)的基礎上乘以詞重要度系數(shù)可以使結果得到少量的提升；在TFIDF系數(shù)的基礎上乘以去背景化系數(shù)，結果比單獨的TFIDF更差，然而詞重要度系數(shù)、去背景化系數(shù)和TFIDF系數(shù)三者乘積使得結果有了相對顯著的提升。這說明詞重要度系數(shù)雖然考慮了詞的“主體性”信息，但是可能過分強調(diào)了那些對正文來說重要的詞，加大了背景的影響，使得結果的提升并不明顯。去背景化系數(shù)雖然降低了正文背景的影響，但是把這些詞的權重降得比一般詞都低，致使一些無關緊要的詞的權重就顯得相對高了，使得去背景化的優(yōu)勢并沒有體現(xiàn)出來，造成結果比單獨的TFIDF還要差。而三者乘積，即強化權重，很好地考慮了詞的重要度信息，同時不過分強調(diào)背景詞的重要度，使得結果得到較大的提升。

4.3.4 聚類實例展示

從上述三組實驗結果我們觀察到，替換EWMD-AP聚類方法的任何一部分(即AP聚類、WMD距離和強化權重)所得方法相較EWMD-AP其性能都有下降，說明AP聚類、WMD距離和強化權重三個部分在EWMD-AP方法中缺一不可。為了進一步說明EWMD-AP方法的有效性，下面展示兩個聚類實例。

某條新浪新聞(評論數(shù)373條)及某條鳳凰新聞(評論數(shù)235)，用Word2vec表達詞向量，進而用EWMD-AP方法進行評論聚類，部分聚類結果分別如表4和表5所示。

表中第一列表示新聞，這里取標題進行展示，第二列為各個簇的聚類中心評論，即代表性評論，第三列為各個簇對應的其他評論。在表中一方面可以從全局的角度查看評論的關注點(第二列)，另一方面可以更細致地查看各個關注點簇的具體情況(第三列)，聚焦到某一個關注點，查看該關注點的其他評論。

表4 某條新浪新聞的評論的聚類結果

表5 某條鳳凰新聞的評論的聚類結果

續(xù)表

5 結論及展望

面對日益增長的新聞和評論數(shù)據(jù)，本文旨在從雜亂的新聞評論中得到關注點簇和對應的代表性評論。傳統(tǒng)的相似度計算方法和聚類方法即使在向量表達中嵌入強化權重也不能很好地利用詞信息，獲得理想的聚類結果。因此本文提出一種面向新聞評論的聚類方法EWMD-AP。該方法基于強化權重向量的WMD計算評論之間的距離，進而用AP算法對評論進行聚類。傳統(tǒng)的WMD距離計算算法，對于權重只考慮詞頻信息，只在數(shù)量角度考慮權重。本文的強化權重向量由三部分組成： 基于詞性及文本表達特征的詞重要度系數(shù)、新聞正文作為評論背景的去背景化系數(shù)和TFIDF系數(shù)。該強化權重向量從數(shù)量和質(zhì)量方面較全面地考慮了詞信息。結合強化權重向量和WMD文本距離計算考慮語義的優(yōu)點，以及AP算法基于文本特征聚類的優(yōu)點，本文方法EWMD-AP在四大中文新聞網(wǎng)站的24個新聞評論數(shù)據(jù)集上取得了很好的效果。聚類結果優(yōu)于Kmeans和Mean Shift等傳統(tǒng)聚類算法，以及Density Peaks等當前最新算法，得到的聚類中心也是很好的代表性評論。

本文直接將得到的聚類中心作為代表性評論，沒有考慮評論者行為，下一步將結合評論者特征、回復數(shù)、點贊數(shù)及與聚類中心的距離等信息，由它們共同決定代表性評論。

[1] HAI Z, CONG G, CHANG K, et al. Coarse-to-fine review selection via supervised joint aspect and sentiment model [C]//Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2014: 617-626.

[2] DAYAN A, MOKRYN O, KUFLIK T. A two-iteration clustering method to reveal unique and hidden characteristics of items based on text reviews [C]//Proceedings of the 24th International Conference on World Wide Web. New York: ACM, 2015: 637-642.

[3] ZHOU X, WAN X, XIAO J. Representation learning for aspect category detection in online reviews [C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence. Menlo Park, CA: AAAI, 2015: 417-423.

[4] NGUYEN T-S, LAUW H W, TSAPARAS P. Using micro-reviews to select an efficient set of reviews [C]//Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. New York: ACM, 2013: 1067-1076.

[5] NGUYEN T S, LAUW H W, TSAPARAS P. Review selection using micro-reviews [J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(4): 1098-1111.

[6] CHONG W-H, DAI B T, LIM E-P. Did you expect your users to say this?: Distilling unexpected micro-reviews for venue owners [C]//Proceedings of the 26th ACM Conference on Hypertext and Social Media. New York: ACM, 2015: 13-22.

[7] LU Z, MAMOULIS N, PITOURA E, et al. Sentiment-based topic suggestion for micro-reviews [C]//Proceedings of the 10th International AAAI Conference on Web and Social Media. Menlo Park, CA: AAAI, 2016: 231-240.

[8] KUSNER M, SUN Y, KOLKIN N, et al. From word embeddings to document distances [C]//Proceedings of the 32nd International Conference on Machine Learning. New York: ACM, 2015: 957-966.

[9] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.

[10] HARRIS Z S. Distributional structure [J]. Word, 1954, 10：146-162.

[11] HINTON G E. Learning distributed representation of concepts [C]//Proceedings of the 8th Annual Conference of the Cognitive Science Society. Mahwah, New Jersey: Lawrence Erlbaum Associates, 1986: 1-12.

[12] BROWN P F, DESOUZA P V, MERCER R L, et al. Class-based n-gram models of natural language [J]. Computational Linguistics, 1992, 18(4): 467-479.

[13] JEFFREY P, RICHARD S, MANNING C D. GloVe: Global vectors for word representation[C]//Proceedings of the Conference on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2014: 1532-1543.

[14] MIKOLOV T, CHEN K, CORRADO G, et al. Efficient estimation of word representations in vector space [J]. arXiv preprint arXiv:13013781, 2013.

[15] MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality[C]//Proceedings of Advances in Neural Information Processing Systems. Red Hook, NY: Curran Associates Inc, 2013: 3111-3119.

[16] 田堃, 柯永紅, 穗志方. 基于語義角色標注的漢語句子相似度算法 [J]. 中文信息學報, 2016, 30(6): 126-132.

[17] WANG C, SONG Y, LI H, et al. KnowSim: A document similarity measure on structured heterogeneous information networks [C]//Proceedings of IEEE 15th International Conference on Data Mining. New Jersey: IEEE, 2015: 1015-1020.

[18] 詹志建, 楊小平. 一種基于復雜網(wǎng)絡的短文本語義相似度計算 [J]. 中文信息學報, 2016, 30(4): 71-80+9.

[19] SUN Y, LI W, DONG P. Research on text similarity computing based on word vector model of neural networks [C]//Proceedings of IEEE 6th International Conference on Software Engineering and Service Science (ICSESS). New Jersey: IEEE, 2015: 994-997.

[20] RUBNER Y, TOMASI C, GUIBAS L J. A metric for distributions with applications to image databases[C]//Proceedings of the 6th International Conference on Computer Vision. New Jersey: IEEE, 1998: 59-66.

[21] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability: Volume 1 Statistics. Oakland, CA University of California Press, 1967: 281-297.

[22] COMANICIU D, MEER P. Mean shift: a robust approach toward feature space analysis [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619.

[23] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks [J]. Science, 2014, 344(6191): 1492-1496.

[24] 蔣旦, 周文樂, 朱明. 基于語義和圖的文本聚類算法研究 [J]. 中文信息學報, 2016, 30(5): 121-128.

[25] XIE J, GIRSHICK R, FARHADI A. Unsupervised deep embedding for clustering analysis [C]//Proceedings of the 33rd International Conference on Machine Learning. New York: ACM, 2016: 478-487.

[26] ZHANG Y, XIA Y, LIU Y, et al. Clustering sentences with density peaks for multi-document summarization [C]//Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Stroudsburg, PA: ACL, 2015: 1262.

官賽萍(1991—)，博士研究生，主要研究領域為知識圖譜。

E-mail： guansaiping@software.ict.ac.cn

靳小龍(1976—)，博士，副研究員，主要研究領域為知識圖譜、社會計算、大數(shù)據(jù)等。

E-mail： jinxiaolong@ict.ac.cn

徐學可(1983—)，博士，助理研究員，主要研究領域為情感分析、自然語言處理、機器學習等。

E-mail： haudor@163.com

NewsCommentsClusteringBasedonWMDDistanceandAffinityPropagation

GUAN Saiping1,2, JIN Xiaolong1,2, XU Xueke1,2, WU Dayong1,2, JIA Yantao1,2, WANG Yuanzhuo1,2, LIU Yue1,2

(1. CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology,Chinese Academy of Sciences, Beijing 100090, China；2. School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 100049, China)

With the rapid development of news websites, the news comments increase sharply, which are very important to public opinion analysis and news comments recommendation. This paper proposes a news comments clustering method, called EWMD-AP, to automatically mine the focuses of the public on the news. This method employs Word Mover’s Distance (WMD) with enhanced weight vectors to calculate the distances between news comments. It also adopts Affinity Propagation (AP) to cluster comments, and finally obtains the clusters and their representative comments corresponding to the focuses of the public. Particularly, this paper proposes to replace the traditional word frequency based weight vectors in WMD with enhanced weight vectors, which consist of three components: the importance coefficient of words, the de-contextualization coefficient, and the traditional TFIDF coefficient. Experimental results on 24 news comments datasets demonstrate that EWMD-AP performs much better than both traditional clustering methods (e.g. Kmeans, Mean Shift, etc) and the state-of-the-art ones (e.g. Density Peaks, etc).

news comments clustering; enhanced weight vectors; de-contextualization; Word Mover’s Distance; affinity propagation

1003-0077(2017)05-0203-12

TP391

A

2016-03-16定稿日期2017-05-31

國家重點研發(fā)計劃(2016YFB1000902)；973計劃(2014CB340406)；國家自然科學基金(61772501，61572473，61572469，61402442，91646120)