-
摘要: 提出了一种基于视觉知识加工模型的目标识别方法. 该加工模型结合目标定位、模板筛选和MFF-HMAX (Hierarchical model and X based on multi-feature fusion)方法对图像进行学习, 形成相应的视觉知识库, 并用于指导目标的识别. 首先, 利用Itti模型获取图像的显著区, 结合视觉通路中What和Where通道的位置、大小等特征以及视觉知识库中的定位知识确定初期候选目标区域; 然后, 采用二步去噪处理获取候选目标区域, 利用MFF-HMAX模型提取目标区域的颜色、亮度、纹理、轮廓、大小等知识特征, 并采用特征融合思想将各项特征融合供目标识别; 最后, 与单一特征以及目前的流行方法进行对比实验, 结果表明本文方法不仅具备较高的识别效果, 同时能够模仿人脑学习视觉知识的过程形成视觉知识库.Abstract: A novel object recognition method based on visual knowledge processing model is presented. Combined with object localization, template screening and hierarchical model and X based on multi-feature fusion (MFF-HMAX) method, the visual knowledge processing model yields a visual knowledge base which can be used as a guide in object recognition. Firstly, significant areas of the image can be obtained via Itti model; according to these areas and "what" and "where" information, such as location, size, etc., the candidate objects are conformed. Secondly, MFF-HMAX model is used to extract various features, like color, intensity, texture, contour, size, etc., from the objects denoised by the two-step denoising process. After multi-feature fusion, the features can be used in object recognition. Finally, the method is tested and compared with single feature method and current popular methods. The results show that this method can not only get good performance in improving accuracy of object detection, but also yield a base of visual knowledge by imitating the forming process in human brain.
-
实际网络的结构随时间动态变化,导致传统的静态网络分析方法不能有效挖掘网络信息[1].时序链路预测方法可以根据网络的历史信息推测网络中将会产生的边,是一种重要的动态网络分析方法,具有极大的理论和应用价值[2].如可以用于Facebook、微信等社交平台上的朋友推荐[3],帮助解决商品推荐中的数据稀疏问题[4-5],减少生物实验成本[6],推进复杂网络演化研究等.
近年来,时序链路预测问题受到了多个领域的广泛关注,许多时序链路预测方法相继被提出.其中一类是对网络结构特征直接进行分析的方法[7-9],文献[7]采用时间序列分析的方法对网络中节点对连边次数随时间变化的规律进行分析,并结合其他静态网络结构特征进行链路预测;文献[8]提出了一种进化算法对网络中的拓扑特征和属性特征进行整合,以提高链路预测精度.还有一类是基于机器学习的方法[10-11],文献[10]认为边的连接紧密性随时间不断变化,并据此提出了一种名为"时间分"的新特征,该特征可以用于有监督的学习方法中;文献[11]考虑到链路预测面临正负样本不均衡的问题,提出了一种基于半监督学习的链路预测方法.矩阵分解和张量分解理论在时序链路预测中也发挥了重要作用[12-13],文献[12]将网络动态数据合并为一个矩阵,利用截断奇异值分解对未来可能产生的连边进行预测;此外,该文献还提出了一种原始的将张量分解用于时序链路预测的方法.文献[13]利用矩阵分解和图规则化技术整合网络属性信息和结构信息来进行链路预测.
对未来可能产生的边进行预测的核心是对网络演化规律的把握.上述文献大都采用一定的数学模型,直接在边的层面上对网络的演化规律进行分析.从边的层面对链路进行预测,虽然非常直观,但是忽略了其他网络结构信息.模体是非常重要的一种网络结构,很多复杂网络的重要性质就是借助模体被发现的[14].网络模体演化作为网络微观演化的一种,是网络演化分析的重要组成部分[15].文献[16]研究表明,网络模体演化规律可以从很大程度上描述网络结构特征的变化.因此,边的形成也可能是网络模体不断变化、相互作用的结果.研究模体演化与时序链路预测间的关系,进而根据模体的演化规律对链路进行预测具有重要的意义.
但是这方面的研究仍处于起步阶段[17-20],文献[17]直接从网络的微观演化入手,通过分析网络中经常出现的模式的时序演变来对链路进行预测.三元组是社会网络中非常重要的一类模体,三元组演化在动态社会网络分析中起到了非常重要的作用[18-21].文献[18]分析了Enron网络中相邻快照间的三元组模体转换概率,将转换概率的均值用于链路预测中;文献[19]从多个方面对三元组进行衡量,并将之用于异质网络的时序链路预测中.但是,上述文献大都只对模体的变化进行了实验上的统计,缺乏对模体演化规律的进一步分析.
基于上述分析,本文对社会网络中三元组模体的演化规律进行了研究,并以此为基础,提出了一种基于模体演化的时序链路预测算法.本文的主要贡献如下: 1)在多个实际网络中对三元组的演化规律进行实证研究,发现了一些有趣的现象.2)综合考虑网络结构变化特点,从链路预测角度提出一种三元组重要性指标,实验表明,该指标可以有效提高链路预测精度.3)综合考虑不同三元组类型转换过程中的相互影响,引入非负张量分解和时间序列分析对三元组转换规律进行分析,并以此为基础,提出一种基于三元组演化的时序链路预测方法.4)在真实数据集上与其他方法进行比较,证明本方法更加有效.
本文第1节对一些基本概念进行了介绍,第2节是实验数据说明,第3节介绍提出的基于模体演化的链路预测方法,第4节将本文提出的算法和其他链路预测算法在三个实际网络中进行对比分析,最后第5节给出结论.
1. 相关概念
1.1 时序链路预测问题描述
随时间变化的无向无权无环网络 $G=(g_1,g_2,\cdots,g_t,\cdots,g_T)$ 由T个快照组成,其中,gt表示T时刻网络G的快照, $V(g_t)$ 表示快照gt的节点集,E(gt)表示快照gt的边集.动态链路预测问题可以转化为:已知网络G中g1到gt的拓扑信息,给定一种链路预测方法,为 $g_{t+1}$ 中的任意节点对 $(v_x,v_y)$ 赋予一个分数值,该分数值可以理解为与两节点的连边概率正相关的一个数值.
1.2 三元组
本文对无向网络中三元组模体的变化规律进行深入分析,并将这种变化运用于链路预测中,以得到更高的预测精度.本文对三元组中的节点进行区分,对不同的节点进行编号,得到无向网络中的8种三元组,如图 1所示.图中标识的三元组ID具有唯一性,将在本文其他章节得到应用.
张量(Tensor)是矩阵在高维空间上的扩展,与矩阵相比,它能描述更多的因素,可以很自然地表达高维数据而不丢失信息,因而能在最大程度上保持数据的内在结构特性[22].一个三阶张量可以表示为 $Z \in {{\bf{R}}^{{I_1} \times {I_2} \times {I_3}}}$ ,其元素为 ${z_{ijk}},i \in {I_1},j \in {I_2},k \in {I_3}$ .
张量分解可以挖掘张量的潜在结构及其不同维间的关联[23],一般可以分为CP(CanDecomp/ParaFac)分解和Tucker分解两类,其中,CP分解可以看作是矩阵奇异值分解的高阶扩展,在可解释性、解的唯一性方面具有优势[22].一个三阶张量的CP分解可以表示为
$ \hat Z=\sum\limits_{r=1}^R {{\lambda _r}} {a_r} \circ {b_r} \circ {c_r}=[\lambda;A,B,C] $
(1) 其中,符号 $\circ $ 表示外积,被加数 $\lambda_{r}a_r\circ b_r\circ c_r$ 表示一个组件,设 $\| a_r\|=\| b_r\|=\| c_r\|=1$ , $\lambda_r$ 表示第r个组件的权重,R表示组件的个数. $[\lambda;{\pmb A},{\pmb B},{\pmb C}]$ 是CP分解的缩写形式,其中, ${\pmb A}\in {\bf R}^{I_1\times R},{\pmb B}\in{\bf R}^{I_2\times R},{\pmb C}\in{\bf R}^{I_3\times R}$ 都称作因子矩阵,表示张量在各个维度上的主成分.CP分解过程如图 2所示.
更特别地,非负CP分解的目标是将非负张量 $Z \in {\bf{R}}_+^{{I_1} \times {I_2} \times {I_3}}$ 分解为非负因子之和:
$ Z \approx \sum\limits_{r=1}^R {{\lambda _r}} {a_r}^\circ {b_r}^\circ {c_r} $
(2) 此分解可以通过求解最优化问题得到:
$ \begin{array}{l} \min \left\| {Z - \sum\limits_{r=1}^R {{\lambda _r}} {a_r}^\circ {b_r}^\circ {c_r}} \right\|\\ {\rm{s}}.{\rm{t}}.\quad {\lambda _r} \ge 0,\;{a_r} \ge 0,\;{b_r} \ge 0,\;{c_r} \ge 0,\\ \qquad \qquad \qquad \qquad \quad \;r=1,2,\cdots,R \end{array} $
(3) 2. 实验数据
本文采用三种社会网络数据集对算法进行评估分析.Condmat网络[10]包含了1995年~2000年间,凝聚物理问题中共19464次多机构合作记录,以年为单位划分网络快照.Enron数据集[24]包含了2001年1月1日~2002年3月31日间,Enron机构内部员工的邮件通信记录,以月为时间间隔建立快照.Facebook数据集[25]包含了2006年11月~ 2009年1月,60290位用户以"墙评论"形式的交流记录,以月为时间间隔建立快照.这些网络的参数信息如表 1所示.
表 1 实验数据集参数表Table 1 Parameters of experimental data setsCondmat Enron Facebook 节点数 17636 22 477 60 290 总边数 88 036 164 081 838 090 快招数 6 16 52 3. 算法设计
3.1 算法总体描
本文根据三元组的演化规律对网络中节点对的连边可能进行预测.首先对前两个相邻快照之间的三元组进行统计,得到这两个快照中不同三元组类型之间的转换概率,并构成这两个快照间的三元组转换概率矩阵;以此类推,得到所有相邻快照间的三元组转换概率矩阵,并将其合并为三阶张量.然后对此三元组转换概率张量进行CP分解,对其中的时间因子C进行时间序列分析后合并各因子矩阵,得到T时刻到T+1时刻的三元组转换概率矩阵.根据该三元组转换概率矩阵和T时刻的网络快照可以得到T+1时刻各个三元组的生成概率;最后根据T+1时刻中各个三元组的生成概率和不同三元组的重要性来预测T+1时刻网络中节点对的连边可能.下面对各个步骤进行详细分析.
3.2 三元组转换概率矩阵分析
对网络中的历史信息进行统计,可以得到相邻快照之间,不同三元组类型的转换概率.常用的统计方法是对网络中的节点进行遍历,但是时间复杂度很高.在对数据进行分析时发现,第1类型三元组转换到第1类型三元组的情况占三元组转换总数的很大一部分,传统的对节点遍历的方法将大部分时间花费在了统计此类情况上.复杂网络具有稀疏性,以Facebook数据集为例,网络节点总数为60290,因此网络中可能产生的节点连边总数为60290×(60290-1)/2,但是每个时刻产生的连边的均值为16117,仅占可能产生的总边数的百万分之八.考虑到这种网络的稀疏性,本文提出了一种快速统计方法.方法的核心思想是先对含有连边的节点进行研究,即先统计第2类型三元组转换到第8类型三元组的情况,此类转换情况包含第2~8类型三元组转换到第1类型的情况和第1类型三元组转换到第2 ~8类型三元组的情况.然后用转换总数减去上述情况的转换数,得到第1类型到第1类型三元组的转换数.最后进行归一化,得到三元组各个类型之间的转换概率.快速统计方法只需要对相邻快照间存在连边的节点进行统计即可得到第2~8类型三元组的转换情况.由网络稀疏性可知,网络中实际存在的边只占网络中可能存在的边的很小一部分,因此,此快速统计方法适用于大规模网络.
三元组的类型数为8,因此,本文定义一个大小为8×8的矩阵来描述相邻时刻间不同三元组类型的转换概率,称为三元组转换概率矩阵(Triad changement matrix,TCM).矩阵中各元素的值为
$ \begin{align} {TCM}_t{(i,j)}=P({tr}_i[t]\rightarrow {tr}_j[t+1]) \end{align} $
(4) 其中, ${tr}_i[t]$ 表示T时刻第i类三元组(第1.2节中编号为i的三元组), ${TCM}_t(i,j)$ 表示从t时刻到t+1时刻第i类三元组转换到第j类三元组的概率,即对应时刻TCM矩阵第i行第j列元素.
图 3~5是各数据集的TCM矩阵色谱图,虽然不同数据集中,不同时刻间的TCM矩阵不同,但是这些TCM矩阵仍然表现出一些相同的规律:
1) 所有TCM矩阵左上角元素值都最大,表明整个网络比较稀疏,许多三元组保持着第1类型,即三元组中不存在连边.
2) TCM矩阵最左边一列的元素值较大,表明已经存在连边的三元组在下一时刻中不再存在连边的可能性很大.
3) TCM矩阵对角线上的值普遍较高,表明三元组类型转换时存在"惯性",有较大可能维持原有状态.
4) TCM矩阵左下角的值普遍高于右上角,除最左边的元素较大外,左下角其他元素的值都较为均衡,意味着三元组中各边都较易消失,且消失概率大致相同.
通过对所有TCM矩阵的进一步分析,发现除上述共同规律外,不同三元组类型间的转换概率随着时间的变化也表现出了一些特定的趋势.本文以Facebook数据集为例,描述这些规律.图 6为Facebook数据集中不同三元组类型间转换概率随时间变化的色谱图.
图 6 Facebook数据集不同三元组类型间转换概率随时间变化色谱图Fig. 6 Chromatogram of triad transition probabilities that change with time in Facebook network从图 6中可以发现以下规律:
1)从图 6(a)中可以看出,第1类型三元组较为稳定,基本维持不变,这是因为第1类型三元组中各节点间没有发生联系,随着时间的变化,该三元组内各节点发生联系的可能性仍然较小.
2)从图 6(b)~6(d)中可以看出,第2类型到第4类型三元组随着时间变化表现出了稳定的趋势,或者维持原有状态,或者转换为第1状态;这是因为三元组中只有两个节点间发生了联系,三元组内各个节点还没有都发生联系,三元组内部连接还不够紧密、稳固,可以将这种三元组称为"弱三元组".
3)从图 6(e)~6(h)中可以看出,第5类型到第8类型的三元组有一定概率转换为其他各个类型的三元组,这是因为三元组中至少两个节点间发生了联系,各个节点间的联系较强,可以将这种三元组称为"强三元组".弱三元组转换为强三元组的概率较小,但是强三元组有较大概率转换为弱三元组.
4)有些转换概率还表现出了周期性的趋势,如图 7所示,第6类型三元组到第2类型三元组的转换概率、第7类型三元组到第3类型三元组的转换概率和第8类型三元组到第5类型三元组的转换概率的变化具有周期性;而另外一些三元组转换概率则较为稳定,在一定周期内没有发生较大变化,如第5类型三元组到第8类型三元组的转换概率.
图 7 Facebook数据集中部分随时间变化的三元组转换概率示意图Fig. 7 Diagram of some triad transition probabilities that change with time in Facebook network3.3 三元组转换概率预测
上述规律表明,三元组的演化是非线性的,不同三元组类型间也存在影响,因此,不能采用简单的如求均值的方式对三元组的转换概率进行预测.非负张量可以很自然地描述三元组的转换概率而不丢失信息,张量分解可以挖掘不同三元组转换概率之间的潜在关系.大部分三元组转换概率表现出了周期性趋势或平稳趋势,时间序列分析可以很好地对这些趋势进行预测.因此,本文采用非负张量分解和时间序列分析的方法对三元组转换概率进行进一步分析和预测.本文构建三元组转换概率张量(Triad changement tensor,TCT)来描述所有相邻时刻间三元组的转换概率,张量中的元素为
$ \begin{array}{l} TCT(i,j,t)=TC{M_t}(i,j)=\\ \qquad P(t{r_i}[t] \to t{r_j}[t+1]) \end{array} $
(5) 该张量与TCM矩阵的关系可以表示为
$ \begin{align} TCT=(TCM_1,TCM_2,\cdots,TCM_t,\cdots,TCM_T) \end{align} $
(6) 不同的三元组转换概率间存在关联,同一三元组转换概率本身随时间变化时也存在关联,因此,采用非负CP分解对TCT张量进行分解,挖掘张量各维之间的潜在关系及各维数据自身的潜在结构. $AB^{\rm T}$ 衡量了不同类型三元组间的转换关系,而C中包含了这种关系随时间变化的信息;对时间因子矩阵C进行时序分析,得到 $c_{T+1,r}$ 后,可以得到T时刻到T+1时刻的三元组转换似然矩阵(Triad changement likelihood matrix,TCLM):
$ \begin{align} TCLM_T(i,j)=\sum_{r=1}^R\lambda_r(a_{i,r}\cdot b_{j,r}\cdot c_{T+1,r}) \end{align} $
(7) $TCLM_T$ 矩阵包含了T时刻到 $T+1$ 时刻的三元组转换信息,但是不满足概率条件,因此,对 $TCLM_T$ 矩阵按行进行归一化,得到T时刻到T+1时刻的三元组转换概率矩阵 $TCM_T$ .本文采用Matlab工具箱tensor toolbox 2.5中[26]的cp-nmu函数对TCT张量进行CP非负分解,算法源码由此工具箱提供,采用的时序分析模型是较为简单的指数衰减模型:
$ \begin{array}{*{20}{l}} {{c_{T+1,r}}=}&{\;\alpha {c_{T,r}}+\alpha(1 - \alpha){c_{T - 1,r}}+}\\ {}&{\;\alpha {{(1 - \alpha)}^2}{c_{T - 2,r}}+\cdots+{{(1 - \alpha)}^{T - 1}}{c_{1,r}},}\\ {}&{\qquad \qquad \quad \;r=1,\cdots,R且0 <\alpha <1} \end{array} $
(8) 其中,α是平滑参数,设α=0.5,ct,r是对TCT张量进行CP分解后得到的时间因子矩阵C中的元素,表示第r个组件中t时刻的时间因子值.除指数衰减模型外,也可以采用Holter-Winter等其他时序分析方法来分析三元组转换概率随时间变化的潜在趋势[27],对未来的时间因子值进行推测.
3.4 三元组重要性分析
一个节点对包含在不同的三元组中,如图 8所示,节点对AB包含在ABC、ABD、ABE三个三元组中.每个包含该节点对的三元组的状态都为预测其连边可能提供了参考,但不同的三元组对预测的重要性不同,"活跃"的三元组往往能起到更加积极的作用.三元组的活跃度可以表现为两个方面,一方面是三元组内部各节点间连边的频率,频率越高,三元组越活跃;另一方面是三元组形成闭合的频率,网络演化中,三元组形成闭合的次数越多,说明该三元组内部节点间关系越紧密,对预测节点对的连边也越重要.此外,历史连边的产生时间距预测时刻点越远,则对预测时刻点的节点对产生的影响越小[28],本文用指数衰减模型描述这种影响.
基于上述分析,本文定义三元组重要性指标来描述三元组对于链路预测的重要性程度:
$ \begin{align} W_i=\beta\sum_{t=1}^{ T}\theta_1^{T-t}l_{i,t}+\gamma\sum_{t=1}^{ T}\theta_2^{T-t}trc_{i,t}+1 \end{align} $
(9) 其中,Wi表示三元组i的重要程度,li,t表示t时刻三元组i中各节点的连边个数,trci,t表示t时刻三元组i是否闭合,闭合为1,不闭合为0,β 、γ为调控参数,θ1、θ2取值为(0,1),用来衡量历史连边的产生时间对链路预测的影响.
3.5 根据TCM矩阵和三元组重要性指标进行链路预测
根据 $TCM_T$ 矩阵和计算得到的三元组重要性指标,可以得到T+1时刻网络中每个节点对的连边可能值:
$ \begin{align} score_{i,j}=\sum_{m=1}^{M_{tr}}W_m\times TCM(m) \end{align} $
(10) 其中, $M_{tr}$ 表示T+1时刻所有包含节点对ij的三元组总数,Wm表示第m个三元组的重要程度,TCM(m)表示T+1时刻包含节点对ij的第m个三元组从时刻T到时刻T+1的转换概率.
将本文提出的算法称为TCM链路预测算法,算法伪码如下所示.
算法1.基于模体演化的链路预测方法
输入. 1到T时刻网络快照.
输出. T+1时刻节点对的连边概率.
1 initialize: calculate TCM matrix of T snapshot to T+1 snapshot
2 for each node pair
3 for each triad including the node pair
4 calculate the importance of the triad by(9)
5 end
6 calculate link probability of the node pair by(10)
7 end
4. 实验结果和分析
4.1 实验设计
为测试算法可行性,本文在上述三个数据集上进行实验.实验程序采用Matlab编写,在装有32位Win7系统的单机上运行,该单机内存为4GB,Matlab版本为R2013a.
本文与TTM[18]、HPLP[29]、PA[30]和TS[7]四种时序链路预测方法进行对比.TTM方法首先对三元组转换概率进行了统计研究,并将其用于链路预测中.PA方法是链路预测中常用的基准比较算法.HPLP方法是目前公认较好的一种基于特征的链路预测有监督学习框架,TS方法是一种经典的时序链路预测方法.
文献[31]对链路预测中各个评价指标进行了比较,研究表明,当正负样本非常不均衡时,采用精确度--召回率曲线下面积(Area under precision-recall curve,AUPR)值作为评价指标更加合理,但是之前的链路预测方法大多采用接收者操作特征曲线下面积(Area under receiver operating characteristic curve,AUC)值作为评价指标,严谨起见,本文采用AUC值和AUPR值作为评价指标.
在计算AUC值和AUPR值时,采用如图 9所示的方法确定训练集和测试集.首先选取网络中前▽ T时刻的快照作为训练集,以第▽ T+1时刻的网络快照为测试集,计算一次AUC值和AUPR值.然后将时间窗口顺次移动一个步长,重新计算AUC值和AUPR值,循环十次后,对所有AUC值和AUPR值求平均作为对应时间窗口▽ T的AUC值和AUPR值.
4.2 实验结果分析
4.2.1 有效性验证
选取时间窗口为5,三元组重要性指标中各参数都设定为0.5,其他算法中各参数按原文默认值设定,得到实验结果如表 2~4所示.从表中可以看出,采用AUC值进行衡量时,TCM算法在Condmat数据集中取得了很好的预测精度,但在Enron数据集中略低于TS算法,在Facebook数据集中也只略优于TS算法.但是当采用AUPR值作为评价指标时,TCM算法都取得了很好的预测效果,并且同其他算法相比,优势明显.例如,在Enron数据集中,TCM算法比TS算法提高了23\%.因此,本文提出的算法具有较高的预测精度.从表中还可以看出,许多情况下,时序链路预测算法优于静态链路预测方法,TS算法和TCM算法都取得了较好的效果,虽然TTM算法只是对三元组的转换概率进行了简单的统计,但是也取得了和HPLP算法相比拟的预测效果,说明了根据网络模体演化规律进行链路预测具有可行性.
表 2 Facebook数据集中各算法预测精度表Table 2 Accuracy of different methods in Facebook networkPA HPLP TTM TS TCM AUC 0.52 0.76 0.79 0.83 0.84 AUPR 0.03 0.06 0.08 0.1 0.13 表 3 Enron数据集中各算法预测精度表Table 3 Accuracy of different methods in Enron networkPA HPLP TTM TS TCM AUC 0.8 0.91 0.81 0.92 0.89 AUPR 0.04 0.17 0.21 0.23 0.30 表 4 Condmat数据集中各算法预测精度表Table 4 Accuracy of different methods in Condmat networkPA HPLP TTM TS TCM AUC 0.59 0.68 0.76 0.81 0.92 AUPR 0.24 0.25 0.22 0.25 0.35 TTM算法与TCM算法都对三元组的转换概率进行了分析,但TTM算法缺乏对不同三元组转换概率随时间变化的规律的进一步挖掘和对三元组重要性程度的区分.为更详细直观地比较这两种算法的性能,绘制出三个数据集中TCM算法与TTM算法的ROC曲线和PR曲线如图 10~12所示.从图中可以更直观地看出,只有在Facebook数据集中,采用ROC曲线衡量时,二者预测效果相差不大,其他情况下TCM算法都优于TTM算法.这是因为,TTM算法对三元组演化规律的挖掘还不够深入,TCM算法不仅研究了相邻时刻间的三元组转换规律,还从整体上研究了三元组转换概率随时间变化的规律,并合理衡量了不同三元组在预测中的作用.
图 10 Facebook数据集TCM算法和TTM算法性能对比图Fig. 10 Performance contrastgures of TCM algorithm and TTM algorithm in Facebook network
图 11 Enron数据集TCM算法和TTM算法性能对比图Fig. 11 Performance contrastgures of TCM algorithm and TTM algorithm in Enron network
图 12 Condmat数据集TCM算法和TTM算法性能对比图Fig. 12 Performance contrastgures of TCM algorithm and TTM algorithm in Condmat network4.2.2 算法时间复杂度分析
本文提出的算法可以分为三个主要部分,一是三元组重要性指标的计算,二是三元组转换概率矩阵的计算,三是计算节点间可能产生的连边.三元组重要性指标计算的时间复杂度为O(tn).其中,t为时间窗口,n表示网络节点总数.如果采用传统的对网络进行遍历的方式计算三元组转换概率矩阵,则时间复杂度为O(tn3),但是本文提出了一种快速的统计方法,该方法的时间复杂度为O(tL2),其中,L为相邻两时刻网络快照的连边总数.通过比较可知,这种快速方法有效地降低了此步骤的时间复杂度.在计算单个节点对的连边可能时,本文采用与计算三元组转换概率矩阵相类似的思想,其时间复杂度为O(l),其中,l为t时刻网络快照中的连边总数.计算全网络所有节点对的连边可能的时间复杂度则为O(ln2).
4.2.3 时间窗口及三元组重要性指标对TCM算法的影响
Condmat数据集的快照数只有6,因此,本文使用Facebook数据集和Enron数据集来分析时间窗口和三元组重要性指标对TCM算法的影响,评价指标采用AUPR,实验结果如图 13所示.
图 13 时间窗口及三元组重要性指标对TCM算法的影响Fig. 13 Influence of time window and the triad importance index to TCM method1) 时间窗口对TCM算法的影响.从图中可以看出,多数情况下,随着时间窗口的增加,TCM算法的预测精度有逐渐提升的趋势,这是由于算法可以利用更多的网络时序信息.但是当时间窗口的大小增加到一定程度时,算法精度反而下降,这应该是由于初始时刻距要预测时刻较远,该时刻快照的拓扑信息反而会对链路预测产生负面影响.此外,当β=0,γ=1时,算法预测精度随时间窗口缓慢增加,但增加幅度较小,这可能是由于网络比较稀疏,三元组闭合次数较少,此种情况下的三元组重要性指标不能很好地衡量三元组在链路预测中的重要程度,即使时间窗口增加时,算法也无法很好地利用网络时序信息.
2) 三元组重要性指标对TCM算法的影响.本文比较了β=0.5/γ=0.5,β=0/γ=1,β=1、γ=0三种情况下,TCM算法的预测精度.从图中可以看出,当β=1、γ=0时,TCM算法预测精度最高,β=0.5、γ=0.5时,算法预测精度次之,β=0、 γ=1时,算法预测精度最差.这可能是由于网络数据比较稀疏,三元组闭合次数较少,不能准确反映三元组的重要程度.实验结果还不能完全说明在链路预测中,三元组内部节点连接次数比三元组闭合次数重要.
5. 结论
时序链路预测与网络演化分析密不可分,将网络微观演化规律用于链路预测可以取得较好的预测效果,反之根据链路预测效果也可以从一定程度上评估网络演化机理.本文从这一角度出发,对社会网络中具有重要结构和功能意义的一种模体-三元组的演化规律进行了分析,进而提出了一种基于模体演化的链路预测方法.在三个真实数据集上的实验结果表明,利用网络微观演化规律进行链路预测具有可行性,该方法有较好的预测效果.此外,本文还通过实验分析了时间窗口、三元组重要性指标对实验结果的影响.
本文从网络模体入手,对网络中三元组的演化规律进行了初步探索,并提出了一种新的时序链路预测方法.但在以后的工作中,仍需对三元组演化规律、网络微观演化规律、网络中连边的形成规律以及它们之间的关系进行更深入的理论分析.此外,进一步降低算法时间复杂度并在更多的数据集上测试算法的有效性也是我们下一步的研究方向.
-
图 2 基于视觉知识加工模型的目标识别方法图
Fig. 2 Object recognition method based on visual knowledge processing
图 4 原图与候选目标对象图的对比图
Fig. 4 Comparison between the original images and the candidate object
图 5 二步去噪处理后的轮廓信息图
Fig. 5 The contour information maps after two-step denoising processing
图 7 不同方法针对Caltech 101数据集的分类效果对比图
Fig. 7 Performance of different methods for Caltech 101
图 8 Caltech 101数据集不同类型的分类效果对比图
Fig. 8 Performance for different categories of Caltech 101
图 9 Pascal 2007数据集不同类型的分类效果对比图
Fig. 9 Performance for different categories of Pascal 2007
表 1 本文方法参数设置
Table 1 Parameters setting of our method
Band $\Sigma$ Filt sizes $\delta$ $\lambda$ $N$$^\Sigma$ Orient $\theta$ Patch $n_j$ 1 7 & 9 2.8 & 3.6 3.5 & 4.6 8 0 4$\times$4 2 11 & 13 4.5 & 5.4 5.6 & 6.8 10 3 15 & 17 6.3 & 7.3 7.9 & 9.1 12 $\dfrac{\pi}{4}$ 8$\times$8 4 19 & 21 8.2 & 9.2 10.3 & 11.5 14 5 23 & 25 10.2 & 11.3 12.7 & 14.1 16 $\dfrac{\pi}{2}$ 12$\times$12 6 27 & 29 12.3 & 13.4 15.4 & 16.8 18 7 31 & 33 14.6 & 15.8 18.2 & 19.7 20 $\dfrac{3\pi}{4}$ 14$\times$14 8 35 & 37 17.0 & 18.2 21.2 & 22.8 22 
下载: 导出CSV
-
[1] Serre T, Wolf L, Poggio T. Object recognition with features inspired by visual cortex. In: Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). San Diego, CA: IEEE, 2005. 994-1000 [2] 朱庆生, 张敏, 柳锋. 基于HMAX特征的层次式柑桔溃疡病识别方法. 计算机科学, 2008, 35(4): 231-232Zhu Qing-Sheng, Zhang Min, Liu Feng. Hierarchical citrus canker recognition based on HMAX features. Computer Science, 2008, 35(4): 231-232 [3] 汤毓婧. 基于人脑视觉感知机理的分类与识别研究 [硕士学位论文], 南京理工大学, 中国, 2009Tang Yu-Qian. Classification and Recognition Research based on Human Visual Perception Mechanism [Master dissertation], Nanjing University of Science, China, 2009 [4] 江达秀. 基于HMAX模型的人脸表情识别研究 [硕士学位论文], 浙江理工大学, 中国, 2010Jiang Da-Xiu. Research on the Facial Expression Recognition based on HMAX model [Master dissertation], Zhejiang Sci-Tech University, China, 2010 [5] Walther D, Koch C. Modeling attention to salient proto-objects. Neural Networks, 2006, 19(9): 1395-1407 [6] 何佳聪,蔡恒进,邓娟,吕恒,刘翘楚. 基于改进的 HMAX 算法的车型识别应用. 计算机科学与应用, 2012, 2(5): 233-239He Jia-Cong, Cai Heng-Jin, Deng Juan, Lv Heng, Liu Qiao-Chu. Improved HMAX model for vehicle type recognition. Computer Science and Application, 2012, 2(5): 233-239 [7] 邱香, 傅小兰, 隋丹妮, 李健, 唐一源. 复合字母刺激心理旋转加工中的整体优先效应. 心理学报, 2009, 41(1): 1-9Qiu Xiang, Fu Xiao-Lan, Sui Dan-Ni, Li Jian, Tang Yi-Yuan. The effect of global precedence on mental rotation of compound stimuli. Acta Psychologica Sinica, 2009, 41(1): 1-9 [8] Navon D. Forest before trees: the precedence of global features in visual perception. Cognitive psychology, 1977, 9(3): 353-383 [9] 胡湘萍. 基于多核学习的多特征融合图像分类研究. 计算机工程与应用, 2016, 52(5): 194-198Hu Xiang-Ping. Multiple feature fusion via multiple kernel learning for image classification. Computer Engineering and Applications, 2016, 52(5): 194-198 [10] Borji A, Sihite D N, Itti L. Probabilistic learning of task-specific visual attention. In: Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI: IEEE, 2012. 470-477 [11] Itti L, Koch C. Feature combination strategies for saliency-based visual attention systems. Journal of Electronic Imaging, 2001, 10(1): 161-169 [12] Chikkerur S, Serre T, Tan C, Poggio T. What and where: a Bayesian inference theory of attention. Vision Research, 2010, 50(22): 2233-2247 [13] Navalpakkam V, Itti L. An integrated model of top-down and bottom-up attention for optimizing detection speed. In: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). New York, NY: IEEE, 2006. 2049-2056 [14] Marat S, Itti L. Influence of the amount of context learned for improving object classification when simultaneously learning object and contextual cues. Visual Cognition, 2012, 20(4-5): 580-602 [15] Ungerleider L G. Two cortical visual systems. Analysis of Visual Behavior. Cambridge: MIT Press, 1982. 549-586 [16] Riesenhuber M, Poggio T. Hierarchical models of object recognition in cortex. Nature Neuroscience, 1999, 2(11): 1019-1025 [17] Zhou H, Friedman H S, Von Der Heydt R. Coding of border ownership in monkey visual cortex. The Journal of Neuroscience, 2000, 20(17): 6594-6611 [18] DiCarlo J J, Maunsell J H R. Form representation in monkey inferotemporal cortex is virtually unaltered by free viewing. Nature Neuroscience, 2000, 3(8): 814-821 [19] Zien A, Ong C S. Multiclass multiple kernel learning. In: Proceedings of the 24th International Conference on Machine Learning. Corvallis, OR: ACM, 2007. 1191-1198 [20] Vedaldi A, Fulkerson B. Vlfeat: an open and portable library of computer vision algorithms. In: Proceedings of the 18th ACM International Conference on Multimedia. Firenze: ACM, 2010. 1469-1472 [21] Sohn K, Jung D Y, Lee H, Hero A O. Efficient learning of sparse, distributed, convolutional feature representations for object recognition. In: Proceedings of the 2011 IEEE International Conference on Computer Vision (ICCV). Barcelona, Spain: IEEE, 2011. 2643-2650 [22] Balasubramanian K, Yu K, Lebanon G. Smooth sparse coding via marginal regression for learning sparse representations. In: Proceedings of the 30th International Conference on Machine Learning. Atlanta, Georgia, USA: IMLS, 2012. 289-297 [23] Wang J J, Yang J C, Yu K, Lv F J, Huang T, Gong Y H. Locality-constrained linear coding for image classification. In: Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). San Francisco, CA: IEEE, 2010. 3360-3367 [24] Qiao M, Li J. Distance-based mixture modeling for classification via hypothetical local mapping. Statistical Analysis and Data Mining: The ASA Data Science Journal, 2016, 9(1): 43-57 [25] Su Y, Jurie F. Improving image classification using semantic attributes. International Journal of Computer Vision, 2012, 100(1): 59-77 [26] Wu L, Hoi S C H, Yu N H. Semantics-preserving bag-of-words models and applications. IEEE Transactions on Image Processing, 2010, 19(7): 1908-1920 [27] 杨波, 敬忠良. 梅花形采样离散小波框架图像融合算法. 自动化学报, 2010, 36(1): 12-22Yang Bo, Jing Zhong-Liang. Image fusion algorithm based on the quincunx-sampled discrete wavelet frame. Acta Automatica Sinica, 2010, 36(1): 12-22 [28] 朱仁欢, 魏海锋, 卢一相, 孙冬. 不均匀光照车牌增强算法研究. 小型微型计算机系统, 2015, 36(3): 601-604Zhu Ren-Hua, Wei Hai-Feng, Lu Yi-Xiang, Sun Dong. Study on enhancement algorithm of license plate under non-uniform illumination. Journal of Chinese Computer Systems, 2015, 36(3): 601-604 [29] 张小利, 李雄飞, 李军. 融合图像质量评价指标的相关性分析及性能评估. 自动化学报, 2014, 40(2): 306-315Zhang Xiao-Li, Li Xiong-Fei, Li Jun. Validation and correlation analysis of metrics for evaluating performance of image fusion. Acta Automatica Sinica, 2014, 40(2): 306-315 [30] 徐萌萌. 基于小波变换的图像融合算法研究 [硕士论文], 哈尔滨理工大学, 中国, 2014Xu Meng-Meng. Image Fusion Algorithm based on Wavelet Transform [Master dissertation], Harbin University of Science and Technology, China, 2014 [31] 郭雄飞. 图像融合技术研究与应用 [硕士学位论文], 中北大学, 中国, 2014Guo Xiong-Fei. Image Fusion Algorithms Research and Application [Master dissertation], North University of China, China, 2014 期刊类型引用(9)
1. 赵宇红，张晓炜. 基于模体演化的多因子动态链路预测方法. 计算机应用与软件. 2022(03): 234-240 . 
百度学术2. 吴翼腾，于洪涛，顾泽宇. 基于统一描述网络结构模型的链路预测方法. 计算机工程. 2022(07): 51-58 . 百度学术3. 吴铮，陈鸿昶，张建朋. 基于时序模体注意力图卷积的动态网络链路预测算法. 计算机应用研究. 2021(10): 3143-3147 . 百度学术4. 顾传青，唐鹏飞，陈之兵. 计算张量指数函数的广义逆张量ε-算法. 自动化学报. 2020(04): 744-751 . 本站查看5. 顾秋阳，琚春华，吴功兴. 基于子图演化与改进蚁群优化算法的社交网络链路预测方法. 通信学报. 2020(12): 21-35 . 百度学术6. 杜凡，刘群. 有向动态网络中基于模体演化的链路预测方法. 计算机应用研究. 2019(05): 1441-1445+1453 . 百度学术7. 刘书新，刘群，杜凡. 基于模体演化与社区一致性的时序链路预测方法. 计算机应用研究. 2019(12): 3674-3678+3684 . 百度学术8. 蔡海尼，牛冰慧，文俊浩，王喜宾. 基于时序模型和矩阵分解的推荐算法. 计算机应用研究. 2018(06): 1624-1627+1659 . 百度学术9. 潘永昊，于洪涛，刘树新. 基于神经网络的链路预测算法. 网络与信息安全学报. 2018(07): 30-38 . 百度学术其他类型引用(11)
-
下载:
计量
- 文章访问数: 2039
- HTML全文浏览量: 314
- PDF下载量: 895
- 被引次数: 20
