基于最近鄰算法的短語(yǔ)結(jié)構(gòu)語(yǔ)法關(guān)系判定方法*

楊 泉 朱瑞平

（北京師范大學(xué)漢語(yǔ)文化學(xué)院 北京 100875）

1 引言

漢語(yǔ)短語(yǔ)層級(jí)的相似度計(jì)算是自然語(yǔ)言處理中的重要基礎(chǔ)性工作，其研究成果在機(jī)器翻譯［1］、信息檢索、情感分析等諸多領(lǐng)域都有實(shí)際應(yīng)用。“N1+N2”結(jié)構(gòu)是典型的漢語(yǔ)短語(yǔ)結(jié)構(gòu)，也是自然語(yǔ)言處理中的高頻語(yǔ)言現(xiàn)象，其內(nèi)部語(yǔ)法關(guān)系較為復(fù)雜，因此成為計(jì)算機(jī)自動(dòng)準(zhǔn)確判定的重點(diǎn)和難點(diǎn)問(wèn)題。本文以此結(jié)構(gòu)為例探討漢語(yǔ)短語(yǔ)結(jié)構(gòu)的語(yǔ)法關(guān)系自動(dòng)判定方法。

k最近鄰（k-nearest neighbor，KNN）算法是機(jī)器學(xué)習(xí)中經(jīng)典的分類方法之一［2］，它具有較高的有效性和數(shù)據(jù)訓(xùn)練時(shí)間復(fù)雜度低等特點(diǎn)，已經(jīng)被成功地應(yīng)用到很多實(shí)際分類問(wèn)題中，包括與中文文本相關(guān)的分類問(wèn)題［3］。該方法基于由N個(gè)已經(jīng)標(biāo)注分類樣本組成的訓(xùn)練樣本集T=｛xi，i=1，…，N｝。針對(duì)測(cè)試樣本xt，通過(guò)計(jì)算其與樣本集中樣本間的距離進(jìn)行分類。因此根據(jù)分類問(wèn)題的屬性，提取個(gè)體分類特征，依據(jù)分類特征建立個(gè)體間的距離，并在此基礎(chǔ)上建立訓(xùn)練集是KNN分類算法的基本前提。

綜上，本文擬在詞語(yǔ)相似度計(jì)算方法的基礎(chǔ)上，從語(yǔ)言學(xué)角度研究詞義相似度與短語(yǔ)結(jié)構(gòu)語(yǔ)法關(guān)系之間的關(guān)系，從而建立基于短語(yǔ)結(jié)構(gòu)相似度的短語(yǔ)結(jié)構(gòu)之間的距離關(guān)系。為此建立了標(biāo)注詞語(yǔ)語(yǔ)義類別和短語(yǔ)結(jié)構(gòu)語(yǔ)法關(guān)系的樣本集，最終給出基于k最近鄰算法的短語(yǔ)結(jié)構(gòu)判定方法。我們選用基于《同義詞詞林》的詞義相似度計(jì)算方法，目的是充分利用《同義詞詞林》的樹狀結(jié)構(gòu)，提高計(jì)算測(cè)試樣本與訓(xùn)練樣本之間距離的運(yùn)行效率。

2 基于《同義詞詞林》的詞義相似度的短語(yǔ)結(jié)構(gòu)距離定義

語(yǔ)言學(xué)領(lǐng)域的很多專家學(xué)者都關(guān)注到了N1+N2結(jié)構(gòu)中詞語(yǔ)的語(yǔ)法語(yǔ)義關(guān)系，如文獻(xiàn)［4~5］探討了N1+N2結(jié)構(gòu)中兩個(gè)名詞的語(yǔ)義類型和語(yǔ)法功能特點(diǎn)。漢語(yǔ)是典型的孤立型語(yǔ)言，不是通過(guò)詞的形態(tài)變化來(lái)表達(dá)語(yǔ)法作用的。同一個(gè)結(jié)構(gòu)實(shí)例化為不同的詞語(yǔ)時(shí)，可能產(chǎn)生不同的語(yǔ)法、語(yǔ)義關(guān)系。在N1+N2結(jié)構(gòu)兩個(gè)詞的詞性已經(jīng)確定的情況下，N1和N2各自的語(yǔ)義類別決定了其所構(gòu)成短語(yǔ)的語(yǔ)法關(guān)系，因此兩個(gè)短語(yǔ)中構(gòu)成詞的語(yǔ)義類別越接近兩個(gè)短語(yǔ)的語(yǔ)法關(guān)系就越相似。這從語(yǔ)言學(xué)原理上肯定了使用構(gòu)成短語(yǔ)的詞語(yǔ)間的語(yǔ)義相似度來(lái)定義短語(yǔ)結(jié)構(gòu)相似度的合理性。

在自然語(yǔ)言處理領(lǐng)域，詞義相似度是對(duì)給定的兩個(gè)詞之間語(yǔ)義相似或相關(guān)程度的衡量，通常用［0~1］之間的數(shù)值來(lái)表示。詞義相似度的值越大，說(shuō)明兩個(gè)詞的距離越近，相關(guān)性越大，緊密程度也越高。目前漢語(yǔ)中詞義相似度計(jì)算方法主要分為兩大類［6］：基于語(yǔ)料庫(kù)和基于知識(shí)本體的方法。第一類基于語(yǔ)料庫(kù)的方法能夠較為客觀地反映真實(shí)語(yǔ)言面貌，如文獻(xiàn)［7］運(yùn)用詞向量的方法計(jì)算詞義相似度，但是很多研究結(jié)果表明基于語(yǔ)料庫(kù)的方法對(duì)語(yǔ)料的依賴性較大，需要在大規(guī)模精確標(biāo)注語(yǔ)料的基礎(chǔ)上進(jìn)行，然而語(yǔ)料的規(guī)模、內(nèi)容、范圍以及標(biāo)注的標(biāo)準(zhǔn)和規(guī)范難以統(tǒng)一，而且可解釋性較差［8］；第二類基于知識(shí)本體的方法在這些方面就顯示出了其優(yōu)越性，越來(lái)越多的專家學(xué)者都在這方面進(jìn)行了有效嘗試?！锻x詞詞林》是重要的漢語(yǔ)知識(shí)本體，它是梅家駒等編撰的可計(jì)算用漢語(yǔ)語(yǔ)義詞典，后經(jīng)哈工大研究人員擴(kuò)展為《哈工大同義詞詞林?jǐn)U展版》（下文簡(jiǎn)稱《詞林》），目前共收錄詞語(yǔ)77456條，使用8位編碼來(lái)表示詞語(yǔ)義項(xiàng)，如表1所示。展示了《詞林》編碼體系。

表1 《詞林》語(yǔ)義編碼表

前7位編碼可以唯一代表一個(gè)原子詞群，第8位編碼表示原子詞群中詞語(yǔ)間的關(guān)系，“＝、＃、＠”分別表示“同義、相關(guān)、唯一”三種關(guān)系。

近年來(lái)基于《詞林》的詞義相似度算法層出不窮，比如文獻(xiàn)［9］、［10］、［11］、［12］、［13］分別提出了基于《詞林》結(jié)點(diǎn)路徑、深度或分支結(jié)點(diǎn)數(shù)的詞義相似度計(jì)算方法。文獻(xiàn)［13］中計(jì)算詞語(yǔ)相似度的具體公式如下：

上式（1）中，S（s1，s2）代表兩個(gè)詞的語(yǔ)義s1和s2的相似度，D為最近父結(jié)點(diǎn)深度，系數(shù)為λ1=0.9811，λ2=0.4977，λ3=0.1244，λ4=4.4612。

在計(jì)算語(yǔ)言學(xué)領(lǐng)域中，很多研究在分析語(yǔ)法語(yǔ)義關(guān)系的基礎(chǔ)上，提出了識(shí)別N1與N2結(jié)構(gòu)的規(guī)則［14~16］。以此從實(shí)證研究的角度證明了語(yǔ)法關(guān)系相同的結(jié)構(gòu)其語(yǔ)義類別也往往具有較高的相似性。

人工智能領(lǐng)域有許多處理語(yǔ)言學(xué)問(wèn)題的成功方法，本文研究的短語(yǔ)結(jié)構(gòu)判定問(wèn)題屬于人工智能領(lǐng)域中的分類問(wèn)題。在標(biāo)準(zhǔn)訓(xùn)練集的基礎(chǔ)上可以使用k最近鄰分類算法進(jìn)行計(jì)算。即計(jì)算N1+N2測(cè)試集中的語(yǔ)料與訓(xùn)練集中全部語(yǔ)料之間的距離，然后判定該短語(yǔ)結(jié)構(gòu)關(guān)系屬于哪一類語(yǔ)法關(guān)系。

為了使用k最近鄰算法判定“N1+N2”的語(yǔ)法關(guān)系，我們首先需要定義兩個(gè)短語(yǔ)結(jié)構(gòu)之間的距離。根據(jù)上文的分析，設(shè)有兩個(gè)待比較的“N1+N2”短語(yǔ)結(jié)構(gòu)，分別表示為“N1c+N2c”和“N1x+N2x”，設(shè)詞語(yǔ)N1c和N1x之間的語(yǔ)義相似度為S1，N2c和N2x之間的語(yǔ)義相似度為S2，則定義這兩個(gè)結(jié)構(gòu)之間的相似度為

其中0≤μ1≤1，0≤μ2≤1，且μ1+μ2=1。

因此可以定義短語(yǔ)結(jié)構(gòu)間的距離為

根據(jù)該定義，當(dāng)S1和S2均取最大值1時(shí)，S取最大值1，此時(shí)其距離取最小值0。當(dāng)S1和S2均取最小值0時(shí)，短語(yǔ)結(jié)構(gòu)中的詞在語(yǔ)義上無(wú)相關(guān)性，此時(shí)結(jié)構(gòu)間的距離定為無(wú)窮大。

計(jì)算兩個(gè)名詞間的語(yǔ)義相似度，經(jīng)過(guò)多方比較，本文采用式（1）的語(yǔ)義相似度的計(jì)算方法。該方法簡(jiǎn)潔易用，效果也較為理想，此外，采用基于《詞林》的語(yǔ)義相似度計(jì)算方法，可以根據(jù)《詞林》編碼已有的樹形結(jié)構(gòu)，設(shè)計(jì)計(jì)算測(cè)試集短語(yǔ)與訓(xùn)練集短語(yǔ)距離的快速搜索算法。

3 基于語(yǔ)料庫(kù)的N1+N2結(jié)構(gòu)標(biāo)準(zhǔn)樣本集

3.1 收集整理語(yǔ)料

首先在北京語(yǔ)言大學(xué)BCC語(yǔ)料庫(kù)中提取出N1+N2結(jié)構(gòu)語(yǔ)料共17108條，這些語(yǔ)料來(lái)自“人民日?qǐng)?bào)、人民日?qǐng)?bào)、文學(xué)、科技文獻(xiàn)”四個(gè)子語(yǔ)料庫(kù)，去掉各類不合格語(yǔ)料，剩下合格語(yǔ)料共10398條。

3.2 分析標(biāo)注語(yǔ)料

N1+N2結(jié)構(gòu)實(shí)例化后實(shí)際存在四種語(yǔ)法關(guān)系：“定中、并列、復(fù)指、主謂”關(guān)系（下文用“dzp、blp、fzp、zwp”表示），據(jù)此又建成四種語(yǔ)法關(guān)系子庫(kù)。合格語(yǔ)料中還存在大量重復(fù)語(yǔ)料，因此又對(duì)語(yǔ)料進(jìn)行了去重處理，剩下不重復(fù)合格語(yǔ)料共5098條，詳見表2。

表2 N1+N2結(jié)構(gòu)去重后各關(guān)系數(shù)量及占比

下面為N1和N2標(biāo)注語(yǔ)義信息，選擇《詞林》語(yǔ)義編碼體系作為語(yǔ)義標(biāo)注體系，先用計(jì)算機(jī)自動(dòng)標(biāo)注，再進(jìn)行人工校對(duì)。

3.3 構(gòu)建訓(xùn)練集與測(cè)試集

本文著重研究語(yǔ)義類別與語(yǔ)法關(guān)系之間的規(guī)律，因此在四種語(yǔ)法關(guān)系子庫(kù)的基礎(chǔ)上對(duì)訓(xùn)練集與測(cè)試集按8∶2的比例進(jìn)行分配，具體數(shù)量及占比見表3。

表3 訓(xùn)練集與測(cè)試集各關(guān)系統(tǒng)計(jì)表

然后將每種語(yǔ)法關(guān)系子庫(kù)的訓(xùn)練集和測(cè)試集分別匯總，形成最終不重復(fù)合格語(yǔ)料的訓(xùn)練集和測(cè)試集，并將訓(xùn)練集語(yǔ)料作為標(biāo)準(zhǔn)樣本集。

4 基于詞義相似度和最近鄰算法的N1+N2結(jié)構(gòu)語(yǔ)法關(guān)系判定方法

首先需要作一些形式化處理。

1）將訓(xùn)練集中的語(yǔ)料設(shè)為N1x、N2x；將測(cè)試集中待測(cè)試的語(yǔ)料設(shè)為N1c、N2c。

2）四種語(yǔ)法關(guān)系中“N1+N2”結(jié)構(gòu)的名詞具體表示為并列關(guān)系兩個(gè)名詞表示為N1b、N2b；復(fù)指關(guān)系兩個(gè)名詞表示為N1f、N2f；定中關(guān)系兩個(gè)名詞表示為N1d、N2d；主謂關(guān)系兩個(gè)名詞表示為N1z、N2z。

K最近鄰結(jié)構(gòu)判定算法：

1）輸入：測(cè)試結(jié)構(gòu)“N1c+N2c”；

2）計(jì)算：比較測(cè)試結(jié)構(gòu)與訓(xùn)練集中所有結(jié)構(gòu)“N1x+N2x”間k個(gè)最近的距離；

3）判定：k個(gè)距離最近的結(jié)構(gòu)中，所屬類別最多的一類作為測(cè)試結(jié)構(gòu)所屬的類別。

我們使用kd樹算法來(lái)提高計(jì)算測(cè)試實(shí)例和訓(xùn)練集中實(shí)例距離的計(jì)算效率。該方法包括三步：第一步是建樹，第二部是搜索最近鄰，最后一步是預(yù)測(cè)。其中需要根據(jù)訓(xùn)練集的特點(diǎn)來(lái)構(gòu)造kd樹，其它兩步都是通用方法。kd樹是一種二叉樹，用于存儲(chǔ)高維空間的實(shí)例點(diǎn)，以便對(duì)其進(jìn)行快速檢索的樹形結(jié)構(gòu)。訓(xùn)練集中的實(shí)例都是“N1x+N2x”的短語(yǔ)結(jié)構(gòu)，基于《詞林》的相似度計(jì)算方法中，N1x和N2x都有唯一的《詞林》編碼，因此我們可以直接將這兩個(gè)詞的《詞林》編碼構(gòu)造為一個(gè)新的編碼，這就完成了將短語(yǔ)結(jié)構(gòu)到高維空間的映射，從而可以方便進(jìn)行后續(xù)kd樹的構(gòu)成。從語(yǔ)言學(xué)上，該分類方法的基本原理如下。

1）N1、N2語(yǔ)義編碼都相同

如果我們?cè)跍y(cè)試集中需要測(cè)試的語(yǔ)料為N1c+N2c，在訓(xùn)練集中存在N1c和N2c語(yǔ)義編碼都相同的短語(yǔ)。只需要根據(jù)訓(xùn)練集標(biāo)注的結(jié)果去標(biāo)注N1c+N2c的語(yǔ)法關(guān)系就可以了。因?yàn)槲覀兏鶕?jù)語(yǔ)義編碼計(jì)算相似度，而《詞林》體系中存在語(yǔ)義編碼相同，詞語(yǔ)不同的情況，如當(dāng)測(cè)試語(yǔ)料為“新郎新婦”時(shí)，在訓(xùn)練集中存在“新郎新娘”，是并列關(guān)系，只需要根據(jù)訓(xùn)練集的標(biāo)注結(jié)果判定即可。

2）N1語(yǔ)義編碼相同、N2語(yǔ)義編碼不同

如果我們?cè)跍y(cè)試集中需要測(cè)試的語(yǔ)料為N1c+N2c，在訓(xùn)練集中存在與N1c語(yǔ)義編碼相同，N2c語(yǔ)義編碼不同的短語(yǔ)。比如當(dāng)N1實(shí)例化為“工資”時(shí)，在訓(xùn)練集中有“工資待遇”，是并列關(guān)系，記為“N1b+N2b”；還有“工資增幅”，是定中關(guān)系，記為“N1d+N2d”，這些短語(yǔ)的N1語(yǔ)義編碼都相同。如果需要判定測(cè)試集中“工資+N2c”的語(yǔ)法關(guān)系，比如“工資基金”，我們就需要計(jì)算N2c與N2b的語(yǔ)義相似度以及N2c與N2d的語(yǔ)義相似度，然后比較幾個(gè)詞對(duì)相似度的大小，以N2c與N2x最大相似度短語(yǔ)的語(yǔ)法關(guān)系作為判定結(jié)果。

3）N2語(yǔ)義編碼相同、N1語(yǔ)義編碼不同

如果我們?cè)跍y(cè)試集中需要測(cè)試的語(yǔ)料為N1c+N2c，在訓(xùn)練集中存在與N2c語(yǔ)義編碼相同，N1c語(yǔ)義編碼不同的短語(yǔ)。如當(dāng)N2實(shí)例化為“護(hù)士”時(shí)，在訓(xùn)練集中有“大夫護(hù)士”，是并列關(guān)系，記為“N1b+N2b”；還有“國(guó)際護(hù)士”，是定中關(guān)系，記為“N1d+N2d”，這些短語(yǔ)的N2語(yǔ)義編碼都相同。如果需要判定測(cè)試集中“N1c+護(hù)士”的語(yǔ)法關(guān)系，比如“病區(qū)護(hù)士”，我們就需要計(jì)算N1c與N1b的語(yǔ)義相似度以及N1c與N1d的語(yǔ)義相似度，然后比較兩個(gè)相似度的大小，以最大相似度結(jié)果的語(yǔ)法關(guān)系作為判定結(jié)果。

4）N1、N2語(yǔ)義編碼都不同

如果我們?cè)跍y(cè)試集中需要測(cè)試的語(yǔ)料為N1c+N2c，在訓(xùn)練集不存在與N1c、N2c語(yǔ)義編碼都相同的短語(yǔ)。比如測(cè)試集中有“楊樹刺槐”這個(gè)短語(yǔ)，其中的兩個(gè)名詞的語(yǔ)義編碼在訓(xùn)練集中都沒有出現(xiàn)，這時(shí)就需要計(jì)算“楊樹”與訓(xùn)練集中N1列中哪個(gè)名詞的語(yǔ)義相似度最大，再計(jì)算“刺槐”與訓(xùn)練集中N2列中哪個(gè)名詞的語(yǔ)義相似度最大，然后結(jié)合兩個(gè)相似度計(jì)算結(jié)構(gòu)的相似度。再求出結(jié)構(gòu)的距離，作為判定依據(jù)。

5 實(shí)驗(yàn)結(jié)果與分析

按照上述方法，我們對(duì)測(cè)試集中的語(yǔ)料進(jìn)行判斷。在距離計(jì)算中取μ1=μ2=0.5，在k最近鄰算法中，經(jīng)過(guò)測(cè)試發(fā)現(xiàn)取k=1，即能取得較好的結(jié)果，因此以下結(jié)果中都取k=1，所以實(shí)際上用的是最近鄰算法。

語(yǔ)料計(jì)算結(jié)果見表4所示。

表4 語(yǔ)料測(cè)試結(jié)果

計(jì)算機(jī)自動(dòng)標(biāo)注的結(jié)果與人工結(jié)果比較后，四種語(yǔ)法關(guān)系計(jì)算結(jié)果的精確率和召回率見表5所示。

表5 四種語(yǔ)法關(guān)系判定結(jié)果的精確率和召回率

對(duì)本文實(shí)驗(yàn)進(jìn)行分析后，可以得出以下一些結(jié)論：

1）本文計(jì)算結(jié)果證明了本文設(shè)計(jì)算法的有效性，同時(shí)也證明了“N1+N2”結(jié)構(gòu)中詞的語(yǔ)義類別對(duì)語(yǔ)法關(guān)系確實(shí)有決定性的作用，因此可以根據(jù)“N1+N2”結(jié)構(gòu)中兩個(gè)名詞的語(yǔ)義類別去判定短語(yǔ)的語(yǔ)法關(guān)系，這個(gè)規(guī)律不僅在“N1+N2”結(jié)構(gòu)中存在，在其他類型的漢語(yǔ)短語(yǔ)結(jié)構(gòu)中也同樣存在。

2）在本文的計(jì)算過(guò)程中，我們對(duì)不同“N1+N2”結(jié)構(gòu)短語(yǔ)分別計(jì)算N1的相似度及N2的相似度，所得結(jié)果已經(jīng)較為理想，但仍有個(gè)別例外現(xiàn)象，究其原因主要是因?yàn)檎Z(yǔ)料庫(kù)中四種語(yǔ)法關(guān)系的語(yǔ)料不均衡，定中關(guān)系語(yǔ)料過(guò)多，而其他關(guān)系特別是主謂關(guān)系語(yǔ)料過(guò)少。后面我們可再結(jié)合“N1+N2”結(jié)構(gòu)中兩個(gè)名詞的相似度進(jìn)行計(jì)算，并進(jìn)一步補(bǔ)充完善非定中關(guān)系語(yǔ)料，以期得到更為客觀、準(zhǔn)確的語(yǔ)法關(guān)系判定結(jié)果。

3）漢語(yǔ)中含有兩個(gè)詞的短語(yǔ)結(jié)構(gòu)我們稱為二元短語(yǔ)結(jié)構(gòu)，用最近鄰算法在效果和運(yùn)算量上是最優(yōu)的；含有三個(gè)詞的三元短語(yǔ)結(jié)構(gòu)或更多元的短語(yǔ)結(jié)構(gòu)可以考慮采用2、3近鄰或更多近鄰的算法。近鄰算法的思想很適合計(jì)算語(yǔ)言學(xué)運(yùn)用語(yǔ)料庫(kù)處理語(yǔ)言問(wèn)題，在處理過(guò)程中簡(jiǎn)潔易用，體現(xiàn)了人工智能領(lǐng)域目前“弱標(biāo)注、小數(shù)據(jù)、大任務(wù)”的發(fā)展趨勢(shì)。

6 結(jié)語(yǔ)

綜上所述，短語(yǔ)由詞構(gòu)成，又是構(gòu)成句子的基本單位，是詞與句子之間的過(guò)渡單位，因此短語(yǔ)的語(yǔ)法關(guān)系和語(yǔ)義屬性是由其所構(gòu)成的詞決定的；而短語(yǔ)本身的語(yǔ)法關(guān)系和語(yǔ)義屬性又對(duì)其所構(gòu)成的句子起到了決定性作用。詞層級(jí)的相似度計(jì)算結(jié)果是短語(yǔ)層級(jí)的基礎(chǔ)；而短語(yǔ)層級(jí)的相似度計(jì)算結(jié)果是句子層級(jí)的基礎(chǔ)，如果將短語(yǔ)的關(guān)系進(jìn)行適當(dāng)建模，并結(jié)合相應(yīng)的機(jī)器學(xué)習(xí)算法，一定會(huì)大大提升利用人工智能方法處理自然語(yǔ)言的效果。