基于決策樹的知識融合關鍵技術研究

賈丙靜，張振強

（安徽科技學院信息與網絡工程學院，蚌埠 233000）

0 引言

大數據時代，網絡中每天都會產生大量的文本、圖片和視頻等數據，這些數據來源多、規模大、表述不規范，為人們獲取知識帶來了極大的挑戰。知識圖譜［1］以圖的形式幫助人們組織現實世界中雜亂無章的數據，實現客觀世界的知識映射。它的基本組成單位是三元組<實體，關系，實體>，其中實體表示真實世界中存在的客觀事物，如人、國家和公司等；關系則表示不同實體之間的某種聯系，如某個影視明星和某個電影之間的主演關系，某個教師和某個課程之間的講授關系等。目前比較流行的知識圖譜有Wikipedia［2］、Freebase［3］、復旦大學的CN-DBpeida［4］和清華大學的XLore［5］等。知識圖譜能夠為語義檢索、智能問答和情感分析等提供知識支撐，然而，知識圖譜普遍存在不完備的問題，現實世界中知識是不斷變化的，人們對世界的描述也在不斷更新和修正。因此，為了更好地滿足系統應用的需求，必須不斷地對知識圖譜進行知識擴充。早期的知識圖譜通常依賴人工構建和擴充，不僅效率低而且成本極高，針對上述問題，擬從實體鏈接的角度進行知識擴充，將文本中挖掘的新實體鏈接到已有的知識庫中。為了提高實體鏈接的效果，首先研究如何學習多源、多模態和異質的數據表示，并對這些特征進行篩選和融合；然后使用ID3決策樹算法對待鏈接數據進行深層次分析，實驗結果表明該算法能夠去除噪音，將實體鏈接到知識庫正確的候選上，從而達到知識擴充的效果。

1 研究現狀

知識擴充是提高知識圖譜完整性的重要手段，已發展成為自然語言領域新的研究熱點。其主要目標是將網絡中獲取的新知識與知識圖譜中已有的知識進行關聯，更新到知識圖譜中。目前文本中獲取的實體與知識圖譜中的實體的關系類別有兩種，一種是在知識圖譜中能找到映射實體，即通過實體鏈接［6］方法就可以擴充知識圖譜；另一種是在知識圖譜中不存在映射實體，需要通過實體分類［7］的方法進行知識合并。其中，實體鏈接獲得了研究人員的廣泛關注，主要包括單實體鏈接和集成實體鏈接兩種方法。單實體鏈接表示在把實體鏈接到知識圖譜的過程中不考慮同一文本中其它實體對其的影響，MPME 模型［8］認為實體的歧義會影響相同語義空間的建模，對于字面表達相同的實體采用同一向量表示顯然是不全面的，因此聯合文本和知識圖譜為不同含義的實體學習不同的特征。

EAT模型［9］把文本中的實體和知識圖譜中的實體放在同一個文本序列中，來學習對象的統一表示，避免單獨學習后的重新對齊。集成實體鏈接在實現的過程中綜合考慮上下文待鏈接實體之間的語義相關性，進行聯合推斷。基于網狀結構的圖可以表示對象之間的復雜關系，為集成實體鏈接提供了新的思路。REL-RW 模型［10］認為當前的主流方法對一些不知名的實體指稱可能并不適用，由此提出在構建圖時不僅要考慮知識圖譜中實體之間的直接關聯，還要考慮它們的間接聯系，在信息論的基礎上綜合考慮所有候選實體的相關度。PPRSim［11］模型通過個性化隨機游走結合整篇文檔的語義特征能過濾掉非正確候選實體帶來的噪音。但是，有些模型只考慮了部分特征，沒用充分利用不同粒度級別的信息，為了改善鏈接的效果，需要使用各層次的信息，并對這些信息進行篩選。因此，分別使用詞向量、先驗流行度和編輯距離來學習待鏈接實體的詞語級別、統計級別和文檔級別的特征，然后基于ID3決策樹算法對這些特征進行篩選，并預測最終的鏈接結果。

2 ID3決策樹算法

2.1 基本原理

ID3算法屬于有監督學習，通過構建樹模型將數據分類，每次通過信息增益來選擇劃分的屬性，即每次選擇信息增益最好的屬性，體現了屬性與標簽之間的函數映射關系。信息增益和信息熵是ID3算法中描述樣本集合純度的一種常用指標，假設當前樣本集合S中第i個樣本所占的比例是Pi，則S的信息熵可以表示為

其中，k表示數據集S中樣本預測結果的種類，Ent(S)越大，數據集S的純度越高。

同樣，設屬性t還有W個可能的特征值t1,t2,…,tw，利用屬性t對數據集S進行分類，將產生W個分支節點，其中第W個分支節點包含S中所有在屬性t上取值為tw的樣例，記為SW，然后根據公式（1）計算出信息熵。由于不同分支節點所包含的數據個數不同，給每個分支節點賦予一個權重 |S|，即數據個數越多的分支節點對預測性能影響越大，于是可以計算出屬性t劃分數據集S所獲得的信息增益，其公式為

2.2 算法流程

對于給定數據集，每個樣本上的屬性可能有多個，不同屬性對分類的作用有大有小，而決策樹的實現過程就是不停地確定跟分類標簽最相關的屬性。ID3算法實現流程為：①對數據集進行預處理，初始化根節點包含所有的數據；②遍歷所有的屬性，選擇信息增益最大的屬性作為決策樹的根節點，并將此屬性刪除；③根據根節點將數據分叉，在剩余的屬性中遞歸地尋找每個分支的最優屬性；④當決策樹到葉子節點或者數據已經不需要再分，算法停止。

3 信息處理

3.1 實體嵌入

詞嵌入通過詞向量描述一個詞，計算詞與詞之間的語義相似度。Le 等［12］認為如果一個詞經常和另一個詞一起出現，那么它們是相似的。然而，詞嵌入模型忽略了短語或實體內在的意義。以Wikipedia 為例，候選實體之間是有關聯的，錨文本和單詞也可能同時出現在一篇文章中，這就為在同一連續空間中聯合學習詞和實體的嵌入提供了便利條件。最新研究表明通過學習實體和詞的嵌入可以提高實體鏈接的效果，Yamada 等［13］先從Wikipedia中提取豐富的結構化信息，再設計Wikipedia2Vec 學習高質量的單詞和實體嵌入。在訓練詞和實體向量時，從Wiki?pedia中抽取文本和錨文本，并基于鏈接結構測量候選實體對之間的關系，因此可以同時得到詞和候選的嵌入。υ(m)和υ(e)分別表示文本中的實體向量和知識圖譜中的候選實體向量，它們之間的相似度可以通過公式（3）的余弦相似度計算。

3.2 實體流行度

實體流行度表示實體的流行程度，它是基于知識圖譜的一種統計特征。根據知識圖譜中候選實體的超鏈接信息計算得到，在不知道上下文的情況下，觀察候選實體是文檔中實體鏈接對象的概率。例如，“李白”有90%的概率指向“李白（唐代著名浪漫主義詩人）”，10%的概率指向“李白（李榮浩演唱歌曲）”，參照文獻［14］中的方法計算實體流行度。

3.3 實體上下文

實體本身的名字包含的字符信息比較少，表層特征差異性比較大，無法提供足夠的證據進行鏈接。而圍繞實體的上下文中含有一些關鍵信息，比如當實體“李白”的周圍出現“詩詞”或者“唐代”等信息時，就暗示該實體鏈接的對象是詩人“李白”而不是歌曲“李白”。另外，候選實體所在的背景知識圖譜也提供了豐富的文本信息，可以基于編輯距離對待鏈接實體和候選實體的上下文語義關聯度進行分析。編輯距離表示一個字符串轉化為另一個字符串需要的最少編輯次數，可進行的操作有：替換、插入和刪除，距離越小說明它們越相似，實體m和待鏈接候選實體e之間的上下文相似度可以通過公式（4）計算得到，其中max len(m,e)表示二者中的較長者。

4 實驗結果

背景知識圖譜采用Wikipedia 官方網站提供的2016 年4 月版本，里面包含豐富的上下文描述文本，鏈接信息和類別信息等。同時，利用詞向量工具wikipedia2vec 學習實體嵌入，維度是300。選擇在AIDA 標準數據集上驗證模型效果，它是Hoffart 等［15］在CoNLL2003 的基礎上重新標注的，整個數據集包含1393 篇新聞文檔，被劃分為訓練集AIDA-Train，驗證集AIDA-A和測試集AIDA-B三部分。

利用精確率、召回率和F1 值來客觀評估實驗結果，只考慮在背景知識圖譜中能找到對應鏈接對象的實體，假設T表示測試數據集中所有待鏈接實體在知識圖譜中的正確結果集合，O表示決策樹算法的輸出結果，可根據公式（5）、（6）和（7）計算決策樹算法在該數據集上的精確率（P）、召回率（R）和F1值。

ID3是一種貪心算法，在構造決策樹的過程中，除了計算特征的信息增益外，還要考慮樹的深度影響，在用sklearn 包實現該算法的過程中，比較不同樹深度下的精確率、召回率和F1值，結果如圖1 所示，樹的深度默認從3 開始，當深度為14 時整體效果最好，這時精確率P為0.74，召回率R為0.78，F1值為0.76。

圖1 不同樹深度下的精確率、召回率和F1值對比

5 結語

隨著人工智能和大數據的發展，網絡上每天都會涌現新的知識，知識融合將新知識鏈接到已有的知識圖譜中去，從而解決知識圖譜不完整問題。ID3算法的核心思想就是以信息增益來度量屬性的選擇，選擇分裂后信息增益最大的屬性進行劃分，該算法采用自頂向下的貪婪搜索遍歷可能的決策空間。在此算法的基礎上，研究實體嵌入、先驗流行度和實體上下文特征如何將文本中的實體鏈接到知識圖譜對應候選中去，從而完成新知識的融合。