基于图神经网络的小样本学习方法研究进展

小样本学习(few-shot learning,FSL)旨在利用少量样本学习得到解决问题的模型,为解决应用场景中样本量少或标注样本少的问题.图神经网络(graph neural network,GNN)由于其在许多应用中的卓越性能引起了极大的关注,许多学者开始尝试利用图神经网络进行小样本学习,基于图神经网络的方法在小样本领域取得了卓越的成绩.目前与基于图神经网络的小样本学习方法相关的综述性研究较少,缺乏该类方法的划分体系与介绍性工作,因此系统地梳理了当前基于图神经网络的小样本学习的相关工作:概括了小样本学习的图神经网络方法的概念,根据模型的基本思想将其划分为基于节点特征、基于边特征、基于节点对特征和基于类级特征的4类方法,介绍了这4类方法的研究进展;总结了目前常用的小样本数据集和代表性模型在这些数据集上的实验结果,归纳各类方法主要的研究内容和优劣势;最后概述了基于图神经网络的小样本学习方法的应用和面临的挑战,并展望其未发展方向.

带约束的一维装箱问题近似算法的研究

作为经典装箱问题的扩展,有色装箱问题在多处理器实时调度的过程中有很强的应用背景。论文提出了有色装箱问题的新算法-SCPF算法,按颜色分类,将相同颜色的物品分成一类。放置时按照相同颜色的物品首先放置的原则,将物品进行装箱。实验证明,该算法与文献犤3犦中的KC-A算法相比具有更好的装箱效果,使用的箱子数更少。并从理论上论证了该算法的性能比KC-A算法更好。

基于新型的竞争型神经网络的Web日志挖掘

提出了一种基于竞争的自激励神经网络学习算法SIN ,该算法综合了自适应谐振理论和竞争型神经网络的特点 ,并在隐含层采用了Hebb学习规则 ,既能保证原有记忆不受影响 ,又能对新的信息加以记忆 ,同时又克服了ART网络对噪音敏感的缺点 ,学习速度快 ,分类性能好 ,具有在线学习的功能 将该算法应用于Web日志挖掘能够有效地剔除噪音 ,得到很好的用户聚类和页面聚类的结果 。

大型数据库中基于邻域连接的层次聚类算法

提出了一种基于邻域连接的层次聚类算法HANL,该算法首先采用分割的方法将数据集划分为若干个子簇,通过对子簇间的连接的分析,建立子簇间的连接构成图,图中带权的边代表了子簇间的连接紧密度。合并连接紧密度高的结点,得到最后的聚类结果。该算法适用于高维数据集,能够对任意形状的簇进行聚类,无论对于数值属性的数据库还是分类属性的数据库都是一个有效的聚类方法。同时这种方法聚类速度快,效率高,具有良好的伸缩性。

一种快速高效的神经网络分类器

提出了一种新型型的基于竞争型神经网络的学习算法,该算法综合了竞争型神经网络和层次聚类的特点,通过竞争型神经网络对对象进行初步分类,并在隐含层采Hebb学习规则对子类进行关联学习,学习速度快,分类质量好,可以对任意形状、任意大小的簇进行聚类,同时不受噪音的影响,是一种快速高效的分类算法。

差分隐私保护参数ε的选取研究

2006年,差分隐私保护作为一种新的隐私保护范式出现,因其不需要攻击者先验知识的假设,而被认为是一种非常可靠的保护机制。然而,作为隐私保护技术的主要参数ε的意义对于一般用户而言不十分明确。鉴于此,提出一个新的攻击模型,可以用来选取参数ε的值。详细分析了该攻击模型的特点,通过理论证明和模型的实证分析,最后给出了一个参数ε的选取计算式。

基于事件的位置不确定移动对象连续概率Skyline查询

Skyline查询是基于位置服务(Location based service,LBS)的一项重要操作,其目的是发现数据集中不被其他点支配的点的集合.移动对象在运动过程中,其位置信息具有不确定性,导致各数据点间的支配关系不稳定,从而影响Skyline操作.本文针对以位置不确定移动对象为查询点的Skyline查询进行研究,首先,定义了查询点移动时各对象间支配概率,提出了支配概率和Skyline概率的微元计算方法.在此基础上,提出一种面向不确定移动对象进行连续概率Skyline查询的有效算法UCPSC.该算法首先快速计算初始时刻的p-Skyline集合;然后,定义了两类可能引起p-Skyline变动的事件,通过对这些事件的跟踪计算快速更新p-Skyline集合,无需在移动对象的每一运动时刻去遍历整个数据集,实现了对p-Skyline的连续更新操作,大大减少了算法的查找和计算开销,提高了运算效率;最后,提出一种静态算法USPSC,与UCPSC进行了对比试验,实验结果证明了算法的有效性.

动态网络表示学习研究进展

网络表示学习旨在将网络信息表示为低维稠密的实数向量,解决链接预测、异常检测、推荐系统等任务.近年来,网络表示学习研究取得重大进展,但研究多基于静态网络,而真实世界构成的网络是动态变化的,对动态网络分析的需求日益增加.本文总结了当前动态网络表示学习的方法与研究进展,首先提出网络表示学习的动机,阐述动态网络以及表示学习的发展历史与理论基础;接着,系统概述了大量动态网络嵌入方法,包括基于矩阵分解的动态图嵌入、基于随机游走的动态图嵌入、基于深度学习的动态图嵌入和基于重构概率的动态图嵌入,并分析与比较,给出动态网络表示学习的应用场景;最后,总结未来网络表示学习的研究方向.只有考虑网络的动态性,才能真实反映现实网络的演化,使网络表示学习更具价值.

基于道路网络不确定移动对象的连续概率Skyline查询

Skyline查询是基于位置服务LBS的一项重要操作,其目的是发现数据集中不被其它点支配的点的集合。对道路网络环境下移动对象的连续概率Skyline查询进行了研究。在对道路网络和移动对象建模的基础上,定义了基于道路网络的数据间支配概率和Skyline概率的表示方式,提出了两类可能引起p-Skyline集合变动的event事件,并提出4条剪枝方案进行优化。在此基础上,设计了对网络受限的不确定移动对象进行连续概率Skyline查询的动态增量算法U-CPSQRN。该算法通过对event的跟踪计算实现了对p-Skyline的连续更新操作,减少了算法的查找和计算开销。实验结果显示了算法的有效性。

基于K-sup稠密子图的大规模复杂网络概要算法及可视化

现实社会存在大量复杂网络,随着大数据时代的来临,复杂网络数据规模不断扩大,难以进行算法分析和可视化展示.针对复杂网络小世界、无标度特性,提出基于K-sup稠密子图的复杂网络概要算法,利用三角形在网络中的同质性和传递性发现复杂网络中的稠密子图,结合模块度最大化,将子图中相似的节点归并为超点;运用分层结构存储概要图,并进行可视化显示.该算法能对大规模复杂网络进行有效压缩,保持原网络的性质.在5个真实数据集上进行对比实验,显示出该算法在压缩率、幂率性和平均聚类系数的保持等指标优于已有算法,同时在大规模数据下具有保持网络拓扑结构且支持概要图分层可视化的优点.

内嵌式溢油回收机电液阀控马达速度变结构控制

针对内嵌式溢油回收机扫油臂端部线速度控制参数不确定性问题,基于变结构控制理论,提出采用饱和函数准滑模变结构控制方法(CSS)来消除参数不确定性对控制系统性能的影响,并采用饱和函数平滑不连续控制法有效减弱系统中抖动现象。仿真结果表明,采用滑模变结构控制的扫油臂电液阀控马达系统输出速度与位置具有良好的鲁棒性与跟踪性。

基于混合遗传聚类的Web日志挖掘

通过对Web日志文件进行分析,提出了一种用混合遗传聚类对Web用户的行为进行分析的方法.混合遗传聚类是标准遗传算法和K-中心点算法的有机结合.实验证明,该方法是一个具有全局最优解的聚类方法,其结果明显优于标准遗传聚类方法.该算法能够有效地剔除噪音,得到很好的用户聚类和页面聚类的结果,为网站的管理者设计个性化的商务网站提供了有效的决策依据.

面向复杂网络的图稀疏算法综述

大规模数据下复杂网络的算法分析面临复杂度高的挑战,为此引入图稀疏的思想,在保持原始图性质的情况下以一定的精度在稀疏图上实现了高效的算法分析。图稀疏算法是一种保留顶点、对边稀疏采样的方法。按照相应算法分析所需要的原始图性质,提出图稀疏的边度量方式。文中系统回顾了4种边度量下的图稀疏采样方法:生成图稀疏、边连通图稀疏、聚类图稀疏、边传播性图稀疏,归纳了不同边度量方式下图稀疏的优缺点和适应性,并进一步讨论了动态图流稀疏化的最新研究进展。最后,总结了图稀疏领域有待解决的问题并展望了未来的研究方向。

集成时空轨迹的动态属性网络表征学习

网络表征学习是当前信息网络数据表示的研究热点,相比于传统网络分析技术已显示出它的有效性和高效性.目前绝大多数研究仅将网络视为静态来处理,即网络结构不随时间演化而变化,而且很少考虑网络中丰富的节点属性信息,难以适应现实信息网络时刻变化的动态特性.同时考虑网络的动态性和节点属性,提出基于时空路径的动态属性网络表征学习(DAWalk),将结构特征与属性特征聚合为节点的嵌入表示.游走时空轨迹序列以捕获网络的结构特征以及动态演化趋势规律.在模型学习方面使用改进的自编码器模型,最小化序列中成对节点的距离损失,学习出序列节点对隐藏的高度非线性规律,使得学到的节点表示更具健壮性.实验表明,在可视化、链接预测、节点分类任务上,提出的DAWalk在3个数据集上的性能均优于其他基准算法.

FSMBUS:一种基于Spark的大规模频繁子图挖掘算法

随着社交网络用户数的快速增加,大规模单图上频繁子图挖掘的需求越来越强烈.单机算法对大规模图的运行效率较低,难以支撑支持度较低的频繁子图的挖掘;现有的分布式环境下单图的频繁子图挖掘算法不支持子图增长模式的挖掘,它们所使用的Hadoop框架也不适合运行迭代式算法.提出了一种基于Spark的大规模单图频繁子图挖掘算法FSMBUS,通过次优树构建并行计算的候选子图,在给定最小支持度时挖掘出所有的频繁子图,并利用非频繁检测和搜索顺序选择实现优化,还设计了一种名为Sorted-Greedy的轻量级数据划分方法.实验结果表明,FSMBUS的效率要比现有单图上最新的算法快一个数量级,并支持更低最小支持度阈值以及更大规模图数据的挖掘,同时FSMBUS比其Hadoop的移植版要快2~4倍.

基于结构紧密性的重叠社区发现算法

随着网络结构的不断扩大和日益复杂,传统的重叠社区发现算法已经不能有效地处理大规模网络数据,发现合理的社区结构.本文提出了顶点引力的概念,引入顶点凝聚度和社区凝聚度作为满足社区的外部结构稀疏性和社区内部结构紧密性的判定指标,构造了基于结构紧密性的重叠社区发现算法OCSC.该算法经过预处理,核心子图划分以及核心社区的扩展三个步骤,能有效地发现重叠社区,通过对人工合成网络和真实网络结构的社区发现实验,运用NMI和F1Score等指标验证OCSC算法的合理性和优越性.

面向时空数据的区块链研究综述

时空数据包括时间和空间2个维度,常被应用于物流、供应链等领域。传统的集中式存储方式虽然具有一定的便捷性,但不能充分满足时空数据存储及查询等要求,而区块链技术采用去中心化的分布式存储机制,并通过共识协议来保证数据的安全性。研究现有区块链1.0、2.0和以Block-DAG为代表的3.0体系架构及性能特点,分析三代区块链架构应用于时空数据时的性能支持度、优化方式以及局限性,并对区块链技术在时空数据领域的应用前景、存在的问题和未来的研究方向进行展望。

大规模图数据划分算法综述

对大规模图数据划分算法进行了总结,介绍了并行环境下图计算模型,详述了大规模静态图划分算法和动态图划分算法,归纳了这些算法的优缺点以及适应性。最后,指出了关于大图划分尚未探索的有意义的研究课题。

基于Attention深度随机森林的社区演化事件预测

在网络结构不断变化的同时,社区结构也随之演化.社区结构在不同时间片的变化可定义为四种不同的演化事件:持续、分离、融合和消失.本文运用网络表示学习的方法,对网络进行图嵌入编码映射到低维向量空间中,研究动态社区演化事件的预测.特征方面,在传统的社区内部属性特征、时间片间属性特性变化和前段时间片的社区演化事件的特征维度的基础上,引入潜在结构特征表征四种演化事件,运用随机游走和Softmax思想获取潜在的结构特征;模型方面,引入深度随机森林的策略,同时采用attention机制、蒙特卡洛特征采样策略进行特征融合和特征训练,克服了已有算法仅获取局部结构特征的缺陷.实验在DBLP、FACEBOOK和Bitcoin数据集上,对比SVM、XGBOOST和RIDGE模型训练,证实了新提出的算法模型对最终预测准确率有很大的提升.

MapReduce框架下的不确定数据Top-k查询计算

Top-k查询是不确定性数据管理中普遍采用的一种技术.基于参数化排名函数的Top-k查询语义是近年来提出的各种查询语义的统一.文中针对海量不确定数据,提出一种基于MapReduce框架的Top-k计算的有效方法.通过分析基于参数化排名函数的不确定数据Top-k查询语义,设计一种获得未计算元组的排名函数值上界的算法,避免计算所有元组的排名函数值,解决Top-k计算中的剪枝问题.在MapReduce计算模型中提出两种不同的策略来实现该算法.文中针对单机环境和Hadoop分布式计算平台进行两组不同的对比实验.实验表明在处理海量不确定数据时,该算法在计算时间上有较高的性能提升.