一种面向近似查询处理的和积网络与残差神经网络混合模型

摘要

本发明属于数据分析技术领域，具体为一种面向近似查询处理的和积网络与残差神经网络混合模型。本发明包括两个模块：基于和积网络的无监督学习模块，针对数据集的不同样本，训练多个相互独立的和积网络模型来捕捉数据的整体分布规律，每个和积网络模型等价于原始数据集的一个密度估计器，可以通过该模型计算出聚合查询的近似结果；基于残差神经网络的监督学习模块，针对一个给定的查询，将该查询在训练好的多个和积网络中预测出的查询结果以及和积网络预测过程中的特征向量作为输入，用查询的真实结果作为标签训练深度神经网络，当用户查询输入时，该模型能够输出经过校正后具有更高准确性的近似查询结果。本发明在大幅降低查询执行时延的同时提供具有较高准确性的近似查询结果。

说明书

技术领域

本发明属于数据分析技术领域，具体涉及数据分析中的查询优化处理系统。

背景技术

当数据分析人员针对大规模数据集进行交互式探索分析时，在数据库中执行精确查询的时延很长。例如，在一个包含五亿行数据记录的航班延误数据表(约43GB)上执行一个简单COUNT查询耗时约为2分钟32秒，这在交互式场景下是用户难以接受的，过长的查询等待时间会超出用户的忍耐范围，严重影响分析的效果和行为决策。

为了降低此类查询延迟，一系列基于采样的近似查询处理方法被提出。BlinkDB提出了一个从原始数据中构建分层样本的方法，它基于查询的准确性和响应时间要求动态地选择样本构建策略；JinglinPeng等人提出AQP++，将采样方法与数据立方体预计算技术相结合，提高了近似查询的准确性；微软在2016年提出了Sample+Seek在采样的基础上针对查询选择性低的数据构建辅助索引来提高准确性。然而，这些基于采样的近似方法都不具备较强的可扩展性，即当数据量增大时需要更多的数据样本来保证采样方法的准确性，由此带来了更长的查询时延和更大的存储空间占用，无法应对日益增长的数据规模需求。因此，如何为用户提供一种更加快速、轻量、准确的大数据近似查询处理方法是一个亟待解决的重要问题。

发明内容

为了解决上述问题，本发明的目的在于提供一种针对大规模数据集的查询速度更快、准确性更高、占用存储空间更小的面向近似查询处理的和积网络与残差神经网络混合模型，使用训练好的机器学习模型来代替数据样本执行近似查询。

本发明提供的面向近似查询处理的和积网络与残差神经网络混合模型，主要包含两个模块：基于和积网络的无监督学习模块和基于残差神经网络的监督学习模块，其中：

(一)基于和积网络的无监督学习模块，该模块使用和积网络模型(H.Poon andP.Domingos,“Sum-product networks:A new deep architecture,”in 2011 IEEEInternational Conference on Computer Vision Workshops(ICCV Workshops),Barcelona,Spain,Nov.2011,pp.689–690.)构建数据集的多个密度估计器，用以针对常见的SPJA查询(SPJA查询是指SELECT子句中包含聚合运算符的Select-Project-Join(SPJ)查询)计算出近似结果。该模块中：

在离线学习阶段，首先针对一个给定的数据集，使用用户指定的采样率随机生成多个数据样本；接着针对每个数据样本分别训练一个混合型和积网络，混合型和积网络是面向混合类型属性的概率模型，每个和积网络依据对应数据样本学习到数据集的分布规律，最终得到多个基密度估计器；

在在线预测阶段，当用户查询输入时，对用户的SPJA查询进行解析后转换为概率表达式，训练好的和积网络模型通过模型推断计算出该表达式的结果，得到对该查询的预测值；

该模块使用机器学习模型代替前述其他方法中的数据样本进行近似计算，基于模型的方法通过模型推断执行计算，比针对样本的查询速度更快；只需存储模型参数，所需存储空间大幅减少；模型推断速度和存储空间占用与数据规模呈现出次线性关系，具备良好的可扩展性。

(二)基于残差神经网络的监督学习模块，该模块是带有残差结构的深度神经网络，它将前述多个和积网络模型进行集成，融合其学习到的数据分布信息，以对和积网络的预测结果进行准确性校正；该模块中：

在离线学习阶段，按照SPJA查询模板生成大批查询(即训练数据)，针对每个查询，前述多个和积网络模型都将计算得到多个预测值，将该查询在训练好的多个和积网络中预测的查询结果、和积网络预测过程中的特征向量作为输入，用查询的真实结果作为标签，训练深度神经网络；

在在线预测阶段，用户输入的查询依次经过前述和积网络模型和上述训练好的神经网络模型中，最终输出校正后准确性更高的查询预测结果；

前序实验表明，基于和积网络的单个基密度估计器的误差主要来源于选择性较低的查询，这部分查询对应元组较少，在数据样本中易被忽略，本模块通过残差神经网络将多个基密度估计器学到的信息进行融合，使得网络捕捉到的原始数据分布信息更全面，以此来提高查询的预测准确性。

本发明中，训练时使用的数据样本依据原始数据分布特征选取特定的采样方法，根据用户的空间和时间开销预算选取恰当的采样率及样本数量；所构建的基密度估计器基于混合型和积网络模型，和积网络模型自底向上地执行推断以计算数据的概率分布；同时，所训练的残差神经网络模型由编码器层(encoder)、融合层(fusionlayer)以及解码器层(decoder)组成。

构建多个和积网络使用的数据样本的生成：依据原始数据集的整体分布特征选取特定的采样方法，对分布均匀的数据进行随机均匀采样，对分布偏斜的数据进行分层采样或加权有偏采样。同时根据用户的空间开销预算选取恰当的样本数量，提高资源利用效益。由于数据样本训练完模型后不需要持久化存储，因此只需要考虑所生成的模型消耗的空间资源即可；有结论表明，在本发明的实验设置中，单个模型占用的存储空间大小S与数据集的属性个数m呈近似线性关系，即S＝Cm，其中C为可通过实验度量的常数，给定用户空间开销B，最多可容纳的模型数量为n，有nCm≤B，即

由数据样本构建和积网络模型时，完整数据集按照行和列递归分解，以加快模型推理速度。每轮递归分解操作中，共分为三种情况：

(1)若当前节点的数据中包含多个列属性，则先依据RDC相关系数计算列与列之间的相关性，并按照相关程度分组，分解相关度低的列属性，并将分解后的数据簇使用乘积节点连接；

(2)若当前节点的数据记录条数超过指定阈值，则使用K-Means算法对数据记录按行进行聚类，每个数据簇使用求和节点连接；其中阈值大小一般取为n

(3)若当前节点的数据中只涉及一个列属性，且数据记录条目小于指定分解阈值，则返回该列属性上的一个单变量分布，构成一个叶子节点。

本发明中，和积网络模型对查询的预测转化为自底向上的概率和期望计算实现，针对一张关系型数据表R(即按照行和列存储的二维表格)，其转化过程为：

(1)针对形如SELECT COUNT(*)FROM R WHERE filter的查询，其结果可表示为

(2)针对形如SELECT AVG(A)FROM R WHERE filter的查询，其中A为需要在其上执行聚合查询的属性，该查询可表示为

(3)针对SUM查询，其可以表示为COUNT*AVG，由前述(1)、(2)方法可通过执行两次模型推断计算得到结果。

本发明中，和积网络模型基于数据本身学习，与其他基于查询学习的模型相比，更能适应工作负载的变化，树状结构也使得数据更新更加便捷，健壮性强。

本发明中，残差神经网络模型由编码器层(encoder)、融合层(fusionlayer)以及解码器层(decoder)组成，具体结构如图1所示，其中：

(1)编码器层：

编码器层由六层全连接神经网络组成，其任务是对多个和积网络模型的输出进行单独编码和表征；残差神经网络的输入包括多个和积网络模型的预测值和和积网络模型推断过程中提取出的特征向量，该特征向量可以表征给定模型在给定查询下的一个特定状态，该状态既包含模型本身学习到的数据分布信息，又包含查询对应的特征信息，能够为残差神经网络提供更多可学习的信息；实施例中，和积网络的默认数量为3，每个和积网络的特征向量(其维度与网络节点数相同)输入相应的编码器层后经过特征提取和压缩映射到相同维度的向量空间(512维)；

(2)融合层：

融合层由两个线性层(处理输入输出)和四个残差块组成，其将编码器层的输出融合后输入到带有残差结构的全连接神经网络，以学习到更全面的数据分布特征；全连接神经网络呈现出很好的向量表征能力，同时模型轻量、推断速度快；在模型训练过程中添加残差块，能够保护信息的完整性，通过将输入直接传递给输出来减少传播过程中的信息丢失；如图1所示，一个残差块包括一个512维的线性层和一个ReLU激活函数；

(3)解码器层：

解码器层由六层全连接神经网络组成，其任务是将前两层输出的特征向量作为输入，并拟合和积网络的预测结果、特征向量与真实查询结果之间的关系，从而能够针对给定的查询输入预测真实的查询结果；在网络的末端添加了残差结构以限制误差的大幅波动，多个和积网络预测的初步结果的均值作为指导被输入到解码器层，使得解码器层学习的是一个残差分布而不是完整的输出，网络的学习目标得以简化且易于训练，以此获得准确性更高的预测结果；解码器层将融合层的输出(512维)进行非线性变换，最终输出一维的预测值。

本发明的和积网络与残差神经网络混合模型具有如下优势：

可帮助数据分析人员在对大规模数据集进行交互式探索分析时，通过构建基于机器学习的数据分布模型，将常用SPJA查询转换为针对模型的推断计算，避免了在原始数据库上执行精确查询的高延迟，更快速的获得查询的响应结果，以提升用户体验，提高决策的有效性。实验结果表明，本发明在具有数亿条数据记录的大型数据集上执行一条聚合查询可达到亚秒级响应时间(从2毫秒到低于500毫秒)，同时保持较低的误差水平。

附图说明

图1为本发明面向近似查询处理的和积网络与残差神经网络混合模型的架构图。

图2为本发明中基于和积网络的学习流程示意图。

图3为用户通过使用该模型从进行查询直至获得结果的流程图。

图4为本发明在Flights数据集上的查询准确性对比图。

图5为本发明在Flights数据集上的查询时延对比图。

具体实施方式

下面通过一个常用的探索性分析数据集来进一步介绍本发明，并将其与基于采样的近似查询处理方法比较以体现其优势。对该数据集的介绍如下：

Flights数据集：是一个美国航班延误数据集，包含航班的延误时间、载客量等统计信息，包含六个类别型属性和六个数值型属性。本发明中Flights数据集使用IDEBench方法(一种数据扩增方法)扩增到5亿条数据元组。

图3展示了使用基于采样的近似方法和基于本发明回答用户查询的流程对比。数据分析人员与数据分析工具进行交互，执行交互查询时，对于基于采样的近似方法，该查询先被重写为针对样本的计算，通过构建好的样本进行预测后将近似结果返回到数据分析工具；对于本发明，该查询先被重写为针对模型的概率表达式，模型执行推断后将近似结果返回到分析工具。实验中：

对于和积网络模型的训练，原始数据集为包含5亿条元组的Flights数据，按1％采样率采样得到三个数据样本，基于这三个样本按照前述方法分别训练一个和积网络模型；

对于残差神经网络的训练，针对Flights数据集生成120000条SPJA查询，并使用前述和积网络模型得到初步预测结果和和积网络的特征向量，其中100000条数据作为训练集，20000条数据作为验证集。

测试时，在Flights数据集上对RandomSampling-based(基于随机采样的近似查询方法)、StratifiedSampling-based(基于分层采样的近似查询方法)和本发明进行对比，并使Flights数据集上常用的分析型工作负载(包含10条查询，分别表示为F1-F10)进行测试。

图4中展示了测试工作负载在使用基于随机采样的近似方法、基于分层采样的近似方法和本发明时的相对误差对比。在Flights数据集上，本发明的查询准确性优于其它两种方法，基于本发明的查询的相对误差均在5％以内；而基于随机采样和分层采样的方法上的平均相对误差分别为9.68％和5.22％，且有多条查询的相对误差大于10％。

图5中展示了测试工作负载在使用基于随机采样的近似方法、基于分层采样的近似方法和本发明时的查询时延对比。在Flights数据集上，本发明的查询时延均在50毫秒以内，而基于随机采样和分层采样的近似方法平均查询时延分别是本发明的11倍和64倍，远远超出用户可接受的查询等待时间。因此相比于其它两种基于采样的近似查询处理方法，本发明可以大幅提高聚合查询的响应时间，同时提供具有较高准确性的查询结果。