一種基于短文本相似度計(jì)算的知識(shí)子圖融合方法

鄭志蘊(yùn)，吳建萍，李 鈍，劉 允，米高揚(yáng)

(鄭州大學(xué) 信息工程學(xué)院，鄭州 450001)

1 引 言

知識(shí)圖譜實(shí)質(zhì)上是一個(gè)語義網(wǎng)，清晰明確的表達(dá)了物理世界中的實(shí)體及其相互關(guān)系.目前，已經(jīng)涌現(xiàn)出一大批知識(shí)圖譜的相關(guān)產(chǎn)品，其中具有代表性的國外產(chǎn)品有谷歌公司使用的Knowledge Vault、蘋果公司使用的Wolfram Alpha、智能計(jì)算引擎及Freebase等；具有代表性的國內(nèi)產(chǎn)品有百度“知心”和搜狗“知立方”等.這些已有的知識(shí)圖譜研究目標(biāo)是從無/半結(jié)構(gòu)的互聯(lián)網(wǎng)信息中獲取有結(jié)構(gòu)知識(shí)、自動(dòng)融合構(gòu)建知識(shí)庫、服務(wù)知識(shí)推理等.其中，知識(shí)融合是知識(shí)圖譜構(gòu)建的重要步驟.

知識(shí)融合在實(shí)際應(yīng)用中主要以圖融合的形式存在.圖融合可以被認(rèn)為是基于知識(shí)相似度的計(jì)算任務(wù)，通過歐式距離或余弦距離等方式計(jì)算任意兩個(gè)對(duì)象之間的相似度.在已有的工作中，多是關(guān)注知識(shí)圖譜中的拓?fù)浣Y(jié)構(gòu)而忽略了實(shí)體名稱字面含義中所攜帶的語義信息，如圖1所示.因此在圖融合過程中，不僅需要考慮圖的結(jié)構(gòu)信息，而且需要引入語義信息.

從圖1可以看出，忽略字面含義的知識(shí)圖譜表示學(xué)習(xí)并不能直接預(yù)測(cè)Tom和Jane之間的關(guān)系，但是，在考慮到他們相近的出生日期以及校友關(guān)系等因素之后，Tom和Jane之間是存在潛在關(guān)系的.

圖1 攜帶語義信息的關(guān)聯(lián)圖Fig.1 Association graph carrying semantic information

為了改善學(xué)習(xí)，知識(shí)圖譜逐漸被引入教育領(lǐng)域.在構(gòu)建教育知識(shí)圖譜的過程中，將概念信息引入知識(shí)表示，并得到融合后的知識(shí)子圖，是一個(gè)復(fù)雜的過程.由于實(shí)體所攜帶的語義信息具有內(nèi)容簡(jiǎn)短等特點(diǎn)，本文提出了一種基于短文本相似度計(jì)算的知識(shí)子圖融合方法，用以解決知識(shí)子圖融合中的問題.

在本文中，首先利用基于眾包的知識(shí)子圖獲取方法，采用頂點(diǎn)權(quán)重和頂點(diǎn)關(guān)聯(lián)權(quán)重占比策略對(duì)知識(shí)子圖進(jìn)行約簡(jiǎn)，其次通過統(tǒng)計(jì)詞頻對(duì)頂點(diǎn)進(jìn)行二次約簡(jiǎn)，并采用圖集合距離對(duì)短文本進(jìn)行相似度計(jì)算；最后通過一種基于向量運(yùn)算的雙鄰接矩陣融合方法，得到最終的高質(zhì)量知識(shí)圖.通過實(shí)驗(yàn)驗(yàn)證本文方法具有可行性，而且得到了較好的融合結(jié)果.

2 相關(guān)工作

2.1 知識(shí)表示

現(xiàn)有的知識(shí)表示方法多是關(guān)注知識(shí)圖譜中的拓?fù)浣Y(jié)構(gòu)而忽略了實(shí)體名稱字面含義中所攜帶的語義信息.Chen等人[1]學(xué)習(xí)低維度網(wǎng)絡(luò)中結(jié)點(diǎn)的潛在表示，得到的低維度向量可以用來結(jié)點(diǎn)分類，對(duì)結(jié)點(diǎn)與結(jié)點(diǎn)之間的關(guān)系進(jìn)行預(yù)測(cè).Sami等人[2]提出了一種新方法，將邊緣信息作為結(jié)點(diǎn)嵌入的函數(shù)，同時(shí)結(jié)合隨機(jī)游走的信息，產(chǎn)生了高精度的圖形結(jié)構(gòu).Rossi等人[3]提出了一種通用的歸納圖表示學(xué)習(xí)框架DeepGL，用于學(xué)習(xí)跨網(wǎng)絡(luò)概括的深度結(jié)點(diǎn)和邊緣特征.方陽等人[4]針對(duì)知識(shí)圖譜能夠符號(hào)化并具備有邏輯性的特點(diǎn)，提出一種改進(jìn)的基于翻譯的知識(shí)圖譜表示方法TransAH.

2.2 相似度計(jì)算

傳統(tǒng)的文本相似度計(jì)算方法通過統(tǒng)計(jì)文本間共有的詞語信息得到文本間的相似度，本文采用五元組來表示知識(shí)圖譜中的結(jié)點(diǎn)，其中結(jié)點(diǎn)攜帶概念信息，由于結(jié)點(diǎn)攜帶的短文本信息只包含很少數(shù)量的詞語，短文本內(nèi)容簡(jiǎn)短的特性會(huì)導(dǎo)致數(shù)據(jù)稀疏而造成計(jì)算結(jié)果出現(xiàn)偏差，因此本文提出了一種基于短文本的相似度計(jì)算方法.目前圖相似性的研究工作主要集中于子圖的匹配，而沒有充分考慮圖集合之間的匹配，由于本文采用眾包的方式獲取數(shù)據(jù)，數(shù)據(jù)量大且冗余過多，因此本文提出了一種基于圖集合距離的方法，通過結(jié)合圖集合距離方法和短文本相似度計(jì)算方法，可以獲得相似度較高且子圖質(zhì)量較高的圖集.

目前TF-IDF[5](Term Frequency-Inverse Document Frequency,TF-IDF)是一個(gè)用于度量文本相似性的常用表示方法，它依賴于詞的重疊，來找到相似之處，但在很短的文本上，詞重疊很罕見.Miller等人[6]對(duì)語義相似度從高到低的成對(duì)名詞進(jìn)行研究，探討了語義相似度與語境相似度的關(guān)系.Liang等人[7]提出了基于支配集的子圖匹配算法，采用兩階段剪枝策略，加快了集合相似度子圖匹配的圖查詢.Li等人[8]針對(duì)大多數(shù)現(xiàn)有的工作都是以“全局”的方式實(shí)現(xiàn)融合權(quán)重，提出了一種新的基于“局部”學(xué)習(xí)的屬性圖聚類加權(quán)的k均值算法，稱為結(jié)構(gòu)與屬性信息的自適應(yīng)融合Adapt-SA(Adaptive Fusion of Structual and Attribute Information,Adapt-SA).Zeng等人[9]建立了一個(gè)星形模型，采用多項(xiàng)式時(shí)間來計(jì)算上下界，在考慮圖的數(shù)量和大小的情況下，實(shí)現(xiàn)了圖搜索問題.龐俊等人[10]針對(duì)目前圖相似性的研究工作主要集中在子圖的匹配上，而沒有充分關(guān)注圖集合之間的匹配，提出了一種基于過濾-求精框架的GSSS算法.詹志建等人[11]通過對(duì)短文本建立復(fù)雜網(wǎng)絡(luò)模型，計(jì)算出短文本詞語的復(fù)雜網(wǎng)絡(luò)特征值再借助外部工具計(jì)算得出短文本詞語之間的語義相似度.宋冬云等人為提高中文短文本相似度計(jì)算的準(zhǔn)確率，提出一種新的基于混合策略的中文短文本相似度計(jì)算方法.張培穎等人[12]將義原樹之間的最短路徑作為衡量?jī)蓚€(gè)義原之間的語義距離的依據(jù)，然后把義原距離轉(zhuǎn)換為義原相似度，提出了一種多特征結(jié)合的詞語相似度計(jì)算方法，實(shí)驗(yàn)驗(yàn)證了算法的有效性.

2.3 知識(shí)圖融合

在知識(shí)融合過程中，由于知識(shí)來源廣泛，質(zhì)量難以判定，其中可能包含大量的模糊、歧義、冗余甚至錯(cuò)誤信息，而對(duì)于帶有標(biāo)簽的圖更是包含了結(jié)構(gòu)信息和語義信息，這兩種不同類型的異構(gòu)信息加大了融合的難度.Wang等人[13]提出了一種用于卡消歧的新概率評(píng)分算法，以選擇卡來參考最可能的實(shí)體，設(shè)計(jì)一種基于學(xué)習(xí)的方法來對(duì)齊代表同一實(shí)體卡片的屬性.Cheng等人[14]基于知識(shí)圖的廣泛應(yīng)用和教育領(lǐng)域日益增長(zhǎng)的需求，提出了一種基于知識(shí)圖的教育知識(shí)圖譜自動(dòng)構(gòu)建系統(tǒng).Sun等人[15]研究了一種更實(shí)用的設(shè)置，即對(duì)知識(shí)庫和實(shí)體鏈接文本的組合進(jìn)行QA.Nie等人[16]通過醫(yī)師專業(yè)知識(shí)分布和專業(yè)知識(shí)問題分布的概率融合來彌合專業(yè)知識(shí)匹配差距.郭芳等人[17]采用眾包技術(shù)進(jìn)行知識(shí)資源的獲取，并提出了基于矩陣運(yùn)算的知識(shí)子圖融合方法.吳笑凡等人[18]提出了基于分布式主題圖融合的TOM(Topic & Occurrence-Oriented Merging,TOM)算法，通過判斷不同主題圖中的主題是否指示同一項(xiàng)目，檢查它們所表示內(nèi)容的相似性程度以實(shí)現(xiàn)融合.

3 相關(guān)定義

定義1.(傳統(tǒng)子圖集).知識(shí)子圖集G={G1,…,Gi,…},Gi=(VG,EG,WV,WE).其中VG為知識(shí)圖譜的頂點(diǎn)集合，每個(gè)結(jié)點(diǎn)v∈VG；EG?VG×VG表示知識(shí)圖譜的邊集合，每條邊e∈EG用無向的直線表示；WV是頂點(diǎn)權(quán)重集；WE是邊權(quán)重集.

定義2.(二分圖).在知識(shí)子圖Gi中，如果頂點(diǎn)V可分割為兩個(gè)互不相交的子集V1和V2，并且Gi中每條邊e所關(guān)聯(lián)的頂點(diǎn)v1，v2分別屬于這兩個(gè)不同的頂點(diǎn)集，則稱為二分圖.

定義3.(二分圖最小完美匹配).在二分圖Gi中，每條邊e互不相交且滿足e的權(quán)重最小，若覆蓋了二分圖的所有頂點(diǎn)，則為二分圖的最小完美匹配.

定義4.(圖集合對(duì)最小二分圖匹配).已知兩個(gè)圖集合S(ui)和S(vj)可以構(gòu)成二分圖，S(ui)表示包含圖ui的集合，S(vj)表示包含圖vj的集合，S(ui)和S(vj)分別對(duì)應(yīng)二分圖中的V1、V2集合，S(ui)或S(vj)中的每一個(gè)圖對(duì)應(yīng)V1或V2中的一個(gè)頂點(diǎn)，若兩集合中的基數(shù)不相等，則在基數(shù)較小的圖集合中補(bǔ)充虛擬圖，使得圖集合對(duì)等.

定義5.(圖集合距離).由圖集合S(ui)和S(vj)得到的最小二分圖匹配數(shù)，則為圖集合距離d.

定義6.(標(biāo)簽子圖集).在傳統(tǒng)子圖集中引入標(biāo)簽數(shù)據(jù)集L={l1,l2,…}，L中主要描述的是知識(shí)圖譜Gk中集合VG的頂點(diǎn)對(duì)應(yīng)的標(biāo)簽概念信息，數(shù)據(jù)中的一條記錄Li可以表示為{Vi,Ti},其中Vi表示知識(shí)點(diǎn)，Ti={t1,t2,…}表示vi對(duì)應(yīng)的標(biāo)簽集，此時(shí)G={G1,…,Gi,…},Gi=(VG,EG,WV,WE,L).

4 一種基于圖集合距離的短文本相似度計(jì)算方法

本節(jié)將以計(jì)算機(jī)學(xué)科的子圖獲取為例，結(jié)合眾包思想，獲取個(gè)體知識(shí)子圖，在獲取子圖之后，主要通過子圖降噪和相似度計(jì)算，對(duì)知識(shí)子圖進(jìn)行預(yù)處理并融合.首先，根據(jù)子圖的頂點(diǎn)權(quán)重值和頂點(diǎn)關(guān)聯(lián)權(quán)重值，采用基于加權(quán)策略的子圖降噪算法對(duì)其進(jìn)行約簡(jiǎn)處理；其次，對(duì)具有相同頂點(diǎn)數(shù)的子圖進(jìn)行同等劃分，得到若干圖集合，并對(duì)其進(jìn)行圖集合相似度計(jì)算，將獲取的候選結(jié)果集進(jìn)行求精；最后，通過對(duì)集合內(nèi)各個(gè)子圖的頂點(diǎn)所攜帶的標(biāo)簽含義進(jìn)行短文本相似度計(jì)算，得到最終有效的圖集.

4.1 基于眾包的知識(shí)子圖獲取方法

本節(jié)結(jié)合眾包思想，首先學(xué)習(xí)者根據(jù)已學(xué)過的課程并加入自己的理解構(gòu)建屬于自己認(rèn)知范圍內(nèi)的個(gè)體知識(shí)子圖；其次學(xué)習(xí)者還可對(duì)關(guān)鍵知識(shí)點(diǎn)進(jìn)行更新，迭代知識(shí)聯(lián)想過程，如果發(fā)現(xiàn)有新的關(guān)系無法用已有的關(guān)系表達(dá)時(shí)，便說明這是一個(gè)新的關(guān)系需要補(bǔ)充，如果發(fā)現(xiàn)有新的概念無法利用已有的概念替代時(shí)，便說明這是一個(gè)新的知識(shí)需要補(bǔ)充.最后根據(jù)知識(shí)子圖對(duì)關(guān)鍵知識(shí)點(diǎn)進(jìn)行更新，迭代知識(shí)聯(lián)想過程，獲得個(gè)體知識(shí)子圖集G={G1,G2,…,Gi,…}.

4.2 子圖降噪

通過眾多學(xué)習(xí)者得到的數(shù)據(jù)普遍具有冗余性，本節(jié)將對(duì)第4.1節(jié)獲取的子圖集進(jìn)行降噪處理，采用頂點(diǎn)權(quán)重和頂點(diǎn)關(guān)聯(lián)權(quán)重占比策略對(duì)子圖進(jìn)行約簡(jiǎn)，再通過統(tǒng)計(jì)詞頻對(duì)頂點(diǎn)進(jìn)行二次約簡(jiǎn).

1)子圖約簡(jiǎn)

首先學(xué)習(xí)者k根據(jù)子圖Gk的頂點(diǎn)集及頂點(diǎn)關(guān)聯(lián)集的大小，得到頂點(diǎn)個(gè)數(shù)|VG|和邊個(gè)數(shù)|EG|；然后通過公式(1)和公式(3)計(jì)算，得到Gk的頂點(diǎn)權(quán)重WV(Gk,Vi)和邊權(quán)重WE(Gk,Vi,Vj)；最后依據(jù)權(quán)重比，篩選出具有重要知識(shí)點(diǎn)與知識(shí)關(guān)聯(lián)的子圖集.頂點(diǎn)權(quán)重計(jì)算如公式(1)所示.

(1)

其中，Gk表示學(xué)習(xí)者k構(gòu)建的子圖，W(Gk,Vi)表示Gk的頂點(diǎn)權(quán)重之和，若權(quán)重和越大，則說明圖中包含的重要知識(shí)點(diǎn)越多，該學(xué)習(xí)者構(gòu)建的知識(shí)子圖整體質(zhì)量越高.vi表示第i個(gè)頂點(diǎn)，|WVi|表示第i個(gè)頂點(diǎn)的權(quán)重，n表示Gk的頂點(diǎn)個(gè)數(shù)，即|VG|.

本節(jié)將邊權(quán)重計(jì)算分為兩步，先對(duì)邊權(quán)重進(jìn)行初始化，如公式(2)所示；再根據(jù)學(xué)習(xí)者k構(gòu)建子圖的關(guān)聯(lián)權(quán)重對(duì)邊權(quán)重進(jìn)行更新，如公式(3)所示.

(2)

其中，WE(Gk,Vi,Vj)表示vi與vj是否存在相連的邊，若子圖Gk中vi與vj有邊相連，則WE(Gk,Vi,Vj)值置為1；否則，置為0.

(3)

其中，WE(Vi,Vj)表示邊(vi,vj)的權(quán)重，n表示Gk的頂點(diǎn)個(gè)數(shù).

通過得到的頂點(diǎn)權(quán)重值與邊權(quán)重值，采用基于加權(quán)策略的子圖降噪算法(Subgraph Denoising Algorithm Based on Weighting Strategy,SDWS)對(duì)子圖集G進(jìn)行降噪處理，如算法1所示.

算法1.基于加權(quán)策略的子圖降噪算法(SDWS)

輸入：子圖集G

輸出：子圖集G*

1.給定初始值p←m,i←1,j←1,λ∈(0,1) ;

2.while(p≥1)

3.while(i≤n&&j≤n)

4. 通過式(1)計(jì)算頂點(diǎn)權(quán)重WV(Gk,Vi)；

5. 通過式(3)計(jì)算邊權(quán)重WE(Gk,Vi,Vj)；

7.a[n]=k;

8.G*←G-Gk;

9.endif

10.i++；

11.endwhile;

12.p--;

13. go to step 2;

14.endwhile;

15. 輸出G*；

16.end;

在算法1中，結(jié)合頂點(diǎn)權(quán)重和邊權(quán)重，剔除質(zhì)量較差的子圖.在1中，p表示圖的個(gè)數(shù)，i，j均表示圖的頂點(diǎn)個(gè)數(shù)且i≠j，設(shè)置閾值λ來判斷圖中含有的重要知識(shí)點(diǎn)和知識(shí)關(guān)聯(lián)的比重；在3中，n表示當(dāng)前圖的頂點(diǎn)個(gè)數(shù)；在4、5 中，Gk表示學(xué)習(xí)者k構(gòu)建的子圖；在7中表示將構(gòu)建質(zhì)量差的子圖所屬的學(xué)習(xí)者記錄在數(shù)組a中，并給出一定的評(píng)分；在8中表示將無用子圖剔除.重復(fù)上述過程，得到高質(zhì)量的知識(shí)子圖集G*.

2)頂點(diǎn)約簡(jiǎn)

首先對(duì)每個(gè)知識(shí)點(diǎn)的出現(xiàn)頻率進(jìn)行統(tǒng)計(jì)，將詞頻小于閾值γ的知識(shí)點(diǎn)過濾以后，得到集合V′.然后對(duì)V′進(jìn)行人工篩查，剔除其中的噪聲詞.為了降低人工篩查的難度和工作量，將V′與現(xiàn)有大規(guī)模詞庫比對(duì)，取二者交集V″之后再進(jìn)行人工篩查.因?yàn)榇笠?guī)模詞庫通常都是行業(yè)公用的詞典，詞匯量大且較為全面，可信度高，因此先將V′與大規(guī)模詞庫取交集，可以大大縮小V′的規(guī)模，有效減少人工篩查的工作量.經(jīng)過上述一系列的預(yù)處理過程后，得到有效知識(shí)點(diǎn)集合V′={v1,v2,…,vn}.

4.3 基于圖集合距離的短文本相似度計(jì)算方法

在知識(shí)子圖集中，結(jié)構(gòu)相似的圖所對(duì)應(yīng)的頂點(diǎn)和邊具有相似的表達(dá)含義，目前大部分學(xué)者忽略了頂點(diǎn)所攜帶的結(jié)構(gòu)信息和語義信息.本節(jié)提出了基于圖集合距離的短文本相似度計(jì)算方法，首先，根據(jù)圖集合距離，構(gòu)建完全二分圖，用圖集合相似度搜索策略獲取較小的候選結(jié)果集；其次，通過對(duì)子圖頂點(diǎn)所攜帶的語義信息進(jìn)行預(yù)處理，計(jì)算出各個(gè)詞語結(jié)點(diǎn)的綜合特征值，得到短文本相似度；最后，對(duì)兩種相似度進(jìn)行加權(quán)，得到最終的相似度.

結(jié)合SDWS算法中得到的子圖集G*，并對(duì)其進(jìn)行劃分，將具有相同頂點(diǎn)數(shù)的子圖劃分到同一個(gè)集合中，得到若干子圖集S={S1,S2,…,Sm}(其中m為集合個(gè)數(shù))；其次，通過擴(kuò)展的KM算法求解S中集合對(duì)間的最大完美匹配，若匹配數(shù)小于等于t，則兩個(gè)集合相似[10]，此時(shí)知識(shí)子圖集G**={s|d(s,si)≤t,s∈S,i∈(1,m)}，其中，t表示距離閾值，si表示第i個(gè)圖集合，d(s,si)≤t表示從集合S中的所有圖集合里，找出與si集合間的距離小于等于t的集合，并將集合對(duì)相似的集合存到G**中.

由于得到的圖集G**中的每個(gè)圖的頂點(diǎn)均攜帶語義信息，只要文本相似，那么文本中的詞語在一定程度上也是相似的，而文中的標(biāo)簽信息具有內(nèi)容簡(jiǎn)短、數(shù)據(jù)稀疏等特點(diǎn)，采用傳統(tǒng)的文本相似度計(jì)算方法可能會(huì)引起計(jì)算結(jié)果出現(xiàn)偏差.本文借助現(xiàn)有的工具對(duì)中文短文本進(jìn)行預(yù)處理，對(duì)其進(jìn)行分詞、詞性標(biāo)注、停用詞過濾等操作.然后，根據(jù)短文本建立復(fù)雜網(wǎng)絡(luò)模型，計(jì)算短文本詞語的復(fù)雜網(wǎng)絡(luò)特征值，再借助外部工具計(jì)算短文本詞語之間的語義相似度[11]SimST(Gk l1,Gkl2)，其中Gkl1表示Gk中頂點(diǎn)V1所攜帶的文本信息，Gkl2表示Gk中頂點(diǎn)V2所攜帶的文本信息.若得到的相似度大于μ，其中μ表示詞語相似度閥值，則視為文本相似，否則視為不相似，得到最終的結(jié)果集G***.

5 基于向量運(yùn)算的雙鄰接矩陣融合方法

知識(shí)子圖融合是指將若干學(xué)習(xí)者自主構(gòu)建的缺少完整性和缺乏準(zhǔn)確度的知識(shí)子圖經(jīng)過有效的處理，生成較為完整和標(biāo)準(zhǔn)的群體知識(shí)圖譜的過程.標(biāo)簽圖與傳統(tǒng)圖有一定的不同，前者包含了兩種不同類型的異構(gòu)信息，即結(jié)構(gòu)信息和語義信息.結(jié)構(gòu)信息表示結(jié)點(diǎn)間的聯(lián)系，語義信息表示每個(gè)結(jié)點(diǎn)上攜帶的標(biāo)簽信息.本節(jié)提出了基于向量運(yùn)算的雙鄰接矩陣融合方法，用來平衡各結(jié)點(diǎn)的結(jié)構(gòu)連接和標(biāo)簽信息，得到具有高屬性語義相似性的最終知識(shí)子圖.融合過程可以分為5個(gè)步驟：

1)根據(jù)公式(3)計(jì)算得到的知識(shí)關(guān)聯(lián)權(quán)重WE(Gk,Vi,Vj)，將知識(shí)子圖轉(zhuǎn)換為知識(shí)子圖關(guān)聯(lián)權(quán)重矩陣En×n=(E1,E2,…,En)，如公式(4)所示.

(4)

其中，WE表示Gk中Vi和Vj間的關(guān)聯(lián)權(quán)重，Ek[i][j]表示若Gk中知識(shí)點(diǎn)有邊相連，則矩陣值為邊的權(quán)重WE；否則，矩陣值為0.

2)根據(jù)用鄰接矩陣A=(A1,A2,…An)表示頂點(diǎn)語義信息，如公式(5)所示.

Ak[i][1]=Ti，Vi∈Gk

(5)

其中，Ti表示Gk中第i個(gè)頂點(diǎn)Vi所攜帶的標(biāo)簽信息，即語義信息，Ak[i][1]表示用n×1的矩陣將知識(shí)子圖的語義信息進(jìn)行存儲(chǔ).

3)由于結(jié)點(diǎn)的標(biāo)簽都是短文本，因此本節(jié)采用第4.3節(jié)計(jì)算得到的短文本相似函數(shù)SimST(Gk l1,Gkl2)，將知識(shí)語義信息矩陣轉(zhuǎn)換為知識(shí)語義信息相似度矩陣，如公式(6)所示.

(6)

4)對(duì)圖G***中每個(gè)圖都做上述處理之后，將每個(gè)結(jié)點(diǎn)vi∈vG的這兩個(gè)信息組合起來，得到一個(gè)聯(lián)合表示.通過設(shè)置一組權(quán)重向量α=(α1，α2，…,αn)T,αi∈[0,1]，得到融合后的矩陣，如公式(7)所示.

EAk=Ekαi+Ak(1-αi)

(7)

通過將子圖轉(zhuǎn)換為二維矩陣，采用基于向量運(yùn)算的雙鄰接矩陣融合方法(Double Adjacency Matrix Fusion Algorithm,DAMF)對(duì)子圖集G***進(jìn)行融合處理，如算法2所示.

算法2.基于向量運(yùn)算的雙鄰接矩陣融合方法(DAMF)

輸入：子圖集G***

輸出：融合矩陣EAk

1.給定初始值En×n，An×1，m,i,j，k;

2.while(k≥1)

3.for(i←0；i≤m；i++)

4.for(j←i+1；j≤m；j++)

5. 通過公式(3)計(jì)算得到知識(shí)關(guān)聯(lián)WE(Gk,Vi,Vj)的值；

6. 通過公式(4)將Gk轉(zhuǎn)換為知識(shí)關(guān)聯(lián)權(quán)重矩陣Ek[i][j]；

7. 通過公式(5)將Gk轉(zhuǎn)換為知識(shí)語義信息矩陣Ak[i][1]；

8.endfor;

9.endfor;

10.if(k≥2)

11. 根據(jù)第4.3節(jié)計(jì)算得到短文本相似度函數(shù) SimST(Gk-1 l 1,Gkl2)；

12. 通過公式(6)將Ak[i][1]轉(zhuǎn)換為Ak[i][j]；

13. 設(shè)置一組權(quán)重向量α=(α1,α2，…,αn)T；

14. 通過公式(7)計(jì)算出融合矩陣EAk;

15.endif;

16. k--;

17.endwhile;

在算法2中，結(jié)合向量運(yùn)算，用鄰接矩陣的形式存儲(chǔ)子圖，對(duì)子圖進(jìn)行融合.在1中，En×n表示n行n列的矩陣，An×1表示n行1列的矩陣，m表示Gk中頂點(diǎn)的個(gè)數(shù)，i，j均表示頂點(diǎn)的初始值,k表示子圖的個(gè)數(shù).重復(fù)上述過程，得融合后的矩陣.

綜上，通過子圖降噪與基于圖集合的短文本相似度計(jì)算加快了融合的過程,并且使用結(jié)點(diǎn)縮略圖大大減少了再次查詢的時(shí)間代價(jià).由于在構(gòu)建知識(shí)圖譜過程中需要專家的協(xié)助，特別是針對(duì)特定領(lǐng)域的知識(shí)圖譜更需要專家提供的專業(yè)知識(shí).因此，在課程數(shù)據(jù)采集原型平臺(tái)中，教師可以對(duì)融合后的課程知識(shí)圖譜進(jìn)行完善修正，得到最終完整的知識(shí)子圖.

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

6.1 數(shù)據(jù)采集

為了獲取真實(shí)的數(shù)據(jù)集，本文構(gòu)建了一個(gè)計(jì)算機(jī)學(xué)科內(nèi)的課程數(shù)據(jù)采集原型系統(tǒng)，采用眾包的方式，組織30位學(xué)生對(duì)已學(xué)過的某門課程根據(jù)自己的理解構(gòu)建個(gè)體知識(shí)子圖.在構(gòu)建的過程中，表1介紹了部分知識(shí)點(diǎn)數(shù)據(jù)采集，表2介紹了部分知識(shí)關(guān)聯(lián)數(shù)據(jù)采集，圖2介紹了課程知識(shí)圖譜數(shù)據(jù)采集界面.在真實(shí)環(huán)境的背景下，共得到2036個(gè)知識(shí)點(diǎn)和3814條知識(shí)關(guān)聯(lián)，來驗(yàn)證子圖融合的效果.

表1 知識(shí)點(diǎn)部分采集示例Table 1 Knowledge point part collection example

表1介紹了以數(shù)據(jù)結(jié)構(gòu)為中心知識(shí)點(diǎn)向四周輻射的所有知識(shí)點(diǎn)，其中包含了學(xué)習(xí)者Gk、課程號(hào)、知識(shí)點(diǎn)名稱、知識(shí)點(diǎn)權(quán)重、知識(shí)點(diǎn)描述等.在對(duì)知識(shí)點(diǎn)進(jìn)行擴(kuò)展的過程中，對(duì)數(shù)據(jù)結(jié)構(gòu)中心知識(shí)點(diǎn)進(jìn)行描述，使得學(xué)習(xí)者能夠?qū)W習(xí)整個(gè)以數(shù)據(jù)結(jié)構(gòu)為中心知識(shí)點(diǎn)的知識(shí)圖譜.

表2 知識(shí)關(guān)聯(lián)部分采集示例Table 2 Link acquisition part collection example

表2介紹了以數(shù)據(jù)結(jié)構(gòu)為中心知識(shí)點(diǎn)向四周輻射的所有知識(shí)關(guān)聯(lián)，其中包含了學(xué)習(xí)者Gk、課程號(hào)、知識(shí)點(diǎn)A、知識(shí)點(diǎn)B、知識(shí)關(guān)聯(lián)權(quán)重等.知識(shí)關(guān)聯(lián)主要介紹了課程內(nèi)知識(shí)間的緊密程度，使得學(xué)習(xí)者能夠理清課程脈絡(luò)，搭建屬于自己的知識(shí)框架，構(gòu)建完整的課程知識(shí)圖譜.

圖2 課程知識(shí)圖譜采集界面Fig.2 Course knowledge graph collection interface

圖2介紹了整個(gè)課程知識(shí)圖譜的數(shù)據(jù)采集過程，對(duì)每個(gè)知識(shí)點(diǎn)都有相應(yīng)的概述和權(quán)重，權(quán)重表示了知識(shí)點(diǎn)的重要程度，在課程知識(shí)圖譜采集界面內(nèi)包含數(shù)據(jù)結(jié)構(gòu)在內(nèi)的多種課程，如軟件工程、編譯原理等，能夠?yàn)閷W(xué)習(xí)者提供詳細(xì)的多課程知識(shí)點(diǎn)表示，為學(xué)科知識(shí)圖譜的構(gòu)建打下基礎(chǔ).

6.2 實(shí)驗(yàn)對(duì)比

本節(jié)對(duì)課程知識(shí)采集得到的個(gè)體知識(shí)子圖進(jìn)行子圖約簡(jiǎn).子圖約簡(jiǎn)是對(duì)原始知識(shí)圖譜進(jìn)行處理，在保持原始知識(shí)圖譜所表示的知識(shí)體系不變的情況下，去除冗余的知識(shí)子圖.本節(jié)采用SDWS算法對(duì)獲得的子圖進(jìn)行約簡(jiǎn)，將不同知識(shí)點(diǎn)權(quán)重比和知識(shí)關(guān)聯(lián)權(quán)重比進(jìn)行實(shí)驗(yàn)，確定最優(yōu)的閾值，如圖3所示.

從圖3可以得出，閾值λ(包含知識(shí)點(diǎn)權(quán)重比和知識(shí)關(guān)聯(lián)權(quán)重比)的選取對(duì)約簡(jiǎn)圖數(shù)量是整體負(fù)相關(guān)的，即隨著約簡(jiǎn)圖數(shù)量的變小，知識(shí)點(diǎn)權(quán)重比和知識(shí)關(guān)聯(lián)權(quán)重比的計(jì)算數(shù)值逐漸變大.在知識(shí)圖約簡(jiǎn)到達(dá)200時(shí)，知識(shí)點(diǎn)權(quán)重比和知識(shí)關(guān)聯(lián)權(quán)重比已經(jīng)趨于不變，此時(shí)計(jì)算得出知識(shí)點(diǎn)權(quán)重比的值在[0.52，0.55]之間，知識(shí)關(guān)聯(lián)權(quán)重比的值在[0.51，0.56]之間，最終取閾值λ=0.54即為對(duì)原始知識(shí)圖數(shù)據(jù)的最大約簡(jiǎn)效果.在約簡(jiǎn)的過程中，將知識(shí)點(diǎn)權(quán)重占比或知識(shí)關(guān)聯(lián)權(quán)重占比小于0.54的子圖刪除，去除無效的知識(shí)子圖.然后對(duì)剩余的知識(shí)子圖進(jìn)行相似度計(jì)算，得到高密度的知識(shí)子圖集.

圖3 閾值選取Fig.3 Threshold selection

本文提出基于圖集合距離的短文本相似度計(jì)算方法，既考慮圖集合之間的結(jié)構(gòu)信息，又考慮了結(jié)點(diǎn)所攜帶的文本概念信息.傳統(tǒng)的TF-IDF方法可以應(yīng)用在短文本相似度計(jì)算中，但實(shí)驗(yàn)表明其F度量值較低，這是因?yàn)門F-IDF方法只考慮詞語的TF-IDF值而未考慮詞語的上下文信息.最長(zhǎng)公共子序列(Longest Common Subsequence，LCS)[19]方法主要用于計(jì)算兩個(gè)字符串的最大公共子序列的長(zhǎng)度，但公共子序列不一定連續(xù)，它要求出現(xiàn)的次序相同.傳統(tǒng)的向量空間模型(Vector Space Model，VSM)[20]主要計(jì)算文檔相似度，未考慮到詞語語義距離.編輯距離算法(Levenshtein Distance，LD)，主要用于兩個(gè)字符串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)，但未考慮語義間相關(guān)關(guān)系.基于圖集合距離的相似度計(jì)算方法，能夠進(jìn)一步對(duì)知識(shí)子圖進(jìn)行約簡(jiǎn)，并且能夠計(jì)算圖之間的相似度關(guān)聯(lián)函數(shù)值，其與TF-IDF、LCS、VSM、LD方法的對(duì)比實(shí)驗(yàn)結(jié)果如圖4所示.

圖4 不同短文本相似度計(jì)算方法對(duì)比Fig.4 Comparison of different short text similarity calculation methods

在圖4中，通過查全率(Recall)、查準(zhǔn)率(Precision)、F度量(F1)三個(gè)指標(biāo)進(jìn)行評(píng)價(jià)，本文提出的基于圖集合距離的相似度計(jì)算方法在查全率和F1值上均優(yōu)于其它方法，在查準(zhǔn)率上略低于TF-IDF方法，主要原因是TF-IDF方法考察了所選特征出現(xiàn)的頻率.

通過圖集合距離和短文本相似度計(jì)算方法相結(jié)合，得到了圖間的相似度函數(shù)，同時(shí)獲得了相似度高的知識(shí)子圖集.在此基礎(chǔ)上，將獲得高質(zhì)量高密度的知識(shí)子圖轉(zhuǎn)換為雙鄰接矩陣，得到融合后的知識(shí)子圖.本文提出VDMF算法，同時(shí)均衡了知識(shí)子圖的結(jié)構(gòu)信息和語義信息，將知識(shí)表示所攜帶的短文本概念轉(zhuǎn)換為概念矩陣，利用圖集合距離相似度計(jì)算方法得到語義相似度，再將知識(shí)點(diǎn)、知識(shí)關(guān)聯(lián)等信息轉(zhuǎn)換為語義信息相似度矩陣，通過向量運(yùn)算得到融合后的知識(shí)子圖.

為了驗(yàn)證VDMF的有效性與準(zhǔn)確性，對(duì)比了不同算法構(gòu)建知識(shí)圖譜的效果.郭芳[20]提出一種單矩陣融合算法(VDSE)，將知識(shí)圖轉(zhuǎn)換為矩陣，圖中有邊相連，矩陣值為1；無邊相連，矩陣值為0.由于其未考慮圖中頂點(diǎn)攜帶的語義信息，同時(shí)也未考慮頂點(diǎn)的重要程度，因此DAMF算法將權(quán)重作為矩陣值，更好的突出知識(shí)點(diǎn)重要性及知識(shí)關(guān)聯(lián)緊密度.與此同時(shí)，將VDMF算法與邏輯回歸算法(Logistic Regression，LR)、支持向量機(jī)算法(Support Vector Machine，SVM)、決策樹算法(Decision Tree，DT)作對(duì)比，如圖5所示.

圖5 雙矩陣融合算法對(duì)比Fig.5 Comparison of double matrix fusion algorithms

在圖5中，本文提出的雙矩陣融合算法在查全率和F1值上較大幅度優(yōu)于其它算法，但在查準(zhǔn)率上略低于SVM算法，這是由于本文提出的算法在對(duì)所有知識(shí)點(diǎn)檢索過程中得到的總知識(shí)點(diǎn)數(shù)與SVM計(jì)算得出的總知識(shí)點(diǎn)數(shù)有差異，優(yōu)化并彌補(bǔ)實(shí)驗(yàn)過程中的差異也是下一步的研究方向.

7 總 結(jié)

面向在線教育領(lǐng)域的研究是一個(gè)既有學(xué)術(shù)意義又有應(yīng)用價(jià)值的研究方向，隨著知識(shí)圖譜的發(fā)展，越來越多的組織及個(gè)人參與到在線教育相關(guān)的研究中.而如何發(fā)揮每位學(xué)生的主觀能動(dòng)性，激勵(lì)學(xué)生自主學(xué)習(xí)，成為一項(xiàng)挑戰(zhàn).本文采用眾包的方式獲取學(xué)習(xí)者對(duì)課程的掌握程度，以玩樂的方式在平臺(tái)上畫一個(gè)自己認(rèn)知范圍內(nèi)的課程體系結(jié)構(gòu)，通過VDMF算法在融合效率可以接受的情況下，實(shí)現(xiàn)了相對(duì)較好的效果.但是本研究中也存在一些需要完善的地方，由于知識(shí)結(jié)構(gòu)體系包含非常豐富的內(nèi)容，從中還可以提取出其它有價(jià)值的信息，比如知識(shí)關(guān)聯(lián)類別、知識(shí)點(diǎn)前驅(qū)后繼關(guān)系等，甚至后期可以將課程內(nèi)知識(shí)點(diǎn)融合擴(kuò)展到課程間知識(shí)點(diǎn)融合，形成一個(gè)學(xué)科知識(shí)圖譜.總之，知識(shí)圖譜是一個(gè)在理論體系和應(yīng)用技術(shù)兩方面都非常有研究?jī)r(jià)值的領(lǐng)域，需要探索和提升的空間還很大，值得后續(xù)學(xué)者為之不斷努力.