1.一种基于子图同构的web数据自动可视化方法,其特征在于,所述方法包括以下步骤:
第一步:构建服务数据可视化建模与匹配方法的架构,包括三个模块:数据建模、图形建模和降维匹配;
第二步:定义元数据树MDT,包括根节点TRoot、索引节点INode、数据节点DNode,同时用深度level来表示节点在树结构中的层数,根节点默认为第一层,即level=1;
第三步:读取调用的REST API所返回的JSON数据,将JSON数据集ds作为建模算法的输入,对ds进行树形结构建模;
第四步:由于JSON数据集中存在批量数据,批量数据以相同的数据结构形式存在,在数据集中数组的形式表现;若是用户的对于JSON数据分析的重点不在于数据的定位、查询,而是针对数据结构的分析,在上述JSON数据解析建模的方法基础上,可以通过剪枝的方法,保留数据结构信息,剪除相同的重复数据结构,缩小模型的体量,但仍然保留数据结构,降低JSON数据结构所带来的查询开销;
第五步:对可视化图形进行分类,归纳总结各类图形的属性及结构特征,通过建模创建一种可视模型树VT,来形式化地表述各类图形信息;
第六步:子图同构是一个在查询图中查找查询子图,判断查询图中是否包含了查询子图的问题;先用降维方法对MDT进行降维操作,生成元结构树MST,再将可视模型树VT与MST进行匹配查询,调用基于子图同构的匹配方法查找MST中与VT的各个StructModel匹配的片段,并根据Mapping信息进行数据映射,生成可视化图形。
2.如权利要求1所述的基于子图同构的web数据自动可视化方法,其特征在于,所述第一步的过程如下:
1.1、数据建模:从Internet获取的REST服务经解析器解析后进行注册,存储于缓存cache或数据库Database中,自动调用后所获取的基于JSON的REST服务数据,通过服务数据建模将服务数据转变为标准化模型,并抽取出主要数据结构生成元数据树MDT;
1.2、图形建模:对多种配置型可视化工具所支持的图形进行数据结构分析与归纳,整理出主要图形的通用数据结构及数据映射关系,再根据上述信息进行可视化图形建模,创建描述性可视模型VT;
1.3、降维匹配:调取数据建模所生成的MDT,通过降维算法对其进行结构降维,获得包含源数据基础数据结构的元结构树MST,然后通过VT解析器提取出VT中的图形结构模型,在MST中使用基于子图同构的匹配算法来搜索与图形结构模型匹配的数据结构片段,最后输出源数据可生成的图形种类及MST中的匹配片段;
1.4、图像生成:根据所属1.3输出的图形种类及MST中的匹配片段,将其按照VT解析器提取出的映射关系通过映射处理器来自动化生成可视化图形。
3.如权利要求1或2所述的基于子图同构的web数据自动可视化方法,其特征在于,所述第二步的过程如下:
2.1、根节点:MDT的根节点,即MDT的起始节点;
2.2、索引节点:代表JSON数据中每一个关键字KEY,但不包括JSON数据中最内层的“键-值”对的关键字,索引节点为非根节点、非叶子节点;
2.3、数据节点:代表JSON数据中最内层的“键-值”对,存储为叶子节点;
所述2.1中,所述根节点内包含以下信息:
2.1.1、星标isMark:记录JSON数据中最外层结构是否为数组类型,若是用1标记,若否用0标记;isMark形式化定义表述如(1)(2),isMark的数据类型为数字NUMBER,若JSON数据中“键-值”对中的值VALUE为数组ARRAY,则isMark=1,否则isMark=0;“#”为数据类型定义符,“::=”为赋值符,〖A→condition⊕:
(1)、“isMark”#
2.1.2、元素数量arrayNum:若当前节点的isMark为1,则记录数组元素个数,若当前节点的isMark为0,则用0标记;arrayNum形式化定义表述如(3)(4),arrayNum属性值为数字NUMBER类型,若JSON数据中“键-值”对中的值VALUE为ARRAY,则arrayNum等于VALUE数组的长度,否则arrayNum=0;
(3)、“arrayNum”#
2.2.1、节点名称name:name的数据类型为字符串STRING,name属性值为JSON数据中“键-值”对中的关键字KEY;name形式化定义表述如(5)(6);
(5)、“name”#
(6)、“name”::=
2.2.2、节点值类型vType:vType是JSON数据中“键-值”对中的值VALUE的数据类型,属性值为对象OBJECT、数组ARRAY、字符串STRING、数字NUMBER、TRUE、FALSE之一;vType形式化定义表述如(7);
(7)、“vType”::=[OBJECT|ARRAY|STRING|NUMBER|TRUE|FALSE]
2.2.3、星标isMark:记录JSON数据中,以当前节点名称name作为关键字的“键-值”对中的值VALUE是否为数组类型,若是用1标记,若否用0标记;isMark形式化定义表述同步骤
2.1.1中的(1)(2);
2.2.4、元素数量arrayNum:若当前节点的isMark为1,则记录“键-值”对中的值VALUE的数组元素个数,若当前节点的isMark为0,则用0标记;arrayNum形式化定义表述同步骤
2.1.2中的(3)(4);
所述2.3中,所述数据节点内包含以下信息:
2.3.1、节点名称name:保存JSON数据中“键-值”对中的关键字KEY,数据类型为字符串STRING;name形式化定义表述同步骤2.2.1中的(5)(6);
2.3.2、节点值nValue:nValue的数据类型为STRING,属性值为JSON数据中“键-值”对中的值VALUE;nValue形式化定义表述如(8)(9);
(8)、“nValue”#
2.3.3、节点类型type:保存JSON数据中“键-值”对中的值VALUE的数据类型,为“str”、“num”或NULL,其中“str”代表type的数据类型为STRING,“num”代表type的数据类型为NUMBER,NULL表示type的属性值为空;type形式化定义表述如(10);
(10)、“type”::=[“str”|“num”|NULL]。
4.如权利要求1或2所述的基于子图同构的web数据自动可视化方法,其特征在于,所述第三步的步骤如下:
3.1、创建一棵根节点为TRoot的MDT,TRoot是起始节点,根节点的深度level默认为1;
3.2、读取JSON数据集ds,如果是首次读取ds,设置ds的第一个元素为当前元素,元素包括关键字KEY及其值VALUE;否则设置ds的下一个元素为当前元素;若JSON数据最外层就是ARRAY,则TRoot的isMark=1,元素数量arrayNum为ARRAY元素个数。
5.如权利要求4所述的基于子图同构的web数据自动可视化方法,其特征在于,所述步骤3.2的过程如下:
3.2.1、若VALUE的数据类型非OBJECT,同时非ARRAY,创建深度为level+1的数据节点,节点名称name为关键字KEY,节点值nValue为值VALUE,节点类型type为值VALUE的数据类型;完成后跳转至步骤3.2;
3.2.2、若VALUE的数据类型为ARRAY,创建深度level’=level+1的索引节点,节点名称name为关键字KEY,节点值类型vType为ARRAY,isMark=1,元素数量arrayNum为当前VALUE数组中的元素个数;
3.2.2.1、若所述3.2.2中的VALUE数组的元素不是OBJECT类型,则创建level”=level’+1的数据节点,节点名称name为关键字KEY,节点值nValue为值VALUE,节点类型type为值VALUE的数据类型;完成后跳转至步骤3.2;
3.2.2.2、若所述3.2.2中的VALUE数组的元素是OBJECT类型,则创建level”=level’+1的索引节点,节点名称(name)为每个OBJECT元素中的关键字KEY,节点值类型vType为每个OBJECT元素中的值VALUE的数据类型;若当前vType为ARRAY,则isMark=1,元素数量arrayNum为当前VALUE数组中的元素个数;若当前vType不为ARRAY,则isMark=0,arrayNum=0;
3.2.2.3、将步骤3.2.2.2中VALUE数组作为新的JSON数据集ds’,跳转至步骤3.2;
3.2.3、若VALUE的数据类型为OBJECT,创建深度level’=level+1的索引节点,节点名称name为每个OBJECT元素中的关键字KEY,节点值类型vType为每个OBJECT元素中的值VALUE的数据类型;若当前vType为ARRAY,则isMark=1,元素数量arrayNum为当前VALUE数组中的元素个数;若当前vType不为ARRAY,则isMark=0,arrayNum=0;
3.2.4、将步骤3.2.3中VALUE数组作为新的JSON数据集ds’,跳转至步骤3.2。
6.如权利要求1或2所述的基于子图同构的web数据自动可视化方法,其特征在于,所述第四步的步骤如下:
4.1、从level=1的TRoot开始,按广度优先策略,按层遍历MDT的根节点与索引节点;广度优先策略将按level逐层遍历MDT,从level=1的第一层开始遍历,当level层的节点遍历完成后,再继续遍历level+1层的节点;
4.2、将MDT的TRoot存入遍历队列;
4.3、按遍历队列顺序,读取每个节点的isMark属性;过程如下:
4.3.1、若遍历到的节点的isMark属性值为1,则保留当前节点的第一个子节点,剪除其余的子节点及其子节点的子树结构,跳转至步骤4.3.4;
4.3.2、若遍历到的节点的isMark属性值为0,则不进行任何操作,跳转至步骤4.3.4;
4.3.3、若遍历到的节点为数据节点,将当前节点从遍历队列中删除,跳转至步骤4.3;
4.3.4、将当前遍历到的节点的子节点加入遍历队列,并将当前节点从遍历队列中删除,再跳转至步骤4.3;
4.4、当遍历队列中全部为数据节点时或遍历队列为空时,停止遍历,结束方法;
4.5、输出剪枝后的MDT。
7.如权利要求1或2所述的基于子图同构的web数据自动可视化方法,其特征在于,所述第五步的过程如下:
5.1、定义VT包括基础属性BASICATTRIBUTE和可视结构DVSCHEMA两个部分,形式化定义如(11),其中BASICATTRIBUTE保存了图形标题和副标题;
(11)、VisualModel::=
5.2、BASICATTRIBUTE包括三个属性:标题title、子标题subtitle、属性attributes,形式化定义如(12),title用于保存最终生成的可视化图形的标题,subtitle用于保存最终生成的可视化图形的子标题,attributes用于保存最终生成的可视化图形的位置、颜色组合、字体、字号设置参数;
(12)、BASICATTRIBUTE::=
5.3、BASICATTRIBUTE根据图形所需的数据类型、图形数据结构、图形维度将常见的可视化图形归纳为四种基础类别:一般图形General、拓扑图Topology、地图Map、文本图形Text,形式化定义如(13);
(13)、DVSCHEMA::=
5.4、步骤5.3中的四种基础类别下属均分别包含两个属性:图形类型VType和图形结构StructModel,VType保存了该类别所属图形种类,StructModel保存了该类别所属图形的可视化结构,形式化定义如(14),“A::B”表示“A包含了属性B”;
(14)、DVSCHEMA::=
5.4.1、General包括柱状图BarChart、折线图LineChart、饼图PieChart、雷达图RadarChart、散点图ScatterChart;
5.4.2、Topology包括网络图NetworkChart、树图TreeMap、面积树图TreeMapChart;
5.4.3、Map包括地区地图AreaMapChart、国家地图CountryMapChart、世界地图WorldMapChart;
5.4.4、Text包括词云WorldCloudChart;
5.5、步骤5.4中四种基础类别均有各自的映射关系Mapping,描述了各类图形的数据结构、数据维度、图形结构关系、数据映射位置信息;根据Mapping信息并结合图形的数据结构,可以抽象出各类图形的可视化结构StructModel,步骤三中所生成的MDT将与StructModel进行匹配,来判断REST API的返回数据能够生成何种可视化图形。
8.如权利要求7所述的基于子图同构的web数据自动可视化方法,其特征在于,所述步骤5.5的过程如下:
5.5.1、General类型中的图形通常用于表示二维数据或三维数据,可用二元组(XAxis,YAxis)或三元组(XAxis,YAxis,ZAxis)来表示信息,此类图形的Mapping结构如(15),其中LegendName表示图例名称,以ARRAY类型来存储各分组信息;根据Mapping结构可抽象出基础StructModel的结构如(16),StructModel的子节点为临时根节点Root,Root包含两个子节点:键值对K_V与图例节点LegendNode;
(15)、Mapping::=
5.5.2、Topology类型中的图形通常用于表示拓扑关系数据,树图与面积树图可用嵌套的键值对{key:value,children:{key:value}}来表示属性结构,Mapping结构如(17);网络图可用节点集合Nodes和边集合Links来表示图结构,Mapping结构如(18),其中source表示一条边link的起始节点,target表示该条边link的指向节点;根据Mapping结构可抽象出基础StructModel的结构如(19),StructModel有两个子结构,Root1和Root2分别为两个子结构的临时根节点,Root1包含两个子节点:键值对K_V和孩子节点children,children的子结构为键值对K_V;Root2包含两个子节点:节点集合Nodes和边集合Links,节点集合的子节点为关键字key和值value,其中value为空,边集合的子节点为起点source和目标target;
(17)、Mapping::=
5.5.3、Map类型中的图形用于表示地图信息,用键值对数组[{PlaceName:value}]或三元组数组[{lng,lat,value}]来表示地图信息,此类图形的Mapping结构如(20),其中PlaceName表示地名,lng表示纬度,lat表示经度;根据Mapping结构可抽象出基础StructModel的结构如(21),StructModel有两个子结构,Root1和Root2分别为两个子结构的临时根节点,Root1包含子子节点键值对K_V;Root2包含了三个子节点:经度lat,纬度lng,数值value;
(20)、Mapping::=
5.5.4、Text类型中的图形常用二元组(Keyword,frequency)来表示关键字频率,此类图形的Mapping结构如(22),其中Keyword为文本中提取出的词汇,frequency表示该词汇在文本中的出现频率;根据Mapping结构可抽象出基础StructModel的结构如(23),StructModel的子节点为临时根节点Root,Root包含了键值对K_V;
(22)、Mapping::=
9.如权利要求1或2所述的基于子图同构的web数据自动可视化方法,其特征在于,所述第六步的过程如下:
6.1、定义元结构树MST,包括子树根节点STRoot、子结构Substruct,形式化定义如(24),MST用于保存降维后的MDT;其中子结构Substruct由引导节点GNode和数据节点LNode两部分构成,形式化定义如(25);根节点STRoot内包含的信息同2.1.1至2.1.2;引导节点GNode内包含的信息同2.2.1至2.2.4;叶子节点LNode内包含的信息同2.3.1至2.3.3;同时用深度(level)来表示节点在树结构中的层数,STRoot默认为第一层,即level=1;
(24)、MST::=
6.2、解析VT中四种基础类别的StructModel,提取每种StructModel中的临时根节点及其子结构,每一个临时根节点及其子结构构成的树结构片段将作为查询子图,根据步骤
5.5.1至5.5.4可以提取出六个查询子图:General类型的StructModel的下属Root为起点的子结构,Topology类型的StructModel的下属分别以Root1和Root2为起点的两个子结构,Map类型的StructModel的下属分别以Root1和Root2为起点的两个子结构,Text类型的StructModel的下属Root为起点的子结构;
6.3、定义基于子图同构的匹配方法Match(MST),以MST作为输入,将步骤6.2中的六个查询子图用StructModelk表示,与每个StructModelk同属于一个大类,即General、Topology、Map、Text之一的VType用VTypek表示;
6.4、基于子图同构的降维匹配算法通过对MDT进行降维操作生成MST后,调用步骤6.3中定义的基于子图同构的匹配方法Match(MST)进行自动化匹配,将MDT作为输入,最后输出源数据可生成的图形种类及MST中的匹配片段;
6.5、根据Match(MST)方法输出的匹配片段从源数据中提取数据,并将数据根据Mapping结构映射到输出的对应类型的图形结构中,从而生成可视化图形。
10.如权利要求9所述的基于子图同构的web数据自动可视化方法,其特征在于,所述步骤6.3的过程如下:
6.3.1、按照广度优先策略,按层遍历MST,将MST的节点从STRoot开始,按层数从小到大的顺序,将STRoot和所有GNode存入遍历队列Q;
6.3.2、设置节点s为StructModelk的根节点;
6.3.3、按遍历队列Q的顺序,将当前Q中遍历到的节点xi与节点s进行比较,判断xi与s的isMark属性值是否相等;
6.3.3.1、若xi与s的isMark属性值相等,将xi加入集合P,设置i=i+1,跳转至步骤
6.3.3;
6.3.3.2、若xi与s的isMark属性值不相等,设置i=i+1,跳转至步骤6.3.3;
6.3.4、当Q遍历完成后,遍历集合P中的节点pj,判断pj与s的父子节点关系是否一致;
6.3.4.1、若pj与s的父子节点关系不一致,设置j=j+1,跳转至步骤6.3.4;
6.3.4.2、若pj与s的父子节点关系一致,将pi加入集合M,跳转至步骤6.3.5;
6.3.5、判断集合M与StructModelk的结构是否一致;
6.3.5.1、若M与StructModelk的结构一致,输出集合M和StructModelk对应的VTypek;清空集合P,设置k=k+1,设置xi为Q的第一个节点,跳转至步骤6.3.2;
6.3.5.2、若M与StructModelk的结构不一致,将s设置为它在StructModelk中的下一个节点,清空集合P,设置k=k+1,设置xi为Q的第一个节点,跳转至步骤6.3.3;
6.3.6、当六个查询子图均完成查询后,结束方法Match(MST),输出源数据可生成的图形种类VTypek及MST中匹配片段的集合M;
所述步骤6.4的过程如下:
6.4.1、按照广度优先策略,按层遍历MDT,将MDT的节点从TRoot开始,按层数从小到大的顺序,将TRoot和所有INode存入遍历队列L;
6.4.2、按遍历队列L的顺序,对当前遍历到的节点ma的isMark属性和m的子节点的type属性进行判断,是否符合isMark=1且type=”num”;
6.4.2.1、若isMark=1且type=”num”,将ma加入集合S,设置a=a+1,跳转至步骤6.4.2;
6.4.2.2、若不符合isMark=1且type=”num”,设置a=a+1,跳转至步骤6.4.2;
6.4.3、当L遍历完成后,按集合S中节点加入顺序的逆序来遍历集合S,当前遍历到的节点用nb表示;
6.4.4、如果在S中没有其他节点与nb有相同的父节点,将nb和它的子结构存储为临时子树subtree,将subtree加入MST,作为STRoot的子结构,再从MDT中剪除subtree,并将nb从集合S中删除,调用步骤6.3中定义的基于子图同构的匹配方法Match(MST),跳转至步骤6.5;
6.4.5、如果在S中存在其他节点与nb有相同的父节点,将nb加入集合U;
6.4.6、按顺序遍历集合U,对遍历到的节点uc的arrayNum属性值进行判断;
6.4.6.1、若arrayNum>2,将uc和它的子结构存储为临时子树subtree,将subtree加入MST,作为STRoot的子结构,再从MDT中剪除subtree,并将uc从集合U中删除,调用步骤6.3中定义的基于子图同构的匹配方法Match(MST),跳转至步骤6.5;
6.4.6.2、若arrayNum<=2,在U中查找出其他的arrayNum<=2节点d,将uc的父节点、uc、d、uc的子节点、d的子节点存储为总层数为3的临时子树subtree,若subtree与Topology类中StructModel的两个子结构之一结构相同,则将该subtree存入MST,以uc的父节点为STRoot,再从MDT中剪除subtree,并将nb和d从集合U与S中删除,调用步骤6.3中定义的基于子图同构的匹配方法Match(MST),跳转至步骤6.5;
6.4.6.3、若arrayNum<=2,在U中没有其他的arrayNum<=2节点,将uc和它的子结构存储为临时子树subtree,将subtree加入MST,作为STRoot的子结构,再从MDT中剪除subtree,并将uc从集合U中删除,调用步骤6.3中定义的基于子图同构的匹配方法Match(MST),跳转至步骤6.5。