朱艷輝,李 飛,胡駿飛,錢繼勝 ,王天吉
ZHU Yanhui1,2,LI Fei1,2,HU Junfei1,2,QIAN Jisheng3,WANG Tianji1,2
1.湖南工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,湖南 株洲 412008
2.湖南工業(yè)大學(xué) 湖南省智能信息感知及處理技術(shù)重點(diǎn)實(shí)驗(yàn)室,湖南 株洲 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
隨著計(jì)算機(jī)的普及和知識工程的蓬勃發(fā)展,信息量正以指數(shù)級的規(guī)模爆炸式增長。人們迫切地需要一些自動化的工具幫助人們在海量數(shù)據(jù)源中快速檢索到需要的知識。信息抽取(Information Extraction)研究以此為背景應(yīng)運(yùn)而生。其主要目的是將互聯(lián)網(wǎng)中海量的非結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)化為結(jié)構(gòu)化或半結(jié)構(gòu)化信息形成“知識”,供用戶查詢以及進(jìn)一步分析挖掘。信息抽取在信息檢索、知識表示、篇章理解、智能問答等領(lǐng)域具有重要的應(yīng)用價(jià)值。信息抽取從文本中抽取出特定的事實(shí)稱之為“實(shí)體”,然而大多數(shù)應(yīng)用中不僅需要“實(shí)體”,還要確定這些實(shí)體的關(guān)系,稱其為實(shí)體關(guān)系抽取。美國國家標(biāo)準(zhǔn)技術(shù)研究院(NIST)組織了自動內(nèi)容抽?。ˋutomatic Content Extraction,ACE),其評測任務(wù)之一就是實(shí)體關(guān)系識別。實(shí)體關(guān)系抽取通過識別命名實(shí)體,進(jìn)而抽象出實(shí)體間關(guān)系類型,如NIST定義了制造使用關(guān)系(ART)、組織機(jī)構(gòu)從屬關(guān)系(ORG-AFF)、局部整體關(guān)系(PARTWHOLE)等關(guān)系類型。因此可將關(guān)系抽取問題轉(zhuǎn)化為多分類問題。首先識別出句子中所有的實(shí)體對,然后使用分類器決定實(shí)體關(guān)系類型屬于預(yù)定義的哪一類。
許多學(xué)者采用SVM分類器進(jìn)行實(shí)體關(guān)系抽取,車萬翔[1]等人使用SVM構(gòu)造不同窗口大小的特征向量,在ACE2004語料上取得了較好的分類效果。劉紹毓[2]等對SVM模糊邊界樣本進(jìn)行雙投票,對模糊樣本采用KNN分類器進(jìn)行二次分類,大大提高了實(shí)體關(guān)系抽取的準(zhǔn)確率。但是,雖然SVM具有較強(qiáng)的抗噪聲能力和較高的分類準(zhǔn)確率等優(yōu)點(diǎn),但該分類器對于分布在超平面附近區(qū)域的樣本分類效果不理想。當(dāng)處理多分類任務(wù)時,樣本在超平面附近的類交疊區(qū)域的分類效果更差。故隨著分類類別數(shù)的增多,由于各個類別樣本交疊愈加嚴(yán)重,從而影響分類準(zhǔn)確率。
三支決策理論[3-6]是傳統(tǒng)二支決策理論的拓展,二支決策只考慮接受或者拒絕(或者是或否)兩種選擇。但是實(shí)際應(yīng)用中,由于信息的不確定性和不全面性,無法明確對一個事物明確的判斷接受或是拒絕。因此,Yao(姚一豫)[7-8]提出了三支決策理論,當(dāng)判決信息不足以判斷接受或者拒絕時,采用不承諾選擇,然后再加入細(xì)粒度信息進(jìn)行下一步判斷[9]。李金海[10]論述了三支決策與概念格相結(jié)合的研究進(jìn)展,針對兩個結(jié)合點(diǎn):三支概念分析和三支概念學(xué)習(xí)進(jìn)行對比分析,提出了兩種思維的互補(bǔ)性。并且提出一種建立不完整的上下文近似概念格的新方法[11],通過從不完全決策環(huán)境中提取非冗余近似決策規(guī)則,進(jìn)一步提高了三支決策在信息不完備情況下的決策效率。二支決策和三支決策就應(yīng)用場景而言各有優(yōu)劣,在信息充足、消息準(zhǔn)確時,采用二支決策,可使得決策迅速簡潔。在信息不足或者獲取信息代價(jià)過大時,適合使用三支決策,可以權(quán)衡利弊,等待細(xì)粒度的信息,再做出進(jìn)一步判斷。三支決策策略提供了一個很好的權(quán)衡資源和效益的決策框架。
本文將三支決策應(yīng)用到實(shí)體關(guān)系抽取領(lǐng)域,對信息不足以判斷實(shí)體關(guān)系屬于哪一類型的樣本,引入中間類別(中間域)。針對SVM分類器交疊區(qū)域樣本難以界定的問題,提出一種基于三支決策的兩階段實(shí)體關(guān)系抽取方法。首先構(gòu)建SVM三支決策分類器實(shí)現(xiàn)第一階段實(shí)體關(guān)系抽取,采用softmax函數(shù)作為三支決策概率函數(shù),然后采用KNN分類器對三支決策分類后的中間域樣本進(jìn)行二階段分類。并將結(jié)果與SVM分類方法和一階段SVM三支決策分類方法進(jìn)行比較實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,基于三支決策兩階段分類實(shí)體關(guān)系抽取方法取得了很好的抽取效果。
三支決策理論是在粗糙集和決策粗糙集理論之上提出的,Yao通過對粗糙集理論中的正、負(fù)、邊界區(qū)域語義方面研究,提出了從三支決策角度解釋粗糙集中規(guī)則提取問題。其規(guī)則分別對應(yīng)對象所屬的正、負(fù)、邊界三個區(qū)域,根據(jù)對象所屬區(qū)域不同,分別判決該對象屬于目標(biāo)類、不屬于目標(biāo)類、不承諾是否屬于目標(biāo)類的三支決策策略,對于決策粗糙集模型所需的閾值參數(shù)可由決策損失函數(shù)決定。
定義一個四元組W=(U,At=B?C,{Va|a∈At},{Ia|a∈At}),其中U是一個有限且非空的數(shù)據(jù)對象集合[12],At是一個非空且有限屬性集合,B是條件屬性,C是決策屬性,B?C=?,Va為屬性值的集合,Ia是對象U到Va的一個映射,稱為信息函數(shù),即將集合U映射到屬性值域Va上。(U,EA)是屬性集合A上的近似集合,U/EA是基于關(guān)系集合EA對對象集合的劃分,EA定義如下:
則包含對象x的等價(jià)類可表示為:
判斷一個對象是否屬于決策類可用狀態(tài)集合Ω={X,?X}表示,則等價(jià)類[x]屬于決策類X的概率函數(shù)為:
不屬于決策類X的概率函數(shù)為:
Yao等人提出了決策粗糙集模型,并定義了如下三個域(設(shè)閾值0≤ β < α≤1):
其中 POS(α,β)(X)、BND(α,β)(X)、NEG(α,β)(X)分別稱為X的正域、邊界域、負(fù)域。
當(dāng)對象 x屬于決策類 X時,令 λpp、λnp、λbp為分別劃分到 POS(α,β)(X)、BND(α,β)(X)、NEG(α,β)(X)的損失函數(shù)。當(dāng)對象x不屬于決策類時,則令λpn、λbn、λnn為劃分到相同三個域的損失函數(shù)。則損失函數(shù)表如表1所示。
表1 損失函數(shù)表
對于三個域的風(fēng)險(xiǎn)決策,結(jié)合貝葉斯決策理論給出的最小風(fēng)險(xiǎn)決策規(guī)則??芍?/p>
則以上決策規(guī)則簡化如下:
在[x]A的情況下,如果X發(fā)生的概率大于等于α,則將[x]A劃分為X的正域,如果X發(fā)生概率大于β小于α,則將[x]A劃分為X的邊界域,如果X發(fā)生的概率小于等于β,則將[x]A劃分為X的負(fù)域[13]。
本文采用詞匯、實(shí)體類型、位置等作為文本特征。
(1)詞匯
實(shí)體本身所包含的所有詞匯,以及實(shí)體左右的詞匯對確定實(shí)體之間的關(guān)系有很好的作用。例如,“微軟公司創(chuàng)始人比爾蓋茨從哈佛大學(xué)退學(xué)后創(chuàng)辦微軟公司”。實(shí)體“微軟”和實(shí)體“比爾蓋茨”屬于雇傭關(guān)系,其中在實(shí)體“微軟”附近的詞(公司、創(chuàng)辦)對實(shí)體“比爾蓋茨”很有指示作用。所以實(shí)體窗口詞對于分類也十分關(guān)鍵,但是窗口太大,會引入太多無關(guān)信息。窗口太小,又會導(dǎo)致重要信息的遺漏。車萬翔等人經(jīng)過重復(fù)實(shí)驗(yàn)驗(yàn)證了在窗口取2時,分類能取得最好的效果,故本文取實(shí)體上下文窗口為2的詞,如表2所示。E1、E1pos表示實(shí)體1詞匯及詞性,E2、E2pos表示實(shí)體2詞匯及詞性。E1L1、E1L1pos表示實(shí)體左側(cè)第一個詞及其詞性,E1L2、E1L2pos表示實(shí)體左側(cè)第二個詞及其詞性,E1R1、E1R1pos、E1R2、E1R2pos表示實(shí)體右側(cè)第一、二個詞及其詞性。E2同理。
(2)位置特征
實(shí)體的位置特征以及實(shí)體的先后順序?qū)τ陉P(guān)系類型有很大影響。董靜[14]等人對ACE語料樣本特征進(jìn)行分析,提取實(shí)體包含和非包含關(guān)系特征對實(shí)體關(guān)系抽取,證明了實(shí)體包含和非包含特征對實(shí)體關(guān)系抽取有一定影響。本文采取的實(shí)體位置特征如表3所示。
表2 實(shí)體詞和上下文特征
表3 實(shí)體位置特征
(3)實(shí)體類型
實(shí)體關(guān)系分類中實(shí)體類型及其組合特征[15]是一個非常重要的特征,對分類準(zhǔn)確與否至關(guān)重要,實(shí)體類型特征標(biāo)記如表4所示。
表4 實(shí)體類型特征
本文通過構(gòu)造SVM三支決策分類器,進(jìn)行一階段實(shí)體關(guān)系抽取,然后采用KNN分類器對三支決策中間域樣本進(jìn)行二階段實(shí)體關(guān)系抽取,從而實(shí)現(xiàn)基于三支決策的兩階段實(shí)體關(guān)系抽取。實(shí)體關(guān)系抽取流程圖如圖1所示。
鑒于實(shí)體關(guān)系抽取是一個多分類問題,SVM提供了多分類方法:一種是one-against-rest方法,基本思想是對于M(M≥3)類樣本,將其中一類和其余類分別作為正、負(fù)例來訓(xùn)練分類器,M個類別需構(gòu)建M個分類器。另一種是one-against-one方法,基本思想是對于M(M≥3)類樣本,每兩類訓(xùn)練一個分類器,M個類別需構(gòu)建M(M-1)/2個分類器。鑒于one-against-rest方法分類速度較快,訓(xùn)練分類器數(shù)目較少,本文采用oneagainst-rest方法。在三支決策分類器的構(gòu)建中,針對多分類問題,采用softmax函數(shù)作為概率函數(shù),計(jì)算每個樣本屬于某類的概率值,計(jì)算公式如式(8)所示:
圖1 實(shí)體關(guān)系抽取流程圖
SVM三支決策分類器構(gòu)造算法如下:
輸入:訓(xùn)練集U,測試集C,類別集合k。
輸出:實(shí)體類別集Set(T),邊界域(中間域)樣本集Set(MID),No-Relation樣本集 Set(F)。
訓(xùn)練階段:
步驟1輸入訓(xùn)練集樣本集合U。
步驟2使用SVM分類器對訓(xùn)練集U進(jìn)行訓(xùn)練,得到SVM分類模型。
測試階段:
步驟1輸入測試集樣本集合C。
步驟2 forci∈C,使用訓(xùn)練好的SVM分類器進(jìn)行分類。
步驟3由式(8)計(jì)算C中所有樣本對象分別屬于類別集合k中某類的概率,并構(gòu)成概率矩陣集合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個樣本進(jìn)行分類,并且要計(jì)算n個樣本分別屬于類別集合k中某類的概率,故算法需執(zhí)行n×k次,由于k為常數(shù),所以時間復(fù)雜度與n成線性關(guān)系,T(n)=O(n),算法從時間復(fù)雜度的角度分析是有效的。
對于閾值α與β,作如下假設(shè):
則由式(6)和(10)可得:
由于α>γ>β,所以η>2,η的最后取值由實(shí)驗(yàn)結(jié)果確定[17]。
KNN算法是一種簡單易行的無參數(shù)分類方法,該算法對非正態(tài)分布的數(shù)據(jù)具有較高的分類準(zhǔn)確率,具有魯棒性強(qiáng)、易于實(shí)現(xiàn)等優(yōu)點(diǎn),在人工智能領(lǐng)域、模式識別等領(lǐng)域已經(jīng)取得廣泛的應(yīng)用[18]。但該算法時間及空間復(fù)雜度隨著樣本集合增大而增高,由于中間域樣本數(shù)較少,故本文選用KNN算法在第二階段對中間域樣本進(jìn)行二次分類。該算法基本思路是:如果某樣本在特征空間的K個最相似的樣本中的大多數(shù)屬于某類別,則該樣本也屬于該類別。本文采用KNN分類器作為二階段分類器,對三支決策中間域樣本集Set(MID)進(jìn)行二次分類,使用歐式距離計(jì)算樣本間距離:
其中X與Y分別表示樣本集中某兩樣本構(gòu)成的特征向量 X=(x1,x2,…,xn)和 Y=(y1,y2,…,yn),d(X,Y)表示兩樣本之間距離。
本文實(shí)驗(yàn)語料采用ACE2005中文評測語料,數(shù)據(jù)來源為廣播新聞(Broadcast News),新華社新聞(XinHua News)[19]。并選取前8 000篇作為訓(xùn)練語料,后1 317篇作為測試語料。ACE的訓(xùn)練數(shù)據(jù),不僅標(biāo)注實(shí)體以及實(shí)體的屬性,還詳細(xì)標(biāo)注了實(shí)體關(guān)系以及關(guān)系的屬性,數(shù)據(jù)以及標(biāo)注結(jié)果以XML格式存儲,句子中任意兩個實(shí)體之間即形成一個實(shí)例,表5列出了本文所選取語料所有實(shí)例的統(tǒng)計(jì)情況。
表5 實(shí)例統(tǒng)計(jì)信息
由表5可知,轉(zhuǎn)喻關(guān)系(METONYMY)類型僅占39個,且轉(zhuǎn)喻關(guān)系類型不包含任何子類型,故本實(shí)驗(yàn)剔除轉(zhuǎn)喻關(guān)系(METONYMY)類型,只考慮除METONYMY(轉(zhuǎn)喻關(guān)系)外的6類關(guān)系類型。
語料預(yù)處理包括分詞、詞性標(biāo)注等。分詞采用Python自帶的jieba分詞,抽取樣本集中所有實(shí)體詞匯,構(gòu)成實(shí)體詞典,作為jieba分詞的自定義詞典,大大避免了實(shí)體詞匯被錯分的情況。詞性標(biāo)注采用jieba自帶的詞性標(biāo)注工具[15]。
本文采用信息檢索的通用評價(jià)方法,準(zhǔn)確率(P)、召回率(R)和F值定義如下:
對兩階段分類結(jié)果進(jìn)行加權(quán)處理作為最終分類結(jié)果。公式如下:
其中,ALL為所有樣本數(shù),A1為一階段中分到各實(shí)體類別的的樣本總數(shù),M1為一階段中間域樣本數(shù)。P1、R1、F1分別為一階段準(zhǔn)確率、召回率和F值。P2、R2、F2分別為二階段準(zhǔn)確率、召回率和F值。
5.3.1 參數(shù)η取值實(shí)驗(yàn)
對參數(shù)η進(jìn)行取值實(shí)驗(yàn),實(shí)驗(yàn)區(qū)間為[2.0,4.0],實(shí)驗(yàn)結(jié)果如圖2所示。
從圖2~7可得出如下結(jié)論:隨著η值的增大,準(zhǔn)確率逐漸上升,F(xiàn)值在[1.7,2.9]之間逐漸增大,而召回率在[1.7,2.9]區(qū)間緩慢下降,在2.9以后呈直線下降,η取均值2.85時準(zhǔn)確率、召回率、F值達(dá)到最高。取η=2.85時,實(shí)驗(yàn)結(jié)果如表6所示。
表6 一階段SVM三支決策分類結(jié)果(η=2.85)
5.3.2 二階段中間域樣本KNN實(shí)驗(yàn)
由上節(jié)可知,η取2.85時效果最好,故下面實(shí)驗(yàn)取η =2.85,將其代入式(11),可得:
圖2 類別I參數(shù)η取值實(shí)驗(yàn)
圖3 類別Ⅱ參數(shù)η取值實(shí)驗(yàn)
圖4 類別Ⅲ參數(shù)η取值實(shí)驗(yàn)
圖5 類別Ⅳ參數(shù)η取值實(shí)驗(yàn)
圖6 類別Ⅴ參數(shù)η取值實(shí)驗(yàn)
圖7 類別Ⅵ參數(shù)η取值實(shí)驗(yàn)
將中間域樣本Set(MID)輸入訓(xùn)練好的KNN分類器中進(jìn)行實(shí)體關(guān)系抽取。實(shí)驗(yàn)結(jié)果如表7所示。
表7 二階段KNN實(shí)體關(guān)系抽取實(shí)驗(yàn)結(jié)果
5.3.3 實(shí)驗(yàn)結(jié)果對比
選擇效果最好的η=2.85的兩階段分類加權(quán)平均實(shí)驗(yàn)結(jié)果與一階段SVM三支決策分類結(jié)果、文獻(xiàn)[1]中結(jié)果進(jìn)行比較。結(jié)果如表8所示。
表8 本文方法與各方法結(jié)果比較
由表8可知,一階段SVM三支決策分類結(jié)果較傳統(tǒng)SVM分類結(jié)果提升效果較為顯著,這表明三支決策方法在實(shí)體關(guān)系抽取領(lǐng)域的應(yīng)用是有效的?;谌Q策兩階段分類(本文方法)結(jié)果相較于傳統(tǒng)SVM分類結(jié)果在準(zhǔn)確率、召回率、F值上分別提高了9%、11%、9%,表明本文方法大大提高了實(shí)體關(guān)系抽取的效果,而三支決策兩階段分類結(jié)果相較于一階段SVM三支決策分類結(jié)果也有一定的提升,證明了使用KNN分類器對中間域樣本的處理對提高實(shí)體關(guān)系抽取效果也是有效的。
本文以ACE2005中文評測語料進(jìn)行研究,提出了一種基于三支決策的SVM-KNN兩階段實(shí)體關(guān)系抽取方法。實(shí)驗(yàn)結(jié)果表明,該方法有效提高了實(shí)體關(guān)系抽取的分類效果。本文研究還存在一些不足之處:(1)三支決策的損失函數(shù)、閾值僅根據(jù)專家經(jīng)驗(yàn)進(jìn)行了簡單預(yù)設(shè);(2)文本特征選擇還偏于簡單,應(yīng)研究更細(xì)粒度的特征如語義特征、句法路徑特征、包含非包含特征等。接下來的工作,將對上述不足之處進(jìn)行進(jìn)一步探討,以進(jìn)一步提高實(shí)體關(guān)系的抽取效果。
致謝 本文研究內(nèi)容得益于作者朱艷輝在加拿大Regina大學(xué)訪學(xué)期間來自于姚一豫教授的悉心指導(dǎo),在此對姚一豫教授表示深深的感謝。
參考文獻(xiàn):
[1]車萬翔,劉挺,李生.實(shí)體關(guān)系自動抽取[J].中文信息學(xué)報(bào),2005,19(2):1-6.
[2]劉紹毓,周杰,李弼程,等.基于多分類SVM-KNN的實(shí)體關(guān)系抽取方法[J].數(shù)據(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],計(jì)算機(jī)科學(xué)與探索,2014,8(5):593-600.
[10]李金海,鄧碩.概念格與三支決策及其研究展望[J].西北大學(xué)學(xué)報(bào):自然科學(xué)版,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近鄰的不完備數(shù)據(jù)三支決策聚類方法[J].計(jì)算機(jī)科學(xué)與探索,2016,10(6):875-883.
[13]劉盾,梁德翠.廣義三支決策與狹義三支決策[J].計(jì)算機(jī)科學(xué)與探索,2017,11(3):502-510.
[14]董靜,孫樂,馮元勇,等.中文實(shí)體關(guān)系抽取中的特征選擇研究[J].中文信息學(xué)報(bào),2007,21(4):80-85.
[15]黃鑫,朱巧明,錢龍華.基于特征組合的中文實(shí)體關(guān)系抽取[J].微電子學(xué)與計(jì)算機(jī),2010,27(4):198-200.
[16]朱艷輝,田海龍,劉璟,等.基于三支決策的新聞情感關(guān)鍵句識別方法[J].山西大學(xué)學(xué)報(bào):自然科學(xué)版,2015,38(4):595-600.
[17]田海龍,朱艷輝,梁韜,等.基于三支決策的中文微博觀點(diǎn)句識別研究[J].山東大學(xué)學(xué)報(bào),2014,49(8):58-65.
[18]劉克彬,李芳,劉磊,等.基于核函數(shù)中文關(guān)系自動抽取系統(tǒng)的實(shí)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展,2007,44(8):1406-1411.
[19]ACE2005.The Automatic Content Extraction(ACE)projects[EB/OL].(2007).http://www.ldc.upenn.edu/Projects/ACE/.