混合模型下的雅可比矩陣退火算法優(yōu)化

王靜紅，馮 嬋，柴變芳

1) 河北師范大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院, 人工智能研究中心, 河北石家莊 050024；2)伊利諾伊大學(xué)香檳分校信息科學(xué)學(xué)院，厄巴納-香檳市 61801，美國(guó)；3)河北工程技術(shù)學(xué)院人工智能與大數(shù)據(jù)學(xué)院，河北石家莊 050091；4)河北地質(zhì)大學(xué)信息工程學(xué)院，河北石家莊 050031

隨著大數(shù)據(jù)技術(shù)的發(fā)展，現(xiàn)有網(wǎng)絡(luò)日漸成為大規(guī)模、動(dòng)態(tài)性強(qiáng)的復(fù)雜網(wǎng)絡(luò)[1]．互聯(lián)網(wǎng)社交平臺(tái)產(chǎn)生的多是此性質(zhì)的網(wǎng)絡(luò)，而在不確定的復(fù)雜網(wǎng)絡(luò)前提下有效發(fā)現(xiàn)其內(nèi)部結(jié)構(gòu)是大數(shù)據(jù)分析的關(guān)鍵任務(wù)[2]．社區(qū)檢測(cè)[3]是網(wǎng)絡(luò)分析中一類(lèi)流行的自動(dòng)識(shí)別技術(shù)，如抑制整個(gè)網(wǎng)絡(luò)的復(fù)雜性和發(fā)現(xiàn)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)．目前雖然已有大量的用于社區(qū)網(wǎng)絡(luò)檢測(cè)的方法，如層次聚類(lèi)和分割聚類(lèi)等方法，但這些方法僅用于檢測(cè)鏈接緊密的子圖．也有一些用于檢測(cè)鏈接相對(duì)遠(yuǎn)距離子圖的模型和方法，這些模型主要分為隨機(jī)塊模型算法[4]、變分貝葉斯推理[5]和用于網(wǎng)絡(luò)探索的混合模型[6]．混合模型中期望最大化(expectation-maximization, EM) 算法的時(shí)間復(fù)雜度比隨機(jī)塊模型算法的小．王垚等[7]提出基于逆模擬退火的半監(jiān)督高斯混合模型(anti-annealing semi-supervised Gaussian mixture model expectation maximization, ASGMM-EM)聚類(lèi)算法，改善了半監(jiān)督聚類(lèi)中EM算法在計(jì)算過(guò)程中發(fā)生的局部收斂等問(wèn)題．

本研究基于ASGMM-EM，采用雅可比矩陣，利用溫度參數(shù)進(jìn)行初始化，提出混合模型下的雅可比矩陣退火算法，以期解決網(wǎng)絡(luò)結(jié)構(gòu)局部最大值和收斂速度的問(wèn)題．分別采用本研究提出的改進(jìn)后的雅可比矩陣退火算法和ASGMM-EM算法測(cè)試其在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中的檢測(cè)準(zhǔn)確度、調(diào)整蘭德系數(shù)值(adjusted Rand index, ARI)和標(biāo)準(zhǔn)互信息值(normalized mutual information, NMI)，結(jié)果表明，在混合模型中，本研究改進(jìn)后的雅可比矩陣退火算法性能要優(yōu)于ASGMM-EM算法．

1 半監(jiān)督高斯混合模型下的逆模擬退火算法

確定性逆模擬退火期望最大化(deterministic anti-annealing EM, DAEM)算法能有效改善傳統(tǒng)EM算法關(guān)于收斂慢的問(wèn)題[8]，并且對(duì)傳統(tǒng)的無(wú)監(jiān)督類(lèi)分布不均衡導(dǎo)致算法性能降低等不足做了優(yōu)化，但該算法沒(méi)有考慮類(lèi)太松散或者太密集的半監(jiān)督數(shù)據(jù)集合[7]．根據(jù)這種情況，王垚等[7]提出基于半監(jiān)督高斯模型的逆模擬退火EM(anti-annealing semi-supervised GMM EM, ASGMM-EM)算法．

(1)

M步(maximization step)時(shí)估計(jì)模型參數(shù)αi、μi和Σi分別為

(2)

(3)

(4)

(5)

ASGMM-EM算法停止執(zhí)行條件與文獻(xiàn)[8]條件一致．

(6)

其中，Θk為第k次迭代后的模型參數(shù)；L(Θk)為Θk的最大似然估計(jì)值；τ為預(yù)設(shè)的閾值．

ASGMM-EM算法偽代碼如圖1．

圖1 半監(jiān)督高斯模型的逆模擬退火算法EM

2 混合模型的EM算法

混合模型的結(jié)構(gòu)檢測(cè)[6]在于通過(guò)將模型模擬到實(shí)際網(wǎng)絡(luò)中來(lái)觀察和推導(dǎo)．如果存在節(jié)點(diǎn)i到節(jié)點(diǎn)j的邊緣，則具有N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)由鄰接矩陣A表示，其元素Aij=1； 否則，Aij=0．設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)i在c個(gè)社區(qū)的參數(shù)設(shè)置為三元組({gi}, {πr}, {θri}). 其中，gi為節(jié)點(diǎn)i的組分配；πr為組r中的節(jié)點(diǎn)分布概率；θri為從組r到節(jié)點(diǎn)i中有向邊的概率．設(shè)g為所有節(jié)點(diǎn)節(jié)點(diǎn)的組分配集合；π為所有組中的節(jié)點(diǎn)分布概率；θ為所有有向邊的概率，則從節(jié)點(diǎn)i到節(jié)點(diǎn)j觀察到的網(wǎng)絡(luò)A可能性概率為

P(A,g|π,θ)=

P(A|g,π,θ)P(g|π,θ)P(A|π,θ)=

(7)

式(7)中的似然對(duì)數(shù)是

M=lgP(A|π,θ)=

(8)

使用EM算法通過(guò)最大化對(duì)數(shù)似然M來(lái)估計(jì)參數(shù)，由Jensen不等式來(lái)算出M的下限為

(9)

其中，qir為節(jié)點(diǎn)i屬于集群r的后驗(yàn)概率，滿(mǎn)足∑qir=1歸一化條件．

引入拉格朗日乘數(shù)λ， 則式(9)變?yōu)?/p>

(10)

(11)

(12)

其中，βj為第j個(gè)節(jié)點(diǎn)對(duì)應(yīng)的逆溫度參數(shù)．

令MM的導(dǎo)數(shù)在式(7)M步中為0，則更新方程為

(13)

(14)

其中，di為節(jié)點(diǎn)i的偏度．

3 混合模型的雅可比矩陣退火算法

目前，計(jì)算收斂性使用最廣的兩大工具是Hessian 矩陣[9]和Jacobian矩陣[10]．XIONG等[11]通過(guò)Hessian矩陣進(jìn)行最優(yōu)測(cè)試，但Hessian矩陣太復(fù)雜，無(wú)法分析其收斂性，而CHAOMURILIGE等[12]證明了Jacobian矩陣的有效性．因此，本研究通過(guò)分析Jacobian矩陣并引入對(duì)應(yīng)于反溫度的參數(shù)β，傳統(tǒng)的EM算法是雅可比矩陣退火算法在溫度參數(shù)β=1時(shí)的特殊情況，雅可比矩陣退火算法考慮了β一般情況．式(11)中q的后驗(yàn)概率可以重寫(xiě)為

(15)

其中，β為相應(yīng)的溫度參數(shù)．

本研究提出的基于雅可比矩陣的退火算法描述如圖2．

圖2 雅可比矩陣退火算法

當(dāng)雅可比矩陣退火算法算法的收斂速率小于1時(shí)，就可得出一個(gè)理論上較小的β0值范圍，范圍內(nèi)的β0都符合DAEM算法的標(biāo)準(zhǔn)．根據(jù)OLVER[13]的推論，如果算法收斂到穩(wěn)定的固定點(diǎn)p*， 則在點(diǎn)p*處的雅可比矩陣的譜半徑 (或最大特征值) 應(yīng)當(dāng)小于1．

采用容易計(jì)算和具有算法的收斂性質(zhì)的能力的雅可比矩陣，在定向網(wǎng)絡(luò)中計(jì)算出雅可比矩陣退火算法的收斂速率．

雅可比矩陣通項(xiàng)公式為

(16)

由式(15)得到雅可比矩陣．為了能得到雅可比矩陣，首先需要明確雅可比矩陣退火算法算法的參數(shù)映射．

雅可比矩陣退火算法每一輪都經(jīng)過(guò)E步和M步，F(xiàn)(β)表示算法的β次迭代過(guò)程．其中，F(xiàn)(β)的分解形式為

采用式(17)和式(18)，雅可比矩陣退火算法算法的迭代公式可以為映射p(t+1)=F(β)(p(t))， 則節(jié)點(diǎn)i到r的映射為

(17)

(18)

(19)

引理1當(dāng)i=1, 2,…,N,r=1, 2,…,c-1， 且j=1, 2,…,N,s=1, 2,…,c-1時(shí)，有

(20)

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

本研究通過(guò)實(shí)驗(yàn)驗(yàn)證基于雅可比矩陣分析的退火算法在真實(shí)網(wǎng)絡(luò)上的初始參數(shù)數(shù)值并對(duì)算法的性能進(jìn)行分析．

4.1 基于雅可比矩陣退火算法性能分析

將優(yōu)化算法分別在3個(gè)經(jīng)典網(wǎng)絡(luò)數(shù)據(jù)集books on politics(以下簡(jiǎn)稱(chēng)book)、adjnoun和football中進(jìn)行測(cè)試，以此來(lái)檢測(cè)該算法在判斷真實(shí)網(wǎng)絡(luò)的準(zhǔn)確性．由文獻(xiàn)[14]可知，當(dāng)β=1.15時(shí)，檢測(cè)混合模型下雅可比矩陣退火算法的收斂性較好．

首先，調(diào)查book、 adjnoun和football 3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的β值對(duì)檢測(cè)網(wǎng)絡(luò)準(zhǔn)確性的影響．由圖3可見(jiàn)，在book網(wǎng)絡(luò)數(shù)據(jù)集中，β的值對(duì)雅可比矩陣退火算法的檢測(cè)準(zhǔn)確性無(wú)影響；在adjnoun網(wǎng)絡(luò)數(shù)據(jù)集中，當(dāng)β>0.6時(shí)，雅可比矩陣退火算法的檢測(cè)準(zhǔn)確性偏低；在football網(wǎng)絡(luò)數(shù)據(jù)集中，準(zhǔn)確度隨著β的增加而降低．因?yàn)棣略叫。趴杀染仃囃嘶鹚惴ㄔ饺菀资諗康阶畲笾担?/p>

圖3 三個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中不同β值的雅可比矩陣退火算法檢測(cè)準(zhǔn)確性對(duì)比圖Fig.3 Accuracy comparison of Jacobian matrix annealing algorithm with different β values in three real network data sets

4.2 對(duì)比分析

為更準(zhǔn)確地探索混合模型下雅可比矩陣退火算法的性能，本研究設(shè)計(jì)了混合模型和半監(jiān)督高斯混合模型(semi-supervised Gaussian mixture model, SGMM)，并從準(zhǔn)確性、聚類(lèi)結(jié)果之間相似性度量(ARI)和真實(shí)聚類(lèi)的相似度(NMI)3個(gè)方面，分別在不同的β值下對(duì)兩個(gè)模型進(jìn)行測(cè)試．圖4是逆模擬退火算法和改進(jìn)的退火算法在SGMM中的實(shí)驗(yàn)結(jié)果測(cè)試對(duì)比．由圖4可見(jiàn)，逆模擬退火算法在SGMM中使用收斂性更強(qiáng)，準(zhǔn)確率更高．圖5是逆模擬退火算法和改進(jìn)的退火算法在混合模型中的實(shí)驗(yàn)測(cè)試結(jié)果．從圖5可見(jiàn)，在混合模型中本研究改進(jìn)的退火算法的性能更優(yōu)．

圖4 逆模擬退火算法和改進(jìn)的退火算法在SGMM中β的準(zhǔn)確性、ARI值、NMI值對(duì)比Fig.4 Comparison of the accuracy of β、ARI values and NMI values of the anti-annealing and imprved annealing algorithms in SGMM

圖5 逆模擬退火算法和改進(jìn)的退火算法在有向網(wǎng)絡(luò)混合模型中β準(zhǔn)確性、ARI值、NMI值的對(duì)比Fig.5 Comparison of the accuracy of β、ARI values and NMI values of the anti-annealing and imprved annealing algorithms in a directed network hybrid model

根據(jù)以上對(duì)比分析可得，在本研究中，混合模型的退火算法是在基于雅可比矩陣的退火算法上用來(lái)計(jì)算收斂速率的，使用確定性抗退火期望最大化算法可估計(jì)混合模型的參數(shù)．根據(jù)本研究提供的參數(shù)選擇方法的理論下限選擇初始參數(shù)，在不小于下限的情況下，改進(jìn)的退火算法不會(huì)收斂到無(wú)意義的結(jié)果，而在不大于上限的情況下，改進(jìn)的退火算法可避免收斂到局部最優(yōu)的結(jié)果．

結(jié) 語(yǔ)

對(duì)比逆模擬退火算法和改進(jìn)的退火算法，逆模擬退火算法更適用于SGMM中，通過(guò)實(shí)驗(yàn)中數(shù)據(jù)集和維度的分析測(cè)試，逆模擬退火算法不僅比傳統(tǒng)的高斯混合模型EM算法準(zhǔn)確率更高，也比改進(jìn)的退火算法在SGMM中的準(zhǔn)確率高．在逆模擬算法中，采用的是約束信息基于節(jié)點(diǎn)標(biāo)記的，需由用戶(hù)先驗(yàn)提供，并且適合在類(lèi)不均衡、重疊度密集的情況下使用．改進(jìn)的退火算法是在有向網(wǎng)絡(luò)下進(jìn)行研究，這是因?yàn)樗菀讛U(kuò)展到無(wú)向網(wǎng)絡(luò)或加權(quán)網(wǎng)絡(luò)．本研究基于雅可比矩陣，改進(jìn)了退火算法，使其更適合用于清晰的社區(qū)結(jié)構(gòu)下的真實(shí)網(wǎng)絡(luò)．而且，改進(jìn)后的退火算法，通過(guò)參數(shù)選擇任務(wù)的收斂速率分析算法以便進(jìn)行網(wǎng)絡(luò)探索，更容易在參數(shù)的設(shè)計(jì)上擴(kuò)展到其他算法的社區(qū)發(fā)現(xiàn)．