粗糙集屬性約簡(jiǎn)算法綜述

唐衛(wèi)國(guó)張 濤羅 奕徐晉勇

（1.廣西壯族自治區(qū)右江礦務(wù)局有限公司，廣西 百色 531501；2.桂林電子科技大學(xué)，廣西 桂林 541004）

粗糙集屬性約簡(jiǎn)算法綜述

唐衛(wèi)國(guó)1張 濤2羅 奕2徐晉勇2

（1.廣西壯族自治區(qū)右江礦務(wù)局有限公司，廣西 百色 531501；2.桂林電子科技大學(xué)，廣西 桂林 541004）

屬性約簡(jiǎn)是粗糙集理論中最核心的問(wèn)題。文章闡述了基于信息熵、可辨識(shí)矩陣、遺傳算法、Johnson等粗糙集屬性約簡(jiǎn)算法流程，指出了粗糙集屬性約簡(jiǎn)算法的現(xiàn)有問(wèn)題及發(fā)展趨勢(shì)，促進(jìn)粗糙集屬性約簡(jiǎn)的研究進(jìn)一步發(fā)展。

屬性約簡(jiǎn)；粗糙集理論；算法

隨著計(jì)算機(jī)網(wǎng)絡(luò)的高速發(fā)展，人們所要處理的數(shù)據(jù)越來(lái)越多。在大量數(shù)據(jù)中會(huì)伴有不確定問(wèn)題。目前處理不確定性問(wèn)題的方法主要包括概率統(tǒng)計(jì)、模糊理論、證據(jù)理論等[1]。但這些方法必須依靠大量的先驗(yàn)知識(shí)。粗糙集理論很好彌補(bǔ)了以上方法缺點(diǎn)，可以有效處理不確定信息，卻不需要任何先驗(yàn)知識(shí)[2]。

粗糙集約簡(jiǎn)是粗糙集理論中最重要一環(huán)，包括值約簡(jiǎn)和屬性約簡(jiǎn)兩種。目前，大量的研究都是側(cè)重于屬性約簡(jiǎn)[3]。屬性約簡(jiǎn)，就是在保證系統(tǒng)本身含義前提下，刪除其中多余或重復(fù)的屬性，保留起決定作用的核心屬性。通過(guò)屬性約簡(jiǎn)，可以在不改變系統(tǒng)本身含義的前提下得到更簡(jiǎn)潔的決策屬性。

對(duì)于信息表I(U,A)，如果有屬性集B?A，且滿足ind(B)=ind(A)，則稱(chēng)B為A的一個(gè)約簡(jiǎn)，記為red(A)。ind(A)，ind(B)代表著A和B上的不可分辨關(guān)系。

集A所有約簡(jiǎn)的交集稱(chēng)為A的核，記為core(A)，即：

core(A)含有屬性集A的全部約簡(jiǎn)集合中共同的等價(jià)關(guān)系，是屬性集A中最重要集合。核的定義表示了核屬性是約簡(jiǎn)屬性集中一部分，利用核屬性可以更迅速的進(jìn)行屬性約簡(jiǎn)，改變屬性核屬性就會(huì)影響屬性約簡(jiǎn)的前后一致性[4]。

1 粗糙集約簡(jiǎn)算法初探

1.1基于信息熵的約簡(jiǎn)算法

屬性集M相對(duì)于屬性集K的條件熵H(K｜M)為：

屬性集M同屬性集K的互信息為：

基于信息熵的約簡(jiǎn)算法流程為：

步驟1：針對(duì)決策表S=(U,C∪D,V,f )，計(jì)算決策屬性D的信息熵H(D)；

步驟2：計(jì)算條件屬性C同決策屬性D的互信息量I(C,D)；

步驟3：求核屬性。初始化core=?，對(duì)?a∈C，有f(x, D)≠f(y,D)，且f(x,C-a)= f(y,C-a)，屬性a就為決策表的核屬性；

步驟4：令R等于核屬性，并計(jì)算R同決策屬性D的互信息量I(R, D)；

步驟5：對(duì)?a∈C-R，計(jì)算其同決策屬性D的互信息量I(a, D)，找出使互信息量最大的屬性a，且R=R∪{a}；

步驟6：計(jì)算此時(shí)屬性R同決策屬性D的互信息量I(R,D)，判斷屬性R的信息量和條件屬性C的信息量是否相等，如果是就停止運(yùn)算；否則轉(zhuǎn)至步驟5。

1.2基于可辨識(shí)矩陣的約簡(jiǎn)算法

基于可辨識(shí)矩陣約簡(jiǎn)算法的流程為：

步驟1：針對(duì)知識(shí)表達(dá)系統(tǒng)S=(U, C∪D,V,f )，C為條件屬性，D為決策屬性，a(x)、D(x)為第x條記錄對(duì)應(yīng)屬性的值。建立決策表的可辨識(shí)矩陣M=(mij)n×n。(mij)n×n有如下定義[6]：

其中i,j=1,2,…,n。

步驟2：如果M=(mij)n×n中存在單屬性元素，則將其歸入集合R，集合R就稱(chēng)為核屬性，并轉(zhuǎn)至步驟4，否則建立可辨識(shí)矩陣中非零元素的析取表達(dá)式：

其中ai為非零元素mij中的屬性項(xiàng)。

步驟3：對(duì)任意Ri=R(i=1, 2, …, n)，如果Ri∈M，則令M中與Ri對(duì)應(yīng)元素等于0，得到新的矩陣M′。對(duì)新矩陣M′中的所有非零元素建立析取表達(dá)式：

ai為非零元素mij中的屬性項(xiàng)。

步驟4：將析取表達(dá)式進(jìn)行合取運(yùn)算，得到合取范式為：

步驟5：將合取范式L轉(zhuǎn)換為析取范式：

步驟6：將核屬性R中的屬性插入L′中的每個(gè)析取范式中，得到的每一組集合就為一個(gè)屬性約簡(jiǎn)結(jié)果。基于可辨識(shí)矩陣約簡(jiǎn)算法得到的約簡(jiǎn)結(jié)果通常都不止一組。

1.3基于遺傳算法的約簡(jiǎn)算法

定義2 在一個(gè)知識(shí)表達(dá)系統(tǒng)中，P、Q分別為論域中的屬性集合。當(dāng)

稱(chēng)屬性Q是km度依賴(lài)于屬性P的，︱·︱表示屬性集合中包含對(duì)象個(gè)數(shù)。

定義3 令屬性子集PP′?，則P′關(guān)于Q的重要性定義為：

特別的，當(dāng)P′={a}時(shí)，屬性a∈P關(guān)于Q的重要性定義為：

定義4 適值函數(shù)是在遺傳算法中評(píng)價(jià)個(gè)體位串適應(yīng)性的標(biāo)準(zhǔn)，定義為[7]：

每個(gè)個(gè)體被選擇的概率可以表示為：

其中n表示條件屬性的數(shù)量，c(x)表示個(gè)體所含條件屬性的數(shù)量，k表示全部條件屬性相對(duì)于決策屬性的依賴(lài)度，kp為每個(gè)個(gè)體包含的條件屬性相對(duì)于決策屬性的依賴(lài)度。

根據(jù)以上定義，遺傳算法的流程為：

步驟1：知識(shí)表達(dá)系統(tǒng)S=(U,C∪D,V,f )，由公式(12)計(jì)算條件屬性C相對(duì)于決策屬性D的依賴(lài)度kp；

步驟3：產(chǎn)生n個(gè)長(zhǎng)度為r的初始種群，個(gè)體中每一位對(duì)應(yīng)一個(gè)條件屬性；

步驟4：計(jì)算每個(gè)個(gè)體所含條件屬性相對(duì)于決策屬性D的依賴(lài)度kp，并利用式(14)計(jì)算出適值最大的個(gè)體傳遞給下一代；

步驟5：對(duì)于規(guī)模為n的種群，計(jì)算其每個(gè)個(gè)體適值及被選擇的概率，得出被選擇的期望數(shù)。以輪盤(pán)賭的方式對(duì)個(gè)體進(jìn)行挑選，組成新的種群；

步驟6：對(duì)種群進(jìn)行交叉和變異操作，并針對(duì)于現(xiàn)階段的每個(gè)個(gè)體，再次計(jì)算所含條件屬性相對(duì)于決策屬性的依賴(lài)度kp和每個(gè)個(gè)體的適值；

步驟7：判斷遺傳算法是否成熟（連續(xù)n代的最優(yōu)個(gè)體適值不繼續(xù)增加），如果最優(yōu)個(gè)體的依賴(lài)度k=kp，且該屬性集合的具有獨(dú)立性，則停止運(yùn)算，否則轉(zhuǎn)至步驟5。

1.4基于Johnson算法的約簡(jiǎn)算法

Johnson算法是一個(gè)新型約簡(jiǎn)算法，由用戶(hù)來(lái)決定屬性的權(quán)重，從而可以快速地計(jì)算出約簡(jiǎn)組合[8]。選取當(dāng)前頻率最大的屬性加入約簡(jiǎn)組合，如果一個(gè)屬性出現(xiàn)次數(shù)的頻率越大，它的可分辨能力就越強(qiáng)。而且Johnson算法得出的約簡(jiǎn)組合只有一組，相比于其他方法更加直觀。設(shè)定R表示約簡(jiǎn)，其算法流程為：

步驟2：計(jì)算可分辨矩陣M，M={mij:mij≠?}；

步驟3：計(jì)算屬性ai在M中出現(xiàn)的次數(shù)ωai(M)；

步驟4：選擇使ωai(M)最大的屬性記為a，R=R∪{a}；

步驟5：將M中包含a屬性的全部刪除；

步驟6：如果M=?，停止計(jì)算，否則轉(zhuǎn)至步驟3。

2 屬性約簡(jiǎn)方法存在問(wèn)題發(fā)展趨勢(shì)

粗糙集理論的優(yōu)越性在很多實(shí)際應(yīng)用中得到了證明，其屬性約簡(jiǎn)仍有一些間題有待解決。下面列舉一些今后可能的研究方向。

（1）如何提高約簡(jiǎn)算法的效率，降低算法的執(zhí)行效率和復(fù)雜度，是進(jìn)一步研究粗糙集理論的關(guān)鍵部分；

（2）當(dāng)屬性值不是一個(gè)固定值，而是一個(gè)連續(xù)區(qū)間時(shí)，如何將數(shù)據(jù)進(jìn)行合理的離散化處理，直接從這類(lèi)信息系統(tǒng)中獲取知識(shí)是一個(gè)值得研究的問(wèn)題；

（3）屬性約簡(jiǎn)方法眾多，在實(shí)際應(yīng)用中可以互相融合，提高約簡(jiǎn)速度。如很多方法就使用可辨識(shí)矩陣來(lái)獲取核屬性集[9]。

3 總結(jié)

本文總結(jié)了現(xiàn)有粗糙集屬性約簡(jiǎn)方法，分析了現(xiàn)有方法的存在缺點(diǎn)，并提出了未來(lái)的發(fā)展趨勢(shì)。粗糙集屬性約簡(jiǎn)方法的不斷完善對(duì)如何在大數(shù)據(jù)時(shí)代做出正確的決策具有重要的理論和現(xiàn)實(shí)意義。

[1] 王國(guó)胤,姚一豫,于洪.粗糙集理論與應(yīng)用研究綜述[J].計(jì)算機(jī)學(xué)報(bào),2009,32(7):1229-1246.

[2] 湯建國(guó),祝峰,佘堃.粗糙集與其他軟計(jì)算理論結(jié)合情況研究綜述[J].計(jì)算機(jī)應(yīng)用研究,2010,27(7):2404-2410.

[3] 黃楠.基于粗糙集和模糊聚類(lèi)方法的屬性約簡(jiǎn)算法[J].電腦知識(shí)與技術(shù),2012,8(32):7718-7719.

[4] 譚旭.改進(jìn)分辨矩陣下的增量式條件屬性約簡(jiǎn)算法[J].系統(tǒng)工程理論與實(shí)踐,2010,30(9):1684-1694.

[5] 陳媛,楊棟.基于信息熵的屬性約簡(jiǎn)算法及應(yīng)用[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué)),2013,27(1):42-46.

[6] Yiyu Yao, Yan Zhao. Discernibility Matrix Simplification for Constructing Attribute Reducts[J]. Information Sciences, 2009, 179(17):867-882.

[7] 顏艷,楊慧中.基于遺傳算法的粗糙集屬性約簡(jiǎn)算法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(31):156-158.

[8] 陳桂芬,馬麗,董瑋.聚類(lèi)、粗糙集與決策樹(shù)的組合算法在地力評(píng)價(jià)中的應(yīng)用[J].中國(guó)農(nóng)業(yè)科學(xué),2011,44(23): 4833-4840.

[9] Junbo Zhang, Tianrui Li, Da Ruan, et al. Rough Sets based Matrix Approaches with Dynamic Attribute Variation in Set-valued Information Systems[J]. International Journal of Approximate Reasoning,2012, 53(4):620-635.

A survey of rough set reduction process algorithm

Attribute reduction is most important issue in the rough set theory. This paper describes rough set reduction process algorithm based on information entropy, discernable matrix, genetic algorithms, Johnson algorithms, pointing current problems and developing tendency in rough set reduction process algorithm, motivating higher research development of rough set reduction process algorithm.

Rough set;reduction process;algorithm

O13

A

1008-1151(2015)11-0017-03

2015-10-12

廣西科學(xué)研究與技術(shù)開(kāi)發(fā)計(jì)劃（桂科能1598020-8）。

唐衛(wèi)國(guó)（1974－），廣西壯族自治區(qū)右江礦務(wù)局有限公司工程師，研究生學(xué)歷，碩士，研究方向?yàn)榈V山通風(fēng)與安全工程。

徐晉勇（1962－），男，桂林電子科技大學(xué)教授，博士，從事金屬材料表面改性、機(jī)械工程及其產(chǎn)業(yè)化的研究。