肖融，孔亮，張巖

(北京大學(xué)教育部機(jī)器感知重點(diǎn)實(shí)驗(yàn)室，北京100871)

人們生活在信息時(shí)代，每天都在接收大量的信息，從各種媒體渠道瀏覽各種新聞事件.有些新聞事件只有基于事件本身的客觀性報(bào)道，比如《哈利波特7》上映，莫斯科發(fā)生大規(guī)模球迷騷亂，歐盟呼吁歐洲共同應(yīng)對(duì)危機(jī)等.這類新聞報(bào)道主要是對(duì)所發(fā)生的新聞事實(shí)進(jìn)行客觀描述，一般所有的報(bào)道都相近似，不會(huì)眾說(shuō)紛紜.而有一些新聞事件由于具有開(kāi)放性或者模糊性，導(dǎo)致各方面口徑不一，就會(huì)出現(xiàn)所謂的“羅生門”現(xiàn)象.比如流行天王Michael Jackson的死因，有報(bào)道說(shuō)是心臟病意外死亡，有報(bào)道稱是自殺，有報(bào)道稱是私人醫(yī)生誤殺或謀殺等.再比如對(duì)于韓國(guó)天安艦沉船事件，有報(bào)道稱是朝鮮所為，有報(bào)道稱是美國(guó)的陰謀，還有報(bào)道說(shuō)是南北交火時(shí)沉沒(méi)等.這一類新聞事件的眾多報(bào)道就會(huì)出現(xiàn)對(duì)于同一事件有多個(gè)不同版本說(shuō)法的現(xiàn)象，也就是本文所研究的多版本事件.

隨著話題發(fā)現(xiàn)與追蹤技術(shù)(topic detection and tracking，TDT)［1-2］的發(fā)展日益成熟，很多網(wǎng)站都可以提供為用戶組織歸納新聞事件的應(yīng)用.通過(guò)話題發(fā)現(xiàn)與追蹤，用戶可以清楚地知道新聞事件的發(fā)生和衍化過(guò)程，也可以看到關(guān)于事件的各種報(bào)道.TDT源于1996年美國(guó)國(guó)防高級(jí)研究計(jì)劃委員會(huì)提出的需要一種能自動(dòng)確定新聞報(bào)道流中話題結(jié)構(gòu)的技術(shù)［3-5］.隨后，DARPA、卡內(nèi)基·梅隆大學(xué)、Dragon系統(tǒng)公司以及馬薩諸塞大學(xué)的研究人員定義了TDT的相關(guān)內(nèi)容，并檢驗(yàn)信息檢索中基于主題的技術(shù)在TDT中的應(yīng)用情況，這些研究及評(píng)測(cè)被命名為TDT pilot［6］.TDT是一項(xiàng)綜合的技術(shù)，需要較多的自然語(yǔ)言處理理論和技術(shù)作為支撐.話題發(fā)現(xiàn)技術(shù)可以看作是一種按事件的聚類，研究者常采用的算法有agglomerative聚類、增量K-means聚類、增量聚類等.話題追蹤的常用技術(shù)有Rocchio分類方法、決策樹(shù)方法、基于HMM的語(yǔ)言模型等［7-10］.

然而，對(duì)于多版本的新聞事件，簡(jiǎn)單的組織歸納難以滿足用戶對(duì)于不同版本報(bào)道的信息獲取的需求.對(duì)于存在多個(gè)版本的事件，讀者很難面對(duì)龐大的新聞數(shù)據(jù)而自行鑒別事件的版本，如果存在一個(gè)算法可以為讀者找出一共存在多少個(gè)版本，每一個(gè)版本的描述是什么，那么對(duì)于讀者獲取相關(guān)新聞信息將會(huì)十分有用.

遺憾的是，目前關(guān)于事件多版本發(fā)現(xiàn)的研究很少，沒(méi)有太多有價(jià)值的相關(guān)文獻(xiàn).對(duì)于多版本發(fā)現(xiàn)最直接的考慮就是進(jìn)行簡(jiǎn)單的聚類分析.聚類是數(shù)據(jù)挖掘技術(shù)中極為重要的組成部分，是在事先不規(guī)定分組規(guī)則的情況下，將數(shù)據(jù)按照其自身特征劃分成不同的簇(cluster)，不同簇的數(shù)據(jù)之間差距越大、越明顯越好，而每個(gè)簇內(nèi)部的數(shù)據(jù)之間要盡量相似，差距越小越好.常見(jiàn)的聚類算法有 K-means算法、Birch算法、Dbscan算法、Clique算法、神經(jīng)網(wǎng)絡(luò)方法等［11-14］.但是單純的聚類方法具有很多局限性.由于對(duì)于同一事件的新聞報(bào)道在內(nèi)容主體上通常具有高度的相似性，簡(jiǎn)單的聚類方法無(wú)法將其中不同的“聲音”有效地區(qū)分開(kāi)來(lái).文獻(xiàn)［15］提出了一種基于圖模型的事件多版本發(fā)現(xiàn)算法.該算法是基于語(yǔ)義的迭代算法，通過(guò)提取流行詞并將之過(guò)濾來(lái)降低同一特定事件的文檔之間的緊密聯(lián)系性.然后構(gòu)建詞圖以發(fā)現(xiàn)詞與詞之間的層次關(guān)系.根據(jù)社區(qū)發(fā)現(xiàn)算法［16］，構(gòu)建虛擬文檔來(lái)表示每一版本的中心.最后根據(jù)Rocchio分類算法［17］來(lái)進(jìn)行多版本的分類.

盡管本文在內(nèi)容上借鑒上述一些前人的工作，但無(wú)論從算法思想還是效果上都有很大創(chuàng)新.一方面，它提出了話題層的概念，建立了文檔集與話題層的映射關(guān)系，利用LDA將文檔集合引申到話題空間，然后對(duì)每一話題進(jìn)行特征提取.另一方面，它提出了一種有效的提取高區(qū)分度特征的方法.該方法過(guò)濾掉了文本集之間相似性的部分，有效地提取出文檔集之間的差異性特征，從而提高多版本發(fā)現(xiàn)的效率和準(zhǔn)確度.

1 基本定義

關(guān)于事件的多版本發(fā)現(xiàn)，這里首先要討論的就是一個(gè)有效的事件多版本發(fā)現(xiàn)算法需要具備的性質(zhì).并且，為了使多版本發(fā)現(xiàn)的工作更有意義，本文認(rèn)為這樣的算法必須是足夠強(qiáng)健的(qualitatively strong)［18］.

首先，這里先要聲明幾個(gè)符號(hào)表示的意義.令D={di，di+1，…，dn}表示對(duì)于某一特定新聞事件所搜集的n個(gè)文檔的集合，其中每一篇文檔di，i=1:n，用 bag of words表示(w1，w2，…，wd).多版本發(fā)現(xiàn)的目標(biāo)在于發(fā)現(xiàn)m個(gè)不同的版本V={v1，v2，…，vm}來(lái)描述一個(gè)事件，其中每一種版本vi(i=1:m)，用一種詞的分布表示.對(duì)于某一事件的多版本發(fā)現(xiàn)也就是找到關(guān)于這一事件的不同方面、不同說(shuō)法或不同觀點(diǎn)等，讓用戶能夠一目了然地看到這一事件的不同角度和層面.

為了得到有效的多個(gè)版本描述，一個(gè)關(guān)于新聞事件的多版本發(fā)現(xiàn)算法需要滿足以下3個(gè)特性:

1)多樣性.即給定一個(gè)文檔集合D作為輸入，多版本發(fā)現(xiàn)算法需要在不改變相似度函數(shù)的情況下，找到m(m＞1)個(gè)不同的版本 vi，i=1:m.也就是說(shuō)算法不依賴于相似度函數(shù)的形式.

2)區(qū)別性.得到的每一個(gè)版本vi(i=1:m)應(yīng)該是顯著不同的.這里指的是任意2個(gè)版本之間應(yīng)該具有高度不相似度.

3)高質(zhì)性.得到的每一個(gè)版本vi(i=1:m)應(yīng)該是關(guān)于相似度函數(shù)表現(xiàn)強(qiáng)健的(qualitatively strong).

可以證明，本文介紹的多版本發(fā)現(xiàn)算法滿足以上提到的多樣性、區(qū)別性和高質(zhì)性.

2 CDW:基于文本的事件多版本發(fā)現(xiàn)模型

2.1 CDW算法框架

CDW(clustering by highly-differentiated words)對(duì)于事件的多版本發(fā)現(xiàn)，最樸素、最直接的做法就是對(duì)文檔進(jìn)行簡(jiǎn)單的聚類.然而，由于大數(shù)據(jù)集文檔間存在復(fù)雜的語(yǔ)義關(guān)聯(lián)和高度的相似性，僅僅簡(jiǎn)單的聚類方法無(wú)法得到區(qū)分度高的版本類別，“區(qū)別性”方面的表現(xiàn)很差.為了解決這個(gè)問(wèn)題，本文提出的CDW事件多版本發(fā)現(xiàn)算法將整個(gè)問(wèn)題分為2部分:首先，需要找到具有高區(qū)分度的特征;其次，將文檔進(jìn)行特征向量化，并且進(jìn)行文本聚類.進(jìn)一步具體分析，本文算法可以分為以下3步:

1)尋找區(qū)分度高的特征.每一篇文檔都可以被表示成a bag of words，對(duì)于大數(shù)據(jù)集來(lái)說(shuō)，不經(jīng)篩選無(wú)疑會(huì)造成維數(shù)災(zāi)難.為了得到更利于區(qū)分文檔的特征并去掉干擾噪音，本算法將文檔集引申到話題層，通過(guò)運(yùn)用詞頻過(guò)濾和提取popular words等方法，對(duì)特征進(jìn)行篩選和降維，最終得到區(qū)分度較高的特征.

2)特征向量化，構(gòu)建處理后的文檔.需要將所有文檔用經(jīng)過(guò)篩選的高區(qū)分度特征進(jìn)行向量化表示.這里，本算法利用的是TF-IDF加權(quán)技術(shù)［19］.

3)文本聚類.經(jīng)過(guò)特征篩選和特征表示，已經(jīng)得到了經(jīng)過(guò)處理的文檔特征向量.然后，用K-means方法［20］進(jìn)行文本聚類，得到最終的多版本.

圖1展示了CDW算法的流程框架.下面將對(duì)這3步做進(jìn)一步具體說(shuō)明.

圖1 CDW算法框架Fig.1 The framework of CDW algorithm

2.2 高區(qū)分度特征的生成策略

詞匯是文檔最基礎(chǔ)的組成單元，也是最常用的特征表示.然而，如果將一篇文檔包含的所有詞語(yǔ)都作為這篇文檔的特征，那么對(duì)于大數(shù)據(jù)集來(lái)說(shuō)可能會(huì)造成維數(shù)災(zāi)難.所以，必須提取出對(duì)于區(qū)分文檔版本最有效的詞語(yǔ)，以進(jìn)行降維.

2.2 .1 根據(jù)詞頻過(guò)濾公共詞

詞頻過(guò)濾是進(jìn)行特征篩選時(shí)最基礎(chǔ)的手段.經(jīng)過(guò)分析可知，對(duì)于同一事件的文檔集中頻率較高的詞通常是描述客觀事件本身的詞，并不具有版本信息.所以，本算法首先統(tǒng)計(jì)數(shù)據(jù)集中的每一個(gè)詞出現(xiàn)在文檔中的數(shù)目作為這個(gè)詞的頻率.這里設(shè)定一個(gè)閾值d，將頻率高于閾值d的詞全部篩掉.另外也過(guò)濾掉頻率為1的詞.

2.2 .2 基于LDA分析的話題映射與聚類

本算法利用LDA分析［21-23］對(duì)詞頻過(guò)濾后的特征集進(jìn)行進(jìn)一步特征提取，這樣做的目的是進(jìn)一步降維，并且將文檔集映射到不同的話題.然后，對(duì)文檔集進(jìn)行聚類.這樣，就得到了文檔的初步類別信息.

方法步驟如下［24］:

1)初始化.確定K的值，以及抽樣數(shù)目和參數(shù).進(jìn)行LDA分析，得到詞-話題矩陣.

2)矩陣每一行為一個(gè)詞的特征向量，對(duì)其進(jìn)行聚類.

首先，利用LDA分析將文檔集映射到話題層.

給定一個(gè)文檔集合D，每個(gè)文檔d包含一個(gè)詞序列{w1，w2，…，wn}.在集合 D 對(duì)應(yīng)的 LDA 模型中，首先假設(shè)話題數(shù)目固定為K，然后經(jīng)過(guò)LDA分析得到每個(gè)文檔屬于每個(gè)話題的概率.

然后進(jìn)行文本聚類.在LDA分析后，獲得一個(gè)詞-話題的矩陣，每一行是詞在文本上的分布，每行有K維.之后把詞的特征向量進(jìn)行聚類，根據(jù)最大隸屬原則，將每篇文章劃為概率最大的話題.這樣就完成了文檔集到話題層的映射.

2.2 .3 popular words的提取算法

通過(guò)之前2步對(duì)特征集的降維和提取，至此已經(jīng)將文檔集進(jìn)行了話題的映射并且得到了初步的聚類結(jié)果.現(xiàn)在，需要對(duì)每一類進(jìn)行提取popular words，從而得到每一類最具代表性的詞.這里所用到的提取方法是基于文獻(xiàn)［25］中提到的關(guān)鍵詞提取方法，并加以改進(jìn)運(yùn)用.本文認(rèn)為，并往往在重要的句子中.有代表性的詞往往和其他有代表性的詞共同出現(xiàn).并且，句子和詞能夠根據(jù)他們的連接結(jié)構(gòu)計(jì)算排名.所以，首先計(jì)算句子排名，找到重要的句子集，從而減少句子的影響.構(gòu)建句子連接關(guān)系圖GS，句子si和sj邊的權(quán)值 IF(si，sj)定義如下:

式中:maxCo(si，sj)表示si和sj之間相同詞的個(gè)數(shù)，Length(sj)表示sj的長(zhǎng)度.然后構(gòu)造鄰接矩陣MS，利用PageRank［26］的思想，對(duì)MS進(jìn)行迭代計(jì)算得到每一個(gè)SRank(si)，其代表句子i的重要程度.

下一步根據(jù)句子的重要程度計(jì)算詞的重要程度.其基本思想與句子的計(jì)算和排名近似.同樣建立詞鏈接關(guān)系無(wú)向圖GW，詞i與詞j之間邊的權(quán)值定義如下:

式中:p代表句子sp中的詞集，SRank(sp)代表sp的重要程度.然后利用PageRank算法思想進(jìn)行排名，得到每一個(gè)詞的WRank(wi).根據(jù)WRank(wi)的大小，排名靠前的詞為popular words.

最后將每一類得到的popular words合并去重到一個(gè)集合中，作為最終得到的具有高區(qū)分度的特征集合.

2.3 特征向量化

在這一步中，需要將原始數(shù)據(jù)集用得到的高區(qū)分度特征詞進(jìn)行表示.對(duì)文檔進(jìn)行向量化最常用的方法就是計(jì)算每個(gè)詞的TF-IDF權(quán)值，作為這一特征的特征值.TF-IDF［27-28］實(shí)際上是 TF*IDF，TF 為詞頻，IDF為反文檔頻率.計(jì)算公式如下:

2.4 文本聚類

最后，對(duì)處理后的數(shù)據(jù)集進(jìn)行文本聚類.這里用的是 K-means聚類算法［29-30］.K-均值聚類(K-means clustering)是MacQueen提出的一種非監(jiān)督實(shí)時(shí)聚類算法，在最小化誤差函數(shù)的基礎(chǔ)上將數(shù)據(jù)劃分為預(yù)定的類別數(shù)K.設(shè)定類別數(shù)目K，然后將數(shù)據(jù)對(duì)象劃分為K個(gè)聚類以便使所獲得的聚類滿足:同一聚類中的對(duì)象相似度較高;不同聚類中的對(duì)象相似度較小.

2.5 文檔集與話題層的映射關(guān)系

圖2展示了CDW事件多版本算法中文檔集與話題層的映射關(guān)系以及整個(gè)算法的流程.

圖2 文檔與話題層的映射關(guān)系Fig.2 Mapping between documents and topics

通過(guò)圖示和之前的算法介紹，總結(jié)如下:

1)建立文檔集與話題層之間的映射關(guān)系，將文檔映射到不同的話題中;

2)提取每一個(gè)話題的特征;

3)合并所有話題的特征，過(guò)濾掉公共部分，找到具有特性的特征詞項(xiàng);

4)將原始文檔集用提取出的特征表示，進(jìn)行聚類.

最終得到不同版本的文檔集.

3 實(shí)驗(yàn)與評(píng)價(jià)

3.1 實(shí)驗(yàn)數(shù)據(jù)集

為了展示CDW算法的有效性，作者在2個(gè)真實(shí)的數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn).一個(gè)是韓國(guó)的天安艦沉沒(méi)事件，包括533篇文檔，分別來(lái)自英國(guó)廣播BBC、英國(guó)天空廣播、美國(guó)之音、美國(guó)紐約時(shí)報(bào)、朝日新聞、朝鮮日?qǐng)?bào)等，以下簡(jiǎn)稱為CS.另一個(gè)是臺(tái)灣連勝文槍擊案，包括391篇文檔，分別來(lái)自騰訊、雅虎、新浪、搜狐、人民網(wǎng)、鳳凰網(wǎng)等，以下簡(jiǎn)稱為L(zhǎng)SW.

韓國(guó)天安艦事件發(fā)生于2010年3月26日，韓國(guó)軍方稱其一艘導(dǎo)彈護(hù)衛(wèi)艦“天安艦”因發(fā)生不明原因的爆炸事故而沉沒(méi).由于確切的原因一直無(wú)法調(diào)查清楚，所以關(guān)于此次沉沒(méi)事件的原因引發(fā)了很大爭(zhēng)議.類似地，臺(tái)灣連勝文槍擊案發(fā)生于2010年11月26日，當(dāng)時(shí)正值臺(tái)灣5市選舉，連戰(zhàn)的兒子連勝文在助選時(shí)頭部遭到槍擊.由于正值政治敏感時(shí)期，關(guān)于此次槍擊案兇手的動(dòng)機(jī)就成了一大疑點(diǎn).

表1 CS和LSW數(shù)據(jù)集說(shuō)明Table 1 Illustration of data sets CS and LSW

數(shù)據(jù)集CS中，經(jīng)過(guò)去停用詞和詞根還原后的詞條一共有9 842個(gè)，利用詞頻過(guò)濾后有6 749個(gè)，最后提取到的高區(qū)分度特征詞為879個(gè).數(shù)據(jù)集LSW中，經(jīng)過(guò)去停用詞和詞根還原后的詞條一共有7 477個(gè)，利用詞頻過(guò)濾后有4 952個(gè)，最后提取到的高區(qū)分度特征詞為650個(gè).

3.2 評(píng)估方法

對(duì)于一個(gè)事件的新聞報(bào)道，很難通過(guò)逐篇瀏覽來(lái)確定每一篇報(bào)道屬于哪一個(gè)版本.所以，本文采用一個(gè)逐對(duì)判別的方法來(lái)評(píng)估CDW算法的效用.

在逐對(duì)判別方法中，這里關(guān)注的是某一對(duì)文檔是否屬于同一版本.首先，需要構(gòu)建標(biāo)準(zhǔn)測(cè)試集.作者從CS數(shù)據(jù)集中隨機(jī)選取了200對(duì)文檔，從 LSW數(shù)據(jù)集中隨機(jī)選取了150對(duì)文檔，并且確保每一對(duì)文檔都不同.然后，把每一對(duì)文檔給志愿者瀏覽，讓他們投票決定每一對(duì)文檔是否屬于同一版本.如果某一對(duì)文檔很難判別是否同類，則直接將這一對(duì)文檔剔除，并且添加一對(duì)新的文檔到測(cè)試集中.形式化定義如下:

式中:vi=1表示文檔對(duì)和屬于同一版本，vi=0表示其他情況.特別地，這里將為CS數(shù)據(jù)集和LSW數(shù)據(jù)集構(gòu)建的測(cè)試集簡(jiǎn)記為TCS和TLSW.

式中:|Tε|表示事件ε的文檔對(duì)測(cè)試集的大小，⊙表示異或運(yùn)算.

3.3 參數(shù)設(shè)定

本文通過(guò)檢驗(yàn)參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響程度來(lái)確定參數(shù)的設(shè)定.本文提出的算法中一共包括3個(gè)參數(shù):α、β、K.

α表示的是算法第1步中濾掉高頻詞的閾值，這里指的是濾掉的高頻詞占整個(gè)數(shù)據(jù)集詞庫(kù)總數(shù)的百分比.在參數(shù)測(cè)定中，實(shí)驗(yàn)中讓 α從0變化到10%，變化步長(zhǎng)為0.01.β表示的是算法第1步中提取popular words時(shí)，每一類取的詞數(shù)，這里指的是每一類中提取的popular words數(shù)目占這一類總詞數(shù)的百分比.在參數(shù)測(cè)定中，實(shí)驗(yàn)中讓?duì)聫?0%變化到20%，變化步長(zhǎng)為0.01.

通過(guò)計(jì)算Pscore值來(lái)檢驗(yàn)這2個(gè)參數(shù)的變化以及它們對(duì)算法效果的影響.圖3展示了2個(gè)數(shù)據(jù)集中，不同的α和β下Pscore的值的分布.

圖3 CS和LSW中特定K下的α和β的參數(shù)設(shè)定Fig.3 α and β tuning under specific K in CS and LSW

從圖3中可以看出，得到最好的一組 αbest和βbest分別是在CS數(shù)據(jù)集中，當(dāng) α=4%和 β=15%時(shí)，得到的Pscore值最優(yōu);在LSW數(shù)據(jù)集中，當(dāng)α=3%和β=13%時(shí)，得到的Pscore值最優(yōu).另外，也可以看出，當(dāng)α或者β遞增時(shí)，Pscore的值先增后減.

K值表示的是LDA話題分析和K-means聚類中類別數(shù)的設(shè)定，也意味著最后得到的版本數(shù).提前設(shè)定K值是對(duì)版本數(shù)的一個(gè)預(yù)測(cè).這里從2個(gè)方面對(duì)K值進(jìn)行設(shè)定.1)讓志愿者根據(jù)一定數(shù)量的閱讀新聞報(bào)道或分析總結(jié)性的新聞報(bào)道，獲取關(guān)于這一特定事件版本信息的先驗(yàn)知識(shí)，即志愿者通過(guò)大致的瀏覽分析，得到關(guān)于這一特定新聞事件版本數(shù)的模糊區(qū)間.通過(guò)第1步分析后，可以得到CS數(shù)據(jù)集和LSW數(shù)據(jù)集的版本數(shù)均在4～7種.2)同樣通過(guò)計(jì)算Pscore值來(lái)最終確定2個(gè)數(shù)據(jù)集分為幾個(gè)版本.以1為步長(zhǎng)，讓K值在4～7變化，分別得到相應(yīng)的Pscore值，如表2所示.

表2 CS和LSW中K的參數(shù)設(shè)定Table 2 Parameter tuning of K in CS and LSW

從表2中可以看出，在數(shù)據(jù)集CS時(shí)，當(dāng)K=5時(shí)，Pscore達(dá)到最優(yōu);在數(shù)據(jù)集 LSW 中，當(dāng)K=4時(shí)，Pscore達(dá)到最優(yōu).

3.4 實(shí)驗(yàn)結(jié)果及評(píng)價(jià)

在實(shí)驗(yàn)的部分，作者將與幾種相關(guān)算法進(jìn)行對(duì)比試驗(yàn)，以檢驗(yàn)本文提出的CDW算法的效果.相關(guān)算法研究包括:

1)K-means:根據(jù)文檔之間的相似度對(duì)文檔進(jìn)行聚類;

2)LDA:根據(jù)詞的分布對(duì)文檔進(jìn)行聚類;

3)DVD:基于圖模型的時(shí)間多版本發(fā)現(xiàn)算法;

4)CDW-lda:CDW算法的變種，過(guò)濾高頻詞后不進(jìn)行LDA分析而直接提取popular words，再進(jìn)行聚類;

5)CDW-pw:CDW算法的另一變種，LDA分析后不用原方法提取popular words，而是直接用每一類的高頻詞做popular words，再進(jìn)行特征向量化和聚類.

作者在之前構(gòu)建的2個(gè)測(cè)試集TCS和TLSW上進(jìn)行實(shí)驗(yàn)，以比較CDW模型和其他相關(guān)算法的效果.不同算法在測(cè)試集TCS和TLSW上的Pscore值如圖4所示.

圖4 在數(shù)據(jù)集CS和LSW上的Pscore值Fig.4 Pscoreperformance comparison in pairwise test of CS and LSW

最后，用表3來(lái)展示本文的多版本發(fā)現(xiàn)結(jié)果.其中，通過(guò)本文中的CDW模型，韓國(guó)天安艦事件共有5個(gè)不同版本，中國(guó)臺(tái)灣連勝文槍擊案共有4個(gè)不同版本.從這個(gè)結(jié)果中可以看出，本文提出的多版本發(fā)現(xiàn)結(jié)果是比較準(zhǔn)確可靠的.

表3 CDW算法對(duì)于2個(gè)事件的多版本發(fā)現(xiàn)結(jié)果Table 3 Results of CDW model for diverse versions discovery in CS and LSW

從圖4中可以看出，K-means算法和LDA話題分析在2個(gè)測(cè)試集上的表現(xiàn)都是最差的.DVD算法的結(jié)果相對(duì)較好，但是由于DVD算法只利用了詞與詞之間的層級(jí)關(guān)系，而忽略了文本信息和話題關(guān)系，所以它的結(jié)果并不如CDW算法.在CDW的3個(gè)版本中，完整的CDW算法和CDW-lda的結(jié)果要好于其他所有算法.這表明，在話題層上進(jìn)行popular words的提取對(duì)于事件的多版本發(fā)現(xiàn)問(wèn)題十分重要.另外，CDW算法的結(jié)果優(yōu)于CDW-lda也優(yōu)于CDW-pw，這意味著文檔集與話題的映射和映射之后popular words的提取都是十分有必要的.

4 結(jié)束語(yǔ)

本文提出了一種基于文本的新聞事件多版本發(fā)現(xiàn)的模型，能夠幫助讀者對(duì)某一特定新聞事件進(jìn)行自動(dòng)快速的多版本生成.在論文工作中發(fā)現(xiàn)，簡(jiǎn)單的聚類方法具有很多局限性，無(wú)法將文本中不同的版本信息區(qū)分開(kāi)來(lái).為了取得更好的效果，本算法建立了話題層與文檔集合之間的映射關(guān)系，將文本集合引申到話題空間，在話題空間中對(duì)文本進(jìn)行高區(qū)分度特征的提取.然后，再根據(jù)這些提取出來(lái)的特征進(jìn)行文本聚類，從而得到關(guān)于某一新聞事件的多個(gè)版本.

通過(guò)在2個(gè)真實(shí)的數(shù)據(jù)集上的實(shí)驗(yàn)，可以看出，與以往的相關(guān)算法相比，本文提出的方法在事件多版本發(fā)現(xiàn)的問(wèn)題上具有更高的準(zhǔn)確性和有效性.

雖然本文的算法取得了非常不錯(cuò)的效果，但是還存在一些需要改進(jìn)的地方.在算法中確定多版本類別數(shù)目時(shí)，算法采用的是提前設(shè)定版本數(shù)目.如果可以將自動(dòng)確定類別數(shù)的相關(guān)算法應(yīng)用到多版本的發(fā)現(xiàn)問(wèn)題中，那么將會(huì)產(chǎn)生更為準(zhǔn)確的多版本結(jié)果.同時(shí)，改進(jìn)最后的聚類分析方法對(duì)于提高多版本發(fā)現(xiàn)模型的準(zhǔn)確性也將起到一定的作用.另外，本文的算法只是對(duì)事件的多版本進(jìn)行生成，而沒(méi)有對(duì)生成結(jié)果做總結(jié)性概括描述.因此可以考慮加入提取摘要來(lái)完善算法，將會(huì)更具有實(shí)際應(yīng)用意義.

［1］ALLAN J.Topic detection and tracking:event-based information organization［M］.Boston:Kluwer Academic Publishers，2002:1241-1253.

［2］HE T T，QU G Z，LI S W，et al.Semi-automatic hot event detection［C］//Lecture Notes in ComputerScience.Hongkong，China，2006:1008.

［3］YU M Q，LUO W H，XU H B，et al.Research on hierarchical topic detection in topic detection and tracking［J］.Journal of Computer Research and Development，2006，43(3):489-495.

［4］邱立坤，龍志祎，鐘華，等.層次化話題發(fā)現(xiàn)與跟蹤方法及系統(tǒng)實(shí)現(xiàn)［J］.廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版，2007，25(2):157-160.

QIU Likun，LONG Zhiyi，ZHONG Hua，et al.Hierarchical topic detection and tracking and implementation of system［J］.Journal of Guangxi Normal University:Natural Science Edition，2007，25(2):157-160.

［5］CARTHY J.Lexical chains versus keywords for topic tracking［C］//Proceedings of the 5th International Conference on Intelligent Text Processing and Computational Linguistics.Seoul，Korea，2004:507-510.

［6］ALLAN J，CARBONELL J，DODDINGTON G，et al.Topic detection and tracking pilot study final report［C］//Proceedings of the DARPA Broadcasting News Transcript and Understanding Workshop.［S.l.］，1998:194-218.

［7］YANG Y，PIERCE T，CARBONELL J.A study of retrospective and on-line event detection［C］//Special Interest Group on Information Retrieval’98.Melbourne，Australia，1998:28-36.

［8］ALLAN J，PAPKA R，LAVRENKO V.On-line new event detection and tracking［C］//Special Interest Group on Information Retrieval’98.Melbourne，Australia，1998:37-45.

［9］BRANTS T，CHEN F，F(xiàn)ARAHAT A.A system for new event detection［C］//Special Interest Group on Information Retrieval’03.Toronto，Canada，2003:330-337.

［10］NALLAPATI R，F(xiàn)ENG A，PENG F，et al.Event threading within news topics［C］//International Conference on Information and Knowledge Management. Washington，DC，USA，2004:446-453.

［11］STEINBACH M，KARYPIS G，KUMAR V.A comparison of document clustering techniques［EB/OL］.［2011-05-14］.http://www.cs.cmu.edu/～ dunja/KDDpapers/Steinbach_IR.pdf.

［12］PAUL S B，USAMA M F.Refining initial points for K-means clustering［C］//Proceedings of the Fifteenth International Conference on Machine Learning.San Francisco，USA，1998:91-99.

［13］JAIN A K，MURTY M N，F(xiàn)LYNN P J.Data clustering:a review［J］.ACM Computing Surveys，1999，31(3):264-333.

［14］RYMOND T，HAN J W.Efficient and effective clustering methods for spatial data mining［C］//Proceedings of the 20th International Conference on Very Large Data Bases.Hong Kong，China，1994:144-155.

［15］KONG L，YAN R，HE Y J，et al.DVD:a model for event diversified versions discovery［C］//Asia-Pacific Web Conference’11.Beijing，China，2011:18-20.

［16］FLAKE G W，LAWRENCE S，GILES C L.Efficient identification of Web communities［C］//International Conference on Knowledge Discovery and Data Mining'00.Boston，USA，2000:160-169.

［17］ROCCHIO J.Relevance feedback in information retrieval［C］//The SMART Retrieval System:Experiments in Automatic Document Processing.Englewood Cliffs，USA，1971:313-323.

［18］DASGUPTA S，NG V.Towards subjectifying text clustering［C］//Special Inspector General for Iraq Reconstruction’10.Geneva，Switzerland，2010:483-490.

［19］DUMAIS S T，PLATT J，HECKERMAN D，et al.Inductive learning algorithms and representations for text categorization［C］//Proceedings of the Seventh International Conference on Information and Knowledge Management.New York，USA，1998:148-155.

［20］FRANZ M，WARD T，MCCARLEY J S，et al.Unsupervised and supervised clustering for topic tracking［C］//Special Inspector General for Iraq Reconstruction’01.New Orlean，USA，2001:310-317.

［21］BLEI D M，ANDREW Y NG，MICHAEL I J.Latent Dirichlet allocation［J］.The Journal of Machine Learning Research，2003(3):993-1022.

［22］WEI X，CROFT W B.LDA-based document models for ad-hoc retrieval［C］//Proceedings of the 29th Special Inspector General for Iraq Reconstruction Conference.New York，USA，2006:178-185.

［23］BHATTACHARYA I，GETOOR I.A latent Dirichlet model for unsupervised entity resolution［C］//SIAM International Conference on Data Mining.Bethesda，USA，2006:47-58.

［24］JEROME R B.A novel word clustering algorithm based on latent semantic analysis［C］//Acoustics，Speech，and Sig-nal Processing 1996.［S.l.］，1996:172-175.

［25］SUN B，SHI L，KONG L，et al.Describing web topics meticulously through word graph analysis［C］//The IEEE Conference on Instructional Technologies ’09.Xiamen，China，2009:11-14.

［26］PAGE L，BRIN S，MOTWANI R，et al.The pagerank citation ranking:bringing order to the web［C］//Proceedings of the 7th International World Wide Web Conference.Brisbane，Australia，1998:161-172.

［27］KAREN J S.A statistical interpretation of term specificity and its application in retrieval［J］.Journal of Documentation，1972，28(1):11-21.

［28］HARTIGANJ A，WONG M A.A K-means clustering algorithm［J］.Journal of the Royal Statistical Society，Series C:Applied Statistics，1979，28(1):100-108.

［29］PELLEG D，MOORE A W.X-means:extending K-means with efficient estimation of the number of clusters［C］//Proceedings of the Seventeenth International Conference on Machine Learning.Stanford，USA，2000:727-734.

［30］MACQUEEN J B.Some methods for classification and analysis of multivariate observations［C］//Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability.Berkeley:University of California Press，1967:281-297.