一種基于MapReduce 的粗糙集并行屬性約簡(jiǎn)算法

楊 勇，朱 影

(重慶郵電大學(xué)計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室，重慶400065)

0 引言

粗糙集理論［1］是1982年由Z.Pawlak教授提出的，它可以有效地處理分析各種不完備信息，并能找出其潛在規(guī)律，所以近年來(lái)被廣泛應(yīng)用在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等多個(gè)領(lǐng)域［2］，屬性約簡(jiǎn)則是其中一個(gè)重要的研究?jī)?nèi)容。隨著科學(xué)技術(shù)的飛速發(fā)展，各行業(yè)的數(shù)據(jù)都在急劇增長(zhǎng)，如何處理這些大數(shù)據(jù)，并從中挖掘出有用的信息就變得非常重要。

近年來(lái)，為了能夠適應(yīng)大數(shù)據(jù)的不斷增長(zhǎng)，許多學(xué)者為得到高效的屬性約簡(jiǎn)算法進(jìn)行了大量研究，文獻(xiàn)［3］將分治法的思想和粗糙集算法相結(jié)合，在屬性序給定的條件下，提出基于分治策略的屬性約簡(jiǎn)算法，文獻(xiàn)［4］則是將并行思想與基于粗糙集理論的快速屬性約簡(jiǎn)相結(jié)合，提出了一種基于Rough集理論的快速并行屬性約簡(jiǎn)算法，然而，這些算法在處理實(shí)際大數(shù)據(jù)時(shí)，效率并不理想。由此看出，并行地處理大數(shù)據(jù)進(jìn)行屬性約簡(jiǎn)成為一種主流的方法。文獻(xiàn)［5］提出將MapReduce和Rough集理論相結(jié)合，主要對(duì)基于MapReduce的并行正區(qū)域計(jì)算、并行屬性核計(jì)算和并行屬性約簡(jiǎn)進(jìn)行研究，在處理大數(shù)據(jù)的同時(shí)得到了較為良好的約簡(jiǎn)結(jié)果，但是該算法的計(jì)算過(guò)程較為繁雜。

差別矩陣濃縮［6］是楊明于2006年提出的一種高效的基于差別矩陣的改進(jìn)算法，考慮到?jīng)Q策表相容不相容2種情況，針對(duì)Skowron可辨識(shí)矩陣算法在求解約簡(jiǎn)過(guò)程中的不足，有效地作出了改進(jìn);而濃縮布爾矩陣［7］是殷志偉于2009年在濃縮差別矩陣基礎(chǔ)上所提出的，通過(guò)使用布爾代數(shù)形式有效地降低了存儲(chǔ)空間，提高了效率。

因此，本文將濃縮布爾矩陣［7］和MapReduce并行模型相結(jié)合，采用基于MapReduce的濃縮布爾矩陣并行約簡(jiǎn)算法，同等條件下，可以更為方便地得到屬性核及約簡(jiǎn)結(jié)果。本文的創(chuàng)新點(diǎn)主要是利用云計(jì)算的MapReduce編程模型對(duì)基于濃縮布爾矩陣的約簡(jiǎn)算法的各個(gè)步驟并行化，這個(gè)過(guò)程更加簡(jiǎn)單和直觀，提高了算法的效率，實(shí)驗(yàn)證明了算法的有效性和高效性。

1 基本概念

1.1 Rough 集的基本概念

定義1 決策表［8］。一個(gè)決策表，其S=〈U，A=C∪D，V，f＞中，A=C∪D是屬性集合，子集C={ai|i=1，…，m}和D=j5i0abt0b分別稱(chēng)為條件屬性集和決策屬性集，D≠?，V是屬性值的集合，f:U×A→V是一個(gè)信息函數(shù)，它指定了U中每個(gè)對(duì)象的屬性值。

定義2 可辨識(shí)矩陣［2］。給定一個(gè)決策表S=〈U，A=C∪D，V，f＞，F(xiàn)(xi，a)是樣本xi在屬性a上的取值，F(xiàn)(xi，D)是樣本xi在屬性D上的取值。Mij表示矩陣中第i行j列的元素，(其中i，j=1，…，n)，則可辨識(shí)矩陣元素Mij定義為

定義3 相對(duì)正區(qū)域［8］。設(shè)U為一個(gè)論域，P，Q為定義在U上的2個(gè)等價(jià)關(guān)系簇，則Q的P正域記為POSP(Q)，并定義為

定義4 屬性核［8］。設(shè)U為一個(gè)論域，P，Q為定義在U上的2個(gè)等價(jià)關(guān)系簇，若POSP(Q)=POSP－{r}(Q)，則稱(chēng)r為P中相對(duì)于Q是不必要的，否則稱(chēng)r為P中相對(duì)于Q是必要的。P中所有相對(duì)于Q必要的屬性組成的集合稱(chēng)為P的Q核，記為COREQ(P)。

1.2 MapReduce介紹

MapReduce［9-10］是Google于2004年提出的一種編程模型，作為Google云計(jì)算技術(shù)的核心之一，能夠在大規(guī)模分布式集群上并行計(jì)算處理海量數(shù)據(jù)。其概念和思想主要來(lái)自矢量編程語(yǔ)言和函數(shù)式編程語(yǔ)言，極大地方便了編程人員在不會(huì)分布式并行編程的情況下，將自己的程序運(yùn)行在分布式系統(tǒng)上。

Map(映射)和Reduce(化簡(jiǎn))的概念及他們的主要思想都是從函數(shù)式編程語(yǔ)言借來(lái)的，還有從矢量編程語(yǔ)言借來(lái)的特性。基于這種特點(diǎn)，MapReduce將復(fù)雜的并行計(jì)算過(guò)程高度地抽象成為2個(gè)函數(shù)，即Map和Reduce。

MapReduce的具體工作流程如圖1所示。

圖1 MapReduce工作流程Fig.1 MapReduce work flow

2 基于MapReduce的粗糙集并行屬性約簡(jiǎn)算法

濃縮布爾矩陣算法是在文獻(xiàn)［7］中提出的一種改進(jìn)的矩陣屬性約簡(jiǎn)算法，主要使用布爾代數(shù)代替?zhèn)鹘y(tǒng)的字符串進(jìn)行運(yùn)算，大大地減少了計(jì)算量，提高了算法的效率;使用二進(jìn)制位進(jìn)行存儲(chǔ)也在很大程度上減少了存儲(chǔ)的代價(jià);此外，它是基于濃縮差別矩陣算法［6］改進(jìn)所得，因此，對(duì)于相容和不相容決策表的屬性約簡(jiǎn)同樣適用;其計(jì)算屬性核及約簡(jiǎn)結(jié)果的過(guò)程更為簡(jiǎn)單明了，可以有效地減少不必要的計(jì)算量，提高算法的效率。因此，本文基于濃縮布爾矩陣算法，分析其并行性，提出了基于MapReduce的粗糙集并行屬性約簡(jiǎn)算法。

2.1 濃縮布爾矩陣算法及其并行性分析

2.1.1 濃縮布爾矩陣定義

定義5 布爾矩陣［7］。布爾矩陣BM中的每個(gè)元素定義為為條件屬性集合POS(D)，U2=U－U1，即U1表示為相容對(duì)象的集合，U2表示為不相容對(duì)象的集合。

定義6 濃縮布爾矩陣［7］。由定義5可得，濃縮布爾矩陣IME(BM)可以表示為IME(BM)={m|m(m≠0)∈BM}，且不存在m'(m'≠0)∈BM使得m'?m。

2.1.2 濃縮布爾矩陣算法

命題1［7］在濃縮布爾矩陣中，若某行只有一位元素為1，則該元素所在列屬性為核屬性。

由命題1可得算法1，如下所示。

算法1［11］濃縮布爾矩陣算法。

輸入:決策表S=(U，C∪D)。

(3)中，k=1，2，…，n;集合(xi，xj)(xi∈U1，xj∈U1∪U2)表示xi和xj進(jìn)行屬性比較后的結(jié)果，表示

輸出:濃縮布爾矩陣IME(BM)。

1)計(jì)算U1及U2;U1={x1，x2，…，xs}，U2={y1，y2，…，yt}，置Core=?;

2)置IME(BM)=?;

3)遍歷集合U1中對(duì)象，對(duì)任意xi∈U1，xj∈U1(i＜j)，若f(xi，D)≠f(xi，D)，則將xi，xj的各屬性對(duì)應(yīng)進(jìn)行“異或”操作，相同屬性為0，不同為1，所得結(jié)果存入數(shù)組array中;

4)若IME(BM)=?，將array添加到IME(BM)中;若IME(BM)=?，掃描矩陣，將array與矩陣中各元素進(jìn)行“或”運(yùn)算，若 ?a∈IME(BM)存在a與array中各位相“或”所得結(jié)果與a的各位相同，則從IME(BM)中刪除a，添加array;若相“或”后，結(jié)果與array各位相同，則不做任何操作;其他情況下，在IME(BM)中添加array。

5)遍歷集合U1和U2中對(duì)象，對(duì)任意(xi，yj)，其中U2={y1，y2，…，yt}，將xi，yj的各個(gè)屬性依次進(jìn)行“異或”操作，得出結(jié)果并存入數(shù)組array中;再進(jìn)行步驟4)操作，并最終得到IME(BM)。

6)判斷矩陣中每一行的元素值，如果為1的元素值只有一個(gè)，則對(duì)值為1的元素進(jìn)行以下操作:將其所在列對(duì)應(yīng)的屬性添加到核屬性集中。

2.2 基于MapReduce的決策表相容性判斷算法

由上述濃縮布爾矩陣算法步驟可知，在得到矩陣之前很重要的一個(gè)步驟就是區(qū)分決策表中的相容對(duì)象以及不相容對(duì)象。由定義可知，判斷決策表中對(duì)象的相容性，需要兩兩對(duì)比決策表中對(duì)象的條件屬性和決策屬性值;若2個(gè)對(duì)象的條件屬性值不完全相同，或者條件屬性值和決策屬性值完全相同，則表示2個(gè)對(duì)象相容，屬于U1;若2個(gè)對(duì)象對(duì)應(yīng)條件屬性都相同，而決策屬性值不同，則表示2個(gè)對(duì)象不相容，屬于U2。而判斷的過(guò)程中，可以先按照條件屬性對(duì)對(duì)象集進(jìn)行劃分，然后再判斷決策屬性值的一致性，由此判斷過(guò)程可以看出，決策表中對(duì)象劃分的過(guò)程是相互獨(dú)立可并行的。

而我們只需要知道每條記錄是否屬于相容對(duì)象集合，而不需要輸出具體結(jié)果，所以在此基礎(chǔ)上，引入一個(gè)標(biāo)志，記為CS_flag，若對(duì)象屬于相容對(duì)象集，則標(biāo)志為true，否則為false，最后輸出一個(gè)決策表CS，這樣可以縮短計(jì)算時(shí)間，提高效率。

在MapReduce并行模型中，Map的過(guò)程是將原始輸入數(shù)據(jù)拆分成key/value對(duì)，然后MapReduce框架將相同key值的value分到一起，傳遞給Reduce進(jìn)行處理。其中key和value都是偏移量，value這個(gè)值是用來(lái)進(jìn)行分割處理的值。

由此可以看出，若將U中每個(gè)對(duì)象在屬性集C上的屬性值看成是Map過(guò)程中的key，那么，判斷決策表相容性的過(guò)程與MapReduce中的Map過(guò)程是一致的，則可以通過(guò)Map的過(guò)程實(shí)現(xiàn)對(duì)決策表相容性判斷的并行計(jì)算。

由此提出算法2。

算法2基于MapReduce的決策表相容性判斷算法。

輸入:決策表S=(U，C∪D)。

輸出:帶有CS_flag標(biāo)志的新決策表CS。

Map階段。

Map輸入:〈x_No，x_C+x_D〉。

其中，x_No為決策表中的記錄編號(hào);x_C為xi在條件屬性集C上的值;x_D為xi在在決策屬性集D上的值。

Map輸出:〈x_C，x_D+x_No〉。

Map階段操作如下。

1)將決策表S中的對(duì)象拆分成key/value對(duì)，按照編號(hào)依次輸入。

2)利用MapReduce框架對(duì)中間結(jié)果進(jìn)行排序，將具有相同key的value分為一組，得到C對(duì)論域U的劃分U|IND(C)={X1，X2，…，XN}，并將Xi傳遞給Reduce任務(wù)。

Reduce階段。

Reduce輸入:〈C，Xj〉，(Xj∈U|IND(C))。

Reduce輸出:〈x_No，x_C+x_D+CS_flag〉。

Reduce階段操作如下。

2.3 基于MapReduce的濃縮布爾矩陣算法

算法2可生成一個(gè)新的決策表CS，里面每條記錄最后都添加了CS_flag的標(biāo)志位，來(lái)識(shí)別該條記錄是屬于相容或者不相容對(duì)象集合;而根據(jù)算法1［11］可以得到，矩陣是由決策表CS中的記錄兩兩比較所得，結(jié)合MapReduce并行模型，可得并行濃縮布爾矩陣的計(jì)算算法。

在Map實(shí)現(xiàn)過(guò)程中，首先為了實(shí)現(xiàn)記錄的兩兩比較，將新決策表內(nèi)記錄拆分成多個(gè)key/value對(duì)作為Map輸入，而在Map輸出時(shí)，則將每條記錄輸出為多條，即若當(dāng)前記錄編號(hào)為1，則只需輸出〈1，C1+D1〉，若記錄編號(hào)為2，則輸出〈1，C2+D2〉，〈2，C2+D2〉，以此類(lèi)推;再按照key值將輸出的記錄進(jìn)行中間合并;在Reduce過(guò)程中，通過(guò)將key值相同的記錄兩兩進(jìn)行比較，可得到IME(BM)。

算法3基于MapReduce的并行濃縮布爾矩陣算法。

輸入:決策表S=(U，C∪D)。

輸出:濃縮布爾矩陣IME(BM)。

1)調(diào)用算法2對(duì)原始決策表進(jìn)行判斷，并輸出新決策表CS;

2)創(chuàng)建一個(gè)MapReduce任務(wù)并行計(jì)算得出濃縮布爾矩陣?yán)锏拿恳豁?xiàng)，其中Map和Reduce階段具體工作如下。

Map階段。

Map輸入:〈xi_No，xi_C+xi_D+CS_flag〉。

Map輸出:〈xs_No，xi_C+xi_D+CS_flag〉。(其中，s=1，…，i)

Map階段操作如下。

中間結(jié)果的合并由MapReduce框架完成。

Reduce階段。

Reduce_intput:〈xs_No，xi_C+xi_D+CS_flag〉。(其中，s=1，…，i)

Reduce_output:〈x_No，x_C〉

Reduce階段操作如下。

3)結(jié)束。

2.4 基于MapReduce的并行屬性核計(jì)算算法

要得到約簡(jiǎn)結(jié)果，首先需要求出原決策表的屬性核。由濃縮布爾矩陣定義可知，若矩陣中只有一個(gè)屬性值為1，則該值對(duì)應(yīng)的條件屬性為核屬性。

由于屬性核的計(jì)算過(guò)程符合并行條件，因此可以結(jié)合MapReduce作并行約簡(jiǎn)。

算法4基于MapReduce的并行屬性核計(jì)算算法。

輸入:決策表S=(U，C∪D)。

輸出:Core。

1)初始化Core=?，調(diào)用算法3對(duì)原始決策表進(jìn)行計(jì)算，并輸出濃縮布爾矩陣IME(BM)。

2)創(chuàng)建一個(gè)MapReduce任務(wù)對(duì)所得矩陣中對(duì)象進(jìn)行計(jì)算處理，其中Map和Reduce階段過(guò)程如下。

Map階段。

Map輸入:〈x_No，x_C〉。

Map輸出:〈x_One_Index，x_C〉。

Map階段操作如下。

其中，Map的輸入x為矩陣IME(BM)中的每一行記錄，x_No為每行記錄的編號(hào)，x_C為該行記錄在所對(duì)應(yīng)條件屬性集C上的值。Map的輸出x_One_Index為該行記錄中唯一值為1所在列的編號(hào)。

中間結(jié)果合并由MapReduce框架完成。

Reduce階段操作如下。

即是將Reduce輸出存入核屬數(shù)組Core中。

3)結(jié)束。

2.5 基于MapReduce的并行屬性約簡(jiǎn)算法

計(jì)算決策表CS、計(jì)算濃縮布爾矩陣IME(BM)和最終結(jié)果化簡(jiǎn)是本文約簡(jiǎn)算法的3個(gè)關(guān)鍵步驟。本文在基于MapReduce的決策表相容性判斷算法(算法2)、基于MapReduce的濃縮布爾矩陣算法(算法3)、基于MapReduce的并行屬性核計(jì)算算法(算法4)基礎(chǔ)上，提出基于MapReduce的并行屬性約簡(jiǎn)算法。其中對(duì)于所得矩陣的合取析取操作采用文獻(xiàn)［15］中趙榮泳等所提出的直接搜索算法，其過(guò)程也是可并行的。

算法5基于MapReduce的并行屬性約簡(jiǎn)算法。

輸入:決策表S=(U，C∪D)。

輸出:決策表S的屬性約簡(jiǎn)R。

1)調(diào)用算法2對(duì)決策表S相容性進(jìn)行判斷，得出新決策表CS;

2)調(diào)用算法3得到濃縮布爾矩陣IME(BM);

3)調(diào)用算法4并行計(jì)算屬性核Core;

4)初始化一個(gè)數(shù)組R'=?，并創(chuàng)建一個(gè)MapReduce任務(wù)計(jì)算約簡(jiǎn)，過(guò)程如下。

Map階段。

Map輸入:〈x_No，x_C〉。

Map輸出:〈1，x_No+array(值為1所在列)〉。

Map階段操作如下。

//對(duì)每一行記性掃描，得到所有值為1所在列編號(hào)，并構(gòu)造上述輸出。

其中Map的輸入為矩陣IME(BM)中的每一行記錄，x_No為每行記錄的編號(hào)，x_C為該行記錄在所對(duì)應(yīng)條件屬性集C上的值。Map輸出的key值為該行記錄中值為1所在列的編號(hào)。

Reduce階段操作如下。

5)將輸出結(jié)果放入數(shù)組R'中，則R'與Core相或可得最后約簡(jiǎn)結(jié)果。

6)結(jié)束。

文獻(xiàn)［5］亦采用基于MapReduce的并行約簡(jiǎn)算法，其算法采用計(jì)算正域進(jìn)而求得核屬性的方法得出最終約簡(jiǎn)結(jié)果，算法5在計(jì)算步驟上更加簡(jiǎn)練和直觀，在各個(gè)步驟都并行實(shí)現(xiàn)的前提下，直接通過(guò)求得濃縮布爾矩陣并進(jìn)一步進(jìn)行化簡(jiǎn)即可得出約簡(jiǎn)結(jié)果。

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

3.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證本文算法的有效性以及處理大數(shù)據(jù)的能力，本文設(shè)計(jì)了以下3個(gè)實(shí)驗(yàn):1)通過(guò)與傳統(tǒng)算法對(duì)比，測(cè)試本文算法的約簡(jiǎn)效果;2)測(cè)試本文算法的大數(shù)據(jù)處理能力;3)測(cè)試本文算法在云計(jì)算環(huán)境中的加速比系數(shù)。

實(shí)驗(yàn)環(huán)境如表1所示。

表1 實(shí)驗(yàn)環(huán)境Tab.1 Experimental environment

3.2 算法約簡(jiǎn)效果的測(cè)試

3.2.1 實(shí)驗(yàn)?zāi)康募霸O(shè)置

為測(cè)試本文算法的約簡(jiǎn)效果，本文選取了UCI經(jīng)典數(shù)據(jù)庫(kù)中的Zoo，Glass，Chess，Heart和Iris 5個(gè)數(shù)據(jù)集，并分別采用本文算法、基于信息熵的屬性約簡(jiǎn)算法［8］、歸納屬性約簡(jiǎn)算法［8］、MIBARK算法［12］和MR-sAR算法［5］進(jìn)行測(cè)試并對(duì)比約簡(jiǎn)效果。而針對(duì)數(shù)據(jù)集中的連續(xù)屬性，均采用基于屬性重要性的離散化算法［4］進(jìn)行離散化。

實(shí)驗(yàn)分為2個(gè)部分:1)分別測(cè)試5種算法在5個(gè)數(shù)據(jù)集上的約簡(jiǎn)結(jié)果，并統(tǒng)計(jì)約簡(jiǎn)之后所剩條件屬性的個(gè)數(shù);2)5種算法的識(shí)別率測(cè)試(識(shí)別率=正確識(shí)別樣本數(shù)/測(cè)試樣本總數(shù)之比)，對(duì)每個(gè)數(shù)據(jù)集，將隨機(jī)抽取每個(gè)數(shù)據(jù)集的50%數(shù)據(jù)用作訓(xùn)練集，剩下的一半用作測(cè)試集。對(duì)訓(xùn)練集分別采用5種算法進(jìn)行屬性約簡(jiǎn)，并用歸納值約簡(jiǎn)［4］方法進(jìn)行規(guī)則提取，然后對(duì)測(cè)試集進(jìn)行測(cè)試，依次統(tǒng)計(jì)5種算法的識(shí)別率。

3.2.2 實(shí)驗(yàn)結(jié)果對(duì)比及分析

實(shí)驗(yàn)結(jié)果如表2所示，N是約簡(jiǎn)后所剩條件屬性個(gè)數(shù)，P是識(shí)別率。

表2 約簡(jiǎn)效果對(duì)比Tab.2 Reduction effect contrast

從表2可以看出，本文算法在Chess數(shù)據(jù)集上，本文的算法識(shí)別率比MR-AR算法高，而在其他4個(gè)數(shù)據(jù)集上的約簡(jiǎn)結(jié)果和其他幾種算法是一致的，說(shuō)明本文算法的約簡(jiǎn)效果與其他算法是相當(dāng)?shù)模C明了本文算法是有效的。

3.3 并行屬性約簡(jiǎn)算法的運(yùn)行效率測(cè)試

3.3.1 實(shí)驗(yàn)?zāi)康募霸O(shè)置

在并行計(jì)算環(huán)境下，為了驗(yàn)證本文算法在處理實(shí)際大數(shù)據(jù)集的效率及有效性，本文將采用包含有4 898 432條記錄的KDDCUP99［14］數(shù)據(jù)集對(duì)其進(jìn)行測(cè)試，并將同時(shí)采用文獻(xiàn)［5］中所提MR-AR算法對(duì)相同數(shù)據(jù)集在同等情況下進(jìn)行算法效率的比較。數(shù)據(jù)集中每條記錄都有41個(gè)條件屬性和1個(gè)決策屬性。實(shí)驗(yàn)中所采用的環(huán)境同表1，僅1個(gè)計(jì)算機(jī)節(jié)點(diǎn):包括4個(gè)map和2個(gè)reduce任務(wù)。

實(shí)驗(yàn)過(guò)程中，把數(shù)據(jù)集等分成10份，編號(hào)1到10，每次抽取其中的9份作為訓(xùn)練集進(jìn)行實(shí)驗(yàn)，保證10組數(shù)據(jù)集每組輪空一次，如此重復(fù)做10次實(shí)驗(yàn)，即每次實(shí)驗(yàn)數(shù)據(jù)集都包含4 408 588條記錄，其中數(shù)據(jù)集采用等頻率離散化方法［8］進(jìn)行離散化處理。對(duì)比實(shí)驗(yàn)將分別對(duì)本文算法及MR-AR算法［5］在相同實(shí)驗(yàn)環(huán)境下進(jìn)行測(cè)試。對(duì)比實(shí)驗(yàn)結(jié)果如表3所示。

3.3.2 實(shí)驗(yàn)結(jié)果對(duì)比及分析

實(shí)驗(yàn)結(jié)果如表3所示，其中列出了本文算法和MR-AR算法［5］的運(yùn)行時(shí)間。

表3 運(yùn)行時(shí)間統(tǒng)計(jì)Tab.3 Run-time statistics

從表3中可以看出，本文算法的運(yùn)行時(shí)間有一定的波動(dòng)，這主要是因?yàn)槊看螖?shù)據(jù)集雖然大小一樣，但是具體記錄并不相同，且系統(tǒng)可能出現(xiàn)誤差;通過(guò)求運(yùn)行時(shí)間方差可得MR-AR算法方差為3.3，而本文算法為2.1，可見(jiàn)本文算法在穩(wěn)定性上要優(yōu)于MR-AR算法。

從表3中還可以看出，本文算法運(yùn)行時(shí)間比MR-AR算法要少，在時(shí)間效率上整體要優(yōu)于MRAR算法，這是因?yàn)镸R-AR算法首先需要求正區(qū)域進(jìn)而再求核屬性，再采用基于屬性重要性求約簡(jiǎn)，需要計(jì)算屬性重要性參數(shù)，再通過(guò)比較參數(shù)值將屬性一一添加到核屬性里，進(jìn)而得到約簡(jiǎn)結(jié)果，過(guò)程較為繁雜;而本文算法在生成矩陣后，求得核屬性，刪除包含核屬性的記錄后，將矩陣中所剩記錄進(jìn)行合取析取操作，所得結(jié)果再跟核屬性進(jìn)行或操作，即可得最終約簡(jiǎn)，上述邏輯操作過(guò)程簡(jiǎn)明直觀，兩者相比，本文算法耗費(fèi)時(shí)間更少，因而本文算法比MR-AR算法效率更高。

3.4 算法的性能測(cè)試

為了進(jìn)一步對(duì)本文提出的基于MapReduce的濃縮布爾矩陣并行算法的性能進(jìn)行評(píng)價(jià)，本文對(duì)并行算法的加速比(speedup)及可擴(kuò)展性(scaleup)2個(gè)指標(biāo)進(jìn)行了測(cè)試。

1)加速比實(shí)驗(yàn)。

加速比是衡量并行算法性能的一個(gè)重要指標(biāo)，是數(shù)據(jù)規(guī)模一定的條件下，增大計(jì)算機(jī)節(jié)點(diǎn)的個(gè)數(shù)時(shí)，并行算法的性能，其計(jì)算為

(4)式中:t1表示一個(gè)計(jì)算節(jié)點(diǎn)上該算法的運(yùn)行時(shí)間;tn表示n個(gè)計(jì)算節(jié)點(diǎn)上該算法的運(yùn)行時(shí)間。實(shí)驗(yàn)中，隨機(jī)生成2×107，1×107條記錄，其中每條記錄包含10個(gè)條件屬性和1個(gè)決策屬性，屬性值在0—9間隨機(jī)取值，這些自定義數(shù)據(jù)集分別稱(chēng)為D1，D2。在該2個(gè)數(shù)據(jù)集上，分別在采用1—5個(gè)計(jì)算節(jié)點(diǎn)的情況下，對(duì)本文算法的運(yùn)行時(shí)間進(jìn)行測(cè)試，并計(jì)算其加速比系數(shù)，結(jié)果如圖2所示。

從圖2可以看出，隨著計(jì)算節(jié)點(diǎn)的增多，加速比系數(shù)趨于緩和，這是由于各節(jié)點(diǎn)間通信開(kāi)銷(xiāo)、任務(wù)啟動(dòng)、任務(wù)調(diào)度和故障處理等時(shí)間消耗會(huì)隨著節(jié)點(diǎn)個(gè)數(shù)增加而變多，而對(duì)于較大的數(shù)據(jù)集，其加速比系數(shù)曲線近似成線性增長(zhǎng)，算法效果更明顯，說(shuō)明在云計(jì)算環(huán)境下，本文算法具有良好的加速比。

2)可擴(kuò)展性實(shí)驗(yàn)。

可擴(kuò)展性(scaleup)是指按照比例增加計(jì)算節(jié)點(diǎn)的個(gè)數(shù)與數(shù)據(jù)規(guī)模時(shí)并行算法的性能。其計(jì)算公式為

(5)式中:t1·DB表示在DB數(shù)據(jù)上使用1個(gè)計(jì)算節(jié)點(diǎn)運(yùn)行該算法所用的時(shí)間;tn·n·DB表示在n·DB規(guī)模的數(shù)據(jù)上使用n個(gè)節(jié)點(diǎn)運(yùn)行該算法所用的時(shí)間。實(shí)驗(yàn)依然采用數(shù)據(jù)集D1和D2，結(jié)果如圖3所示。實(shí)驗(yàn)結(jié)果表明，算法效率整體上呈下降趨勢(shì)，但是D1的曲線較D2要平穩(wěn)一些，說(shuō)明在數(shù)據(jù)集規(guī)模越大時(shí)，算法效率曲線越平穩(wěn)，說(shuō)明了本文算法具有比較良好的可擴(kuò)展性。

圖2 加速比系數(shù)曲線Fig.2 Speedup coefficient curve

圖3 不同數(shù)據(jù)集下可擴(kuò)展性對(duì)比Fig.3 Different data set scalability contrast

4 結(jié)束語(yǔ)

本文以濃縮布爾矩陣屬性約簡(jiǎn)算法為基礎(chǔ)，結(jié)合MapReduce并行計(jì)算模型，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)并行的粗糙集屬性約簡(jiǎn)算法。在算法實(shí)現(xiàn)過(guò)程中，通過(guò)對(duì)每個(gè)步驟實(shí)現(xiàn)并行化，使其能在大數(shù)據(jù)環(huán)境下進(jìn)行屬性約簡(jiǎn)，提高了屬性約簡(jiǎn)的效率。實(shí)驗(yàn)結(jié)果表明，本文算法在進(jìn)行屬性約簡(jiǎn)時(shí)是有效以及高效的，同時(shí)具有良好的并行性能。

［1］PAWLAK Z.Rough set［J］.International Journal of Com-puter and Information Science，1982，11(5):341-356.

［2］SKOWRONA.RAUSZER C.The discernibility matrices and functions in information systems［M］.Dordrecht:Kluwer Academic Publishers，1992:331-362.

［3］胡峰，王國(guó)胤.屬性序下的快速約簡(jiǎn)算法［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30(8):1429-1435.

HU Feng，WANG Guoyin.Quick Reduction Algorithm Based on Attribute Order［J］.Chinese Journal of Computers，2007，30(8):1429-1435.

［4］肖大偉，王國(guó)胤，胡峰.一種基于粗糙集理論的快速并行屬性約簡(jiǎn)算法［J］.計(jì)算機(jī)科學(xué)，2009，36(3):208-211.

XIAO Dawei，WANG Guoyin，HU Feng.Fast Parallel Attribute Reduction Algorithm Based on Rough Set Theory［J］.Computer Science，2009，36(3):208-211.

［5］陳崢嶸.基于MapReduce和Rough集理論的海量數(shù)據(jù)屬性約簡(jiǎn)方法研究［D］.重慶:重慶郵電大學(xué)，2012.

CHEN Zhengrong.Research on Methods of Attribute Reduction for Massive Data Based on MapReduce and Rough Set Theory［D］.Chongqing:Chongqing University of Posts and Telecommunications，2012.

［6］楊明，楊萍.差別矩陣濃縮及其屬性約簡(jiǎn)求解方法［J］.計(jì)算機(jī)科學(xué)，2006，33(9):181-183.

YANG Ming，YANG Ping.Discernibility Matrix Enriching and Computation for Attribute Reduction［J］.Computer Science，2006，33(9):181-183.

［7］殷志偉，張健沛.基于濃縮布爾矩陣的屬性約簡(jiǎn)算法［J］.哈爾濱工程大學(xué)學(xué)報(bào)，2009，30(3):307-311.

YIN Zhiwei，ZHANG Jianpei.An Attribute Reduction Algorithm Based on a Concentration Boolean Matrix［J］.Journal of Harbin Engineering University，2009，30(3):307-311.

［8］王國(guó)胤.Rough集理論與知識(shí)獲?。跰］.西安:西安交通大學(xué)出版社，2001:30-62.

WANG Guoyin.Rough Set Theory and Knowledge Acquisition［M］.Xi’an:Xi’an Jiaotong University Press，2001:30-62.

［9］DEAN J，GHEMMAWAT S.MapReduce:Simplified data processing on large clusters［C］//ACM.Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation.New York:Press，2004:137-150.

［10］DEAN J，GHEMAWAT S.MapReduce:A flexible data processing tool［J］.Communications of the ACM，2010，53(1):72-77.

［11］李丹.基于粗糙集的數(shù)據(jù)挖掘?qū)傩约s簡(jiǎn)算法的研究［D］.哈爾濱:哈爾濱工程大學(xué)，2008.

LI Dan.Research on Attribute Reduction Algorithms for Data Mining Based on Rough Set［D］.Harbin:Harbin Engineering University，2008.

［12］苗奪謙，胡桂榮.知識(shí)約簡(jiǎn)的一種啟發(fā)式算法［J］.計(jì)算機(jī)研究與發(fā)展，1999，36(6):681-684.

MIAO Duoqian，HU Guirong.A Heuristic Algorithm for Reduction of Knowledge［J］.Journal of Computer Researching and Development，1999，36(6):681-684.

［13］葉東毅，陳昭炯.一個(gè)新的差別矩陣及其求核方法［J］.電子學(xué)報(bào)，2002，30(7):1086-1088.

YE Dongyi，CHEN Zhaojiong.A New Discernibility Matrix and the Computation of a Core［J］.Acta Electronica Sinica，2002，30(7):1086-1088.

［14］ANONYMITY.KDDCUP99［EB/OL］.(2007-06-26)［2013-01-19］.http://kdd.ics.uci.edu/databases/kddcup99/.

［15］趙容泳，張浩，李翠玲，等.粗糙集理論中分辨函數(shù)的析取范式生成算法［J］.計(jì)算機(jī)工程，2006，32(2):183-185.

ZHAO Rongyong，ZHANG Hao，LI Cuiling，et al.Disjunctive Normal Form Generation Algorithm for Discernibility Function in Rough Set Theory［J］.Computer Engineering，2006，32(2):183-185.