基于MapReduce的大數(shù)據(jù)主動學(xué)習(xí)

翟俊海,張素芳,王 聰,沈 矗,劉曉萌

(1.河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,河北 保定 071002; 2. 河北省機器學(xué)習(xí)與計算智能重點實驗室(河北大學(xué)),河北 保定 071002; 3.中國氣象局氣象干部培訓(xùn)學(xué)院 河北分院,河北 保定 071002)(*通信作者電子郵箱mczsf@126.com)

0 引言

大數(shù)據(jù)具有以下幾個特征[1-3]:海量(Volume)、多模態(tài)(Variety)、變化速度快(Velocity)、蘊含價值高(Value)和可靠性高(Veracity)。在大數(shù)據(jù)環(huán)境下,傳統(tǒng)的機器學(xué)習(xí)面臨著巨大的挑戰(zhàn),其中也包括主動學(xué)習(xí)[4-5]。主動學(xué)習(xí)算法大致可以分為兩大類:基于池的主動學(xué)習(xí)算法和基于流的主動學(xué)習(xí)算法。

在基于池的主動學(xué)習(xí)研究中,主要集中在新的樣例選取策略和應(yīng)用研究上。Huang等[6]在文獻(xiàn)中定義了樣例代表性的概念,并將樣例的信息量和代表性結(jié)合起來,提出了一種選擇既富含信息量又具有代表性的無類標(biāo)樣例的算法,該方法受到了國內(nèi)外同行的好評。在文獻(xiàn)[6]的基礎(chǔ)上,Du等[7]進(jìn)一步研究了基于信息量和代表性的主動學(xué)習(xí)算法。傳統(tǒng)的主動學(xué)習(xí)算法對已經(jīng)進(jìn)行標(biāo)注的樣例不再進(jìn)行改變,Zhang等[8]針對這一問題,提出了一種雙向主動學(xué)習(xí)算法,對已經(jīng)進(jìn)行標(biāo)注的樣例還可以刪除,用這種方法選擇出的樣例具有更高的質(zhì)量,用標(biāo)注類標(biāo)的樣例訓(xùn)練出的分類器具有更強的泛化能力。在批處理模式的主動學(xué)習(xí)中,樣例塊的大小是固定的,Chakraborty等[9]提出了一種自適應(yīng)的批處理主動學(xué)習(xí)算法,并用基于梯度下降的方法優(yōu)化主動樣例選擇的策略。與固定塊模式的主動學(xué)習(xí)算法相比,用該算法選擇的樣例更具代表性?；谂判虻乃枷?Cardoso等[10]從另一個角度改進(jìn)了批處理主動學(xué)習(xí)方法,提出了一種排序批處理主動學(xué)習(xí)算法,取得了很好的效果。而Long等[11]通過優(yōu)化期望損失,提出了一種針對排序?qū)W習(xí)的主動學(xué)習(xí)算法,這兩種主動學(xué)習(xí)算法有異曲同工之處。受集成學(xué)習(xí)中分類器多樣性概念的啟發(fā),Gu等[12]定義了樣例多樣性的概念,提出了一種組合樣例不確定性和多樣性的主動學(xué)習(xí)算法,并應(yīng)用于圖像分類,取得了很好的效果。Wang等[13]將樣例的多樣性和信息量結(jié)合起來,提出了一種多示例主動學(xué)習(xí)算法。Du等[14]將主動學(xué)習(xí)推廣到多標(biāo)簽學(xué)習(xí)的情況,提出了一種基于最大相關(guān)熵的多標(biāo)簽主動學(xué)習(xí)算法,并應(yīng)用于圖像標(biāo)注,該方法擴展了主動學(xué)習(xí)的應(yīng)用范疇,具有重要的理論及應(yīng)用價值。Shen等[15]將分布式的處理機制引入到主動學(xué)習(xí)中,設(shè)計了分布式樣本選擇策略和分布式主動學(xué)習(xí)算法,并實驗驗證了算法的有效性。Lipor等[16]將主動樣例選擇的思想應(yīng)用到信號處理中的空域信號選擇,提出了一種基于距離懲罰的主動學(xué)習(xí)方法。

基于流的主動學(xué)習(xí)也可以看作基于池的主動學(xué)習(xí)的在線版本。這類方法早期代表性的工作包括:Cohn等[17]提出的方法和Dagan等[18]提出的方法。與基于池的主動學(xué)習(xí)相比,基于流的主動學(xué)習(xí)效率較低,因此研究相對較少。近幾年,比較有代表性的工作包括:Smailovic等[19]針對金融領(lǐng)域數(shù)據(jù)語義分析,提出的一種基于流的主動學(xué)習(xí)算法;該算法用支持向量機作為分類器,用不確定性作為選擇無類別樣例的啟發(fā)式?；跇永訖?quán)機制,Bouguelia等[20]提出的一種自適應(yīng)流主動學(xué)習(xí)算法。

截至目前,無論是基于池的主動學(xué)習(xí)還是基于流的主動學(xué)習(xí),研究人員提出的算法都是針對中小規(guī)模的主動學(xué)習(xí)問題。針對大規(guī)模主動學(xué)習(xí)問題的研究還很少,僅有Silva等[21]針對Twitter大數(shù)據(jù)提出了一種主動流形學(xué)習(xí)方法。然而,該方法是用流形學(xué)習(xí)方法進(jìn)行降維,用基于支持向量機的主動學(xué)習(xí)方法減少有類標(biāo)樣例數(shù)據(jù)集的大小,嚴(yán)格地說還不是真正意義上的大數(shù)據(jù)主動學(xué)習(xí)[4,22-23]。

本文基于MapReduce[24]提出了一種大數(shù)據(jù)主動學(xué)習(xí)算法——MR-AL(MapReduce based Active Learning)算法。該算法以并行的方式在云計算平臺上從無類別標(biāo)簽的大數(shù)據(jù)集中選擇重要的樣例,以信息熵作為無類別標(biāo)簽樣例重要性的度量,以極限學(xué)習(xí)機(Extreme Learning Machine, ELM)作為分類器。

1 基礎(chǔ)知識

1.1 主動學(xué)習(xí)

主動學(xué)習(xí)[4,22-23]可用一個四元組AL刻畫,AL=(C,L,U,O)。其中,C表示分類器,L表示有類別標(biāo)簽的樣例集合,U表示無類別標(biāo)簽的樣例集合,O表示領(lǐng)域?qū)＜?。主動學(xué)習(xí)是一個迭代學(xué)習(xí)的過程,如圖1[23]所示。開始時,L包含少量有類別標(biāo)簽的樣例;然后用某種訓(xùn)練算法從L中訓(xùn)練一個分類器C,并用某種預(yù)定義的度量指標(biāo)評估U中樣例的重要性,選擇若干個重要的樣例交給領(lǐng)域?qū)＜襉進(jìn)行標(biāo)注;然后,將標(biāo)注的樣例添加到L中。重復(fù)這一過程若干次,直到訓(xùn)練出的分類器C具有好的泛化性能,主動學(xué)習(xí)過程結(jié)束。

圖1 主動學(xué)習(xí)過程示意圖Fig. 1 Schematic diagram of active learning process

在主動學(xué)習(xí)中,不確定性是最常用的樣例選擇準(zhǔn)則,這種準(zhǔn)則分為三種[23]:

1)最小置信度準(zhǔn)則。

這種準(zhǔn)則用概率學(xué)習(xí)模型計算或估計樣例的后驗概率,用式(1)選擇樣例。

(1)

2)最大熵準(zhǔn)則。

這種準(zhǔn)則用信息熵度量樣例的不確定性,用式(2)選擇樣例。

(2)

其中:yi表示樣例的類標(biāo)。

3)投票熵準(zhǔn)則。

設(shè)C表示由若干個分類器構(gòu)成的委員會,投票熵準(zhǔn)則用式(3)選擇樣例。

(3)

其中:V(yi)表示類標(biāo)yi獲得的票數(shù)；|C|表示委員會C中包含的分類器個數(shù)。

1.2 MapReduce

MapReduce[24]是一種簡單易用的軟件編程框架,它采用“分而治之”的思想,把對大數(shù)據(jù)的處理分發(fā)到集群的各個節(jié)點上并行完成,接著通過整合各個節(jié)點的中間結(jié)果,得到最終的處理結(jié)果。從MapReduce的名字可以看出,MapReduce處理大數(shù)據(jù)的過程分為兩個階段:Map階段和Reduce階段。用MapReduce解決實際問題時,用戶的應(yīng)用邏輯由Map和Reduce兩個函數(shù)來實現(xiàn)。換句話說,MapReduce處理大數(shù)據(jù)的思路是把大數(shù)據(jù)劃分為相互獨立的數(shù)據(jù)塊,這些數(shù)據(jù)塊以完全并行的方式由Map函數(shù)和Reduce函數(shù)處理。

Map函數(shù)的輸入是一系列鍵值對,用〈K1,V1〉表示。其輸出也是一系列鍵對,把每一個鍵以及與之關(guān)聯(lián)的值組成一個列表,這一過程稱為數(shù)據(jù)重排,重排的結(jié)果用〈K2,LIST(V2)〉表示。Reduce函數(shù)的輸入是〈K2,LIST(V2)〉,其輸出是另一系列鍵值對,用〈K3,V3〉表示。MapReduce的輸入和輸出以及中間結(jié)果均存儲在HDFS(Hadoop Distributed File System)中。MapReduce對用戶是透明的,許多底層細(xì)節(jié)系統(tǒng)自動完成,如數(shù)據(jù)的劃分與分發(fā)、任務(wù)調(diào)度與監(jiān)控、節(jié)點之間的負(fù)載均衡與通信、失敗節(jié)點的檢測與恢復(fù)等。用MapReduce處理數(shù)據(jù)的過程如圖2所示。

圖2 MapReduce處理數(shù)據(jù)的流程Fig. 2 Process of data processing with MapReduce

1.3 極限學(xué)習(xí)機

極限學(xué)習(xí)機(ELM)[25]是訓(xùn)練如圖3所示的單隱含層前饋神經(jīng)網(wǎng)絡(luò)(Single hidden Layer Feed-forward Neural network, SLFN)的隨機化算法。

圖3 單隱含層前饋神經(jīng)網(wǎng)絡(luò)Fig. 3 Feed-forward neural network with single hidden layer

給定訓(xùn)練集D={(xi,yi)|xi∈Rd,yi∈Rk}(1≤i≤n),圖3所示SLFN的輸入與輸出之間是一種線性關(guān)系,可用式(4)表示:

(4)

其中:m是隱含層節(jié)點的個數(shù);g是激活函數(shù);wj是輸入層節(jié)點到隱含層第j個節(jié)點的連接權(quán);bj是隱含層第j個節(jié)點的偏置;βj是隱含層第j個節(jié)點到輸出層節(jié)點的連接權(quán)。在式(4)中,wj和bj是用隨機化方法按著某種概率分布(如均勻分布)給定的,ELM算法的隨機性就體現(xiàn)在這里。而式(4)中的βj是唯一需要確定的參數(shù),可用給定的訓(xùn)練集用最小二乘擬合來估計它。將訓(xùn)練集中的樣例xi(1≤i≤n)逐個代入式(4)中,可得:

(5)

式(5)是由n個線性方程組成的線性方程組,它可以寫成如下的矩陣形式:

Hβ=Y

(6)

其中：

H=

T表示轉(zhuǎn)置;H是單隱含層前饋神經(jīng)網(wǎng)絡(luò)的隱含層輸出矩陣,它的第j列是隱含層第j個節(jié)點相對于輸入x1,x2,…,xn的輸出,它的第i行是隱含層相對于輸入xi的輸出。如果單隱含層前饋神經(jīng)網(wǎng)絡(luò)的隱含層節(jié)點個數(shù)m等于樣例的個數(shù)n,那么矩陣H是可逆的方陣。此時,用訓(xùn)練集得到的單隱含層前饋神經(jīng)網(wǎng)絡(luò)模型沒有誤差,即誤差為零。但一般情況下,m≤n,即隱含層節(jié)點個數(shù)遠(yuǎn)遠(yuǎn)小于訓(xùn)練樣例個數(shù)。此時,H不是一個方陣,方程(6)沒有精確解。根據(jù)線性方程理論,可以通過求解優(yōu)化問題(7)來得到方程(6)的近似解,這種近似解稱為最小范數(shù)最小二乘解。

(7)

優(yōu)化問題(7)的最小范數(shù)最小二乘解由式(8)給出:

(8)

其中：H+是矩陣H的Moore-Penrose廣義逆矩陣。

2 本文算法

大數(shù)據(jù)主動學(xué)習(xí)中的大數(shù)據(jù)是指無類別標(biāo)簽的數(shù)據(jù)集U是大數(shù)據(jù)集,而有類別標(biāo)簽的數(shù)據(jù)集L是中小型數(shù)據(jù)集。本文算法利用MapReduce的分治策略,將大數(shù)據(jù)集U劃分為若干個子集,并部署到不同的云計算節(jié)點上,這些節(jié)點并行地選擇重要的樣例交給專家O進(jìn)行標(biāo)注。因為有類別標(biāo)簽的數(shù)據(jù)集L是中小型數(shù)據(jù)集,所以分類器L的訓(xùn)練是在本地進(jìn)行的。本文MR-AL算法用極限學(xué)習(xí)機作為分類器,用式(2)給出的最大熵原則選擇重要的樣例。為了計算無類別標(biāo)簽樣例的信息熵,需要對ELM的輸出用式(9)的軟最大化函數(shù)進(jìn)行變換,使之成為一個后驗概率分布。

(9)

用MapReduce實現(xiàn)大數(shù)據(jù)主動學(xué)習(xí),關(guān)鍵是Map函數(shù)和Reduce函數(shù)的設(shè)計。在迭代學(xué)習(xí)的過程中,每次都要執(zhí)行Map和Reduce操作,中間還有一個Shuffle操作,主要負(fù)責(zé)在各自的節(jié)點上對中間結(jié)果進(jìn)行合并、排序。Map的輸出是Reduce的輸入,而所有的輸入和輸出都是以鍵值對的形式傳輸?shù)?。其?涉及4個鍵值對,分別加以說明:〈k1,v1〉代表Map的輸入,實際是從HDFS中獲取數(shù)據(jù),k1代表數(shù)據(jù)的偏移量,而v1是數(shù)據(jù);〈k2,v2〉代表Map的輸出,在MR-AL中,經(jīng)過Map的處理,k2代表每個樣例的信息熵的倒數(shù),v2為樣例;〈k3,v3〉代表Reduce的輸入,即Map的輸出,k2=k3,但v3是經(jīng)過Shuffle操作得到的一個集合;〈k4,v4〉代表Reduce的輸出,實際輸出到HDFS中進(jìn)行保存，k4在MR-AL中設(shè)計為空值Nullwritable,它代表利用信息熵準(zhǔn)則選擇出來的樣例。以上是整個MapReduce的鍵值對設(shè)計。具體實現(xiàn)時,在Map階段主要完成的功能包括:使用本地訓(xùn)練的ELM分類器對無類標(biāo)的樣例進(jìn)行預(yù)測,對結(jié)果作軟最大處理,之后計算信息熵,得到樣例的信息熵后,就構(gòu)成了需要的〈k2,v2〉鍵值對。Hadoop的Shuffle階段會以k2,也就是信息熵進(jìn)行排序,Reduce階段功能相對簡單,就是在排好序的數(shù)據(jù)中取出前q個樣例,q為用戶指定的參數(shù),最終輸出〈k4,v4〉,將選擇的樣例保存到HDFS中完成一次迭代。Map函數(shù)和Reduce函數(shù)的偽代碼在算法1和2中給出。

算法1 MR-AL Map函數(shù)。

輸入 〈k1,v1〉, 其中：k1為偏移量,v1為未標(biāo)記樣例。

輸出 〈k2,v2〉, 其中：k2為樣例信息熵的倒數(shù),v2為標(biāo)記后樣例。

對數(shù)據(jù)進(jìn)行預(yù)處理,包括數(shù)據(jù)分片,將分片數(shù)據(jù)變換為矩陣pre_matrix;

ELM.test(pre_matrix), 對數(shù)據(jù)進(jìn)行預(yù)測, 得到predict_matrix;

for(i=0;i

對predict_matrix進(jìn)行軟最大化處理;

end

for(i=0;i

計算樣例的信息熵, 得到entropy;

end

context.write(new DoubleWritable(1/entropy), new Text(value));

算法2 MR-AL Reduce函數(shù)。

輸入 〈k2,v2〉, 其中：k2為熵倒數(shù),v2為已標(biāo)記樣例。

輸出 〈k3,v3〉, 其中：k3為Null值,v3為選擇的樣例。

if(q>0) then

//q為用戶指定的選擇樣例個數(shù)

for(test:v2) do

context.write(Null值,text);

//text為每個已標(biāo)記樣例

end

end

圖4 MR-AL方法在不同數(shù)據(jù)集上的實驗結(jié)果對比Fig. 4 Comparison of experimental results on different data sets by MR-AL

3 實驗與分析

為了驗證本文算法的有效性,在4個數(shù)據(jù)集上與AL-ELM(Active Learning based on ELM)方法[26]進(jìn)行了對比實驗。4個數(shù)據(jù)集中包括1個人工數(shù)據(jù)集和3個UCI數(shù)據(jù)集。人工數(shù)據(jù)集(記為Artificial)是一個兩類數(shù)據(jù)集,由高斯分布產(chǎn)生,兩類服從的高斯分布參數(shù)列于表1中,所用數(shù)據(jù)集的基本信息如表2所示。在實驗中,對于每一個數(shù)據(jù)集,隨機選擇一定數(shù)量的樣例作為初始訓(xùn)練集L,初始訓(xùn)練集L包含的樣例數(shù)列于表2的第5列。對于未選擇的樣例,隱去其類別信息作為無類別標(biāo)簽數(shù)據(jù)集U使用。

實驗所用的Hadoop集群包括一個主節(jié)點和兩個從節(jié)點,每個節(jié)點基本配置信息為:處理器Intel Core i5-2400 3.10 GHz,內(nèi)存4 GB,硬盤10 GB,操作系統(tǒng)為64位ubuntu16.04。每個節(jié)點配置的軟件環(huán)境如下: Java選用的開發(fā)包為jdk-1.8-linux-x64、Hadoop-2.7.3。

在4個數(shù)據(jù)集上進(jìn)行了兩個實驗：一個實驗用于發(fā)現(xiàn)標(biāo)注的樣例數(shù)與分類器測試精度之間的關(guān)系。對于不同的數(shù)據(jù)集,在迭代學(xué)習(xí)的過程中,每一次迭代,選擇q個樣例進(jìn)行標(biāo)注,并記錄分類器的測試精度,實驗結(jié)果如圖4所示。另一個實驗是在測試精度相同的前提下,與AL-ELM進(jìn)行了運行時間的比較,實驗結(jié)果如表3所示。從表3可以看出,本文算法在運行效率上遠(yuǎn)遠(yuǎn)優(yōu)于AL-ELM算法,AL-ELM算法在3個數(shù)據(jù)集上沒有得到運行結(jié)果,而本文算法都能得到運行結(jié)果,從而驗證了本文算法的有效性。

表1 人工數(shù)據(jù)集的高斯分布參數(shù)Tab. 1 Parameters of Gaussian distribution for data set artificial

表2 實驗所用數(shù)據(jù)集的基本信息Tab. 2 Basic information of data sets used in the experiments

表3 MR-AL與AL-ELM在運行時間上的比較 sTab. 3 Comparison of running time between MR-AL and AL-ELM s

4 結(jié)語

利用Hadoop MapReduce自身具有的分治特性,提出了一種大數(shù)據(jù)主動學(xué)習(xí)算法——MR-AL。MR-AL算法以信息熵作為樣例重要性的度量,利用極限學(xué)習(xí)機作為分類器。本文算法思想簡單,易于實現(xiàn),能有效地從無類別標(biāo)簽的大數(shù)據(jù)集中選擇出重要的樣例。與AL-ELM算法的對比實驗結(jié)果表明,本文MR-AL算法在四個數(shù)據(jù)集上均能得到運行結(jié)果,而AL-ELM算法在三個大數(shù)據(jù)集Artificial、Skin和Poker無法得到結(jié)果。進(jìn)一步的工作包括:1)在更多更大的數(shù)據(jù)集上進(jìn)行實驗,以進(jìn)一步說明本文算法具有好的可擴展性;2)研究自適應(yīng)地選擇樣例數(shù)是否可行；3)研究基于Spark的大數(shù)據(jù)主動學(xué)習(xí),并用本文方法進(jìn)行比較,分析兩種方法在泛化能力和運行時間上有無本質(zhì)區(qū)別。