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

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

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

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

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

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

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

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

0 引 言

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

1 研究現(xiàn)狀

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

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

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

2 粗糙集屬性約簡

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

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

2.1 粗糙集基本概念

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

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

=fb(y)}

(1)

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

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

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

(2)

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

2.2 基于信息熵改進的屬性約簡

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

算法1 基于信息熵改進的屬性約簡算法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)，并對其進行降序排列

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

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

8Thenai可被約簡，RedSet=RedSet-{ai}轉到Step4

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

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

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

12Fori=1toRedSet.size

13IfPosRedSet-{ai}(D)=U

14RedSet=RedSet-{ai}

15Endfor

16End

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

2.3MapReduce下基于信息熵改進的屬性約簡

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

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

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

算法2 基于信息熵改進的屬性約簡并行化算法IDSDRM

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

Output：一個數(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)值進行降序排序

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

18ComputePosRedSet-{ai}(D)

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

Thenai可被約簡，RedSet=RedSet-{ai}轉到Step9

Else

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

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

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

22Fori=1toRedSet.size

24ComputePosRedSet-{ai}(D)

25IfPosRedSet-{ai}(D)=U

ThenletRedSet=RedSet-{ai}

26Endfor

27Ouput(RedSet)

28End

3 約簡算法的實驗分析

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

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

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

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

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

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

3.2 實驗結果及分析

3.2.1 IDSDRM算法的約簡實驗

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

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

3.2.2IDSDRM算法的性能實驗

1) 運行時間

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

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

2) 可擴展性

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

3) 加速比

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

4 結 語

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

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

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

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

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

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

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

[13] 王國胤,于洪,楊大春.基于條件信息熵的決策表約簡[J].計算機學報,2002,25(7):759-766.

[14] 王玨,王任,苗奪謙,等.基于RoughSet理論的“數(shù)據(jù)濃縮”[J].計算機學報,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。國家自然科學基金項目(61540004)。呂潔，碩士生，主研領域：云計算與大數(shù)據(jù)分析。劉利民，教授。胡皎月，碩士生。許志偉，講師。

TP311

A

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