基于隨機(jī)游走的概念顯性語(yǔ)義關(guān)聯(lián)度計(jì)算

胡斯卉, 張 波, 宋倩倩

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

?

基于隨機(jī)游走的概念顯性語(yǔ)義關(guān)聯(lián)度計(jì)算

胡斯卉, 張 波, 宋倩倩

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

開(kāi)放知識(shí)網(wǎng)絡(luò)中概念語(yǔ)義關(guān)聯(lián)度計(jì)算是一個(gè)重要的問(wèn)題.吸取蟻群算法思想中的信息素策略,并以融入了該策略的隨機(jī)游走作為關(guān)聯(lián)度計(jì)算的基本框架,將信息素分布作為語(yǔ)義關(guān)聯(lián)緊密程度的判定依據(jù),提出一種基于隨機(jī)游走的語(yǔ)義關(guān)聯(lián)度計(jì)算方法,以顯性方式呈現(xiàn)語(yǔ)義關(guān)聯(lián)度的計(jì)算探索過(guò)程.該算法主要包含路徑選擇模型(PSM)和語(yǔ)義關(guān)聯(lián)度計(jì)算模型(SRCM)兩部分.PSM用于指定游走代理在游走過(guò)程中的路徑選擇、信息素釋放過(guò)程;SRCM利用游走代理反饋的信息進(jìn)行語(yǔ)義關(guān)聯(lián)度的計(jì)算.實(shí)驗(yàn)結(jié)果表明,該算法能夠在線性復(fù)雜度下實(shí)現(xiàn)語(yǔ)義關(guān)聯(lián)度的計(jì)算,擴(kuò)展了語(yǔ)義關(guān)聯(lián)度計(jì)算的可行策略.

語(yǔ)義關(guān)聯(lián)度; 隨機(jī)游走; 信息素; 蟻群算法; 開(kāi)放知識(shí)網(wǎng)絡(luò)

0 引 言

以維基百科為代表的開(kāi)放知識(shí)網(wǎng)絡(luò)為人們提供了一種新型的知識(shí)組織形式,其開(kāi)放性的知識(shí)編輯與組織模式可以實(shí)現(xiàn)知識(shí)“廉價(jià)”、“快速”、“優(yōu)質(zhì)”的動(dòng)態(tài)更新.因此,開(kāi)放知識(shí)網(wǎng)絡(luò)中的高質(zhì)量知識(shí)內(nèi)容和結(jié)構(gòu),已經(jīng)成為人們獲取知識(shí)概念的重要來(lái)源[1].

近年來(lái),已有不少學(xué)者投入到了基于開(kāi)放知識(shí)網(wǎng)絡(luò)的概念語(yǔ)義關(guān)聯(lián)方面研究工作中.例如MajidYazdani[2]、Michael Strube[3]等學(xué)者已經(jīng)利用維基百科的知識(shí)組織特性提出了性能優(yōu)良的語(yǔ)義關(guān)聯(lián)度計(jì)算方法.但這些算法往往基于統(tǒng)計(jì)的隨機(jī)游走,即無(wú)法對(duì)游走過(guò)程進(jìn)行跟蹤.由于無(wú)法掌握游走態(tài)勢(shì),此類(lèi)語(yǔ)義關(guān)聯(lián)度計(jì)算方法雖然在計(jì)算精度上有比較理想的效果,但其本質(zhì)上無(wú)法顯示游走內(nèi)在關(guān)聯(lián)的隱性語(yǔ)義關(guān)聯(lián)度計(jì)算,所返回的結(jié)果僅局限于表示度量關(guān)聯(lián)緊密程度的數(shù)值.

針對(duì)以往研究中的不足,本文作者提出一種利用蟻群算法在開(kāi)放知識(shí)網(wǎng)絡(luò)上進(jìn)行可追蹤的隨機(jī)游走,在游走過(guò)程中根據(jù)語(yǔ)義關(guān)聯(lián)信息釋放不同濃度的信息素,實(shí)現(xiàn)語(yǔ)義關(guān)聯(lián)度計(jì)算的方法.主要工作為:提出問(wèn)題模型及相關(guān)概念;基于問(wèn)題模型提出代理路徑選擇模型(PSM)完成語(yǔ)義關(guān)聯(lián)信息的采集;提出關(guān)聯(lián)度計(jì)算模型(SRCM)完成語(yǔ)義關(guān)聯(lián)度的計(jì)算.并且,據(jù)此提出基于隨機(jī)游走的顯性語(yǔ)義關(guān)聯(lián)度計(jì)算的概念,代表以隨機(jī)游走為基礎(chǔ)并且能過(guò)對(duì)游走過(guò)程進(jìn)行追蹤的語(yǔ)義關(guān)聯(lián)度計(jì)算方法.

第1節(jié)介紹其他學(xué)者的相關(guān)工作與研究;第2節(jié)提出問(wèn)題模型及相關(guān)定義;第3節(jié)詳細(xì)描述路徑選擇模型;第4節(jié)詳細(xì)描述關(guān)聯(lián)度計(jì)算模型;第5節(jié)闡述針對(duì)不同數(shù)據(jù)集進(jìn)行的實(shí)驗(yàn)所得到的實(shí)驗(yàn)結(jié)果及結(jié)果分析;第6節(jié)對(duì)所做工作進(jìn)行總結(jié),并給出未來(lái)研究的重點(diǎn).

1 相關(guān)工作

隨著開(kāi)放知識(shí)網(wǎng)絡(luò)的興起,不少學(xué)者注意到開(kāi)放知識(shí)網(wǎng)絡(luò)在概念語(yǔ)義關(guān)聯(lián)方面的研究?jī)r(jià)值.2006年,Strube和Ponzetto[4]首次提出基于開(kāi)放知識(shí)網(wǎng)絡(luò)層次分類(lèi)結(jié)構(gòu)的語(yǔ)義關(guān)聯(lián)度計(jì)算方法WikiRelate!,并取得了與基于Wordnet的算法相近的準(zhǔn)確度,此后大量基于開(kāi)放知識(shí)網(wǎng)絡(luò)的語(yǔ)義關(guān)聯(lián)度計(jì)算算法被提出.由Gabrilovich和Markovitch[5]提出的Explicit Semantic Analysis(ESA),采用向量空間模型思想,通過(guò)比較知識(shí)網(wǎng)絡(luò)中文章鏈接的帶權(quán)向量實(shí)現(xiàn)語(yǔ)義關(guān)聯(lián)度的計(jì)算,是迄今為止基于開(kāi)放知識(shí)網(wǎng)絡(luò)準(zhǔn)確率最高的語(yǔ)義關(guān)聯(lián)度計(jì)算方法,斯皮爾曼系數(shù)達(dá)到0.75.孫琛琛[6]等國(guó)內(nèi)學(xué)者提出考慮到開(kāi)放知識(shí)網(wǎng)絡(luò)中多類(lèi)型鏈接的語(yǔ)義關(guān)聯(lián)度計(jì)算方法WSR,算法基于開(kāi)放知識(shí)網(wǎng)絡(luò)的分類(lèi)結(jié)構(gòu)和鏈接結(jié)構(gòu),充分考慮了鏈接結(jié)構(gòu)中不同語(yǔ)義強(qiáng)度的鏈接.Yazdani[2]提出基于隨機(jī)游走和開(kāi)放知識(shí)網(wǎng)絡(luò)的語(yǔ)義關(guān)聯(lián)度計(jì)算方法,使用訪問(wèn)概率度量概念間的語(yǔ)義關(guān)聯(lián)度計(jì)算,實(shí)驗(yàn)結(jié)果顯示該算法性能在其實(shí)驗(yàn)場(chǎng)景中高于ESA.此后,基于隨機(jī)游走的語(yǔ)義關(guān)聯(lián)度算法興起.但是目前基于隨機(jī)游走的語(yǔ)義關(guān)聯(lián)度算法無(wú)法對(duì)游走過(guò)程進(jìn)行跟蹤,語(yǔ)義信息挖掘的深度與擴(kuò)展性十分有限.

2 問(wèn)題定義

本章節(jié)首先對(duì)研究問(wèn)題進(jìn)行建模,并給出文中的相關(guān)定義.

2.1 問(wèn)題建模

語(yǔ)義是指數(shù)據(jù)所對(duì)應(yīng)的現(xiàn)實(shí)世界中的事物所代表的概念含義以及含義之間的關(guān)系,是數(shù)據(jù)在某個(gè)領(lǐng)域的解釋和邏輯表示.以開(kāi)放知識(shí)網(wǎng)絡(luò)為背景知識(shí)庫(kù),將概念語(yǔ)義模型形式化表述為N=(V,E,W),其中V={v1,v2,…,vn}表示頂點(diǎn)集,對(duì)應(yīng)現(xiàn)實(shí)世界中的一個(gè)概念;E={e1,e2,…,em}表示邊集,表示概念之間的語(yǔ)義關(guān)聯(lián);W=(wi,j)n×n表示邊所對(duì)應(yīng)的關(guān)聯(lián)度集合.其中任意一條邊對(duì)應(yīng)與一個(gè)節(jié)點(diǎn)的二元組:ex={vi,vj};對(duì)于W:E→R+,記W(ex)=wij,其數(shù)值表示該邊所連接兩個(gè)概念之間的關(guān)聯(lián)度,稱(chēng)這樣的圖結(jié)構(gòu)為概念網(wǎng)絡(luò),是事物關(guān)聯(lián)的形式化表示.

采用如圖1所示策略解決概念網(wǎng)絡(luò)上的語(yǔ)義關(guān)聯(lián)度計(jì)算問(wèn)題.信息素矩陣模塊和語(yǔ)義關(guān)聯(lián)度計(jì)算模塊為對(duì)應(yīng)模型的結(jié)果輸出.通過(guò)語(yǔ)義游走,路徑選擇模型,根據(jù)被比較概念在概念網(wǎng)絡(luò)中的位置,為語(yǔ)義關(guān)聯(lián)度計(jì)算模型提供計(jì)算概念間語(yǔ)義關(guān)聯(lián)度所需的信息素信息.語(yǔ)義關(guān)聯(lián)度計(jì)算模型則以信息素矩陣對(duì)關(guān)聯(lián)程度的反映特性為依據(jù),計(jì)算得到概念間的語(yǔ)義關(guān)聯(lián)度.

圖1 語(yǔ)義關(guān)聯(lián)度計(jì)算問(wèn)題解決策略圖

2.2 相關(guān)定義

定義1 語(yǔ)義信息素(Semantic Pheromone).語(yǔ)義信息素是以游走代理的視角,對(duì)概念網(wǎng)絡(luò)中某段路徑兩端概念之間的語(yǔ)義關(guān)聯(lián)緊密度進(jìn)行評(píng)價(jià)的數(shù)值化信號(hào).其在語(yǔ)義游走階段被引入,釋放量根據(jù)概念間的語(yǔ)義關(guān)聯(lián)緊密度決定.語(yǔ)義信息素濃度高的邊,被其他游走代理選擇的概率高,而語(yǔ)義信息素濃度低的邊,被經(jīng)過(guò)的可能性小.記語(yǔ)義信息素為τ.

定義2 語(yǔ)義強(qiáng)度(Semantic Intensity).語(yǔ)義強(qiáng)度出現(xiàn)在語(yǔ)義游走框架的信息素釋放策略中,用于描述文件中某文本對(duì)于確定該文件的語(yǔ)義特性所發(fā)揮的影響力.文件中某段文本的語(yǔ)義強(qiáng)度由該文本片段的出現(xiàn)頻率級(jí)別決定.

定義3 概念網(wǎng)絡(luò)(Concept Network).概念網(wǎng)絡(luò)是被良好組織,并蘊(yùn)含概念間語(yǔ)義關(guān)聯(lián)的圖結(jié)構(gòu),其節(jié)點(diǎn)對(duì)應(yīng)于人類(lèi)認(rèn)知中的概念,其帶權(quán)或不帶權(quán)的邊表征兩端節(jié)點(diǎn)所表示的概念間的語(yǔ)義關(guān)聯(lián)緊密程度或有無(wú)語(yǔ)義關(guān)聯(lián).概念網(wǎng)絡(luò)是代理游走算法執(zhí)行的基礎(chǔ),語(yǔ)義游走在其上進(jìn)行,其組織構(gòu)建的合理性對(duì)算法執(zhí)行的效果有直接影響.概念網(wǎng)絡(luò)通過(guò)MajidYazdani[2]提出的混合鏈接構(gòu)建方法獲得.記為N=(V,E,W).

定義4 概念頻率級(jí)別(Concept Frequency Level).根據(jù)某個(gè)詞匯或者文本在文本文件中出現(xiàn)的頻率評(píng)級(jí),頻率越高對(duì)應(yīng)的評(píng)級(jí)越高.概念頻率級(jí)別出現(xiàn)在語(yǔ)義游走的信息素釋放策略中,是判斷文件中某一文本片段語(yǔ)義強(qiáng)度的主要依據(jù).

3 路徑選擇模型

開(kāi)放知識(shí)網(wǎng)絡(luò)中,概念得到良好組織,概念間關(guān)聯(lián)具備了圖結(jié)構(gòu),被稱(chēng)為概念網(wǎng)絡(luò).在概念網(wǎng)絡(luò)中,概念節(jié)點(diǎn)之間帶權(quán)或不帶權(quán)的邊代表兩端節(jié)點(diǎn)所表示概念間的語(yǔ)義關(guān)聯(lián)緊密程度或有無(wú)語(yǔ)義關(guān)聯(lián).本文作者主要采用MajidYazdani[2]所提出的混合鏈接構(gòu)建方法獲得概念網(wǎng)絡(luò).這種方法同時(shí)考慮開(kāi)放知識(shí)網(wǎng)絡(luò)中存在于文章之間的超鏈接和基于文章之間內(nèi)容相似度抽象出來(lái)的語(yǔ)義鏈接的方式,從而使概念網(wǎng)絡(luò)作為進(jìn)行隨機(jī)游走的基礎(chǔ).

3.1 游走框架

本模型借鑒蟻群算法的信息素策略[6],結(jié)合語(yǔ)義場(chǎng)景提出改進(jìn).不同之處為,提出了語(yǔ)義信息素的概念,即螞蟻(游走代理)釋放信息素的濃度直接由對(duì)概念間語(yǔ)義關(guān)聯(lián)的緊密程度決定,用以反映概念間的語(yǔ)義關(guān)系.本文作者還提出了用于處理游走過(guò)程中相鄰路徑節(jié)點(diǎn)間路徑語(yǔ)義可靠度的評(píng)價(jià)機(jī)制,相關(guān)內(nèi)容見(jiàn)2.2節(jié).設(shè)定初始階段每條路徑上的信息素濃度為T(mén)INY(很小的數(shù)值).圖2描述了語(yǔ)義游走的基本框架.

圖2 代理游走基本框架

由圖2可見(jiàn),初始階段游走代理的路徑選擇主要受概念網(wǎng)絡(luò)結(jié)構(gòu)影響,由于不同鏈接擁有不同權(quán)值,游走代理傾向于選擇權(quán)值較大的邊前行.即游走代理選擇與其所在節(jié)點(diǎn)對(duì)應(yīng)的概念語(yǔ)義關(guān)聯(lián)更為緊密的節(jié)點(diǎn)行進(jìn).隨著探索的進(jìn)行,概念網(wǎng)絡(luò)上的語(yǔ)義信息素含量不斷累積,語(yǔ)義信息素對(duì)代理路徑選擇的影響力逐漸增大.一次迭代中,概念網(wǎng)絡(luò)中的信息素矩陣按更新公式為.

τij(t+n)=ρ·τij(t)+Δτij,

(1)

其中,ρ表示信息殘留系數(shù),當(dāng)前輪次的游走中,第k個(gè)游走代理在邊(i,j)上釋放的信息素濃度Δτij(k)為.

(2)

(3)

其中,allowedk={1,2,…,n}-tabuk,表示代理下一步被允許選擇的節(jié)點(diǎn),tabuk是游走代理k的禁忌表,記錄代理當(dāng)前探索中已經(jīng)過(guò)的節(jié)點(diǎn);ci,j是聯(lián)結(jié)節(jié)點(diǎn)i和節(jié)點(diǎn)j的邊上的信息素濃度.單個(gè)游走代理進(jìn)行路徑探索的過(guò)程如圖3所示.

圖3 單個(gè)代理的游走過(guò)程

3.2 信息素釋放機(jī)制

本算法在游走過(guò)程中融入語(yǔ)義因素,語(yǔ)義關(guān)聯(lián)的緊密程度決定將施加在某邊上的信息素濃度.文件中不同詞頻的詞匯對(duì)文件的語(yǔ)義定性影響不同,頻率越高的詞,影響力越大.因此,在計(jì)算語(yǔ)義信息素釋放量計(jì)算前,先對(duì)被比較文件中的各詞匯按頻率進(jìn)行評(píng)級(jí).

假設(shè)游走代理剛從節(jié)點(diǎn)x行進(jìn)到節(jié)點(diǎn)y.在它們對(duì)應(yīng)的解釋文本中(包括所有包含解釋成分的文本內(nèi)容),若comWord是其共同擁有的概念詞集合,設(shè)其包含m項(xiàng),將每個(gè)解釋文本中頻率最高的k個(gè)單詞分級(jí),分級(jí)公式如下:

(4)

式中Grand(Item)表示概念詞Item的頻率級(jí)別;rankOf(Item)表示概念詞Item在其所在解釋文檔中的頻率排名;TopFre(k)表示平率最高的k個(gè)概念組成的集合.如果有不同文本t1和t2都能對(duì)應(yīng)到概念網(wǎng)絡(luò)中的概念it,認(rèn)為Grand(it)=Grand(t1)+Grand(t2),此概念度量的是對(duì)應(yīng)概念在解釋文檔中的出現(xiàn)的頻率.用兩概念對(duì)應(yīng)解釋文本中共同概念的詞頻等級(jí)分布決定釋放信息素的量,代理施加在上一步其經(jīng)過(guò)的邊上的信息素濃度

(5)

式中Release為GRANDx|y(comWord(i))指的是共同概念詞comWord(i)在解釋文本x|y中的頻率等級(jí);MAX_INF為表示信息素最大釋放量的常量.

4 語(yǔ)義關(guān)聯(lián)度計(jì)算模型

關(guān)聯(lián)緊密時(shí),收斂的信息素矩陣表現(xiàn)出兩種特性:1)關(guān)聯(lián)邊多,信息素總殘留多,平均殘留多,信息素矩陣收斂快;2)關(guān)聯(lián)邊少,信息素總殘留多,平均殘留多,信息素矩陣收斂快.收斂的速度和信息素分布的緊密程度可作為關(guān)聯(lián)度的評(píng)判依據(jù).因此,將取定迭代次數(shù)執(zhí)行完畢作為終止條件.此時(shí),得到的信息素矩陣可以反映算法的收斂程度,并包含語(yǔ)義信息素在拓?fù)浣Y(jié)構(gòu)上的分布信息.

基于以上兩段,提出概念之間的語(yǔ)義關(guān)聯(lián)度計(jì)算公式,rel(xs→xt)從概念xs到概念xt的語(yǔ)義關(guān)聯(lián)度為

(6)

其中,xs、xt表示被比較的兩個(gè)概念;SucCount表示整個(gè)游走過(guò)程路徑探索的成功總次數(shù),是圖2返回的數(shù)值之一.(6)式所獲得的數(shù)值越小,表示兩節(jié)點(diǎn)表示概念之間的語(yǔ)義關(guān)聯(lián)度越大.語(yǔ)義關(guān)聯(lián)是有向的,通過(guò)取中間值的方法作為基于雙向語(yǔ)義認(rèn)定的關(guān)聯(lián)公式:

(7)

5 實(shí)驗(yàn)分析

本實(shí)驗(yàn)使用2015年2月5號(hào)發(fā)布的英文維基百科sql備份版本.其中,page.sql.gz是頁(yè)面信息sql腳本(1.1GB,包含ID、標(biāo)題、約束不包含頁(yè)面內(nèi)容),pagelinks.sql.gz是頁(yè)面鏈接信息(4.2GB,文章之間的鏈接信息).此外,還有同日發(fā)布的pages-articles-multistream.xml.bz2(11.7GB,包含頁(yè)面內(nèi)容).這些數(shù)據(jù)主要用于概念網(wǎng)絡(luò)的構(gòu)建.使用的測(cè)試集是語(yǔ)義關(guān)聯(lián)研究領(lǐng)域常用的數(shù)據(jù)集WordSim-353.通過(guò)重復(fù)實(shí)踐,設(shè)置算法參數(shù):信息素留存率0.85;主動(dòng)終止探索概率0.2;迭代輪次600;每次迭代參與游走代理數(shù)800[10].

對(duì)于語(yǔ)義關(guān)聯(lián)度計(jì)算準(zhǔn)確度的檢驗(yàn),采用將目標(biāo)算法計(jì)算結(jié)果與人工判斷的結(jié)果進(jìn)行比較,計(jì)算兩者之間Spearman等級(jí)相關(guān)系數(shù)的方法.Spearman等級(jí)相關(guān)系數(shù)計(jì)算公式為[7]

(8)

式中di是第i個(gè)元素的等級(jí)差,對(duì)應(yīng)第i個(gè)詞對(duì)的目標(biāo)算法計(jì)算結(jié)果和人工判斷結(jié)果在各自排序表中位置的差值,n表示測(cè)試集的規(guī)模.

5.1 游走算法合理性評(píng)估

表1 實(shí)驗(yàn)數(shù)據(jù)分組

為了對(duì)算法游走框架合理性進(jìn)行檢驗(yàn),對(duì)游走算法進(jìn)行功能擴(kuò)展,使其能夠記錄游走過(guò)程中經(jīng)過(guò)的路徑.選取算法每次執(zhí)行中被經(jīng)過(guò)頻率最高的路徑作為利用游走框架得到的語(yǔ)義關(guān)聯(lián)路徑,算法執(zhí)行所用的數(shù)據(jù)來(lái)自WordSim-353 Relatedness(252 word pairs that only show relatedness),所獲得的實(shí)驗(yàn)數(shù)據(jù)包含252條路徑記錄,平均路徑長(zhǎng)度為3.63.根據(jù)WordSim-353 Relatedness中詞匯對(duì)中關(guān)聯(lián)度的評(píng)定,將所得到的路徑記錄組如表1所示.

實(shí)驗(yàn)結(jié)果如圖4所示,從中可知,游走算法的合理性受被比較對(duì)象之間的語(yǔ)義強(qiáng)度影響(高語(yǔ)義關(guān)聯(lián)度詞匯對(duì)對(duì)應(yīng)的關(guān)聯(lián)路徑被判定認(rèn)同的概率更高),但整體來(lái)說(shuō),能夠達(dá)到較高的合理性,可以保證語(yǔ)義關(guān)聯(lián)度計(jì)算的進(jìn)行.

5.2 語(yǔ)義關(guān)聯(lián)度計(jì)算準(zhǔn)確性評(píng)估

圖5是WordSim-353數(shù)據(jù)集上,本算法的語(yǔ)義關(guān)聯(lián)度計(jì)算精確度與其他基于維基百科的關(guān)聯(lián)度計(jì)算算法的對(duì)比數(shù)據(jù).可見(jiàn),雖本算法與目前最優(yōu)秀的算法相比,在計(jì)算精度上有所損失,但折損并不明顯.總體說(shuō),本算法在提升算法擴(kuò)展性能的前提下,較好地保證了語(yǔ)義關(guān)聯(lián)度計(jì)算的精度.

圖4 游走算法評(píng)估結(jié)果

圖5 基于開(kāi)放知識(shí)網(wǎng)絡(luò)的各語(yǔ)義關(guān)聯(lián)度算法Spearman系數(shù)比較

6 結(jié) 語(yǔ)

針對(duì)開(kāi)發(fā)知識(shí)網(wǎng)絡(luò)中概念語(yǔ)義關(guān)聯(lián)度計(jì)算問(wèn)題,本文作者提出一種基于蟻群算法和隨機(jī)游走方法的語(yǔ)義關(guān)聯(lián)度計(jì)算方法,該方法采用蟻群算法作為關(guān)聯(lián)度計(jì)算的基本框架,根據(jù)語(yǔ)義關(guān)聯(lián)在信息素矩陣上的表現(xiàn)特性,將信息素分布作為語(yǔ)義關(guān)聯(lián)緊密程度的判定依據(jù).實(shí)驗(yàn)結(jié)果表明,該算法能夠保證語(yǔ)義關(guān)聯(lián)度計(jì)算精度.作者將在后續(xù)的工作中繼續(xù)優(yōu)化本方案.

[1] Barbu E.Property type distribution in Wordnet,corpora and Wikipedia [J].Expert Systems with Applications,2015,42(1):3501-3507.

[2] Majid Y,Andrei P B.Computing text semantic relatedness using the contents and links of a hypertext encyclopedia [J].Artificial Intelligence,2013(194):176-202.

[3] Michael S,Simone P P.WikiRelate! Computingsemantic relatedness using Wikipedia [J].American Association for Artificial Intelligence,2006(6):1419-1424.

[4] Gabrilovich E,Markovitch S.Computing semantic relatedness using Wikipedia-based explicit semantic analysis [J].Proceedings of International Joint Conference on Artificial Intelligence,2007,6:1606-1611.

[5] Chen C S.WSR:a semantic relatedness measure based on Wikipedia structure [J].Chinese Journal of Computers,2012,35(11):2361-2370.

[6] Bacry E.Multifractal random walk [J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2001,64(2):1107-1112.

[7] Duan H B,Wang D B,Zhu J Q,et al.Development on ant colony algorithm theory and its application [J].Kongzhi Yu Juece/control & Decision,2004,19(12):1321-1320.

[8] Di J.Structure detection of complex network cluster [J].Journal of Software,2012,23(3):451-464.

[9] Boryczka,U,Kozak J.Enhancing the effectiveness of Ant Colony Decision Tree algorithms by co-learning [J].Applied Soft Computing,2015,30(c):166-178.

(責(zé)任編輯：包震宇,馮珍珍)

An explicit semantic relatedness measure based on random walk

HU Sihui, ZHANG Bo, SONG Qianqian

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

The semantic relatedness calculation of open domain knowledge network is a significant issue.In this paper,pheromone strategy is drawn from the thought of ant colony algorithm and is integrated into the random walk which is taken as the basic framework of calculating the semantic relatedness degree.The pheromone distribution is taken as a criterion of determining the tightness degree of semantic relatedness.A method of calculating semantic relatedness degree based on random walk is proposed and the exploration process of calculating the semantic relatedness degree is presented in a dominant way.The method mainly contains Path Select Model(PSM) and Semantic Relatedness Computing Model(SRCM).PSM is used to simulate the path selection of ants and pheromone release.SRCM is used to calculate the semantic relatedness by utilizing the information returned by ants.The result indicates that the method could complete semantic relatedness calculation in linear complexity and extend the feasible strategy of semantic relatedness calculation.

semantic relatedness; random walk; pheromone; ant colony algorithm; open domain knowledge network

2015-06-28

國(guó)家自然科學(xué)基金(61572326,61103069);上海市教委科研創(chuàng)新項(xiàng)目(13YZ052);上海師范大學(xué)創(chuàng)新基金(DCL201302)

張 波,中國(guó)上海市徐匯區(qū)桂林路100號(hào),上海師范大學(xué)信息與機(jī)電工程學(xué)院,郵編:200234,E-mail:zhangbo@shnu.edu.cn

TP 301

A

1000-5137(2016)05-0580-07

10.3969/J.ISSN.1000-5137.2016.05.011