面向知識(shí)擴(kuò)充的實(shí)體關(guān)系挖掘

楊帥++宋汝良

摘要：為了從自由文本中挖掘大量高質(zhì)量的事實(shí)抽象出三元組，并將其與現(xiàn)有的知識(shí)庫(kù)進(jìn)行知識(shí)融合，提出了知識(shí)圖譜構(gòu)建中的知識(shí)擴(kuò)充框架。首先對(duì)知識(shí)圖譜的構(gòu)建過(guò)程進(jìn)行了認(rèn)知，指出傳統(tǒng)的關(guān)系挖掘僅僅是利用句法依存樹(shù)抽取路徑上的節(jié)點(diǎn)作為關(guān)系， 對(duì)于復(fù)雜句子表現(xiàn)較差。在此基礎(chǔ)上建立了一種基于關(guān)系類型的結(jié)合多種特征的知識(shí)擴(kuò)充框架，該方法自動(dòng)獲取高質(zhì)量知識(shí)。效果在開(kāi)放網(wǎng)頁(yè)句子中達(dá)到F1值88%。

關(guān)鍵詞：知識(shí)圖譜；關(guān)系挖掘；知識(shí)擴(kuò)充；句法依存；特征抽取

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）01-0028-03

Entity Relationship Discovery for Knowledge Growth

YANG Shuai1 ， SONG Ru-liang2

（1.School of Electronic and Information Engineering of Tongji University， Shanghai 201804， China；2. Shanghai dream Creation Software Technology Co.， Ltd.， Shanghai 200092， China）

Abstract：To extract the high quality facts as triplets and merge them into existing knowledge base， an extended frame of knowledge growth in the construction of knowledge base is presented. Firstly， the process of knowledge base constructing is recognized. It is pointed out that the limitation in recognizing relationship between entities is to only rely on parsing dependency tree， and perform worse on complex sentences which contain large amount of entities. Then， the knowledge growth framework fusing different types of features is proposed for extracting high quality knowledge automatically. Finally， in web data sentences， the F1 measure of 88% of the presented method is demonstrated.

Key words：knowledge graph； relationship discovery； knowledge growth； dependency tree； feature extraction

隨著互聯(lián)網(wǎng)的普及以及中文搜索引擎的發(fā)展，存在于Web的數(shù)據(jù)越來(lái)越多，用戶對(duì)互聯(lián)網(wǎng)數(shù)據(jù)快速、準(zhǔn)確、實(shí)時(shí)獲取的需求越來(lái)越高。借助搜索引擎，用戶可以迅速，快捷地找到相關(guān)的信息、知識(shí)。搜索引擎[1]通過(guò)進(jìn)行網(wǎng)絡(luò)爬蟲(chóng)、HTML的清洗（清除標(biāo)簽）、分詞、建立倒排索引建立網(wǎng)頁(yè)庫(kù)，當(dāng)用戶通過(guò)搜索框鍵入關(guān)鍵詞時(shí)，搜索引擎首先解析用戶的查詢意圖（Query）并通過(guò)已建立的倒排索引，將匹配用戶Query的結(jié)果展示。2012年，Google首次提出知識(shí)圖譜（Google Knowledge Graph），旨在利用搜索系統(tǒng)建立的豐富的數(shù)據(jù)內(nèi)容，將搜索結(jié)果進(jìn)行整合、對(duì)齊、結(jié)構(gòu)化，使得用戶可以便捷迅速的獲取知識(shí)，找到所求。因此構(gòu)建知識(shí)圖譜具有很高的研究?jī)r(jià)值以及應(yīng)用價(jià)值。

1 相關(guān)工作

近年來(lái)國(guó)內(nèi)外總結(jié)了構(gòu)建知識(shí)圖譜的方法，根據(jù)構(gòu)建數(shù)據(jù)進(jìn)行區(qū)分，包括基于百科類的構(gòu)建[2]、基于互聯(lián)網(wǎng)數(shù)據(jù)的構(gòu)建、基于自由文本的構(gòu)建方法與基于垂直網(wǎng)站的構(gòu)建方法等。知識(shí)圖譜構(gòu)建中的技術(shù)包括：命名實(shí)體的挖掘、實(shí)體間關(guān)系的挖掘、知識(shí)的更新、知識(shí)的推理等，其中命名實(shí)體的挖掘和實(shí)體關(guān)系的挖掘?yàn)闃?gòu)建知識(shí)圖譜的核心技術(shù)。命名實(shí)體的挖掘旨在在從文本信息（微博[3]、新聞、搜索內(nèi)容[4]、評(píng)論文本等）中挖掘出存在的命名實(shí)體作為知識(shí)圖譜中的頂點(diǎn)，包括人名、地名、機(jī)構(gòu)名、時(shí)間、度量衡等[5]。實(shí)體關(guān)系挖掘的目的在于挖掘出實(shí)體之間的確定性關(guān)系作為知識(shí)圖譜中的頂點(diǎn)（實(shí)體）之間的邊[6]。實(shí)體關(guān)系的挖掘方法包含：基于現(xiàn)有邊關(guān)系的挖掘（如社交媒體用戶的挖掘[7]，HTML中的鏈接分析等）、基于結(jié)構(gòu)化的數(shù)據(jù)挖掘（如web頁(yè)面的DOM挖掘、頁(yè)面下表格的解析、百科中的INFOBOX的抽取[8]等）、基于自由文本的關(guān)系挖掘（如基于Query的挖掘，基于新聞?lì)惖氖聦?shí)挖掘）。

對(duì)于自由文本的關(guān)系挖掘，文獻(xiàn)[9]介紹了一種根據(jù)模板進(jìn)行關(guān)系挖掘的方法，通過(guò)預(yù)定義模板的方法有較高的準(zhǔn)確率，但是存在的不足在于：創(chuàng)建模板（規(guī)則）所需要較大的人力投入、模板的局限性使得關(guān)系可擴(kuò)展性較差以及模板本身的召回覆蓋率較低。文獻(xiàn)[10]介紹了根據(jù)句法依存關(guān)系進(jìn)行挖掘?qū)嶓w間的關(guān)系的方法，通過(guò)句法分析工具將切句后的句子進(jìn)行依存解析得到依存樹(shù)，根據(jù)最小構(gòu)建子樹(shù)所形成的鏈路提取實(shí)體間的關(guān)系。這種方法減少了模板方法所需要的人力成本，同時(shí)準(zhǔn)確度較高，但是依舊存在以下問(wèn)題：對(duì)于較復(fù)雜的句子句法依存結(jié)構(gòu)效果不明顯、鏈路進(jìn)行提取關(guān)系無(wú)法利用到句子的語(yǔ)義信息。本文提出一種集成方法，利用句法依存、模板、詞法統(tǒng)計(jì)、相對(duì)位置等構(gòu)建基本特征，并進(jìn)行特征組合，利用隨機(jī)森林（Random Forests）[11]作為分類器建立關(guān)系挖掘模型，在Web文本數(shù)據(jù)上效果達(dá)到了準(zhǔn)確率85%召回率90%的效果。

2 面向知識(shí)擴(kuò)充的關(guān)系挖掘計(jì)算框架

面向知識(shí)擴(kuò)充的關(guān)系挖掘是對(duì)現(xiàn)有知識(shí)庫(kù)的補(bǔ)充和完善。因而對(duì)于挖掘到的知識(shí)的質(zhì)量、時(shí)效性、置信度等有更高的要求。同時(shí)，通過(guò)限定關(guān)系類型可以使得在保證高質(zhì)量的情況下提高流程的復(fù)用性，減少模型遷移的成本。

2.1 總體流程

本文采取的是線下模型訓(xùn)練線上流式預(yù)測(cè)的手段，由數(shù)據(jù)獲取、數(shù)據(jù)清洗、特征構(gòu)建、訓(xùn)練模型組成，如圖1所示：

圖1 架構(gòu)圖

2.2 數(shù)據(jù)獲取

為了達(dá)到實(shí)時(shí)性關(guān)系挖掘要求，實(shí)時(shí)性的數(shù)據(jù)抓取是該挖掘框架的重要組成部分。為了保證數(shù)據(jù)的真實(shí)性以及消息的準(zhǔn)確性，本文所采用的數(shù)據(jù)源涵蓋大型新聞門戶站點(diǎn)，如新浪網(wǎng)、騰訊新聞網(wǎng)、搜狐新聞、百度新聞以及重要的官方新聞?wù)军c(diǎn)，如新華網(wǎng)、人民網(wǎng)等作為新聞?wù)军c(diǎn)源。通過(guò)爬蟲(chóng)爬取各個(gè)站點(diǎn)的首頁(yè)并遞歸的抓取內(nèi)容以及子頁(yè)面的內(nèi)容，并根據(jù)站點(diǎn)模板進(jìn)行過(guò)濾，將符合要求的url以及數(shù)據(jù)保留，同時(shí)不再對(duì)不符合要求的url進(jìn)行解析和抓取。

2.3 數(shù)據(jù)清洗

數(shù)據(jù)清洗的流程分為HTML解析、文本斷句清洗以及候選關(guān)系 對(duì)（即<主語(yǔ)（Subject） ，關(guān)系（Predicate 或 Relation），賓語(yǔ)（Object）>）三個(gè)步驟。

1）由于所抓到的數(shù)據(jù)均為HTML源碼，因此首先需要通過(guò)正則進(jìn)行清洗標(biāo)簽，獲取文中的文本信息，包含正文的標(biāo)題部分、正文的段落、頁(yè)面內(nèi)其他的新聞標(biāo)題等。

2）根據(jù)規(guī)則進(jìn)行斷句并清洗。本文選取單句作為最小關(guān)系挖掘單元，因此在清洗完HTML標(biāo)簽后，通過(guò)標(biāo)點(diǎn)符號(hào)如“？”，“！”，“。”進(jìn)行斷句，并建立過(guò)濾規(guī)則如下：

①根據(jù)句子長(zhǎng)短進(jìn)行過(guò)濾。由于解析HTML正文的時(shí)候可能存有準(zhǔn)確性問(wèn)題，所以會(huì)產(chǎn)生一些長(zhǎng)度異常的句子，在此處進(jìn)行過(guò)濾；

②根據(jù)關(guān)系的關(guān)鍵詞是否出現(xiàn)進(jìn)行過(guò)濾。例如進(jìn)行“兒子”關(guān)系挖掘時(shí)，句中必須出現(xiàn)“兒子”，“長(zhǎng)子”等關(guān)鍵詞。

3）根據(jù)關(guān)系的類型選出所有的關(guān)系候選集，即 對(duì)。對(duì)不同的關(guān)系類型，產(chǎn)生候選集的方法也不同。例如，對(duì)于人物關(guān)系挖掘，主語(yǔ)和賓語(yǔ)都為人名，并且主語(yǔ)和賓語(yǔ)不相同；對(duì)于職位關(guān)系挖掘，主語(yǔ)為人名，賓語(yǔ)為職位名全稱；對(duì)于文學(xué)作品之間的關(guān)系，主語(yǔ)賓語(yǔ)都為作品名稱，但是存在主語(yǔ)名稱與賓語(yǔ)名稱相同的情況。而后續(xù)的訓(xùn)練模型的目標(biāo)則是通過(guò)選出這些候選集中正確的關(guān)系對(duì)，排除錯(cuò)誤的關(guān)系對(duì)。

2.4 模型構(gòu)建

模型構(gòu)建分為特征構(gòu)建（特征工程）以及分類器訓(xùn)練兩個(gè)步驟。

2.4.1 特征工程

在數(shù)據(jù)挖掘的整個(gè)過(guò)程中，特征構(gòu)建是關(guān)鍵環(huán)節(jié)，將直接影響最終的效果。常用的做法為首先構(gòu)建部分特征集合，作為基礎(chǔ)特征集合（Base Feature Set）。本文采取的基礎(chǔ)特征有實(shí)體上下文特征（Entity Context）、實(shí)體相對(duì)位置特征、詞法統(tǒng)計(jì)特征、句法依存特征[12]等。

然而增加新特征往往需要很大的人力成本，因此需要進(jìn)行特征工程以提升模型的分類效果。特征工程主要分為三個(gè)部分：特征生成、特征評(píng)價(jià)、特征約減。特征生產(chǎn)通過(guò)一定的規(guī)則或窮舉的方式盡可能全面地生成特征作為候選集合。特征評(píng)價(jià)是指通過(guò)一定的度量方式（如基尼系數(shù)、熵、統(tǒng)計(jì)[13]等）對(duì)候選特征在分類效果中進(jìn)行評(píng)估。特征約減（有時(shí)也稱為降維）通過(guò)選擇、變換使得得到的新的特征集合數(shù)量遠(yuǎn)少于原有的特征，從而加快模型的訓(xùn)練速度以及預(yù)測(cè)速度（尤其對(duì)于非線性分類器），同時(shí)分類效果基本保持不變。特征生產(chǎn)通過(guò)特征組合，形成新的特征集合并加入原有特征集合中形成。對(duì)于n個(gè)特征，兩兩組合形成的特征有個(gè)，因而存在大量的無(wú)效特征，因此需要進(jìn)行特征選擇。本文采取統(tǒng)計(jì)每個(gè)特征的值，通過(guò)排序選取較大的特征作為新特征的方法進(jìn)行特征選擇。對(duì)于每一個(gè)特征計(jì)算值公式如式（1）所示：

（1）

其中n為樣本總數(shù)，即 ，a、b、c、d含義如表1所示，

表1 特征-標(biāo)簽矩陣圖

[ 樣本數(shù)量 正樣本 負(fù)樣本＼& 特征為1 a b＼& 特征為0 c d＼&]

2.4.2 分類器訓(xùn)練

一般的線性分類器往往對(duì)距離敏感，所以需要首先進(jìn)行特征歸一。而對(duì)于非線性分類（或回歸）器（如決策樹(shù)、GBDT、隨機(jī)森林等），是通過(guò)度量方式（如根據(jù)Gini系數(shù)、熵等）進(jìn)行分支，因此特征值的放縮不會(huì)影響分裂指標(biāo)進(jìn)而對(duì)輸出結(jié)果產(chǎn)生影響。對(duì)于非線性分類器，隨機(jī)森林和GBDT往往有較好的分類效果以及抗過(guò)擬合性，但是由于本次訓(xùn)練樣本較少，因此采用隨機(jī)森林作為分類器。

3 實(shí)驗(yàn)和結(jié)果分析

通過(guò)互聯(lián)網(wǎng)中文文本進(jìn)行實(shí)驗(yàn)并展示實(shí)驗(yàn)結(jié)果以驗(yàn)證基于關(guān)系類型的結(jié)合多種特征的知識(shí)擴(kuò)充框架的有效性。

3.1 數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)是通過(guò)對(duì)于新聞門戶網(wǎng)站（如新浪新聞、騰訊新聞、百度新聞、搜狐新聞）等頁(yè)面的抓取、解析、分句以及候選關(guān)系抽取產(chǎn)生，利用人工標(biāo)注的手段，對(duì)于“弟弟”、“兒子”、“父親”、“哥哥”、“姐姐”和“妹妹”共6種人物關(guān)系的2400個(gè) <句子-關(guān)系> 進(jìn)行標(biāo)注得到的。數(shù)據(jù)格式包含三列：標(biāo)簽，關(guān)系和句子。并隨機(jī)抽取（不放回的）70% 的樣本為訓(xùn)練集，剩余的30%的樣本為測(cè)試集。

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

評(píng)價(jià)標(biāo)準(zhǔn)為常用的準(zhǔn)確率、召回率以及F1值，其中準(zhǔn)確率計(jì)算方法，如式（2）所示，

（2）

召回率計(jì)算公式如式（3）所示，

（3）

由于僅僅使用準(zhǔn)確率或者召回率無(wú)法全面的衡量模型的效果，因此采取F1 值進(jìn)行度量可以更好地權(quán)衡準(zhǔn)確以及召回率。F1值計(jì)算公式如式（4）所示，

（4）

其中 ，即模型判為關(guān)系正確并且標(biāo)簽為正確的樣本數(shù)，，即模型判為關(guān)系正確但標(biāo)簽為錯(cuò)誤的樣本數(shù)，，即模型判為關(guān)系錯(cuò)誤但標(biāo)簽為正確的樣本數(shù)。

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

根據(jù)人工標(biāo)注的6種關(guān)系的訓(xùn)練數(shù)據(jù)集分別建立六個(gè)關(guān)系模型，并分別驗(yàn)證模型在測(cè)試集的效果。結(jié)果如下圖所示：

通過(guò)對(duì)于6種關(guān)系的2400 個(gè)樣本進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2所示，

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

分別對(duì)于“弟弟”、“兒子”、“父親”、“哥哥”、“姐姐”和“妹妹”6種人物關(guān)系進(jìn)行模型訓(xùn)練并在測(cè)試集上進(jìn)行驗(yàn)證，準(zhǔn)確率均在85%左右，召回率均在90%左右，F(xiàn)1值均在88%左右，降低了知識(shí)圖譜的擴(kuò)充所帶來(lái)的錯(cuò)誤知識(shí)增加的風(fēng)險(xiǎn)。

4 結(jié)語(yǔ)

本文提出的基于關(guān)系類型的結(jié)合多種特征的知識(shí)擴(kuò)充框架在真實(shí)的互聯(lián)網(wǎng)數(shù)據(jù)上能夠抽取高質(zhì)量的事實(shí)信息，以快速低成本地豐富完善現(xiàn)有的知識(shí)庫(kù)，然而在知識(shí)的更新過(guò)程中對(duì)關(guān)系挖掘的模型要求更高（95%的F1值），因此后續(xù)還需要借助其他類型的數(shù)據(jù)（如垂直站點(diǎn)下的挖掘、百科的挖掘）進(jìn)行數(shù)據(jù)融合，從而確保自動(dòng)獲取的知識(shí)有更高的純度。

參考文獻(xiàn)：

[1] 徐寶文， 張衛(wèi)豐. 搜索引擎與信息獲取技術(shù)[M]. 淸華大學(xué)出版社， 2003.

[2] Deshpande O， Lamba D S， Tourn M， et al. Building， maintaining， and using knowledge bases： A report from the trenches[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM， 2013： 1209-1220.

[3] Ritter A， Clark S， Etzioni O. Named entity recognition in tweets： an experimental study[C]//Proceedings of the Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics， 2011： 1524-1534.

[4] Guo J， Xu G， Cheng X， et al. Named entity recognition in query[C]//Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval. ACM， 2009： 267-274.

[5] 張曉艷， 王挺， 陳火旺. 命名實(shí)體識(shí)別研究[J]. 計(jì)算機(jī)科學(xué)， 2005， 32（4）： 44-48.

[6] Zhang C. DeepDive： A Data Management System for Automatic Knowledge Base Construction[D]. UW-Madison， 2015.

[7] Diehl C P， Namata G， Getoor L. Relationship identification for social network discovery[C]//AAAI. 2007， 22（1）： 546-552.

[8] Bu F， Hao Y， Zhu X. Semantic relationship discovery with wikipedia structure[C]//IJCAI Proceedings-International Joint Conference on Artificial Intelligence. 2011， 22（3）： 1770.

[9] 李娟， 張全， 賈寧， 等. 基于模板的中文人物評(píng)論意見(jiàn)挖掘[J]. 計(jì)算機(jī)應(yīng)用研究， 2010， 27（3）.

[10] 李付民， 楊靜， 賀樑. 基于中文句法結(jié)構(gòu)的關(guān)系挖掘[J]. 計(jì)算機(jī)工程， 2014， 40（7）： 143-147.

[11] Liaw A， Wiener M. Classification and regression by randomForest[J]. R news， 2002， 2（3）： 18-22.

[12] Culotta A， Sorensen J. Dependency tree kernels for relation extraction[C]//Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics. Association for Computational Linguistics， 2004： 423.

[13] 王娟， 慈林林， 姚康澤. 特征選擇方法綜述[J]. 計(jì)算機(jī)工程與科學(xué)， 2005（ 12）.