基于树图的大规模数据集合

基于树图的大规模数据集合

0可视化树图的应用1991年5月，美国密歇根大学的虚拟机专家贝塞尔姆提出了一种新方法来表示大数据集。这种方法采用基于二维空间填充的技术将显示空间划分为许多具有一定大小的矩形来可视化层次数据集合,充分利用了显示空间的每一个象素。由于树图可用各个矩形的大小来表示数据元素的某一属性,非常适合数据集合很大的情况。树图现在已经应用在很多领域的可视化中。1992年,德国的AlexanderJungmeiseter使用树图可视化了一个销售公司的管理结构,这个应用程序可以显示客户、管理人员、工业部门和市场的层次结构。2001年,微软研究小组的MarcSmith将树图使用在Netscan项目中用于可视化Usenet,网上最大的虚拟社会之一;微软公司还在它的.NET开发环境中加入了树图组件。2003年,IBM公司也开始使用树图来可视化它的网络管理系统。目前针对树图的研究主要集中在国外,国内几乎没有涉及树图的研究。研究树图主要集中在如何直观地显示层次结构和优化矩形长宽比这两个方面,由于研究起步晚,方法还不够全面,因此树图有进一步改进的潜力和可能。1树图的应用研究对于一个具有层次结构的数据集合,图1显示了用传统的节点连接图和树图来可视化同一个层次数据集合的结果。树图的生成过程如下:整个显示空间,即初始矩形,被用来表示整个数据集合(等同于节点-连接图中的根结点A16)。然后,根据下一层的数据元素B3、C3和D10的大小,纵切初始矩形,切出的三个矩形分别对应B3、C3和D10,并且它们的面积比例和它们对应数据元素的大小比例相同。然后如此递归,每次递归都改变切割的纵横方向,一直切到叶子节点为止。这也就是最简单的Slice-and-Dice算法。在数据规模比较大的时候,树图更能体现它相比传统方法的优越性。图2显示了一个磁盘上文件系统的总体情况。这个文件系统上一共有1400多个文件,而用树图可以毫不费力的将他们显示出来,这是任何传统可视化方法都无法做到的。用户还可以直观的从整张图上看出哪个文件最大,消耗了磁盘的空间等等。通过点击方块可以获得对应文件的详细信息。虽然树图在可视化大规模层次数据集合方面有节省空间的优势,但从图2中我们也不难看出,树图存在前文中提到的两个明显的缺陷:层次结构不够直观和生成矩形长宽比过大。因此针对树图的理论研究主要集中在改进树图的两个缺陷上。近十年来,可视化的研究者们提出了多种树图生成算法,其中有改进树图层次结构显示的Cushion算法,改进树图矩形长宽比的正方化算法,以及针对正方化算法乱序的缺陷提出的Pivot算法和Strip算法。下面介绍和比较这几种树图生成算法。1.1cup实现树图的层次结构从图2中可以很直观地看到一个磁盘上文件大小的总体信息。然而,磁盘上的文件是个典型的树型结构,每一层的文件就像叶子结点,而文件夹像中间接点。从这个树图上虽然可以清楚的看出叶子结点大小比例关系,但是其中a文件和b文件是同一目录下的吗?c文件是不是d文件上层目录的?这些层次信息在树图中体现的很不明显,不符合可视化的原则。Eindhoven大学的JarkeJ.vanWijk提出了一种用阴影来表示层次关系的树图生成算法。这种算法使用不同的阴影来表示整个树图不同的层次,使得层次结构非常直观。图3是一个使用阴影单方向分割的例子。图3中,下方是显示空间,现预将它切割成表示三层、每层两个元素(假设大小相等)的树图。第一层有两个元素,将宽等分成两个子宽,并在其上都添加一个突起。对每个子宽又划分两个子宽,并添加两个幅度为上一步一半的突起。如此划分并添加,直到最底层元素。图中下半部分既是使用这种算法产生的树图。如果我们从切面观察树图,这些突起就构成了一系列的脊,这些脊清楚的将不同元素分开。而且,两个脊中间峡谷的深度越深,说明两个脊层次越高。图4给出了一个较复杂的层次数据集合用Cushion算法生成的树图的例子。可以看出图的层次结构信息很明显,而且也不需要牺牲额外的显示空间来表示层次结构。Cushion算法本身并不是一种生成树图的算法,不提供切割矩形的方法和策略,它所做的就是在矩形切割好以后,按照矩形的大小和切割的方向在其上添加阴影,模拟突起的效果。因此,Cushion算法可以灵活的和其他算法结合使用。但是,Cushion算法也有其不足之处。树图的设计方案决定了树图只能通过矩形的面积和矩形的颜色两个要素,同时表示出至多二维的信息。嵌套树图不得不牺牲一部分矩形的面积作为边缘来体现层次关系(改变矩形边缘宽度事实上也是牺牲一部分矩形的面积换取一定层次关系的体现)。Cushion算法自然也不可能凭空变出另一个要素。它使用的虽然是阴影,但是阴影实际上也不过是颜色这个要素中抽取的一维。就像牺牲一部分面积会影响总体面积一样,牺牲颜色中的一维必然也会对颜色的使用造成影响。从总体上说,Cushion算法还是很有价值的。它不像其他算法需要额外的显示空间来表达层次信息,而且算法比较简单,阴影深度也比较好控制。并且,树图使用者通常最关心的是面积较大的元素,使得小元素在Cushion树图中辨不甚清的缺点也可以忽略了。因此,Cushion算法的思想仍是目前对树图层次结构的改进最成功的思想。1.2加入本形的矩形信息进行移动假设有一个一层的数据集合T={6,6,4,3,2,2},需要在一个长为6,宽为4的矩形区域上显示出这个数据集合。如果使用slice-and-dice算法,由于这个数据集合只有一层,所以初始矩形不是被横切就是被纵切,如图5,这样生成的矩形大都呈现为长条状,可视化效果很差;如果使用正方化算法,整个过程如下(矩形x表示面积为x的矩形):(1)首先选出当前面积最大的矩形6,摆在初始矩形的较小边上,使生成的矩形贴着矩形的较小侧边,记录此时矩形6的长宽比,为8/3。(2)横向加入当前面积最大的矩形6,同样贴着初始矩形的较小侧边,并和第一个矩形相邻。记录此时已加入的两个矩形长宽比中的最大值,为3/2。(3)由于3/2<3/8,说明第二个矩形6的加入对整体的长宽比有改善,确定加入第二个矩形6。(4)横向加入当前面积最大的矩形4。记录此时已加入的矩形长宽比中的最大值,为4。(5)由于4>3/2,说明矩形4的加入增大了整体的长宽比,放弃加入矩形4。(6)矩形4成为当前待加入的矩形,初始矩形为当前剩余的空白区域。按照和上述步骤相同的方法进行加入,直到最后所有矩形都被加入为止。将图6和图5略加比较就可以看出,正方化算法大大降低了生成矩形的长宽比,可视化的效果更好。图中的阴影部分表示当前处理的阶段,每一个阶段完结时,将剩下未填充的显示区域作为下一阶段的工作区域,将这一阶段最后那个放弃加入的矩形作为下一个阶段第一个待加入的矩形,进行下一阶段的填充。正方化算法本质上是一种自适应的算法,通过密切关注每一步导致长宽比的变化来控制布局。同时它每一步也是尽可能多加入矩形,只要加入的矩形对这个阶段的长宽比是有利的,那么就加入;反之结束当前阶段,将这一矩形留到下一阶段。正方化算法的着力点在改进树图的长宽比。因为矩形的长宽比取决于面积和摆放位置,正方化算法因此在这两方面都作了考虑,也达到了非常好的效果。但是,在面积方面,由于元素在树图中对应矩形的位置是根据大小排序的,如果元素原来在集合中有顺序的话,那么原来的顺序势必需要打乱。而在摆放策略方面,由于采用的自适应的思想,当元素面积发生变化时,会导致很明显的布局变化;这在动态情况下会导致树图剧烈的抖动。因此,正方化算法并不适合元素动态变化情况下的使用。1.3pivat算法Cluster算法和正方化算法都要打乱原数据集合中元素的顺序才能达到良好的显示效果。当数据集合中元素顺序无关紧要时这是可以容忍的,但当数据集合中元素顺序是个比较重要的属性的时候,就不大适合使用这两种算法了,用户无法从生成的树图上得到任何顺序信息。而对于最简单的Slice-and-Dice算法,元素的顺序倒是可以很直观地体现出来,只需在每一轮切割时保持元素的顺序,那么生成的树图就是分块有序的。而对于这样分块有序的树图,定位一个元素的难度很小,当元素属性变化的时候给整个树图带来的变化也很小。针对这一情况,BenShneiderman在2002年提出了顺序树图的概念,并提出了两种兼顾顺序和长宽比的算法:Pivot算法和Strip算法。Pivot算法并不能保证树图中矩形的顺序能绝对符合对应元素在数据集合中的顺序,它采用的是一种部分有序的思想。使用Pivot算法对于某个数据集合生成的树图,原来位置接近的数据元素,其对应树图中的矩形位置也接近;原来相邻的元素,在树图中对应的矩形位置不一定相邻但也不会太远。Pivot算法使用一个递规的过程完成矩形的摆放,整个过程试图在二维空间上模拟快速查找(quicksort)算法。算法的输入是一个待切割的初始矩形R(初始显示区)和一个有序号的有大小的的元素的集合。算法的第1步是寻找一个特殊的元素pivot,摆放在R的边上;第2步,集合剩下的元素被分配到R剩余部分的三个大矩形里;然后算法按照此方法递规地切割每个矩形,直到到达最底层元素。可用图7来辅助说明算法的过程。虽然在此图中初始矩形R的宽比高要大,但算法稍作改动就可以适合宽比高小的情况。Pivot算法:输入:待切割的矩形R;有大小的元素L1,L2,…,Ln输出:一系列矩形,R1,R2,…,Rn(1)如果当前集合中元素个数≤4,用Pivot算法切割,整个过程完成。(2)设集合中最大的元素为P,也就是pivot。(3)如果R的宽大于高,按图7将R切割成R1,R2,R3,Rp四个矩形(如果R的高大于宽,只需采用沿y=x对称的切割布局)。(4)将P放在Rp中。Rp的实际大小和位置在第5步决定。(5)将集合中除了P剩下的元素分成3组L1,L2,L3,分别放在R1,R2和R3中。L1,L2和L3都可能为空。分组原则是:L1应包含所有序号小于R的元素;L2中的元素序号都小于L3中的元素,并且应尽量使矩形Rp的长宽比接近1。(6)对于R1,R2,R3,回到第一步,按照同样的过程对它们进行切割。根据Pivot的选取原则,Pivot算法有几个变体。上述的Pivot算法选取面积最大的元素作为pivot,其动机是因为面积最大的元素通常最不好摆放,因此尽可能最先摆放,因此这种Pivot算法也叫做Pivot-by-size。Pivot算法能够大致保持元素的顺序。在生成的树图中,元素的顺序大体服从从左到右和从上到下递增的规律。Pivot算法的每一个递规过程都是将数据元素分成四个块来处理。当数据元素比较多的时候,这种递规确实能够保持较小的长宽比。但是当数据元素比较少,尤其是最后一步(数据元素的个数≤4)的时候,这种分块就显得太粗糙,以至于最后一步总是不能获得好的长宽比。Benshneiderman试图在最后一步采用其他策略布局,但是这样又会失去Pivot算法保持顺序和动态情况下稳定性好的优点。总的来说,Pivot算法在长宽比,动态稳定性和保持元素顺序三者间做了一个折衷,希望生成的树图获得比较小的长宽比,较好的顺序性和动态稳定性,虽然不管在哪个方面都不是最好的算法。然而算法试图在二维空间上找到一种quicksort算法的思想,却是非常具有启发性。1.4不平衡说的strap算法受正方化算法自适应思想的启发,BenShneiderman提出了一种Strip算法。Strip算法同样在长宽比,顺序和动态稳定性之间做了折衷,但是Strip算法比Pivot算法更为成功。Strip算法是正方化算法的一个变体,但使得长宽比、顺序性和动态稳定性最平衡。自适应的思想使得每一行的元素都不会有很大的长宽比;顺序排列和条形布局使得矩形非常符合元素原来的顺序,动态情况下整个布局的稳定性也很好。美中不足的地方是Strip算法最后一步的长宽比总是很差,因为通常最后一步剩下的显示空间非常细长。BenShneiderman虽然随后对最后一步进行了改进,最后一步的时候有选择的向倒数第二步回溯;然而终究只能细微改进,毕竟这是strip算法的一个秉性。2pivat算法Cushion算法可以优化生成树图的层次结构,但本身并不是一个完整的算法,必须和其他算法结合使用。更抽取了颜色中的一个要素:阴影来表示层次结构,导致Cushion算法生成的树图,不便以黑白程度表示数据元素的某个属性;正方化算法能够显著降低生成树图中矩形的平均长宽比,但打乱了元素顺序,当元素属性变化较明显时,不适合可视化动态数据;Pivot算法巧妙将快速排序算