基于矩陣的多粒度粗糙集粒度約簡方法

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

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

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

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

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

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

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

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

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

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

1 相關(guān)理論

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

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

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

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

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

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

2 基于多粒度粗糙集的粒度約簡方法

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

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

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

證 明

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

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

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

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

（2）證明類似（1）.

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

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

證 明 類似定理2.

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

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

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

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

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

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

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

證 明

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

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

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

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

定義16令S=()

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

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

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

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

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

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

3 基于矩陣的粒度約簡算法

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

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

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

4 UCI 數(shù)據(jù)實驗

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

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

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

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

圖2 粒度的屬性集增大時四個算法的計算時間對比Fig.2 Time consumption of OMBGRA，PMBGRA，EAGRMRS and GRAMGRS with different size of granules

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

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

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

5 結(jié)論

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

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