基于概要图的数字地形生成方法

针对地形生成算法在易用性、可控性、真实感、速度等方面难以平衡的问题,提出了一种基于概要图的地形生成方法.该方法使用生成对抗网络,在隐空间中对地形坡度、坡向等信息建模,使生成的地形符合用户手绘概要图约束.提出基于地形高度图的概要图提取算法,可从真实地形高度图中提取出类似用户手绘效果的概要图,快速构建数据集.提出多尺度地形细节填充算法,通过引入多尺度的概念,使地形纹理细节得到了动态补充,真实感美观度大幅提升.提出了基于用户反馈的地形满意度评价方法,并据此进行实验验证,结果表明该地形生成方法可以准确高效地生成符合用户预期的数字地形.

基于解耦概要图的大规模图数据高效分布式挖掘算法

频繁封闭子图挖掘被证明是NP-难问题.多年来,虽然已有许多算法被提出用于解决该问题,但在挖掘大规模图数据时,却面临着共同的计算效率问题.特别是,当图中节点的平均度数增加时,挖掘效率更是急剧下降.现在已有的面向图数据库的分布式频繁子图挖掘算法大多采用基于水平划分的分布式计算框架,且都聚焦在挖掘所有频繁子图的问题上.基于水平划分的分布式计算框架是对原始数据进行水平分片,完成分布式挖掘过程.在计算效率方面,该框架存在一些不足.同时,由于封闭子图模式需要对频繁子图进行封闭性检测,如果直接将现有的分布式频繁子图挖掘算法用于闭图模式挖掘可能导致各节点间频繁的通讯,或大量的子图同构检测.针对以上问题,本文提出一种面向大规模图数据的高效分布式挖掘算法Desu-FSM.与现有基于水平分解的分布式挖掘框架不同,该算法首次采用了基于垂直分解的分布式挖掘框架.其基本思想可概括为“快速抵近,双向搜索”.首先,通过τ-邻域核图合并,获得概要图集,跨越式地快速抵近较大尺寸子图的聚集区域.在此基础上,通过对概要图的缩减和扩展发现所有被概要图包含和包含概要图的闭图模式.相较于原始图数据,概要图的尺寸和平均节点度数更小.而且,基于概要图的双向搜索可在分布式环境下同时独立完成,不存在耦合.与基于水平划分的框架采用的“数据物理分治”方式不同,该框架采用“任务逻辑分治”.前者减少了各节点处理的图数据量,后者将原始图数据中的挖掘任务分解为一系列具有更小尺寸和平均节点度数的子图限定的子任务.因此,计算效率大幅提升.本文还提出一组高效的优化策略来减少概要图之间存在公共子图导致的大量重复计算.大量真实和人工数据集上的测试结果表明,在大规模图数据封闭子图挖掘中,基于垂直分解框架的挖掘效率相较于水平分解框架的效率可提升一个数量级.同时,具有更少的内存空间占用.

基于解耦概要图的图数据频繁模式挖掘算法

为了提高图数据频繁模式的分析效果,提出基于解耦概要图的图数据频繁模式挖掘算法.构建闭频繁项特征分析模型,采用解耦概要图模式分析方法进行图数据频繁模式特征检测,根据图数据频繁模式数据的混合分类属性进行相似度分析,提取图数据频繁模式数据的数值属性特征和分类特征,结合自相关特征检测方法进行图数据频繁模式挖掘的统计分析,建立图数据频繁模式挖掘的模糊相关性融合模型,采用解耦概要图检测方法进行图数据频繁模式挖掘过程中的特征提取,建立图数据频繁模式挖掘的特征提取和分类模型,采用大数据融合方法进行图数据频繁模式挖掘的模式匹配和信息融合聚类,根据信息融合结果实现对图数据频繁模式挖掘优化.仿真结果表明,采用该方法进行图数据频繁模式挖掘的自适应性较好,数据挖掘的精度较高,提高了图数据频繁模式检测和特征分析能力.

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

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

基于最小描述长度原则的属性图概要方法

图概要技术是管理、分析和可视化大规模图的关键技术之一。如何综合结构和属性信息进行图概要是一个挑战。大部分现有的图概要方法或者只考虑结构或属性某一方面的信息,或者要求属性的表现形式是一致的。结合信息论中最小描述长度原则,对属性图概要问题建模,将其转化为求解最小表示代价问题,以实现图压缩和图概要的双重目标。提出了一种计算节点属性相似性的方法,该属性度量方法对节点属性的限制较小,并且将节点间的相似性统一为存储代价,实现了节点结构相似和属性相似的协同考虑。提出了两种求解最小代价表示的图概要算法。在真实和合成的数据集上实验,验证了提出算法的有效性。

基于本体分割的语义图概要方法

语义图概要的目的是提取语义图的关键信息,形成原数据集的概要模型以解决大规模语义图的理解、查询、应用难题。为提升现有语义图概要方法效率,提出一种基于本体分割的概要方法。通过本体分割算法对语义图进行分割生成扩展子图。采用形式概念分析对每个扩展子图生成元素的偏序格(又称特征集格)。在此基础上,由所有子图的特征集格形成了原语义图的概要。在关联开放数据集和Berlin SPARQL Benchmark数据集上的实验结果表明,该方法具有较好的可扩展性,有效提高了概要方法的效率。

图概要技术研究进展

图的概要化,简称图概要,旨在寻找一组简洁的超图或稀疏图,阐明原始图的主要结构信息或变化趋势.当前图概要的研究大多结合原始图的应用领域和背景,使用不同的概要技术构建一个特定的概要图,解决目前大图面临的信息过载、查询优化、空间压缩、影响分析、社交网络可视化等问题.对现有的图概要技术进行了汇总,以概要主要目的作为分类标准划分为基于空间压缩的图概要、基于查询优化的图概要、基于模式可视化的图概要和基于影响分析的图概要四大类,针对部分属性图和无属性图概要算法在真实数据集上进行了相关实验,并从压缩率、信息保持率、信息熵和时间进行对比分析.点明图概要的发展趋势,并指出图概要面临的挑战和可深入探索的研究方向,结合热门的深度学习技术提出了部分有价值的的宏观想法用以解决当前挑战.

基于编辑行为码的图概要技术

图数据的处理面临庞大规模和复杂结构的制约.图的概要化,旨在寻找一组简洁的超图或稀疏图,阐明原始图的主要结构信息或变化趋势.针对属性图提出了基于编辑行为码的概要模型,遵循最小描述长度原理(Minimum Description Length,MDL),将结构的相似性和属性的相似性统一为存储代价,构建编辑行为码.在此模型基础上提出了Greedy算法和Random算法,存储属性和结构的编辑信息,生成高质量的超图,并支持原始图的重构.实验结果表明本文提出的概要模型和算法相比于其他图概要算法,在压缩率和时间代价等指标上具有一定的优越性.

图稀疏算法研究进展

作为加速大规模图分析的技术,图稀疏算法在尽可能保留原始图性质的基础上实现图的稀疏化存储,从而加速大规模图的分析和处理。图稀疏算法是一种顶点全保存边稀疏的采样方法,可概括为四种边度量下的图稀疏采样方法:基于距离相似性的生成图稀疏算法、基于边连通的割稀疏和谱稀疏算法、基于社会网络的聚类稀疏和影响力传播的稀疏算法。本文归纳了这些算法的优缺点和适应性,最后展望了大规模图稀疏化尚未探索的有意义的研究课题。

一种基于互信息度量的时序数据因果发现方法

在时序数据因果关系发现研究中,传统算法针对时间窗口内时序数据之间的因果关系进行分析,存在因果关系识别准确率受限、算法复杂度较高等问题.为解决该问题,首先对概要因果图、因果概要互信息和条件因果概要互信息进行定义,在此基础上推导出基于因果互信息的时序变量定向规则,而后区分是否存在混杂因子,结合PC (Peter and Clark)和FCI (fast causal inference)算法分别提出改进的PCSMI (Peter and Clark summary mutual information)和FCISMI (fast causal inference summary mutual information)算法.实验结果表明改进后算法能够在低复杂度条件下有效提升时序数据因果发现的准确率.

台湾海峡两岸横向构造的对比研究

台湾海峡及其两岸的山势走向都是北东或北北东向,但根据对该地区地貌、地表构造、深部地震结果和重力场等分析,都发现有彼此相应的横向构造,而且从台湾西部山麓平原地震带8次6级以上地震等震线均有方形或长方形的特征,也可以推论台湾岛具有明确的南北分段性.1999年集集地震的地表运动由GPS测定的结果亦为佐证台湾岛内横向构造可以与福建沿海更为直观的北西和东西向横构造对比.两岸横向构造的论定有助于对台湾海峡地质构造的认识,文中给出的台湾海峡及两岸的构造概要图,编入了可供进一步研究的北西和近东西向两组横向构造中.

北京奥运会测试赛综合项目管理创新与实践

本文以北京奥运会体育测试赛为案例，根据赛事特点和计划管理的需求，综合运用项目管理的有关方法、技术和工具，在实践中进行创新，探索与开发适合于奥运会大型复杂项目的管理方法与技术工具，以此提高赛事筹办的管理效率和水平。