李 立

(安慶廣播電視大學(xué),安徽安慶 246003)

0 引 言

近年來,將粗糙集理論和粗糙集對分析中的聯(lián)系度相結(jié)合的研究成為了一個熱點[1-3],有學(xué)者在限制容差關(guān)系模型的基礎(chǔ)上,通過引入聯(lián)系度的概念[4],建立了一種基于聯(lián)系度的粗糙集擴展模型[5].本文對該模型做了改進,加入了條件屬性存在重要性差異的因素,以決策屬性對條件屬性的依賴程度作為條件屬性的重要性,定義了不完備決策表中對象間的重要性聯(lián)系度,進而定義了相應(yīng)的重要性聯(lián)系度容差關(guān)系,提出了基于重要性聯(lián)系度的粗糙集擴展模型.同時,在此模型中給出了對不完備決策表進行屬性約簡和規(guī)則提取的算法,并進行了實驗驗證.

1 基本概念

其中,a+b+c=1.

定義2 不完備決策表,S=(U,C∪D,V,f), A?C,給定一個閾值θ,則定義重要性聯(lián)系度容差關(guān)系LWR(A,θ)為,(x,y)∈LWR(A,θ)?(a≥θ,且c=0)或(x=y).

定義3 對象 x的重要性聯(lián)系度容差關(guān)系類,

2 屬性約簡

定義4 不完備決策表,S=(U,C∪D,V,f), C為條件屬性集合,D為決策屬性,設(shè) C′?C,若POSC′(D)=POSC(D),且C′中的任意屬性都是必要的,那么C′稱為基于重要性聯(lián)系度的粗糙集模型在不完備決策表中的屬性約簡.

算法1 基于重要性聯(lián)系度容差關(guān)系的屬性約簡算法如下:

輸入:不完備決策表,S=(U,C∪D,V,f),C為條件屬性集合,D為決策屬性集合.

輸出:S的屬性約簡,

yj= φ;

計算每個條件屬性的重要性以及對應(yīng)的權(quán)值,分別存放在數(shù)組sita和qz中;計算每個對象的重要性聯(lián)系度容差關(guān)系類,存放在數(shù)組 LW中;計算POSC(D);

{令 C′=C-{ci}};

計算C′中各條件屬性重要性對應(yīng)的權(quán)值;計算在集合 C′上,每個對象的重要性聯(lián)系度容差關(guān)系類;

計算 POSC′(D);

若 POSC(D)≠POSC′(D),則:

yj= yj+{ci};}

while(true)

{判斷yj中的每一個屬性cj是否是必要的,若cj不必要,則,

例1 對于表1所示的不完備決策表S,求其屬性約簡.

表1 不完備決策表S

由表 1可計算出:C—θΦ ={a1,a10},C—θΨ = {a6,a8,a11},由此得,POSC(D)={a1,a6,a8,a10, a11}.去掉條件屬性c1,記 C′=C-{c1}={c2,c3, c4},重新計算各條件屬性重要性對應(yīng)的權(quán)值,得, ω2=1/2,ω3=0,ω4=1/2,若取θ=0.6,則各對象的重要性聯(lián)系度容差關(guān)系類為:

由此得,

所以,條件屬性c1是必要的.

同理可計算得,屬性c1、c2和c4是必要的;屬性c3是不必要的.

由此可得,表1表示的不完備決策表S的屬性約簡為{c1,c2,c4}.

3 規(guī)則提取

定義5 不完備決策表,S=(U,C∪D,V,f),其中,A?C,則其每個對象 x的廣義決策函數(shù)為,

定義6 對于對象x,決策規(guī)則關(guān)于條件屬性集的一致程度為,

算法2 基于重要性聯(lián)系度容差關(guān)系的規(guī)則提取算法如下:

輸入:不完備決策表,S=(U,C∪D,V,f),C為條件屬性集合,D為決策屬性集合.

輸出:S的決策規(guī)則.

根據(jù)算法1對不完備決策表進行屬性約簡,得約簡,P={c1,c2,…,cn}.

{計算出μ(x,P)和 ?P(x);Q= P;

{k=Q[j];如果對象i的屬性cj為空值,則:

{在 Q中刪去屬性cj;|Q|--;j--;}

如果對象 i的屬性cj不是空值,則:

{計算μ(x,Q-{cj})和 ?Q-{cj}(i);

{刪去屬性 cj;|Q|--;j--;}

else{保留屬性 cj;}}}

{輸出對象i對應(yīng)的決策規(guī)則:∧(c,v)→

例2 確定對于表1所示的不完備決策表S,提取其屬性約簡后的決策規(guī)則.

由例1可知,表1中不完備決策表的屬性約簡為,{c1,c2,c4},則,Q={c1,c2,c4}.

對于對象 a1,μ(a1,Q)=1,?Q(a1)={Φ}, μ(a1,Q-{c1})=1=μ(a1,Q),?Q-{c1}(a1)= {Φ} = ?Q(a1).所以,Q = {c2,c4},μ(a1,Q -{c2})=2/3,μ(a1,Q-{c4})=1/2.因此,約簡后提取出的決策規(guī)則為,

同理,考察其他的對象可以提取表1所示的不完備決策表中的決策規(guī)則:

4 實驗結(jié)果與分析

4.1 實驗結(jié)果

為了驗證算法1和算法2的正確性和有效性,我們利用Visual C++6.0編寫了程序,并在計算機上實現(xiàn)了這2個算法,同時,采用UCI機器學(xué)習(xí)數(shù)據(jù)庫中的數(shù)據(jù)集進行了測試.

程序運行的界面如圖1所示,輸入對象的個數(shù)、條件屬性的個數(shù)以及設(shè)定的閾值,單擊屬性約簡或者規(guī)則提取的按鈕,則顯示相應(yīng)的結(jié)果.

圖1 屬性約簡和規(guī)則提取程序運行界面

若設(shè)定閾值為0.6,從UCI機器學(xué)習(xí)數(shù)據(jù)庫中選取了4個數(shù)據(jù)集[5],實驗結(jié)果如表2所示.

表2 實驗結(jié)果

4.2 分 析

從表2的實驗結(jié)果來看,基于重要性聯(lián)系度的粗糙集模型在進行規(guī)則提取時,由于考慮了條件屬性重要性的差異,并盡量保留重要性高的屬性,所提取出來的規(guī)則更有實際利用價值.同時,在計算各對象的重要性聯(lián)系度容差關(guān)系類時,可以直接輸入希望的閾值,更符合設(shè)計者的主觀要求.而如何更合理地選取闡值以及如何更合理地評估屬性的重要性則是需要進一步研究的問題.

[1]劉富春.變集對聯(lián)系度的擴充粗糙集模型及其屬性約簡[J].計算機科學(xué),2006,33(3):185-187.

[2]陳蓉素.不完備信息系統(tǒng)中的集對粗糙集模型分析[J].計算機工程與應(yīng)用,2009,45(16):63-65.

[3]陶志,戴慧君,張艷.不完備信息系統(tǒng)中集對粗糙集模型分析[J].計算機應(yīng)用,2008,28(7):1684-1685.

[4]黃兵,周獻中.不完備信息系統(tǒng)中基于聯(lián)系度的粗集模型拓展[J].系統(tǒng)工程理論與實踐,2004,24(1):88-92.

[5]黃兵,李華雄,周獻中.不完備聯(lián)系度粗糙集模型的知識約簡[J].計算機工程,2008,34(11):19-20.