伍杰華 熊云艷

1(廣東工貿(mào)職業(yè)技術(shù)學(xué)院計(jì)算機(jī)與信息工程學(xué)院 廣東 廣州 510510)2(華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 廣東 廣州 510641)

0 引 言

信息網(wǎng)絡(luò)是一種基于實(shí)體和實(shí)體之間紛繁復(fù)雜互聯(lián)關(guān)系組成的網(wǎng)絡(luò)結(jié)構(gòu)[1]。各實(shí)體通過(guò)信息網(wǎng)絡(luò)實(shí)現(xiàn)信息的傳遞、傳播和交互。比較常見(jiàn)的信息網(wǎng)絡(luò)有科研學(xué)術(shù)合作網(wǎng)絡(luò)[2]、社交媒體網(wǎng)絡(luò)[3]、生物蛋白質(zhì)功能網(wǎng)絡(luò)[4]等。由于實(shí)體之間關(guān)系是信息傳播之間的橋梁，因此對(duì)關(guān)系的分析與研究顯得非常重要[5]，其中一個(gè)主要的研究方向是關(guān)系預(yù)測(cè)與推斷(又稱(chēng)鏈接預(yù)測(cè)或者關(guān)系分類(lèi)與推斷)[6]。該技術(shù)的核心思想是根據(jù)當(dāng)前信息網(wǎng)絡(luò)的結(jié)構(gòu)信息預(yù)測(cè)尚未存在關(guān)系的實(shí)體之間產(chǎn)生關(guān)系的可能性。它首先能夠從理論層面幫助深入理解信息網(wǎng)絡(luò)的演化機(jī)制和信息傳播機(jī)制[7]，例如社交網(wǎng)絡(luò)中的消息(信息)傳播機(jī)制的本質(zhì)是把人與人之間的互聯(lián)關(guān)系引入到傳播過(guò)程當(dāng)中，因此該互聯(lián)的社交關(guān)系直接影響信息傳播效果及范圍。例如，謠言、傳聞、流言的傳播是目前社交媒體或者社會(huì)網(wǎng)絡(luò)領(lǐng)域中危害社會(huì)穩(wěn)定和安全的垃圾信息，通過(guò)關(guān)系預(yù)測(cè)結(jié)合影響力節(jié)點(diǎn)分析等其他社交網(wǎng)絡(luò)分析技術(shù)，我們能夠進(jìn)一步深入揭示謠言在用戶之間的傳播方式和整個(gè)網(wǎng)絡(luò)的實(shí)體關(guān)系及其演化機(jī)制，從而有助于更好地找到謠言發(fā)起的源頭、散步的規(guī)律，協(xié)助治理網(wǎng)絡(luò)安全。此外，該技術(shù)在應(yīng)用領(lǐng)域也有廣泛的應(yīng)用前景。例如知識(shí)圖譜中實(shí)體之間的關(guān)系預(yù)測(cè)[8]。知識(shí)圖譜是一種基于語(yǔ)義信息并描述實(shí)體與實(shí)體之間關(guān)系的異質(zhì)結(jié)構(gòu)。它能把不同知識(shí)領(lǐng)域的多維度的關(guān)系網(wǎng)絡(luò)。關(guān)系預(yù)測(cè)技術(shù)有助于實(shí)現(xiàn)知識(shí)圖譜實(shí)體之間關(guān)系的學(xué)習(xí)、融合以及推理，并為其實(shí)體關(guān)系進(jìn)行標(biāo)注，在新聞事件的關(guān)聯(lián)分析、識(shí)別反欺詐潛在風(fēng)險(xiǎn)、失聯(lián)客戶管理和謠言識(shí)別等眾多領(lǐng)域有重要的應(yīng)用價(jià)值。

圖1 算法模型

1 相關(guān)工作

預(yù)測(cè)，在一定程度上是個(gè)概率計(jì)算問(wèn)題。即通過(guò)計(jì)算兩潛在實(shí)體之間產(chǎn)生關(guān)系的概率來(lái)進(jìn)行推斷。由于該概率可通過(guò)挖掘網(wǎng)絡(luò)結(jié)構(gòu)信息直接計(jì)算或構(gòu)建概率模型學(xué)習(xí)獲得，因此關(guān)系預(yù)測(cè)與推斷算法主要分為基于概率相似度和基于學(xué)習(xí)思想兩大類(lèi)[9]。第一類(lèi)算法把概率視為兩潛在實(shí)體之間的相似度，并通過(guò)信息網(wǎng)絡(luò)節(jié)點(diǎn)、路徑、社區(qū)、鄰接矩陣等拓?fù)浣Y(jié)構(gòu)或網(wǎng)絡(luò)表示結(jié)構(gòu)計(jì)算該相似度,其原理簡(jiǎn)單，一直是研究的主流。但是本文主要介紹的是基于學(xué)習(xí)思想的算法，因此對(duì)于第一類(lèi)算法的相關(guān)工作就不作詳細(xì)敘述，可參考相關(guān)綜述[9-10]。近幾年來(lái)，隨著機(jī)器學(xué)習(xí)理論的飛速發(fā)展，一些新技術(shù)、新方法不斷提出，這些研究為第二類(lèi)基于統(tǒng)計(jì)機(jī)器學(xué)習(xí)技術(shù)的關(guān)系預(yù)測(cè)奠定了基礎(chǔ)。該類(lèi)算法的主要思想是根據(jù)社交網(wǎng)絡(luò)結(jié)構(gòu)提取特征并建立一個(gè)適合的模型，采用統(tǒng)計(jì)方法估計(jì)模型的參數(shù)，然后通過(guò)參數(shù)進(jìn)行類(lèi)別判斷和最優(yōu)化推斷等。其研究思路主要分為以下幾個(gè)方面：基于特征學(xué)習(xí)的分類(lèi)算法、基于概率圖(層次圖)模型的算法、基于矩陣分解和補(bǔ)全算法和基于網(wǎng)絡(luò)表示學(xué)習(xí)與嵌入的算法等。(1) 基于特征學(xué)習(xí)的分類(lèi)算法。該類(lèi)算法假設(shè)潛在鏈接的形成與否受到與其相關(guān)聯(lián)的特征空間的影響，并把鏈接形成與否視為一個(gè)二分類(lèi)問(wèn)題。文獻(xiàn)[11]首先把鏈接預(yù)測(cè)變成給定特征下的兩分類(lèi)問(wèn)題，并比較了多個(gè)監(jiān)督學(xué)習(xí)算法的性能。文獻(xiàn)[12]提出了一種高性能的基于流信息采用基于Bagging和Random Forest的分類(lèi)模型，該模型有效地解決了分類(lèi)中的不平衡問(wèn)題。文獻(xiàn)[13]提出了一個(gè)面向微博社交網(wǎng)絡(luò)的預(yù)測(cè)算法。該算法從多個(gè)層面收集了網(wǎng)絡(luò)中基于節(jié)點(diǎn)、拓?fù)浣Y(jié)構(gòu)、投票和社交信息等信息構(gòu)建特征，采用SVM等多種方法有效地進(jìn)行鏈接分類(lèi)。(2) 基于概率圖(層次圖)模型的算法。該類(lèi)算法的主要思想在于兩個(gè)節(jié)點(diǎn)之間鏈接形成的概率取決于它們從屬的層次、社區(qū)或者塊信息。文獻(xiàn)[14]認(rèn)為鏈接可以看作社交網(wǎng)絡(luò)內(nèi)在的層次結(jié)構(gòu)的反映，并提出了一種挖掘網(wǎng)絡(luò)層次結(jié)構(gòu)的最大似然估計(jì)的算法。文獻(xiàn)[15]通過(guò)引入高斯過(guò)程，提出了一種基于隨機(jī)關(guān)系模型(Stochastic Relational Models，SRM)的鏈接預(yù)測(cè)算法。該算法的關(guān)鍵思想在于通過(guò)多重高斯過(guò)程的張量相互作用對(duì)隨機(jī)實(shí)體關(guān)系結(jié)構(gòu)建模。文獻(xiàn)[16]結(jié)合信息網(wǎng)絡(luò)另外的一個(gè)熱門(mén)研究領(lǐng)域-社區(qū)劃分，把關(guān)系預(yù)測(cè)的問(wèn)題從判斷鏈接是否存在變成在一個(gè)社區(qū)劃分網(wǎng)絡(luò)下，已存在網(wǎng)絡(luò)結(jié)構(gòu)中不同類(lèi)型的關(guān)系生成最大化推斷問(wèn)題，提出了一種平衡度模塊度最大化的模型(Modularity Maximization Link Prediction Model, MMLP)。

但是上述算法依然存在通用的問(wèn)題，因?yàn)樗鼈儍H僅考慮了如何建立模型提高對(duì)特征的學(xué)習(xí)，而忽略了特征之間存在的關(guān)聯(lián)會(huì)影響學(xué)習(xí)與分類(lèi)的性能。在分類(lèi)問(wèn)題中，特征是決定分類(lèi)性能最重要的因素。但是由于獲取的原始特征不一定能夠準(zhǔn)確反映待分類(lèi)對(duì)象的本質(zhì)特征，樣本也可能比較稀疏，計(jì)算量大，不利于高效的分類(lèi)；同時(shí)高維的原始特征存在冗余信息，不做分析直接用于分類(lèi)會(huì)存在“維度災(zāi)難”，影響分類(lèi)性能。

針對(duì)原始信息網(wǎng)絡(luò)特征存在的不足，同時(shí)彌補(bǔ)上述算法在特征提取過(guò)程當(dāng)中難以兼顧類(lèi)型、數(shù)量及缺乏特征選擇過(guò)程，本文提出一個(gè)結(jié)合最大似然互信息特征選擇的信息網(wǎng)絡(luò)關(guān)系預(yù)測(cè)算法。具體來(lái)說(shuō)，算法首先基于相似度預(yù)測(cè)指標(biāo)提取了局部和全局(半局部)兩類(lèi)特征，然后極大似然推斷最大化特征之間互信息，對(duì)特征的重要性進(jìn)行排序，根據(jù)排序選擇最具影響力的特征進(jìn)行分類(lèi)。算法的主要貢獻(xiàn)如下：

(1) 結(jié)合最大似然理論計(jì)算互信息，有效地篩選最具判別性特征，提高了學(xué)習(xí)和預(yù)測(cè)效率。

(2) 把提出的特征選擇算法嵌入到基于特征學(xué)習(xí)的分類(lèi)算法和新提出的基于概率圖(層次圖)模型中，在多個(gè)真實(shí)信息網(wǎng)絡(luò)數(shù)據(jù)集的結(jié)果表明，分類(lèi)性能得到提高，特性選擇步驟是必要的。

2 特征提取

2.1 問(wèn)題定義

基于分類(lèi)理論的關(guān)系預(yù)測(cè)算法。該類(lèi)方法把關(guān)系預(yù)測(cè)問(wèn)題看成是一個(gè)標(biāo)簽預(yù)測(cè)問(wèn)題(Label Prediction)，其中存在的和不存在的關(guān)系分別被標(biāo)記為正例和負(fù)例?；蛘甙褑?wèn)題看成存在概率P(e∈G)的估計(jì)問(wèn)題，然后建立一個(gè)預(yù)測(cè)模型M和獲取影響鏈接生成的特征空間和參數(shù)空間θ，并通過(guò)分類(lèi)、優(yōu)化等理論與方法計(jì)算該概率。概率越高，關(guān)系生成的概率越大。具體的函數(shù)映射如下：

fM(GT,,θ)→{0,1}

(1)

式中：0表示潛在節(jié)點(diǎn)之間不存在鏈接，1則表示存在鏈接。M指預(yù)測(cè)模型，GT是訓(xùn)練集網(wǎng)絡(luò)。

2.2 局部與全局特征提取

2.2.1局部特征

在信息網(wǎng)絡(luò)關(guān)系分類(lèi)領(lǐng)域，鄰接節(jié)點(diǎn)指和指定和潛在節(jié)點(diǎn)i存在直接鏈接關(guān)系的節(jié)點(diǎn)集合，記為N(i)。節(jié)點(diǎn)i的d路徑內(nèi)鄰居(或者指d條鏈接內(nèi)可達(dá)到)是指i在d步路徑之內(nèi)能達(dá)到的節(jié)點(diǎn)j的集合，記為N(i,d)。如果V是一個(gè)節(jié)點(diǎn)集合，那么N(V,d)是指V中節(jié)點(diǎn)在d步路徑之內(nèi)能達(dá)到的節(jié)點(diǎn)集合。由于該節(jié)點(diǎn)集合的信息對(duì)于潛在節(jié)點(diǎn)對(duì)是否存在關(guān)系的影響是最直觀的，因此局部結(jié)構(gòu)或者局部性(locality)一般表示在1～3步路徑內(nèi)的節(jié)點(diǎn)集合。由于定義信息網(wǎng)絡(luò)結(jié)構(gòu)特征的指標(biāo)有非常多，文中選擇了5個(gè)典型具有代表性的指標(biāo)構(gòu)建局部特征集合L：

CommonNeighbors(CN)[6]:CN相似度指標(biāo)(在文中指標(biāo)也可稱(chēng)為方法、算法)是鏈接預(yù)測(cè)中最直觀、最簡(jiǎn)單的相似度計(jì)算方法。假設(shè)兩個(gè)潛在節(jié)點(diǎn)對(duì)擁有的共鄰節(jié)點(diǎn)數(shù)目越多，它們之間產(chǎn)生鏈接的概率就越高。公式如下：

CN(i,j)=|N(i)∩N(j)|

(2)

式中：N(i)指所有與節(jié)點(diǎn)i相鄰的節(jié)點(diǎn)的集合。

Adamic-Adar(AA)[17]:該指標(biāo)通過(guò)對(duì)每個(gè)共鄰節(jié)點(diǎn)的不同度的對(duì)數(shù)值差分化處理不同共鄰節(jié)點(diǎn)的角色和貢獻(xiàn)，度大的共鄰節(jié)點(diǎn)貢獻(xiàn)小于度小的共鄰節(jié)點(diǎn)。其公式如下：

(3)

PreferentialAttachment(PA)[18]:該指標(biāo)主要反映網(wǎng)絡(luò)中的偏好性生成機(jī)制，即節(jié)點(diǎn)的度越大，其吸引其余節(jié)點(diǎn)產(chǎn)生關(guān)系的可能性越高。公式如下：

PA(i,j)=|N(i)|×|N(j)|

(4)

JaccardCoefficient(JC)[6]:JC指標(biāo)不僅考慮了預(yù)測(cè)節(jié)點(diǎn)對(duì)的共鄰節(jié)點(diǎn)數(shù)目，它還考慮了共鄰節(jié)點(diǎn)在兩個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合中所占的比率。公式如下：

(5)

ClusterCoefficient[18]:聚類(lèi)系數(shù)表示節(jié)點(diǎn)鄰接節(jié)點(diǎn)之間鏈接的密集程度，該指標(biāo)取共鄰節(jié)點(diǎn)聚類(lèi)系數(shù)的和。公式如下：

(6)

式中：cω表示共鄰節(jié)點(diǎn)ω的聚類(lèi)系數(shù)。

2.2.2全局(半全局)特征

基于局部特征算法主要考慮局部拓?fù)浣Y(jié)構(gòu)屬性，相應(yīng)的指標(biāo)所需的信息量少、算法簡(jiǎn)單、時(shí)間復(fù)雜度低，運(yùn)行速度快，適用于小規(guī)模的網(wǎng)絡(luò)關(guān)系預(yù)測(cè)任務(wù)。但是局部拓?fù)浣Y(jié)構(gòu)屬性不能夠深層次反映兩節(jié)點(diǎn)之間的隱含屬性，也不能反映整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)對(duì)潛在預(yù)測(cè)節(jié)點(diǎn)的影響。基于上述兩個(gè)原因，一部分相似度特征指標(biāo)的構(gòu)建工作基于路徑或者基于隨機(jī)游走展開(kāi)(由于該過(guò)程取決于網(wǎng)絡(luò)的結(jié)構(gòu)，因此可能是全局的，也可能是半全局的，但后續(xù)均統(tǒng)稱(chēng)為全局特征)。因此，文中選擇了5個(gè)典型的指標(biāo)構(gòu)建全局特征集合G：

LocalPath(LP)[19]:為了避免僅僅考慮共鄰節(jié)點(diǎn)結(jié)構(gòu)而導(dǎo)致的精確度以及區(qū)分度過(guò)低等問(wèn)題，局部路徑指標(biāo)額外考慮了三階路徑的影響。公式如下：

LP(u,v)=(D2)u,v+α(D3)u,v

(7)

式中：α是權(quán)重參數(shù)，D是圖矩陣，Du,v表示節(jié)點(diǎn)對(duì)u、v之間的一步路徑，則是兩步路徑，(D2)u,v以此類(lèi)推。當(dāng)α=0時(shí)，LP(u,v)=(D2)u,v相似度指標(biāo)變成只考慮共同鄰居節(jié)點(diǎn)的影響，此時(shí)LP就是CN。

Katz[20]:根據(jù)局部路徑指標(biāo)可知，如果想要將網(wǎng)絡(luò)結(jié)構(gòu)的影響因素更全面地考慮進(jìn)來(lái)，同時(shí)更進(jìn)一步地提高計(jì)算精度，可以將四階路徑、五階路徑、乃至n階路徑考慮進(jìn)來(lái)。當(dāng)n→∞時(shí)，相似度計(jì)算將全局網(wǎng)絡(luò)路徑均考慮在內(nèi)，此時(shí)的相似度指標(biāo)就相當(dāng)于Katz指標(biāo)。公式如下：

Katz(u,v)=(I-αD)-1-I

(8)

式中：I是單位矩陣，該算法將所有對(duì)節(jié)點(diǎn)間產(chǎn)生影響的路徑信息都考慮進(jìn)來(lái)了。

RandomWalkwithRestart(RWR)[21]:該指標(biāo)基于一個(gè)物理意義上的假設(shè)：隨機(jī)游走的粒子會(huì)以一定的概率返回起始位置，其中元素πuv表示從節(jié)點(diǎn)u走到v的概率。公式如下：

RWR(u,v)=πuv+πvu

(9)

同時(shí)，基于隨機(jī)游走還選取了SRW和LRW兩個(gè)指標(biāo)作為全局特征，由于版面關(guān)系，在此不再詳細(xì)敘述。

3 算法框架

在基于信息網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)系預(yù)測(cè)或者分類(lèi)算法的相關(guān)工作中，所提取的相似度特征一般均基于節(jié)點(diǎn)、共鄰節(jié)點(diǎn)或者相關(guān)路徑等信息構(gòu)建，因此特征之間會(huì)存在相似的信息，直接用作分類(lèi)和推斷優(yōu)化會(huì)保留特征之間的噪音和冗余信息。因此，本文的核心思想在于考慮能否運(yùn)用機(jī)器學(xué)習(xí)特征工程領(lǐng)域的特征選擇技術(shù)篩選出具備最優(yōu)判別性的特征幫助分類(lèi)——即特征選擇。特征選擇技術(shù)指在未處理的特征空間中通過(guò)指定的標(biāo)準(zhǔn)篩選出一組具備最佳分類(lèi)性能的特征子集的過(guò)程[22]，該過(guò)程有助于刪除特征間冗余信息和不相關(guān)的特征。

3.1 最大似然互信息特征選擇

在面向特征選擇的信息論中，兩個(gè)隨機(jī)變量的互信息(Mutual Information，MI)[23]定義變量間相互依賴(lài)性的量度。在分類(lèi)問(wèn)題中，特征和類(lèi)別之間的相互信息體現(xiàn)了特征和類(lèi)別的相關(guān)程度，即可以評(píng)價(jià)特征對(duì)于分類(lèi)效果貢獻(xiàn)。因此，估計(jì)特征和類(lèi)別之間的MI在特征選擇領(lǐng)域多年來(lái)一直備受關(guān)注，在度量特征之間的關(guān)系和輔助特征選擇上有重要的意義。因此，使用互信息理論對(duì)特征進(jìn)行選擇和提取基于如下假設(shè)：特征在某個(gè)類(lèi)別出現(xiàn)的頻率高，但是其他出現(xiàn)的頻率低，可以認(rèn)為該特征和類(lèi)別的互信息比較大。所以如何計(jì)算MI是其中的關(guān)鍵問(wèn)題。MI可以定義為：

(10)

然而對(duì)上述公式中的密度進(jìn)行估計(jì)是一個(gè)比較困難的問(wèn)題。因?yàn)楣烙?jì)密度的劃分涉及到MI的逼近，容易使估計(jì)誤差放大。一部分工作例如用k近鄰(KNN)方法估計(jì)熵算法嘗試適當(dāng)?shù)卮_定k的值以使偏方差權(quán)衡得到最優(yōu)，但是該步驟在MI估計(jì)的上下文中的實(shí)現(xiàn)并不簡(jiǎn)單。當(dāng)目標(biāo)密度接近正態(tài)分布時(shí)，計(jì)算邊緣分布的方法效果較好；否則，它是有偏差的和不可靠的。針對(duì)計(jì)算互信息存在的問(wèn)題，本文提出了一種稱(chēng)為最大似然互信息(Maximum Likelihood Mutual Information，MLMI)新的MI估計(jì)方法[24]。該方法的優(yōu)點(diǎn)在于不涉及密度估計(jì)，直接對(duì)密度比建模：

(11)

(12)

然后用以下線性模型對(duì)密度比函數(shù)w(x,y)建模:

(13)

式中：α:=(α1,α2,…,αb)T是需要從樣本中學(xué)習(xí)的參數(shù)。φ(x,y):=(φ1(x,y),φ2(x,y),…,φb(x,y)T則是偏差函數(shù)。

(14)

(15)

(16)

(17)

現(xiàn)在我們的優(yōu)化準(zhǔn)則總結(jié)如下：

在估計(jì)密度函數(shù)之后以互信息作為提取特征的評(píng)價(jià)選擇互信息最大的N個(gè)特征進(jìn)行分類(lèi)。

3.2 基于MLMI的關(guān)系預(yù)測(cè)

整個(gè)算法框架如下所示：

Input：網(wǎng)絡(luò)G=(V,E)

Output：Accuracy AUC Precision Recall F1

1: 對(duì)G劃分為訓(xùn)練網(wǎng)絡(luò)GT和預(yù)測(cè)網(wǎng)絡(luò)GP

2:forGT和GP中的每一條存在或不存在關(guān)系do

4:endfor

7: 采用優(yōu)化準(zhǔn)則公式推斷參數(shù)

9: 采用NB，SVM和RF進(jìn)行分類(lèi)

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

4.1 實(shí)驗(yàn)設(shè)置

根據(jù)關(guān)系分類(lèi)算法遵循圖1的過(guò)程：按照比例r(默認(rèn)設(shè)置為0.9)把網(wǎng)絡(luò)劃分為訓(xùn)練網(wǎng)絡(luò)和預(yù)測(cè)網(wǎng)絡(luò)，對(duì)兩個(gè)網(wǎng)絡(luò)分別提取特征空間T和P，然后根據(jù)圖1的分類(lèi)優(yōu)化過(guò)程的每個(gè)步驟進(jìn)行實(shí)驗(yàn)。每個(gè)算法劃分10次，取10次結(jié)果的平均值。其中默認(rèn)選擇的特征是最具判別性(排序在前)的前8個(gè)特征作為特征子集。在該過(guò)程中把存在鏈接視為正類(lèi)(Positive)，不存在鏈接視為負(fù)類(lèi)(Negative)，True表示預(yù)測(cè)準(zhǔn)確，F(xiàn)alse表示預(yù)測(cè)錯(cuò)誤，TP則表示實(shí)際存在鏈接被成功分類(lèi)的數(shù)目。實(shí)驗(yàn)結(jié)果采用信息檢索領(lǐng)域分類(lèi)模型標(biāo)準(zhǔn)評(píng)價(jià)指標(biāo)準(zhǔn)確率(Accuracy)、AUC(Area Under Curve)、精確率(Precision)、召回率(Recall)和F1-Measure對(duì)算法進(jìn)行評(píng)價(jià)。其中：

(18)

(19)

(20)

(21)

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

(1) Dolphins[26]。這是寬吻海豚的定向社交網(wǎng)絡(luò)。節(jié)點(diǎn)表示寬吻海豚社區(qū)的寬吻海豚，關(guān)系表示海豚間的頻繁關(guān)聯(lián)。

(2) Football[26]。2000年秋季常規(guī)賽期間IA大學(xué)之間的美式足球比賽網(wǎng)絡(luò)。

(3) Enron[27]。郵件網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點(diǎn)是表示員工，關(guān)系表示節(jié)點(diǎn)之間的電子郵件。

(4) Yeast[28]。生物酵母數(shù)據(jù)集。

(5) Email[28]。Virgili大學(xué)成員之間的電子郵件交換網(wǎng)絡(luò)。

(6) Openflights[29]，航班網(wǎng)絡(luò)。 每個(gè)節(jié)點(diǎn)表示一個(gè)機(jī)場(chǎng)，關(guān)系代表一個(gè)航空公司到另一個(gè)航空公司的航班。

數(shù)據(jù)集的拓?fù)浣Y(jié)構(gòu)屬性顯示在表1中。

表1 多元網(wǎng)絡(luò)結(jié)構(gòu)屬性

4.3 對(duì)比方法

實(shí)驗(yàn)中對(duì)網(wǎng)絡(luò)中的潛在鏈接進(jìn)行分類(lèi)和推斷，判斷鏈接是否生成，驗(yàn)證提出模型的有效性。同時(shí)，實(shí)驗(yàn)采用多種有監(jiān)督學(xué)習(xí)算法作為分類(lèi)算法[30]，這些分類(lèi)算法包括樸素貝葉斯分類(lèi)(Na?ve Bayes，NB)，支持向量機(jī)(Support Vector Machine，SVM)和隨機(jī)森林(Radom Forest，RF)。本文提出方法簡(jiǎn)稱(chēng)為MLFS(Maximum Likelihood Mutual Information Feature Selection)。

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

為了充分驗(yàn)證提出特征分類(lèi)算法對(duì)鏈接分類(lèi)問(wèn)題的有效性，本文使用不同分類(lèi)算法在6個(gè)數(shù)據(jù)集中做了大量的實(shí)驗(yàn)。表2和表3給出了結(jié)果的平均值，其中No-FS表示沒(méi)有經(jīng)過(guò)特征選擇步驟，直接采用原始特征進(jìn)行分類(lèi)的算法；MLFS表示經(jīng)過(guò)特征選擇過(guò)程的分類(lèi)算法。根據(jù)表2的結(jié)果，有以下幾點(diǎn)發(fā)現(xiàn)：(1) 實(shí)驗(yàn)使用了6個(gè)數(shù)據(jù)集、5個(gè)評(píng)價(jià)指標(biāo)和3個(gè)分類(lèi)器，因此共有90個(gè)對(duì)比案例。經(jīng)過(guò)統(tǒng)計(jì)，與No-FS相比，MLFS在67.77%的案例中效果更好，在20%的案例中效果相等，在12.23%的案例中效果相對(duì)較差。該結(jié)果表明經(jīng)過(guò)最大似然互信息特征選擇步驟得到的分類(lèi)性能要優(yōu)于沒(méi)有經(jīng)過(guò)特征選擇步驟基準(zhǔn)方法，也反映本文提出的算法泛化性能很高，在多個(gè)數(shù)據(jù)集中均具備不錯(cuò)的性能。同時(shí)，對(duì)于每個(gè)數(shù)據(jù)集，最優(yōu)的算法均出現(xiàn)在MLFS中，這是因?yàn)樘卣鬟x擇刪除了一些不相關(guān)或冗余的特征，解決了維數(shù)過(guò)多帶來(lái)的災(zāi)難，在一定程度上避免過(guò)擬合，也側(cè)面反映特征選擇過(guò)程是有效且必要的。需要指出的是，由于這5種評(píng)估指標(biāo)各有側(cè)重點(diǎn)，因此一個(gè)數(shù)據(jù)集上一個(gè)方法很難在所有評(píng)估指標(biāo)上均優(yōu)于對(duì)應(yīng)基準(zhǔn)算法。(2) 各數(shù)據(jù)集各指標(biāo)在不同分類(lèi)器下的分類(lèi)結(jié)果有差別。在SVM分類(lèi)器下，76.66%的案例中MLFS比No-FS要優(yōu)，該百分比在NB和RF分類(lèi)器分別下降為56.66%和53.33%，因此從整體上看，SVM和RF比NB要更適合信息網(wǎng)絡(luò)關(guān)系分類(lèi)這一任務(wù)，原因在于SVM的優(yōu)點(diǎn)是處理高維特征數(shù)據(jù)，同時(shí)能更好地解決特征的非線性問(wèn)題。(3) 無(wú)論是對(duì)于小規(guī)模的網(wǎng)絡(luò)(例如Football數(shù)據(jù)集潛在關(guān)系有35×35)，還是對(duì)于較大規(guī)模網(wǎng)絡(luò)(Openflights數(shù)據(jù)集潛在關(guān)系有3 425×3 425)，在對(duì)經(jīng)過(guò)特征選擇的特征分類(lèi)的過(guò)程中均能夠比原始特征取得更好的分類(lèi)精度，這表明提出的算法能夠適應(yīng)不同規(guī)模的網(wǎng)絡(luò)，在一定條件下具備拓展到超大規(guī)模網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)。

表2 各分類(lèi)算法在Dolphins Football Enron下的分類(lèi)效果

續(xù)表2

表3 各分類(lèi)算法在Yeast Email Openflights下的分類(lèi)效果

續(xù)表3

此外，為了更加細(xì)致地分析每個(gè)算法的效果，文中還進(jìn)行了以下拓展實(shí)驗(yàn)：

(1) 為了驗(yàn)證提出算法的穩(wěn)定性和解決稀疏網(wǎng)絡(luò)學(xué)習(xí)的能力，表4給出了在不同規(guī)模劃分網(wǎng)絡(luò)下各分類(lèi)算法的分類(lèi)性能力，其中訓(xùn)練集比例r分別設(shè)置為0.5、0.6、0.7、0.8、0.9。我們?cè)谄渌麛?shù)據(jù)集也發(fā)現(xiàn)了類(lèi)似的效果，由于版面的關(guān)系，僅僅給出Email數(shù)據(jù)集的分類(lèi)結(jié)果。由表4可知，隨著r值不斷變大，對(duì)應(yīng)No-FS和MLFS的分類(lèi)效果基本上均呈上升趨勢(shì)，在r=0.8或r=0.9時(shí)達(dá)到穩(wěn)定狀態(tài)。這是由于隨著訓(xùn)練集規(guī)模的變大，更多的正例(存在鏈接)被加入到訓(xùn)練集中。更重要的是，基本在每一步r值上，MLFS均比對(duì)應(yīng)的No-FS表現(xiàn)出更好的分類(lèi)性能，這表明算法不受訓(xùn)練集大小的影響，表現(xiàn)出穩(wěn)定的態(tài)勢(shì)。值得一提的是，當(dāng)r=0.5時(shí)，Email數(shù)據(jù)集99.96%共鄰節(jié)點(diǎn)數(shù)目小于5，99.54%共鄰節(jié)點(diǎn)數(shù)目小于2，網(wǎng)絡(luò)變成一個(gè)非常稀疏的狀態(tài)，這樣的情況下MLFS在分類(lèi)任務(wù)上仍然獲得一個(gè)較為理想的結(jié)果，表明提出算法在稀疏網(wǎng)絡(luò)上的靈活性和優(yōu)越性。

表4 Email數(shù)據(jù)集下的訓(xùn)練集規(guī)模變化下各指標(biāo)的分類(lèi)效果

續(xù)表4

(2) 第二部分在圖2-圖4輸出了經(jīng)過(guò)MLFS篩選不同特征數(shù)目下Openflight數(shù)據(jù)集各指標(biāo)的分類(lèi)效果。需要指出，由于把過(guò)多的指標(biāo)繪制在同一個(gè)圖表中會(huì)過(guò)于擁擠，同時(shí)F1指標(biāo)綜合了Precision和Recall的效果，因此該部分實(shí)驗(yàn)顯示了Accuracy、AUC和F1對(duì)應(yīng)曲線，其中SVM-MLFS表示在SVM算法下經(jīng)過(guò)MLFS特征選擇的分類(lèi)效果，SVM-NoFS表示未經(jīng)特征選擇直接分類(lèi)的效果?？梢钥闯?，當(dāng)特征數(shù)目逐漸變大的時(shí)候(特征數(shù)目從5到8)，對(duì)應(yīng)的分類(lèi)效果也呈現(xiàn)線性增長(zhǎng)的趨勢(shì)。這是因?yàn)樘卣鲾?shù)目過(guò)少(5或者6)會(huì)影響分類(lèi)的性能，增加相似度指標(biāo)的數(shù)目有利于提高特征判別性。同時(shí)在許多情況下(例如AUC指標(biāo)的NB分類(lèi)算法)，當(dāng)特征數(shù)目為9時(shí)分類(lèi)性能并沒(méi)有顯著提升，甚至還有所降低，原因在于特征數(shù)目過(guò)多基本沒(méi)有選擇刪除了不相關(guān)或冗余的特征，等于沒(méi)有進(jìn)行特征選擇步驟。綜上所述，默認(rèn)特征選擇數(shù)目設(shè)置為8 既保證了實(shí)驗(yàn)性能又提高了分類(lèi)效率，因此是合理的。值得一提的是，在大部分的不同的特征數(shù)目設(shè)置中，經(jīng)過(guò)MLFS的各指標(biāo)性能優(yōu)于NoFS，表明MLFS對(duì)特征數(shù)目不敏感，即無(wú)論特征數(shù)目如何變化，MLFS過(guò)程都是十分必要的。

圖2 不同特征數(shù)目下Openflight的Accuracy指標(biāo)

圖3 不同特征數(shù)目下Openflight的 AUC指標(biāo)

圖4 不同特征數(shù)目下Openflight的F1指標(biāo)

(3) 為了驗(yàn)證局部特征(Local)和全局特征(Global)對(duì)分類(lèi)性能的差異化影響，本文在圖5-圖7輸出了Yeast數(shù)據(jù)集在Accuracy、AUC和F1指標(biāo)下各分類(lèi)器的在局部特征和全局特征下的分類(lèi)效果，其中Local-MLFS表示使用局部特征并經(jīng)過(guò)MLFS特征選擇的分類(lèi)效果，其余表示則依次類(lèi)推。從結(jié)果可以明顯看出，無(wú)論是局部特征還是全局特征，在大部分情況下MLFS比NoFS的分類(lèi)性能要好。以圖7為例，可以看出MLFS表示的柱體(第二、四根柱體)比基準(zhǔn)分類(lèi)算法(第一、三根柱體)高，該結(jié)果進(jìn)一步驗(yàn)證了特征選擇步驟的必要性和有效性。此外，從結(jié)果也可以看出基于全局特征的分類(lèi)算法和基于局部特征的分類(lèi)算法各有優(yōu)劣。結(jié)合在其他數(shù)據(jù)集中的統(tǒng)計(jì)結(jié)果可以發(fā)現(xiàn)，全局特征比局部特征判別性要更好，可能原因是在無(wú)監(jiān)督學(xué)習(xí)鏈接預(yù)測(cè)任務(wù)中，全局特征指標(biāo)比局部特征指標(biāo)的整體預(yù)測(cè)性能更優(yōu)。但是相關(guān)文獻(xiàn)也指出，特征指標(biāo)的優(yōu)劣和具體的網(wǎng)絡(luò)拓?fù)鋵傩韵嚓P(guān)，因此一類(lèi)特征無(wú)法全面優(yōu)于另一類(lèi)特征，結(jié)合兩類(lèi)特征分類(lèi)是較好的方案。

圖5 Yeast數(shù)據(jù)集下局部和全局特征的Accuracy指標(biāo)

圖6 Yeast數(shù)據(jù)集下局部和全局特征的AUC指標(biāo)

圖7 Yeast數(shù)據(jù)集下局部和全局特征的F1指標(biāo)

為了驗(yàn)證MLFS步驟的通用性和可推廣性，在最后一部分實(shí)驗(yàn)中擬把特征選擇到新近提出的模塊度最大化鏈接預(yù)測(cè)算法(Modularity Maximization Link Prediction Model,MMLP)當(dāng)中。在MMLP中，一個(gè)重要步驟是提取基于社區(qū)劃分結(jié)構(gòu)下社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，使用的8個(gè)特征分別是中介性核心性、緊密中心性、PageRank、HITS、CN、AA、JC和CC。和前文采用同樣的實(shí)驗(yàn)設(shè)置，抽取的特征數(shù)目設(shè)置為6，評(píng)估指標(biāo)設(shè)置為AUC。從圖8的實(shí)驗(yàn)結(jié)果可以看出，在絕大部分?jǐn)?shù)據(jù)集上引入MLFS過(guò)程的MMLP算法獲得了較好的性能提升，在各數(shù)據(jù)集中的預(yù)測(cè)值增長(zhǎng)量分別是8.493%、2.369%、1.871%、-0.762%，1.891%和0.524%。這表明MLFS步驟對(duì)于引入特征進(jìn)行鏈接預(yù)測(cè)或者鏈接分類(lèi)的新近提出的算法均是有效的。

圖8 MLFS在MMLP模型中的影響

5 結(jié) 語(yǔ)

本文對(duì)信息網(wǎng)絡(luò)的關(guān)系分類(lèi)與推斷中的特征提取與處理過(guò)程進(jìn)行分析與研究，主要工作包括以下幾個(gè)部分：(1) 提取了反映信息網(wǎng)絡(luò)局部和全局兩類(lèi)相似度特征，并提出一種基于密度估計(jì)的極大似然算法計(jì)算特征之間的互信息，該算法是一種不涉及密度估計(jì)的單步處理方法，能采用交叉驗(yàn)證的方法進(jìn)行模型選擇，可有效地計(jì)算出唯一的全局解。(2) 采用經(jīng)典分類(lèi)算法和新近提出的MMLP算法進(jìn)行關(guān)系分類(lèi)與推斷。通過(guò)在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)，有效驗(yàn)證了本文算法的優(yōu)越性和互信息特征選擇過(guò)程的必要性。

下一步將從以下幾個(gè)方面繼續(xù)深入探索：(1) 引入機(jī)器學(xué)習(xí)特征降維 、維度約減等相關(guān)算法進(jìn)一步處理特征，提高算法的運(yùn)行效率。(2) 由于網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性，進(jìn)一步把模型推廣到符號(hào)信息網(wǎng)絡(luò)、多維度信息網(wǎng)絡(luò)等場(chǎng)景的分類(lèi)與推斷任務(wù)上。