唐國瑜, 夏云慶, 張 民, 鄭 方

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

1 引言

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

傳統(tǒng)單語言文檔聚類方法采取向量空間模型(Vector Space Model, VSM)表示文本，它利用詞袋(Bag of Word, BOW)模型來構建特征空間，將每個文檔轉化為一個向量。詞袋模型在特征匹配中通常采用“硬匹配”方法。例如，當詞“海岸”被選為特征時，除非“海邊”也被選為特征，否則“海邊”無法影響到文檔表示。這是因為“硬匹配”中“海岸”和“海邊”完全不同。為解決這個問題，文獻[1]提出的潛語義分析(LSA)方法，基于語料庫中的共現(xiàn)信息將一組詞與一個特征進行匹配。GVMS則將文檔中的詞看作向量，然后通過計算詞的內積或者相似度進行將文檔表示在一個非正交的空間上。但是上述模型都是基于單語文檔集設計的，并不能直接用到跨語言文檔集中。

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

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

2 相關工作

2.1 跨語言文檔聚類

跨語言文檔聚類的難點在于如何處理跨語言相似性問題，其中最直接的方法是采用詞典或機器翻譯工具。在TDT-3評測中，四個系統(tǒng)均采用機器翻譯工具(文獻[3]等)。結果表明，與單語言話題跟蹤相比，采用機器翻譯方法會導致50%的性能下降。下降的主要原因是機器翻譯技術的準確性問題。

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

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

2.2 詞匯相似度

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

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

3 相似度空間模型

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

3.1 廣義向量空間模型

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

(1)

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

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

G=XXT

(2)

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

(3)

其中Q為X的抽樣，并且

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

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

VSM模型中，詞對于一個文檔的重要性可以簡單采取詞頻表示，對于一個文檔集的重要性則用倒文檔頻表示。拓展到CLGVSM模型中，我們定義了類似的特征重要性指標。

考慮一個包含“criminal”3次、“imprisonment”10次的文檔。認為詞“criminal”仍然是非常重要的，雖然他的詞頻比較低。這是由于“imprisonment”與“criminal”是語義相似的。為此，我們提出了兩個基于CLGVSM模型的特征重要性指標:軟詞頻和軟文檔頻。給定詞匯t和文檔集D={dj}j=1…L，假設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的權重計算公式：

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

(7)

如果我們單純依靠權重進行特征選擇，相似度比較高的單詞會同時被選為特征。這是因為相似度比較高的單詞含有相近的權重，這將造成特征集的冗余。因此，我們提出了一個改進的特征選擇算法，只賦予相似詞集中的一個詞比較高的軟詞頻，而其余詞匯則降低權重。即按照初始軟詞頻的從大到小更新軟詞頻，刪除相似度所造成的冗余。

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

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

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

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

4 詞匯相似度

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

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

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

嚴格來說，基于統(tǒng)計的詞匯相似度計算算法其實是與它們在語料中的共現(xiàn)程度有關。因此我們可以稱統(tǒng)計的詞匯相似度為詞匯相關度。

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

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

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

5 實驗

5.1 實驗設置

? 開發(fā)集

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

? 測試集

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

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

? 評測指標

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

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

? 實驗方法

本研究中，我們評測了以下五個方法。

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

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

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

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

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

5.2 實驗結果及討論

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

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

從表2可以得出以下結論。

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

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

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

6 結語

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

本文得出兩個結論： 首先，CLGVSM方法比VSM和LSA都更有效；其次，結合《知網(wǎng)》翻譯信息以及可比語料的相似度，有利于進一步提高文檔聚類效果。在接下來的工作中，我們計劃將GVSM模型用于更多語言的跨語言聚類。同時，由于CLGVSM模型能在語義空間上有效表示文本，我們將應用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.