·442· 智能系统学报 第13卷 0.95 后使α值衰减（α*=0.9），目的是使算法尽快收敛，最 0.90 大迭代次数为30次。得到的预测结果是符号网上 0.85 两节点间以正或负的符号相连的倾向，这一预测值 并不是离散的±1而是连续的值，因此得到预测结果 会070 后需要对预测结果进行划分，划分方法有直接划 0.65 分、全局划分、局部划分、从众划分，本文采用直 0.60 接划分，即预测结果≥0则预测符号为正，否则为 0.5 负。以下通过均方根误差(RMSE)和预测精确性 0.10.20.30.40.50.60.70.80.9 训练集数据占比% (Accuracy)评价各算法的预测效果。 (e)数据集Slashdotf的预测误差 3.2.3实验结果及讨论 0.95 图4的实验结果显示：随着抽样数据的增加， 0.90 MF-Bias 预测误差(RMSE)减小，预测精确度增加。基于低 0.85 秩矩阵分解的方法（包括MF、MF-Bias)获得了比其 0.80 ◆OD 他算法更好的预测效果，这说明在符号网络中节点 标注的偏置现象确实存在，同时，由于MF-Bias充 0.65 分考虑了节点的局部偏置特性，得到了相较于基本 0.60 矩阵分解算法好的预测精度，例如：在数据集Epin- 0.5 ions上当训练集为90%时，预测精确度为95.04%， 0.10.20.30.40.50.60.70.80.9 训练集数据占比% 相较于基本矩阵分解方法提高了0.6%，LR方法提 (①数据集Vikipedia的预测误差 高了2.3%，在其他两个数据集上也得到了与图4a) 图43个符号网络的预测结果 相似的结果（见图4(b)~(c),RMSE误差分析结果 Fig.4 Three signed networks predicted results (见图4(d)(①)与预测精确度得到相似的结论：本文 2)精确性(Accuracy) 所提MF-Bias模型获得了最小预测误差。实验表 用于评价预测算法对符号预测的准确程度，精 明：带有偏置的矩阵分解方法能够很好地对抗数据 确性计算公式为 稀疏带来的问题并提高预测效果。尽管两种启发式 TP+TN Accuracy P+N (11) 算法(D和OD)的预测精度都低于矩阵分解模型 和逻辑回归模型，但是它们的特点是计算复杂度 式中：TP表示对符号为正的边的预测正确的数目， 低，因为它们仅仅使用待预测边两端节点的局部信 TN表示符号为负的预测正确的数目，P+N则是需 息且能在一定程度上反映数据的结构特性。不同数 要预测的边的总数。Accuracy的值越大表示预测 据集ID和OD的效果截然不同，在Slashdot上OD 成功的概率越高。图4(d)、(e)、()给出了3个符号 好于ID,在Wiki上ID好于OD,可见仅考虑出度 网络在不同抽样比率下的精确性实验结果。 或入度作为预测依据不够合理，用户在不同数据集 3.2.2实验参数设置 上的行为特征值得进一步思考。 给定部分观察的符号网络，符号推断的目标就 3.3秩与预测精度 是通过符号网中已知边符号推断出未知边的符号。 本文构建的符号网络模型为有向网络，需要说明的 根据1.3节可知，符号网络邻接矩阵的秩与弱 是，所提算法也适用于无向符号网络。实验采用随 平衡结构间存在必然联系：当符号网络满足k平衡 机抽样的方法将数据集分为训练集(training data 条件时，网络节点可以被分成k个子集，邻接矩阵具 set)和测试集(testing data set)。训练集被看作部分 有低秩性且矩阵的秩恰好等于k,而矩阵分解的本质 观测的符号网络，利用测试集训练模型，然后对测 是做降维操作，将会把邻接矩阵分解为2个k行列 试集中边符号进行预测：测试集分别为整个符号网 的矩阵，那么到底将邻接矩阵分解为多少行合适 络的15%，30%，，90%。对于MF和MF-Bias算 呢？本文分别令k=1、2、4、5、6、7、8、16、32,对两 法，首先需要对矩阵P、Q进行初始化，这里我们令其 种矩阵分解算法在3个数据集进行精确度测试，所 为全1矩阵，有时也将P、Q的初始值设为随机矩 有实验均取测试集为90%，其余各参数与3.2节相 阵。另外，模型还需要确定3个参数，即k、α和入，其 同。实验结果如图5所示，实验结果显示：相较于 中K为符号网络的秩，取k=5;入为惩罚因子，取 k=1,k=2时预测精度有大幅提高，这支持了1.4节 =0.12;α是学习速度，初始值取a=0.2,且每次迭代 所述结构平衡理论的正确性，k值从2~5预测精度2) 精确性 (Accuracy) 用于评价预测算法对符号预测的准确程度，精 确性计算公式为 Accuracy = TP+TN P+N (11) TP TN P+N 式中： 表示对符号为正的边的预测正确的数目， 表示符号为负的预测正确的数目， 则是需 要预测的边的总数。Accuracy 的值越大表示预测 成功的概率越高。图 4(d)、(e)、(f) 给出了 3 个符号 网络在不同抽样比率下的精确性实验结果。 3.2.2 实验参数设置 ··· P Q P Q κ α λ κ κ λ λ α α 给定部分观察的符号网络，符号推断的目标就 是通过符号网中已知边符号推断出未知边的符号。 本文构建的符号网络模型为有向网络，需要说明的 是，所提算法也适用于无向符号网络。实验采用随 机抽样的方法将数据集分为训练集 (training data set) 和测试集 (testing data set)。训练集被看作部分 观测的符号网络，利用测试集训练模型，然后对测 试集中边符号进行预测；测试集分别为整个符号网 络的 15%，30%， ，90%。对于 MF 和 MF-Bias 算 法，首先需要对矩阵 、 进行初始化，这里我们令其 为全 1 矩阵，有时也将 、 的初始值设为随机矩 阵。另外，模型还需要确定 3 个参数，即 、 和 ，其 中 为符号网络的秩，取 = 5 ； 为惩罚因子，取 =0.12； 是学习速度，初始值取 =0.2，且每次迭代 后使α值衰减 (α*=0.9)，目的是使算法尽快收敛，最 大迭代次数为 30 次。得到的预测结果是符号网上 两节点间以正或负的符号相连的倾向，这一预测值 并不是离散的±1 而是连续的值，因此得到预测结果 后需要对预测结果进行划分，划分方法有直接划 分、全局划分、局部划分、从众划分[14] ，本文采用直 接划分，即预测结果≥0 则预测符号为正，否则为 负。以下通过均方根误差 (RMSE) 和预测精确性 (Accuracy) 评价各算法的预测效果。 3.2.3 实验结果及讨论 图 4 的实验结果显示：随着抽样数据的增加， 预测误差 (RMSE) 减小，预测精确度增加。基于低 秩矩阵分解的方法 (包括 MF、MF-Bias) 获得了比其 他算法更好的预测效果，这说明在符号网络中节点 标注的偏置现象确实存在，同时，由于 MF-Bias 充 分考虑了节点的局部偏置特性，得到了相较于基本 矩阵分解算法好的预测精度，例如：在数据集 Epin￾ions 上当训练集为 90% 时，预测精确度为 95.04%， 相较于基本矩阵分解方法提高了 0.6%，LR 方法提 高了 2.3%，在其他两个数据集上也得到了与图 4(a) 相似的结果 (见图 4(b)~(c))，RMSE 误差分析结果 (见图 4(d)~(f)) 与预测精确度得到相似的结论：本文 所提 MF-Bias 模型获得了最小预测误差。实验表 明：带有偏置的矩阵分解方法能够很好地对抗数据 稀疏带来的问题并提高预测效果。尽管两种启发式 算法 (ID 和 OD) 的预测精度都低于矩阵分解模型 和逻辑回归模型，但是它们的特点是计算复杂度 低，因为它们仅仅使用待预测边两端节点的局部信 息且能在一定程度上反映数据的结构特性。不同数 据集 ID 和 OD 的效果截然不同，在 Slashdot 上 OD 好于 ID，在 Wiki 上 ID 好于 OD，可见仅考虑出度 或入度作为预测依据不够合理，用户在不同数据集 上的行为特征值得进一步思考。 3.3 秩与预测精度 κ κ κ κ n κ κ κ κ 根据 1.3 节可知，符号网络邻接矩阵的秩与弱 平衡结构间存在必然联系：当符号网络满足 -平衡 条件时，网络节点可以被分成 个子集，邻接矩阵具 有低秩性且矩阵的秩恰好等于 ，而矩阵分解的本质 是做降维操作，将会把邻接矩阵分解为 2 个 行 列 的矩阵，那么到底将邻接矩阵分解为多少行合适 呢？本文分别令 =1、2、4、5、6、7、8、16、32，对两 种矩阵分解算法在 3 个数据集进行精确度测试，所 有实验均取测试集为 90%，其余各参数与 3.2 节相 同。实验结果如图 5 所示，实验结果显示：相较于 =1， =2 时预测精度有大幅提高，这支持了 1.4 节 所述结构平衡理论的正确性， 值从 2~5 预测精度 ౳᫥ᵥ䄛ጚ 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 䃙㏯䯲᪜ᢚࢌ%/a/c (e) ᪜ᢚ䯲Slashdot⮰䶰≷䄛ጚ MF−Bias MF LR ID OD ౳᫥ᵥ䄛ጚ 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 䃙㏯䯲᪜ᢚࢌ%/a/c (f) ᪜ᢚ䯲Wikipedia⮰䶰≷䄛ጚ MF−Bias MF LR ID OD 图 4 3 个符号网络的预测结果 Fig. 4 Three signed networks predicted results ·442· 智 能 系 统 学 报 第 13 卷