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

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

(1.銅陵學院 數學與計算機學院，安徽 銅陵 244000；2.合肥工業大學 管理學院，合肥 230009)

0 引 言

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

1 樂觀多粒度粗糙集

下面先給出相關的概念。

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

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

(3)

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

(4)

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

(5)

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

(6)

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

2 粒度約簡算法

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

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

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

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

(7)

定義3設S=(U,C∪D,V,f)是一個決策表，令A={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 快速等價類劃分算法

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

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

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

算法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;

//計算每個檔位記錄的條數

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

{計算uj屬性值前m個二進制位的值v[uj];

f[v[uj]]++;}

//計算每個檔位的起始地址

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]]++;}

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

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

if(f[r]>=2)

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

//劃分等價類

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

輸出H。

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

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

表1 一個冗余決策表

利用算法1計算表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上。實際上經分析，在粒度約簡的過程中基于整個對象集U進行計算并不是必要的。針對決策表中存在的冗余對象而造成粒度約簡的低效，進一步提高粒度約簡算法的效率，本文對決策表中冗余對象進行了處理，降低了決策表的規模，并由此生成壓縮決策表，并在此基礎上進行粒度約簡。下面給出壓縮決策表的定義和定理1。

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

依據定義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中，等價類劃分的時間復雜度為O(|C||U|)，求U′的時間復雜度為O(|U|)，輸出S′的時間復雜度為O(|U|)，故算法2總的時間復雜度為O(|C||U|)。

根據算法2可求得表1所對應的壓縮決策表，如表2所示。

表2 壓縮決策表

2.4 下近似算法

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

證明根據定義1，定理2顯然成立。

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

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

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

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

L=?;

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

{調用算法1,計算U/Ai;

//[u]Ai循環

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

{if([u]Ai?X)

L=L∪[u]Ai;

if(L==U)

結束循環; }}

輸出L。

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

2.5 粒度重要性

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

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

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

算法4核粒度求解算法。

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

輸出:coreD(A)。

coreD(A)=?;

調用算法3,計算ψ(A,D)

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

{調用算法3, 計算ψ(AAi,D);

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

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

輸出coreD(A)。

證明根據定義1，定理3顯然成立。

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

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

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

(10)

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

2.6 粒度約簡算法

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

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

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

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

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

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

調用算法4,計算核粒度coreD(A);

R=coreD(A);

調用算法3,計算|ψ(R,D)|和|ψ(A,D)|;

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

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

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

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

R=R∪{Ai};

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

輸出R。

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

3 實例分析

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

表3 投資決策信息表

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

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

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

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

4 實驗結果

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

4.1 同一數據集不同?？臻g個數的約簡效果比較

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

表4 UCI數據集

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

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

4.2 相同?？臻g基數不同數據集的約簡效果比較

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

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

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

5 結 論

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