鄰域互信息熵的混合型數(shù)據(jù)決策代價(jià)屬性約簡(jiǎn)

熊菊霞，吳盡昭，王秋紅

1(中國(guó)科學(xué)院 成都計(jì)算機(jī)應(yīng)用研究所，成都 610041)

2(中國(guó)科學(xué)院大學(xué) 成都計(jì)算機(jī)應(yīng)用研究所，北京 100049)

3(廣西民族大學(xué) 數(shù)學(xué)與物理學(xué)院，南寧 530006)

1 引 言

粗糙集理論是人工智能和智能計(jì)算領(lǐng)域的重要研究?jī)?nèi)容[1].由于現(xiàn)實(shí)環(huán)境下數(shù)據(jù)內(nèi)容的復(fù)雜性，學(xué)者們將傳統(tǒng)的粗糙集理論進(jìn)行推廣，提出了決策粗糙集模型[2]，該模型通過引入閾值來限定粗糙集上下近似的范圍，使得具有更高的泛化性能.決策粗糙集模型已成為目前粗糙集理論的研究熱點(diǎn)[3，4].

屬性約簡(jiǎn)是粗糙集理論的重要應(yīng)用，在傳統(tǒng)的粗糙集理論中，屬性約簡(jiǎn)的目的是為了刪除數(shù)據(jù)集中的不相關(guān)屬性和冗余屬性，使得提高數(shù)據(jù)的分類性能[5，6].然而在決策粗糙集中，決策區(qū)域不滿足屬性變化的單調(diào)性，因此傳統(tǒng)的屬性約簡(jiǎn)算法在決策粗糙集下并不適用[7].由于決策粗糙集是建立在代價(jià)理論基礎(chǔ)上粗糙集模型，Jia等[8]學(xué)者在決策粗糙集模型中提出了最小化決策代價(jià)的屬性約簡(jiǎn)方法，理論分析了這種屬性約簡(jiǎn)方式的合理性.在Jia的基礎(chǔ)上，其他學(xué)者進(jìn)一步地提出了多種推廣的屬性約簡(jiǎn)算法，例如Song等[9]學(xué)者在模糊數(shù)據(jù)環(huán)境下提出了最小化代價(jià)的屬性約簡(jiǎn)算法，彭莉莎等[10]學(xué)者提出了面向特定類的最小化代價(jià)屬性約簡(jiǎn)，Li等[11]學(xué)者將決策粗糙集推廣至混合型數(shù)據(jù)，提出一種鄰域決策粗糙集的最小化代價(jià)屬性約簡(jiǎn)算法.雖然決策粗糙集不滿足屬性變化的單調(diào)性，但是學(xué)者們提出了多種非單調(diào)性的屬性約簡(jiǎn)，例如姚晟等[12]學(xué)者提出一種決策粗糙集的非單調(diào)決策區(qū)域的屬性約簡(jiǎn)，Gao等[13]學(xué)者提出一種最大決策熵模型，并利用該熵模型去設(shè)計(jì)屬性約簡(jiǎn)算法.

然而目前的決策粗糙集屬性約簡(jiǎn)算法大多都是基于單獨(dú)的視角進(jìn)行屬性約簡(jiǎn)，即決策代價(jià)或分類性能，實(shí)際應(yīng)用中可能需要同時(shí)考慮多種情形[14]，并且目前基于分類性能的屬性約簡(jiǎn)都是直接利用啟發(fā)式函數(shù)進(jìn)行屬性約簡(jiǎn)結(jié)果的搜索，沒有考慮所選擇屬性之間的獨(dú)立性，使得最終的結(jié)果可能包含一些冗余屬性，因此也存在一定的缺陷.受這些局限因素的驅(qū)使，本文將對(duì)聯(lián)合決策代價(jià)和分類性能兩方面的屬性約簡(jiǎn)進(jìn)行探索，并且盡可能減少屬性約簡(jiǎn)結(jié)果中的冗余屬性.

互信息熵是度量屬性之間依賴程度的一種常用方法，并且條件互信息熵也是對(duì)屬性之間獨(dú)立性的一種重要評(píng)估，是構(gòu)造屬性約簡(jiǎn)的一種重要方法[15-17].本文在混合型鄰域粗糙集模型的基礎(chǔ)上，分別提出了鄰域信息熵、鄰域聯(lián)合熵和鄰域條件熵，然后進(jìn)一步提出了鄰域互信息熵以及鄰域條件互信息熵，理論分析了它們之間的關(guān)系，然后將鄰域互信息熵理論融入鄰域決策粗糙集的決策代價(jià)屬性約簡(jiǎn)中，提出了基于鄰域互信息熵的混合型數(shù)據(jù)決策代價(jià)屬性約簡(jiǎn)算法，該屬性約簡(jiǎn)方法選擇出的屬性子集可同時(shí)兼顧決策代價(jià)和分類性能，由于是利用鄰域互信息熵去選擇屬性，使得屬性約簡(jiǎn)結(jié)果中的屬性具有很高的獨(dú)立性，仿真實(shí)驗(yàn)表明了所提出屬性約簡(jiǎn)算法的優(yōu)越性.

2 相關(guān)理論

設(shè)混合型信息系統(tǒng)為S=(U，AT=C∪D)，其中論域U={x1，x2，…，xn}，xi(1≤i≤n)稱為信息系統(tǒng)的對(duì)象.條件屬性集C={a1，a2，…，am}，其中C=Ca∪Cn，Ca和Cn分別稱為條件屬性集C中的離散型屬性子集和連續(xù)型屬性子集.決策屬性D=j5i0abt0b表示信息系統(tǒng)S的類特征，信息系統(tǒng)中的每個(gè)對(duì)象都有一個(gè)唯一的類標(biāo)記.對(duì)于?x∈U在屬性a∈C下的屬性值表示為a(x).

定義1[18].設(shè)混合型信息系統(tǒng)S=(U，AT=C∪D)，屬性子集A?C并且A=Aa∪An，對(duì)于鄰域半徑δ，由屬性子集A確定的鄰域關(guān)系定義為:

(?a∈Ac，a(x)=a(y))∧dAn(x，y)≤δ}.

P(D-|δA(x))=1-P(D+|δA(x)).

在鄰域決策粗糙集模型中[11]，當(dāng)對(duì)象x屬于對(duì)象集D+時(shí)，λPP，λBP和λNP分別表示對(duì)象x劃分入D+的正區(qū)域POS(D+)、邊界域BUN(D+)和負(fù)區(qū)域NEG(D+)所產(chǎn)生的代價(jià)；類似地，當(dāng)對(duì)象x不屬于對(duì)象集D+時(shí)，即對(duì)象x屬于D-，λPN，λBN和λNN分別表示對(duì)象x劃分入D-的正區(qū)域POS(D-)、邊界域BUN(D-)和負(fù)區(qū)域NEG(D-)所產(chǎn)生的代價(jià).

那么對(duì)象x∈U采取不同動(dòng)作的決策代價(jià)表示為：

1)CostP(x)=λPP·P(D+|δA(x))+λPN·P(D-|δA(x))；

2)CostB(x)=λBP·P(D+|δA(x))+λBN·P(D-|δA(x))；

3)CostN(x)=λNP·P(D+|δA(x))+λNN·P(D-|δA(x)).

根據(jù)貝葉斯最小化決策代價(jià)規(guī)則，那么有：

1)當(dāng)CostP(x)≤CostB(x)且CostP(x)≤CostN(x)時(shí)，即P(D+|δA(x))≥α且P(D+|δA(x))≥γ，則x∈POS(D+).

2)當(dāng)CostB(x)≤CostP(x)且CostB(x)≤CostN(x)時(shí)，即P(D+|δA(x))≤α且P(D+|δA(x))≥β，則x∈BUN(D+).

3)當(dāng)CostN(x)≤CostP(x)且CostN(x)≤CostB(x)時(shí)，即P(D+|δA(x))≤β且P(D+|δA(x))≤γ，則x∈NEG(D+).

其中：

1)當(dāng)P(D+|δA(x))≥α?xí)r，那么x∈POS(D+)；

2)當(dāng)β

3)當(dāng)P(D+|δA(x))≤β時(shí)，那么x∈NEG(D+).

基于上述決策條件，接下來可以得到整個(gè)信息系統(tǒng)中所有對(duì)象進(jìn)行決策時(shí)所產(chǎn)生的的代價(jià)結(jié)果.

其中P(x)=P(D+|δA(x))；1-P(x)=P(D-|δA(x)).

考慮到正確的決策結(jié)果通常不產(chǎn)生任何代價(jià)，那么λPP=λNN=0.所以有:

利用定義3所示的決策代價(jià)，學(xué)者們定義了一種最小化決策代價(jià)的屬性約簡(jiǎn).

定義4[11].設(shè)混合型信息系統(tǒng)S=(U，AT=C∪D)，鄰域半徑為δ，若屬性子集red?C為信息系統(tǒng)S的最小決策代價(jià)屬性約簡(jiǎn)，那么當(dāng)且僅當(dāng)：

2)?red′?red，Costred′(U)>Costred(U).

在各類經(jīng)典的粗糙集模型中，其中屬性約簡(jiǎn)大多基于決策區(qū)域作為評(píng)價(jià)準(zhǔn)則，即約簡(jiǎn)結(jié)果保持決策區(qū)域的大小不變.然而在決策粗糙集中，決策區(qū)域的劃分是根據(jù)對(duì)象作出決策的最小代價(jià)來確定，因此在決策粗糙集中，基于最小化代價(jià)定義屬性約簡(jiǎn)是合理的[11].

3 混合型信息系統(tǒng)下鄰域互信息熵的決策代價(jià)屬性約簡(jiǎn)

3.1 鄰域互信息熵模型

Jia等[8]學(xué)者提出的最小化代價(jià)屬性約簡(jiǎn)只考慮風(fēng)險(xiǎn)，而不考慮條件屬性子集對(duì)決策屬性的分類能力.Yu等[19]學(xué)者在最小化代價(jià)屬性約簡(jiǎn)中引入了屬性重要性，但是這一屬性重要度定義只考慮了單個(gè)屬性對(duì)決策的分類能力.然而在一些實(shí)際的數(shù)據(jù)集中，條件屬性之間往往存在著很強(qiáng)的相關(guān)性，可能存在兩個(gè)屬性，它們都具有較強(qiáng)的分類能力，但結(jié)合在一起不能提高分類性能.為了改善這一局限，本節(jié)將使用條件互信息熵的來定義屬性的重要性.

互信息在含噪聲的數(shù)據(jù)環(huán)境中具有良好得魯棒性.在文獻(xiàn)[20]中，Hu等學(xué)者將鄰域融入信息熵，提出了連續(xù)型數(shù)據(jù)的信息熵模型，本文將該模型在混合型數(shù)據(jù)下進(jìn)行推廣，提出混合型信息系統(tǒng)下的信息熵以及互信息熵模型.

對(duì)于?x∈U滿足{x}?δA(x)?U，因此鄰域信息熵滿足0≤NEδ(A)≤logn，其中NEδ(A)=logn當(dāng)且僅當(dāng)?x∈U，δA(x)={x}.其中NEδ(A)=0當(dāng)且僅當(dāng)?x∈U，δA(x)=U.

類似于定義5，鄰域聯(lián)合信息熵同樣滿足關(guān)系0≤NEδ(A，B)≤logn.

定理1.NEδ(B|A)=NEδ(A，B)-NEδ(A).

證明：NEδ(A，B)-NEδ(A)=

定理2.設(shè)混合型信息系統(tǒng)為S=(U，AT=C∪D)，|U|=n，屬性子集A，B?C，那么如下等式成立：

1)NEδ(B；A)=NEδ(A；B)；

2)NEδ(B；A)=NEδ(A)+NEδ(B)-NEδ(A，B)；

3)NEδ(B；A)=NEδ(B)-NEδ(B|A)=NEδ(A)-NEδ(A|B)；

證明：

1)根據(jù)定義8，即：

2)根據(jù)定義5和定義6有：

NEδ(A)+NEδ(B)-NEδ(A，B)=

3)根據(jù)式(1)和式(2)，聯(lián)合定理1，可以得到式(3)成立.

在鄰域互信息熵的基礎(chǔ)上，可以進(jìn)一步推廣得到鄰域條件互信息熵.

定義9.設(shè)混合型信息系統(tǒng)為S=(U，AT=C∪D)，|U|=n，屬性子集P，Q，R?C，那么定義屬性集R下P與Q的鄰域條件互信息熵為:

定理3.NEδ(P；Q|R)=NEδ(P，R)+NEδ(Q，R)-NEδ(R)-NEδ(P，Q，R)；

證明：

NEδ(P，R)+NEδ(Q，R)-NEδ(R)-NEδ(P，Q，R)=

圖1的兩幅圖展示出了各類熵之間的相互關(guān)系，其中可以看出鄰域互信息熵表示了兩個(gè)屬性集之間相互依賴的程度，而鄰域條件互信息熵可以反映出其中兩個(gè)屬性之間的獨(dú)立程度.

圖1 各類熵之間的關(guān)系示意圖

3.2 鄰域互信息熵的決策代價(jià)屬性約簡(jiǎn)算法

鄰域互信息熵可以很好地表達(dá)混合型信息系統(tǒng)中兩個(gè)屬性之間的依賴程度，并且具有很高的魯棒性.因此我們可以通過鄰域互信息熵去定義混合型信息系統(tǒng)中條件屬性子集與決策屬性之間的關(guān)聯(lián)程度，那么在屬性約簡(jiǎn)的搜索過程中，需要選擇出依賴程度最大的屬性子集，即：

maxφ(A，D)；

φ(A，D)即為屬性子集A?C中所有屬性與決策屬性D之間鄰域互信息熵的平均值，通過這個(gè)平均值來表達(dá)屬性子集A整體關(guān)于決策屬性D的依賴程度.

通過鄰域互信息熵選擇出的屬性子集雖然有著較高的依賴程度，但是選擇的屬性子集中可能存在著冗余屬性，即屬性子集中的兩個(gè)屬性之間可能存在著依賴關(guān)系，刪除其中任意一個(gè)而不會(huì)對(duì)最終的依賴度產(chǎn)生影響.因此接下來利用鄰域條件互信息熵去評(píng)估屬性子集中屬性之間的獨(dú)立程度，即選擇出的屬性子集需滿足：

maxφ(A，D)

由于NE(aj；D|ai)和NE(ai；D|aj)是通過鄰域條件互信息熵來反映屬性ai與aj之間的獨(dú)立程度，即獨(dú)立程度大小可以表示為:

NE(aj；D|ai)+NE(ai；D|aj).

那么對(duì)于屬性子集A，任意選擇其中兩個(gè)屬性進(jìn)行獨(dú)立程度的計(jì)算，將所有選擇結(jié)果的獨(dú)立程度累加起來，來衡量屬性子集A的獨(dú)立性，即:

最后再求取平均值，也就是:

因此φ(A，D)可以度量出屬性子集A?C中屬性之間的平均獨(dú)立程度，其值越大說明屬性子集A中屬性之間的相互獨(dú)立程度越高.

那么對(duì)于鄰域互信息熵的屬性約簡(jiǎn)，這里希望選擇出的屬性約簡(jiǎn)子集A滿足:

max[φ(A，D)+φ(A，D)].

利用鄰域互信息熵作為屬性重要度的評(píng)估，這里定義一種屬性重要度函數(shù)，具體如定義10所示.

定義10.設(shè)混合型信息系統(tǒng)為S=(U，AT=C∪D)，鄰域半徑為δ和屬性子集A?C，屬性?a∈C-A關(guān)于屬性子集A的鄰域互信息熵屬性重要度定義為:

sig(a，A)=ηδ(A∪{a}，D)-ηδ(A，D)，

這里的ηδ(A，D)=φ(A，D)+φ(A，D).

傳統(tǒng)決策粗糙集下的屬性約簡(jiǎn)主要集中于屬性子集的決策代價(jià)，而未考慮屬性子集的分類能力，因此接下來將本文提出的鄰域互信息熵屬性重要度引入決策代價(jià)屬性約簡(jiǎn)中，提出一種新的改進(jìn)屬性約簡(jiǎn)算法.

算法1.基于鄰域互信息熵的混合型數(shù)據(jù)決策代價(jià)屬性約簡(jiǎn)算法.

輸入：混合型信息系統(tǒng)S=(U，AT=C∪D)，鄰域半徑δ，決策代價(jià).

輸出：屬性約簡(jiǎn)結(jié)果red.

1.初始化red=?，ηδ(?，D)=0.

2.對(duì)于條件屬性集中的每個(gè)屬性ai∈C，其中i=1，2，…，|C|.計(jì)算屬性ai的鄰域互信息熵屬性重要度sig(ai，red)=ηδ(red∪{ai}，D)-ηδ(red，D)，

找出sig(ai，red)最大值對(duì)應(yīng)的屬性，記為amax，并且red←red∪{amax}.

3.計(jì)算論域U在屬性集red下的鄰域粒化，并根據(jù)定義3得到整個(gè)論域U的決策代價(jià)Costred(U).

4.對(duì)于屬性?a∈C-red，計(jì)算其鄰域互信息熵的屬性重要度sig(a，red)，選擇C-red中屬性重要度最大的屬性amax，并且red′←red∪{amax}.

5.計(jì)算屬性集red′下整個(gè)論域U的決策代價(jià)Costred′(U)，若Costred′(U)≤Costred(U)，那么進(jìn)行red←red′，并且重新返回步驟4，否則進(jìn)入步驟6.

6.返回屬性約簡(jiǎn)結(jié)果red.

算法1所示的是一種啟發(fā)式方法的屬性約簡(jiǎn)算法，即通過決策代價(jià)函數(shù)和鄰域互信息熵屬性重要度一起進(jìn)行信息系統(tǒng)屬性的搜索.該算法主要通過鄰域互信息熵去搜索出與決策屬性具有較高依賴度的屬性，并且選擇出的屬性與已選擇的屬性子集具有較高地獨(dú)立性，當(dāng)該屬性能夠進(jìn)一步降低論域的決策代價(jià)時(shí)，那么將該屬性添加至屬性約簡(jiǎn)集中，重復(fù)上述流程直至完成最終的屬性搜索.算法1的計(jì)算量主要集中在鄰域互信息熵的計(jì)算和論域決策代價(jià)的計(jì)算，這些計(jì)算主要是針對(duì)對(duì)象鄰域類的計(jì)算，因此整個(gè)算法1的時(shí)間復(fù)雜度可表示為O(|C|2·|U|2).

4 實(shí)驗(yàn)分析

為了進(jìn)一步驗(yàn)證所提出屬性約簡(jiǎn)算法的有效性，本實(shí)驗(yàn)從UCI機(jī)器學(xué)習(xí)公開數(shù)據(jù)集中選取了6個(gè)數(shù)據(jù)集，具體詳情如表1所示，所列舉的這些數(shù)據(jù)集均為離散型屬性和連續(xù)型屬性混合的類型，并且將連續(xù)型屬性歸一化至[0，1]區(qū)間.本實(shí)驗(yàn)將所提出的屬性約簡(jiǎn)算法與文獻(xiàn)[11]的決策代價(jià)屬性約簡(jiǎn)算法和文獻(xiàn)[21]的鄰域粗糙熵屬性約簡(jiǎn)算法分別進(jìn)行實(shí)驗(yàn)，通過屬性約簡(jiǎn)的長(zhǎng)度、約簡(jiǎn)結(jié)果的分類精度、約簡(jiǎn)結(jié)果的決策代價(jià)以及約簡(jiǎn)用時(shí)4個(gè)方面來評(píng)價(jià)各個(gè)算法的優(yōu)劣.

表1 實(shí)驗(yàn)數(shù)據(jù)集

在本文所提出的算法中，鄰域半徑δ是一個(gè)很重要的參數(shù)，其取值的不同將會(huì)對(duì)最終的實(shí)驗(yàn)結(jié)果產(chǎn)生很大的影響，本實(shí)驗(yàn)借鑒其他學(xué)者的處理方式[11，18，21]，將鄰域半徑在一定區(qū)間內(nèi)分別取值進(jìn)行實(shí)驗(yàn)，每個(gè)鄰域半徑都會(huì)得到對(duì)應(yīng)的屬性約簡(jiǎn)結(jié)果，將該結(jié)果利用支持向量機(jī)分類器(SVM)和樸素貝葉斯分類器(NB)分別進(jìn)行分類精度評(píng)估，然后對(duì)多組數(shù)據(jù)集的結(jié)果進(jìn)行比較，選取出最佳的鄰域半徑.圖2所示的是鄰域半徑在區(qū)間[0，0.3]下間隔取值得到的分類精度結(jié)果.綜合各個(gè)數(shù)據(jù)集的結(jié)果，可以發(fā)現(xiàn)當(dāng)鄰域半徑取值為0.12左右時(shí)得到的屬性約簡(jiǎn)結(jié)果分類精度較高，因此本實(shí)驗(yàn)將鄰域半徑設(shè)置為0.12.另外本文的屬性約簡(jiǎn)算法需要確定對(duì)象分類的決策代價(jià)，本實(shí)驗(yàn)這里基于文獻(xiàn)[11]的代價(jià)關(guān)系，在0-1之間隨機(jī)進(jìn)行選取.

圖2 各個(gè)數(shù)據(jù)集不同鄰域半徑下屬性約簡(jiǎn)的分類精度結(jié)果

表2所示的是本文算法與文獻(xiàn)[11]中的算法和文獻(xiàn)[21]中的算法在各個(gè)數(shù)據(jù)集下屬性約簡(jiǎn)結(jié)果的長(zhǎng)度比較.觀察表2可以發(fā)現(xiàn)本文算法在除數(shù)據(jù)集Annealing以外有著更小的約簡(jiǎn)長(zhǎng)度，產(chǎn)生這一結(jié)果的主要原因是由于本文算法采用鄰域互信息熵去搜索屬性，每次選擇出的屬性與決策屬性具有很強(qiáng)的相關(guān)性，并且與已經(jīng)搜索到的屬性之間也具有很強(qiáng)的獨(dú)立性，最終得到的屬性約簡(jiǎn)結(jié)果包含了較少的冗余和不相關(guān)屬性，因此得到的約簡(jiǎn)屬性要更少.而其余兩種屬性約簡(jiǎn)算法，雖然是基于不同的評(píng)價(jià)策略去進(jìn)行屬性的搜索，但是均未考慮屬性的獨(dú)立性因素，因此最終的屬性約簡(jiǎn)結(jié)果包含了更多的屬性.

表2 屬性約簡(jiǎn)的長(zhǎng)度比較

表3和表4分別所示的本文算法與對(duì)比算法在每個(gè)數(shù)據(jù)集下屬性約簡(jiǎn)結(jié)果的SVM分類精度和NB分類精度比較.對(duì)比表3和表4的結(jié)果，可以發(fā)現(xiàn)文獻(xiàn)[21]的屬性約簡(jiǎn)算法在數(shù)據(jù)集Heart、Annealing和Sick下具有較高的SVM分類精度，本文算法和文獻(xiàn)[11]算法在其余數(shù)據(jù)集下具有較高的SVM分類精度；文獻(xiàn)[21]的屬性約簡(jiǎn)算法在數(shù)據(jù)集Heart、German、Sick和Abalone下具有較高的NB分類精度，本文算法在其余數(shù)據(jù)集下具有較高的NB分類精度.綜合比較起來，文獻(xiàn)[21]的算法在較多的數(shù)據(jù)集下具有更高的分類精度，這主要是由于文獻(xiàn)[21]的算法利用鄰域粗糙信息熵作為啟發(fā)式函數(shù)進(jìn)行屬性搜索，將屬性子集的分類性能作為屬性約簡(jiǎn)的重點(diǎn)，因而得到的約簡(jiǎn)結(jié)果分類性能更高，但是本文算法兼顧分類性能的同時(shí)，又考慮了屬性子集的決策代價(jià)，因而分類性能略低于文獻(xiàn)[21]的算法，但是本文算法在多數(shù)數(shù)據(jù)集下的分類精度與最高分類精度之間差距不是很大，因此說明本文算法得到的屬性約簡(jiǎn)結(jié)果同樣具有較高的分類性能.

表3 各個(gè)算法屬性約簡(jiǎn)的SVM分類精度比較(%)

表4 各個(gè)算法屬性約簡(jiǎn)的NB分類精度比較(%)

表5所示的是本文算法與對(duì)比算法在每個(gè)數(shù)據(jù)集下屬性約簡(jiǎn)結(jié)果的決策代價(jià)比較，對(duì)比表3和表4的結(jié)果可以發(fā)現(xiàn)，文獻(xiàn)[11]中的算法在數(shù)據(jù)集Horse、Heart和German下具有更低的決策代價(jià)，本文算法在數(shù)據(jù)集Annealing、Sick和Abalone下具有更低的決策代價(jià).這主要是由于本文算法和文獻(xiàn)[11]的算法都通過考慮屬性子集的決策代價(jià)進(jìn)行屬性約簡(jiǎn)，因此本文算法和文獻(xiàn)[11]的算法有著較小的決策代價(jià)，而文獻(xiàn)[21]的鄰域粗糙熵屬性約簡(jiǎn)未考慮屬性的決策代價(jià)，因此得到的屬性約簡(jiǎn)結(jié)果具有更高的決策代價(jià).

表5 各個(gè)算法屬性約簡(jiǎn)的決策代價(jià)比較

屬性約簡(jiǎn)的用時(shí)也是衡量算法性能的重要指標(biāo)，圖3所示的是本文算法和對(duì)比算法在各個(gè)數(shù)據(jù)集下屬性約簡(jiǎn)的用時(shí)比較結(jié)果.觀察圖3可以發(fā)現(xiàn)，文獻(xiàn)[11]中的屬性約簡(jiǎn)算法有著最多的約簡(jiǎn)用時(shí)，文獻(xiàn)[21]中的屬性約簡(jiǎn)算法有著最少的約簡(jiǎn)用時(shí)，本文算法的屬性約簡(jiǎn)用時(shí)介于前兩種算法之間.這主要是由于計(jì)算屬性子集的決策代價(jià)具有較多的計(jì)算量，例如首先需要計(jì)算論域在屬性子集下的鄰域?；?，然后計(jì)算每個(gè)決策類的正區(qū)域、邊界域和負(fù)區(qū)域，最后依據(jù)區(qū)域的劃分計(jì)算最終的決策代價(jià)結(jié)果，而文獻(xiàn)[21]的算法只需進(jìn)行鄰域粗糙熵的計(jì)算，因此計(jì)算量會(huì)少一些，而本文算法既進(jìn)行了決策代價(jià)的部分計(jì)算也進(jìn)行了鄰域互信息熵的計(jì)算，因此計(jì)算量介于二者之間.

圖3 各個(gè)算法屬性約簡(jiǎn)的用時(shí)比較

綜合比較本文算法與兩種對(duì)比算法，可以證明本文算法在屬性約簡(jiǎn)的長(zhǎng)度、約簡(jiǎn)結(jié)果的分類精度、約簡(jiǎn)結(jié)果的決策代價(jià)以及約簡(jiǎn)用時(shí)4個(gè)方面上具有整體更優(yōu)的屬性約簡(jiǎn)性能.

5 總 結(jié)

屬性約簡(jiǎn)是粗糙集理論的核心研究?jī)?nèi)容.傳統(tǒng)的決策粗糙集模型通過決策代價(jià)的視角進(jìn)行數(shù)據(jù)集的屬性約簡(jiǎn)，使得選擇出的屬性子集在進(jìn)行決策劃分時(shí)具有最小的分類代價(jià)，然而這種屬性約簡(jiǎn)方法未考慮屬性子集的分類性能，并且已有的算法在考慮分類性能的同時(shí)，未考慮選擇出屬性的獨(dú)立性，因而所得到的屬性約簡(jiǎn)結(jié)果具有較高的冗余性，針對(duì)這一問題，提出一種基于鄰域互信息熵的混合型數(shù)據(jù)決策代價(jià)屬性約簡(jiǎn)算法，該算法在考慮屬性約簡(jiǎn)結(jié)果的決策代價(jià)同時(shí)，利用鄰域互信息熵去選擇依賴度高且獨(dú)立性強(qiáng)的屬性，使得最終的屬性約簡(jiǎn)結(jié)果具有更高的優(yōu)越性，仿真實(shí)驗(yàn)證明了算法的有效性.在接下來的研究中，我們將進(jìn)一步探索動(dòng)態(tài)混合數(shù)據(jù)環(huán)境下的屬性約簡(jiǎn)問題.