喻 瑛,楊 崢,王偉杰

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

0 引 言

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

隨著信息通訊技術(shù)和云計(jì)算技術(shù)的發(fā)展，各行業(yè)領(lǐng)域數(shù)據(jù)逐年呈指數(shù)級(jí)增長。為適應(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}是一個(gè)信息系統(tǒng)的表達(dá)，其中U為對(duì)象集合，亦稱為論域；R=C∪D，為屬性集合，其中C為條件屬性集，D為決策屬性集；V為屬性值集合；f:U×R→V為信息函數(shù)，它指定U中每個(gè)對(duì)象x的屬性值[7-8]。

定義2(不可區(qū)分關(guān)系)：在決策表S中，對(duì)屬性子集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是個(gè)體全域上的子集，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ū)分的所有對(duì)象的集合。

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

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

1.2 粗糙集屬性約簡

知識(shí)約簡是指在保持知識(shí)庫分類或決策能力不變的前提條件下剔除冗余屬性知識(shí)，得到最簡屬性集的過程[9]。常見的典型屬性約簡方法有三種：主成分分析法[10]、奇異值分解法[11]、基于粗糙集的屬性約簡[12-14]。主成分分析法利用降維的思想將不同屬性上的信息轉(zhuǎn)換到主成分上面，易造成某些重要信息的缺失。奇異值分解法是矩陣分析中正規(guī)矩陣酉對(duì)角化的推廣，在分析數(shù)據(jù)時(shí)往往因直接舍棄某些信息而造成部分有用信息缺失。基于粗糙集的屬性約簡可在保持信息系統(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)對(duì)每個(gè)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)對(duì)?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ái)傳統(tǒng)的分布式計(jì)算模式，針對(duì)基于Hadoop平臺(tái)的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對(duì)返回結(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ù)空間占用最小化，是一個(gè)優(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í)間受到數(shù)據(jù)分配最大的機(jī)器的運(yùn)行時(shí)間制約，因此算法運(yùn)行時(shí)間具備不確定性。文中提出了一種新型數(shù)據(jù)分布規(guī)則，配以簡單的算法實(shí)現(xiàn)，不僅可在實(shí)現(xiàn)all-to-all比較的同時(shí)最小化數(shù)據(jù)空間占用，而且可以大致確定機(jī)器運(yùn)行時(shí)間。

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

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

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

(1)將數(shù)據(jù)l等分為l(l≥3)個(gè)數(shù)據(jù)塊，將數(shù)據(jù)塊按順序編號(hào)為X1,X2,…,Xl，對(duì)l個(gè)數(shù)據(jù)塊各自二等分，編號(hào)為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)對(duì)于數(shù)據(jù)塊(Xi-r,1,Xi-r,2)(0

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

證明：

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

依據(jù)規(guī)則可知，(Xi,1，Xj,1)在DataNode1上，(Xi,2，Xj,2)在DataNode2上；i為奇數(shù)時(shí)，(Xi,2，Xj,1)在DataNodei上，(Xi,1，Xj,2)在DataNodej上；i為偶數(shù)時(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í)，數(shù)據(jù)分配結(jié)果如表1所示(當(dāng)l=2k+1時(shí)，數(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個(gè)局部數(shù)據(jù)文件，按DataNode數(shù)為l的數(shù)據(jù)分布規(guī)則發(fā)布到l臺(tái)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分別為條件屬性集和決策屬性集，對(duì)象個(gè)數(shù)為ni；

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

步驟：

(1)求差別矩陣：

M(i,j)=

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

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

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

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

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

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

5 仿真算例

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

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

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

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

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

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

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

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

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

6 結(jié)束語

為適應(yīng)大數(shù)據(jù)發(fā)展的需要，首先在MapReduce分布式計(jì)算框架下提出了基于正域的屬性約簡算法；然后針對(duì)差別矩陣的all-to-all計(jì)算特性，基于Hadoop分布式計(jì)算理念，設(shè)計(jì)了一種可自行處理數(shù)據(jù)分布的分布式計(jì)算模式，并提出了數(shù)據(jù)在DataNode間的新型分配規(guī)則和相應(yīng)算法，基于此提出了基于分布式處理機(jī)制的差別矩陣屬性約簡方法。仿真算例表明，兩種算法均具有可行性；相對(duì)于文獻(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)行時(shí)間對(duì)比來看，基于MapReduce計(jì)算模式的正域計(jì)算算法優(yōu)于基于分布式處理機(jī)制的差別矩陣屬性約簡算法，該差別矩陣算法在運(yùn)行時(shí)間方面還有進(jìn)一步改進(jìn)空間，這將是下一步的研究方向。

[1] 王 宇,楊志榮,楊習(xí)貝.決策粗糙集屬性約簡:一種局部視角方法[J].南京理工大學(xué)學(xué)報(bào)：自然科學(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é)報(bào)：自然科學(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].電測(cè)與儀表,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ì)模糊綜合評(píng)價(jià)[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é)報(bào),2016,36(5):92-96.