黃哲學(xué) 何玉林 魏丞昊 張曉亮

（1.深圳大學(xué)計算機與軟件學(xué)院大數(shù)據(jù)技術(shù)與應(yīng)用研究所，深圳，518060；2.深圳大學(xué)大數(shù)據(jù)系統(tǒng)計算技術(shù)國家工程實驗室，深圳，518060）

引 言

數(shù)據(jù)分析是挖掘大數(shù)據(jù)價值的重要手段和途徑。數(shù)據(jù)文件通常被表示成個對象（或記錄）的集合D={x1,x2,…,xN}，其中每個對象被表示成M個屬性（或特征）的向量xn=(xn1,xn2,…,xnM),n=1,2,…（當(dāng)M很大時，D為超高維數(shù)據(jù)；當(dāng)N很大時，D為大數(shù)據(jù)；當(dāng)M和N都很大時，D為超高維大數(shù)據(jù)）。正如陳國良院士[1]描述的那樣：“到目前為止尚沒有這樣一個被普遍認可的大數(shù)據(jù)定義出現(xiàn)”，僅能夠從大數(shù)據(jù)的特征對其展開描述，其中比較有代表性的是大數(shù)據(jù)的“4V”特征。給定數(shù)據(jù)文件或數(shù)據(jù)集D，數(shù)據(jù)分析的任務(wù)主要包括：數(shù)據(jù)預(yù)處理、數(shù)據(jù)探索分析、奇異值檢測、關(guān)聯(lián)分析、聚類分析、分類和預(yù)測等。

目前可用于數(shù)據(jù)分析的方法和算法很多，計算復(fù)雜度高是許多數(shù)據(jù)分析和機器學(xué)習(xí)算法的共有特點，因此，這些算法很難用于大數(shù)據(jù)分析。分而治之是當(dāng)前大數(shù)據(jù)分布式并行處理普遍采用的策略，其步驟是將大數(shù)據(jù)文件D切分成個小的數(shù)據(jù)塊文件，分布式地存儲在集群節(jié)點上。對大數(shù)據(jù)分析時，先在每個節(jié)點上對小數(shù)據(jù)塊進行計算，然后把小數(shù)據(jù)塊的計算結(jié)果傳送到主節(jié)點進行綜合分析，得到大數(shù)據(jù)的分析結(jié)果，對于復(fù)雜的分析算法，上述兩個步驟需要迭代進行，算法需要按分而治之的計算模式并行實現(xiàn)。當(dāng)前主流的大數(shù)據(jù)處理平臺Hadoop MapReduce和Apache Spark采用的都是分而治之策略。

大數(shù)據(jù)的劃分和數(shù)據(jù)塊文件的管理采用分布式文件系統(tǒng)，如HDFS[2-3]；而大數(shù)據(jù)的分析算法則采用MapReduce[4-5]或Spark[6]計算模型實現(xiàn)。近年來，國內(nèi)對于MapReduce和Spark的研究主要集中在提高它們解決大數(shù)據(jù)分析問題的效率上。2017年，張濱[7]對MapReduce大數(shù)據(jù)并行處理過程中的查詢優(yōu)化控制、數(shù)據(jù)分布優(yōu)化和調(diào)度優(yōu)化控制等若干關(guān)鍵技術(shù)進行了研究。2018年，李志斌[8]通過引入基于內(nèi)存的PageRank算法設(shè)計了一個針對大規(guī)模圖數(shù)據(jù)集的MapReduce大數(shù)據(jù)并行處理系統(tǒng)。2018年，王晨曦等人[9]提出了面向大數(shù)據(jù)處理的基于Spark的異質(zhì)內(nèi)存編程框架，解決了如何將數(shù)據(jù)合理地布局到異質(zhì)內(nèi)存的問題。2019年，宋泊東等人[10]通過使用Apache Kafka作為消息中間件設(shè)計了一種基于Spark的分布式大數(shù)據(jù)分析算法。更多關(guān)于MapReduce和Spark框架性能分析的介紹可參見吳信東等人的研究工作[11]。

基于MapReduce的分布式計算框架通過磁盤文件進行Map節(jié)點與Reduce節(jié)點之間的數(shù)據(jù)交換，在運行循環(huán)迭代算法時需要大量的磁盤讀寫操作，極大地降低了算法的執(zhí)行效率。Spark采用RDD內(nèi)存數(shù)據(jù)結(jié)構(gòu)將大數(shù)據(jù)分布式存儲在節(jié)點的內(nèi)存中，在運行迭代式分而治之的算法時不需要反復(fù)地讀寫磁盤，在一定程度上提升了算法的運行速度。但是，當(dāng)數(shù)據(jù)量超出內(nèi)存容量時，Spark的算法執(zhí)行效率將被大大降低，甚至無法運行。因此，內(nèi)存資源成為TB級以上大數(shù)據(jù)的深度分析、挖掘和建模技術(shù)的瓶頸。

采用隨機樣本數(shù)據(jù)對大數(shù)據(jù)做統(tǒng)計估計和建模是大數(shù)據(jù)分析的有效途徑。但是，對分布式大數(shù)據(jù)做隨機抽樣是計算成本很高的操作，因為要對大數(shù)據(jù)的分布式數(shù)據(jù)塊文件進行遍歷才能獲得隨機樣本數(shù)據(jù)，這一過程需要大量的磁盤讀寫操作和節(jié)點間的數(shù)據(jù)通信。如果大數(shù)據(jù)的分布式數(shù)據(jù)塊可以直接當(dāng)作樣本數(shù)據(jù)來用，大數(shù)據(jù)的隨機抽樣操作就不需要了，有了可用的樣本數(shù)據(jù)，大數(shù)據(jù)的分析與建模問題就可以通過對樣本數(shù)據(jù)的分析與建模解決，這樣就減少了大數(shù)據(jù)分析對內(nèi)存的約束。但是，當(dāng)前的大數(shù)據(jù)分布式數(shù)據(jù)塊，即HDFS數(shù)據(jù)塊文件不能當(dāng)作大數(shù)據(jù)的隨機樣本使用，因為不同數(shù)據(jù)塊的數(shù)據(jù)分布不同，數(shù)據(jù)塊的數(shù)據(jù)分布與大數(shù)據(jù)本身的數(shù)據(jù)分布也不同，簡單地將數(shù)據(jù)塊當(dāng)作大數(shù)據(jù)的隨機樣本數(shù)據(jù)使用，會產(chǎn)生統(tǒng)計意義上不正確的結(jié)果。

針對當(dāng)前大數(shù)據(jù)分析的技術(shù)瓶頸，本文介紹一個新的將統(tǒng)計方法與集群計算融合的大數(shù)據(jù)分析解決方案。針對分布式大數(shù)據(jù)抽樣的問題，本文提出大數(shù)據(jù)隨機樣本劃分（Random sample partition，RSP）模型來表達分布式大數(shù)據(jù)。RSP模型同樣將大數(shù)據(jù)劃分成小的數(shù)據(jù)塊分布式存儲在集群的節(jié)點上，但每個數(shù)據(jù)塊的樣本數(shù)據(jù)分布與整個大數(shù)據(jù)的樣本數(shù)據(jù)分布保持一致，這樣就可以將存儲在節(jié)點上的數(shù)據(jù)塊文件直接拿來當(dāng)作隨機樣本數(shù)據(jù)使用，采用統(tǒng)計中普遍使用的樣本估計方法估計大數(shù)據(jù)的統(tǒng)計量，采用機器學(xué)習(xí)中的集成學(xué)習(xí)方法建立大數(shù)據(jù)集成學(xué)習(xí)模型?；赗SP數(shù)據(jù)塊的大數(shù)據(jù)分析不需要對整個大數(shù)據(jù)進行計算，極大地降低對內(nèi)存的需求，具有更大的數(shù)據(jù)擴展性，突破了TB級大數(shù)據(jù)的計算技術(shù)瓶頸。

本文首先介紹大數(shù)據(jù)隨機樣本劃分模型的定義、存在性定理和大數(shù)據(jù)隨機樣本劃分的生成算法。然后介紹了基于RSP數(shù)據(jù)表達模型的大數(shù)據(jù)漸近式集成學(xué)習(xí)框架——Alpha框架以及基于此框架和RSP數(shù)據(jù)塊的大數(shù)據(jù)分析方法，包括大數(shù)據(jù)探索與清洗、大數(shù)據(jù)概率密度函數(shù)估計、大數(shù)據(jù)子空間學(xué)習(xí)、大數(shù)據(jù)半監(jiān)督集成學(xué)習(xí)、大數(shù)據(jù)聚類集成和大數(shù)據(jù)異常點檢測等。最后總結(jié)采用RSP數(shù)據(jù)模型和Alpha框架進行大數(shù)據(jù)分析的優(yōu)越性和創(chuàng)新性。

1 隨機樣本劃分模型

隨機樣本劃分模型的核心思想是將大數(shù)據(jù)文件劃分成許多小的隨機樣本劃分數(shù)據(jù)塊文件，即每個數(shù)據(jù)塊文件是大數(shù)據(jù)文件的一個隨機樣本數(shù)據(jù)。這樣的劃分給大數(shù)據(jù)分析帶來兩個好處：（1）隨機樣本數(shù)據(jù)可以直接通過選擇數(shù)據(jù)塊文件獲得，不需要對大數(shù)據(jù)的單個記錄進行抽樣，避免了分布式大數(shù)據(jù)隨機抽樣的操作；（2）通過對少量數(shù)據(jù)塊文件的分析和建模即可得到大數(shù)據(jù)的統(tǒng)計估計結(jié)果和模型。采用隨機樣本劃分模型，大數(shù)據(jù)分析的工作轉(zhuǎn)變成對隨機樣本數(shù)據(jù)塊文件的分析與建模，極大地減少了大數(shù)據(jù)分析的計算量，提高了大數(shù)據(jù)分析的能力。本節(jié)對大數(shù)據(jù)隨機樣本劃分的理論基礎(chǔ)和大數(shù)據(jù)隨機樣本數(shù)據(jù)塊的生成方法進行詳細闡述。

1.1 RSP模型的理論基礎(chǔ)

在定義隨機樣本劃分之前，本文首先定義大數(shù)據(jù)劃分。

定義1（大數(shù)據(jù)劃分）設(shè)T是由操作T生成的大數(shù)據(jù)的一組子集D1,D2,…,Dk構(gòu)成的集合，即T={D1,D2,…,Dk}，如果T滿足以下兩個條件，則稱T是D的一個劃分：（1）對于任意的i,j∈ {1,2,…,k}且i≠j，Di∩Dj= ?；（2），同時稱T是大數(shù)據(jù)D的一個劃分操作。

由定義1可知，在HDFS分布式文件系統(tǒng)中，大數(shù)據(jù)表達成數(shù)據(jù)塊文件的劃分，HDFS數(shù)據(jù)塊文件被分布式存儲在集群節(jié)點上。在一般情況下，HDFS數(shù)據(jù)塊文件不能作為大數(shù)據(jù)的隨機樣本數(shù)據(jù)使用，因為數(shù)據(jù)塊文件的數(shù)據(jù)分布與大數(shù)據(jù)的數(shù)據(jù)分布不一致。為解決分布不一致的問題，本文給出大數(shù)據(jù)隨機樣本劃分定義[12]。

定義2（隨機樣本劃分數(shù)據(jù)塊）設(shè)T是大數(shù)據(jù)D的一個劃分操作，T={D1,D2,…,Dk}是由T生成的D的含有k個子集的一個劃分，記和F(D)分別表示數(shù)據(jù)子集Dk和大數(shù)據(jù)D的概率分布函數(shù)。對于任意k∈{1,2,…,k}，如果成立，表示分布的期望，則稱T是D的一個隨機樣本劃分，D1,D2,…,Dk是D的隨機樣本劃分數(shù)據(jù)塊，簡稱RSP數(shù)據(jù)塊。

下面給出定理1，確保對于任何大數(shù)據(jù)都可以將其表達成一組RSP數(shù)據(jù)塊，本文將RSP數(shù)據(jù)塊稱之為大數(shù)據(jù)隨機樣本劃分數(shù)據(jù)模型，或RSP模型。

定理1（RRSSPP存在性定理）設(shè)大數(shù)據(jù)D有N個記錄，N1,N2,…,Nk,是滿足的k(k＞1)個正整數(shù)，則存在一個劃分操作T，使得由T生成的大數(shù)據(jù)劃分T={D1,D2,…,Dk}是D的隨機樣本劃分，其中Dk含有Nk個記錄，k∈{1,2,…,K}。

證明：對于任意給定的含有N個對象的大數(shù)據(jù)D={x1,x2,…,xN}，隨機選取一個N元排列τ={τ1,τ2,…,τN}。 將D的全部N個對象按τn(n=1,2,…,N)值的大小重新排序，得到D′={x′1,x′2,…,x′N}，其中x′n=xτn。將D′按順序切分成k個子集D1,D2,…,Dk，其中每個子集分別含有N1,N2,…,Nk個記錄。則對任意Dk，k∈ {1,2,…,K}以及D中任意一個元素xn，n∈ {1,2,…,N}，有成立。記F(x)和F(x)分別表示數(shù)據(jù)子集D和大數(shù)據(jù)D的概率分布函數(shù)。對任意kk實數(shù)x，由樣本分布函數(shù)的定義知，D中取值不大于x的對象數(shù)為N×F(x)，所以Dk中取值不大于x的對象數(shù)的期望為，所以Fk(x)的期望為。由k的任意性知T={D1,D2,…,DK}為大數(shù)據(jù)D的一個RSP。

簡便起見，這里只考慮對象取值為一維時的情況。當(dāng)對象取值為向量時，證明方法類似。定理1保證了對于任意大數(shù)據(jù)，本文都能通過隨機樣本劃分操作將它轉(zhuǎn)換成RSP表達。由定義2可知，每個RSP數(shù)據(jù)塊的概率分布函數(shù)與大數(shù)據(jù)D的概率分布函數(shù)保持一致性。但是，這種一致性是在期望意義下的，所以每個具體的RSP數(shù)據(jù)塊的概率分布函數(shù)與大數(shù)據(jù)D的概率分布函數(shù)不完全相同。當(dāng)然，RSP數(shù)據(jù)塊之間的概率分布函數(shù)相似度也有所不同。相似度越高，兩個數(shù)據(jù)塊之間相互表達的準確度越高。

給定一個大數(shù)據(jù)D的隨機樣本劃分T，本文采用如下公式計算兩個RSP數(shù)據(jù)塊的概率密度相似性和RSP數(shù)據(jù)塊與D的概率密度相似性。首先，如果，i,j∈{1,2,…,K}且i≠j，滿足

則稱Di和Dj具有α顯著性水平下的概率分布一致性，其中g(shù)mmd(·,·)為基于再生核希爾伯特空間核函數(shù)kernel(·,·)構(gòu)造的推廣最大平均差異（Generalized maximum mean discrepancy，GMMD）[13-14]，表達式為

式中：Ni和Nj為數(shù)據(jù)塊Di和Dj包含記錄的個數(shù)，u為核函數(shù)kernel(·,·)的上界，kernel(·,·)可以選擇徑向基函數(shù)核。之后，構(gòu)造個數(shù)據(jù)塊對(D,D)，i=1,2,…,K-1，j=i+1,i+2,…,K，如果式ij（1）成立的次數(shù)大于等于，其中為正態(tài)分布的分位數(shù)，則將D1,D2,…,DK判定為α顯著性水平下的概率同分布數(shù)據(jù)塊。在實踐中，本文可以用式（1）來檢驗RSP的大數(shù)據(jù)表達，也可以在RSP抽樣過程中通過式（1）來選擇RSP數(shù)據(jù)塊。

1.2 RSP模型的生成方法

定理1的證明給出了一個RSP數(shù)據(jù)模型的生成方法，但此方法需要對整個大數(shù)據(jù)進行排序，當(dāng)大數(shù)據(jù)的對象數(shù)很大時，在分布式計算環(huán)境下對大數(shù)據(jù)的排序是計算量很大的操作，費時或者難于完成。

為了解決分布式環(huán)境下大數(shù)據(jù)RSP的生成問題，本文提出了分為兩步的計算方法[15]：第一步先將大數(shù)據(jù)切成P(P＞ 1)個較大的數(shù)據(jù)塊D1,D2,…,DP，再將每個數(shù)據(jù)塊按定理1證明中的方法分別隨機打亂，切分成Q(Q＞ 1)個更小的RSP數(shù)據(jù)塊Dp1,Dp2,…,Dp，p=1,2,…,P,生成P個RSP集合；第二步將每個RSP中的對應(yīng)RSP數(shù)據(jù)塊D1q,D2q,…,Dq，q=1,2,…,Q，合并生成新的數(shù)據(jù)塊D′q，新生成的大數(shù)據(jù)劃分D′1,D′2,…,D′Q是大數(shù)據(jù)的一個RSP。這一方法的正確性可以通過定理2證明。

定理2設(shè)D1和D2是分別含有N1和N2個對象的兩個數(shù)據(jù)塊，D1·和D2·分別是D1和D2的含有N1·和N個對象的RSP數(shù)據(jù)塊，當(dāng)2·時，D1·∪D2·是D1∪D2的 RSP 數(shù)據(jù)塊。

證明：設(shè)D1和D2的概率分布函數(shù)分別為F1(x)和F2(x)，D1·和D2·的概率分布函數(shù)分別為F1·(x)和F2·(x)，則有E[F1·(x)]=F1(x)和E[F2·(x)]=F2(x)。對于任意實數(shù)x，D1·和D2·中取值不大于x的對象數(shù)分別為N1·×F1·(x)和N2·×F2·(x)，所 以D1·∪D2·的概率分布函數(shù)為。同理可得D1∪D2的概率分布函數(shù)為。從而可計算F1·∪2·(x)的期望為

所以，D1·∪D2·是D1∪D2的 RSP數(shù)據(jù)塊。

簡便起見，這里只考慮對象取值為一維時的情況。當(dāng)對象取值為向量時，證明方法類似。根據(jù)定理2進行推理，可以證明合并后的每個數(shù)據(jù)塊都是大數(shù)據(jù)的一個隨機樣本，因此，Q個數(shù)據(jù)塊是大數(shù)據(jù)的一個RSP。圖1展示了上述大數(shù)據(jù)RSP的兩步生成算法實現(xiàn)過程。

圖2展示一個真實數(shù)據(jù)HDFS數(shù)據(jù)塊的一個屬性分布和RSP數(shù)據(jù)塊的同一屬性分布?？梢钥吹剑琑SP數(shù)據(jù)塊的屬性數(shù)據(jù)分布同大數(shù)據(jù)的屬性數(shù)據(jù)分布相似，因此RSP數(shù)據(jù)塊可以作為隨機樣本來分析大數(shù)據(jù)（圖2(b)）。HDFS數(shù)據(jù)塊之間的屬性數(shù)據(jù)分布不同，同時與大數(shù)據(jù)的屬性數(shù)據(jù)分布也不同，因此HDFS數(shù)據(jù)塊不能當(dāng)作隨機樣本數(shù)據(jù)塊來用（圖2(a)），要想得到大數(shù)據(jù)的正確結(jié)果，必須對整個大數(shù)據(jù)進行分析。

圖1 大數(shù)據(jù)RSP的生成過程Fig.1 RSP model of big data

圖2 不同數(shù)據(jù)模型中數(shù)據(jù)塊與大數(shù)據(jù)整體分布一致性的對比Fig.2 Distribution comparison between data block and whole big data in different data management models

筆者已經(jīng)在Spark上實現(xiàn)了上述大數(shù)據(jù)RSP的兩步生成算法，初步的實驗結(jié)果顯示，在27個計算節(jié)點的集群上，生成1 TB大數(shù)據(jù)（含100億個對象，10屬性）的RSP（30 000個RSP數(shù)據(jù)塊）大概需要56 min。在實際應(yīng)用中，對每個大數(shù)據(jù)的RSP生成只需要一次。

2 基于RSP模型的計算框架

第1節(jié)介紹了RSP數(shù)據(jù)模型的理論基礎(chǔ)和在分布式環(huán)境下生成大數(shù)據(jù)RSP的算法。在分布式集群上，針對某個大數(shù)據(jù)D生成的RSP數(shù)據(jù)塊隨機分布存儲在計算節(jié)點的磁盤上，為了有效地利用分布的RSP數(shù)據(jù)塊對大數(shù)據(jù)進行分析，本文設(shè)計開發(fā)了基于RSP數(shù)據(jù)塊的漸近式集成學(xué)習(xí)框架——Alpha計算框架[16-17]。下面介紹Alpha計算框架和在此框架下的大數(shù)據(jù)分析流程。

Alpha計算框架是基于RSP數(shù)據(jù)塊的分布式大數(shù)據(jù)處理與分析框架，其設(shè)計思想是基于RSP模型的相關(guān)理論。處理和分析一個給定的大數(shù)據(jù)D，當(dāng)把D轉(zhuǎn)換成RSP數(shù)據(jù)塊D1,D2,…,DK，并將其分布存儲在計算節(jié)點磁盤上后，針對任意一個RSP數(shù)據(jù)塊Dk，k∈{1,2,…,K}，進行處理和分析都能得到D的一個統(tǒng)計量θk的估計值，而θk估計值的期望值是D的統(tǒng)計量θ值[18]。因此，θk是θ的近似值，存在一定的誤差。如果采用多個RSP數(shù)據(jù)塊的來計算θ的估計值，其估計值的誤差將隨著RSP數(shù)據(jù)塊的增加而下降。

根據(jù)上述統(tǒng)計估計原理和分布式環(huán)境下分而治之的大數(shù)據(jù)處理策略，本文設(shè)計了漸近式集成學(xué)習(xí)Alpha計算框架如圖3所示，本文僅以分類問題來闡述Alpha框架的工作原理。給定大數(shù)據(jù)D的RSP數(shù)據(jù)塊集合{D1,D2,…,DK}，假設(shè)集群中計算節(jié)點的個數(shù)為Q（Q＜K）。采用無放回塊抽樣隨機抽取個RSP數(shù)據(jù)塊，每個計算節(jié)點抽取一個，上標(1)表示是第一批抽樣；在Q個節(jié)點上采用同一算法從Q個RSP數(shù)據(jù)塊訓(xùn)練Q個基分類器，每個基分類器在各節(jié)點上獨立計算完成；在主節(jié)點上構(gòu)建集成分類器H1；采用獨立樣本測試集測試H1，如果精度達到了設(shè)定的閾值條件，輸出H1，訓(xùn)練結(jié)束；否則，進行第二批RSP數(shù)據(jù)塊無放回抽樣，按相同方式訓(xùn)練第二批基分類器，在主節(jié)點上構(gòu)建集成分類器H2，采用統(tǒng)一樣本測試集測試H1∪H2，如果精度達到了設(shè)定的閾值條件，輸出H1∪H2，否則，進行新的一次RSP抽樣和建模過程。不斷重復(fù)上述過程，直到滿足設(shè)定的閾值條件，其中J為逼近閾值條件的迭代次數(shù)。理論推導(dǎo)可以得出上述漸近式集成學(xué)習(xí)Alpha框架的收斂條件為

圖3 大數(shù)據(jù)漸近式集成學(xué)習(xí)Alpha計算框架Fig.3 Alpha framework for big data analysis and computation

式中：H為在大數(shù)據(jù)D上的學(xué)習(xí)模型（這是一個期望模型，實際不存在），N為大數(shù)據(jù)D含有對象的個數(shù)，K為RSP數(shù)據(jù)塊的個數(shù)，δ＞0為正數(shù)閾值。由式（3）可見，當(dāng)RSP數(shù)據(jù)塊的個數(shù)K和集群計算節(jié)點個數(shù)Q確定之后，的取值僅與逼近閾值條件的迭代次數(shù)J相關(guān)，當(dāng)J→+∞時，。這表明Alpha框架能夠保證學(xué)習(xí)算法的收斂性。

Alpha計算框架的樣機已經(jīng)在Microsoft R Server、Apache Spark和HDFS集群上實現(xiàn)。圖4展示真實數(shù)據(jù)HIGGS上4個特征的均值和標準差的漸近估計值，每一個子圖的橫軸代表使用數(shù)據(jù)的數(shù)據(jù)量占數(shù)據(jù)總量的百分比。圖5展示HIGGS數(shù)據(jù)基于RSP數(shù)據(jù)塊的漸近集成分類模型精度與所有數(shù)據(jù)建模的精度對比，每一個子圖的橫軸代表使用數(shù)據(jù)的數(shù)據(jù)量占數(shù)據(jù)總量的百分比，其中60個RSP數(shù)據(jù)塊，每個數(shù)據(jù)塊大約183 753條記錄；100個RSP數(shù)據(jù)塊，每個數(shù)據(jù)塊110 000條記錄；200個RSP數(shù)據(jù)塊，每個數(shù)據(jù)塊55 000條記錄。本文從圖5中可以發(fā)現(xiàn)只用少量的RSP數(shù)據(jù)塊就可以達到從全部數(shù)據(jù)學(xué)習(xí)的單一模型的精度，該實驗證實了式（3）的合理性。圖6是集成學(xué)習(xí)模型的計算時間與單個模型計算時間的對比，其中圖6(b)最右側(cè)的灰色柱代表單個模型計算時間。本文從圖6中可以發(fā)現(xiàn)基于RSP數(shù)據(jù)塊的Alpha計算框架極大地提高了集群計算的效率。

圖4 HIGGS數(shù)據(jù)4個特征均值和標準差的漸近估計值Fig.4 Feature approximations of mean and standard derivation in HIGGS data set

圖5 基于RSP數(shù)據(jù)塊的集成分類模型與基于所有數(shù)據(jù)建模的精度對比Fig.5 Accuracy comparison between asymptotic ensemble learning model and single learning model

圖6 漸近式集成學(xué)習(xí)模型與單個模型計算時間的對比Fig.6 Time comparison between asymptotic ensemble learning model and single learning model

3 基于RSP模型的大數(shù)據(jù)分析技術(shù)

基于RSP模型和Alpha計算框架可以設(shè)計開發(fā)一系列新的分布式大數(shù)據(jù)分析方法和技術(shù)，這些分析方法的核心思想是：根據(jù)分而治之的策略，在分布式集群系統(tǒng)上利用Alpha計算框架，隨機抽取RSP數(shù)據(jù)塊的子集計算大數(shù)據(jù)的統(tǒng)計量估計值，建立大數(shù)據(jù)的集成模型。本節(jié)介紹以下6種基于RSP數(shù)據(jù)模型和Alpha計算框架的大數(shù)據(jù)分析方法。

3.1 數(shù)據(jù)探索和清洗

數(shù)據(jù)探索是數(shù)據(jù)分析的重要步驟，分析一個未知的大數(shù)據(jù)D，首先需要做的工作是要理解D，要知道D的各屬性的分布，了解D的各種數(shù)據(jù)錯誤，設(shè)計數(shù)據(jù)清洗流程對D進行清理，改正數(shù)據(jù)錯誤。有了D的RSP數(shù)據(jù)模型后，數(shù)據(jù)探索和清洗可以在RSP數(shù)據(jù)塊上進行，可以極大地降低工作量，提高數(shù)據(jù)理解和清洗的效率。

因為RSP數(shù)據(jù)塊具有同整個大數(shù)據(jù)D一致的分布，可以隨機抽取一個或幾個RSP數(shù)據(jù)塊，用可視化工具展示數(shù)據(jù)塊屬性的分布，通過數(shù)據(jù)塊屬性的分布即可理解大數(shù)據(jù)的屬性分布，其原理如圖2(b)所示。同理，可以通過處理RSP數(shù)據(jù)塊找出數(shù)據(jù)的錯誤，設(shè)計清洗錯誤的過程，再將清洗過程應(yīng)用在其他RSP數(shù)據(jù)塊。由于錯誤數(shù)據(jù)重復(fù)出現(xiàn)在RSP數(shù)據(jù)塊中的概率大致相同，在少量隨機抽取的RSP數(shù)據(jù)塊中發(fā)現(xiàn)的錯誤數(shù)據(jù)反映了大數(shù)據(jù)中的主要錯誤數(shù)據(jù)，通過Alpha計算框架的多次迭代，即可發(fā)現(xiàn)大數(shù)據(jù)D中的大部分錯誤數(shù)據(jù)。由于錯誤數(shù)據(jù)的發(fā)現(xiàn)過程是在RSP數(shù)據(jù)塊上進行的，要比從整個大數(shù)據(jù)上發(fā)現(xiàn)錯誤的效率高。

3.2 概率密度函數(shù)估計

概率密度函數(shù)（Probability density function，PDF）是隨機變量統(tǒng)計特性的集中體現(xiàn)，估計概率密度分布是數(shù)據(jù)分析的重要任務(wù)，也是大數(shù)據(jù)分析的一大挑戰(zhàn)。RSP數(shù)據(jù)模型提供了一種“局部推斷整體”的間接式估計大數(shù)據(jù)PDF的途徑。

假設(shè)大數(shù)據(jù)D的屬性變量均為連續(xù)值，對應(yīng)的PDF為，RSD數(shù)據(jù)塊D1,D2,…,DK對應(yīng)的PDF分別為，其中可以通過核密度估計方法求得。直觀的想法，由于D1,D2,…,DK與D存在概率分布上的一致性，可以通過建立式（4）確定為

式中Q（Q＜K）是隨機抽取的RSP數(shù)據(jù)塊個數(shù)。即在α顯著性水平下大數(shù)據(jù)D的PDF可由RSP數(shù)據(jù)塊PDF的均值表示?？梢钥闯?，可以采用Alpha計算框架獲得，通過將在集群節(jié)點上獨立地算出。

3.3 有監(jiān)督子空間學(xué)習(xí)

采用RSP樣本數(shù)據(jù)建立分類或回歸集成模型，由于RSP數(shù)據(jù)塊分布的一致性，降低了基分類器的多樣性，影響集成模型的精度。為增加基分類器的多樣性，可以采用子空間抽樣的方法，對RSP數(shù)據(jù)塊抽取不同的屬性子集來學(xué)習(xí)基分類器。給定大數(shù)據(jù)D的屬性變量集合{A1,A2,…,AM}和Q個RSP數(shù)據(jù)塊集合{D1,D2,…,DQ}，為每個RSP數(shù)據(jù)塊隨機抽取一個L維的子空間，得到Q個不同的子空間。

根據(jù)Alpha計算框架，子空間抽樣可以在節(jié)點上的RSP數(shù)據(jù)塊獨立進行，對每個RSP數(shù)據(jù)塊的子空間數(shù)據(jù)進行獨立建模，生成基分類器{h′1,h′2,…,h′Q}，最后獲得集成模型

由于每個基模型h′q，q∈{1,2,…,Q}從不同子空間數(shù)據(jù)得來，因此增加了基模型的多樣性，提高漸近集成學(xué)習(xí)模型的性能。

3.4 半監(jiān)督集成學(xué)習(xí)

對于含有少量有標簽數(shù)據(jù)和大量無標簽數(shù)據(jù)的大數(shù)據(jù)，采用RSP數(shù)據(jù)模型在Alpha計算框架下最大限度地利用無標簽數(shù)據(jù)提升基于有標簽數(shù)據(jù)訓(xùn)練的集成模型的泛化能力。半監(jiān)督集成學(xué)習(xí)[19]是一種融合了半監(jiān)督學(xué)習(xí)和集成學(xué)習(xí)優(yōu)勢的學(xué)習(xí)方法，基于RSP數(shù)據(jù)模型，在Alpha計算框架下可以設(shè)計如下集成學(xué)習(xí)算法：

（1）隨機抽取Q個RSP數(shù)據(jù)塊{D1,D2,…,DQ}，將這些數(shù)據(jù)塊中的有標簽數(shù)據(jù)抽取出來合并成一個訓(xùn)練數(shù)據(jù)集DT。

（2）對DT做Q次放回抽樣生成Q個訓(xùn)練數(shù)據(jù)集，放回{D1,D2,…,DQ}的相應(yīng)節(jié)點，根據(jù)Alpha框架訓(xùn)練個基模型，并構(gòu)建集成模型。

（3）使用H(0)對{D1,D2,…,DQ}中的無標簽數(shù)據(jù)進行打標。

（4）將打標的數(shù)據(jù)與同節(jié)點的相應(yīng)訓(xùn)練數(shù)據(jù)合并，重新訓(xùn)練一組基模型，并構(gòu)建集成模型。再用H(1)對中無標簽數(shù)據(jù)進行打標。不斷重復(fù)上述過程，直至集成模型表現(xiàn)穩(wěn)定。

獲得穩(wěn)定的模型H后，用它對其他沒有選擇的RSP數(shù)據(jù)塊中無類標的數(shù)據(jù)進行打標。如果有類標的數(shù)據(jù)極少，可以抽取大數(shù)據(jù)所有有類標的數(shù)據(jù)做有放回抽樣。

3.5 聚類集成

基于大數(shù)據(jù)D的RSP數(shù)據(jù)塊{D1,D2,…,DK}的聚類集成是一大挑戰(zhàn)，因為已有的聚類集成方法都是集成同一數(shù)據(jù)集的不同聚類結(jié)果，而被聚類的對象是同一對象集合[20]，在集成不同聚類結(jié)果時，有相同的對象標識可以參考。而不同的RSP數(shù)據(jù)塊包含不同的對象集合，在集成不同RSP數(shù)據(jù)塊聚類結(jié)果時沒有相同的標識可以參考。因此，需要采用不同RSP數(shù)據(jù)塊的簇的統(tǒng)計特征集成聚類結(jié)果。

基于RSP數(shù)據(jù)塊的聚類集成過程可以采用不同的聚類算法[21-22]生成每個RSP數(shù)據(jù)塊的聚類簇，可以采用不同的簇之間的相似性度量，可以采用不同的簇合并方法進行簇的合并，整個過程可以在Alpha計算框架上完成。

3.6 異常點檢測

異常點檢測[23]是數(shù)據(jù)分析的一個重要任務(wù)，在許多領(lǐng)域有應(yīng)用需求，大數(shù)據(jù)中的異常點檢測也是當(dāng)前的一大挑戰(zhàn)，RSP數(shù)據(jù)模型提供了異常點檢測的新途徑。

基于RSP數(shù)據(jù)塊的異常點檢測通過兩步進行：第一步是從隨機選出的Q個RSP數(shù)據(jù)塊{D1,D2,…,DQ}中發(fā)現(xiàn)異常點，已有的異常點檢查算法都可以在這一步采用；第二步是判定從每個RSP數(shù)據(jù)塊發(fā)現(xiàn)的異常點是否是大數(shù)據(jù)的異常點。假設(shè)數(shù)據(jù)，是RSP數(shù)據(jù)塊Dq的異常點，可以用下面兩種方法判斷是否為大數(shù)據(jù)D的異常點。

（1）基于數(shù)據(jù)塊的概率密度函數(shù)判定法：對于給定的閾值ε＞0和顯著性水平α，檢驗，p=1，2，…，Q且p≠q成立的次數(shù)，如果未達到某種假設(shè)檢驗的標準，則認為是大數(shù)據(jù)的異常點。

（2）基于數(shù)據(jù)信息量的判定法：即將RSP數(shù)據(jù)塊Dq的異常點加到其他RSP數(shù)據(jù)塊上會否引起信息量的激增。通常情況下，非異常數(shù)據(jù)的增加不會引起數(shù)據(jù)集信息量的激增。如果未能夠引起大多數(shù)RSP數(shù)據(jù)塊信息量的激增，那么則認為是大數(shù)據(jù)的異常點。

4 結(jié)束語

RSP數(shù)據(jù)模型將大數(shù)據(jù)劃分成隨機樣本數(shù)據(jù)塊文件分布式存儲，由于任何一個RSP數(shù)據(jù)塊的分布都與大數(shù)據(jù)的分布保持一致，因此大數(shù)據(jù)的統(tǒng)計特征可以用RSP數(shù)據(jù)塊來估計，大數(shù)據(jù)的分類、聚類、回歸等模型可以用隨機抽取的少量RSP數(shù)據(jù)塊來建立。Alpha計算框架提供了分布式環(huán)境下迭代漸近式的集成模型學(xué)習(xí)流程。任何大數(shù)據(jù)，一旦轉(zhuǎn)換成RSP數(shù)據(jù)塊后，大數(shù)據(jù)的分析就轉(zhuǎn)換成RSP數(shù)據(jù)塊的分析。因為單個RSP數(shù)據(jù)塊就可以在集群的單個節(jié)點上獨立計算，采用本文介紹的RSP數(shù)據(jù)模型和Alpha計算框架技術(shù)進行大數(shù)據(jù)分析極大地降低了集群計算資源的約束，提高了集群系統(tǒng)大數(shù)據(jù)處理與分析的擴展能力，在有限計算資源的集群上可以實現(xiàn)TB級大數(shù)據(jù)分析和建模能力。

對比現(xiàn)有的分布式大數(shù)據(jù)計算方法和分析技術(shù)，RSP數(shù)據(jù)模型在兩個方面取得了突破：

（1）在分而治之的策略下，用隨機抽取的少量RSP數(shù)據(jù)塊計算取代了大數(shù)據(jù)所有數(shù)據(jù)塊的計算，提高了計算效率和擴展能力；

（2）由于大數(shù)據(jù)的隨機樣本已經(jīng)預(yù)先生成，不再需要分布式環(huán)境面向大數(shù)據(jù)所有記錄的簡單隨機抽樣操作。如果需要隨機樣本數(shù)據(jù)，隨機抽取RSP數(shù)據(jù)塊就可得到，計算量大大地降低。

第一個問題是目前大數(shù)據(jù)分析的主要技術(shù)瓶頸，Hadoop MapReduce和Spark采用的HDFS文件系統(tǒng)存儲大數(shù)據(jù)，由于HDFS的數(shù)據(jù)塊不是大數(shù)據(jù)的隨機樣本，因此要取得正確的結(jié)果，必須計算整個大數(shù)據(jù)，計算能力受到計算資源限制，特別是內(nèi)存資源的約束。

除上述兩個基本突破外，RSP數(shù)據(jù)模型和Alpha計算框架還帶來了如下兩個優(yōu)勢：

（1）由于每個數(shù)據(jù)塊在單個計算節(jié)點獨立計算，現(xiàn)有的串行算法都可以直接使用，不再需要并行算法，降低了算法并行化的成本。

（2）可以實現(xiàn)RSP數(shù)據(jù)塊存儲系統(tǒng)與大數(shù)據(jù)分析平臺的分離。因為采用Alpha計算框架，在分批計算基模型時，可以從RSP數(shù)據(jù)塊存儲系統(tǒng)中隨機抽取少量RSP數(shù)據(jù)塊，下載到分析平臺建模和集成，不需要在存儲RSP大數(shù)據(jù)的平臺上直接運算，可以很好地實現(xiàn)大數(shù)據(jù)的存儲共享。

RSP數(shù)據(jù)模型和Alpha計算框架是為TB級以上大數(shù)據(jù)的分析設(shè)計開發(fā)的新技術(shù)，許多大數(shù)據(jù)分析任務(wù)[24-25]都可以采用此技術(shù)完成。目前筆者團隊所完成的工作還只是實現(xiàn)一些基本功能，很多理論和技術(shù)問題需要深入研究解決。但是，初期的成果已經(jīng)展示出這一新技術(shù)的發(fā)展前景，為大數(shù)據(jù)分析提供了一個新的可選擇方案，可以促進大數(shù)據(jù)的分析與應(yīng)用技術(shù)的發(fā)展。