黃 娟,郭 強(qiáng),劉建國
(1.上海理工大學(xué) 管理學(xué)院,上海 200093;2.上海財(cái)經(jīng)大學(xué) 金融科技研究院,上海 200433)
相比于傳統(tǒng)靜態(tài)網(wǎng)絡(luò),時(shí)序網(wǎng)絡(luò)不僅能夠表示節(jié)點(diǎn)間的關(guān)系,還能通過節(jié)點(diǎn)或連邊的增加或減少表現(xiàn)拓?fù)浣Y(jié)構(gòu)隨時(shí)間變化情況,近年來被廣泛應(yīng)用于建模解決金融、醫(yī)療、交通、電子商務(wù)等領(lǐng)域問題[1]。關(guān)鍵節(jié)點(diǎn)是整個(gè)網(wǎng)絡(luò)中處于核心位置的節(jié)點(diǎn),對(duì)整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)和功能具有較大影響力。在時(shí)序網(wǎng)絡(luò)中,識(shí)別關(guān)鍵節(jié)點(diǎn)能夠更精準(zhǔn)地刻畫事物間的交互關(guān)系及發(fā)展進(jìn)程,如建模復(fù)雜社交系統(tǒng)、刻畫經(jīng)濟(jì)網(wǎng)絡(luò)、建立合作網(wǎng)絡(luò)、預(yù)測重要樞紐以防止交通堵塞、預(yù)測關(guān)鍵患者以防止病毒傳播、識(shí)別核心客戶、預(yù)測流行產(chǎn)品等[2-5]。因此,研究并設(shè)計(jì)有效的關(guān)鍵節(jié)點(diǎn)識(shí)別方法具有重要的理論與實(shí)踐意義。
近年來,時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的識(shí)別方法大致可分為3類:基于拓?fù)浣Y(jié)構(gòu)的識(shí)別方法、基于動(dòng)力學(xué)的識(shí)別方法,以及基于機(jī)器學(xué)習(xí)的識(shí)別方法[1]。其中,經(jīng)典的時(shí)序網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別研究工作主要思路在于根據(jù)時(shí)序數(shù)據(jù)構(gòu)建時(shí)序網(wǎng)絡(luò)模型,通過網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)或動(dòng)力學(xué)特征,采用節(jié)點(diǎn)排序算法識(shí)別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。基于拓?fù)浣Y(jié)構(gòu)的識(shí)別方法僅考慮時(shí)序網(wǎng)絡(luò)每個(gè)層內(nèi)的連接關(guān)系,為更好地表示時(shí)序網(wǎng)絡(luò)的時(shí)序特征,還需要考慮不同時(shí)間層間的連接關(guān)系[6-7]。如Taylor 等[8]在傳統(tǒng)動(dòng)力學(xué)方法的基礎(chǔ)上,采用多層耦合網(wǎng)絡(luò)分析方法,將時(shí)序網(wǎng)絡(luò)按照層間關(guān)系和層內(nèi)關(guān)系建立超鄰接矩陣(Supra-Adjacency Matrix,SAM),然后根據(jù)特征向量的中心性得到節(jié)點(diǎn)重要性排名;楊劍楠等[6]在SAM 方法的基礎(chǔ)上,通過鄰居拓?fù)渲丿B系數(shù)構(gòu)建新的超鄰接矩陣(Super Supra-Adjacency Matrix,SSAM)。以上學(xué)者的研究結(jié)果表明,對(duì)層間關(guān)系的建模能更準(zhǔn)確地預(yù)測節(jié)點(diǎn)的重要性排序。此外,機(jī)器學(xué)習(xí)結(jié)合復(fù)雜網(wǎng)絡(luò)的研究也得到學(xué)者們的廣泛關(guān)注,如林國強(qiáng)等[9]將復(fù)雜網(wǎng)絡(luò)分析數(shù)據(jù)作為特征輸入機(jī)器學(xué)習(xí)模型,用支持向量機(jī)方法預(yù)測P2P行業(yè)的用戶違約情況;Fang 等[10]以時(shí)間T 為界限,以在此之前的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù),剩余數(shù)據(jù)作為測試數(shù)據(jù),并以社會(huì)網(wǎng)絡(luò)理論為依據(jù)選取相關(guān)特征,采用決策樹模型訓(xùn)練并預(yù)測社會(huì)網(wǎng)絡(luò)中最有力的說服者。以上學(xué)者成功將時(shí)序信息引入到機(jī)器學(xué)習(xí)方法中,從而為后續(xù)相關(guān)研究提供參考。
綜上可以看出,近年來基于動(dòng)力學(xué)的研究主要在于充分運(yùn)用時(shí)序網(wǎng)絡(luò)中的層間信息輔助關(guān)鍵節(jié)點(diǎn)識(shí)別?;跈C(jī)器學(xué)習(xí)方法的識(shí)別研究工作嘗試更好地將時(shí)序信息引入到模型中,但這些方法僅從單一角度進(jìn)行分析,每種方法往往都優(yōu)缺點(diǎn)并存,加上時(shí)序網(wǎng)絡(luò)中不同時(shí)間段的數(shù)據(jù)特征并非完全一致,很難突破現(xiàn)有瓶頸以及獲得更高的準(zhǔn)確率。因此,本文結(jié)合上述兩種分析角度,提出一種基于深度學(xué)習(xí)的混合預(yù)測模型,使得兩種方法在有效發(fā)揮優(yōu)勢(shì)的同時(shí),優(yōu)缺點(diǎn)也可以實(shí)現(xiàn)互補(bǔ)。首先,深度學(xué)習(xí)模型和SSAM 方法分別獨(dú)立地預(yù)測節(jié)點(diǎn)重要性排序,然后通過訓(xùn)練一個(gè)線性模型對(duì)兩種方法得出的結(jié)果進(jìn)行加權(quán)處理,從而確定最終的節(jié)點(diǎn)排序。
時(shí)序網(wǎng)絡(luò)可按照一定時(shí)間間隔被切分為T個(gè)時(shí)間窗口,則其可被分為有序的時(shí)間層網(wǎng)絡(luò)G1,G2,G3,…GT。時(shí)序網(wǎng)絡(luò)可被超鄰接矩陣建模表示,SSAM 方法采用一個(gè)NT×NT的分塊矩陣建模時(shí)序網(wǎng)絡(luò)。具體形式如下:
其中,A(1),A(2),A(3),…,A(T)均為N×N的鄰接矩陣,用于表示各網(wǎng)絡(luò)層的層內(nèi)連接關(guān)系,C(1,2),C(2,3),…,C(t-1,t)均為由鄰居拓?fù)渲丿B系數(shù)組成的N×N對(duì)角矩陣,用于表示各網(wǎng)絡(luò)時(shí)間層之間的層間連接關(guān)系。其定義為:
之后,SSAM 方法針對(duì)上文中的超鄰接矩陣A'計(jì)算主特征向量v={v1,v2,…,vNT},其中wit=vN(t-1)+i即為時(shí)間網(wǎng)絡(luò)層Gt中節(jié)點(diǎn)i的特征向量中心性,其作為節(jié)點(diǎn)重要性排序的衡量指標(biāo),可得出每個(gè)時(shí)間網(wǎng)絡(luò)層上的節(jié)點(diǎn)重要性排序[6]。
長短期記憶神經(jīng)網(wǎng)絡(luò)(Long Short-Term Memory Neural Network,LSTM)是循環(huán)神經(jīng)網(wǎng)絡(luò)的一個(gè)變種,其在基礎(chǔ)循環(huán)神經(jīng)網(wǎng)絡(luò)單元基礎(chǔ)上增加了記憶和遺忘單元,使之能更有效地處理與預(yù)測較長的時(shí)間序列數(shù)據(jù)[11-12]。LSTM 通過門控制結(jié)構(gòu)調(diào)控先前與當(dāng)前時(shí)間單元的信息,輸入門it、遺忘門ft和輸出門ot將短期記憶與長期記憶結(jié)合起來,使循環(huán)神經(jīng)網(wǎng)絡(luò)具備長期記憶能力[10]。LSTM 工作流程可表示為:
(1)遺忘門ft對(duì)信息進(jìn)行過濾,通過Sigmoid(σ)函數(shù)使有用信息的值接近1;反之,無用信息的值接近0。
(2)輸入門根據(jù)當(dāng)前輸入信息和遺忘門的結(jié)果更新狀態(tài)信息:
輸入信息:
記憶細(xì)胞:
長期記憶細(xì)胞:
(3)輸出門輸出信息:
其中,σ代表Sigmoid函數(shù),W、b分別代表各個(gè)門單元中的權(quán)重和偏置,ht-1、ht分別為前序和當(dāng)前時(shí)間單元的輸出信息,xt為當(dāng)前時(shí)間單元的輸入信息?;谘h(huán)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的LSTM 能有效利用前序時(shí)間單元上的信息,已被廣泛應(yīng)用于時(shí)序數(shù)據(jù)預(yù)測任務(wù),因此本文采用LSTM 模型結(jié)構(gòu)對(duì)時(shí)序網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行處理與預(yù)測。
本文從模型融合角度出發(fā),結(jié)合SSAM 方法與LSTM 模型優(yōu)勢(shì),使二者的優(yōu)劣勢(shì)互補(bǔ),從而提高時(shí)序網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序的預(yù)測準(zhǔn)確率。本文提出的混合模型可分為3部分:SSAM 模型、LSTM 模型和線性加權(quán)模型。
在第1 部分中,本文在SSAM 模型部分主要參考并復(fù)現(xiàn)楊劍楠等[6]的研究工作,首先通過超鄰接矩陣建模時(shí)序網(wǎng)絡(luò),之后根據(jù)節(jié)點(diǎn)的特征向量中心性得出每個(gè)時(shí)間層網(wǎng)絡(luò)上的節(jié)點(diǎn)重要性排序。
第2 部分為基于LSTM 的時(shí)序預(yù)測模型,由循環(huán)神經(jīng)網(wǎng)絡(luò)LSTM 與一個(gè)全連接網(wǎng)絡(luò)層(Fully Connected Layer)組成。首先,LSTM 方法根據(jù)先前與當(dāng)前信息輸出節(jié)點(diǎn)的向量化表示;其次,將這些向量作為特征輸入分類器,分類器根據(jù)節(jié)點(diǎn)特征將其分類為對(duì)應(yīng)排序區(qū)間。
以上兩部分在混合模型中可并行化地執(zhí)行,其結(jié)果互不干擾,兩者分別獨(dú)立預(yù)測節(jié)點(diǎn)在每個(gè)時(shí)間層網(wǎng)絡(luò)上的排序,但往往由于數(shù)據(jù)特征以及方法本身的限制,單一方法難以取得更好的預(yù)測效果。因此,本文在混合模型的第3部分采用融合的方式,使用一個(gè)線性模型加權(quán)兩種方法得出節(jié)點(diǎn)排序,最終的排序結(jié)果無需人為干涉,線性模型能夠自動(dòng)學(xué)習(xí)不同時(shí)間層上的加權(quán)權(quán)重。圖1 描述了混合模型基本組織架構(gòu)。
Fig.1 Basic architecture of hybrid model integrating deep learning model圖1 融合深度學(xué)習(xí)模型的混合模型基本組織架構(gòu)
混合模型的基本訓(xùn)練流程如下:
算法:模型訓(xùn)練流程描述
為了驗(yàn)證模型預(yù)測的準(zhǔn)確率及參數(shù)設(shè)置的合理性,并避免因數(shù)據(jù)隨機(jī)切分等帶來的干擾,本文在模型訓(xùn)練與驗(yàn)證過程中采用K折交叉驗(yàn)證法,即將數(shù)據(jù)劃分為K份,訓(xùn)練總共進(jìn)行K輪次,每次使用其中1 份用于驗(yàn)證模型效果,剩余K-1 份用于訓(xùn)練模型,并以K次實(shí)驗(yàn)結(jié)果的均值作為最終結(jié)論。根據(jù)時(shí)序網(wǎng)絡(luò)數(shù)據(jù)特征,本文分別按照基于時(shí)間與基于節(jié)點(diǎn)的切分方式劃分?jǐn)?shù)據(jù)集,用于適應(yīng)不同的數(shù)據(jù)集及進(jìn)行實(shí)驗(yàn)對(duì)比。則上述兩種數(shù)據(jù)切分方法可被描述為:
(1)基于時(shí)間的數(shù)據(jù)切分。時(shí)序網(wǎng)絡(luò)按照時(shí)間窗口劃分。假設(shè)時(shí)間總周期為10,K值取5,則每輪次訓(xùn)練時(shí)選取連續(xù)的2 個(gè)時(shí)間窗口作為驗(yàn)證數(shù)據(jù),剩余8 個(gè)連續(xù)時(shí)間窗口作為訓(xùn)練數(shù)據(jù)。
(2)基于節(jié)點(diǎn)的數(shù)據(jù)切分。時(shí)序網(wǎng)絡(luò)首先按照時(shí)間窗口劃分,之后訓(xùn)練和驗(yàn)證數(shù)據(jù)再按照節(jié)點(diǎn)劃分。假設(shè)K值取5,則每輪次訓(xùn)練時(shí)選取20%的節(jié)點(diǎn)作為驗(yàn)證數(shù)據(jù),其余80%的節(jié)點(diǎn)作為訓(xùn)練數(shù)據(jù)。
本文使用Workspace 數(shù)據(jù)集進(jìn)行模型訓(xùn)練與測試,該數(shù)據(jù)集包括法國某公司通過移動(dòng)射頻技術(shù)采集的員工之間面對(duì)面交互產(chǎn)生的交互數(shù)據(jù),持續(xù)時(shí)間為2013 年6 月24日-2013 年7 月3 日,并按照天為單位進(jìn)行切分。表1 描述了該數(shù)據(jù)集的基本統(tǒng)計(jì)特征,其中N為網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù),C為總交互次數(shù),E為連邊數(shù)目,T為時(shí)間窗口數(shù)量。
Table 1 Workspace dataset statistics description表1 Workspace 數(shù)據(jù)集統(tǒng)計(jì)描述
節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性排序可根據(jù)刪除該節(jié)點(diǎn)前后網(wǎng)絡(luò)的連通性變化進(jìn)行度量,如果節(jié)點(diǎn)刪除后網(wǎng)絡(luò)的連通性變化較大,則證明被刪除的節(jié)點(diǎn)對(duì)于網(wǎng)絡(luò)較為關(guān)鍵,反之則重要性較低[1,6-7]。網(wǎng)絡(luò)的連通性可由網(wǎng)絡(luò)的時(shí)序全局效率來表示,其定義形式如下:
其中,N為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量,dij表示網(wǎng)絡(luò)中各節(jié)點(diǎn)間的時(shí)序距離。定義eit為時(shí)間層網(wǎng)絡(luò)Gt在刪除了節(jié)點(diǎn)i 之后的時(shí)序全局效率,則該節(jié)點(diǎn)的重要性排序依據(jù)可表示為:
Eit值越大,則該節(jié)點(diǎn)在網(wǎng)絡(luò)Gt中的排序越靠前。本文將通過節(jié)點(diǎn)刪除法得到的節(jié)點(diǎn)重要性排序作為模型訓(xùn)練中的標(biāo)簽值。此外,為降低分類模型的復(fù)雜度,本文將節(jié)點(diǎn)排名作近似處理,如將12、18 分別轉(zhuǎn)變?yōu)?0 和20,該處理方式使得模型由92 分類問題降為10 分類問題。
為了檢驗(yàn)實(shí)驗(yàn)得出的節(jié)點(diǎn)重要性排序效果,本文采用肯德爾系數(shù)(Kendall's τ)作為評(píng)價(jià)指標(biāo)。Kendall's τ是度量兩個(gè)有序序列之間相關(guān)程度的常用方法,其取值范圍為[-1,1]。該值越大,證明兩個(gè)序列相關(guān)性越強(qiáng)。兩個(gè)序列越相似,當(dāng)其數(shù)值大于0 時(shí),可作為關(guān)鍵節(jié)點(diǎn)的識(shí)別準(zhǔn)確率[6-8]。對(duì)于序列{a1,a2,…,an} 和序列{b1,b2,…,bn},Kendall'sτ可定義為:
為了使LSTM 方法能夠更好地在當(dāng)前時(shí)間層網(wǎng)絡(luò)表示節(jié)點(diǎn)屬性,本文參考網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的主要特性,采用Pearson 相關(guān)系數(shù)過濾法過濾掉與節(jié)點(diǎn)排名相關(guān)性過低的特征(絕對(duì)值小于0.2)。將所選取的特征作為輸入,通過LSTM 方法構(gòu)建每個(gè)節(jié)點(diǎn)的向量化表示。
最終,本文按照上述特征選取方法選取如下節(jié)點(diǎn)拓?fù)鋵傩宰鳛檩斎胩卣鳎汗?jié)點(diǎn)入度、節(jié)點(diǎn)出度、節(jié)點(diǎn)度、接近中心性、介數(shù)中心性、特征向量中心性以及連邊介數(shù)中心性共7 個(gè)特征。所選取的特征間的相關(guān)性如圖2 所示(彩圖掃OSID 碼可見,下同)。
由圖中可以看出,節(jié)點(diǎn)度數(shù)、接近中心性及介數(shù)中心性3 個(gè)拓?fù)涮卣髋c節(jié)點(diǎn)重要性排名有較高相關(guān)度,說明這些特征將在預(yù)測中起關(guān)鍵作用。以上特征數(shù)值高的節(jié)點(diǎn),在排序中的位置相對(duì)更加靠前,在網(wǎng)絡(luò)中也相對(duì)更為重要。
本文在SSAM 方法部分參考楊劍楠等[6]研究工作中的實(shí)驗(yàn)設(shè)置。在LSTM 方法模塊通過調(diào)節(jié)LSTM 中的隱藏層數(shù)目(L)、大?。℉)以及訓(xùn)練迭代輪數(shù)(M)尋找最佳的模型設(shè)置。在線性加權(quán)部分通過不同線性模型對(duì)比預(yù)測效果。本文首先固定LSTM 中的超參數(shù)L、H、M分別為8、1、10,采用線性回歸模型作加權(quán)處理,交叉驗(yàn)證中的K值取5。表2為不同訓(xùn)練策略的實(shí)驗(yàn)結(jié)果比較。
Fig.2 Correlation comparison of each feature and node ranking圖2 各特征及節(jié)點(diǎn)排名相關(guān)性比較
Table 2 Comparison of experimental results of different training strategies表2 不同訓(xùn)練策略實(shí)驗(yàn)結(jié)果比較
其中,τmean、τstd分別表示10 個(gè)時(shí)間網(wǎng)絡(luò)層上對(duì)應(yīng)方法得到的節(jié)點(diǎn)重要性排序,以及采用節(jié)點(diǎn)刪除法得到節(jié)點(diǎn)排序的Kendall's τ均值和標(biāo)準(zhǔn)差。根據(jù)實(shí)驗(yàn)結(jié)果對(duì)比,基于時(shí)間窗口的切分方法訓(xùn)練結(jié)果優(yōu)于單獨(dú)使用SSAM 方法以及基于網(wǎng)絡(luò)節(jié)點(diǎn)的切分方法。基于節(jié)點(diǎn)的切分方法沒有取得較好效果的原因在于,在本文使用的Workspace 數(shù)據(jù)集中,當(dāng)20%的節(jié)點(diǎn)被用于驗(yàn)證模型時(shí),一部分重要節(jié)點(diǎn)在訓(xùn)練中可能沒有被充分利用,導(dǎo)致LSTM 方法未能學(xué)習(xí)到足夠有價(jià)值的信息。
本文通過實(shí)驗(yàn)不同的超參數(shù)組合尋找模型的最佳性能。本文主要調(diào)節(jié)的超參數(shù)有隱藏層數(shù)目、隱藏層大小、迭代輪數(shù)及回歸模型等,其中優(yōu)化器采用Adam 優(yōu)化算法,最大迭代輪數(shù)均為10 輪,實(shí)驗(yàn)結(jié)果如表3 所示。其中,LR表示線性回歸模型(Linear Regression),RT 與XGB 分別表示回歸樹(Regression Tree)和梯度提升樹(XGBoost)。
實(shí)驗(yàn)結(jié)果表明,當(dāng)隱藏層數(shù)為1,大小為8,線性模型選擇XGB 時(shí),模型的預(yù)測準(zhǔn)確率最高,每個(gè)時(shí)間層網(wǎng)絡(luò)上的準(zhǔn)確率相對(duì)較為穩(wěn)定。固定加權(quán)模型為XBG,在不同的參數(shù)設(shè)置下,每個(gè)時(shí)間層網(wǎng)絡(luò)上的Kendall's τ值如圖3 所示;固定模型參數(shù)設(shè)置,選取不同加權(quán)模型時(shí)各時(shí)間層網(wǎng)絡(luò)上的Kendall's τ值如圖4 所示。
Table 3 Experimental results of different parameter settings表3 不同參數(shù)設(shè)置實(shí)驗(yàn)結(jié)果
Fig.3 Comparison of model parameter settings and experimental results圖3 模型參數(shù)設(shè)置實(shí)驗(yàn)結(jié)果比較
Fig.4 Comparison of experimental results of different weighting models圖4 不同加權(quán)模型選取實(shí)驗(yàn)結(jié)果比較
以上結(jié)果表明,本文提出融合LSTM 方法的混合模型使時(shí)序網(wǎng)絡(luò)各時(shí)間層上關(guān)鍵節(jié)點(diǎn)的識(shí)別準(zhǔn)確率平均值比單一的層間相似度方法提高了1.44%,能更準(zhǔn)確地在時(shí)序網(wǎng)絡(luò)中預(yù)測出節(jié)點(diǎn)的重要性排序。此外,融合了LSTM 方法的混合模型雖然在時(shí)序數(shù)據(jù)前期(t≤4),由于沒有得到足夠的前序數(shù)據(jù)用于擬合模型,其識(shí)別準(zhǔn)確率略低于單一SSAM 方法的結(jié)果,但在時(shí)序網(wǎng)絡(luò)中后期(t≥5),混合模型得到的結(jié)果更優(yōu)。LSTM 模型的加入在一定程度上可以解決SSAM 方法在時(shí)序網(wǎng)絡(luò)中后期準(zhǔn)確率降幅過大的問題。
本文基于Workspace 數(shù)據(jù)集,通過融合深度學(xué)習(xí)方法與基于層間相似度的SSAM 方法,構(gòu)建混合模型挖掘時(shí)序網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn),獲取節(jié)點(diǎn)的重要性排序。實(shí)驗(yàn)結(jié)果表明,融合深度學(xué)習(xí)模型的方法預(yù)測出的節(jié)點(diǎn)重要性排序不僅準(zhǔn)確率均值與標(biāo)準(zhǔn)差優(yōu)于單一的SSAM 方法,而且能夠有效提升SSAM 方法在時(shí)間層網(wǎng)絡(luò)中靠后序列上的識(shí)別準(zhǔn)確率。本文通過實(shí)驗(yàn)證明融合深度模型能夠在一定程度上彌補(bǔ)傳統(tǒng)基于層間相似度方法的缺陷,并輔助其提高預(yù)測準(zhǔn)確率,該實(shí)驗(yàn)結(jié)果對(duì)時(shí)序網(wǎng)絡(luò)中重要節(jié)點(diǎn)的挖掘與識(shí)別研究工作具有積極意義。同時(shí),本文研究還存在一些不足,如特征選取和數(shù)據(jù)預(yù)處理可能會(huì)對(duì)結(jié)果造成一定影響,另外模型的選取、優(yōu)化及訓(xùn)練方式的調(diào)整都是可以繼續(xù)深入探索的方向。未來工作可以考慮融合更復(fù)雜的模型,選取更多數(shù)據(jù)和特征進(jìn)行挖掘與分析。