李俊峰

（北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院，北京 100876）

多特征融合的新聞聚類相似度計(jì)算方法

李俊峰

（北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院，北京 100876）

隨著網(wǎng)絡(luò)的發(fā)展，互聯(lián)網(wǎng)已經(jīng)成為了最重要的新聞媒介。網(wǎng)絡(luò)上的新聞報(bào)道能廣泛傳播，對(duì)社會(huì)有著深刻的影響。因此互聯(lián)網(wǎng)新聞事件的監(jiān)督和挖掘分析，對(duì)政府，企業(yè)有著巨大的價(jià)值。在進(jìn)行新聞報(bào)道分析的時(shí)候，最為重要的任務(wù)之一就是把網(wǎng)絡(luò)上類別雜亂，來(lái)源廣泛的新聞進(jìn)行識(shí)別和歸類。新聞歸類主要是基于通用的聚類的方法，其中一項(xiàng)基本的技術(shù)就是新聞報(bào)道相似度計(jì)算。

根據(jù)需求不同，新聞聚類類別可以是一個(gè)事件，或者是一領(lǐng)域。本文針對(duì)事件的新聞報(bào)道聚類，提出了一種混合特征的相似度計(jì)算方法。采用了 Tf-Idf和n-gram結(jié)合的向量空間模型來(lái)得到文本相似度，再通過(guò)規(guī)則識(shí)別出新聞文本中的時(shí)間，地點(diǎn)等關(guān)鍵信息，進(jìn)行關(guān)鍵信息匹配度計(jì)算，最后再把兩個(gè)相似度結(jié)合作為最終匹配度。實(shí)驗(yàn)表明，混合特征的方法明顯提高了事件聚類的準(zhǔn)召率。

計(jì)算機(jī)應(yīng)用技術(shù)；話題發(fā)現(xiàn)；聚類；文本相似度

0 引言

隨著互聯(lián)網(wǎng)的發(fā)展和普及，網(wǎng)絡(luò)上信息體量呈指數(shù)增長(zhǎng)，深刻影響了人們的生活的各方面。同時(shí)越來(lái)越多的媒體都利用互聯(lián)網(wǎng)通過(guò)論壇、博客、微博等平臺(tái)發(fā)表新聞和評(píng)論，事件經(jīng)網(wǎng)絡(luò)傳播，能迅速得引起大量民眾關(guān)注，形成網(wǎng)絡(luò)熱點(diǎn)。在這種情況下，對(duì)互聯(lián)網(wǎng)新聞報(bào)道的監(jiān)督和分析無(wú)疑對(duì)企業(yè)和政府有著巨大的用處。然而相對(duì)的，互聯(lián)網(wǎng)上的信息大多是沒(méi)有經(jīng)過(guò)整合的，更為雜亂，不利于分析和整合。因此在做互聯(lián)網(wǎng)新聞報(bào)道分析，挖掘的時(shí)候，往往需要利用一些技術(shù)對(duì)新聞報(bào)道，話題進(jìn)行聚合，歸并。

根據(jù)需求不同，聚類類別可以是一個(gè)事件[1]，或者是一領(lǐng)域。本文針對(duì)事件的新聞報(bào)道聚類，提出了一種混合特征的相似度計(jì)算方法。新聞報(bào)道的聚合，即把報(bào)道內(nèi)容，報(bào)道事件相同的事件聚集在一起，所使用的技術(shù)核心是基于文本的聚類技術(shù)。常用的話題聚類方法有k-means，single-pass。在特征挖掘方面，文獻(xiàn)[2]則引入了凝聚層次聚類來(lái)提升聚類效果。文獻(xiàn)[3]提出了了基于標(biāo)簽的話題發(fā)現(xiàn)方法，根據(jù)Twitter中的hashtag的變化趨勢(shì)來(lái)發(fā)掘話題。無(wú)論使用哪種聚類方法，計(jì)算報(bào)道相似度都是聚類基礎(chǔ)，需要深入地挖掘特征來(lái)計(jì)算。計(jì)算報(bào)道相似度的策略對(duì)聚類的精確度有著極大地影響，本文從特征挖掘的角度出發(fā)，提出了融合多種特征的報(bào)道相似度方法，提高聚類的精確度。

1 報(bào)道文本聚類方法

聚類，即將數(shù)據(jù)對(duì)象分組成為多個(gè)類或者簇，在同一個(gè)簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差別較大。常用的聚類方法有混合高斯算法 GMM，k-means，層次聚類，single-pass聚類，譜聚類[4]。其中混合高斯算法GMM，k-means，譜聚類需要事先確定聚類類別 K。層次聚類，single-pass聚類則是通過(guò)相似度的閾值來(lái)劃分類別。

在新聞報(bào)道文本聚類的場(chǎng)景下，聚類的目的是將報(bào)道事件對(duì)象相同的文本聚合在一起，這種情況下聚類的類別也就是事件的個(gè)數(shù)，是無(wú)法通過(guò)經(jīng)驗(yàn)來(lái)事先估計(jì)得到的。因此在針對(duì)新聞報(bào)道做事件內(nèi)容聚類的時(shí)候，采用HAC層次聚類，single-pass聚類這些基于相似度閾值，而不需要確定類別數(shù)量的方法更為合適。

1.1 Single-pass聚類

Single-Pass算法又稱單通道法或單遍法,是一種增量聚類方法。Single-Pass算法需要按一定順序依次讀取數(shù)據(jù)，每次讀取的新樣本都和已有的類別進(jìn)行比較，如果與其中的某一類匹配，則歸到這一類中，否則創(chuàng)建新類[5]。

設(shè)新聞報(bào)道的樣本集合為 D = {d1, d2, d3,…,dk,…, dn},初始類集合C為空集，具體步驟如下：

第一步：從數(shù)據(jù)集讀入一個(gè)新的樣本di

第二步：以這個(gè)樣本構(gòu)建一個(gè)新的類Ck

第三步：計(jì)算它與類集合中每個(gè)類之間的距離，并選擇與它相似度最大的簇 Cj。如果 Ck和 Cj的相似度大于一定閾值F，合并Ck到類Cj中；否則，把Ck加入類集合C中。

第四步：重復(fù)一，二，三步直到所有數(shù)據(jù)處理完畢。

1.2 凝聚層次聚類模型

層次聚類算法(Hierarchical Clustering,簡(jiǎn)稱HAC)又稱為樹(shù)聚類算法,它使用數(shù)據(jù)的聯(lián)接規(guī)則,透過(guò)一種層次架構(gòu)方式,反復(fù)將數(shù)據(jù)進(jìn)行分裂或聚合,以形成一個(gè)層次序列的聚類問(wèn)題解[6]。層次聚類可分為凝聚的，分裂的兩種方案。凝聚的層次聚類，就是首先把每對(duì)象設(shè)為一個(gè)類別，再根據(jù)條件迭代合并。分裂的層次聚類則相反，首先把所有對(duì)象歸為同一個(gè)類別，再迭代地去分裂類別。

在本文中采用凝聚層次聚類模型，設(shè)新聞報(bào)道的樣本集合為D={d1, d2, d3,…, dk,…, dn}聚類的基本步驟[7]就是：

第一步：把每個(gè)樣本自身歸為一類，設(shè)類集合為C={C1, C2, C3,…, Ci,…, Cn}，初始時(shí)每個(gè)類的元素只有一個(gè)，即Ci={di}。

第二步：計(jì)算兩兩之間的相似度分?jǐn)?shù)，Sij=Sim{Ci,Cj}。

第三步：選擇出結(jié)果中最大相似度分?jǐn)?shù)Sij對(duì)應(yīng)的兩個(gè)類 Ci和 Cj，把他們合并為一個(gè)新類 C′=Ci∪Cj，此時(shí)類別集合變?yōu)?C={C1, C2, C3,…, Ci,…, Cn-1}。

第四步：重復(fù)二，三步直到所有樣本點(diǎn)都?xì)w為一類，或者最大相似度Sij小于一定的閾值F。

Single-pass和凝聚層級(jí)聚類都使用于無(wú)法確定類別數(shù)量K的聚類的情況，都適合用于新聞報(bào)道的聚類，但是兩者的使用場(chǎng)景也有所不同。Single-pass是增量聚類，適合用于進(jìn)行實(shí)時(shí)的聚類，數(shù)據(jù)需要有一定的時(shí)序?qū)傩?，方法?jiǎn)單但是聚類精確度不高。而層級(jí)聚類HAC則是非增量的聚類方法，計(jì)算復(fù)雜度高，但是一般情況下精確度也比較好。

2 新聞報(bào)道文本相似度計(jì)算

相似度的計(jì)算是聚類的基礎(chǔ)，在本文主要考慮文本信息，根據(jù)文本提取特征計(jì)算相似度。提取文本特征最常用的處理方法就是建立基于 TF-IDF的向量空間模型。

2.1 向量空間模型

向量空間模型（Vector Space Model，簡(jiǎn)稱VSM）的基本思想是以向量來(lái)表示文本，用空間距離體現(xiàn)語(yǔ)義相似度[8]。對(duì)一篇新聞文檔 D，其向量可表示為式（1）：

其中ti表示第i個(gè)特征，取值為0或1，wi則代表這個(gè)特征對(duì)應(yīng)的特征權(quán)重。

對(duì)于向量化后的特征，最常用計(jì)算相似度方法就是余弦相似度，表示為式（2）：

2.1.1 TF-IDF

TF-IDF（term frequency-inverse document frequency）是一種常用的文本處理中的權(quán)重計(jì)算方法[9]，TF意思是詞頻（Term Frequency），IDF意思是逆向文件頻率（Inverse Document Frequency）。其思想就是，在一篇文檔中，某個(gè)字詞的重要性和它在本文檔出現(xiàn)的次數(shù)成正比，和它在語(yǔ)料庫(kù)出現(xiàn)的總頻率成反比。

詞頻（Term Frequency）計(jì)算公式如式（3）所示：

其中nij是詞在文檔中的出現(xiàn)次數(shù)，而分母則是在文檔中包含的總字詞數(shù)。

逆向文件頻率（Inverse Document Frequency）計(jì)算公式如式（4）所示：

其中|D|為語(yǔ)料庫(kù)中的文件總數(shù)。如果用TFIDF于計(jì)算新文檔，且此文檔時(shí)包含詞語(yǔ) 如果該詞語(yǔ)不在原語(yǔ)料庫(kù)中，就會(huì)導(dǎo)致被除數(shù)為零。此時(shí)可以把分母項(xiàng)加1，做平滑處理，公式變?yōu)槭剑?）：

最終的TF-IDF值為式（6）：

在特定文檔內(nèi)的高詞頻，以及該在整個(gè)文件集合中的低文檔頻率的詞語(yǔ)，能得到高權(quán)重的TF-IDF值。因此，TF-IDF傾向于過(guò)濾掉過(guò)于常見(jiàn)的詞語(yǔ)，保留重要的詞語(yǔ)。

TF-IDF是基于詞頻角度挖掘的文本特征，忽略了詞之間的鄰近順序等重要信息，沒(méi)有完全提取原有文檔的語(yǔ)義特征，因此本文將n-gram語(yǔ)言模型也結(jié)合在一起，挖掘更多的特征。

2.1.2 n-gram語(yǔ)言模型

語(yǔ)言模型就是用來(lái)計(jì)算一個(gè)句子的概率的模型，即 P（W1, W2,…Wk）。n-gram 模型也稱為 n-1階馬爾科夫模型，它有一個(gè)有限歷史假設(shè)：當(dāng)前詞的出現(xiàn)概率僅僅與前面n-1個(gè)詞相關(guān)。

n-gram在特征提取中，則可以看做提取當(dāng)前詞語(yǔ)與后繼 n-1個(gè)詞語(yǔ)所組成的短語(yǔ)[10]。例如使用2-gram，設(shè)文檔為D = {w1, w2, w3}，wi為其中的詞，則可以提取出特征詞組合T = {w1w2,w2w3}。

n-gram實(shí)質(zhì)上枚舉了所有可能的組合，但是其中有大量組合是非法的，這樣直接使用會(huì)加大模型的空間復(fù)雜度，并且影響相似度計(jì)算，因此必須要做詞組的過(guò)濾。通常的方法就是基于詞頻進(jìn)行過(guò)濾，對(duì)于詞組頻率小于一定閾值的直接舍棄。

例如“現(xiàn)場(chǎng)濃煙滾滾，消防官兵到達(dá)后開(kāi)始緊急救火，由于火勢(shì)較大，多部門聯(lián)合指揮滅火行動(dòng)。事故原因和人員傷亡情況有待進(jìn)一步調(diào)查。”，當(dāng)使用n-gram提取時(shí)，可以提取出“事故原因”，“人員傷亡”，“滅火行動(dòng)”，“濃煙滾滾”，“消防官兵”等詞組特征。

2.1.3 向量空間特征組合

設(shè)原始分詞后為，句子的詞向量為：

n為語(yǔ)料庫(kù)詞數(shù)量，當(dāng)ti=1，代表本句中包含這個(gè)詞，ti=0則為不包含。

設(shè)通過(guò)公式（6）計(jì)算得到的特征的 TFIDF權(quán)重向量為（未出現(xiàn)的詞直接置0）：

在n-gram提取和過(guò)濾處理后，得到句子的詞組向量為：

n為語(yǔ)料庫(kù)詞數(shù)量，當(dāng)ti=1，代表本句中包含這個(gè)詞組，ti=0則為不包詞組。對(duì)n-gram的詞組也進(jìn)行TFIDF值計(jì)算，得到得到TFIDF權(quán)重向量為：

最后權(quán)重向量特征可以合并在一起，得到組合的特征向量，即為：

文本相似度則取特征向量的余弦值,表示為：

2.2 關(guān)鍵信息點(diǎn)匹配

部分描述的空間向量模型主要是基于詞，詞組特征進(jìn)行建模，但是對(duì)于新聞報(bào)道類聚合的相似度計(jì)算，除了單純的詞，詞組特征還有一些特有的信息點(diǎn)可以提取。新聞和報(bào)道一般都會(huì)包含時(shí)間，地點(diǎn)，人物等等要素，統(tǒng)一件事件，無(wú)論用什么方法去描述，它的這些要素都是不變的。因此這些關(guān)系的信息點(diǎn)可以看做比較顯著特征，可以做單獨(dú)處理，進(jìn)行更為細(xì)致的匹配。本文主要對(duì)時(shí)間和地點(diǎn)進(jìn)行匹配，在進(jìn)行相應(yīng)的相似度計(jì)算。

2.2.1 時(shí)間關(guān)鍵詞匹配

在時(shí)間關(guān)鍵詞匹配中，由于文本中的時(shí)間信息是非格式化的，無(wú)法直接去匹配，需要首先進(jìn)行時(shí)間詞識(shí)別，按一定的規(guī)則模板抽取出其中的時(shí)間信息。時(shí)間關(guān)鍵詞可分為表示年月日的日期關(guān)鍵詞Td，和表示小時(shí)或者時(shí)段的時(shí)刻關(guān)鍵詞Tt，分別進(jìn)行提取。

對(duì)于日期關(guān)鍵詞，具體分為以下幾類：

數(shù)字類，例如“12日”，“7月2日”：對(duì)于此類使用模板進(jìn)行正則匹配提取，例如“*月*日”，其中“*”代表通配符。

相對(duì)日期，例如“昨天”，“明天”：對(duì)于此類的關(guān)鍵詞不多，所以可以直接使用關(guān)鍵詞匹配。

在抓取新聞文本的時(shí)候基本都可以得到新聞的發(fā)布時(shí)間，對(duì)于相對(duì)日期，可以通過(guò)簡(jiǎn)單的日期加運(yùn)算得到具體的時(shí)間。

對(duì)于時(shí)刻關(guān)鍵詞，分為以下幾類：

數(shù)字類，例如“8點(diǎn)12分”，“十時(shí)十二分”：對(duì)于此類使用模板進(jìn)行正則匹配提取，例如“*點(diǎn)*分”。

模糊時(shí)刻，例如“上午”，“下午”：對(duì)于此類的關(guān)鍵詞不多，所以可以直接使用關(guān)鍵詞匹配。在記錄的時(shí)候同時(shí)歸一化為一定的時(shí)間范圍，例如上午對(duì)應(yīng)8-12點(diǎn)。

在識(shí)別時(shí)間詞后，根據(jù)時(shí)間詞計(jì)算匹配。設(shè)文檔集合為D = {D1, D2, D3,…,Dk,…,Dn}，對(duì)其中兩文檔Di和Dj，對(duì)應(yīng)的日期詞，時(shí)刻詞分別為Tdi和Tdj，Tti和Ttj。采用以下策略計(jì)算時(shí)間詞匹配相似度St。

第一步：初始化St= 0。

第二步：如果日期詞Tdi或者Tdj有一個(gè)缺省，直接到第三步。否則對(duì)日期詞進(jìn)行匹配，如果Tdi=Tdj，則匹配得分累加為St=St+St1；如果不匹配，這令St=St-St1，并直接結(jié)束。

第三步：如果時(shí)刻詞 Tti或者 Ttj有一個(gè)缺省，直接結(jié)束。否則對(duì)時(shí)刻詞進(jìn)行匹配，如果 Tti=Ttj，則匹配得分累加為 St=St+St2；如果不匹配，這令St=St-St2。如果含有模糊時(shí)刻詞，且匹配成功（即落在時(shí)刻段范圍內(nèi)），則匹配得分累加為St=St+St3；如果不匹配，這令St=St-St3。

其中St1，St2，St3，為三個(gè)匹配分?jǐn)?shù)，本文中取0.4，0.4，0.2。

2.2.2 地點(diǎn)關(guān)鍵詞匹配

地點(diǎn)關(guān)鍵詞種類比較多，有“上?！?，“北京”這類的省市地點(diǎn)詞，也有“商場(chǎng)”，“工廠”等場(chǎng)所詞，還可以是“101號(hào)公路”等等更具體的地點(diǎn)詞。由于很多地點(diǎn)詞存在歧義，而省市地點(diǎn)詞一般比較固定，因此在本文只選擇省市地點(diǎn)詞做匹配。

地點(diǎn)關(guān)鍵詞提?。菏紫雀鶕?jù)中國(guó)省，市名，以及對(duì)應(yīng)的區(qū)建立3層級(jí)詞表。格式為：

北京（省級(jí)）-北京（市級(jí)）-海淀區(qū)（區(qū)級(jí)）

通過(guò)詞匹配提取文中的地點(diǎn)詞，得到3個(gè)層級(jí)的地點(diǎn)詞，省Pp，市Pc和區(qū)Pa。如果匹配不到則設(shè)為空，如果省級(jí)信息為空，市級(jí)信息非空，則根據(jù)層級(jí)關(guān)系填充省信息。

設(shè)文檔集合為 D = {D1, D2, D3,…, Dk,…, Dn}，對(duì)其中兩文檔Di和Dj，對(duì)應(yīng)的省，市，區(qū)關(guān)鍵詞分別為 Ppi和 Ppj，Pci和 Pcj，Pdi和 Pdj。采用以下策略計(jì)算地點(diǎn)詞匹配相似度St。

第一步：初始化Sp= 0

第二步：匹配省級(jí)，如果Ppi，Ppj都不缺?。喝绻?Ppi==Ppj，則 Sp=Sp+Sp1；否則 Sp=Sp-Sp1,直接結(jié)束；

第三步：匹配市級(jí)，如果Pci，Pcj都不缺省：如果 Pci==Pcj，則 Sp=Sp+Sp2；否則 Sp=Sp-Sp2,直接結(jié)束；

第四步：匹配區(qū)級(jí)，如果Pdi，Pdj都不缺?。喝绻?Pdi==Pdj，則 Sp=Sp+Sp3；否則 Sp=Sp-Sp3，其中 Sp1，Sp2，Sp3，為三個(gè)匹配分?jǐn)?shù)，本文中取 0.2，0.5，0.3。

2.3 混合特征相似度計(jì)算

結(jié)合向量空間模型中的詞和ngram特征，以及關(guān)鍵信息點(diǎn)匹配的特征，得到總的文本相似度公式為：

其中α,β,δ為權(quán)重參數(shù)，本文中取0.7，0.15，0.15。

3 實(shí)驗(yàn)

為了驗(yàn)證混合特征聚類方法的有效性，使用網(wǎng)絡(luò)爬蟲(chóng)，基于微博的檢索功能，抓取了新浪微博上面大約2000條關(guān)于電梯故障或事故的新聞報(bào)道，并進(jìn)行人工標(biāo)注，歸類新聞。在實(shí)驗(yàn)中n-gram的n值取 2。在經(jīng)過(guò)分詞，去停用詞處理后，分別使用基于TF-IDF的向量空間模型，TF-IDF和2-gram的向量空間模型，混合VSM和信息點(diǎn)匹配的策略進(jìn)行報(bào)道相似度的計(jì)算。計(jì)算出相似度后，使用凝聚層次聚類HAC的方法進(jìn)行聚類。

在評(píng)價(jià)聚類結(jié)果的時(shí)候，采用一般信息檢索常用的標(biāo)準(zhǔn)：準(zhǔn)確率，召回率。準(zhǔn)確率，召回率計(jì)算方法可表示：

其中Pi為實(shí)際類標(biāo)記為i樣本，Ci為機(jī)器標(biāo)記為i的樣本。

在評(píng)價(jià)聚類的時(shí)候涉及一個(gè)標(biāo)簽對(duì)應(yīng)的問(wèn)題：在人工標(biāo)注的時(shí)候標(biāo)記的編號(hào)，和程序自動(dòng)聚類時(shí)候打的編號(hào)需要一一對(duì)應(yīng)。這里基于人工標(biāo)簽，采用貪心地方法進(jìn)行對(duì)應(yīng)，這時(shí)準(zhǔn)召率計(jì)算方法如下：

標(biāo)簽匹配：設(shè)人工標(biāo)簽的類標(biāo)簽為 L={L1, L2,L3…}，程序聚類的類標(biāo)簽為M={M1, M2, M3…}，令L∩M={}。對(duì)于每一個(gè)人工標(biāo)簽的類Li，遍歷其中的樣本，找出其中數(shù)量最多的程序標(biāo)注類Mk，然后把 Mk映射到 Li。例如，設(shè)第 Li個(gè)人工標(biāo)注類中程序標(biāo)注類標(biāo)簽為{1，2，3，2，2}，其中樣本數(shù)量最多的程序標(biāo)注類對(duì)應(yīng)的標(biāo)簽為 2，則人工標(biāo)簽 Li與程序標(biāo)簽2對(duì)齊，把程序類標(biāo)簽2映射到Li上。按此策略處理所有人工標(biāo)簽類，直到每個(gè)都找到匹配。每個(gè)程序標(biāo)簽的類不一定能匹配上人工標(biāo)簽類，這種情況會(huì)在計(jì)算召回率的時(shí)候受到懲罰。

計(jì)算準(zhǔn)確率：Ci為人工標(biāo)注類為i的樣本個(gè)數(shù)，Pi∩Ci則為這些樣本中映射為 i的程序標(biāo)注類的樣本數(shù)量，即準(zhǔn)確率為一個(gè)人工標(biāo)注類里面最大程序標(biāo)注類數(shù)量的的占比。例如，設(shè)第 i個(gè)人工標(biāo)注類中程序標(biāo)注類標(biāo)簽為{1，2，3，2，2}，人工標(biāo)注類Ci數(shù)量為 5，其中樣本數(shù)量最多的程序標(biāo)注類對(duì)應(yīng)的標(biāo)簽為2，即人工標(biāo)簽i與程序標(biāo)簽2對(duì)齊，程序標(biāo)簽2數(shù)量為3，因此準(zhǔn)確率為3/5=60%。

計(jì)算召回率：設(shè)Pi為類標(biāo)簽映射為i程序標(biāo)注類的樣本個(gè)數(shù)，Pi∩Ci則為這些樣本中人工標(biāo)注類為i的樣本個(gè)數(shù)。例如,設(shè)標(biāo)簽映射為2的程序標(biāo)注類中人工標(biāo)注類標(biāo)簽為{1，2，2，2，2}，程序標(biāo)注映射為2的類的樣本總數(shù)量為5，其中人工標(biāo)簽為2的樣本數(shù)量為 4，因此準(zhǔn)確率為 4/5=80%。如果一個(gè)程序標(biāo)注類沒(méi)有映射，即沒(méi)有匹配上人工標(biāo)注類，則令召回率為0。

基于凝聚層次聚類的算法需要事先確定聚類閾值 T，因此實(shí)驗(yàn)中設(shè)置不同的閾值 T分別對(duì)基于TFIDF，基于TFIDF+2gram，基于混合特征的三種相似度計(jì)算方法進(jìn)行實(shí)驗(yàn)，得到實(shí)驗(yàn)數(shù)據(jù)如表1所示.

在實(shí)驗(yàn)中閾值比較大時(shí)，準(zhǔn)確率變得很高，因?yàn)楫?dāng)閾值過(guò)大的時(shí)候，劃分為一個(gè)類的標(biāo)準(zhǔn)變得很嚴(yán)格，一個(gè)類的樣本變得很小，準(zhǔn)確率保持比較高，但是同時(shí)召回率會(huì)降低。

從實(shí)驗(yàn)可以看出，加入n-gram詞組后的向量空間模型一定程度上提升了聚類效果，通過(guò)分析差異樣本時(shí)發(fā)現(xiàn)n-gram提取的一些詞組，類似于“購(gòu)物中心”,”腰椎骨折”,”廢棄工地”，比較起“購(gòu)物”，“中心”,”腰椎”，“骨折”等詞來(lái)看有更強(qiáng)的區(qū)別度，能對(duì)聚類有很大幫助。與基于單獨(dú)的TFIDF模型相比，基于n-gram和TFIDF組合的模型隨T曲線中，峰值出現(xiàn)比較早，這是因?yàn)?-gram的詞組比單詞匹配的頻率要更低，而余弦值總是在0～1之間，所以基于n-gram和TFIDF組合的模型計(jì)算出來(lái)的相似度總體偏低，用比較小的閾值T可以得到更好的效果。

表1 聚類準(zhǔn)確率Tab.1 Accuracy rate

表2 聚類召回率Tab.2 Recall rate

采用向量空間模型和信息點(diǎn)匹配結(jié)合的混合特征模型得到了最好的效果，對(duì)召回率的提升最為明顯，另外受閾值影響產(chǎn)生的波動(dòng)比較小，更有魯棒性。因?yàn)榛谠~和基于信息點(diǎn)的特征匹配可以很好地互補(bǔ)：對(duì)于時(shí)間，地點(diǎn)這些信息點(diǎn)沒(méi)有缺失的情況下，一旦匹配上相似度會(huì)很大，從而可以保證精準(zhǔn)召回。而在這些特定信息缺少的情況下，向量空間模型可以從語(yǔ)義上進(jìn)行補(bǔ)充。

4 結(jié)論

本文提出了一種使用混合特征進(jìn)行新聞報(bào)道聚類的方法，在傳統(tǒng)的基于TFIDF的向量空間特征上加入了n-gram特征；并針對(duì)新聞報(bào)道的特點(diǎn)提取了關(guān)鍵信息點(diǎn)，把信息點(diǎn)匹配和向量空間模型進(jìn)行組合，從而可以使用多種特征計(jì)算相似度。實(shí)驗(yàn)結(jié)果表明，采用混合特征能明顯地提高新聞報(bào)道聚類效果。

[1] Li B. Research on Topic Detection and Tracking[J].Computer Engineering & Applications, 2003.

[2] Cui A, Zhang M, Liu Y, et al. Discover breaking events with popular hashtags in twitter[C].

[3] Yang Y, Pierce T, Carbonell J. A study of retrospective and on-line event detection.

[4] Everitt B. Cluster analysis[J]. Quality & Quantity, 1980,14(1): 75-100.

[5] 稅儀冬, 瞿有利, 黃厚寬. 周期分類和Single-Pass聚類相結(jié)合的話題識(shí)別與跟蹤方法[J]. 北京交通大學(xué)學(xué)報(bào), 2009,33(5): 85-89.Yi-Dong Shui, You-Li Qu, Hou-Kuan Huang. A New Topic Detection and Tracking Approach Combining Periodic Classification and Single-Pass Clustering. Journal of Beijing Jiaotong University [J] , 2009, 33(5): 85-89.

[6] 孫吉貴, 劉杰, 趙連宇. 聚類算法研究[J]. 軟件學(xué)報(bào), 2008,19(1):48-61.SUN Ji-Gui, LIU Jie, ZHAO Lian-Yu. Clustering Algorithms Research. Journal of Software, Vol.19, No.1, January 2008,pp. 48-61.

[7] Johnson S C. Hierarchical clustering schemes[J]. Psychometrika,1967, 32(3): 241-254.

[8] 龐劍鋒, 卜東波. 基于向量空間模型的文本自動(dòng)分類系統(tǒng)的研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用研究, 2001, 18(9): 23-26.PANG Jian-feng, BU Dong-bo, BAI Shuo. Research and Implementation of Text Categorization System Based on VSM[J].Application Research of Computers, 2001, 18(9): 23-26.

[9] Shi C Y, Chao-Jun X U, Yang X J. Study of TFIDF algorithm[J]. Journal of Computer Applications, 2009.

[10] Urnkranz J F. A Study Using n-gram Features for Text Categorization[J]. Oesterreichisches Forschungsinstitut Artificial Intelligence, 1998, 3.

A Similarity Calculation for News Clustering with Mixed

LI Jun-feng
(Institute of Network Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China)

With the development of network technology,Internet have become the most important news media.The news in the Internet could be widespread and have profound influence on the society. Thus, the analysis and supervision of online news is valuable to government and company. One of the most important tasks in the analysis of online news and reports is identifying and classifying those news and reports. News and reports classifying base on general classification technologies, and a basic technology of them is the computation of news similarity.

The "class" in news classification could be an event or a field, according to different requirements. In the thesis, a algorithm of computing news and report similarity for events clustering with mixed feature is designed. This method apply both Tf-Idf and n-gram in vector space model (VSM). Furthermore, it abstracts some key information of news,such as time and place, calculating key information similarity using those information. In the end,combe those two similarity as final similarity. The experiment show that this method improve the accuracy and recall rate though mixing features.

Computer application technology; Topic detection; Clustering; Text similarity

TP391.3

A

10.3969/j.issn.1003-6970.2017.12.032

本文著錄格式：李俊峰. 多特征融合的新聞聚類相似度計(jì)算方法[J]. 軟件，2017，38（12）：170-174

李俊峰(1992-)，男，研究生，研究方向：自然語(yǔ)言處理。