数字层次数据集的平衡分区树图方法-虚拟现实智能硬件中的应用与评估

引文：冯聪，龚明伦，Oliver DEUSSEN。数字层次数据集的平衡分区树图方法。虚拟现实智能硬件，2022，4（4）：342虚拟现实智能硬件• 文章·2022年8月第4卷第4期：34210.1016/j.vrih.2021.09.006数字地理数据集Cong FENG1*，Minglun GONG2，OliverDEUSSEN31. 湘潭工学院统计信息系湖南湘潭411104;2. 加拿大纽芬兰纪念大学3. 德国康斯坦茨大学接收日期：2021年8月14日;修订日期：2021年8月21日;接受日期：2021年9月24日翻译后摘要：背景可视化的层次数据集的问题是一个重要的和有用的技术，在许多现实生活中的情况。文件夹系统、股票市场和其他与层次结构相关的数据集可以使用这种技术来更好地理解数据集的结构和动态变化传统的基于空间填充（正方形）的方法具有紧凑的空间使用和节点大小的优点，而不是基于网格的方法。基于空间填充的方法有两个主要的研究方向：静态和动态性能。方法本研究提出了一种基于平衡分区的树映射方法，该方法在一个变体中具有良好的纵横比，在另一个变体中具有良好的动态数据的时间一致性，并且在第三个变体中，在这两个方面之间具有令人满意的折衷为了布局树图，节点的所有子节点被分成两组，然后进一步划分，直到到达单个元素的组。在此之后，这些组被组合以形成代表父节点的矩形。对分层数据集的每一层执行该过程。对于分区的第一个变体，对子元素进行排序，并从大元素和小元素构建大小尽可能相等的两个这实现了令人满意的宽高比的rec-tangles，但不太这样的时间相干性（动态）。对于第二种变体，采用子序列，并从中创建大小尽可能相等的组，而不需要排序（基于序列，纵横比和时间一致性之间的良好折衷）。对于第三个变量，孩子们被分成两组，基数相等，不管他们的大小（数量平衡，纵横比差，但时间一致性好）。结果本研究评估了所采用方法的纵横比和动态稳定性，并提出了一种新的度量标准，该度量标准测量矩形在运动过程中的视觉差异，以表示随时间变化的输入。结论该研究表明，通过平衡分区的树映射方法优于一些现实世界的数据集的最先进的方法关键词：信息可视化;树映射;平衡划分*通讯作者：287956404@qq.com2096-5796/©版权所有2022北京中科学报出版有限公司Elsevier B. V.代表KeAi Communation Co. Ltd.提供的出版服务。这是CC BY-NC-ND许可证下的开放获取文章（http：//creativecommons.org/licenses/by/4.0/）。343Cong FENG，et al.一种数字层次数据集的平衡分区树图方法1介绍层次数据集的可视化技术有许多重要的应用。使用树结构可以更自然地表示层次结构，在树结构中，分支用于连接不同层次级别的数据当不同的叶节点具有不同的值时，树结构受到限制，因为它显示节点之间的因此，通常使用基于区域的方法，其中层次结构通过包含进行编码，并且值通过区域进行可视化。子节点的值之和定义层次结构中其父节点的值相应的基于区域的方法分为两类，即自顶向下和自底向上的方法。自顶向下方法首先创建一个区域作为根节点的表示，然后递归地将根节点的子节点排列到该区域中[1]，而自底向上方法首先利用布局算法将所有叶节点的表示排列到一个区域中，然后递归地将这些重新表示打包到更大的区域中，这取决于给定层次结构的输入[2]。矩形是在基于面积的方法中用于表示节点的最广泛使用的形状，其中矩形的面积基于矩形的树图方法创建了紧凑的结构，这些结构对于计算是有效的，并且易于阅读，使得它们在可视化层次数据集，特别是大型动态数据集方面很受欢迎假设层次结构的所有元素都是矩形，可以通过多种方式创建视觉上清晰的结构这些优点使得基于矩形的树图方法成为可视化分层数据集的流行工具。给定相同的数据集，有许多方法可以生成相应的矩形树图。两个因素对树图结果的质量有重要影响。一个是单个节点的可见性和纵横比，而另一个是动态稳定性。所提出的方法使用自上而下的方法改进了这两个因素。对于树图的每一层，我们将每个节点的子节点细分为两组，然后再细分，直到达到单个元素的组。在该算法的两个变体中，分组基于每个孩子的个体大小[3]）。两个组都由两个矩形表示，这两个矩形被布置成分割父亲矩形。由于递归除法在每一步都优化了纵横平衡划分问题是一个NP难问题，但存在几个近似其中之一是贪婪策略，其中元素可以根据它们的大小进行排序，并且两个bin交替填充，以便它们总是具有相似的大小。虽然这实现了良好的结果，但是两组之间的变化因此，本研究使用了另一种组分配策略，将所有大元素分组到一个组中，将所有小元素分组到另一个组中（大小平衡分割）。这为树图创建了令人满意的纵横比，并且在动态情况下，当元素的大小和相应的顺序随时间变化时，会产生不一致性因此，该研究开发了该方法的其他两种变体，以更好地保持时间一致性。最稳定的结果是，如果数据被分成两组相等的基数，无论元素的大小（数量平衡分裂）。当子序列未排序时，达到时间稳定性和纵横比之间的良好折衷，然后使用贪婪算法（序列平衡分裂）创建大小尽可能相等的两个组。为了评估树图的质量，这项研究使用了几个标准数据集以及一个变化极大的合成数据集。也使用这两种已建立的措施[4]对树图进行了数值分析344虚拟现实智能硬件八月（2022）卷。4条第4图1我们的树图依赖于平衡分区，非常容易实现。我们的大小平衡分区的一个实例（a）与其他方法相比显示出更好的纵横比，例如，（b）螺旋放置，（c）条带，（d）切片和切块。作为一种同时考虑矩形运动和形状变化的新方法评估表明，大小平衡的分裂（图1a）用非常简单的算法实现了出色的纵横比，而数量平衡的版本与最先进的解决方案一样稳定，在该领域更常用。该算法的序列平衡版本创建的树图在两个属性之间具有理想的组合，因此被推荐为通用树图的强有力的选择。因此，本文的贡献包括：• 大小平衡分区保持树图中矩形的近正方形长宽比，以便小元素具有更好的可读性。• 序列平衡分区在保持良好纵横比的同时更好地保持动态稳定性• 只关注元素数量的数量平衡分区对于高度时间动态的数据是最稳定的。• 关于视觉变化的新度量补充了现有的动态稳定性测量，其通常仅考虑距离和尺寸变化。如图2所示，给定属于相同层次级别的输入数据序列，执行数量平衡分区（图2a）确保子集中的节点数量平衡，并且时间相干性得到很好的保留。然而，由于这两个子集的总价值差异很大（8+9vs.1+2），相应的矩形具有较差的纵横比。对于大小平衡的划分问题（图2b），有一个贪婪搜索算法，它尽管第一级的两个子集在大小上完全平衡，但由于子集内的节点大小变化，第二级的拆分不能平衡。与贪婪策略一样，所提出的大小平衡分区（图2c）也根据输入节点的大小对其进行排序，然而，不是将节点交替分配给两个子集，而是将小节点保留在同一个子集中，从而减少子集内的大小变化这允许在所有层次级别上的平衡分区当需要保持输入序列中节点的顺序时，所提出的序列平衡分区（图2d）直接划分序列，而不试图在处理动态数据集时实现更好的时间一致性。本文的其余部分进行如下：回顾相关工作后，第3节在理论上证明了所提出的方法，并描述了一个有效的计算树图的替代方案，而第4节提出了新的质量测量树图的方法，提供了三个数据集的结果，并将它们与相关作品进行比较。第5节得出结论，并确定未来工作的潜在机会2相关作品Shneiderman[1]提出了第一个基于空间填充的方法来可视化分层数据集。这345Cong FENG，et al.一种数字层次数据集的平衡分区树图方法图 2不同划分方法的比较。方法通过交替地水平和垂直分割矩形，如果一个节点有很多子节点，那么会出现很多细矩形Bruls等人引入了方形化的树图，目的是为每个细分的矩形保持良好的长宽比[5]。该方法首先将子元素从大到小排序，然后将元素连续添加为矩形，每一步都优化纵横比如果矩形太细，填充顺序会改变，因此输入顺序会被破坏，并且对于随时间变化的输入，可能会发生大的重排。Bederson等人使用条带方法细化了平方化的树图，该方法保持了输入的顺序[6]。子元素以条带的顺序从上到下、从左到右排列Tu和Shen提出了一种基于螺旋的方法来在树映射过程中保持输入序列[7]。这两种方法都将元素线性排列，从而创建具有或大或小纵横比的矩形Duarte et al.提出了一种邻域保持方法来保持输入数据的相似性[8]。该方法涉及将输入数据布置在矩形中，然后在该矩形中绘制切片线，并随后通过缩放移动到保持其两个部分的比例的位置虽然这种方法能够很好地保留邻域，但它不提供序列保留或动态稳定的结果。Lu Fogarty提出了级联树图，使用元素的级联来可视化树图中的子依赖关系[9]。在显示层次结构和空间填充之间存在折衷当数据大小发生变化时，许多树图方法会显著改变其外观。Tak Cockburn提出了一个位置漂移度量来显示映射方法的动态稳定性，使用移动元素中心随时间的变化[10]。此度量对于比较树图中的局部和全局移动特别有用。作者还介绍了希尔伯特和摩尔曲线为基础的树图，可以用来获得空间稳定性。为可视化添加额外的空间是动态稳定性的关键这是由Itoh等人完成的[2]谁用矩形包装来安排346虚拟现实智能硬件八月（2022）卷。4条第4子元素以自顶向下的方式。Sondag等人提出了一种动态方法，该方法通过拉伸和翻转相邻矩形来更新序列中最后一个时间步的树图矩形[4]。该方案可以与不同的树图相结合，但可能被认为过于复杂，无法用于大规模数据集。更多基于矩形的树图方法可以在在线调查中找到[11]。除了矩形，还存在许多其他形式的树图Wang等人使用嵌套的圆来可视化分层数据，根据自上而下的顺序逐层包装圆[12]。Zhao等人使用连续打包方法来生成基于圆形的树图，并提出了一种基于鱼眼失真的交互式缩放技术[13]。Fischer等人将圆形树图归因于字形以可视化时间序列数据[14]。Balzer等人提出的Voronoi树图使用Lloyd虽然这种方法提供了比基于切片的方法更好的纵横比Görtler等人提出了使用气泡轮廓来包装圆的气泡树图，增加轮廓的透明度或锯齿度以可视化数据的不确定性，从而使其比圆形包装更紧凑[16]。Vernier等人提出了两个指标来比较不同树图方法的性能：第一个是将纵横比归一化为1，而第二个旨在矩形位置和形状随时间序列的变化[17]。Scheibel等人[18]对不同树图方法进行了最新的调查和分类。Li等人提出了一种条形码树图方法，该方法使用矩形条来显示分层数据集中的变化，其中每个条的宽度表示节点级别[19]。这种方法的一个优点是它可以同时可视化树结构中的几个变化最后，Scheibel等人使用了一个初始布局，数据集中的所有变化都映射到该布局上[19]。3方法该算法使用分层数据集作为输入，并生成相应的树图。首先，创建一个默认长宽比为1.25的矩形区域，以形成保存整个数据集的根节点，最高层次级别的数据元素被视为该节点的子节点。然后根矩形被分割成多个较小的矩形，每个子矩形对应一个矩形，之后根矩形的面积根据相应数据元素的值确定。当一个子矩形在分层数据集中包含多个数据元素时，它将在相同的条件下进一步拆分。递归拆分过程（图3）一直持续到每个矩形表示单个数据元素，这被称为叶矩形。下一节将解释如何将给定的父矩形拆分为子矩形，以及如何根据元素的大小、输入序列和序列中的输入位置将所有元素拆分为子组3.1给定节点给定一组属于同一父节点的数据元素，本研究的目的是找到一种适当且有效的方法将父矩形分割成子矩形，使得：（1）子矩形的并集填充父矩形;（2）没有两个子矩形相交;（3）每个子矩形的面积与相应数据元素的值成比例;以及（4）每个子矩形的形状尽可能接近正方形。为了实现这些目标，递归分区程序。集合L被分成两个子集，即L1和L2，每次之后父矩形被切割成两个子矩形，其面积与L1和L2中的值成比例。为了确保子矩形尽可能接近正方形，父矩形总是沿其短边剪切子集L1和L2的值也是平衡的，使得两个子矩形具有相似的面积。347Cong FENG，et al.一种数字层次数据集的平衡分区树图方法图3递归分割过程的一个例子：根矩形首先在（a）中按大洲分割，然后每个大洲在（b）中按国家分割。如前所述，将一个数字列表（元素的大小）分成两个子集，使得两个子集中的总值（元素大小之和）之间的差异最小化是计算中的一个众所周知的问题，称为平衡划分问题[3]。作为一个NP难问题，已经提出了几种算法来实现接近最优的解决方案[20]。这里通常使用的是简单贪婪算法，它将所有数字按降序排序，以便首先处理较大的数字，然后将下一个最大的数字分配给具有较小总值的子集。伪代码在算法1中给出。算法1平衡配分函数SPLIT（L）inti={i};intn={};当L！{}做int x=L. getString（）;remove（x）;如果sum（L1）sum（L2），则L1.append（x）;elseL2.append（x）;endifend whilereturnL1;L2; end函数虽然上述贪婪算法通常可以平衡两个子集的大小，但进一步划分每个子集通常会导致不平衡的子树（图2b），因为该算法倾向于将数据元素交替分配给两个子集，导致每个集合内的数据值之间的差异很大。假设给出了以下元素大小的序列：[2，15，20，21]。分割将这个列表分成两个列表：[20，21]和[2，21]，这会创建初始矩形的完美分割，但后续列表的两个分割很差。为了解决这个问题，该策略涉及将L分成子集，使得：（1）每个子集内的内部方差最小化，以及（2）L1和L2的总值尽可能接近实现这一目标的一个简单的启发式方法是将L1中的大元素和L2中的小元素分组，使得两个子集都具有348虚拟现实智能硬件八月（2022）卷。4条第4低内方差为了平衡L1和L2中的总值，初始化L1= 0和L2=L，之后L2中的下一个最大元素逐渐移动到L1，直到这样的移动增加了两个集合之间的总值差算法2中给出了这种分裂方法的伪代码算法2平衡配分函数SPLIT（L）h= sum（L）/2;inti={i};L2=L;int x=L2. getString（）;当（abs（sum（L1）-h）> abs（sum（L1+x）-h））时，l.append（x）;L2.remove（x）;int x=L2. getString（）;endwhilereturnL1;L2; end函数这种方法（图2c）在填充父矩形方面有几个优点：（1）计算效率高，存储占用量小，（2）易于实现，（3）与其他方法相比，如非切片和曲线分割方法[21]，它为所有子节点保持了类似的矩形结构。有关更多详细信息，请参见图4。应该注意的是，虽然使用了类似的思想来获得矩形的尽可能相等的分区，但这种方法不同于拆分大小方法[6]的枢轴。分割大小方法的目的是保持每个矩形内输入序列的顺序，因此涉及根据序列顺序对矩形的两个部分进行布局。与此相反，本研究所使用的方法递归地划分元素列表，直到部分仅由单个元素组成。对于每对子列表，相应的矩形被分成两部分，创建更接近正方形的长宽比，如下所示3.2序列平衡划分上面的分区算法主要是为树图中的所有元素创建近似正方形的形状。由于在拆分每个父节点时对元素进行排序，元素值的微小变化可能会因此，当可视化动态变化的数据集时，树图之间的时间一致性可能很差所提出的用于平衡分裂的方差最小化解决方案的一个特别优点是，它也适用于未排序的序列。即使两个子组之间的大小差异可能大于原始算法，该解决方案也可以获得两个近似相等的组，用于划分父矩形，从而产生序列平衡分区（图2d）。虽然纵横比可能更差，但元素的大小随时间变化，因此序列不会重新排序，并且可以保持时间稳定性。3.3数平衡划分只有当由于元素大小的变化而必须以不同的方式执行拆分时，树形图的结构才会发生变化。为了避免这种类型的结构变化，本研究提出了这种方法的第三种变体。在这里，每个父节点，没有排序，连续分为两组具有相等数量（基数）的元素。应该注意的是，这种数量平衡分区（图2a）的主要缺点是，它产生了更高的纵横比变化，从而导致可见性降低，349Cong FENG，et al.一种数字层次数据集的平衡分区树图方法图4贪婪算法（a）和大小平衡分区（b）的比较。在这项研究的结果中，叶节点2.88贪婪小矩形的美学外观。然而，该方法的最终优点在于，它产生完全动态稳定的树图结果，其中每个细分根据输入序列的数量确定，从而允许连续地确定所有元素的位置4评价和结果该方法在几个广泛使用的数据集上进行了测试，即Coffee，Name和Population，所有这些数据集都随时间而变化，但并不显著。因此，本研究涉及创建一个合成数据集，该数据集具有两级分层结构中的20帧上的200个元素。每个元素的大小从小于1到大于9000不等。图5显示了与方形化树图和增量方法相比的树图结果。使用两种措施对不同方法的质量进行评价。第一个涉及静态树图的矩形的可读性，通常使用平均值和中等纵横比来测量[4]。第二个问题涉及动态数据的不同方法的稳定性，其中测量子元素位置的变化以及大小的任何变化。使用还测量元件形状变化的方法来修正该测量4.1静态质量树形图的矩形元素的可读性使用它们的平均和中值纵横比来测量。对于具有n个子元素的父元素，其中每个子元素的纵横比表示为ar1，ar2，…,用于测量平均纵横比的替代方案如下：如果每个子矩形的大小为w1，w2，…,以下加权和：加权平均纵横比具有减少具有大纵横比的极小元素的贡献的优点。在下文中，加权平均纵横比保持未使用，因为具有大纵横比的小元素经常干扰树形图的外观，从而妨碍内容的可读性。因此，应将小物体判断为大物体，或者也可以在大元素和小元素之间加上一个加权项。如果从不同的数据集或从动态变化的单个集给出几个树形图，则可以通过计算其平均值和中值来进一步处理纵横这些平均纵横比被称为平均平均纵横比和平均中值纵横比。350虚拟现实智能硬件八月（2022）卷。4条第4图5合成数据集的三个时间步长：（a）数字平衡方法的结果，（b）平方树图，（c）增量树图。具有相同父根的矩形共享相同的颜色。4.2动态质量分层数据集可以随时间变化。例如，在文件中，可能会修改、添加或删除系统文件。为了获得反映这种动态集合的树形图可视化，可以为每个时间步构建树形图，但这通常会导致不连贯的可视化。另一种可能性是为每个时间步更新初始树图（增量设计）。这两种方法都已经过去了，我们将比较我们的方法，属于第一类，与这两种最先进的方法距离变化[22]是Shneiderman和Wattenberg首次提出的一种技术，通过测量矩形的位置和大小随时间的变化来评估动态数据集的树图方法的距离变化的方差也可用于测量距离平均变化周围的稳定性。一些方法实现了位置漂移度量[10]，其关注整个时间段内的位置变化，而不仅仅是两个时间步长之间的位置变化分割矩形中仅在局部区域内移动的元素的位置漂移值应低于全局移动的矩形Sondag等人[4]使用351Cong FENG，et al.一种数字层次数据集的平衡分区树图方法一个动态的指标。他们声称，在动态数据集中，树图方法的稳定性取决于分割矩形的邻居如果一个分割的矩形在不同的时间步长显著移动，但它的邻居保持稳定，则该矩形将获得低稳定性值。从感知的角度来看，这两个指标都是有意义的。在现实生活中，层次结构中的数据集可以被视为一个类似序列的系统，正是由于这个原因，可读性[6]在这里被提出作为树映射结果的顺序的度量。可读性度量计算对应于输入序列的读者的眼睛扫描方向的所需改变的数量。为了优化这一点，在[6]和[7]中分别提出了基于条带和螺旋的树图布局方法。这些指标在某种程度上是有用的，但不幸的是，不能完全捕获树图的动态稳定性。例如，这些指标都关注距离变化，但忽略了形状随时间的变化对于动态数据集，两个矩形之间的变化不仅依赖于其位置差异，还依赖于其视觉变化。两个矩形之间的视觉变化如下面的图6所示两个矩形以相同的中心对齐，之后它们的面积之间的差异被计算为虚线。使用以下公式计算：视觉变化=s1+s2+s3+s40（1）图6两个矩形之间的视觉变化是通过它们的面积（虚线）之间的差异来测量的为了获得完整树图的值，其元素的视觉变化通过数据集大小的变化进行归一化不考虑两个时间步的变化的绝对大小，但是，累积每个叶节点因此，该研究提出了如下方法来衡量树映射方法的稳定性：给定一个具有n个元素的分层数据集，我们指定分层数据集在两个时间步长中的变化量，并根据叶节点的累积变化将这些变化例如，在距离变化度量中，我们将距离变化度量归一化如下：其中i和i+1是两个相继的时间步长，并且size（j）表示树图中第j个矩形的大小。这种规范化背后的原因是，树图中的变化紧密跟随数据集中的变化。在这项研究中，中心移动和视觉变化被用来评估树图方法的稳定性的动态数据集。两个度量都通过输入数据的大小进行归一化（参见等式（2））。4.3结果在所有直方图中，视觉变化和中心移动的较低值是优选的。对于1至1.5的纵横比，优选。使用Coffee和Name数据集的结果如[4]所示。使用这两个数据集测试了11种树映射方法。还测试了从互联网下载的人口数据集。咖啡数据集包含85个国家，从1994年到2014年的咖啡进口量，咖啡数据集的层次结构分为三个级别。国家被视为叶节点，并被分为对照组。352虚拟现实智能硬件八月（2022）卷。4条第4北美、西欧和东亚等地。最高层次包括美洲、欧洲和亚洲。名称数据集包含1993年至2015年荷兰的62个流行名称。该数据集只有一个级别，名称之间的差异小于Coffee数据集中的差异。人口数据集包括1980年至2010年的 200多个国家，并呈现两层。顶层是区域层，其中包含亚洲大洋洲、欧洲、北美、中美洲和南美洲、中东和非洲，而下层包含所有国家。虽然这不是一个深度层次数据集，但在某些时间步长中会出现新元素，这对于动态考虑非常有用所提出的方法进行了测试，使用上述静态和动态指标，并与上述现有的方法进行比较。更具体地，平均和中值纵横比被用作静态度量，并且平均中心移动和平均视觉变化被用作动态度量。平均中心移动和平均视觉变化通过分层数据集大小的全局变化进行归一化。对于Coffee数据集，不同方法的纵横比（图7a）变化很大。尺寸平衡的方法比大多数其他方法得到更好的结果，平均中值纵横比优于所有其他方法。序列平衡方法具有比现有方法更好的平均中值纵横比，平均纵横比也优于Moore、Spiral、Pivot、Slice和Dice。数字平衡方法对于平均纵横比没有很好地工作，但是，它对于中值纵横比呈现出良好的性能。对于咖啡数据集，不同国家之间的差异很大。因此，许多方法具有大的平均纵横比，例如大于100。对于这个具有挑战性的数据集，所提出的方法提供了良好的静态测量。图7b显示了咖啡数据集的动态度量结果大小平衡和序列平衡的对于平均视觉变化，切片和骰子技术表现出最好的稳定性。顺序平衡法的值仅略高于增量法，且高于切片法和切片法。因此，序列平衡方法为咖啡数据集提供了良好的动态稳定性大小平衡方法的平均视觉变化值在所有这些方法中居中，大小平衡方法与更好方法之间的差异小于1 E-07。因此，该方法在视觉变化方面也表现良好。数字平衡方法在动态特性方面表现良好，呈现出最好的平均视觉变化，其平均中心移动仅高于大小平衡，序列平衡和切片和骰子方法。与其他方法相比的结果可以在图8中看到。对于咖啡数据集，这些方法在可视化和稳定性方面都表现良好，因为可以看到许多小矩形，并且可以在数据集中轻松跟踪动态变化对于图7c中的Name数据集，除了螺旋和切片和骰子之外，所有方法（包括所提出的方法）都呈现出良好的静态稳定性。大小平衡和序列平衡方法的值约为1.5，这与增量、Hibert、Moore、大小枢轴、简化和条带方法具有竞争力数字平衡方法在数据集中也表现良好，平均和中值纵横比约为1.8。许多方法在这个数据集上表现良好，因为它们只有一个级别，元素之间的差异很小。对于图7d中更动态的名称数据集，Slice和Dice仍然是所有方法中最好的动态稳定性。大小平衡和顺序平衡的方法有更高的价值，在平均中心移动比增量和切片和骰子树图，并与螺旋和枢轴中间的方法。这些方法在平均视觉变化方面并不比其他方法表现得更好，然而，数字平衡方法在平均中心移动和353Cong FENG，et al.一种数字层次数据集的平衡分区树图方法图7本研究计算了三个数据集（咖啡，姓名，人口）的平均平均长宽比和平均中位数长宽比，如左图所示，以及它们的平均中心移动和视觉变化，如右图所示平均视觉变化，结果值仅略高于切片和骰子方法。三个连续时间步长的该组结果如图10所示。数量平衡和序列平衡的方法被发现有很好的保存序列对于Population数据集，所提出的方法提供了理想的纵横比，如图7e所示，除了增量和近似方法之外，其性能优于所有其他方法。虽然尺寸平衡的方法呈现出比这两种方法略高的平均平均纵横比，但它也呈现出比这两种方法低的平均纵横比。354虚拟现实智能硬件八月（2022）卷。4条第4图8Coffee数据集的可视化结果。将方法（a-c）与Moore（d）、切片和骰子（e）、平方化（f）、按大小透视（g）、按分割大小透视（h）和Hibert（i）方法进行比较。具有相同父根的叶节点共享相同的颜色。平均中值纵横比。基于序列的方法也呈现出比增量和近似方法更高的平均平均纵横比，但平均中值纵横比结果相当。数字平衡方法没有得到令人满意的结果的纵横比。平均平均纵横比优于使用“中间”、“平方”和“切片和骰子”的枢轴，平均中值纵横比优于“切片和骰子”。另一个有趣的观察是，简化的树图方法没有给出令人满意的平均长宽比，理想情况下应该大于2000。这是因为平均长宽比很容易受到非常薄的元素的影响，并且方形化的树图包含非常薄的矩形。图7f中示出了动态比较，显示了尺寸平衡和序列平衡方法的良好中心移动结果，然而，所提出的方法的平均中心移动仅高于增量和切片和切块方法的平均中心移动基于序列的方法的视觉变化高于增量、条带、切片和骰子树图，并且基于大小的方法的视觉变化在所有方法的中间数字平衡法对动态355Cong FENG，et al.一种数字层次数据集的平衡分区树图方法图9Population数据集的可视化结果。将大小平衡方法（a）与螺旋（b）、条带（c）、方形化（d）、切片和骰子（e）以及中间轴（f）方法进行比较。具有相同父根的叶节点共享相同的颜色。属性，与Incremental和Slice and Dice方法竞争此外，该研究还在图9中显示了大小平衡的树图，与螺旋，条带，方形化，切片和模具以及中间枢轴相比。其他方法的结果使用Sondag等人提供的软件获得。[4]的文件。应该注意的是，局部移动方法[4]旨在通过使用其他树映射方法进行初始化来解决动态稳定性问题，并形成近似方法。在处理一个简单的数据集，如名称数据集，所提出的方法和本地移动方法执行类似的纵横比，但是，所提出的方法被发现更好地保留序列。对于复杂的数据集，局部移动方法有时会失败，效率很低。图5和图10将与所提出的方法相关的结果与局部移动的结果进行了视觉比较，表明获得了相似的纵横比结果，但是序列平衡和数量平衡的变体表现出更好的序列和动态稳定性的保持最后，不同算法的计算性能在表1中报告，其中时间以毫秒为单位测量。结果清楚地表明，所提出的算法的所有三个变种可以产生令人满意的结果比大多数现有的方法更快。5讨论和结论从摘要中讨论的问题来看，本研究旨在获得更好的小元素可见性能，并实现动态稳定的结果，从而使输入数据集在树图的相对稳定位置可视化。然而，令人满意的静态和动态性能可能难以同时实现在一个树映射方法，正是由于这个原因，研究把这两个方向到一个框架。在框架中，我们有三个子分支：一个是具有良好静态356虚拟现实智能硬件八月（2022）卷。4条第4图10Name数据集连续三年的可视化结果（1993 - 1995）。将所提出的方法（a-c）与增量（d）方法进行比较。较浅的灰色表示较早的输入，而较深的灰色表示较晚的输入。一种是动态性能好，动态性能差;一种是动态稳定性能好，但所有小元件难以可视化;一种是静态和稳定动态性能介于前两者之间这项研究提出了有效的树图策略，要么保持近正方形的长宽比的矩形树图，使小元素更明显，或创建稳定的布局随时间变化的序列（股票市场随时间的变化），而这两个方面可以加权的影响。357Cong FENG，et al.一种数字层次数据集的平衡分区树图方法表 1不同方法方法时间方法时间方法时间大小顺序7.8序列顺序20号顺序3.5切片和骰子7.2中间轴25按大小28拆分轴22地带22平方化30螺旋23沼地25Hilbert38近似78增量75因此，设计了三种用于安排结果的替代方案：大小平衡的可视化保持近正方形的长宽比，并且数量平衡的版本保持时间一致性。一个介于两者之间的是由一个序列平衡的划分方法形成的，它合理地保持了这两个方面为了更好地进行比较和评估，该研究引入了一个基于视觉变化定义的新指标。它补充了现有的动态稳定性测量，通常只考虑距离和大小的变化。除了绝对距离和大小变化之外，该度量还反映形状变化。通过比较和讨论各种方法，除了其他已建立的措施，使用该措施，该研究提出了行为的树映射结果相对于标准数据集。在未来，建议研究继续尽量减少差异和保持时间的连贯性。使用非切片方法划分矩形也是一个有趣的探索方向。对于数量平衡的分区方法，我们可以将层次聚类和布局方法结合起来，而不是尽可能接近两此外，对于数字孪生，本文提出的方法可以用于分层数据集布局和可视化，这可以帮助数字孪生管道。竞合利益我们声明我们没有利益冲突引用1 施奈德曼湾用树图可视化树。ACM图形学报，1992，11（1）：922 李文，李文.使用快速矩形填充算法的分层数据可视化IEEETransactions onVisualizationand Computer Graphics，2004，10（3）：302DOI：10.1109/tvcg.2004.12727293 Wikipedia：分割问题https://en.wikipedia.org/wiki/Partition问题4 放大图片作者：J.通过本地移动稳定的树图IEEETransactions on Visualization and Computer Graphics，2018，24（1）：729DOI：10.1109/tvcg.2017.27451405 Treemaps S，Bruls M，Huizing K，Wijk J.方形树图。20006 放大图片作者：J.有序和量子树图。ACM图形学报，2002，21（4）：8337 涂毅，沈华伟.使用树形图可视化层次数据的变化。IEEE Transactions on Visualization and Computer Graphics，2007，13（6）：1286DOI：10.1109/tvcg.2007.705298 Duarte F S L G，Sikansi F，Fatore F M，Fadel S G，Paulovich F V. Nmap：a novel neighborhood preservation space filling algorithm.IEEETransactionson Visualization and Computer Graphics，2014，20（12）：2063DOI：10.1109/tvcg.2014.23462769 Lü H，Fogarty J.级联树图：检查树图中结构的可见性和稳定性。在：Proceedings of Graphics Interface 2008中。温莎，安大略省，加拿大，加拿大信息处理协会，2008年，25910 作者：Tak S，Cockburn A使用Hilbert和Moore树图增强空间稳定性。IEEE Transactions on Visualization and ComputerGraphics，2013，19（1）：141DOI：10.1109/tvcg.2012.10811 施奈德曼湾空间限制层次可视化的树图，包括马里兰大学树图研究的历史。199212 王文新，王宏，戴国智，王宏.用圆填充实现大型层次数据的可视化在：会议记录的SIGCHI358虚拟现实智能硬件八月（2022）卷。4条第4计算机系统中的人为因素会议。蒙特利尔魁北克加拿大，纽约，纽约，美国，ACM，2006，517-520 DOI：10.1145/1124772.112485113 赵洪生，林林.分层数据交互式可视化的变分环形树图。2015年IEEE太平洋可视化研讨会（PacificVis）。杭州，中国，IEEE，2015，81DOI：10.1109/pacificvis.2015.715636014 放大图片作者：J. ClockMap：使用时间字形增强时间序列数据的圆形树图。在：欧洲图形可视化会议。201215 放大图片作者：Balzer M. Voronoi树图在：IEEE信息可视化研讨会，2005。INFOVIS 2005年。Minneapolis，MN，USA，IEEE，2005，49DOI：10.1109/infvis.2005.153212816 放大图片作者：Görtler J，Schulz C，Weiskopf D，Deussen O.用于不确定性可视化的气泡树图。IEEE Transactions onVisualization andComputer Graphics，2018，24（1）：719DOI：10.1109/tvcg.2017.274395917 张文龙，张文龙.时间相关树图的定量比较。计算机图形学论坛，2020，39（3）：393DOI：10.1111/cgf.1398918 Scheibel W，Weyand C，Döllner J. EvoCells-a treemap layout algorithm for evolving tree data.第九届信息可视化理论与应用国际会议（IVAPP）201819 李刚，张勇，董勇，梁军，张军，王军，麦古芬，袁旭.BarcodeTree：多个层次结构的可伸缩比较IEEETransactionsonVisualization and Computer Graphics，2020，26（1）：1022DOI：10.1109/tvcg.2019.293453520 Korf R E.多路号码划分。第21届国际人工智能联合会议论文集。Pasadena，California，USA，2009，53821 Scheibel W，Trapp M，Limberger D，Döllner J. A taxonomy of treemap visualization techniques.第15届计算机视觉、成像和计算机图形理论与应用国际联合会议论文集。瓦莱塔，马耳他，科学技术出版物，2020DOI：10.5220/000915390273028022 作者：Shneiderman B.有序的树图布局。在：IEEE信息可视化研讨会，2001。INFOVIS 2001。SanDiego，CA，USA，IEEE，2001，73DOI：10.1109/infvis.2001.963283