一种基于变换的关联图可视分析方法及其系统

摘要

本发明公布了一种基于变换的关联图可视分析方法、系统及应用，通过关联图TransGraph中关联描述及关联探索两个视图展示数据集中的复杂关联，利用基于力导引的布局方法、图简化技术及图可视化中的交互设计，实现对数据的关联信息进行可视分析，解决在表示复杂关联时容易因边的交叉而导致视觉混乱的问题，突出重点监管对象、全面地展现关联信息，从而可有效地辅助分析人员制定决策。该可视分析方法可应用于农药残留检测结果数据集的可视分析，并提供了利用该可视分析方法实现的农残数据关联可视分析系统。

说明书

技术领域

本发明属于信息可视化领域，涉及数据可视分析方法，尤其涉及一种基于变换的关联图可视分析方法及其系统。

背景技术

关联关系一直以来都是数据分析的重要研究对象，存在于现实世界的各个领域之中，以农药残留数据为例，它由农药和农产品这两个互不相交的集合组成，同时农药与农产品之间存在着残留这种关联关系。图是一种常见的用来为关联关系进行建模的数学方法，可以在高层次上对事物间的联系进行有效总结，而从可视化角度而言，图可视化也是信息可视化领域的一个重要分支，又称为关联网络、网络或关联图，是关联数据分析过程中的核心组成部分，在可视化研究领域中有着大量的研究成果。

然而，针对复杂关联的图可视化工作往往有着较大挑战性，通常易因边的交叉而导致视觉混乱(visual cluttering)，且其布局复杂度也会因图的规模增大而受较大影响，难以将信息高效地传达至分析人员或最终用户。而基于数据抽象、视图变换等图简化技术从数据或视图层面上对原始图数据进行变换，则可有效降低可视化复杂度,减少视觉杂乱，并具有交互方法灵活等特点，进而能够充分发挥节点-链接图的优势，提升用户体验和工作效率，在分析复杂关联时有着重要的价值和意义。

针对图布局的优化方法一直以来都是图可视化研究的重点之一,常用的图布局方法主要包括节点-链接图(Node-Link Graph)和相邻矩阵(Adjacency Matrix)两大类。而节点-链接图是对网络关系最自然、经典的可视化布局表达,具有关系传递表达清晰、直观易理解的特点, 在社交网络分析、生物网络研究等多个领域内得到了广泛地应用,力导引布局则为该类方法的一种代表性布局。力导引布局方法(Force-directed Algorithm)是一种广受欢迎的节点-链接图布局技术，该方法可有效避免边的交叉，尽量保持边长一致，能产生优美的网络布局，充分展现网络的整体结构及其特征。Eades基于弹簧模型将图看成一个顶点为钢环、边为弹簧的物理系统，进而模拟布局过程：在系统被赋予某个初始状态后，弹簧的作用会导致钢环的运动，过近的点会被弹开，过远的点被拉进，通过不断迭代使整个布局达到平衡并趋于稳定。力导引布局方法有着良好的美学特性，且直观、易理解，可以用于大多数网络关联数据集，这一特点使其成为具有较大吸引力的一种图布局方法。但是，因该方法需要通过反复迭代以使得模型能量最小化，故其复杂度通常相对较高。针对此问题许多学者对布局方法进行了优化，其思路主要为减少迭代次数和降低每次迭代的时间复杂度。然而，随着现阶段数据量的不断增大，图可视化面临着更多的挑战，仅仅依靠布局优化难以实时高效地完成图布局并视觉友好地将具有复杂关联的信息(层次或网络关联描述或探索信息)呈现在一个固定大小的屏幕之内，因此，基于简化技术动态、交互性地实现对图的信息分级和联动展示，实现通过变换来进行复杂图数据的呈现则具有更加重要的价值和作用。

图的简化技术是指针对复杂关联图所进行的图数据以及视图层次上的精简与可视表达方法，又称为基于变换的大图可视化方法。该类方法融合了现有的图布局方法、数据抽象(聚类、图过滤等)方法、视图变换(边绑定、鱼眼变换)以及主流交互技术(Overview+Detail， Focus+Context等)，具有可视复杂度较低，用户交互体验好的优点，在分析复杂关联时可发挥重要的作用。其中，数据层次的简化往往需要结合数据挖掘或统计手段预先对数据进行过滤筛选、数据聚集或分层处理，将待可视化的图转换为小型图或特殊类型的图(如：树)以为后续进行信息编码及可视化渲染等做好准备，主要包括抽样、聚类和降维方法。而视图层次的简化则是指在可视化视图的层面上对图中的节点或连接的绘制以及可视化信息编码方面进行简化处理。边绑定技术(edge bundling)和鱼眼(fish eye)视图变换则是典型的视图层次的图简化方法。

此外，交互技术也是基于变换的图可视化方法的重要组成部分，在图可视化的一些早期研究工作中，主要为针对图结构的静态可视化布局算法的研究，往往不具有或具有非常有限的交互功能，而随着图数据量的增大以及人们认识的转变，交互技术也逐渐较多地融入图可视化的许多研究工作之中。交互组件允许用户通过过滤筛选、平移缩放及参数调整等操作动态地影响可视化结果，从而更加有效地帮助分析人员发现模式与规律。

现有可视化方法在解决关联数据可视分析的时候，往往无法同时实现针对复杂关联的描述及探索，突出展示重点对象、全面展示关联信息的功能。

发明内容

本发明提出了一种基于变换的关联图TransGraph可视分析方法及其系统，可实现针对复杂关联的描述及探索，突出展示重点对象、全面展示关联信息。

本发明中，关联图TransGraph主要由关联描述及关联探索两个主视图组成，用于实现对数据中复杂关联的描述与探索。关联图TransGraph采用力导向布局展现节点间的关联关系，利用双层圆环和放射环展示当前关注节点的数据分布和层次结构；采用图过滤实现数据层面的抽象和筛选，并通过K-means聚类探索图中节点的潜在相似性；通过鱼眼(fisheye)技术、边绑定以及基于细节分级原则(Level of Detail)的交互式分层探索方法进行视图变换，实现对焦点图元信息的突出展示和复杂视图的简化；支持用户交互式地逐层钻取查看图的细节及节点相似性。即通过本发明可以实现针对复杂关联的描述及探索，突出展示重点对象、全面展示关联信息。

本发明的技术方案如下：

一种基于变换的关联图TransGraph可视分析方法及其系统。关联图TransGraph主要包括关联描述及关联探索两个主视图，用于描述数据中的复杂关联；基于变换的关联图TransGraph 可视分析方法，首先，针对关联数据的属性及关联信息映射为图模型(如：二部图)中的元素，然后对关联数据的属性及关联信息进行有选择性地过滤(例如特定的研究范围)及初步统计分析，然后利用TransGraph的关联描述视图与关联探索视图对关联信息进行视觉编码，将信息映射为颜色、形状或布局等视觉元素，进而完成待分析任务；如图1所示，具体包括如下步骤：

A.针对关联数据，提取关联数据中的的层次关系以树的形式来展示，通过节点的选择或者导航区的筛选，得到焦点f_u；

B.根据A所得的焦点fu，生成关联描述视图，所述关联描述视图为二部图；

本发明具体实施时，基于donut圆环图与力导向布局方法展现节点间的关联关系；采用基于Level of Detail思想的可视交互技术及鱼眼视图变换技术对力导向关联图布局进行简化；

C.根据A所得的焦点fu，生成关联探索视图；

本发明具体实施时，利用Sunburst放射环的根节点区域展示图中节点的K-means相似性聚类结果概览(包括簇的个数、每个簇中子数据(如实施例中的农药)的个数、各簇子数据整体属性)，并支持通过视图切换进一步查看层次结构中的相似性(子数据属性相似)与关联细节,该部分内容基于层次边绑定思想实现展示各节点之间的连接密度；

其中，本发明以可视化两类数据间复杂关联为例，即用二部图(关联描述视图)进行建模，其中二部图为图论中的一种特殊模型,该类图的特点为其顶点集可以分成两个不相交的集合,使得在同一个集合内的顶点互不相邻(没有共同边)，则步骤B所述操作包括的处理步骤具体为：

B1.获取A所得的焦点fu，计算与当前焦点关联的子图V，得到关联边集合E₁；获取关联数据属性，计算不同属性值在该焦点中的占比，并用圆环实现可视化；

B2.计算与B1中V关联的其他节点所构成的子图U’，得到关联边集合E₂，进而满足对不同节点的相同属性进行对比分析的需求，本发明将此过程称为二次关联；

B3.根据关联边集合E₁,E₂，基于力导向布局连接fu，V，U’图中相应节点，构成新的二部图G’，其中力中心根据圆环圆心位置进行初始设置和调整；基于弹簧模型E_s的力导向布局方法的计算公式表示为式1:

其中，k为弹性系数，d(i,j)表示平面上两点i和j之间的欧式距离，s(i,j)表示弹簧的自然长度。

其后上述弹簧模型E_s演化为能量模型E，即针对两点间的物理模型(弹簧模型)做了进一步丰富，采用静电力来模拟图中节点间的相互作用，进而计算节点间的相对位置关系，能量模型可表示为式2：

其中，r表示两点间的静电力常数；w_iw_j为两点的权重；d(i,j)同样表示平面上两点i和>

B4.将二部图G’中两个部分别可视化为圆形与矩形视觉元素，以加以显示区分，更好地体现二者关联；

B5.在B4所得的视图基础上，通过鱼眼变形函数实现对普通视图中各节点坐标的变换，至此得到变换后的关联描述子视图，进而突出重点关注对象。鱼眼技术(鱼眼变形函数)最早由Furnas于1986年提出，具体通过式3建立用户对信息空间中对象的DOI函数(Degree of Interest Function)：

DOI（x|y）＝API(x)-D(x，y) (式3)

其中，x是任一个信息对象；y是当前的焦点对象；API(x)是用户对信息对象x的先验关注度(A Priori Interest)；D(x，y)是x与y之间的空间距离或语义距离。

步骤C所述操作包括的步骤具体为：

C1.首先，获取A所得的焦点的关联数据属性及其所属分类，用交互式放射环展示层次关联；

C2.根据关联数据节点间的关联关系，确立待聚类的数据点，即获得数据集合节点相应的向量。

针对二部图中的其中一个数据集合节点vk(k＝1,2,...,m,m为集合节点个数)以及另一数据集合序列u1,u2,u3,...,un(其中n为集合节点个数)，定义如下：若vk与ul(l＝1,2,...,n) 存在关联关系，则对应标识ukl取值为1，否则为0，则对于任意一个vi都存在一个向量(ui1, ui2,ui3,...,uin)；

C3.根据上述检出向量计算WSS(Within Sum of Square，内平方和)：

其中p_i为数据对象，q⁽ⁱ⁾表示与该数据对象最近的质心，d和N分别代表节点间的距离以及数据点的个数；根据WSS确定K-means聚类中的K的个数，通常随k值的增减使得WSS显著降低时的k较为合适。

C4.通过计算农药节点vi,vj(其中i,j＝1,2,...,m,m为农药节点个数)之间的欧式距离 (式5)，进行K-means聚类(K为C3所得结果)，得出聚类向量，该向量指出农药节点的聚类簇编号(如图7所示聚类向量中类别1、2、3)。

其中，d为节点间的距离；节点vi对应向量为(ui1,ui2,ui3,...,uin)；

C5.将步骤C4的聚类结果以圆形节点簇的形式置于放射环的根节点区域内，每个圆代表一个农药节点，基于力导向布局将各个圆根据聚类结果组成各个簇，实现对结果的概览展示；

C6.通过视图切换和层次边绑定展示层次结构中的潜在关联细节，层次边绑定即以B样条曲线的形式借助层次关系进行关联边的弯曲，进而有效地展现关联层次复合图的复杂关系。并可根据节点及关联边数目调整绑定边的张力系数，即通过调整该系数控制边集束曲线的弯曲程度，进而实现降低视觉复杂度和展示关联边细节之间的权衡。

将上述方法应用于农药残留检测结果数据集，本发明实施例提供一种农残数据关联可视分析系统PestResiTGVis，该系统从关联描述及分析两个角度展示农药残留数据集中的复杂关联，包括农药与农产品间的检出关系，农产品的类别归属(层次关联)，农药同农药之间的同源或衍生关系，农药毒性和功效分类(层次关联)，检出值(超标量)随时间的变化关联，检出值(超标量)与不同地域的关联分布等。系统包括农残检测结果数据过滤导航模块、农产品与农药的检出关联描述模块、农残检出关联探索模块，还包括辅助视图模块；具体地：

一、农残检测结果数据过滤导航模块，用以获取用户过滤选择关注的焦点对象，满足按照农产品所属类目、特定样品名称、采样时间区间及省份进行数据筛选的需求。农残关联数据集可以表示为如下形式：

G＝(U,V,E)

其中，图G代表农残检测结果数据集,U和V为图G的两个部(parts),分别代表农产品和农药集合。E则为U和V之间的关联边集合,对于每个E中的每条边e(u,v)代表在农产品u中有农药v检出。

二、农产品与农药的检出关联描述模块，该模块实现了在对比、展示数据中网络关联的同时体现当前关注节点的数据分布。支持节点双击钻取展示细节，钻取后展示细节描述图。该模块揭示当前关注农产品节点的农药检出情况(农药种类、检出频次、化学成分、毒性及超标分布)以及检出同种农药的其他农产品，支持通过节点双击钻取农产品子视图中农产品节点 u，计算该农产品中的各种农药v的检出含量分布,将节点以donut圆环代替圆形来可视化分布，还结合了鱼眼视图与力导向图，可以展示切换后的关联细节(农残检出含量分布等)视图；

三、农残检出关联探索模块，该模块用于展示农药节点的K-means相似性聚类结果概览 (簇的个数，每个簇中农药的个数，各簇农药整体毒性)，支持通过视图切换进一步查看层次结构中的相似性(农药施用的对象相似)关联细节。还可以体现不同农药间的检出相似性关联以及功效分布。

四、辅助视图模块，该模块用于展示统计得出的农药残留数据，充分利用字云与条形图在信息对比排序、显示占比分布等方面的优势,进而直观展示检出频次较多的农药及农产品。能够提供农残超标排名前3名的水果、蔬菜名称，并对比显示相应的检出农药频次、检出农药种数及超标农药频次。

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

本发明提出了一种基于变换的关联图可视分析方法及系统，提供关联描述及关联探索两个主视图区,支持在对比、展示数据中网络关联的同时体现当前关注节点的数据分布或层次结构，并能根据用户关注度交互式地逐层展示图的细节及节点的潜在相似性，从而更加有效地帮助分析人员发现模式与规律、突出展示重点对象、全面展示关联信息。

附图说明

图1为本发明实施例中农残可视分析方法/系统PestResiTGVis的流程框图。

图2为本发明实施例提供的关联描述及关联探索两个主视图区；

中，(a)为关联描述视图，(b)为关联探索视图；关联描述视图是用来对比、展示数据中网络关联的同时体现当前关注节点的数据分布；关联探索视图实现了对农药的功效类别归属的展示,并探索节点间的潜在关联。

图3为本发明实施例中的可视化分析视图；

其中，(A)、(B)为农残检测结果数据过滤导航区；(C)为农产品与农药的检出关联描述视图；(D)为农残检出关联探索视图；(E)为经权重过滤动态生成的C视图的变换效果图；(F) 为经鱼眼视图变换与鼠标悬停高亮显示关联信息的交互效果图；(G)为视图为根据所聚类节点数目变换簇中节点大小后的效果图。

图4为本发明实施例中的导航过滤窗口(农产品层次分类树)。

图5为本发明实施例中关联描述视图；

其中，(a)、(b)分别为鱼眼视图变换前后的效果图；(c)为节点钻取之后的细节展示图；(d) 为根据权重过滤动态生成的变换效果图。

图6为本发明实施例中聚类簇个数的计算结果。

图7为本发明实施例中500余种农药的聚类向量结果。

图8为本发明实施例中关联探索视图；

其中，(a)、(b)分别为包含不同类农药节点簇的放射环，环的颜色代表农药功效，环内节点颜色代表所属簇的类别。

图9为簇中节点名称所生成字云，其同簇颜色相同。

图10为本发明实施例中关联探索视图的辅助视图，展示农药层次结构中的潜在关联细节。

图11为本发明实施例中可视分析系统界面效果图；

其中，(H)为关联农药名称的字云视图；(I)为检测农药频次的条形图视图；(J)为原始关联数据展示区；(K)为农药残留统计数据展示视图。

图12为本发明实施例中二部图模型示意图。

具体实施方式

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

本发明提供基于变换的关联图可视分析方法、系统及应用，从关联描述及探索两个角度展示数据集中的复杂关联(如图2所示)，利用基于力导引的布局方法(节点-链接图)、图简化技术(K-means聚类、基于图拓扑的鱼眼变换技术、图过滤和边绑定技术)以及图可视化中的交互设计(焦点+上下文技术、平移和缩放技术、全局+细节的技术以及交互式动态过滤)。采用本发明方法能够解决在表示复杂关联时容易因边的交叉而导致视觉混乱的问题，突出重点监管对象、全面地展现关联信息，从而可有效地辅助分析人员制定决策。该方法的具体操作步骤为：

A.针对关联数据，将关联数据的层次信息投影到层次关系树中，通过节点的选择或者

导航区的筛选，得到焦点；具体实施方式是：

对农产品子图U’按照专家知识提取农产品层次关系树(如:水果→核果类水果→油桃)，分为水果和蔬菜两个大类；将上述所获得层次关系树对应映射至树展示区，该树支持动态展开与收缩，采用树节点名称展示U’中元素名称，树中节点大小表示该子类下属的农产品数目，例如，数目越多，节点颜色越接近红色，否则则接近绿色(如图4以及图3中A、B区所示)；选中节点，则可获取当前用户关注焦点fu。

B.根据A所得的焦点，生成关联描述视图；处理步骤具体为：

B1.获取当前关注农产品焦点fu，以红色边框标注；计算与当前焦点关联的农药子图V，得到关联边集合E₁；获取农药化学成分属性(如:有机氮类农药)，计算不同成分农药在该农产品中残留的占比，并用圆环实现可视化；

B2.计算与B1中V关联的其他农产品所构成的子图U’，得到关联边集合E₂，进而满足>

B3.根据关联边集合E₁，E₂，基于力导向布局连接fu，V，U’图中相应节点，构成新的二部图G’，其中力中心根据圆环圆心位置进行初始设置和调整；其中力导向布局(Force-directed>

B4.将二部图G’中的农产品部与农药部分别可视化为圆形与矩形视觉元素，以加以显示区分，更好地体现二者关联；计算G’中所有农产品节点的农药检出品种数及频次，并根据其值分别可视化映射为农产品节点的颜色(插值)和大小，所检出的农药品种数值越大农产品节点越接近红色颜色，所检出频次越多，节点越大；获取农药毒性，则农药节点的矩形边框颜色将根据毒性(如:剧毒、高毒、中低毒)不同而有所不同(如：红、深橘、黄)；

B5.在B4所得的视图(如图5(a)所示)基础上通过鱼眼变形函数实现对普通视图中各节点坐标的变换，至此得到子视图(如图5(b)所示)。

基于图拓扑的鱼眼变换技术(鱼眼变形函数)是另一种有效的图简化方法，该类方法可以产生类似摄影中鱼眼镜头的效果。鱼眼镜头是一种广角镜头，其拍摄所得效果近似于将图像径向扭曲变形，因此经此变换的可视化结果的特点是将焦点信息放大，而焦点周围的上下文信息则相对逐渐缩小，从而达到突出重点、兼顾周边信息的视觉效果。将鱼眼视图扩展到图(Graphs)的可视化，即扩展为图中的鱼眼视图。图中的鱼眼视图中，鱼眼视图中顶点的位置取决于它在变换前的普通视图中的位置以及它与当前焦点的距离；鱼眼视图中顶点的大小取决于它与焦点的距离以及它在普通视图中的大小，以及它的先验关注度；而在一个顶点中可显示的细节的数量则取决于其在鱼眼视图中的大小。

B6.本步为可选步骤，以展示具体农产品中的农药检出含量分布(如:1-5ug/kg；5-10ug/kg):双击钻取农产品子视图(如图5(b)所示)中农产品节点u，则计算该农产品中的各种农药v的检出含量分布，将节点以donut圆环代替圆形来可视化分布，得到变换后的关联描述子视图(如图5(c)所示)。

B7.本步为可选步骤，以能够满足高效展现农产品样品中所检出的农药品种数在一定范围内的农产品名称的任务T3:以农产品中所检出农药种数为权重动态过滤(如图3 E区所示) 与生成图，并在该子图中过滤掉关联边集合E₂，以突出关注对象(如图5(d)所示)。

C.根据A所得的焦点，生成关联探索视图；操作包括的步骤具体为：

C1.首先，获取A所得的焦点的关联数据属性及其所属分类，用交互式放射环展示层次关联，并可根据其化学成分进行动态过滤；

C2.根据农药与农产品节点间的关联关系，确立待聚类的农药对象数据点.针对农药节点vk(k＝1，2，...，m，m为农药节点个数)以及农产品序列u1，u2，u3，...，un(其中n为农产品样品个数)，定义如下:若农药vk在农产品ul(l＝1，2，...，n)中被检出，则对应检出标识ukl取值为1，否则为0，则对于任意一个农药节点vi都存在一个检出向量(ui1，ui2，ui3，...，uin)；

C3.根据检出向量计算WSS(Within Sum of Square，内平方和)，WSS为所有待聚类点与各个最近质心之间距离的平方和的大小。确立K-means聚类中的K的个数(如图6所示)，此处最优聚簇的数量为3；

C4.通过计算农药节点vi，vj(其中i，j＝1，2，...，m，m为农药节点个数)之间的欧式距离，进行K-means聚类(K为C3所得结果)，得出聚类向量(如图7所示)，该向量指出农药节点的聚类簇编号。

C5.将C4的聚类结果以圆形节点簇的形式置于放射环的根节点区域内，每个圆代表一个农药节点，基于力导向布局将各个圆根据聚类结果组成各个簇，使得相同簇节点之间距离较近，不同簇之间以不同颜色进行标注(如图8(a)所示)，以圆形节点的边框颜色代表农药毒性，根据簇中节点个数决定圆形节点半径的大小(如图8(b)所示)，实现对结果的概览展示.并辅助以字云形式自动加载对应农药名称，其颜色和簇颜色相对应(如图9所示)；

C6:通过视图切换和层次边绑定展示层次结构中的潜在关联细节(具体的农药名称，归属同一簇的农药，具体农药毒性)，并可根据节点及关联边数目调整绑定边的张力系数(如图3D 区及图10所示)；

利用上述农残数据关联可视分析方法实现系统PestResiTGVis，该系统能够实现本技术方案所述方法，完成关联数据结构展示、数据关联描述、数据关联探索等功能。

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