幾種基于統(tǒng)計的詞聚類方法比較

袁里馳

?

幾種基于統(tǒng)計的詞聚類方法比較

袁里馳

(江西財經大學信息管理學院，數(shù)據(jù)與知識工程江西省高校重點實驗室，江西南昌，330013)

基于數(shù)據(jù)稀疏問題是影響語言統(tǒng)計模型系統(tǒng)性能的主要問題，而基于詞類的語言統(tǒng)計模型是解決這一問題的主要方法之一，利用相鄰詞語的互信息定義一種詞語相似度，在詞語相似度的基礎上定義詞語集合的相似度，進而提出一種能得到全局最優(yōu)結果、自下而上的詞聚類算法。研究結果表明：該詞聚類算法執(zhí)行效率高，聚類效果較好；根據(jù)該詞聚類模型的結果所構造的基于詞類和基于詞語的線性插值模型，能較好地緩解統(tǒng)計語言模型中的數(shù)據(jù)稀疏問題。

自然語言處理；詞聚類；互信息；詞相似度

在自然語言理解的研究中，人們越來越重視統(tǒng)計語言模型，其最具代表性的元語言統(tǒng)計模型根據(jù)詞序列已出現(xiàn)的前?1個詞預測后1個詞出現(xiàn)的概率。構造元語言模型通常需要非常大的訓練語料，有2個問題越來越突出：1) 系統(tǒng)的開銷。隨著語料資源的不斷擴大，語言模型的參數(shù)規(guī)模急劇膨脹，語言模型的計算使現(xiàn)有的計算機硬件資源難以承受。2) 對某些特定領域來說，元語言模型會遇到數(shù)據(jù)稀疏問題，即使使用的訓練語料庫龐大，也無法覆蓋所有可能出現(xiàn)的語言現(xiàn)象。因此，在元語言模型的實際使用中，很難避免會遇到大量從未出現(xiàn)的語言現(xiàn)象，如何估計這些語言現(xiàn)象的發(fā)生概率，是元語言模型的主要問題之一?；谠~類的元語言模型是解決語言統(tǒng)計模型數(shù)據(jù)稀疏問題的重要方法之一。由于詞類的數(shù)量要遠小于詞的數(shù)量，因此，基于詞類的元語言統(tǒng)計模型成功地緩解了基于詞的元語言模型所遇到的稀疏數(shù)據(jù)問題，而且因為詞類的數(shù)量較少，使得統(tǒng)計基于詞類的高階語言模型成為可能。詞的分類方法主要有2種：1) 語言學家根據(jù)語義語法知識，人工歸納詞的分類，通常劃分為幾十個到幾百個詞類，這種詞分類方法分類過粗，難以充分運用從語料庫中獲取的大量統(tǒng)計知識描述復雜多變的語言現(xiàn)象；2) 詞的自動聚類算法。隨著計算機科學與技術的發(fā)展，大規(guī)模的語料資源已成為開展語言研究的有力工具，通過對語料庫進行統(tǒng)計實現(xiàn)詞自動聚類成為可能。這種詞分類方法可根據(jù)需要自動確定合適的詞類數(shù)目，從而在一定程度上可以避免前一種詞分類方法面臨的問題。傳統(tǒng)的詞聚類統(tǒng)計方法[1?4]通常以貪婪原則為基礎，以語料庫的似然函數(shù)或困惑度作為判別函數(shù)。其基本思想是：隨機地嘗試合并2個詞類，計算困惑度或似然函數(shù)的變化，將使困惑度最小的2個詞類合并。這種傳統(tǒng)的詞聚類統(tǒng)計方法的主要缺點是聚類速度較慢，初始選擇對聚類結果影響大，易陷入局部最優(yōu)。本文作者利用基于鄰接關系的詞的互信息定義詞相似度[5?6]，在詞相似度定義的基礎上定義詞集合(即詞類)的相似度，進而提出一種能得到全局最優(yōu)結果、自下而上的分層詞聚類算法。

1元語言統(tǒng)計模型及其主要性能 評價

語言統(tǒng)計模型[7?10]最重要的任務是在已知前面出現(xiàn)的一些詞的情況下，預測下一個詞出現(xiàn)的概率。基于詞的(≥1，為自然數(shù))元語言統(tǒng)計模型是最具代表性的語言統(tǒng)計模型，能在已知前面出現(xiàn)的?1個詞的情況下，確定下一個詞w(為自然數(shù)，≥2)可能出現(xiàn)的概率為

其中：w為測試語料集中全部詞的數(shù)量。對于1個語言統(tǒng)計模型來說，測試語料集困惑度越低，則該語言統(tǒng)計模型越好。

2 布朗詞聚類算法

BROWN等[11]提出了一種經典的基于互信息和貪婪原則的詞聚類統(tǒng)計方法。其基本思想是：隨機地嘗試合并2個詞類，計算互信息的變化，將使互信息損失最小的2個詞類合并。布朗詞聚類統(tǒng)計方法初始設置詞表中的每個詞各代表一詞類，設訓練語料集中詞的數(shù)量為，經過?次合并后，還有個詞類：

其中：1≤＜≤。下面計算合并詞類和引起的互信息變化。

設

其中：1≤＜≤；為詞類和出現(xiàn)的聯(lián)合概率。并設

經過?次合并后，保留下來的平均互信息為

(12)

其中：

平均互信息損失為

將息損失最小的2種詞類合并成1種新的詞類。

3 基于長距離二元模型的詞聚類算法

BASSIOU等[12]提出了一種基于概率潛在語義分析(probabilistic latent semantic analysis)和線性插值長距離二元模型的詞聚類方法。概率潛在語義分析的核心思想是示象模型(aspect model)，該模型使得每個類變量與每次觀測值相關。在聚類模型中，觀測值即為文本(或文檔)中的某個詞，而不可見的類變量則為生成某個文本的主題建立的模型變量。據(jù)示象模型的基本假設，所有的觀測對獨立分布，并且關于各自的潛在類條件獨立，此由，在潛在類生成的1文本及文本中的1詞的聯(lián)合概率分布可由下式給出：

E-步(計算期望，利用對隱藏變量的現(xiàn)有估計值計算其最大似然估計值)：

M-步(最大化在E步上求得的最大似然值來計算參數(shù)值)：

交替計算式(19)，(20)和(21)，直到對數(shù)似然函數(shù)值收斂到局部最大值為止。每個詞由下式分配到1個詞類：

其中：

4 基于詞相似度的聚類算法

4.1 基于互信息的詞相似度和詞類相似度

與前面提到的2種貪婪詞聚類統(tǒng)計方法不同，本文提出的詞聚類方法基于詞對之間的相似度和詞集合 (詞類)的相似度。因此，首先要找到一種可靠的、適于計算的詞與詞間相似度、詞類之間相似度的定量計算標準。基于語料庫的傳統(tǒng)統(tǒng)計方法通常認為某個詞的意義可能與該詞所處的上下文中出現(xiàn)的其他詞語有關，即可能與該詞的語言環(huán)境有關。因此，2個詞在訓練語料中所處的語言環(huán)境若總是很相似，則可以認為這2個詞彼此之間可能很相似[13]。

若2個詞1和2很相似，則可以推斷這2個詞1和2與其他詞之間的互信息也很相似。記表示相鄰的詞對和之間的互信息：

(25)

由式(26)可知：若2個詞1和2與它們的左右相鄰詞之間的互信息差別越小，則這2個詞之間的相似度越高，因而，這種詞相似度的定義較合理的。基于詞相似度定義，2個詞類(詞集合)1和2之間的相似度(1,2)定義如下：

4.2 詞聚類算法

為了使本文提出的詞聚類算法更接近于漢語語義真實分類體系[14?15]，選擇分層聚類方法作為詞聚類算法。分層詞聚類方法采用自底向上的算法，即首先每個詞分別代表1個詞集合(詞類)，而詞集合(詞類)的數(shù)目就是該詞表的大小()，然后找出具有最大詞相似度的2個詞集合(詞類)。將這2個詞集合(詞類)合并成1個新的詞集合(詞類)，直到達到聚類結束的要求為止。整個詞聚類算法過程如下。

1) 計算任意2個詞之間的相似度。

2) 初始化。設詞表中的每個詞分別代表1個詞集合(詞類)，詞表共包括個詞集合(詞類)(其中，為該詞表中包含的詞的個數(shù))。

3) 找出詞集合(詞類)中具有最大相似度的2個詞集合(詞類)，并將這2個詞集合(詞類)合并成1個新的詞集合(詞類)。

4) 計算剛合并的詞集合(詞類)與其他詞集合(詞類)的相似度。

5) 檢查算法是否達到聚類結束的條件(任意2個詞類之間的最大相似度都小于某個預先確定的門檻值，或詞表中的詞類數(shù)目達到聚類的要求)。若是，則程序可以結束；否則，轉步驟3)。

本文提出的基于詞相似度的聚類算法與2種貪婪聚類算法相比，有2個較突出的優(yōu)點：1) 基于長距離二元模型的詞聚類方法，其對數(shù)似然函數(shù)值收斂到局部最大值，而基于詞相似度的分層聚類方法能得到全局最優(yōu)結果；2) 分層詞聚類算法的速度遠遠高于2種貪婪聚類算法的速度。布朗詞聚類算法復雜度為，本文詞聚類算法可以分為3部分：1) 計算任意2個詞或詞類之間的互信息，其計算復雜度為；2) 找出詞表中具有最大相似度的2個詞類，其計算復雜度仍為；3) 計算剛合并的詞類與其他詞類的相似度，其計算復雜度為。綜上所述，基于詞相似度的分層詞聚類算法的計算復雜度為?；谠~相似度的分層詞聚類算法其算法復雜度要遠比使平均互信息損失最小的布朗詞聚類算法的復雜度小。

5 實驗結果驗證

在前面所介紹的3種詞聚類統(tǒng)計語言模型的基礎上，選取1998年的《人民日報》標注語料庫用作實驗語料。該《人民日報》標注語料庫以1998年《人民日報》語料為加工對象，由富士通研究開發(fā)中心有限公司和北京大學計算語言學研究所共同制作，包含 13 000多篇文章和2 600萬字。本文從實驗語料中選取大約6 M語料作為測試語料，其余語料作為訓練語料，用3種詞聚類統(tǒng)計方法進行測試，其困惑度測試結果如表1所示。

表1 3種詞聚類算法的困惑度測試結果比較

從表1可見：基于詞相似度的詞聚類算法的困惑度只有213，其聚類效果要明顯比2種經典的詞聚類統(tǒng)計方法好。雖然這2種經典的詞聚類統(tǒng)計方法是以訓練語料的困惑度作為指導進行分類，但這2種貪婪詞聚類算法很容易陷入局部最優(yōu)，因而，其聚類結果的困惑度要遠高于本文提出的基于詞相似度的分層聚類算法的困惑度?，F(xiàn)從詞聚類實驗結果中隨意選擇一些詞類，其分類如下。

詞類1：合肥，湛江，長沙，南昌，巴格達，倫敦，上海，北京，等等。

詞類2：兩樣，一致，雷同，平等，不相上下，一如，異口同聲，同一，相等，一律，相同，一樣，等于，同樣，不等，異曲同工，勢均力敵，大同小異，對等，一模一樣，等等。

詞類3：偷盜，騙取，制黃，抄襲，偷竊，持槍，賣淫，逃稅，恐怖，摻假，販黃，抗稅，等等。

詞類4：近似，宛如，相近，一般，類似，譬如，比如，恰似，似，好似，如同，相似，仿佛，猶如，接近，相仿，貌似，有如，好像，形似，似乎，等等。

詞類5：大，超越，超出，勝，后來居上，壓倒，等等。

詞類6：相形見絀，遜色，不及，望塵莫及，等等。

詞類7：不比，相左，懸殊，不同，等等。

從聚類結果可以看到，基于詞相似度的聚類統(tǒng)計方法比較接近真實的自然語言語義分類體系。本文第2個實驗是比較基于詞的模型、基于詞類的模型(基于詞相似度的聚類算法構造)、使用線性插值的基于詞類和基于詞相結合的語言模型對數(shù)據(jù)稀疏問題的承受能力。將訓練語料從6 M遞減到3 M再減小到1 M，分別訓練基于詞的二元模型、基于詞類的二元模型和線性插值二元模型，然后用全部的6 M語料測試困惑度變化，結果如表2所示。

表2 3種模型的困惑度變化

從表2可以看出：在訓練語料較充分的情況下，基于詞的二元模型的性能遠遠優(yōu)于基于詞類的二元模型的性能，但在訓練語料數(shù)據(jù)非常稀疏的情形下，基于詞的二元語言統(tǒng)計模型的性能急劇下降。然而，基于詞類的二元語言統(tǒng)計模型在訓練語料數(shù)據(jù)非常稀疏時，其性能也有所下降，但其性能始終相對平穩(wěn)，即使在訓練語料數(shù)據(jù)極端稀疏的情形下，模型性能的下降幅度也不太大。并且無論語料在什么情況下，線性插值二元模型均能明顯提高系統(tǒng)性能。

6 結論

1) 利用基于相鄰關系的詞的互信息定義了一種詞相似度，再在詞的相似度定義基礎上定義詞類(詞集合)的相似度，進而提出了一種能得到全局最優(yōu)結果、自下而上的分層詞聚類算法。

2) 本文提出的分層詞聚類算法其計算復雜度要遠遠比基于貪婪原則的傳統(tǒng)統(tǒng)計詞聚類算法的計算復雜度小，以較小的計算代價取得了比較好的聚類效果。

3) 對3種詞聚類統(tǒng)計方法進行測試，其中基于詞相似度的分層詞聚類算法的困惑度為213，遠低于其他2種詞聚類統(tǒng)計方法的困惑度。

4) 根據(jù)新的詞聚類模型的結果所構造的基于詞類的語言統(tǒng)計模型、基于詞類和基于詞的線性插值語言模型能較好地解決統(tǒng)計語言模型的稀疏數(shù)據(jù)問題，且基于詞類和基于詞的線性插值二元語言模型的困惑度為94，低于基于詞的二元語言模型的困惑度(105)。由于詞類的數(shù)量要遠小于詞的數(shù)量，因而，基于詞類的語言模型遇到的數(shù)據(jù)稀疏問題要遠比基于詞的語言模型少，系統(tǒng)性能明顯穩(wěn)定。

[1] 陳浪周, 黃泰翼. 一種新穎的詞聚類算法和可變長統(tǒng)語言模型[J]. 計算機學報, 1999, 22(9): 942?947. CHEN Langzhou, HUANG Taiyi. A novel word clustering algorithm and vari-gram language mode[J]. Chinese Journal of Computers, 1999, 22(9): 942?947.

[2] 孫靜, 朱杰, 徐向華. 一種新的中文詞自動聚類算法[J]. 上海交通大學學報, 2003, 37(Suppl): 139?142. SUN Jing, ZHU Jie, XU Xianghua. A new algorithm of Chinese words automatic clustering[J]. Journal of Shanghai Jiaotong University, 2003, 37(Suppl): 139?142.

[3] MATSUZAKI T, MIYAO Y. An Efficient clustering algorithm for class-based language models[C]// Proceedings of the 7th Conference on Natural Language Learning at HLT-NAACL. Edmonton, Canada, 2003: 119?126.

[4] LIU Ying, WANG Nan, ZHANG Tie. Spectral clustering for Chinese word[C]// Proceedings of the Sixth International Conference on Fuzzy Systems and Knowledge Discovery.2009: 529?533.

[5] 袁里馳. 基于相似度的詞聚類算法和可變長語言模型[J]. 小型微型計算機系統(tǒng), 2009, 30(5): 912?915. YUAN Lichi. word clustering based on similarity and vari-gram language model[J]. Journal of Chinese Computer Systems, 2009, 30(5): 912?915.

[6] 袁里馳. 基于詞聚類的依存句法分析[J]. 中南大學學報(自然科學版), 2011, 42(7): 2023?2027. YUAN Lichi. Dependency language paring model based on word clustering[J]. Journal of Central South University (Science and Technology), 2011, 42(7): 2023?2027.

[7] 劉水, 李生, 趙鐵軍, 等. 頭驅動句法分析中的直接插值平滑算法[J]. 軟件學報, 2009, 20(11): 2915?2924. LIU Shui, LI Sheng, ZHAO Tiejun, et al. Directly smooth interpolation algorithm in head-driven parsing[J]. Journal of Software, 2009, 20(11): 2915?2924.

[8] 吳偉成, 周俊生, 曲維光. 基于統(tǒng)計學習模型的句法分析方法綜述[J]. 中文信息學報, 2013, 27(3): 9?19. WU Weicheng, ZHOU Junsheng, QU Weiguang. A survey of syntactic parsing based on statistical learning[J]. Journal of Chinese Information Processing, 2013, 27(3): 9?19.

[9] 代印唐, 吳承榮, 馬勝祥, 等. 層級分類概率句法分析[J]. 軟件學報, 2011, 22(2): 245?257. DAI Yintang, WU Chengrong, MA Shengxiang, et al. Hierarchically classified probabilistic grammar parsing[J]. Journal of Software, 2011, 22(2): 245?257.

[10] JURAFSKY D, MARTIN J H. Speech and language processing[M]. New Jersey: Prentice Hall, 2009: 210?265.

[11] BROWN P F, PIETRA V J D, DE SOUZA P V, et al. Class-based n-gram models of natural language[J]. Computational Linguistics, 1997, 18(4): 467?479.

[12] BASSIOU N, KOTROPOULOS C. Long distance bigram models applied to word clustering[J]. Pattern Recognition, 2011, 44(1): 145?158.

[13] DAGAN I, et al. Context word similarity and estimation from sparse data[J]. Computer Speech and Language, 1995, 9(2): 123?152.

[14] 袁里馳. 融合語言知識的統(tǒng)計句法分析[J]. 中南大學學報(自然科學版), 2012, 43(3): 986?991. YUAN Lichi. Statistical parsing with linguistic features[J]. Journal of Central South University (Natural Science), 2012, 43(3): 986?991.

[15] YUAN Lichi. Improving head-driven statistical models for natural language parsing[J]. Journal of Central South University, 2013, 20(10): 2747?2752.

A comparison of severalstatistical word clustering methods

YUAN Lichi

(Jiangxi Key Laboratory of Data and Knowledge Engineering, School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China)

Considering that sparse-data problem is a main issue that influences the performances of statistical language models, statistical language model based on word classes is an effective method to solve sparse-data problems. A definition of word similarity was proposed by utilizing mutual information of adjoining words, and the definition of word set similarity was given based on word similarity; a bottom-up hierarchical word clustering algorithm which can get global optimum was put forward. The results show that the word clustering algorithm has high executing speed and good clustering performances. The class-based models interpolated with the word-based models can mitigate remaining sparse-data problems of statistical language models.

natural language processing; word clustering; mutual information; word similarity

10.11817/j.issn.1672-7207.2016.09.023

TP391.1

A

1672?7207(2016)09?3079?06

2015?11?13；

2015?12?28

國家自然科學基金資助項目(61262035，61562034)；江西省自然科學基金資助項目(20142BAB207028)；江西省科技支撐計劃項目(20151BBE50082)；江西省教育廳科技項目(GJJ14335) (Projects(61262035, 61562034) supported the National Natural Science Foundation of China; Project(20142BAB207028) supported the Natural Science Foundation of Jiangxi Province; Project(20151BBE50082) supported the Key Technology Support Program of Jiangxi Province; Projects(GJJ14335) supported the Scientific Research Foundation of Education Department of Jiangxi Province)

袁里弛，博士，副教授，從事自然語言處理研究；E-mail: yuanlichi@sohu.com

(編輯 陳燦華)