面向拓扑感知的层次结构信息可视探索方法

谭博友，韩永国，王桂娟，赵韦鑫，周 锐，蔡梦杰，吴亚东

(1.西南科技大学 计算机科学与技术学院，四川 绵阳 621000；
2.四川轻化工大学 计算科学与工程学院，四川 自贡 643000)

层次结构数据不仅常见于文件系统、动植物分类、系谱图等领域，还能将复杂领域通过层次结构的形式进行简化表示[1]。层次数据的拓扑结构，能直观地反映某一事物的分类特征，帮助数据分析人员探寻结构信息并理解层次数据的分类模式等。因此，探索层次数据的拓扑结构信息是层次数据分析的一项重要环节。

通过可视化的方式探索层次数据比较常见。现有的层次数据可视化技术主要分为连接式、空间填充和混合式[2]。层次拓扑结构的绘制技术通常基于Reingold和Tilford`s[3]算法，利用模块化方法来定位节点，其中子节点位于父节点下方(自上而下的方向)，或者位于右侧(从左向右的方向)。由于显示空间的限制，原始的经典布局主要在一维上扩展，降低了层次结构数据可视探索的实用性，同时伴随节点数的增多也带来了节点遮蔽和分支拥挤等情况。为了克服上述限制，各种交互技术应运而生，例如缩放、鱼眼视图和一维扭曲。流行的交互式可视化方法则通过显示感兴趣的子结构同时缩小其他子结构来提供焦点+上下文视图。如SpaceTree和DOITree。此外，视觉线索提供有关隐藏分支内容的持续信息，并以平滑的动画显示节点何时被聚焦或缩小。对隐藏分支使用视觉编码提示在探索大型层次结构方面已经证明是有效的[4-5]。但在寻找目标子结构或相似子结构时，需频繁地点击视觉提示展开隐藏的分支，这将浪费用户大量的时间，同时对用户的瞬时记忆也带来了挑战。对于采用兴趣度进行分支隐藏的方法，需要用户指定各节点的初始兴趣度，这对于用户来说具有一定的挑战性。若节点未指定兴趣度，如何确定那些分支应该隐藏并确保未隐藏的分支能为用户呈现更多的结构信息，降低用户在探索的过程中频繁点击的隐藏分支的时间消耗也具有挑战性。

基于以上问题，该文提出了一个面向拓扑感知的层次结构信息探索框架。该框架通过评估重要节点来解决无兴趣度标记时分支隐藏的问题并保留更多的结构信息。通过提取关键子结构对整体层次结构进行概要，同时引入图嵌入算法对结构进行向量化来提高用户探索子结构和相似子结构的效率。最后，基于该框架实现了一个交互式的可视探索系统,通过案例分析和用户实验来验证该方法的有效性。

层次结构信息计算主要由三大模块组成，分别为重要节点评估模块、关键子结构提取模块、相似子结构提取模块。

1.1 重要节点评估

为解决在无兴趣度标记的层次结构数据分支隐藏的问题，该文引入网络分析领域中提取重要节点的分析方法，对层次数据中的重要节点进行提取。在对网络中的节点进行重要节点评估的算法中，常采用度指标、接近度指标和介数指标。其中接近度指标和介数指标都需要计算各节点之间的最短路径，但层次结构数据大多都只有一个根节点，大多路径都将通过根节点，这将影响算法的计算结果，因此接近度指标和介数指标不适用层次结构的节点重要性评估。度指标则采用计算节点的度值来确定节点的重要性。除度指标以外，张玫等[6]提出的合度评估算法以及DN(delete node based on both degree)评估算法均围绕节点的度值进行评估，为确定最佳的评估算法，依次对上述算法进行实验，结果如图1所示。从图中可以看出，在保证没有节点遮蔽以及分支拥挤的情况下，DN算法的结果保留了更多的节点、分支结构和深度信息。

A:原始布局 B:度指标评估算法结果 C:合度算法结果 D:DN算法结果

通过以上实验结果，该文采用DN评估算法来对层次数据的节点的重要性进行评估。由于不同数据的节点数量不一样，其所要收缩隐藏的节点数是不确定的，因此，在实际应用中基于DN算法进行了扩展。以此适应不同的节点数量的层次数据。其算法主要流程为:

Step1：根据DN算法计算各节点重要度;

Step2：根据重要度排序,取Top-k节点,k默认取10;

Step3：将这些重要节点及其子节点进行隐藏，保存这些重要节点；

Step4：通过布局算法计算各节点位置;

Step5：当前兄弟节点之间圆心距离减去一个直径后是否小于阈值n,是则将当前绘制出的所有节点重复Step1～Step4;

Step6：输出重要节点序列。

流程中的布局算法主要指基于节点连接方法的正交布局和径向布局两种，空间填充和混合式涉及的布局算法并不适用于该文。文中食物分类数据为实验数据，通过调节阈值n来对比两种算法对于重要节点数量的影响。实验结果显示，在相同的阈值n下径向布局算法提取的重要节点数量少于正交布局，且伴随n的增长，径向布局的效果越明显。采用正交布局时，其对于层次结构的分层效果展示更加直观，径向布局的直观效果没有正交布局那么好。因此，如果考虑隐藏更少的重要节点，建议采用径向布局；
如果追求更好的层次分明可视化效果，建议采用正交布局。

1.2 关键子结构提取

Ben Shneiderman曾提出“Overview first, zoom and filter, then detail on demand”的标准分析流程[7]。该流程指出在可视分析中概览属于第一步。因此，要更好地对层次数据的拓扑结构进行探索分析，需提供关于结构的概览。基于TF-IDF算法提取文本关键词的思想，该文通过提取关键子结构来高度概括整体层次结构。

在提取关键子结构之前，首先要解决子结构的定义问题，定义一种类似于文本中的词的子结构，这样才能更好地提取关键子结构。

在层次结构中，其最小单元为节点，但一个节点并不能算是一个拓扑结构，一个拓扑结构至少应包含边。因此，定义的子结构应由节点和边组成。在层次结构中，由边和节点组成的最小单元为父子节点连接而成的结构。因此，为便于对整个层次结构进行分解，对子结构定义如下：非叶子节点和其直接相连的节点构成一个子结构(如图2中A区域所示)。

由于TF-IDF算法由词频TF和逆文档频率指数IDF两部分组成，因此要提取关键子结构，首先需计算TF和IDF值。计算TF值相当于计算子结构的频率。由于文本中计算IDF时通常需要文档库，因此计算层次结构的IDF时也需要类似于文档库的东西。但是层次结构数据往往是一个整体，如果直接将整体作为一个文档计算IDF将得到0值。因此，在计算IDF值时应定义层次结构的文档库。

该文采用以下方法定义层次结构的文档库。首先，假设根节点直接相连的节点有多个，这时删除根节点，可得到多个如图2中B区域A、B、C所示的子结构。将图2B区域A、B、C这样的子结构单独作为一个层次结构数据，那么A、B、C就可以构成当前层次结构的文档库。

根据以上定义，列出如下TF和IDF计算公式:

(1)

(2)

公式(1)中，Cij表示子结构i在结构文档j中出现的次数，分母表示结构文档j中k个子结构出现次数和。公式(2)中，T表示结构文档总数,分母表示j结构文档中子结构i出现在所有结构文档中的次数。tfij与idfi的乘积代表j结构文档中i子结构的tf-idf值。然后将各结构文档中的各子结构的tf-idf值进行降序排序，取前n个作为该结构文档中的关键子结构。最后将所有结构文档的关键子结构进行汇总去重后，剩余的子结构作为整个层次结构的关键子结构。

1.3 相似子结构提取

相似子结构是对整体结构的一种过滤，能帮助用户快速定位与用户焦点子结构相似的结构特征。

相似子结构的匹配实际为对相似子图挖掘。现有的许多工作总结了近年来的子图挖掘相关算法，如VF2plus[8]、VF3[9]等。这些算法虽然能够得到完全匹配的子图，但在匹配的过程中存在会匹配大量不符合的结构导致大量的运算时间消耗。

笔者希望用户在使用该可视探索系统时能在较短的交互时间内获取结果，若采用VF3等算法，将导致在探索的过程中浪费用户大量的时间而影响交互体验。潘嘉铖[10]和李珍[11]等人的研究表明，通过表示学习将网络中的节点进行向量化，能减少无关的子结构的匹配次数，极大地提高相似子结构的提取效率，同时生成的节点向量更能体现“邻居紧密性”。因此，该文采用表示学习的方法对层次结构的节点进行向量化。

采用GraphWave[12]算法对层次结构进行向量化。所需提取的相似子结构存在于整个结构的不同位置，只需局部结构特征具有相似性即可。GraphWave算法已被证明能很好地提取图中局部特征相似的结构。

为保证提取出来的相似子结构的准确性，采取以下步骤提取相似子结构：

Step1：对向量化后的节点使用高斯混合聚类模型进行聚类，目的是将相似的节点聚集到同一类簇，在相同聚类簇中的节点所构成的子结构的相似性也更接近。

Step2：将用户当前所选子结构的节点向量所属的所有聚类簇中的所有节点作为相似子结构匹配候选集。

Step3：剔除用户所选子结构上的节点，在剩余的节点集中构建子结构集合。由于构建出的子结构存在其节点数量远小于或者远大于用户所选子结构节点数量的问题，因此将该部分结构删除，得到候选的相似子结构集合。

Step4：采用Weisfeiler-Lehman图核[13]对候选相似子结构集合中的子结构分别与用户所选的子结构进行相似度分数计算，相似度分数越高的子结构其相似度越高。按相似度分数降序排序，取前k(默认k=6)个相似子结构呈现在相似子结构查看面板中。

为证明文中相似子结构提取算法的效率，与VF3算法在食物分类数据(总共463个节点)上进行了对比，通过测试的数据显示，VF3算法的平均时间在15到20秒之间，而文中算法平均在5秒内就能返回结果。因此，采用图表示学习将节点向量化后，对相似子结构的效率是有所提升的。

为便于用户交互式地探索层次数据的拓扑结构，基于层次结构探索框架开发了原型系统，系统界面如图3所示。系统主要分为三个模块:(1)数据概览模块(A1、A2、A3)；
(2)主视图模块(B1、B3)；
(3)相似子结构探索模块(C1、C2、C3、C4)。

2.1 数据概览模块

数据概览模块主要目的是为用户提供层次数据的概览。其主要由向量聚类投影视图(A1)、节点统计概览视图(A2)、度分布概览视图(A3)组成。

由于GraphWave算法生成的节点向量为高维向量，难以直接可视化呈现。为便于用户更直观地探索相似子结构和对节点的整体特征进行概览，首先使用高斯混合模型将节点向量聚类得到各节点的聚类标签，然后通过T-SNE将各节点高维向量投影到二维平面，最后基于聚类标签对投影平面中的各节点进行颜色编码。在向量聚类投影视图中用户可通过点击不同颜色的点，以查看相同颜色编码的节点在节点连接视图中的分布情况。

由于主视图只是对层次结构的呈现，对于如节点度值分布等信息无法很好地体现。因此,设计了两个统计性的数据概览视图帮助用户更好地了解数据的拓扑结构信息。以堆叠柱状图(A2)的方式显示了当前系统所探索的层次结构数据在总体上的层数、每层节点的数量、叶节点和非叶子节点在各层之间的占比。同时,通过气泡图(A3)的形式来呈现每层节点的度值统计情况,气泡的大小为度值相同的节点数量。这能帮助用户直观地了解当前探索的层次数据各层节点孩子节点数的分布情况。

2.2 主视图模块

主视图中的节点连接视图(B1)为用户探索层次结构数据结构信息的主要视图，在该视图中，结合了节点重要性评估算法的评估结果，将对布局质量影响较大的节点进行隐藏。在其父节点处进行视觉编码(B2)以提示用户该节点处存在隐藏的节点及其子结构。椭圆的短轴表示其隐藏的子结构的深度，长轴表示隐藏子结构所包含的节点数量。用户可以通过点击椭圆节点，展开隐藏的结构。主视图模块中的关键子结构如图3 B3所示。用户可以通过点击相关子结构，在节点连接视图中将高亮显示与关键子结构匹配的结构，若隐藏的结构中包含与关键子结构相匹配的结构,其对应的视觉提示也将高亮显示。

2.3 相似结构探索模块

相似结构探索模块主要由用户焦点结构(C2)、相似子结构(C3)、结构探索历史(C4)组成。

用户焦点结构为用户当前点击的关键子结构或框选的子结构。相似子结构部分呈现相似子结构匹配算法所提取的top-k个相似子结构。结构探索历史则将用户探索过的子结构相关信息进行保存，通过走马灯效果来回切换用户探索过的历史子结构。通过这样的方式保证用户能够及时切换前后关注的结构，从而对不同的子结构进行对比分析等。

同时，为便于用户更好地探索数据，设计了如图3 C1所示的控制面板。用户可以通过控制面板来控制主视图是否采用重要节点评估算法显示优化布局或者原始布局，这可帮助用户对比采用重要节点算法前后差异。对于布局方式可选择采用正交布局或者径向布局。除此之外，用户可使用框选工具在节点连接视图中框选感兴趣的子结构。

为验证该方法在对层次数据结构信息进行探索的有效性，采用用户评估以及案例研究来进行证明。

3.1 用户评估

实验目的：在文献[4]的研究中，证明了采用视觉提示的方式对于用户探索具有良好的帮助。但未说明是否只需部分的子结构采用视觉提示，就能加快数据探索。为证明所采用的节点重要性评估方法的有效性，将与文献[4]的Tree Cues方法进行用户对照实验。同时，为验证所提方法对于寻找相似子结构在精确度、完成时间上的有效性，将与文献[14]的BarcodeTree方法进行用户对照实验。

实验设计：用户对照实验方法参考文献[4,14]的方法进行展开。在实验之前，招募了48位志愿者，这些志愿者的年龄分布为20到30岁。为避免志愿者在完成不同实验过程中对数据产生了一定的熟悉度，将这48位志愿者分成两组来进行规避。第一组志愿者完成文中方法与Tree Cues的对照实验A，第二组完成文中方法与文献[14]的用户对照实验B。对照实验A设计主要针对节点级别上的探索，其实验内容参考文献[4]中的实验任务进行设计，以此保证在实验任务上的一致性。其任务详细设计为：TA1 标识层次结构中第二层(根节点为第一层)直接子节点数量10以内的节点。TA2 标识层次结构中第三层中直接子节点最多的节点。TA3 标识层次结构中第二层和第三层各10个直接子节点数量超过10个的节点。TA4 标识第三层的所有叶节点。

对照实验B的实验任务设计以子结构为主，其任务详细设计为：TB1 标识指定子结构在第二层和第五层的位置及数量。TB2 标识指定子结构，在第二层及第四层最相似的子结构。TB3 标识指定子结构，在第二层及第四层最相似的10个子结构

实验过程：对于对照实验A和B，进行重复方差分析，将a设置为0.05。实验A共进行576次,实验B共进行432次。在重复实验过程中，为避免用户对实验数据的熟悉程度产生依赖，每隔三到四天做一次实验，同时将对数据中每一层节点的位置在该层进行打乱布局顺序，进行重排。实验A中的每项任务都能获取准确值。因此，对于实验A，只收集用户的完成时间。由于实验B中涉及寻找相似子结构，用户在寻找过程中是会存在错误情况的。因此在对照实验B中收集完成时间和错误率。

实验结果：图4显示了对照实验A完成实验的平均完成时间。表1中显示了各项任务完成时间的显著性检验结果。从表1的结果显示可知，在任务TA1、TA2、TA3的完成时间上，文中方法与文献[4]的方法具有显著性差异，说明在这三类任务的完成时间上文中方法是优于Tree Cues的。但对于类似任务TA4这种直接寻找叶节点，不需要其他额外的交互操作，两种方法在完成时间上并没有大的差异，也不具有显著性差异。这表明，文中采用的基于节点重要性对部分子结构采用视觉提示的方式，对于执行类似TA1、TA2、TA3这些任务时相比于Tree Cues中只采用视觉提示的方法在完成时间上具有一定的优势。

对照实验B中采用文中方法与文献[14]中方法完成各项任务的时间和错误率，如图4所示。表1显示对照实验B中各项任务完成时间和错误率的显著性检验结果。从表1可知，在对照实验B中，完成时间上文中方法与文献[14]中的方法具有显著性差异。在任务错误率上，文中方法与文献[14]中的方法在TB1任务上不具有显著性差异，在TB2和TB3任务上具有显著性差异。该结果表明，文中方法在完成类似实验B中的任务时，在完成时间上相对于文献[14]中的方法更为高效。在完成任务错误率上的表现除TB1外具有显著差异。从对照实验B的结果可以得出，文中方法与文献[14]中的方法在精确度和完成时间总体上具有一定的优势。

表1 对照实验

3.2 案例分析

该文设计了两个案例来说明该方法对于探索大型层次数据的有效性。

两个案例所使用的数据分别来源于中国政府统计网2021年成都市统计用区划和城乡划分代码和食安通网站上的农药残留限量数据。区划和城乡划分代码数据集是一个典型的层次数据集，详细反映了一个区域的行政层级划分情况。农药残留限量数据收集了19版和14版的数据。两个版本的层级划分都是以各类食物的类别进行详细划分，如水果类、蔬菜类等。

在两项案例分析中，分别招募了一位对案例分析数据陌生的志愿者参与案例研究中，避免志愿者的先验知识对实验产生影响。

案例一:以成都市的区划分代码数据为例进行案例分析。证明该系统能帮助用户通过交互式的方式从未知的大型层次数据中获取见解。

在对相似子结构进行探索的过程中，发现成都市的锦江区(图5A)、成华区(图5B)和青羊区(图5C)的区划分的局部结构特征最为相似。同时这三个子结构的向量投影聚类结果也属于同一类簇。通过图5中显示可知，这三个区的子结构中大多由4到8个节点构成。通过这一现象说明这三个区的区划分具有一定的规律。查阅相关资料显示，这三个城区都为成都市的中心城区中的第一圈层。这从侧面反映了这三城区的区划分可能与其所处的地理位置、经济、人口等有一定联系。

除此之外，用户通过探索关键子结构时发现了部分生僻的子结构，如图6中的A、B两类子结构在整个结构中远不如C这样的结构在整个区划分数据中分布的那么广泛。尤其A类结构的子节点数远多于B、C两类结构。为探知出现这一现象的原因，与用户一起查阅了相关资料。资料显示出现A类结构的新都区其面积在成都市排名第三，这一数据间接反映出A类结构的出现可能因其地理因素影响较大。出现B类结构的城区为金牛区和武侯区作为一圈城的城区，出现该情况可能跟其他因素有关如人口等。

案例二:探索不同版本的层次数据之间的差异，可帮助用户快速了解版本之间的演变过程，同时也能协助对错误进行追踪[15]等。选择19版和14版农药残留限量数据证明该方法可用于辅助探索具有版本迭代地层次数据的结构差异性。

为探索两个版本之间的差异，志愿者首先对比两版本的数据的概览模块。对比发现，在19版中第四层总的节点数由14版的170多增加到200。其增加节点类型以叶节点为主。这说明，在19版本中引入了更多的测定对象。然后又进行了关键子结构对比，发现在两个版本中，其关键子结构的数量都为7种，但关键子结构只有4个保持完全相同(见图7)。志愿者接着对比了关键子结构在原始布局上的整体分布。在对比的过程中发现，19版的第四层节点中删除了部分14版中的叶节点，如在谷物这一大类下19版删除了14版中的一个叶节点(其他麦类)。这一细微差异相对于结构差异变化明显的来说是很难发现的(如油料油脂分类的子类在19版由四大分类变为两大分类)。除对比两个相同子结构在整体上的分布外，志愿者在对比两个相似的子结构时，同样发现了类似上述的差异情况。

与现有的方法相比，提出采用重要节点评估算法来评估节点的重要性，根据重要性来决定需视觉编码的节点，这能保留更多的拓扑结构信息避免过多的结构信息被视觉编码隐藏，从而提高了探索效率。同时，采用提取关键子结构对层次结构的拓扑特征进行概括和图嵌入算法对节点进行向量化方法相结合，提升了用户探索拓扑结构信息的效率与准确率。实验案例研究表明，该方法不仅支持单一层次结构数据的拓扑结构信息探索，还适用于具有版本迭代的层次结构信息的对比分析。

由于层次数据不仅蕴含着结构信息，同时各节点中具有属性信息，在未来的工作中将研究或提出一种合理的方法将属性信息加入当前探索框架中，来帮助用户更全面地探索层次数据中的结构信息和属性信息。