基于MapReduce的大數據主動學習

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

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

0 引言

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

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

基于流的主動學習也可以看作基于池的主動學習的在線版本。這類方法早期代表性的工作包括:Cohn等[17]提出的方法和Dagan等[18]提出的方法。與基于池的主動學習相比,基于流的主動學習效率較低,因此研究相對較少。近幾年,比較有代表性的工作包括:Smailovic等[19]針對金融領域數據語義分析,提出的一種基于流的主動學習算法;該算法用支持向量機作為分類器,用不確定性作為選擇無類別樣例的啟發式。基于樣例加權機制,Bouguelia等[20]提出的一種自適應流主動學習算法。

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

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

1 基礎知識

1.1 主動學習

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

圖1 主動學習過程示意圖Fig. 1 Schematic diagram of active learning process

在主動學習中,不確定性是最常用的樣例選擇準則,這種準則分為三種[23]:

1)最小置信度準則。

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

(1)

2)最大熵準則。

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

(2)

其中:yi表示樣例的類標。

3)投票熵準則。

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

(3)

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

1.2 MapReduce

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

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

圖2 MapReduce處理數據的流程Fig. 2 Process of data processing with MapReduce

1.3 極限學習機

極限學習機(ELM)[25]是訓練如圖3所示的單隱含層前饋神經網絡(Single hidden Layer Feed-forward Neural network, SLFN)的隨機化算法。

圖3 單隱含層前饋神經網絡Fig. 3 Feed-forward neural network with single hidden layer

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

(4)

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

(5)

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

Hβ=Y

(6)

其中：

H=

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

(7)

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

(8)

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

2 本文算法

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

(9)

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

算法1 MR-AL Map函數。

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

輸出 〈k2,v2〉, 其中：k2為樣例信息熵的倒數,v2為標記后樣例。

對數據進行預處理,包括數據分片,將分片數據變換為矩陣pre_matrix;

ELM.test(pre_matrix), 對數據進行預測, 得到predict_matrix;

for(i=0;i

對predict_matrix進行軟最大化處理;

end

for(i=0;i

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

end

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

算法2 MR-AL Reduce函數。

輸入 〈k2,v2〉, 其中：k2為熵倒數,v2為已標記樣例。

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

if(q>0) then

//q為用戶指定的選擇樣例個數

for(test:v2) do

context.write(Null值,text);

//text為每個已標記樣例

end

end

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

3 實驗與分析

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

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

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

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

表2 實驗所用數據集的基本信息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 結語

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