基于MapReduce的高效粗糙集屬性約簡算法

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

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

基于MapReduce的高效粗糙集屬性約簡算法

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

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

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

屬性約簡 粗糙集理論 信息熵

0 引 言

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

1 研究現(xiàn)狀

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

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

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

2 粗糙集屬性約簡

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

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

2.1 粗糙集基本概念

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

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

=fb(y)}

(1)

定義3 對于?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相對于條件屬性Q的依賴度見式(2)：

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

(2)

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

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

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

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

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

Output：屬性約簡集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)，并對其進(jìn)行降序排列

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

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

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

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

10untilRedSet所有屬性都不可被約簡

11 檢查屬性約簡集RedSet是否存在冗余屬性

12Fori=1toRedSet.size

13IfPosRedSet-{ai}(D)=U

14RedSet=RedSet-{ai}

15Endfor

16End

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

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

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

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

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

算法2 基于信息熵改進(jì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 對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可被約簡，RedSet=RedSet-{ai}轉(zhuǎn)到Step9

Else

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

20 直到RedSet所有屬性都不可被約簡

21 檢查屬性約簡集RedSet是否存在冗余屬性

22Fori=1toRedSet.size

24ComputePosRedSet-{ai}(D)

25IfPosRedSet-{ai}(D)=U

ThenletRedSet=RedSet-{ai}

26Endfor

27Ouput(RedSet)

28End

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

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

為了說明IDSDRM算法的約簡效果和處理海量數(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ù)來源于中國氣象科學(xué)數(shù)據(jù)共享服務(wù)網(wǎng)，該數(shù)據(jù)集為中國752個(gè)站點(diǎn)1951年以來的最新日值數(shù)據(jù)集，該數(shù)據(jù)集要素包括平均本站氣壓、日最高本站氣壓、日最低本站氣壓、平均氣溫、日最高氣溫、日最低氣溫、平均水汽壓、平均相對濕度、最小相對濕度、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ù)集大小對實(shí)驗(yàn)結(jié)果的影響，按著對象數(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算法的約簡實(shí)驗(yàn)

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

表3 約簡前后條件屬性數(shù)對比

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存儲數(shù)據(jù)文件時(shí)，HDFS是為訪問大文件而設(shè)計(jì)，當(dāng)對小文件讀取時(shí)通常會造成大量的中間文件，從而造成低效的訪問方式。IDSDRM并行算法是為不能在單機(jī)模式下運(yùn)行的大數(shù)據(jù)設(shè)計(jì)的，故當(dāng)數(shù)據(jù)大小超過單機(jī)模式可運(yùn)行的最大數(shù)據(jù)時(shí)，并行算法的優(yōu)勢會突顯出來。

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

2) 可擴(kuò)展性

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

3) 加速比

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

4 結(jié) 語

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

[1] 錢進(jìn),苗奪謙,張澤華.云計(jì)算環(huá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] 曲朝陽,陳帥,楊帆,等.基于云計(jì)算技術(shù)的電力大數(shù)據(jù)預(yù)處理屬性約簡方法[J].電力系統(tǒng)自動化,2014,38(8):67-71.

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

[6] 胡清華,趙輝,于達(dá)仁.基于粗糙集的符號與數(shù)值屬性的快速約簡算法[C]//第七屆中國Rough集與軟計(jì)算、第一屆中國Web智能、第一屆中國粒計(jì)算聯(lián)合會議(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)革.基于粗糙集屬性約簡算法的研究[M].成都:西南交通大學(xué)出版社,2013.

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

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

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

[13] 王國胤,于洪,楊大春.基于條件信息熵的決策表約簡[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。國家自然科學(xué)基金項(xiàng)目(61540004)。呂潔，碩士生，主研領(lǐng)域：云計(jì)算與大數(shù)據(jù)分析。劉利民，教授。胡皎月，碩士生。許志偉，講師。

TP311

A

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