BP-ANN預測網絡關系中的數據降維與模型綜合方法

馬 峻，萬 劼

（首都經濟貿易大學 安全與環境工程學院，北京 100070）

0 引言

復雜網絡廣泛存在于社會各個領域。社交網站用戶構成的社交網絡，反映的是社交網站用戶之間的好友關系或關注(收聽)關系；商店顧客與商品構成的購買關系網絡，反映的是顧客對商品的購買關系；其他諸如航空網絡、國家的電力網絡、蛋白質相互作用網絡、食物鏈網絡等。不論是什么種類的網絡，一個網絡可抽象為由點集P和邊集E組成的圖G=(P,E)，設R是從P到其自身的一個二元關系，即R?P×P，對任意(x,y)∈P×P，如果xRy，則從x有一條有向連邊指向y，連邊反映了x與y的一種二元關系，如果(x,y)≠(y,x)，則構成一個不對稱關系，否則為對稱關系。但在數量方面，同樣規模的網絡中，二元不對稱關系的潛在數量往往比二元對稱關系多；在信息量方面，二元不對稱關系更具有方向性，因此描述二元不對稱關系的網絡要比描述二元對稱關系的網絡包含更多的信息量。網絡中存在的這種關系對于網絡影響力的拓展以及網絡資源的有效利用具有很大的價值[1]，二元不對稱關系相對于二元關系的研究更具有普遍性和研究意義。

目前針對社會網絡中的二元關系的預測主要基于的信息可分為三類，第一類是根據網絡節點屬性信息進行預測；第二類是根據網絡結構信息進行預測；第三類是上述兩類的混合方法，即在預測中既使用節點屬性信息也使用網絡結構信息。文獻[2，3]表明使用節點屬性信息對社會網絡中的二元關系進行預測求解可以得到較好的效果，但是使用節點屬性信息存在著以下問題：第一，大量的節點屬性信息很難獲取，可靠性也難以得到保證；第二，需要大量的資源來存儲、讀取節點屬性信息。但是根據網絡結構信息進行關系預測求解一般不存在上述兩個問題。

根據網絡結構信息進行關系預測求解中，一類是基于節點相似度的關系預測求解方法，另一類是基于似然分析的預測求解方法。基于相似度的關系預測求解方法較為簡便，需要的假設前提較少，而基于似然分析的關系預測求解方法較為復雜，且需要建立在較多的假設(如層次結構、社團結構等)之上，使用較少。文獻[4]將節點相似度與機器學習方法相結合，收到了較好的求解效果，但是還存在一些有待解決的問題；其次，基于節點相似性的關系預測方法在處理二部分網絡時會遇到困難，例如很多常用的相似度指標是無法計算的，這時一般需要使用一些更為復雜的相似度指標，或者采用集合投影和協同過濾的方法[5-7]，這些方法或是較為復雜，或是有待完善。而神經網絡(Artificial Neural Network，ANN)作為一種非線性動力學模型廣泛用在各個領域預測求解，但是神經網絡在進行社會網絡關系預測計算中，由于社會網絡的動態性和時變性導致網絡資源拓展的不確定性，同時社會網絡規模大、小世界性小社團等特性導致網絡鄰接關系矩陣稀疏和不均勻性，產生社會網絡預測求解中輸入數據維數高，同時網絡中存在的不平衡性也極大地影響了神經網絡預測計算的效果[8]，為此，本文針對這兩個問題，在提出相應降維算法基礎上，建立了如何克服不平衡性從而提高模型求解效果的方法。

1 問題描述

本文采用BP神經網絡對社會網絡二元不對稱關系進行預測求解的基本邏輯過程如下頁圖1所示。

圖1 利用BP神經網絡進行社會網絡二元不對稱關系預測求解邏輯過程

T=(SR)反映訓練集所有樣本在整個網絡的連接關系。

P=(UV)反映了預測求解集所有樣本在整個網絡的連接關系。

S和U分別是訓練和預測求解的輸入值，R是訓練輸出值，V是預測求解輸出值。S，U，R是鄰接矩陣的已知部分，V是鄰接矩陣的未知部分。

實際應用中V的某些部分可能是已知的，但鑒于一般V占整個鄰接矩陣的比例較小（不大于1/9），而考慮V的已知部分會增大算法和代碼的復雜度，因此將V的全部設為未知。如果只需要預測求解V的部分列向量，那么就不需要獲取關于R的全部信息，只需要知道R所對應列向量的取值。

根據圖1，預測求解需要大量的訓練樣本，因此An×n的m會很大，如果將S和U這種高維向量直接作為輸入，則算法復雜度會很大，因此需要采取適當方法進行降維；另外由于網絡中大部分節點對是不存在關系的（這種情形也被稱為數據不平衡），而神經網絡算法通常以訓練誤差最小化為目標求解模型，這會導致模型傾向做出關系不存在的預測，而實際應用中更多被關注的是存在的關系，將存在的關系判斷為不存在所導致的損失經常遠大于將不存在的關系判斷為存在所導致的損失，因此需要對模型進行進一步的處理。

2 數據降維

2.1 數據降維方法

根據圖1，在利用神經網絡進行關系預測時，需要將關系矩陣An×n中Sm×m的m個變量取值全部直接輸入到神經網絡輸入層，通常較大的m將導致神經網絡規模也會變大，將大大增加算法的復雜度，因此有必要設法減少輸入層的節點數。

根據鄰接關系矩陣An×n，m個原始輸入變量的取值只有0與1兩種可能，又因為這個變量的順序是固定不變的，因此神經網絡輸入層其實是一個長度為m的0-1向量，為此可以將其固定長度轉化為一個整數，從而實現數據的降維。具體方法如下：

設πn為全體n維0-1向量構成的集合，Z為整數集。對?x∈πn，x可被表述為如下形式：

再做如下映射：

對于f，有如下命題成立：

命 題 1：對 ?x1,x2∈πn，若x1≠x2，則 必 有f(x1)≠f(x2)。

采用反證法可以對上述命題進行證明。

命題1說明：f可將不同長度的0-1向量轉化為不同整數，并且通過fn進行數據降維的過程中不會丟失原有的任何信息。

2.2 存在的問題

理論上任意n維0-1向量可以轉化為一維整數，因此可以將m個輸入變量轉化為一個輸入變量，這樣神經網絡的輸入層節點數最少只需要一個，而不是m個。但是，如果僅僅用一個十進制數替代原先的m個變量，那么可能會大大增加神經網絡的訓練難度。

例如：設m為5，樣本A的原始輸入向量為(1，0，0，0，1)，轉化為十進制數，即為17。樣本B的原始輸入向量為(0，0，0，0，1)，轉化為十進制數，即為1。A和B只在一個位置上不同，應該說兩個樣本比較相似。但是轉化為十進制數后，兩個樣本對應的輸入值要相差16倍。再設樣本C的輸入向量為(0，1，1，1，0)。C與A在所有位置上都不同，但是C的輸入向量轉化為十進制后為14，反而與A比較接近。一般來說，A與B的輸出值往往是相同的，而A與C的輸出值更可能是不同的。這意味著輸出值對輸入值的變化非常敏感，而且通過神經網絡得出的預測函數會有高頻且大幅的波動。

雖然神經網絡算法比很多其他算法更善于處理此類非線性的回歸，但在輸入值與輸出值之間幾乎毫無線性相關性的情況下，如果訓練樣本并不是很多，那么神經網絡也較難做出準確的預測。

2.3 分段降維算法

解決上述問題的辦法是將原始m維輸入向量分為k段（k＞1），提高算法效率同時保證算法的有效性。m維的輸入向量分為k段，每段轉化為一個整數，輸入變量轉化為k個整數。這樣對于任意一個樣本集，設原始輸入向量x=(a1,a2,…,am)（ai∈{0,1}，i=1,2,…,m），分段降維結果y=(b1,b2,…,bk)∈Zk（k≤m）。

k的取值既不能太大，也不能太小。如果k太大，達不到降低神經網絡輸入層維數的目的，如果k太小，則輸出值對輸入值的變化會很敏感，從而增加神經網絡學習的難度。由于k實際上就是輸入層的節點數，因此k是一個影響神經網絡結構的變量，而神經網絡結構也會影響預測的效果。

分段降維算法如下：

步驟1：ifk|m!=int

步驟1.1：設h=m'/(k-1)

步驟1.2：Forj=0tok-2

依次將 (ajh+1,ajh+2,…ajh+h)記為Aj+1,將x的最后(m-m')個分量(am'+1,am'+2,…,am)記為Ak

步驟2：ifk|m=int

步驟2.1：設h=m/k

步驟2.2：Forj=0tok-1

依次將 (ajh+1,ajh+2,…ajh+h)記為Aj+1,將x的最后(m-m')個分量(am'+1,am'+2,…,am)記為Ak

步驟3：得到分為k段的向量x，記為(A1,A2,…,Ak)

步驟4：Forj=0tok

?Aj∈{A1,A2,…,Ak}將Aj轉化為整數f(Aj)

bj=f(Aj)

步驟5：得到k維整數向量y=(b1,b2,…,bk)∈Zk

上述將An×n劃分為An×n的過程中，可以保證An×n都有相同的維數An×n，并且能使An×n盡量大。這樣，An×n就能較為“均勻”地被劃分為An×n段。同時由于分段降維算法對于每個二進制數都會與一個十進制數一一對應，因此降維前后的數據之間存在一一映射，降維并沒有使數據所包含的信息量減少，整個數據降維過程是可逆的。

3 模型綜合法

數據的降維提高了神經網絡計算的效率，但是由于復雜社會網絡存在關系的復雜性，以及所擁有的冪律特性導致在利用神經網絡進行關系預測時存在的不平衡性問題，即對于關系比較密集的社會網絡，預測出不存在的關系實際是存在的，反之在稀疏關系網絡預測出存在的關系實際是不存在的，這種不平衡性是由于模型本身造成的[8]，為了消除這種不平衡性，本文構建預測模型綜合評價指標基本上建立模型綜合方法，具體實現過程如下。

3.1 基本評價指標

神經網絡預測模型的評價是建立在鄰接矩陣An×n基礎上，設Y=(aij)(n-m)×q是An×n中V的一個子矩陣，表示V中全部待預測的部分，q是待預測的列向量的數量。X=(bij)(n-m)×q是對Y的預測值（Y為真實值）。||A表示任意有限集合A的基數，N+表示正整數集，則有：

Np=(n-m)q，即Np為Y的元素總數；

Nt=|{(i,j)∈N+×N+|aij=bij}|，即Nt為預測正確的次數；

Mp=|{(i,j)∈N+×N+|aij=1}|，即Mp為預測集中真正存在的連邊數量；

Mt=|{(i,j)∈N+×N+|aij=bij=1}|，即Mt為在連邊真實存在的條件下，正確預測的次數。

評價指標有兩個。一個是總預測準確率P1，另一個是正類預測準確率P2。

從本質看P1反映的是模型整體的預測準確率，P2反映的是模型對關系存在性的發現能力。之所以要進一步計算P2，是因為在分析實際問題中，人們往往更關注關系的存在性，而對關系的不存在性并不那么關注，從廣義上來看，關系的存在性與不存在性的受重視程度是不同的，P2會增強模型對非重視關系的發現能力。

因此P1和P2是評價模型預測效果的兩個基本指標，兩個指標缺一不可。如果忽視P2，而只看P1，那么將正類誤判為負類的概率就難以得到控制。另一方面，如果P2很高而P1很低，那么總的誤判損失還是會很大。為了彌補這個缺陷，本文建立基于P1和P2基本指標的綜合評價指標。

3.2 綜合評價指標

將基本指標P1和P2加權平均可以得到一個新的綜合指標Pc，Pc可由式（4）確定：

γ1和γ2的取值是與使用者對P1和P2的重視程度有關，但是在實際應用中Pc計算方法未必能真實體現使用者對P1和P2的重視程度。這是因為P1和P2的標準差可能會有很大差異，在許多復雜網絡中(尤其是連邊較為稀疏網絡中)，由于真實存在的連邊要比節點對總數少很多，往往P2的標準差要比P1大很多，影響P2的偶然隨機因素要比P1大，P1的差異更大程度上是模型本身因素導致的。為了消除上述影響，只有對P1和P2做調整，使兩者的標準差相同，才能更加客觀地評價模型的預測能力。

設σi是Pi的標準差，則P1σ1和P2σ2具有相同的標準差，帶入公式（4）可得到：

其中γi由人為主觀決定。σi是Pi總體的性質，無法直接結算，但是可以根據不?同模型得到的Pi值，通過計算Pi的樣本標準差 ，再將作為σi的估計值。

3.3 模型綜合

利用神經網絡進行關系預測時，不同的模型參數，相同的輸入其輸出的預測結果也不同，在這里把擁有不同參數的神經網絡預測模型稱為不同的分類器。在實際問題求解過程中，如果以預測效果最好的一個分類器預測結果為準，可能會導致較大的誤判風險，因為一個分類器預測效果的好壞，通常需要通過已知樣本進行檢測才能得出，當一個分類器在用于檢測模型效果的已知樣本上表現出良好效果時，雖然可以認為該分類器的預測能力是較強的，但其未必會在待預測的未知樣本上也能取得最好的效果。即使該分類器在未知樣本上的預測能力仍然是最強的，其預測效果也未必好于將多個分類器綜合得出的結果。因此，相對于僅僅“信任”一個分類器的做法，本文將若干個分類器組合起來進行預測，降低結果的誤判風險。基本原理是對各神經網絡預測模型賦予權重，根據各個分類器的預測值加權平均來獲得最終預測結果，加權平均值表達形式如下：

其中，H為分類器個數，yi是第i個分類器的預測值，βi第i個分類器的權重系數。問題的關鍵轉換為如何得到每個分類器的βi值。

在公式（6）中，βi值的大小是與預測效果成正比的，如果只考慮兩個分類器ρ1和ρ2的情形下，分類器ρi（i=1,2）的權重系數βi的計算公式為：

其中，Pc(ρi)是分類器ρi對檢測集樣本的預測效果綜合評價指標Pc的值。在其他條件不變的情況下，βi與Pc(ρi)成正比，說明預測效果越好，權重系數越大。而φ(ρ1,ρ2)是兩個分類器ρ1和ρ2預測值相同的概率，，其中Ns是用于檢測集樣本總數，yρ1,i和yρ2,i分別是分類器ρ1和ρ2對第i個檢測集樣本的預測值。

根據公式（7），φ(ρ1,ρ2)越大，則βi越小。如果φ(ρ1,ρ2)達到最大值1，則有：

這樣，在使用兩個預測結果完全相同的分類器的情況下，兩個分類器權重系數總和與僅僅保留其中一個分類器的情況下的權重系數是相同的。如果φ(ρ1,ρ2)達到最小值0，則βi=Pc(ρi)，說明當兩個預測結果完全不同的分類器組合起來時，他們各自的權重都不會被削弱。

把式（7）式擴展到兩個以上分類器的情形，在有H個分類器情況下，第i（i=1,2,…H）個分類器ρi的權重系數βi的計算公式為：

由于φ(ρi,ρi)=1，因此式（8）又能寫成以下形式：

因此，模型綜合的權值βi求解過程為：

步驟1：從已知樣本中抽出一部分，將其作為檢測集樣本，并用各分類器對檢測集樣本進行預測，得出預測值；

步驟2：根據第一步的預測結果，計算各分類器的Pc值；

步驟3：計算每兩個分類器預測值相同的概率φ(ρi,ρj)；

步驟4：利用式（9）計算βi。

4 實例驗證

本文以美國政治博客引用關系網絡為實例（數據來源于www.linkprediction.org 2014年6月），網絡中節點是博客文章，如果博客文章A引用了博客文章B，則在網絡中代表文章A的節點會有一條有向邊指向代表文章B的節點。驗證數據選用這一網絡的一個導出子網絡進行實證分析，該子網絡包含150個節點，將網絡中的節點編號為1～150號，并將這150個節點構成的集合記為Np。以1～100號節點為訓練集，101～150號節點為預測集。為檢驗算法效果，假定有序節點對集合Yp={(x,y)|x∈Np,y∈Np,101≤x≤150,106≤y≤150}中的二元關系存在性是未知的，其余節點對的二元關系存在性是已知的。然后從106～150號節點中隨機選擇10個節點，構成集合Kt，利用本文提出的方法對有序節點對集合Y={(x,y)|x∈Np,y∈Kt,101≤x≤150}中的二元關系存在性進行預測。

神經網絡求解約束條件設置：①訓練的最大迭代次數為1000；②連接函數選擇為Logistic函數；③初始開始進行訓練的次數選為50；④訓練的學習率取值為0.01；⑤訓練時觀察模型誤差的頻率是每迭代10次觀察一次；⑥迭代收斂的判斷標準是相鄰兩次觀察到的誤差值相差小于5×10-7。

不同分類器的參數調整是：①輸入向量的維數k；②隱藏層的節點數s；③正類樣本權重c。

將Yt={(x,y)|x∈Np,y∈Np,101≤x≤150,101≤y≤105}作為檢測集，以檢測不同參數下模型的預測效果。在k取10和20、s取15和30、c取5和6情況下，三個參數的全部組合共是8，分別在這8個參數組合下對檢測集進行預測實驗。測試實驗發現s為30，c為6情況下的兩個模型預測效果最好。于是s取為30，c取為6，再分別取k為5、15和25，進行三組實驗。

根據算法1，在k取5情況下的數據降維是：

根據公式（2）和（3）計算得到11個參數組合下預測模型評價指標如表1所示。

表1 參數組合及預測模型評價指標

計算出表1中任意兩個模型預測值相同的概率如表3所示。

表2 各個預測模型綜合評價指標值

表3 任意兩個模型預測值相同的概率

根據公式（9）各個模型權重系數βi如表4所示。

表4 各個模型的權重系數（歸一化前）

依據表1中11個模型對Y中的關系進行預測，得出各模型對Y中有序各節點對關系存在性的預測值，然后對于每個待預測的有序節點對，根據式(6)并采用表4的βi值計算各模型預測值的加權平均，該加權平均值即為整個模型最終的預測值。將各模型的預測值以及模型最終預測值與真實值做比較，計算各模型的P1值和P2值以及模型綜合的預測效果P1值和P2如下頁表5所示。

從表5可以看出，最終對預測值求加權平均后得到的綜合模型的P2值是所有模型中最高的。雖然3號模型和8號模型的P2值與最終綜合模型的P2值相同，但這兩個模型的P1值都相對較低。在P1值方面，除去10號模型與11號模型以外，其他模型的P1值都比最終綜合模型低。10號模型與11號模型的P1值比最終綜合模型的P1值略高，但在P2值方面卻不如最終綜合模型。根據表5，可以計算出各模型的Pc值(其中對P1和P2的重視程度相同)如表6所示。

表5 各模型的預測效果以及模型綜合法預測效果

表6 各個模型的預測效果綜合評價指標值

從表6可知，在對P1和P2的重視程度相同的前提下，綜合模型的Pc值是最高的。可見綜合模型預測效果比單個模型要好。

5 結束語

隨著互聯網+的不斷發展，社會網絡逐步滲透到社會各個領域，充分利用網絡資源拓展服務成為互聯網經濟時代面臨的一個突出問題，而有效地預知網絡中二元不對稱關系可以為用戶準確地把握措施的實施提供了有力的支持。本文基于社會網絡的復雜性和動態性，利用神經網絡預測特性，構建了預測時高維輸入向量降維的算法，在建立模型綜合評價指標基礎上，構造了具有消除不平衡性的模型綜合預測方法，實例驗證表明，本文所提算法和方法是有效的。