基于壓縮決策表的樂觀多粒度粗糙集粒度約簡算法

王必晴，梁昌勇，齊 平，黃永青

(1.銅陵學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，安徽 銅陵 244000；2.合肥工業(yè)大學(xué) 管理學(xué)院，合肥 230009)

0 引 言

粗糙集理論[1]是一種處理不精確、不一致、不完整信息與知識的數(shù)學(xué)工具，在決策分析、機(jī)器學(xué)習(xí)、知識發(fā)現(xiàn)等領(lǐng)域得到了廣泛且成功的應(yīng)用[2-5]。在此基礎(chǔ)上，從粒計(jì)算的角度出發(fā)，產(chǎn)生了多粒度粗糙集模型[6]，進(jìn)而使得粗糙集理論針對具體問題有了多視角、多層次分析處理的能力。多粒度粗糙集已發(fā)展出樂觀多粒度粗糙集和悲觀多粒度粗糙集2種模型。目前的多粒度粗糙集粒度約簡主要是基于悲觀多粒度粗糙集[7-10]，對決策表的全部對象利用粒度重要性進(jìn)行約簡，采取的是“求同排異”的近似策略，即所有決策者使用共同滿意的方案進(jìn)行決策，存在分歧的方案則不能用于決策。隨著?？臻g的增加，悲觀多粒度粗糙集的近似精度反而越小，因此，該策略在一定程度上略顯保守和苛刻[11]。同時，決策表中存在的冗余數(shù)據(jù)會影響粒度約簡的效率。本文從另一個角度出發(fā)，針對樂觀多粒度粗糙集，利用線性時間排序算法，對冗余的決策表進(jìn)行壓縮，引入分布約簡的概念[12]，提出一種高效的基于壓縮決策表的樂觀多粒度粗糙集粒度約簡算法，提高粒度約簡的效率，采取的是“求同存異”的近似策略，為粒度約簡問題的解決提供一個有效的思路。

1 樂觀多粒度粗糙集

下面先給出相關(guān)的概念。

定義1設(shè)S=(U,AT,V,f)是一個信息系統(tǒng)，令A(yù)={A1,A2,…,Am}為AT的m個屬性子集族，?X?U，則X關(guān)于A1,A2,…,Am的樂觀多粒度粗糙集下近似集、上近似集分別定義為[6]

(2)式中，～X為X的補(bǔ)集。序偶

(3)

稱為X關(guān)于屬性子集A1,A2,…,Am的樂觀多粒度粗糙集。X的樂觀多粒度粗糙集的A邊界域定義為

(4)

X的樂觀多粒度粗糙集的A正域定義為

(5)

X的樂觀多粒度粗糙集的A負(fù)域定義為

(6)

如果只有一個粒度，樂觀多粒度粗糙集就退化成經(jīng)典的Pawlak粗糙集。

2 粒度約簡算法

文獻(xiàn)[12]給出了分布約簡的概念，本文將其應(yīng)用到樂觀多粒度粗糙集，定義樂觀多粒度粗糙集下近似分布粒度約簡。

2.1 樂觀多粒度粗糙集下近似的分布粒度約簡

首先給出樂觀多粒度粗糙集下近似集定義。

定義2設(shè)S=(U,C∪D,V,f)是一個決策表，令A(yù)={A1,A2,…,Am}為C的m個屬性子集族，R?A，U/D={X1,X2,…,Xk}，則U/D關(guān)于R的樂觀多粒度粗糙集下近似集定義為

(7)

定義3設(shè)S=(U,C∪D,V,f)是一個決策表，令A(yù)={A1,A2,…,Am}為C的m個屬性子集族，R?A，若R滿足以下2個條件

ψ(R,D)=ψ(A,D)

(8)

?R′?R,ψ(R,D)?ψ(A,D)

(9)

則稱R為A相對于D的一個樂觀多粒度粗糙集下近似分布粒度約簡。

2.2 快速等價(jià)類劃分算法

在多粒度粗糙集中，下近似的求解是粒度約簡算法中的基本操作，而等價(jià)類劃分又是求下近似的重要步驟；同時，本文后面要介紹的決策表壓縮也要計(jì)算等價(jià)類劃分，因此，提高等價(jià)類劃分的效率是粒度約簡的關(guān)鍵問題。文獻(xiàn)[7]中最壞情況下需要計(jì)算|AT|個劃分的時間復(fù)雜度是O(|AT||U|2)，因此，該文獻(xiàn)計(jì)算下近似集的時間復(fù)雜度也為O(|AT|·|U|2)。實(shí)際上，等價(jià)類劃分的時間復(fù)雜度可進(jìn)一步降低。

求等價(jià)類的一般方法是將對象集U中的個體進(jìn)行兩兩比較，判斷它們的每個屬性取值是否都相同，因而時間復(fù)雜度為O(|C||U|2)[13]。文獻(xiàn)[14]使用了快速排序，使等價(jià)類劃分算法的時間復(fù)雜度降低為O(|C||U|log|U|)。在以上文獻(xiàn)的基礎(chǔ)上，本文給出一個利用檔位快速排序求解U/C的算法，時間復(fù)雜度進(jìn)一步降低為O(|C||U|)，在此基礎(chǔ)上可對決策表進(jìn)行壓縮和下近似求解。

按照屬性集C對U分類，即依次以每個條件屬性ai對U排序。為了進(jìn)一步提高排序速度, 在相關(guān)文獻(xiàn)[15]的基礎(chǔ)上，本文提出利用時間復(fù)雜度僅為O(|U|)的檔位快速排序來進(jìn)行等價(jià)類劃分。檔位快速排序是對快速排序的一種推廣，基本設(shè)計(jì)思想如下[15]。對于每個屬性ai，根據(jù)實(shí)際經(jīng)驗(yàn)按照屬性值前m個二進(jìn)制位的值重新安排所有記錄，將待排序序列分割成若干檔位，使前面檔位的屬性值小于后面檔位的屬性值，然后將記錄條數(shù)大于等于2的檔位中的對象用快速排序法排序。這樣，整個序列被排序。然后依次以剩余屬性對U排序，分析排序后的U，劃分出等價(jià)類。

算法1利用檔位快速排序求解U/C的算法。

輸入:S=(U,C∪D,V,f),U={u1,u2,…,un},C={a1,a2,…,ak};

輸出:U/C。

//依次以每個條件屬性ai(i=1,2,…,k)對U排序

for(i=1;i<=k;i++)

{//f[2m]初始化為0

for(r=0;r<=2m-1;r++)

f[r]=0;

//計(jì)算每個檔位記錄的條數(shù)

for(j=1;j<=n;j++)

{計(jì)算uj屬性值前m個二進(jìn)制位的值v[uj];

f[v[uj]]++;}

//計(jì)算每個檔位的起始地址

a[0]=0;

for(r=1;r<=2m-1;r++)

a[r]=a[r-1]+f[r-1];

//重新放置每條記錄

for(j=1;j<=n;j++)

{S′[a[v[uj]]]=Rj;a[v[uj]]++;}

//將記錄條數(shù)大于等于2的檔位用快速排序法排序

for(r=0;r<=2m-1;r++)

if(f[r]>=2)

將S′[a[r]…a[r]+f[r]-1]中的對象按照ai用快速排序法排序;}

//劃分等價(jià)類

for(j=2;j<=n;j++)

輸出H。

由于上述檔位快速排序循環(huán)次數(shù)為|C|，故算法1中排序總的時間復(fù)雜度為O(|C||U|)，之后的等價(jià)類劃分時間復(fù)雜度也為O(|C||U|)，從而算法1的時間復(fù)雜度為O(|C||U|)。

下面是一個等價(jià)類劃分的例子。表1是一個冗余決策表，由于根據(jù)實(shí)際情況可以確定這些數(shù)據(jù)只需用2位二進(jìn)制表示，故可取m=2。

表1 一個冗余決策表

利用算法1計(jì)算表1的U/{a,b,c}。首先，以屬性a對U排序，U被分為3個檔位{u3}, {u2,u7,u4,u5}和{u1,u6}。接著，將2檔位和3檔位用快速排序法排序。這樣，通過以屬性a排序后，U為{u3,u2,u7,u4,u5,u1,u6}。類似地，我們可以依次以其他條件屬性對U排序。通過以屬性b排序后，U為{u3,u2,u7,u1,u6,u5,u4}。通過以屬性c排序后，U為{u6,u5,u4,u3,u2,u7,u1}。最終，U/{a,b,c}為{{u6}, {u5,u4}, {u3}, {u2,u7}, {u1}}。

2.3 壓縮決策表

在決策表S=(U,C∪D,V,f)中，過去的粒度約簡算法都是建立在整個對象集U上。實(shí)際上經(jīng)分析，在粒度約簡的過程中基于整個對象集U進(jìn)行計(jì)算并不是必要的。針對決策表中存在的冗余對象而造成粒度約簡的低效，進(jìn)一步提高粒度約簡算法的效率，本文對決策表中冗余對象進(jìn)行了處理，降低了決策表的規(guī)模，并由此生成壓縮決策表，并在此基礎(chǔ)上進(jìn)行粒度約簡。下面給出壓縮決策表的定義和定理1。

定理1若R是決策表S′=(U′,C∪D,V′,f′)的一個粒度約簡，則R一定是決策表S=(U,C∪D,V,f)的一個粒度約簡。

依據(jù)定義4和定理1，下面給出壓縮決策表的生成算法。

算法2壓縮決策表生成算法。

輸入:S=(U,C∪D,V,f)；

輸出:S′=(U′,C∪D,V′,f′)。

U′=?;

for(i=1;i<=d;i++)

輸出S′=(U′,C∪D,V′,f′)。

在算法2中，等價(jià)類劃分的時間復(fù)雜度為O(|C||U|)，求U′的時間復(fù)雜度為O(|U|)，輸出S′的時間復(fù)雜度為O(|U|)，故算法2總的時間復(fù)雜度為O(|C||U|)。

根據(jù)算法2可求得表1所對應(yīng)的壓縮決策表，如表2所示。

表2 壓縮決策表

2.4 下近似算法

在多粒度粗糙集計(jì)算中，下近似求解是粒度約簡的關(guān)鍵步驟，因此，如何提高計(jì)算效率是一個重要問題，下面給出定理2，做為下近似計(jì)算算法的理論基礎(chǔ)。

證明根據(jù)定義1，定理2顯然成立。

由定理2，可得以下求下近似集的算法3。

算法3計(jì)算X的樂觀多粒度粗糙集下近似集的算法。

輸入:S=(U,C∪D,V,f)，C的m個屬性子集族A={A1,A2,…,Am}，X?U；

輸出:X關(guān)于A的樂觀多粒度粗糙集下近似集L。

L=?;

for(i=0;i<=m;i++) //Ai循環(huán)

{調(diào)用算法1,計(jì)算U/Ai;

//[u]Ai循環(huán)

for(j=1;j<=[u]Ai的個數(shù);j++)

{if([u]Ai?X)

L=L∪[u]Ai;

if(L==U)

結(jié)束循環(huán); }}

輸出L。

在算法3中，計(jì)算U/Ai的時間復(fù)雜度是O(|C|·|U|)，計(jì)算[u]Ai循環(huán)的時間復(fù)雜度是O(|U|)。因此,在最壞情況下，算法3的時間復(fù)雜度為O(|C|2·|U|)。因?yàn)樵诖髷?shù)據(jù)集的情況下，一般有|C|<<|U|[16]，例如UCI中的mushroom，有8 000多個對象，卻只有22個屬性，所以O(shè)(|C|2|U|)的時間復(fù)雜度優(yōu)于文獻(xiàn)[7]中O(|AT||U|2)的時間復(fù)雜度，提高了計(jì)算下近似集的效率。

2.5 粒度重要性

在粒度約簡中，粒度的重要性可以作為啟發(fā)信息使得被搜索空間以更快的速度減小。所以，下面給出粒度重要性的相關(guān)概念。

定義5設(shè)S=(U,C∪D,V,f)是一個決策表，令A(yù)={A1,A2,…,Am}為C的m個屬性子集族，給定粒度G∈A，如果ψ(AG,D) ?ψ(A,D)，則稱G在A中關(guān)于D是必要的；如果ψ(AG,D)=ψ(A,D)，則稱G在A中關(guān)于D是不必要的。A中所有必要的粒度構(gòu)成的集合稱為A的D核粒度，記為coreD(A)。

記|ψ(A,D)|為ψ(A,D)所含對象的個數(shù)，后同。

算法4核粒度求解算法。

輸入:S=(U,C∪D,V,f)，C的m個屬性子集族A={A1,A2,…,Am}；

輸出:coreD(A)。

coreD(A)=?;

調(diào)用算法3,計(jì)算ψ(A,D)

for(i=1;i<=m;i++)

{調(diào)用算法3, 計(jì)算ψ(AAi,D);

if(|ψ(AAi,D)|<|ψ(A,D)|)

coreD(A)=coreD(A)∪Ai;}

輸出coreD(A)。

證明根據(jù)定義1，定理3顯然成立。

通過定理3可知，對于樂觀多粒度粗糙集，歸入下近似集合的對象數(shù)隨粒空間的增加而單調(diào)增加。這樣，我們可以利用這個變化的趨勢來刻畫粒度的重要性。而且，從算法4和后面的粒度約簡算法可看出，?？臻g個數(shù)的增加還將一步步導(dǎo)致ψ(A,D)、核粒度以至粒度約簡計(jì)算時間的增加。

定義6設(shè)S=(U,C∪D,V,f)是一個決策表，令A(yù)={A1,A2,…,Am}為C的m個屬性子集族，R?A，G∈A-R，則G關(guān)于D的粒度重要性定義為

ess(G,R,D)=|ψ(R∪G,D)|-|ψ(R,D)|

(10)

由以上定義可知，當(dāng)且僅當(dāng)ess(G,R,D)=0時，粒度G關(guān)于D是下近似不重要的。ess(G,R,D)的值越大，說明在已知粒度集A和R的條件下，粒度G對決策D就越重要。本文把ess(G,R,D)作為計(jì)算粒度約簡時的啟發(fā)式信息，減少搜索空間，加快搜索速度。

2.6 粒度約簡算法

依據(jù)上述分析，設(shè)計(jì)出樂觀多粒度粗糙集的下近似粒度約簡算法如下。

算法5樂觀多粒度粗糙集的下近似粒度約簡算法。

輸入:S=(U,C∪D,V,f)，C的m個屬性子集族A={A1,A2,…,Am}；

輸出:決策表S的一個粒度約簡R。

調(diào)用算法2,計(jì)算壓縮決策表S′=(U′,C∪D,V′,f′);

//以下所有計(jì)算都基于壓縮決策表S′

調(diào)用算法4,計(jì)算核粒度coreD(A);

R=coreD(A);

調(diào)用算法3,計(jì)算|ψ(R,D)|和|ψ(A,D)|;

while(|ψ(R,D)| < |ψ(A,D)|)

{for(i=1;i<=|A-R|;i++)

計(jì)算ess(Ai); //Ai∈A-R

選擇具有最大ess(Ai)的Ai;

R=R∪{Ai};

計(jì)算|ψ(R,D)|;}

輸出R。

在算法5中，計(jì)算壓縮決策表的時間復(fù)雜度為O(|C||U|)，計(jì)算核粒度的時間復(fù)雜度為O(|C|3·|U/C||U/D|)，計(jì)算|ψ(R,D)|的時間復(fù)雜度是O(|C|2|U/C||U/D|)，while循環(huán)的時間復(fù)雜度是O(|C|4|U/C||U/D|)。因此，計(jì)算樂觀多粒度粗糙集的下近似粒度約簡的時間復(fù)雜度為O(|C|4·|U/C||U/D|)。由于文獻(xiàn)[7]中給出的粒度約簡算法時間復(fù)雜度為O(|C|3|U|3)，而大數(shù)據(jù)環(huán)境下，一般有|C|<<|U|，故本文算法5的時間復(fù)雜度低于文獻(xiàn)[7]中的算法時間復(fù)雜度，具有較好的粒度約簡效率。

3 實(shí)例分析

為了說明本文提出算法的可行性和有效性，下面通過一個投資決策的實(shí)例來具體分析，在表2所示壓縮決策表的基礎(chǔ)上對其進(jìn)行粒度約簡。假設(shè)表2表示一個投資評估決策，3位專家{a,b,c}對5個投資方案{u1,u2,u3,u4,u6}進(jìn)行評估，每位專家的評估意見互相獨(dú)立，評價(jià)指標(biāo)有3種{0,1,2}，分別表示{差,中,好}，方案的決策結(jié)果為{0,1}，表示{反對,贊成}。將每位專家的評估意見看成一個粒度空間，即粒度集A={a,b,c}，D=j5i0abt0b。在樂觀多粒度空間下考慮哪些專家的評估對于目標(biāo)決策是必要的，哪些是可以忽略的。下面我們利用基于壓縮決策表的樂觀多粒度粗糙集粒度約簡算法對其進(jìn)行粒度約簡。表2對應(yīng)的投資決策信息表如表3所示。

表3 投資決策信息表

1)首先，計(jì)算決策類：U/D={Y1,Y2}={{u1,u4,u6},{u2,u3}}。然后，計(jì)算各個粒度空間：U/a={{u1,u6},{u2,u4},{u3}}，U/b={{u1,u2,u3},{u4,u6}}，U/c={{u1,u2},{u3,u4,u6}}。

2)然后，根據(jù)算法4計(jì)算核粒度：ψ(A,D)={{u1,u4,u6},{u3}}，ψ(Aa,D)={{u4,u6}}，ψ(A,D)={{u1,u6},{u3}}，ψ(Ac,D)={{u1,u4,u6},{u3}}，因?yàn)閨ψ(Aa,D)|<|ψ(A,D)|而且|ψ(A,D)|<|ψ(A,D)|，故coreD(A)={a,b}。

3)最后，根據(jù)算法5計(jì)算粒度約簡：令R=coreD(A)，因?yàn)閨ψ(R,D)|=|ψ(A,D)|=4，所以{a,b}即為粒度約簡。

從以上結(jié)果可以看出, 求得的粒度約簡與原始多粒度空間具有同樣的的決策能力，在各個粒度互相獨(dú)立的情況下，專家a和專家b的評估構(gòu)成最終的粒度約簡，而專家c的評估在決策中可以忽略。從而可以在更簡潔的粒度空間里解決其他相關(guān)問題，為決策分析提供了一個新的理論思考方向。

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

為了驗(yàn)證并且比較算法的時間復(fù)雜度,選用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的6個數(shù)據(jù)集在PC機(jī)上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為Windows 10, Inter Core i7 CPU，8 GByte內(nèi)存。數(shù)據(jù)集的基本信息如表4所示。分別采用文獻(xiàn)[17]中的樂觀多粒度粗糙集粒度約簡算法和本文粒度約簡算法計(jì)算獲得約簡所需要的時間，從而比較算法的效率，對本文算法性能進(jìn)行評估。為了保證粒度約簡的準(zhǔn)確度，各數(shù)據(jù)集的屬性值進(jìn)行了相應(yīng)的預(yù)處理。因?yàn)榱６燃s簡的時間與2個因素有關(guān)，一個是?？臻g個數(shù)，一個是數(shù)據(jù)集所含對象數(shù)，所以采用以下2組實(shí)驗(yàn)分別研究。

4.1 同一數(shù)據(jù)集不同?？臻g個數(shù)的約簡效果比較

數(shù)據(jù)集的?？臻g劃分按以下方法設(shè)計(jì)。對于表5中的同一數(shù)據(jù)集，分別以隨機(jī)選擇的1，2，3個條件屬性組成一個粒空間，將條件屬性集分為若干粒空間。如果條件屬性個數(shù)不能被2或3整除，則剩下的屬性組成一個?？臻g。針對不同的情況，分別進(jìn)行粒度約簡，實(shí)驗(yàn)結(jié)果如圖1所示。其中，算法1和算法2分別表示文獻(xiàn)[17]中的樂觀多粒度粗糙集粒度約簡算法和本文粒度約簡算法。

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

由圖1可知，算法2粒度約簡的運(yùn)行時間少于算法1。而且，隨著?？臻g個數(shù)變多，算法1的約簡時間較快上升，而算法2的約簡時間只是略有增加，這個結(jié)果在Sonar數(shù)據(jù)集上體現(xiàn)得尤其明顯，這是算法2平穩(wěn)性的表現(xiàn)。因此，本文算法在約簡效率和平穩(wěn)性方面相對于算法1都有所提高。

圖1 不同?？臻g個數(shù)的約簡時間比較Fig.1 Time of reduction for different granular space number

4.2 相同?？臻g基數(shù)不同數(shù)據(jù)集的約簡效果比較

?？臻g基數(shù)即每個粒空間所含屬性的個數(shù)。圖2為?？臻g基數(shù)等于2時，不同數(shù)據(jù)集的粒度約簡效果比較。因前3個數(shù)據(jù)集上的約簡時間遠(yuǎn)遠(yuǎn)小于后3個數(shù)據(jù)集，二者不在同一個數(shù)量級，故分成2個子圖顯示。

圖2 不同數(shù)據(jù)集上的約簡時間比較Fig.2 Time of reduction on different data sets

從圖2可以看出，算法2在效率上優(yōu)于其他算法，而且對象數(shù)越多，算法2在效率上的提高就越顯著，驗(yàn)證了算法2較好的性能。

5 結(jié) 論

本文針對樂觀多粒度粗糙集模型，定義了樂觀多粒度粗糙集下近似分布粒度約簡的概念，分析了快速等價(jià)類劃分算法，給出了壓縮決策表和下近似集的計(jì)算方法，討論了作為啟發(fā)式信息的粒度重要性的定義方法，最后提出了基于壓縮決策表的樂觀多粒度粗糙集粒度約簡算法，對比其他算法分析了其計(jì)算的時間復(fù)雜度，并通過實(shí)例驗(yàn)證了該算法的可行性。下一步的研究方向是構(gòu)建基于三支決策的多粒度粗糙集模型，并設(shè)計(jì)其粒度約簡算法。