一种大数据上的均值近似聚集方法

摘要

一种大数据上的均值近似聚集方法，本发明涉及一种大数据上的近似聚集方法。本发明的目的是为了解决现有方法的采样顺序敏感、需要用户参与观测、计算结果精度低的问题。一、在需要进行均值聚集计算的包含M个数据的数据集中随机采一个包含m个个体的样本，求出一个粗略均值和样本标准差；二、用户给定指定的精度，求出满足精度所需要的采样率；三、确定需要进行均值聚集计算的数据集的数据边界，得到一个表示需要进行均值聚集计算的数据集的数据边界的参数；四、将参数传到每一个计算单元内，得到每一个计算单元内的均值；五、将每一个计算单元内的均值进行整合，输出最终结果。本发明用于金融，统计等领域。

说明书

技术领域

本发明涉及一种大数据上的近似聚集方法，应用于金融，统计等领域。

背景技术

现有技术对数据的处理通常采用以下三种方法：

1、基于采样的近似算法。

近年来，很多针对采样过程的近似算法被提出，例如文献([1]、S.Agarwal,B.Mozafari,A.Panda,H.Milner,S.Madden,and I.Stoica.Blinkdb:queries withbounded errors and bounded response times on very large data.InAcm EuropeanConference on ComputerSystems,pages 29–42,2012.)，([2]、L.Sidirourgos,M.L.Kersten,and P.A.Boncz.Sciborq:Scientific data management with bounds onruntime and quality.In CIDR 2011,Fifth BiennialConference on Innovative DataSystems Research,Asilomar,CA,USA,January 9-12,2011,OnlineProceedings,pages296–301,2011.)，([3]、Y.Yan,L.J.Chen,and Z.Zhang.Error-bounded sampling foranalytics on big sparse data.Proceedingsof the Vldb Endowment,7(13):1508–1519,2014.)。其中，文献[2]依据当前的查询选择样本，文献[1]考虑了样本之间的差异情况，文献[3]针对稀疏数据。以先前的查询结果为依据来选取样本，而这种方法有采样顺序敏感的致命的缺点，即不同的采样的顺序会导致不同的聚集结果。

2、在线算法(online-aggregation)。

文献([4]、J.M.Hellerstein,P.J.Haas,and H.J.Wang.Onlineaggregation.AcmSigmodRecord,26(2):171–182,1997.)中首次提出了在线算法。随后的几年，有很多学者又相继提出了后续的算法，如文献([5]、S.Wu,S.Jiang,B.C.Ooi,andK.L.Tan.Distributed online aggregation.Proceedings ofthe VldbEndowment,2(1):443–454,2010.)提出了分布式在线算法，文献([6]、T.Condie,N.Conway,P.Alvaro,J.M.Hellerstein,J.Gerth,J.Talbot,K.Elmeleegy,and R.Sears.Online aggregationand continuous query support in mapreduce.In ACMSIGMODInternationalConference on Management ofData,SIGMOD 2010,Indianapolis,Indiana,Usa,June,pages 1115–1118,2010.)实现了在线模式的map-reduce的持续查询，文献([7]、N.Pansare,V.R.Borkar,C.Jermaine,and T.Condie.Online aggregation forlarge mapreducejobs.Proceedings ofthe Vldb Endowment,4(11):1135–1145,2011.)针对大规模的map-reduce的工作。在线算法是一种高效的处理大数据聚集的算法。这类算法的特点是可以随时停止，用户可以对实验过程进行观测，当聚集结果达到了他们的精度要求时，用户可以选择停止计算。然而，这也是它的一个弊端。在线算法需要用户全程观测聚集过程，这极大地降低了用户体验。此外，这类算法并没有把样本之间的差异考虑其中，因此降低了精度。

3、样本差异的体现。

近年来，有学者提出了一种新颖的重定权值的概率计算方法，SLEV算法([8]、P.Ma,M.W.Mahoney,and B.Yu.A statistical perspective on algorithmicleveraging.Journal ofMachineLearningResearch,1(1):861–911,2013.)。这种算法将平均概率和体现样本间差异的概率结合到一起，用平均概率来调节有偏抽样的概率，因此减小了偏差较大的样本对结果的影响。SLEV算法提出了一种新的概率计算方法。假设一共采样n次，对样本i，其计算时的概率可用如下公式进行计算：prob_i＝α·weight_i+β，其中，α为参数，反映了权值对该样本概率的调节程度，β为常量，值为(1-α)·1/n，weight_i为该样本的权值，所有样本的权值之和为1，这样就保证了所有样本概率和为1。SLEV算法将样本间的差异考虑在内，相对平均抽样，其精度更高。此外，这种计算方法引入了参数，方便对样本的概率进行灵活的调整。

SLEV算法从概率的角度调控了聚集结果。然而，在SLEV算法中，样本间差异的计算只与样本的值有关，且对于不同特点的样本都是采用相同的计算方式，而在正态分布中，不但样本的值不同，概率的差异也很明显，将这种差异考虑在外会导致计算精度降低。

发明内容

本发明的目的是为了解决现有方法的采样顺序敏感、需要用户参与观测、计算结果精度低的问题，而提出一种大数据上的均值近似聚集方法。

一种大数据上的均值近似聚集方法具体过程为：

步骤一、在需要进行均值聚集计算的M个数据集中随机采一个包含m个个体的样本，记为X＝{x₁,x₂,…,x_m}，其中，m的取值范围为200<m<500，用X＝{x₁,x₂,…,x_m}样本集求出一个粗略均值sketch和样本标准差σ；

x_i为第i个个体样本，1≤i≤m，i取值为正整数，m取值为正整数；M取值为正整数；

步骤二、用户给定指定的精度e，根据步骤一求出的样本标准差σ和精度e求出满足精度e的采样率r；

步骤三、根据粗略均值sketch和标准差σ确定需要进行均值聚集计算的数据集的数据边界，得到一个表示需要进行均值聚集计算的数据集的数据边界的参数；

步骤四、将需要进行均值聚集计算的M个数据均分成b份，并存储在不同的计算单元，其中，b的值为10；将采样率r、需要进行均值聚集计算的数据集的数据边界、粗略均值sketch和需要进行均值聚集计算的数据集的数据边界的参数传到每一个计算单元内，得到每一个计算单元内的均值；

步骤五、将每一个计算单元内的均值进行整合，输出最终结果。

本发明的有益效果为：

用一部分有特点的样本来代替整体，同时考虑样本间的差异，用一个较小的样本实现一个高精度的均值计算结果。

实验编号12345均匀抽样99.6321100.17299.799199.726100.138本发明方法100.247100.108100.20699.9992100.238

进行了五组实验，结果显示，即使是在采样次数仅为均匀抽样的三分之一时，本发明求得的均值依然能够满足精度约束0.5，并且大多数情况下本发明的计算结果比均匀抽样好。

1.高精度。

本发明将样本间的差异考虑在内，而不是对所有的样本都采用相同的处理方法，因此精度更高。在此基础上，本发明引用了两种方法对结果进行估计，两种方法互为约束迭代地调整，逐渐逼近真实值，因此又为高精度提供了保障。

2.不需要存储数据。

设定α是权值作用的程度，取值范围为[0,1]。在本发明中，对均值近似聚集结果进行推导，发现它是一个一次函数：f(α)＝k·α+c，其中，k为一个和样本的和，平方和，立方和有关的常数，c为样本的不加任何权重的均值。在本发明中，为了得到这个一次函数，系统并不需要存储样本的值，只需要设定几个变量(如，样本的和，平方和，立方和，等),用于计算这个一次函数中的各个参数。在采样过程中系统对这几个参数进行加减，以此代表所有的样本，因此不需要太多的存储空间。这一特性很好地契合了当今的大数据背景。

3.采样顺序不敏感。

根据上面的分析，系统采样完成后，系统构造出了一个均值的函数，由此对均值进行估计，而不是在采样的过程中对结果进行估计。这一特性使得该方法有采样不敏感的特性，即，采样顺序不会影响到结果。

4.易扩展。

本发明可以扩展为在线模式。在每次计算过程中，系统保存了存储样本信息的变量(和，平方和，立方和)。当前计算完成后，如果用户想在现有基础上继续进行计算，系统可以在这几个参数的基础上对参数进行操作。此外，由流程图可知，本发明易扩展为MapReduce模式。综上，本发明是很灵活易扩展的。

附图说明

图1为本发明具体流程图，Block为块；

图2为本发明五类数据示意图，TS类(too small data)为数据的值很小的值；S类(small data)为数据的值不太大的值；N类(normal data)为数据关于正态分布的中心轴对称，并且该类数据在整个正态分布中占着不小的比例；L类(large data)为数据的值很大，并且有着不小的概率；TL类(too large data)为数据的值明显地大，但概率却异常地小，因此被定义为另一类离群点；σ为样本标准差；μ为均值；P₁为参数；P₂为参数；

图3为本发明中从五类数据中选择S和L类数据的示意图；

图4为本发明粗略均值sketch、加权均值estimation和精确值之间的关系A示意图；

图5为本发明粗略均值sketch、加权均值estimation和精确值之间的关系B示意图。

具体实施方式

具体实施方式一：结合图1说明本实施方式，本实施方式的一种大数据上的均值近似聚集方法具体过程为：

大数据为数据存储量为TB级及以上；

步骤一、在需要进行均值聚集计算的M个数据集中随机采一个包含m个个体的样本，记为X＝{x₁,x₂,…,x_m}，其中，m的取值范围为200<m<500，用X＝{x₁,x₂,…,x_m}样本集求出一个粗略均值sketch和样本标准差σ；

x_i为第i个个体样本，1≤i≤m，i取值为正整数，m取值为正整数；M取值为正整数；

步骤二、用户给定指定的精度e，根据步骤一求出的样本标准差σ和精度e求出满足精度e的采样率r；

步骤三、根据粗略均值sketch和标准差σ确定需要进行均值聚集计算的数据集的数据边界，得到一个表示需要进行均值聚集计算的数据集的数据边界的参数；

步骤四、将需要进行均值聚集计算的M个数据均分成b份，并存储在不同的计算单元，其中，b的值为10；将采样率r、需要进行均值聚集计算的数据集的数据边界、粗略均值sketch和需要进行均值聚集计算的数据集的数据边界的参数传到每一个计算单元内，得到每一个计算单元内的均值；

步骤五、将每一个计算单元内的均值进行整合(相加取平均)，输出最终结果。

具体实施方式二：本实施方式与具体实施方式一不同的是：所述步骤一中在需要进行均值聚集计算的包含M个数据的数据集中随机采一个包含m个个体的样本，记为X＝{x₁,x₂,…,x_m}，其中，m的取值范围为200<m<500，用X＝{x₁,x₂,…,x_m}样本集求出一个粗略均值sketch和样本标准差σ；具体过程为：

粗略的均值sketch计算公式为：

样本标准差σ计算公式为：

其它步骤及参数与具体实施方式一相同。

具体实施方式三：本实施方式与具体实施方式一或二不同的是：所述步骤二中用户给定指定的精度e，根据步骤一求出的样本标准差σ和精度e求出满足精度e的采样率r；具体公式为：

其中，u是和置信度有关的参数，置信度为95％时u为1.96，置信度为90％时u为1.64；M为需要进行均值聚集计算的数据集包含的数据个数，已知数据集大小可以很容易地得到这个值。

在不同的情况下，用户的精度需求是不同的，如，用户对公司员工的工资进行求均值运算的时候，如果只需得到一个大概的值，用户可能会接受5元之内的偏差，但如果用户需要一个高一点的精度的聚集结果，那么此时的精度需求可能就需要达到5角了；

其它步骤及参数与具体实施方式一或二相同。

具体实施方式四：本实施方式与具体实施方式一至三之一不同的是：所述步骤三中根据粗略均值sketch和标准差σ确定需要进行均值聚集计算的数据集的数据边界，得到一个表示需要进行均值聚集计算的数据集的数据边界的参数；具体过程为：

将需要进行均值聚集计算的数据分成5类，分别为TS类、S类、N类、L类和TL类；

其中TS类的范围为：(-∞,μ-P₂σ]；

其中S类的范围为：(μ-P₂σ,μ-P₁σ)；

其中N类的范围为：[μ-P₁σ,μ+P₁σ]；

其中L类的范围为：(μ+P₁σ,μ+P₂σ)；

其中TL类的范围为：[μ+P₂σ,+∞)；

μ为均值，取值为粗略均值sketch，P₁为参数，取值为0.5；σ为步骤一求出的样本标准差，P₂为参数，取值为2。

这种分类方式主要是针对了正态分布中各个区域的数据的特点。在正态分布里，不同位置的元素的大小、概率大不相同，导致了他们对结果的贡献有很大差异。例如，有些数据值很大，同时他们的概率很小(即，离群点)，很难被取到，但一旦采到了这样的元素，聚集结果就会发生明显的变化。上面的五类数据，每一类都有其自身的特点，如图2所示。

1)TS类(too small data)。这样的数据的值很小并且很难被采到，因此看成是一类离群点。在聚集过程中，这样的数据对结果的影响几乎可以忽略不计。

2)S类(small data)。这样的数据的值不太大，但是他们所占的概率并不小。

3)N类(normal data)。这一类数据关于正态分布的中心轴对称，并且该类数据在整个正态分布中占着不小的比例。

4)L类(large data)。这类数据的值很大，并且有着不小的概率。因此在聚集过程中他们有着重要的贡献。

5)TL类(too large data)。这类数据的值明显地大，但概率却异常地小，因此被定义为另一类离群点。然而，同TS类数据不同的是，这类数据对聚集结果的影响不能被简单地忽略掉，因为他们的值实在是太大了，这样的数据一旦被采到，可能会对结果产生很明显的影响。

该分类方法主要考虑正态分布，因为正态分布最符合实际情况，而其他的大多数分布都可以由正态分布扩展而来。为了提高精度，需要将样本之间的差异考虑在内。将数据按照特点分为以上五类并为其划定边界，方便在后续的步骤中对不同类型的数据进行不同的处理操作，从而提高聚集值的精确度。

在平均抽样的基础上，将样本分为这五类，对这些数据赋予不同的杠杆值，计算出一个用于计算的概率。在聚集的过程中，用这个新的概率进行计算。由于这样的概率将样本个体间的差异纳入其中，因此可以用很小的一部分样本来获得较精确的聚集值。

其它步骤及参数与具体实施方式一至三之一相同。

具体实施方式五：本实施方式与具体实施方式一至四之一不同的是：所述步骤四中将需要进行均值聚集计算的M个数据均分成b份，并存储在不同的计算单元，其中，b的值为10；将采样率r、需要进行均值聚集计算的数据集的数据边界、粗略均值sketch和需要进行均值聚集计算的数据集的数据边界的参数传到每一个计算单元内，得到每一个计算单元内的均值；具体过程为：

为了符合实际情况，假定数据存储在不同的地方，即，存储在不同的计算单元。这样的情况下，每个计算单元分别进行计算，再讲结果进行整合，这样的效率更高。这个数据边界是用来限定每个计算单元内的数据的。就相当于，整个的数据集分成几份，每一份在一个数据单元内进行计算；

前面的只是计算了数据边界，这个步骤是在每个计算单元内采样，然后边采样边用这个数据边界进行分类；

步骤四一、依据数据边界对每个计算单元内的数据进行分类，分为5类，选取其中的S类和L类的数据，估算出一个加权均值estimation＝f(α)＝k·α+c，其中，f(α)为基于杠杆的估计函数；α是代表权值作用强度的参数，其取值范围为0-1，k为一个和S、L类数据的和，平方和，立方和有关的常数，c为S、L类数据不加任何权重的均值；

F(α)是由如下公式推导而成的

其中，x是抽样个体的值，weight是权重。将这个式子化简之后即可得到estimation是关于α的一次函数。

由于正态分布在分布上的特性，可以选择一部分有特点的样本进行计算。观察上面提到的数据分类规则，发现S类数据和L类数据是很有特点的。依照这两类数据，甚至可以推测出正态分布的形态，如图3所示。

因此，选择S和L类数据进行计算，这样既能保证聚集值的精确度又能保证算法的效率，还避免了TL类离群点对结果的影响。

步骤四二、衡量粗略均值sketch和精确值之间的偏差；

当S类的数据个数大于L类的数据个数时，则粗略均值sketch大于精确值；

当S类的数据个数小于L类的数据个数时，则粗略均值sketch小于精确值；

当S类的数据个数与L类的数据个数近似相等时，则粗略均值sketch与精确值近似相等，则直接返回粗略均值sketch；

近似相等为S类的数据个数与L类的数据个数的比值范围为0.99-1.01；

步骤四三、设定α初始值为0，衡量加权均值estimation和粗略均值sketch之间的偏差Δ；

Δ＝f(0)-sketch＝c-sketch

c为S、L类数据不加任何权重的均值；由此得到加权均值estimation的初始值和粗略均值sketch之间的大小关系；

步骤四四、由步骤四二和步骤四三得到sketch、estimation和精确值之间的关系，如，sketch>estimation>精确值。将粗略均值sketch和加权均值estimation同时向精确值调整；调整步长是根据用户给定精度e设定的；粗略均值Sketch和加权均值estimation中和精确值偏差大的那个均值每一次调整步长为0.1e，偏差小的那个均值每一次调整步长为0.08e；sketch和estimation依次调整，直至二者近似相等，得到每一个计算单元内的均值；

近似相等为加权的均值estimation与粗略均值sketch的差值绝对值为0-0.1r。

该计算单元内的计算停止，系统将该计算单元得到的聚集结果传入到整合模块进行整合；

大体意思就是，用户拿来一个很大的数据集来求均值，系统为了算得快，把它分成几份，每一份分别进行计算，最后汇总取平均求出最后结果。该步骤的原理示意图如图4、图5所示。

采用以下实施例验证本发明的有益效果：

本实施例验证了该方法的精确性，具体是按照以下步骤制备的：

平台：WindowsPC,CPU：2.60GHz，RAM：4GB

领域：金融，统计等领域

实施方案：我们采用钢材公司生产的100cm长的钢管作为样本，对钢管的长度的均值进行估计。

在该实施例中，我们采用100万条数据进行验证。我们对均值聚集结果和真实值进行比较，从而验证本发明的精确性。通过预先的计算可知，钢管的长度的真实均值为100.05cm。我们将钢管长度的数据集均分成10份，模拟成10个计算单元，在每个计算单元内数据进行均值聚集计算，随后，系统将各个计算单元的聚集结果进行整合，最终返回整个数据集的均值。

在该实施例中，将本发明和均匀抽样方法进行对比，并设置精度要求e为0.5。为了更好地体现出本发明的优势，在算出采样率之后，设置均匀抽样的抽样次数为用本发明的抽样次数的三倍。结果显示如下表所示：

实验编号12345均匀抽样99.6321100.17299.799199.726100.138本发明方法100.247100.108100.20699.9992100.238

进行了五组实验，结果显示，即使是在采样次数仅为均匀抽样的三分之一时，本发明求得的均值依然能够满足精度约束0.5，并且大多数情况下本发明的计算结果比均匀抽样好。

本发明还可有其它多种实施例，在不背离本发明精神及其实质的情况下，本领域技术人员当可根据本发明作出各种相应的改变和变形，但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。