一個選擇最大似然互信息特征的網(wǎng)絡關系預測通用模型

伍杰華 熊云艷

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

0 引 言

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

圖1 算法模型

1 相關工作

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

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

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

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

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

2 特征提取

2.1 問題定義

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

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

(1)

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

2.2 局部與全局特征提取

2.2.1局部特征

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

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

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

(2)

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

Adamic-Adar(AA)[17]:該指標通過對每個共鄰節(jié)點的不同度的對數(shù)值差分化處理不同共鄰節(jié)點的角色和貢獻，度大的共鄰節(jié)點貢獻小于度小的共鄰節(jié)點。其公式如下：

(3)

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

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

(4)

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

(5)

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

(6)

式中：cω表示共鄰節(jié)點ω的聚類系數(shù)。

2.2.2全局(半全局)特征

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

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

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

(7)

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

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

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

(8)

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

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

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

(9)

同時，基于隨機游走還選取了SRW和LRW兩個指標作為全局特征，由于版面關系，在此不再詳細敘述。

3 算法框架

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

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

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

(10)

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

(11)

(12)

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

(13)

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

(14)

(15)

(16)

(17)

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

在估計密度函數(shù)之后以互信息作為提取特征的評價選擇互信息最大的N個特征進行分類。

3.2 基于MLMI的關系預測

整個算法框架如下所示：

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

Output：Accuracy AUC Precision Recall F1

1: 對G劃分為訓練網(wǎng)絡GT和預測網(wǎng)絡GP

2:forGT和GP中的每一條存在或不存在關系do

4:endfor

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

9: 采用NB，SVM和RF進行分類

4 實 驗

4.1 實驗設置

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

(18)

(19)

(20)

(21)

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

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

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

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

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

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

(6) Openflights[29]，航班網(wǎng)絡。 每個節(jié)點表示一個機場，關系代表一個航空公司到另一個航空公司的航班。

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

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

4.3 對比方法

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

4.4 實驗結(jié)果與分析

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

表2 各分類算法在Dolphins Football Enron下的分類效果

續(xù)表2

表3 各分類算法在Yeast Email Openflights下的分類效果

續(xù)表3

此外，為了更加細致地分析每個算法的效果，文中還進行了以下拓展實驗：

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

表4 Email數(shù)據(jù)集下的訓練集規(guī)模變化下各指標的分類效果

續(xù)表4

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

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

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

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

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

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

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

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

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

圖8 MLFS在MMLP模型中的影響

5 結(jié) 語

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

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