基于三支決策的兩階段實體關系抽取研究

朱艷輝，李 飛，胡駿飛，錢繼勝 ，王天吉

ZHU Yanhui1，2,LI Fei1，2,HU Junfei1，2,QIAN Jisheng3,WANG Tianji1，2

1.湖南工業大學 計算機學院，湖南 株洲 412008

2.湖南工業大學 湖南省智能信息感知及處理技術重點實驗室，湖南 株洲 412008

3.中國人民銀行 銅陵市中心支行，安徽 銅陵 244000

1.School of Computer Science,Hunan University of Technology,Zhuzhou,Hunan 412008,China

2.Hunan Key Laboratory of Intelligent Information Perception and Processing Technology,Hunan University of Technology,Zhuzhou,Hunan 412008,China

3.The People’s Bank of China Tongling Central Sub-branch,Tongling,Anhui 244000,China

1 引言

隨著計算機的普及和知識工程的蓬勃發展，信息量正以指數級的規模爆炸式增長。人們迫切地需要一些自動化的工具幫助人們在海量數據源中快速檢索到需要的知識。信息抽取（Information Extraction）研究以此為背景應運而生。其主要目的是將互聯網中海量的非結構化數據轉化為結構化或半結構化信息形成“知識”，供用戶查詢以及進一步分析挖掘。信息抽取在信息檢索、知識表示、篇章理解、智能問答等領域具有重要的應用價值。信息抽取從文本中抽取出特定的事實稱之為“實體”，然而大多數應用中不僅需要“實體”，還要確定這些實體的關系，稱其為實體關系抽取。美國國家標準技術研究院（NIST）組織了自動內容抽取（Automatic Content Extraction，ACE），其評測任務之一就是實體關系識別。實體關系抽取通過識別命名實體，進而抽象出實體間關系類型，如NIST定義了制造使用關系（ART）、組織機構從屬關系（ORG-AFF）、局部整體關系（PARTWHOLE）等關系類型。因此可將關系抽取問題轉化為多分類問題。首先識別出句子中所有的實體對，然后使用分類器決定實體關系類型屬于預定義的哪一類。

許多學者采用SVM分類器進行實體關系抽取，車萬翔[1]等人使用SVM構造不同窗口大小的特征向量，在ACE2004語料上取得了較好的分類效果。劉紹毓[2]等對SVM模糊邊界樣本進行雙投票，對模糊樣本采用KNN分類器進行二次分類，大大提高了實體關系抽取的準確率。但是，雖然SVM具有較強的抗噪聲能力和較高的分類準確率等優點，但該分類器對于分布在超平面附近區域的樣本分類效果不理想。當處理多分類任務時，樣本在超平面附近的類交疊區域的分類效果更差。故隨著分類類別數的增多，由于各個類別樣本交疊愈加嚴重，從而影響分類準確率。

三支決策理論[3-6]是傳統二支決策理論的拓展，二支決策只考慮接受或者拒絕（或者是或否）兩種選擇。但是實際應用中，由于信息的不確定性和不全面性，無法明確對一個事物明確的判斷接受或是拒絕。因此，Yao（姚一豫）[7-8]提出了三支決策理論，當判決信息不足以判斷接受或者拒絕時，采用不承諾選擇，然后再加入細粒度信息進行下一步判斷[9]。李金海[10]論述了三支決策與概念格相結合的研究進展，針對兩個結合點：三支概念分析和三支概念學習進行對比分析，提出了兩種思維的互補性。并且提出一種建立不完整的上下文近似概念格的新方法[11]，通過從不完全決策環境中提取非冗余近似決策規則，進一步提高了三支決策在信息不完備情況下的決策效率。二支決策和三支決策就應用場景而言各有優劣，在信息充足、消息準確時，采用二支決策，可使得決策迅速簡潔。在信息不足或者獲取信息代價過大時，適合使用三支決策，可以權衡利弊，等待細粒度的信息，再做出進一步判斷。三支決策策略提供了一個很好的權衡資源和效益的決策框架。

本文將三支決策應用到實體關系抽取領域，對信息不足以判斷實體關系屬于哪一類型的樣本，引入中間類別（中間域）。針對SVM分類器交疊區域樣本難以界定的問題，提出一種基于三支決策的兩階段實體關系抽取方法。首先構建SVM三支決策分類器實現第一階段實體關系抽取，采用softmax函數作為三支決策概率函數，然后采用KNN分類器對三支決策分類后的中間域樣本進行二階段分類。并將結果與SVM分類方法和一階段SVM三支決策分類方法進行比較實驗，實驗結果表明，基于三支決策兩階段分類實體關系抽取方法取得了很好的抽取效果。

2 三支決策理論

三支決策理論是在粗糙集和決策粗糙集理論之上提出的，Yao通過對粗糙集理論中的正、負、邊界區域語義方面研究，提出了從三支決策角度解釋粗糙集中規則提取問題。其規則分別對應對象所屬的正、負、邊界三個區域，根據對象所屬區域不同，分別判決該對象屬于目標類、不屬于目標類、不承諾是否屬于目標類的三支決策策略，對于決策粗糙集模型所需的閾值參數可由決策損失函數決定。

2.1 決策粗糙集理論

定義一個四元組W=(U,At=B?C,{Va|a∈At},{Ia|a∈At})，其中U是一個有限且非空的數據對象集合[12]，At是一個非空且有限屬性集合，B是條件屬性，C是決策屬性，B?C=?，Va為屬性值的集合，Ia是對象U到Va的一個映射，稱為信息函數，即將集合U映射到屬性值域Va上。(U,EA)是屬性集合A上的近似集合，U/EA是基于關系集合EA對對象集合的劃分，EA定義如下：

則包含對象x的等價類可表示為：

判斷一個對象是否屬于決策類可用狀態集合Ω={X,?X}表示，則等價類[x]屬于決策類X的概率函數為：

不屬于決策類X的概率函數為：

2.2 三支決策閾值

Yao等人提出了決策粗糙集模型，并定義了如下三個域（設閾值0≤ β ＜ α≤1）：

其中 POS(α,β)(X)、BND(α,β)(X)、NEG(α,β)(X)分別稱為X的正域、邊界域、負域。

當對象 x屬于決策類 X時，令 λpp、λnp、λbp為分別劃分到 POS(α,β)(X)、BND(α,β)(X)、NEG(α,β)(X)的損失函數。當對象x不屬于決策類時，則令λpn、λbn、λnn為劃分到相同三個域的損失函數。則損失函數表如表1所示。

表1 損失函數表

對于三個域的風險決策，結合貝葉斯決策理論給出的最小風險決策規則。可知：

則以上決策規則簡化如下：

在[x]A的情況下，如果X發生的概率大于等于α，則將[x]A劃分為X的正域，如果X發生概率大于β小于α，則將[x]A劃分為X的邊界域，如果X發生的概率小于等于β，則將[x]A劃分為X的負域[13]。

3 特征抽取

本文采用詞匯、實體類型、位置等作為文本特征。

（1）詞匯

實體本身所包含的所有詞匯，以及實體左右的詞匯對確定實體之間的關系有很好的作用。例如，“微軟公司創始人比爾蓋茨從哈佛大學退學后創辦微軟公司”。實體“微軟”和實體“比爾蓋茨”屬于雇傭關系，其中在實體“微軟”附近的詞（公司、創辦）對實體“比爾蓋茨”很有指示作用。所以實體窗口詞對于分類也十分關鍵，但是窗口太大，會引入太多無關信息。窗口太小，又會導致重要信息的遺漏。車萬翔等人經過重復實驗驗證了在窗口取2時，分類能取得最好的效果，故本文取實體上下文窗口為2的詞，如表2所示。E1、E1pos表示實體1詞匯及詞性，E2、E2pos表示實體2詞匯及詞性。E1L1、E1L1pos表示實體左側第一個詞及其詞性，E1L2、E1L2pos表示實體左側第二個詞及其詞性，E1R1、E1R1pos、E1R2、E1R2pos表示實體右側第一、二個詞及其詞性。E2同理。

（2）位置特征

實體的位置特征以及實體的先后順序對于關系類型有很大影響。董靜[14]等人對ACE語料樣本特征進行分析，提取實體包含和非包含關系特征對實體關系抽取，證明了實體包含和非包含特征對實體關系抽取有一定影響。本文采取的實體位置特征如表3所示。

表2 實體詞和上下文特征

表3 實體位置特征

（3）實體類型

實體關系分類中實體類型及其組合特征[15]是一個非常重要的特征，對分類準確與否至關重要，實體類型特征標記如表4所示。

表4 實體類型特征

4 基于三支決策的兩階段實體關系抽取

本文通過構造SVM三支決策分類器，進行一階段實體關系抽取，然后采用KNN分類器對三支決策中間域樣本進行二階段實體關系抽取，從而實現基于三支決策的兩階段實體關系抽取。實體關系抽取流程圖如圖1所示。

4.1 SVM三支決策分類器構建

鑒于實體關系抽取是一個多分類問題，SVM提供了多分類方法：一種是one-against-rest方法，基本思想是對于M(M≥3)類樣本，將其中一類和其余類分別作為正、負例來訓練分類器，M個類別需構建M個分類器。另一種是one-against-one方法，基本思想是對于M(M≥3)類樣本，每兩類訓練一個分類器，M個類別需構建M(M-1)/2個分類器。鑒于one-against-rest方法分類速度較快，訓練分類器數目較少，本文采用oneagainst-rest方法。在三支決策分類器的構建中，針對多分類問題，采用softmax函數作為概率函數，計算每個樣本屬于某類的概率值，計算公式如式（8）所示：

圖1 實體關系抽取流程圖

SVM三支決策分類器構造算法如下：

輸入：訓練集U，測試集C，類別集合k。

輸出：實體類別集Set(T)，邊界域（中間域）樣本集Set(MID)，No-Relation樣本集 Set(F)。

訓練階段：

步驟1輸入訓練集樣本集合U。

步驟2使用SVM分類器對訓練集U進行訓練，得到SVM分類模型。

測試階段：

步驟1輸入測試集樣本集合C。

步驟2 forci∈C，使用訓練好的SVM分類器進行分類。

步驟3由式（8）計算C中所有樣本對象分別屬于類別集合k中某類的概率，并構成概率矩陣集合P。

步驟4 if σ(z(ci))≥α ，樣本 ci→ POS(α,β)(X)，將 ci加入Set(T)。

步驟 5 else if β ＜σ(z(ci))＜α，樣本ci→BND(α,β)(X)，將ci加入 Set(MID)。

步驟6 else if σ(z(ci))≤β ，樣本 ci→NEG(α,β)(X)，將ci加入 Set(F)。

步驟7 end。

由算法可以看出，首先對n個樣本進行分類，并且要計算n個樣本分別屬于類別集合k中某類的概率，故算法需執行n×k次，由于k為常數，所以時間復雜度與n成線性關系，T(n)=O(n)，算法從時間復雜度的角度分析是有效的。

4.2 SVM三支決策分類器閾值計算

對于閾值α與β，作如下假設：

則由式（6）和（10）可得：

由于α＞γ＞β，所以η＞2，η的最后取值由實驗結果確定[17]。

4.3 基于KNN的三支決策中間域樣本二階段分類

KNN算法是一種簡單易行的無參數分類方法，該算法對非正態分布的數據具有較高的分類準確率，具有魯棒性強、易于實現等優點，在人工智能領域、模式識別等領域已經取得廣泛的應用[18]。但該算法時間及空間復雜度隨著樣本集合增大而增高，由于中間域樣本數較少，故本文選用KNN算法在第二階段對中間域樣本進行二次分類。該算法基本思路是：如果某樣本在特征空間的K個最相似的樣本中的大多數屬于某類別，則該樣本也屬于該類別。本文采用KNN分類器作為二階段分類器，對三支決策中間域樣本集Set(MID)進行二次分類，使用歐式距離計算樣本間距離：

其中X與Y分別表示樣本集中某兩樣本構成的特征向量 X=(x1,x2,…,xn)和 Y=(y1,y2,…,yn)，d(X,Y)表示兩樣本之間距離。

5 實驗設計與結果分析

5.1 實驗數據選取及預處理

本文實驗語料采用ACE2005中文評測語料，數據來源為廣播新聞（Broadcast News），新華社新聞（XinHua News）[19]。并選取前8 000篇作為訓練語料，后1 317篇作為測試語料。ACE的訓練數據，不僅標注實體以及實體的屬性，還詳細標注了實體關系以及關系的屬性，數據以及標注結果以XML格式存儲，句子中任意兩個實體之間即形成一個實例，表5列出了本文所選取語料所有實例的統計情況。

表5 實例統計信息

由表5可知，轉喻關系（METONYMY）類型僅占39個，且轉喻關系類型不包含任何子類型，故本實驗剔除轉喻關系（METONYMY）類型，只考慮除METONYMY（轉喻關系）外的6類關系類型。

語料預處理包括分詞、詞性標注等。分詞采用Python自帶的jieba分詞，抽取樣本集中所有實體詞匯，構成實體詞典，作為jieba分詞的自定義詞典，大大避免了實體詞匯被錯分的情況。詞性標注采用jieba自帶的詞性標注工具[15]。

5.2 評價標準

本文采用信息檢索的通用評價方法，準確率(P)、召回率(R)和F值定義如下：

對兩階段分類結果進行加權處理作為最終分類結果。公式如下：

其中，ALL為所有樣本數，A1為一階段中分到各實體類別的的樣本總數，M1為一階段中間域樣本數。P1、R1、F1分別為一階段準確率、召回率和F值。P2、R2、F2分別為二階段準確率、召回率和F值。

5.3 實驗結果分析

5.3.1 參數η取值實驗

對參數η進行取值實驗，實驗區間為[2.0，4.0]，實驗結果如圖2所示。

從圖2～7可得出如下結論：隨著η值的增大，準確率逐漸上升，F值在[1.7，2.9]之間逐漸增大，而召回率在[1.7，2.9]區間緩慢下降，在2.9以后呈直線下降，η取均值2.85時準確率、召回率、F值達到最高。取η=2.85時，實驗結果如表6所示。

表6 一階段SVM三支決策分類結果（η=2.85）

5.3.2 二階段中間域樣本KNN實驗

由上節可知，η取2.85時效果最好，故下面實驗取η =2.85，將其代入式（11），可得：

圖2 類別I參數η取值實驗

圖3 類別Ⅱ參數η取值實驗

圖4 類別Ⅲ參數η取值實驗

圖5 類別Ⅳ參數η取值實驗

圖6 類別Ⅴ參數η取值實驗

圖7 類別Ⅵ參數η取值實驗

將中間域樣本Set(MID)輸入訓練好的KNN分類器中進行實體關系抽取。實驗結果如表7所示。

表7 二階段KNN實體關系抽取實驗結果

5.3.3 實驗結果對比

選擇效果最好的η=2.85的兩階段分類加權平均實驗結果與一階段SVM三支決策分類結果、文獻[1]中結果進行比較。結果如表8所示。

表8 本文方法與各方法結果比較

由表8可知，一階段SVM三支決策分類結果較傳統SVM分類結果提升效果較為顯著，這表明三支決策方法在實體關系抽取領域的應用是有效的。基于三支決策兩階段分類（本文方法）結果相較于傳統SVM分類結果在準確率、召回率、F值上分別提高了9%、11%、9%，表明本文方法大大提高了實體關系抽取的效果，而三支決策兩階段分類結果相較于一階段SVM三支決策分類結果也有一定的提升，證明了使用KNN分類器對中間域樣本的處理對提高實體關系抽取效果也是有效的。

6 總結與展望

本文以ACE2005中文評測語料進行研究，提出了一種基于三支決策的SVM-KNN兩階段實體關系抽取方法。實驗結果表明，該方法有效提高了實體關系抽取的分類效果。本文研究還存在一些不足之處：（1）三支決策的損失函數、閾值僅根據專家經驗進行了簡單預設；（2）文本特征選擇還偏于簡單，應研究更細粒度的特征如語義特征、句法路徑特征、包含非包含特征等。接下來的工作，將對上述不足之處進行進一步探討，以進一步提高實體關系的抽取效果。

致謝 本文研究內容得益于作者朱艷輝在加拿大Regina大學訪學期間來自于姚一豫教授的悉心指導，在此對姚一豫教授表示深深的感謝。

參考文獻：

[1]車萬翔，劉挺，李生.實體關系自動抽取[J].中文信息學報，2005，19（2）：1-6.

[2]劉紹毓，周杰，李弼程，等.基于多分類SVM-KNN的實體關系抽取方法[J].數據采集與處理，2015，30（1）：202-210.

[3]Pawlak Z.Rough sets[J].International Journal of Computer and Information Sciences，1982，11（5）：341-356.

[4]Pawlak Z.Roughset：Theoretical aspects of reasonsing about data[M].Dordrecht：Kluwer Academic Publishers，1991.

[5]Yao Y Y，Wong S K M，Lingras P.A decision-theoretic rough set model[C]//The 5th International Symposium on Methodologies for Intelligent Systems，1990.

[6]Yao Y Y，Wong S K M.A decision theoretic framework for approximating concepts[J].International Journal of Man-Machine Studies，1992，37：793-809.

[7]Yao Y Y.An outline of a theory of three-way decisions[C]//Proceedings of the 8th International RSCTC Conference，2012.

[8]Yao Y Y.The superiority of three-way decisions in probabilistic rough set models[J].Information Sciences，2011，181：1080-1096.

[9]張燕平，鄒慧錦，邢航，等.CCA三支決策模型的邊界域樣本處理[J]，計算機科學與探索，2014，8（5）：593-600.

[10]李金海，鄧碩.概念格與三支決策及其研究展望[J].西北大學學報：自然科學版，2017，47（3）：321-329.

[11]Li J H，Mei C L，Lv Y J.Incomplete decision contexts：Approximate concept construction，rule acquisition and knowledge reduction[J].International Journal of Approximate Reasoning，2013，54（1）：149-165.

[12]蘇婷，于杰.基于q近鄰的不完備數據三支決策聚類方法[J].計算機科學與探索，2016，10（6）：875-883.

[13]劉盾，梁德翠.廣義三支決策與狹義三支決策[J].計算機科學與探索，2017，11（3）：502-510.

[14]董靜，孫樂，馮元勇，等.中文實體關系抽取中的特征選擇研究[J].中文信息學報，2007，21（4）：80-85.

[15]黃鑫，朱巧明，錢龍華.基于特征組合的中文實體關系抽取[J].微電子學與計算機，2010，27（4）：198-200.

[16]朱艷輝，田海龍，劉璟，等.基于三支決策的新聞情感關鍵句識別方法[J].山西大學學報：自然科學版，2015，38（4）：595-600.

[17]田海龍，朱艷輝，梁韜，等.基于三支決策的中文微博觀點句識別研究[J].山東大學學報，2014，49（8）：58-65.

[18]劉克彬，李芳，劉磊，等.基于核函數中文關系自動抽取系統的實現[J].計算機研究與發展，2007，44（8）：1406-1411.

[19]ACE2005.The Automatic Content Extraction（ACE）projects[EB/OL].（2007）.http：//www.ldc.upenn.edu/Projects/ACE/.