李 立

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

0 引 言

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

1 基本概念

其中,a+b+c=1.

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

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

2 屬性約簡(jiǎn)

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

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

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

輸出:S的屬性約簡(jiǎn),

yj= φ;

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

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

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

計(jì)算 POSC′(D);

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

yj= yj+{ci};}

while(true)

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

例1 對(duì)于表1所示的不完備決策表S,求其屬性約簡(jiǎn).

表1 不完備決策表S

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

由此得,

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

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

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

3 規(guī)則提取

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

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

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

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

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

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

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

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

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

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

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

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

else{保留屬性 cj;}}}

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

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

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

對(duì)于對(duì)象 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.因此,約簡(jiǎn)后提取出的決策規(guī)則為,

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)結(jié)果

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

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

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

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

表2 實(shí)驗(yàn)結(jié)果

4.2 分 析

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

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

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

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

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

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