喻 瑛,楊 崢,王偉杰

(上海大學(xué) 機(jī)電工程與自動化學(xué)院,上海 200072)

0 引 言

粗糙集是處理不確定、不完備數(shù)據(jù)的經(jīng)典理論。屬性約簡是粗糙集理論的核心知識之一，屬性約簡的目標(biāo)在于發(fā)現(xiàn)必要的條件屬性，使得根據(jù)這些條件屬性而形成的相對于決策屬性的分類和所有條件屬性所形成的相對于決策屬性的分類一致，即保持原有的分類能力[1]。屬性約簡算法主要有基于正域的屬性約簡算法[2-3]、基于信息熵的屬性約簡算法[4-5]、基于差別矩陣的屬性約簡算法[6]等。

隨著信息通訊技術(shù)和云計(jì)算技術(shù)的發(fā)展，各行業(yè)領(lǐng)域數(shù)據(jù)逐年呈指數(shù)級增長。為適應(yīng)大數(shù)據(jù)發(fā)展，文中提出了兩種適應(yīng)分布式處理機(jī)制的改進(jìn)屬性約簡算法。首先基于MapReduce分布式計(jì)算框架，探討了基于正域的屬性約簡算法；然后借鑒Hadoop分布式處理機(jī)制，提出了一種新型的分布式處理機(jī)制和數(shù)據(jù)分割分布規(guī)則，并在此基礎(chǔ)上提出了基于分布式處理機(jī)制的差別矩陣屬性約簡算法。

1 粗糙集屬性約簡理論

1.1 粗糙集相關(guān)概念

定義1(決策信息表)：決策信息表S={U,A,V,f}是一個信息系統(tǒng)的表達(dá)，其中U為對象集合，亦稱為論域；R=C∪D，為屬性集合，其中C為條件屬性集，D為決策屬性集；V為屬性值集合；f:U×R→V為信息函數(shù)，它指定U中每個對象x的屬性值[7-8]。

定義2(不可區(qū)分關(guān)系)：在決策表S中，對屬性子集B?R，定義不可區(qū)分關(guān)系IND(B)，即：IND(B)={(x,y)|(x,y)∈U×U,?b∈B,b(x)=b(y)}。

定義3(上近似集和下近似集)：在信息系統(tǒng)S={U,A,V,f}中，設(shè)X?U是個體全域上的子集，P?A。則X的下近似集和上近似集分別定義為：

定義4(正域)：在信息系統(tǒng)S={U,C∪D,V,f}中，設(shè)D*={X1,X2,…,Xm}，屬性子集P(P?C)關(guān)于決策屬性D的“正區(qū)域”定義為：

P關(guān)于D的正區(qū)域表示根據(jù)屬性子集P就能正確區(qū)分的所有對象的集合。

定義5(約簡)：設(shè)U為論域，P和Q分別為定義在U上的兩個等價關(guān)系簇，若P的Q獨(dú)立子集S?P有POSS(Q)=POSP(Q)，則稱S為P的Q約簡。

定義6(核)：屬性C的所有約簡的交集稱為核，記作：CORE(C)=∩RED(C)。核表示C中對于所有約簡都不可缺少的屬性集合。與約簡不同，核一定是唯一的，但可能為空集。

1.2 粗糙集屬性約簡

知識約簡是指在保持知識庫分類或決策能力不變的前提條件下剔除冗余屬性知識，得到最簡屬性集的過程[9]。常見的典型屬性約簡方法有三種：主成分分析法[10]、奇異值分解法[11]、基于粗糙集的屬性約簡[12-14]。主成分分析法利用降維的思想將不同屬性上的信息轉(zhuǎn)換到主成分上面，易造成某些重要信息的缺失。奇異值分解法是矩陣分析中正規(guī)矩陣酉對角化的推廣，在分析數(shù)據(jù)時往往因直接舍棄某些信息而造成部分有用信息缺失?；诖植诩膶傩约s簡可在保持信息系統(tǒng)分類能力和決策能力不變的前提下，刪除系統(tǒng)中不必要的屬性[15]。相比于前兩種方法，其約簡結(jié)果更加可靠、準(zhǔn)確。

2 基于正域和MapReduce的屬性約簡算法

2.1 基于正域的屬性約簡算法流程

輸入：決策表T={U,C∪D}，C={c1,c2,…,cm}，其中C，D分別為條件屬性集和決策屬性集。

輸出：約簡Red(C,D)。

步驟：

(1)令Core(C,D)=?，計(jì)算POSC(D)；

(2)對每個a∈C，計(jì)算POSC-{a}(D)，如果

POSC(D)≠POSC-{a}(D)，則Core(C,D)=Core(C,D)∪{a}；

(3)令B=Core(C,D)，如果

POSB(D)=POSC(D)，則轉(zhuǎn)向(5)，否則轉(zhuǎn)向(4)；

(4)對?a∈CB，求

(5)輸出Red(C,D)=B。

算法中，POSC(D)、POSC-{a}(D)、POSB(D)等正域計(jì)算應(yīng)用MapReduce計(jì)算模式完成。

2.2 基于正域和MapReduce的屬性約簡算法流程

以POSC(D)為例，基于MapReduce計(jì)算模式的正域計(jì)算算法流程如下：

輸入：決策表T={U,C∪D}，C={c1,c2,…,cm}，其中C，D分別為條件屬性集和決策屬性集。

輸出：正域POSC(D)。

步驟：

(1)基于MapReduce框架計(jì)算IND(D)；

(2)基于MapReduce框架計(jì)算IND(C)；

(3)計(jì)算POSC(D)。

3 基于分布式處理機(jī)制的差別矩陣屬性約簡方法

3.1 分布式計(jì)算處理機(jī)制

基于差別矩陣的屬性約簡是常用的屬性約簡方法，差別矩陣具有all-to-all[7]比較特性，為在分布式計(jì)算模式下運(yùn)用差別矩陣進(jìn)行屬性約簡，需要設(shè)計(jì)一種有效的分布式處理機(jī)制和數(shù)據(jù)分配及調(diào)度機(jī)制實(shí)現(xiàn)all-to-all比較。文中借鑒Hadoop平臺傳統(tǒng)的分布式計(jì)算模式，針對基于Hadoop平臺的MapReduce計(jì)算框架在數(shù)據(jù)調(diào)度方面靈活性不足的特點(diǎn)，在此基礎(chǔ)上設(shè)計(jì)了一種新型的分布式計(jì)算模式和數(shù)據(jù)調(diào)度機(jī)制。最后基于該規(guī)則探討基于分布式處理機(jī)制的差別矩陣屬性約簡算法。

首先給出分布式計(jì)算機(jī)制。該機(jī)制主要由Master和DataNode兩部分組成，Master機(jī)器負(fù)責(zé)數(shù)據(jù)的分割、預(yù)調(diào)度、調(diào)度分配和分布式算法發(fā)布工作；DataNode接收到由Master傳來的數(shù)據(jù)和分布式算法分布完畢的消息后進(jìn)行分布式計(jì)算，并將運(yùn)算結(jié)果返回給Master，最終由Master對返回結(jié)果進(jìn)行歸并等處理。

3.2 數(shù)據(jù)分布規(guī)則

為實(shí)現(xiàn)差別矩陣的all-to-all比較，各分布式的DataNode需要放置部分重復(fù)數(shù)據(jù)塊，如何規(guī)劃數(shù)據(jù)塊分割和預(yù)調(diào)度，使重復(fù)數(shù)據(jù)塊最小，以實(shí)現(xiàn)數(shù)據(jù)空間占用最小化，是一個優(yōu)化組合問題。文獻(xiàn)[7]提出了以最小化數(shù)據(jù)空間占用實(shí)現(xiàn)all-to-all比較的數(shù)據(jù)調(diào)度啟發(fā)式算法，但其數(shù)據(jù)調(diào)度在各DataNode上分配不均勻，算法運(yùn)行時間受到數(shù)據(jù)分配最大的機(jī)器的運(yùn)行時間制約，因此算法運(yùn)行時間具備不確定性。文中提出了一種新型數(shù)據(jù)分布規(guī)則，配以簡單的算法實(shí)現(xiàn)，不僅可在實(shí)現(xiàn)all-to-all比較的同時最小化數(shù)據(jù)空間占用，而且可以大致確定機(jī)器運(yùn)行時間。

該分配規(guī)則如下：假設(shè)有3臺DataNode，先將數(shù)據(jù)平均等分為X1、X2、X3份，后再各等分2份，即共分為X1,1、X1,2、X2,1、X2,2、X3,1、X3,2。

每臺DataNode數(shù)據(jù)量為總數(shù)據(jù)量的2/3。將上述的數(shù)據(jù)分配規(guī)則推廣到DataNode數(shù)量l>3，得定理1。

定理1：對于l臺DataNode，將數(shù)據(jù)按以下規(guī)則分配，可實(shí)現(xiàn)all-to-all比較。

(1)將數(shù)據(jù)l等分為l(l≥3)個數(shù)據(jù)塊，將數(shù)據(jù)塊按順序編號為X1,X2,…,Xl，對l個數(shù)據(jù)塊各自二等分，編號為X1,1,X1,2,X2,1,X2,2,…,Xl,1,Xl,2。

(2)在DataNode1分配數(shù)據(jù)X1,1，X1,2，以及所有數(shù)據(jù)塊Xi,1(i=3,4,…,l)。

(3)在DataNode2分配數(shù)據(jù)X2,1，X2,2，以及所有數(shù)據(jù)塊Xi,2(i=3,4,…,l)。

(4)在任意DataNodei(i>3)上：

(4.1)分配數(shù)據(jù)Xi,1，Xi,2；

(4.2)對于數(shù)據(jù)塊(Xi-r,1,Xi-r,2)(0

(4.3)對于數(shù)據(jù)塊(Xi+p,1,Xi+p,2)(p>0)，如果i為奇數(shù)，分配數(shù)據(jù)Xi+p,1，如果i為偶數(shù)，分配數(shù)據(jù)Xi+p,2。

證明：

對于任意兩個數(shù)據(jù)塊Xi、Xj(i>j)，各自再二等分后成為Xi,1、Xi,2、Xj,1、Xj,2，要實(shí)現(xiàn)all-to-all比較，構(gòu)造差別矩陣生成數(shù)據(jù)對如下：

依據(jù)規(guī)則可知，(Xi,1，Xj,1)在DataNode1上，(Xi,2，Xj,2)在DataNode2上；i為奇數(shù)時，(Xi,2，Xj,1)在DataNodei上，(Xi,1，Xj,2)在DataNodej上；i為偶數(shù)時，(Xi,1，Xj,2)在DataNodei上，(Xi,2，Xj,1)在DataNodej上。

按此規(guī)則分配數(shù)據(jù)，可實(shí)現(xiàn)all-to-all比較。

當(dāng)DataNode數(shù)量l=2k+2時，數(shù)據(jù)分配結(jié)果如表1所示(當(dāng)l=2k+1時，數(shù)據(jù)分配結(jié)果如表1的列1～7所示)。顯然，表1所示的數(shù)據(jù)分割分配結(jié)果可實(shí)現(xiàn)all-to-all比較。

3.3 數(shù)據(jù)分割及配置算法

在分布式計(jì)算處理機(jī)制及數(shù)據(jù)分布規(guī)則提出的基礎(chǔ)上，現(xiàn)整理算法流程如下：

輸入：配置到Master上的全局?jǐn)?shù)據(jù)文件，DataNode數(shù)量l。

輸出：完成數(shù)據(jù)分割，并將局部數(shù)據(jù)文件發(fā)布到各DataNode上。

步驟：

(1)計(jì)算l所在區(qū)間[kq，(k+1)q]的所有k值與q值，求出使空間節(jié)約率最大的k值與q值；

(3)將數(shù)據(jù)等分成2l個局部數(shù)據(jù)文件，按DataNode數(shù)為l的數(shù)據(jù)分布規(guī)則發(fā)布到l臺DataNode上，轉(zhuǎn)到步驟(13)；

(4)令r=1，Dr={d1|d1=全局?jǐn)?shù)據(jù)文件}；

(5)Whilej1≤qdo

(6)Dj1+1=?

(7)Whilej2≤|Dj1| do

Dj1+1=Dj1+1∪{d|Dj1+1|+1,d|Dj1+1|+2,…,d|Dj1+1|+k}；

(10)j2=j2+1；

(11)j1=j1+1;

(12)結(jié)束。

3.4 算法步驟

各DataNode分別執(zhí)行的差別矩陣屬性約簡算法流程如下：

輸入：決策表T={U,C∪D}，C={c1,c2,…,cm}，其中C，D分別為條件屬性集和決策屬性集，對象個數(shù)為ni；

輸出：析取、合取后的邏輯式。

步驟：

(1)求差別矩陣：

M(i,j)=

(2)對差別矩陣進(jìn)行析取、合取邏輯運(yùn)算。

(3)在Master上進(jìn)行歸并處理，對各DataNode返回的析取、合取邏輯式繼續(xù)進(jìn)行合取，輸出約簡Red(C,D)。

4 算法的時間復(fù)雜度比較

基于正域的非分布式屬性約簡算法、非分布式差別矩陣屬性約簡算法、基于正域的MapReduce分布式屬性約簡算法、基于分布式處理機(jī)制的差別矩陣屬性約簡算法的時間復(fù)雜度對比如表2所示。

表2 算法的時間復(fù)雜度對比

其中，n為對象記錄條數(shù)，m為條件屬性個數(shù)，l為DataNode個數(shù)(kq≤l≤(k+1)q)，C為基于正域和MapReduce的屬性約簡算法中Master與DataNode之間數(shù)據(jù)交換與通信時間，C'為基于分布式處理機(jī)制的差別矩陣屬性約簡方法中Master與DataNode之間數(shù)據(jù)交換與通信時間。

5 仿真算例

應(yīng)用包含10個條件和1個決策屬性的數(shù)據(jù)集，取不同對象記錄條數(shù)，應(yīng)用文中提出的兩種算法進(jìn)行屬性約簡。應(yīng)用基于MapReduce計(jì)算模式的正域計(jì)算算法進(jìn)行屬性約簡，其運(yùn)行時間與單機(jī)版正域算法的時間對比如表3所示。

表3 運(yùn)行時間對比(基于MapReduce計(jì)算模式的正域計(jì)算算法)

應(yīng)用基于分布式處理機(jī)制的差別矩陣屬性約簡算法，其運(yùn)行時間與單機(jī)版差別矩陣屬性約簡的時間對比如表4所示。由表3與表4比較可知，基于MapReduce計(jì)算模式的正域計(jì)算算法在計(jì)算時間上優(yōu)于基于分布式處理機(jī)制的差別矩陣屬性約簡算法。

表4 運(yùn)行時間對比(基于分布式處理機(jī)制的差別矩陣屬性約簡算法)

將DataNode數(shù)量進(jìn)行擴(kuò)展，應(yīng)用基于分布式處理機(jī)制的差別矩陣屬性約簡算法進(jìn)行屬性約簡，應(yīng)用文中提出的數(shù)據(jù)分布機(jī)制，其數(shù)據(jù)空間節(jié)約率與文獻(xiàn)[9]、Hadoop機(jī)制的對比如表5所示。

表5 數(shù)據(jù)空間節(jié)約對比 %

從表5可以看出，隨著DataNode數(shù)量的不斷增加，文中提出的數(shù)據(jù)分割方式在數(shù)據(jù)空間節(jié)約率效用上逐漸接近甚至部分優(yōu)于文獻(xiàn)[9]與Hadoop的處理結(jié)果。而且，文獻(xiàn)[9]與Hadoop在各臺DataNode上分配的數(shù)據(jù)不均勻，計(jì)算時間將受分配數(shù)據(jù)量最大的DataNode的計(jì)算時間影響，而文中提出的數(shù)據(jù)分配規(guī)則，數(shù)據(jù)在各臺DataNode上均勻分配，計(jì)算時間可以大致確定，相比文獻(xiàn)[9]與Hadoop來說，在處理方式上更加便捷。

隨著DataNode數(shù)量的增加，數(shù)據(jù)空間節(jié)約率變化如圖1所示。從圖1可以看出，隨著機(jī)器臺數(shù)的增加，基于分布式處理機(jī)制的差別矩陣屬性約簡算法的數(shù)據(jù)空間節(jié)約率在逐漸增加。由此進(jìn)一步驗(yàn)證了算法的有效性。

圖1 數(shù)據(jù)空間節(jié)約率變化

6 結(jié)束語

為適應(yīng)大數(shù)據(jù)發(fā)展的需要，首先在MapReduce分布式計(jì)算框架下提出了基于正域的屬性約簡算法；然后針對差別矩陣的all-to-all計(jì)算特性，基于Hadoop分布式計(jì)算理念，設(shè)計(jì)了一種可自行處理數(shù)據(jù)分布的分布式計(jì)算模式，并提出了數(shù)據(jù)在DataNode間的新型分配規(guī)則和相應(yīng)算法，基于此提出了基于分布式處理機(jī)制的差別矩陣屬性約簡方法。仿真算例表明，兩種算法均具有可行性；相對于文獻(xiàn)[9]和Hadoop的數(shù)據(jù)分配機(jī)制，文中提出的DataNode數(shù)據(jù)分配規(guī)則不僅處理效率更優(yōu)，在數(shù)據(jù)空間節(jié)約率上也接近或部分更優(yōu)。而且，該數(shù)據(jù)分布機(jī)制不僅適用于差別矩陣算法，還可推廣應(yīng)用于其他所有all-to-all類型的比較。此外，從運(yùn)行時間對比來看，基于MapReduce計(jì)算模式的正域計(jì)算算法優(yōu)于基于分布式處理機(jī)制的差別矩陣屬性約簡算法，該差別矩陣算法在運(yùn)行時間方面還有進(jìn)一步改進(jìn)空間，這將是下一步的研究方向。

[1] 王 宇,楊志榮,楊習(xí)貝.決策粗糙集屬性約簡:一種局部視角方法[J].南京理工大學(xué)學(xué)報：自然科學(xué)版,2016,40(4):444-449.

[2] 黃國順.保正域的決策粗糙集屬性約簡[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(2):165-169.

[3] 劉濤濤,馬福民,張騰飛.基于正區(qū)域和差別元素的增量式屬性約簡算法[J].計(jì)算機(jī)工程,2016,42(8):183-187.

[4] 劉城霞,何華燦.基于信息熵的屬性約簡算法研究與實(shí)現(xiàn)[J].北京信息科技大學(xué)學(xué)報：自然科學(xué)版,2015,30(4):56-60.

[5] 李少年,吳良剛.基于鄰域信息熵度量數(shù)值屬性快速約簡算法[J].計(jì)算機(jī)工程與科學(xué),2016,38(2):350-355.

[6] 王治和,崔曉慧.改進(jìn)的差別矩陣啟發(fā)式屬性約簡算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2016,37(4):1032-1036.

[7] NASIRI J H,MASHINCHI M.Rough set and data analysis in decision tables[J].Journal of Uncertain Systems,2009,3(3):232-240.

[8] 朱 繼,喻 瑛,王辰煒,等.基于粗糙集合自適應(yīng)遺傳算法的電力變壓器故障診斷[J].電測與儀表,2012,49(6):47-51.

[9] ZHANG Y, TIAN Y, FIDGE C, et al. Data-aware task scheduling for all-to-all comparison problems in heterogeneous distributed systems[J].Journal of Parallel & Distributed Computing,2016,93-94:87-101.

[10] 錢 程,穆文平,王 康,等.基于主成分分析的地下水水質(zhì)模糊綜合評價[J].水電能源科學(xué),2016,34(11):31-35.

[11] 馬宗杰，劉華文.基于奇異值分解-偏最小二乘回歸的多標(biāo)簽分類算法[J].計(jì)算機(jī)應(yīng)用,2014,34(7):2058-2060.

[12] BILSKI P.Data set preprocessing methods for the artificial intelligence-based diagnostic module[J].Measurement,2014,54:180-190.

[13] WANG J,LIU J.Fault diagnosis of wind turbine based on rough set and BP network[C]//Advances in computer science research.Paris:Atlantis Press,2015:877-883.

[14] YANG Q J.Study on computer network application layer fault diagnosis based on RSNN:advanced materials research[J].Advanced Materials Research,2014,846-847:1423-1426.

[15] 韓 玉,李美聰,郭新辰.基于粗糙集理論的文本分類屬性約簡算法[J].東北電力大學(xué)學(xué)報,2016,36(5):92-96.