基于圖排序和最大信息增益的領(lǐng)域?qū)嶓w抽取方法

張曉明，鄭理欣，王會(huì)勇

（河北科技大學(xué)信息科學(xué)與工程學(xué)院，石家莊 050018）

0 概述

隨著知識(shí)圖譜技術(shù)的發(fā)展，越來(lái)越多的研究開(kāi)始從通用知識(shí)圖譜轉(zhuǎn)向領(lǐng)域知識(shí)圖譜，例如醫(yī)療知識(shí)圖譜、金融知識(shí)圖譜、電商知識(shí)圖譜、課程知識(shí)圖譜等。領(lǐng)域知識(shí)圖譜中的節(jié)點(diǎn)是領(lǐng)域?qū)嶓w，因此，領(lǐng)域?qū)嶓w的挖掘是構(gòu)建領(lǐng)域知識(shí)圖譜的基礎(chǔ)。以課程知識(shí)圖譜為例，將傳統(tǒng)的非結(jié)構(gòu)化文本形式轉(zhuǎn)化為以課程術(shù)語(yǔ)實(shí)體為核心的知識(shí)圖譜，更易于學(xué)生對(duì)學(xué)科架構(gòu)［1］、知識(shí)點(diǎn)的學(xué)習(xí)。教育知識(shí)圖譜中的節(jié)點(diǎn)具有多樣性，如節(jié)點(diǎn)可以為術(shù)語(yǔ)、視頻資源、知識(shí)點(diǎn)等，而術(shù)語(yǔ)是最基礎(chǔ)、最細(xì)粒度的學(xué)習(xí)資源。因此，構(gòu)建課程領(lǐng)域?qū)嶓w集對(duì)教育知識(shí)圖譜的構(gòu)建起著重要的作用，為教育課程推薦、個(gè)性化學(xué)習(xí)等任務(wù)［2-4］奠定了基礎(chǔ)。

目前對(duì)于實(shí)體抽取方法的研究主要采用基于機(jī)器學(xué)習(xí)的方法、基于深度學(xué)習(xí)的方法和基于關(guān)系的方法。垂直領(lǐng)域?qū)嶓w抽取與公開(kāi)領(lǐng)域?qū)嶓w抽取特點(diǎn)不同，垂直領(lǐng)域的語(yǔ)料較少，標(biāo)注數(shù)據(jù)稀缺，因此基于機(jī)器學(xué)習(xí)的方法、基于深度學(xué)習(xí)的方法在領(lǐng)域?qū)嶓w抽取過(guò)程中存在一定的限制?；陉P(guān)系的實(shí)體抽取方法則是先獲得候選實(shí)體，然后在給定種子的基礎(chǔ)上利用實(shí)體間關(guān)系進(jìn)行排序篩選，其中對(duì)于非結(jié)構(gòu)文本數(shù)據(jù)源需要先構(gòu)建相關(guān)度等關(guān)系再進(jìn)行排序，對(duì)于結(jié)構(gòu)化的知識(shí)則通過(guò)一定的策略利用已有的結(jié)構(gòu)關(guān)系進(jìn)行實(shí)體挖掘。

本文提出一種基于關(guān)系的領(lǐng)域?qū)嶓w挖掘方法，基于結(jié)構(gòu)相關(guān)度從文本中構(gòu)建實(shí)體圖以抽取領(lǐng)域核心實(shí)體，根據(jù)最大信息增益原理在DBpedia 中對(duì)核心實(shí)體進(jìn)行擴(kuò)展。通過(guò)對(duì)基于維基百科的TagMe 系統(tǒng)進(jìn)行實(shí)體識(shí)別，計(jì)算實(shí)體間的相關(guān)度，并根據(jù)圖排序算法進(jìn)行實(shí)體抽取獲得領(lǐng)域核心實(shí)體作為種子實(shí)體集，在CSEN、EcoEN 數(shù)據(jù)集上對(duì)實(shí)體抽取方法進(jìn)行評(píng)估?；诜N子實(shí)體集在DBpedia 中計(jì)算具有最大信息增益的類，并將其實(shí)例經(jīng)篩選后作為擴(kuò)展實(shí)體，最終在INEX 數(shù)據(jù)集上對(duì)實(shí)體擴(kuò)展方法進(jìn)行評(píng)估。

1 相關(guān)工作

早期的實(shí)體抽取分為基于規(guī)則的方法［5-6］和基于統(tǒng)計(jì)的方法［7-8］?；谝?guī)則的方法抽取的實(shí)體準(zhǔn)確率較高，但依賴領(lǐng)域語(yǔ)言特點(diǎn)，且領(lǐng)域移植性較差?；诮y(tǒng)計(jì)的方法利用術(shù)語(yǔ)共現(xiàn)和詞頻等特征抽取實(shí)體，對(duì)低頻術(shù)語(yǔ)不敏感，且依賴目標(biāo)語(yǔ)料庫(kù)。因此，基于以上方法的局限性，目前對(duì)實(shí)體抽取的方法主要采用基于機(jī)器學(xué)習(xí)的方法、基于深度學(xué)習(xí)的方法和基于關(guān)系的方法。

1.1 基于機(jī)器學(xué)習(xí)的實(shí)體抽取

該方法一般通過(guò)序列標(biāo)注［9］、術(shù)語(yǔ)分布等特征利用分類算法抽取實(shí)體，通常需要大量的訓(xùn)練數(shù)據(jù)訓(xùn)練算法模型，實(shí)體抽取的準(zhǔn)確率較高。但不同于通用領(lǐng)域的數(shù)據(jù)，領(lǐng)域的標(biāo)注數(shù)據(jù)較為缺乏，由領(lǐng)域?qū)＜襾?lái)標(biāo)注數(shù)據(jù)則會(huì)消耗大量的時(shí)間和人力資源，因此這種方法在構(gòu)建領(lǐng)域?qū)嶓w集時(shí)代價(jià)成本較高。

1.2 基于深度學(xué)習(xí)的實(shí)體抽取

該方法通過(guò)對(duì)文本向量嵌入，將嵌入向量輸入到深度學(xué)習(xí)模型中，經(jīng)過(guò)多個(gè)處理層的學(xué)習(xí)來(lái)抽取實(shí)體。基于深度學(xué)習(xí)的實(shí)體抽取方法不需要人工特征工程，具有強(qiáng)大的學(xué)習(xí)能力，也是近年來(lái)較好的實(shí)體抽取方法，典型的神經(jīng)網(wǎng)絡(luò)模型有BiLSTM［10-11］、CNN-LSTM-CRF［12-13］等，但該方法也存在一些限制，例如需要大量的標(biāo)注數(shù)據(jù)，訓(xùn)練模型的時(shí)間較長(zhǎng)，且存在模型復(fù)雜、可解釋性弱的缺點(diǎn)。

1.3 基于關(guān)系的實(shí)體抽取

該方法通常在給定少數(shù)種子的條件下，利用候選實(shí)體間的關(guān)系進(jìn)行排序來(lái)抽取領(lǐng)域?qū)嶓w。候選實(shí)體間的關(guān)系有類別信息［14］、結(jié)構(gòu)路徑關(guān)系［15］、語(yǔ)義路徑［16］、語(yǔ)義距離［17］等。排序過(guò)程通常利用圖排序算法［18］通過(guò)主題信息進(jìn)行編碼或利用候選實(shí)體之間的相互加強(qiáng)關(guān)系［19］來(lái)提高候選詞的排名效果。

基于圖排序的實(shí)體抽取方法較為常用，該方法的來(lái)源為PageRank 算法，將實(shí)體間關(guān)系緊密程度和領(lǐng)域?qū)嶓w的置信度作為衡量領(lǐng)域?qū)嶓w的依據(jù)，以此來(lái)迭代更新實(shí)體節(jié)點(diǎn)的置信度。例如利用單詞上下文的語(yǔ)義信息［20］、位置信息［21］及圖 結(jié)構(gòu)的 主題信息［19］迭代更新圖，對(duì)候選術(shù)語(yǔ)進(jìn)行排序?；趫D排序的實(shí)體抽取方法不需要大量的標(biāo)注數(shù)據(jù)，不存在低頻術(shù)語(yǔ)不敏感問(wèn)題，是效率較高的實(shí)體抽取方法。

基于關(guān)系的實(shí)體抽取方法不需要大量的人工參與，具有普適性及可解釋性的優(yōu)點(diǎn)，因此利用該類方法構(gòu)建課程領(lǐng)域?qū)嶓w集。首先利用維基百科的信息計(jì)算相關(guān)度來(lái)構(gòu)建實(shí)體間關(guān)系，通過(guò)排序算法從中抽取領(lǐng)域核心實(shí)體，然后在知識(shí)圖譜中利用最大信息增益進(jìn)行實(shí)體擴(kuò)展，最后通過(guò)計(jì)算擴(kuò)展實(shí)體與領(lǐng)域核心實(shí)體的相關(guān)度進(jìn)行擴(kuò)展實(shí)體的過(guò)濾，提高領(lǐng)域?qū)嶓w集的質(zhì)量。

2 問(wèn)題描述

本文研究的問(wèn)題是如何構(gòu)建領(lǐng)域?qū)嶓w集。首先從文本中構(gòu)建候選實(shí)體圖，并利用圖排序算法抽取領(lǐng)域核心實(shí)體；然后對(duì)DBpedia 中的subject 關(guān)系利用最大信息增益原理對(duì)核心實(shí)體進(jìn)行擴(kuò)展；最后通過(guò)實(shí)體過(guò)濾策略進(jìn)一步提高領(lǐng)域?qū)嶓w集的準(zhǔn)確性。任務(wù)描述如圖1 所示。

圖1 任務(wù)描述Fig.1 Tasks description

對(duì)使用的符號(hào)進(jìn)行以下定義，候選實(shí)體圖表示為G=（T，R），其中包括候選實(shí)體節(jié)點(diǎn)T和候選實(shí)體間的相關(guān)度R，ti（i=1，2，…，n）表示候選實(shí)體，rij（i=1，2，…，n，j=1，2，…，n）表示候選實(shí)體ti和tj的相關(guān)度，TC為領(lǐng)域核心實(shí)體集（TC?T），TC的擴(kuò)展實(shí)體集表示為T(mén)E，擴(kuò)展實(shí)體集篩選過(guò)濾得到的領(lǐng)域全部實(shí)體集表示為T(mén)D。

領(lǐng)域?qū)嶓w集獲取方法主要包括3 個(gè)步驟：

步驟1在文本中進(jìn)行實(shí)體識(shí)別，計(jì)算兩兩實(shí)體間的相關(guān)度構(gòu)建實(shí)體圖G，并通過(guò)基于置信度傳播的圖排序算法得到領(lǐng)域?qū)嶓wTC。

步驟2將文本抽取的領(lǐng)域?qū)嶓wTC作為種子，利用DBpedia 中的subject 關(guān)系進(jìn)行實(shí)體擴(kuò)展，得到擴(kuò)展實(shí)體集TE。

步驟3通過(guò)篩選策略對(duì)擴(kuò)展的實(shí)體過(guò)濾，以提高領(lǐng)域?qū)嶓w集的準(zhǔn)確率，獲得領(lǐng)域?qū)嶓w集TD。

3 基于圖排序的實(shí)體抽取

基于文本的實(shí)體抽取主要分為構(gòu)建候選實(shí)體圖和對(duì)候選實(shí)體排序兩大步驟。

3.1 候選實(shí)體圖的構(gòu)建

構(gòu)建候選實(shí)體圖的目的是利用文本中的實(shí)體及實(shí)體間的關(guān)系構(gòu)建一個(gè)圖，思想為識(shí)別文本中所有的實(shí)體作為候選實(shí)體集，候選實(shí)體之間通過(guò)相關(guān)度建立相關(guān)關(guān)系，這樣就形成了一個(gè)結(jié)點(diǎn)為候選實(shí)體、邊為相關(guān)度的候選實(shí)體圖。

文本中的實(shí)體通常以縮讀、口語(yǔ)化等形式出現(xiàn)，使得多個(gè)名詞性短語(yǔ)表達(dá)的是同一實(shí)體，因此將文本語(yǔ)料中的名詞性短語(yǔ)和維基百科中的實(shí)體建立映射關(guān)系，減少冗余實(shí)體。實(shí)體映射過(guò)程利用TagMe系統(tǒng)［22］對(duì)輸入的文本自動(dòng)識(shí)別出實(shí)體，并返回維基百科對(duì)應(yīng)的實(shí)體。

候選實(shí)體間通過(guò)相關(guān)度建立關(guān)聯(lián)，候選實(shí)體間的相關(guān)度是指兩個(gè)候選實(shí)體存在相關(guān)關(guān)系的可能性大小，其取值為［0～1］，值越大表示兩候選實(shí)體間的相關(guān)性越強(qiáng)。每個(gè)實(shí)體在維基百科中有詳細(xì)描述信息，在描述信息中提及次數(shù)較多的實(shí)體通常與該實(shí)體具有較強(qiáng)的相關(guān)程度，且每個(gè)相關(guān)實(shí)體都是以超鏈接形式存在的。因此，利用WML［23］模型，通過(guò)比較兩個(gè)維基百科頁(yè)面的輸入和輸出的超鏈接來(lái)衡量其語(yǔ)義相關(guān)度。對(duì)于兩個(gè)候選實(shí)體ti和tj，I和J是分別鏈接到ti和tj的維基百科頁(yè)面的超鏈接集合，W是維基百科中實(shí)體的集合，r（ti，tj）表示兩候選實(shí)體間的相關(guān)度，通過(guò)WML 計(jì)算，如式（1）所示：

候選實(shí)體圖G由所有的候選實(shí)體T和候選實(shí)體間的關(guān)系R組成，其中兩兩候選實(shí)體都通過(guò)相關(guān)度計(jì)算建立聯(lián)系，但由于較低的相關(guān)度值r（ti，tj）在接下來(lái)的基于置信度傳播的圖排序算法中可能引入噪聲，因此引入了一個(gè)相關(guān)度閾值α來(lái)修剪圖，即當(dāng)候選實(shí)體間的相關(guān)度r（ti，tj）大于閾值α?xí)r才保留在圖G中。

3.2 基于置信度傳播的圖排序算法

對(duì)實(shí)體圖的候選實(shí)體按照與領(lǐng)域的相關(guān)程度排序得到領(lǐng)域?qū)嶓w。對(duì)于實(shí)體圖G中的每個(gè)候選實(shí)體ti，將conf（ti）作為領(lǐng)域?qū)嶓w的置信度。與較高置信度候選實(shí)體相關(guān)度高的實(shí)體很大可能也是該領(lǐng)域?qū)嶓w，從而可以發(fā)現(xiàn)其他潛在的領(lǐng)域?qū)嶓w。這里利用基于置信度傳播的圖迭代算法CCP［18］對(duì)候選實(shí)體進(jìn)行排序。

首先給圖G中的每個(gè)候選實(shí)體ti分配一個(gè)初始置信度，然后通過(guò)相鄰候選實(shí)體的置信度及候選實(shí)體間的相關(guān)度迭代更新每個(gè)候選實(shí)體節(jié)點(diǎn)的置信度值。初始情況候選實(shí)體的置信度值由種子集決定，即將種子實(shí)體置信度值設(shè)為1，其他候選實(shí)體置信度值設(shè)為0。實(shí)體ti的置信度用conf（ti）表示，ti迭代k次后實(shí)體的置信度用confk+1（ti）表示，A（ti）表示與候選實(shí)體ti的鄰居實(shí)體。置信度更新過(guò)程則是由A（ti）投票得分的平均值計(jì)算而來(lái)，即每次置信度的更新受其鄰居實(shí)體的影響，若鄰居置信度較高，則表示該實(shí)體是領(lǐng)域?qū)嶓w的可能性也越大。達(dá)到迭代停止條件時(shí)通過(guò)設(shè)定截止置信度閾值來(lái)選擇領(lǐng)域?qū)嶓w，即置信度大于閾值的為領(lǐng)域核心實(shí)體TC，小于閾值的為非領(lǐng)域核心實(shí)體。圖傳播算法的迭代過(guò)程如式（2）所示：

其中：Z為標(biāo)準(zhǔn)化因子，取值為所有候選實(shí)體置信度的最大值；|A（ti）|表示ti鄰居節(jié)點(diǎn)的個(gè)數(shù)；vsk（ti，tj）為候選實(shí)體tj對(duì)候選實(shí)體ti的影響，vsk（ti，tj）定義如式（3）所示，即tj的置信度與ti和tj的相關(guān)度值乘積。

基于文本的實(shí)體抽取具體實(shí)例如圖2 所示。以數(shù)據(jù)結(jié)構(gòu)課程中的部分文本內(nèi)容為例，通過(guò)TagMe 系統(tǒng)識(shí)別出候選實(shí)體“Huffman coding，Binary expression tree，Data compression，Binary tree，Binary code，AA tree，Red-black tree”。計(jì)算兩兩候選實(shí)體間的相關(guān)度，并將相關(guān)度值小于閾值α的邊r（Huffman coding，Binary code）、r（Data compression，Binary expression tree）、r（Binary tree，Binary code）等剪枝。給定種子實(shí)體為“Binary tree，Red-black tree”，則conf0（Binary tree）=1，conf0（Red-black tree）=1，其余候選實(shí)體初始置信度為0，第1 次迭代后各候選實(shí)體的置信度更新。迭代達(dá)到停止條件后取大于置信度閾值實(shí)體TC（“Huffman coding，Binary expression tree，Binary tree，AA tree，Redblack tree”）為數(shù)據(jù)結(jié)構(gòu)課程實(shí)體。

圖2 實(shí)體抽取實(shí)例Fig.2 Entity extraction example

4 基于最大信息增益的實(shí)體擴(kuò)展

4.1 方法步驟

由于從文本中抽取的領(lǐng)域?qū)嶓w不夠全面，因此需要進(jìn)行實(shí)體擴(kuò)展。下文對(duì)使用的概念進(jìn)行定義，類表示實(shí)體在DBpedia 中通過(guò)subject 關(guān)系相連的抽象概念。每個(gè)實(shí)體有多個(gè)類，例如Red-black tree 的類有Binary trees、1972 in computing 等。

利用DBpedia 的subject 關(guān)系獲得種子的類，在類中利用最大信息增益獲得與種子相關(guān)程度較高的類，稱為共性類，然后將共性類的實(shí)例作為擴(kuò)展實(shí)體TE，最后通過(guò)計(jì)算擴(kuò)展實(shí)體與種子的相關(guān)程度進(jìn)行篩選過(guò)濾得到領(lǐng)域?qū)嶓wTD。該方法主要包括以下3 個(gè)步驟：

步驟1生成共性類。實(shí)體從不同的角度來(lái)看屬于不同的類，會(huì)劃分到不同的類下，共性類則是與種子集相關(guān)的類，即共性類能盡可能多地涵蓋種子集中的實(shí)體。

步驟2共性類實(shí)例擴(kuò)展。共性類通過(guò)subject的逆關(guān)系Is subject of 得到共性類的所有實(shí)例作為擴(kuò)展實(shí)體TE。

步驟3擴(kuò)展實(shí)體過(guò)濾。通過(guò)計(jì)算擴(kuò)展實(shí)體與種子的相關(guān)性對(duì)擴(kuò)展實(shí)體進(jìn)一步篩選，以提高領(lǐng)域?qū)嶓w集的準(zhǔn)確率。

4.2 共性類生成

共性類利用種子集與類的相關(guān)性和類的抽象程度兩個(gè)因素衡量。當(dāng)類的抽象程度較高時(shí)，其包含的實(shí)例通常越多，與種子集有較強(qiáng)相關(guān)性的概率越大，但抽象程度較高的類包含的實(shí)例也就越雜，即非領(lǐng)域?qū)嶓w就越多，因此當(dāng)類同時(shí)滿足種子集與該類的相關(guān)性較高且類的抽象程度較低2 個(gè)條件時(shí)才為種子集的共性類。為平衡這兩方面因素的影響，采用最大信息增益原理將2 個(gè)條件相結(jié)合，如式（4）所示：

其中：c（t）表示實(shí)體t的所有類；ci表示其中一個(gè)類；p表示實(shí)體t的類ci與種子集TC具有共同特性的程度，取值范圍為［0，1］，值越大，表示類ci與TC的共性程度越高；I表示類的抽象程度，通過(guò)類的實(shí)例個(gè)數(shù)來(lái)計(jì)算。

式（4）參考了文獻(xiàn)［15］實(shí)體擴(kuò)展方法，其方法是在DBpedia 的DBO 體系中，根據(jù)關(guān)系路徑的抽象程度和該路徑上的實(shí)體與種子的相關(guān)程度來(lái)選擇合適的關(guān)系路徑，并對(duì)路徑上的實(shí)體進(jìn)行相關(guān)度排序得到擴(kuò)展實(shí)體。本文則是在DBpedia 的SKOS 體系中，通過(guò)計(jì)算subject關(guān)系對(duì)應(yīng)的類與種子的相關(guān)程度及其抽象程度選擇合適的類，并對(duì)其實(shí)例進(jìn)行過(guò)濾篩選，其中根據(jù)類的實(shí)例集與種子集的共現(xiàn)情況來(lái)計(jì)算類的相關(guān)性，通過(guò)類包含的實(shí)例個(gè)數(shù)評(píng)判其抽象程度。

最大信息增益是用來(lái)描述一個(gè)屬性區(qū)分?jǐn)?shù)據(jù)樣本的能力，在這里最大信息增益是用來(lái)衡量類與種子集的共性程度，判斷是否為共性類是從該類的相關(guān)性和抽象程度兩個(gè)方面確定的。因?yàn)橄嚓P(guān)性高的類通常抽象程度較高，抽象程度低的類與種子的相關(guān)性通常較低，而生成共性類的目標(biāo)是高相關(guān)性與低抽象程度，所以要平衡存在矛盾的相關(guān)程度和抽象程度方面因素，采用I（cj）-I（cj|ci）來(lái)衡量，該公式表示在計(jì)算類ci的共性值情況下，周圍類cj對(duì)ci的影響，cj的抽象程度越低且與ci的相關(guān)程度越高，對(duì)ci共性值的計(jì)算影響就越大。ci（t）值越大表示類ci與種子的相關(guān)度高，并且周邊的類也與種子相關(guān)度高，同時(shí)周邊類的抽象程度低。c*（t）表示實(shí)例t的類中最大的共性值，最大共性值對(duì)應(yīng)的類作為共性類。

4.2.1 種子集與類的相關(guān)性的計(jì)算

種子集與類的相關(guān)性由種子集與類實(shí)例的交集個(gè)數(shù)判斷。判別方法如圖3 所示，對(duì)于種子集t1、t2、t3中t1的類：類1 和類2，類1 的實(shí)例包括t1、t2、t4、t5、t6，類2 的實(shí)例包括t1、t7、t8、t9，類1 的實(shí)例與種子集有t1、t2兩個(gè)相同的實(shí)例，類2 的實(shí)例與種子集有t1一個(gè)相同的實(shí)例。類的實(shí)例與種子集交集個(gè)數(shù)越多，該類與種子集的相關(guān)性越高，所以類1 比類2 具有更高的相關(guān)性。

圖3 種子集與類相關(guān)性示意圖Fig.3 Schematic diagram of correlation between seed sets and classes

通過(guò)式（5）計(jì)算類與種子集的相關(guān)性程度，將兩者的交集個(gè)數(shù)作為衡量相關(guān)性的標(biāo)準(zhǔn)。

其中：TC表示種子集；‖‖TC表示種子集的個(gè)數(shù)；E（ci（t））表示實(shí)例t的類ci的實(shí)例。

種子集與類的相關(guān)性計(jì)算具體實(shí)例如圖4 所示。以種子集TC=｛AVL tree，B-tree，Red black tree｝中AVL tree為例，其類為Soviet inventions，Binary trees，Search trees，AVL tree 與3 個(gè)類的實(shí)例交集個(gè)數(shù)分別為1、2、2，相關(guān)度分別為1/3、2/3、2/3，則與TC相關(guān)度高的類為Binary trees、Search trees。

圖4 種子集與類相關(guān)性實(shí)例Fig.4 Correlation between seed sets and classes example

4.2.2 類的抽象程度計(jì)算

類的抽象程度是指對(duì)實(shí)體描述的粗細(xì)程度，對(duì)實(shí)體描述的越抽象，抽象程度越高，即該類的實(shí)例涵蓋范圍越廣，實(shí)體集間的相關(guān)性越小。實(shí)體擴(kuò)展過(guò)程的目標(biāo)則是生成抽象程度較低的類。通常抽象程度高的類，其實(shí)例數(shù)量一般也越多，抽象程度越低的類，其實(shí)例數(shù)量越少。因此，通過(guò)類的實(shí)例數(shù)量來(lái)判斷其抽象程度，計(jì)算公式如式（6）所示：其中：N為t的類中實(shí)例個(gè)數(shù)最大的值；I值越大表示類的抽象程度越低，即該類的表達(dá)粒度越細(xì)。目標(biāo)是獲得抽象程度低的類，即I值越大越好。

通過(guò)式（7）探究類和周邊的類之間的相關(guān)性，其值越小表示各個(gè)類之間的關(guān)聯(lián)強(qiáng)度越強(qiáng)。類cj與類ci的相關(guān)性越強(qiáng)，則表明類cj對(duì)類ci的影響越重要，該值越小越好。

由于取共性類時(shí)僅將共性值最大的一個(gè)類用來(lái)擴(kuò)展，使得擴(kuò)展的實(shí)例較少，因此為提高領(lǐng)域?qū)嶓w的召回率，采用松弛機(jī)制適當(dāng)放松生成類的條件，即為每個(gè)實(shí)體生成多個(gè)共性類，使得在保證一定查準(zhǔn)率的同時(shí)提高擴(kuò)展實(shí)體的查全率。當(dāng)類ci的共性值ci（t）與最大共性類值c*（t）比值大于閾值θ時(shí)，類ci也作為實(shí)體的共性類。如圖4 中AVL tree 的類中Search trees、Binary trees 都和數(shù)據(jù)結(jié)構(gòu)課程的關(guān)聯(lián)性較強(qiáng)，若僅選擇其中一個(gè)類來(lái)擴(kuò)展，則擴(kuò)展的實(shí)例較少，因此在使用松弛機(jī)制后生成了多個(gè)類，會(huì)進(jìn)一步提高領(lǐng)域?qū)嶓w的召回率。

4.3 實(shí)例擴(kuò)展和過(guò)濾

通過(guò)以上步驟獲取共性類，在DBpedia 中，共性類與其實(shí)例之間通過(guò)關(guān)系（Is subject of）相連，因此通過(guò)該關(guān)系提取共性類的實(shí)例作為擴(kuò)展實(shí)體。例如AVL tree的類Search trees 包含的實(shí)例：Red black tree，Binary Search tree，（a，b）-tree，…均為AVL tree的擴(kuò)展實(shí)體。

擴(kuò)展過(guò)程也會(huì)引入噪聲，例如類Binary trees 的實(shí)例中除Binary search tree、Top tree 外，還有Interleave lower bound、Rotation distance 這樣的非數(shù)據(jù)結(jié)構(gòu)的實(shí)體，因此需要對(duì)擴(kuò)展實(shí)體再進(jìn)行篩選。

領(lǐng)域?qū)嶓w中許多實(shí)體是由單詞拼接而成的，以數(shù)據(jù)結(jié)構(gòu)課程為例統(tǒng)計(jì)了術(shù)語(yǔ)實(shí)體中由詞綴拼接而成的情況，如圖5 所示，這對(duì)判別術(shù)語(yǔ)實(shí)體間相似度有著很大的參考價(jià)值。

圖5 領(lǐng)域?qū)嶓w特點(diǎn)分析Fig.5 Analysis of domain entities characteristics

但基于字符串相似的特征具有局限性，沒(méi)有考慮到實(shí)體間結(jié)構(gòu)語(yǔ)義相關(guān)性，因此在計(jì)算擴(kuò)展實(shí)體tj與種子集TC相關(guān)度時(shí)，將基于字符串的相似度Comm（ti，tj）和基于結(jié)構(gòu)的相關(guān)度r（ti，tj）進(jìn)行相加作為實(shí)例與種子集的相關(guān)度Sim，如式（8）所示：

字符串相似度計(jì)算采用SMOA 算法［24］的Comm方法，如式（9）所示：

其中：分子為兩個(gè)字符串的最大公共子串長(zhǎng)度的兩倍；分母為兩字符串的長(zhǎng)度之和。

基于結(jié)構(gòu)的相關(guān)度r（ti，tj）利 用TagMe 系統(tǒng)實(shí)現(xiàn)，原理如式（1）所示。

擴(kuò)展實(shí)體篩選過(guò)程首先計(jì)算擴(kuò)展實(shí)體與每個(gè)種子的相關(guān)度，然后將該擴(kuò)展實(shí)體與種子集相關(guān)度均值作為該擴(kuò)展實(shí)體的相關(guān)程度，最后將擴(kuò)展實(shí)體按相關(guān)度值由大到小排序，取topN 為領(lǐng)域?qū)嶓wTD。

5 實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)體抽取實(shí)驗(yàn)分析

本節(jié)首先分析實(shí)體間相關(guān)度閾值α和圖傳播算法迭代次數(shù)兩個(gè)參數(shù)的影響，然后在最佳參數(shù)條件下與實(shí)體抽取基線方法分別在公開(kāi)數(shù)據(jù)集和領(lǐng)域數(shù)據(jù)集上進(jìn)行對(duì)比。

5.1.1 數(shù)據(jù)集和評(píng)價(jià)指標(biāo)

在數(shù)據(jù)集CSEN、EcoEN［18］上進(jìn)行實(shí)體抽取實(shí)驗(yàn)對(duì)比。數(shù)據(jù)集CSEN、EcoEN 是從MOOC 平臺(tái)的Coursera 和XuetangX 上收集計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)英文版本的課程資源，其中從8 個(gè)計(jì)算機(jī)科學(xué)課程中收集視頻字幕來(lái)形成CSEN 數(shù)據(jù)集，從5 個(gè)經(jīng)濟(jì)學(xué)課程中選取視頻字幕來(lái)構(gòu)建EcoEN 數(shù)據(jù)集。

實(shí)驗(yàn)評(píng)測(cè)指標(biāo)選擇精確率P、召回率R、F1 值、R-precision（Rp）、mean Average Precision（mAP）。精確率P是指擴(kuò)展結(jié)果中領(lǐng)域?qū)嶓w個(gè)數(shù)與擴(kuò)展實(shí)體個(gè)數(shù)的比值。召回率R是指擴(kuò)展結(jié)果中領(lǐng)域?qū)嶓w個(gè)數(shù)與領(lǐng)域?qū)嶓w個(gè)數(shù)之比。F1 值是對(duì)精確率P和召回率R的綜合評(píng)價(jià)。Rp 是一個(gè)關(guān)注排名的信息檢索指標(biāo)，給定一個(gè)包含n個(gè)種子的排名列表，它計(jì)算排序后的前n個(gè)實(shí)體中領(lǐng)域?qū)嶓w的精確率。平均精度均值（mAP）是信息檢索中評(píng)價(jià)排名列表的重要評(píng)價(jià)指標(biāo)，AP 指的是在不同召回率上的準(zhǔn)確率，mAP 是AP的平均值，如式（10）所示：

其中：n為種子的個(gè)數(shù)；Ri為n個(gè)召回率；P（Ri）表示在召回率為Ri時(shí)的準(zhǔn)確率。

5.1.2 實(shí)體抽取實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)體相關(guān)度閾值α這一參數(shù)控制著實(shí)體圖中邊的建立。當(dāng)α過(guò)小時(shí)，一方面使得實(shí)體圖中的邊較多，計(jì)算復(fù)雜度大，另一方面使得置信度傳播過(guò)程噪聲增大。當(dāng)α過(guò)大時(shí)，會(huì)使得存在相關(guān)性的實(shí)體間因未建立邊而造成召回率較低。如圖6 所示，當(dāng)α取0.2 時(shí)Rp、mAP 取得最高值，因此實(shí)體圖構(gòu)建時(shí)候選實(shí)體間相關(guān)度閾值設(shè)為0.2。

圖6 不同閾值的Rp 和mAP值Fig.6 Rp and mAP values of different thresholds

迭代次數(shù)決定圖迭代何時(shí)結(jié)束，迭代次數(shù)過(guò)少會(huì)使得置信度不能充分傳播到每個(gè)實(shí)體上，導(dǎo)致領(lǐng)域?qū)嶓w的實(shí)體置信度值較低而被過(guò)濾掉，從而使召回率較低。迭代次數(shù)過(guò)多則會(huì)使置信度值趨于一致，從而引入非領(lǐng)域?qū)嶓w且浪費(fèi)計(jì)算資源。圖7 所示為在不同迭代次數(shù)的條件下Rp 和mAP 值。迭代次數(shù)過(guò)少則無(wú)法擴(kuò)展更多的領(lǐng)域?qū)嶓w，例如當(dāng)初始條件時(shí)（即迭代次數(shù)為0）領(lǐng)域?qū)嶓w僅為種子，迭代次數(shù)過(guò)多則在擴(kuò)展實(shí)體中引入非領(lǐng)域?qū)嶓w，例如當(dāng)?shù)螖?shù)過(guò)多時(shí)，高置信度的實(shí)體會(huì)被鄰居節(jié)點(diǎn)的投票得分拉低，導(dǎo)致領(lǐng)域?qū)嶓w與非領(lǐng)域?qū)嶓w置信度值趨于一致。從圖7 可以看出，迭代次數(shù)從6 到11 時(shí)尚有下降趨勢(shì)，說(shuō)明迭代過(guò)程中擴(kuò)展了領(lǐng)域?qū)嶓w，導(dǎo)致種子實(shí)體排名下降。第11 次迭代后基本不變，說(shuō)明基本不再擴(kuò)展更多的領(lǐng)域?qū)嶓w，所以種子實(shí)體排名也基本不變，如果繼續(xù)迭代則會(huì)使得所有實(shí)體置信度值的差值越來(lái)越小，不利于根據(jù)置信度值判定是否為領(lǐng)域?qū)嶓w，因此最佳迭代次數(shù)為11。

圖7 不同迭代次數(shù)的Rp 和mAP值Fig.7 Rp and mAP values of different iterations

5.1.3 與基線實(shí)驗(yàn)的對(duì)比

實(shí)體抽取的實(shí)驗(yàn)基線選取了兩個(gè)基于統(tǒng)計(jì)的方法TF-IDF 和PMI，兩個(gè)基于圖的方法TextRank、topic PageRank（TPR）與CCP，基線結(jié)果來(lái)自文獻(xiàn)［18］。從表1 可以看出（粗體數(shù)字為最優(yōu)結(jié)果），在CSEN 數(shù)據(jù)集上的Rp 和mAP 評(píng)價(jià)指標(biāo)僅次于最優(yōu)的CCP 方法，在EcoEN 數(shù)據(jù)集上Rp 指標(biāo)達(dá)到最優(yōu)效果，mAP指標(biāo)僅次于TPR 方法?？傮w分析可以看出，本文實(shí)驗(yàn)效果與CCP 接近，但本文實(shí)驗(yàn)不需要搜集大量的領(lǐng)域資料與嵌入過(guò)程，相比而言，本文實(shí)驗(yàn)的操作更加便捷。

表1 實(shí)體抽取結(jié)果Table 1 Results of entity extraction

5.1.4 領(lǐng)域數(shù)據(jù)集的實(shí)體抽取實(shí)驗(yàn)結(jié)果

數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)嶓w抽取數(shù)據(jù)源為數(shù)據(jù)結(jié)構(gòu)教材，以每章中的節(jié)為單位進(jìn)行實(shí)體抽取，評(píng)價(jià)結(jié)果為各節(jié)評(píng)測(cè)值的平均值。實(shí)驗(yàn)對(duì)比基線為T(mén)extRank、TF-IDF，評(píng)價(jià)指標(biāo)采用P@n、Rp 和mAP，在P@n中n分別取值5、10、20，結(jié)果如表2 所示（粗體數(shù)字為最優(yōu)結(jié)果）。

表2 數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)嶓w的抽取結(jié)果Table 2 Extraction results of data structure domain entity

由于基于圖的TextRank方法和基于詞頻統(tǒng)計(jì)的TFIDF 方法均受到語(yǔ)料規(guī)模及質(zhì)量的影響，因此在語(yǔ)料相對(duì)較少的情況下實(shí)驗(yàn)效果較差，而本文所提出的方法則是利用維基百科作為背景知識(shí)進(jìn)行實(shí)體抽取，因此受語(yǔ)料影響較小，從而具有較好的實(shí)驗(yàn)結(jié)果。

從表2 中可以看出，在評(píng)測(cè)指標(biāo)P@n中，隨著n的增大，P@n呈下降趨勢(shì)，這是合理的現(xiàn)象。因?yàn)閷?shí)體按領(lǐng)域性相關(guān)性排序后，在領(lǐng)域相關(guān)性越強(qiáng)的部分領(lǐng)域?qū)嶓w越密集，隨著領(lǐng)域性的減弱，領(lǐng)域?qū)嶓w越稀疏，所以會(huì)出現(xiàn)在P@n中隨著n的增大，P@n減小的趨勢(shì)。

5.2 實(shí)體擴(kuò)展實(shí)驗(yàn)分析

本節(jié)首先分析實(shí)體擴(kuò)展實(shí)驗(yàn)中參數(shù)的影響，然后將擴(kuò)展方法與基線在公共數(shù)據(jù)集INEX 上進(jìn)行對(duì)比，最后分析在數(shù)據(jù)結(jié)構(gòu)課程領(lǐng)域數(shù)據(jù)集上的擴(kuò)展結(jié)果。

5.2.1 數(shù)據(jù)集和評(píng)價(jià)指標(biāo)

公共數(shù)據(jù)集采用INEX-XER2009［25］（INEX），領(lǐng)域數(shù)據(jù)集采用本文構(gòu)建的數(shù)據(jù)結(jié)構(gòu)領(lǐng)域術(shù)語(yǔ)實(shí)體集。INEX 是一個(gè)包含60 個(gè)主題的數(shù)據(jù)集，其中每個(gè)主題包含一個(gè)問(wèn)題描述和若干個(gè)種子，按每個(gè)話題給出種子個(gè)數(shù)（seed=2、3、4、5），INEX 分為4 組數(shù)據(jù)。該數(shù)據(jù)集常被用來(lái)評(píng)估實(shí)體檢索相關(guān)任務(wù)，如實(shí)體排名、實(shí)體擴(kuò)展任務(wù)。數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)嶓w由5 名計(jì)算機(jī)專業(yè)研究生手動(dòng)標(biāo)注，取其公認(rèn)的領(lǐng)域?qū)嶓w作為數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)嶓w集。

評(píng)估測(cè)度采用召回率R、準(zhǔn)確率P、F1 值和前n個(gè)結(jié)果的準(zhǔn)確率P@n，本文取P@5、P@10和P@20。

5.2.2 松弛機(jī)制參數(shù)的影響

為研究松弛機(jī)制對(duì)擴(kuò)展實(shí)驗(yàn)的影響，在INEX 的4 組數(shù)據(jù)上評(píng)估松弛閾值θ的影響。松弛機(jī)制的目的是獲得較高的召回率，因此這里的評(píng)測(cè)指標(biāo)僅為R，結(jié)果如表3 所示。從表3 可以看出，隨著θ的減小，召回率R不斷增大。當(dāng)考慮種子數(shù)量seed 的影響時(shí)，在seed 取值為2、3、4 時(shí)，隨著種子個(gè)數(shù)的增加，召回率也在提升，這表明種子越多，實(shí)體擴(kuò)展方法的性能越好。當(dāng)seed 取值為5 時(shí)，召回率較小，這是因?yàn)榉N子越多，其共性會(huì)減弱，使得召回率較低。當(dāng)考慮松弛閾值θ的影響時(shí)，隨著θ的減小，召回率R不斷提高，當(dāng)θ取0.6 時(shí)，R值最大，但當(dāng)θ從0.7 減小到0.6 時(shí)，R的增幅較小，但每降低較小的閾值，得到的擴(kuò)展實(shí)體個(gè)數(shù)會(huì)增加很多，擴(kuò)展結(jié)果中有很多的非領(lǐng)域?qū)嶓w，使得實(shí)體篩選的時(shí)間較長(zhǎng)。因此，松弛閾值取0.7。

表3 松弛機(jī)制參數(shù)θ對(duì)R 的影響Table 3 Influence of relaxation mechanism parameters θ on R

5.2.3 實(shí)體擴(kuò)展與基線實(shí)驗(yàn)的對(duì)比

本文實(shí)驗(yàn)將與已有的7 個(gè)基線進(jìn)行比較，基線和基線間的實(shí)驗(yàn)結(jié)果來(lái)自文獻(xiàn)［18］?；€包括LDSD、BBR、ARM、QBEES、SEAL、ESER。其中，LDSD 是基于鏈接的實(shí)體擴(kuò)展方法，BBR、SEAL 為基于非結(jié)構(gòu)化文本的實(shí)體擴(kuò)展方法，ARM 為基于關(guān)聯(lián)規(guī)則挖掘的方法，以及基于種子共同特征的QBEES、ESER 實(shí)體擴(kuò)展方法。

在INEX 的4 組數(shù)據(jù)上評(píng)測(cè)P@5、P@10和P@20，將4 組結(jié)果的均值作為評(píng)測(cè)結(jié)果，如圖8 所示。

圖8 不同基線的對(duì)比結(jié)果Fig.8 Comparison results of different baselines

基于知識(shí)圖譜的擴(kuò)展方法LDSD 表現(xiàn)較差，這是因?yàn)槠淅玫氖俏谋久枋鲋谐霈F(xiàn)的帶有超鏈接的相關(guān)實(shí)體來(lái)評(píng)估實(shí)體間的相似性，沒(méi)有考慮種子的語(yǔ)義相關(guān)性?；谧匀徽Z(yǔ)言處理模型的實(shí)體擴(kuò)展方法表現(xiàn)優(yōu)于LDSD，但相較于本文基于語(yǔ)義結(jié)構(gòu)的方法擴(kuò)展效果相對(duì)較差，這也表明了基于自然語(yǔ)言處理模型從非結(jié)構(gòu)化文本中擴(kuò)展實(shí)體有一定的局限性。ARM 應(yīng)用關(guān)聯(lián)規(guī)則挖掘來(lái)發(fā)現(xiàn)頻繁模式，利用種子間的共性提高了召回率，但其排序模型不足以達(dá)到良好的準(zhǔn)確性。由于知識(shí)圖譜是不完整的，QBEES 應(yīng)用嚴(yán)格的模式檢索類似的實(shí)體會(huì)導(dǎo)致召回率較低。SEAL 從搜索引擎的強(qiáng)大功能中收益良多，使得檢索到的網(wǎng)頁(yè)與種子相關(guān)度較高，然而在某些情況下很難從非結(jié)構(gòu)化文本中發(fā)現(xiàn)和提取種子的共性。ESER 在結(jié)構(gòu)化知識(shí)圖譜中通過(guò)挖掘種子的公共語(yǔ)義路徑擴(kuò)展實(shí)體有著良好的表現(xiàn)，但隨著種子個(gè)數(shù)的增加，挖掘的路徑越多，導(dǎo)致擴(kuò)展的實(shí)體精度降低。本文方法在INEX 上綜合表現(xiàn)最好，因?yàn)樵跀U(kuò)展過(guò)程中僅利用了知識(shí)圖譜中的一跳路徑，即類與實(shí)例的關(guān)系，避免路徑過(guò)長(zhǎng)出現(xiàn)語(yǔ)義漂移，再利用擴(kuò)展實(shí)體與種子實(shí)體的字符串相似性和結(jié)構(gòu)距離相關(guān)性對(duì)擴(kuò)展實(shí)體排序，使得擴(kuò)展實(shí)驗(yàn)在擁有較高召回率的基礎(chǔ)上提高TopN的準(zhǔn)確率。

排序后的擴(kuò)展實(shí)體在相關(guān)度越高的部分領(lǐng)域?qū)嶓w越密集，隨著相關(guān)度的降低，領(lǐng)域?qū)嶓w越稀疏，所以P@n隨著n增大而減小。

5.2.4 領(lǐng)域數(shù)據(jù)集的實(shí)體擴(kuò)展實(shí)驗(yàn)結(jié)果

在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域數(shù)據(jù)集上按章節(jié)進(jìn)行實(shí)體擴(kuò)展，即以每章節(jié)的核心術(shù)語(yǔ)實(shí)體為種子在DBpedia中擴(kuò)展。在實(shí)驗(yàn)評(píng)價(jià)中隨機(jī)選取了3 個(gè)章節(jié)P、R和F1 值的平均值作為領(lǐng)域?qū)嶓w擴(kuò)展的評(píng)測(cè)結(jié)果。不同松弛機(jī)制閾值下的實(shí)體擴(kuò)展結(jié)果如表4 所示。

表4 數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)嶓w的擴(kuò)展結(jié)果Table 4 Extension results of data structure domain entity

從表4 可以看出，閾值越低召回的領(lǐng)域?qū)嶓w越多，因此將松弛機(jī)制閾值θ為0.7 時(shí)的擴(kuò)展實(shí)體進(jìn)行標(biāo)注獲得領(lǐng)域?qū)嶓w。隨著松弛閾值的減小，P值降低，R提高，這是因?yàn)殚撝翟叫?，擴(kuò)展得到的實(shí)體越多，使得R提高，同時(shí)也因?yàn)橐肓烁嗟姆穷I(lǐng)域?qū)嶓w使得P降低。從綜合評(píng)價(jià)指標(biāo)F1 可知，當(dāng)閾值θ取0.8 時(shí)，擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)嶓w效果最佳。

5.3 結(jié)果展示

從數(shù)據(jù)結(jié)構(gòu)課程文本中分別抽出各章節(jié)的核心實(shí)體，例如從講解Heap的章節(jié)中抽取出實(shí)體Binary heap、Heap（data structure）、Binomial heap，在DBpedia 中利用實(shí)體的subject 關(guān)系（Is subject of 的逆關(guān)系）選擇類Heaps，類通過(guò)Is subject of 獲得其實(shí)例，最后通過(guò)實(shí)體篩選過(guò)濾，得到擴(kuò)展實(shí)體Fibonacci heap、Breadth first traversal、Treap 等。通過(guò)挖掘課程領(lǐng)域核心實(shí)體和從DBpedia中擴(kuò)展實(shí)體共獲得數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)嶓w1 115個(gè)，結(jié)果如圖9 所示。

圖9 實(shí)體擴(kuò)展示例Fig.9 Entity expansion example

6 結(jié)束語(yǔ)

本文利用候選實(shí)體間結(jié)構(gòu)相關(guān)度構(gòu)建概念圖，通過(guò)基于置信度傳播的圖排序算法抽取核心實(shí)體，在DBpedia 中計(jì)算關(guān)系路徑的最大信息增益選擇實(shí)體的共性類，并將共性類下的實(shí)例作為擴(kuò)展實(shí)體，最后通過(guò)基于字符串相似和結(jié)構(gòu)相關(guān)度的排序方法對(duì)擴(kuò)展概念進(jìn)行過(guò)濾。實(shí)驗(yàn)結(jié)果表明，實(shí)體抽取方法在CSEN 數(shù)據(jù)集上僅次于CCP 方法，在EcoEN 數(shù)據(jù)集上達(dá)到最優(yōu)，實(shí)體擴(kuò)展方法在INEX 數(shù)據(jù)集上的P@n均優(yōu)于基線實(shí)驗(yàn)。本文對(duì)領(lǐng)域?qū)嶓w相關(guān)度的計(jì)算以及擴(kuò)展實(shí)體的篩選排序過(guò)程均未考慮語(yǔ)義上的相似度，這可能影響實(shí)體挖掘方法的魯棒性，下一步通過(guò)將文本嵌入計(jì)算實(shí)體向量的語(yǔ)義相似度，從而使實(shí)體間相似性的計(jì)算更加可靠全面，并利用實(shí)體間關(guān)系信息挖掘領(lǐng)域?qū)嶓w，根據(jù)圖像等多模態(tài)信息進(jìn)行實(shí)體挖掘。