楊帥++宋汝良

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

關鍵詞：知識圖譜；關系挖掘；知識擴充；句法依存；特征抽取

中圖分類號：TP393 文獻標識碼：A 文章編號：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)網的普及以及中文搜索引擎的發(fā)展，存在于Web的數(shù)據(jù)越來越多，用戶對互聯(lián)網數(shù)據(jù)快速、準確、實時獲取的需求越來越高。借助搜索引擎，用戶可以迅速，快捷地找到相關的信息、知識。搜索引擎[1]通過進行網絡爬蟲、HTML的清洗（清除標簽）、分詞、建立倒排索引建立網頁庫，當用戶通過搜索框鍵入關鍵詞時，搜索引擎首先解析用戶的查詢意圖（Query）并通過已建立的倒排索引，將匹配用戶Query的結果展示。2012年，Google首次提出知識圖譜（Google Knowledge Graph），旨在利用搜索系統(tǒng)建立的豐富的數(shù)據(jù)內容，將搜索結果進行整合、對齊、結構化，使得用戶可以便捷迅速的獲取知識，找到所求。因此構建知識圖譜具有很高的研究價值以及應用價值。

1 相關工作

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

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

2 面向知識擴充的關系挖掘計算框架

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

2.1 總體流程

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

圖1 架構圖

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

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

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

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

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

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

①根據(jù)句子長短進行過濾。由于解析HTML正文的時候可能存有準確性問題，所以會產生一些長度異常的句子，在此處進行過濾；

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

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

2.4 模型構建

模型構建分為特征構建（特征工程）以及分類器訓練兩個步驟。

2.4.1 特征工程

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

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

（1）

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

表1 特征-標簽矩陣圖

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

2.4.2 分類器訓練

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

3 實驗和結果分析

通過互聯(lián)網中文文本進行實驗并展示實驗結果以驗證基于關系類型的結合多種特征的知識擴充框架的有效性。

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

實驗數(shù)據(jù)是通過對于新聞門戶網站（如新浪新聞、騰訊新聞、百度新聞、搜狐新聞）等頁面的抓取、解析、分句以及候選關系抽取產生，利用人工標注的手段，對于“弟弟”、“兒子”、“父親”、“哥哥”、“姐姐”和“妹妹”共6種人物關系的2400個 <句子-關系> 進行標注得到的。數(shù)據(jù)格式包含三列：標簽，關系和句子。并隨機抽?。ú环呕氐模?0% 的樣本為訓練集，剩余的30%的樣本為測試集。

3.2 評價標準

評價標準為常用的準確率、召回率以及F1值，其中準確率計算方法，如式（2）所示，

（2）

召回率計算公式如式（3）所示，

（3）

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

（4）

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

3.3 實驗結果

根據(jù)人工標注的6種關系的訓練數(shù)據(jù)集分別建立六個關系模型，并分別驗證模型在測試集的效果。結果如下圖所示：

通過對于6種關系的2400 個樣本進行實驗，實驗結果如圖2所示，

圖2 實驗結果

分別對于“弟弟”、“兒子”、“父親”、“哥哥”、“姐姐”和“妹妹”6種人物關系進行模型訓練并在測試集上進行驗證，準確率均在85%左右，召回率均在90%左右，F(xiàn)1值均在88%左右，降低了知識圖譜的擴充所帶來的錯誤知識增加的風險。

4 結語

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

參考文獻：

[1] 徐寶文， 張衛(wèi)豐. 搜索引擎與信息獲取技術[M]. 淸華大學出版社， 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] 張曉艷， 王挺， 陳火旺. 命名實體識別研究[J]. 計算機科學， 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] 李娟， 張全， 賈寧， 等. 基于模板的中文人物評論意見挖掘[J]. 計算機應用研究， 2010， 27（3）.

[10] 李付民， 楊靜， 賀樑. 基于中文句法結構的關系挖掘[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]. 計算機工程與科學， 2005（ 12）.