決策系統(tǒng)中約簡(jiǎn)的不一致分析

鄧大勇

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

0 引 言

粗糙集理論是一種處理不完全、不精確、不一致數(shù)據(jù)的有效數(shù)學(xué)工具[1-9].自20世紀(jì)80年代初Pawlak教授創(chuàng)立粗糙集理論以來(lái)，粗糙集理論在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、模式識(shí)別、人工智能等領(lǐng)域有著非常廣泛的應(yīng)用.其理論發(fā)展很快，到目前為止已創(chuàng)立了很多種類的粗糙集擴(kuò)展模型，主要包括：可變精度粗糙集、概率粗糙集、貝葉斯粗糙集、S粗糙集、占優(yōu)關(guān)系粗糙集、特征關(guān)系粗糙集、相容或相似關(guān)系粗糙集、粗糙模糊集和模糊粗糙集等[1-11].

眾多的粗糙集理論都應(yīng)用于分類，上近似、下近似等概念是其核心的內(nèi)容，數(shù)據(jù)約簡(jiǎn)是它們最主要的應(yīng)用.大部分粗糙集方法都只對(duì)正區(qū)域內(nèi)的個(gè)體進(jìn)行分類，對(duì)負(fù)區(qū)域和邊界區(qū)域的個(gè)體則是通過(guò)轉(zhuǎn)化為其他決策或知識(shí)的正區(qū)域來(lái)處理.數(shù)據(jù)約簡(jiǎn)一般都是保持正區(qū)域，而忽略其他區(qū)域.

但是,粗糙集的約簡(jiǎn)對(duì)數(shù)據(jù)本身有多大的影響呢？對(duì)此類問(wèn)題的研究還未見(jiàn)相關(guān)報(bào)道.本文應(yīng)用3種常用的粗糙集模型，對(duì)決策系統(tǒng)中的不一致程度進(jìn)行了分析.在Pawlak粗糙集、一般決策粗糙集和可變精度粗糙集下，對(duì)約簡(jiǎn)前后決策系統(tǒng)的分類率、未分類率、分類正確率以及決策表的不一致層次等方面進(jìn)行了比較，從而說(shuō)明這3種粗糙集模型下的數(shù)據(jù)約簡(jiǎn)對(duì)數(shù)據(jù)本身的影響.討論結(jié)果對(duì)粗糙集理論的應(yīng)用和發(fā)展具有一定的指導(dǎo)作用，主要體現(xiàn)在應(yīng)用和研究中如何選擇粗糙集及控制分類的精度等方面.

1 決策系統(tǒng)

設(shè)DS=(U,A,D)是一個(gè)決策系統(tǒng)(或決策表)，其中U是非空有限的個(gè)體集合，稱為論域，A是非空的條件屬性集，D是決策屬性集.在決策表DS中,屬性集A的屬性個(gè)數(shù)有多個(gè)，而決策屬性集中的屬性個(gè)數(shù)只有1個(gè)，記為d.本文討論的正是這種情況.

對(duì)?a∈A∪j5i0abt0b，存在一個(gè)對(duì)應(yīng)的a:U→Va，Va是屬性a的值域.任意的屬性子集合B?A∪j5i0abt0b確定了如下一個(gè)不可區(qū)分關(guān)系IND(B):

IND(B)={(x,y)∈U×U|a∈B∧a(x)=a(y)}.

IND(B)是一個(gè)等價(jià)關(guān)系，它對(duì)U的劃分記為U/IND(B)或簡(jiǎn)記為U/B.相對(duì)于B的包含x的等價(jià)類記為IB(x)或[x]B，即IB(x)=[x]B={y∈U| (x,y)∈IND(B)}.于是

U/A={Xj,j=1,2,…,m}={[x]A|x∈U},Xi≠Xj(i≠j);

U/j5i0abt0b={Yj,j=1,2,…,p}={[x]d|x∈U},Yi≠Yj(i≠j).

函數(shù)?B:U→P(Vd)(P(Vd)表示Vd的冪集,B?A)定義為?B(x)={d(y) |y∈[x]B}.其中，?B稱為DS中的一般決策.如果對(duì)所有的x∈U都有card(?A(x))=1，則DS是一致的，否則DS不一致.其中card(5)表示集合的勢(shì).

2 不一致的層次

在粗糙集理論中，決策系統(tǒng)可分為一致決策系統(tǒng)和不一致決策系統(tǒng)，不一致的決策系統(tǒng)還缺少一個(gè)對(duì)不一致程度進(jìn)行度量的指標(biāo).下面就引入這個(gè)指標(biāo).

當(dāng)W=U時(shí)，LI(U)稱為決策系統(tǒng)DS的不一致層次.

當(dāng)個(gè)體的不一致層次為1時(shí)，對(duì)于這個(gè)個(gè)體的決策是一致的;當(dāng)個(gè)體的不一致層次大于1時(shí)，對(duì)于該個(gè)體的決策是不一致的.同樣，當(dāng)決策系統(tǒng)的不一致層次等于1時(shí)，整個(gè)決策系統(tǒng)是一致的;當(dāng)決策系統(tǒng)的不一致層次大于1時(shí)，該決策系統(tǒng)存在不一致.不一致的層次越高，不一致的程度越高.根據(jù)定義1，很容易得到下面幾個(gè)命題：

命題1在決策系統(tǒng)DS=(U,A,d)中，對(duì)?y∈[x]A，都有LI(y)=LI(x).

命題2在決策系統(tǒng)DS=(U,A,d)中，個(gè)體和整個(gè)決策系統(tǒng)的不一致層次隨著條件屬性個(gè)數(shù)的減少而單調(diào)遞增.

命題3在決策系統(tǒng)DS=(U,A,d)中，不一致的最大層次小于等于card(Vd).

不一致層次可以刻畫決策系統(tǒng)中個(gè)體和整個(gè)決策表的不一致程度.粗糙集理論是一種處理不完全、不精確、不一致數(shù)據(jù)的數(shù)學(xué)工具，而且是一種用于分類的數(shù)學(xué)工具,這就有必要從分類的角度對(duì)粗糙集理論進(jìn)行分析.通常是用分類率、未分類率、分類正確率等指標(biāo)對(duì)分類理論或分類算法進(jìn)行考核.分類率是指能夠被分類的數(shù)據(jù)占整個(gè)數(shù)據(jù)的比率；分類正確率是指被分類的數(shù)據(jù)中正確分類的數(shù)據(jù)的比率；未分類率是指不能分類的數(shù)據(jù)在整個(gè)數(shù)據(jù)中所占的比率.在粗糙集理論中，往往只能對(duì)正區(qū)域中的數(shù)據(jù)進(jìn)行分類，在Pawlak粗糙集中，正區(qū)域的數(shù)據(jù)是能夠分類而且能正確分類，在其他形式的粗糙集模型中，正區(qū)域的數(shù)據(jù)雖然能夠分類，但不一定能正確分類.下面將對(duì)幾種粗糙集下決策系統(tǒng)中分類率、未分類率、分類正確率以及不一致層次在約簡(jiǎn)前后進(jìn)行對(duì)比分析.

3 不一致的Pawlak粗糙集分析

在決策系統(tǒng)DS=(U,A,d)中，B?A，Y?U，在Pawkak粗糙集下，下、上近似分別定義為:

?

Pawlak粗糙集的屬性約簡(jiǎn)定義如下：

定義2在決策系統(tǒng)DS=(U,A,d)中,稱B?A是一個(gè)約簡(jiǎn)，當(dāng)且僅當(dāng)B滿足下面2個(gè)條件：

1)POSB(d)=POSA(d)；2)對(duì)?a∈B,都有POSB-{a}(d)≠POSA(d).

根據(jù)定義2知，Pawlak粗糙集的屬性約簡(jiǎn)是一種保持正區(qū)域的約簡(jiǎn)，約簡(jiǎn)后的正區(qū)域、邊界區(qū)域和負(fù)區(qū)域與約簡(jiǎn)前的正區(qū)域、邊界區(qū)域和負(fù)區(qū)域分別保持相等，從而在Pawlak粗糙集的屬性約簡(jiǎn)作用下，決策系統(tǒng)的分類率、未分類率以及分類正確率保持不變.但是,對(duì)于決策表中個(gè)體以及整個(gè)決策表的不一致層次卻不一樣.經(jīng)過(guò)屬性約簡(jiǎn),個(gè)體和整個(gè)決策表的不一致層次會(huì)產(chǎn)生變化，命題4正是刻畫決策表經(jīng)過(guò)Pawlak約簡(jiǎn)之后不一致層次的變化規(guī)律.

命題4決策表經(jīng)過(guò)Pawlak粗糙集的屬性約簡(jiǎn)之后，正區(qū)域部分的個(gè)體的不一致層次保持不變，邊界區(qū)域的個(gè)體的不一致層次隨著屬性的減少而單調(diào)遞增,從而決策表經(jīng)過(guò)Pawlak粗糙集的屬性約簡(jiǎn)之后，正區(qū)域部分的不一致層次不變，邊界區(qū)域的不一致層次隨著屬性的減少而單調(diào)遞增(證明略).

4 不一致的一般決策分析

在不一致決策系統(tǒng)中，非常少的約簡(jiǎn)算法得到的約簡(jiǎn)是Pawlak粗糙集約簡(jiǎn)，大部分約簡(jiǎn)算法都不是Pawlak粗糙集約簡(jiǎn).一般決策在一般情況下不被認(rèn)為是一種單獨(dú)的粗糙集模型，但由于和Skowron差別矩陣有關(guān)的約簡(jiǎn)算法(包括差別矩陣約簡(jiǎn)算法和遺傳算法的約簡(jiǎn)算法等)所得到的約簡(jiǎn)一般情況下都是一般決策約簡(jiǎn)[8]，所以本文將它看成是一個(gè)獨(dú)立的粗糙集模型.

個(gè)體的一般決策約簡(jiǎn)是指在決策系統(tǒng)中該個(gè)體保持一般決策不變的最小屬性子集;決策系統(tǒng)的一般決策約簡(jiǎn)是指決策系統(tǒng)中的每個(gè)個(gè)體都保持一般決策不變的最小屬性子集.

命題5決策系統(tǒng)經(jīng)過(guò)一般決策約簡(jiǎn)之后，決策系統(tǒng)中的任何個(gè)體的不一致層次都保持不變，從而整個(gè)決策表的不一致層次保持不變.

5 不一致的可變精度粗糙集分析

現(xiàn)實(shí)的數(shù)據(jù)是存在噪音的，可變精度粗糙集模型正是基于這點(diǎn)建立的.可變精度粗糙集模型共有3種類型:1種為參數(shù)不對(duì)稱的可變精度粗糙集模型;2種為參數(shù)對(duì)稱的可變精度粗糙集模型.在2種參數(shù)對(duì)稱的可變精度粗糙集模型中，一種模型中的參數(shù)β表示錯(cuò)誤率，另一種模型中的參數(shù)β表示正確率[12-15].這里僅研究后一種情形.

定義6給定論域U，不可區(qū)分關(guān)系B?U×U，Y?U，β∈(0.5,1]，則

分別稱為Y在B下的β下近似和Y在B下的β上近似.Y在B下的β下近似也稱為Y在B下的β正區(qū)域，記為POS(B,Y,β)；BND(B,Y,β)=Bβ(Y)-Bβ(Y)稱為Y在B下的β邊界區(qū)域，NEG(B,Y,β)=U-Bβ(Y)稱為Y在B下的β負(fù)區(qū)域.

從以上的分析容易得到，在決策系統(tǒng)DS=(U,A,d)中分類率隨著β的增大而減小，分類正確率隨β的增大而增大，未分類率隨β的增大而增大.當(dāng)β=H(DS)>0.5時(shí)，β正區(qū)域POS(A,d,β)=U，β邊界區(qū)域和β負(fù)區(qū)域都等于φ.

定義7對(duì)于決策系統(tǒng)DS=(U,A,d)，給定β，稱B?A是條件屬性集A關(guān)于決策屬性d的β約簡(jiǎn)，當(dāng)且僅當(dāng)B滿足下面2個(gè)條件：

1)γ(A,d,β)=γ(B,d,β)；2)任何B的真子集都不滿足條件1).

在決策系統(tǒng)DS=(U,A,d)中，給定參數(shù)β，經(jīng)過(guò)可變精度粗糙集約簡(jiǎn)之后，可能出現(xiàn)決策異常的問(wèn)題[5,16]，從而決策系統(tǒng)中不論是β正區(qū)域部分還是其他部分，都有可能出現(xiàn)不一致的層次增加的現(xiàn)象，這就會(huì)導(dǎo)致分類正確率的下降，此時(shí)的分類正確率的下限是β.

命題6在可變精度粗糙集參數(shù)為β(0.5,1] 的屬性約簡(jiǎn)過(guò)程中，決策系統(tǒng)中在β正區(qū)域、β邊界區(qū)域和β負(fù)區(qū)域中的個(gè)體的不一致層次都隨屬性的減少而單調(diào)增加，從而整個(gè)決策系統(tǒng)的不一致層次隨屬性的減少而單調(diào)增加(證明略).

通過(guò)以上的分析可以得到該3種粗糙集模型下屬性約簡(jiǎn)對(duì)決策表的影響.將該3種粗糙集約簡(jiǎn)前后的分類率、分類正確率、未分類率、不一致的層次變化作一比較，結(jié)果如表1所示.在表1中,()內(nèi)的數(shù)據(jù)或文字表示約簡(jiǎn)后的相應(yīng)指標(biāo)值，()上面的數(shù)值表示約簡(jiǎn)前相應(yīng)指標(biāo)的數(shù)值.

表1 決策表中約簡(jiǎn)前后4種指標(biāo)的比較

從表1可以看出，和其他2種粗糙集相比，Pawlak粗糙集的分類率比較小，未分類率比較大，分類正確率是1，這3個(gè)指標(biāo)在約簡(jiǎn)前后不發(fā)生變化，不一致層次在約簡(jiǎn)后有可能增加；在一般決策下，分類率為1，未分類率為0，但是分類正確率比較小，約簡(jiǎn)前后的4種指標(biāo)都不發(fā)生變化，也就是說(shuō)，一般決策約簡(jiǎn)對(duì)這4個(gè)指標(biāo)不產(chǎn)生影響；在可變精度粗糙集下，約簡(jiǎn)使得分類正確率有所下降，不一致層次有所上升，分類率和未分類率在約簡(jiǎn)前后不變.

表2 決策表DS

6 應(yīng)用舉例

表2是一個(gè)決策表DS=(U,A,d)，其中A={a,b,c}是條件屬性，d為決策屬性.決策表DS的4種指標(biāo)的對(duì)比結(jié)果如表3所示.從表3可以看出，在Pawlak粗糙集下，約簡(jiǎn)前后，分類率、未分類率和分類正確率都不發(fā)生變化，但是不一致的層次在約簡(jiǎn)前后發(fā)生了變化，約簡(jiǎn)后的不一致層次增大了；在一般決策下，約簡(jiǎn)前后4種指標(biāo)都不變；在可變精度粗糙集下，從表3可以看出，約簡(jiǎn)后只有不一致的層次增大了，而分類率、分類正確率以及未分類率都沒(méi)有變化，這是因?yàn)闆Q策表DS在β等于0.8和0.9的情況下都沒(méi)有發(fā)生決策異常的現(xiàn)象，當(dāng)β減小到一定的程度時(shí)，一旦發(fā)生決策異常，決策表的分類正確率在約簡(jiǎn)前后將會(huì)發(fā)生變化，約簡(jiǎn)后的分類正確率小于約簡(jiǎn)前的分類正確率.從表3還可以看出，β越大，分類正確率越大，分類率越小;反之，β越小,分類率越大，分類正確率越小.所以，在進(jìn)行數(shù)據(jù)處理時(shí)要根據(jù)實(shí)際需要選擇適當(dāng)?shù)拇植诩Ｐ?

表3 決策表DS的4種指標(biāo)的比較

7 結(jié) 論

定義了決策系統(tǒng)中的不一致層次的概念，用來(lái)刻畫決策系統(tǒng)的不一致程度.通過(guò)分析3種粗糙集模型在約簡(jiǎn)前后正區(qū)域、負(fù)區(qū)域和邊界區(qū)域的變化，比較了3種粗糙集模型在約簡(jiǎn)前后的分類率、未分類率、分類正確率以及不一致的層次的變化，所得結(jié)果對(duì)實(shí)際應(yīng)用中選擇何種粗糙集理論具有指導(dǎo)意義.

參考文獻(xiàn)：

[1]Pawlak Z.Rough Sets—Theoretical Aspect of Reasoning about Data[M].Dordrecht:Kluwer Academic Publishers,1991.

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

[3]王國(guó)胤.Rough集理論與知識(shí)獲取[M].西安：西安交通大學(xué)出版社，2001.

[4]劉清.Rough集及Rough推理[M].北京：科學(xué)出版社,2001.

[5]王加陽(yáng).面向海量數(shù)據(jù)的粗糙集理論與方法研究[D].長(zhǎng)沙：中南大學(xué)，2005.

[6]王基一，林仁炳.模糊粗糙集粗糙熵的修正[J].浙江師范大學(xué)學(xué)報(bào):自然科學(xué)版，2006，29(4):394-397.

[7]鄧大勇，黃厚寬，李向軍.不一致決策系統(tǒng)中約簡(jiǎn)之間的比較[J].電子學(xué)報(bào),2007,35(2):252-255.

[8]鄧大勇.基于粗糙集的數(shù)據(jù)約簡(jiǎn)及粗糙集擴(kuò)展模型的研究[D].北京：北京交通大學(xué)，2007.

[9]苗奪謙,王國(guó)胤,劉清,等.粒計(jì)算：過(guò)去、現(xiàn)在與展望[M].北京：科學(xué)出版社，2007.

[10]Kryszkiewicz M.Comparative Studies of Alternative Type of Knowledge Reduction in Inconsistent Systems[J].International Journal of Intelligent Systems,2001,16(1):105-120.

[11]Dubois D,Prade H.Rough fuzzy sets and fuzzy rough sets[J].International Journal of General Systems,1990,17(2/3):191-209.

[12]Slezak D,Ziarko W.The investigation of the bayesian rough set model[J].International Journal of Approximate Reasoning,2005,40(1/2):81-91.

[13]Ziarko W.Variable precision rough sets model[J].Journal of Computer and System Sciences,1993,46(1):39-59.

[14]Katzberg J D,Ziarko W.Variable precision extension of rough set[J].Foundamenta Informaticae,1996,27(2/3):155-168.

[15]An A,Shan N,Chan C,et al.Discovering rules for water demand prediction:An enhanced rough-set approach[J].Engineering Application and Artificial Intelligence,1996,9(6):645-653.

[16]Kryszkiewicz M.Maintenance of Reducts in the Variable Precise Rough Sets Model[C]//ICS Research Report.Warsaw:Warsaw University of Technology,1994:31-94.