馬秋微,趙書良,趙 妍

(1. 河北師范大學(xué) 計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院,河北 石家莊 050024;2. 供應(yīng)鏈大數(shù)據(jù)分析與數(shù)據(jù)安全河北省工程研究中心,河北 石家莊 050024;3. 河北省網(wǎng)絡(luò)與信息安全重點(diǎn)實(shí)驗(yàn)室,河北 石家莊 050024)

0 引言

真實(shí)世界中的大部分?jǐn)?shù)據(jù)主要以非結(jié)構(gòu)化文本的形式存在,從非結(jié)構(gòu)化文本中挖掘結(jié)構(gòu)和知識(shí)是數(shù)據(jù)挖掘任務(wù)中的主要挑戰(zhàn)之一,具有巨大的潛在影響。傳統(tǒng)的文本相似性度量方法使用簡單的詞袋模型作為文本表示,將文本表示為獨(dú)熱向量的形式,并使用不同的度量方法(如Cosine相似性、Jaccard相似性和Dice系數(shù))計(jì)算文本相似性。然而,在文本相似性度量任務(wù)中,不能僅僅考慮單詞粒度。如果兩篇文檔中的單詞不相同,但其實(shí)體所對(duì)應(yīng)的實(shí)體類型相同,這兩篇文檔也具有相關(guān)性。基于向量空間模型的文本相似性度量方法僅利用文本中簡單的詞頻信息將文本轉(zhuǎn)化為向量,忽略了文本的語義關(guān)系,導(dǎo)致其計(jì)算過程復(fù)雜且精確度不高。為了結(jié)合上下文信息,Nguyen等人[1]提出LF-LDA(Latent Feature-LDA)主題模型,該模型將預(yù)先訓(xùn)練好的詞向量引入多項(xiàng)式分布模型,提高了相似度計(jì)算結(jié)果的準(zhǔn)確性。除了主題模型,訓(xùn)練神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)文本語料庫中的語義信息從而得到文本向量,也成為目前研究的熱點(diǎn)。文獻(xiàn)[2]結(jié)合文本中單詞的上下文信息,利用Word2Vec模型將單詞表示為低維向量,再利用距離度量方法進(jìn)行文本相似性度量。Kusner等人[3]提出詞移距離算法(Word Mover's Distance,WMD)度量文本距離,該算法利用文本中所有詞語轉(zhuǎn)移到另一文本中對(duì)應(yīng)詞語所需要的最小距離來度量二者的相似度。Tian等人[4]提出基于特征貢獻(xiàn)度的句向量表示模型,得到語義信息集中且任務(wù)針對(duì)性強(qiáng)的句向量表示,在一定程度上提高了模型的計(jì)算效率。上述方法將文本表示為向量的形式度量文本的隱式語義相似性,降低了文本語義的可解釋性,忽略了非結(jié)構(gòu)化文本中的結(jié)構(gòu)化信息。

異質(zhì)信息網(wǎng)絡(luò)(Heterogeneous Information Network,HIN)[5]作為一種結(jié)構(gòu)化數(shù)據(jù)能夠有效建模和處理多種類型對(duì)象及其之間復(fù)雜的交互關(guān)系,并且在許多不同的數(shù)據(jù)挖掘任務(wù)中得到了廣泛應(yīng)用。Du等人[6]認(rèn)為元路徑可以表示HIN中節(jié)點(diǎn)之間的關(guān)系,于是通過豐富的路徑信息,構(gòu)造基于元路徑的特征矩陣,并對(duì)隨機(jī)森林分類器進(jìn)行訓(xùn)練,實(shí)現(xiàn)HIN中節(jié)點(diǎn)的分類。Cao等人[7]提出一種基于異質(zhì)信息網(wǎng)絡(luò)的文本聚類框架,將文本建模為異質(zhì)信息網(wǎng)絡(luò),通過文本節(jié)點(diǎn)之間的相似度矩陣對(duì)給定文本進(jìn)行聚類。文獻(xiàn)[8-9]在HIN上利用元路徑豐富的語義信息來產(chǎn)生用戶感興趣的相關(guān)推薦。Bai等人[10]在HIN上利用節(jié)點(diǎn)的分布式向量表示,將其他節(jié)點(diǎn)作為“背景知識(shí)”學(xué)習(xí)目標(biāo)節(jié)點(diǎn)集的向量表示。邱等人[11]提出了一種基于向量的語義特征提取方法,利用向量的空間距離度量節(jié)點(diǎn)的相似性。劉等人[12]將文獻(xiàn)異質(zhì)信息網(wǎng)絡(luò)中的節(jié)點(diǎn)屬性信息與文本內(nèi)容信息相結(jié)合以量化節(jié)點(diǎn)之間的相似性。Wan等人[13]提出一種基于強(qiáng)化學(xué)習(xí)的元路徑挖掘方法,利用多跳推理策略,從網(wǎng)絡(luò)模式復(fù)雜的HIN中挖掘信息豐富的元路徑,獲取不同對(duì)象之間的路徑語義信息。文獻(xiàn)[14]將文本內(nèi)容的主題分布作為元路徑的屬性約束,度量文獻(xiàn)異質(zhì)信息網(wǎng)絡(luò)中相同類型對(duì)象之間的相似性。文獻(xiàn)[15-17]基于元路徑度量HIN上不同類型對(duì)象間的相似性。

結(jié)合異質(zhì)信息網(wǎng)絡(luò)的結(jié)構(gòu)特性和語義特性,將非結(jié)構(gòu)化文本數(shù)據(jù)轉(zhuǎn)換為結(jié)構(gòu)化知識(shí),在此基礎(chǔ)上挖掘需要的知識(shí)具有重要的研究意義。Yao等人[18]建立了一個(gè)基于語料庫的同質(zhì)文本網(wǎng)絡(luò),利用圖卷積網(wǎng)絡(luò)實(shí)現(xiàn)文本分類。Bao等人[19]利用長短時(shí)記憶網(wǎng)絡(luò)度量文本語義相似性。上述方法僅考慮了文本的上下文信息,忽略了背景信息以及背景之外的知識(shí)。與上述基于嵌入的方法相比,使用顯式的語義特征來計(jì)算文本相似性,其度量結(jié)果更具有可解釋性,更容易被人類理解。Wang等人[20]提出了無監(jiān)督自動(dòng)元路徑選擇方法對(duì)元路徑進(jìn)行選擇,并定義了一種集成元路徑的相似性度量方法。但是該方法沒有考慮單詞或者實(shí)體本身對(duì)文本相似性的影響。針對(duì)上述不足,本文結(jié)合鏈接權(quán)重信息在非結(jié)構(gòu)化文本中使用結(jié)構(gòu)信息及顯式語義信息進(jìn)一步改進(jìn)文本相似性計(jì)算。

本文的主要貢獻(xiàn)如下:

(1) 將文本相似性度量問題轉(zhuǎn)化為加權(quán)異質(zhì)信息網(wǎng)絡(luò)上的基于元路徑的節(jié)點(diǎn)相似性度量問題。提出基于異質(zhì)信息網(wǎng)絡(luò)的文本相似性度量模型HINSim。

(2) 結(jié)合世界知識(shí)庫,構(gòu)建帶有鏈接權(quán)重的文本異質(zhì)信息網(wǎng)絡(luò)。其中,文本被表示為一種特定類型的節(jié)點(diǎn)。并將點(diǎn)互信息(PMI)值,以及詞頻-逆文檔頻率(TF-IDF)作為不同類型節(jié)點(diǎn)之間的鏈接權(quán)重。

(3) 挖掘關(guān)于文本類型節(jié)點(diǎn)的元路徑,提出基于元路徑的ω-PageRank-Nibble子圖劃分算法,對(duì)網(wǎng)絡(luò)模式復(fù)雜的異質(zhì)信息網(wǎng)絡(luò)進(jìn)行剪枝處理,降低空間成本,并根據(jù)子圖計(jì)算存儲(chǔ)元路徑的交換矩陣,節(jié)約相似性計(jì)算的時(shí)間成本。

(4) 提出基于元路經(jīng)集的AllPathSim耦合相似性度量方法。結(jié)合多條元路徑的權(quán)重,綜合度量文本類型節(jié)點(diǎn)的相似性。

1 加權(quán)異質(zhì)信息網(wǎng)絡(luò)

1.1 整體解決方案架構(gòu)

與傳統(tǒng)的文本度量方式不同,基于異質(zhì)信息網(wǎng)絡(luò)的文本相似性度量方法結(jié)合世界知識(shí)庫,將文本特征粒度擴(kuò)大化,將單詞粒度或短語粒度上升到實(shí)體類型粒度。同時(shí),以異質(zhì)信息網(wǎng)絡(luò)的結(jié)構(gòu)特性為切入點(diǎn),從非結(jié)構(gòu)化信息轉(zhuǎn)化為結(jié)構(gòu)化知識(shí)的角度出發(fā),將文本類型數(shù)據(jù)表示為網(wǎng)絡(luò)模式復(fù)雜的且?guī)в墟溄訖?quán)重的異質(zhì)信息網(wǎng)絡(luò)的形式。利用加權(quán)異質(zhì)信息網(wǎng)絡(luò)中豐富的顯式語義信息進(jìn)行節(jié)點(diǎn)相似性度量。概括來說,基于異質(zhì)信息網(wǎng)絡(luò)的文本相似性度量方法將文本相似性度量問題轉(zhuǎn)化為加權(quán)異質(zhì)信息網(wǎng)絡(luò)上基于元路徑的相同類型節(jié)點(diǎn)的相似性度量問題?；诋愘|(zhì)信息網(wǎng)絡(luò)的文本相似性度量方法的整體框架主要分為三部分,如圖1所示。

圖1 基于異質(zhì)信息網(wǎng)絡(luò)的文本相似性度量方法框架

(1) 構(gòu)建加權(quán)文本異質(zhì)信息網(wǎng)絡(luò)。首先,生成實(shí)體類型節(jié)點(diǎn),對(duì)給定文本進(jìn)行語義解析和語義過濾,將文本中的實(shí)體及關(guān)系映射到世界知識(shí)庫中,得到其對(duì)應(yīng)的實(shí)體類型及關(guān)系類型。其次,對(duì)給定文本進(jìn)行去除停用詞及特征提取操作,得到單詞類型節(jié)點(diǎn)。最后,利用TF-IDF和PMI方法對(duì)鏈接關(guān)系進(jìn)行加權(quán),實(shí)現(xiàn)從文本到加權(quán)異質(zhì)信息網(wǎng)絡(luò)的轉(zhuǎn)換。

(2) 元路徑挖掘及圖剪枝。首先,基于加權(quán)文本異質(zhì)信息網(wǎng)絡(luò)進(jìn)行元路徑挖掘,得到對(duì)稱元路徑。其次,基于每條特定的元路徑,利用ω-PageRank-Nibble子圖劃分算法對(duì)網(wǎng)絡(luò)模式復(fù)雜的異質(zhì)信息網(wǎng)絡(luò)進(jìn)行剪枝,得到包含給定文本節(jié)點(diǎn)集的局部圖,以節(jié)省存儲(chǔ)空間。最后,根據(jù)局部圖,計(jì)算并存儲(chǔ)元路徑的交換矩陣,為后續(xù)計(jì)算節(jié)約時(shí)間成本。

(3) 文本節(jié)點(diǎn)相似性度量。首先,結(jié)合元路徑交換矩陣,利用基于特定元路徑的OnePathSim相似性度量方法,度量單條元路徑下文本類型節(jié)點(diǎn)的相似性。其次,根據(jù)不同元路徑的路徑實(shí)例個(gè)數(shù)為每條元路徑進(jìn)行加權(quán)。最后,結(jié)合多條元路徑的權(quán)重,利用基于元路徑集的AllPathSim耦合相似性度量方法度量元路徑集下文本類型節(jié)點(diǎn)的相似性。

1.2 異質(zhì)信息網(wǎng)絡(luò)構(gòu)建方法

加權(quán)文本異質(zhì)信息網(wǎng)絡(luò)的構(gòu)建即實(shí)現(xiàn)從文本到帶有鏈接權(quán)重的異質(zhì)信息網(wǎng)絡(luò)的轉(zhuǎn)化。

定義1 加權(quán)異質(zhì)信息網(wǎng)絡(luò)網(wǎng)絡(luò)為加權(quán)無向圖G(V,W,E),具有節(jié)點(diǎn)類型映射函數(shù)φ:V→A和關(guān)系類型映射函數(shù)ψ:E→R,其中,每個(gè)對(duì)象v∈V屬于一個(gè)特定的節(jié)點(diǎn)類型φ(V)∈A,每個(gè)鏈接e∈E屬于一個(gè)特定的關(guān)系類型ψ(E)∈R且具有相應(yīng)的權(quán)重ω∈W。當(dāng)滿足節(jié)點(diǎn)類型數(shù)量|A|>1或關(guān)系類型數(shù)量|R|>1時(shí),該網(wǎng)絡(luò)為加權(quán)異質(zhì)信息網(wǎng)絡(luò)。

世界知識(shí)庫包含多種實(shí)體類型和關(guān)系類型。本文結(jié)合世界知識(shí)庫,將文本中的實(shí)體及關(guān)系映射到世界知識(shí)庫中,得到其對(duì)應(yīng)的實(shí)體類型及關(guān)系類型。構(gòu)建帶有鏈接權(quán)重的文本異質(zhì)信息網(wǎng)絡(luò),首先,對(duì)給定文本進(jìn)行語義解析,提取候選實(shí)體。其次,對(duì)語義解析結(jié)果進(jìn)行語義過濾,選取候選實(shí)體得分最高的實(shí)體,以此生成不同的實(shí)體類型節(jié)點(diǎn)。然后,通過對(duì)給定文本集合的預(yù)處理及特征提取等方法生成文本異質(zhì)信息網(wǎng)絡(luò)中的單詞類型節(jié)點(diǎn)。最后,對(duì)不同節(jié)點(diǎn)間的鏈接關(guān)系進(jìn)行加權(quán),實(shí)現(xiàn)文本到異質(zhì)信息網(wǎng)絡(luò)的轉(zhuǎn)換。本文構(gòu)建的異質(zhì)信息網(wǎng)絡(luò)的節(jié)點(diǎn)類型包含實(shí)體節(jié)點(diǎn)類型,單詞節(jié)點(diǎn)類型,以及文本節(jié)點(diǎn)類型。其中,文本節(jié)點(diǎn)與實(shí)體節(jié)點(diǎn)以及文本節(jié)點(diǎn)與單詞節(jié)點(diǎn)之間的權(quán)重是該實(shí)體或單詞在對(duì)應(yīng)文本中的詞頻-逆文檔頻率(TF-IDF),本文在后續(xù)的實(shí)驗(yàn)中證明了使用TF-IDF方法比單純使用詞頻(TF)方法效果更好。不同實(shí)體節(jié)點(diǎn)之間的權(quán)重是實(shí)體間的點(diǎn)互信息(PMI)值。以兩篇短文本為例,加權(quán)文本異質(zhì)信息網(wǎng)絡(luò)示意圖如圖2所示。

圖2 加權(quán)文本異質(zhì)信息網(wǎng)絡(luò)示意圖

1.2.1 實(shí)體節(jié)點(diǎn)生成

(1) 語義解析

語義解析是將一段自然語言文本映射成邏輯形式表示的任務(wù)[20]。世界知識(shí)庫由形式為<實(shí)體,關(guān)系,實(shí)體>的三元組集構(gòu)成。簡單來說,語義解析就是將文本中的實(shí)體以及關(guān)系短語映射到世界知識(shí)庫并得到其類型的過程。將世界知識(shí)Freebase加載到Virtuoso圖數(shù)據(jù)庫中,通過SPARQL語句查詢得到相應(yīng)的實(shí)體類型。例如,給定一段文本“Obama is the president of United States of America.”。使用Accurate Online Disambiguation of Entities(AIDA)工具來識(shí)別文本中的實(shí)體。將識(shí)別的實(shí)體“Obama”和“United States of America”映射到知識(shí)庫中得到一元邏輯形式“People.BarackObama”和“Country.USA”,其中“People”和“Country”是知識(shí)庫中的實(shí)體類型信息。關(guān)系短語“president”映射成二元邏輯形式“PresidentofCountry”,該形式是知識(shí)庫中的關(guān)系類型信息。然后,使用語法規(guī)則組合基本邏輯形式進(jìn)而生成邏輯形式People.BarackObama∧President.USA來表示其語義信息。語義解析的結(jié)果是將給定文本解析為不同的邏輯形式,該形式包含該實(shí)體以及對(duì)應(yīng)的候選實(shí)體類型。

(2) 語義過濾

對(duì)于給定文本中的每個(gè)句子,語義解析之后得到對(duì)應(yīng)文本的一組表示語義信息的邏輯形式。然而,語義解析過程所提取的實(shí)體可能具有多層含義。例如: “Apple”的實(shí)體類型可能是水果或者公司。這就需要針對(duì)語義解析的結(jié)果進(jìn)行語義過濾,即對(duì)具有多種實(shí)體類型的實(shí)體進(jìn)行消歧處理。假設(shè)文檔的所有句子中最常見的實(shí)體類型是含有正確語義的實(shí)體類型。以文檔中出現(xiàn)的實(shí)體的類型頻率為標(biāo)準(zhǔn),選取在文本中出現(xiàn)次數(shù)最多即得分最高的實(shí)體類型作為該實(shí)體的正確語義。

1.2.2 單詞節(jié)點(diǎn)生成

文本中存在的某些單詞并非是實(shí)體,即在世界知識(shí)庫中不存在其相應(yīng)類型,但是這些單詞也是文本異質(zhì)信息網(wǎng)絡(luò)的重要組成部分。這些單詞在構(gòu)建的文本異質(zhì)信息網(wǎng)絡(luò)中只具有一種節(jié)點(diǎn)類型,統(tǒng)稱為單詞類型節(jié)點(diǎn)。與實(shí)體類型節(jié)點(diǎn)不同,單詞類型節(jié)點(diǎn)僅僅與文本類型節(jié)點(diǎn)具有相應(yīng)鏈接,表示包含與被包含的關(guān)系。單詞類型節(jié)點(diǎn)的生成包含文本預(yù)處理和文本特征提取兩個(gè)步驟。首先,以空格作為分隔符對(duì)給定文本進(jìn)行分詞處理;其次,去除停用詞,刪除對(duì)內(nèi)容影響較小或毫無意義的詞;最后,利用TF-IDF加權(quán)方法得到特征詞匯。該特征詞匯即為文本異質(zhì)信息網(wǎng)絡(luò)中的單詞類型節(jié)點(diǎn)。

1.2.3 鏈接加權(quán)

考慮到不同實(shí)體或單詞在文本中的重要程度以及不同實(shí)體之間的相關(guān)性不同,本文將該實(shí)體或單詞在對(duì)應(yīng)文本中的TF-IDF值作為文本節(jié)點(diǎn)和單詞節(jié)點(diǎn)或?qū)嶓w節(jié)點(diǎn)之間的鏈接權(quán)重。另外,本文采用PMI單詞關(guān)聯(lián)度量方法,計(jì)算不同實(shí)體節(jié)點(diǎn)之間的鏈接權(quán)重。鏈接權(quán)重wij的計(jì)算如式(1)所示。

(1)

加權(quán)文本異質(zhì)信息網(wǎng)絡(luò)構(gòu)建算法偽代碼如算法1所示。

算法1: 加權(quán)文本異質(zhì)信息網(wǎng)絡(luò)構(gòu)建算法

2 元路徑挖掘與圖剪枝

2.1 相關(guān)定義

定義2 網(wǎng)絡(luò)模式網(wǎng)絡(luò)模式是對(duì)異質(zhì)信息網(wǎng)絡(luò)G(V,W,E)的一種元描述,其是定義在節(jié)點(diǎn)類型A、關(guān)系類型R上的無向圖,記為SG=(A,R),包含節(jié)點(diǎn)類型的映射φ:V→A和關(guān)系類型的映射ψ:E→R。

本文構(gòu)建的文本異質(zhì)信息網(wǎng)絡(luò)的網(wǎng)絡(luò)模式如圖3所示。

圖3 文本異質(zhì)信息網(wǎng)絡(luò)的網(wǎng)絡(luò)模式

基于上述定義,元路徑還延伸出對(duì)稱元路徑的定義。如果元路徑中的關(guān)系R是對(duì)稱的,即P和P-1相等,那么該元路徑即為對(duì)稱元路徑。

定義4 交換矩陣給定加權(quán)異質(zhì)信息網(wǎng)絡(luò)G(V,W,E)及其網(wǎng)絡(luò)模式SG,基于元路徑P=A1→A2→…→Al+1的交換矩陣MP=(WA1A2,WA2A3,…,WAlAl+1),其中WAkAk+1是類型Ak和Ak+1之間的鄰接矩陣。MP(i,j)是節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的鏈接權(quán)重的值。

2.2 元路徑挖掘

在帶有鏈接權(quán)重的文本異質(zhì)信息網(wǎng)絡(luò)中,兩個(gè)文本類型節(jié)點(diǎn)之間存在多條元路徑。假設(shè)相似的文本在結(jié)構(gòu)上由對(duì)稱元路徑定義[21],本文只探索兩個(gè)文本類型節(jié)點(diǎn)之間的對(duì)稱元路徑。

不同于結(jié)構(gòu)簡單的異質(zhì)信息網(wǎng)絡(luò),例如: DBLP,本文所構(gòu)建的文本異質(zhì)信息網(wǎng)絡(luò)的網(wǎng)絡(luò)模式較為復(fù)雜,其中包含的實(shí)體節(jié)點(diǎn)類型多樣化,本文選取簡單的元路徑挖掘方法。首先定義對(duì)稱元路徑的最大長度L,枚舉L/2個(gè)不同的實(shí)體類型并進(jìn)行簡單的排列組合。然后,存儲(chǔ)每兩種不同節(jié)點(diǎn)類型的交換矩陣。最后,選取對(duì)稱的且具有語義意義的元路徑。本文在4.3.1節(jié)實(shí)驗(yàn)部分進(jìn)行了不同路徑長度影響相似性度量結(jié)果的實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,最佳路徑長度為4。

2.3 圖剪枝

由交換矩陣的定義可知,需要利用矩陣乘法來計(jì)算路徑中每兩個(gè)相鄰實(shí)體之間鄰接矩陣的乘積。計(jì)算具有多種實(shí)體類型的元路徑的交換矩陣花銷巨大[22]。另外,在網(wǎng)絡(luò)模式復(fù)雜的異質(zhì)信息網(wǎng)絡(luò)中,并非所有實(shí)體都是相關(guān)的。為了節(jié)省存儲(chǔ)空間,提高度量效率,本文提出基于元路徑的ω-PageRank-Nibble子圖劃分算法,基于每一條特定的元路徑,采用剪枝策略,對(duì)大規(guī)模異質(zhì)信息網(wǎng)絡(luò)進(jìn)行修剪,從而得到包含給定文本節(jié)點(diǎn)集的局部圖。根據(jù)局部圖,計(jì)算并存儲(chǔ)基于每一條特定元路徑的交換矩陣,為后續(xù)的相似性度量節(jié)約時(shí)間以及空間成本。本文在4.3.2節(jié)實(shí)驗(yàn)部分證明了基于元路徑的ω-PageRank-Nibble子圖劃分算法的可行性和有效性。

傳統(tǒng)的PageRank-Nibble算法是從一個(gè)節(jié)點(diǎn)開始,在給定圖上進(jìn)行隨機(jī)游走,以一定的概率游走到其他的鄰居節(jié)點(diǎn)。不同于傳統(tǒng)的PageRank-Nibble算法,基于元路徑的ω-PageRank-Nibble子圖劃分算法針對(duì)每條元路徑進(jìn)行隨機(jī)游走,從多個(gè)不同的文本節(jié)點(diǎn)開始,并根據(jù)不同的鏈接權(quán)重跳轉(zhuǎn)到其他鄰居節(jié)點(diǎn)。基于加權(quán)文本異質(zhì)信息網(wǎng)絡(luò)G(V,W,E),給出本方法中的相關(guān)定義。

定義5 節(jié)點(diǎn)i的加權(quán)度dw(i)式中,N(i)表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)個(gè)數(shù)。wij為節(jié)點(diǎn)i和鄰居節(jié)點(diǎn)j之間的鏈接權(quán)重。

dw(i)=∑j∈N(i)wij

(2)

定義6 整張圖G的所有節(jié)點(diǎn)的加權(quán)量Dw(V)式中,V代表圖G的所有節(jié)點(diǎn)的集合。

Dw(V)=∑i∈Vdw(i)

(3)

Dw(S)=∑i∈Sdw(i)

(4)

(5)

基于元路徑的ω-PageRank-Nibble子圖劃分算法維護(hù)了一個(gè)剩余向量r和一個(gè)ε近似的PageRank向量。以給定文本節(jié)點(diǎn)集為初始節(jié)點(diǎn),進(jìn)行一系列的push操作,若r[v]/dw(v)≥ε,則執(zhí)行下一步游走操作。將r[v]*α賦給p[v],r[v]的值等于剩余的r[v]×(1-α)的值,一直重復(fù)此過程選擇滿足條件的節(jié)點(diǎn),直到r[v]/dw(v)<ε則停止迭代。其中α和ε的值如文獻(xiàn)[20]中一樣分別設(shè)置為0.45,10-5。該算法的偽代碼如算法2所示。

算法2: 基于元路徑的ω-PageRank-Nibble子圖劃分算法

3 節(jié)點(diǎn)相似性度量方法

3.1 基于特定元路徑的OnePathSim相似性度量方法

在異質(zhì)信息網(wǎng)絡(luò)上,元路徑可以用來計(jì)算源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的相似性。受PathSim[22]啟發(fā),在構(gòu)建的加權(quán)文本異質(zhì)信息網(wǎng)絡(luò)上,基于給定的一條特定元路徑,結(jié)合該元路徑下不同對(duì)象之間的鏈接權(quán)重,度量兩個(gè)不同文本節(jié)點(diǎn)的相似性。

定義9給定一條特定元路徑,文本節(jié)點(diǎn)i和文本節(jié)點(diǎn)j之間基于特定元路徑的OnePathSim相似性度量定義如式(6)所示。

(6)

由定義4可知,元路徑p的交換矩陣MP=(W12,W23,…,Wl-1l),其中W12為元路徑p下第一個(gè)節(jié)點(diǎn)類型和第二個(gè)節(jié)點(diǎn)類型之間的鄰接矩陣。鄰接矩陣中的值為該節(jié)點(diǎn)類型中不同對(duì)象之間的鏈接權(quán)重ω,ω的值根據(jù)式(1)計(jì)算得到。式(6)中,Mp(i,j)為節(jié)點(diǎn)i和節(jié)點(diǎn)j在交換矩陣中的權(quán)重值,即交換矩陣中第i行第j列對(duì)應(yīng)位置的值。Mp(i,i)為節(jié)點(diǎn)i與其自身在交換矩陣中的權(quán)重值,即交換矩陣中第i行第i列對(duì)應(yīng)位置的值。Mp(j,j)為節(jié)點(diǎn)j與其自身在交換矩陣中的權(quán)重值,即交換矩陣中第j行第j列對(duì)應(yīng)位置的值。

3.2 基于元路徑集的AllPathSim耦合相似性度量方法

源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間可能包含多條元路徑,某一元路徑下的路徑實(shí)例越多,表明該元路徑對(duì)相似性度量更重要。本文結(jié)合多條元路徑,將基于某一特定的元路徑的實(shí)例數(shù)與所有路徑實(shí)例數(shù)的比值作為該元路徑的相應(yīng)權(quán)重。結(jié)合每條元路徑的權(quán)重,綜合度量文本類型節(jié)點(diǎn)之間的相似性。由于提前存儲(chǔ)了所有元路徑的交換矩陣,所以在進(jìn)行相似性度量時(shí)節(jié)約了大量的時(shí)間與空間成本。

定義10給定對(duì)稱元路徑集合P{P1,P2,…,PN},文本節(jié)點(diǎn)i和文本節(jié)點(diǎn)j之間基于元路徑集的AllPathSim耦合相似性度量定義如式(7)所示。

AllPathSim(i,j)

(7)

AllPathSim耦合相似性度量滿足以下性質(zhì),具有度量有效性。

(1) 正定性

AllPathSim(i,j)≥0,且AllPathSim(i,i)=1

(2) 對(duì)稱性

AllPathSim(i,j)=AllPathSim(j,i)

(3) 三角不等式

AllPathSim(i,j)≤AllPathSim(i,k)+AllPathSim(j,k)

算法3描述了基于元路徑集的耦合相似性度量算法的偽代碼。

算法3: 基于元路徑集的耦合相似性度量算法

4 實(shí)驗(yàn)驗(yàn)證與分析

4.1 數(shù)據(jù)集

本文采用20Newsgroups(20NG)和GCAT兩個(gè)短文本數(shù)據(jù)集來評(píng)估基于元路徑集AllPathSim耦合相似性度量方法的有效性和可行性。其中GCAT是從RCV1中選取的部分文檔的集合[20]。每個(gè)數(shù)據(jù)集的文檔個(gè)數(shù),以及提取的特征個(gè)數(shù)和類別個(gè)數(shù)不盡相同。上述兩個(gè)數(shù)據(jù)集基本情況如表1所列。

表1 數(shù)據(jù)集相關(guān)信息

本文采用SICK數(shù)據(jù)集和MSRP數(shù)據(jù)集對(duì)本文提出的基于異質(zhì)信息網(wǎng)絡(luò)的文本相似性度量方法進(jìn)行綜合性評(píng)估。SICK數(shù)據(jù)集[23]包含9 927個(gè)英文句子對(duì),每個(gè)句子對(duì)標(biāo)注有語義關(guān)系和蘊(yùn)含關(guān)系。

MSRP數(shù)據(jù)集[24]包含5 081個(gè)英文句子對(duì),每個(gè)句子對(duì)具有人工注釋,指示每對(duì)句子之間的相關(guān)性。

將世界知識(shí)庫Freebase作為實(shí)體映射的外部知識(shí)庫,Freebase數(shù)據(jù)庫是不同三元組的集合,由不同的實(shí)體和關(guān)系組成。Freebase中包含1 500+種實(shí)體類型和3 500+種關(guān)系類型。將Freebase加載到Virtuoso數(shù)據(jù)庫中,將文本解析后生成的邏輯形式轉(zhuǎn)換為SPARQL查詢,以找到相應(yīng)的實(shí)體類型和關(guān)系類型。

4.2 評(píng)價(jià)指標(biāo)

本文采用相關(guān)系數(shù)作為度量結(jié)果的評(píng)價(jià)指標(biāo)。相關(guān)系數(shù)計(jì)算如式(8)所示。

(8)

另外,為了更直觀地觀察文本相似性度量的有效性,在評(píng)估文本相似性結(jié)果時(shí),往往將文本相似性問題看作文本是否相似的二分類問題。本文將分類實(shí)驗(yàn)中常用的準(zhǔn)確率、召回率和F1-Score作為評(píng)價(jià)本文提出的模型性能的標(biāo)準(zhǔn)。

4.3 實(shí)驗(yàn)

4.3.1 最佳元路徑長度

在異質(zhì)信息網(wǎng)絡(luò)上,利用元路徑進(jìn)行節(jié)點(diǎn)的相似性度量時(shí),較長的路徑并不會(huì)對(duì)結(jié)果產(chǎn)生良好的影響[20]。本文探究了不同的元路徑長度對(duì)文檔相似性度量結(jié)果的影響,分別在20NG和GCAT數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。探究了元路徑長度分別為2、4、6、8時(shí)的相似性度量結(jié)果,如圖4所示。結(jié)果表明,對(duì)稱元路徑長度為4時(shí),相關(guān)系數(shù)最高,相似性度量結(jié)果最好。

圖4 不同元路徑長度對(duì)度量結(jié)果的影響

4.3.2 ω-PageRank-Nibble子圖劃分算法

為了證明基于元路徑的ω-PageRank-Nibble子圖劃分算法的有效性,本文與傳統(tǒng)的PageRank-Nibble算法在20NG數(shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn)。首先,隨機(jī)選取10條對(duì)稱元路徑,如表2所示。然后,針對(duì)每條元路徑,分別采用傳統(tǒng)的PageRank-Nibble算法和ω-PageRank-Nibble子圖劃分算法生成不同的交換矩陣。最后,對(duì)不同方法的交換矩陣進(jìn)行結(jié)果分析。

表2 元路徑示例

圖5 兩種交換矩陣的Frobenius范數(shù)盒圖

通過比較度量結(jié)果的相關(guān)系數(shù),間接證明基于元路徑的ω-PageRank-Nibble子圖劃分算法的有效性。基于上述10條對(duì)稱元路徑,利用兩種不同的子圖劃分算法生成兩種不同的近似交換矩陣,通過AllPathSim方法在20NG數(shù)據(jù)集上得出三種不同的相似性度量結(jié)果。同時(shí),也對(duì)比了三種方法所消耗的空間以及時(shí)間成本,結(jié)果如表3所示。實(shí)驗(yàn)結(jié)果表明,基于元路徑的ω-PageRank-Nibble子圖劃分算法相比于傳統(tǒng)PageRank-Nibble算法與不進(jìn)行剪枝的結(jié)果更為相近,空間成本節(jié)約20.6%,時(shí)間成本節(jié)約20.8%。

表3 不同子圖劃分算法的比較

4.3.3 文本相似性度量

基于異質(zhì)信息網(wǎng)絡(luò)的文本相似性度量方法針對(duì)文本特征稀疏的問題,擴(kuò)大文本特征粒度,結(jié)合外部知識(shí)庫,將單詞或短語粒度擴(kuò)大到實(shí)體類型粒度,提高了度量結(jié)果的準(zhǔn)確性。另外,針對(duì)忽略文本結(jié)構(gòu)特征的問題,本文結(jié)合異質(zhì)信息網(wǎng)絡(luò)的結(jié)構(gòu)特性,將非結(jié)構(gòu)化文本以結(jié)構(gòu)化形式表示出來,充分利用元路徑的豐富語義信息,度量文本的顯式語義相似性,從而增強(qiáng)度量結(jié)果的可解釋性?？偨Y(jié)來說,基于異質(zhì)信息網(wǎng)絡(luò)的文本相似性度量方法從兩個(gè)方面提高了度量結(jié)果的相關(guān)系數(shù)。一是利用異質(zhì)信息網(wǎng)絡(luò)的結(jié)構(gòu)信息、語義信息和鏈接權(quán)重信息。二是擴(kuò)大了文本特征粒度。分別用BOW、Entity和BOW+Entity表示三種不同的文本特征。

BOW傳統(tǒng)的詞袋模型,以文本中的單詞作為文本特征。分別將單詞在文本中的TF值和TF-IDF值作為其權(quán)重。

Entity結(jié)合世界知識(shí)庫提取實(shí)體類型作為文本特征。分別將該實(shí)體在文本中的TF值和TF-IDF值作為其權(quán)重。另外,利用PMI值實(shí)現(xiàn)實(shí)體與實(shí)體之間的鏈接加權(quán)。

BOW+Entity文本中的單詞與不同類型的實(shí)體作為文本的集成特征,分別將單詞或?qū)嶓w在文本中的TF值和TF-IDF值作為該單詞或?qū)嶓w的權(quán)重。

PathSim[22]基于單條元路徑的相同類型節(jié)點(diǎn)的相似性度量方法,度量結(jié)果僅與單條路徑上的實(shí)例個(gè)數(shù)相關(guān)。

KnowSim[20]基于多條元路徑的相同類型節(jié)點(diǎn)的相似性度量方法,度量結(jié)果為多個(gè)PathSim計(jì)算結(jié)果的加權(quán)和。

基于特定元路徑的OnePathSim相似性度量方法,充分利用了元路徑的語義信息并結(jié)合了特定元路徑下的不同路徑實(shí)例的鏈接權(quán)重信息?；谠窂郊腁llPathSim耦合相似性度量方法不僅結(jié)合了鏈接權(quán)重信息,同時(shí)也將不同元路徑間的路徑實(shí)例個(gè)數(shù)作為相似性結(jié)果的影響因子。以BOW+Entity集成文本特征和TF-IDF加權(quán)方法為基礎(chǔ),本文將OnePathSim相似性度量方法、AllPathSim耦合相似性度量方法和與具有代表性的相似性度量方式: Cosine相似性、Jaccard相似性和Dice系數(shù),同時(shí)與PathSim和KnowSim相似性度量方法進(jìn)行了對(duì)比。

圖6表示了不同相似性度量方法在同一文本特征下的相關(guān)系數(shù)。表4匯總了不同特征粒度、不同特征加權(quán)方法的不同相似性度量方法的相關(guān)系數(shù)。由圖6和表4可知,在20NG數(shù)據(jù)集上,OnePathSim相似性度量方法與傳統(tǒng)的度量方法中效果最好的Cosine相似性相比,相關(guān)系數(shù)提高了15.1%;與PathSim度量方法相比,相關(guān)系數(shù)提高了5.2%。在GCAT數(shù)據(jù)集上,與傳統(tǒng)的度量方法中效果最好的Dice系數(shù)相比,相關(guān)系數(shù)提高了16.6%;與PathSim度量方法相比,相關(guān)系數(shù)提高了9.4%。另外,在相同文本特征粒度下,基于特定元路徑的OnePathSim度量方法的相關(guān)系數(shù)低于KnowSim方法,出現(xiàn)此情況的原因是,即使OnePathSim度量方法結(jié)合了異質(zhì)網(wǎng)絡(luò)中的不同類型節(jié)點(diǎn)之間的鏈接權(quán)重信息,但其忽略了其他元路徑的顯式語義信息,所以其度量效果略差于KnowSim方法。AllPathSim耦合相似性度量方法則解決了PathSim和OnePathSim方法的多路徑語義忽略問題,并且結(jié)合了不同節(jié)點(diǎn)間的鏈接關(guān)系,有效提高了度量結(jié)果的相關(guān)系數(shù)。

表4 特征粒度不同的相似性度量方法在20NG和GCAT數(shù)據(jù)集上的相關(guān)系數(shù)

圖6 特征粒度相同的相似性度量方法在20NG和GCAT數(shù)據(jù)集上的相關(guān)系數(shù)

AllPathSim耦合相似性度量方法與傳統(tǒng)的度量方法中效果最好的Cosine相似性相比,相關(guān)系數(shù)提高了23.8%;與KnowSim度量方法相比,相關(guān)系數(shù)提高了6.1%。在GCAT數(shù)據(jù)集上,與傳統(tǒng)的度量方法中效果最好的Dice相似性相比,相關(guān)系數(shù)提高了45.6%;與KnowSim度量方法相比,相關(guān)系數(shù)提高了6.9%。另外,通過將基于元路徑集AllPathSim度量方法與基于特定元路徑的OnePathSim度量方法比較,前者相關(guān)系數(shù)在兩個(gè)數(shù)據(jù)集上都高于后者,證明了對(duì)具有不同路徑實(shí)例數(shù)的元路徑的耦合有效性和可行性。由此分析可知,基于元路徑集的AllPathSim度量方法的度量效果在利用元路徑結(jié)構(gòu)特性、語義特性以及異質(zhì)信息網(wǎng)絡(luò)鏈接權(quán)重方面要優(yōu)于以上其他方法。

為了證明結(jié)合外部知識(shí)庫提取實(shí)體類型,以擴(kuò)大文本特征粒度對(duì)文本相似性度量的重要性,本文從特征粒度和特征權(quán)重兩種不同角度的分別進(jìn)行了實(shí)驗(yàn)分析。本文將BOW、Entity以及BOW+Entity分別作為文本特征,以及利用不同的特征加權(quán)方法進(jìn)行了不同的相似性度量實(shí)驗(yàn)。圖7和圖8分別是具有不同特征粒度的各個(gè)度量算法在20NG和GCAT數(shù)據(jù)集上的相關(guān)系數(shù)。由圖7、圖8分析可知,一方面,在每種不同的相似性度量方法中,當(dāng)以BOW+Entity作為文本的集成特征時(shí),相關(guān)系數(shù)最高,度量結(jié)果最好。另一方面,在每種不同的文本特征基礎(chǔ)上,AllPathSim相似性度量方法的結(jié)果都要優(yōu)于其他的度量方法。另外,相同特征粒度下,以TF-IDF值作為鏈接權(quán)重比單純使用TF值作為權(quán)重,相似性度量效果更好。由此分析可以得出,AllPathSim相似性度量方法,在結(jié)合外部知識(shí)庫中的結(jié)構(gòu)特征,擴(kuò)大文本特征粒度方面比只利用文本中的扁平特征進(jìn)行相似性度量更具有效性。

圖7 不同文本特征的相似性度量方法在20NG上的相關(guān)系數(shù)

圖8 不同文本特征的相似性度量方法在GCAT上的相關(guān)系數(shù)

為了進(jìn)一步評(píng)估基于異質(zhì)信息網(wǎng)絡(luò)的文本相似性度量方法的性能,本文將文本相似性度量問題轉(zhuǎn)化為文本是否相似的二元分類問題,利用4.2節(jié)給出的分類問題中的評(píng)價(jià)指標(biāo)進(jìn)一步評(píng)估本文方法的有效性。本文以經(jīng)驗(yàn)值0.7作為相似度閾值,以單詞和實(shí)體作為文本的集成特征,以TF-IDF加權(quán)方法和PMI單詞關(guān)聯(lián)度量方法作為文本異質(zhì)信息網(wǎng)絡(luò)的鏈接權(quán)重的加權(quán)方法,將本文提出的基于異質(zhì)信息網(wǎng)絡(luò)的文本相似性度量方法(HINSim)分別與不同的隱式語義相似性度量方法進(jìn)行對(duì)比。計(jì)算不同文本相似性度量算法在英語句子對(duì)數(shù)據(jù)集SICK和MSRP上的準(zhǔn)確率、召回率及F1-Score的值,利用上述三個(gè)不同的評(píng)價(jià)指標(biāo)評(píng)估本文度量算法的性能。

LF-LDASim[1]基于LF-LDA主題模型的相似度計(jì)算方法。該模型生成的文本表示向量為服從概率分布的隱藏主題向量。

WMDSim[3]典型的基于詞移距離的文本相似性度量方法。利用文本A中所有的詞語轉(zhuǎn)移到文本B中對(duì)應(yīng)詞語需要的最小距離來度量兩篇文本的相似度。

Word2VecSim+TF-IDF[2]利用Word2Vec模型得到每個(gè)詞的向量表示,利用TF-IDF方法提取出的每個(gè)文本數(shù)據(jù)的關(guān)鍵詞,求其平均值得到每個(gè)文本數(shù)據(jù)的向量表示。

IIGSIFSim[4]基于IIG-SIF句向量的相似度計(jì)算算法。利用特征貢獻(xiàn)度的句向量表示模型將文本中的句子表示為向量形式,計(jì)算向量的余弦相似度作為文本相似性計(jì)算結(jié)果。

表5為五種不同文本相似性度量方法在不同數(shù)據(jù)集上的準(zhǔn)確率、召回率及F1-Score的值。由表5得出,本文提出的基于異質(zhì)信息網(wǎng)絡(luò)的文本相似性度量方法(HINSim)在準(zhǔn)確率、召回率和F1-Score三個(gè)評(píng)價(jià)指標(biāo)上的實(shí)驗(yàn)效果均優(yōu)于其他對(duì)照算法。從五種算法在兩類數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)結(jié)果數(shù)據(jù)來看,在SICK數(shù)據(jù)集上,HINSim模型較其他文本相似性度量算法準(zhǔn)確率提升3.78%～14.68%;召回率提升2.55%～9.5%;F1-Score提升2.63%～10.67%。在MSRP數(shù)據(jù)集上,HINSim模型較其他文本相似性度量算法準(zhǔn)確率提升3.64%～10.09%;召回率提升4.08%～10.55%;F1-Score提升6.62%～12.46%?？傮w而言,基于異質(zhì)信息網(wǎng)絡(luò)的文本顯式語義相似性度量方法與其他四種隱式語義相似性度量方法相比,可以更有效且更準(zhǔn)確地計(jì)算文本之間的相似性。HINSim模型充分考慮了非結(jié)構(gòu)化文本數(shù)據(jù)中的結(jié)構(gòu)化信息,并且為不同的文本特征增加了相應(yīng)的權(quán)重屬性,利用元路徑充分挖掘了文本的語義和結(jié)構(gòu)信息,從而得到準(zhǔn)確且有效的相似性度量結(jié)果。

表5 不同相似性度量方法在SICK和MSRP數(shù)據(jù)集上的準(zhǔn)確率、召回率及F1-Score (單位: %)

5 結(jié)束語

目前現(xiàn)有的文本相似性度量方法側(cè)重于文本中的“扁平特征”,忽略了文本中的結(jié)構(gòu)信息。本文實(shí)現(xiàn)了非結(jié)構(gòu)化文本數(shù)據(jù)的結(jié)構(gòu)化表示,將文本表示為異質(zhì)信息網(wǎng)絡(luò)中的一種特定類型的節(jié)點(diǎn),從而將文本相似性度量問題轉(zhuǎn)化為異質(zhì)信息網(wǎng)絡(luò)上的節(jié)點(diǎn)相似性度量問題,并利用元路徑豐富的語義信息,度量文本類型節(jié)點(diǎn)的顯式語義相似性。首先,結(jié)合豐富的世界知識(shí),生成與領(lǐng)域相關(guān)的特征。將文本特征粒度擴(kuò)大化,從單詞或短語粒度轉(zhuǎn)變?yōu)閷?shí)體類型粒度,提高度量結(jié)果的準(zhǔn)確性。另外,考慮到這些特征對(duì)文本的重要性不同,利用特征加權(quán)方法為其賦予不用的權(quán)重,從而構(gòu)建加權(quán)文本異質(zhì)信息網(wǎng)絡(luò)。其次,采用剪枝策略,實(shí)現(xiàn)對(duì)大規(guī)模異質(zhì)信息網(wǎng)絡(luò)的修剪,提出基于元路徑的ω-PageRank-Nibble算法劃分子圖,節(jié)省存儲(chǔ)空間。根據(jù)子圖,計(jì)算并存儲(chǔ)元路徑的交換矩陣,為相似性度量任務(wù)降低時(shí)間成本,提高度量效率。最后,提出基于元路徑集的AllPathSim耦合相似性度量方法,結(jié)合鏈接權(quán)重信息和不同元路徑下的路徑實(shí)例個(gè)數(shù),綜合度量加權(quán)文本異質(zhì)信息網(wǎng)絡(luò)中的文本節(jié)點(diǎn)的相似性。

雖然基于元路經(jīng)集的AllPathSim耦合相似性度量方法在相同類型節(jié)點(diǎn)的相似性度量方面效果很好,但是元路徑的權(quán)重并沒有通過自學(xué)習(xí)的方式得到。如何通過自學(xué)習(xí)的方法學(xué)習(xí)不同元路徑的權(quán)重,是我們今后的研究方向。