树图可视化

树图是一种流行的利用包含关系表达层次化数据的可视化方法.由于其呈现数据时高效的空间利用率和良好的交互性,受到众多的关注,得到深入的研究,并在科学、社会学、工程、商业等领域都得到了广泛的应用.文中从树图的布局算法、交互方法、改进和变种、应用领域和用户评价研究等角度,对树图可视化及其扩展方法的基础和研究前沿进行了综述,并对树图可视化方法的前景进行了展望.     

基于蒙特卡罗树搜索的树图布局

树图是层次数据可视化的常用方法,已有的研究发现,满足逐步加点原则的3种树图布局算法(正方化布局算法、条状布局算法和螺旋线布局算法)在常见的4种优化指标(平均长宽比、稳定性、数据一致性和可读性)上各有优缺点.其中,条状布局算法和螺旋线布局算法的长宽比较大,正方化布局的长宽比仍有优化空间.基于蒙特卡罗树搜索,在树图布局的同时构建对应的搜索树并利用置信度上界公式作为搜索路径的选定标准,在用户可接受时间内对3种布局算法的算术平均长宽比和所提加权平均长宽比分别进行了优化.为了证明算法的有效性,在构造出的3种不同分布、7种不同规模的单层数据集以及真实的多层数据集上测试,并与原算法进行比较分析,最后利用对应结论指导用户选择更好的布局算法以及设置更恰当的参数.     

一种层次结构中多维属性的可视化方法

在很多领域的统计分析中,通常需要分析既具有层次结构又具有多维属性的复杂数据,如食品安全数据、股票数据、网络安全数据等.针对现有多维数据和层次结构的可视化方法不能满足对同时具有层次和多维两种属性数据的可视分析要求,提出了一种树图中的多维坐标MCT(multi-coordinate in treemap)技术.该技术采用基于Squarified和Strip布局算法的树图表示层次结构,用树图中节点矩形的边作为属性轴,通过属性映射、属性点连接、曲线拟合实现层次结构中多维属性的可视化.将该技术应用于全国农药残留侦测数据,实现了对全国各地区、各超市、各农产品中农药残留检出和超标情况的可视化,为领域人员提供了有效的分析工具.MCT技术也可用于其他领域的层次多属性数据的可视化.     

高维时空房地产数据的可视分析

高维房地产数据中包含着复杂的空间和时间趋势,为了使用户能够创建自己的可视化形式并理解房地产市场中的内容,提出基于HTML5的在线房地产信息的、包含4个组件的可视分析方法.该方法提出了基于楼盘地理位置聚类的可视化方法来展示楼盘地理信息的地学可视化组件,结合多种布局和排序方式来展示楼盘销售数量变化的堆栈图组件,基于楼盘销量和价格的聚类方法来展示楼盘多维属性的像素条图组件,并结合多种节点布局和排序的方式展示数据层次结构的树图组件;最后对各组件设计了良好的交互操作,丰富了系统的分析能力.文中方法已用于杭州市房地产的真实数据分析中,用户和专家反馈效果良好.     

大规模天文时序粒子数据的可视化

时序数据的可视化是理解宇宙结构形成与演化的重要手段.围绕大规模天文数值模拟输出的近百TB粒子时序数据的可视化,针对数据的高动态范围色调映射问题,提出一种基于统计直方图的算法,实现了时序上色调连贯的可视化;同时,在插值重建演化过程时,考虑到模拟输出的每个关键帧的数据依据Hilbert三维填充曲线分布于2048个文件中,在一次可视化中通常有相当部分的文件包含的数据不会进入视锥内,据此提出一种文件尺度上根据前后关键幀预判插值幀可见性的剪裁算法,将前后关键帧可见数据文件的序号集合作为插值幁可见数据文件的序号集合;对裁剪结果进行实时插值和投影,通过裁剪算法大幅降低计算量、存储和I/O,并通过Hilbert哈希元胞快速完成裁剪过程;最后给出了算法的性能和效果分析.可视化结果表明文中算法可以直观、有效地表达大规模数据所包含的宇宙结构形成细节与演化信息.     

WSN中一种基于拓扑优化的数据收集方案

针对现有数据收集方法的不足,提出一种优化的网络拓扑构造算法来实现数据收集。该算法首先从给定的网络全连通图中找到符合条件的k个顶点的子图,使得k个顶点间的距离平方和最小化,然后采用Hungarian算法来实现边的约简,直到得到一颗生成树。另外,为了降低控制开销,还提出一种分布式的网络拓扑构造算法,提高算法的适应性。理论分析和仿真实验结果表明,该方法是有效的,在数据收集延迟以及网络生命周期等方面要优于传统的方法。     

基于多层图布局算法的不确定性网络可视化方法

由于越来越多的数据包含了不确定性,可视化不确定性网络最近几年成为了数据可视化领域中的一个热点。在现有的不确定性可视化研究中,基于概率图布局的方法取得了比较好的效果,通过一种固定采样图算法,可以很好地可视化不确定性网络,并反映出网络中的概率分布情况。针对基于概率图布局的方法存在运行时间过长、图布局不稳定等问题,提出了一种基于多层图布局的方法,改进了多层图布局算法并与固定采样图算法相结合,弥补基于概率图布局的不确定性网络可视化方法的缺陷。实验证明改进之后的算法与原来的方法相比具有更高的时间效率,而且生成的图结构更加稳定。     

基于关联规则的Apriori-Partition算法的可视化研究

关联规则的提取是数据挖掘中的重要研究内容,对关联规则提取中的Apriori算法进行了分析与研究,针对该算法的运算效率不高,对该算法进行了优化.Partition算法以经典的Apriori算法为基础,通过将数据库分成几个互不相交的块来实现算法效率的提高.同时,还介绍了一种基于Apriori-Partition算法的可视化挖掘模型,并讨论了该可视化模型的实现方法.     

TVBPS：一种基于Parallel Sets的具有度量属性的多变元时态数据可视化方法

针对现有“具有度量属性的多变元时态数据”可视化方法不足,提出Parallel Sets分类值排列顺序优化算法ACLEARCR、基于相关度的Parallel Sets变元轴配置算法（VABC）、深度信息Parallel Sets（DCPS）共同组成基于Parallel Sets的具有度量属性的多变元时态数据可视化方法TVBPS。使用具体数据集对提出的可视化方法进行实验,获得的视图能够挖掘数据集中的隐含知识,证明了该方法的有效性。TVBPS可视化方法为分析多变元时态数据集提供了有效手段,具有较高的适用性和易用性。     

空间晶体生长实验中流场的动态显示研究

矢量场可视化是科学计算可视化研究的重要方向.对于复杂环境条件下大数据量矢量场的可视化,传统的方法运算量大,实时性难以满足要求.以空间晶体生长实验中的流场数据可视化为应用背景,针对目前常用方法的不足,引入了一种全新的基于图像的流场可视化方法--IBFV方法,并对该方法的机理进行了深入地分析和研究,给出了一种基于OpenGL图形库的简单实现算法,最终应用于布里奇曼晶体生长实验中流场数据的实时动态显示.实践证明此方法独立于流场数据,具有良好的适用性和直观性,并具有极高的速度,在当前普通PC机上可以实现50fps的动态显示帧频,得到连续无抖动的流场动态图像仿真.     

基于LCS的逻辑重构算法的研究

在逆向工程的研究中,逻辑重构中的等级簇聚合算法计算效率较低。为了改进计算效率,基于最长公共子序列(LCS)与高内聚的思想提出改进的逻辑重构算法。利用组件和数据表的关系以及存在交集的组件之间的相似程度来生成模块,并循环迭代,从而可以得到清晰的组件关系。与现有的等级簇聚合算法相比,该算法无需反复计算距离,时间复杂度更低,计算效率更高。     

一种基于道路网络层次拓扑结构的分层路径规划算法

鉴于平面最短路径算法应用于大规模网络规划中的效率不高,而分层算法引入"分而治之"策略,则能有效解决此难题。为了利用分层算法进行路径规划,首先研究了分层算法的数据基础——道路网络层次拓扑结构,其涉及基于道路等级的路网分层抽象、道路数据分区组织、以区域为单位的路网层次拓扑关系模型;接着提出了一种适用于LBS(基于位置的服务)的分层路径规划算法。该算法先通过距离值判断是否切换到上一层;然后利用启发式A*算法搜索入口和出口;最后使用双向策略搜索层内两点之间的最短路径。利用现实道路网络进行的实验分析结果表明,该算法能从本质上提高大规模网络中路径规划的效率。     

基于知识点层次图的个性化习题推荐算法

针对海量习题带来的信息过载导致学习针对性不强、效率不高等问题,提出了基于知识点层次图的个性化习题推荐算法（a personalized exercises Recommendation algorithm based on Knowledge Hierarchical Graph,ReKHG）。借鉴课程知识点体系结构的特点,构建了表征知识点层次关系的权重图,该权重图有效反映知识点间的层次关系。根据学生对知识点的掌握情况,在知识点层次图的基础上提出了一种个性化习题推荐算法。该算法通过更新学生-知识点失分率矩阵,获取学生掌握薄弱的知识点,以此实现习题推荐。实验结果表明,ReKHG算法能够针对性给学生推荐适合的习题。     

一种基于层次栈的XML数据小枝查询算法研究

当前针对小枝模式的XML查询是XML文档查询的研究热点。文章在分析XML数据小枝查询处理常用算法的基础上,提出了一种高灵活性的、易确定结点对之间结构关系的EDiezt-P编码,并基于EDiezt-P编码和层次栈结构提出了一种自底向上的小枝查询算法。实验表明,该算法在一定程度上减少了查询处理时间,提高了查询效率。     

数据流中结构二叉树挖掘算法研究

针对传统数据流挖掘算法不能挖掘出频繁项之间的关系而且挖掘时间和空间复杂度高、准确度不高的问题,本文提出了一种数据流中结构二叉树挖掘算法（AMST）。该算法利用了二叉树结构的优势,将所处理事务数据库中的数据流转化成结构化二叉树,然后利用数据流矩阵对结构二叉树进行挖掘。整个过程只对事务数据库进行了一次扫描,大大提高了挖掘的效率。此外,算法还找出了具有层次关系的频繁子树。实验结果表明,AMST算法性能稳定,在时间复杂度和空间复杂度方面有很大的优越性,能够快速准确地对数据流进行挖掘。     

随程序规模动态调整的通道优化布线算法

针对常规层次型布图算法在大规模程序中布线混乱的缺点,借鉴Sugiyama层次布局算法,提出了一种随着程序规模动态调整的通道优化布线算法。通过将节点的通道数目与程序规模建立函数关系,以解决现有算法在布图时出现的线路重叠和效率低下的问题;在布图中结合广义张量平衡思想,以减少交叉并实现布图的美观性;并根据调用节点之间的相对位置关系,给出了相应的线路分配和申请策略,实现了布线的有序性。实践证明,该算法能够提高布图效率,有效地减少交叉,实现节点的有序布线和实现简单等优点。     

Binary-Positive下的并行化CURE算法

当CURE算法在处理不均匀的海量数据时,针对随机抽样不具有代表性的问题,提出了一种健壮的并行化改进算法。该算法使用Binary-Positive算法得到原始数据的有效属性,并利用MapReduce并行框架对有效数据进行层次聚类,从而实现了正确率与效率的一种权衡。实验分析表明,改进后的CURE算法具有更高的执行效率,且聚类效果良好。     

自由标签系统中标签的层次关系提取方法

在自由标签系统中,标签之间没有显式的表示出层次关系,但其内在却隐含着某个标签是其他一些标签的子标签这样的层次关系.提出一种简单高效的、基于概率统计的方法,用OWL本体中的类来表示标签,并从中提取出类的层次关系.实验表明,本方法的提取结果在正确率、召回率上完全满足实际需要,算法执行效率高,非常符合信息飞速增长的互联网的需要.     

面向实体模型相似评价的层次图生成与高效匹配

在三维模型的表示、匹配与检索中广泛地使用了图,然而图匹配的效率十分低下,原因在于它无法有效地表示图中不同部分的重要性及其层次关系.基于多分辨的描述思想,提出一种层次图的表征方式,可有效地表征模型的整体信息、细节信息及它们之间的关系;进一步提出层次图的匹配算法,通过层次间的关联信息,缩减匹配空间、优化匹配方案.实验结果表明,该匹配算法非常高效,并能够有效地支持实体模型的相似评价.     

Shortest-linkage-based parallel hierarchical clustering on main-belt moving objects of the solar system

Data clustering is an important data preparation process in many scientific analysis researches. In astronomy, although the distributed environments and modern observation techniques enable users to collect and access huge amounts of data, the corresponding clustering process may become very costly. One of the challenges is that the sequential clustering algorithms, that can be applied to cluster hundreds of thousand main-belt asteroids to reason about the origins of the main-belt asteroids, may not be used in the distributed environment directly. Therefore, this study focuses on the problem of parallelizing the traditional hierarchical agglomerative clustering algorithm using shortest-linkage. We propose a new parallel hierarchical agglomerative clustering algorithm based on the master–worker model. The master process divides the whole computation into several small tasks, and distributes the tasks to the worker processes for parallel processing. Then, the master process merges the results from the worker processes to form a hierarchical data structure. The proposed algorithm uses a pruning threshold to reduce the execution time and the storage requirement during the computation. It also supports fast incremental update that merges new data items into a constructed hierarchical tree in seconds, given a tree of about 550,000 data items. To evaluate the performance of our algorithm, this study has conducted several experiments using the MPCORB dataset and a dataset from the DVO database. The results confirm the efficiency of our proposed methodology. Compared with prior similar studies, the proposed algorithm is more flexible and practical in the problem of distributed hierarchical agglomerative clustering.