劉牧雷, 徐菲菲

(上海電力學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 上海 200090)

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

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

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

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

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

1.1 三枝決策

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

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

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

根據(jù)最小風(fēng)險(xiǎn)決策規(guī)則可得

(P) 當(dāng)Pr(X|[x])≥α?xí)r,x∈POS(X),Pr為條件概率;

(B) 當(dāng)β

(N) 當(dāng)Pr(X|[x])≤β時(shí),x∈NEG(X)。

其中

(1)

(2)

且

0≤β<α≤1

(3)

1.2 Spark與并行化

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

圖1 Spark運(yùn)行時(shí)的結(jié)構(gòu)示意

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

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

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

圖2 Spark的運(yùn)算流程

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

2 基于Spark的三枝決策算法

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

2.1 算法介紹

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

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

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

(1) //建立一個(gè)迭代100次,不進(jìn)行標(biāo)準(zhǔn)化、正則化、不使用彈性網(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ù)進(jìn)行訓(xùn)練:

(1) //training 為訓(xùn)練集,test為測(cè)試集;

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

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

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

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

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

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

(4)

(5)

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

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

2.2 算法流程

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

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

具體描述如下。

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

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

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

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

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

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

2.3 MapReduce 過(guò)程分析

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

表6 服務(wù)器配置

測(cè)試數(shù)據(jù)集來(lái)自UCI開(kāi)放數(shù)據(jù)集,是一個(gè)常用的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集,由加州大學(xué)歐文分校(University of California Irvine,UCI)提供。數(shù)據(jù)集均為分類(lèi)任務(wù)。測(cè)試結(jié)果與結(jié)果分析如下。

3.1 Mushroom

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

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

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

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

圖6 整體準(zhǔn)確率指標(biāo)

(6)

(7)

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

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

p,r——查準(zhǔn)率和查全率。

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

3.2 connect-4

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

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

圖7 不同的邊界值對(duì)分類(lèi)性能的影響

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

3.3 運(yùn)行效率

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

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

圖8 集群模式與單機(jī)模式運(yùn)行時(shí)間對(duì)比

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

表7給出了不同輪數(shù)的三枝決策算法運(yùn)行時(shí)間對(duì)比。由表7可知,運(yùn)算流程復(fù)雜度的增加會(huì)使計(jì)算時(shí)間增加。因此,隨著復(fù)雜度和數(shù)據(jù)量?jī)煞矫娴脑鲩L(zhǎng),基于Spark的三枝決策算法的效率優(yōu)勢(shì)會(huì)越來(lái)越明顯。

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

4 結(jié) 論

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

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

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