针对时变层次数据的时变树图布局方法和应用

摘要

本发明公布了一种针对时变层次数据的时变树图布局方法，包括：将数据集DS按层次和时间关系表示为K棵树；将不同时刻的树或子树的根节点(tk，root)在时间轴上按顺序进行排列布局；采用行布局的方式将(tk，root)的孩子节点在对应区域内对第一行进行布局；重复执行布局直至该父节点下孩子节点均布局完毕；最后完成对待显示的整个数据集DS的时变树图布局。本发明提供方法应用于具有时变性和层次性的农残数据的展示分析，将每个时刻的原始布局区域设置为正方形，采用行布局的方式完成树图填充布局，生成的树图能够同时显示农残数据的层次特性和时间属性，具有很好的可视化效果。

权利要求

1.一种针对时变层次数据的时变树图布局方法，所述时变层次数据是一组具有权值随时间发生变化的时变性质的通过层次结构关系互相关联的层次数据集，用DS表示，针对时变层次数据集DS进行可视化处理，具体操作步骤如下：A.将DS按照层次和时间关系表示为K棵树；表示成的树的数目与待可视化数据划分的时刻的数目相同；将时刻k下的树或子树的根节点记为(tk，root)；

B.将不同时刻的树或子树的根节点(tk，root)从左到右在时间轴上按顺序进行排列布局；

C.采用行布局的方式，将(tk，root)的孩子节点在对应区域内对第一行进行树图填充布局；

D.对于同父节点下的其他孩子节点，重复执行C的布局过程，完成其他行的树图填充布局，直至该父节点下孩子节点均布局完毕；

E.对于树结构中的所有节点，在叶子节点被布局完毕之前，重复C和D的布局步骤；直至完成对待显示的整个数据集DS的时变树图布局。

2.如权利要求1所述针对时变层次数据的时变树图布局方法，其特征是，所述布局均依照紧靠上边的方法进行。

3.如权利要求1所述针对时变层次数据的时变树图布局方法，其特征是，步骤B所述进行排列布局，具体是将每个时刻的原始布局区域设置为正方形进行布局；所述正方形的面积与根节点的权值成正比，并通过计算确定每一个时刻对应填充区域的正方形边长，其中，Rmax为根节点权值最大的时刻在布局中所对应正方形的边长；其余时刻的正方形边长由式1计算得到：式1中，Rmax为根节点权值最大的时刻在布局中所对应正方形的边长；Rk为其余时刻的正方形边长；rootk.value为第k个根节点的权值；rootmax.value为权值最大的根节点的权值。

4.如权利要求1所述针对时变层次数据的时变树图布局方法，其特征是，步骤C中所述进行布局，具体是按行计算出最优填充个数，并应用于所有时刻的该行布局中；具体操作步骤为：C1.假设对于当前布局的行数从第m个节点开始进行布局，第m个节点的子节点记作childim，对应节点m每一个时刻的变化值为(tk，childim)，其中k代表时刻；在节点m对应的父节点每一个时刻的变化值(tk，fatheri)的布局空间内，依照紧靠上边的方法，计算得出在不同时刻第一行节点布局的各自的平均长宽比，并选择取值最小的平均长宽比所对应的布局个数为各时刻的最佳布局个数(tk，nk)；所述平均长宽比通过式2计算得到：式2中，ASi为第i个子节点对应的矩形长宽比，ASi＝Max(hi/wi,wi/hi)；n为节点数目；

AAR为树图的平均长宽比，AAR的值越接近1，则该矩形越接近正方形；

C2.当各时刻的填充个数没有达到可填充上限时，计算填充nk+1个节点后的平均长宽比；

C3.设定nmax为所有时刻最佳布局个数(tk，nk)的最大值Max[n1..k]，即nmax＝Max[n1..k]，对于填充个数小于nmax的时刻仍需要继续补充计算平均长宽比，从而得出每个时刻k下，所有填充个数属于[1，nmax]时各自相应的平均长宽比；

C4.计算填充个数为nk时所有时刻的平均长宽比的均值，nk属于[1，nmax]，取平均长宽比均值最低的填充个数Min[n1..k]作为所有时刻的最优填充个数，由此计算得出该行在所有时刻下的最优填充个数，并应用于所有时刻的该行布局中。

5.将权利要求1所述针对时变层次数据的时变树图布局方法应用于农药残留数据的展示分析，其特征是，针对具有时变性和层次性的农药残留数据，按不同时刻下的数据的层次和时间关系表示为多棵树，将不同时刻的树的根节点记为(tk，root)，从左到右在时间轴上按顺序进行排列布局，将每个时刻的原始布局区域设置为正方形，采用行布局的方式，首先将(tk，root)的孩子节点在对应区域内对第一行进行布局，计算出最优填充个数，并应用于所有时刻的该行布局中，完成第一行布局；针对其他孩子节点，重复执行布局过程，完成其他行的树图填充布局，直至该父节点下孩子节点均布局完毕；完成树结构中的所有节点均布局；从而利用生成的树图同时显示农残数据的层次特性和时间属性的目的。

说明书

针对时变层次数据的时变树图布局方法和应用

技术领域

[0001] 本发明属于信息可视化领域，具体涉及针对时变层次数据的时变树图布局方法和应用。

背景技术

[0002] 在大数据时代背景下，如何通过有效的可视分析方法从海量数据中寻找到其中规律，从而帮助用户决策是当今大数据领域中的一个热点话题。

[0003] 层次数据一直是可视化领域中的一个重点研究对象，经典的层次数据可视化算法有节点-链接、树图和放射环等，其中树图方法已经在生理分析、图片展示和经济状况分析等各个领域之中有所应用。树图布局算法最早于1993年由Johnson等提出，其针对节点链接方法中存在的节点覆盖和空间利用率低的缺点提出了填充式布局算法Slice and Dice。而为了解决Slice and Dice中细长矩形数量过多、用户难以识别的问题，Mark Burls等于1999年提出了Squarified算法，使用Squarified布局算法能够得到很好的平均长宽比，但是打乱了数据原本的顺序。因此，为了使树图的布局能够让用户方便快捷地沿节点顺序找到相应在树图中的布局位置，Bederson等于2002年提出了Strip算法，Tu等于2007提出了Spiral方法，对Strip方法进行了优化，使节点在树图布局中保持连续。为了使树图布局算法能够让具有地理信息的数据进行应用，Wood等人于2009年提出了Ordered-Squarified。
Thomas等于2012年对树图布局算法进行了归纳总结，将影响树图布局算法中布局的变量归纳为以下5个：Order、Size、Chunk、Recurse和Phrase，用户可通过对这五个变量的自定义设置改变树图布局的情况。

[0004] 然而，现实生活所产生的数据往往包含多种属性，例如经采集后的数据往往是携带有时间属性的，而在数据挖掘和数据分析过程中，对时间属性的处理也是一个不可忽视的环节，目前具有时间维度属性的数据的可视化算法主要包括主题河流、热力图和矢量图等。时变布局算法可以分为两个类别：按时间轴布局和动态变化布局。最常见的方法是使用轴长来表示时间的变化，每一个刻度代表一个时间段，然后在该刻度上通过高度、形状、颜色和文本显示等标识数据的其它属性；将数据的时间属性使用横轴表示，然后使用改进的流程图表示事件其它相关属性的Outflow；对平行坐标进行优化，采用引入时间轴概念的Time Wheel；在文本可视化中使用引入时间元素的Theme River或螺旋状时间轴的Helix glyphs。而动态变化的布局方式则是通过在图上对海量数据进行快速变化显示，使整个显示效果在视觉感知中以动态的形式展现出来，包括以高亮和颜色深浅表示量的大小的热力图，以及以线条为基础随时间发生变化的矢量图。

[0005] 综上所述，现有的树图布局算法和时变布局算法均从不同角度实现了对数据的良好可视化展示，在不同评价指标方面也各有良好的表现。但是，针对时变层次数据(同时具备层次和时间两个维度属性的数据)进行可视化，如采用现有树图算法对布局中相同的节点进行跟踪时，仍需要耗费较多时间，还不能实现在保留树图层次的同时精确、快速地描述节点的变化情况。

发明内容

[0006] 为了克服上述现有技术的不足，本发明提供一种针对时变层次数据的时变树图布局方法Treemap array along timeline(TAT)，能够针对同时具有时变和层次属性的数据进行可视分析，保证生成的树图在保留树图可视化层次并凸显节点值大小的同时又具备时间属性显示能力，解决时变数据在树图布局中查找时间过长的问题。

[0007] 本发明提供的技术方案是：

[0008] 一种针对时变层次数据的时变树图布局方法，所述时变层次数据是一组具有权值随时间发生变化的时变性质的通过层次结构关系互相关联的层次数据；针对待显示的时变层次数据集(用DS表示)进行可视化处理，具体操作步骤如下：

[0009] A.将待可视化数据集DS按照层次和时间关系表示为K棵树；对于时刻k下的树(或子树)根节点，记为(tk，root)；

[0010] 对于时刻k下的树(或子树)根节点，记为(tk，root)，其中tk代表时刻k，相应的父节点fatheri记为(tk，fatheri)，fatheri的子节点记为(tk，childij)，如图2所示，每个节点对应的权值以value表示，图2中灰色节点表示该节点的权值发生了改变。

[0011] 表示成树的数目具体根据实际需要对比的节点变化时刻来确定，例如，若需要比较时刻T1、时刻T2、时刻T3和时刻T4的同一节点的变化情况，则对应4个时刻将数据表示为4棵树；每棵树都是一个嵌套层次关系，树图层次以嵌套布局表示：若根节点A有子节点B，则树图布局时B要在A的树图布局区域内，若B和C是同一个根节点A的兄弟则B和C都在A的范围内布局，但是A和B不互相嵌套。

[0012] B.将不同时刻的根节点(tk，root)从左到右在时间轴上按顺序进行排列布局；

[0013] 将每个时刻的原始布局区域设置为正方形(正方形比细长条形的矩形更易于识别)，其中正方形的面积与根节点的权值成正比，并通过计算确定每一个时刻对应填充区域的正方形边长，如图3所示，显示区域的ymax由用户自定义，在图3中对应ymax＝Rmax，其中，Rmax为根节点权值最大的时刻在布局中所对应正方形的边长；其余时刻的正方形边长由式1计算得到：

[0014]   (式1)

[0015] 式1中，Rmax为根节点权值最大的时刻在布局中所对应正方形的边长；Rk为其余时刻的正方形边长；rootk.value为第k个根节点的权值；rootmax.value为权值最大的根节点的权值。

[0016] C.采用行布局的方式，首先将(tk，root)的孩子节点在对应区域内对第一行进行布局，计算出最优填充个数，并应用于所有时刻的该行布局中，完成第一行布局；

[0017] 由根节点至子节点的所有中间节点都进行树图层次递进嵌套布局，为了便于在不同时刻对树图中同一节点进行跟踪，可引入节点位置属性position(pi，qi)，其中pi代表行数，qi代表个数，且在树图布局中每一个节点的位置属性唯一。采用此方法即可利用位置行列号搜索到单个节点，实现快速跟踪，如图3所示。

[0018] D.对于同父节点下的其他孩子节点，重复执行C的布局过程，依照紧靠上边的原则完成其他行的树图填充布局，直至该父节点下孩子节点均布局完毕。

[0019] E.对于树结构中的所有节点，在叶子节点被布局完毕之前，重复C和D的布局步骤。

[0020] 经过上述步骤的操作，即可完成对待显示的整个数据集DS的时变树图布局。

[0021] 本发明方法中，每行布局的个数与所有需要布局时刻的节点相关，步骤C中所述按行计算出最优填充个数，并应用于所有时刻的该行布局中的具体操作步骤为：

[0022] C1.若对于当前布局的行数从第m个节点开始进行布局，节点m对应记作childim，对应节点m每一个时刻的变化值为(tk，childim)，其中k代表时刻。在其对应的父节点(tk，fatheri)的布局空间内，依照紧靠上边的原则，计算得出在不同时刻第一行节点布局的各自的平均长宽比，并选择最优(取值最小)平均长宽比所对应的布局个数为各时刻的最佳布局个数(tk，nk)。

[0023] 其中，平均长宽比的计算方法如下：设第i个子节点对应的矩形长宽比为ASi，其中ASi＝Max(hi/wi,wi/hi)，则树图的平均长宽比AAR为其所有子节点长宽比的平均值，如式2所示：

[0024]   (式2)

[0025] 式2中，ASi为第i个子节点对应的矩形长宽比；n为节点数目；AAR为树图的平均长宽比，AAR的值越接近1，则该矩形越接近正方形，更有利于人眼识别及鼠标操作。

[0026] C2.在各个时刻(如图3中的T1，T2和T3时刻)下，当填充个数没有达到可填充上限时，计算填充nk+1个节点后的平均长宽比。

[0027] C3.令nmax为所有时刻最佳布局个数(tk，nk)的最大值Max[n1..k]，即nmax＝Max[n1..k]，则对于填充个数小于nmax的时刻仍需要继续补充计算平均长宽比，从而得出每个时刻k下，所有填充个数属于[1，nmax]时各自相应的平均长宽比。

[0028] C4.最后，计算填充个数为nk(nk属于[1，nmax])时所有时刻的平均长宽比的均值，取平均长宽比均值最低的填充个数Min[n1..k]作为所有时刻的最优填充个数。

[0029] 经过步骤C1至C4的操作，则可计算出该行在所有时刻下的最优填充个数，并应用于所有时刻的该行布局中。

[0030] 本发明还同时提供将上述针对时变层次数据的时变树图布局方法应用于农药残留数据的展示分析，具体是，针对具有时变性和层次性的农药残留数据，按不同时刻下的数据的层次和时间关系，表示为多棵树，将不同时刻的树的根节点记为(tk，root)从左到右在时间轴上按顺序进行排列布局，将每个时刻的原始布局区域设置为正方形，采用行布局的方式，首先将(tk，root)的孩子节点在对应区域内对第一行进行布局，计算出最优填充个数，并应用于所有时刻的该行布局中，完成第一行布局；针对其他孩子节点，重复执行布局过程，完成其他行的树图填充布局，直至该父节点下孩子节点均布局完毕；直到树结构中的所有节点均布局完成；生成的树图能够同时显示农残数据的层次特性和时间属性。数据的层次关系由树图展现，时间关系由时间轴体现，并且可以根据对比不同时刻下的树图查看同一节点的权值变化，实现通过引入时间特性来对值不断发生变化的层次数据进行长期追踪分析。

[0031] 与现有技术相比，本发明的有益效果是：

[0032] 本发明针对时变数据在树图布局中查找时间过的问题，提供一种针对时变层次数据的时变树图布局方法Treemap array along timeline(TAT)以及时移性的评价指标。本发明所提出的方法可以保证生成的树图在保留树图可视化层次并凸显节点值大小的同时又具备时间属性显示能力，能够帮助用户更精确和快速的找到相应的节点，在评价指标上也有良好表现，将该布局算法应用于不同时间段内农产品农药残留量检测结果的对比与跟踪等数据分析场景之中，有较好的效果。

附图说明

[0033] 图1为本发明提供的针对时变层次数据的时变树图布局方法的流程框图。

[0034] 图2为本发明中实施例中将待可视化数据集按照层次和时间关系表示为三棵树之后的示意图；

[0035] 其中，(a)、(b)、(c)分别为时刻t1、t2、t3时层次数据所对应的树，可见相对于t1而言，t2和t3的树结构未发生变化，但是相应的权值发生了改变，图中权值发生改变以灰色节点标出。

[0036] 图3为本发明中实施例中将不同时刻的根节点(tk，root)从左到右在时间轴上按顺序进行排列布局后的示意图；其中，x轴为时刻；y轴为正方形边长；R2为根节点权值最大的时刻(即t2时刻)在布局中所对应正方形的边长。

[0037] 图4为本发明中实施例中树图节点增加位置属性之后的示意图；

[0038] 其中，(a)、(b)分别为单层结构的位置属性的示意图和多层结构的位置属性的示意图。

[0039] 图5为本发明具体实施例中将计算出的每行在所有时刻下的最优填充个数应用于所有时刻的该行布局后的布局示意图；

[0040] 其中，(a)表示具体实施例I所有时刻第1行节点布局完以后的结果示意图；(b)表示具体实施例I所有时刻第2行节点布局完以后的结果示意图；(c)表示具体实施例I所有时刻全部3行节点均处理完以后的结果示意图；(d)表示具体实施例II中布局完成的北京市2月和3月农残检测数据(水果、蔬菜农药残留检测数据)的布局示意图。

[0041] 图6为本发明具体实施例中从不同评价指标的角度分析树图布局算法的对比结果图；

[0042] 其中，(a)、(b)、(c)和(d)分别对应平均长宽比、稳定性、稳定的平衡性和时移性指标图，横坐标为节点数目，纵坐标为指标值；而线1、2和3分别代表Strip、Spiral和TAT算法对应的指标结果图。

具体实施方式

[0043] 下面结合附图，通过实施例进一步描述本发明，但不以任何方式限制本发明的范围。

[0044] 本发明提供一种针对时变层次数据的时变树图布局方法Treemap array along timeline(TAT)，TAT方法能够针对同时具有时变和层次属性的数据进行可视分析，保证生成的树图在保留树图可视化层次并凸显节点值大小的同时又具备时间属性显示能力，解决时变数据在树图布局中查找时间过长的问题。图1为本发明提供的针对时变层次数据的时变树图布局方法的流程框图，以下通过实施例描述本发明提供方法的实施步骤。

[0045] 实施例I：

[0046] 本实施例中的待可视化数据集DS为数据A1{1,1,1,1,1,1,1,1,1}，A2{3,3,4,1,1,1,1,1,1}}，A3{1,1,1,1,2,1,3,2,4}所组成的集合，分别对应同一树结构在T1，T2和T3三个时刻的权值变化与分布情况，其节点值的和分别为9、16和16。

[0047] 采用本发明提出的针对时变层次数据的时变树图布局方法，对上述可视化数据集DS进行可视化操作，其具体操作步骤为：

[0048] A，将待可视化数据集DS按层次和时间关系表示为K棵树；

[0049] 表示为树的数目与对一节点进行变化前后比较的时刻的数目相同，即有几个时刻就表示为几棵树。

[0050] 如图2所示，表示为树的数目K＝3，根节点分别为(t1，root)、(t2，root)和(t3，root)，各根节点下面分别有9个子节点，相应的父节点fatheri记为(tk，fatheri)，fatheri的子节点记为(tk，childij)，此处k为满足1≤k≤3的整数；i为父节点的数目；j为父节点fatheri相应的子节点的数目；

[0051] B，将3个不同时刻的根节点(tk，root)从左到右在时间轴上按顺序进行排列布局；

[0052] 将每个时刻的原始布局区域设置为正方形，其中正方形的面积与根节点的权值(根节点权值为子节点值相加)成正比。在本实施例中，如数据集A1根节点的权值是9，A2和A3根节点的权值都是16。首先确定代表根节点的正方形的面积大小，假设最大布局面积为4*4，则此处Rmax为根节点权值最大的时刻在布局中所对应正方形的边长4，其余时刻的正方形边长可由式1计算得出：

[0053]   (式1)

[0054] 式1中，Rmax为根节点权值最大的时刻在布局中所对应正方形的边长；Rk为其余时刻的正方形边长；rootk.value为第k个根节点的权值；rootmax.value为权值最大的根节点的权值。

[0055] 因此，在按节点值进行同步换算之后，在本实施例中，可得知数据集A2和A3在4*4的正方形中布局，A1在3*3的正方形中布局。显示区域的ymax由用户自定义，可设置ymax＝Rmax＝4；

[0056] C.为各节点引入位置属性position(pi，qi)，以便跟踪节点权值变化；

[0057] 采用行布局的方式，首先将T1，T2和T3这三个时刻根节点(tk，root)的孩子在对应区域内对第一行进行布局，具体如下：

[0058] C1.首先在对应的父节点的布局空间内，依照紧靠上边的原则，计算得出在T1，T2和T3时刻第一行节点布局的各自的平均长宽比，并选择最优(取值最小)平均长宽比所对应的布局个数为各时刻的最佳布局个数(tk，nk)；

[0059] 表1是本实施例中采用时变树图布局算法对时变树图的第一行进行布局时，根据所有时刻的行最优填充个数的计算方法，所计算得出的结果：

[0060] 表1根据所有时刻的行最优填充个数的计算方法计算得出的T1，T2和T3时刻第一行节点布局的平均长宽比

[0061]

[0062] 如表1所示，在T1，T2和T3各时刻第一行布局对应的最优平均长宽比分别为1、1.33和1，最佳布局个数对应取值分别为3、2、4，因此图中所有时刻最佳布局个数的最大值Max[n1..k]＝nk＝4(此处k＝3)。

[0063] C2.在T1，T2和T3时刻下，当填充个数没有达到可填充上限时，计算填充nk+1个节点后的平均长宽比。如表1的T1时刻所示，该时刻最优平均长宽比为1.00，最佳布局个数为3个，但因为此时未达到可填充上限，则仍计算填充为4个节点时候的平均长宽比，因此在计算过程中将可以形成如图4中的部分数据。

[0064] 同理，T2和T3时刻分别计算填充个数分别取值为3和5时的平均长宽比。

[0065] C3.令nmax为所有时刻最佳布局个数(tk，nk)的最大值Max[n1..k]，即nmax＝Max[n1..k]，则对于填充个数小于nmax的时刻仍需要继续补充计算平均长宽比，从而得出每个时刻k下，所有填充个数属于[1，nmax]时各自相应的平均长宽比。本实施例中最大的最佳布局个数nmax此处应取值为T3时刻的nk对应值4，所以需要对T1和T2时刻进行补充计算，直至计算得出各时刻填充个数属于[1，4]时的平均长宽比。

[0066] C4.最后，计算所有时刻填充个数为nk(nk属于[1，nmax])时的平均长宽比的均值，取平均长宽比均值最低的填充个数Min[n1..k]作为所有时刻的最优填充个数。如表1所示，此处选择平均长宽比均值的最小值1.56所对应的填充个数3作为最终T1，T2和T3时刻布局第一行时的共同的最优填充个数。

[0067] 图5为本发明具体实施例中将计算出的每行在所有时刻下的最优填充个数应用于所有时刻的该行布局后的布局示意图；其中，(a)表示所有时刻第1行节点布局完以后的结果示意图；(b)表示所有时刻第2行节点布局完以后的结果示意图；(c)表示所有时刻全部3行节点均处理完以后的结果示意图；(d)表示具体实施例II中布局完成的北京市2月和3月农残检测数据(水果、蔬菜农药残留检测数据)的布局示意图。

[0068] 经过步骤C1至C4的操作，则可计算出该行在所有时刻下的最优填充个数，并应用于所有时刻的该行布局中，完成第一行布局，如图5(a)所示。

[0069] D.对于同父节点下的其他孩子节点，重复执行C的布局过程，依照紧靠上边的原则完成其他行的树图填充布局，直至该父节点下孩子节点均布局完毕。

[0070] E.对于树结构中的所有节点，在叶子节点被布局完毕之前，重复C和D的布局步骤。

[0071] 图5(b)为所有时刻第2行节点布局完以后的结果示意图。经过上述步骤的操作，即可完成对待显示的整个数据集DS的时变树图布局，最终得到的布局图如图5(c)所示。

[0072] 实施例II：

[0073] 本实施例对本发明提供的可视化方法在农药残留检测结果数据中的应用为例进行说明。本实施例中的待可视化数据集DS为北京市2月至3月农产品的农药残留检测数据，该数据为以真实数据为基础的模拟数据，其中包括水果农残记录477条、蔬菜农残记录1233条，此处仅列举部分数据如下：

[0074]

[0075]

[0076]

[0077]

[0078] 采用本发明提出的针对时变层次数据的时变树图布局方法，对上述待显示的数据集DS进行可视化操作，其具体操作步骤为：

[0079] A.将待可视化数据集DS按层次和时间关系表示为2棵树；

[0080] 本实施例中，因为只涉及到2个时间点(2月和3月)，故将待可视化数据集DS按层次和时间关系表示为2棵树。每棵树都对应一个该时刻权值对应的树图布局，这样对比多个时刻的树图布局就可以发现同一节点的权值变化了。而对于层次关系的展现，例如北京市包括延庆、顺义等区，则北京市作为一个大的根节点，延庆和顺义在其中布局；延庆又分为两个部分，则每一个节点分为两部分；树图布局与地区的对应关系如图5(d)所示。

[0081] 本实施例中K＝2，因此根节点分别为(t1，root)、(t2，root)，此处t1＝2，t2＝3(单位：月)，根节点下面有若干子节点，相应的父节点fatheri记为(tk，fatheri)，fatheri的子节点记为(tk，childij)。

[0082] B.将2个不同时刻的根节点(tk，root)从左到右在时间轴上按顺序进行排列布局。将每个时刻的原始布局区域设置为正方形，其中正方形的面积与根节点的权值成正比，此处节点权值代表北京市各区县蔬菜或水果的农药检出频次(只要农产品在相应区域存在农药检出量，则相应地为其进行频次计数)。

[0083] C.为各节点引入位置属性position(pi，qi)，以便跟踪节点权值变化，采用行布局的方式，首先将T1和T2这两个时刻根节点(tk，root)的孩子在对应区域内对第一行进行布局，具体如下：

[0084] C1.首先在对应的父节点的布局空间内，依照紧靠上边的原则，计算得出在T1和T2时刻第一行节点布局的各自的平均长宽比，并选择最优(取值最小)平均长宽比所对应的布局个数为各时刻的最佳布局个数(tk，nk)。

[0085] C2.在T1和T2时刻下，当填充个数没有达到可填充上限时，计算填充nk+1个节点后的平均长宽比。

[0086] C3.令nmax为所有时刻最佳布局个数(tk，nk)的最大值Max[n1..k]，即nmax＝Max[n1..k]，则对于填充个数小于nmax的时刻仍需要继续补充计算平均长宽比，从而得出每个时刻k下，所有填充个数属于[1，nmax]时各自相应的平均长宽比。

[0087] C4.最后，计算所有时刻填充个数为nk(nk属于[1，nmax])时的平均长宽比的均值，取平均长宽比均值最低的填充个数Min[n1..k]作为所有时刻的最优填充个数。

[0088] 经过步骤C1至C4的操作，则可计算出该行在所有时刻下的最优填充个数，并应用于所有时刻的该行布局中，完成第一行布局。

[0089] D.对于同父节点下的其他孩子节点，重复执行C的布局过程，依照紧靠上边的原则完成其他行的树图填充布局，直至该父节点下孩子节点均布局完毕。

[0090] E.对于树结构中的所有节点，在叶子节点被布局完毕之前，重复C和D的布局步骤。

[0091] 经过上述步骤的操作，即可完成对待显示的整个数据集DS的时变树图布局。

[0092] 最终得到的布局图如图5(d)所示。由图可见，其在保留层次结构(北京市、北京市各区县、区县内农产品层次)的同时，很好地体现出了不同时间段内(2月和3月内)某区域的权值变化情况(农产品的农药检出频次增大或减少情况)。

[0093] 通过平均长宽比、稳定性、稳定的平衡性和时移性指标来验证本发明。其中，时移性指标及相应验证方法如下：

[0094] 假设节点矩形Ri(xi，yi)有2个属性，分别为矩形Ri的在布局中以边长为分母进行归一化处理后的中心点的坐标。对于两个时刻的节点变化情况，用Gi(di，θi)来代表每个节点在布局中变化的量，其中di为变化坐标的绝对值差，θi为相对于水平线而言变化的角度；i为第i个节点矩形Ri的节点编号。

[0095] 参照计算2个矢量之间扇形面积的原理，对于2个连续的节点之间，以最大的变化距离作为扇形半径，将时移性指标TMD定义为：

[0096]   (式3)

[0097] 式3中，用Gi(di，θi)来代表每个节点在布局中变化的量，其中di为变化坐标的绝对值差，θi为相对于水平线而言变化的角度；i为第i个节点矩形Ri的节点编号。其值与节点布局变化的距离的平方以及角度成正比。该值越接近0，则表示其变化量越小。将该指标与稳定性及稳定的平衡性指标相比，由于后两者均是以变化的标量计算值来做评价的，而节点位置的变化应该是发生矢量的变化，因此时移性指标比这两项指标更能较好地描述数据时变的性质。

[0098] 另外，平均长宽比(average aspect ratio,AAR)的计算方法为：设第i个子节点对应的矩形长宽比为ASi＝Max(hi/wi,wi/hi)，则树图的平均长宽比AAR为其所有子节点长宽比的平均值,如上述式2所示。

[0099] 而稳定性指标ADC的计算方法如下：假设节点矩形Ri(xi，yi，wi，hi)具有4个属性，分别为节点矩形Ri的横坐标、纵坐标、宽度和高度，则对于单个节点用式4求其对应矩形Ri的位置和形状变化，即

[0100]   (式4)

[0101] 则ADC为树图中所有节点位置和形状变化d的平均值，即

[0102]   (式5)

[0103] 稳定的平衡性指标VDC的计算方法如下：该值由对式4中的位置和形状变化d求方差而得到，其定义如式6所示，其中Var(d)表示对d求方差，E(d)表示对d求期望值。

[0104] VDC＝Var(d)＝E{[d-E(d)]2}  (式6)

[0105] 同时，也利用Strip树图布局方法、Spiral树图布局方法对以上数据进行可视化布局并计算各指标值，最后将计算结果进行比较，图6即最终结果图。

[0106] 通过图6我们可以看到从不同评价指标的角度分析树图布局算法的对比效果：相对于Strip和Spiral布局算法，通过对比图6(a)，TAT布局算法在平均长宽比上相对较高，性质较差，但是差距较小，不影响布局的美观性和矩形的可见性；通过对比图6(b)，TAT布局算法在稳定性上数据值较小，性质较好，随数据量的增加，三者的指标差距相对稳定在8附近，说明TAT布局算法在数据发生变化时，树图布局结构变化较小；通过对比图6(c)，TAT布局算法在稳定的平衡性上有明显的优势，说明TAT布局算法在布局上比较稳定，不存在个别节点位置发生突变的情况；通过对比图6(d)，TAT布局算法在时移性上的值在1左右，非常接近理想值0，明显优于其余两种算法，说明在数据发生变化时，树图布局的变化不会明显影响用户搜索节点的速度。

[0107] 综合对比，TAT布局算法在牺牲少量平均长宽比的条件下，可以得到更好的稳定性、稳定的平衡性和时移性，并且在有所提高的指标上提高量较为明显。相对于Strip和Spiral布局算法，能使树图布局在数据变化时产生更小的布局变化，对用户理解树图产生更小的影响，TAT树图布局算法更加适于应用在具有时变性质的层次数据中。

[0108] 需要注意的是，公布实施例的目的在于帮助进一步理解本发明，但是本领域的技术人员可以理解：在不脱离本发明及所附权利要求的精神和范围内，各种替换和修改都是可能的。因此，本发明不应局限于实施例所公开的内容，本发明要求保护的范围以权利要求书界定的范围为准。