多粒度粗糙集粒度約簡的高效算法

胡善忠，徐 怡,2，何明慧，王 冉

(1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601； 2.計(jì)算智能與信號處理教育部重點(diǎn)實(shí)驗(yàn)室(安徽大學(xué))，合肥 230039)

多粒度粗糙集粒度約簡的高效算法

胡善忠1，徐 怡1,2*，何明慧1，王 冉1

(1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601； 2.計(jì)算智能與信號處理教育部重點(diǎn)實(shí)驗(yàn)室(安徽大學(xué))，合肥 230039)

針對已有多粒度粗糙集粒度約簡算法效率較低的問題，提出一種多粒度粗糙集粒度約簡的高效算法(EAGRMRS)。首先，以決策信息系統(tǒng)為對象，定義決策類下近似布爾矩陣，該矩陣能夠?qū)⒘６燃s簡過程中過多且有重復(fù)的集合運(yùn)算轉(zhuǎn)換為布爾運(yùn)算，基于該矩陣給出計(jì)算決策類下近似算法和計(jì)算粒度重要度算法。然后，針對計(jì)算粒度重要度時存在冗余計(jì)算的問題，提出粒度動態(tài)增加時快速計(jì)算粒度重要度的算法，并在此基礎(chǔ)上，提出EAGRMRS，該算法的時間復(fù)雜度為O(|A|·|U|2+|A|2·|U|)，其中|A|表示粒度集合大小，|U|表示決策信息系統(tǒng)中實(shí)例數(shù)。在UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了所提算法的有效性和高效性，并且隨著數(shù)據(jù)集的增大，EAGRMRS相較于多粒度粗糙集粒度約簡的啟發(fā)式算法(HAGSS)效率優(yōu)勢更加明顯。

多粒度粗糙集；布爾矩陣；信息系統(tǒng); 重要度；粒度約簡

0 引言

粗糙集理論是波蘭數(shù)學(xué)家Pawlak[1]提出的能有效處理不精確、不一致和不完備數(shù)據(jù)的方法，目前，粗糙集理論已廣泛用于機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、特征選擇等領(lǐng)域[2-4]。從粒計(jì)算的角度看，經(jīng)典的粗糙集模型是基于單粒度和單層次的，無法從多粒度、多層次的角度分析和處理問題。為了使粗糙集能夠更好地解決實(shí)際問題，Qian等[5]提出了多粒度粗糙集，在多粒度粗糙集中，目標(biāo)決策可以通過多個粒度空間中的信息粒進(jìn)行刻畫，因此可以從多個角度、多個層次出發(fā)分析問題并獲得更加滿意、合理的求解。此后，許多學(xué)者提出了基于多粒度粗糙集的擴(kuò)展粗糙集模型，例如，多粒度優(yōu)勢關(guān)系粗糙集、多粒度模糊關(guān)系粗糙集、鄰域多粒度粗糙集、多粒度決策理論粗糙集、可變多粒度粗糙集等[6-10]。這些多粒度粗糙集的擴(kuò)展模型對粗糙集理論具有重要的推廣作用。

在多粒度粗糙集中，粒度約簡是一個重要問題，通過粒度約簡能夠在保持信息系統(tǒng)決策能力不變的前提下，選擇一個無冗余的粒度空間子集。為了對多粒度粗糙集進(jìn)行粒度約簡，Qian等[5]首先提出了啟發(fā)式的粒度約簡算法，該算法首先基于整個粒度空間對所有粒度按照粒度重要度大小進(jìn)行排序，然后按序?qū)⒘６燃尤爰s簡集直到獲得一個粒度約簡結(jié)果，但是該算法并沒有給出每步粒度選取時的啟發(fā)式函數(shù)，且在算法的最后并沒有進(jìn)一步對約簡集進(jìn)行冗余粒度的反向消除，獲得的約簡結(jié)果可能存在冗余粒度。張明等[10]提出了可變多粒度粗糙集粒度約簡算法，該算法在獲得一個粒度約簡集之后也沒有進(jìn)一步對約簡集進(jìn)行冗余粒度的反向消除，所以約簡結(jié)果也可能存在冗余粒度。桑妍麗等[11]發(fā)展了一種適合悲觀多粒度粗糙集的粒度約簡算法，雖然該算法效率較高，但并不適用于樂觀多粒度粗糙集。此后，Yang等[12]提出了一種多粒度粗糙集粒度約簡的啟發(fā)式算法，該算法能獲得約簡率較高的約簡結(jié)果，但約簡效率并不高。然而，在實(shí)際應(yīng)用中，面對的往往是數(shù)據(jù)量很大的決策信息系統(tǒng)，此時，如何提高多粒度粗糙集粒度約簡的效率就成為了一個關(guān)鍵問題。

為了提高多粒度粗糙集粒度約簡的效率，本文定義了決策類下近似布爾矩陣，該矩陣能簡化多粒度粗糙集粒度約簡過程中決策類下近似的計(jì)算，基于該矩陣給出了計(jì)算決策類下近似算法和計(jì)算粒度重要度算法，并提出了粒度動態(tài)增加時快速計(jì)算粒度重要度算法來優(yōu)化粒度約簡過程中粒度重要度的計(jì)算。在此基礎(chǔ)上，本文提出了一種多粒度粗糙集粒度約簡的高效算法(Effective Algorithm for Granulation Reduction of Multi-granulation Rough Set, EAGRMRS)，最后通過實(shí)驗(yàn)驗(yàn)證了本文所提算法的有效性和高效性。

1 相關(guān)概念

在本章，介紹本文用到的相關(guān)知識。

定義2[5]設(shè)信息系統(tǒng)IS=(U,AT,V,f)，B?AT，對于X?U，X的下、上近似集合和邊界域定義為：

(1)

(2)

(3)

其中[x]B是x在B上的等價類。

為了能夠從多粒度、多層次的角度分析和處理問題，Qian等[5]提出了多粒度粗糙集。本文中用上標(biāo)O(Optimistic)表示樂觀的語義，用上標(biāo)P(Pessimistic)表示悲觀的語義，以此來區(qū)分樂觀多粒度粗糙集和悲觀多粒度粗糙集。

定義3[5]設(shè)信息系統(tǒng)IS=(U,AT,V,f)，A={A1,A2,…,Am}是AT的m個屬性子集族。對于?X?U，X關(guān)于A的樂觀多粒度下近似和樂觀多粒度上近似分別定義如下：

[x]A2?X∨…∨[x]Am?X,x∈U}

(4)

(5)

定義4[5]設(shè)信息系統(tǒng)IS=(U,AT,V,f)，A={A1,A2,…,Am}是AT的m個屬性子集族。對于?X?U，X關(guān)于A的悲觀多粒度下近似和悲觀多粒度上近似分別定義如下：

[x]Am?X,x∈U}

(6)

(7)

定義5[13]設(shè)決策信息系統(tǒng)DIS=(U,C∪D,V,f)，A={A1,A2,…,Am}是C的m個屬性子集族，決策屬性D導(dǎo)出的劃分為U/D={X1,X2,…,Xr}。用粒度集A表示U/D的近似質(zhì)量(也稱為依賴度)，定義為：

(8)

2 多粒度粗糙集的粒度約簡

目前，為了滿足不同的需要，已經(jīng)有許多不同的約簡定義[14-16]被提出，一個常用的定義是保持決策信息系統(tǒng)的正域不變。

定義6[11]設(shè)決策信息系統(tǒng)DIS=(U,C∪D,V,f)，A={A1,A2,…,Am}是C的m個屬性子集族，決策屬性D導(dǎo)出的劃分為U/D={X1,X2,…,Xr}，則基于A的樂觀下近似分布函數(shù)定義如下：

(9)

定義8[11]設(shè)決策信息系統(tǒng)DIS=(U,C∪D,V,f)，A={A1,A2,…,Am}是C的m個屬性子集族，給定粒度集A′，??A′?A，X∈U/D。

定理1[11]設(shè)決策信息系統(tǒng)DIS=(U,C∪D,V,f)，A={A1,A2,…,Am}是C的m個屬性子集族，A′?A，則：

根據(jù)定義3，該定理顯然成立。由該定理可知，在樂觀多粒度粗糙集中，隨著粒度空間的增大，下近似中對象的個數(shù)增加。在悲觀多粒度粗糙集中，也可以得出類似的結(jié)論，隨著粒度空間的增大，下近似中對象的個數(shù)減少。因此，可以利用下近似中對象個數(shù)的變化來衡量粒度的重要性。

定義9[12]設(shè)決策信息系統(tǒng)DIS=(U,C∪D,V,f)，A={A1,A2,…,Am}是C的m個屬性子集族。

1)A′?A，?Ai∈A′，定義在粒度集A′上，Ai關(guān)于D的粒度重要度為：

Sigin(Ai,A′,D)=abs(γ(A′,D)-γ(A′-Ai,D))

(10)

2)A′?A，?Ai∈A-A′，定義在粒度集A′上，Ai關(guān)于D的粒度重要度為：

Sigout(Ai,A′,D)=abs(γ(Ai∪A′,D)-γ(A′,D))

(11)

其中：abs(N)表示N的絕對值。在粒度約簡的過程中，一般以粒度重要度為啟發(fā)來設(shè)計(jì)粒度約簡算法。

3 多粒度粗糙集粒度約簡的高效算法

3.1 決策類下近似布爾矩陣

粒度約簡中計(jì)算粒度重要度時要多次求不同粒度集合下決策類的下近似，為了將過多且有重復(fù)的集合運(yùn)算轉(zhuǎn)換為布爾運(yùn)算來提高效率，本文定義了決策類下近似布爾矩陣并給出了根據(jù)決策信息系統(tǒng)求決策類下近似布爾矩陣的算法。

該定理顯然成立，對于?x∈U，x僅可能屬于決策類Xk(x∈Xk)的下近似，也就是說x最多屬于一個決策類的下近似。

定義10 設(shè)決策信息系統(tǒng)DIS=(U,C∪D,V,f)，U={x1,x2,…,xn},A={A1,A2,…,Am}是C的m個屬性子集族，決策屬性D導(dǎo)出的劃分為U/D={X1,X2,…,Xr}，定義決策類下近似布爾矩陣為M=(M_m(i,j)),其中M_m(i,j)表示第i行第j列的元素(1≤i≤n,1≤j≤m)，元素定義如下：

(12)

其中xi∈Xk(k∈{1,2,…,r})。

決策類下近似布爾矩陣包含|U|行、|A|列，|U|表示決策信息系統(tǒng)中的實(shí)例數(shù)，|A|表示粒度集合大小。

顯然，決策信息系統(tǒng)的決策類下近似布爾矩陣包含了所有對象在每個粒度上是否屬于對應(yīng)決策類下近似的信息。這樣，求某個決策類在某個粒度集合上的下近似時我們只需要進(jìn)行布爾矩陣元素的0、1判斷，不需要再進(jìn)行集合運(yùn)算。因此，該矩陣可將粒度約簡中的集合運(yùn)算轉(zhuǎn)化為布爾運(yùn)算。以完備決策信息系統(tǒng)為對象，本文給出計(jì)算決策類下近似布爾矩陣的算法。

算法1 計(jì)算決策類下近似布爾矩陣算法。

輸入 決策信息系統(tǒng)DIS=(U,C∪D,V,f)，粒度空間A={A1,A2,…,Am}；

輸出 下近似布爾矩陣M。

1)

設(shè)置M←?，i←1，j←1；

2)

計(jì)算U/D={X1,X2,…,Xr}；

3)

Fori=1 to |U|

Forj=1 tom

If [xi]Aj?Xk

M_m(i,j)=1；

Else

M_m(i,j)=0；

Endif

Endfor

Endfor

4)

輸出M。

該算法的復(fù)雜度為O(|A|·|U|2)，建立了上述決策類下近似布爾矩陣以后，粒度約簡算法中計(jì)算粒度重要度時，可以基于該矩陣快速計(jì)算決策類在任意粒度上的下近似，這個過程只需要簡單地判斷矩陣中元素M_m(i,j)的取值。若M_m(i,j)=0，則對象xi在粒度Aj上不屬于x所在決策類Xk的下近似;若M_m(i,j)=1，則對象xi在粒度Aj上屬于x所在決策類Xk的下近似，避免了過多并且耗時的集合運(yùn)算。

下面以文獻(xiàn)[17]中的決策信息系統(tǒng)為例，說明構(gòu)建決策類下近似布爾矩陣的過程。

例1 給定一個決策信息系統(tǒng)DIS=(U,C∪D,V,f),如表1所示，其中:U={x1,x2,x3,x4,x5,x6}為對象集，A={{a1},{a2},{a3},{a4},{a5},{a6}}為粒度空間。

表1 一個完備決策信息系統(tǒng)Tab. 1 A complete decision information system

首先，根據(jù)決策屬性導(dǎo)出劃分為U/D={{x1,x2,x3},{x4,x5,x6}}，令X1={x1,x2,x3}，X2={x4,x5,x6}。

然后，對于每個對象xi計(jì)算其在每個粒度{aj}上的等價類[x]{aj}并判斷是否包含于對應(yīng)的決策類，若是，設(shè)置矩陣M對應(yīng)的位置M_m(i,j)=1，否則設(shè)置M_m(i,j)=0。對于對象x1，[x1]{a1}={x1,x3,x5,x6}?X1，設(shè)置M_m(1,1)=0；[x1]{a2}={x1,x5}?X1，設(shè)置M_m(1,2)=0；[x1]{a3}={x1,x3,x4,x5}?X1，設(shè)置M_m(1,3)=0；[x1]{a4}={x1,x4,x5,x6}?X1，設(shè)置M_m(1,4)=0；[x1]{a5}={x1,x4,x5,x6}?X1，設(shè)置M_m(1,5)=0；[x1]{a6}={x1,x2,x3}?X1，設(shè)置M_m(1,6)=1。類似，可以計(jì)算出x2，x3，x4，x5，x6在粒度{a1}，{a2}，{a3}，{a4}，{a5}，{a6}上的等價類并判斷是否包含于對應(yīng)的決策類，最終，可以建立如下決策信息系統(tǒng)的決策類下近似布爾矩陣：

接下來以樂觀多粒度粗糙集為例，給出基于決策類下近似布爾矩陣計(jì)算決策類下近似算法和基于決策類下近似布爾矩陣計(jì)算粒度重要度算法。

算法2 基于決策類下近似布爾矩陣計(jì)算決策類下近似算法。

輸入 決策信息系統(tǒng)DIS=(U,C∪D,V,f)，粒度空間A={A1,A2,…,Am}，Xk∈U/D，決策類下近似布爾矩陣M=(M_m(i,j))；

輸出Xk的下近似集合L。

1)

設(shè)置L←?，j←1；

2)

?xi∈Xk，

Forj=1 tom

IfM_m(i,j)=1

L←L∪{xi}，break；

Endif

Endfor

3)

輸出L。

然后利用算法2計(jì)算決策類下近似，根據(jù)定義9易得下面樂觀多粒度粗糙集基于決策類下近似布爾矩陣計(jì)算粒度重要度算法。

算法3 基于決策類下近似布爾矩陣計(jì)算粒度重要度算法。

輸入 決策信息系統(tǒng)DIS=(U,C∪D,V,f)， 粒度空間A={A1,A2,…,Am}，決策屬性D導(dǎo)出的劃分U/D={X1,X2,…,Xr}，決策類下近似布爾矩陣M=(M_m(i,j))，A′?A，?Ai∈A；

輸出 在粒度集A′上，Ai關(guān)于D的粒度重要度SigO。

1)

設(shè)置D′←?，D″←?，k←1；

2)

Fork=1 tor

Endfor

3)

IfAi?A′

A″=A′-Ai；

Else

A″=A′∪Ai；

Fork=1 tor

Endfor

4)

基于D′和D″，根據(jù)定義9計(jì)算SigO；

5)

輸出SigO。

3.2 快速計(jì)算粒度重要度算法

文獻(xiàn)[18]中對粒度動態(tài)變化時如何快速計(jì)算某個對象集的下、上近似進(jìn)行了研究，提出了一個在粒度動態(tài)變化時快速計(jì)算下、上近似的算法。而在粒度約簡算法中，選取當(dāng)前重要度最大的粒度加入約簡集，就涉及粒度動態(tài)增加時計(jì)算決策類的下近似，基于決策類下近似布爾矩陣，參考文獻(xiàn)[18]可以設(shè)計(jì)算法來優(yōu)化計(jì)算粒度重要度過程中決策類下近似的計(jì)算。

定理3[18]設(shè)決策信息系統(tǒng)DIS=(U,C∪D,V,f)，A={A1,A2,…,Am}是C的m個屬性子集族，X?U,有：

(13)

(14)

以樂觀多粒度粗糙集為例，基于決策類下近似布爾矩陣，根據(jù)定理3給出粒度動態(tài)增加時快速計(jì)算決策類下近似算法和粒度動態(tài)增加時快速計(jì)算粒度重要度算法。

算法4 粒度動態(tài)增加時快速計(jì)算決策類下近似算法。

1)

2)

IfM_m(t,i)=1

Endif

3)

基于算法4，得出如下粒度動態(tài)增加時快速計(jì)算粒度重要度的算法。

算法5 粒度動態(tài)增加時快速計(jì)算粒度重要度算法。

輸出 在粒度集A′上，Ai關(guān)于D的粒度重要度SigO。

1)

2)

A″=A′∪Ai；

Fork=1 tor

Endfor

3)

4)

輸出SigO。

悲觀多粒度粗糙集中快速計(jì)算粒度重要度算法類似，在此不再贅述。

3.3 EAGRMRS

粒度約簡算法的基本過程如下：首先獲得一個原始粒度空間下不可除去的粒度集合(粒度約簡核)，然后以這個粒度集為起點(diǎn)，以粒度重要度為啟發(fā)，每次選擇當(dāng)前粒度空間下最為重要的粒度加入到約簡粒度集中，直到其下近似分布與原始粒度空間下近似分布一致。

算法6 多粒度粗糙集粒度約簡的高效算法(EAGRMRS)。

輸入 決策信息系統(tǒng)DIS=(U,C∪D,V,f)，粒度空間A={A1,A2,…,Am}，決策屬性D導(dǎo)出的劃分U/D={X1,X2,…,Xr}；

輸出 粒度約簡集REDO。

1)

設(shè)置REDO←?；

2)

利用算法1建立決策類下近似布爾矩陣M；

3)

對于?Ai∈A，利用算法3計(jì)算Sigin(Ai,A,D)，

IfSigin(Ai,A,D)≠0

REDO=REDO∪Ai；

Endif

令COREO=REDO；

4)

Do

IfSigout(Ak,REDO,D)=max{Sigout(Ai,REDO,D):Ai∈A-REDO}

REDO=REDO∪Ak；

Endif

Untilγ(REDO,D)=γ(A,D)；

5)

?Ai∈REDO-COREO

Ifγ(REDO-Ai,D)=γ(A,D)

REDO=REDO-Ai；

Endif

6)

輸出REDO。

算法復(fù)雜度分析：第2)步時間復(fù)雜度為O(|A|·|U|2)，第3)步時間復(fù)雜度為O(|A|2·|U|)，第4)步時間復(fù)雜度為O(|A|2·|U|)，所以算法6的時間復(fù)雜度為O(|A|·|U|2+|A|2·|U|)。悲觀多粒度粗糙集粒度約簡的高效算法與樂觀多粒度粗糙集粒度約簡的高效算法類似。

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

文獻(xiàn)[12]提出了一種多粒度粗糙集粒度約簡的啟發(fā)式算法(Heuristic Approach to Granular Structure Selection, HAGSS)，其中計(jì)算決策類下近似可以參考文獻(xiàn)[5]。將本文所提算法EAGRMRS與算法HAGSS進(jìn)行比較，比較兩種算法的運(yùn)行效率以及運(yùn)行效率與數(shù)據(jù)集包含的數(shù)據(jù)量的關(guān)系。

選用UCI機(jī)器學(xué)習(xí)庫中的4個數(shù)據(jù)集進(jìn)行測試，數(shù)據(jù)集具體信息見表2，其中：數(shù)據(jù)集Zoo、Chess是完備的，數(shù)據(jù)集Audiology、Mushroom有缺失的屬性值，是不完備的。對于不完備的數(shù)據(jù)集等價關(guān)系將不再適用，本文中用容差關(guān)系來處理不完備的數(shù)據(jù)集[14]。

表2 實(shí)驗(yàn)中使用的UCI數(shù)據(jù)集Tab. 2 UCI datasets used in the experiment

多粒度粗糙集中一個粒度可能包含多個屬性，為了模擬多粒度的情況，對于表2中的數(shù)據(jù)集，從第一個屬性開始，分別以每1、2、3、4、5個屬性構(gòu)成一個粒度，若數(shù)據(jù)集的條件屬性個數(shù)不能被1、2、3、4、5整除，最后余下的屬性構(gòu)成一個粒度，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 不同數(shù)據(jù)集上不同算法粒度約簡的運(yùn)行時間Fig. 1 Running time of granulation reduction for different algorithms on different datasets

粒度大小就是構(gòu)成一個粒度的屬性個數(shù)，對于同一個數(shù)據(jù)集，因?yàn)闂l件屬性一定，所以當(dāng)選取的粒度大小越大，所組成的粒度空間就越小。從圖1中可以看出，在所有數(shù)據(jù)集上，算法EAGRMRS進(jìn)行粒度約簡的運(yùn)行時間均少于算法HAGSS，且隨著粒度大小變小，也就是粒度空間變大時，HAGSS運(yùn)行效率下降較為明顯，而算法EAGRMRS運(yùn)行效率較為穩(wěn)定。所以，本文所提算法在約簡效率和穩(wěn)定性方面都優(yōu)于算法HAGSS。

接下來，為了比較算法EAGRMRS和算法HAGSS的約簡效率與數(shù)據(jù)集包含的數(shù)據(jù)量的關(guān)系，取粒度大小為3時，四個數(shù)據(jù)集的約簡時間如圖2所示。

由表2可知，編號為1、2、3、4的數(shù)據(jù)集包含的數(shù)據(jù)量是遞增的，由圖2可知，隨著數(shù)據(jù)集包含的數(shù)據(jù)量越大，算法HAGSS的運(yùn)行時間增加得較快，而算法EAGRMRS的運(yùn)行時間增加較慢，所以在對數(shù)據(jù)量較大的決策信息系統(tǒng)進(jìn)行粒度約簡時，本文所提算法效率優(yōu)勢將更加明顯。

圖2 不同算法在不同數(shù)據(jù)集上的運(yùn)行時間Fig. 2 Running time of different algorithms on different datasets

5 結(jié)語

本文以決策信息系統(tǒng)為對象，定義了決策信息系統(tǒng)決策類下近似布爾矩陣，該矩陣能簡化多粒度粗糙集粒度約簡過程中決策類下近似的計(jì)算，基于該矩陣給出了計(jì)算決策類下近似算法和計(jì)算粒度重要度算法。此外，針對計(jì)算粒度重要度時存在冗余計(jì)算，基于決策類下近似布爾矩陣提出了粒度動態(tài)增加時快速計(jì)算粒度重要度算法，在此基礎(chǔ)上，提出了一種多粒度粗糙集粒度約簡的高效算法(EAGRMRS)。在UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提算法的有效性和高效性。粒度約簡能夠獲得保持決策信息系統(tǒng)決策能力不變的粒度空間子集，如何在粒度約簡之后對每個粒度中的屬性進(jìn)行進(jìn)一步的約簡，并對約簡后的決策信息系統(tǒng)進(jìn)行規(guī)則提取是接下來要研究的問題。

References)

[1] PAWLAK Z. Rough sets [J]. International Journal of Computer & Information Sciences, 1982, 11(5): 341-356.

[2] HU Q H, CHE X J, ZHANG L, et al. Rank entropy based decision trees for monotonic classification [J]. IEEE Transactions on Knowledge & Data Engineering, 2012, 24(11): 2052-2064.

[3] SRINIVASA K G, VENUGOPAL K R, PATNAIK L M. A soft computing approach for data mining based query processing using rough sets and genetic algorithms [J]. International Journal of Hybrid Intelligent Systems, 2008, 5(1): 1-17.

[4] 白鶴翔,王健,李德玉,等.基于粗糙集的非監(jiān)督快速屬性選擇算法[J].計(jì)算機(jī)應(yīng)用,2015,35(8):2355-2359.(BAI H X, WANG J, LI D Y, et al. Fast unsupervised feature selection algorithm based on rough set theory [J]. Journal of Computer Applications, 2015, 35(8): 2355-2359.)

[5] QIAN Y H, LIANG J Y, YAO Y Y, et al. MGRS: a multi-granulation rough set [J]. Information Sciences, 2010, 180(6): 949-970.

[6] XU W H, SUN W X, ZHANG X Y, et al. Multiple granulation rough set approach to ordered information systems [J]. International Journal of General Systems, 2012, 41(5): 475-501.

[7] YANG X B, SONG X N, DOU H L, et al. Multi-granulation rough set: from crisp to fuzzy case [J]. Annals of Fuzzy Mathematics and Informatics, 2011, 1(1): 55-70.

[8] LIN G P, QIAN Y H, LI J J. NMGRS: Neighborhood-based multigranulation rough sets [J]. International Journal of Approximate Reasoning, 2012, 53(7): 1080-1093.

[9] QIAN Y H , ZHANG H, SANG Y L, et al. Multigranulation decision-theoretic rough sets [J]. International Journal of Approximate Reasoning, 2014, 55(1): 225-237.

[10] 張明,唐振民,徐維艷,等.可變多粒度粗糙集模型[J].模式識別與人工智能,2012,25(4):709-720.(ZHANG M, TANG Z M, XU W Y, et al. Variable multigranulation rough set model [J]. Pattern Recognition and Artificial Intelligence, 2012, 25(4): 709-720.)

[11] 桑妍麗,錢宇華.一種悲觀多粒度粗糙集中的粒度約簡算法[J].模式識別與人工智能,2012,25(3):361-366.(SANG Y L, QIAN Y H. A granular space reduction approach to pessimistic multi-granulation rough sets [J]. Pattern Recognition and Artificial Intelligence, 2012, 25(3): 361-366.)

[12] YANG X B, QI Y S, SONG X N, et al. Test cost sensitive multigranulation rough set: model and minimal cost selection [J]. Information Sciences, 2013, 250(11):184-199.

[13] 張明,程科,楊習(xí)貝,等.基于加權(quán)粒度的多粒度粗糙集[J].控制與決策,2015,30(2):222-228.(ZHANG M, CHENG K, YANG X B, et al. Multigranulation rough set based on weighted granulations [J]. Control and Decision, 2015, 30(2): 222-228.)

[14] DAI J H, WANG W T, TIAN H W, et al. Attribute selection based on a new conditional entropy for incomplete decision systems [J]. Knowledge-Based Systems, 2013, 39(2): 207-213.

[15] MIAO D Q, GAO C, ZHANG N, et al. Diverse reduct subspaces based co-training for partially labeled data [J]. International Journal of Approximate Reasoning, 2011, 52(8): 1103-1117.

[16] QIAN J, MIAO D Q, ZHANG Z H, et al. Hybrid approaches to attribute reduction based on indiscernibility and discernibility relation [J]. International Journal of Approximate Reasoning, 2011, 52(2): 212-230.

[17] 鞠恒榮,周獻(xiàn)中,楊佩,等.測試代價敏感的粗糙集方法[J].系統(tǒng)工程理論與實(shí)踐,2017,37(1):228-240.(JU H R, ZHOU X Z, YANG P, et al. Test-cost-sensitive based rough set approach [J]. System Engineering — Theory and Practice, 2017, 37(1): 228-240.)

[18] YANG X B, QI Y, YU H L, et al. Updating multigranulation rough approximations with increasing of granular structures [J]. Knowledge-Based Systems, 2014, 64(1): 59-69.

This work is partially supported by the National Natural Science Foundation of China (61402005), the Natural Science Foundation of Anhui Province (1308085QF114), the Higher Education Natural Science Foundation of Anhui Province (KJ2013A015), the Open Foundation of Key Laboratory of Intelligent Computing and Signal Processing at Anhui University of Ministry of Education of China.

HUShanzhong, born in 1990, M. S. candidate. His research interests include rough set theory, granular computing, data mining.

XUYi, born in 1981, Ph. D., associate professor. Her research interests include intelligent information processing, granular computing, rough set theory.

HEMinghui, born in 1991, M. S. candidate. His research interests include neural network, rough set theory.

WANGRan, born in 1993, M. S. candidate. His reseach interests include recommender system, rough set theory.

Effectivealgorithmforgranulationreductionofmulti-granulationroughset

HU Shanzhong1, XU Yi1,2*, HE Minghui1, WANG Ran1

(1.CollegeofComputerScienceandTechnology,AnhuiUniversity,HefeiAnhui230601,China;2.KeyLaboratoryofIntelligentComputingandSignalProcessing,MinistryofEducation(AnhuiUniversity),HefeiAnhui230039,China)

Aiming at the low efficiency problem of the existing granulation reduction algorithms for multi-granulation rough set, an Effective Algorithm for Granulation Reduction of Multi-granulation Rough Set (EAGRMRS) was proposed. Firstly, the lower approximation Boolean matrix of decision classes was defined by using the decision information system as the object. The defined matrix could be used for converting redundant and repeated set operations into Boolean operations in the process of granular reduction. Based on this matrix, the algorithm for computing lower approximation of decision classes and the algorithm for computing the important measure of granularity were presented. Then, focusing on the problem of redundancy calculation when computing the important measure of granularity, a fast algorithm for computing the important measure of granularity with dynamic increasing of granularity was presented. On the basis, the EAGRMRS was proposed. The time complexity of the proposed algorithm isO(|A|·|U|2+|A|2·|U|), in which |A| is the size of granulation set, |U| is the number of instances in decision information system. The experimental results on UCI datasets show that, the proposed algorithm is effective and efficient, the efficiency advantage of EAGRMRS is more obvious over Heuristic Approach to Granular Structure Selection (HAGSS) for multi-granulation rough set when the dataset increases.

multi-granulation rough set; boolean matrix; information system; important measure; granulation reduction

2017- 06- 16;

2017- 09- 07。

國家自然科學(xué)基金資助項(xiàng)目(61402005)；安徽省自然科學(xué)基金資助項(xiàng)目(1308085QF114)；安徽省高等學(xué)校省級自然科學(xué)基金資助項(xiàng)目(KJ2013A015)；安徽大學(xué)計(jì)算智能與信號處理教育部重點(diǎn)實(shí)驗(yàn)室課題項(xiàng)目。

胡善忠(1990—)，男，安徽安慶人，碩士研究生，CCF會員，主要研究方向：粗糙集理論、粒計(jì)算、數(shù)據(jù)挖掘； 徐怡(1981—)，女，安徽滁州人，副教授，博士，主要研究方向：智能信息處理、粒計(jì)算、粗糙集理論； 何明慧(1991—)，男，山西晉中人，碩士研究生，主要研究方向：神經(jīng)網(wǎng)絡(luò)、粗糙集理論； 王冉(1993—)，男，安徽合肥人，碩士研究生，主要研究方向：推薦系統(tǒng)、粗糙集理論。

1001- 9081(2017)12- 3391- 06

10.11772/j.issn.1001- 9081.2017.12.3391

(*通信作者電子郵箱xuyi1023@126.com)

TP18

A