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

(1. 中國科學院計算技術(shù)研究所智能信息處理重點實驗室,北京 100190;2. 中國科學院大學,北京 100049)

?

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

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

(1. 中國科學院計算技術(shù)研究所智能信息處理重點實驗室,北京 100190;2. 中國科學院大學,北京 100049)

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

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

1 引言

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我們的評價指標包括準確率(P)、召回率(R)和F值，定義如式(1)、(2)、(3)所示。

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

表2 初步獲取部分實驗結(jié)果

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

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

4.1 層次聚類方法

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

層次聚類算法描述如下：

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

4.2 實驗結(jié)果

我們在初步獲取的部分概念集上采用分裂的層次聚類方法，是基于以下假設(shè)。

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

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

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

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

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

simWeight(Pi, Pj)=

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

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

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

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

表3 層次聚類實驗結(jié)果

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

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

5.1 懲罰逗號邊

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

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

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

因此，對于逗號連接的邊，可以施行懲罰，降低它的權(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，即將圖中逗號邊的權(quán)重縮小為原來的λ1倍。懲罰逗號邊的實驗結(jié)果如表4所示。

表4 懲罰逗號邊實驗結(jié)果

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

5.2 去除低頻邊

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

在4.1節(jié)懲罰逗號邊實驗的基礎(chǔ)上：

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

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

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

表5 去除低頻邊實驗結(jié)果

5.3 獎勵環(huán)路

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

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

表6顯示了獎勵環(huán)路后的實驗結(jié)果，其中 λ3=1 時為表5去除低頻邊的結(jié)果，即不增加環(huán)路上的邊的權(quán)重?？偟膩砜矗剟瞽h(huán)路對準確率的提升并不明顯，原因應(yīng)當是圖中的環(huán)路并不多。λ3取3時F值最大，后續(xù)的實驗將在這一取值下進行。

表6 獎勵環(huán)路實驗結(jié)果

5.4 加重相同后綴

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

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

(7)

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

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

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

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

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

表7 加重相同后綴實驗結(jié)果

5.5 加重相同前綴

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

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

(10)

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

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

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

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

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

表8 加重相同前綴實驗結(jié)果

6 實驗結(jié)果及分析

我們選擇了初步獲取結(jié)果中可以繼續(xù)實驗的24個概念，用層次聚類算法與上一節(jié)提出的改進方法和取值進行實驗。因為我們是在獲取未知的知識，無法確知某一概念有哪些部分概念，數(shù)量多少，理論上我們無法計算實驗的召回率。因此，我們在初步獲取后，從語料中人工標注出其中的正確與錯誤的結(jié)果，假設(shè)其中正確的部分概念數(shù)為總的正確概念數(shù)，以此為基準計算召回率和F值，結(jié)果如表9所示。其中Cnt(correct-all)表示語料中正確的部分概念數(shù)。

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

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

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

表9 實驗結(jié)果

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

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

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

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

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

7 結(jié)束語

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

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

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

2) 獲取的部件結(jié)果中也存在一些術(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)系知識的獲取與驗證方法[D]. 上海:華東理工大學碩士學位論文. 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]. 北京: 中國科學院大學博士學位論文. 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] 吳云芳,石靜,金彭.基于圖的同義詞集自動獲取方法[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)域為知識獲取、文本挖掘。E?mail：xiafei．1986@163．com曹馨宇(1982—)，博士，主要研究領(lǐng)域為人工智能、知識工程。E?mail：cxy8202@163．com符建輝(1985—)，博士研究生，助理研究員，主要研究領(lǐng)域為智能軟件和大規(guī)模知識處理。E?mail：fjh5228203@126．com

1003-0077(2015)01-0088-09

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

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

TP391

A