基于粒度決策熵的屬性約簡(jiǎn)

李 華，江 峰，于 旭，杜軍威，劉國柱

(青島科技大學(xué)信息科學(xué)與技術(shù)學(xué)院，山東 青島 266061)

0 引 言

在1982年的時(shí)候，波蘭有名的數(shù)學(xué)家Pawlak就提出了著名的粗糙集理論[1]。具體來說，粗糙集理論是一種數(shù)學(xué)工具，它主要是用來描繪數(shù)據(jù)的不完整性和不確定性。人們用該理論來刻畫數(shù)據(jù)的不精確性，并且可以從數(shù)據(jù)中得出隱含的大量知識(shí)，還可以得出數(shù)據(jù)之間的規(guī)律性。粗糙集的主要研究之一可以說是屬性的約簡(jiǎn)[2]。一個(gè)好的約簡(jiǎn)算法不僅可以除去數(shù)據(jù)集中不相關(guān)的屬性還能確保整體系統(tǒng)的分類能力和決策能力，從而簡(jiǎn)化知識(shí)表示，并提高系統(tǒng)處理的效率，方便用戶的決策。

現(xiàn)在國內(nèi)許多學(xué)者致力于研究屬性約簡(jiǎn)的方法，并且已經(jīng)提出了許多求解的算法，例如基于正區(qū)域的屬性約簡(jiǎn)算法[3-5]、基于信息熵的屬性約簡(jiǎn)算法[6-8]和基于差別矩陣的屬性約簡(jiǎn)算法[9-10]等。在進(jìn)行數(shù)據(jù)集的約簡(jiǎn)時(shí)，可能會(huì)得到多個(gè)約簡(jiǎn)集，然而人們希望能夠找出最小的即最優(yōu)的那個(gè)約簡(jiǎn)集?，F(xiàn)有的約簡(jiǎn)算法已經(jīng)表明了找尋最優(yōu)的約簡(jiǎn)集是一個(gè)NP-hard的問題。所以，已經(jīng)提出的約簡(jiǎn)算法把找尋最優(yōu)約簡(jiǎn)的目標(biāo)改為了找尋盡可能小的約簡(jiǎn)，同時(shí)還能夠降低計(jì)算的時(shí)間復(fù)雜度和空間復(fù)雜度即計(jì)算的開銷。在進(jìn)行屬性約簡(jiǎn)時(shí)，需要對(duì)數(shù)據(jù)集中屬性的重要度進(jìn)行概括總結(jié)，并且同時(shí)給出定義。而當(dāng)前來看，人們定義屬性重要度主要是基于代數(shù)和信息論2種觀點(diǎn)。具體來講，人們用代數(shù)觀點(diǎn)定義屬性重要性主要是考慮代數(shù)學(xué)中的集合運(yùn)算和不可分辨關(guān)系，而用信息論觀點(diǎn)來定義時(shí)主要是考慮信息論中信息熵的作用[11]。

在1948年的時(shí)候，香農(nóng)提出了一種新的理論概念即信息熵理論，人們把香農(nóng)提出的信息熵理論概念應(yīng)用到處理信息的量化度量方面，來解決在數(shù)據(jù)集的約簡(jiǎn)中數(shù)據(jù)的量化度量難題。這些年來，隨著人們把信息熵引入粗糙集理論中，很多新的有效的理論概念被提出來。例如，學(xué)者們得出了許多新的信息熵模型——組合熵、知識(shí)熵和粗糙熵等模型。在這些不同的信息熵的模型的基礎(chǔ)上，人們提出了不同的屬性約簡(jiǎn)算法。比如，利用數(shù)據(jù)集上數(shù)據(jù)中屬性之間的互信息，苗奪謙等得出了新的屬性約簡(jiǎn)算法即基于互信息的約簡(jiǎn)算法。王國胤[11]等提出了基于條件信息熵的屬性約簡(jiǎn)算法，利用條件信息熵來重新定義屬性的重要性。梁吉業(yè)等利用粗糙熵來重新定義屬性的重要性，提出了基于粗糙熵的屬性約簡(jiǎn)算法。

文獻(xiàn)[12]中利用相對(duì)決策熵的概念來重新定義屬性重要性，提出了約簡(jiǎn)算法FSMRDE。與粗糙集理論中人們所提出的已有信息熵模型不一樣的是，F(xiàn)SMRDE約簡(jiǎn)算法是利用Pawlak提出的粗糙度的定義來重新對(duì)相對(duì)決策熵進(jìn)行概括定義的，是對(duì)香農(nóng)信息熵的一種有效擴(kuò)展。通過實(shí)驗(yàn)數(shù)據(jù)證明，F(xiàn)SMRDE算法不僅可以生成較小的約簡(jiǎn)，而且所生成的分類器也具有更高的分類精度。特別地，F(xiàn)SMRDE算法的計(jì)算開銷要小于現(xiàn)有的基于信息熵的屬性約簡(jiǎn)算法，從而使得該算法更適合于處理大規(guī)模數(shù)據(jù)集。

雖然FSMRDE算法具有很多優(yōu)點(diǎn)，但是文獻(xiàn)[12]中所定義的相對(duì)決策熵只使用了粗糙度這一概念。粗糙度通常被用來度量知識(shí)的完備性，但它卻不能有效度量知識(shí)的粒度大小，這是因?yàn)閷?duì)任意X?U, X的粗糙度只與X的邊界區(qū)域以及X的上近似有關(guān)，缺乏對(duì)負(fù)區(qū)域信息變化的刻畫能力。相應(yīng)地，相對(duì)決策熵也不能反映出知識(shí)的粒度大小。很多時(shí)候，即使知識(shí)的粒度變小了(即知識(shí)的劃分粒度變細(xì))，相對(duì)決策熵也不會(huì)發(fā)生任何變化。這明顯是不合理的。因?yàn)殪赝ǔ１硎鞠到y(tǒng)的不確定性，當(dāng)知識(shí)的劃分粒度變細(xì)，不確定性(即熵)應(yīng)該減少。為了避免上述問題，有必要將知識(shí)粒度這一概念引入相對(duì)決策熵中。本文將采用苗奪謙等所提出的知識(shí)粒度計(jì)算公式，將知識(shí)粒度與相對(duì)決策熵結(jié)合在一起，利用知識(shí)粒度來刻畫知識(shí)的粒度大小，并采用粗糙度來度量知識(shí)的完備性，從而得到粒度決策熵這一新的信息熵模型。因此，本文所提出的粒度決策熵模型對(duì)于粗糙集中數(shù)據(jù)集的知識(shí)粒度大小和知識(shí)的完整精確性都能夠進(jìn)行很好的度量。因此，它是對(duì)相對(duì)決策熵的一種有效擴(kuò)展。

本文將基于粒度決策熵來定義屬性重要性，并由此提出一種新的屬性約簡(jiǎn)算法ARGDE。與文獻(xiàn)[11]中的條件信息熵的算法相比較，雖然都運(yùn)用了知識(shí)熵的概念，但是算法的理論出發(fā)點(diǎn)是不一樣的。文獻(xiàn)[11]中，條件信息熵的算法是在決策屬性集對(duì)條件屬性集的條件熵的基礎(chǔ)上提出的，而在本文中ARGDE屬性約簡(jiǎn)算法是建立在條件屬性和決策屬性的粒度決策熵的基礎(chǔ)之上的，以粒度決策熵的變化量作為條件屬性對(duì)于決策的重要度，并且以此作為啟發(fā)式信息提出粒度決策熵模型。

通過證明粒度決策熵在約簡(jiǎn)過程中具有非嚴(yán)格單調(diào)性，因此能夠確保本文所提出的粒度決策熵模型在粗糙集的屬性約簡(jiǎn)過程中具有精確的合理性。另一方面，為了提高ARGDE算法的計(jì)算性能，在該算法中引入了計(jì)數(shù)排序以及增量式學(xué)習(xí)的思想，其目的就是在屬性約簡(jiǎn)的過程中使得粒度決策熵ARGDE算法能夠擁有更好的計(jì)算結(jié)果，提高約簡(jiǎn)算法的效率，與現(xiàn)在已有的約簡(jiǎn)算法相比較，ARGDE約簡(jiǎn)算法能夠取得較好的計(jì)算性能。

1 粗糙集中的有關(guān)理論介紹

把信息表中的非空有限屬性集A分為不相交的2個(gè)屬性集，一個(gè)是屬性集C，稱為條件屬性；一個(gè)是屬性集D，稱為決策屬性。這種劃分條件屬性集和決策屬性集的信息表稱為決策表，簡(jiǎn)記為DT=(U, C, D, V, f)。

定義2不可分辨關(guān)系[1-2]。對(duì)于決策表DT=(U, C, D, V, f)中的任意屬性子集B?C∪D，由屬性集B所確定的一個(gè)不可分辨關(guān)系IND(B)定義如下：

IND(B)={(x,y)∈U×U:?a∈B(f(x,a)=f(y,a))}

可以證明，IND(B)是U上的一個(gè)等價(jià)關(guān)系。等價(jià)關(guān)系IND(B)把決策表中的論域U劃分為多個(gè)等價(jià)類，所有這些等價(jià)類的集合就構(gòu)成U的一個(gè)劃分，記為U/IND(B)或U/B。

定義3上、下近似[1-2]。給定決策表DT=(U, C, D, V, f)，對(duì)任意屬性子集B?C∪D和對(duì)象子集X?U, X的B-上近似和B-下近似分別被定義為：

定義4粗糙度[1-2]。給定一個(gè)決策表DT=(U, C, D, V, f)，對(duì)于任意的屬性子集B?C∪D和對(duì)象子集X?U(X≠Φ)，定義X的B-粗糙度如下：

為了度量知識(shí)劃分的粒度大小，苗奪謙等首次提出了知識(shí)粒度的計(jì)算公式，具體定義如下。

定義5知識(shí)粒度[13]。給定一個(gè)決策表DT=(U, C, D, V, f)，對(duì)于任意的屬性子集B?C∪D，如果U/IND(B)={X1,X2,…,Xt}，則U/IND(B)的知識(shí)粒度被定義為：

2 粒度決策熵

本文在文獻(xiàn)[12]中所提出的相對(duì)決策熵模型基礎(chǔ)上，在粗糙集中定義一種新的信息熵模型——粒度決策熵，并對(duì)粒度決策熵的基本性質(zhì)進(jìn)行分析。與粗糙集中現(xiàn)有的信息熵模型不同，粒度決策熵采用粗糙集中的粗糙度以及知識(shí)粒度進(jìn)行定義。粗糙度是粗糙集中的一個(gè)重要概念，主要用來度量知識(shí)的完備性，而知識(shí)粒度則可以度量知識(shí)的粒度大小。因此，有必要將這2種知識(shí)度量機(jī)制結(jié)合在一起，從而設(shè)計(jì)出一種更加全面的信息熵模型。

定義6粒度決策熵。給定決策表DT=(U,C,D,V,f)，令U/IND(D)={Y1,Y2,…,Ym}為IND(D)對(duì)U的劃分。對(duì)任意B?C，令U/IND(B)={X1,X2,…,Xt}為IND(B)對(duì)U的劃分，將D在關(guān)系IND(B)下的粒度決策熵GDE(D,B)定義為：

從定義6可以看出，粒度決策熵同時(shí)使用粗糙度和知識(shí)粒度來進(jìn)行定義，其中前者可以度量知識(shí)的完備性，而后者可以度量知識(shí)的粒度大小。將這兩者有機(jī)地結(jié)合起來是非常有意義的，為后續(xù)的屬性約簡(jiǎn)提供了一種更加全面的屬性重要性度量機(jī)制。

下面，給出粒度決策熵的一些基本性質(zhì)。

定理2給定決策表DT=(U,C,D,V,f)，其中U={x1,x2,…,xn}。令劃分U/IND(D)={Y1,Y2,…,Ym}，對(duì)任意B?C，粒度決策熵GDE(D,B)滿足以下性質(zhì)：

2)當(dāng)U/IND(B)={{x1},{x2},…,{xn}}時(shí)，GDE(D,B)得到最小值；

3)當(dāng)U/IND(D)={{x1},{x2},…,{xn}}并且U/IND(B)={U}時(shí)，GDE(D,B)得到最大值。

證明：

當(dāng)B為U上的論域關(guān)系時(shí)：

2)當(dāng)U/IND(B)={{x1},{x2},…,{xn}}時(shí)，由定義3可知，對(duì)任意的Yi∈U/IND(D)(1im),Yi的B-上近似和B-下近似都等于Yi自身，從而使得屬性集B的粗糙度又由于因此，可以得出GDE(D,B)=0。在此情形下，GDE(D,B)得到最小值0。

3)當(dāng)U/IND(D)={{x1},{x2},…,{xn}}并且U/IND(B)={U}時(shí)，由定義3和定義4可知，對(duì)于任意Yi∈U/IND(D)(1im)，ρB(Yi)=1并且知識(shí)粒度由于因此，可以得出GDE(D,B)=m=n。在此情形下，GDE(D,B)得到最大值n。

推論1給定決策表DT=(U,C,D,V,f)，對(duì)任意W?C,Z?C，如果W?Z，那么GDE(D,W)GDE(D,Z)。

定義7基于粒度決策熵的屬性重要性。給定決策表DT=(U,C,D,V,f)，對(duì)于任意B?C和a∈C-B，將屬性a在決策表DT中相對(duì)于B和D的重要性定義為：

Sig(a,B,D)=GDE(D|B)-GDE(D|B∪{a})

3 基于粒度決策熵的屬性約簡(jiǎn)算法ARGDE

由于在屬性約簡(jiǎn)的過程中要對(duì)屬性集B對(duì)于論域U的劃分進(jìn)行很多次的計(jì)算，因此為了使本文約簡(jiǎn)算法的時(shí)間復(fù)雜度和空間復(fù)雜度能夠降低，利用一種新的理論方法即計(jì)數(shù)排序的方法來解決這問題。

為了進(jìn)一步降低算法ARGDE的計(jì)算復(fù)雜度，首先提出一種增量式計(jì)算劃分U/IND(B)的算法。

算法1增量式計(jì)算U/IND(B)

輸入：給定的決策表DT=(U,C,D,V,f)，任意B?C∪D，以及之前計(jì)算出的劃分U/IND(B-{a})={E1,E2,…,Ek}，其中a∈B。

輸出：U/IND(B)。

Step1初始化：令U/IND(B)=Φ。

Step2對(duì)任意1ik，循環(huán)執(zhí)行：

Step2.1采用計(jì)數(shù)排序的方法計(jì)算劃分Ei/IND({a})，其中Ei∈U/IND(B-{a})；

Step2.2令U/IND(B)=U/IND(B)∪Ei/IND({a})。

Step3返回U/IND(B)。

在最壞的情況下，算法1的時(shí)間復(fù)雜度和空間復(fù)雜度都為O(|U|)。

通常，如果采用計(jì)數(shù)排序的方法來計(jì)算劃分U/IND(B)，則其時(shí)間復(fù)雜度為O(|U|×|B|)。然而，在算法1中，為了進(jìn)一步降低計(jì)算U/IND(B)的時(shí)間開銷，充分利用了之前已經(jīng)計(jì)算出的結(jié)果U/IND(B-{a})={E1,E2,…,Ek}，從而使得計(jì)算U/IND(B)的時(shí)間復(fù)雜度僅為O(|U|)。

算法2粒度決策熵GDE

輸入：給定的決策表DT=(U,C,D,V,f)，任意B?C，以及3個(gè)劃分：U/IND(B)={X1,X2,…,Xt},U/IND(D)={Y1,Y2,…,Ym}和U/IND(B∪D)。

輸出：粒度決策熵GDE(D,B)。

Step1初始化：對(duì)任意1it,令flag[i]=F，并且對(duì)任意Xi∈U/IND(B)，令I(lǐng)(Xi)表示Xi的編號(hào)。

Step2對(duì)任意x∈U，分別利用劃分U/IND(B)和U/IND(B∪D)來計(jì)算等價(jià)類[x]B和[x]B∪D的勢(shì)。

Step3對(duì)任意1jm，循環(huán)執(zhí)行：

Step3.1令number1=0；

Step3.2對(duì)任意x∈Yj，若|[x]B∪D|=|[x]B|并且flag[I([x]B)]=F，那么令：

number1=number1+|[x]B|

flag[I([x]B)]=T

Step3.3令LA[j]=number1。

Step4對(duì)于任意1it，令flag[i]=F。

Step5對(duì)于任意1jm，循環(huán)執(zhí)行：

Step5.1令number2=0；

Step5.2對(duì)任意x∈Yi，若flag[I([x]B)]=F，則令：

number2=number2+|[x]B|

flag[I([x]B)]=T

Step5.3令UA[j]=number2；

Step5.4對(duì)任意x∈Yi，若flag[I([x]B)]=T，則令flag[I([x]B)]=F。

Step7對(duì)任意1jm，循環(huán)執(zhí)行：

Step7.1令ρB(Yj)=1-(LA[j]/UA[j])；

Step7.2令GDE(D,B)=GDE(D,B)+ρB(Yj)log2(ρB(Yj)+1)。

Step8令GDE(D,B)=GK(B)×GDE(D,B)。

Step9返回GDE(D,B)。

在最壞的情況下，算法2的時(shí)間復(fù)雜度和空間復(fù)雜度均為O(|U|)。

算法3ARGDE

輸入：決策表DT=(U,C,D,V,f)。

輸出：約簡(jiǎn)RED。

Step1初始化：令RED為空集，Core為空集。

Step2利用計(jì)數(shù)排序的方法計(jì)算劃分U/IND(C),U/IND(D)和U/IND(C∪D)。

Step3利用算法2計(jì)算粒度決策熵GDE(D,C)。

Step4對(duì)于任意a∈C，反復(fù)執(zhí)行：

Step4.1利用計(jì)數(shù)排序的方法計(jì)算劃分U/IND(C-{a})和U/IND((C-{a})∪D)；

Step4.2利用算法2計(jì)算粒度決策熵GDE(D,C-{a})；

Step4.3如果GDE(D,C)≠GDE(D,C-{a})，則令Core=Core∪{a}。

Step5令RED=Core表示當(dāng)前的約簡(jiǎn)。如果RED為空集，則令TEM=GDE(D,C)+1；否則，先計(jì)算劃分U/IND(RED)和U/IND(RED∪D)，然后，再利用算法2計(jì)算GDE(D,RED)，并且令TEM=GDE(D,RED)。

Step6若GDE(D,C)≠TEM，則循環(huán)執(zhí)行：

Step6.1對(duì)任意a∈C-RED，循環(huán)執(zhí)行：

Step6.1.1基于U/IND(RED)和U/IND(RED∪D)，增量式計(jì)算U/IND(RED∪{a})和U/IND(RED∪{a}∪D)；

Step6.1.2利用算法2來計(jì)算GDE(D,RED∪{a})，從而得到屬性a的重要性Sig(a,RED,D)；

Step6.2從C-RED中選取屬性重要性最大的屬性b(若有多個(gè)，則隨機(jī)選取一個(gè))；

Step6.3令TEM=GDE(D,RED∪),RED=RED∪。

Step7返回約簡(jiǎn)RED。

算法3不僅采用了計(jì)數(shù)排序的方法來計(jì)算劃分U/IND(B)(其中，B?C)，而且還采用了增量式方法，從而使得其計(jì)算開銷非常小。

在最壞的情況下，算法3的時(shí)間復(fù)雜度為O(|C|2×|U|)，空間復(fù)雜度為O(|C|×|U|)。

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

為了能夠得出粒度決策熵的屬性約簡(jiǎn)算法對(duì)于現(xiàn)有的其他約簡(jiǎn)算法的性能比較結(jié)果，在數(shù)個(gè)UCI數(shù)據(jù)集上做了實(shí)驗(yàn)對(duì)比[14]：1)Tic-tac-toe endgame (Tic); 2)Wisconsin breast cancer (Breast); 3)Zoo; 4)Mushroom (Mush); 5)Congressional voting records (Vote); 6)Lymphography (Lymph); 7)Soybean-small (Soyb)。這7個(gè)數(shù)據(jù)集的詳細(xì)描述如表1所示。

表1 UCI數(shù)據(jù)集

數(shù)據(jù)集數(shù)據(jù)集大小屬性個(gè)數(shù)Tic9589Breast6999Zoo10116Mush812422Vote30016Lymph14818Soyb4735

ARGDE約簡(jiǎn)算法的具體實(shí)現(xiàn)主要是采用Java語言，在實(shí)驗(yàn)的過程中所用到的硬件環(huán)境具體如下：2.5 GHz Intel處理器，8.0 GB內(nèi)存。在上述7個(gè)UCI數(shù)據(jù)集上，分別比較POSAR(基于正區(qū)域的約簡(jiǎn)算法)[15]、DISMAR(基于分辨矩陣的約簡(jiǎn)算法)[16]、CIQ(基于條件信息量的約簡(jiǎn)算法)[17]、GAAR(基于遺傳算法的約簡(jiǎn)算法)[11]以及PSORSAR(基于粒子群優(yōu)化和粗糙集的約簡(jiǎn)算法)[18]與本文算法(ARGDE)的性能。對(duì)于算法POSAR，DISMAR，CIQ，GAAR和PSORSAR，它們的實(shí)驗(yàn)結(jié)果可以從文獻(xiàn)[18]中得到。

首先，利用數(shù)據(jù)挖掘平臺(tái)Weka對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，采用等寬區(qū)間(Equal Width Binning, EW)離散化算法對(duì)7個(gè)數(shù)據(jù)集進(jìn)行離散化，其中區(qū)間數(shù)設(shè)置為5。然后，利用不同的約簡(jiǎn)算法在各個(gè)離散化之后的數(shù)據(jù)集上計(jì)算約簡(jiǎn)，同時(shí)對(duì)于不同算法得出的約簡(jiǎn)結(jié)果進(jìn)行比較，表2羅列了不同的屬性約簡(jiǎn)算法在數(shù)個(gè)不一樣的數(shù)據(jù)集合上的約簡(jiǎn)比較結(jié)果。

表2 各屬性約簡(jiǎn)算法的約簡(jiǎn)結(jié)果對(duì)比

數(shù)據(jù)集屬性約簡(jiǎn)集中屬性的數(shù)目POSARDISMARPSORSARGAARCIQARGDETic888888Breast454444Zoo555655Mush564544Vote988988Lymph677866Soyb222222

從表2可以看出，在所有的數(shù)據(jù)集上，ARGDE算法都能夠獲得最小約簡(jiǎn)。因此，從約簡(jiǎn)的大小來看，ARGDE算法的性能要優(yōu)于現(xiàn)有的算法。

下面比較不同約簡(jiǎn)算法的分類精度。本文采用Wang等人所提出的實(shí)驗(yàn)驗(yàn)證做法，也就是在實(shí)驗(yàn)中當(dāng)要度量每一個(gè)屬性約簡(jiǎn)結(jié)果的分類精度時(shí)，利用Wang等人提出的十折交叉實(shí)驗(yàn)的做法來驗(yàn)證，然后采用RSES系統(tǒng)中的LEM2算法來提取規(guī)則，再用提取的這些規(guī)則對(duì)要進(jìn)行測(cè)試的數(shù)據(jù)集進(jìn)行測(cè)試實(shí)驗(yàn)(如果在測(cè)試的過程中出現(xiàn)了沖突，可以通過RSES系統(tǒng)中的Standard Voting方法來解決出現(xiàn)的沖突問題)[19]。關(guān)于分類精度具體的實(shí)驗(yàn)結(jié)果如表3所示。

表3 各屬性約簡(jiǎn)算法的分類精度對(duì)比

數(shù)據(jù)集各屬性約簡(jiǎn)算法的分類精度/%POSARDISMARPSORSARGAARCIQARGDETic94.4286.2196.3293.0596.3397.40Breast95.9495.9495.8095.6598.6398.80Zoo96.093.6796.092.097.7599.4Mush10010099.70100100100Vote94.3393.6795.3394.097.9498.10Lymph85.7172.1475.7170.081.582.4Soyb10010010097.50100100

從表3中可以得出，相較于其他5種約簡(jiǎn)算法，除了Lymph數(shù)據(jù)集以外，ARGDE算法在大多數(shù)數(shù)據(jù)集上都能取得最高的分類精度。這表明，從分類性能的角度，ARGDE算法也要優(yōu)于現(xiàn)有的算法。

通過實(shí)驗(yàn)可以發(fā)現(xiàn)，在Lymph數(shù)據(jù)集上，ARGDE算法要比POSAR算法的分類性能低一些，這是因?yàn)樵贚ymph數(shù)據(jù)集中有多個(gè)離群點(diǎn)，這些離群點(diǎn)的存在影響了ARGDE算法的分類性能。而對(duì)于POSAR算法，所受的干擾要小一些。所以，POSAR算法的分類精度要比ARGDE算法高一些。針對(duì)這一問題，可以考慮在進(jìn)行屬性約簡(jiǎn)之前，利用離群點(diǎn)檢測(cè)的方法把離群點(diǎn)找出來，盡量避免離群點(diǎn)對(duì)ARGDE算法的分類性能的影響。

5 結(jié)束語

本文將知識(shí)粒度的概念引入相對(duì)決策熵中，從而得到了有關(guān)粒度決策熵的新模型。在粒度決策熵的基礎(chǔ)上，對(duì)屬性重要度這一概念進(jìn)行了重新的概括總結(jié)。同時(shí)，依據(jù)粒度決策熵的模型得出了新的有關(guān)屬性約簡(jiǎn)的ARGDE算法。ARGDE算法由于采用了增量式學(xué)習(xí)和計(jì)數(shù)排序的思想，其計(jì)算開銷要小于現(xiàn)有的算法。通過在多個(gè)UCI數(shù)據(jù)集上的實(shí)驗(yàn)，驗(yàn)證了ARGDE算法的性能。相對(duì)于現(xiàn)有的約簡(jiǎn)算法，本文提出的ARGDE算法在屬性約簡(jiǎn)結(jié)果和算法的分類精度方面都能取得更好的結(jié)果。一方面，ARGDE算法能夠得到比較小的屬性約簡(jiǎn)集；另一方面，在屬性約簡(jiǎn)的分類性能比較的過程中也能夠取得比較好的結(jié)果。

在接下來的工作中，主要是考慮把粒度決策熵ARGDE算法應(yīng)用到模糊粗糙集或鄰域粗糙集中，設(shè)計(jì)出新的算法，可以對(duì)粗糙集中連續(xù)型的數(shù)據(jù)集進(jìn)行直接處理，而不是在對(duì)數(shù)據(jù)進(jìn)行離散化后才可以對(duì)數(shù)據(jù)進(jìn)行進(jìn)一步的處理，提高算法的效率，優(yōu)化算法的性能。

參考文獻(xiàn)：

[1] Pawlak Z. Rough sets[J]. International Journal of Parallel Programming, 1982,11(5):341-356.

[2] Pawlak Z. RoughSets: Theoretical Aspects of Reasoning About Data[M]. Dordrecht: Kluwer Academic Publishers, 1991.

[3] 張文修,吳偉志,梁吉業(yè),等. 粗糙集理論與方法[M]. 北京:科學(xué)出版社, 2001.

[4] 馮林,羅芬,方丹,等. 基于改進(jìn)擴(kuò)展正域的屬性核與屬性約簡(jiǎn)方法[J]. 山東大學(xué)學(xué)報(bào)(理學(xué)版), 2012,47(1):72-76.

[5] 申雪芬,謝珺,劉海峰,等. 一種改進(jìn)的基于相對(duì)正域的增量式屬性約簡(jiǎn)算法[J]. 廣西師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013,31(3):45-50.

[6] 楊波,徐章艷,舒文豪. 基于差別矩陣的完備屬性約簡(jiǎn)算法[J]. 計(jì)算機(jī)工程, 2011,37(16):51-53.

[7] 葛浩,李龍澍,楊傳健. 基于簡(jiǎn)化差別矩陣的增量式屬性約簡(jiǎn)[J]. 四川大學(xué)學(xué)報(bào)(工程科學(xué)版), 2013,45(1):116-124.

[8] 葛浩,李龍澍,楊傳健. 基于差別集的啟發(fā)式屬性約簡(jiǎn)算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2013,34(2):380-385.

[9] 陳媛,楊棟. 基于信息熵的屬性約簡(jiǎn)算法及應(yīng)用[J]. 重慶理工大學(xué)學(xué)報(bào)(自然科學(xué)), 2013,27(1):42-46.

[10] 呂林霞,趙錫英,唐占紅. 一種基于信息熵的信息系統(tǒng)屬性約簡(jiǎn)算法[J]. 自動(dòng)化與儀器儀表, 2013(5):197-199.

[11] 王國胤,于洪,楊大春. 基于條件信息熵的決策表約簡(jiǎn)[J]. 計(jì)算機(jī)學(xué)報(bào), 2002,25(7):759-766.

[12] Jiang Feng, Sui Yuefei, Zhou Lin. A relative decision entropy-based feature selection approach[J]. Pattern Recognition, 2015,48(7):2151-2163.

[13] 張偉,徐章艷,王曉宇. 一種結(jié)合概率啟發(fā)信息和知識(shí)粒度的屬性約簡(jiǎn)算法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2013,30(7):43-45.

[14] Hettich S, Bay S D. The UCI KDD Archive[DB/OL]. http://kdd.ics.uci.edu, 1999-01-10.

[15] 江峰,王莎莎,杜軍威,等. 基于近似決策熵的屬性約簡(jiǎn)[J]. 控制與決策, 2015,30(1):65-70.

[16] Hu Keyun, Lu Yuchang, Shi Chunyi. Feature ranking in rough sets[J]. AI Communications, 2003,16(1):41-50.

[17] 李鴻. 基于條件信息量的知識(shí)相對(duì)約簡(jiǎn)算法[J]. 中國礦業(yè)大學(xué)學(xué)報(bào), 2005,34(3):378-382.

[18] Wang Xiangyang, Yang Jie, Teng Xiaolong, et al. Feature selection based on rough sets and particle swarm optimization[J]. Pattern Recognition Letters, 2007,28(4):459-471.

[19] Skowron A, Bazan J, Son N H, et al. RSES 2.2 User’s Guide[EB/OL]. http://logic.mimuw.edu.pl/rses, 2005-01-19.