一種變粒度的規(guī)則提取算法

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

(1. 重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065；2. 重慶郵電大學(xué) 理學(xué)院，重慶 400065)

一種變粒度的規(guī)則提取算法

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

(1. 重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065；2. 重慶郵電大學(xué) 理學(xué)院，重慶 400065)

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

粗糙集；屬性約簡(jiǎn)；規(guī)則提??；多粒度

0 引 言

由波蘭數(shù)學(xué)家Z.Pawlak在1982年提出的rough sets[1]，能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識(shí)，揭示潛在的規(guī)律。經(jīng)過(guò)三十余年的發(fā)展，該理論已滲透到各個(gè)行業(yè)，在工業(yè)控制、醫(yī)學(xué)衛(wèi)生及生物科學(xué)、交通運(yùn)輸、農(nóng)業(yè)科學(xué)、環(huán)境科學(xué)與環(huán)境保護(hù)管理、安全科學(xué)、社會(huì)科學(xué)、航空、航天和軍事等領(lǐng)域中得到了廣泛應(yīng)用[2]。

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

1 基本概念

為了更好地描述問(wèn)題，首先介紹相關(guān)的概念。

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

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

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

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

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

定義5(決策屬性劃分標(biāo)號(hào)) 設(shè)S=(U,A,V,f)是一個(gè)信息系統(tǒng)，U是論域，A是屬性集，且A=C∪D。決策屬性對(duì)論域的劃分為U/IND(D)={Y1,Y2,…,Yi,…,Yk}，1≤i≤k，即決策屬性把論域劃分為k個(gè)等價(jià)類(lèi)，第i個(gè)等價(jià)類(lèi)包含論域?qū)ο笮蛱?hào)標(biāo)記為i，記為g(Yi)=i。

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

決策屬性的等價(jià)類(lèi)劃分使論域中每個(gè)個(gè)體都有一個(gè)標(biāo)號(hào)，且每個(gè)Yi中標(biāo)號(hào)統(tǒng)一為i；在條件子集的等價(jià)類(lèi)Xj中，標(biāo)號(hào)不同，即?pb∈Ej,pc∈Ej(pb≠pc)；標(biāo)號(hào)完全相同，即?pb∈Ej,pc∈Ej(pb=pc)。當(dāng)?shù)葍r(jià)類(lèi)Xj中的標(biāo)號(hào)相同時(shí)，且為i，記N(j)=i。

定理1當(dāng)且僅當(dāng)N(j)=i成立時(shí)，條件屬性子集B(B?C)對(duì)應(yīng)的條件屬性值是等價(jià)類(lèi)Yi的子集的一個(gè)規(guī)則。

證明：設(shè)S=(U,A,V,f)是一個(gè)信息系統(tǒng)，U/IND(D)={Y1,Y2,…,Yi,…,Yk}是決策屬性集對(duì)論的劃分，第i個(gè)劃分子集對(duì)應(yīng)的標(biāo)號(hào)記為i。條件屬性子集B對(duì)論域的劃分記為U/IND(B)={X1,X2,…,Xj,…,Xl}，Xj中的標(biāo)號(hào)由Yi對(duì)論域的標(biāo)記而來(lái)。

1)當(dāng)N(j)=i時(shí)，由定義6知Xj對(duì)應(yīng)的論域?qū)ο笫荵i對(duì)應(yīng)的論域?qū)ο蟮淖蛹?，因此Xj?Yi成立。因?yàn)閁/IND(B)={X1,X2,…,Xj,…,Xl}，所以用條件屬性子集B可以區(qū)分出Xj對(duì)應(yīng)的論域?qū)ο?，即B對(duì)應(yīng)的條件屬性的值為Xj對(duì)應(yīng)的論域?qū)ο蟮囊粋€(gè)規(guī)則。且Xj?Yi，所以集合B對(duì)應(yīng)的條件屬性值是等價(jià)類(lèi)Yi的子集的一個(gè)規(guī)則。

2)當(dāng)條件子集B對(duì)應(yīng)的條件屬性值是等價(jià)類(lèi)Yi的子集的一個(gè)規(guī)則時(shí):集合B對(duì)論域形成劃分為U/IND(B)={X1,X2,…,Xj,…,Xl},則至少存在一個(gè)等價(jià)類(lèi)是Yi對(duì)應(yīng)論域的一個(gè)子集，不妨設(shè)為Xj。如果Xj對(duì)應(yīng)的論域?qū)ο蟛皇荵i對(duì)應(yīng)的論域的子集，則它們至少分屬在2個(gè)子集中，即?p≠q,p,q∈{1,2,…,k}(Xj∩Yp≠?,Xj∩Yq≠?)，所以該論域?qū)ο蟛豢蓞^(qū)分，即條件子集B對(duì)應(yīng)的條件屬性值不能形成規(guī)則。所以Xj對(duì)應(yīng)的論域是Yi對(duì)應(yīng)的論域的子集，Xj?Yi成立。由于Yi對(duì)應(yīng)的論域標(biāo)號(hào)為i，所以Xj對(duì)應(yīng)的論域也標(biāo)號(hào)為i，即有N(j)=i。

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

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

這一步選擇是為了保證剩下的任何一個(gè)論域都至少對(duì)應(yīng)2條規(guī)則。

2)在上一步2的基礎(chǔ)上，根據(jù)剩余的論域?qū)ο?，比較區(qū)分度δ的大小，優(yōu)先選取區(qū)分度δ較大的規(guī)則；同時(shí)把新的條件屬性加入C′中。

3)如果區(qū)分度相同，優(yōu)先選取規(guī)則所對(duì)應(yīng)的條件屬性在C′中；并把新的條件屬性加入C′中。

它的主要目的是在粒度相同的條件下，用最少的規(guī)則數(shù)區(qū)分出最多的未出現(xiàn)的對(duì)象。它的基本原理是，每選取一條規(guī)則，都盡量多的區(qū)分未識(shí)別對(duì)象。

2 問(wèn)題引入

在粗糙集中，知識(shí)獲取的最終目的是規(guī)則獲取。這些得到的規(guī)則是對(duì)整個(gè)信息表的高度概括，應(yīng)包括整個(gè)信息表所要表達(dá)的完整信息。知識(shí)獲取的一般步驟是先進(jìn)行屬性約簡(jiǎn)，然后再做值的約簡(jiǎn)，最后得到規(guī)則。這是因?yàn)閷傩约s簡(jiǎn)后得到的信息表往往可以大幅度改善值約簡(jiǎn)的時(shí)間和空間復(fù)雜度。在屬性約簡(jiǎn)時(shí)，某些條件屬性對(duì)信息表而言可以刪除，而對(duì)規(guī)則獲取來(lái)說(shuō)是一個(gè)不錯(cuò)的選擇，如果刪除它們，得到的規(guī)則可能不是最優(yōu)。

表1的信息系統(tǒng)1中記錄的是某件產(chǎn)品測(cè)試的具體信息，共有6個(gè)對(duì)象。條件屬性a，b，c分別表示3項(xiàng)測(cè)試項(xiàng)目的測(cè)試結(jié)果；決策屬性Y表示是否合格。

根據(jù)文獻(xiàn)[12]中提出基于差別矩陣的屬性約簡(jiǎn)方法，得出該信息系統(tǒng)的3種屬性約簡(jiǎn)結(jié)果，分別是{a,b}、{a,c}和{b,c}。用這3種屬性約簡(jiǎn)的結(jié)果進(jìn)行規(guī)則獲取，得出的規(guī)則如下所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

規(guī)則集4的規(guī)則數(shù)量為3，包含的特征屬性均為1，平均每條規(guī)則包含的特征屬性數(shù)為1。

分別根據(jù)規(guī)則集1～3與規(guī)則集4進(jìn)行測(cè)試時(shí)，無(wú)論是在規(guī)則數(shù)量、或者包含的特征屬性最大值以及規(guī)則的簡(jiǎn)化程度上后者都優(yōu)于前者。每個(gè)對(duì)象的最差測(cè)試量(最壞情況下，得出最終結(jié)果需要測(cè)試的特征屬性個(gè)數(shù))前者比后者高50%。

表1 信息系統(tǒng)1

為了從上述3方面得出較優(yōu)的規(guī)則，下文從原始信息系統(tǒng)出發(fā)，提出了一種基于變粒度的標(biāo)記法進(jìn)行規(guī)則提取。

3 算法描述

屬性約簡(jiǎn)的算法，一般是按照自頂向下設(shè)計(jì)啟發(fā)式算法，逐漸增加重要屬性，直到得到約簡(jiǎn)的結(jié)果為止；或是按照自底向上設(shè)計(jì)啟發(fā)式算法，逐漸刪除不重要屬性，直到得到約簡(jiǎn)的結(jié)果為止。它們都是通過(guò)側(cè)面逼近的方法進(jìn)行約簡(jiǎn)，而規(guī)則獲取是在其基礎(chǔ)上進(jìn)行的，獲取的規(guī)則存在限制，難免有些許不如意的地方。本文提出一種正面選取規(guī)則的算法。算法主要先對(duì)論域標(biāo)號(hào)，再?gòu)臈l件屬性的粒度由粗至細(xì)變化的過(guò)程中對(duì)論域的劃分中選取標(biāo)號(hào)相同的項(xiàng)，直接提取其對(duì)應(yīng)的規(guī)則，并組合成完整論域的規(guī)則。

3.1 算法步驟

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

圖1 流程圖Fig.1 Flowcharting

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

輸出：該信息系統(tǒng)規(guī)則獲取的結(jié)果。

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

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

其中Yi={xi1,xi2,xi3,…}對(duì)應(yīng)包含的對(duì)象序號(hào)。

Step 3 根據(jù)定義5，對(duì)每個(gè)對(duì)象進(jìn)行標(biāo)號(hào)：

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

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

if(xj∈Yi)xj←i

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

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

Step 4.1 把Step 3得到的標(biāo)號(hào)填入Xl中；

Step 4.2 根據(jù)定理1，首先找出所有Xl中標(biāo)號(hào)相等的等價(jià)類(lèi)，它所對(duì)應(yīng)的是當(dāng)前可以區(qū)分的對(duì)象，然后把不重復(fù)的對(duì)象加入subset中，并記錄subset={xw1,xw2,…,xwt}。

Step 4.3 根據(jù)定義8規(guī)則的選取順序，找出所有不重復(fù)的規(guī)則。

Step 4.4 ifU=subset，end；elsew=w+1，繼續(xù)執(zhí)行Step 4。

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

3.2 算法舉例

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

Step 1 論域中對(duì)象的數(shù)量|U|=l=15，條件屬性個(gè)數(shù)|C|=n=4。

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

表2 信息系統(tǒng)2

Step 3 根據(jù)定義5進(jìn)行標(biāo)號(hào)，標(biāo)記后為：{{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 粒度由粗到細(xì)變化，首先當(dāng)w=1時(shí)，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 根據(jù)定義6得對(duì)應(yīng)映射值如下：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，說(shuō)明只用屬性a1的值就能正確區(qū)分第二個(gè)等價(jià)類(lèi)，即{3,7,12,13,15}，subset={3,7,12,13,15}。此時(shí)條件屬性集合為a1，所以選取規(guī)則得：

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

Step 4.4 因?yàn)閟ubset={3,7,12,13,15}≠U，所以++w，返回繼續(xù)執(zhí)行step 4。

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

Step 4.1 根據(jù)定義6得對(duì)應(yīng)映射值為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 所有滿(mǎn)足N(p)=q的不重復(fù)subset={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}。

Step 4.3 根據(jù)定義8，由于論域中第4項(xiàng)與第8項(xiàng)為唯一的，首先選擇規(guī)則：

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

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

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

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

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

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

Step 4.4：此時(shí)，subset=U，結(jié)束。

同時(shí)，分析表2，{a1,a2,a4}與{a1,a3,a4}是其屬性約簡(jiǎn)的結(jié)果。如果單獨(dú)用{a1,a2,a4}或{a1,a3,a4}進(jìn)行規(guī)則獲取，最長(zhǎng)的規(guī)則都為3，但是，用{a1,a2,a3,a4}進(jìn)行規(guī)則獲取時(shí)，用2個(gè)條件屬性形成的規(guī)則，足夠區(qū)分整個(gè)論域。 這充分體現(xiàn)出了在進(jìn)行規(guī)則提取時(shí)，完整的信息系統(tǒng)優(yōu)于約簡(jiǎn)后的信息系統(tǒng)性。

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

為了驗(yàn)證本文中的算法，我們?cè)赑entium(R) CPU3.00 GHz，RAM=4 GB微機(jī)上，Visual studio 2013上的C++ 環(huán)境下，采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的數(shù)據(jù)集進(jìn)行測(cè)試。為證明其效果，我們用Rosetta軟件作了對(duì)比測(cè)試：在試驗(yàn)中，除了monks(采用Rosetta自帶的genetic algorithm算法進(jìn)行約簡(jiǎn))外，都是采用Rosetta自帶的Dynamic reduction算法進(jìn)行約簡(jiǎn)，再采用Rosetta自帶的值約簡(jiǎn)算法進(jìn)行規(guī)則的獲取，保證它們?cè)谠摷s簡(jiǎn)算法中的得到的屬性個(gè)數(shù)與規(guī)則數(shù)相對(duì)最好，得出的測(cè)試結(jié)果如表3所示。從表3中可知，和Rosetta軟件相比，本文算法得到的決策規(guī)則在規(guī)則數(shù)量上與平均每條規(guī)則包含的特征屬性個(gè)數(shù)都比Rosetta軟件得到的少，同時(shí)對(duì)測(cè)試集的分類(lèi)正確識(shí)別數(shù)也與Rosetta軟件得到的結(jié)果相當(dāng)。因此，本文算法是有效和可行的。

表3 實(shí)驗(yàn)結(jié)果

5 結(jié)束語(yǔ)

屬性約簡(jiǎn)與值約簡(jiǎn)是知識(shí)獲取的核心，但算法大多集中于屬性約簡(jiǎn)，對(duì)屬性值的約簡(jiǎn)研究相對(duì)較少。本文提出一種基于變粒度的規(guī)則提取算法，主要是解決了對(duì)于某些信息系統(tǒng)進(jìn)行規(guī)則提取時(shí)，有些重要的條件屬性在屬性約簡(jiǎn)中可能丟失，從而導(dǎo)致規(guī)則提取時(shí)提取的規(guī)則不是最優(yōu)這一問(wèn)題。該算法從正面直接選取合適的規(guī)則，直到?jīng)]有剩余區(qū)分項(xiàng)，因此獲得規(guī)則可以覆蓋整個(gè)論域。且粒度從粗到細(xì)變化，保證規(guī)則的長(zhǎng)度最短。該算法為規(guī)則提取提供了一種新的方法。由于該算法比較適用信息系統(tǒng)較小的情況下，在下一步的研究中，將在并行計(jì)算與增量式的方向進(jìn)行研究，來(lái)改善算法的執(zhí)行效率。

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

[2] 王國(guó)胤,姚一豫,于洪.粗糙集理論與應(yīng)用研究綜述[J].計(jì)算機(jī)學(xué)報(bào),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] 王國(guó)胤,于洪,楊大春.基于條件信息熵的決策表約簡(jiǎn)[J].計(jì)算機(jī)學(xué)報(bào),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].計(jì)算機(jī)學(xué)報(bào),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] 馮琴榮,苗奪謙,程昳.決策表屬性約簡(jiǎn)的相對(duì)劃分粒度表示[J].小型微型計(jì)算機(jī)系統(tǒng),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] 楊明.一種基于一致性準(zhǔn)則的屬性約簡(jiǎn)算法[J].計(jì)算機(jī)學(xué)報(bào),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] 苗奪謙,胡桂榮.知識(shí)約簡(jiǎn)的一種啟發(fā)式算法[J].計(jì)算機(jī)研究與發(fā)展,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] 馬希驁,王國(guó)胤,于洪.決策域分布保持的啟發(fā)式屬性約簡(jiǎn)方法[J].軟件學(xué)報(bào),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] 常犁云,王國(guó)胤,吳渝.一種基于Rough Set理論的屬性約簡(jiǎn)及規(guī)則提取方法[J].軟件學(xué)報(bào),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] 梁吉業(yè),王俊紅.基于概念格的規(guī)則產(chǎn)生集挖掘算法[J].計(jì)算機(jī)研究與發(fā)展,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] 文香軍,蔡云澤,譚天樂(lè)，等.基于粗糙屬性向量樹(shù)的規(guī)則提取快速矩陣算法[J].電子學(xué)報(bào),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] 鄂旭,邵良杉,張毅智，等.一種基于粗糙集理論的規(guī)則提取方法[J].計(jì)算機(jī)科學(xué),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ì)算的集合論描述[J].計(jì)算機(jī)學(xué)報(bào),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] 王國(guó)胤,張清華.不同知識(shí)粒度下粗糙集的不確定性研究[J].計(jì)算機(jī)學(xué)報(bào),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] 王國(guó)胤,張清華,馬希驁,等.知識(shí)不確定性問(wèn)題的粒計(jì)算模型[J].軟件學(xué)報(bào),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ì)算的認(rèn)知模型研究[J].計(jì)算機(jī)科學(xué),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] 陳澤華,謝剛,謝珺，等.粒矩陣及其在知識(shí)約簡(jiǎn)中的應(yīng)用[J].計(jì)算機(jī)科學(xué)與探索,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] 王國(guó)胤.Rough集理論與知識(shí)獲取[M].西安:西安交通大學(xué)出版社,2001. WANG Guoyin.Rough Set Theory and knowledge Acquisition[M].Xi’an:Xi’an Jiao tong University Press,2001.

[25] 張清華,王國(guó)胤,劉顯全.基于最大粒的規(guī)則獲取算法[J].模式識(shí)別與人工智能,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-),男,河南平頂山人,碩士研究生,主要研究領(lǐng)域?yàn)榇植诩? 粒計(jì)算等。E-mail: hushpe@163.com.

張清華(1974-),男,重慶市人,教授,博士,主要研究領(lǐng)域?yàn)榇植诩?粒計(jì)算等。主持國(guó)家自然基金1項(xiàng)等。

姚龍洋(1989-),男,河南洛陽(yáng)人,碩士研究生,主要研究領(lǐng)域?yàn)榇植诩?粒計(jì)算等。

(編輯：張 誠(chéng))

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

國(guó)家自然科學(xué)基金項(xiàng)目(61472056，61309014)；重慶郵電大學(xué)科研訓(xùn)練計(jì)劃項(xiàng)目(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