一種變粒度的規則提取算法

胡帥鵬，張清華,2，姚龍洋

(1. 重慶郵電大學 計算智能重慶市重點實驗室，重慶 400065；2. 重慶郵電大學 理學院，重慶 400065)

一種變粒度的規則提取算法

胡帥鵬1，張清華1,2，姚龍洋1

(1. 重慶郵電大學 計算智能重慶市重點實驗室，重慶 400065；2. 重慶郵電大學 理學院，重慶 400065)

屬性約簡和值約簡是粗糙集理論中知識獲取的重要組成部分。通常，在知識獲取的過程中先進行屬性約簡，然后在其基礎上進行規則提取。但在實際應用中，屬性約簡在簡化信息系統與提高規則提取效率的同時，原始信息系統中有些重要的條件屬性可能被丟棄，從而導致屬性約簡后對信息系統進行知識獲取得到的規則其數量與簡化程度并不占優。針對上述問題，提出一種基于粒度變化的規則獲取算法，通過屬性粒度從粗到細的變化，直接從原始信息系統中提取規則；采用該方法得到的規則與屬性約簡后得到的規則相比，它們的數量與平均每條規則包含的特征屬性數相對較少。最后，在理論分析的基礎上，通過實例驗證了算法可行性，并通過實驗驗證了算法的正確性和高效性。

粗糙集；屬性約簡；規則提??；多粒度

0 引 言

由波蘭數學家Z.Pawlak在1982年提出的rough sets[1]，能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發現隱含的知識，揭示潛在的規律。經過三十余年的發展，該理論已滲透到各個行業，在工業控制、醫學衛生及生物科學、交通運輸、農業科學、環境科學與環境保護管理、安全科學、社會科學、航空、航天和軍事等領域中得到了廣泛應用[2]。

知識獲取是粗糙集的理論研究中的一項核心內容，主要是通過對原始決策表的約簡，在保證決策表的決策屬性和條件屬性之間的依賴關系不發生變化的前提下，對決策表進行約簡，包括屬性約簡和值約簡。目前國內外學者針對屬性約簡和值約簡的算法進行了大量的研究，其中，屬性約簡有基于代數觀、信息觀和正區域的約簡算法[3-12]；值約簡有基于可辨識矩陣、邏輯運算以及啟發式的約簡算法[13-17]。這些方法往往專注于某一項，從而忽視了屬性約簡對值約簡的影響，從而導致約簡效果并不理想。如文獻[13]中，屬性約簡的結果有多種，需要值約簡的結果來判定；文獻[14-15]并沒有有效地對規則進行簡化；文獻[16]雖然在規則的簡化程度上取得明顯效果，但在規則的數量上沒有明顯降低。從目前的研究看來，知識約簡是知識獲取的關鍵步驟，研究者往往給出某種啟發式信息，然后設計某種啟發式約簡算法，在知識空間中按照自頂向下或自底向上的方式實現約簡。知識約簡的主要目的是在保持信息系統分辨能力不變的前提下，刪除冗余屬性。這存在一個關鍵性問題，在知識約簡的過程中，條件屬性的刪除，主要基于主觀的啟發式方法，而不是基于是否對獲取規則有利。這就導致了某些信息系統在約簡后獲取的規則在其數量與簡化的程度上并不是最優的。本文通過實例驗證了某些信息系統直接獲取的規則優于對其屬性約簡后獲取的規則。針對一致信息系統，本文提出了一種新的獲取規則的算法，從正面直接獲取規則。在該算法中，提出了一種判定條件屬性是否是規則原理，即條件屬性對論域的劃分的標記是否相同，并對原理給予了證明。該算法主要基于粒計算的粗糙集模型[18-22]，在條件屬性粒度由粗到細[23]變化的過程中，直接選取滿足要求的最優的規則。

1 基本概念

為了更好地描述問題，首先介紹相關的概念。

定義1(決策表信息系統)[24]決策表信息系統可以表示為S=(U,A,V,f)，其中，U是對象全集，也稱為論域，它是非空有限的對象集合；A=C∪D是屬性全集，子集C和D分別稱為條件屬性集和決策屬性集，且C∩D=?；V是屬性值的集合，即屬性集A的值域；f:U×A→V，f為一個信息函數，表示每個實例對象的每個屬性賦予一個信息值。

定義2(不分明關系(Indiscernible relations))[24]設S=(U,A,V,f)是一個信息系統，R是一個屬性子集且R?A，決定了一個不可區分二元關系：IND(R)={(x,y)|(x,y)∈U2,?b∈R(b(x)=b(y))}。

不可區分二元關系IND(R)構成了U的劃分，記為U/IND(R)，且U/IND(R)={[x]R|x∈U}，其中，[x]R={y|?a∈R,f(x,a)=f(y,a)}。

定義4(知識顆粒)[19]設S=(U,A,V,f)是一個信息系統，其中A={c1,c2,…,cm}是屬性集，任給一個屬性子集R(R?A)，我們可以得到論域U的一個劃分U/IND(R)。U/IND(R)的每個元素[x]R([x]R表示對象的等價類) 表示一個知識顆粒。

屬性子集R包含屬性越多，知識顆粒越大；它與知識的粒度的變化趨勢相似，都隨著屬性子集R的多少由粗到細變化。

定義5(決策屬性劃分標號) 設S=(U,A,V,f)是一個信息系統，U是論域，A是屬性集，且A=C∪D。決策屬性對論域的劃分為U/IND(D)={Y1,Y2,…,Yi,…,Yk}，1≤i≤k，即決策屬性把論域劃分為k個等價類，第i個等價類包含論域對象序號標記為i，記為g(Yi)=i。

定義6(條件屬性子集劃分標號)S=(U,A,V,f)是一個信息系統，U是論域，A是屬性集，且A=C∪D。任給一個條件屬性子集B(B?C)，U/IND(B)={X1,X2,…,Xl}，根據定義5中決策屬性劃分的論域對象標號，依次填入等價類Xj,(j=1,2,…,l)中，并記Xj所對應的標號集合為Ej={p|?x∈Xj∧x∈Yi,p=g(Yi)}，其中，p表示Xj中元素的標號，x表示論域的對象。

決策屬性的等價類劃分使論域中每個個體都有一個標號，且每個Yi中標號統一為i；在條件子集的等價類Xj中，標號不同，即?pb∈Ej,pc∈Ej(pb≠pc)；標號完全相同，即?pb∈Ej,pc∈Ej(pb=pc)。當等價類Xj中的標號相同時，且為i，記N(j)=i。

定理1當且僅當N(j)=i成立時，條件屬性子集B(B?C)對應的條件屬性值是等價類Yi的子集的一個規則。

證明：設S=(U,A,V,f)是一個信息系統，U/IND(D)={Y1,Y2,…,Yi,…,Yk}是決策屬性集對論的劃分，第i個劃分子集對應的標號記為i。條件屬性子集B對論域的劃分記為U/IND(B)={X1,X2,…,Xj,…,Xl}，Xj中的標號由Yi對論域的標記而來。

1)當N(j)=i時，由定義6知Xj對應的論域對象是Yi對應的論域對象的子集，因此Xj?Yi成立。因為U/IND(B)={X1,X2,…,Xj,…,Xl}，所以用條件屬性子集B可以區分出Xj對應的論域對象，即B對應的條件屬性的值為Xj對應的論域對象的一個規則。且Xj?Yi，所以集合B對應的條件屬性值是等價類Yi的子集的一個規則。

2)當條件子集B對應的條件屬性值是等價類Yi的子集的一個規則時:集合B對論域形成劃分為U/IND(B)={X1,X2,…,Xj,…,Xl},則至少存在一個等價類是Yi對應論域的一個子集，不妨設為Xj。如果Xj對應的論域對象不是Yi對應的論域的子集，則它們至少分屬在2個子集中，即?p≠q,p,q∈{1,2,…,k}(Xj∩Yp≠?,Xj∩Yq≠?)，所以該論域對象不可區分，即條件子集B對應的條件屬性值不能形成規則。所以Xj對應的論域是Yi對應的論域的子集，Xj?Yi成立。由于Yi對應的論域標號為i，所以Xj對應的論域也標號為i，即有N(j)=i。

定理1表明，在信息系統S=(U,A,V,f)，U/IND(D)={Y1,Y2,…,Yi,…,Ym}為決策屬性集對論的劃分；條件屬性子集B(B?C)，子集B對論域的劃分為U/IND(B)={X1,X2,…,Xj,…,Xk}，當N(j)=i成立時，屬性子集B可以正確區分決策屬性的等價類Yi對應的論域U中的對象。

定義8(規則選取順序) 在進行規則選取時，不能盲目的進行，應按照一定的順序，這可以降低規則選取難度，加快規則選取的效率。規則選取的一般順序如下：

這一步選擇是為了保證剩下的任何一個論域都至少對應2條規則。

2)在上一步2的基礎上，根據剩余的論域對象，比較區分度δ的大小，優先選取區分度δ較大的規則；同時把新的條件屬性加入C′中。

3)如果區分度相同，優先選取規則所對應的條件屬性在C′中；并把新的條件屬性加入C′中。

它的主要目的是在粒度相同的條件下，用最少的規則數區分出最多的未出現的對象。它的基本原理是，每選取一條規則，都盡量多的區分未識別對象。

2 問題引入

在粗糙集中，知識獲取的最終目的是規則獲取。這些得到的規則是對整個信息表的高度概括，應包括整個信息表所要表達的完整信息。知識獲取的一般步驟是先進行屬性約簡，然后再做值的約簡，最后得到規則。這是因為屬性約簡后得到的信息表往往可以大幅度改善值約簡的時間和空間復雜度。在屬性約簡時，某些條件屬性對信息表而言可以刪除，而對規則獲取來說是一個不錯的選擇，如果刪除它們，得到的規則可能不是最優。

表1的信息系統1中記錄的是某件產品測試的具體信息，共有6個對象。條件屬性a，b，c分別表示3項測試項目的測試結果；決策屬性Y表示是否合格。

根據文獻[12]中提出基于差別矩陣的屬性約簡方法，得出該信息系統的3種屬性約簡結果，分別是{a,b}、{a,c}和{b,c}。用這3種屬性約簡的結果進行規則獲取，得出的規則如下所示。

1)以{a,b}為條件屬性得到的規則如下，記為規則集1：

①(a,1),則Y=R;

②(b,2),則Y=N;

③(a,2)且(b,1),則Y=P;

④(a,3)且(b,3),則Y=P;

2)以{a,c}為條件屬性得到的規則如下，記為規則集2：

①(a,1),則Y=R;

②(c,3),則Y=P;

③(a,2)且(c,1),則Y=N;

④(a,3)且(c,2),則Y=N;

3)以{b,c}為條件屬性得到的規則如下，記為規則集3：

①(b,2),則Y=N;

②(c,3),則Y=P;

③(b,1)且(c,1),則Y=R;

④(b,3)且(c,2),則Y=R;

規則集1～3的規則數量都為4，包含的特征屬性最大值為2，平均每條規則包含的特征屬性數為1.5。

4)但以原始信息系統{a,b,c}為條件屬性得到的規則如下，記為規則集4：

①(a,1),則Y=R;

①(b,2),則Y=N;

②(c,3),則Y=P;

規則集4的規則數量為3，包含的特征屬性均為1，平均每條規則包含的特征屬性數為1。

分別根據規則集1～3與規則集4進行測試時，無論是在規則數量、或者包含的特征屬性最大值以及規則的簡化程度上后者都優于前者。每個對象的最差測試量(最壞情況下，得出最終結果需要測試的特征屬性個數)前者比后者高50%。

表1 信息系統1

為了從上述3方面得出較優的規則，下文從原始信息系統出發，提出了一種基于變粒度的標記法進行規則提取。

3 算法描述

屬性約簡的算法，一般是按照自頂向下設計啟發式算法，逐漸增加重要屬性，直到得到約簡的結果為止；或是按照自底向上設計啟發式算法，逐漸刪除不重要屬性，直到得到約簡的結果為止。它們都是通過側面逼近的方法進行約簡，而規則獲取是在其基礎上進行的，獲取的規則存在限制，難免有些許不如意的地方。本文提出一種正面選取規則的算法。算法主要先對論域標號，再從條件屬性的粒度由粗至細變化的過程中對論域的劃分中選取標號相同的項，直接提取其對應的規則，并組合成完整論域的規則。

3.1 算法步驟

算法的流程圖如圖1所示。

圖1 流程圖Fig.1 Flowcharting

輸入：信息系統S=(U,A,V,f)。

輸出：該信息系統規則獲取的結果。

Step 1 首先初始化原始信息系統，設論域U={x1,x2,…,xn}，對象數量為|U|=n。條件屬性C={a1,a2,…,am}，條件屬性個數|C|=m，可區分對象集subset=?，粒度w=1。

Step 2 其次，再求決策屬性D對論域劃分，U/IND(D)={Y1,Y2,…,Yi,…,Yk}。

其中Yi={xi1,xi2,xi3,…}對應包含的對象序號。

Step 3 根據定義5，對每個對象進行標號：

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

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

if(xj∈Yi)xj←i

Step 4 粒度由粗到細變化，即條件屬性的個數由少到多遞增時，求取其對論域的劃分：while(w≤m)

U/IND(aw)={X1,X2,…,Xl}

Step 4.1 把Step 3得到的標號填入Xl中；

Step 4.2 根據定理1，首先找出所有Xl中標號相等的等價類，它所對應的是當前可以區分的對象，然后把不重復的對象加入subset中，并記錄subset={xw1,xw2,…,xwt}。

Step 4.3 根據定義8規則的選取順序，找出所有不重復的規則。

Step 4.4 ifU=subset，end；elsew=w+1，繼續執行Step 4。

算法說明：①算法以U=subset為結束條件，所以規則確定的論域與原始論域相同，即規則可以覆蓋整個論域。②算法在執行時，以包含的條件屬性數從少到多逐步的遞增，當規則最長為length(length正整數，表示規則包含條件屬性的個數，且1≤length≤card(C))時，不能完全覆蓋整個論域，才驗證包含長度為length+1的規則長度。所以，獲得的規則包含的特征屬性數一定是最小的。③為了滿足①與②所述的特征，即保證所求規則對論域的覆蓋率為100%，且規則數最少和平均每條規則包含的特征屬性數最小，需要粒度從粗到細逐步變化，所以導致算法的時間復雜度較高。但是，由于不同粒度之間計算相互獨立，互不影響，所以采取了并行運算方式，可以把算法的時間復雜度降低到與計算條件屬性對論域的劃分相當。

3.2 算法舉例

如表2所示的信息系統，其中論域U={1,2,…,15}，C={a1,a2,a3,a4}，D={d}。

Step 1 論域中對象的數量|U|=l=15，條件屬性個數|C|=n=4。

Step 2U/IND(d)=Y={{1,2,6,8,14},{3,4,5,7,9,10,11,12,13,15}}。

表2 信息系統2

Step 3 根據定義5進行標號，標記后為：{{1(1),2(1),6(1),8(1),14(1)},{3(2),4(2),5(2),7(2),9(2),10(2),11(2),12(2),13(2),15(2)}}。

Step 4 粒度由粗到細變化，首先當w=1時，G1={{a1},{a2},{a3},{a4}}，Xa1={{1,2,8,9,11},{3,7,12,13,15},{4,5,6,10,14}},Xa2={{1,2,3,13},{4,8,10,11,12,14},{5,6,7,9,15}},Xa3={{1,3,4,8,12,14},{2,9,15},{5,6,7,10,11,13}},Xa4={{1,3,4,5,8,9,10,13},{2,6,7,11,12,14,15}}。

Step 4.1 根據定義6得對應映射值如下：VXa1={(1,1,1,2,2),(2,2,2,2,2),(2,2,1,2,1)}，VXa2={(1,1,2,2),(2,1,2,2,2,2),(2,1,2,2,2)}，VXa3={(1,2,2,1,2,1),(1,2,2),(2,1,2,2,2,2)}，VXa4={(1,2,2,2,1,2,2,2),(1,1,2,2,2,1,2)}。

Step 4.2,4.3 只有VXa1的N(2)=2，說明只用屬性a1的值就能正確區分第二個等價類，即{3,7,12,13,15}，subset={3,7,12,13,15}。此時條件屬性集合為a1，所以選取規則得：

規則1：(a1，2)，則Class=P；

Step 4.4 因為subset={3,7,12,13,15}≠U，所以++w，返回繼續執行step 4。

Step 4 粒度進一步細分，變更為w=2，得G2={{a1a2},{a1a3},{a1a4},{a2a3},{a2a3},{a3a4}}。

Step 4.1 根據定義6得對應映射值為VXa1a2={(1,1),(2,2),(2,2,1),(2,1),(2,2),(1,2),(2),(2)}，VXa1a3={(1,1),(1,2),(2,2),(2,1),(2,1,2),(2,2),(2),(2)}，VXa1a4={(1,1,2),(1,2),(2,2),(2,2,2),(1,1),(2,2,2)}，VXa2a3={(1,2),(1),(2,1,2,1),(2,1,2),(2,2),(2,2),(2)}，VXa2a4={(1,2,2),(1),(2,1,2),(2,2),(1,2,2),(2,2,1)}，VXa3a4={(1,2,2,1),(1),(2,2,2),(1,2,2),(2,2),(2,1)}。

Step 4.2 所有滿足N(p)=q的不重復subset={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}。

Step 4.3 根據定義8，由于論域中第4項與第8項為唯一的，首先選擇規則：

規則2：(a1，1) 且 (a3，1)，則Class=N；

規則3：(a1，3) 且 (a4，1)，則Class=P；

規則4：(a1，3) 且 (a4，2)，則Class=N；

規則5：(a1,1)且(a2,1),則Class=N；

規則6：(a2,2)且(a3,3),則Class=N；

規則7：(a2,3)且(a4,1),則Class=P。

Step 4.4：此時，subset=U，結束。

同時，分析表2，{a1,a2,a4}與{a1,a3,a4}是其屬性約簡的結果。如果單獨用{a1,a2,a4}或{a1,a3,a4}進行規則獲取，最長的規則都為3，但是，用{a1,a2,a3,a4}進行規則獲取時，用2個條件屬性形成的規則，足夠區分整個論域。 這充分體現出了在進行規則提取時，完整的信息系統優于約簡后的信息系統性。

4 實驗結果

為了驗證本文中的算法，我們在Pentium(R) CPU3.00 GHz，RAM=4 GB微機上，Visual studio 2013上的C++ 環境下，采用UCI機器學習數據庫中的數據集進行測試。為證明其效果，我們用Rosetta軟件作了對比測試：在試驗中，除了monks(采用Rosetta自帶的genetic algorithm算法進行約簡)外，都是采用Rosetta自帶的Dynamic reduction算法進行約簡，再采用Rosetta自帶的值約簡算法進行規則的獲取，保證它們在該約簡算法中的得到的屬性個數與規則數相對最好，得出的測試結果如表3所示。從表3中可知，和Rosetta軟件相比，本文算法得到的決策規則在規則數量上與平均每條規則包含的特征屬性個數都比Rosetta軟件得到的少，同時對測試集的分類正確識別數也與Rosetta軟件得到的結果相當。因此，本文算法是有效和可行的。

表3 實驗結果

5 結束語

屬性約簡與值約簡是知識獲取的核心，但算法大多集中于屬性約簡，對屬性值的約簡研究相對較少。本文提出一種基于變粒度的規則提取算法，主要是解決了對于某些信息系統進行規則提取時，有些重要的條件屬性在屬性約簡中可能丟失，從而導致規則提取時提取的規則不是最優這一問題。該算法從正面直接選取合適的規則，直到沒有剩余區分項，因此獲得規則可以覆蓋整個論域。且粒度從粗到細變化，保證規則的長度最短。該算法為規則提取提供了一種新的方法。由于該算法比較適用信息系統較小的情況下，在下一步的研究中，將在并行計算與增量式的方向進行研究，來改善算法的執行效率。

[1] PAWLAK Z.Rough Set[J].International Journal of Computer and Information Science,1982,11(5):341-356.

[2] 王國胤,姚一豫,于洪.粗糙集理論與應用研究綜述[J].計算機學報,2009,32(7):1229-1246. WANG Guoyin，YAO Yiyu, YU Hong. A survey on Rough Set theory and applications[J]. Chinese Journal of Computers, 2009, 32(7):1229-1246.

[3] HU Xiaohu, CERCON N. Learning in relational databases: a rough set approach[J]. Computational Intelligence, 1995, 11(2):323-338.

[4] 王國胤,于洪,楊大春.基于條件信息熵的決策表約簡[J].計算機學報,2002,25(7):759-766. WANG Guoyin,YU Hong,YANG Dachun. Decision table reduction based on conditional information entropy[J].Chinese Journal of Computers,2002,25(7):759-766.

[5] WANG Guoyin. Rough reduction in algebra view and information view[J]. International Journal of Intelligent Systems, 2003, 18(6):679-688.

[6] 劉少輝,盛秋戩,吳斌,等.Rough集高效算法的研究[J].計算機學報,2003,26(5):524-529. LIU Shaohui, SHENG Qiujian, WU Bin, et al. Research on efficient algorithms for Rough Set methods[J]. Chinese Journal of Computers, 2003, 26(5):524-529.

[7] 馮琴榮,苗奪謙,程昳.決策表屬性約簡的相對劃分粒度表示[J].小型微型計算機系統,2008,29(12):2305-2308. FENG Qinrong, MIAO Duoqian, CHENG Yi. Presentation of relative partition granularity of attributes reduction for decision table[J]. Mini-Micro Systems, 2008, 29(12):2305-2308.

[8] 楊明.一種基于一致性準則的屬性約簡算法[J].計算機學報,2010,33(2):231-239. YANG Ming. A novel algorithm for attribute reduction based on consistency criterion[J]. Chinese Journal of Computers, 2010, 33(2):231-239.

[9] XU Zhangyan, ZHANG Wei, WANG Xiaoyu, et al. A quick attribute reduction algorithm based on knowledge granularity[C]//Fuzzy Systems and Knowledge Discovery (FSKD), 2012 9th International Conference on. Chinese: IEEE, 2012:220-223.

[10] ZHANG Tengfei,YANG Xingxing,MA Fumin.Algorithm for attribute relative reduction based on generalized binary discernibility matrix[C]∥Control and Decision Conference(2014 CCDC).Chinese：IEEE,2014:2626-2631.

[11] 苗奪謙,胡桂榮.知識約簡的一種啟發式算法[J].計算機研究與發展,1999,36(6):681-684. MIAO Duoqian, HU Guirong. A heuristic algorithm for reduction of knowledge[J]. Journal of Computer Research and Development, 1999, 36(6):681-684.

[12] 馬希驁,王國胤,于洪.決策域分布保持的啟發式屬性約簡方法[J].軟件學報,2014,25(8):1761-1780. MA Xi’ao,WANG Guoyin,YU Hong.Heuristic method to attribute reduction for decision region distribution preservation[J].Journal of Software,2014,25(8):1761-1780.

[13] 常犁云,王國胤,吳渝.一種基于Rough Set理論的屬性約簡及規則提取方法[J].軟件學報,1999,10(11):1206-1211. CHANG Liyun,WANG Guoyin,WU Yu.An approach for attribute reduction and rule generation based on Rough Set theory[J].Journal of Software,1999,10(11)：1206-1211.[14] 梁吉業,王俊紅.基于概念格的規則產生集挖掘算法[J].計算機研究與發展,2004,41(8):1339-1344. LIANG Jiye, WANG Junhong. An algorithm for extracting rule generating sets based on concept lattice[J]. Journal of Computer Research and Development, 2004, 41(8):1339-1344.

[15] 文香軍,蔡云澤,譚天樂，等.基于粗糙屬性向量樹的規則提取快速矩陣算法[J].電子學報,2006,34(1):66-70. WEN Xiangjun, CAI Yunze, TAN Tianle, et al. Fast matrix computation algorithms based on RAVT for rules extraction[J]. Chinese Journal of Electronic, 2006, 34(1):66-70.

[16] 鄂旭,邵良杉,張毅智，等.一種基于粗糙集理論的規則提取方法[J].計算機科學,2011,38(1):232-235. E Xu, SHAO Liangshan, ZHANG Yizhi, et al. Method of rule extraction based on Rough Set theory[J]. Computer Science, 2011, 38(1):232-235.

[17] QIAN Wenbin, YANG Bingru, XIE Yonghong, et al. A rule extraction algorithm based on compound attribute measure in decision systems [C]//Fuzzy Systems and Knowledge Discovery (FSKD), 2013 10th International Conference on. Chinese: IEEE, 2013: 407-411.

[18] 苗奪謙,徐菲菲,姚一豫，等.粒計算的集合論描述[J].計算機學報,2012,35(2):351-363. MIAO Duoqian, XU Feifei, YAO Yiyu, et al. Set-theoretic formulation of granular computing[J]. Chinese Journal of Computers, 2012, 35(2):351-363.

[19] 王國胤,張清華.不同知識粒度下粗糙集的不確定性研究[J].計算機學報,2008,31(9):1588-1598. WANG Guoyin, ZHANG Qinghua. Uncertainty of Rough Sets in different knowledge granularities[J]. Chinese Journal of Computers, 2008, 31(9):1588-1598.

[20] 王國胤,張清華,馬希驁,等.知識不確定性問題的粒計算模型[J].軟件學報,2011,22(4):676-694. WANG Guoyin, ZHANG Qinghua, MA Xi’ao. Granular computing models for knowledge uncertainty[J]. Journal of Software, 2011, 22(4): 676-694.

[21] YAO J T, VASILAKOS A V, PEDRYCZ W. Granular computing: perspectives and challenges[J]. Cybernetics, IEEE Transactions on, 2013, 43(6):1977-1989

[22] 周如旗,馮嘉禮.基于屬性粒計算的認知模型研究[J].計算機科學,2014,41(7): 68-73. ZHOU Ruqi, FENG Jiali. Research on cognitive model base on attribute granular computing[J]. Computer Science, 2014, 41(7):68-73.

[23] 陳澤華,謝剛,謝珺，等.粒矩陣及其在知識約簡中的應用[J].計算機科學與探索,2010,4(3):283-288. CHEN Zehua, XIE Gang, XIE Qun, et al. BGRM and its application in knowledge reduction[J]. Journal of Frontiers of Computer Science and Technology, 2010, 4(3):283-288.

[24] 王國胤.Rough集理論與知識獲取[M].西安:西安交通大學出版社,2001. WANG Guoyin.Rough Set Theory and knowledge Acquisition[M].Xi’an:Xi’an Jiao tong University Press,2001.

[25] 張清華,王國胤,劉顯全.基于最大粒的規則獲取算法[J].模式識別與人工智能,2012,25(3):388-396. ZHANG Qinghua, WANG Guoyin, LIU Xianquan. Rule acquisition algorithm based on maximal granular [J]. Pattern recognition and artificial intelligence, 2012, 25(3):388-396.

胡帥鵬(1989-),男,河南平頂山人,碩士研究生,主要研究領域為粗糙集, 粒計算等。E-mail: hushpe@163.com.

張清華(1974-),男,重慶市人,教授,博士,主要研究領域為粗糙集,粒計算等。主持國家自然基金1項等。

姚龍洋(1989-),男,河南洛陽人,碩士研究生,主要研究領域為粗糙集,粒計算等。

(編輯：張 誠)

An algorithm for rule extraction based on changing granularity

HU Shuaipeng1, ZHANG Qinghua1,2, YAO Longyang1

(1.Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China;2.School of Science, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China)

The attribute reduction and value reduction are two important parts of knowledge acquisition in rough set. Generally, the method of knowledge acquisition is based on rule extraction of attribute reduction. But in the actual application, attribute reduction simplifies the information system and improves rule extraction’s efficiency. At the same time, some important condition attributes may be discarded. So it has the direct result that the numbers and simplification of rules are not necessarily good. Therefore, in this paper, an algorithm based on changing granularity is presented, and with this method we can obtain rules step by step when the granularity is changed from coarse to fine. The rules can extracted from the original information system. Compared with the results after attribute reduction, the numbers and simplification of rules are better. Theoretical analysis and experimental result show that the algorithm of this paper is feasible. Finally, experimental results show that the new algorithm is not only accurate but also efficient.

rough set; attribute reduction; rule extraction; multi-granularity

10.3979/j.issn.1673-825X.2016.06.018

2014-12-24

2016-06-11

胡帥鵬 hushpe@163.com

國家自然科學基金項目(61472056，61309014)；重慶郵電大學科研訓練計劃項目(A2014-45)

Foundation Items：The National Science Foundation of China(61472056，61309014)；The Research Training Program of Chongqing University of Posts and Telecommunications (A2014-45)

TP181

A

1673-825X(2016)06-0856-07