李 立

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

0 引 言

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

1 基本概念

其中,a+b+c=1.

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

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

2 屬性約簡

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

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

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

輸出:S的屬性約簡,

yj= φ;

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

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

計算C′中各條件屬性重要性對應的權值;計算在集合 C′上,每個對象的重要性聯(liá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},重新計算各條件屬性重要性對應的權值,得, ω2=1/2,ω3=0,ω4=1/2,若取θ=0.6,則各對象的重要性聯(liá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ī)則關于條件屬性集的一致程度為,

算法2 基于重要性聯(liá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對應的決策規(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 實驗結果與分析

4.1 實驗結果

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

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

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

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

表2 實驗結果

4.2 分 析

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

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

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

[3]陶志,戴慧君,張艷.不完備信息系統(tǒng)中集對粗糙集模型分析[J].計算機應用,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.