呂 潔 劉利民 胡皎月 許志偉,2

1(內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院 內(nèi)蒙古 呼和浩特 010080)2(中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100086)

基于MapReduce的高效粗糙集屬性約簡(jiǎn)算法

呂 潔1劉利民1胡皎月1許志偉1,2

1(內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院 內(nèi)蒙古 呼和浩特 010080)2(中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100086)

針對(duì)粗糙集理論中傳統(tǒng)的基于正域的屬性約簡(jiǎn)算法和基于信息熵的屬性約簡(jiǎn)算法無(wú)法得到最小約簡(jiǎn)集的問(wèn)題，給出基于信息熵改進(jìn)的屬性約簡(jiǎn)算法，即先使用條件熵識(shí)別出重要度值最大的屬性，使用正域進(jìn)行約簡(jiǎn)判斷。在此基礎(chǔ)上，設(shè)計(jì)了高效的基于MapReduce的信息熵改進(jìn)屬性約簡(jiǎn)算法。以真實(shí)海量氣象數(shù)據(jù)為基礎(chǔ)，在Hadoop集群上實(shí)現(xiàn)上述算法，驗(yàn)證了該算法的有效性和效率。

屬性約簡(jiǎn) 粗糙集理論 信息熵

0 引 言

針對(duì)粗糙集理論中傳統(tǒng)的基于正域的屬性約簡(jiǎn)算法和基于信息熵的屬性約簡(jiǎn)算法無(wú)法得到最小約簡(jiǎn)集的問(wèn)題，以及在代數(shù)觀點(diǎn)下和信息論觀點(diǎn)下屬性重要度定義不一致的問(wèn)題，給出了基于信息熵改進(jìn)的屬性約簡(jiǎn)算法，即先使用條件熵識(shí)別出重要度值最大的屬性，使用正域進(jìn)行約簡(jiǎn)判斷。為了保證此約簡(jiǎn)是最小約簡(jiǎn)，當(dāng)?shù)玫郊s簡(jiǎn)集時(shí)，再次使用正域檢查去除約簡(jiǎn)集中的冗余屬性。本文給出了基于MapReduce的信息熵改進(jìn)屬性約簡(jiǎn)算法，通過(guò)真實(shí)海量氣象數(shù)據(jù)，驗(yàn)證了算法的有效性。

1 研究現(xiàn)狀

目前已有很多學(xué)者做了關(guān)于提高粗糙集約簡(jiǎn)效率的研究和探索，主要分為基于正域的屬性約簡(jiǎn)算法、基于信息論的屬性約簡(jiǎn)算法和基于差別矩陣的屬性約簡(jiǎn)算法以及在這些算法基礎(chǔ)上進(jìn)行改進(jìn)的屬性約簡(jiǎn)[1]。文獻(xiàn)[1]利用粗糙集理論中的屬性可辨識(shí)性以及差別矩陣與其之間的關(guān)系，提出了在云計(jì)算環(huán)境下的知識(shí)約簡(jiǎn)算法。該算法采用數(shù)據(jù)并行策略計(jì)算每個(gè)數(shù)據(jù)分片的等價(jià)類，之后對(duì)相同的等價(jià)類進(jìn)行合并，通過(guò)計(jì)算邊界域的可辨識(shí)對(duì)象對(duì)個(gè)數(shù)，選擇最優(yōu)的約簡(jiǎn)屬性，重復(fù)此過(guò)程直到獲得整個(gè)數(shù)據(jù)集的屬性約簡(jiǎn)集，該方法沒(méi)有處理冗余屬性。文獻(xiàn)[2]利用MapReduce技術(shù)對(duì)數(shù)據(jù)集進(jìn)行分片，針對(duì)每一個(gè)數(shù)據(jù)分片計(jì)算其約簡(jiǎn)集，然后合并數(shù)據(jù)分片的約簡(jiǎn)集，再增加其他剩余的必要候選屬性，最后刪除冗余的屬性。然而，該方法在合并之后的約簡(jiǎn)集可能是整個(gè)屬性集，故在刪除冗余屬性時(shí)會(huì)大幅增加I/O開銷，系統(tǒng)效率偏低。文獻(xiàn)[3]利用等價(jià)類與決策類之間的關(guān)系，提出了計(jì)算上下近似的并行算法，此關(guān)系中包含大量的對(duì)象對(duì)，此算法把等價(jià)類和決策類之間的關(guān)系轉(zhuǎn)換為關(guān)系相對(duì)應(yīng)的索引值，實(shí)驗(yàn)表明，其算法計(jì)算精度仍需改善。文獻(xiàn)[4]以電力大數(shù)據(jù)為背景，提出了使用MapReduce技術(shù)并行計(jì)算正域中元素個(gè)數(shù)(稱為正域的勢(shì))的約簡(jiǎn)算法，此算法避免了因使用正域計(jì)算屬性約簡(jiǎn)集而造成的繁瑣操作，節(jié)省了大量的時(shí)間和空間開銷，該方法計(jì)算結(jié)果并非最優(yōu)約簡(jiǎn)集。

文獻(xiàn)[5]以快速縮小搜索空間為目標(biāo)，使用度量屬性重要度的公式設(shè)計(jì)了一個(gè)基于差別矩陣且時(shí)間復(fù)雜度為max(O(|C||U|),O(|C|2|U/C|))的快速屬性約簡(jiǎn)算法，該算法可處理大型的決策表，但沒(méi)有實(shí)現(xiàn)算法的并行化來(lái)提高算法的執(zhí)行時(shí)間。文獻(xiàn)[6]利用正域和屬性集的單調(diào)關(guān)系，設(shè)計(jì)了基于正域的屬性依賴度約簡(jiǎn)算法，并選取了快速選擇方法來(lái)選取約簡(jiǎn)屬性，減少了樣本比較次數(shù)，但對(duì)約簡(jiǎn)結(jié)果的質(zhì)量不是很理想。

當(dāng)前相關(guān)研究還未實(shí)現(xiàn)在保證屬性約簡(jiǎn)效果的同時(shí)保證處理效率。針對(duì)海量數(shù)據(jù)粗糙集屬性約簡(jiǎn)問(wèn)題，屬性約簡(jiǎn)的效果和效率都會(huì)影響到大數(shù)據(jù)分析系統(tǒng)的可用性，因此，需針對(duì)這一問(wèn)題進(jìn)行更加深入的研究。

2 粗糙集屬性約簡(jiǎn)

粗糙集理論是一個(gè)處理不確定和模糊知識(shí)的數(shù)學(xué)工具，其主要思想是在保持?jǐn)?shù)據(jù)分類能力不變的情況下，通過(guò)知識(shí)約簡(jiǎn)，導(dǎo)出問(wèn)題的決策或分類規(guī)則[7]。針對(duì)海量數(shù)據(jù)粗糙集屬性約簡(jiǎn)的效果和效率都會(huì)影響到大數(shù)據(jù)分析系統(tǒng)的可用性的問(wèn)題，以不可分辨關(guān)系(即等價(jià)關(guān)系)作為標(biāo)準(zhǔn)對(duì)整個(gè)知識(shí)進(jìn)行劃分，形成相應(yīng)的知識(shí)表達(dá)系統(tǒng)。引入上下近似集(詳見(jiàn)定義3)來(lái)逼近研究對(duì)象，通過(guò)計(jì)算每個(gè)屬性的重要度，從而刪除冗余或者不相關(guān)屬性，簡(jiǎn)化知識(shí)表達(dá)系統(tǒng)[8]。

屬性約簡(jiǎn)問(wèn)題在很多領(lǐng)域都有廣泛的應(yīng)用。例如近幾年氣象部門信息化程度日益提高，每天全國(guó)氣象臺(tái)站接收的數(shù)據(jù)高達(dá)100GB，這些海量的氣象數(shù)據(jù)中蘊(yùn)藏著豐富的氣象規(guī)律。在實(shí)驗(yàn)粗糙集理論處理相關(guān)數(shù)據(jù)的過(guò)程中，氣象數(shù)據(jù)集通常具有屬性缺失或冗余度較大等問(wèn)題，不符合數(shù)據(jù)挖掘算法要求規(guī)范，同時(shí)降低了存儲(chǔ)性能和訪問(wèn)效率。因此，需要引入屬性約簡(jiǎn)機(jī)制來(lái)優(yōu)化氣象數(shù)據(jù)的粗糙集分析過(guò)程。

2.1 粗糙集基本概念

定義2 (等價(jià)關(guān)系的概念)對(duì)于Va∈A(A中可包含一個(gè)或多個(gè)屬性)，A?R，x?U，y?U，若fa(x)=fb(y)成立，則對(duì)象x和y是對(duì)屬性集A的等價(jià)關(guān)系(即不可分辨關(guān)系)，見(jiàn)式(1)：

IND(A) ={(x,y)|(x,y)∈U×U,?a∈A,fa(x)

=fb(y)}

(1)

定義3 對(duì)于?X?U，屬性A的等價(jià)類Ei=[x]A，X的下近似集定義為：A-(X)=∪{Ei∈A∧Ei?X}，表示等價(jià)類Ei=[x]A中的元素x一定屬于X；X的上近似集定義為：A-(X)=∪{Ei∈A∧X≠?}，表示等價(jià)類Ei=[x]A中的元素x不一定屬于X。

定義4 在數(shù)據(jù)決策表S=中，Q?C，決策屬性D相對(duì)于條件屬性Q的依賴度見(jiàn)式(2)：

γ(Q,D)=|PosQ(D)|/|U|

(2)

式中|PosQ(D)|表示正域PosQ(D)所含元素個(gè)數(shù)；|U|表示整個(gè)信息系統(tǒng)所含對(duì)象個(gè)數(shù)。

2.2 基于信息熵改進(jìn)的屬性約簡(jiǎn)

從尋找最小屬性約簡(jiǎn)集的角度出發(fā)，鑒于屬性重要性在信息論觀點(diǎn)中的定義和其在代數(shù)觀點(diǎn)下的定義的不一致性[10]，故結(jié)合基于正域和基于信息熵的屬性約簡(jiǎn)算法，針對(duì)傳統(tǒng)的粗糙集理論無(wú)法進(jìn)行海量數(shù)據(jù)計(jì)算的問(wèn)題，提出了一種使用信息熵下定義的屬性重要度作為啟發(fā)式函數(shù)的并行屬性約簡(jiǎn)算法。此算法對(duì)基于信息熵的屬性約簡(jiǎn)算法進(jìn)行改進(jìn)，使用和CEBARKC[5]算法一樣的搜索空間，以原始條件屬性集作為出發(fā)點(diǎn)，使用根據(jù)熵定義的屬性重要度作為啟發(fā)條件，依次刪除相對(duì)最不重要的屬性，以決策表的正域作為檢查是否終止約簡(jiǎn)算法的條件，對(duì)于得出的約簡(jiǎn)集，進(jìn)行每個(gè)屬性必要性的檢查以確保是最小的約簡(jiǎn)集，從而達(dá)到了減少冗余屬性的目的。此算法結(jié)合正域和信息熵，消除了信息論下和代數(shù)觀點(diǎn)下的屬性重要度定義的不一致性。基于信息熵改進(jìn)的屬性約簡(jiǎn)算法如算法1所示。

算法1 基于信息熵改進(jìn)的屬性約簡(jiǎn)算法IDSDR

Input：數(shù)據(jù)決策表S=，R=C∪D

Output：屬性約簡(jiǎn)集RedSet

1Begin

2RedSet=C

3ComputePosC(D)，foreacha∈C，ComputeH(D|a)

4Foreacha∈RedSet，Compute

5SGF(a,RedSet,D)=H(D|RedSet-{a})-H(D|RedSet)，并對(duì)其進(jìn)行降序排列

6 選擇使SGF(a,RedSet,D)達(dá)到最小值的ai，如果有多個(gè)ai同時(shí)使SGF達(dá)到最小，則選擇H(D|{ai})值最大的ai

7IFPosRedSet-{ai}(D)=PosC(D)

8Thenai可被約簡(jiǎn)，RedSet=RedSet-{ai}轉(zhuǎn)到Step4

9Elseai不可被約簡(jiǎn)，若同時(shí)存在多個(gè)ai使SGF達(dá)到最大值，則選擇次小的(剩余的ai中，H(D|{ai})值最大的)轉(zhuǎn)到Step6

10untilRedSet所有屬性都不可被約簡(jiǎn)

11 檢查屬性約簡(jiǎn)集RedSet是否存在冗余屬性

12Fori=1toRedSet.size

13IfPosRedSet-{ai}(D)=U

14RedSet=RedSet-{ai}

15Endfor

16End

此算法中第四行至第五行是計(jì)算每一個(gè)屬性的條件熵，找到現(xiàn)有RedSet中使得SGF值達(dá)到最大的屬性；第六行根據(jù)正域來(lái)判斷此屬性是否可以約簡(jiǎn)，當(dāng)?shù)贸鯮edSet時(shí)，第十行至第十一行根據(jù)正域去除約簡(jiǎn)集中的冗余屬性，從而求得最小的約簡(jiǎn)集。通過(guò)信息熵下的屬性重要度定義找到使得相應(yīng)的屬性，通過(guò)正域判斷是否可以約簡(jiǎn)從而保證了信息論觀點(diǎn)下和代數(shù)觀點(diǎn)下的一致性。

2.3MapReduce下基于信息熵改進(jìn)的屬性約簡(jiǎn)

為了解決處理海量數(shù)據(jù)在單機(jī)模式下存儲(chǔ)性能和訪問(wèn)效率低問(wèn)題，本文結(jié)合MapReduce編程思想給出基于信息熵改進(jìn)的屬性約簡(jiǎn)并行化算法。為了提升方案適用范圍，保證算法在硬件條件不佳的情況下仍能正常使用，我們以單機(jī)模式展開討論，當(dāng)然本文方案可以通過(guò)簡(jiǎn)單的配置部署在任意具備MapReduce機(jī)制的集群之上。

在進(jìn)行并行數(shù)據(jù)約簡(jiǎn)之前，需將原始海量數(shù)據(jù)分成若干個(gè)子數(shù)據(jù)集，并上傳到Hadoop集群的分布式文件系統(tǒng)HDFS上，Hadoop集群按輸入的數(shù)據(jù)量，利用資源感知調(diào)度器來(lái)統(tǒng)一分配和調(diào)度計(jì)算機(jī)資源，使每一個(gè)子數(shù)據(jù)集對(duì)應(yīng)一個(gè)Mapper任務(wù)。針對(duì)每一個(gè)Mapper任務(wù)，每個(gè)子數(shù)據(jù)集形式化為數(shù)據(jù)決策表，每個(gè)數(shù)據(jù)決策表可單獨(dú)計(jì)算等價(jià)類，由定義2和定義4可知相同的等價(jià)關(guān)系是不可區(qū)分的，即子決策表的等價(jià)類合并后與原決策表的等價(jià)類是等價(jià)的。

下面給出MapReduce下通過(guò)并行計(jì)算等價(jià)類，基于信息熵的并行屬性約簡(jiǎn)算法IDSDRM，該算法由一個(gè)Map函數(shù)，一個(gè)Reduce函數(shù)，一個(gè)Main函數(shù)構(gòu)成。

算法2 基于信息熵改進(jìn)的屬性約簡(jiǎn)并行化算法IDSDRM

Input：一個(gè)數(shù)據(jù)決策表S

Output：一個(gè)數(shù)據(jù)屬性約減RedSetD(C)

1Begin

2letRedSet=C

4ComputePosC(D)

5Foreacha∈C

7ComputeH(D|a)

8Endfor

9Foreacha∈RedSet

11ComputeH(D|RedSet)

13ComputeH(D|RedSet-{a})和SGF(a,RedSet,D)

14Endfor

15 對(duì)SGF(a,RedSet,D)值進(jìn)行降序排序

16 選擇使SGF(a,RedSet,D)達(dá)到最小值的ai，如果有多個(gè)ai同時(shí)使SGF達(dá)到最小，則選擇H(D|{ai})值最大的ai

18ComputePosRedSet-{ai}(D)

19IfPosRedSet-{ai}(D)=PosC(D)

Thenai可被約簡(jiǎn)，RedSet=RedSet-{ai}轉(zhuǎn)到Step9

Else

Thenai不可被約簡(jiǎn)，若同時(shí)存在多個(gè)ai使SGF達(dá)到最大值，則選擇次小的(剩余的ai中，H(D|{ai})值最大的)轉(zhuǎn)到Step17

20 直到RedSet所有屬性都不可被約簡(jiǎn)

21 檢查屬性約簡(jiǎn)集RedSet是否存在冗余屬性

22Fori=1toRedSet.size

24ComputePosRedSet-{ai}(D)

25IfPosRedSet-{ai}(D)=U

ThenletRedSet=RedSet-{ai}

26Endfor

27Ouput(RedSet)

28End

3 約簡(jiǎn)算法的實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

為了說(shuō)明IDSDRM算法的約簡(jiǎn)效果和處理海量數(shù)據(jù)的性能效果，需要兩組不同的實(shí)驗(yàn)數(shù)據(jù)。故有以下數(shù)據(jù)：

IDSDRM算法性能實(shí)驗(yàn)的數(shù)據(jù)集為UCI數(shù)據(jù)集中的BreastCancer(BC)、GerMan(GM)、House-votes-84(HV)、Auto(AT)和Soybean-large(SBL)這五個(gè)數(shù)據(jù)集，如表1所示。

表1 UCI 五個(gè)數(shù)據(jù)集信息

IDSDRM算法性能實(shí)驗(yàn)的數(shù)據(jù)來(lái)源于中國(guó)氣象科學(xué)數(shù)據(jù)共享服務(wù)網(wǎng)，該數(shù)據(jù)集為中國(guó)752個(gè)站點(diǎn)1951年以來(lái)的最新日值數(shù)據(jù)集，該數(shù)據(jù)集要素包括平均本站氣壓、日最高本站氣壓、日最低本站氣壓、平均氣溫、日最高氣溫、日最低氣溫、平均水汽壓、平均相對(duì)濕度、最小相對(duì)濕度、20-20時(shí)降水量、小型蒸發(fā)量、平均風(fēng)速、最大風(fēng)速、最大風(fēng)速的風(fēng)向、日照時(shí)數(shù)等，總共包含有19個(gè)要素。其中，選取內(nèi)蒙古地區(qū)內(nèi)的數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，20-20時(shí)降水量為決策屬性，其余18個(gè)要素為條件屬性，形成由9 000 000條數(shù)據(jù)組成大小為5.9 GB數(shù)據(jù)集，考慮數(shù)據(jù)集大小對(duì)實(shí)驗(yàn)結(jié)果的影響，按著對(duì)象數(shù)等差遞增，從中抽取大小不同的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，6個(gè)數(shù)據(jù)集的具體信息如表2所示。

表2 氣象數(shù)據(jù)的6個(gè)數(shù)據(jù)集信息

3.2 實(shí)驗(yàn)結(jié)果及分析

3.2.1 IDSDRM算法的約簡(jiǎn)實(shí)驗(yàn)

三種算法的實(shí)驗(yàn)約簡(jiǎn)結(jié)果對(duì)比如表3所示。從表中可看出IDSDR算法(簡(jiǎn)稱C)約簡(jiǎn)后的屬性個(gè)數(shù)少于其他兩種算法A和B。根據(jù)屬性蒸發(fā)率評(píng)判標(biāo)準(zhǔn)，約簡(jiǎn)效果是較好的。

表3 約簡(jiǎn)前后條件屬性數(shù)對(duì)比

3.2.2IDSDRM算法的性能實(shí)驗(yàn)

1) 運(yùn)行時(shí)間

為了驗(yàn)證IDSDRM并行算法的優(yōu)越性，選取表2中的六組數(shù)據(jù)進(jìn)行運(yùn)行時(shí)間實(shí)驗(yàn)，這六組數(shù)據(jù)集由小到大，實(shí)驗(yàn)結(jié)果如圖1所示。從圖中可以看出，當(dāng)數(shù)據(jù)量較小時(shí)，所用運(yùn)行時(shí)間比數(shù)據(jù)量較大的所用時(shí)間要多，產(chǎn)生這樣的結(jié)果是因?yàn)镠adoop進(jìn)行計(jì)算之前，先把數(shù)據(jù)集分成若干數(shù)據(jù)塊，當(dāng)數(shù)據(jù)集較小時(shí)，這些數(shù)據(jù)塊即為小文件。使用HDFS存儲(chǔ)數(shù)據(jù)文件時(shí)，HDFS是為訪問(wèn)大文件而設(shè)計(jì)，當(dāng)對(duì)小文件讀取時(shí)通常會(huì)造成大量的中間文件，從而造成低效的訪問(wèn)方式。IDSDRM并行算法是為不能在單機(jī)模式下運(yùn)行的大數(shù)據(jù)設(shè)計(jì)的，故當(dāng)數(shù)據(jù)大小超過(guò)單機(jī)模式可運(yùn)行的最大數(shù)據(jù)時(shí)，并行算法的優(yōu)勢(shì)會(huì)突顯出來(lái)。

圖1 不同數(shù)據(jù)集下IDSDRM并行算法的運(yùn)行時(shí)間

2) 可擴(kuò)展性

表4 算法IDSDRM在不同數(shù)據(jù)集下的擴(kuò)展比

3) 加速比

表5 算法IDSDRM在不同數(shù)據(jù)集下的加速比

4 結(jié) 語(yǔ)

本文針對(duì)傳統(tǒng)的粗糙集屬性約簡(jiǎn)算法不是最小約簡(jiǎn)集的缺點(diǎn)，提出了使用根據(jù)熵定義的屬性重要度作為啟發(fā)條件，依次刪除相對(duì)最不重要的屬性，以決策表的正域作為檢查是否終止約簡(jiǎn)算法的條件，并利用MapReduce編程框架實(shí)現(xiàn)，在Hadoop平臺(tái)上進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，本文提出的MapReduce下基于信息熵改進(jìn)的屬性約簡(jiǎn)算法具有良好的可擴(kuò)展性和加速比，且從屬性蒸發(fā)率可看出約簡(jiǎn)效果優(yōu)于傳統(tǒng)的基于正域的屬性約簡(jiǎn)和基于信息熵的屬性約簡(jiǎn)算法。

[1] 錢進(jìn),苗奪謙,張澤華.云計(jì)算環(huán)境下知識(shí)約簡(jiǎn)算法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(12):2332-2343.

[2] Yang Y,Chen Z,Liang Z,et al.Attribute reduction for massive data based on rough set theory and MapReduce[C]//Proceedings of the 5th International Conference on Rough Set and Knowledge Technology.Springer,2010:672-678.

[3]ZhangJ,LiT,RuanD,etal.Aparallelmethodforcomputingroughsetapproximations[J].InformationSciences,2012,194:209-223.

[4] 曲朝陽(yáng),陳帥,楊帆,等.基于云計(jì)算技術(shù)的電力大數(shù)據(jù)預(yù)處理屬性約簡(jiǎn)方法[J].電力系統(tǒng)自動(dòng)化,2014,38(8):67-71.

[5] 徐章艷,劉作鵬,楊炳儒,等.一個(gè)復(fù)雜度為max(O(|C||U|),O(|C|2|U/C|))的快速屬性約簡(jiǎn)算法[J].計(jì)算機(jī)學(xué)報(bào),2006,29(3):391-399.

[6] 胡清華,趙輝,于達(dá)仁.基于粗糙集的符號(hào)與數(shù)值屬性的快速約簡(jiǎn)算法[C]//第七屆中國(guó)Rough集與軟計(jì)算、第一屆中國(guó)Web智能、第一屆中國(guó)粒計(jì)算聯(lián)合會(huì)議(CRSSC-CWI-CGrC’2007)論文集,2007.

[7]WangX,YangJ,TengX,etal.Featureselectionbasedonroughsetsandparticleswarmoptimization[J].PatternRecognitionLetters,2007,28(4):459-471.

[8]QianY,ZhangH,SangY,etal.Multigranulationdecision-theoreticroughsets[J].InternationalJournalofApproximateReasoning,2014,55(1):225-237.

[9] 景運(yùn)革.基于粗糙集屬性約簡(jiǎn)算法的研究[M].成都:西南交通大學(xué)出版社,2013.

[10] 張文修,吳偉志,梁吉業(yè),等.粗糙集理論與方法[M].北京:科學(xué)出版社,2001.

[11]BartokJ,HabalaO,BednarP,etal.Dataminingandintegrationforpredictingsignificantmeteorologicalphenomena[J].ProcediaComputerScience,2010,1(1):37-46.

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

[13] 王國(guó)胤,于洪,楊大春.基于條件信息熵的決策表約簡(jiǎn)[J].計(jì)算機(jī)學(xué)報(bào),2002,25(7):759-766.

[14] 王玨,王任,苗奪謙,等.基于RoughSet理論的“數(shù)據(jù)濃縮”[J].計(jì)算機(jī)學(xué)報(bào),1998,21(5):393-400.

EFFICIENT ROUGH SET ATTRIBUTE REDUCTION ALGORITHM BASED ON MAPREDUCE

Lü Jie1Liu Limin1Hu Jiaoyue1Xu Zhiwei1,2

1(CollegeofInformationEngineering,InnerMongoliaUniversityofTechnology,Huhhot010080,InnerMongolia,China)2(InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100086,China)

Aiming at the problem that the traditional attribute reduction algorithm based on positive domain and the attribute reduction algorithm based on information entropy can’t get the minimum reduction set in rough set theory, an optimized attribute reduction algorithm based on information entropy is proposed. The conditional entropy is used to identify the attribute with the highest significance value, and the positive domain is used to the reduction judgment. On this basis, an efficient algorithm of information entropy improved attribute reduction based on MapReduce is designed. Based on the real meteorological data, the algorithm is implemented on Hadoop cluster, and the effectiveness and efficiency of the algorithm are verified.

Attribute reduction Rough set theory Information entropy

2016-03-15。國(guó)家自然科學(xué)基金項(xiàng)目(61540004)。呂潔，碩士生，主研領(lǐng)域：云計(jì)算與大數(shù)據(jù)分析。劉利民，教授。胡皎月，碩士生。許志偉，講師。

TP311

A

10.3969/j.issn.1000-386x.2017.04.046