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

袁里馳

?

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

袁里馳

(江西財(cái)經(jīng)大學(xué)信息管理學(xué)院，數(shù)據(jù)與知識(shí)工程江西省高校重點(diǎn)實(shí)驗(yàn)室，江西南昌，330013)

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

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

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

1元語言統(tǒng)計(jì)模型及其主要性能 評(píng)價(jià)

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

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

2 布朗詞聚類算法

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

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

設(shè)

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

經(jīng)過?次合并后，保留下來的平均互信息為

(12)

其中：

平均互信息損失為

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

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

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

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

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

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

其中：

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

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

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

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

(25)

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

4.2 詞聚類算法

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

1) 計(jì)算任意2個(gè)詞之間的相似度。

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

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

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

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

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

5 實(shí)驗(yàn)結(jié)果驗(yàn)證

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

表1 3種詞聚類算法的困惑度測(cè)試結(jié)果比較

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

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

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

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

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

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

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

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

從聚類結(jié)果可以看到，基于詞相似度的聚類統(tǒng)計(jì)方法比較接近真實(shí)的自然語言語義分類體系。本文第2個(gè)實(shí)驗(yàn)是比較基于詞的模型、基于詞類的模型(基于詞相似度的聚類算法構(gòu)造)、使用線性插值的基于詞類和基于詞相結(jié)合的語言模型對(duì)數(shù)據(jù)稀疏問題的承受能力。將訓(xùn)練語料從6 M遞減到3 M再減小到1 M，分別訓(xùn)練基于詞的二元模型、基于詞類的二元模型和線性插值二元模型，然后用全部的6 M語料測(cè)試?yán)Щ蠖茸兓Y(jié)果如表2所示。

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

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

6 結(jié)論

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

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

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

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

[1] 陳浪周, 黃泰翼. 一種新穎的詞聚類算法和可變長統(tǒng)語言模型[J]. 計(jì)算機(jī)學(xué)報(bào), 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] 孫靜, 朱杰, 徐向華. 一種新的中文詞自動(dòng)聚類算法[J]. 上海交通大學(xué)學(xué)報(bào), 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]. 小型微型計(jì)算機(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]. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 劉水, 李生, 趙鐵軍, 等. 頭驅(qū)動(dòng)句法分析中的直接插值平滑算法[J]. 軟件學(xué)報(bào), 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ì)學(xué)習(xí)模型的句法分析方法綜述[J]. 中文信息學(xué)報(bào), 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í)分類概率句法分析[J]. 軟件學(xué)報(bào), 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] 袁里馳. 融合語言知識(shí)的統(tǒng)計(jì)句法分析[J]. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版), 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

國家自然科學(xué)基金資助項(xiàng)目(61262035，61562034)；江西省自然科學(xué)基金資助項(xiàng)目(20142BAB207028)；江西省科技支撐計(jì)劃項(xiàng)目(20151BBE50082)；江西省教育廳科技項(xiàng)目(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

(編輯 陳燦華)