第八章-层次及网络数据可视化1

层次数据可视化主讲人：刘天亮liutl@

TEL京邮电大学图像处理与图像通信江苏省重点实验室提纲层次数据层次数据的可视化节点链接法及其应用空间填充法及其应用混合型层次数据

(HierarchicalData)层次数据（树结构）层次数据着重表现个体之间的隶属关系社会、自然界中的从属关系机构的组织结构，

物种关系信息的组织形式文件列表逻辑承接关系决策树我们通过分类来理解事物，层次结构是我们认知行为的基础——PeterMorville为什么要层次结构？层次结构是复杂系统中有效的管理组织形式，以及稳定、可持续的发展机制"TheArchitectureofComplexity:HierarchicSystems"

社会系统

生物和物理系统

符号系统层次结构中

个体元素的相对独立性层级结构中的个体元素

相关的子系统(interrelatedsubsystems)

相对独立(semi-independent)子系统之间的关系

影响往往是通过子系统之间的功能(输入、输出）

和一个子系统内部实现其功能的具体方式无关可拆分(decomposability)或准可拆分(neardecomposability/2011/06/27/organizational-charts/公司组织结构图六大计算机公司的组织结构图，生动地反映了独特的企业文化：亚马逊有严格的等级制度；谷歌也有清晰等级，但部门之间相互交错，由google的三驾马车CEO埃里克·施密特（EricSchmidt）、Google联合创始人拉里·佩奇（LarryPage）和塞吉·布林（SergeyBrin）共同领导；Facebook像一张分布式网络；微软各自占山为王，且相互竞争，但其实应该更接近于Apple的情况，即以扎克伯格为核心；苹果是各小团队相互平等灵活作战，但乔布斯的作用非常明显；甲骨文法务部门远大于工程部门国内公司结构图1.腾讯，产品与部门关系千丝万缕，QQ是所有产品与服务的基石。2.百度崇尚简单；3.华为，技术创新引发矩阵结构变化；4.阿里巴巴，马云的影子无时无处不在；5.360掐架大王，总要有人在后面擦屁股家谱树希腊神话中众神的家谱（局部），其中字母F表示一个由父母（在字母F之上的黑色圆点）和子女（在字母F之下的黑色圆点）组成的家庭。A.Bezerianos,P.Dragicevic,J.-D.Fekete,J.Bae,B.Watson.GeneaQuilts:ASystemforExploringLargeGenealogiesGeneaQuilts家谱树物种发展这棵树清晰地呈现了不同物种之间的遗传关系，所有物种通过生物发展史的基因链接关系相连。本数据包含93891个物种，占今天地球上的1亿物种的极小部分。根节点"LifeonEarth''(红色字体)被置于树的西南角，它的西南方向链接了``Greenplants''（绿色植物，绿色）分支，东南方向链接了''Protista''（原生动物，淡红色）分支，西北方向链接的是''Fungi''（菌类，黄色）分支。数据来源：/tree/图片来源：/~yifanhu/TOL/思维导图层次数据的表达:图结构图G由一个顶点（或节点）集合V和一个边集合E组成

G={V,E}每条边exy=(x,y)连接图G的两个顶点x,y例如：V={1,2,3,4},E={(1,2),(1,3),(2,3),(3,4),(4,1)}显然，这种表达对于非专业人士来说，还是比较难懂的层次数据的图形化表达G={V,E}V={1,2,3,4},E={(1,2),(1,3),(2,3),(3,4),(4,1)}图的结构表达无向图;(b)加权图;(c)不连通图;(d)顶点的度;(e)回路;(f)无回路图;(g)有根结点的层次树;(h)结点深度图的结构表达图的结构表达树形结构和网络结构是层次和网络数据可视化的基本型边的方向和权重，是可视编码的重要组成部分结点的度、平面性、连通性，是图结构的基本性质，对树、网络的挖掘至关重要但对于大的层级结构来说，

图形化的展示面临一些挑战物种发展数据来源：/tree/图片来源：/~yifanhu/TOL/主要的挑战把节点和边信息展示出来

点和边的空间排布组织形式允许用户对层次数据进行交互式分析探索

对层次数据的相关部分进行观察分析

展示：合理的利用显示空间交互：和任务相关的功能工具

微观细节和

宏观背景

对子系统进行汇总、比较不同的子系统等层次数据的可视化层次数据的展现方式按数据的理解方式不同，层次数据的构建分：自上而下和自下而上层次数据可视化的核心：1、如何表达层次关系的树形结构2、如何表达树形结构中的父结点和子结点3、如何表现父子结点、具有相同父结点的兄弟结点之间的关系等层次数据的展现方式

按布局策略，主流方法可分为：节点链接法：结构清晰型表达(structure-clarity)节点链接树双曲树三维树空间填充法：空间利用率高(space-efficiency)树图(Treemap)Voronoi树图混合型：利用上述两种方法的互补性，弹性层次图为代表Jürgensmann和Schulz对树结构可视化技术进行了总结和分类，并制作了海报。他们采用的分类思路与上面介绍的基本一致：显性，隐性与混合三种。显性方法基本等同于节点链接法，而隐性方法则对应空间填充法。在此基础上，根据空间维度（二维或三维）及布局方法（正交、径向、自由布局）做了更进一步分类。这样的层层分类本身也是一个层次结构，可采用空间填充方法进行可视化。

作品赢得了2010年IEEEInfoVis会议的最佳海报奖，其后又演化成在线互动版()Jürgensmann和Schulz对树结构可视化技术进行了总结和分类，并制作了海报以及在线东台书可视化检索系统。

图8.2层次数据可视化分类。

分类延续了结点链接、空间填充和混合型的思路，分界线的粗细表达了层次的深度。8.1.1节点链接法节点链接法是图论中树形的扩展，可视化绘制的核心是结点和边的位置编码和视觉符号编码。为了达到结点链接法实用性和美观性，绘图算法设计往往需遵循一些原则：尽量避免边的交叉。边的教材可能会导致对图的错误理解。结点和边尽量均匀分布在整个布局界面上。边的长度统一可视化效果整体对称，保持一定的比例网络中相似的子结构的可视化效果相似实际设计中，并不一定能完全满足所有的原则，设置原则之间会产生矛盾，需要平衡和取舍，因此将产生对各原则有不同侧重的布局根据节点与链接的布局策略，

可以细分为如下三种正交布局（网格型布局）缩进图(indent)聚类树(dendrogram)冰柱图(icicle)径向布局（辐射型）径向布局图双曲树三维布局dendrogram径向布局正交布局节点在放置的时候，都按照水平或垂直对齐方向与坐标轴一致的，布局规则与视觉识别习惯吻合，非常直观缺点对于大型的层次结构，特别是广度比较大的层次结构，这样的布局会导致不合理的长宽比、布局不均匀分布和较大空间浪费电路图正交且空间高效•对机器友好，对用户不友好电磁炉的电路图缩进图快速并易于实现可以使用纯文本（或HTML）浏览大数据时需要很多滚动操作容易失去上下文(context)Flare软件包的子目录结构/jheer/files/zoo//?p=951美国铁路的兼并聚类图美国曾经也是个大量依赖铁路货运的国家。货运公司遍布全国。但是近50年来，这些公司互相兼并。上面的可视化来自财富杂志的美术总监NicolasRapp的文章TheBattleofTheRails。他用这样一个类似树状的结构很清晰的展示了铁路公司兼并的历史。在80年代，这许多公司在大量的兼并之后，只剩下屈指可数的7家。而现在上图中用红线标出区区四家占了全国铁路货运的九成。印欧语系冰柱图常用于聚类分析，展现层次聚类结果/jheer/files/zoo/ex/hierarchies/icicle.png正交树图的一般实现•简单的递归实现–根据树的深度将空间沿纵轴平均分成等高的区域。每个区域对应树的一层。树中相同深度的节点属于同一层。–根据叶节点的数量,将对应的区域沿横轴平均分成等宽的区域。–将节点布置在每个区域的中心。–在节点和它的父节点之间连线。Reingold-Tilford树算法•标准：–所有节点按照在树中的层次进行分层绘制–避免边相交–相似的子树用相似（或镜像）进行表达–表达紧凑•基本方法：–自底向上递归计算–对于每个父节点，确保子树已完全绘制–尽可能紧致地包装子树–将父节点放在子树的中心位置尤其注重布局的对称性和紧凑性Reingold-Tilford树算法•自底向上递归计算：–对树进行后序遍历•这样对于父节点，在遍历到的时候可以确保其左右子树都已经布局完毕。•对于每个父节点，确保子树已完全绘制–通过这样的绘制顺序可以保证结构相同的子树拥有相同的表示——因为每个子树的绘制过程都不会受到子树外元素的影响。Reingold-Tilford树算法•尽可能紧致地包装子树–对于每一个节点，计算其左子树的右轮廓与右子树的左轮廓，并调整左右子树的位置直至两者刚好错开一个预先设定的阈值r为止。•随后将父节点放在左右子树的中心位置•可以推广至多叉树径向布局

更加合理地利用空间 根节点位于圆心，不同层次的节点被放置在半径不同的同心圆上

节点到圆心的距离对应于它的深度 满足树结构节点数量随层次而增加的特点Radial/demo径向布局Flare软件包的目录结构/jheer/files/zoo/三维树(Cone-Tree)GeorgeRobertson,

JockD.Mackinlay,

StuartCard.ConeTrees:Animated3DVisualizationsofHierarchicalInformation.In

ProceedingsoftheACMCHI91HumanFactorsinComputingSystemsConference,pages189--194,April28-June5,1991,NewOrleans,Louisiana,June1991.AssociationforComputingMachinery三维树(Cone-Tree)三维空间，结合二维投影优点

三维空间来扩展可用显示空间

三维动画来降低认知成本缺点

难以对付很大的树

三维交互还是一个挑战双曲树排布

将节点在双曲空间分布（节点数仍然随深度曾几何级数增长！）双曲树排布利用对二维空间的非线性映射来有效地利用空间优点

很酷

在局部细节和宏观结构的平衡缺点

操控不是很容易，非线性映射使得准确控制节点的空间位置变得困难节点链图的问题节点数随着深度增加呈几何级数增长解决方案——交互使用变形对节点进行汇总、过滤鱼眼变形DOI树（节点过滤）DOI:DegreeofInterestSpaceTree(Grosjea,etal.,2002)树的展示根据用户的需求进行动态的调整支持实时的查找并根据查找来调整树的展示8.1.2空间嵌套填充法一种基于区域的可视化方法，直接采用显示空间中的分块区域表示数据中的个体。三个可计算的评价指标：可读性、距离相关性、稳定性包含/被包含关系Enclosure

为了表达节点的父-子关系，将子节点整个封装在父节点中树图(Treemaps)Johnson和Shneiderman在1991年提出 假设每个叶节点具有一个“尺寸”属性（例如磁盘中的文件，或者机构图中的薪水等）

父节点的尺寸是所有子节点尺寸之和例：磁盘浏览类别数据的树图

伦敦个人房产交易数据的树图可视化类别数据的层次类别数据本身没有层次关系类别的层次安排对结果影响很大把类别对数据的影响程度作为层次房产数据地区：闹市、郊区房子类型：别墅、商品房周边环境利用树图的几个原则层次数据层次之间的关系比较清晰、容易理解每个子系统有一个统一的数字化度量

文件尺寸、股票价格等最好允许用户控制树图中元素的展示粒度层次上行/下行树图的一个问题逐级纵横切割细分会产生狭长的四边形难以与内部节点交互交替纵横切分法严格的正等分法Voronoi树图Voronoi树图

采用凸多边形代替矩形，同时解决圆填充图中利用率不高和经典树图算法的长宽比等问题Voronoi树图Squarified树图原始树图

(slice-and-dice)BalzerM,DeussenO.VoronoiTreemaps美国家庭消费结构可视化/interactive/2008/05/03/business/20080403_SPENDING_GRAPHIC.html混合型弹性层次图ZhaoS,McGuffinM

J,ChignellM

H.Elastichierarchies:combiningtreemapsandnode-linkdiagrams弹性层次图文件系统浏览器

(FileSystemNavigator,FSN)混合法在三位中的应用—节点和连线来表示目录之间的关系—文件和目录(最后一级)用空间填充法其他方法可缩放交互空间(zoomableuserin