黃大君，王大剛，吳 昊

(合肥師范學(xué)院 計(jì)算機(jī)學(xué)院，安徽 合肥 230601)

1 概述

文檔鏈接分析在社交網(wǎng)絡(luò)、搜索引擎、超鏈接網(wǎng)絡(luò)方面有著廣泛的應(yīng)用。利用預(yù)測(cè)模型可以將網(wǎng)絡(luò)成員指向新朋友，將科學(xué)論文指向相關(guān)引用，并將網(wǎng)頁(yè)指向其他相關(guān)頁(yè)面。國(guó)內(nèi)外學(xué)者在這個(gè)領(lǐng)域相繼提出了許多模型，比較具有代表性的模型是Airoldi等人2008年提出的MMSB[1]模型和主題模型[2-3](Laten Dirichlet Allocation,LDA)。主題模型為這個(gè)領(lǐng)域奠定了一個(gè)理論框架，為文檔之間的相似性引入主題語(yǔ)義層次奠定了基礎(chǔ)。LDA話題模型可以通過推斷的隱藏結(jié)構(gòu)來組成文檔的主題結(jié)構(gòu)。LDA和其他一些話題模型從屬于概率建模領(lǐng)域之下。概率建模領(lǐng)域下生成過程定義了一個(gè)在已觀測(cè)隨機(jī)變量和隱藏隨機(jī)變量之上的聯(lián)合概率分布，通過使用聯(lián)合概率分布來計(jì)算給定觀測(cè)變量值下的隱藏變量的條件分布。

在LDA模型中，假定文檔看成是在主題上的分布，而主題又看成是在相應(yīng)單詞上的分布。LDA是一個(gè)層次概率模型，主題分布在一個(gè)固定的詞匯表上來描述一個(gè)文檔的語(yǔ)料庫(kù)。在其生成過程中，每個(gè)文檔都被賦予一個(gè)Dirichlet[4-6]分布的主題比例向量，文檔中的每個(gè)單詞都是通過從這些比例繪制主題分配，然后從相應(yīng)的主題分布中繪制出單詞來繪制的?；贚DA模型的視角，科研人員將該模型的各種變種加以擴(kuò)展，MMSB模型是應(yīng)用于社交網(wǎng)絡(luò)、超鏈接網(wǎng)絡(luò)中的一個(gè)典型基本框架，該框架基于LDA的理論基礎(chǔ)框架，定義社區(qū)中節(jié)點(diǎn)的交互關(guān)系與概率生成關(guān)系。MMSB模型為了促進(jìn)節(jié)點(diǎn)與社區(qū)之間的一對(duì)多關(guān)系，每個(gè)節(jié)點(diǎn)都有自己的“混合成員分布”，其中與所有其他節(jié)點(diǎn)的關(guān)系由其分布向量來表征，這個(gè)方法描述了扮演多個(gè)角色的對(duì)象之間的交互。在MMSB框架下，描述性統(tǒng)計(jì)可以揭示網(wǎng)絡(luò)數(shù)據(jù)集隱藏的社區(qū)結(jié)構(gòu)。

在這之后的研究中，針對(duì)文本挖掘、超鏈接網(wǎng)絡(luò)領(lǐng)域中又涌現(xiàn)出很多的具體的概率模型結(jié)構(gòu)。關(guān)系主題模型[7](Relational topic model，RTM)由M. BLE于2010年提出用于文檔挖掘的模型，該模型兼顧文檔的屬性信息和鏈接信息，對(duì)新文檔可能的鏈接進(jìn)行預(yù)測(cè)，針于每一對(duì)文件，RTM將其鏈接建模為一個(gè)二進(jìn)制隨機(jī)變量，并以其內(nèi)容為條件，預(yù)測(cè)它們之間的聯(lián)系，并預(yù)測(cè)其中的文字。RTM是網(wǎng)絡(luò)和每節(jié)點(diǎn)屬性數(shù)據(jù)的分層模型。 RTM用于分析鏈接的語(yǔ)料庫(kù)，如引用網(wǎng)絡(luò)，鏈接的網(wǎng)頁(yè)，社交網(wǎng)絡(luò)與用戶配置文件，以及地理標(biāo)記的新聞?！癙airwise Link-LDA”是Nallapati[8]等人2008年提出的模型，它是混合隸屬隨機(jī)塊模型的擴(kuò)展，來建模網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性。模型假定每個(gè)鏈接都是根據(jù)兩個(gè)單獨(dú)的主題生成的從與鏈接的端點(diǎn)關(guān)聯(lián)的主題比例向量中選擇，因?yàn)闈撛诘脑掝}和鏈接是在這個(gè)模型中獨(dú)立繪制的，所以不能保證發(fā)現(xiàn)的話題同時(shí)代表了話語(yǔ)和鏈接，模型結(jié)合了LDA和MMSB(Mixed Membership Stochastic Block )隨機(jī)模型的思想，并允許建模任意鏈接結(jié)構(gòu)，提出了一個(gè)新的折中方案，它結(jié)合了這兩個(gè)模型的最佳性質(zhì)，也明確地模擬了引用文獻(xiàn)和被引用文獻(xiàn)之間的依賴關(guān)系。此外，該模型為每個(gè)鏈路引入了附加的變化參數(shù)，增加了計(jì)算復(fù)雜度。

以上模型都建立在固定主題數(shù)為K的基本假定上，但實(shí)際上文檔的主題是很難預(yù)先確定的，固定主題的假定與事實(shí)是不相符合的。以上模型要么側(cè)重利用內(nèi)容信息預(yù)測(cè)鏈接信息，要么利用鏈接信息預(yù)測(cè)內(nèi)容。在RTM模型中利用主題信息和鏈接共同建模，但建模過程比較復(fù)雜，需要假定預(yù)測(cè)數(shù)據(jù)的形態(tài)分布信息，實(shí)際匹配過程往往也很難做到。

本文重點(diǎn)關(guān)注網(wǎng)絡(luò)文檔鏈接預(yù)測(cè)和主題分析，假定文檔結(jié)構(gòu)基于混合成員文件模型的基礎(chǔ)，每個(gè)文檔都是相關(guān)主題上的混合成員分布，都展示了多項(xiàng)分布或主題的潛在混合。最后我們推導(dǎo)出基于M-H[16-23]的推理和估計(jì)算法。并利用實(shí)驗(yàn)評(píng)估NTM在科學(xué)摘要網(wǎng)絡(luò)，網(wǎng)絡(luò)文件上的預(yù)測(cè)性能。

2 概率圖模型和生成模型

2.1 非參貝葉斯模型分層Dirichlet過程(HDP)

基于LDA模型的簡(jiǎn)單參數(shù)設(shè)定，模型中的主題和單詞的分布均是簡(jiǎn)單的概率分布。HDP 過程是Dirichlet過程混合模型的多層形式，HDP模型相比較LDA 不僅能實(shí)現(xiàn)聚類和推斷等功能，而且能夠自動(dòng)生成聚類數(shù)目，比如我們?cè)谑褂镁垲惙椒╧-means時(shí)，需要指定k的值(聚成k個(gè)簇)；在使用LDA時(shí)需要指定主題的數(shù)目k，但通過HDP這種非參方法，可以不指定k，而是通過數(shù)據(jù)學(xué)習(xí)，自動(dòng)獲取k值，這樣能夠大大增強(qiáng)算法的魯棒性。HDP是一種非參貝葉斯模型，是隨機(jī)過程的應(yīng)用。HDP從一個(gè)隨機(jī)測(cè)度[22]空間中抽樣，首先以基分布H和Concentration 參數(shù)λ構(gòu)成Dirichlet過程，G0～DP(λ,H)，而后以G0為基分布，以α0為Concentration 參數(shù)，對(duì)每對(duì)數(shù)據(jù)構(gòu)造Dirichlet過程混合模型，Gj～DP(α0,G0)。依據(jù)該層Dirichlet過程為先驗(yàn)分布，構(gòu)造Dirichlet過程混合模型。從Dirichlet過程的定義中很難采樣，通?？梢酝ㄟ^Stick-breaking 過程和Chinese restaurant franchise(CRF)兩種方法進(jìn)行構(gòu)造， DP 過程的定義：β|γ～GEM(γ),πj|α0,β～DP(α0,β)

(1)

2.2 關(guān)系主題模型(RTM)

在RTM中，每個(gè)文檔首先由LDA中的主題生成。 然后將文檔之間的鏈接建模為二進(jìn)制變量，每對(duì)文檔一個(gè)。 這些二進(jìn)制變量分配取決于用于生成每個(gè)構(gòu)成文檔的主題。 由于這種依賴性，文檔的內(nèi)容在統(tǒng)計(jì)上與它們之間的鏈接結(jié)構(gòu)相關(guān)。 因此，每個(gè)文檔的混合成員都取決于文檔的內(nèi)容以及鏈接的模式。 反過來，其成員資格相似的文件將更有可能在模型下鏈接。該模型在MMSB塊的基礎(chǔ)上，把文檔的結(jié)構(gòu)和文檔的主題內(nèi)容結(jié)合在一起，共同訓(xùn)練模型，以達(dá)到更好的預(yù)測(cè)未知文檔的鏈接情況。在RTM模型中，作者使用一般廣義指數(shù)分布簇建立主題和分布之間的關(guān)系。建立如下關(guān)系：yd,d′|zd,zd'∝φ(.|zd,zd',η) 。其中φ定義為鏈接密度函數(shù)，該函數(shù)根據(jù)不同數(shù)據(jù)集的分布形態(tài)分別用正態(tài)、指數(shù)、對(duì)數(shù)等概率密度來表達(dá)。節(jié)點(diǎn)d和d’模如果存在鏈接關(guān)系，則yd,d′=1。η用于構(gòu)造一般指數(shù)分布族。模型的概率過程和實(shí)際的訓(xùn)練采樣過程都比較復(fù)雜，且實(shí)際操作過程中很難根據(jù)待預(yù)測(cè)的未知數(shù)據(jù)源來確定具體的指數(shù)簇分布類型。

3 基于非參貝葉斯的文檔關(guān)系模型( NTM)

3.1 NTM模型概率圖和生成模型

HDP是DP過程的兩層形式，本文之所以選擇兩層HDP作為先驗(yàn)概率分布，考慮到網(wǎng)絡(luò)文檔中任意兩個(gè)節(jié)點(diǎn)共享原子節(jié)點(diǎn)，即同一文檔可能屬于不同的文檔集，不同文檔集共享文檔原子節(jié)點(diǎn)，所以從HDP模型的第二層采樣，以便文檔能夠共享原子主題。假定分布不再?gòu)囊粋€(gè)有限的的主題數(shù)為K的分布中采樣，從HDP的第二層采樣，進(jìn)而引入非參假定。為了使得模型能夠針對(duì)一般的未知的數(shù)據(jù)源進(jìn)行預(yù)測(cè)，還需要對(duì)模型進(jìn)行一定程度的簡(jiǎn)化和假設(shè)?；诓蓸拥玫降闹黝}分布向量，計(jì)算文檔之間向量的余弦夾角。利用這個(gè)相似值作為鏈接文檔之間相似性的基本度量單位，該值大小能夠從語(yǔ)義上表示文檔間的相似性大小的相關(guān)關(guān)系。該值作為文檔間鏈接的語(yǔ)義關(guān)聯(lián)依據(jù)，我們認(rèn)為相似度大的文檔之間，鏈接的可能性越大，隨后在概率圖的基礎(chǔ)上，利用貝葉斯關(guān)系，通過數(shù)據(jù)來學(xué)習(xí)分布參數(shù)。

圖1 NTM概率圖模型

此處的{πi}1:n為混合成員分布，網(wǎng)絡(luò)中單個(gè)文檔可能具有屬于多個(gè)文檔集的屬性，如同一個(gè)人可以參加多個(gè)社區(qū)活動(dòng)，即同時(shí)具有屬于多個(gè)社區(qū)的屬性。其中{πi}1:n的先驗(yàn)概率分布存在以下關(guān)系:

(2)

從隨機(jī)側(cè)度中采樣出來的{πi}1:n是個(gè)K維的Dirichlet向量，反映網(wǎng)絡(luò)數(shù)據(jù)集中的文檔的主題分布，對(duì)向量求余弦夾角得到它們之間的相似度，這個(gè)值大小與未來兩個(gè)文檔間可能存在的鏈接關(guān)系存在某種程度的正相關(guān)，定義函數(shù)f，對(duì)f進(jìn)行二值采樣，利用數(shù)據(jù)來學(xué)習(xí)模型。

NTM生成模型表示如下:

β～GEM(γ)

Zd,n|πd～mul(πd)

y|πd,πd′～bernoulli(f)

cos(πd,πd′)∈(0,1)

(3)

3.2 NTM模型的參數(shù)采樣

3.2.1 采樣πi

定義轉(zhuǎn)移概率為獨(dú)立鏈方式

經(jīng)整合后，消元

(4)

3.2.2 采樣

β的先驗(yàn)p(β/γ)=GEM(γ)， 在文獻(xiàn)[14]中指出，通過增加輔助變量得到：

可以增加接下來的接受率：

其中p(mik=m|Nik,α,βk)∝S(Nik,m)(αβk)m

S(Nik,m)為第一類Stirling 數(shù)。

定義:Α(β，β*)=min(1,a)

提議分布采樣獨(dú)立鏈方式得到：

(5)

這樣得到采樣β的接受率:

(6)

3.2.3 采樣Ζd,n,Ζd′n

推導(dǎo)出Ζd,n，Ζd′n的適合Gibbs采樣的條件概率。

p(zd,n=k,zd′,n=l|Z{zd,n=k,zd′,n=l},W,α,β,η,y)=p(zd,n=k,zd′,n=l|Z{zd,n=k,zd′,n=l},α,β)

p(zd,n=k,zd′,n=l|Z{zd,n=k,zd′,n=l},W,α,β,η,y)=p(zd,n=k,zd′,n=l|Z{zd,n=k,zd′,n=l},α,β)

*p(Wd,n,Wd′,n|W{Wd,n,Wd′,n},(zd,n=k,zd′,n=l),Z{zd,n=k,zd′,n=l},η}

*p(yd,d'|(zd,n=k,zd′,n=l),Z{zd,n=k,zd′,n=l},α,β,y{yd,d′})

p(Wd,n,Wd′,n|W{Wd,n,Wd′,n},(zd,n=k,zd′,n=l),Z{zd,n=k,zd′,n=l},η}

p(yd,d'|(zd,n=k,zd′,n=l),α,β)

∝p(yd,d'|(πd=k,πd′=l),α,β)

(7)

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

4.1 RTM模型和NTM模型比較

本文采用基于鏈接與文本屬性的數(shù)據(jù)集CiteSeer來發(fā)現(xiàn)和對(duì)比UTM和RTM模型的鏈接結(jié)果和鏈接質(zhì)量。CiteSeer數(shù)據(jù)集由3312種科學(xué)出版物組成，分為六類中的一種。 引文網(wǎng)絡(luò)由4732個(gè)鏈接組成。 數(shù)據(jù)集中的每個(gè)出版物由0/1值單詞向量描述，指示字典中相應(yīng)單詞的不存在/存在。 該詞典由3703個(gè)獨(dú)特單詞組成。該目錄包含CiteSeer數(shù)據(jù)集的選擇。這些論文集由六個(gè)類別組成，包括人工智能，數(shù)據(jù)挖掘 ，數(shù)據(jù)庫(kù)，模式識(shí)別等。這些論文的選擇方式使得在最終的語(yǔ)料庫(kù)中，每篇論文引用或引用至少另一篇論文。整個(gè)語(yǔ)料庫(kù)在阻止和刪除停用詞后，留下了3703個(gè)獨(dú)特單詞的詞匯量。文檔頻率小于10的所有單詞都被刪除。在CiteSeer運(yùn)行本文的模型和RTM模型，對(duì)數(shù)據(jù)集采用10倍交叉驗(yàn)證，對(duì)其中一個(gè)驗(yàn)證集，運(yùn)行模型得到圖3和表3的結(jié)果。

實(shí)驗(yàn)環(huán)是Win7系統(tǒng)，Python 2.7編程環(huán)境。采樣過程的提議分布采用獨(dú)立鏈的方法，所以必須選擇合適的迭代次數(shù)和步長(zhǎng)，經(jīng)過對(duì)多次試驗(yàn)結(jié)果的觀察和嘗試，對(duì)迭代次數(shù)選擇14000，迭代的步長(zhǎng)設(shè)置為0.5，保證能夠在有限次迭代次數(shù)和時(shí)間下得到比較好的仿真圖，圖2 是仿真的結(jié)果圖。運(yùn)行MCMC采樣器過程中，一般而言，不希望寬度過窄，因?yàn)槌闃有什桓撸瑫r(shí)需要很長(zhǎng)時(shí)間才能探索整個(gè)參數(shù)空間并顯示典型的隨機(jī)游動(dòng)行為，但也不希望它太大，以至于永遠(yuǎn)不會(huì)接受跳躍。圖2是RTM模型和NTM模型在似然函數(shù)上比較圖，將提案寬度設(shè)置為0.5?？梢钥吹絅TM模型收斂的似然值要高于RTM模的似然值。

圖2 RTM模型和NTM模型在似然函數(shù)上比較圖

表1 RTM模型和NTM模型鏈接預(yù)測(cè)表現(xiàn)

在6大類文章類型中，其中10個(gè)主題作為模型比較范圍，選擇訓(xùn)練集中的Dynamic Infinite Mixed-Membership Stochastic Blockmodel文檔，表3的結(jié)果是模型測(cè)試集上前6個(gè)鏈接預(yù)測(cè)表現(xiàn)，從表1中可以看出UTM模型識(shí)別出來的有效文檔是3個(gè)，相比RTM模型識(shí)別的有效文檔是2個(gè)。針對(duì)本次發(fā)現(xiàn)可以看出，UTM模型能夠準(zhǔn)確把握關(guān)鍵詞Mixed-membership，能夠在整個(gè)文本潛在空間上發(fā)現(xiàn)語(yǔ)義關(guān)聯(lián)。注意觀察RTM的部分結(jié)果，給出的建議鏈接是針對(duì)文檔題目的字典單詞相似度而非在整個(gè)引文數(shù)據(jù)庫(kù)中的結(jié)構(gòu)語(yǔ)義。一般而言，您不希望寬度過窄，因?yàn)槟某闃有什桓?，因?yàn)樾枰荛L(zhǎng)時(shí)間才能探索整個(gè)參數(shù)空間并顯示典型的隨機(jī)游動(dòng)行為，但你也不希望它太大以至于你永遠(yuǎn)不會(huì)接受跳躍。

4.2 多數(shù)據(jù)源綜合實(shí)驗(yàn)

用不同的模型在相同的仿真數(shù)據(jù)集上做出了部分定性和定量的比較分析，在實(shí)際網(wǎng)絡(luò)實(shí)驗(yàn)數(shù)據(jù)集中，需要對(duì)不同算法在不同數(shù)據(jù)集上的表現(xiàn)性能做全面的分析，從而判斷算法的優(yōu)越性。選擇3個(gè)真實(shí)世界數(shù)據(jù)集進(jìn)行基準(zhǔn)測(cè)試。分別是 Cora、WebKB、PNAS。Cora數(shù)據(jù)包含來自Cora計(jì)算機(jī)科學(xué)研究論文搜索引擎的摘要，以及相互引用的文檔之間的鏈接。WebKB數(shù)據(jù)包含來自不同的大學(xué)計(jì)算機(jī)科學(xué)系的網(wǎng)頁(yè)，網(wǎng)頁(yè)上的超鏈接關(guān)系標(biāo)注了網(wǎng)頁(yè)文檔間的鏈接。PNAS數(shù)據(jù)包含來自美國(guó)國(guó)家科學(xué)院院刊的最新摘要，文件之間的鏈接是PNAS內(nèi)部引用。

表2 數(shù)據(jù)集的統(tǒng)計(jì)摘要

將MMSB，RTM，本文的NTM算法，在三個(gè)實(shí)際數(shù)據(jù)集上驗(yàn)證，其中MMSB，RTM算法利用所給文獻(xiàn)公布的代碼進(jìn)行仿真，三個(gè)數(shù)據(jù)集上檢查了“和”“的”或“但是”這樣的詞，以及不經(jīng)常出現(xiàn)的詞被刪除。定向鏈接轉(zhuǎn)換為無向鏈接，沒有鏈接的文檔被刪除。

表3 各模型性能比較

其中Train err和Test err的值是1000迭代的結(jié)果的平均值，發(fā)現(xiàn)在迭代過程中，Train err的值隨著發(fā)現(xiàn)聚類個(gè)數(shù)K的值有比較平穩(wěn)的變化，Test err的值有降低的變化趨勢(shì)。 算法在數(shù)據(jù)集WebKB 上的Train err 的值表現(xiàn)比其它算法較差，原因大概是由于WebKB在數(shù)據(jù)量較小時(shí)，部門之間的相關(guān)性表現(xiàn)較差，NTM的相關(guān)性發(fā)現(xiàn)不能充分有效。而我們的值是前1000次的平均，所以可看到整體表現(xiàn)較差。表3中NTM算法的Test loglikelood 相比其他算法有非常明顯優(yōu)勢(shì)，原因應(yīng)該是采用了非參的假定，數(shù)據(jù)根據(jù)自身的表現(xiàn)在迭代過程中自動(dòng)發(fā)現(xiàn)聚類的K值，從而對(duì)數(shù)據(jù)集中的數(shù)據(jù)來說能夠獲得較大的數(shù)據(jù)似然值的支持，而其它三種算法都是基于固定值的假設(shè)，所以實(shí)際聚類值與假定的一定存在差距，從而導(dǎo)致較差的Test loglikelood(表中采用的是負(fù)對(duì)數(shù)值)。AUC 值通常小于0.7是比較差的，大于0.9是比較好的結(jié)果，從表3的結(jié)果來看，NTM在三個(gè)數(shù)據(jù)集上都取得了較好的效果。從訓(xùn)練誤差，測(cè)試誤差，測(cè)試用例的對(duì)數(shù)似然和AUC四個(gè)指標(biāo)上對(duì)上述3種模型進(jìn)行對(duì)比分析，從表3中可以看出整體上分析來看，在全部三個(gè)數(shù)據(jù)集上NTM比其它兩個(gè)模型都有更好的性能表現(xiàn)。

5 總結(jié)

模型在社交網(wǎng)絡(luò)和文本關(guān)系發(fā)現(xiàn)領(lǐng)域有重要的應(yīng)用價(jià)值，本文定義了一個(gè)非參數(shù)的概率圖模型，將非參數(shù)貝葉斯先驗(yàn)(即DP過程的先驗(yàn)假定)結(jié)合到模型中將允許它靈活地調(diào)整主題數(shù)量與數(shù)據(jù)。模型綜合考慮節(jié)點(diǎn)的主題和鏈接信息，定義聯(lián)合分布，給出了一個(gè)MCMC框架的參數(shù)推理算法，合成數(shù)據(jù)集和現(xiàn)實(shí)世界數(shù)據(jù)集實(shí)驗(yàn)證明了我們的方法能夠推斷出隱藏的主題及其數(shù)量，相比已有模型能夠更好的進(jìn)行未知文檔和潛在鏈接結(jié)構(gòu)的預(yù)測(cè)，提供有關(guān)網(wǎng)絡(luò)潛在成員結(jié)構(gòu)的新見解。在參數(shù)推理中，給出了具體的推理步驟和推理算法。