（计算机软件与理论专业论文）双向正方化树图生成算法.pdf

硕士学位论文 摘要 随着计算机应用技术的深化和发展，可视化技术逐渐成为当今计算机 应用研究的热点。具有层次结构的数据集合的可视化是可视化研究领域 中的一个重要问题，目前对层次结构数据集合的可视化方法主要包括表、 缩进图和结点连接图，以及新提出的树图。 树图是一种二维空间填充的可视化方法，相比传统的对层次结构数据 集合的可视化方法，其最大特点是充分利用了显示空间的每一个象素， 因此也更加适合显示大规模的层次结构数据集合。树图的生成算法很多， 其中包括改进树图层次结构显示的c u s h i o n 算法，改进树图矩形长宽比的 正方化算法，以及针对正方化算法乱序的缺陷提出的p i v o t 算法和s t r i p 算法。本文对这些算法进行了分析和比较，并在对正方化算法分析的基 础上，提出了双向正方化算法。双向正方化算法采用了双向靠边策略来 优化每一个阶段矩形的摆放，并使用了靠边阈值优化了算法的时间复杂 度，同时对矩形的摆放进行进一步控制。通过模拟实验，我们验证了双 向正方化算法在改进原算法平均长宽比方面的优越性，并证明了双向正 方化算法相比原算法更好的稳定性。 在对树图生成算法理论研究的基础上，我们实现了一个集合几种主要 树图生成算法的树图原型：树图1 0 。树图1 0 通过典型的应用说明了树 图可视化方法的优越性，并为树图算法的研究提供了一个理想的平台。 在树图1 0 平台下，结合用户的反馈意见，我们对双向正方化算法和其他 几种算法进行了进一步的分析和比较。分析数据表明，双向正方化算法 是目前对树图平均长宽比改进最大的算法，但在顺序性和动态稳定性方 面，和正方化算法一样不如其他几种树图生成算法。对于双向正方化算 法动态稳定性较差的缺陷，我们提出了一些可能的解决方案；同时，我 们提出当数据集合需要保留顺序的时候，将双向正方化算法和其他算法 结合使用的思想。 关键词：可视化；树图；双向正方化算法：正方化算法 双向正方化树图生成算法 a b s t r a c t w i t ht h ef u r t h e rp e n e t r a t i o na n dd e v e l o p m e n to fc o m p u t e ra p p l i c a t i o n t e c h n o l o g y ，v i s u a l i z a t i o ng r a d u a l l yb e c a m ear e s e a r c hf o c u si nc o m p u t e r a p p l i c a t i o nr e s e a r c hf i e l d o n eo ft h ei m p o r t a n ts u b j e c t si nv i s u a l i z a t i o ni s t h ev i s u a l i z i n go fh i e r a r c h i c a ld a t as e t ，w h i c hc o m p r i s e dt e c h n i q u e ss u c ha s l i s t ，o u t l i n e ，n o d e - l i n kd i a g r a ma n dn e w l yi n v e n t e dt r e e m a p t r e e m a p ，av i s u a l i z a t i o nt e c h n i q u eb a s e do n2 ds p a c ef i l l i n g ，w i t hi t s s i g n i f i c a n tf e a t u r eo fm o r ee f f e c t i v e l yu l t i l i z i n ge v e r yp i x e l si nt h ed i s p l a y s p a c ec o m p a r e dw i t ho t h e rt r a d i t i o n a lt e c h n i q u e s ，w a sm o r es u i t a b l ef o r v i s u a l i z i n gl a r g eh i e r a r c h i c a ld a t as e t t h e r eh a db e e nm a n ya l g o r i t h m sf o r g e n e r a t i n gt r e e m a p ，i n c l u d i n gc u s h i o na l g o r i t h mf o re n f o r c i n gt h ea b i l i t yt o i l l u s t r a t eh i e r a r c h i c a li n f o r m a t i o n ，s q u a r i f i e da l g o r i t h mf o rr e d u c i n gt h e a s p e c tr a t i o s ，p i v o ta l g o r i t h m a n d s t r i pa l g o r i t h m f o r r e m e d i n gt h e s h o r t c o m i n go fs q u a r i f i e da l g o r i t h mf o rl o s i n gt h eo r d e ri n f o r m a t i o n t h i s p a p e ra n a l y z e da n dc o m p a r e dt h e s ea l g o r i t h m s ，a n dp r e s e n t e db i d i r e c t i o n a l s q u a r i f i e da l g o r i t h mv i at h ea n a l y s i so fs q u a r i f i e da l g o r i t h m b i d i r e c t i o n a l s q u a r i f i e da l g o r i t h mi m p l e m e n t e dab i d i r e c t i o n a ls t r a t e g yt oo p t i m i z et h e l a y o u t o fr e c t a n g l e si n e v e r ys t e p ，a n dd e f i n e d a l a y o u t t h r e s h o l dt o m i n i m i z et h et i m ec o m p l e x i t ya n df u r t h e rc o n t r o lt h el a y o u to fr e c t a n g l e s t h r o u g hs i m u l a t i n ge x p e r i m e n t s ，w et e s t i f i e d t h ea v e r a g ea s p e c tr a t i o s r e d u c t i o na n db e t t e r s t a b i l i t y o fb i d i r e c t i o n a ls q u a r i f i e d a l g o r i t h m c o m p a r e dw i t hs q u a r i f i e da l g o r i t h m g r o u n d e do nt h et h e o r e t i c a ls t u d yo nt r e e m a pa l g o r i t h m s ，w ei n c a r n a t e d at r e e m a pp r o t o t y p e - t r e e m a p1 0 ，w h i c hi n t e g r a t e ds e v e r a lm a i nt r e e m a p a l g o r i t h m s t r e e m a p 1 0d e m o n s t r a t e dt h ee f f e c t i v e n e s so f t r e e m a p t e c h n i q u et h r o u g ht y p i c a la p p l i c a t i o n s ，p u r v e y i n g a ni d e a l p l a t f o r m f o r s t u d y i n gt r e e m a pa l g o r i t h m s u n d e rt r e e m a p1 。0 ，c o m b i n i n gt h ef e e d b a c ko f u s er s ，w e p e r f o r m e df ur t h e ra n a l y s i s a n dc o m p a r esi nb i d i r e c t i o n a la n d o t h e ra l g o r i t h m s t h er e s u l t si n d i c a t e dt h a tb i d i r e c t i o n a la l g o r i t h mc a n e v e n t u a l l ya c h i e v et h el e a s ta s p e c tr a t i o s ，w h i l es u f f e r e dl e s so r d e rp r o p e r t y a n dd y n a m i cs t a b i l i t yc o m p a r i n gt oo t h e ra l g o r i t h m s ，j u s t a s s q u a r i f i e d a l g o r i t h m d i d t o t h e r a p y t h el e s s d y n a m i cs t a b i l i t y o fb i d ir e c t i o n a l s q u a r i f i e da l g or i t h m ，w ep o s e ds e v e r a lp o s s i b l e s o l u t i o ns m e a n w h i l e ，w e 硕士学位论文 a r g u e dt h a tw h e nk e e p i n gt h eo r d e rw a sn e c e s s a r y ，b i d i r e c t i o n a ls q u a r i f i e d a l g o r i t h mc o u l db eu s e dc o m b i n e dw i t ho t h e ra l g o r i t h m s k e yw o r d s ：v i s u a l i z a t i o n ；t r e e m a p ；b i d i r e c t i o n a ls q u a r i f i e da l g o r i t h m ； s q u a r i f i e da l g o r i t h m 双向正方化树图生成算法 图1 1 图1 2 图1 3 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图3 1 图3 2 图4 1 图4 2 图4 3 图4 4 插图索引 某单位招聘信息表4 一个典型注册表的缩进图5 一个结点连接图5 节点连接图和树图可视化同一集合的结果9 一个磁盘文件系统的树图1 0 一维c u s h i o n 算法示意图1 1 一个使用了c u s h i o n 算法的树图1 3 s l i c e a n d d i c e 算法生成的树图1 4 正方化算法流程示意图1 5 p i v o t 算法示意图1 7 一个s t r i p 算法生成的树图1 8 小元素优先的正方化算法流程2 1 双向靠边策略的流程图2 2 树图1 0 对n b a 比赛成绩生成的树图3 2 p r o g r a mf i l e s 文件夹对应的树图3 4 双击m so f f i c e 矩形后的树图3 4 s t r i p 算法生成的m so f f i c e 文件夹的树图3 5 硕士学位论文 表3 1 表3 2 表3 3 表3 4 表3 5 表3 6 表5 1 表5 2 表5 3 表5 4 附表索引 三种算法的比较2 4 正方化算法和双向靠边策略算法比较2 5 几种主要数据集合的靠边阈值2 7 正方化算法和双向正方化算法的平均长宽比2 8 正方化算法和双向正方化算法时间比较2 8 正方化算法和双向正方化算法长宽比分布比较2 9 2 0 1 的数据集合下几种算法的比较3 7 5 0 x 1 的数据集合下几种算法的比较3 7 1 0 2 的数据集合下几种算法的比较3 8 8 x 3 的数据集合下几种算法的比较3 8 v 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：l 訇插 日期：小哼年5 月2 ，日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名：l 习蜇 导师签 日期：p 叮年万月二多曰 日期：稚p 月乡日 硕士学位论文 第1 章引言 随着计算机在社会各行各业各领域的渗透和发展，使用计算机的社会 群体越来越广泛，计算机技术的应用也越来越普遍；随之而来的，传统 的贫乏的显示数据的方式已不能满足人们的需求。人们越来越不能满足 计算机提供的静态的、单调的、枯燥的表示数据的方法，而希望有一些 动态的、多样的、生动的方法表示这些现实生活中的数据。在这种情况 下，可视化技术一一即研究如何将数据、信息和知识转化成人脑可以 快速认知的生动形式，使人们可以有效的观察、使用、理解和交流大规 模的复杂信息的技术1 1 】，成为计算机应用领域中的一个重要问题。 1 1 可视化技术概况 1 1 1 科学可视化 早期计算机主要用在科学研究方面，因此这个时期的可视化技术主要 是用于辅助科学研究；当时的科学家们使用这些技术来可视化实验仪器 和超级计算机生成的实验数据 2 1 。这种主要用于科学研究需要的可视化 通常称为科学可视化。科学可视化具有很强的专业性和针对性：它可视 化的对象通常是科学实验中得到的各种数据：它的主要任务是帮助科学 家深入理解、探索和发现埋藏在实验数据下的科学规律；它的使用者， 则主要是从事这些研究工作的科学家们。科学可视化的出身，决定了它 不可能被非专业领域的人们使用，也导致了随后的信息时代对新的可视 化技术的呼声。 1 1 2 信息可视化 随着互联网络的飞速发展和计算机在各领域的渗透，社会各界各领域 都产生了对可视化技术的迫切需求。过去留下来的科学可视化技术不能 满足信息时代的这种需求；人们需要的是更友好，更普遍的可视化方法。 新的可视化方法主要针对的不应是实验室里产生的实验数据，而是现实 生活中存在的各种联系、信息和非科学方面的数据：新的可视化方法的 主要任务不应是辅助科学家们探索科学的奥秘，而是如何快速的发现和 理解现实生活中的信息和数据【3 j 。 这种新的可视化的技术，我们通常称之为信息可视化。信息可视化， 听起来是属于计算机图形的范畴，而实际上它远不止是计算机图形的研 双向正方化树图生成算法 究；它还融合了科学可视化、人机交互和数据挖掘。经过近年来的发展， 信息可视化已经初具雏形；研究者们研究了各种可视化的方法，针对各 种类型的信息进行可视化。根据可视化数据其结构上的特点，可以将现 有的可视化技术分成七类【4 】： 1 一维数据的可视化。 一维数据，通常指的就是一维的、线性的数据，比如文字或者一组符 号。文本文件，人名和地址的列表。计算机程序的源代码这些都是基于 一维线性数据的信息。对一维数据的可视化主要需要考虑两个问题：数 据有多大的规模，和用户需要对数据进行什么操作。 对于一维数据的可视化，这里有一个很常见的例子。早期的程序员都 在只有黑白两种颜色的编辑器下面编写源代码，代码里不管是关键字、 注释，还是变量名、宏，都是一样的颜色，阅读代码、检查代码错误的 难度很大：程序员们通常需要花很长的时间检查出一个拼写错误，或者 排除一个b u g 。而在现代的集成开发环境下，程序员键入的每一行代码、 每个单元都按照语法被分析、显示成各种颜色，这样整个代码看上去 条理分明、结构清晰，也便于程序员寻找拼写错误和程序的b u g 。这就是 一个典型的一维可视化的例子。 2 二维数据的可视化。 二维数据的可视化指的是对二维空间内实体的可视化。对于二维数据 的可视化，近年来最热门的研究英过于g i s ( 地理信息系统) 了。大型的 g i s 系统一直都被用于区域规划、交通规划、天气预报和地图制订方面， 而小型的g i s 系统更是随处可见，比如互联网上常见的一个城市的交互 性的地图就是一个小型的g i s 。 3 三维数据的可视化。 三维数据即对三维空间内实体的可视化。三维数据在生活中太普遍 了，我们接触到的任何实体都是三维的，而在科学研究中获取的数据很 多也是三维的。三维数据的可视化主要是使用计算机屏幕这种二维空间， 配合一些交互性的操作来模拟三维空间，实现对三维数据的可视化。 三维数据的可视化现在已经广泛应用到社会各个领域，但是其中最主 要的领域还是在建筑和医学方面。q u i c k t i m e v r ，v r m l ( 虚拟现实建 模语言) 和数字图象是三维数据可视化领域中比较具有代表性的技术。 4 多维数据的可视化。 多维数据，也就是一些具有三个以上属性的数据。这些属性都是同等 重要，对描述一个这样的数据必不可少的。通常我们可以结合颜色、大 小、文字和呵视化二维数据、三维数掘的方法来可视化这类数据。 硕士学位论文 5 实时数据的可视化。 动态的可视化实时数据也是近两个世纪来人们一直在研究的问题。所 谓实时数据，就是会实时变化的数据；对实时数据的可视化，不仅要能 够反映实时数据在某一时刻的特征，还要能体现实时数据在一段时期内 变化的规律和特征。w i n d o w s 的任务管理器就是一个实时数据可视化的 例子，它不仅通过文字来动态表示各个进程占用c p u 及内存的信息，也 通过图表显示c p u 的占用率及网络的使用情况。 6 网状数据的可视化。 网状数据，是指可能和其他数据有关系的数据的集合。这种关系通常 没有父子之分，是同级的关系，任何一个数据可能和任意其他数据有这 种关系；因此它不像下文中要提到的层次结构数据一样具有阶层。由于 一个网状数据集合内部的关系非常复杂，如果不应用可视化手段的话， 通常很难有效的表示它。因此，对网状数据集合的可视化也是可视化问 题中的一个难点。 7 层次结构数据的可视化。 层次结构数据可以看成一种特殊的网状数据，这种数据的集合通常可 以形象的用一颗树来表示，所有的元素，及树中的结点都有一个共同的 父结点，每个结点又可以有兄弟结点和孩子结点。当数据集合的规模扩 大时，这种数据集合内部的关系也非常繁多和复杂，因此如何可视化层 次结构数据，也一直是研究者们关心的问题。本文将主要针对层次结构 数据可视化的方法进行介绍和研究。 在可视化方法的应用中，由于各行业信息的不同特点，某个行业待可 视化的数据可能是一维的，另一个行业可能是二维的，甚至有的行业的 信息是结合了两种或多种数据类型的。在这种要求下，研究者们展开了 对各种类型的数据可视化的研究，使得可视化的内容相当丰富。然而， 虽然可视化技术的发展必然呈现多样化、专门化的特点，业界仍然需要 一套统一的规范和标准，能抛开这些具体的差异，站在更抽象的层面上 对信息可视化技术的发展进行指导。这种规范和标准的制订也是将来可 视化领域发展的一个重要方向”j 。 1 2 层次数据集合的可视化 层次数据集合的可视化一直是可视化研究领域中的一个重要问题。自 然界广泛存在着各种具有层次结构的信息：计算机的目录结构，一个单 位和组织的人员结构，个图书馆的藏书信息，等等。对这种普遍存在 的信息研究一种可视化的方法，其意义是不言而喻的。对于层次结构数 双向正方化树图生成算法 据集合的可视化，传统的方法主要包括表、缩进图和结点连接图【6 1 。 1 表。表是一种被广泛用来表示层次数据集合的可视化方法。使用 表可以很直观的看到数据集合中个要素的详细内容，但是使用表很难体 现整个数据集合的层次结构。有的表格规定了一些表示方法来表示层次 结构，但是这些方法通常都不直观，使用者要花一定的时问和精力从这 些表格上获取数据集合的层次信息。 2 缩迸图。缩进图是很常用的表示层次数据集合的方法，最典型的 例子就是w i n d o w s 中资源管理器的用于显示整个文件系统的结构图。使 用缩进图可以直观地表示数据集合的结构和内容，但是通常使用者只能 通过缩进图看到整个数据集合的部分元素，这种部分的显示经常不能满 足使用者的要求 7 1 。 3 结点连接图。结点连接图是由一系列的结点以及它们之间的连接 组成的视图，这种图是显示小规模层次数据集合非常有效的方法f 8 1 l 】。 但是结点连接图浪费了较大部分的显示空间，而且使用结点连接图也不 便直观地表示数据集合中各元素的内容。 图1 1 、1 2 和1 3 分别给出了表、缩进图和节点连接图的例子。这些 方法通常都是使用基于文字的方式显示数据元素的属性，因此当数据集 合的规模一扩大，这种基于文字的显示方法不够直观一一必须逐个仔细 查看每个元素的文字内容，否则使用者无法从整个图上找出他感兴趣的 部分。而且，要使文字能够被用户看清楚，必然会对显示范围内的数据 集合大小产生限制。 因此，一旦数据集合规模扩大，传统的显示层次数据集合的方法都显 得力不从心了。有没有一种可视化的方法，可以在有限的面积上显示大 量的数据，而又可以使浏览更加直接、快捷呢? 帮n幢研室( 科室)人披专生( 方冉)学历 政治经济学硼士菠以上 西方经济学博士 经济蕞 徽研室 计量经济学碗爱以上 宏观l 鞋井学博士 金融系埘 i 金融投瓷博士 保睑幕保险 保险车科及以上 1匝际经济掌尴界经济博士 田际贸易 田贸幕时际物流与运输t w r o - 籼l碉士爱i 【上 投资理财 固际投资国际商务 博士 图1 1某单位招聘信息表 硕士学位论文 1 3 树图及其应用 图1 2一个典型注册表的缩进图 图1 3一个结点连接图 1 9 9 1 年5 月，美国m a r y l a n d 大学的人机交互专家b e ns h n c i d c r m a n 提出了用一种新的方法树图来表示大规模层次数据集合的方法1 1 1 。这种 方法采用基于二维空间填充的技术将显示空间划分为许多具有一定大小 的矩形来可视化层次数据集合，充分利用了显示空间的每一个象素，非 常适合数据集合很大的情况。由于可以用各个矩形的大小来表示数据元 素的某一属性，因此当使用者对数据元素的某一属性非常感兴趣时，树 图中很明显的面积分布可以帮助使用者直观、快速的得到整个数据集合 关于这一属性的总体情况。图2 1 中显示了一个典型的树图。 当树图刚提出来的时候，树图的生成算法还很不完善。其中存在两个 最大的问题就是层次结构不够直观和图中表示数据元素的矩形长宽比过 高【13 1 。 1 层次结构不够直观。 由于整个显示空间都被繁多的矩形填满，要从整个图中看出层次结构 比较网难。b c ns h n c i d er m a n 指出可以通过给每一层的矩形空出 定的边 嘲叫c 畦r d a 脚l e n v i r m 鞠 童 i d 哪t h 酵 也 d 0 3 d b d 6 5 - h 4 c 啪3 b z l d l 9 科 日o c 7 l i 国自r 斜i 丑h k r o k 国t o b 口ke 印哥 5o e jb b c k 5 h d h s ；t 口。口k 朋佑 丑h t t p _ ：t 龃h a 劓吐e e b 晰w # t 口r c e m5 罐 口1 - r l 脯 r r _ r t b n _ y w l h 目a 江r l 如f ：曲嘲曩 m 圈1 2 一个典型注册袁的缩进田 1 3 埘图及其应用 图13 一个结点连接图 1 9 9 1 年5 月，美国m a r y l a n d 大学的人机交互专家b e ns h n e i d e r m a n 提出了用一种新的方法树图来表示大规模层次数据集合的方法 1 2j 。这种 方法采用基于二维空间填充的技术将显示空间划分为许多具有一定大小 的矩形米可视化层次数据集合，充分利用了显示空间的每一个象素。非 常适合数据集合很大的情况。由于可以用各个矩形的大小来表示数据元 素的某一属性，因此当使用者对数据元素的某一属性非常感兴趣时，树 图中很明显的面积分布可以帮助使用者直观、快速的得到整个数据集合 关于这一届性的总体情况。图2 1 中显示了一个典型的树图。 当树图刚提出来的时候，树图的生成算法还很不完善。其中存在两个 最大的问题就是层次结构不够直舰和图中表示数据元素的矩形长宽比过 高【”i 。 1 层次结构不够直观。 _ 丁整个显示窑问都被繁多的矩形填满，要从整个图中看出层次结构 比较困难。b e l ls h l e i dg r l l l a n 指出可以通过给每层的矩形空h 定的边 比较困难。b e ns h n e i de r m a n 指出町以通过给每一层的矩形窄m 一定的边 双向正方化树图生成算法 隙来表示层次结构【1 4 】，这种方法从一定程度上提高了层次结构的可见性， 但是仍然不够理想。而且这种方法使用了一定的空间表示边隙，浪费了 显示空间。 2 矩形长宽比过高。 由于初始的树图的生成算法只是由简单的切割显示空间形成，使得图 中存在大量高长宽比的矩形。矩形的长宽比太高有许多弊端，最主要的 弊端体现在：不便于比较两个矩形的面积；不便于使用定位型输入设备 ( 如鼠标) 选择某个矩形，等等【”l 。 针对树图中矩形长宽比过高的问题，1 9 9 9 年w a t t c n b e r g 提出了一种 改进的方法，他使用一个递归的算法实现矩形的分布，减少了矩形的长 宽比，这种方法被命名为c l u s t e r 树图【1 6 】。同年，荷兰e i n d h o v e n 大学的 j a r k ej v a l lw i j k 看到了树图中存在的层次关系不直观的缺点，提出了另 一种改进的方法c u s h i o n 树图，这种方法使用三维的光影效果表示树图 中的层次关系，得到了很好的效果【1 7 】。2 0 0 0 年，b r u i s ，h u i z i n g ， 和 v a nw i j k 提出了另一种算法生成的树图一一正方化树图，比之c l u s t e r 树图能够更大地降低矩形的长宽比【“】。但是，c l u s t e r 树图和正方化树图 这两种方法都改变了数据在原来数据集合中的顺序一一生成的矩形的顺 序和其对应数据原来的顺序不一致。这使得在一个图中寻找某个特定的 数据非常困难；而且当数据集合部分变化时，会导致整个图发生很大的 变化，使得观察动态数据集合非常困难【1 8 】。 2 0 0 1 年1 0 月，b e ns h n e i d e r m a n 在i e e e 信息可视化会议上面提出了 一种新的树图生成算法，这种算法既可以缩小矩形的长宽比，又能够保 持各数据元素在原数据集合中的顺序。2 0 0 2 年，b e ns h n e i d e r m a n 又对原 来最早的树图算法进行了改进，提出了s t r i p 树图算法，保持了数据在原 数据集合中的顺序，并可以获得好的长宽比【”】。同年i e e e 的信息可视 化会议上，f r a n kv a nh a m 和j a r k ej v a nw i j k 又提出了一种全新的方法 b e e m t r e e s f ”1 ，它使用交叉覆盖的方法表示数据集合，既保存了顺序，并 且有很好的长宽比，而且还能很好的体现数据集合中的层次关系。但是 它并没有完全使用显示空间，因此能够显示的数据集合的规模小于树图。 树图自1 9 9 1 年b c ns h n e i d e r m a n 提出来以后，到现在已经应用在很多 领域的可视化中。1 9 9 2 年出现了第一个树图的应用，德国的a l e x a n d e r j u n g m e i s e t e r 使用树图可视化了一个销售公司的管理结构，这个应用程序 可以显示客户，管理人员，工业部门和市场的层次结构f “】。1 9 9 4 年，f _ 1 本的a s a h it o s h i y u k i 使用树图建造了一个用于事务决策的程序，用户可 以投票选择他认可的方案或组织【22 1 。m a r y l a n d 大学的h ug h c s 网络系统 硕士学位论文 中的人造卫星网络子系统也使用了树图【23 1 。2 0 0 1 年，微软研究小组的 m a r cs m i t h 将树图使用在n e t s c a n 项目中用于可视化u s e n e t ，网上最大 的虚拟社会之一【2 4 】；微软公司还在它的n e t 开发环境中加入了树图组 件。2 0 0 3 年，i b m 公司也开始使用树图来可视化它的网络管理系统 2 5 】。 综上所述，树图是一种表示大规模层次数据集合的一种有效的方法 【2 6 - 3 0 】。目前针对这种方法的研究重要集中在国外，国内几乎没有有涉 及树图的研究。研究树图主要集中在如何直观显示层次结构和优化矩形 长宽比这两个方面，而由于这些研究起步晚，方法还不够全面；因此在 这两个方面，树图尚有进一步改进的潜力和可能。 1 4 本文工作及结构 本文工作主要包括两个部分： 1 提出了双向正方化算法。本文首先分析了正方化算法，在对一些 实例进行分析的基础上，对原算法中的假设提出了新的看法，并依此提 出了小元素优先的思想和双向靠边策略。同时，本文对这两种思想进行 了分析和实验，根据实验结果体现出的两种思想对长宽比的改进程度， 保留了双向靠边策略；并引入长宽比阈值的概念，通过实验选择出最优 的长宽比闽值，并结合长宽比阙值进一步优化了生成树图的平均长宽比 和时间复杂度。实验数据表明，双向正方化算法使用有限的时间代价换 取了较小的平均长宽比和较好的稳定性。 2 实现了一个功能较完全的树图原型：树图1 0 ，并对几种树图生成 算法做出了进一步分析。树图1 0 实现了几种主要的树图生成算法，能够 导入用户编写的数据文件并生成对应树图，并可以使用树图分析磁盘文 件的分布和使用情况。同时，在树图1 0 下我们还进一步进行了模拟实验 和用户反馈分析的工作，进一步考察了几种主要的树图生成算法和双向 正方化算法在其他方面的性能；并对双向正方化算法的部分缺陷提出了 一些解决方法。 本文的结构安排如下。第一章为引言，介绍了可视化技术和层次数据 集合可视化技术的发展概况，以及树图的特点和发展过程。第二章为树 图生成算法的研究，针对几种主要的树图生成算法进行了分析和比较。 第三章进一步分析了正方化算法，并在此基础上提出了结合了双向靠边 策略和靠边阈值思想的双向正方化算法，通过实验对双向正方化算法和 正方化算法的性能进行了分析和比较。第四章介绍了我们开发的树图原 型的特点和功能。第五章我们以树图原型为平台进行了进一步的实验， 并通过爻验结果分析了双向正方化算法和其他几种树图生成算法。最后 双向正方化树图生成算法 我们总结了本文的工作，并对后继的工作提出了一些设想。 硕士学位论文 第2 章几种主要树图生成算法 下面我们就一个简单的实例来说明树图的概念。对于一个具有层次结 构的数据集合，图2 1 中显示了用传统的节点一连接图和树图来来可视化 同一个层次数据集合的结果。 j 1耗1 i = t 1 4 4 c 3 f 2 l 1啊1n 10 1 图2 1 节点连接图和树图可视化同一集合的结果 显然，相比节点连接图，树图更有效的使用了显示空间的每一个象素， 图中的每一个象素都被使用来表示其中某个节点【3 1 3 5 】。就本例来说， 这个数据集合是一个具有4 层结构的集合，集合中每个元素都具有一定 的大小。树图的生成过程如下：整个显示空间，即初始矩形，被用来表 示整个数据集合( 等同于节点一连接图中的根结点a 1 6 ) 。然后，根据下 一层的数据元素口3 、c 3 和d 1 0 的大小，纵切初始矩形，切出的三个矩 形分别对应b 3 、c 3 和d 1 0 ，并且它们的面积比例和它们对应数据元素的 大小比例相同。然后如此递归，每次递归都改变切割的纵横方向，一直 切到叶子节点为止。这也就是最简单的s l i c e a n d d i c e 算法。 在数据规模比较大的时候，树图更能体现它相比传统方法的优越性。 图2 2 显示了个磁盘上文件系统的总体情况。这个文件系统上一共有 1 4 0 0 多个文件，而用树图可以毫不费力的将他们显示出来，这是任何传 统可视化方法都无法做到的。同时，用户还可以直观的从整张图上看出 那个文件最大，主要是那些部分消耗了磁盘的空间，等等。每个块的标 签在这里并没有显示，但是通过点击方块可以获得对应文件的详细信息。 近年来研究者们针对结点连接图展开了一系列的研究，而且现在结点 连接图仍然是最广泛用来表示层次结构数据集合的可视化方法。但这种 方法浪费了大量显示空间，不适合数据规模比较大的情况【3 6 】【3 。像上例 中磁盘空削的显示，用节点连接图是很难完成的。 虽然树图在可视化大规模层次数据集合方面有节省空间的优势，但从 图2 2 中我们也不难看出，树图存在前文中提到的两个明显的缺陷：层次 森一 双向正方化树图生成算法 结构不够直观和生成矩形长宽比过大。因此在树图的思想及 s l i c e - a n d d i c e 算法提出以后，针对树图的理论研究主要集中在改进树图 的这两个缺陷方面。近十年来，可视化的研究者们提出了许多种树图生 成算法，其中有改进树图层次结构显示的c u s h i o n 算法，改进树图矩形长 宽比的正方化算法，以及针对正方化算法乱序的缺陷提出的p i v o t 算法和 s t r i p 算法。下面我们介绍和比较这几种树图生成算法。 2 1 c u s h i o n 算法 圈22 一个磁盘文件系统的树圈 从图2 2 中我们可以很直观的看到一个磁盘上文件大小的总体信息。 然而，磁盘上的文件是个典型的树型结构，每一层的文件就像叶子结点， 而文件夹像中间接点。从这个树图上倒是可以很清楚的看出叶子结点大 小比例关系，但是其中a 文件和b 文件是同一目录下的吗? c 文件是不是 d 文件上层目录的? 这些层次信息在树图中体现的很不明显。虽然经过仔 细的观察可以大致看出层次关系，但是花费人力太大，不符合可视化的 原则14 0 。 嵌套树图可以在一定程度上解决这个问题f ”1 。在每个阶段摆放元素 的时候，实际r 放上去的矩形比本来的小一点，这样就可以每一。层的兄 硕士学位论文 弟节点都共有一个边缘。但是嵌套树图由于要留出空间来体现结构，这 样势必要消耗多余的显示空间。而且，当树图层次比较多的时候，用嵌 套树图还是需要较大的人力辨别出层次结构。使用宽度不同的边缘线表 示结构也是一种方法，但是这种方法也需要较大的人为工作才能识别层 次结构【 j 。而且使用这种方法生成的图看起来就像个迷宫，显得非常不 友好并会使用户感到困惑。用颜色来表示层次结构虽然可行，但是在树 图中通常颜色还要被用来表示其他的信息，因此这样做将大大削弱树图 的功能 4 0 1 4 。 e i n d h o v e n 大学的j a r k ej v a nw i j k 提出了一种用阴影来表示层次关 系的树图生成算法。这种算法使用不同的阴影来表示整个树图不同的层 次，使得层次结构非常直观。图2 3 是一个使用阴影单方向分割的例子。 图中，下方是显示空间，现预将它切割成表示三层、每层两个元素( 假 设大小相等) 的树图。第一层有两个元素，将宽等分成两个子宽，并在 其上都添加一个突起。对每个子宽又划分两个子宽，并添加两个幅度为 上一步一半的突起。如此划分并添加，直到最底层元素。图中下半部分 既是使用这种算法产生的树图。如果我们从切面观察树图，这些突起就 构成了一系列的脊，这些脊清楚的将不同元素分开。而且，两个脊中间 峡谷的深度越深，说明两个脊层次越高。 图2 3 一维c u $ h i o n 算法示意图 实际上使用的时候，我们都是将这种思想在两个方向上分割的。设z 轴为水平轴，y 轴为垂直轴，z 轴为射向观察者的轴。如果我们沿着x 轴 切割矩形，那么就可以在y 轴方向添加突起；反之如果沿着y 轴切割矩 形，就在x 轴方向添加突起。算法最后形成的是一个类似坐垫( c u s h i o n ) 一样的树图，因此这种算法叫做c u s h i o n 算法。算法中采用的突起是最简 单的抛物线突起，因此每个矩形都具有一个类抛物线的表面。对于任何 双向正方化树图生成算法 一个矩形，它在z 轴方向上的高可以用下式表示： z ( x ，y ) = a x 2 七b y 2 七c x 七d y 七e 算法开始时，初始矩形是平的，式中所有系数都为0 。假设现在沿z 轴向切割出了一个新的矩形，那么我们在z 轴上的增量4 z 可以表示为： a zh ，) ，夕= j l 0 一x 1 ) ( x ：一x ) 石2 一z 1 式中z ，善2 为矩形在z 轴方向的边界坐标。增加突起的高度在x = x 和并= x 2 处为0 ，在z = ( x l + z 2 ) 2 处为h 2 x i j h 。h 是高和宽的比值， 用来控制突起的形状。从式中我们可以看出厶z 并不依赖于y ，因此在y = c 上突起的高度都是一样的。 同样的，我们也可以得出沿着y 轴切割时z 的表达式： h za ，_ y 夕= 旦( y y 。) ( y ：一y ) y 2 一y 1 通过调整h 的值，可以改变树图对层次结构的强调程度。通常的做法 是令每一步的 h i ：f i h ( o l 1 ) 图2 4 中给出了一个较复杂的层次数据集合用c u s h i o n 算法生成的树 图的例子。可以看出图的层次结构信息很明显，而且也不需要牺牲额外 的显示空间来表示层次结构。 c u s h i o n 算法本身并不是一种生成树图的算法，它并不提供切割矩形 的方法和策略，它所做的就是在矩形切割好以后，按照矩形的大小和切 割的方向在其上添加阴影，模拟突起的效果。因此，c u s h i o n 算法可以灵 活的和其他算法结合使用。 但是，c u s h i o n 算法也有其不足之处。树图的设计方案决定了树图只 能通过矩形的面积和矩形的颜色两个要素，同时表示出至多二维的信息。 嵌套树图不得不牺牲一部分矩形的面积作为边缘来体现层次关系( 改变 矩形边缘宽度事实上也是牺牲一部分矩形的面积换取一定层次关系的体 现) 。c u s h i o n 算法自然也不可能凭空变出另一个要素。它使用的虽然是 阴影，但是阴影实际上也不过是颜色这个要素中抽取的一维。就像牺牲 一部分面积会影响总体面积一样，牺牲颜色中的一维必然也会对颜色的 使用造成影响。 图2 4 中虽然可以明显看出层次关系，但由于突起的特征是中间亮边 缘暗，使得每个大突起的边缘都很暗；而在大突起边缘上小一点的矩形， 由于层次较低，突起较小，对光晕的影响也很小，因而呈现深暗色，给 硕士学位论文 元素的识别带来很大困难。同时，有几处元素比较密集而光线又比较暗 图2 4 一个使用了c h $ h i o n 算法的i 对图 的地方，基本看不清楚有多少个元素。而且，如果用户采用颜色深浅来 表示元素的某种属性的话，c u s h i o n 视图会使得这种属性很难分辨。 但是从总体上说，c u s h i o n 算法还是很有价值的。它不像其他算法需 要额外的显示空间来表达层次信息，而且算法比较简单，阴影深度也比 较好控制。并且，树图使用者通常最关心的是面积较大的元素，使得小 元素在c u s h i o n 树图中辨不甚清的缺点也可以忽略了。因此，c u s h i o n 算 法的思想仍是目前对树图层次结构的改进最成功的思想。 2 2 正方化算法 在1 9 9 9 年1 0 月的i e e e 信息可视化会议