李姚舜，劉黎志

智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室（武漢工程大學(xué)），湖北 武漢 430205

邏輯回歸算法是機(jī)器學(xué)習(xí)領(lǐng)域的經(jīng)典算法，雖然它使用起來比較簡單，但是在各個(gè)行業(yè)中使用效率很高。邏輯回歸模型僅在線性回歸的基礎(chǔ)上，套用了一個(gè)邏輯函數(shù)，使其成為了一種二分類算法，主要用于尋找危險(xiǎn)因素、預(yù)測(cè)和判別等二分類模型［1-3］。有很多研究人員通過建立多個(gè)分類器或者改進(jìn)邏輯回歸的損失函數(shù)等方法，讓邏輯回歸可以解決多分類問題［4-6］。隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)量已經(jīng)不僅僅局限于PB的范圍，算法的計(jì)算過程還要求能夠快速處理大批量的數(shù)據(jù)集。邏輯回歸算法在計(jì)算過程中，不可避免需要對(duì)全局訓(xùn)練數(shù)據(jù)進(jìn)行遍歷以更新參數(shù)，這種串行運(yùn)算隨著訓(xùn)練數(shù)據(jù)集的增加，所消耗的資源也會(huì)難以估計(jì)，有很多研究人員也從硬件和算法優(yōu)化上提出了優(yōu)化的方法［7-8］。目前Apache基金會(huì)開發(fā)的Hadoop分布式框架，占據(jù)了大數(shù)據(jù)處理的龐大市場(chǎng)，已經(jīng)成為大數(shù)據(jù)開發(fā)的標(biāo)準(zhǔn)。Hadoop中的HDFS的數(shù)據(jù)管理能力、MapReduce處理任務(wù)時(shí)的高效率以及它的開源特性，使它在同類的分布式系統(tǒng)中大放異彩［9-11］。MapReduce是Hadoop中的一個(gè)分布式計(jì)算框架，它將一項(xiàng)繁雜的計(jì)算任務(wù)劃分為幾項(xiàng)相對(duì)較輕的計(jì)算任務(wù)，交由多個(gè)計(jì)算節(jié)點(diǎn)并行處理以加速任務(wù)進(jìn)程［12-15］。本文就如何在MapReduce框架下改進(jìn)邏輯回歸的參數(shù)訓(xùn)練過程進(jìn)行討論，并與單節(jié)點(diǎn)環(huán)境下的訓(xùn)練過程進(jìn)行比較，并通過實(shí)驗(yàn)進(jìn)行驗(yàn)證。

1 研究背景

邏輯回歸的原理是將樣本的特征與樣本發(fā)生的概率聯(lián)系起來，計(jì)算結(jié)果是通過樣本的特征來擬合計(jì)算出一個(gè)事件發(fā)生的概率，它實(shí)際上是一種分類模型，主要用于解決二分類問題。

邏輯回歸的線性決策邊界形式如下［16］：

其中θn表示第n個(gè)特征參數(shù)，xn表示一行樣本的第n個(gè)特征值。

其回歸預(yù)測(cè)利用了Sigmoid函數(shù)，形式如下：

構(gòu)造預(yù)測(cè)函數(shù)為：

hθ(x)的值表示結(jié)果取1的概率。設(shè)訓(xùn)練數(shù)據(jù)集中的樣本數(shù)量為m，基于最大似然估計(jì)推導(dǎo)，得到的損失函數(shù)如下：

與線性回歸相比，邏輯回歸的損失函數(shù)并不能推導(dǎo)出一個(gè)正規(guī)方程解，即J(θ)并沒有數(shù)學(xué)的解析解，所以只能使用梯度法進(jìn)行求解。此處J(θ)中乘了一個(gè)負(fù)的系數(shù)因此采用梯度下降算法求J(θ)取最小值時(shí)的θ為所需要的最佳系數(shù)，θ參數(shù)更新過程為：

其中α為學(xué)習(xí)率。對(duì)J(θ)求偏導(dǎo)數(shù)的結(jié)果為：

從參數(shù)更新過程中可以看出，式（6）（即計(jì)算梯度向量）是最基本的步驟，而式（6）中的在計(jì)算過程中只需要進(jìn)行向量間的點(diǎn)乘、相加，此處可以將求和過程拆分成相互獨(dú)立的計(jì)算步驟，即對(duì)每行數(shù)據(jù)均單獨(dú)計(jì)算最后再歸并計(jì)算求和結(jié)果，并代入式（6）中得到目標(biāo)函數(shù)的梯度向量。

通過分析，可以考慮對(duì)式（6）中的求和計(jì)算進(jìn)行改進(jìn)以達(dá)到并行化的目的。若將訓(xùn)練數(shù)據(jù)集拆分為{Split(1),Split(2),…,Split(s)}等s個(gè)分片，每個(gè)分片中有p條數(shù)據(jù)（p不一定相同），將每個(gè)分片交由一個(gè)節(jié)點(diǎn)獨(dú)立計(jì)算，最后將結(jié)果進(jìn)行匯總，則式（6）求偏導(dǎo)數(shù)過程可轉(zhuǎn)化為：

其中Spli（tt）表示第t個(gè)分片中的數(shù)據(jù)。綜上所述，θ的更新過程可以表示為：

2 批量梯度下降算法并行化

2.1 批量梯度下降算法

梯度法是一種基于搜索的最優(yōu)化方法，它是人工智能領(lǐng)域的一個(gè)非常重要的方法，但是它的作用是用于優(yōu)化一個(gè)目標(biāo)函數(shù)，如果要最小化一個(gè)損失函數(shù)，使用的就是梯度下降法，如果要最大化一個(gè)效用函數(shù)，使用的是梯度上升法。

式（5）中采用梯度下降算法求解損失函數(shù)最小值，有兩種不同的形式：批量梯度下降（batch gradient descent，BGD）、隨機(jī)梯度下降（stochastic gradient descent，SGD）。由于SGD在每次迭代過程只用到一個(gè)訓(xùn)練數(shù)據(jù)來更新參數(shù)，使得SGD并不是每次迭代都向著整體最優(yōu)化方向，其在解空間的搜索過程看起來很盲目。與SGD相比，BGD每次學(xué)習(xí)都使用整個(gè)訓(xùn)練集，而邏輯回歸的是一個(gè)凸函數(shù)，沒有局部最優(yōu)解，只有唯一的全局最優(yōu)解，因此選用BGD求解J(θ)最小值。BGD可以保證每次更新都會(huì)朝著正確的方向進(jìn)行，最后能夠使訓(xùn)練過程收斂于全局極值點(diǎn)，而且BGD對(duì)每行樣本都進(jìn)行了計(jì)算處理，因此也更能夠改進(jìn)為并行化算法。

2.2 基于MapReduce的批量梯度下降

MapReduce是一種可用于數(shù)據(jù)處理的編程框架，采用“分而治之”的思想，把對(duì)大規(guī)模數(shù)據(jù)集的操作，分發(fā)給各個(gè)子節(jié)點(diǎn)共同完成，然后通過整合各個(gè)節(jié)點(diǎn)的中間結(jié)果，得到最終結(jié)果。MapReduce把處理過程高度抽象為map和reduce兩個(gè)函數(shù)，map負(fù)責(zé)把任務(wù)分解成多個(gè)子任務(wù)，reduce負(fù)責(zé)把分解后多個(gè)子任務(wù)處理的結(jié)果匯總起來。

圖1 MapReduce工作流程Fig.1 MapReduce workflow

在MapReduce框架下，采用JDK編程環(huán)境，矩陣運(yùn)算在編程過程中均可轉(zhuǎn)化為循環(huán)操作，實(shí)驗(yàn)過程中將矩陣向量均作為一維數(shù)組處理。

邏輯回歸中的BGD算法并行化步驟如下：

2.2.1 Split分片 將數(shù)據(jù)集放入HDFS文件系統(tǒng)下，當(dāng)Job開始時(shí)，MapReduce會(huì)讀取數(shù)據(jù)文件并按照HDFS數(shù)據(jù)塊大小進(jìn)行分片{Split(1),Split(2),…,Split(s)}，每一個(gè)分片交由一個(gè)Map節(jié)點(diǎn)進(jìn)行處理。

2.2.2 解析鍵值對(duì) MapReduce處理數(shù)據(jù)的最小單位是鍵值對(duì)，當(dāng)分片Split（t）中的數(shù)據(jù)輸入map函數(shù)之前，會(huì)將其按照默認(rèn)規(guī)則轉(zhuǎn)化為“<文本起始位置，文本內(nèi)容>”的鍵值對(duì)形式，分片中的每一行樣本便會(huì)轉(zhuǎn)化為一個(gè)輸入鍵值對(duì)

其中x(ni)表示第i行的第n個(gè)特征值，y(i)表示第i行的標(biāo)簽值。

2.2.3 Map過程 每一個(gè)分片由一個(gè)Map節(jié)點(diǎn)處理，每解析出分片中的一條記錄便會(huì)調(diào)用一個(gè)map函數(shù)。只需要將value值x1(i),x(2i),…,x(ni),y(i)（此時(shí)為文本形式）通過Java分割函數(shù)分割為字符串?dāng)?shù)組然后將其中的特征值存儲(chǔ)到數(shù)組中，在存儲(chǔ)過程中，須對(duì)每一個(gè)數(shù)組手動(dòng)添加一個(gè)參數(shù)偏移量x(0i)（此處取常量1.0）；將標(biāo)簽值存儲(chǔ)到標(biāo)簽變量 y=y(i)中，從而達(dá)到獲取特征值與標(biāo)簽值的效果。

輸出完成后map函數(shù)結(jié)束，當(dāng)分片Spli（tt）中的所有樣本均被map函數(shù)處理后，該分片的Map過程結(jié)束。當(dāng)所有分片的Map過程均完成處理后，整個(gè)Job的Map過程結(jié)束，所有的輸出結(jié)果會(huì)溢出到HDFS本地磁盤中保存為一個(gè)文件。

2.2.4 Combine過程 此過程是對(duì)Reduce過程的優(yōu)化，如果將所有的鍵值對(duì)均傳輸給Reduce過程進(jìn)行處理，勢(shì)必要耗費(fèi)大量的網(wǎng)絡(luò)傳輸資源。因此Map在輸出結(jié)果到磁盤之前，會(huì)先將數(shù)據(jù)在Combine過程中提前處理，將鍵值對(duì)中key相同的value值進(jìn)行求和，得到當(dāng)前分片中的向量，將向量按照“＜參數(shù)序號(hào)的鍵值對(duì)形式整理后再進(jìn)行輸出。

2.2.5 排序溢寫過程 每一個(gè)分片處理完成后均會(huì)輸出2.2.4中描述的鍵值對(duì)，所有分片的輸出結(jié)果會(huì)傳給排序溢寫（Shuffle）過程進(jìn)行排序、歸并處理，再將結(jié)果傳給Reduce階段進(jìn)行處理。整理結(jié)果會(huì)按照“＞＞”的鍵值對(duì)形式進(jìn)行輸出。

2.2.6 歸并過程 歸并（Reduce）輸出時(shí)為保證將更新后的所有參數(shù)均同時(shí)輸出，在Job過程中設(shè)置Reduce的個(gè)數(shù)為1，即將所有的匯總結(jié)果均傳給同一個(gè)Reduce節(jié)點(diǎn)進(jìn)行處理。將同一個(gè)key中value值進(jìn)行求和運(yùn)算，得到代入式（7）求和得到代入式（8）更新參數(shù)，將結(jié)果以“＜參數(shù)序號(hào)j,θj＞”的鍵值對(duì)形式輸出。輸出完成后Reduce過程結(jié)束，一次參數(shù)更新過程完成，循環(huán)上述過程，直至參數(shù)收斂，便完成訓(xùn)練。

2.2.7 參數(shù)收斂過程判斷

1）判斷θ向量更新后的變化距離的平方和，若值d小于指定閾值，則判斷系數(shù)已經(jīng)收斂：

2）訓(xùn)練數(shù)據(jù)集按設(shè)的次數(shù)結(jié)束迭代后，計(jì)算最后一次更新的θ與上一次θ的變化距離的平方和，即

3）若d小于指定閾值，則判斷系數(shù)已經(jīng)收斂。

2.3 算法的具體實(shí)現(xiàn)

Function map（regex，theta［］，data）

輸入：regex←訓(xùn)練數(shù)據(jù)分割字符串，theta［］←回歸系數(shù)向量，data←訓(xùn)練數(shù)據(jù)集文件夾路徑

2.3.2 算法2 Combiner過程歸并各分片輸出結(jié)果，計(jì)算

Function combiner（）

Begin

1： for value←values［0］to values［values.length-1］

2：do sum←sum+value End combiner

2.3.3 算法3 Reduce過程合并所有分片輸出結(jié)果，計(jì)算更新參數(shù)

Function reduce（，alpha）

輸出：鍵值對(duì)＜參數(shù)序號(hào)j,θj＞

2.3.4 算法4 開始一個(gè)訓(xùn)練過程（Job），調(diào)用Map、Combiner、Reduce過程，輸出更新后參數(shù)

Function trainData（data，result，theta［］，last-Theta［］，alpha，regex，diff=100）

輸入：result←輸出文件夾路徑，lastTheta［］←上一次訓(xùn)練的回歸系數(shù)向量，diff←誤差初始值輸出：更新后參數(shù)

3 實(shí) 驗(yàn)

實(shí)驗(yàn)用服務(wù)器為機(jī)械革命s1筆記本，其配置為1個(gè)物理CPU（Intel i7-8550u 1.8 GHZ，CPU含4核心8線程），16 GB內(nèi)存，1T硬盤，1個(gè)物理網(wǎng)卡。服務(wù)器安裝win10專業(yè)版操作系統(tǒng)，使用VMware Workstation Pro15軟件新建3個(gè)虛擬機(jī)，每個(gè)虛擬機(jī)的配置為1內(nèi)核CPU，2 GB內(nèi)存，20 GB硬盤，1個(gè)物理網(wǎng)卡。每個(gè)虛擬機(jī)安裝CentOS7操作系統(tǒng)，Hadoop 2.7.3分布式計(jì)算平臺(tái)，組成含1個(gè)主節(jié)點(diǎn)，2個(gè)從節(jié)點(diǎn)的集群。使用eclipse4.11、Java SE 1.8作為開發(fā)環(huán)境。

實(shí)驗(yàn)內(nèi)容分為兩部分，第一部分驗(yàn)證并行MapReduce并行化結(jié)果的正確性，第二部分將分布式集群運(yùn)行結(jié)果與單節(jié)點(diǎn)運(yùn)算結(jié)果進(jìn)行比較，說明并行化集群的優(yōu)勢(shì)所在。

實(shí)驗(yàn)中使用Java語言構(gòu)建了一個(gè)針對(duì)大規(guī)模抵押貸款數(shù)據(jù)的邏輯回歸分類模型，用于預(yù)測(cè)客戶是否會(huì)如期歸還貸款，數(shù)據(jù)集中共包含5個(gè)樣本特征，數(shù)據(jù)集描述如表1所示。

表1 抵押貸款數(shù)據(jù)集描述Tab.1 Description of mortgage loan data set

取2001至2005年的數(shù)據(jù)樣本進(jìn)行分析測(cè)試，每一年的數(shù)據(jù)文件中包含100萬條數(shù)據(jù)樣本，以9∶1的比例劃分訓(xùn)練集和測(cè)試集，即在每一年的數(shù)據(jù)文件中取90萬條訓(xùn)練數(shù)據(jù)集、10萬條測(cè)試數(shù)據(jù)集，最終試驗(yàn)時(shí)共包含450萬條訓(xùn)練數(shù)據(jù)和50萬條測(cè)試數(shù)據(jù)。

3.1 驗(yàn)證并行化實(shí)驗(yàn)結(jié)果正確

取50萬條訓(xùn)練數(shù)據(jù)分別在集群環(huán)境和單節(jié)點(diǎn)環(huán)境下進(jìn)行測(cè)試，單機(jī)訓(xùn)練的過程此處不再進(jìn)行贅述，實(shí)驗(yàn)所得兩種環(huán)境下訓(xùn)練結(jié)果相同，可以驗(yàn)證并行化改進(jìn)算法思路正確。參數(shù)訓(xùn)練結(jié)果如表2所示。

表2 小數(shù)據(jù)集參數(shù)訓(xùn)練結(jié)果Tab.2 Training results of small data set's parameters

3.2 集群與單機(jī)環(huán)境下訓(xùn)練結(jié)果比較

在上一步測(cè)試的環(huán)境下，每次添加80萬條數(shù)據(jù)，在單機(jī)和集群中分別迭代運(yùn)算1000次，統(tǒng)計(jì)兩者的運(yùn)行時(shí)間，以訓(xùn)練數(shù)據(jù)總量Data為橫坐標(biāo)，集群與單機(jī)的運(yùn)行時(shí)間比λ（倍）為縱坐標(biāo)，畫出對(duì)應(yīng)的散點(diǎn)圖如圖2所示。

理想情況下，集群中有3個(gè)節(jié)點(diǎn)參與運(yùn)算，時(shí)間比λ應(yīng)該在3倍左右。實(shí)際實(shí)驗(yàn)中，在初期訓(xùn)練數(shù)據(jù)集較小的情況下，運(yùn)行效率沒有達(dá)到預(yù)測(cè)值，但是隨著訓(xùn)練數(shù)據(jù)集的擴(kuò)大，集群運(yùn)行效率達(dá)到理想值，甚至超過理想值。原因在于MapReduce過程中分割文件、傳輸數(shù)據(jù)均包含大量的文件輸入輸出操作，在數(shù)據(jù)集較小時(shí)，消耗資源不能忽略不計(jì)。

圖2 集群與單機(jī)訓(xùn)練時(shí)間比Fig.2 Time ratio between cluster and single machine training

4 結(jié) 語

本文基于MapReduce分布式計(jì)算框架，提出了邏輯回歸中BGD算法訓(xùn)練參數(shù)時(shí)的并行處理辦法，實(shí)驗(yàn)結(jié)果表明，這一思路可行，集群環(huán)境下的運(yùn)算效率顯著提高。在實(shí)際應(yīng)用過程中，隨著節(jié)點(diǎn)數(shù)量的增加以及集群計(jì)算性能的提升，單位時(shí)間內(nèi)能夠處理的數(shù)據(jù)量也會(huì)越來越多。在實(shí)驗(yàn)過程中沒有從根本上改進(jìn)BGD算法，只是將求和過程進(jìn)行分解，驗(yàn)證了并行化結(jié)果的正確以及高效性。在后續(xù)實(shí)驗(yàn)和研究過程中，將試圖結(jié)合算法優(yōu)化以及集群平臺(tái)升級(jí)，從算法、軟件和硬件平臺(tái)三方面使邏輯回歸等機(jī)器學(xué)習(xí)算法能適應(yīng)更多生產(chǎn)環(huán)境。