楊 勇，朱 影

(重慶郵電大學計算智能重慶市重點實驗室，重慶400065)

0 引言

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

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

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

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

1 基本概念

1.1 Rough 集的基本概念

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

定義2 可辨識矩陣［2］。給定一個決策表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)，則可辨識矩陣元素Mij定義為

定義3 相對正區(qū)域［8］。設U為一個論域，P，Q為定義在U上的2個等價關系簇，則Q的P正域記為POSP(Q)，并定義為

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

1.2 MapReduce介紹

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

Map(映射)和Reduce(化簡)的概念及他們的主要思想都是從函數(shù)式編程語言借來的，還有從矢量編程語言借來的特性?；谶@種特點，MapReduce將復雜的并行計算過程高度地抽象成為2個函數(shù)，即Map和Reduce。

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

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

2 基于MapReduce的粗糙集并行屬性約簡算法

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

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

2.1.1 濃縮布爾矩陣定義

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

定義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進行屬性比較后的結果，表示

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

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

2)置IME(BM)=?;

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

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

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

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

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

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

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

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

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

由此提出算法2。

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

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

輸出:帶有CS_flag標志的新決策表CS。

Map階段。

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

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

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

Map階段操作如下。

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

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

Reduce階段。

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

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

Reduce階段操作如下。

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

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

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

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

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

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

1)調用算法2對原始決策表進行判斷，并輸出新決策表CS;

2)創(chuàng)建一個MapReduce任務并行計算得出濃縮布爾矩陣里的每一項，其中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階段操作如下。

中間結果的合并由MapReduce框架完成。

Reduce階段。

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

Reduce_output:〈x_No，x_C〉

Reduce階段操作如下。

3)結束。

2.4 基于MapReduce的并行屬性核計算算法

要得到約簡結果，首先需要求出原決策表的屬性核。由濃縮布爾矩陣定義可知，若矩陣中只有一個屬性值為1，則該值對應的條件屬性為核屬性。

由于屬性核的計算過程符合并行條件，因此可以結合MapReduce作并行約簡。

算法4基于MapReduce的并行屬性核計算算法。

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

輸出:Core。

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

2)創(chuàng)建一個MapReduce任務對所得矩陣中對象進行計算處理，其中Map和Reduce階段過程如下。

Map階段。

Map輸入:〈x_No，x_C〉。

Map輸出:〈x_One_Index，x_C〉。

Map階段操作如下。

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

中間結果合并由MapReduce框架完成。

Reduce階段操作如下。

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

3)結束。

2.5 基于MapReduce的并行屬性約簡算法

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

算法5基于MapReduce的并行屬性約簡算法。

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

輸出:決策表S的屬性約簡R。

1)調用算法2對決策表S相容性進行判斷，得出新決策表CS;

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

3)調用算法4并行計算屬性核Core;

4)初始化一個數(shù)組R'=?，并創(chuàng)建一個MapReduce任務計算約簡，過程如下。

Map階段。

Map輸入:〈x_No，x_C〉。

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

Map階段操作如下。

//對每一行記性掃描，得到所有值為1所在列編號，并構造上述輸出。

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

Reduce階段操作如下。

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

6)結束。

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

3 實驗結果與分析

3.1 實驗環(huán)境

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

實驗環(huán)境如表1所示。

表1 實驗環(huán)境Tab.1 Experimental environment

3.2 算法約簡效果的測試

3.2.1 實驗目的及設置

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

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

3.2.2 實驗結果對比及分析

實驗結果如表2所示，N是約簡后所剩條件屬性個數(shù)，P是識別率。

表2 約簡效果對比Tab.2 Reduction effect contrast

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

3.3 并行屬性約簡算法的運行效率測試

3.3.1 實驗目的及設置

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

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

3.3.2 實驗結果對比及分析

實驗結果如表3所示，其中列出了本文算法和MR-AR算法［5］的運行時間。

表3 運行時間統(tǒng)計Tab.3 Run-time statistics

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

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

3.4 算法的性能測試

為了進一步對本文提出的基于MapReduce的濃縮布爾矩陣并行算法的性能進行評價，本文對并行算法的加速比(speedup)及可擴展性(scaleup)2個指標進行了測試。

1)加速比實驗。

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

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

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

2)可擴展性實驗。

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

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

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

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

4 結束語

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

［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］胡峰，王國胤.屬性序下的快速約簡算法［J］.計算機學報，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］肖大偉，王國胤，胡峰.一種基于粗糙集理論的快速并行屬性約簡算法［J］.計算機科學，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ù)屬性約簡方法研究［D］.重慶:重慶郵電大學，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］楊明，楊萍.差別矩陣濃縮及其屬性約簡求解方法［J］.計算機科學，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］殷志偉，張健沛.基于濃縮布爾矩陣的屬性約簡算法［J］.哈爾濱工程大學學報，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］王國胤.Rough集理論與知識獲取［M］.西安:西安交通大學出版社，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ù)挖掘屬性約簡算法的研究［D］.哈爾濱:哈爾濱工程大學，2008.

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

［12］苗奪謙，胡桂榮.知識約簡的一種啟發(fā)式算法［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］葉東毅，陳昭炯.一個新的差別矩陣及其求核方法［J］.電子學報，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］.計算機工程，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.