夏 飛，曹馨宇，符建輝，王 石，曹存根

(1. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所智能信息處理重點(diǎn)實(shí)驗(yàn)室,北京 100190;2. 中國(guó)科學(xué)院大學(xué),北京 100049)

?

基于并列結(jié)構(gòu)的部分整體關(guān)系獲取方法

夏 飛1,2，曹馨宇1,2，符建輝1，王 石1，曹存根1

(1. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所智能信息處理重點(diǎn)實(shí)驗(yàn)室,北京 100190;2. 中國(guó)科學(xué)院大學(xué),北京 100049)

部分整體關(guān)系是一種基礎(chǔ)而重要的語義關(guān)系，從文本中自動(dòng)獲取部分整體關(guān)系是知識(shí)工程的一項(xiàng)基礎(chǔ)性研究課題。該文提出了一種基于圖的從Web中獲取部分整體關(guān)系的方法，首先利用部分整體關(guān)系模式從Google下載語料，然后用并列結(jié)構(gòu)模式從中匹配出部分概念對(duì)，據(jù)此形成圖，用層次聚類算法對(duì)該圖進(jìn)行自動(dòng)聚類，使正確的部分概念聚集在一起。在層次聚類基礎(chǔ)上，我們挖掘并列結(jié)構(gòu)的特性、圖的特點(diǎn)和漢語的語言特點(diǎn)，采用懲罰逗號(hào)邊、去除低頻邊、獎(jiǎng)勵(lì)環(huán)路、加重相同后綴和前綴等5種方法調(diào)整圖中邊的權(quán)重，在不損失層次聚類的高準(zhǔn)確率條件下，大幅提高了召回率。

部分整體關(guān)系；圖模型；并列結(jié)構(gòu)；層次聚類；邊權(quán)重

1 引言

WordNet和HowNet之類的語義詞典在解決自然語言處理問題時(shí)發(fā)揮著越來越重要的作用，自動(dòng)文摘、信息檢索、自動(dòng)問答等系統(tǒng)常常需要借助這些詞典確定概念之間的語義關(guān)系。語義關(guān)系是構(gòu)建語義詞典的基礎(chǔ)，例如，WordNet中的概念之間就有上位(hypernym)、下位(hyponym)、部分(part-meronym)、整體(part-holonym)等關(guān)系[1]。人工編纂這類語義詞典費(fèi)時(shí)費(fèi)力，因此，有必要研究如何從文本中自動(dòng)獲取語義關(guān)系。

部分整體關(guān)系是一類基礎(chǔ)而重要的語義關(guān)系，人造物及其部件、組織及其成員、化學(xué)試劑及其成分，這些都包含著部分整體關(guān)系。研究部分整體關(guān)系，不僅有助于解決一系列自然語言處理問題，在人造物的設(shè)計(jì)、生化試劑的配置等實(shí)際問題中也有重要應(yīng)用。

近年來網(wǎng)絡(luò)迅猛發(fā)展，電子文檔越來越多，其中蘊(yùn)含的信息越來越豐富，從Web中挖掘知識(shí)成為熱門研究課題。基于此，本文提出了一種基于并列結(jié)構(gòu)的從Web中獲取部分整體關(guān)系的方法，利用部分整體關(guān)系模式從Google獲取語料，匹配出具有并列結(jié)構(gòu)的句子，從中獲取出給定整體概念的部分概念，用層次聚類算法對(duì)候選的部分概念進(jìn)行自動(dòng)聚類。在此基礎(chǔ)上，重點(diǎn)研究了利用圖的特點(diǎn)和漢語的語言特點(diǎn)，對(duì)圖中邊的權(quán)重進(jìn)行調(diào)整而提升層次聚類算法的實(shí)驗(yàn)效果。

本文結(jié)構(gòu)如下： 第2部分將介紹國(guó)內(nèi)外相關(guān)工作，第3部分給出了從Web中初步獲取部分整體關(guān)系的方法，第4、5部分研究利用并列結(jié)構(gòu)特點(diǎn)和漢語語言特點(diǎn)的改進(jìn)方法；第6部分給出實(shí)驗(yàn)結(jié)果并做分析，最后是總結(jié)并展望下一步工作。

2 相關(guān)工作

基于詞匯—句法模式獲取語義關(guān)系，這種方法的依據(jù)是人們經(jīng)常用一些特定的句法結(jié)構(gòu)(即模式)來表述某種語義關(guān)系，因此可以從滿足某些模式的句子中獲取出對(duì)應(yīng)的語義關(guān)系。這種方法由文獻(xiàn)[2]提出。文獻(xiàn)[3]首先將這一方法用于部分整體關(guān)系的獲取，使用模式獲取候選的部分概念，再根據(jù)統(tǒng)計(jì)函數(shù)likelihood選取正確的部分概念，然而受限于使用的模式，他們獲取的部分整體關(guān)系的實(shí)例很少，準(zhǔn)確率較低。

模式的方法也被引入中文領(lǐng)域的部分整體關(guān)系獲取。文獻(xiàn)[4-5]利用基于圖論的方法構(gòu)造部分整體圖，將所有候選概念從全局的角度進(jìn)行分析驗(yàn)證，形成可供使用的知識(shí)庫。文獻(xiàn)[6-7]利用中文語義特征和部分整體關(guān)系的特性，構(gòu)造一系列啟發(fā)式規(guī)則，對(duì)獲取的部分整體關(guān)系進(jìn)行驗(yàn)證。這些方法都是在發(fā)現(xiàn)模式方法的局限性下，希望加強(qiáng)后期的驗(yàn)證以提高獲取效果。

文獻(xiàn)[8]利用模式的方法獲取到部分整體關(guān)系后，借助WordNet標(biāo)注概念的語義特征，構(gòu)建大量的訓(xùn)練集實(shí)例，使用C4.5算法學(xué)習(xí)關(guān)于部分整體關(guān)系的分類規(guī)則，利用這些規(guī)則驗(yàn)證候選的部分整體關(guān)系。在包含10 000條句子的語料中進(jìn)行實(shí)驗(yàn)，最終獲取結(jié)果的準(zhǔn)確率為83%，召回率為98%。然而這一方法對(duì)外部資源和工具的依賴較大，并且需要手工標(biāo)注大量的訓(xùn)練集。

隨著互聯(lián)網(wǎng)的發(fā)展，Web開始替代傳統(tǒng)的語料庫作為知識(shí)獲取的資源。文獻(xiàn)[9]利用Google從Web中獲取表示部分整體關(guān)系的模式，再利用Google和獲取到的模式從Web中獲取已知部分概念的部分整體關(guān)系。他們將這種方法應(yīng)用在食品安全領(lǐng)域，取得了較好的實(shí)驗(yàn)結(jié)果。但是這種方法非常依賴相關(guān)領(lǐng)域的詞典，擴(kuò)展不易。

以并列結(jié)構(gòu)形式出現(xiàn)的概念往往是語義相似的，文獻(xiàn)[10-11]利用這種特性構(gòu)建和擴(kuò)充語義詞典，首先對(duì)于某一類別選出一些種子概念，然后從語料庫中找出與種子概念并列出現(xiàn)的概念，利用一些統(tǒng)計(jì)方法從中篩選出新的種子概念，循環(huán)迭代，最后對(duì)獲取到的所有概念進(jìn)行統(tǒng)計(jì)排名，得到屬于選定類別的概念。

文獻(xiàn)[12]利用并列關(guān)系對(duì)獲取到的概念建圖，以概念為點(diǎn)，以并列關(guān)系為邊，通過增量的聚類算法對(duì)該圖進(jìn)行聚類，將語義相似的概念聚在一起，最終得到了82%的準(zhǔn)確率。他們更進(jìn)一步將這種方法用于語義消歧，對(duì)于一個(gè)概念的多個(gè)義項(xiàng)，利用并列結(jié)構(gòu)找出與這些義項(xiàng)的語義關(guān)系相近的概念，用這些概念作為消歧的依據(jù)。

并列結(jié)構(gòu)也被用于語義關(guān)系的獲取，文獻(xiàn)[13]在初步獲取到的上下位關(guān)系基礎(chǔ)上，利用并列結(jié)構(gòu)從語料中抽取新的上下位關(guān)系，將召回率提高了5倍。文獻(xiàn)[16]將并列結(jié)構(gòu)用于同義詞集的自動(dòng)獲取上，通過并列關(guān)系作圖，使用聚類方法和一些語言學(xué)特征提高獲取精度，取得了很好的結(jié)果。

3 部分整體關(guān)系初步獲取

3.1 部分整體關(guān)系的定義

目前，對(duì)于部分整體關(guān)系的定義和分類，研究者們并沒有統(tǒng)一的認(rèn)識(shí)。Winston et al.在大量語言心理學(xué)實(shí)驗(yàn)的基礎(chǔ)上提出將meronymic關(guān)系分為6類，分別是： component-integral object、member-collection、portion-mass、stuff-object、feature-activity、place-area[14]。這種分類在以后的研究中被廣泛使用。本文獲取的部分整體關(guān)系主要集中在component-integral object這一類，其中的整體通常有一個(gè)結(jié)構(gòu)，它們的組成部分是可分離的并且有特定的功能。這是一類常見的部分整體關(guān)系，主要體現(xiàn)在物體與其部件的關(guān)系上，例如，汽車和輪胎，桌子和桌腿。

一般來說，對(duì)于兩個(gè)概念X與Y，如果它們的關(guān)系可以由“X是Y的一部分”、“Y的組成部分中包括X等”、“Y由X等構(gòu)成”等句子描述，那么可以認(rèn)為它們滿足部分整體關(guān)系，記作partof(X，Y)。例如，partof(發(fā)動(dòng)機(jī)，汽車)，表示發(fā)動(dòng)機(jī)是汽車的部分。

3.2 部分整體關(guān)系的模式

表述部分整體關(guān)系的句法模式有很多，例如，“X是Y的一部分”、“Y包含X”、“Y由X等組成”，這些句子可能都預(yù)示著X與Y之間存在部分整體關(guān)系。然而，有些部分整體關(guān)系模式具有很大的模糊性，例如，常用的“<整體>的<部分>”這一模式，既可以表示部分整體關(guān)系(如，汽車的發(fā)動(dòng)機(jī))，也可以表述屬性(如，汽車的速度)。

因此，我們選擇那些包含并列結(jié)構(gòu)的模式，實(shí)驗(yàn)發(fā)現(xiàn)，這樣的模式獲取到的概念較多，其中的概念較易抽取，且概念之間可以相互驗(yàn)證。

例如，對(duì)于模式“<整體>由<部分>等組成”，可以匹配出下面的句子

1) 汽車由發(fā)動(dòng)機(jī)、底盤、變速箱等組成。

從句子1)中，我們可以很容易抽取出汽車的3個(gè)部分概念： 發(fā)動(dòng)機(jī)、底盤和變速箱。我們使用的模式如表1所示。

表1 部分整體關(guān)系模式

其中，(?整體)是整體概念區(qū)，構(gòu)造查詢串時(shí)會(huì)用給定的整體概念去替換；(?部分)是部分概念區(qū)，表示所要獲取的部分概念，這部分會(huì)替換成通配符“*”；(!部分詞)是一些可以表示部分關(guān)系的詞，例如，“部件”、“零件”、“器件”等，搜索時(shí)會(huì)替換成這些詞。經(jīng)過這些轉(zhuǎn)化，我們就可以得到查詢串。

例如，獲取“汽車”的部分概念時(shí)，模式Com003將轉(zhuǎn)化為下面的查詢串

查詢串： 1)“(等|之類)汽車(部件|零件|器件|元件|組件|構(gòu)件|配件|零部件|元器件)”。

查詢串1)就可以提交給搜索引擎進(jìn)行網(wǎng)頁搜索。

3.3 部分整體關(guān)系的初步獲取

我們使用上面的模式獲取給定整體概念的部分概念，步驟如下：

1) 利用給定的概念將模式轉(zhuǎn)化為查詢串；

2) 到Google中查詢，將搜索出的頁面摘要切割成句子，形成語料；

3) 篩選出滿足模式的句子，并且要求句子中包含并列結(jié)構(gòu)；

4) 用并列符號(hào)和并列詞從句子的并列結(jié)構(gòu)中切割、抽取出概念。

例如，對(duì)于模式Com001和給定的概念“電腦”，我們首先將它轉(zhuǎn)化為下面的查詢串。

2) “電腦(是由|由)”“(組成|構(gòu)成)”。

Google利用查詢串2)獲取到很多的頁面摘要(snippets)，我們抓取出其中的前1 000項(xiàng)，將它們用句號(hào)、問號(hào)、感嘆號(hào)等標(biāo)點(diǎn)符號(hào)切割成句子，再次利用模式Com001從中篩選出可以匹配的句子，并且要求句子中包含并列符號(hào)(頓號(hào)、逗號(hào))或者并列詞(和、與、及等)，最后對(duì)句子中的并列結(jié)構(gòu)進(jìn)行切割，抽取出其中的詞或短語。

例如，Com001匹配到下面的句子，

2) 大家知道，電腦是由主機(jī)、顯示器以及鍵盤、鼠標(biāo)等外設(shè)構(gòu)成的。

利用模式中的關(guān)鍵詞“由”、“構(gòu)成”以及并列符號(hào)和并列詞，我們可以從句子2)中抽取出“主機(jī)”、“顯示器”、“鍵盤”和“鼠標(biāo)等外設(shè)”4個(gè)部分。

我們用一些規(guī)則對(duì)這些初步獲取到的詞或短語進(jìn)行簡(jiǎn)單的預(yù)處理，例如切去頭部的數(shù)量詞，如“四個(gè)輪胎”切成“輪胎”，“一些車燈”切成“車燈”；或者剝離尾部多余的詞，如“鼠標(biāo)等外設(shè)”剝離為“鼠標(biāo)”。最后得到的概念作為候選的部分概念。

我們的評(píng)價(jià)指標(biāo)包括準(zhǔn)確率(P)、召回率(R)和F值，定義如式(1)、(2)、(3)所示。

其中，Cnt(correct-extracted)表示獲取結(jié)果中正確的部分概念數(shù)，Cnt(all-extracted)表示獲取結(jié)果中總的概念數(shù)，Cnt(correct-all)表示語料庫中正確的部分概念數(shù)。我們選取了“冰箱”、“電腦”、“汽車”等27個(gè)常見的人造物做實(shí)驗(yàn)，除了“U盤”、“電熨斗”沒有獲取到相關(guān)的部分概念，“攝像頭”只獲取到了3個(gè)部分概念無法繼續(xù)后面的實(shí)驗(yàn)外，其他概念的初步獲取都取得了較好的結(jié)果。初步獲取實(shí)驗(yàn)中，我們的模式對(duì)部分整體關(guān)系的覆蓋率達(dá)到了88.89%，部分實(shí)驗(yàn)結(jié)果如表2所示?？梢钥闯?，使用并列結(jié)構(gòu)模式獲取部分整體關(guān)系，準(zhǔn)確率較高，獲取的結(jié)果數(shù)也很多。下面的實(shí)驗(yàn)將以初步獲取的結(jié)果為基準(zhǔn)進(jìn)行對(duì)比。

表2 初步獲取部分實(shí)驗(yàn)結(jié)果

4 基于層次聚類的部分整體關(guān)系分析

為了從候選的部分概念中抽取出正確的概念，本節(jié)將介紹一種基于層次聚類的部分整體關(guān)系分析方法。

4.1 層次聚類方法

聚類分析是數(shù)據(jù)挖掘中一種重要的學(xué)習(xí)方法，它按照事物的某些屬性，把事物聚集成類，使類間的相似性盡可能小，類內(nèi)的相似性盡可能大。層次聚類是一種常用的聚類方法，按照層次的形成方式，又分為凝聚的方法和分裂的方法。本文采用的是分裂的方法，它又稱為自頂向下的方法，一開始將所有的對(duì)象都置于同一個(gè)類中，然后通過不斷的迭代，一個(gè)類被分裂為更小的類，直到每個(gè)對(duì)象被歸入某個(gè)單獨(dú)的類中，或者達(dá)到某個(gè)終止條件[15]。

層次聚類算法描述如下：

算法4?1 層次聚類算法輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫，閾值λ輸出：k個(gè)類(1)將所有對(duì)象置于同一個(gè)類中(2)DoBegin(3)在所有類中挑選出具有最大基數(shù)的類Cmax；(4)從Cmax里找出與其他點(diǎn)平均相似度最小的一個(gè)點(diǎn)，記該相似度為Simmin，將該點(diǎn)放入新類Cnew，剩余的放入舊類Cold中。(5)從Cold里找出與Cnew中點(diǎn)的最小相似度不小于Cold中點(diǎn)的最小相似度的點(diǎn)，并將這些點(diǎn)放入Cnew，直到?jīng)]有新的Cold的點(diǎn)被分配給Cnew(6)Cnew和Cold為Cmax分裂成的兩個(gè)類，與其他類一起組成新的類集合(7)Repeat(2)～(6)UntilSimmin<λ(8)End

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

我們?cè)诔醪将@取的部分概念集上采用分裂的層次聚類方法，是基于以下假設(shè)。

假設(shè)1 初始結(jié)果中正確的部分概念占多數(shù)。

假設(shè)2 大多數(shù)正確的部分概念可以通過某些聯(lián)系聚集在一個(gè)類中。

假設(shè)3 錯(cuò)誤的結(jié)果會(huì)聚集成其他不同的類。

其中，假設(shè)1已經(jīng)在初始獲取結(jié)果中得到驗(yàn)證，后兩個(gè)假設(shè)則有待后面實(shí)驗(yàn)的驗(yàn)證。因此，一開始我們假定初始結(jié)果中所有的概念都是正確的部分概念，即將它們置于同一個(gè)類中，然后通過每次迭代，將錯(cuò)誤的概念劃分出去，最后留下所有我們認(rèn)為正確的結(jié)果。

我們定義部分概念共現(xiàn)圖G(V, E)，其中V為結(jié)點(diǎn)的集合，每一個(gè)結(jié)點(diǎn)即為初步獲取到的一個(gè)部分概念；E是邊的集合，結(jié)點(diǎn)間是否有邊連接取決于它們所代表的概念是否以并列結(jié)構(gòu)的形式出現(xiàn)在同一個(gè)句子中，邊的權(quán)重為共現(xiàn)次數(shù)。即，對(duì)于兩個(gè)概念Pi、Pj，若它們以并列結(jié)構(gòu)“Pi+ /c + Pj”的形式出現(xiàn)了w次，則它們所在邊的權(quán)重weight(Pi, Pj)=w。在權(quán)重基礎(chǔ)上，我們定義兩個(gè)概念Pi、Pj的相似度為它們邊的權(quán)重與其中度較小的點(diǎn)的度的比值，即式(4)。

simWeight(Pi, Pj)=

對(duì)于聚類過程中的某個(gè)類Ci，我們定義它的基數(shù)為其中對(duì)象的個(gè)數(shù)，即Card(Ci)=| Ci|?；谶@樣的定義，分裂聚類時(shí)每次都將基數(shù)最大的類，即具有最多對(duì)象的類別分開，將錯(cuò)誤的概念劃分出去，最后留下的是我們認(rèn)為正確的結(jié)果。這與我們上文的假設(shè)是一致的。這樣做雖然會(huì)降低召回率，并造成F值偏低，但可以大大提高準(zhǔn)確率。通過觀察研究這一部分準(zhǔn)確率較高的結(jié)果，我們提出后文的改進(jìn)方法，將“散落在外”的其他正確概念吸收回來，以提高最終的F值。

例如，初步獲取到的“汽車”的部分概念可以構(gòu)成如下概念共現(xiàn)圖(圖1)，省略的概念用加矩形框的省略號(hào)表示。

圖1 “汽車”的部分概念共現(xiàn)圖

我們用算法4-1對(duì)該圖進(jìn)行聚類，最后輸出的k個(gè)類中基數(shù)最大的類為實(shí)驗(yàn)結(jié)果。表3給出了實(shí)驗(yàn)結(jié)果，可以看出層次聚類對(duì)準(zhǔn)確率的提升較明顯，對(duì)比初步獲取59.9%的準(zhǔn)確率，在λ的不同取值下“汽車”的準(zhǔn)確率均提升了超過20%。其中，λ越小，聚類算法分裂次數(shù)越多，對(duì)象越“分散”，準(zhǔn)確率高，召回率則相應(yīng)較低；λ越大，聚類算法分裂次數(shù)越少，對(duì)象越“集中”，準(zhǔn)確率降低，召回率則相應(yīng)提升。λ取0.4時(shí)，F(xiàn)值最大，所以我們的實(shí)驗(yàn)將在λ=0.4下進(jìn)行?？偟膩砜?，實(shí)驗(yàn)結(jié)果顯示出召回率的不足，接下來的實(shí)驗(yàn)將逐步改進(jìn)層次聚類的效果。

表3 層次聚類實(shí)驗(yàn)結(jié)果

5 對(duì)部分整體關(guān)系獲取層次聚類方法的改進(jìn)

為提高層次聚類方法的效果，我們可以利用各種知識(shí)來調(diào)整邊的權(quán)重。本文通過去除原始數(shù)據(jù)中的噪音，以及利用漢語的語言特點(diǎn)，大幅提升了部分整體關(guān)系獲取的準(zhǔn)確率和召回率。

5.1 懲罰逗號(hào)邊

漢語中，逗號(hào)除了可以表示句子成分之間的并列外，還可以用于分開句內(nèi)各詞語或表示語氣的停頓等。相比頓號(hào)，逗號(hào)連接的兩個(gè)概念表示并列關(guān)系的可能性降低。例如，下面這條句子：

3) 凱翔達(dá)汽車配件有限公司，日產(chǎn)公爵前嘴，機(jī)蓋，車門，葉子板，倒車鏡等汽車配件。

“日產(chǎn)公爵前嘴”、“機(jī)蓋”、“車門”等等都是汽車的部件，此時(shí)中間的逗號(hào)作并列成分的分隔用；但句首的“凱翔達(dá)汽車配件有限公司”并非汽車的部件，后面的逗號(hào)用來表示分句的停頓。

因此，對(duì)于逗號(hào)連接的邊，可以施行懲罰，降低它的權(quán)重。

設(shè)概念Pi和Pj在“Pi+ ，+ Pj”中出現(xiàn)了c1次，在“Pi+ 、+ Pj”中出現(xiàn)了c2次，則式(5)為：

Weight1(Pi,Pj)=λ1×c1+c2

(5)

其中0<λ1<1，即將圖中逗號(hào)邊的權(quán)重縮小為原來的λ1倍。懲罰逗號(hào)邊的實(shí)驗(yàn)結(jié)果如表4所示。

表4 懲罰逗號(hào)邊實(shí)驗(yàn)結(jié)果

其中λ1=1時(shí)即為表3層次聚類算法的結(jié)果。由表中數(shù)據(jù)看出，懲罰逗號(hào)邊可以略微提升準(zhǔn)確率，λ1越小，準(zhǔn)確率提升越多，但召回率也會(huì)相應(yīng)降低。λ1取0.75時(shí)，F(xiàn)值最大，所以我們后續(xù)的實(shí)驗(yàn)將在λ1=0.75下進(jìn)行。

5.2 去除低頻邊

當(dāng)一個(gè)錯(cuò)誤的概念Pi偶然與一個(gè)正確的部分概念Pj共現(xiàn)在并列結(jié)構(gòu)中時(shí)，這種關(guān)聯(lián)很有可能會(huì)造成錯(cuò)誤傳染，使得與Pi共現(xiàn)的其他錯(cuò)誤概念聚集到表示正確概念的類中。因此，出現(xiàn)次數(shù)較少的邊有可能是噪音，可以通過切斷權(quán)重小于某個(gè)閾值的邊來減少此類錯(cuò)誤。

在4.1節(jié)懲罰逗號(hào)邊實(shí)驗(yàn)的基礎(chǔ)上：

若Weight1(Pi, Pj)≤λ2，則去除邊(Pi, Pj)；否則

Weight2(Pi, Pj)=Weight1(Pi, Pj)

表5顯示了去除低頻邊的實(shí)驗(yàn)結(jié)果，其中λ2=0時(shí)為表4懲罰逗號(hào)邊的結(jié)果，即不刪除任何邊。λ2越大，刪除的邊越多，此時(shí)召回率降低較多。λ2取0.75時(shí)F值最大，此時(shí)去除只用逗號(hào)連接的邊，后續(xù)的實(shí)驗(yàn)將在這一取值下進(jìn)行。這一節(jié)實(shí)驗(yàn)與上一節(jié)結(jié)合在一起，顯示出逗號(hào)在句中作用的模糊性，即通過逗號(hào)連接的句子成分不一定是并列的。

表5 去除低頻邊實(shí)驗(yàn)結(jié)果

5.3 獎(jiǎng)勵(lì)環(huán)路

對(duì)于兩個(gè)概念Pi和Pj，若它們同時(shí)出現(xiàn)在對(duì)稱的并列結(jié)構(gòu)“Pi+ /c + Pj”和“Pj+ /c + Pi”中，則它們之間的聯(lián)系要比只出現(xiàn)在單向并列結(jié)構(gòu)中的概念要緊密。推而廣之，對(duì)于概念Pk1, Pk2, … , Pkn(n>=3)，若它們形成“Pk1+ /c + Pk2”, “Pk2+ /c + Pk3”, … , “Pkn+ /c + Pk1”這樣的環(huán)路，則它們之間的聯(lián)系也更緊密，可以增加這些邊的權(quán)重。

我們?cè)趫D上進(jìn)行搜索，找到所有這樣的環(huán)路。對(duì)于概念Pi、Pj，如果邊(Pi, Pj)出現(xiàn)在環(huán)路上，則如式(6)所示。

表6顯示了獎(jiǎng)勵(lì)環(huán)路后的實(shí)驗(yàn)結(jié)果，其中 λ3=1 時(shí)為表5去除低頻邊的結(jié)果，即不增加環(huán)路上的邊的權(quán)重。總的來看，獎(jiǎng)勵(lì)環(huán)路對(duì)準(zhǔn)確率的提升并不明顯，原因應(yīng)當(dāng)是圖中的環(huán)路并不多。λ3取3時(shí)F值最大，后續(xù)的實(shí)驗(yàn)將在這一取值下進(jìn)行。

表6 獎(jiǎng)勵(lì)環(huán)路實(shí)驗(yàn)結(jié)果

5.4 加重相同后綴

觀察發(fā)現(xiàn)，同屬一個(gè)整體的部件概念常常有相同的后綴，如“汽車”的部件“發(fā)動(dòng)機(jī)”、“發(fā)電機(jī)”、“方向機(jī)”、“起動(dòng)機(jī)”有相同的后綴“機(jī)”，“車架總成”、“前缸骨架總成”、“轉(zhuǎn)向縱橫拉桿總成”有相同的后綴“總成”。這是因?yàn)楦鶕?jù)漢語的構(gòu)詞特點(diǎn)，如果兩個(gè)概念的后綴相同，則它們屬于同一個(gè)語義類的可能性就很大。因此，如果兩個(gè)概念的后綴相同，可以增加它們的邊的權(quán)重。

本文在分詞后的基礎(chǔ)上計(jì)算概念的后綴，對(duì)于某個(gè)概念P，設(shè)其分詞后的結(jié)果為w1w2…wn，則其后綴Suf(P)按式(7)計(jì)算：

(7)

其中LC(P)表示取P的最后一個(gè)字(Last Character)。例如，“怠速馬達(dá)”的分詞結(jié)果為“怠/a 速/a 馬達(dá)/n”，則Suf(“怠速馬達(dá)”)=“馬達(dá)”，同理，Suf(“倒車?yán)走_(dá)”)=“雷達(dá)”， Suf(“馬自達(dá)”)=“達(dá)”，三者的后綴并不相同。另外，“發(fā)動(dòng)機(jī)”作為常見詞，其分詞結(jié)果為“發(fā)動(dòng)機(jī)/n”，則Suf(“發(fā)動(dòng)機(jī)”)=“機(jī)”，同理，Suf(“發(fā)電機(jī)”)=“機(jī)”，Suf(“暖風(fēng)機(jī)”)=“機(jī)”，它們具有相同的后綴。

兩個(gè)概念Pi和Pj基于后綴的相似度定義為式(8)所示。

在5.2節(jié)去除低頻邊實(shí)驗(yàn)的基礎(chǔ)上如式(9)所示。

Weight4(Pi, Pj)= Weight3(Pi, Pj)+

表7顯示了加重相同后綴的實(shí)驗(yàn)結(jié)果，其中 λ4=0時(shí)為表6獎(jiǎng)勵(lì)環(huán)路的結(jié)果?？梢钥闯觯@一步改進(jìn)對(duì)實(shí)驗(yàn)結(jié)果的影響主要體現(xiàn)在召回率上，λ4不同取值下“汽車”的召回率都有超過30個(gè)百分點(diǎn)的提升，顯示出“汽車”的很多部件概念都有相同的后綴。λ4取3時(shí)F值最大，后續(xù)的實(shí)驗(yàn)將在這一取值下進(jìn)行。

表7 加重相同后綴實(shí)驗(yàn)結(jié)果

5.5 加重相同前綴

在漢語中，概念的前綴常常與概念本身構(gòu)成部分整體關(guān)系。例如，“車把”、“車座”、“車軸”、“車筐”、“車輪”有相同的前綴“車”，它們都是“(自行)車”的部件；“發(fā)動(dòng)機(jī)罩蓋”、“發(fā)動(dòng)機(jī)散熱器”、“發(fā)動(dòng)機(jī)缸體”有相同的前綴“發(fā)動(dòng)機(jī)”，它們都是“發(fā)動(dòng)機(jī)”的部件，也是“汽車”的部件。因此，如果兩個(gè)概念的前綴相同，則它們與同一個(gè)概念構(gòu)成部分整體關(guān)系的可能性就很大，可以增加它們的邊的權(quán)重。

本文在分詞后的基礎(chǔ)上計(jì)算概念的前綴，對(duì)于某個(gè)概念P，設(shè)其分詞后的結(jié)果為w1w2…wn，則其前綴Pre(P)按式(10)計(jì)算：

(10)

其中FC(P)表示取P的第一個(gè)字(First Character)。例如，“車把”的分詞結(jié)果為“車把/n”，則Pre(“車把”)=“車”；“車筐”的分詞結(jié)果為“車/n 筐/n”，則Pre(“車筐”)=“車”，兩者具有相同的前綴。

兩個(gè)概念Pi和Pj基于前綴的相似度定義如式(11)所示。

在5.2節(jié)去除低頻邊實(shí)驗(yàn)的基礎(chǔ)上如式(12)所示。

Weight5(Pi, Pj)= Weight4(Pi, Pj)+

表8顯示了加重相同前綴的實(shí)驗(yàn)結(jié)果，其中 λ5=0時(shí)為表7加重相同后綴的結(jié)果，λ5=1時(shí)F值最大，最終的準(zhǔn)確率達(dá)到了76.87%，召回率更是達(dá)到91.68%。這一節(jié)與上一節(jié)一起，顯示出在漢語詞匯中，前后綴蘊(yùn)含了豐富的語義信息。

表8 加重相同前綴實(shí)驗(yàn)結(jié)果

6 實(shí)驗(yàn)結(jié)果及分析

我們選擇了初步獲取結(jié)果中可以繼續(xù)實(shí)驗(yàn)的24個(gè)概念，用層次聚類算法與上一節(jié)提出的改進(jìn)方法和取值進(jìn)行實(shí)驗(yàn)。因?yàn)槲覀兪窃讷@取未知的知識(shí)，無法確知某一概念有哪些部分概念，數(shù)量多少，理論上我們無法計(jì)算實(shí)驗(yàn)的召回率。因此，我們?cè)诔醪将@取后，從語料中人工標(biāo)注出其中的正確與錯(cuò)誤的結(jié)果，假設(shè)其中正確的部分概念數(shù)為總的正確概念數(shù)，以此為基準(zhǔn)計(jì)算召回率和F值，結(jié)果如表9所示。其中Cnt(correct-all)表示語料中正確的部分概念數(shù)。

可以看出，我們的層次聚類算法擁有較高的準(zhǔn)確率，普遍在70%以上；在聚類基礎(chǔ)上的改進(jìn)研究主要在召回率的提升上發(fā)揮了作用，從而提高了F值。綜合來看，我們的方法的優(yōu)點(diǎn)是： 既有效地利用了統(tǒng)計(jì)信息(詞頻、共現(xiàn)度)，又結(jié)合了語義信息(漢語前后綴)。

對(duì)于初步獲取得到部件較多的概念，這種優(yōu)點(diǎn)帶來的效果很明顯。例如，“打印機(jī)”、“手機(jī)”、“自行車”等，我們從Web中獲取到的對(duì)應(yīng)語料較多，統(tǒng)計(jì)出來的詞頻等信息較豐富，可利用的前后綴等信息也較明顯。因此，它們的F值都達(dá)到80%以上。

我們的方法也存在不足，數(shù)據(jù)稀疏是我們面臨的一大問題。對(duì)于“冰箱”、“收音機(jī)”這些概念，我們下載到的對(duì)應(yīng)語料較少，從中獲取的部件概念也少，因而可利用的統(tǒng)計(jì)信息不明顯，前后綴等語義信息也不豐富，導(dǎo)致這些概念的實(shí)驗(yàn)結(jié)果稍差，尤其是召回率。

表9 實(shí)驗(yàn)結(jié)果

除此之外，我們還有其他待解決的問題。

1) 術(shù)語識(shí)別不干凈帶來的錯(cuò)誤。例如，在獲取到的“手機(jī)”的部件中，存在“商務(wù)電池”、“諾基亞耳機(jī)”這樣的概念，需要從中識(shí)別出“電池”、“耳機(jī)”這樣的“干凈”的術(shù)語。達(dá)到這樣的識(shí)別效果，可能需要借助某些領(lǐng)域詞典。

2) 配件概念帶來的錯(cuò)誤。在獲取到的部件中，夾雜著一些配件概念。例如，獲取“電腦”的部件時(shí)，也返回了一些“網(wǎng)線”、“鼠標(biāo)墊”之類的配件。這既源自于網(wǎng)頁文本中表述部分整體關(guān)系的不嚴(yán)謹(jǐn)，也與我們下載語料時(shí)所用的模式有關(guān)。

根據(jù)我們實(shí)驗(yàn)的初步結(jié)果，當(dāng)這些問題得到解決后，實(shí)驗(yàn)結(jié)果的準(zhǔn)確率可以提升2%～4%。

在將來的工作中，我們會(huì)引入其他模式和方法，以獲取更多的語料；同時(shí)會(huì)用迭代的方法獲取更多的候選部分概念，以使層次聚類發(fā)揮出應(yīng)有的效果。區(qū)分出部件和配件的不同，有賴于對(duì)部分整體關(guān)系分類的更深入研究。

7 結(jié)束語

從文本中自動(dòng)獲取部分整體關(guān)系是知識(shí)工程的一項(xiàng)基礎(chǔ)性研究課題，本文利用Google獲取語料，采用并列結(jié)構(gòu)模式從中匹配出部分概念對(duì)形成圖，用層次聚類算法對(duì)候選的部分概念進(jìn)行自動(dòng)聚類。在此基礎(chǔ)上，重點(diǎn)研究了利用圖的特點(diǎn)和漢語的語言特點(diǎn)，對(duì)圖中邊的權(quán)重進(jìn)行調(diào)整而提升層次聚類算法的實(shí)驗(yàn)效果。我們的方法的優(yōu)點(diǎn)是既有效地利用了統(tǒng)計(jì)信息，又結(jié)合了語義信息。我們選擇了一些概念，用本文的方法獲取它們的部分概念，實(shí)驗(yàn)表明，我們的方法是有效的。

當(dāng)然，我們的方法也存在一些不足，主要表現(xiàn)在以下兩個(gè)方面。

1) 由于數(shù)據(jù)稀疏，統(tǒng)計(jì)和語義特征不明顯，當(dāng)給定的整體概念在初步獲取時(shí)得到的候選部分概念較少時(shí)，層次聚類和改進(jìn)方法并沒有給出較好的結(jié)果；

2) 獲取的部件結(jié)果中也存在一些術(shù)語識(shí)別和配件夾雜的問題。

[1] George A Miller. WordNet: A Lexical Database for English[J]. Communications of the ACM, 1995, 38:39-41

[2] M A Hearst, Automatic Acquisition of hyponyms from large text corpora[C]//Proceedings of the 14th International Conference on Computational Linguistics (COLING-92), Nantes,France, 1992: 539-545.

[3] M Berland, E Charniak. Finding Parts in Very Large Corpora[C]//Proceedings of the the 37th Annual Meeting of the Association for Computational Linguistics (ACL-99). 1999.

[4] J Wu, B Luo, C G Cao,et al. Acquisition and Verification of Mereological Knowledge from Web Page Texts[J]. Journal of East China University of Science and Technology(Natural Science Edition), Shanghai, China, 2006: 1310-1317.

[5] 吳潔. 網(wǎng)絡(luò)文本中部分關(guān)系知識(shí)的獲取與驗(yàn)證方法[D]. 上海:華東理工大學(xué)碩士學(xué)位論文. 2006

[6] Xinyu C, Cungen C, Shi W， et al. Extracting Part-Whole Relations from Unstructured Chinese Corpus[C]//Proceedings 4th International Conference on Natural Computation (ICNC’08) and 5th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD’08), Jinan, China. 2008.

[7] 曹馨宇. 部分整體關(guān)系的獲取與分析研究[D]. 北京: 中國(guó)科學(xué)院大學(xué)博士學(xué)位論文. 2012

[8] R Girju, A Badulescu， D Moldovan, Automatic Discovery of Part-Whole Relations[J].Computational Linguistics, 2006,32(1): 83-135.

[9] R H Willem, H Kolb， G Schreiber. A method for learning part-whole relations[C]//Proceedings of the 5th Int. Semantic Web Conf., LNCS, 2006:723-736.

[10] Ellen Riloff， Jessica Shepherd. A corpus-based approach for building semantic lexicons[C]//Proceedings of the Second Conference on empirical Methods in Natural Language Processing, 1997:117-124.

[11] Brian Roark, Eugene Charniak. Noun-phrase cooccurence statistics for semi-automatic semantic lexicon construction[C]//Proceedings of COLING-ACL, 1998:1110-1116.

[12] Dominic Widdows, Beate Dorow. A graph model for unsupervised lexical acquisition[C]//Proceedings of the 19th International Conference on Computational Linguistics,2002:1093-1099.

[13] Cederberg S, D Widdows. Using LSA and noun coordination information to improve the precision and recall of hyponymy extraction[C]//Proceedings of CoNLL, 2003:111-118.

[14] M E Winston, R Chaffin, D Herrman. A taxonomy of part-whole relations[J]. Cognitive Science, 1987，11(4):417-444.

[15] Jiawei H, Micheline K, Jian P. Data Mining: Concept and Techniques[M], Second Edition. Morgan Kaufmann, 2005:408-410.

[16] 吳云芳,石靜,金彭.基于圖的同義詞集自動(dòng)獲取方法[J].《計(jì)算機(jī)研究與發(fā)展》,2011,48(4): 610-616.

Extracting Part-Whole Relations Based on Coordinate Structure

XIA Fei1,2, CAO Xinyu1,2, FU Jianhui1, WANG Shi1, CAO Cungen1

(1. Key Laboratory of Intelligent Information Processing,Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China;2. University of Chinese Academy of Sciences, Beijing 100049， China)

Automatic discovery of part-whole relations from the Web is a fundamental but critical problem in knowledge engineering. This paper proposes a graph-based method of extracting part-whole relations from the Web. Firstly, we download snippets from Google using part-whole query patterns, and then we built a graph by extracting word pairs with a coordinate structure from these snippets, with the co-occurring words as nodes and the frequency count as edges’ weight. A hierarchical clustering method is used to cluster the correct parts, which is optimized by five methods of adjusting the edge weight: reduce the weight of comma-edges, cut the low-frequency edges, enlarge the weight of edges in the loop, enlarge the weight of edges in which two nodes share the same suffix, and enlarge the weight of edges in which two nodes share the same prefix. Experimental results show that the five methods increase the recall substantially.

part-whole relations; graph model; coordinate structure; hierarchical clustering; edge weight

夏飛(1986—)，博士研究生，主要研究領(lǐng)域?yàn)橹R(shí)獲取、文本挖掘。E?mail：xiafei．1986@163．com曹馨宇(1982—)，博士，主要研究領(lǐng)域?yàn)槿斯ぶ悄?、知識(shí)工程。E?mail：cxy8202@163．com符建輝(1985—)，博士研究生，助理研究員，主要研究領(lǐng)域?yàn)橹悄苘浖痛笠?guī)模知識(shí)處理。E?mail：fjh5228203@126．com

1003-0077(2015)01-0088-09

2012-06-07 定稿日期： 2012-10-29

國(guó)家自然科學(xué)基金(91224006、61173063、61035004、61203284、309737163)、國(guó)家社科基金(10AYY003)

TP391

A