唐國(guó)瑜, 夏云慶, 張 民, 鄭 方

(1. 清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，北京 100084； 2. 資訊通信研究院，新加坡 138632)

1 引言

文檔聚類的目的是按照相似程度將文檔劃分為不同的類簇，它已經(jīng)成功應(yīng)用于改進(jìn)文檔分類和文檔流事件發(fā)現(xiàn)。國(guó)內(nèi)外學(xué)者在單語(yǔ)言文檔聚類研究中嘗試了很多算法。但是隨著商業(yè)環(huán)境的全球化，文檔聚類逐步面臨不同語(yǔ)言的挑戰(zhàn)。

傳統(tǒng)單語(yǔ)言文檔聚類方法采取向量空間模型(Vector Space Model, VSM)表示文本，它利用詞袋(Bag of Word, BOW)模型來構(gòu)建特征空間，將每個(gè)文檔轉(zhuǎn)化為一個(gè)向量。詞袋模型在特征匹配中通常采用“硬匹配”方法。例如，當(dāng)詞“海岸”被選為特征時(shí)，除非“海邊”也被選為特征，否則“海邊”無法影響到文檔表示。這是因?yàn)椤坝财ヅ洹敝小昂０丁焙汀昂＿叀蓖耆煌?。為解決這個(gè)問題，文獻(xiàn)[1]提出的潛語(yǔ)義分析(LSA)方法，基于語(yǔ)料庫(kù)中的共現(xiàn)信息將一組詞與一個(gè)特征進(jìn)行匹配。GVMS則將文檔中的詞看作向量，然后通過計(jì)算詞的內(nèi)積或者相似度進(jìn)行將文檔表示在一個(gè)非正交的空間上。但是上述模型都是基于單語(yǔ)文檔集設(shè)計(jì)的，并不能直接用到跨語(yǔ)言文檔集中。

研究者提出了用詞典或機(jī)器翻譯工具對(duì)特征或者文檔進(jìn)行翻譯。然而，一旦詞被選為特征，“硬匹配”問題變得更為嚴(yán)重。如何獲得不同語(yǔ)言文檔中的相似詞匯，這是跨語(yǔ)言文檔聚類的核心問題。文獻(xiàn)[2]提出了采用LSA的解決方法。借助平行語(yǔ)料，他們將相似的詞看作為一個(gè)特征。與單語(yǔ)言LSA不同，跨語(yǔ)言LSA在固定訓(xùn)練集上選擇特征。但由于目標(biāo)文檔集通常與訓(xùn)練集存在內(nèi)容和用詞的顯著不同，這會(huì)導(dǎo)致過度適應(yīng)問題。

本文通過采用跨語(yǔ)言詞匯相似度計(jì)算將單語(yǔ)廣義向量空間模型(Generalized Vector Space Model, GVSM)拓展到跨語(yǔ)言文檔表示中，即跨語(yǔ)言廣義空間向量模型(CLGVSM)。同時(shí)提出了適用于CLGVSM的特征選擇算法。本文實(shí)現(xiàn)了兩種有代表性的詞匯相似度算法，即基于《知網(wǎng)》的詞匯相似度算法和基于SOCPMI的詞匯相似度算法。實(shí)驗(yàn)表明，SOCPMI比《知網(wǎng)》更適合文檔聚類。同時(shí)，我們還在相同可比語(yǔ)料下對(duì)基于SOCPMI的CLGVSM方法與LSA方法進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果表明，基于SOCPMI的CLGVSM方法比LSA方法顯示出更好的性能。

2 相關(guān)工作

2.1 跨語(yǔ)言文檔聚類

跨語(yǔ)言文檔聚類的難點(diǎn)在于如何處理跨語(yǔ)言相似性問題，其中最直接的方法是采用詞典或機(jī)器翻譯工具。在TDT-3評(píng)測(cè)中，四個(gè)系統(tǒng)均采用機(jī)器翻譯工具(文獻(xiàn)[3]等)。結(jié)果表明，與單語(yǔ)言話題跟蹤相比，采用機(jī)器翻譯方法會(huì)導(dǎo)致50%的性能下降。下降的主要原因是機(jī)器翻譯技術(shù)的準(zhǔn)確性問題。

一些研究工作[4-6]通過雙語(yǔ)詞典進(jìn)行詞匹配或者特征詞翻譯。文獻(xiàn)[7]通過多語(yǔ)言主題詞表 Eurovoc 構(gòu)造跨語(yǔ)言文檔向量。以上基于詞典的跨語(yǔ)言文檔聚類方法都難以解決歧義詞的翻譯問題以及未登陸詞問題。

近年來，學(xué)者開始利用平行語(yǔ)料或可比語(yǔ)料進(jìn)行跨語(yǔ)言文檔聚類[2，8]。還有一些研究利用維基百科進(jìn)行跨語(yǔ)言文檔信息檢索[9]。不同于文檔分類，文檔聚類缺乏訓(xùn)練數(shù)據(jù)，因此語(yǔ)義空間只能在固定訓(xùn)練語(yǔ)料中構(gòu)建，特征的選擇也是如此，因此忽略了特征在聚類目標(biāo)集中的不同分布。本文提出的CLGVSM模型構(gòu)建于詞匯相似度之上并在聚類目標(biāo)集中進(jìn)行特征選擇。

2.2 詞匯相似度

詞匯相似度計(jì)算是一個(gè)自然語(yǔ)言處理研究熱點(diǎn)，并在機(jī)器翻譯和詞義排歧等研究中得到應(yīng)用。近年來提出的詞匯相似度計(jì)算算法或基于統(tǒng)計(jì)技術(shù)，或基于語(yǔ)義網(wǎng)絡(luò)。文獻(xiàn)[10-11]提出基于WordNet的英文語(yǔ)義相似度計(jì)算方法。文獻(xiàn)[12-13]則提出了利用知網(wǎng)概念定義計(jì)算跨語(yǔ)言詞匯相似度的方法?；谡Z(yǔ)料的詞匯相似度計(jì)算方法更為廣泛。最經(jīng)典的方法是點(diǎn)互信息(Pointwise Mutual Information, PMI)[14]。PMI值越大，說明詞匯越有可能出現(xiàn)在同一語(yǔ)境下。文獻(xiàn)[15]提出了基于PMI-IR的同義詞獲取方法，利用Alta Vista Adanvced搜索引擎計(jì)算單詞之間的概率。LSA方法[16]分析大規(guī)模語(yǔ)料，利用詞匯之間的共現(xiàn)信息計(jì)算詞匯和文本的相似度。SOCPMI方法[17]利用PMI將兩個(gè)目標(biāo)詞的相鄰詞按重要性排序，并通過計(jì)算相鄰詞的PMI實(shí)現(xiàn)目標(biāo)詞之間的相似度計(jì)算。

本文采用兩個(gè)最具代表性的詞匯相似度計(jì)算方法構(gòu)造CLGVSM矩陣： 基于《知網(wǎng)》的詞匯相似度[13]和基于SOCPMI的詞匯相關(guān)度[17]。

3 相似度空間模型

為了便于描述，我們首先介紹傳統(tǒng)的廣義向量空間模型。

3.1 廣義向量空間模型

假設(shè)D={dj;j=1,…，n}表示包含n個(gè)文檔m個(gè)詞的文檔集。X表示一個(gè)m×n的矩陣，它的元素xij表示詞ti在文檔dj的權(quán)重。GVSM[18]將文檔表示在一個(gè)非正交空間中，文檔的相似度計(jì)算公式如下:

(1)

其中G是一個(gè)m×m關(guān)聯(lián)矩陣，用來表示詞之間的相似度。

傳統(tǒng)的GVSM中[18]，詞表示為文檔的對(duì)偶空間中的向量。G的計(jì)算公式如下：

G=XXT

(2)

在改進(jìn)的GVSM中[19]，性能最好的G為詞向量的協(xié)方差矩陣。

(3)

其中Q為X的抽樣，并且

在上述GVSM模型中，G都是在聚類文檔中計(jì)算得出的，但是它們很難獲得跨語(yǔ)言的詞信息。因此我們通過采用跨語(yǔ)言詞相似度計(jì)算將GVSM拓展為跨語(yǔ)言文檔表示模型CLGVSM。

3.2 跨語(yǔ)言廣義空間向量模型上的特征選擇和文檔表示

VSM模型中，詞對(duì)于一個(gè)文檔的重要性可以簡(jiǎn)單采取詞頻表示，對(duì)于一個(gè)文檔集的重要性則用倒文檔頻表示。拓展到CLGVSM模型中，我們定義了類似的特征重要性指標(biāo)。

考慮一個(gè)包含“criminal”3次、“imprisonment”10次的文檔。認(rèn)為詞“criminal”仍然是非常重要的，雖然他的詞頻比較低。這是由于“imprisonment”與“criminal”是語(yǔ)義相似的。為此，我們提出了兩個(gè)基于CLGVSM模型的特征重要性指標(biāo):軟詞頻和軟文檔頻。給定詞匯t和文檔集D={dj}j=1…L，假設(shè)dj={wi,j}i=1…N代表文檔dj的中的詞匯，軟詞頻和軟文檔頻的定義如下：

軟詞頻TFS：

TFs(t,d)=SimSSM(vt,d)

(4)

軟文檔頻DFS：

DFs(t)=∑dj∈DmaxiSimWD(t,wi,j))

(5)

參考TF-IDF公式的思想，我們定義軟倒文檔頻：

(6)

因此，詞匯t在文檔d的權(quán)重計(jì)算公式：

ws(t,d)=TFs(t,d)IDFw(t)

(7)

如果我們單純依靠權(quán)重進(jìn)行特征選擇，相似度比較高的單詞會(huì)同時(shí)被選為特征。這是因?yàn)橄嗨贫缺容^高的單詞含有相近的權(quán)重，這將造成特征集的冗余。因此，我們提出了一個(gè)改進(jìn)的特征選擇算法，只賦予相似詞集中的一個(gè)詞比較高的軟詞頻，而其余詞匯則降低權(quán)重。即按照初始軟詞頻的從大到小更新軟詞頻，刪除相似度所造成的冗余。

對(duì)軟詞頻改進(jìn)后，我們根據(jù)式(7)計(jì)算每個(gè)特征的權(quán)重，并按照特征權(quán)重的大小選擇每個(gè)文檔的特征，然后合并為一個(gè)特征集。我們使用特征集表示文檔，并考慮特征集之外的詞對(duì)文檔表示的影響。我們將每個(gè)特征集外的詞匯的軟詞頻乘以相似度，累加到與它相似度最大的特征中，從而體現(xiàn)其貢獻(xiàn)。這樣，即使文檔中并不包含某特征，文檔表示也可以將文檔映射到最有代表性的近義特征中。

3.3 基于廣義空間向量模型的文檔聚類算法

獲得文檔相似度后，我們采用聚類算法進(jìn)行文檔聚類。聚類算法不是本文的重點(diǎn)，因此我們選用經(jīng)典的聚類算法，即HAC(Hierarchical Agglomerative Clustering)算法[20]。

HAC算法先將每個(gè)文檔看成一個(gè)類簇，然后逐步將相似度最高的類簇合并為一個(gè)類簇。為了計(jì)算類簇之間的相似度，我們采用group-average link算法[20]。當(dāng)類簇個(gè)數(shù)達(dá)到預(yù)定值后，則停止合并過程。

4 詞匯相似度

詞匯相似度在CLGVSM矩陣的構(gòu)建中起到重要的作用。我們采用兩種詞匯相似度計(jì)算算法構(gòu)造CLGVSM矩陣： 基于知識(shí)的詞匯相似度算法以及基于統(tǒng)計(jì)的詞匯相似度算法。

獎(jiǎng)品揭曉日期雖五花八門，但最多的還是在11月11日，剁手節(jié)。一些網(wǎng)友在看完獎(jiǎng)品名單后感慨，獎(jiǎng)是一個(gè)沒中，反倒被禮品清單種了草。我也是在微博和淘寶之間反復(fù)切換。

文獻(xiàn)[13]利用《知網(wǎng)》計(jì)算跨語(yǔ)言詞匯相似度，基本思想是利用《知網(wǎng)》中詞匯的語(yǔ)義定義。篇幅所限，詳細(xì)過程參見文獻(xiàn)[13]。

嚴(yán)格來說，基于統(tǒng)計(jì)的詞匯相似度計(jì)算算法其實(shí)是與它們?cè)谡Z(yǔ)料中的共現(xiàn)程度有關(guān)。因此我們可以稱統(tǒng)計(jì)的詞匯相似度為詞匯相關(guān)度。

由于SOCPMI在詞匯相似度計(jì)算中具有優(yōu)越性[17]，本文采取了這個(gè)算法。篇幅所限，詳細(xì)過程參見文獻(xiàn)[17]。

然而SOCPMI算法只能處理單語(yǔ)言的詞匯相似度。本文擴(kuò)展了這個(gè)算法，以實(shí)現(xiàn)跨語(yǔ)言詞匯相似度計(jì)算。先在相同語(yǔ)言上對(duì)相鄰詞進(jìn)行排序，然后計(jì)算它們的跨語(yǔ)言PMI值。

可以使用兩種類型的語(yǔ)料計(jì)算跨語(yǔ)言詞匯相似度： 平行語(yǔ)料和可比語(yǔ)料。平行語(yǔ)料被廣泛用于機(jī)器翻譯，它是句子對(duì)齊的。但本文沒有選用平行語(yǔ)料，原因有二： 首先構(gòu)造一個(gè)平行語(yǔ)料的成本比較高；其次跨語(yǔ)言的詞匯相似度對(duì)句子對(duì)齊的要求并不高。最終本文選用更容易獲得的篇章對(duì)齊的可比語(yǔ)料。

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

5.1 實(shí)驗(yàn)設(shè)置

? 開發(fā)集

我們從英文和中文GigaWord中構(gòu)建了一個(gè)中英文可比語(yǔ)料。我們采用以下的策略獲得不同語(yǔ)言的可比文檔對(duì)。1)文檔相似度。采用基于VSM的文檔相似度獲得單語(yǔ)言中的可比文檔。為了保證精度，我們?cè)O(shè)置文檔相度的閾值為0.4;2)基于《知網(wǎng)》獲得詞匯翻譯。我們利用《知網(wǎng)》獲得詞匯之間的翻譯信息，利用這些翻譯信息計(jì)算跨語(yǔ)言文檔那個(gè)相似度;3)時(shí)間限制。本文在計(jì)算文檔相似度的時(shí)候還考慮到時(shí)間的限制，只選取在同一天內(nèi)的新聞?dòng)?jì)算文檔相似度獲得可比語(yǔ)料。我們最后獲得101 409篇中英文可比文檔對(duì)。

? 測(cè)試集

我們采取TDT4數(shù)據(jù)集作為測(cè)試集。TDT4數(shù)據(jù)集的信息如表1所示。

表1 TDT4數(shù)據(jù)集統(tǒng)計(jì)信息

? 評(píng)測(cè)指標(biāo)

我們采用了文獻(xiàn)[21]提出的評(píng)測(cè)指標(biāo)。首先計(jì)算每個(gè)類簇最大的F值。假設(shè)Ai代表系統(tǒng)生成的類簇ci的文檔，Aj代表人工標(biāo)注的類簇cj的文檔。則F值計(jì)算如下：

其中pi,j,ri,j和fi,j分別代表準(zhǔn)確率、召回率和F值。

? 實(shí)驗(yàn)方法

本研究中，我們?cè)u(píng)測(cè)了以下五個(gè)方法。

VSM： 采用VSM表示文檔，并從《知網(wǎng)》獲得詞匯翻譯信息；

LSA： LSA在可比語(yǔ)料中實(shí)現(xiàn)了文獻(xiàn)[2]中的方法；

CLGVSM^HN:采用基于《知網(wǎng)》的跨語(yǔ)言相似度的GVSM。在GVSM矩陣的構(gòu)造中，經(jīng)過實(shí)驗(yàn)驗(yàn)證詞匯相似度閾值為0.7；

CLGVSM^PMI:采用基于SOCPMI的跨語(yǔ)言相似度的GVSM。相似度閾值為0.4；

CLGVSM^PMI&TR: 將SOCPMI與《知網(wǎng)》的翻譯信息結(jié)合起來，《知網(wǎng)》獲得翻譯對(duì)的相似度為1。

5.2 實(shí)驗(yàn)結(jié)果及討論

我們比較了五個(gè)系統(tǒng)在兩個(gè)測(cè)試集上的性能。結(jié)果如表2所示。

表2 系統(tǒng)在兩個(gè)測(cè)試集上的最高F值

從表2可以得出以下結(jié)論。

首先，方法CLGVSM^HN 和VSM的性能相近，基于《知網(wǎng)》跨語(yǔ)言詞匯相似度構(gòu)造的GVSM比VSM幾乎沒有優(yōu)勢(shì)。觀察發(fā)現(xiàn)，基于《知網(wǎng)》計(jì)算的相似度非常高。例如，詞“Federal Reserve”和“bank”的相似度為1。經(jīng)過分析，基于《知網(wǎng)》的跨語(yǔ)言詞匯相似度更多關(guān)注詞的語(yǔ)義特征而不是語(yǔ)義本身，它傾向于給語(yǔ)義相似的詞對(duì)更高的相似度，而不管它們是否是語(yǔ)義相關(guān)。這不利于文檔聚類。因此可以認(rèn)為，基于《知網(wǎng)》的詞相似度不太適用于文檔聚類。

其次，方法CLGVSM^PMI在兩個(gè)測(cè)試集上的性能均優(yōu)于方法LSA。在測(cè)試集TDT41上，F(xiàn)值提高了0.11。在測(cè)試集TDT42上F值提高了0.094。這說明了方法CLGVSM^PMI更適合跨語(yǔ)言文檔聚類。分析原因如下： LSA所構(gòu)建的語(yǔ)義空間是在固定的可比語(yǔ)料中構(gòu)建的，因此它沒有考慮到目標(biāo)聚類集的特征的重要性。相比之下，方法CLGVSM^PMI充分利用了測(cè)試集的信息構(gòu)建語(yǔ)義空間。

最后， SOCPMI與《知網(wǎng)》相結(jié)合的CLGVSM的性能比較VSM的性能要好。在測(cè)試集TDT41中，高出0.014；而在測(cè)試集TDT42的效果更加明顯，超出了0.018。這是本次實(shí)驗(yàn)獲得最好結(jié)果(0.910)。這表明，使用恰當(dāng)?shù)脑~匯相似度計(jì)算方法，CLGVSM方法能取得滿意的跨語(yǔ)言文檔聚類效果。從表2可以看出，當(dāng)只使用《知網(wǎng)》時(shí)，CLGVSM方法給出的結(jié)果與VSM相近。當(dāng)只使用可比語(yǔ)料時(shí)，CLGVSM給出的結(jié)果比VSM要差。我們發(fā)現(xiàn)，從《知網(wǎng)》獲得翻譯信息非常重要。同時(shí)使用可比語(yǔ)料和《知網(wǎng)》，CLGVSM獲得最好的性能。因此，《知網(wǎng)》與語(yǔ)料相結(jié)合可以獲得更好地性能。

6 結(jié)語(yǔ)

本文的貢獻(xiàn)主要有三個(gè)： (1)通過加入跨語(yǔ)言詞匯相似度將GVSM拓展為CLGVSM；(2)實(shí)現(xiàn)了基于知識(shí)和基于統(tǒng)計(jì)的詞匯相似度計(jì)算方法。(3)對(duì)CLGVSM方法和主要流行方法進(jìn)行了評(píng)測(cè)，實(shí)驗(yàn)結(jié)果表明，利用《知網(wǎng)》以及可比語(yǔ)料資源，CLGVSM模型比VSM和LSA的性能更優(yōu)。

本文得出兩個(gè)結(jié)論： 首先，CLGVSM方法比VSM和LSA都更有效；其次，結(jié)合《知網(wǎng)》翻譯信息以及可比語(yǔ)料的相似度，有利于進(jìn)一步提高文檔聚類效果。在接下來的工作中，我們計(jì)劃將GVSM模型用于更多語(yǔ)言的跨語(yǔ)言聚類。同時(shí)，由于CLGVSM模型能在語(yǔ)義空間上有效表示文本，我們將應(yīng)用CLGVSM模型到短文本聚類中，希望能很好地解決稀疏問題。

[1] T. Landauer, P. W. Foltz, Darrell Laham. Introduction to Latent Semantic Analysis[J]. Discourse Processes 25: 259-284.

[2] C-P. Wei, C. C. Yang, C-M. Lin. A Latent Semantic Indexing Based Approach to Multilingual Document Clustering [J]. Decision Support System. 45(3):606-620.

[3] T. Leek, H. Jin, S. Sista, et al. The BBN cross-lingual topic detection and tracking system[C]//Proceedings of TDT’1999.

[4] H.H. Chen, C.J. Lin. A multilingual news summarizer[C]//Proceedings of COLING’2000: 159-165.

[5] D.K. Evans, J.L. Klavans. A Platform for Multilingual News Summarization[R], Technical Report. Department of Computer Science, Columbia University.

[6] B. Mathieu, R. Besancon, C. Fluhr. Multilingual Document Clusters Discovery[C]//Proceedings of RIAO’2004: 1-10.

[7] B. Pouliquen, R. Steinberger, C. Ignat, et al. Multilingual and cross-lingual news topic tracking[C]//Proceedings of COLING’2004: 959-965.

[8] D. Yogatama, K.Tanaka.. Multilingual Spectral Clustering Using Document Similarity Propagation[C]//Proceedings of EMNLP’2009: 871-879.

[9] P. Cimiano, A. Schultz, S. Sizov, et al. Explicit vs. latent concept models for cross-language information retrieval[C]//Proceedings of IJCAI’09, 2009.

[10] D. Lin. Automatic retrieval and clustering of similar words[C]//Proceedings of COLING’98:768-774.

[11] P. Resnik. Semantic similarity in a taxonomy: An information based measure and its application to problems of ambiguity in natural language[J]. Journal of Artificial Intelligence Research, V.11:95-130.

[12] Q Liu, S Li. Word similarity computing based on How Net[C]//Proceedings of Computational Linguistics and Chinese Language Processing.

[13] Y. Xia, T. Zhao, P. Jin. Measuring Chinese-English Cross-lingual Word Similarity with How Net and Parallel Corpus[C]//Proceedings of CICling’2011(II):221-233.

[14] K.W. Church, P. Hanks. Word association norms, mutual information, and lexicography[J]. Computational Linguistics, 16(1):22-29.

[15] P. D. Turney. Mining the Web for Synonyms: PMI-IR versus LSA on TOEF[C]//Proceedings of ECML’2001: 491-502.

[16] T. K. Landauer, S. T. Domais. A Solution to Plato’s Problem: The Latent Semantic Analysis Theory of Acquision, Induction and Representation of Knowledge[J]. Psychological Review. 104(2):211-240.

[17] A. Islam, D. Inkpen. Second order co-occurrence PMI for determining the semantic similarity of words[C]//Proceedings of LREC’2006: 1033-1038.

[18] SKM. Wong, W. Ziarko, PCN. Wong. Generalized vector model in information retrieval[C]//Proceedings of the 8thACM SIGIR:18-25.

[19] A.K. Farahat, M. S. Kamel. Statistical semantic for enhancing document clustering[J]. Knowledge and Information Systems.

[20] E. M. Voorhees. Implementing Agglomerative Hierarchic Clustering Algorithms for Use in Document Retrieval[J]. Information Processing and Management, 22(6): 465-76.

[21] M. Steinbach, G. Kapypis, V. Kumar. A Comparison of Document Clustering Techniques[C]//Proceedings of KDD Workshop on Text Mining, 2000:109-111.