为了突破传统集群计算框架的内存计算瓶颈和分布式文件的在线抽样瓶颈,本博士论文提出了一种新的基于抽样方法的大数据近似计算技术,称作RSP(Random Sample Partition)技术。采用这一新技术,当被处理和分析的数据超出已有计算资源的能力时,数据科学家照样可以在集群上对数据进行探索和分析。本博士论文的主要贡献和创新有如下三个方面:(1)首次提出了随机样本划分(random sample partition,RSP)分布式数据模型,将大数据表达成一组随机样本数据块的集合,称作RSP数据块,这些数据块存储成集群节点的数据文件,可以随机读入内存当作随机样本使用;(2)提出了一个逼近式集成学习框架,支持基于RSP数据模型的大数据近似分析;(3)提出了基于RSP数据块的大数据探索(exploration)和清洗方法,提高分布式大数据的理解和预处理效率。本文采用了仿真和真实数据在小型计算集群上进行实验,展示RSP技术的统计和计算优势。实验结果证实,本方法只需少量的RSP数据块即可获得与整个大数据计算结果等价的近似计算结果(这些结果包括分类、回归和统计量估计)。实验结果进一步展示,对于少量RSP数据块的清洗可以估计整个大数据未知的统计特征。当整个数据大到不可计算时,RSP技术照样可以对数据进行探索和分析。1研究背景在大数据时代,数据的生成速度往往快于计算技术的发展速度[1,2],数据量往往超过计算集群内存的计算能力。事实上,TB级以上数据的分析已逐渐成为大数据应用的日常任务。对于使用小型计算集群的数据科学家来说,这已经成为一项挑战的工作。虽然现有的集群计算框架运行迭代算法,对一定规模的大数据有较好的扩展性[3-7],但其可扩展性受已有的计算资源约束。MapReduce计算模型对于仅需一次扫描整个数据集的算法非常有效。但是,当运算多次迭代的复杂算法处理数据时,大量的通信和I/O操作导致MapReduce模型的计算效率大大降低[8]。Apache Spark采用内存计算技术,将整个数据保留在集群的内存中,可以快速地处理大数据。但是,当集群的内存不够大,不能保留HDFS全部数据块时,Apache Spark计算效率显著降低。当前大数据计算技术的另一不足,是需要将串行的分析算法并行化实现,在集群上并行处理分布的数据块,目的是得到与串行算法相同的结果。这导致在并行算法的开发上耗费大量的精力。即使使用高效的分布式算法,面对不断增大的数据规模,内存资源永远会处于匮乏状态。此外,现有的集群计算框架不能很好地支持通用数据分析语言(如R和Python)中的数据探索算法库的交互性和灵活性。与此同时,这些语言的大量串行算法无法轻松扩展到大数据。虽然基于样本的近似计算是减轻大数据分析负担的常用方法[9-17],但是,随着数据规模的不断增大,集群计算的在线抽样效率越来越低[18,19]。在数据探索、机器学习、统计估计和诊断应用中,在线抽取大量小的随机样本集的操作已经成为集群计算的禁区[20-27]。这一限制操作同样是集群计算框架上频繁的通信和I/O操作导致的。事实上,集群计算的抽样技术本身需提高可扩展性以适应大数据的需求。在分布式大数据文件中进行记录层的抽样(Record-Level Sampling,RLS)非常耗时,因为每次抽样都需要上载和扫描整个大数据的HDFS数据块,以满足每个记录被抽中的概率相等的随机样本条件。在内存有限的情况下,基于记录的抽样成为大数据近似计算的约束。如果只随机抽取HDFS的数据块文件作为大数据的随机样本,技术上很容易实现,但这种数据块层次的抽样(Block-Level Sampling,BLS)往往导致计算结果统计上不正确或带有偏差,原因是这些HDFS数据块文件不是大数据的随机样本,数据块间可能存在相关性[28]。事实上,数据的划分方式影响划分的数据块的统计特征,进而影响算法的运行效率和有效性[19,29-34]。针对大数据分析,集群计算框架的数据划分方法的一个关键问题是,现有的划分方法没有考虑数据本身的统计特征,即对象和属性的概率分布。当数据文件导入HDFS文件系统时,会被切分成大小固定的数据块,若原数据的记录不是随机排列的,这种分块方法不能保证每个数据块是原数据集的一个随机样本。由于原数据文件[18]中的数据记录很少是随机排序的,为了保证所有HDFS数据块的统计一致性,需要研究新的数据划分方法,大数据表达模型和分析计算框架。集群计算框架采用“分而治之”的策略,在集群上进行数据的分布式存储和计算[3]。该策略将大数据划分为小的数据块,然后将这些小数据块分布式存储在计算集群的节点上,执行数据并行的操作,再将中间结果集成为大数据的最终结果。MapReduce计算模型[7]将分治策略应用于主流集群计算框架中[5,6],例如Apache Hadoop和Apache Spark。这些框架实现了无共享架构,其中每个节点在数据和资源方面都是相互独立的。Hadoop分布式文件系统(HDFS)[35]将数据文件组织并复制为小型分布式数据块,HDFS数据块是Hadoop集群中存储和处理的基本数据单元。由于集群计算框架依赖于分布式数据并行计算,因此,可以通过向计算集群添加更多的节点来扩展集群的计算能力。然而,当数据的增长速度快速地超出可用资源,扩展计算集群的计算能力需要额外的成本[36],这在实际应用中并非长久的解决办法。近似计算是降低集群计算成本、提高大数据分析效率的一种很有前景的解决方案[9,10]。它仅利用输入数据的一个子集便可以产生与实际结果相近似的分析结果,同时实现低延迟和高效的资源利用[11,12,13,37]。过去的十年里,基于样本的近似计算技术已应用于近似查询处理(AQP)和集群计算中的大数据统计分析[25,38,39],证明基于样本的近似计算是有效的。近似计算不仅仅在于近似的结果和精准的结果一致[9,11,16,40],还在于采用少量清洗过的“干净”数据样本,可以得到比在整体的“脏”数据上计算能得到的更准确分析结果[41-44]。除了大数据分析中常用的近似抽样计算方法外,抽样技术在集成学习算法[26,45]和统计估计方法(如Bag of Little Bootstraps[23,24])中也是必不可少的。2研究内容及科学问题本论文的研究目标是突破当前集群计算框架对超大数据分析的内存瓶颈和分布式大数据文件在线抽样的瓶颈,使数据分析人员能在小型集群上,对超出可用内存资源的大数据,能够进行有效的数据探索和分析。为实现这一目标,本论文重点研究并解决下面几个关键科学问题:问题1(保持统计一致性的大数据划分方法):HDFS文件系统的数据块划分忽略了整个数据与数据块的分布一致性,致使HDFS数据块中的数据分布不一致。如果以数据块为单位抽样做近似计算,近似计算的结果会有偏差,甚至产生统计上的错误。解决这一问题需要研究支持大数据近似计算的新的分布式数据模型和大数据划分方法,以保证大数据近似分析结果的统计正确性。·问题2(分布式大数据在线抽样):记录层次的在线抽样方法在集群计算框架中的抽样效率低,特别是抽取大量小的随机样本集进行整个数据的统计估计时。在大数据情况下,数据块层次的抽样方法效率更高,因为它不需要加载整个数据。尽管如此,针对数据块层次样本的分析结果,其准确性取决于HDFS数据块的分布,进而由大数据的划分方法决定。由于样本的质量在数据科学的近似计算中起决定性的作用,必须研究新的分布式大数据在线抽样方法,可以高效、高质量地在线抽取近似分析的随机样本集,而无需将整个大数据加载到内存中。·问题3(基于大数据样本的迭代算法):迭代算法往往需要将数据加载到内存中,并经过多次数据迭代,产生最后的计算结果。但是,迭代算法处理大数据的能力,在当前的集群计算框架下,可扩展性受限于可用资源。使用迭代算法进行TB级以上的数据分析变得很难、不切实际。除了内存限制之外,传统的迭代方式还会导致严重的延迟,并且需要大量的通信和I/O操作。解决此问题需要研究基于大数据样本的迭代算法和计算框架。·问题4(基于样本的大数据探索方法):在应用复杂算法进行数据分析之前,需要对大数据的分布和质量进行探索分析,理解大数据的分布。通常需要对原数据反复迭代,抽取小的随机样本,通过样本探究整个数据的统计特征。这项工作对于小型计算集群上的大数据来说,是非常困难的。为了使数据科学家能利用小型计算集群完成大数据的统计特性理解,需要研究新的探索方法,使其可以扩展到大数据的探索任务,。·问题5(大数据的数据清洗):基于样本的近似计算技术,应用于“脏”数据时,往往产生错误的、误差较大的分析结果。但是,大数据的清洗工作非常困难,需要很多人工干预。实际工作中,在应用高级算法对进行大数据分析和建模之前,数据科学家大部分时间都花费在数据清洗工作中。解决大数据的清洗难题,需要研究基于数据块的数据查错、去噪声和清洗方法及算法,降低基于样本的大数据近似计算的数据错误和抽样误差。3主要贡献为了解决上述问题,实现在集群的内存和计算资源受限的情况下,完成大数据的近似分析,本博士论文提出了大数据近似计算和分析的新方法,称作RSP方法。这一新方法将HDFS的数据块表达成整个大数据的随机样本,存成随时可以读取的节点文件。这一新的大数据表达模型可以解决两个问题,一是避免了记录层随机抽样,二是解决了数据块抽样的样本分布式不一致问题。在数据探索和分析时,随机抽取数据块样本集,每个数据块在各自节点上用串行算法计算,所有选中的数据块样本集在集群上并行处理,不再需要对整个数据进行计算,也不再需要做记录层的在线抽样。这些都是本博士论文的创新成果。本博士论文的主要贡献总结成以下三个方面:·随机样本划分(RSP)分布式数据模型:本博士论文首次提出了随机样本划分(random sample partition,RSP)分布式数据模型。该模型支持以数据块为单位的样本抽样,支持小型计算集群进行大数据的近似分析。该模型将大数据集表示为一组相互独立、随时可用的随机样本数据块,我们将之称为RSP数据块。如图1所示,每个RSP数据块的统计分布与整个数据集的统计分布保持一致,这样,RSP数据块可以直接作为具有代表性的随机样本使用,而不需要昂贵的在线抽样操作,这是RSP数据模型最具代表性的优点。假设D是一个具有M个特征和N条记录的多元数据集。在实际情况中,若D非常大,当数据规模超过集群的可用内存资源时,想要对整个D进行计算变得非常昂贵和困难。在RSP数据模型中,D表示为随机样本块集合T={D1,D2,…,DK}。随机样本划分的定义:假设F(x)是D中随机变量X的样本分布函数(s.d.f.)。设T是数据划分操作,它将D划分为一组子集的集合T=[D1,D2,…,DK},Big Data Set DT:a Random Sample Partition(RSP)of D图1:随机样本划分分布式数据模型每个子集包含n条记录。如果满足以下条件,则将T称为D的一个随机样本划分:(1)k∪k=1 Dk=D(2)Di∩Dj=(?),ij∈{1,2,…,K},i≠j;(3)E[Fk(x)]= F(x)for each k= 1,2,…,K,.其中,Fk(x)表示Dk中随机变量x的样本分布函数,,E[Fk(x)]表示其期望分布。因此,将每个Dk称为D的RSP数据块,T称为D上的RSP操作。我们可以用一个两阶段的数据分块(TSDP)算法将一个HDFS文件转换成RSP数据块存储。使用RSP数据模型,数据块抽样可以得到记录层次抽样相同质量的随机样本,但抽样效率非常高,达到秒级抽样速度。本论文证明了RSP数据模型的存在性定理,完成了RSP数据块特征分布于整个数据集特征分布的一致性证明。同时,本论文还对RSP数据块的统计量估计(例如均值等)的无偏性和一致性进行了证明。此外,实验结果表明,RSP数据块的统计分析和记录层次抽样的样本分析结果一致,且明显优于普通HDFS数据块抽样的样本分析结果。鉴于RSP数据块的统计和计算优势,RSP模型对提高和扩展小型计算集群对大数据探索和分析能力和效率具有重要意义。·用于大数据分析的逼近式集成学习框架:由于RSP数据模型中的每个RSP数据块均保留了整个数据集的统计特征,RSP数据块可以直接用于大数据的近似分析。基于RSP数据块的近似分析流程如下:首先对RSP数据块进行抽样,获得数据块样本集;然后对数据块样本集做并行分布式处理,分布式处理的结果集成为近似计算结果;当近似结果满足终止条件时,输出近似结果;否则,做第二批数据块抽样,重复前一步的计算,把新的集成结果与前一步的结果集成,再进行终止条件检查。每一步的近似分析步骤如图2所示。上述分析流程定义为逼近式集成学习框架,这一流程的实现是基于RSP数据模型。分批逼近式近似计算框架采用的是时间换空间的策略,可以在资源有限的小型集群上完成更大的数据分析工作。这一逼近式集成学习框架是本博士论文的另一首创。在这一计算框架下,对每个RSP数据块的计算采用串行算法,多个数据块在集群的多个节点同时进行分布式计算。因此,在此新的数据模型和计算框架下,独立运行在每个节点的算法不在需要并行,减少了算法并行的工作,这是本学习框架的一大优点。根据逼近式集成学习框架原理,我们已经实现了样机,称作Alpha计算框架,该框架结合了主流的集群计算框架、分布式文件系统以及现有数据分析和挖掘算法,在小型计算集群上实现基于RSP数据块的大数据近似分析。该原型样机基于HDFS和RevoScaleR软件包开发,采用真实数据和仿真数据的实验结果表明,在RSP数据块样本集上训练得到的分类和回归模型与从整个数据集训练的模型的性能相同或高于整个数据的模型。在这一框架下,内存限制不再是关键,因为RSP块足够小,完全可以在单个节点上进行处理。有了这个框架,数据规模不再成为大数据数据分析的障碍。·基于RSP数据模型的大数据探索和清洗方法:鉴于RSP方法的统计和计算优势,我们采用这种方法来解决小型计算集群上的大数据理解和清洗问题。在计算集群上使用RSP方法,数据科学家能够利用RSP数据块探索功能RSP-Explore来推断整个数据集的统计特征,同时,根据可用资源调整处理数据的数量。RSP-Explore功能模块如图3所示。该模块主要将RSP数据块的样本集应用于三项任务:统计量估计、错误检测和数据清洗。由于RSP数据块是大小相同的随机样本,因此,该方法的基本原理是,用单个RSP数据块的样本分布来推断和估计全部数据的分布。从RSP数据块的样本分布可以得到一个近似统计结果和置信区间。同样地,我们可以通过RSP数据块样本的误差值、异常值、缺失值和有效值在样本中的比例来估计这些值在整体数据中的比例,从而解决数据质量的推断和错误检测问题。通过计算得到的错误数据和比例,制定数据清理规则,这些规则并行地用于清洗少量RSP样本数据块。然后利用这些清洗好的RSP数据块,来推断未知被清洗数据的概要统计。两个真实数据集的实验结果表明,RSP数据块样本的统计特征可以快速收敛到真值,并且利用清洗过的RSP数据块样本,可以有效估计原数据清洗后的数据统计特征。图3:RSP-Explore.功能模块4主要实验结果和分析为了展示RSP方法在大数据探索和分析中的统计和计算优势,我们在一个由5个节点组成的小型计算集群上。,分别在真实数据集和仿真数据集上进行了实验。主要实验结果总结如下:·两阶段数据划分算法(TSDP)扩展到TB级数据文件的结果:我们使用TSDP算法对10个大小为100GB到1TB不等的仿真数据集进行了测试,每个数据集转换成多个RSP数据块,每个RSP块包含10万条记录。我们发现,分块的时间随着数据集中记录数的增长几乎呈线性增长。例如,将100GB文件转换成1000个RSP数据块,需要时间11分钟;将500GB文件转换成5000个RSP数据块,时间需要1小时;将1TB文件转换成10000个RSP数据块,时间需要2个小时。在实际应用中,数据预处理的目的是为后续的数据探索和分析任务准备数据。也就是说,数据的预处理过程是在数据科学家开始分析数据之前完成的。每个数据集只需转换一次,生成RSP数据模型。因此,1TB数据的RSP数据模型的生成,在5个节点的小型集群上两个小时内完成转换可以接受。这个过程为后续的迭代数据探索和分析任务可以减少了开销。·RSP数据模型在线抽样时间从小时缩短到秒:RSP数据块可以直接作为随机样本,用于各种探索和分析任务。尤其是在需要大量随机样本集时,RSP数据模型能够显著节省在线抽样的时间,提升抽样效率。实验结果展示,从1TB的RSP数据模型中随机抽取100个RSP数据块(每个数据块中的记录数K=10000),使用Apache Spark在本地加载到节点上,平均需要15秒。而使用记录层次抽样方法,从1TB数据文件中随机抽取100个同样大小的随机样本集,Apache Spark的运行时间超过了10个小时。由此可见,使用RSP数据模型能够在更短的时间内抽取大量随机样本集(虽然将1TB的数据转换成10000个RSP数据块,需要2小时转换时间)。而相同的时间内用记录层次抽样,在1TB数据操作只能抽取少量的样本集(例如,10小时内在相同的1TB数据中仅能抽取100个样本集)。·RSP数据块样本在统计结果上和记录层次随机抽样样本一致:为了比较RSP数据块、HDFS数据块和记录层次抽样样本的统计特征,我们在100G仿真数据上做了实验,分别统计了三类数据样本的均值和标准差。实验结果表明,RSP数据块和记录层次抽样的样本的估计值是相同的,并且均接近真实值。同时,两种数据样本可以得到近似相同的方差、标准差和误差范围。另一方面,我们发现HDFS数据块的方差、标准差以及误差范围相较于前两种更大。由此可见,RSP数据块的样本和记录抽样的样本拥有相类似的统计特征。由于HDFS数据块通常不是整个数据集的随机样本,因此,其数据块样本的统计特征与前两种并不一致。·RSP数据块可以直接作为BLB(Bag of Little Bootstraps)方法中的子样本来使用:我们在100GB的仿真数据RSP模型上随机抽取了100个数据块作为100个随机样本集,然后采用BLB方法[24]对100个数据块做了做了统计量的估计,每个样本(块)进行100次的重复采样来评估其平均值和标准差。评估质量的置信区间设置为[0.05%,0.95%]。试验结果表明,RSP数据块和记录层次的抽样样本各项评估指标的置信区间基本相同,而且都很窄,这与随机抽取100个HDFS数据块,再用BLB方法计算的置信区间有明显差异,后者置信区间很宽。同样,我们还基于RSP数据块利用BLB方法来推断100GB仿真数据线性回归模型的回归系数,得到类似的结果。(a)Classification in HIGGS(K = 200,n = 55000,g = 5)(b)Regression in Taxi(K = 250,n = 500,000,g = 10)(c)Regression in DS1(K = 1000,n = 100,000,g = 25)(d)Classification in DS2(K= 1000,n = 100,000,g = 48)图4:基于RSP技术的集成模型性能曲线·少量RSP数据块训练的集成模型的性能等价或优于由整个数据训练的单个模型:我们使用逼近式集成学习框架来构建回归和分类的集成模型,对两个真实数据集和两个仿真数据集中的不同大小的RSP数据块进行了试验。结果表明,集成模型经过少量的RSP数据块的增量训练后,其准确率便不再有显著变化且收敛。图4展示了模型的准确率随着RSP数据块的数量增加变化而变化的曲线。从图中可以看到,利用少量的RSP数据块就足以得到等效于利用完整数据训练的集成模型(例如:分类任务中,真实数据HIGGS仅需要10%的训练数据,100G的仿真数据仅需要9.6%的训练数据。回归任务中,Taxi数据仅需要12%的训练数据,100G的仿真数据仅需要2.4%训练数据)。由此说明,RSP数据模型可以大大减少迭代算法的计算时间,使得小型计算集群能够处理更大的数据规模。· RSP数据块样本足以充分地探索大数据的统计特征:我们用RSP-Explore方法来估计数据的统计特性(例如:平均值,标准差,中位数,偏度,峰度和相关性)。同样,我们发现,利用部分RSP数据块的样本做增量估计,其误差范围会更小以至于可以忽略不计。图5显示了HIGHS数据中的估计均值、标准差和相关系数的变化情况。实验结果表明,对少量的RSP数据块进行统计便可以得到用完整数据进行统计相近似的结果。其它真实数据和仿真数据的实验得到了类似的实验结果。(a)Mean of V2(b)StdDev of V2(c)Pearson’s correlation coefficient be-tween V2 and V20图5:HIGGS数据中的估计均值、标准差和相关系数的变化·清洗过的RSP数据块样本可以充分地估计整个数据清洗后的统计特征:本论文采用RSP-Explore对南方电网的电测数据集做了特征统计分析实验。其中,电测数据的记录数N = 46,669,266,特征属性个数M = 98,RSP数据块的个数K = 6667,每个数据块的记录数n = 7000。原数据转换成RSP数据模型后,随机抽取100个RSP数据块作为样本来估计单个属性变量和两个属性变量的统计量。结果显示,中位数和中位数绝对偏差的估计值接近真实值,且置信区间较窄;其它的统计量与真实值差异较大,置信区间也较大。在标准差、偏度和峰度上,估计值收敛到与真实值有显著差异的水平。同样地,两两特征变量相关系数也不是很接近真实值。从这些结果可以推断,原数据中包含噪声数据,致使估计结果产生偏差。我们使用了RSP-Explore估算电测数据中错误、异常值、缺失值和有效值的比例,结果表明,来自100个RSP数据块的平均比例与来自整个数据的计算结果相当,如图6所示。发现问题后,我们定义了清洗规则,对数据块进行了清洗。然后,对清洗后的数据块做了相同统计量的估计。结果显示,新的估计值与清洗后整个数据的真值没有产生大的偏离。最终发现,只需清洗1.5%的数据(即100个RSP数据块)就足以估计整个已清洗数据的统计特征。·RSP数据模型支持无法对整个数据进行计算的大数据分析:本论文使用的小型计算集群仅有640G内存,可用于Spark应用程序的内核数量为96个。图6:估算电测数据中错误、异常值、缺失值和有效值的比例这并不足以保存1TB的完整数据集(N= 10亿、M = 100、K= 10000、n =10万)。而且,该数据中的数据块数量远远超出了可执行程序的数量。在这种情况下,用RevoScaleR或Spark中的并行算法加载和分析完整的1TB数据是做不到的,很容易遇到时间开销过大或内存瓶颈的情况。利用RSP数据模型则很容易解决这个问题。本论文的实验使用Alpha框架,仅用少于200个RSP块(约4%)就获得了平均准确率为0.839±0.0357的分类模型。因此,逼近式集成学习框架将小型计算集群上TB级规模数据的计算时间从小时减少到分钟甚至秒。表1各模型在测试集上的实验结果对比。5结论本博士论文提出了用于集群计算的大数据近似分析方法,即RSP方法。这种方法的原始创新点是实现了集群计算和近似计算的有效协同,使计算集群平台的大数据分析对数据的扩展性更高,内存资源不再是大数据分析的主要瓶颈。基于此项创新,可以开发扩展性更高的下一代大数据计算技术。研究成果表明,基于随机样本划分的分布式数据模型是大数据近似分析和现有算法扩展到大数据的基础。在TB级数据分析已逐渐成为数据科学家的常规任务的环境下,RSP方法将会对集群计算框架的可扩展性和数据科学家工作能力和效率的提升产生重大影响。由于RSP数据块是整体数据的随机样本,RSP方法既可以避免记录层次抽样的高成本,又可以避免不一致HDFS数据块的样本的统计错误结果。为了探索和分析数据,本文使用串行算法并行地选择和处理数据块样本,而不需要计算整个数据集,或运行昂贵的在线抽样操作。也就是说,使用RSP方法,内存不再是大数据分析的限制条件,数据科学家可以使用小型计算集群来分析更大的数据集。