劉牧雷, 徐菲菲

(上海電力學院 計算機科學與技術(shù)學院, 上海 200090)

決策速度和決策正確性是決策問題的兩大核心要素。對于單一的決策問題,當決策方式為確定時,每一次決策可認為是獨立決策。所以,對與海量的不相關(guān)數(shù)據(jù),可以使用并行化的方式來進行決策。對于決策準確性問題,YAO Y Y教授以粗糙集理論為基礎(chǔ),提出了三枝決策理論[1-2]。相較于傳統(tǒng)決策理論,三枝決策理論更加貼合人們在實際生活中的決策方式,并且在代價敏感決策問題上有著更好的表現(xiàn)[3-5]。

在一般的數(shù)據(jù)集中,數(shù)據(jù)對特征的相關(guān)程度并不是均勻的。因此,對于數(shù)據(jù)集中特征明顯的數(shù)據(jù),只需要少量的訓練就會呈現(xiàn)出明顯的決策傾向。由此,如果對數(shù)據(jù)集的決策是分步進行的,那么在決策過程中也會提高決策的效率。

當前,無論是海量數(shù)據(jù)處理,還是并行化運算,Spark都是流行的解決方案。Spark是基于Hadoop平臺的開源云計算平臺,目前廣泛應用于生產(chǎn)實踐中。Spark通過MapReduce[6]計算模型實現(xiàn)并行計算,通過彈性分布式數(shù)據(jù)集(Resilient Distributed Dataset,RDD)數(shù)據(jù)模型實現(xiàn)適合于分布式平臺的數(shù)據(jù)結(jié)構(gòu)。

本文將三枝決策理論與Spark的MapReduce模型相結(jié)合,對數(shù)據(jù)進行并行處理,以提高三枝決策理論的效率,提升決策的準確率。

1 相關(guān)理論概述

1.1 三枝決策

三枝決策是YAO Y Y由概率粗糙集理論提出的一種新決策思想。相較于傳統(tǒng)的“是,否”二枝決策而言,三枝決策提出了一種不同但更為合理的決策思想,即當對象當前提供的信息不足以支撐決策時,采用延遲決策,等待更多信息來完成最終決策。因此,三枝決策可以規(guī)避分類信息不足時盲目決策造成的風險[7]。

在決策粗糙集公式化描述中,X和U是全集的子集,狀態(tài)集合可以表示為Ω={X,X},X和X分別表示屬于X和不屬于X。為了方便描述,子集和子集的狀態(tài)都使用X來表示。狀態(tài)X對應的動作集合為∧={P,B,N},式中,P,B,N分別表示3種判定動作,即x∈POS(X),x∈BND(X),x∈NEG(X)。三枝決策的損失函數(shù)由各個動作帶來的損失決定,如表1所示。表1中,λPP,λBP,λNP表示當x屬于X時采取動作P,B,N產(chǎn)生的損失;λPN,λBN,λNN表示當對象屬于X時采取動作P,B,N時產(chǎn)生的損失。

表1 三枝決策的損失函數(shù)

根據(jù)最小風險決策規(guī)則可得

(P) 當Pr(X|[x])≥α時,x∈POS(X),Pr為條件概率;

(B) 當β

(N) 當Pr(X|[x])≤β時,x∈NEG(X)。

其中

(1)

(2)

且

0≤β<α≤1

(3)

1.2 Spark與并行化

Spark是由UC Berkeley AMP Lab(加州大學伯克利分校的AMP實驗室)開發(fā)的一個基于MapReduce計算模型的通用并行計算平臺[8]。為了實現(xiàn)適合集群化的并行運算,Spark采用了RDD數(shù)據(jù)模型。RDD是Spark的核心概念,通過實現(xiàn)RDD模型,Spark可以進行基于內(nèi)存的快速運算。圖1為Spark運行時的結(jié)構(gòu)示意。

圖1 Spark運行時的結(jié)構(gòu)示意

在Spark運行時,Driver會讀取分布式存儲系統(tǒng)中的數(shù)據(jù)塊,并以RDD的形式固化在多個節(jié)點內(nèi)存中。當任務啟動時,Driver將會以Tasks的形式向節(jié)點分發(fā)任務,節(jié)點在完成任務后向Driver匯報Results。

RDD包括以下5個信息:一是分區(qū)信息,記錄RDD的數(shù)據(jù)分區(qū)的組成;二是依賴信息,記錄當前RDD是由哪些RDD變換得到的;三是計算信息,記錄當前RDD是由哪些運算得到的;四是元信息,記錄了整個數(shù)據(jù)分區(qū)方案;五是元信息,記錄RDD存放的位置是否在內(nèi)存中。

當任務啟動時,Spark會根據(jù)任務,建立由多個步驟組成的DAG作為執(zhí)行計劃。每一個步驟包含了流水線式轉(zhuǎn)換操作。整個執(zhí)行計劃會啟動多個任務分配給每個節(jié)點,由每個節(jié)點根據(jù)自己分配到的執(zhí)行計劃計算各自的任務,完成任務得到目標RDD后,匯報并匯總結(jié)果。Spark的運算流程如圖2所示。圖2中,實線框為RDD;實心框表示RDD的分片;深色方塊的表示已經(jīng)在內(nèi)存中的數(shù)據(jù)。當RDD G執(zhí)行計算時,Spark將會建立如圖2所示的DAG,并按stage1,stage 2,stage 3的順序依次執(zhí)行。

圖2 Spark的運算流程

Spark的任務規(guī)劃器會根據(jù)每臺機器上已有的數(shù)據(jù)分片去規(guī)劃任務計劃,如果數(shù)據(jù)片在節(jié)點的內(nèi)存里,那么直接發(fā)布任務給對應的節(jié)點;如果不在,則尋找RDD的來源。最后,所有的計算結(jié)果會發(fā)送給Driver,得到計算結(jié)果。

2 基于Spark的三枝決策算法

應用三枝決策算法的核心在于兩個問題:一是條件概率Pr(X[x]R)的計算;二是閾值α和β的選取。在基于樸素貝葉斯模型的決策粗糙集理論中,條件概率是在屬性間獨立的假設(shè)下,利用貝葉斯理論推導出來的[9-11]。由此,三枝決策需要結(jié)合貝葉斯分類器作出判別分析后,再進行三枝決策。本文采用二元Logistic回歸模型作為前置分類器,再結(jié)合Spark的分布式計算能力來實現(xiàn)并行化的三枝決策算法。首先,使用二元Logistic回歸,計算每個樣本的條件概率;然后,根據(jù)決策表中的樣本選取相應的損失函數(shù),并計算相應的閾值;最后,根據(jù)閾值與決策規(guī)則確定每個樣本的最終狀態(tài)。

2.1 算法介紹

首先,對于原始數(shù)據(jù)表,構(gòu)建二元Logistic回歸模型。在Spark中,Logistic回歸模型使用Spark mllib庫中的LogisticRegression類構(gòu)建回歸模型。建立模型的常用參數(shù)如表2所示。

表2 Logistic回歸常用參數(shù)

在通常情況下,用scala語言描述建立的LogisticRegression模型的步驟如下:

(1) //建立一個迭代100次,不進行標準化、正則化、不使用彈性網(wǎng)絡(luò)的Logistic回歸模型;

(2) val lr = new LogisticRegression();

(3) .setMaxIter(100);

(4) .setElasticNetParam(0.0);

(5) .setRegParam(0.0);

(6) .setStandraize(false)。

然后,根據(jù)數(shù)據(jù)進行訓練:

(1) //training 為訓練集,test為測試集;

(2) val model = lr.fit(training).transform(test)。

即可獲得原始數(shù)據(jù)經(jīng)過Logistic回歸的分類結(jié)果。獲得的新數(shù)據(jù)結(jié)構(gòu)如表3所示。

表3 LogisticRegression模型結(jié)構(gòu)

在獲得信息表后,就可以進行對應的域的劃分。域的劃分由損失函數(shù)決定,可以根據(jù)決策表中的每一個樣本來選擇合適的損失函數(shù)。根據(jù)定義,對于每一個對象,我們都可以構(gòu)造損失函數(shù),如表4所示。表4中,λi表示第i個對象的損失函數(shù),具體定義由表1描述。

表4 損失函數(shù)的數(shù)據(jù)結(jié)構(gòu)

αi和βi為由損失函數(shù)劃定的閾值。其公式為

(4)

(5)

在Spark中,由Logistic回歸得到的結(jié)果中包含很多參數(shù),這里只使用計算得到的條件概率。根據(jù)條件概率Pr的劃分,可以判斷此對象為正例、反例或延遲決策。判斷方法根據(jù)規(guī)則(P)～(N)得到:

綜上所述,在整個決策過程中,決策粗糙集根據(jù)計算得到的三枝決策的閾值參數(shù)αi和βi,生成相應的決策規(guī)則。二元Logistic回歸模型用來計算先驗概率。在實際中,一般使用統(tǒng)一的損失函數(shù)而不是對每一個樣本分別設(shè)定損失函數(shù),這樣會顯著減少工作量;對于延遲決策的部分,可重復訓練過程,盡可能獲得更多的信息以幫助決策。

2.2 算法流程

基于Logistic回歸的三枝決策算法流程如圖3所示。

圖3 基于Logistic回歸的三枝決策算法流程示意

具體描述如下。

(1) 對于給定的問題選擇相關(guān)的自變量和因變量,構(gòu)造信息表。

(2) 使用二元Logistic回歸建立回歸方程。

(3) 根據(jù)二元Logistic回歸方程,對每一個樣本Ui,計算對應d=1的條件概率Pr[(d=1)|ui],d為樣本狀態(tài)。

(4) 根據(jù)三枝決策模型生成決策規(guī)則:對任意樣本Ui(i=1,2,3,…,n),根據(jù)經(jīng)驗和其他信息,設(shè)定兩個狀態(tài)d=1和(d=1)時采取不同行動的損失函數(shù),并由損失函數(shù)計算相關(guān)的閾值αi和βi。

(5) 確定每一個樣本的最終決策。對于ui∈U,比較Pr((d=1)|ui)與αi和βi的大小關(guān)系。當Pr((d=1)|ui)≥α時,ui的接受狀態(tài)為d=1;當β

(6) 對于延遲決策的部分,回到第2步繼續(xù)整個算法,直到全部得到歸類或到達設(shè)定的精度。

2.3 MapReduce 過程分析

由于整個程序是通過MapReduce模型實現(xiàn)并行化的,所以從MapReduce的角度來描述整個步驟更能體現(xiàn)程序是如何并行運行的。其整體運行流程如圖4所示。

對于有N個特征的分類數(shù)據(jù),其結(jié)構(gòu)如表5所示。表5中,ωi表示第i個特征。

結(jié)合圖4和表5,輸入數(shù)據(jù)的結(jié)構(gòu)為RDD 1。根據(jù)Spark文檔對LogisticRegression模型的描述,所有的特征被描述為一個特征向量。所以,第1步,對RDD 1中的所有特征進行合并,使其成為一個向量,即通過第一次map,得到RDD 2。第2步,對RDD 2中的數(shù)據(jù)進行二元Logistic回歸,得到表3描述結(jié)構(gòu)的RDD 3。第3步,通過select方法在其中選出概率信息得到RDD 4。此時完成第一部分工作。

第4步,構(gòu)建損失函數(shù)表。由于損失函數(shù)是提前設(shè)定的,所以可以從給出的損失函數(shù)表構(gòu)建形式如表4的RDD 5。第5步,計算閾值αi與βi。根據(jù)式(4)和式(5)計算αi和βi得到RDD 6。第6步,通過join操作使RDD 6與RDD 4進行合并,得到的結(jié)果形式如RDD 7。最后,根據(jù)規(guī)則(P1i)～(N1i)即可得到最終的結(jié)果RDD 8。最終結(jié)果保存于prediction項中。

圖4 MapReduce模型下的算法流程描述表5 輸入數(shù)據(jù)結(jié)構(gòu)

結(jié)構(gòu)元素注釋label標簽ω1特征1ω2特征2? ? ωn特征n

3 實驗與結(jié)果分析

在阿里云平臺上搭建實驗環(huán)境。使用3臺阿里云通用計算型ecs.sn1ne.large服務器。服務器配置如表6所示。

表6 服務器配置

測試數(shù)據(jù)集來自UCI開放數(shù)據(jù)集,是一個常用的標準測試數(shù)據(jù)集,由加州大學歐文分校(University of California Irvine,UCI)提供。數(shù)據(jù)集均為分類任務。測試結(jié)果與結(jié)果分析如下。

3.1 Mushroom

Mushroom數(shù)據(jù)集包括傘菌和小傘菌屬中23種假設(shè)樣品的特征。每種物種都被確定為絕對可食用的、絕對有毒的,或具有未知的可食性且不被推薦。后一類與有毒類相結(jié)合。數(shù)據(jù)由逗號分隔,每一行定義了一個樣本,包含可食、頂蓋形狀、頂蓋光滑、頂蓋顏色等共計22種特征。全部樣本總計8 224條。使用三枝決策方法對數(shù)據(jù)集進行分析,采用二元LogisticRegression作為前置分類器,迭代100次,參數(shù)無正則化處理,無歸一化處理。圖5表示了整個數(shù)據(jù)集經(jīng)過二元Logistic回歸后的條件概率分布。其中,橫坐標代表概率值區(qū)間,縱坐標代表區(qū)間內(nèi)樣本出現(xiàn)的頻率。

圖5 Mushroom數(shù)據(jù)集的條件概率分布

由圖5可知,當進行100次迭代后,共有8 025條數(shù)據(jù)分布在區(qū)間(0,0.085)和(0.935,1)內(nèi)。

然后,對不同的邊界取值,以考察精度A與F1兩個指標。其結(jié)果如圖6所示。

圖6 整體準確率指標

(6)

(7)

式中:m——總的樣本個數(shù);

I(·)——指示函數(shù);

p,r——查準率和查全率。

由試驗數(shù)據(jù)可知,對于本輪分類,從精度和F1指標考慮,主要受α的影響。即本輪的分類效果主要由劃分到正域的樣本個數(shù)決定。經(jīng)過計算,在α=0.44時,其分類效果達到最好,三枝決策分類的精度要高于前置分類器的精度,且此時邊界域較小。在分類過程中,邊界域的大小同時影響本輪分類精度和下一輪的精度。由于精度和F1指標的定義都未考察負域劃分的準確率,所以β取值的影響在圖6中體現(xiàn)不明顯。但顯而易見的是,增加正域和負域的范圍可以使邊界域減小,從而在整體上減少分類的輪數(shù),使分類效率提高。從試驗結(jié)果可知,在選取合適的α和β的情況下,三枝決策算法能夠通過后續(xù)的判斷使得分類的精度較前置分類器有所提高。

3.2 connect-4

connect-4 數(shù)據(jù)集包含了所有符合游戲規(guī)則的8種位置。該數(shù)據(jù)集中兩位玩家都還沒有獲得勝利,并且下一步棋完全不受干擾?！畑’表示玩家1,‘o’表示玩家2。最后的結(jié)果為玩家1本局的理論結(jié)果,分別為獲勝(win)、失敗(loss)、和局(draw)。

該問題是一個多分類問題。在處理多分類問題時,邏輯回歸會分別計算3種分類的可能性,并取最高的可能性作為分類結(jié)果。針對本問題采用三枝決策方法,如果數(shù)據(jù)被劃分到負域,那么只能說明有較強的信息表示該數(shù)據(jù)不屬于此分類,但是依然無法判斷數(shù)據(jù)的準確分類。由此,結(jié)合實際問題,本文取β=0,即不設(shè)定負域,只區(qū)分正域和邊界域。圖7展示了當α在[0,1]取值時分類性能的變化。

圖7 不同的邊界值對分類性能的影響

由圖7可知,當α取[0.4,0.5]時,分類的精度有所提高且F1與前置分類器相當。相較于前置分類器,加入三枝決策后,在合適的邊界域范圍內(nèi),分類效果較前置分類器有所提升。在邊界域選擇不好的情況下,精度維持在原來的水平。雖然從精度和F1指標來看,在一定范圍內(nèi),三枝決策的分類效果較前置分類器有所提高,但是無論邊界域以何種方式劃分,總有一部分正例被劃分到邊界域中。因此,就準確率而言,加入三枝決策算法后,其分類準確率較原始分類器有所下降。對于此問題可由多次迭代解決。因為隨著分類輪數(shù)的增加,邊界域中的元素總是在減少的。從總體來說,三枝決策的應用在保證結(jié)果精度沒有降低時,增加了結(jié)果的可信度,減少了結(jié)果的風險性。

3.3 運行效率

將三枝決策算法引入Spark平臺的目的是希望借由Spark提供的并行化算法和大數(shù)據(jù)處理能力,以增強三枝決策算法的運行效率,使其能夠更好地適應海量數(shù)據(jù)的分析,增加三枝決策算法的實用性。經(jīng)過前兩個數(shù)據(jù)集的分析,分別統(tǒng)計程序在集群模式和單機模式時的運行時間,結(jié)果如圖8所示。圖8中,系列1表示集群模式耗時,系列2表示單機模式耗時。

由圖8可知,隨著數(shù)據(jù)量的增大和運算復雜程度上的增加,集群運行的高效逐漸體現(xiàn)。并且,借助Spark的MapReduce模型,在單機模式下,依然可以提高運行效率。對于本文使用的三枝決策算法,當數(shù)據(jù)量在10 000條以下時,由于集群之間的調(diào)度與通信原因,單機模式的運行速度要高于集群模式;當數(shù)據(jù)量大于10 000條時,集群的運算速度逐漸體現(xiàn)出優(yōu)勢,并且數(shù)據(jù)量越大,優(yōu)勢越明顯;但在數(shù)據(jù)量較小的情況下,Spark處理集群調(diào)度占用的時間接近甚至超過數(shù)據(jù)本身運算的時間,此時,使用Spark進行數(shù)據(jù)處理并不能發(fā)揮集群運算本身的優(yōu)勢。

圖8 集群模式與單機模式運行時間對比

事實上,對于mushroom數(shù)據(jù)集,其本身在一次分類后結(jié)果準確率已經(jīng)超過90%,所以本文的試驗分類過程只進行了一次。對于connect-4數(shù)據(jù)集,由于問題為多分類問題,使用邏輯回歸本身的分類準確率并不高。所以,此項測試中,分類方法使用了前文所描述的多次多輪分類。

表7給出了不同輪數(shù)的三枝決策算法運行時間對比。由表7可知,運算流程復雜度的增加會使計算時間增加。因此,隨著復雜度和數(shù)據(jù)量兩方面的增長,基于Spark的三枝決策算法的效率優(yōu)勢會越來越明顯。

表7不同輪數(shù)的三枝決策算法運行時間對比s

4 結(jié) 論

通過上述試驗結(jié)果可以看到,在Spark上實現(xiàn)的三枝決策算法有以下兩個方面的提高。

(1) 由圖8和表7可知,分布式集群運行的三枝決策算法效率在數(shù)據(jù)量超過10 000的情況下較單機算法有所提高,且數(shù)據(jù)量越大,提高越明顯。

(2) 在Spark系統(tǒng)上,運行效率的提高意味著相同時間內(nèi)可以通過更多輪的訓練,通過圖6和圖7的對比可知,使用三枝決策算法進行分類,分類的性能較前置分類器略有提高。