賈丙靜，張振強(qiáng)

（安徽科技學(xué)院信息與網(wǎng)絡(luò)工程學(xué)院，蚌埠 233000）

0 引言

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

1 研究現(xiàn)狀

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

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

2 ID3決策樹算法

2.1 基本原理

ID3算法屬于有監(jiān)督學(xué)習(xí)，通過構(gòu)建樹模型將數(shù)據(jù)分類，每次通過信息增益來選擇劃分的屬性，即每次選擇信息增益最好的屬性，體現(xiàn)了屬性與標(biāo)簽之間的函數(shù)映射關(guān)系。信息增益和信息熵是ID3算法中描述樣本集合純度的一種常用指標(biāo)，假設(shè)當(dāng)前樣本集合S中第i個樣本所占的比例是Pi，則S的信息熵可以表示為

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

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

2.2 算法流程

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

3 信息處理

3.1 實體嵌入

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

3.2 實體流行度

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

3.3 實體上下文

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

4 實驗結(jié)果

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

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

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

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

5 結(jié)語

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