史 琨

(陽(yáng)泉師范高等?？茖W(xué)校 計(jì)算機(jī)系，山西 陽(yáng)泉 045200)

1982年，由Pawlak教授提出的粗糙集理論[1]，是處理不確定的、模糊的和不完備性問(wèn)題的新型數(shù)學(xué)工具，并得到了廣泛的應(yīng)用[2～5].其主要思想是在保持分類能力不變的前提下，通過(guò)知識(shí)約簡(jiǎn)，導(dǎo)出問(wèn)題的決策或分類規(guī)則.粗糙集作為一種有效的知識(shí)發(fā)現(xiàn)工具，已取得了令人矚目的成果，同樣有著很大的發(fā)展空間.

經(jīng)典的粗糙集是以完備信息系統(tǒng)為研究對(duì)象，以等價(jià)關(guān)系為基礎(chǔ)，通過(guò)等價(jià)關(guān)系對(duì)論域分成互不相交的等價(jià)類，劃分越細(xì)，知識(shí)越豐富，信息越充分.然而，在實(shí)際問(wèn)題中，有很多信息系統(tǒng)由于各種原因，信息達(dá)不到精確和確定，這就帶來(lái)了一系列的問(wèn)題，針對(duì)這類問(wèn)題，基于不完備信息系統(tǒng)的決策規(guī)則提取得到了廣泛的關(guān)注.本文通過(guò)基于知識(shí)距離提出的約簡(jiǎn)算法，針對(duì)不完備信息系統(tǒng)，提出了一種決策規(guī)則的提取方法，實(shí)例證明該方法求得的決策規(guī)則較好的解決了數(shù)據(jù)不精確和缺省的問(wèn)題.

1 基本概念

如果對(duì)于至少一個(gè)屬性a∈A，Va包含空值，則稱S是一個(gè)不完備信息系統(tǒng)(Incomplete Information System)，否則它是完備的.這表明完備信息系統(tǒng)是不完備信息系統(tǒng)的一種特例.進(jìn)一步，我們將用*表示空值.

設(shè)P?A，相容關(guān)系可以定義為:

SIM(P)={(u，v)∈U×U|?a∈P，
a(u)=a(v)或a(u)=*或a(v)=*}；

易知

定義3[6]設(shè)S=(U，C∪D)是一個(gè)決策表，Xi∈U/C，Yj∈U/D，desC(Xi)是Xi在C下的唯一描述，desD(Yj)是Yj在D下的唯一描述.決策規(guī)則定義如下:

rij:desC(Xi)→desD(Yj)，Xi∩Yj≠?.

定義4[6]設(shè)有集合A和集合B，A和B的集合貼近度定義為:

其中0≤H(A，B)≤1.

定義5[6]設(shè)S=(U，A)是一個(gè)信息系統(tǒng)，P，Q?A，P和Q所對(duì)應(yīng)的知識(shí)分別為:

U/SIM(P)={SP(x1)，SP(x2)，…，SP(x|U|)}

和

U/SIM(Q)={SQ(x1)，SQ(x2)，…，SQ(x|U|)}.

則知識(shí)U/SIM(P)和知識(shí)U/SIM(Q)的知識(shí)貼近度定義為:

定義6[6]設(shè)有集合A和集合B，A和B的集合差異度可以定義為:

定義7[6]設(shè)S=(U，A)是一個(gè)信息系統(tǒng)，P，Q?A，P和Q所對(duì)應(yīng)的知識(shí)分別為:

U/SIM(P)={SP(x1)，SP(x2)，…，SP(x|U|)}

和

U/SIM(Q)={SQ(x1)，SQ(x2)，…，SQ(x|U|)}.

則知識(shí)U/SIM(P)和知識(shí)U/SIM(Q)的知識(shí)距離定義為:

定義8[6]設(shè)S=(U，A)是一個(gè)信息系統(tǒng)，a∈B?A是一個(gè)屬性，則知識(shí)B中屬性a的重要性定義為:

sigB(a)=D(B，B-{a}).

定義9[6]設(shè)S=(U，A)是一個(gè)信息系統(tǒng)，a∈B?A是一個(gè)屬性，D(B，A)=0，sigB(a)=0，則知識(shí)B中屬性a的不重要程度定義為:

unsigB(a)=D(B，{a}).

2 決策規(guī)則的獲取

屬性約簡(jiǎn)是粗糙集研究的核心內(nèi)容之一，決策規(guī)則獲取的問(wèn)題歸根結(jié)底就是屬性約簡(jiǎn)的問(wèn)題.然而，就不完備信息系統(tǒng)而言，決策規(guī)則獲取的關(guān)鍵則是條件屬性的約簡(jiǎn).

一個(gè)決策算法的約簡(jiǎn)通常包含兩部分，一部分是在整個(gè)算法中去掉所有可省略的條件屬性，另一部分是對(duì)算法中的每一個(gè)規(guī)則進(jìn)行約簡(jiǎn).這兩部分的順序沒(méi)有特別的要求，先進(jìn)行哪部分都行，本文采取先對(duì)條件屬性集約簡(jiǎn)的方法來(lái)獲取決策規(guī)則.

由于借鑒了基于知識(shí)距離的信息系統(tǒng)屬性約簡(jiǎn)算法[6]，其算法描述如下:

輸入:信息系統(tǒng)S=(U，A)；

輸出:S的一個(gè)約簡(jiǎn)C；

Step1:令B=core(A);

Step2:如果D(B，A)==0，使得C=B，結(jié)束算法;否則選擇一個(gè)滿足以下條件的屬性a:

sigB∪{a}(a)=max{sigB∪{a'}(a')|a'∈A-B}，

令B=B∪{a}，轉(zhuǎn)Step2.

針對(duì)不完備信息系統(tǒng)，利用上述算法，對(duì)條件屬性集進(jìn)行約簡(jiǎn)，得到的約簡(jiǎn)結(jié)果與決策屬性構(gòu)成了新的屬性集，以新的屬性集為條件，對(duì)信息系統(tǒng)求決策規(guī)則;再對(duì)所得的決策規(guī)則進(jìn)行相應(yīng)的合并，最后獲得的約簡(jiǎn)結(jié)果即為相對(duì)最優(yōu)的決策規(guī)則.

3 實(shí)例分析

例1 表1是一個(gè)描述小汽車信息的非完備信息系統(tǒng).其中U={x1，x2，x3，x4，x5，x6}，C={c1，c2，c3，c4，c5}，這里c1，c2，c3，c4，c5表示Price，Mileage，Power，Size，Max-Speed，D={c6}，c6表示Quality.

表1 一個(gè)關(guān)于小汽車的不完備信息系統(tǒng)

(1)根據(jù)算法對(duì)條件屬性集C進(jìn)行約簡(jiǎn)，由表1得:

U/SIM(C)={{x1}，{x2，x6}，{x3}，{x4，x5}，{x4，x5，x6}，{x2，x5，x6}}；

U/SIM(C-{c1})={{x1，x2}，{x1，x2，x6}，{x3}，{x4，x5，x6}，{x4，x5，x6}，{x2，x4，x5，x6}}；

U/SIM(C-{c2})={{x1}，{x2，x6}，{x3}，{x4，x5}，{x4，x5，x6}，{x2，x5，x6}}；

U/SIM(C-{c3})={{x1}，{x2，x6}，{x3}，{x4，x5}，{x4，x5，x6}，{x2，x5，x6}}；

U/SIM(C-{c4})={{x1，x3}，{x2，x3，x6}，{x1，x2，x3，x6}，{x4，x5}，{x4，x5，x6}，{x2，x3，x5，x6}}；

U/SIM(C-{c5})={{x1}，{x2，x6}，{x3}，{x4，x5}，{x4，x5，x6}，{x2，x5，x6}}；

sigC(c2)=D(C，C-{c2})=0；

sigC(c3)=D(C，C-{c3})=0；

sigC(c5)=D(C，C-{c5})=0.

求得B=core(C)={c1，c2}，由于D(B，C)≠0，所以計(jì)算

sigB∪{c2}(c2)=0；

使得B=B∪{c3}，此時(shí)D(B，C)==0，算法結(jié)束，求得約簡(jiǎn)為{c1，c3，c4}.

根據(jù)求得的約簡(jiǎn)結(jié)果得到了新的信息系統(tǒng)U'={x，x2，x3，x4，x5，x6}，C'={c1，c3，c3}，D'={c6}.

(2)對(duì)新的信息系統(tǒng)(U'，C'∪D')求決策規(guī)則，可得:

r1:(Price，high)∧{Power，medium}∧(Size，full)→(Quality，good);

r2:(Price，low)∧{Power，medium}∧(Size，full)→(Quality，good);

r3:{Power，medium}∧(Size，compact)→(Quality，poor);

r4:(Price，high)∧{Power，high}∧(Size，full)→(Quality，good);

r5:{Power，high}∧(Size，full)→(Quality，excel);

r6:(Price，low)∧(Size，full)→(Quality，good).

(3)對(duì)求出的6個(gè)決策規(guī)則進(jìn)行合并，可得:

r'1:((Price，high)∧(Power，medium)∧(Size，full))∨((Price，low)∧(Power，medium)∧(Size，full))∨((Price，high)∧(Power，high)∧(Size，full))∨(Price，low)∧(Size，full)→(Quality，good)；

r'2:(Power，medium)∧(Size，compact)→(Quality，poor)；

r'3:(Power，high)∧(Size，full)→(Quality，excel).

以上獲取的三條規(guī)則即為相對(duì)最優(yōu)決策規(guī)則.

4 結(jié)語(yǔ)

本文通過(guò)基于知識(shí)距離提出的約簡(jiǎn)算法，針對(duì)不完備信息系統(tǒng)，提出了一種決策規(guī)則的提取方法，實(shí)例證明該方法求得的決策規(guī)則，能有效地分析和處理含有缺省數(shù)據(jù)和不精確數(shù)據(jù)的信息系統(tǒng)，擴(kuò)展了粗糙集的應(yīng)用領(lǐng)域.

參考文獻(xiàn)：

[1]Z.Pawlak.Rough Sets-Theoretical Aspects of Reasoning about Data[M].Dordrecht，Boston，London:Kluwer Academic Publishers，1991.

[2]何明，傅向華，馬兆豐.基于不完備信息系統(tǒng)的Rough Set決策規(guī)則提取方法[J].計(jì)算機(jī)應(yīng)用，2003，23(11):6-8.

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

[4]J.Y.Liang，Z.Z.Shi，D.Y.Li，M.J.Wierman.Information entropy，rough entropy and knowledge granulation in incomplete information systems[J].International Journal of General Systems，2006，35(6):641-654.

[5]曲開(kāi)社，翟巖慧，梁吉業(yè)，李德玉.形式概念分析對(duì)粗糙集理論的表示及擴(kuò)展[J].軟件學(xué)報(bào)，2007，18(9):2174-2182.

[6]史琨.粗糙集的知識(shí)獲取方法研究[D].太原:山西大學(xué)，2009.