融合层叠泛化和代价敏感学习的社交网链路异常预测系统转让专利
申请号 : CN202010873940.7
文献号 : CN112073298B
文献日 : 2021-08-17
发明人 : 刘小洋 , 李祥 , 叶舒 , 苗琛香
申请人 : 重庆理工大学
摘要 :
权利要求 :
1.一种融合层叠泛化和代价敏感学习的社交网络链路异常预测系统,其特征在于,包括社交网络节点数据特征获取模块、超参数确定模块、结果预测模块和数据展示模块;
在社交网络节点数据特征获取模块中基模型包括:给定数据集D=(x1,y1),(x2,y2),(x3,y3),……,(xN,yN),其中, yi∈{0,1};当yi=0时,yi表示负类;当yi=1时,yi表示正类;i=1,2,3,…,N; 表示样本特征空间,n表示各个样本的特征个数;N表示数据集D中样本的个数;
T
由于wx+b取值是连续的,其中w表示列向量,维度为(n,1);T表示转置;x表示列向量,维度为(n,1);b表示列向量,维度为(1,1);因此它不能拟合离散变量,用它来拟合条件概率PT
(Y=1|x);但是对于w≠0,w x+b取值为实数R,不满足概率取值为0到1,因此采用广义线性模型;
由于单位阶跃函数不可微,对数几率函数是一个替代函数:于是有:
若y为x取正例的概率,则1‑y为x取反例的概率;两者比值称为几率odds,指该事件发生与不发生的概率比值,若事件发生的概率为P,则对数几率:将y视为类后验概率估计,重写公式有:也就是说,输出Y=1的对数几率是由输入x的线性函数表示的模型,这就是逻辑回归模T
型;当w +b的值越接近正无穷,P(Y=1|x)概率值也就越接近1;因此先拟合决策边界,再建立这个边界与分类的概率联系,从而得到了二分类情况下的概率;
逻辑回归模型的数学形式确定后,剩下就是如何去求解模型中的参数;在统计学中,使用极大似然估计法求解,即找到一组参数,使得在这组参数下,数据的似然度最大;令:p(xi)表示第i个样本在已知特征为xi的情况下的为正类(Y=1)的概率;
yi就是二分类问题给定数据集D中的,即是yi=y1,y2,y3,...,yn,yi∈{0,1};
对等式两边同取对数,写成对数似然函数:在机器学习中有损失函数的概念,其衡量的是模型预测错误的程度;取整个数据集上的平均对数似然损失,可以得到:其中,N表示数据集D中样本的个数;
即在逻辑回归模型中,最大化似然函数和最小化损失函数是等价的;
使用梯度下降法;优化的目标是找到一个方向,参数朝这个方向移动之后使得损失函数的值能够减小,这个方向往往由一阶偏导或者二阶偏导各种组合求得;逻辑回归的损失函数是:
梯度下降是通过J(w)对w的一阶导数来找下降方向,并且以迭代的方式来更新参数,更新方式为:
表示第i个样本权重参数的第k次迭代更新后的权重参数;
α表示学习率,表示1次参数迭代更新的快慢;
表示第i个样本权重参数的第k+1次迭代更新后的权重参数;
wi表示第i个样本的权重参数;
所述社交网络节点数据特征获取模块的数据输出端与超参数确定模块的数据输入端相连,超参数确定模块的数据输出端与结果预测模块的数据输入端相连,结果预测模块的数据输出端与数据展示模块的数据输入端相连;
所述社交网络节点数据特征获取模块用于获取社交网络节点数据,将获取的社交网络节点数据中的相似性指标作为基模型学习的特征;
所述超参数确定模块用于确定基模型的超参数;
所述结果预测模块用于对基模型的预测结果进行重新学习;得到最终的预测结果;
所述数据展示模块用于展示所述结果预测模块输出的结果。
2.根据权利要求1所述的融合层叠泛化和代价敏感学习的社交网络链路异常预测系统,其特征在于,在超参数确定模块中,确定基模型中超参数的方法包括交叉验证、网格搜索、早停法之一。
说明书 :
融合层叠泛化和代价敏感学习的社交网链路异常预测系统
技术领域
背景技术
信息学和统计领域都引起了越来越多的关注。社交网络中的链接预测是一项基本的网络分
析任务,指如何预测在网络中尚未通过已知信息(如网络节点和网络结构)连接的两个节点
之间生成链接的可能性。应该注意的是,链接预测包括对现有链接的预测和对未来链接的
预测。
方法,相似性方法(包括节点相似性和结构相似性)和似然估计方法。到目前为止,基于相似
度的链路预测方法已经取得了一系列成果,并相应地广泛应用于各个领域。基于相似度链
路预测方法可以进一步分为三类,即基于邻居的,基于路径的和基于随机游走的方法。最简
单的链接预测方法基于以下假设:两个节点如果有更多共同的邻居,则更可能具有链接。
Newman首先使用Common Neighbor index(CN)来衡量相似度随后提出了两个节点的索引,
并提出了CN的许多变体,例如Salton index,Resource Allocation index(RA),Adamic‑
Adar index(AA),Jaccard CoefficientHub Promoted index(HPI),Leicht‑Holme‑Newman
index(LHN),Preferential Attachment index(PA)等。根据对真实网络的广泛实验,结果
表明,RA指数表现最佳,而PA指数的整体表现最差。基于路径方法使用两个节点之间的路径
计算节点对的相似性。示例包括Local path index(LP)和Katz指数。LP索引仅考虑长度为2
和3的本地路径。Katz索引基于整体所有路径,并且可以在实际网络上获得高性能。基于随
机游走的方法使用随机游走来对网络中节点之间的交互进行建模。一些代表性的方法包括
Average Commute Time(ACT),SimRank,RandomWalk with Restart(RWR)和Local Random
Walk(LRW)。ACT指数基于平均值随机步行者从一个节点开始到达另一节点所需的步骤数。
SimRank测量分别从两个不同的节点开始的两个随机游走者将在某个节点相遇的时间。RWR
是一个PageRank算法的直接应用。LRW是一个本地索引,只关注几步随机游动。众所周知,
LRW方法优于ACT索引,其计算复杂度低于ACT和RWR。第二类方法是基于似然估计的。
Clauset et al.提出了一种通用技术推断网络的层次结构,并进一步将其用于预测丢失的
链接。The stochastic block model将网络节点分为几组,任意两个节点之间的连接概率
为决定节点属于哪个组。Pan et al.基于预定义的结构哈密顿量最大化观察到的网络的可
能性,并通过将链接添加到的条件概率对未观察到的链接评分观察到的网络。Liben‑
Nowell和Kleinberg提出了链接预测的似然估计方法。之后,相继获得了基于似然分析的新
的链接预测方法这些最大似然方法虽然计算复杂度较高,但可以提供有价值的见解。
不稳定并且无法获得鲁棒性。基于似然估计的思想具有很强的数学意义和较高的预测精
度,但是需要严格的假设,并且计算量大,不适合大规模网络。
发明内容
预测模块和数据展示模块;
块的数据输出端与数据展示模块的数据输入端相连;
示各个样本的特征个数;N表示数据集D中样本的个数;
T
拟合条件概率P(Y=1|x);但是对于w≠0,若w等于零向量则没有什么求解的价值,w x+b取
值为实数R,不满足概率取值为0到1,因此考虑采用广义线性模型;
归模型;当w+b的值越接近正无穷,P(Y=1|x)概率值也就越接近1;因此逻辑回归的思路
是,先拟合决策边界,再建立这个边界与分类的概率联系,从而得到了二分类情况下的概
率;
令:
偏导或者二阶偏导各种组合求得;逻辑回归的损失函数是:
异常链路;若最后的预测结果FinalPredictionLabel小于预设结果阈值,则两节点为正常
链路。
附图说明
具体实施方式
图描述的实施例是示例性的,仅用于解释本发明,而不能理解为对本发明的限制。
信息学和统计领域都引起了越来越多的关注。社交网络中的链接预测是一项基本的网络分
析任务,指如何预测在网络中尚未通过已知信息(如网络节点和网络结构)连接的两个节点
之间生成链接的可能性。应该注意的是,链接预测包括对现有链接的预测和对未来链接的
预测。
方法,相似性方法(包括节点相似性和结构相似性)和似然估计方法。到目前为止,基于相似
度的链路预测方法已经取得了一系列成果,并相应地广泛应用于各个领域。基于相似度链
路预测方法可以进一步分为三类,即基于邻居的,基于路径的和基于随机游走的方法。最简
单的链接预测方法基于以下假设:两个节点如果有更多共同的邻居,则更可能具有链接。
Newman首先使用Common Neighbor index(CN)来衡量相似度随后提出了两个节点的索引,
并提出了CN的许多变体,例如Salton index,Resource Allocation index(RA),Adamic‑
Adar index(AA),Jaccard CoefficientHub Promoted index(HPI),Leicht‑Holme‑Newman
index(LHN),Preferential Attachment index(PA)等。根据对真实网络的广泛实验,结果
表明,RA指数表现最佳,而PA指数的整体表现最差。基于路径方法使用两个节点之间的路径
计算节点对的相似性。示例包括Local path index(LP)和Katz指数。LP索引仅考虑长度为2
和3的本地路径。Katz索引基于整体所有路径,并且可以在实际网络上获得高性能。基于随
机游走的方法使用随机游走来对网络中节点之间的交互进行建模。一些代表性的方法包括
Average Commute Time(ACT),SimRank,RandomWalk with Restart(RWR)和Local Random
Walk(LRW)。ACT指数基于平均值随机步行者从一个节点开始到达另一节点所需的步骤数。
SimRank测量分别从两个不同的节点开始的两个随机游走者将在某个节点相遇的时间。RWR
是一个PageRank算法的直接应用。LRW是一个本地索引,只关注几步随机游动。众所周知,
LRW方法优于ACT索引,其计算复杂度低于ACT和RWR。第二类方法是基于似然估计的。
Clauset et al.提出了一种通用技术推断网络的层次结构,并进一步将其用于预测丢失的
链接。The stochastic block model将网络节点分为几组,任意两个节点之间的连接概率
为决定节点属于哪个组。Pan et al.基于预定义的结构哈密顿量最大化观察到的网络的可
能性,并通过将链接添加到的条件概率对未观察到的链接评分观察到的网络。Liben‑
Nowell和Kleinberg提出了链接预测的似然估计方法。之后,相继获得了基于似然分析的新
的链接预测方法这些最大似然方法虽然计算复杂度较高,但可以提供有价值的见解。
不稳定并且无法获得鲁棒性。基于似然估计的思想具有很强的数学意义和较高的预测精
度,但是需要严格的假设,并且计算量大,不适合大规模网络。
链路预测方法(LLSLP)。
性计算,并获得了融合指标的特征。在此基础上再采用Logistic Regression模型对融合特
征进行学习,并使用Cross‑validation(交叉验证)、Grid searching(网格搜索)和Early
stopping(早停法)方法进行优化,使得提出的LLSLP获得更多的互补性和更稳定的效果以
及良好的泛化性。
且采用7个不同的评估指标,更加全面的衡量算法、模型的性能。将本文提出的LLSLP方法与
单一的传统算法以及模型进行了对比。
I,PA,AA,RA,LP,Katz,ACT,Cos以及RWR等15种链路预测算法平均高出10.52%。并且在数据
集类别极度不平衡的情况下,相对于传统15种链路预测算法,F1‑score值和MCC值分别取得
了3.25%‑9.73%、5.90%‑10.21%的提升。在不同数据集下做出较好的预测,结果分析验
证了该算法的有效性,稳定性和泛化性。
对比分析了实验结果。最后,在第5节对本文进行了总结。另外,本文附录部分补充了相关的
实验数据图,包含了ROC图、PR图以及混淆矩阵图。
二分类问题为例介绍Logistic Regression:
示样本特征空间,n表示各个样本的特征个数;N表示数据集D中样本的个数。
T
拟合条件概率P(Y=1|x)。但是对于w≠0(若等于零向量则没有什么求解的价值),w x+b取
值为实数R,不满足概率取值为0到1,因此考虑采用广义线性模型。
归模型。当w+b的值越接近正无穷,P(Y=1|x)概率值也就越接近1。因此逻辑回归的思路
是,先拟合决策边界(不局限于线性,还可以是多项式),再建立这个边界与分类的概率联
系,从而得到了二分类情况下的概率。
率)最大。令:
偏导或者二阶偏导各种组合求得。逻辑回归的损失函数是:
的模型,可以有效提高泛化预测精度。如果模型过于复杂,变量值稍微有点变动,就会引起
预测精度问题。正则化之所以有效,就是因为其降低了特征的权重,使得模型更为简单。正
则化一般会采用L1范式或者L2范式,其形式分别为Φ(w)=||x||1,Φ(w)=||x||2。
得到的解比较平滑(不是稀疏),但是同样能够保证解中接近于0(但不是等于0,所以相对平
滑)的维度比较多,降低模型的复杂度。
为划分的指标(信息增益),XGBoost则利用到二阶导数。他们共同的不足是,计算信息增益
需要扫描所有样本,从而找到最优划分点。在面对大量数据或者特征维度很高时,它们的效
率和扩展性很难使人满意。解决这个问题的直接方法就是减少特征量和数据量且不影响精
确度,有部分工作根据数据权重采样来加速boosting的过程,但由于GBDT没有样本权重不
能应用。
但每个数据实例有不同的梯度,根据计算信息增益的定义,梯度大的实例对信息增益有更
大的影响,因此在下采样时,应该尽量保留梯度大的样本(预先设定阈值,或者最高百分位
间),随机去掉梯度小的样本。证明此措施在相同的采样率下比随机采样获得更准确的结
果,尤其是在信息增益范围较大时。
中,虽然特征量比较多,但是由于特征空间十分稀疏,是否可以设计一种无损的方法来减少
有效特征呢?特别在稀疏特征空间上,许多特征几乎是互斥的(例如许多特征不会同时为非
0值,像(one‑hot),可以捆绑互斥的特征。最后,将捆绑问题归约到图着色问题,通过贪心算
法求得近似解。
方向表示为{g1,…,gn},决策树通过最优切分点(最大信息增益点)将数据分到各个节点。
GBDT通过分割后的方差衡量信息增益。
然后,将数据根据特征j的分裂点 将数据分到左右子节点。
估计值,所以是
很大时), 将趋于0,即数据量越大,误差越小,精度越高;
因此,在GOSS准确的情况下,GOSS泛化
误差近似于全量的真实数据。另一方面,采样将增加基学习器的多样性(因为每次采样获得
的数据可能会不同),这将提高泛化性。
绑起来才不会丢失信息。如果两个特征并不是完全互斥(部分情况下两个特征都是非0值),
可以用一个指标对特征不互斥程度进行衡量,称之为冲突比率,当这个值较小时,可以选择
把不完全互斥的两个特征捆绑,而不影响最后的精度。EFB的算法步骤如下:
一特征,通过仔细设计特征算法,从特征捆绑中构建了与单个特征相同的特征直方图。这种
方式的间直方图时间复杂度从O(#data*#feature)降到O(#data*#bundle),由于#bundle<
<#feature,所以能够极大加速GBDT的训练过程而且损失精度。但是有两个问题:
Algorithm1所示。
其冲突率小的现有捆绑特征,要么建立新的捆绑。算法Algorithm 1的时间复杂度为O(#
feature)且在训练之前仅处理一次。当特征数量没有那么大时这个复杂度是可以接受的,
但如果面对几百万个特征就会受到很大的影响。为了大大提高效率,提出了一种不需要建
图且更有效率的排序策略:依据非0值的数量进行排序。这与依据度数排序是相似的,因为
非0值的数量多有几率制造更大的冲突。因为只改变了排序策略,所以省略新算法的细节以
避免重复。
存储离散的箱子而不是连续的特征值,可以通过使互斥特征分别从属不同的箱子来构造捆
绑特征。这可以通过给原始特征添加偏移量来完成。举个例子,假设在一个捆绑特征里有两
个特征需要合并。开始A特征的取值范围是[0,10),B特征的取值范围是[0,20)。然后给特征
B添加一个10的偏移量,那么特征B的取值就变成了[10,30)。之后就可以合并特征A和B去代
替原始的A和B,合并后的取值为[10,30]。算法细节在Algorithm 2中体现。
的非0取值。实际,通过用表记录数据中的非0值,来忽略零值特征,达到优化基础的直方图
算法。通过扫描表中的数据,建直方图的时间复杂度将从O(#data)降到O(#non_zero_
data)。然而,在整棵树的建立过程中都需要花费额外的内存和算力去保存和更新这张表。
在LightGBM中实现了这种优化并将其作为一个基本功能。值得注意的是,这种优化方法与
EFB算法并不是冲突的,因为当捆绑后的特征依然稀疏时仍可以使用它。
被正确组合时,可以得到更精确或更具有鲁棒性的模型。在大多数情况下,这些基本模型本
身的性能并不是非常好,可能是因为它们具有较高的偏置(例如,低自由度模型),也可能是
因为它们的方差太大导致鲁棒性不强(例如,高自由度模型)。集成方法的思想是通过将这
些弱学习器的偏置或方差结合起来,从而创建一个强学习器(或“集成模型”),从而获得更
好的性能。通常主要采用以下三种方法组合弱学习器:
预测结果。
同质弱学习器。其次,Stacking学习用元模型组合基础模型,而Bagging和Boosting则根据
确定性算法组合弱学习器。Stacking的概念是学习几个不同的弱学习器,并通过训练一个
“元模型”来组合它们,然后基于这些弱模型返回的多个预测结果输出最终的预测结果。因
此,为了构建Stacking模型,需要定义两个东西:想要拟合的L个学习器以及组合它们的元
模型。例如,对于分类问题来说,可以选择KNN分类器、Logistic Regression和SVM作为弱学
习器,并决定学习神经网络作为元模型。然后,神经网络将会把三个弱学习器的输出作为输
入,并返回基于该输入的最终预测。所以,假设想要拟合由L个弱学习器组成的Stacking集
成模型,必须遵循以下步骤:
训练基础模型,另一半数据用于训练元模型。为了克服这种限制,可以使用类似k折交叉验
证的训练方法。这样所有的观测数据都可以用来训练元模型:对于任意的观测数据,弱学习
器的预测都是通过在k‑1折数据(不包含已考虑的观测数据)上训练这些弱学习器的实例来
完成的,如图1所示。
个观测数据生成相关的预测,然后使用所有这些预测结果训练元模型。Stacking方法会训
练一个元模型,该模型根据较低层的弱学习器返回的输出结果生成最后的输出。
相似度指标被视为网络中任何两个节点的特征。然后,选择Logistic Regression和
LightGBM作为基本模型。最后,引入Stacking思想,对基础模型的预测结果进行重新学习,
以获得更好的预测结果。
对分别划分为原始训练集 与原始测试集
个相似性指数作为节点nx和ny之间的15个不同特征,获得所有节点对的特征集F。在原始网
络中,如果节点对连接,则归为类别1,否则将其归为类别0。因此,获得了一组网络节点对的
类别集C。最后,将特征集与类别集组合得到训练集Dtrain与测试集Dtest。
节点对的数量比没有连接边缘的节点对的数量要少得多。同时,在链路预测中通常更关注
有连接边缘的节点对,即少数类。因此,训练集与测试集中的类别不平衡。在机器学习中,对
于不平衡样本的学习,容易出现过度拟合问题,导致模型泛化能力较差,并使预测毫无意
义。对于不平衡数据,为了不改变原始数据分布,本文使用代价敏感学习(Cost‑sensitive
Learning)策略。代价敏感学习给少数类样本分配较高的误分类代价,而给多数类样本分配
较小的误分类代价。通过这种方式代价敏感学习在学习器的训练过程中提高了少数类别样
本的重要性,以此减轻分类器对多数类的偏好。以Logistic Regression为例对代价敏感学
习进行简要介绍。
LR与LightGBM,并使用Cross‑validation、Grid searching和Early stopping的方法确定
模型的超参数,得到2个基学习器对15个传统相似性指标的融合特征。接着将基学习器学到
的2个融合指标合并构建,得到新的训练集 与测试集 并且将 放入第二个学习
层中进行学习。第2层中只包含一个Meta‑Classifier,为LR模型,同样在学习过程中使用
Cross‑validation、Grid searching和Early stopping确定模型超参数。最后用Meta‑
Classifier训练得到的模型H(x)=h'(h1(x),h2(x),…,hT(x))对新测试集 进行预测,
获得最后的预测结果FinalPredictionLabel:若最后的预测结果FinalPredictionLabel大
于或者等于预设结果阈值 ,则两节点为异常链路 ;若最 后的预 测结果
FinalPredictionLabel小于预设结果阈值,则两节点为正常链路。提出的算法细节如
Algorithm 3所示。
确性与泛化性。本文使用Logistic Regression和LightGBM作为两个基模型对训练集进行
训练,采用5折Cross‑validation,Grid searching和Early stopping确定基模型的超参
数。在基模型训练完成后,引入Stacking方法集成上述两个基模型。将通过Logistic
Regression和LightGBM预测的链接的存在和不存在的概率重新作为特征。由于Stacking的
有效性主要来自于特征抽取,而表示学习中总是伴随着过拟合问题,因为第二层的特征来
自于第一层数据的学习,那么第二层数据中的特征中不应包括原始特征,以达到降低过拟
合的风险。同时,为了降低过拟合问题,第二层分类器应该是较为简单的分类器,广义线性
如Logistic Regression是一个较好的选择。在特征的提取过程中(也就是第一层的学习),
已经使用了复杂的非线性变换,因此在输出层不宜使用太过于复杂的分类器。这一点与神
经网络的激活函数或者输出层类似,都是较为简单的函数,并且能控制复杂度。另外使用
Logistic Regression不但可以配合L1正则化选取有效的特征,从第一层的基模型中删除
不必要的模型,节省运算开销,进一步防止过拟合,而且Logistic Regression的输出结果
可以被理解为概率,这一点较适宜于部分分类任务。综上所述,本文选取Logistic
Regression作为Meta‑Classifier,对已学习到的新特征进行重新训练,并确定最终的预测
结果。LLSLP模型框架如图2所示。
域的共同作者网络。HMT,FBK和ADV是社交网络。EML是一个共享电子邮件的个人的网络。精
心选择了这些网络以涵盖广泛的属性,包括不同的大小、平均度、聚类系数、异质性指数和
不平衡系数IR(Imbalance Ratio)为连接边与非连接边的比值。下表中列出了在实验中使
用的网络的结构特性的摘要,详细信息如表1所示。
文使用AUC、Recall等7个指标来检测模型的性能。AUC、Recall和Precision是评估分类问题
的常用指标。对于样本类别不平衡的数据,本文额外使用Confusion Matrix、Precision‑
Recall Curve、F1‑score、MCC(Matthews correlation coefficient)测量指标。Confusion
Matrix能直观、具体的观察模型的预测结果。MCC是介于‑1与+1之间的相关系数,通常被认
为是平衡度量,即使类别大小差异很大的情况下也可以使用。Precision‑Recall Curve与
F1‑score综合体现Precision和Recall之间的关系。因此,在本文中额外考虑4个指标来评
估LLSLP方法。
为匹配矩阵)。矩阵的每一行代表预测类中的实例,而每一列代表实际类中的实例。以二分
类为例:
好。混淆矩阵在基本的统计结果上可以延伸得到如图3中的5个指标:
一般情况下准确率高、召回率就低;召回率低、准确率就高。
表2~表4分别为基于节点局部信息的相似性指标、基于节点全局信息的相似性指标与基于
随机游走的相似性指标。
制,本文选择了AUC、Precision、Recall、F1‑score、MCC作为主要评估指标,而有关本文提出
的LLSLP在实验数据集上的其余评估指标将会在附录展示。其中AUC、Precision、Recall、
F1‑score的取值均在[0,1]之间,指标值越高代表模型在这类数据集上的效果越好。MCC取
值在[‑1,1]之间,指标值为1代表模型在这类数据集上预测与实际完全一致,取值为0表示
预测的结果与随机预测结果相当,反之,取值‑1代表模型效果在这类数据集上表现预测结
果与实际结果完全不一致。不同算法下的各个数据集AUC、Precision、Recall、F1‑score以
及MCC的实验结果如表5~表9所示。
在UGP网络上的AUC的值是最高的,为0.9998,要优于传统的CN,Sal和LightGBM等对比算法、
模型;基模型LR也较好,比较接近提出的LLSLP方法。传统算法中表现最好的Cos的AUC值为
0.77197,提出的LLSLP方法的AUC值要高出Cos的AUC的值29.536%。而基模型LightGBM则表
现相对较差,AUC值为0.63459,远远小于提出的LLSLP和另外一个基模型LR,可见基模型
LightGBM对UGP数据集的预测不太准确。但这不意味着LightGBM是一个不好的模型,比如在
NSC数据集中,基模型LightGBM的预测表现优于除了提出的LLSLP以外的算法、模型的预测
表现。可以看出,面对不同的数据集,基模型LR和LightGBM的性能有一定的差异,但提出的
LLSLP在面对各种不同的数据集仍具有较好的性能,表明其具有较好的稳定性。
Precision值比传统的算法以及模型都要高。但同样需要指出并非在实验的所有数据集上
都表现良好。比如在NSC数据集上的Precision值的低于传统的CN,AA算法,当然很大程度上
是由于基模型LR表现太差;在EML与FBK数据集上的Precision值低于基模型LR。在SMG数据
集上的Precision值低于CN;在KHN数据集上的表现不及传统算法CN与基模型LightGBM。所
以提出的LLSLP在实验数据集上的Recall值整体较高,但是仍然存在一定的不足。下面分析
Recall值,由表7可知,提出的LLSLP在各个数据集上Recall值的总体表现优与传统算法CN、
AA、LP以及RWR等,传统算法的Recall值平均在50%左右,而LLSLP最低的时候也在90%以
上。但也观察到LLSLP的Recall值与基模型的Recall值相接近,不得不承认LLSLP的高
Recall值一定程度上受益于2个基模型(Logistic Regression,LightGBM)。由于一般情况
下Precision指标与Recall指标呈负相关关系,即Precision值越大时,Recall值越小;反
之,Precision值越小时,Recall值越大。对于不同的数据集以及不同的实际应用的需要,不
能仅通过Precision值或Recall值来评价一个算法或模型的好坏,而F1‑score结合了前两
者,综合衡量一个算法或模型的性能,因此从表8中可以看出,LLSLP在实验数据集上的F1‑
score值位居前2,证明了提出的LLSLP整体的良好性能。值得注意的是,对于二分类而言,可
能分类器的F1‑score值较高,而MCC值偏低。表明单一的指标是无法完全衡量分类器的所有
优点与缺点。
数类的偏好,这会对数据量较少的类别的识别带来困难。对于模型在极端不平衡的社交网
络数据集上的性能评价,MCC展现了其良好的区分性,传统的相似性算法在类别不平的情况
下的整体表现是相对较差的,而本文提出的LLSLP在类别极度不平衡的情况下也能取得相
对较好的性能,可以证实提出的LLSLP是有效的。
上的具体ROC曲线下面积,PA为0.84832,Katz为0.52412,ACT为0.83605,LightGBM为
0.80372,其余的算法和模型都在0.90000以上)。表明仅依赖ROC曲线判断出LLSLP与传统算
法、模型的差异程度是不够的,还需借助其他指标进行性能评估。
的区分度,但在对基模型的区分上,还存在一定的局限性。值得一提的是,传统的算法HPI、
PA、LHN‑I、ACT、COS、RWR虽然拥有较高的AUC值(从表5可以观察得到HPI为0.98592,LHN‑I为
0.96262,COS为0.97020,RWR为0.99126),但在PR曲线上的表现却很差,当然这是由于它们
的Precision值较高时,Recall值较低;或者Recall值较高,Precision值较低(从表6、表7可
以观察到在FBK数据集上HPI、LHN‑I、Katz、Cos、RWR的Precision值分别为0.11996、
0.03803、0.00138、0.00632、0.01471,而Recall值分别为0.74376、0.80827、0.60511、
0.97767、0.98744)。因此导致他们的F1‑score值不高(由表8可知在FBK数据集上HPI、LHN‑
I、ACT、Cos、RWR的F1‑score值分别为0.20615、0.07264、0.00276、0.01255、0.02889)。注意
PA和ACT的PR曲线图也很差,是由于它们的Precision值和Recall值都较低(PA、ACT的
Precision值分别为0.09422,0.00022,Recall值分别为0.19520、001866),从而导致它们的
F1‑score值偏低,分别为0.12709、0.00043。表明F1‑score的确有效的结合了Precision和
Recall,更客观的评价的算法及模型的性能。所以,进一步证实了仅仅依靠单个指标对一个
算法或模型进行评价是不全面的,并不能完全衡量其性能,所以用多个评价指标进行衡量
是有必要的并且全面的。
多,反之,越深则代表数量越少。混淆矩阵图是作为对PR曲线图一个很好的补充。可以从图6
中发现提出的LLSLP分类错误的结果数量相对于传统的算法和基模型更低,具有更好的性
能。值得注意的一点是,设定偏差百分比为两种错误分类的数量之差的绝对值与两者之间
的较大值的百分比,可以观察到基模型LR与LightGBM预测的错误结果中,明显产生了对某
一类别的偏向,前者更倾向于把样本预测为正类,后者更倾向于把样本预测为负类(由图6
知LR将类别0预测为类别1的数量为4455,将类别1预测为类别0的数量为157,偏差百分比为
96.476%;而LightGBM把类别0预测为类别1的数量为569,将类别1预测为类别0的数量为
3451,偏差百分比为83.512%)。同时可以从图6观察到其他传统算法在FBK数据集上产生的
偏向程度更加严重,比如CN将类别0预测为类别1的数量为1342,将类别1预测为类别0的数
量为14670,偏差百分比为90.852%;LHN‑I将类别0预测为类别1的数量为359469,将类别1
预测为类别0的数量为3370,偏差百分比为99.063%;甚至Cos与RWR产生了更严重的偏差,
Cos将类别0预测为类别1的数量为2760377,将类别1预测为类别0的数量为35,偏差百分比
为99.999%;RWR将类别0预测为类别1的数量为1174532,将类别1预测为类别0的数量为45,
偏差百分比为99.996%。而提出的LLSLP则较为平衡,并没有产生对某一类别的过度偏向
(LLSLP把类别0预测为类别1的数量为2103,将类别1预测为类别0的数量为1500,偏差百分
比只有28.673%),这也证明本文提出的LLSLP的确比其他传统算法和模型更有效,很好的
结合了各个基模型的优点。
能也会随之提升。当然必须承认,尽管本文提出的LLSLP在各个评估指标上取得不错的成
绩,但还是有一定的改进空间,从整体实验结果中不难看出,LLSLP的性能表现一定程度上
取决于2个基模型(Logistic Regression,LightGBM)的表现,所以对于基模型的选择尤其
重要。并且随着使用的基模型数量越多,则模型的复杂度越高,运行时间越长。值得注意的
是,即便LLSLP的表现受其基模型影响,但具有一定数量的基模型的前提下,当其中一个基
模型在某个数据集上表现不佳的情况下,其性能表现所受的影响不会太大,这正是其稳定
性的体现。
现有相似度指标,从而进一步提高链路预测的稳定性和准确性,本文将15个相似度指标进
行了组合。这15个相似性指标代表网络的不同特征。本文提出的LLSLP方法不仅集成了指
标,而且还利用了Logistic Regression与LightGBM模型。将Logistic Regression和
LightGBM作为基模型,15个指标作为模型要学习的特征,通过Cross‑validation,Grid
searching和Early stopping确定基模型的超参数;然后,利用集成模型的Stacking思想,
以Logistic Regression作为Meta‑Classifier,提出了一种新的链路预测方法,该方法考
虑了不同相似性指标的互补性和不同模型的互补性,因此其稳定性更强。为了证明其有效
性和可行性,最后以10个网络为例。与单一指标和模型相比,用AUC,Precision等7个指标以
验证所提出的LLSLP方法的合理性、有效性、可靠性和稳定性。本文的主要贡献是整合现有
的相似性指标,并在模型集成中引入了Stacking思想,用于社交网络的链路预测。
发明的范围由权利要求及其等同物限定。