混合模型下的雅可比矩阵退火算法优化

王静红，冯 婵，柴变芳

1) 河北师范大学计算机与网络空间安全学院, 人工智能研究中心, 河北石家庄 050024；2)伊利诺伊大学香槟分校信息科学学院，厄巴纳-香槟市 61801，美国；3)河北工程技术学院人工智能与大数据学院，河北石家庄 050091；4)河北地质大学信息工程学院，河北石家庄 050031

随着大数据技术的发展，现有网络日渐成为大规模、动态性强的复杂网络[1]．互联网社交平台产生的多是此性质的网络，而在不确定的复杂网络前提下有效发现其内部结构是大数据分析的关键任务[2]．社区检测[3]是网络分析中一类流行的自动识别技术，如抑制整个网络的复杂性和发现网络中的关键节点．目前虽然已有大量的用于社区网络检测的方法，如层次聚类和分割聚类等方法，但这些方法仅用于检测链接紧密的子图．也有一些用于检测链接相对远距离子图的模型和方法，这些模型主要分为随机块模型算法[4]、变分贝叶斯推理[5]和用于网络探索的混合模型[6]．混合模型中期望最大化(expectation-maximization, EM) 算法的时间复杂度比随机块模型算法的小．王垚等[7]提出基于逆模拟退火的半监督高斯混合模型(anti-annealing semi-supervised Gaussian mixture model expectation maximization, ASGMM-EM)聚类算法，改善了半监督聚类中EM算法在计算过程中发生的局部收敛等问题．

本研究基于ASGMM-EM，采用雅可比矩阵，利用温度参数进行初始化，提出混合模型下的雅可比矩阵退火算法，以期解决网络结构局部最大值和收敛速度的问题．分别采用本研究提出的改进后的雅可比矩阵退火算法和ASGMM-EM算法测试其在真实网络数据集中的检测准确度、调整兰德系数值(adjusted Rand index, ARI)和标准互信息值(normalized mutual information, NMI)，结果表明，在混合模型中，本研究改进后的雅可比矩阵退火算法性能要优于ASGMM-EM算法．

1 半监督高斯混合模型下的逆模拟退火算法

确定性逆模拟退火期望最大化(deterministic anti-annealing EM, DAEM)算法能有效改善传统EM算法关于收敛慢的问题[8]，并且对传统的无监督类分布不均衡导致算法性能降低等不足做了优化，但该算法没有考虑类太松散或者太密集的半监督数据集合[7]．根据这种情况，王垚等[7]提出基于半监督高斯模型的逆模拟退火EM(anti-annealing semi-supervised GMM EM, ASGMM-EM)算法．

(1)

M步(maximization step)时估计模型参数αi、μi和Σi分别为

(2)

(3)

(4)

(5)

ASGMM-EM算法停止执行条件与文献[8]条件一致．

(6)

其中，Θk为第k次迭代后的模型参数；L(Θk)为Θk的最大似然估计值；τ为预设的阈值．

ASGMM-EM算法伪代码如图1．

图1 半监督高斯模型的逆模拟退火算法EM

2 混合模型的EM算法

混合模型的结构检测[6]在于通过将模型模拟到实际网络中来观察和推导．如果存在节点i到节点j的边缘，则具有N个节点的网络由邻接矩阵A表示，其元素Aij=1； 否则，Aij=0．设网络节点i在c个社区的参数设置为三元组({gi}, {πr}, {θri}). 其中，gi为节点i的组分配；πr为组r中的节点分布概率；θri为从组r到节点i中有向边的概率．设g为所有节点节点的组分配集合；π为所有组中的节点分布概率；θ为所有有向边的概率，则从节点i到节点j观察到的网络A可能性概率为

P(A,g|π,θ)=

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

(7)

式(7)中的似然对数是

M=lgP(A|π,θ)=

(8)

使用EM算法通过最大化对数似然M来估计参数，由Jensen不等式来算出M的下限为

(9)

其中，qir为节点i属于集群r的后验概率，满足∑qir=1归一化条件．

引入拉格朗日乘数λ， 则式(9)变为

(10)

(11)

(12)

其中，βj为第j个节点对应的逆温度参数．

令MM的导数在式(7)M步中为0，则更新方程为

(13)

(14)

其中，di为节点i的偏度．

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

目前，计算收敛性使用最广的两大工具是Hessian 矩阵[9]和Jacobian矩阵[10]．XIONG等[11]通过Hessian矩阵进行最优测试，但Hessian矩阵太复杂，无法分析其收敛性，而CHAOMURILIGE等[12]证明了Jacobian矩阵的有效性．因此，本研究通过分析Jacobian矩阵并引入对应于反温度的参数β，传统的EM算法是雅可比矩阵退火算法在温度参数β=1时的特殊情况，雅可比矩阵退火算法考虑了β一般情况．式(11)中q的后验概率可以重写为

(15)

其中，β为相应的温度参数．

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

图2 雅可比矩阵退火算法

当雅可比矩阵退火算法算法的收敛速率小于1时，就可得出一个理论上较小的β0值范围，范围内的β0都符合DAEM算法的标准．根据OLVER[13]的推论，如果算法收敛到稳定的固定点p*， 则在点p*处的雅可比矩阵的谱半径 (或最大特征值) 应当小于1．

采用容易计算和具有算法的收敛性质的能力的雅可比矩阵，在定向网络中计算出雅可比矩阵退火算法的收敛速率．

雅可比矩阵通项公式为

(16)

由式(15)得到雅可比矩阵．为了能得到雅可比矩阵，首先需要明确雅可比矩阵退火算法算法的参数映射．

雅可比矩阵退火算法每一轮都经过E步和M步，F(β)表示算法的β次迭代过程．其中，F(β)的分解形式为

采用式(17)和式(18)，雅可比矩阵退火算法算法的迭代公式可以为映射p(t+1)=F(β)(p(t))， 则节点i到r的映射为

(17)

(18)

(19)

引理1当i=1, 2,…,N,r=1, 2,…,c-1， 且j=1, 2,…,N,s=1, 2,…,c-1时，有

(20)

4 实验及结果分析

本研究通过实验验证基于雅可比矩阵分析的退火算法在真实网络上的初始参数数值并对算法的性能进行分析．

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

将优化算法分别在3个经典网络数据集books on politics(以下简称book)、adjnoun和football中进行测试，以此来检测该算法在判断真实网络的准确性．由文献[14]可知，当β=1.15时，检测混合模型下雅可比矩阵退火算法的收敛性较好．

首先，调查book、 adjnoun和football 3个真实网络数据集的β值对检测网络准确性的影响．由图3可见，在book网络数据集中，β的值对雅可比矩阵退火算法的检测准确性无影响；在adjnoun网络数据集中，当β>0.6时，雅可比矩阵退火算法的检测准确性偏低；在football网络数据集中，准确度随着β的增加而降低．因为β越小，雅可比矩阵退火算法越容易收敛到最大值．

图3 三个真实网络数据集中不同β值的雅可比矩阵退火算法检测准确性对比图Fig.3 Accuracy comparison of Jacobian matrix annealing algorithm with different β values in three real network data sets

4.2 对比分析

为更准确地探索混合模型下雅可比矩阵退火算法的性能，本研究设计了混合模型和半监督高斯混合模型(semi-supervised Gaussian mixture model, SGMM)，并从准确性、聚类结果之间相似性度量(ARI)和真实聚类的相似度(NMI)3个方面，分别在不同的β值下对两个模型进行测试．图4是逆模拟退火算法和改进的退火算法在SGMM中的实验结果测试对比．由图4可见，逆模拟退火算法在SGMM中使用收敛性更强，准确率更高．图5是逆模拟退火算法和改进的退火算法在混合模型中的实验测试结果．从图5可见，在混合模型中本研究改进的退火算法的性能更优．

图4 逆模拟退火算法和改进的退火算法在SGMM中β的准确性、ARI值、NMI值对比Fig.4 Comparison of the accuracy of β、ARI values and NMI values of the anti-annealing and imprved annealing algorithms in SGMM

图5 逆模拟退火算法和改进的退火算法在有向网络混合模型中β准确性、ARI值、NMI值的对比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

根据以上对比分析可得，在本研究中，混合模型的退火算法是在基于雅可比矩阵的退火算法上用来计算收敛速率的，使用确定性抗退火期望最大化算法可估计混合模型的参数．根据本研究提供的参数选择方法的理论下限选择初始参数，在不小于下限的情况下，改进的退火算法不会收敛到无意义的结果，而在不大于上限的情况下，改进的退火算法可避免收敛到局部最优的结果．

结 语

对比逆模拟退火算法和改进的退火算法，逆模拟退火算法更适用于SGMM中，通过实验中数据集和维度的分析测试，逆模拟退火算法不仅比传统的高斯混合模型EM算法准确率更高，也比改进的退火算法在SGMM中的准确率高．在逆模拟算法中，采用的是约束信息基于节点标记的，需由用户先验提供，并且适合在类不均衡、重叠度密集的情况下使用．改进的退火算法是在有向网络下进行研究，这是因为它更容易扩展到无向网络或加权网络．本研究基于雅可比矩阵，改进了退火算法，使其更适合用于清晰的社区结构下的真实网络．而且，改进后的退火算法，通过参数选择任务的收敛速率分析算法以便进行网络探索，更容易在参数的设计上扩展到其他算法的社区发现．