鄭文彬 ,李進(jìn)金 ,張燕蘭 ,廖淑嬌

（1.閩南師范大學(xué)計(jì)算機(jī)學(xué)院，漳州，363000；2.閩南師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，漳州，363000；3.福建省粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室，閩南師范大學(xué)，漳州，363000）

Qian et al［1］于2012 年提出多粒度粗糙集，在多粒度粗糙集中，目標(biāo)決策可以通過多個(gè)粒度產(chǎn)生的信息粒進(jìn)行刻畫，因此可以從多個(gè)角度出發(fā)分析問題并獲得更加滿意、合理的求解，在許多多維度、多視角的現(xiàn)實(shí)生活問題中有強(qiáng)大的表示能力［2-4］.許多學(xué)者對(duì)多粒度粗糙集拓展模型進(jìn)行了研究，例如Lin et al［5］提出多粒度鄰域粗糙集，Dou et al［6］提出變精度多粒度粗糙集，張明等［7］提出可以自由控制粒度的可變粒度粗糙集等.

應(yīng)用多粒度粗糙集時(shí)不可避免地存在冗余粒度，冗余粒度對(duì)多粒度粗糙集的各種應(yīng)用沒有幫助，反而因參與計(jì)算增加了計(jì)算時(shí)間.為解決這類問題有學(xué)者提出粒度約簡(jiǎn)的概念.Qian et al［1］首先提出一種啟發(fā)式粒度約簡(jiǎn)算法，以粒度重要度為約簡(jiǎn)的依據(jù).對(duì)于多粒度粗糙集，因悲觀與樂觀多粒度下近似集本身存在不同，粒度重要度有多種形式，而無論是何種粒度約簡(jiǎn)算法，粒度重要度都是粒度約簡(jiǎn)的核心［8-9］.現(xiàn)行算法多以悲觀多粒度或者樂觀多粒度粗糙集之正域作為衡量粒度重要性的指標(biāo)，如孟慧麗等［10］考慮下近似分布約簡(jiǎn)，引入下近似分布約簡(jiǎn)中粒度集的信息量；汪小燕等［11］設(shè)計(jì)了可變粒度粗糙集的下近似分布粒度約簡(jiǎn)算法；張艷芹［12］在構(gòu)建基于模糊等價(jià)關(guān)系的悲觀多粒度模糊粗糙集模型的基礎(chǔ)上，進(jìn)一步給出粒度重要度的度量方法；于瑩瑩［13］提出相對(duì)粒度約簡(jiǎn)的概念并給出了基于相應(yīng)的粒度重要性的粒度約簡(jiǎn)算法；桑妍麗和錢宇華［14］引入分布約簡(jiǎn)的概念并給出了相應(yīng)的粒度重要度.這些基于正域或者下近似分布而提出的各種約簡(jiǎn)算法本質(zhì)上都是保持下近似不變的算法.

本文嘗試改進(jìn)基于正域的算法，提出基于多粒度粗糙集上下近似集的粒度重要性度量.在粒度增加時(shí)樂觀多粒度下近似集基數(shù)會(huì)變大，上近似集基數(shù)會(huì)減?。欢^多粒度下近似集基數(shù)會(huì)變小，上近似集基數(shù)會(huì)變大.基于這些性質(zhì)，以平滑系數(shù)為輔助項(xiàng)，提出兩種粒度重要性度量.基于提出的粒度重要性度量，提出一種計(jì)算重要度的矩陣方法并設(shè)計(jì)相應(yīng)的粒度約簡(jiǎn)算法，并使用UCI 數(shù)據(jù)驗(yàn)證了所提算法的有效性與優(yōu)越性.

本文的主要貢獻(xiàn)：

（1）提出保持樂觀/悲觀多粒度上下近似不變的約簡(jiǎn)方法，并提出了兩種基于多粒度粗糙集上下近似集的粒度重要性度量；

（2）提出計(jì)算（1）中粒度重要性度量的具體矩陣方法；

（3）設(shè)計(jì)了兩種啟發(fā)式粒度約簡(jiǎn)算法；

（4）使用公開UCI 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，通過對(duì)比算法驗(yàn)證了所提計(jì)算方法和兩種算法的有效性和高效性.

1 相關(guān)理論

定義1［1］令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng)，其中U={x1，x2，…，xn} 為非空有限論域，AT={A1，A2，…，Am} 為非空有限屬性集族，A∈AT是一個(gè)屬性集.為屬性值的值域，VA為屬性集A的值域.f：U×AT→V為一個(gè)決策函數(shù)，使得f(x，A)∈VA對(duì)任意的A∈AT，x∈U都成立.D={d1，d2，…，dr}為決策屬性.

定義2［1］ 樂觀多粒度粗糙集（Optimistic Multi-Granulation Rough Sets，OMGRS） 令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的X?U，X的樂觀多粒度下近似集與上近似集分別表示為：

引理1［15］令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的X?U，X的樂觀多粒度上近似集可以表示為：

定義3［1］ 悲觀多粒度粗糙集（Pessimistic Multi-Granulation Rough Sets，PMGRS）令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的X?U，X的悲觀多粒度下近似集與上近似集分別表示為：

引理2［15］令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的X?U，X的悲觀多粒度上近似集可以表示為：

定義4［15］令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意X?U，X的向量矩陣表示為G(X)=[g1(X)，g2(X)，…，gn(X)]T，其中表示矩陣的轉(zhuǎn)置.

2 基于多粒度粗糙集的粒度約簡(jiǎn)方法

定義5令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的x∈U，對(duì)于任意的BT?AT，BT的樂觀不定、確定決策累計(jì)函數(shù)分別定義為：

定義6令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的x∈U，對(duì)于任意的BT?AT，BT的悲觀不定、確定決策累計(jì)函數(shù)分別定義為：

定理1令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).如果BT?CT?AT，則以下關(guān)于BT，CT的性質(zhì)總是成立的：

證 明

定義7令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).如果對(duì)于任意的x∈U，對(duì)于任意的BT?AT，若滿足且則稱BT為樂觀累計(jì)決策粒度協(xié)調(diào)集.

定義8令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).如果對(duì)于任意的x∈U，對(duì)于任意的BT?AT，若滿足且則稱BT為悲觀累計(jì)決策粒度協(xié)調(diào)集.

定義9令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).如果BT?AT，BT為樂觀決策粒度協(xié)調(diào)集，若滿足對(duì)于任意的CT?BT，CT不是AT的樂觀決策粒度協(xié)調(diào)集，則稱BT為AT的樂觀累計(jì)決策粒度約簡(jiǎn)集.

定理2令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng)，如果CT為AT的樂觀累計(jì)決策粒度約簡(jiǎn)集.以下結(jié)論總是成立的：

（2）證明類似（1）.

定義10令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).如果BT?AT，BT為悲觀決策粒度協(xié)調(diào)集，若滿足對(duì)于任意的CT?BT，CT不是AT的悲觀決策粒度協(xié)調(diào)集，則稱BT為AT的悲觀累計(jì)決策粒度約簡(jiǎn)集.

定理3令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).如果CT為AT的悲觀累計(jì)決策粒度約簡(jiǎn)集.以下結(jié)論總是成立的：

證 明 類似定理2.

定義11令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的BT?AT，BT的樂觀平滑系數(shù)定義為：

定義12令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的BT?AT，BT的悲觀平滑系數(shù)定義為：

定義13令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的BT?AT，BT的樂觀累計(jì)決策重要度定義為：

定義14令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的BT?AT，BT的悲觀累計(jì)決策重要度定義為：

定理4令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的BT?CT?AT，以下性質(zhì)總是成立的：

（1）γO(BT)≤γO(CT)；

（2）γP(BT)≤γP(CT).

證 明

(1)由定義2 與引理1，顯然BT?CT?AT時(shí)，

從而有γO(BT)≤γO(CT).

（2）由定義3 與引理2，證明類似（1）.

定義15令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的BT?AT，Ak∈BT，Ak的樂觀粒度內(nèi)重要度的定義為：

定義16令S=()

U，AT，V，f，D為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的BT?AT，Ak∈BT，Ak的悲觀粒度內(nèi)重要度的定義為：

定義17令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的BT?AT，Ak?BT，Ak的樂觀粒度外重要度的定義為：

定義18令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的BT?AT，Ak?BT，Ak的悲觀粒度外重要度的定義為：

定義19令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的Ak∈AT，若滿足，則稱Ak為樂觀核心粒度，而所有樂觀核心粒度組成的集合稱為樂觀核心，記為COREO.

定義20令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).對(duì)于任意的Ak∈AT，若滿足，則稱Ak為悲觀核心粒度，而所有悲觀核心粒度組成的集合稱為悲觀核心，記為COREP.

定義21令S=(U，AT，V，f，D)為一個(gè)多粒度決策信息系統(tǒng).粒Ak的特征矩陣定義為，其中：

3 基于矩陣的粒度約簡(jiǎn)算法

由定理5 的（1）（3）可以導(dǎo)出計(jì)算樂觀多粒度粗糙集的粒度約簡(jiǎn)的算法，即算法1.

由定理5 的（2）（4），可以導(dǎo)出計(jì)算悲觀多粒度粗糙集的粒度約簡(jiǎn)的算法，即算法2.

Step 2 計(jì)算COREP，時(shí)間復(fù)雜度為O(|D||AT|2|U|)；Step 4 計(jì)算REDP，時(shí)間復(fù)雜度為O(|D||AT|2|U|)；Step 6 計(jì)算REDP中是否存在可約粒度，時(shí)間復(fù)雜度為O(|D||AT|2|U|).

4 UCI 數(shù)據(jù)實(shí)驗(yàn)

4.1 時(shí)間效率為了驗(yàn)證兩算法的時(shí)間效率，本文選取六個(gè)UCI 數(shù)據(jù)集（表1）來驗(yàn)證本文所提算法的有效性，樣本數(shù)從178 到1055，屬性數(shù)目從20 到41.所有實(shí)驗(yàn)均在系統(tǒng)為64-bit Windows 10 Inter（R） Core（TM） i7 6700HQ CPU @2.60 GHz 16 GB 的內(nèi)存?zhèn)€人計(jì)算機(jī)上進(jìn)行.所使用的編程語言是Matlab r2015b.

表1 實(shí)驗(yàn)使用的UCI 數(shù)據(jù)集Table 1 Details of UCI datasests

選取文獻(xiàn)［8，14］中介紹的計(jì)算多粒度粗糙集粒度約簡(jiǎn)的高效算法（EAGRMRS）與悲觀多粒度粗糙集中的粒度約簡(jiǎn)算法（GRAMGRS）作為對(duì)比算法，與本文的兩個(gè)算法（OMBGRA，PMBGRA）進(jìn)行對(duì)比.首先在同一數(shù)據(jù)集上模擬數(shù)據(jù)量增大的情況，將數(shù)據(jù)集大致等分為10 份，每次取出一份并入臨時(shí)數(shù)據(jù)集并在臨時(shí)數(shù)據(jù)集上進(jìn)行10 次重復(fù)實(shí)驗(yàn)，記錄計(jì)算粒度約簡(jiǎn)所需的時(shí)間，所得的結(jié)果如圖1 所示.可以看出，本文的算法與對(duì)比算法相比，至少有一個(gè)數(shù)量級(jí)的時(shí)間優(yōu)勢(shì).數(shù)據(jù)集增大時(shí)兩種算法的計(jì)算時(shí)間均隨數(shù)據(jù)集增大而增加，圖1 所示的結(jié)果符合預(yù)期，本文的粒度約簡(jiǎn)算法更高效.而后在同數(shù)據(jù)集上模擬粒增大的情況，使粒逐漸增大，進(jìn)行10 次重復(fù)實(shí)驗(yàn)，記錄計(jì)算粒度約簡(jiǎn)所需要的時(shí)間，所得的結(jié)果如圖2所示.可以看出，本文算法在同等粒度下比對(duì)比算法更高效.粒度增大時(shí)，兩種算法的計(jì)算時(shí)間均隨粒度增大而減少，這是因?yàn)槊總€(gè)粒度包含的屬性更多時(shí)，粒度總數(shù)就變少了，圖2 所示的結(jié)果符合預(yù)期.從圖1 和圖2 還可以發(fā)現(xiàn)，本文的兩種算法在計(jì)算時(shí)間效率上差別不大，可以計(jì)入誤差，這是因?yàn)橛?jì)算粒度重要度的兩種矩陣計(jì)算方法本身的復(fù)雜度并無差異，實(shí)驗(yàn)所得結(jié)果符合預(yù)期.

圖1 數(shù)據(jù)集增大時(shí)四個(gè)算法的計(jì)算時(shí)間對(duì)比Fig.1 Time consumption of OMBGRA，PMBGRA，EAGRMRS and GRAMGRS with different size of datasets

圖2 粒度的屬性集增大時(shí)四個(gè)算法的計(jì)算時(shí)間對(duì)比Fig.2 Time consumption of OMBGRA，PMBGRA，EAGRMRS and GRAMGRS with different size of granules

4.2 分類質(zhì)量為了驗(yàn)證所提算法約簡(jiǎn)的質(zhì)量，使用以下方式：使用每個(gè)數(shù)據(jù)集的每個(gè)單一粒度與決策一起構(gòu)造一個(gè)數(shù)據(jù)集，在該構(gòu)造數(shù)據(jù)集上取80%數(shù)據(jù)為訓(xùn)練集，余下的20%為測(cè)試集，在訓(xùn)練集上分別訓(xùn)練KNN（K 近鄰分類器）［16］、CART（決策樹CART 算法）［17］以及SVM（支持向量機(jī)）［18］，對(duì)測(cè)試集進(jìn)行分類，將約簡(jiǎn)后的所有粒度構(gòu)造的數(shù)據(jù)集上生成的分類結(jié)果取眾數(shù)，計(jì)算分類精度（AC），所得結(jié)果如表2 所示.

表2 不同算法的約簡(jiǎn)質(zhì)量對(duì)比Table 2 The reduction quantities of different algorithms

可以看出，在多數(shù)投票的分類集成原則上，本文的約簡(jiǎn)算法生成的粒度約簡(jiǎn)所訓(xùn)練的分類器，在五個(gè)數(shù)據(jù)集上具有與對(duì)比算法一致的分類精度，其中PMBGRA 在所有數(shù)據(jù)集上都具有與對(duì)比算法一致的分類精度，可以在節(jié)省大量計(jì)算時(shí)間的基礎(chǔ)上仍能夠保證一定的分類精度.

5 結(jié)論

本文提出兩種基于矩陣的多粒度粗糙集粒度約簡(jiǎn)方法，設(shè)計(jì)了相應(yīng)的基于矩陣的粒度約簡(jiǎn)算法，進(jìn)行了數(shù)據(jù)實(shí)驗(yàn)，驗(yàn)證了本文兩種算法的有效性.與現(xiàn)存的粒度約簡(jiǎn)方法進(jìn)行對(duì)比，本文的算法比對(duì)比算法的計(jì)算時(shí)間更短.因此，本文提出的計(jì)算方法及算法是可行且高效的.

經(jīng)過約簡(jiǎn)的粒度可以使多粒度決策算法更加高效，并且在一定程度上提高決策算法的魯棒性，在未來的研究中，將把所提出的粒度約簡(jiǎn)算法應(yīng)用于設(shè)計(jì)高效的多粒度決策算法.