何銀川

(汕頭文化藝術(shù)學(xué)校計(jì)算機(jī)技術(shù)系，廣東汕頭 515065)

1 引言

1982 年，Pawlak 首次提出“粗糙集”[1]的概念。之后，隨著粗糙集理論[2]在處理不精確、不完備等數(shù)據(jù)方面的優(yōu)勢(shì)，它逐漸被廣大學(xué)者所熟知。作為粗糙集的核心內(nèi)容，屬性約簡(jiǎn)[3]是逐步從屬性集中刪除不必要屬性來達(dá)到提高數(shù)據(jù)處理效率。目前，許多學(xué)者先后從知識(shí)劃分[4]、貼近度[5]、互信息[6]、粒度[7-8]、等方面提出自己的屬性約簡(jiǎn)改進(jìn)算法?；谖墨I(xiàn)[4]的知識(shí)劃分與文獻(xiàn)[5]的貼近度，本文提出了屬性近似度及相關(guān)屬性約簡(jiǎn)算法。另外，為了提高算法效率，在求解約簡(jiǎn)時(shí)，本文逐步刪除備選非核集屬性集中的不必要屬性，不用重復(fù)計(jì)算不必要屬性的屬性重要度。另外，如果在決策信息系統(tǒng)中動(dòng)態(tài)增加條件屬性，本文還能以原約簡(jiǎn)集為基礎(chǔ)進(jìn)行動(dòng)態(tài)屬性約簡(jiǎn)，降低了數(shù)據(jù)處理工作量。

2 基本概念

定義1[3]]設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，其中：①U為非空對(duì)象集合，又稱論域，且U={x1，x2，…，xn}(n為論域U中對(duì)象個(gè)數(shù))；②C為條件屬性集，D為決策屬性集，且C∩D=，D≠；③V為所有屬性值域，且V={Va|a∈C∪D，Va是a 的值域}；④f：U×C∪D→V，即對(duì)任意的aC∪D，xU，均有f(x，a)Va。

定義2[3]設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，PC，對(duì)任意x、yU，則稱[x]P={y|f(x，P)=f(y，P)}為U上的關(guān)于P的條件等價(jià)類，[x]D={y|f(x，D)=f(y，D)}為U上的關(guān)于D的決策等價(jià)類，U/P={[x]P|xU}為P針對(duì)U的劃分，U/D={[x]D|xU}為D針對(duì)U的劃分。

性質(zhì)1[3]設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，P、QC，對(duì)任意對(duì)象xU，任意屬性aP，則有：

(1)若PQ，則有U/QU/P，且[x]Q[x]P，此時(shí)稱劃分U/Q更精細(xì)，劃分U/P更粗糙。

(2)若P=Q，則有U/P=U/Q，且[x]P=[x]Q，此時(shí)稱P、Q劃分能力相同。

(3)[x]P=∩[x]{a}。

3 屬性近似度

結(jié)合文獻(xiàn)[4，5]，本文先給出等價(jià)類近似度的定義。

定義3 設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，PC，對(duì)任意的xU，定義

則稱s([x]P，[x]D)為對(duì)象x在P條件屬性相對(duì)于決策屬性的近似度，它度量的是[x]P在對(duì)象x下相對(duì)于[x]D的近似程度，其值越大，說明[x]P、[x]D越近似。

性質(zhì)2 設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，PC，對(duì)任意的xU，則有1/|U|≤s([x]P，[x]D)≤1。

證明：對(duì)于任意的xU，則有{x}[x]P∩[x]DU，且[xi]P、[xi]DU，則知1≤|[x]P∩[x]D|≤|U|，且|[x]P|≤|U|，從而1/|U|≤s([x]P，[x]D)≤1。

定義4 設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，PC，定義

則稱S(P，D)為條件屬性集P相對(duì)于決策屬性集D之間的屬性近似度，其值越大，說明條件屬性集P的分類能力越近似于決策屬性集D。

性質(zhì)3 設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，PC，則有1/|U|≤S(P，D)≤1。

證明：由性質(zhì)2 可知1/|U|≤s([x]P，[x]D)≤1，則1≤s（[xi]P，[xi]D）≤|U|，1/|U|≤≤1，即1/|U|≤S(P，D)≤1。

定理1 設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，PC，S(P，D)=1的充分必要條件是對(duì)任意的xiU，有[xi]P[xi]D。

證明：①若S(P，D)=1，則有s([xi]P，[xi]D)=|U|，由性質(zhì)2 可知，對(duì)任意的xiU，有s([xi]P，[xi]D)=1，即，s([xi]P，[xi]D)==1，|[xi]P∩[xi]D|=|[xi]P|，由集合論可知[xi]P[xi]D。

②若對(duì)任意的xiU，有[xi]P[xi]D，則|[xi]P∩[xi]D|=|[xi]P|，s([xi]P，[xi]D)=1，進(jìn)而S(P，D)=1。

定理2 設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，PQC，則有S(P，D)≤S(Q，D)。

證明：若PQC，則由性質(zhì)1(1)可知，對(duì)任意的xiU，有[xi]Q[xi]P，根據(jù)[xi]D、[xi]P、[xi]Q的關(guān)系，下面分三種情況討論：

①若[xi]Q[xi]P[xi]D，對(duì)任意的xiU，有s([xi]P，[xi]D)=，同理可得，s([xi]Q，[xi]D)=，進(jìn)而可得S(P，D)=S(Q，D)；

②若[xi]Q[xi]D[xi]P，對(duì)任意的xiU，有s([xi]P，[xi]D)=≤1，s([xi]Q，[xi]D)==1，進(jìn)而可得S(P，D)≤S(Q，D)；

③若[xi]D[xi]Q[xi]P，對(duì)任意的xiU，有s([xi]P，[xi]D)=，s([xi]Q，[xi]D)=，由于[xi]Q[xi]P，所以|[xi]Q|≤|[xi]P|，1/|[xi]P|≤1/|[xi]Q|，|[xi]D|/|[xi]P|≤|[xi]D|/|[xi]Q|，進(jìn)而可得S(P，D)≤S(Q，D)。

綜合①②③可證得S(P，D)≤S(Q，D)。

定理2說明，隨著P中屬性的不斷增加，P針對(duì)U的劃分越精細(xì)，其相對(duì)于D的屬性近似度越高，分類能力越強(qiáng)。

性質(zhì)4 設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，P、QC，若S(P，D)=S(Q，D)，則對(duì)任意的xU，有[x]P=[x]Q。

定理3 設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，PC，對(duì)任意屬性a、bC-P，若S(P∪{a}，D)=S(P，D)，則S(P∪{a}∪，D)=S(P∪，D)。

定理3說明，對(duì)于屬性集PC，若添加非P屬性a后，若P的屬性近似度沒有發(fā)生變化(即S(P∪{a}，D)=S(P，D))，那么在P∪中添加非P屬性a后，P∪的屬性近似度仍然不會(huì)發(fā)生變化，若在求解約簡(jiǎn)時(shí)，逐步從屬性集中刪除類似屬性，將會(huì)大大減少計(jì)算量。

4 屬性約簡(jiǎn)

4.1 屬性重要度

定義5 設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，對(duì)任意屬性aC，令SigC(a)=S(C，D)-S(C-{a}，D)，則稱SigC(a)為a在C中的屬性重要度。顯然，SigC(a)度量的是從C中刪除屬性a后C相對(duì)于D的屬性近似度變化程度。由于C-{a}C，由定理2 可知S(C-{a}，D)≤S(C，D)，即SigC(a)≥0。SigC(a)值越大，屬性a相對(duì)于C的重要性就越高，SigC(a)值越小，屬性a相對(duì)于C的重要性就越低，特別地，若SigC(a)=0，則稱屬性a相對(duì)于C是不必要的。

性質(zhì)5 設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，對(duì)任意屬性aC，a在C中是必要的充分必要條件是SigC(a)＞0。

性質(zhì)6 核集Core(C)={aC|SigC(a)＞0}。

在使用核集進(jìn)行啟發(fā)式屬性約簡(jiǎn)時(shí)，往往通過某種方法向核集中添加屬性來得到約簡(jiǎn)，所以下面給出屬性重要度的另一種定義。

定義6 設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，PC，對(duì)任意屬性aC-P，令SigP∪{a}(a)=S(P∪{a}，D)-S(P，D)，則稱SigP∪{a}(a)為屬性a相對(duì)于P的屬性重要度。顯然，SigP∪{a}(a)度量的是在屬性集P中增加屬性a后P相對(duì)于D的屬性近似度變化程度。由于PP∪{a}，由定理2 可知S(P，D)≤S(P∪{a}，D)，即SigP∪{a}(a)≥0。

定義7 設(shè)S=(U，C∪D，V，f)為決策信息系統(tǒng)，PC，對(duì)任意的屬性aP在P中是必要的且S(P，D)=S(C，D)，則稱P為C的一個(gè)約簡(jiǎn)。

4.2 基于屬性近似度的屬性約簡(jiǎn)算法

本算法以核集為初始約簡(jiǎn)集，之后依次添加符合要求的非核集屬性來獲得決策信息系統(tǒng)的約簡(jiǎn)。在此期間，為了簡(jiǎn)化算法復(fù)雜度，結(jié)合定理3，在添加非核集屬性時(shí)，若某個(gè)屬性對(duì)于當(dāng)前約簡(jiǎn)集是不必要的，則將從C中直接刪除，避免了對(duì)其屬性重要度的重復(fù)計(jì)算，提高約簡(jiǎn)效率。

步驟1：令Red(S)=，Core(C)=，計(jì)算S(C，D)；步驟2：對(duì)任意屬性aC，計(jì)算屬性重要度SigC(a)，令Core(C)=Core(C)∪{a}(SigC(a)＞0)；步驟3：令Red(S)=Core(C)；步驟4：若S(Red(S)，D)=S(C，D)，則轉(zhuǎn)向步驟6，否則轉(zhuǎn)向步驟5；步驟5：對(duì)任意屬性aC-Red(S)，計(jì)算屬性重要度SigRed(S)∪{a}(a)，如果SigRed(S)∪{a}(a)=0，則令C=C-{a}。之后，將使SigRed(S)∪{a}(a)值最大的屬性(當(dāng)多個(gè)屬性取得最大值時(shí)，任選一個(gè))并入Red(S)中，轉(zhuǎn)向步驟4；步驟6：算法結(jié)束，輸出約簡(jiǎn)Red(S)。

4.3 實(shí)例分析

為了驗(yàn)證本算法的可行性與有效性，本文選取UCI數(shù)據(jù)集中的4 個(gè)決策信息系統(tǒng)Soyb、Zoo、Chess、Mushroom 進(jìn)行實(shí)驗(yàn)對(duì)比，4個(gè)數(shù)據(jù)集的信息如表1所示（其中|U|、|C|分別為數(shù)據(jù)集的對(duì)象數(shù)和條件屬性數(shù)）。本實(shí)驗(yàn)硬件環(huán)境為CPU Intel i32．4GHZ，Win7操作系統(tǒng)，編程工具為VC 6．0。

表1 UCI數(shù)據(jù)集

由于粗糙集只能處理離散化數(shù)據(jù)，所以本文采用等頻區(qū)間法、語義等級(jí)劃分法等方法對(duì)數(shù)據(jù)進(jìn)行離散化。接下來，一方面，運(yùn)用OGSAR算法[9]、ARGDE算法[10]和本文的ADAS算法分別對(duì)這4個(gè)數(shù)據(jù)集進(jìn)行屬性約簡(jiǎn)，得到屬性約簡(jiǎn)結(jié)果如表2所示。

表2 屬性約簡(jiǎn)結(jié)果對(duì)比

其中，|C|、|Red|分別為數(shù)據(jù)集的原條件屬性數(shù)、約簡(jiǎn)集屬性數(shù)。

從表3可知，三種算法的約簡(jiǎn)集基本一致，說明本文算法能正常地計(jì)算出約簡(jiǎn)集，在方法是可行的。

另一方面，為了驗(yàn)證本文算法的有效性，下面從約簡(jiǎn)時(shí)間上進(jìn)行實(shí)驗(yàn)對(duì)比，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 三種算法約簡(jiǎn)時(shí)間對(duì)比

由圖1可知，隨著數(shù)據(jù)集的對(duì)象和屬性個(gè)數(shù)不斷增多，ADAS算法約簡(jiǎn)效率明顯優(yōu)于前2種算法，這是由于在屬性集很大時(shí)存在較多的不必要屬性，而ADAS算法能利用定理3從搜索空間中不斷刪除從備選非核集屬性中刪除不必要屬性，該類屬性不再參與后續(xù)屬性重要度計(jì)算和約簡(jiǎn)工作，降低了數(shù)據(jù)處理工作量，提高了約簡(jiǎn)效率。

5 動(dòng)態(tài)屬性約簡(jiǎn)

針對(duì)決策信息系統(tǒng)中條件屬性集動(dòng)態(tài)變化而引起屬性約簡(jiǎn)的變化，結(jié)合定義7，下面本文將給出基于屬性近似度的動(dòng)態(tài)屬性約簡(jiǎn)算法，該算法不僅無需重新計(jì)算屬性約簡(jiǎn)，還能在約簡(jiǎn)中添加非核屬性時(shí)動(dòng)態(tài)刪除不必要屬性，減少了算法的時(shí)間復(fù)雜度，提高了約簡(jiǎn)效率。

5.1 基于屬性近似度的決策信息系統(tǒng)動(dòng)態(tài)屬性約簡(jiǎn)算法

下面給出該算法的算法描述。

輸入：決策信息系統(tǒng)S=(U，C∪D，V，f)，S的屬性約簡(jiǎn)Red(S)，新增條件屬性集C’，新決策信息系統(tǒng)S’=(U，A∪D，V，f)，其中A=C∪C’。

輸出：動(dòng)態(tài)屬性約簡(jiǎn)Red’(S’)。

步驟1：令Core(C’)=，Red’(S)=Red(S)，計(jì)算S(A，D)；

步驟2：對(duì)任意屬性aC’，依次計(jì)算屬性重要度SigA(a)，令Core(C’)=Core(C’)∪{a}(SigA(a)＞0)；

步驟3：令Red’(S’)=Red(S)∪Core(C’)；

步驟4：若S(Red’(S’)，D)=S(A，D)，則轉(zhuǎn)向步驟6，否則轉(zhuǎn)向步驟5；

步驟5：對(duì)任意屬性aA-Red’(S’)，計(jì)算屬性重要度SigRed′(S′)∪{a}(a)，如果SigRed′(S′)∪{a}(a)=0，則令A(yù)=A-{a}。之后，將使SigRed′(S′)∪{a}(a)值最大的屬性(當(dāng)多個(gè)屬性取得最大值時(shí)，任選一個(gè))并入Red’(S’)中，轉(zhuǎn)向步驟4；

步驟6：對(duì)任意屬性aRed’(S’)，若S(Red’(S’)-{a}，D)=S(Red’(S’)，D)，則屬性a為新約簡(jiǎn)集不必要屬性，令Red’(S’)=Red’(S’)-{a}，轉(zhuǎn)向步驟7；

步驟7：算法結(jié)束，輸出約簡(jiǎn)Red’(S’)。

其中，步驟2是用來計(jì)算新增條件屬性集C’中是否有核屬性，步驟6用來剔除新約簡(jiǎn)集中的不必要屬性。

算法復(fù)雜度分析：對(duì)于步驟1，計(jì)算S(A，D)的時(shí)間復(fù)雜度為O((|A|+|D|)|U|)(|A|、|D|為新條件屬性與決策屬性個(gè)數(shù))；對(duì)于步驟2，由于要對(duì)C’中每個(gè)屬性a，計(jì)算屬性重要度SigA(a)，共計(jì)|C’|次，此步驟的時(shí)間復(fù)雜度為O((|C’|+|D|)|U|)；對(duì)于步驟4，計(jì)算S(Red’(S’)，D)的時(shí)間復(fù)雜度為O(|Red’(S’)|+|D|)|U|)；步驟5 最壞情況下需要計(jì)算|A|(|A|+1)/2 次SigRed′(S′)∪{a}(a)，所以步驟5 的時(shí)間復(fù)雜度為O((|A|(|A|+1)/2+|D|)|U|)。由于決策屬性集的屬性個(gè)數(shù)一般為1，所以可知本算法的復(fù)雜度為O(|A|2|U|)，這與文獻(xiàn)[10]的時(shí)間復(fù)雜度O(|C|2|U|)是一致的，并且比文獻(xiàn)[9]的時(shí)間復(fù)雜度O(|C||U|2)要低。

5.2 實(shí)例分析

接下來，本文選取UCI數(shù)據(jù)集中的Chess、Mushroom數(shù)據(jù)集（如表1所示）進(jìn)行實(shí)驗(yàn)對(duì)比，本實(shí)驗(yàn)環(huán)境與4．3節(jié)一致。在本節(jié)實(shí)驗(yàn)中，選擇本文4．3 節(jié)提出的ADAS 算法（非動(dòng)態(tài)算法）和DADAS 算法（動(dòng)態(tài)算法）。實(shí)驗(yàn)中，本節(jié)將數(shù)據(jù)集的60%條件屬性作為初始數(shù)據(jù)集，之后依次以10%的條件屬性個(gè)數(shù)作為增量條件模擬4次屬性動(dòng)態(tài)變化過程，可得約簡(jiǎn)時(shí)間如圖2、3所示。

由圖2、3 可知，DADAS 算法（動(dòng)態(tài)算法）所用時(shí)間遠(yuǎn)遠(yuǎn)小于ADAS算法（非動(dòng)態(tài)算法），并且隨著增加屬性量增多用時(shí)趨勢(shì)越明顯。這主要由于ADAS 算法（非動(dòng)態(tài)算法）在每次數(shù)據(jù)動(dòng)態(tài)更新后需要重新計(jì)算新數(shù)據(jù)集的屬性約簡(jiǎn)，隨著對(duì)象個(gè)數(shù)增多用時(shí)會(huì)越來越大，而DADAS算法（動(dòng)態(tài)算法）在求解屬性約簡(jiǎn)時(shí)，每次是以上次約簡(jiǎn)集為基礎(chǔ)進(jìn)行求解新約簡(jiǎn)集，僅需處理新增數(shù)據(jù)，減少約簡(jiǎn)工作量，節(jié)省了大量存儲(chǔ)空間，而且還能對(duì)約簡(jiǎn)集進(jìn)行精簡(jiǎn)，剔除約簡(jiǎn)集中不必要屬性。所以，在不同數(shù)據(jù)集實(shí)驗(yàn)對(duì)比中，動(dòng)態(tài)屬性約簡(jiǎn)算法性能要優(yōu)于非動(dòng)態(tài)屬性約簡(jiǎn)算法。

圖2 Chess數(shù)據(jù)集實(shí)驗(yàn)對(duì)比

圖3 Mushroom數(shù)據(jù)集實(shí)驗(yàn)對(duì)比

6 結(jié)束語

隨著粗糙集在許多領(lǐng)域內(nèi)的成功應(yīng)用，關(guān)于粗糙集的研究成果層出不窮。屬性約簡(jiǎn)作為粗糙集理論的核心內(nèi)容之一，旨在尋找不影響整體分類能力的最小屬性集。在等價(jià)類近似的基礎(chǔ)上，本文提出了屬性近似度，用以從整個(gè)論域角度反映條件屬性集與決策屬性集的近似程度。為了更好地度量屬性的重要性，本文先后提出了兩種方法用以度量屬性集P中的屬性及非P屬性關(guān)于P的屬性重要度，并先后給出了兩種基于屬性近似度的決策信息系統(tǒng)屬性約簡(jiǎn)算法。最后，通過實(shí)例驗(yàn)證了算法的有效性，為決策信息系統(tǒng)的知識(shí)發(fā)現(xiàn)提供了新的研究思路。