魏 玲，張琬林，李 陽

（哈爾濱理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院，哈爾濱 150040）

0 引言

波蘭學(xué)者Pawlak于1982年提出的粗糙集理論是用來剖析不定性及不完整性的有效方法，可以從不完備信息中挖掘隱含知識以及潛在規(guī)律[1]。Pawlak粗糙集作為處理不確定與不精確問題的新方法，近年來迅速應(yīng)用在數(shù)據(jù)挖掘和人工智能等領(lǐng)域，但其存在一定局限性，要求分析的類別一定是全部準(zhǔn)確或肯定，即“包含”或“不包含”，不考慮某種程度上的“包含”或“屬于”[2]。為解決其容錯(cuò)性能差這一缺陷問題，Ziarko于1993年對其進(jìn)行了推廣改進(jìn)，引入容錯(cuò)關(guān)系提出變精度粗糙集模型[3]。在經(jīng)典粗糙集模型基礎(chǔ)上，允許在對集合進(jìn)行劃分時(shí)存在一定的錯(cuò)誤分辨率以提高容錯(cuò)能力，當(dāng)前已有大量研究成果[4-6]。在實(shí)際應(yīng)用中，理想的解決方案只需根據(jù)得到的信息去處理問題，不受預(yù)先給定參數(shù)的限制，且選取不同的參數(shù)會產(chǎn)生不同的決策規(guī)則。為克服這種約束，Slezak等引入貝葉斯理論提出了貝葉斯粗糙集模型[7]。

由于傳統(tǒng)粗糙集的應(yīng)用對象是一般二元等價(jià)關(guān)系的信息系統(tǒng)，不適用自然界中的模糊信息系統(tǒng)，因此部分學(xué)者指出在模糊信息系統(tǒng)中應(yīng)用粗糙集理論，最具有代表性的是Dubois等提出的模糊粗糙集模型[8]，但該模型也易受到噪聲數(shù)據(jù)的干擾。為克服傳統(tǒng)粗糙集的各種不同程度的缺陷，故將變精度粗糙集與模糊粗糙集二者相結(jié)合對學(xué)者來說具有重要研究價(jià)值。主要有以下兩個(gè)研究方面：一是采用模糊理論將變精度粗糙集進(jìn)行一定程度的模糊化。做出杰出貢獻(xiàn)的學(xué)者主要有Mieszkowicz-Rolka[9]等。他在分別定義一種模糊包含集和一種錯(cuò)誤包含度的基礎(chǔ)上，進(jìn)而將上下近似算子生成變精度模糊粗糙集（VPFRS）模型進(jìn)行了重新定義；二是使模糊粗糙集精度化，主要研究學(xué)者有王麗[10]等。

本文研究發(fā)現(xiàn)對這類推廣生成的VPFRS模型中參數(shù)的確定還有待改進(jìn)。因此在VPFRS模型的基礎(chǔ)上，引入先驗(yàn)概率來代替參數(shù)，提出一種基于模糊包含度的貝葉斯粗糙集（IDB-BRS）模型，也可稱其為貝葉斯模糊粗糙集，進(jìn)而研究了模型的基本性質(zhì)和單調(diào)性，并以屬性的相對重要度作為啟發(fā)式信息，給出了基于該模型的屬性約簡算法。最后通過驗(yàn)證以上兩種模型的屬性約簡結(jié)果，證明IDB-BRS屬性約簡是合理有效的。

1 理論基礎(chǔ)

1.1 變精度粗糙集模型

定義1[3]：設(shè)S=(U,A,V,f)是一個(gè)信息系統(tǒng)，U為非空有限論域；A=C?D，C?D=?，C為條件屬性集，D為決策屬性集；V是屬性值的集合；f:U×A→V指研究對象的每一個(gè)屬性值都存在于其所對應(yīng)的相應(yīng)屬性之上。設(shè)X，Y為U的非空子集。如果對于每一個(gè)x∈X都有x∈Y則稱X包含于Y中，記作X?Y。令：為X相對于Y的可信度閥值，稱為X被Y包含的程度大小。

設(shè)(U,R)是近似空間，U為非空有限集合，R為U上對應(yīng)的相關(guān)等價(jià)關(guān)系

1.2 貝葉斯粗糙集模型

在屬性約簡等實(shí)際應(yīng)用中，變精度粗糙集模型中參數(shù)值的選取受決策人主觀因素影響，缺乏合理性依據(jù)。因此有學(xué)者提出貝葉斯粗糙集模型，引入先驗(yàn)概率替代參數(shù)，對獲取的信息進(jìn)行高效處理[7]。

在信息系統(tǒng)S內(nèi)，相對于X?U來說,E是U的相應(yīng)等價(jià)關(guān)系，那么貝葉斯正域、負(fù)域、邊界域分別是：

2 IDB-BRS模型及屬性約簡

2.1 模型構(gòu)建

定義3：設(shè)U是有限非空集合，I=[0,1]，?是任意蘊(yùn)涵，稱映射D:F(U)×F(U)→I為模糊包含度，其中I?A,B∈F(U)。

稱D(A,B)為A關(guān)于B的?模糊包含度。其中?選取為模糊集A的支集。

定義4：IDB-BRS模型：設(shè)U為有限非空論域，其中φ={C1,C2,…,Ck}為U的模糊覆蓋之一，也是U相對于C（ii=1,2,…,k）的劃分，D為模糊包含度，那么將稱作模糊包含近似空間。?X∈F(U)取那么X有關(guān)于E依的下近似以及上近似就是定義于U上的一對模糊子集：

IDB-BRS模型的正域，邊界域和負(fù)域依次定義為：

2.2 模型性質(zhì)

性質(zhì)1：設(shè)?是任意蘊(yùn)涵，Ε=(F(U),φ,D)是模糊包含近似空間，那么在?X∈F(U)中，X相對于Ε依P(X)=的 下 近 似和上近似滿足條件

證明：由定義顯然。

性質(zhì)2：設(shè)?是任意蘊(yùn)涵，且滿足對于?x＞0，有成立為模糊包含近似空間，取且則有成立。

證明：由已知條件可得，?Ci∈φ，x∈S(Ci)，有?(Ci(x),0)=0成立，從而故又由性質(zhì)1可得因此成立。

性質(zhì)3：設(shè)?是任意蘊(yùn)涵，且滿足對于?x∈I，有?(x,1)=1成立，Ε=(F(U),φ,D)為模糊包含近似空間，…,r且則有成立。

性質(zhì)4：設(shè)?是右單調(diào)蘊(yùn)涵，Ε=(F(U),φ,D)是模糊包含近似空間，那么在內(nèi)條件下，A,B對于Ε依的下近似及上近似滿足下列性質(zhì)：

性質(zhì)5：設(shè)?是右單調(diào)蘊(yùn)涵模糊包含近似空間，在條件下，A,B的交與并關(guān)于的下近似和上近似滿足如下性質(zhì)：

性質(zhì)6：設(shè)?是滿足邊界條件的左單調(diào)蘊(yùn)涵，1-P(X)＜P(X)≤a內(nèi)，a關(guān)于Ε依是模糊包含近似空間，在的下近似和上近似有成立。

2.3 屬性約簡算法

屬性約簡為粗糙集理論不可或缺的重要應(yīng)用[11-14]，利用IDB-BRS模型對模糊決策信息系統(tǒng)進(jìn)行相應(yīng)屬性約簡后給出相應(yīng)屬性約簡理論以及相關(guān)算法，并利用相關(guān)實(shí)驗(yàn)數(shù)據(jù)對貝葉斯模糊粗糙集屬性約簡算法合理性與有效性進(jìn)行相關(guān)驗(yàn)證。

定義5：設(shè)S=(U,A,V,f)為模糊決策信息系統(tǒng)，U={x1,x2,…,xn}。模糊屬性集B={b1,b2,…,bm}，B?A,則關(guān)于B的相似度為其中，xi,xj看作是B上的模糊集，xik表示xi在模糊屬性bk下的隸屬度，RB簡稱為B的模糊相似關(guān)系。xi的相似類簡記為，稱為由模糊相似關(guān)系RB或由屬性集B誘導(dǎo)的模糊信息粒。

定義6：設(shè)S=(U,A,V,f)是模糊決策信息系統(tǒng)，其中U={x1,x2,…,xn}，A=C?D，C是條件屬性集，D是決策屬性集，B?C，RB,RD分別是屬性集B,D的模糊相似關(guān)系，那么記其中是U的模糊覆蓋，DF是U上的模糊集包含度，稱Ε=(F(U),φ,D)是 模 糊 包 含 近 似 空 間 ，?X∈F(U)取那么D有關(guān)于B的下近似分布以及上近似分布分別是：

定義7：定義U為非空論域，U={x1,x2,…,xn}，Ε=為模糊包含近似空間,A,B∈F(U)，那么則是模糊集A與B之間的分離度，且 0≤ρ(A,B)≤1。

下面利用分離度定義屬性間相對重要度。

定義8：定義S=(U,A,V,f)是一個(gè)模糊決策信息系統(tǒng)，A=C?D，C是條件屬性集，D是決策屬性集，B?C，ρ則是分離度那么b∈B在B中相對于模糊決策屬性集D的P(X)重要度就為則c∈C在C中相對于D的P(X)重要度為則b∈C-B關(guān)于B相對于D的P(X)重要度為C內(nèi)全部相對于D的ε精度P(X)的必須屬性全體，可以稱作C相對于D的ε精度核，為coreP(X)(C,D,ε)。

定義9：設(shè)S=(U,A,V,f)是一模糊決策信息系統(tǒng)，其中A=C?D，C是條件屬性集，D是決策屬性集，B?C，0≤ε＜1若B滿足：

則稱B是C相對于D的ε精度近似約簡。

屬性約簡為NP問題，所以不可以直接用定義對系統(tǒng)進(jìn)行相應(yīng)屬性約簡。下面利用屬性相對重要度給出IDB-BRS模型的屬性約簡啟發(fā)式算法。

算法：IDB-BRS模型屬性約簡算法

輸入：模糊決策信息系統(tǒng)

S=(U,A=C?D,V,f)，模糊包含度DF，參數(shù)ε；

輸出：S的一個(gè)相對約簡red。

步驟1：隨機(jī)選取c∈C，計(jì)算模糊相似關(guān)系Rc，RD；

步驟2：c→red；

步驟3：for任意ci∈C-red

計(jì)算sigi=sigP2(X)(ci,red,D)；

end

步驟4：選擇屬性cq滿足

步驟5：if屬性cq的重要度sigq＞ε

cq?red→red；

返回步驟3

else

輸出red

End

為增大搜索到最小約簡的概率，步驟1采用隨機(jī)搜索，且在步驟4中，當(dāng)選擇屬性cq時(shí)，若出現(xiàn)一個(gè)以上的屬性滿足時(shí)，也采用隨機(jī)搜索來降低產(chǎn)生局部最優(yōu)解的風(fēng)險(xiǎn)。在IDB-BRS屬性約簡算法中時(shí)間復(fù)雜度主要由步驟3和步驟4共同來決定，步驟3的時(shí)間復(fù)雜度為O(|C||U|2)，步驟4為O(|C|2|U|2)，因此，可知算法總體的時(shí)間復(fù)雜度為O(|C|2|U|2)。

3 實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證IDB-BRS屬性約簡具備合理有效性，將算法約簡后的數(shù)據(jù)結(jié)果與文獻(xiàn)[10]中的VPFRS生成的結(jié)果對比分析，得出結(jié)論。

3.1 實(shí)例分析

表1 模糊決策信息系統(tǒng)

根據(jù)表1，分別利用VPFRS和IDB-BRS得出相應(yīng)屬性約簡結(jié)果。在VPFRS中，對參數(shù)β及ε取不同值得出的相應(yīng)約簡結(jié)果見表2。其中，“/”前面的數(shù)值表示500次循環(huán)后得到的所有約簡中所包含的平均屬性個(gè)數(shù)，“/”后面的數(shù)值表示在進(jìn)行500次循環(huán)后得到最小約簡所包含的屬性個(gè)數(shù)。

在IDB-BRS屬性約簡算法中，沒有參數(shù)的限制影響，約簡結(jié)果只與ε精度的取值有關(guān)，根據(jù)公式，由實(shí)驗(yàn)數(shù)據(jù)可得出為實(shí)現(xiàn)與VPFRS約簡結(jié)果對比的條件統(tǒng)一性，精度ε取相同的變化值，約簡循環(huán)次數(shù)為500次，約簡結(jié)果如表3所示。

表2 約簡結(jié)果

表3 約簡結(jié)果

由實(shí)驗(yàn)數(shù)據(jù)可看出，在IDB-BRS屬性約簡算法中，當(dāng)P(X)=0.71時(shí)，在不同精度下得出屬性個(gè)數(shù)比與在VPFRS屬性約簡算法中β=0.75時(shí)對應(yīng)不同的精度得出的屬性個(gè)數(shù)比結(jié)果相一致。下面比較通過約簡得到的候選解項(xiàng)是否存在相同交集。

設(shè)B?C是由約簡算法得到的C相對于D的ε精度約簡的候選解，則稱為B的質(zhì)量，其中γB(D)為γB(D)對D的支持度。在VPFRS模型約簡結(jié)果中，當(dāng)參數(shù)β=0.75，ε=0.05時(shí)，B1={c1,c2,c3}為模糊信息系統(tǒng)屬性約簡的一個(gè)候選解?？梢郧蟮肂1的D正域?yàn)閷的支持度為0.8795。C的D正域?qū)的支持度為得出B1的質(zhì)量為0.9835。在IDB-BRS模型約簡結(jié)果中，當(dāng)ε=0.05時(shí)，對應(yīng)得到的候選解為同理，根據(jù)公式算出B2的質(zhì)量為經(jīng)過對比，可得出結(jié)論候選解項(xiàng)具有相同交集，說明企業(yè)在進(jìn)行供應(yīng)鏈合作伙伴選擇時(shí)傾向于交貨運(yùn)輸質(zhì)量高且企業(yè)技術(shù)狀況良好的對象。經(jīng)過實(shí)例分析可以證明得到IDB-BRS屬性約簡算法具備相應(yīng)合理性。

3.2 UCI數(shù)據(jù)集測試

為更進(jìn)一步檢驗(yàn)IDB-BRS屬性約簡算法具備一定程度的有效性，選擇3組UCI中常用的數(shù)據(jù)集（Soybean、Credit、Balance）來對本文提出的屬性約簡算法以及文獻(xiàn)[10]中的VPFRS屬性約簡算法進(jìn)行相關(guān)比較分析。Soybean數(shù)據(jù)集包括4個(gè)決策類，35個(gè)屬性個(gè)數(shù)，樣本數(shù)為307；Credit數(shù)據(jù)集包括2個(gè)決策類，15個(gè)屬性個(gè)數(shù)，樣本數(shù)為690；Balance數(shù)據(jù)集包括4個(gè)決策類，4個(gè)屬性個(gè)數(shù)，其中樣本數(shù)為625；在計(jì)算屬性約簡時(shí)，參數(shù)ε在區(qū)間[0.03,0.07]里選取比較合理，否則，過大會引起過度約簡，過小會起不到約簡的作用。因此，實(shí)驗(yàn)測試時(shí)取參數(shù)ε=0.05。由于VPFRS受參數(shù)的影響，為克服經(jīng)驗(yàn)主義，從0.5到1之間等距離選取6組β值來進(jìn)行實(shí)驗(yàn)。本次實(shí)驗(yàn)運(yùn)行的硬件環(huán)境為Intel處理器，3.50GHz，2.00GB內(nèi)存；軟件環(huán)境為Windows7&MATLAB R2012a。

使用IDB-BRS屬性約簡算法（以下簡稱算法1）和文獻(xiàn)[10]VPFRS屬性約簡算法（以下簡稱算法2）分別對3組數(shù)據(jù)集進(jìn)行相應(yīng)屬性約簡，同時(shí)記錄其屬性約簡結(jié)果與約簡運(yùn)行時(shí)間，并將得到的數(shù)據(jù)集作為SVM分類器的輸入，根據(jù)10折交叉驗(yàn)證方法輸出識別結(jié)果。實(shí)驗(yàn)結(jié)果見表4。

表4 兩種約簡算法結(jié)果對比

從表4可以看出：在對數(shù)據(jù)集進(jìn)行約簡時(shí)，算法1得到約簡個(gè)數(shù)在算法2取不同參數(shù)值得到的約簡結(jié)果范圍內(nèi)，說明IDB-BRS模型屬性約簡算法是VPFRS在參數(shù)互不相同條件下所獲得的屬性約簡的一種情況，它具備合理性。在對比分類準(zhǔn)確率時(shí)發(fā)現(xiàn)算法1優(yōu)于算法2，同時(shí)，由于不受參數(shù)的限制，在約簡時(shí)間上也低于算法1的約簡時(shí)間。綜合以上數(shù)據(jù)分析，實(shí)驗(yàn)結(jié)果表明基于IDB-BRS的屬性約簡算法具備合理與有效性，且它相對于變精度模糊粗糙集而言不需要預(yù)先給定參數(shù)，在知識獲取屬性約簡方面有實(shí)際應(yīng)用價(jià)值和意義。

4 結(jié)論

由于考慮到VPFRS模型存在一定約束條件，故根據(jù)貝葉斯粗糙集和變精度粗糙集理論研究，運(yùn)用先驗(yàn)概率替換參數(shù)推導(dǎo)出基于模糊包含度的貝葉斯粗糙集模型，并同時(shí)在模糊決策信息系統(tǒng)進(jìn)行屬性約簡過程中運(yùn)用此模型。經(jīng)過對UCI數(shù)據(jù)集進(jìn)行一系列實(shí)驗(yàn)證明此模型屬性約簡算法合理、有效?；谀：鹊呢惾~斯粗糙集模型是變精度模糊粗糙集模型無參數(shù)化的高級推廣方式之一，在未來實(shí)際應(yīng)用中對其性質(zhì)以及其屬性約簡算法的改進(jìn)還有待進(jìn)一步探究。