基于圖聚類的漢越雙語新聞話題發(fā)現(xiàn)

王禹森 余正濤 高盛祥 周 超 洪旭東

(昆明理工大學(xué)信息工程與自動化學(xué)院，昆明，650500)

引 言

隨著經(jīng)濟(jì)全球化，不同國家之間的聯(lián)系日益緊密，共同關(guān)注的事件、話題也越來越多?？缯Z言新聞話題發(fā)現(xiàn)就是針對互聯(lián)網(wǎng)上不同國家發(fā)布的不同語言新聞進(jìn)行分析處理，獲得的不同類別話題的新聞，幫助人們及時掌握當(dāng)前國際和地區(qū)發(fā)生的熱點(diǎn)事件，以及對同一事件不同國家的不同看法。目前話題發(fā)現(xiàn)研究基本都是在單語環(huán)境下做的，并取得了很好的成果。單語話題發(fā)現(xiàn)方法一般分為以下3類：(1)向量空間模型。它通過抽取文本詞頻、詞性和語法結(jié)構(gòu)等特征，將文本表征成多維特征向量，利用向量之間的關(guān)系實(shí)現(xiàn)文本相似度的計算，從而進(jìn)行共同話題的挖掘[1-2]。(2)概率模型。它利用新聞文本中詞語與話題分布的統(tǒng)計規(guī)律，構(gòu)建話題統(tǒng)計概率模型，分析挖掘新聞文本話題[3-4]。(3)圖模型。它提取新聞文檔特征及特征之間的關(guān)系，如特征詞之間關(guān)系，建立特征概率圖模型，通過圖的求解思路分析文本的話題[5]。相比單語環(huán)境下的話題發(fā)現(xiàn)，雙語環(huán)境下的話題發(fā)現(xiàn)研究較少，其關(guān)鍵問題在于如何跨越語言障礙，目前主要基于以下3類方法，(1)基于機(jī)器翻譯。它將不同語言的新聞文本轉(zhuǎn)化到同一目標(biāo)語言，在單語環(huán)境下進(jìn)行共同話題的挖掘與分析，機(jī)器翻譯的準(zhǔn)確性對這種方法有著很大的影響。(2)借助雙語詞典。該方法對文本中的實(shí)體，關(guān)鍵詞進(jìn)行翻譯，來構(gòu)造跨語言特征詞空間，進(jìn)行話題發(fā)現(xiàn)[6]，這種方法忽略了沒有互譯關(guān)系卻存在聯(lián)系的詞語，比如“阮富仲”和“越南國家領(lǐng)導(dǎo)人”在詞典中是沒有互譯關(guān)系的，卻表達(dá)相同的意義。(3)基于大規(guī)模雙語語料[7-9]。如利用概率主題模型，對平行語料或者可比語料進(jìn)行跨語言主題挖掘，將獲得一系列的跨語言主題作為特征空間，這種方法難點(diǎn)在于大規(guī)模對齊語料收集整理。

在對漢越跨語言新聞話題發(fā)現(xiàn)方面，由于漢越雙語新聞采用不同語言進(jìn)行表征，而不同語言在不同的詞空間下，導(dǎo)致不同語言文本很難表示在同一個特征空間上，這給漢越雙語新聞話題發(fā)現(xiàn)工作帶來了挑戰(zhàn)。同時，新聞報道中的時間、地點(diǎn)、人物、事情經(jīng)過和事情發(fā)生的原因具有真實(shí)性，這些關(guān)鍵內(nèi)容必須具體、明確，對于同一事件的報道，漢語與越南語新聞在這些新聞要素上一致，這為進(jìn)行漢越雙語的話題發(fā)現(xiàn)研究提供了有效的途徑。利用新聞要素表征文檔，計算要素間相關(guān)性，可以計算出文本間的相似度，構(gòu)成漢越雙語新聞圖模型，圖中節(jié)點(diǎn)的緊密程度表示文本相似度高低，這樣便將漢越雙語新聞話題發(fā)現(xiàn)看成圖模型的聚類問題來分析。

1 面向漢越新聞報道的圖模型

漢越雙語新聞圖G={V,E,W}，表示漢越雙語新聞集合N與圖的一個映射。V是漢越雙語新聞集合中的新聞文本在圖中對應(yīng)的文本集合，vi為漢語文本,vj為越南語文本，表示為V={vi,vj|1≤i≤n,1≤j≤m}。E是漢越雙語新聞集合中的新聞文本在圖中的邊， (vi1,vi2)為漢語文檔間的邊，(vj1,vj2)為越南語文檔間的邊，(vi,vj)為漢越雙語文檔間的邊，表示為E={(vi,vj),(vi1,vi2),(vj1,vj2)|i1≠i2,j1≠j2}。W表示圖中邊的權(quán)重，表示為W={w(i,j),w(i1,i2),w(j1,j2)}，權(quán)重由新聞要素相似度決定。新聞的事件要素一般包括時間、地點(diǎn)、人物、經(jīng)過和原因，可以表示為When，Where，Who，What和Why，其中，時間可以用時間實(shí)體來表示，地點(diǎn)可以用地點(diǎn)實(shí)體來表示，人物可以用人物實(shí)體來表示，經(jīng)過一般用要素中的動詞來表示。規(guī)定兩個新聞文本間具有連接線必須滿足以下條件之一：(1)兩篇新聞在時間、地點(diǎn)和人物等要素上有相同的要素對出現(xiàn)；(2)兩篇新聞在What這個要素上相似度達(dá)到0.5以上。

計算單語文檔間邊權(quán)重時，考慮新聞文本中的詞對于所在新聞文本的重要程度，采用TF-IDF方法計算。抽取新聞文本要素，以向量的形式表征一篇新聞文本，每個向量由其特征項及權(quán)重表示，構(gòu)成文本向量空間。相同語言文檔節(jié)點(diǎn)間的相似度采用兩篇文檔空間向量的夾角余弦來計算。

設(shè)任意兩個節(jié)點(diǎn)?xi,xk∈V，TF-IDF公式為

Wt,x=TFt,x×IDFt,x

(1)

(2)

IDFt,x=log(X/XN)

(3)

式中:Wt,x為新聞要素t在新聞文本x中的權(quán)重; TFt,x指詞語t在文檔x中出現(xiàn)的頻率，如式(2)表示一篇有M個詞的文檔含有N個新聞要素t。IDFt,x反映新聞要素t在所有新聞文檔中的常見程度，在一定程度上體現(xiàn)了該新聞要素的區(qū)分能力，其中X表示所有新聞文檔的數(shù)目，XN表示所有新聞文檔中包含新聞要素t的文檔數(shù)。

利用文檔向量間的夾角余弦分別計算相同語言文檔節(jié)點(diǎn)間的權(quán)重為

(4)

式中：Wt,x1,Wt,x2分別為文檔x1,x2中的第t個特征項的權(quán)重，從而得到相同語言文檔間的權(quán)重，即w(i1,i2)，w(j1,j2) 。

計算漢越雙語文檔間邊權(quán)重時，抽取新聞文檔要素，將漢越雙語文檔表征成向量，計算漢語文檔向量中新聞要素與越南語文檔向量中每個新聞要素的相似度和，從而得到漢越雙語文檔間的相似度為

(5)

圖1 漢越雙語新聞圖Fig.1 Chinese-Vietnamese bilingual news graph

式中：w(i,j)為漢越雙語文檔間邊的相似度，即圖中邊vi與vj之間的權(quán)重；w(a,b)為漢越文檔中兩個要素的相似度。w(a,b)具體相似度的計算方法是借助維基百科中具有中越互譯關(guān)系的概念，不同語言詞語會出現(xiàn)在不同的概念頁面上，且詞語與其他概念之間存在一定的共現(xiàn)關(guān)系，首先提取維基百科中漢語越南語具有對應(yīng)關(guān)系的概念集合，構(gòu)建雙語概念特征空間，然后根據(jù)詞語在相應(yīng)概念描述文本中出現(xiàn)的詞頻特征，以及詞語與概念在其他概念文本中的共現(xiàn)特征構(gòu)建詞語的概念向量值，最后通過夾角余弦對兩個向量進(jìn)行詞語相似度計算[10]。最后可以得到漢越新聞圖模型，基本框架如圖1所示。

2 隨機(jī)游走相似度矩陣計算

漢越雙語新聞圖的轉(zhuǎn)移概率矩陣可以表示為pz= (pij)，它是一個n×n矩陣,其中的每一個元素pi j表示任意一個頂點(diǎn)vi到其鄰居節(jié)點(diǎn)vj的轉(zhuǎn)移概率為

(6)

式中：wij為新聞文本節(jié)點(diǎn)vi與vj的相似度，即圖中邊的權(quán)重；k為圖中以文本節(jié)點(diǎn)vi為端點(diǎn)的邊的個數(shù)；∑wij為所有以文本節(jié)點(diǎn)vi為端點(diǎn)的邊的權(quán)重之和；圖中不具有連線關(guān)系的文本節(jié)點(diǎn)的轉(zhuǎn)移概率為0。

定義1給定圖G={V,E,W}，頂點(diǎn)vi到vj的路徑是集合E中從頂點(diǎn)v0=vi出發(fā)到頂點(diǎn)vk+1=vj結(jié)束的一系列邊的集(v0,v1),(v1,v2)，…，(vk-1,vk),(vk,vj)，可表示為Path(vi,vj)，如果有這樣一條可以相通的路徑就說明頂點(diǎn)vi和vj是相連的。路徑上邊的權(quán)重之和可以表示路徑的長度，而頂點(diǎn)vi和vj之間的距離指長度中最大的一個。

采用隨機(jī)游走模型來度量漢越新聞圖中頂點(diǎn)之間的相似度，若兩個頂點(diǎn)之間相通的路徑越多，則說明兩頂點(diǎn)之間的轉(zhuǎn)移概率就越大，頂點(diǎn)之間的相似度就越大。

定義2圖G的n×n的轉(zhuǎn)移概率矩陣為pz，給定l為隨機(jī)游走的路徑長度，則頂點(diǎn)vi到vj的鄰近隨機(jī)游走相似度為

(7)

式中：Path(vi,vj)是頂點(diǎn)vi到vj的路徑，其長度為length(Path(vi,vj))，p(Path(vi,vj))為轉(zhuǎn)移概率。隨機(jī)游走相似度矩陣可表示為

(8)

式中：pz為轉(zhuǎn)移概率矩陣，l為隨機(jī)游走的路徑長度。過程如算法1所描述。

算法1漢越新聞圖隨機(jī)游走相似度矩陣算法。

輸入：漢越新聞圖。

輸出：隨機(jī)游走相似度矩陣。

(1)計算漢越新聞圖的轉(zhuǎn)移概率矩陣。

(2)計算漢越新聞圖的鄰近隨機(jī)游走相似度。

(3)利用轉(zhuǎn)移概率矩陣計算漢越新聞圖的隨機(jī)游走相似度矩陣。

(4)輸出漢越新聞圖的隨機(jī)游走相似度矩陣。

3 基于信息傳遞的漢越新聞圖聚類

利用漢越新聞文本相似度矩陣進(jìn)行圖聚類與一般聚類問題相比存在以下特點(diǎn)：(1)通過隨機(jī)游走得到的漢越新聞文本相似度矩陣，描述的是節(jié)點(diǎn)之間的相關(guān)程度，而不是節(jié)點(diǎn)之間的歐式距離，故無法直接使用K-Means算法進(jìn)行求解。(2)本文得到的漢越新聞文本相似度矩陣不對稱，故無法使用譜聚類的方法進(jìn)行求解。因此，本文采用信息傳遞算法[11]對漢越新聞文本圖模型進(jìn)行聚類，整個聚類的過程，利用漢越雙語新聞圖的隨機(jī)游走相似度矩陣，通過迭代更新吸引度和歸屬度兩種信息完成聚類，相應(yīng)的更新公式為

(9)

(10)

(11)

式中：r(vi,vj)為從頂點(diǎn)vi發(fā)送到聚類中心vj的數(shù)值消息，反映頂點(diǎn)vj是否適合作為頂點(diǎn)vi的聚類中心；s(vi,vj)為頂點(diǎn)vi和vj的相似度；a(vi,vj)為從候選聚類中心vj發(fā)送到頂點(diǎn)vi的數(shù)值信息，反映頂點(diǎn)vi是否選擇vj作為其聚類中心。在信息傳遞聚類算法的每次迭代更新頂點(diǎn)vi的過程中，吸引度Ri和歸屬度Ai要與上次迭代所得Ri-1與Ai-1的值進(jìn)行加權(quán)更新，更新公式為

Ri=(1-lam)×Ri+lam×Ri-1

(12)

Ai=(1-lam)×Ai+lam×Ai-1

(13)

其中，lam∈[0,1]通過改變lam的值可以改進(jìn)算法的收斂性。

算法滿足以下條件之一，即停止迭代：

(1)達(dá)到預(yù)先設(shè)定的迭代次數(shù)；(2)頂點(diǎn)信息改變量低于設(shè)定的閾值；(3)所選的聚類中心在連續(xù)若干次的迭代中保持穩(wěn)定的值。

根據(jù)r(vi,vj)+a(vi,vj)的值判斷頂點(diǎn)vj能否作為聚類中心，最后，將其他頂點(diǎn)分配到與其最鄰近的聚類中心。具體的聚類過程如算法2所示。

算法2信息傳遞聚類算法。

輸入：鄰接隨機(jī)游走相似度矩陣。

輸出：k個簇C1，C2，C3，…，Ck。

(1)初始化r(vi,vj)=0，a(vi,vj)=0

(2)迭代執(zhí)行以下更新過程：

(6)Ri=(1-lam)×Ri+lam×Ri-1

(7)Ai=(1-lam)×Ai+lam×Ai-1

(8)對于任一個頂點(diǎn)vi，如果r(vi,vi)+a(vi,vi)達(dá)到迭代次數(shù)或者不再變化，則vi是一個聚類中心。

(9)基于s(vi,vi)，將其他頂點(diǎn)vj分配到與它最鄰近的聚類中心。

(10)輸出k個簇C1，C2，C3，…，Ck。

基于以上隨機(jī)游走算法和信息傳遞算法，最后得到k個簇，認(rèn)為每一個簇都是一個話題，完成了漢越雙語新聞的話題發(fā)現(xiàn)任務(wù)。

4 實(shí)驗結(jié)果與分析

4.1 實(shí)驗數(shù)據(jù)

選取了180個中文門戶網(wǎng)站和20個論壇以及125個不同專題的越南語網(wǎng)站。中文新聞包括新華社、人民日報、知名論壇、主流門戶網(wǎng)站和越南網(wǎng)站(以每日快訊、越訊社和越共機(jī)關(guān)等核心平臺為主)。在從爬取到的數(shù)據(jù)中選擇訓(xùn)練集時，選取了5個話題：兩會、朝核、中國反腐、南海爭端和敘利亞反恐。因為在這5個話題上，越南的各大媒體和中國的各大媒體關(guān)注最多。另外，一個話題出現(xiàn)以后，會在一段時間內(nèi)出現(xiàn)很多關(guān)于該話題的新聞報道，所以在進(jìn)行新聞文檔選取的時候只選取近10天的新聞數(shù)據(jù)進(jìn)行實(shí)驗。

新聞最核心的是What，Who，Where，When和Why 5個要素，而這5個要素的詞性主要對應(yīng)了動詞、名詞、時態(tài)詞、形容詞和數(shù)詞，因此在對漢語和越南語新聞文本進(jìn)行分詞和詞性標(biāo)注后，將這些詞性的詞語抽取出來作為新聞要素。對于中文詞性標(biāo)注和命名實(shí)體識別，采用ICTCLAS3.0工具。利用越南語分詞工具[12]對越南語新聞文本進(jìn)行分詞、詞性標(biāo)注等處理，根據(jù)處理結(jié)果，人工輔助抽取要素。各類新聞數(shù)如表1所示。

表1 實(shí)驗數(shù)據(jù)集

4.2 評價方法

在話題發(fā)現(xiàn)研究中，經(jīng)常會用錯檢率F和漏檢率M作為評價指標(biāo)。評價指標(biāo)的具體含義見表2。

表2 評價指標(biāo)的具體含義

在表2中用大寫字母A，B，C，D來表示某一個話題的檢測結(jié)果，用F=B/(B+D) 來表示話題檢測的錯檢率，用M=C/(A+C)來表示話題檢測的漏檢率。此外，為了綜合漏檢率和錯檢率，定義耗費(fèi)函數(shù)(Cost function)為

CDet=CmissPmissP(rel)+CfaPfa(1-P(rel))

(14)

式中：Cmiss和Cfa為話題檢測中漏檢和誤檢的代價，P(rel)表示某個新聞報道屬于某一類的先驗概率，Pmiss和Pfa為話題檢測的漏檢概率和誤檢概率。在TDT的標(biāo)準(zhǔn)中，令Cmiss=1.0，Cfa=0.1，P(rel)=0.02。由此可以看出耗費(fèi)函數(shù)越小，話題發(fā)現(xiàn)效果越好。

4.3 實(shí)驗結(jié)果與分析

本文通過3個不同方法進(jìn)行漢越新聞話題發(fā)現(xiàn)，方法1通過基于多策略優(yōu)化的分治多層聚類算法的話題發(fā)現(xiàn)方法，首先得出單語文檔下的聚類結(jié)果，然后通過機(jī)器翻譯的方法將其合并；方法2采用雙語文檔主題生成模型(Latent Dirichlet allocation, LDA)，利用Wikipedia中的10 000對漢越雙語文檔構(gòu)建可比語料，訓(xùn)練雙語主題模型，對不同語言文本進(jìn)行表示[13]。認(rèn)為一對文檔主題上具有相同的概率分布。本文共設(shè)置了100個主題，利用獲得的雙語主題模型來對要聚類的500篇新聞進(jìn)行推斷，最后，采用K-Means進(jìn)行聚類。方法3采用本文提出的話題發(fā)現(xiàn)方法。實(shí)驗結(jié)果如表3所示。

表3 新聞話題發(fā)現(xiàn)對比實(shí)驗結(jié)果

根據(jù)實(shí)驗結(jié)果數(shù)據(jù)，分別計算每種方法的誤檢率、漏檢率和消耗函數(shù)，對比結(jié)構(gòu)如表4所示。通過表4的實(shí)驗結(jié)果對比可以發(fā)現(xiàn)，在給定訓(xùn)練集的5個話題下，本文方法通過計算新聞要素的相似度，求得圖模型，并通過隨機(jī)游走算法求得相似度矩陣，在話題發(fā)現(xiàn)方面，不論是漏檢率、誤檢率還是最后的耗費(fèi)函數(shù)都要優(yōu)于基于多策略優(yōu)化的分治多層聚類算法和雙語LDA方法。由此可見，本文提出的基于圖模型的漢越雙語新聞話題發(fā)現(xiàn)圖聚類模型是可行的。

表4 誤檢率、漏檢率和消耗函數(shù)

5 結(jié)束語

在雙語環(huán)境下進(jìn)行話題發(fā)現(xiàn)是一項比較困難的任務(wù)，本文提出基于圖聚類的漢越雙語話題發(fā)現(xiàn)方法，利用雙語新聞要素作為跨語言的橋梁，根據(jù)不同語言新聞要素之間的關(guān)聯(lián)計算不同語言新聞文本之間的相似度。通過本文的研究可以發(fā)現(xiàn)利用新聞要素可以更好地表征一篇新聞文檔；此外，利用新聞要素作為跨語言橋梁，建立漢越雙語新聞圖模型，通過圖中節(jié)點(diǎn)的緊密程度表示新聞相似程度，采用基于信息傳遞的漢越雙語新聞圖聚類算法能夠有效地提高話題發(fā)現(xiàn)的效果。下一步工作將融合新聞主題句的關(guān)聯(lián)，提高漢越雙語話題發(fā)現(xiàn)的效果。

參考文獻(xiàn):

[1] Zhang Dan, Li Shengdong. Topic detection based on K-means[C]// International Conference on Electronics, Communications and Control. Ningbo, China:[s.n.], 2011:2983-2985.

[2] 趙華,趙鐵軍,于浩,等. 基于查詢向量的英語話題跟蹤研究[J].計算機(jī)研究與發(fā)展, 2007,44(8):1412-1417.

Zhao Hua, Zhao Tiejun, Yu Hao, et al. English topic tracking research based on query vector[J]. Journal of Computer Research and Development, 2007,44(8):1412-1417.

[3] Guo Xin, Xiang Yang, Chen Qian, et al. LDA-based online topic detection using tensor factorization[J]. Journal of Information Science, 2013, 39(4):459-469.

[4] Phan X H, Nguyen L M, Horiguchi S. Learning to classify short and sparse text & web with hidden topics from large-scale data collections[C]// International Conference on World Wide Web. Beijing, China:[s.n.], 2008:91-100.

[5] Zhao Wenqing, Hou Xiaoke. News topic recognition of Chinese microblog based on word co-occurrence graph[J]. CAAI Transactions on Intelligent Systems, 2012, 5: 444-449.

[6] Mathieu B, Fluhr C. Multilingual document clusters discovery[C]// Computer-assisted Information Retrieval. Avignon, France: [s.n.], 2004:116-125.

[7] Boyd-Graber J, Blei D M. Multilingual topic models for unaligned text[C]// Conference on Uncertainty in Artificial Intelligence. [S.l.]: AUAI Press, 2012:75-82.

[8] Mimno D, Wallach H M, Naradowsky J, et al. Polylingual topic models[C]// Conference on Empirical Methods in Natural Language Processing. Singapore: ACL, 2009:880-889.

[10] 楊啟悅, 余正濤, 洪旭東,等.基于維基百科的漢越詞語相似度計算[J].南京理工大學(xué)學(xué)報(自然科學(xué)版),2016,40(4):461-466.

Yang Qiyue, Yu Zhengtao, Hong Xudong, et al. Chinese-Vietnamese word similarity computation based on Wikipedia[J]. Journal of Nanjing University of Science and Technology, 2016,40(4):461-466.

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

[12] Cam Tu N, Xuan Hieu P, Thu Trang N. JVnTextPro: A Java-based Vietnamese text processing tool[EB/OL]. http: //jvntextpro.sourceforge.net/, 2010-1-1.

[13] Ni Xiaochuan, Sun Jiantao, Hu Jian, et al. Mining multilingual topics from Wikipedia[C]// International Conference on World Wide Web. Madrid, Spain:[s.n.], 2009:1155-1156.