王金山， 王 磊

(解放軍陸軍軍官學(xué)院數(shù)學(xué)教研室，安徽 合肥 230031)

粗糙集理論是一種能夠定量分析處理不精確、不一致、不完整信息與知識(shí)的數(shù)學(xué)工具，由波蘭華沙大學(xué)Pawlak(1982)首先提出，稱為經(jīng)典粗糙集理論。經(jīng)典粗糙集理論研究的對(duì)象必須是完備信息系統(tǒng)，即論域中所有對(duì)象對(duì)應(yīng)的屬性值是已知的。但是在實(shí)際中，由于數(shù)據(jù)獲取困難、容易丟失甚至數(shù)據(jù)本身就不存在等原因造成了數(shù)據(jù)缺失，稱之為空值。這就造成了獲得的信息系統(tǒng)是不完備的，稱之為不完備信息系統(tǒng)。

為了使粗糙集模型能夠處理不完備信息系統(tǒng)，學(xué)者們對(duì)經(jīng)典粗糙集模型中的等價(jià)關(guān)系進(jìn)行弱化，提出了更一般的二元關(guān)系，如容差關(guān)系、相似關(guān)系、限制容差關(guān)系和量化容差關(guān)系等。其中，使用最廣泛的是由Kryszkiewicz(1999)提出的容差關(guān)系，它對(duì)不完備信息系統(tǒng)中對(duì)象間的相似性給出了定義，但對(duì)于相似程度沒(méi)有定量度量而且容差關(guān)系的限制條件過(guò)于寬松，從而易將某些明顯不相似的對(duì)象劃分到同一容差類中。Stefanowski(2001)在容差關(guān)系基礎(chǔ)上提出了量化容差關(guān)系，它利用己知信息的相同程度定量刻畫(huà)樣本對(duì)象間的相似程度，但對(duì)象間的相似程度量化的精確度不高。國(guó)內(nèi)學(xué)者鄧耀進(jìn)等(2009)提出了一種新的量化容差關(guān)系，它利用統(tǒng)計(jì)分布代替概率分布得到了對(duì)象間的容差度，認(rèn)為不同決策屬性值對(duì)應(yīng)的條件屬性值的概率分布是相同的。然而，在一致決策表中，條件屬性集中的屬性取值不同就對(duì)應(yīng)了不同的決策屬性，反過(guò)來(lái)，決策屬性取值也會(huì)對(duì)條件屬性取值產(chǎn)生影響。對(duì)于某一條件屬性而言，不同決策屬性值對(duì)應(yīng)的條件屬性值的概率分布就可能不同，這會(huì)進(jìn)一步影響容差度的計(jì)算結(jié)果。

同時(shí)，不完備信息系統(tǒng)中的空值是一種不確定的信息，也可以理解為噪聲數(shù)據(jù)。空值的存在可能會(huì)對(duì)分類造成一定的影響甚至?xí)斐慑e(cuò)誤分類的產(chǎn)生，因此利用具有一定噪聲數(shù)據(jù)處理和錯(cuò)誤分類容許能力的變精度粗糙集模型(Ziarko，1993)來(lái)處理不完備信息就非常有必要了。

本文在改進(jìn)量化容差關(guān)系基礎(chǔ)上考慮了策屬性值對(duì)條件屬性值概率分布的影響，建立了新的量化容差關(guān)系，在不完備信息表中已知信息充分的情況下，完全利用已知信息統(tǒng)計(jì)得到條件屬性值的概率分布，建立了基于新的量化容差關(guān)系的變精度模型，提出了基于重要度的屬性約簡(jiǎn)算法，最后通過(guò)實(shí)例說(shuō)明了模型建立和計(jì)算的過(guò)程。

1 量化容差關(guān)系

定義1(官禮和，2009) 設(shè)S=(U，A，V，f)為不完備信息系統(tǒng)，對(duì)象集合X?U，屬性集合B?A。設(shè)b∈B的值域?yàn)?，則對(duì)于 ?x∈U，f(x，b)=Vib的概率為1/|Vb|，其中|Vb|表示集合Vb的基數(shù)(此處為Vb中元素的個(gè)數(shù))。

定義2(官禮和，2009) 對(duì)于?x，y∈U，則x，y在屬性集合B上取等值的概率(容差度)為:

其中pb(x，y)表示x，y在屬性b上取等值的概率，其取值定義如下:

學(xué)者鄧耀進(jìn)等(2009)在量化容差關(guān)系的基礎(chǔ)上提出了一種改進(jìn)的量化容差關(guān)系。

定義3(鄧耀進(jìn)等，2009) 設(shè)對(duì)象集合X?U，屬性集合B?A。設(shè)ci∈B，屬性ci的值域?yàn)閂i=其中m=|Vi|。設(shè)tki表示屬性值為的樣本個(gè)數(shù)。

對(duì)于?x，y∈U及?ci∈B，則x，y在屬性集合B上取等值的概率(容差度)為:

其中pi(x，y)表示x，y在屬性ci上取等值的概率，其取值定義如下:

2 一種新的量化容差關(guān)系

新的量化容差關(guān)系的基本原則為:

(1)不完備信息表中已知信息充分，能夠利用已知信息統(tǒng)計(jì)得到條件屬性值的概率分布;

(2)若兩個(gè)對(duì)象某屬性值均為空值且決策屬性值相同，則它們的條件屬性值的概率分布相同，而且條件屬性對(duì)應(yīng)屬性值中，空值等于次數(shù)出現(xiàn)越多的屬性值的可能性越大;

(3)不管屬性值是否為空值，對(duì)象與自身的容差度均為1。

設(shè)不完備信息系統(tǒng) S=(U，A，V，f)，對(duì)象集合X?U，屬性集合B?A。設(shè)ai∈B，屬性ai的值域?yàn)?，其?m=|Vi|。

定義4 對(duì)于?x，y∈U及?ai∈B，則x，y在屬性集合B上取等值的概率(容差度)為:

其中pi(x，y)表示x，y在屬性ai上取等值的概率，其取值定義如下:

其中，P(Bj|Dr)表示當(dāng)對(duì)象關(guān)于屬性ai值為空且決策值為dr時(shí)，關(guān)于屬性ai值為Vji的對(duì)象數(shù)與論域中關(guān)于屬性ai非空且決策值等于dr對(duì)象數(shù)量的比值，即

3 變精度粗糙集模型

定義5 量化容差關(guān)系定義為:

對(duì)象x的量化容差類IVTB(x)定義為:

定義6 設(shè)(U，IVTB)為近似空間，對(duì)于對(duì)象集合X?U，定義X基于改進(jìn)的量化容差關(guān)系IVTB的β下近似集為:

定義X基于IVTB的β上近似集為:

定義X基于IVTB的β邊界域?yàn)?

定義X基于IVTB的β負(fù)域?yàn)?

定義7 設(shè)U/d為決策屬性d的等價(jià)類集合。

決策屬性d與條件屬性集B的β近似依賴性γ(B，d，β)定義為:

記C關(guān)于d的β近似約簡(jiǎn)為RED(C，d，β)，則RED(C，d，β)滿足下面兩個(gè)條件:

(1)γ(C，d，β)= γ(RED(C，d，β)，d，β);

(2)從RED(C，d，β)中去掉任何一個(gè)屬性都將使(1)不成立。

定義8(文志信等，2011) 設(shè)屬性c∈C－B，定義c相對(duì)于B的重要度SIGB(c)為:

SIGB(c)越大，說(shuō)明在條件屬性集C中屬性c相對(duì)于決策屬性d越重要。

定理1(米據(jù)生等，2004) 在條件屬性集C中所有重要度不為0的屬性構(gòu)成C的核CORE(C)。

基于重要度的屬性約簡(jiǎn)算法步驟如下:

(1)計(jì)算核CORE(C):對(duì)于?c∈C，計(jì)算重要度SIGC(c)，所有重要度大于0的屬性構(gòu)成核CORE(C);

(2)令RED(C)←CORE(C);

(3)計(jì)算 γ(C，d，β)及 γ(RED(C)，d，β)并判斷 γ(C，d，β)= γ(RED(C)，d，β)是否成立。若成立，則轉(zhuǎn)(6)，否則轉(zhuǎn)(4);

(4)對(duì)所有c∈C－RED(C)計(jì)算SIGRED(C)(c)并計(jì)算其中最大值，即

(5)令RED(C)←CORE(C)Y{cmax}，轉(zhuǎn)(3);

(6)輸出最小約簡(jiǎn)RED(C)。

4 實(shí)例

某投資公司現(xiàn)有10個(gè)備選投資項(xiàng)目，10個(gè)項(xiàng)目表示為論域X中的對(duì)象:X={x1，x2，…，x10};影響投資決策的屬性有投資成本(a1)、預(yù)期收益(a2)、其他因素(a3)，則條件屬性集 C={a1，a2，a3};決策屬性為d。

其中，投資成本(a1)的屬性值為高、中、低，分別賦值3，2，1;預(yù)期收益(a2)的屬性值為高、中、低，分別賦值3，2，1;其他影響因素(a3)屬性值為大、中、小，分別賦值3，2，1;策屬性d屬性值為不投資、投資，分別賦值0，1。具體數(shù)據(jù)見(jiàn)表1。

表1 投資數(shù)據(jù)表Table1

在表1中，屬性a1，a2和a3對(duì)應(yīng)的空值較少，已知信息充分，能夠利用已知信息統(tǒng)計(jì)得到條件屬性值的概率分布。

對(duì)于屬性a1，假設(shè)有以下事件:

則有

對(duì)于屬性a2，假設(shè)有以下事件:

則有

對(duì)于屬性a3，假設(shè)有以下事件:

則有

根據(jù)以上數(shù)據(jù)可以計(jì)算得到對(duì)象間關(guān)于C，{a1，a2}，{a1，a3}，{a2，a3}等屬性集上的容差度。

下面利用基于重要度的屬性約簡(jiǎn)算法進(jìn)行屬性約簡(jiǎn)。

設(shè) β =0.25，則有:

關(guān)于屬性集 C，{a1，a2}，{a1，a3}及{a2，a3}的容差類集合分別為:

相對(duì)于決策屬性d的β正域分別為:

β近似依賴度為:

進(jìn)一步計(jì)算得到屬性的重要度為:

可知核 CORE(C)={a1，a2}。

因?yàn)棣?C，d，β)= γ({a1，a2}，d，β)=1。所以{a1，a2}就是所求的約簡(jiǎn)。

5 結(jié)束語(yǔ)

本文提出了一種新的量化容差關(guān)系，充分利用了不完備信息表中的已知信息并且考慮了策屬性值對(duì)條件屬性值的概率分布的影響;建立了基于新的量化容差關(guān)系的變精度模型并提出了基于重要度的屬性約簡(jiǎn)算法，使模型具有一定噪聲數(shù)據(jù)處理和錯(cuò)誤分類容許能力;最后通過(guò)實(shí)例說(shuō)明了該模型能夠處理含有空值數(shù)據(jù)的問(wèn)題。

鄧耀進(jìn)，李仁發(fā).2009.一種粗糙集理論中量化容差關(guān)系的改進(jìn)[J].計(jì)算機(jī)工程與科學(xué)，31(10):105-108.

官禮和.2009.基于粗糙集理論的不完備信息處理方法研究[J].重慶郵電大學(xué)學(xué)報(bào)，21(4):461-466.

米據(jù)生，吳偉志，張文修.2004.基于變精度粗糙集理論的知識(shí)約簡(jiǎn)方法[J].系統(tǒng)工程理論與實(shí)踐，24(1):77-82.

文志信，金棟，單潔.2011.基于條件嫡約簡(jiǎn)和粗糙集規(guī)則匹配的反輻射無(wú)人機(jī)作戰(zhàn)目標(biāo)威脅識(shí)別[J].艦船電子工程，31(6):68-72.

Kryszkicwicz M.1999.Rules in incomplete information systems[J].Information Sciences，113(3):271-292.

Pawlak Z.1982.Rough sets[J].International Journal of Computer and Information Sciences，11(5):314-356.

Stefanowski J.2001.Incomplete information tables and rough classifica-tion[J].Computaional Intelligence，17(3):546-564.

Ziarko W.1993.Variable precision rough set model[J].Journal of Computer and System Science，46(1):39-59.