基于偏序關(guān)系的粗糙集規(guī)則提取方法

陳志恩

(寧夏師范學(xué)院數(shù)學(xué)與計算機(jī)科學(xué)系,寧夏固原　756000)

?

基于偏序關(guān)系的粗糙集規(guī)則提取方法

陳志恩

(寧夏師范學(xué)院數(shù)學(xué)與計算機(jī)科學(xué)系,寧夏固原756000)

規(guī)則提取算法中通常先約簡屬性再約簡屬性值，但該算法當(dāng)屬性數(shù)量增多時，會增加約簡的復(fù)雜性，從而影響規(guī)則提取的速度.針對此問題，本文提出了一種基于偏序關(guān)系的粗糙集規(guī)則提取方法.首先,在不同粒度的知識空間上建立偏序關(guān)系;然后,利用各知識空間中隱含的屬性冗余度作為啟發(fā)式信息，對冗余屬性進(jìn)行逐層約簡；最后，在約簡后的屬性集上提取決策規(guī)則.實例表明，該方法降低了屬性約簡的復(fù)雜性，提高了規(guī)則提取的速度.

粗糙集；偏序關(guān)系；屬性約簡；規(guī)則提取

0　引言

粗糙集理論[1-2]的一個主要任務(wù)是從信息表中獲取知識，而這種知識通常用規(guī)則的形式表示出來.用粗糙集方法得到?jīng)Q策規(guī)則的關(guān)鍵在于屬性約簡，相對約簡和最小約簡[2]是屬性約簡的兩個重要結(jié)果.求最小約簡被證明是NP-hard問題[3].相對約簡不一定是最小約簡，且它不一定是唯一的.知識約簡是規(guī)則提取的關(guān)鍵步驟，研究者往往先給出相應(yīng)的啟發(fā)式信息，然后設(shè)計某種啟發(fā)式約簡算法，在知識空間中按照自頂向下或自底向上的方式實現(xiàn)約簡.

從粒計算的角度來看[4-7]，屬性約簡的目的就是在條件屬性集中尋找一個屬性子集，該子集對論域形成的劃分空間是保持正域不變(或條件信息熵不變)前提下粒度最粗的劃分空間.不管哪種屬性約簡方法，其實質(zhì)就是刪除冗余屬性，依照不同的屬性重要度量方法和原理得到不同的約簡結(jié)果，從而得到不同的決策規(guī)則.Dai等[8]以條件屬性子集的分類一致性來度量屬性的重要性,當(dāng)選擇的屬性子集能正確分類時,獲取決策規(guī)則;Qian等[9]在研究可辨識矩陣的基礎(chǔ)上提出了類別特征矩陣的概念,將原始決策表分成若干個等價子決策表,并借助核屬性和屬性頻率函數(shù)對各類別特征矩陣挖掘決策規(guī)則;Zhang等[10]從分析屬性約簡的粒度原理出發(fā),指出傳統(tǒng)的規(guī)則挖掘方法存在的弊端,并提出了一種基于最大粒的規(guī)則獲取算法;Chen等[11]將屬性約簡和屬性值約簡過程合二為一,以知識粒為單位挖掘規(guī)則，先對決策信息系統(tǒng)分層?；?在不同粒度的知識空間下計算粒關(guān)系矩陣,并從中獲取啟發(fā)式信息,然后根據(jù)啟發(fā)式信息確定信息粒的屬性值約簡順序,在此基礎(chǔ)上去除冗余屬性,并設(shè)定終止條件,實現(xiàn)決策規(guī)則的快速挖掘.但上述各屬性約簡方法中，當(dāng)屬性集中屬性數(shù)量增多時,約簡復(fù)雜性會急劇增加.為此，本文提出一種基于偏序關(guān)系的粗糙集規(guī)則提取方法.該方法首先在不同粒度的知識空間上建立偏序關(guān)系，然后將不同粒層知識空間中隱含的屬性冗余程度信息作為啟發(fā)式算子，在不同粒層的偏序關(guān)系集上對冗余屬性進(jìn)行約簡；最后，在約簡后的屬性集上提取決策規(guī)則.實例計算結(jié)果表明,該方法降低了屬性約簡的復(fù)雜性，提高了規(guī)則提取的速度，與傳統(tǒng)方法形成了較好的互補(bǔ).

1　基本概念

如果A=C∪D且C∩D=?，D≠?，C是條件屬性集，D是決策屬性集，則稱該信息系統(tǒng)為決策信息系統(tǒng)，有時也稱為決策表.決策信息系統(tǒng)中的每一行代表一條決策規(guī)則.

定義1[2]決策信息系統(tǒng)S=(U,A,V,f)中，若C′?C,且POSC′(D)=POSC′-{r}(D)，則稱r為C′中相對于決策屬性D可省略的(不必要的),否則，稱r為C′中相對于決策屬性D不可省略的(必要的)，簡稱r為必要屬性.

定義2[2]在決策信息系統(tǒng)S=(U,A,V,f)中，如果C′?C,且C′中的每一個r都是C′中相對于決策屬性D不可省略的，則稱C′為相對于決策屬性D獨(dú)立的，簡稱C′是獨(dú)立的.

定義3[2]在決策信息系統(tǒng)S=(U,A,V,f)中，如果P?C,且對P的獨(dú)立子集S(S?P)，有POSS(D)=POSP(D)，則稱S為P的相對約簡.相對約簡可能不唯一，記P的所有相對約簡簇為REDD(P),P的所有相對約簡中，屬性個數(shù)最少的稱為最小約簡.

定義4[2]設(shè)S=(U,A,V,f)是決策信息系統(tǒng)，對任意的一個屬性集C′?C，稱劃分U/C′為條件劃分空間(或條件粒空間)，稱劃分U/D為決策劃分空間(或決策?？臻g).

定義5[2]設(shè)S=(U,A,V,f)是決策信息系統(tǒng)，A=C∪D，如果U/C?U/D，則稱S為一致決策信息系統(tǒng).

定義6設(shè)S=(U,A,V,f)是決策信息系統(tǒng)，若條件屬性C′和決策屬性D對論域U的劃分為U/C′={X1,…,Xi,…,Xm}，1≤i≤m≤l,U/D={Y1,…,Yj,…,Ys}，1≤j≤s≤l,則稱等價類Xi,Xj為信息粒.記Grad(C′)=U/C′,Grad(D)=U/D,Grad(C′)表示由條件屬性C′產(chǎn)生的信息粒，Grad(D)表示由決策屬性D產(chǎn)生的信息粒.

定義6表明，每個屬性都可形成很多粒子，不同屬性形成的粒子可合成新的粒子.在決策信息系統(tǒng)中,若令1≤ω≤n，則ω表征當(dāng)前系統(tǒng)的粒度,n為條件屬性個數(shù).這樣系統(tǒng)對應(yīng)有n種粒度,并且粒度ω越小,表明系統(tǒng)的知識粒度越粗.

例1設(shè)決策信息系統(tǒng)S=(U,A,V,f)中，U={x1,x2,…,x7}，條件屬性集C={a,b,c,d}，決策屬性集D={e}，如表1所示.

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

首先，計算由決策屬性集D={e}產(chǎn)生的信息粒Ye={{x1,x2},{x3,x4},{x5,x6,x7}}.

其次，取粒度ω=1，則第1層知識空間{ω=1}={{a},,{c},j5i0abt0b}，分別計算該層空間上由單個屬性產(chǎn)生的信息粒如下：

取粒度ω=2，則第2層知識空間{ω=2}={{ab},{ac},{ad},{bc},{bd},{cd}},分別計算該層空間上由兩個屬性合成的信息粒如下：

類似地，可取粒度ω=3及ω=4，分別計算第3層和第4層知識空間上的信息粒.

在決策信息系統(tǒng)S=(U,A,V,f)中，C為條件屬性，則代數(shù)系統(tǒng)P(C),?是由屬性空間構(gòu)成的一個完備格，其中，P(C)表示屬性集合C的冪集.按照格的基本原理,C是格中的最大(極大)元，?是格的最小(極小)元.在格P(C),?對應(yīng)的Hasse圖中，從?到C的一條路徑稱為屬性鏈.

定義7[12](偏序關(guān)系和偏序集)給定非空有限集合X和Y上的一個關(guān)系R，若R滿足自反性、反對稱性和傳遞性，則稱R是X上的一個偏序關(guān)系，簡稱偏序，記為“≤”．同時稱集合X和X上的偏序關(guān)系R組成的序偶(X,R)為偏序集，記作(X,≤)．

定理1設(shè)S=(U,A,V,f)是一信息系統(tǒng)，C′為屬性集C的任意子集,{ω=k}(1≤k≤n)為該信息系統(tǒng)上的第k層知識空間，若符號“?”表示知識空間{{ω=k}∪Grad(C′)}上的包含關(guān)系,則序偶({ω=k}∪Grad(C′),?)構(gòu)成一個偏序集.

定理1根據(jù)定義7容易證明.

定義8設(shè)S=(U,A,V,f)是一信息系統(tǒng)，條件屬性子集C′={a1,a2,…,an0}，n0≤n,序偶({ω=k}∪Grad(C′),?)為一偏序集，任取P∈{ω=k},1≤k≤n0，記

其中P表示由C′中K個屬性復(fù)合而成的屬性，簡稱復(fù)合屬性，XP表示由復(fù)合屬性P產(chǎn)生的信息粒，Xai表示由屬性ai產(chǎn)生的信息粒,XP?Xai表示由屬性P產(chǎn)生的信息粒較由屬性ai產(chǎn)生的信息粒細(xì).

由NEk(ai)的取值可判斷屬性ai在第k層知識空間上是否冗余.

定義9設(shè)S=(U,A,V,f)是一信息系統(tǒng)，條件屬性C0={a1,a2,…,an}，判斷在第k層知識空間是否存在NEk(ai)=1，記

則稱集合Ck為粒度ω=k下的約簡屬性集，其中

性質(zhì)1若存在NE≠0，則在第k層知識空間上有NE個冗余屬性.

從性質(zhì)1可以看出，NE越大，表明粒度ω=k下屬性約簡能力越強(qiáng)，即NE反映了第k層知識空間上屬性的冗余程度，NE也稱屬性冗余度.

性質(zhì)2若存在SNE≠0，則在全知識空間上有SNE個冗余屬性.

從性質(zhì)2可以看出，SNE越大，表明在全知識空間上屬性約簡能力越強(qiáng).

定義9中的NE和SNE是兩個啟發(fā)式算子,本文利用這兩個啟發(fā)式算子對決策信息系統(tǒng)進(jìn)行屬性約簡和規(guī)則挖掘.

2　基于偏序關(guān)系的粗糙集屬性約簡及規(guī)則提取

2.1基本思想

一般地，在一致決策信息系統(tǒng)中，如果在保持正域不變的前提下進(jìn)行屬性約簡，相當(dāng)于在格P(C),?對應(yīng)的Hasse[12]圖中，沿著某條屬性鏈按照自頂向下設(shè)計啟發(fā)式算法，逐漸增加重要屬性，直到得到約簡結(jié)果為止，或是按照自底向上設(shè)計啟發(fā)式算法，逐漸刪除不重要屬性，直到得到約簡結(jié)果為止.但上述屬性約簡方法中，當(dāng)屬性集增大時,約簡復(fù)雜性會急劇增加.例如，在條件屬性集C中含有m個條件屬性的決策信息系統(tǒng)中，從?到C的屬性鏈路有條，從而增加了屬性約簡的難度.為此，本文給出一種基于偏序關(guān)系的粗糙集屬性約簡方法.該方法通過在不同粒度的知識空間上建立偏序關(guān)系，然后,以不同粒層中屬性的冗余程度NE和SNE作為啟發(fā)式算子，對屬性逐層進(jìn)行約簡，直到在各粒層上約去所有的冗余屬性為止，最后，根據(jù)定義3在約簡后的屬性集上提取最簡決策規(guī)則.該方法降低了屬性約簡的復(fù)雜性，提高了規(guī)則提取的速度，與傳統(tǒng)方法形成較好的互補(bǔ).

2.2屬性約簡算法描述

給定一個一致決策信息系統(tǒng)S=(U,A,V,f),A=C0∪D，條件屬性集C0={a1,a2,…,an}，決策屬性集D=j5i0abt0b，屬性約簡算法如下：

輸入：一致決策信息系統(tǒng).

輸出：約簡屬性集(約去冗余屬性后剩余的屬性集).

1)取粒度ω=1，生成知識空間{ω=1}.

2)令k=1.

3)在知識空間{{ω=k}∪Grad(Ck-1)}上建立偏序關(guān)系({ω=k}∪Grad(Ck-1),?),并計算NE,1≤k≤n.

4)取k=k+1，并轉(zhuǎn)入3).

5)輸出Ck并計算SNE,算法結(jié)束.

2.3基于約簡屬性集的規(guī)則提取

算法描述：

輸入：2.2節(jié)中約簡屬性集Ck.

輸出：所有最簡決策規(guī)則集Ruleset.

2)令k=1.

3)取屬性P∈Ck，若信息粒U/P?U/d,則輸出一條規(guī)則P→d，并終止所有包含節(jié)點(diǎn)P的屬性鏈路上決策規(guī)則的搜索，否則轉(zhuǎn)4).

4)取k=k+1，若k≤n-SNE，則轉(zhuǎn)入3)，否則轉(zhuǎn)入5).

5)輸出所有最簡決策規(guī)則,算法結(jié)束.

3　算法實例

為了考察算法的有效性,選擇文獻(xiàn)[13]中已知規(guī)則的決策信息系統(tǒng)進(jìn)行對比分析,一致決策信息系統(tǒng)如表1所示，其中，條件屬性集C={a,b,c,d}，決策屬性集D={e}.

根據(jù)本文提出的算法對表1進(jìn)行屬性約簡及規(guī)則挖掘,步驟如下:

步驟1.根據(jù)定義6計算決策屬性{e}的信息粒:

步驟2.根據(jù)2.2節(jié)給出的算法，在不同粒層的知識空間上進(jìn)行屬性約簡.

取粒度ω=1，則第1層知識空間{ω=1}={{a},,{c},j5i0abt0b}，分別計算單個屬性下的信息粒{Xa,Xb,Xc,Xd}，其中

步驟3.在知識空間{Xa,Xb,Xc,Xd}上建立偏序關(guān)系({ω=1},?)={Xb,Xc}，由偏序集可以看出Xb≤Xc，據(jù)此計算在知識空間{ω=1}上NE=1，從而C1={a,b,d}，即在第1層知識空間中約去了屬性{c}.由于NE≠0且l=3>k+1=2，所以轉(zhuǎn)入步驟4.

步驟4.在屬性集C1上取粒度ω=2，得知識空間{Xab,Xbd,Xad}，在知識空間{{Xab,Xbd,Xad}∪Grad(Ck-1)}上建立偏序關(guān)系并計算得NE=0，表明在第2層知識空間上沒有可約的屬性，則直接轉(zhuǎn)入步驟5.

步驟5.輸出約簡屬性集C2={a,b,d}.

步驟6.在約簡屬性集C2上結(jié)合2.3節(jié)算法進(jìn)行規(guī)則提取.

由例1計算結(jié)果及2.3節(jié)提供的規(guī)則提取算法，可得決策規(guī)則為：

進(jìn)一步簡化，得到簡化規(guī)則：

與文獻(xiàn)[13]的結(jié)果一致.

本例在含有四個條件屬性的決策信息系統(tǒng)上，只需建立兩次偏序集，經(jīng)過一次循環(huán)計算，即可獲得約簡屬性集，從而降低了屬性約簡的復(fù)雜性，提高了規(guī)則提取的速度.

4　結(jié)論

本文首先在不同粒度的知識空間上建立偏序關(guān)系，并以不同知識空間中屬性的冗余程度NE和SNE作為啟發(fā)式算子，對屬性逐步進(jìn)行約簡，直到在各知識空間上約去所有冗余屬性為止；然后在約簡后的屬性集Ck上，沿著格P(Ck),?上相應(yīng)的Hasse圖自下而上提取最簡決策規(guī)則.算法實例表明，該方法降低了屬性約簡的復(fù)雜性，提高了規(guī)則提取的速度，并與傳統(tǒng)的基于屬性約簡方法得到的最簡決策規(guī)則一致.

[1]PAWLAKZ.Roughsets[J].International Journal of Computer and Information Science,1982,11(5):341.

[2]王國英.粗糙集理論與知識發(fā)現(xiàn)[M].西安：西安交通大學(xué)出版社,2001.

[3]WANG S K,ZIARKO W.On optimal decision rules in decision tables[J].BulletinofPolishAcademyofSciences,1985,33(11):693.

[4]MIAO Duo-qian,WANG Guo-yin,LIU Qing,et al.GranularComputing:Past,Present,andFuture[M].Beijing:Science Press,2007:299.

[5]張向榮，譚山，焦李成.基于商空間粒度計算的SAR 圖像分類[J].計算機(jī)學(xué)報,2007,30(3):483.

[6]苗奪謙，范世棟.知識的粒度計算及其應(yīng)用[J].系統(tǒng)工程理論與實踐,2002,22(1):48.

[7]苗奪謙，徐菲菲，姚一豫，等.粒計算的集合論描述[J].計算機(jī)學(xué)報,2012,35(2):351.

[8]DAI Jian-hua,PAN Yun-he.Algorithm for acquisition of decisionrules based on classification consistency rate[J].ControlandDecision,2004,19(10):1086.

[9]QIAN Jin,MENG Xiang-ping,LIU Da-you,et al.A mining algorithmfor concise decision rules based on rough sets theory[J].ControlandDecision,2007,22(12):1368.

[10]ZHANG Qing-hua,WANG Guo-yin,LIU Xian-quan.Rule acquisitionalgorithm based on maximal granule[J].PattermRecognitionandArtificialIntelligence,2012,25(3):388.

[11]CHEN Ze-hua,ZHANG Yu,XIE Gang.Mining algorithm for concise decision rules based on granular computing [J].ControlandDecision,2015,30(1):143.

[12]張文修，姚一豫，梁怡.粗糙集與概念格[M].西安：西安交通大學(xué)出版社，2006.

[13]CHANG Li-yun,WANG Guo-yin,WU Yu.An approach for attribute reduction and rule generation based on rough set theory[J].JournalofSoftware,1999,10(11):1206.

(責(zé)任編輯馬宇鴻)

A method to extraction rules based on the partial relation of rough set

CHEN Zhi-en

(Department of Mathematics and Computer Science，Ningxia Normal College，Guyuan 756000，Ningxia，China)

The traditional methods for rule extraction algorithm are attribute reduction and attribute value reduction.But the increasing of attributes number increased the complexity of reduction,and finally affected the speed of rule extraction.In this study,an extraction method based on partial relation of rough set is proposed.Firstly,a partial order relation is constructed in different knowledge spaces;and then,the redundant attributes are reduced according to redundancy which are implied in different knowledge spaces;finally,the decision rule is extracted from the attribute set of the reduction.Examples showed that the method can reduce the complexity of the attribute reduction and improve the speed of rule extraction.

rough set；partial order relation；attribute reduction；rule extraction

10.16783/j.cnki.nwnuz.2016.05.007

2015-08-25;修改稿收到日期:2015-10-28

寧夏自然科學(xué)科研基金資助項目(NZ14274,NZ14278,NZ15256)；寧夏高校科學(xué)研究基金資助項目(ZD20142221);寧夏師范學(xué)院科研基金項目

陳志恩(1976—)，男，寧夏海原人，副教授，碩士.主要研究方向為粗糙集理論及應(yīng)用研究.

E-mail:czn2002666@sohu.com

TP 18

A

1001-988Ⅹ(2016)05-0027-05