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

(1. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 中國(guó)科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100190；2. 中國(guó)科學(xué)院大學(xué) 計(jì)算機(jī)與控制學(xué)院，北京 100049)

基于WMD距離與近鄰傳播的新聞評(píng)論聚類

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

(1. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 中國(guó)科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100190；2. 中國(guó)科學(xué)院大學(xué) 計(jì)算機(jī)與控制學(xué)院，北京 100049)

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

新聞評(píng)論聚類；強(qiáng)化權(quán)重向量；去背景化；Word Mover’s Distance；近鄰傳播

1 引言

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

3 EWMD-AP方法

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

3.1 WMD算法及強(qiáng)化權(quán)重向量

本文基于新聞評(píng)論關(guān)注點(diǎn)聚類的目標(biāo)，在原始WMD算法的基礎(chǔ)上，制定新的權(quán)重機(jī)制，用強(qiáng)化權(quán)重向量替代傳統(tǒng)WMD的詞頻權(quán)重向量。

3.1.1 WMD算法

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

令D和D′為分別有m和n個(gè)詞的兩個(gè)文本文檔的標(biāo)準(zhǔn)詞袋向量表達(dá)，文檔D和D′之間的距離定義如下[8]：

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

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

3.1.2 強(qiáng)化權(quán)重向量

Kusner等[8]在流量轉(zhuǎn)移的過程中，對(duì)詞的權(quán)重只考慮了詞頻，所有詞同等對(duì)待，沒有考慮不同詞的貢獻(xiàn)差別。顯然，不同詞對(duì)句子的貢獻(xiàn)度不同。因此本文引入強(qiáng)化權(quán)重向量，包含三部分： 結(jié)合詞性特征和文本表達(dá)特征的詞重要度系數(shù)、參考新聞?wù)奶崛〉娜ケ尘盎禂?shù)及TFIDF系數(shù)。強(qiáng)化權(quán)重向量同時(shí)考慮詞的數(shù)量特征和質(zhì)量特征，引入了詞的“主體性”信息。

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

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

計(jì)算詞的權(quán)重時(shí)，將新聞?wù)目闯稍u(píng)論短文本的擴(kuò)展內(nèi)容，賦予出現(xiàn)在正文中的詞較低的權(quán)重，一方面利用了正文信息，另一方面在一定程度上去背景化，詞t的去背景化系數(shù)αt定義如式(2)所示：

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

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

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

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

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

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

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

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

3.2 EWMD-AP新聞評(píng)論聚類

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

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

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

4 實(shí)驗(yàn)及評(píng)估

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

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

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

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

4.2 評(píng)估標(biāo)準(zhǔn)

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

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

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

H(C)是類的熵：

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

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

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

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

其中MI是互信息：

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

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

4.3 實(shí)驗(yàn)設(shè)置及結(jié)果評(píng)估

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

4.3.1 不同聚類方法對(duì)比實(shí)驗(yàn)

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

表2 不同聚類方法說明及簡(jiǎn)稱

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

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

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

4.3.2 不同相似度度量對(duì)比實(shí)驗(yàn)

該組實(shí)驗(yàn)通過替換本文EWMD-AP方法中的相似度度量： 1減去WMD距離構(gòu)造對(duì)比方法。對(duì)比方法的相似度度量分別為負(fù)的平方歐式距離和歸一化Cosine相似度，分別記為Euclidean-AP和Cosine-AP。

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

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

4.3.3 不同權(quán)重組成對(duì)比實(shí)驗(yàn)

該組實(shí)驗(yàn)涉及的方法及說明如表3所示。

表3 不同權(quán)重組成方法說明及簡(jiǎn)稱

續(xù)表

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

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

圖3 不同權(quán)重組成方法的Vmeasure和NMI指標(biāo)的均值與方差

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

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

4.3.4 聚類實(shí)例展示

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

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

表中第一列表示新聞，這里取標(biāo)題進(jìn)行展示，第二列為各個(gè)簇的聚類中心評(píng)論，即代表性評(píng)論，第三列為各個(gè)簇對(duì)應(yīng)的其他評(píng)論。在表中一方面可以從全局的角度查看評(píng)論的關(guān)注點(diǎn)(第二列)，另一方面可以更細(xì)致地查看各個(gè)關(guān)注點(diǎn)簇的具體情況(第三列)，聚焦到某一個(gè)關(guān)注點(diǎn)，查看該關(guān)注點(diǎn)的其他評(píng)論。

表4 某條新浪新聞的評(píng)論的聚類結(jié)果

表5 某條鳳凰新聞的評(píng)論的聚類結(jié)果

續(xù)表

5 結(jié)論及展望

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

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

[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] 田堃, 柯永紅, 穗志方. 基于語義角色標(biāo)注的漢語句子相似度算法 [J]. 中文信息學(xué)報(bào), 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] 詹志建, 楊小平. 一種基于復(fù)雜網(wǎng)絡(luò)的短文本語義相似度計(jì)算 [J]. 中文信息學(xué)報(bào), 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]. 中文信息學(xué)報(bào), 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—)，博士研究生，主要研究領(lǐng)域?yàn)橹R(shí)圖譜。

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

靳小龍(1976—)，博士，副研究員，主要研究領(lǐng)域?yàn)橹R(shí)圖譜、社會(huì)計(jì)算、大數(shù)據(jù)等。

E-mail： jinxiaolong@ict.ac.cn

徐學(xué)可(1983—)，博士，助理研究員，主要研究領(lǐng)域?yàn)榍楦蟹治?、自然語言處理、機(jī)器學(xué)習(xí)等。

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

國(guó)家重點(diǎn)研發(fā)計(jì)劃(2016YFB1000902)；973計(jì)劃(2014CB340406)；國(guó)家自然科學(xué)基金(61772501，61572473，61572469，61402442，91646120)