粒化單調(diào)的條件鄰域熵及其相關(guān)屬性約簡(jiǎn)

周艷紅 張賢勇 莫智文

1(四川師范大學(xué)數(shù)學(xué)與軟件科學(xué)學(xué)院 成都 610068) 2(中國(guó)民用航空飛行學(xué)院計(jì)算機(jī)學(xué)院 四川廣漢 618307) 3 (四川師范大學(xué)智能信息與量子信息研究所 成都 610068) (zhouyanhong515@163.com)

粗糙集理論是一種有效處理不確定性問(wèn)題的新型數(shù)學(xué)工具[1]，已經(jīng)廣泛應(yīng)用于機(jī)器學(xué)習(xí)與模式識(shí)別等領(lǐng)域[2].屬性約簡(jiǎn)是粗糙集理論進(jìn)行知識(shí)發(fā)現(xiàn)與優(yōu)化處理的基礎(chǔ)，具有重要的應(yīng)用意義，近年來(lái)呈現(xiàn)諸多研究成果.文獻(xiàn)[3]提出基于正域的啟發(fā)式屬性約簡(jiǎn)算法；文獻(xiàn)[4]研究4種不同熵的屬性重要度秩保持性質(zhì)，并提出增量式屬性約簡(jiǎn)算法；文獻(xiàn)[5]基于最大依賴性、最大相關(guān)性與最小冗余性原則提出基于互信息的啟發(fā)式算法；文獻(xiàn)[6-7]利用雙量化思想探討層次約簡(jiǎn)，提出3層粒結(jié)構(gòu)(微觀底層、中觀中層、宏觀高層)的構(gòu)建方法；文獻(xiàn)[8]提出一種基于相對(duì)決策熵的屬性約簡(jiǎn)算法.

經(jīng)典粗糙集主要以等價(jià)關(guān)系與等價(jià)類為基礎(chǔ)，能夠有效處理離散型數(shù)據(jù)，但在處理連續(xù)型數(shù)據(jù)方面具有局限性.對(duì)此，鄰域粗糙集拓展經(jīng)典粗糙集并適用于數(shù)值型及混合型數(shù)據(jù)分析.文獻(xiàn)[9]提出鄰域關(guān)系，文獻(xiàn)[10]提出鄰域互信息，文獻(xiàn)[11]提出鄰域類，文獻(xiàn)[12-19]則對(duì)鄰域信息系統(tǒng)進(jìn)行了深入研究.其中，文獻(xiàn)[12]在鄰域信息系統(tǒng)中提出鄰域熵，并進(jìn)行系列研究；文獻(xiàn)[13]將Shannon 熵與鄰域熵結(jié)合提出鄰域互信息并做屬性約簡(jiǎn)；文獻(xiàn)[15]利用鄰域互信息[10]發(fā)展屬性約簡(jiǎn)；文獻(xiàn)[16]提出基于3支決策的鄰域熵與條件鄰域熵并做屬性約簡(jiǎn)；文獻(xiàn)[17]構(gòu)造基于鄰域粗糙集的多標(biāo)記分類任務(wù)的特征選擇算法；文獻(xiàn)[18]開(kāi)發(fā)基于鄰域粒化與粗糙逼近的數(shù)值屬性約簡(jiǎn)算法；文獻(xiàn)[19]利用鄰域粗糙集中的熵度量來(lái)研究基因選擇.

綜上可見(jiàn)，在鄰域粗糙集中，基于信息度量的屬性約簡(jiǎn)具有研究?jī)r(jià)值與應(yīng)用意義.事實(shí)上，鄰域熵、條件鄰域熵與鄰域互信息已經(jīng)系統(tǒng)地存在[10].但是，其中的條件鄰域熵具有粒化非單調(diào)性，不能建立約簡(jiǎn)的核與啟發(fā)式算法；此外，鑒于對(duì)數(shù)函數(shù)定義域，該條件鄰域熵沒(méi)有考慮“0概率信息項(xiàng)”，從而帶來(lái)不自然的熵值突變；進(jìn)而，這些具體情況阻礙了相關(guān)屬性約簡(jiǎn)的后續(xù)發(fā)展.本文主要針對(duì)經(jīng)典條件鄰域熵[10]及其缺陷，進(jìn)行改進(jìn)并提出具有粒化單調(diào)性的條件鄰域熵，進(jìn)而依托信息增量的可控性來(lái)研究相關(guān)的屬性約簡(jiǎn).

1 鄰域信息系統(tǒng)及條件鄰域熵

1.1 鄰域信息系統(tǒng)的基本知識(shí)

鄰域信息系統(tǒng)是鄰域粗糙集的基本背景，本節(jié)復(fù)習(xí)其基本知識(shí).

本文主要涉及鄰域決策系統(tǒng)DS.針對(duì)DS與IS，設(shè)A,B?C={c1,c2,…,cn}.

定義2[11]. 距離函數(shù).在IS中，設(shè)x,y∈U，則C的距離函數(shù)為

(1)

若p=1，dC(x,y)為Manhattan距離；若p=2，dC(x,y)為Euclidean距離；若p=∞，dC(x,y)為Chebychev距離.

距離函數(shù)在鄰域粗糙集中起著核心作用，這里dC自然誘導(dǎo)dA,dB.本文主要采用Chebychev距離(詳細(xì)計(jì)算參見(jiàn)文獻(xiàn)[20]).

定義3[11]. 鄰域和鄰域關(guān)系.在IS中，x∈U在B上的δ鄰域?yàn)?/p>

B決定的鄰域關(guān)系為

NRδ(B)={(x,y)∈U×U|dB(x,y)≤δ}.

UNRδ(B)記U上基于B的覆蓋，即由鄰域關(guān)系決定的鄰域集.

性質(zhì)1[12]. 鄰域是鄰域粗糙集中的基本粒，具有2項(xiàng)單調(diào)性質(zhì)：

基于鄰域，文獻(xiàn)[10]研究了IS中的信息度量，包括鄰域熵、條件鄰域熵與鄰域互信息等，相關(guān)定義與性質(zhì)如下.

定義4[10]. 鄰域熵.在IS中，B的鄰域熵為

(2)

定義5[10]. 條件鄰域熵、聯(lián)合鄰域熵、鄰域互信息.在IS中，A關(guān)于B的條件鄰域熵為

(3)

A與B的聯(lián)合鄰域熵為

(4)

A與B的鄰域互信息為

(5)

定理1[10].

1)NMIδ(A;B)=NMIδ(B;A)；

2)NMIδ(A;B)=NHδ(A)+NHδ(B)-NHδ(A∪B).

文獻(xiàn)[10]還考慮條件B的鄰域結(jié)構(gòu)與決策D的分類結(jié)構(gòu)，將IS中的條件鄰域熵落實(shí)到了DS中.為了更好地分析信息本質(zhì)與層次機(jī)制，定義6給出一種范化形式.

定義6. 條件鄰域熵.在DS中，D關(guān)于B的條件鄰域熵為

(6)

1.2 條件鄰域熵的粒化非單調(diào)性

針對(duì)DS中的條件鄰域熵(式(6))，下面采用3層粒化技術(shù)[6]進(jìn)行“高層→中層→底層”層次分解(如圖1左列)，以待改進(jìn)與比較.

式(6)位于宏觀高層，能夠轉(zhuǎn)換為等價(jià)形式：

其中：

NHδ(Xj

如此，圖1左列中的中層度量與底層度量具有相關(guān)的符號(hào)描述.

Fig. 1 Conditional neighborhood entropy and its improvement relationship based on three-layer granular structure圖1 基于3層粒結(jié)構(gòu)的條件鄰域熵及其改進(jìn)關(guān)系

由圖1左列可知，高層NHδ(DB)由NHδ(Xj通過(guò)“ΣΣ” 表示；通過(guò)一次分解，中層NHδ(XjB)由NHδ(Xj通過(guò)“Σ” 表示；底層則由NHδ(Xj直接表示.可見(jiàn)，條件鄰域熵具有3層分解形式，其粒化非單調(diào)性主要位于高層且具有如下層次誘因.

例1.DS=(U,C∪D,V,f,δ)如表1所示.其中，U={x1,x2,…,x7},C={c1,c2,…,c5},UD={X1,X2}={{x1,x2,x4,x5},{x3,x6,x7}},δ=0.4.

Table 1 Decision Table of Example 1表1 例1決策表

條件鄰域熵(式(6))可以直接計(jì)算，其等價(jià)于實(shí)施“ΣΣ”集成圖1左列中的底層度量.現(xiàn)選取粗化過(guò)程{c1,c2,c3,c4}→{c1,c2,c3}→{c1,c2}，經(jīng)計(jì)算3個(gè)條件鄰域熵值可得：

NHδ(D{c1,c2})-NHδ(D{c1,c2,c3})=
9.6515×10-4>0；
NHδ(D{c1,c2,c3})-NHδ(D{c1,c2,c3,c4})=
-0.0157<0.

因此，在粗化{c1,c2,c3}→{c1,c2}中，

NHδ(D{c1,c2})>NHδ(D{c1,c2,c3})，

而在粗化{c1,c2,c3,c4}→{c1,c2,c3}中，

NHδ(D{c1,c2,c3})

可見(jiàn)，條件鄰域熵是粒化非單調(diào)的.

Fig. 2 Qualitative change of intersection information in knowledge coarsening圖2 知識(shí)粗化中的交信息質(zhì)變

2 基于3層粒結(jié)構(gòu)的粒化單調(diào)條件鄰域熵

條件鄰域熵(式(6))具有粒化非單調(diào)性的不足，相關(guān)的兩大底層概率誘因是：1) 底層概率在粗化中的不確定性，2) 底層0概率沒(méi)有被考慮.對(duì)此，本節(jié)采用3層粒結(jié)構(gòu)[6]與自底向上粒計(jì)算策略，先改進(jìn)條件鄰域熵對(duì)應(yīng)的底層度量，再集成構(gòu)建具有粒化單調(diào)性的新型條件鄰域熵.

Hδ(Xj

即底層度量可以能夠表示為不確定性信息

的線性集成(或者表示為其中一個(gè)的線性變換)，故關(guān)聯(lián)于集成的不確定性信息；基于Case1的設(shè)置，Case2利用“近似逼近”來(lái)獲取信息度量變化的平穩(wěn)性.因此，定義7所建度量主要具有數(shù)學(xué)優(yōu)勢(shì).

性質(zhì)2. 若A?B，則

Hδ(Xj

因此，粗化過(guò)程涉及3種粒相交情形，相關(guān)的分類與證明如下:

因此：

即Hδ(Xj

類似于情形1的證明過(guò)程，可得：

Hδ(Xj

因此，Hδ(Xj

綜上情形1～3，得證.

證畢.

性質(zhì)2表明底層度量Hδ(Xj具有粒化單調(diào)性.特別地，證明中的情形2恰好可用圖2來(lái)解釋，故也說(shuō)明定義7考慮了圖2的“交信息質(zhì)變”這一特殊情況.

性質(zhì)3. 若0≤γ≤δ≤1，則

Hδ(Xj

定義7構(gòu)建了新型底層度量，性質(zhì)2與性質(zhì)3分別體現(xiàn)了其相關(guān)的粒化單調(diào)性及參數(shù)單調(diào)性，因此其對(duì)條件鄰域熵的底層分解度量具有改進(jìn)性.下面，對(duì)該底層度量實(shí)施自然集成，獲取中高層度量及其單調(diào)性，最終在高層改進(jìn)條件鄰域熵.特別地，基于底層度量的科學(xué)構(gòu)造與信息集成，中高層度量也具有可解釋性與相關(guān)不確定性語(yǔ)義.

定義8. 中層度量.在中層(B，Xj)定義度量

(7)

性質(zhì)4. 若A?B，則

Hδ(XjB)≥Hδ(XjA).

性質(zhì)5. 若0≤γ≤δ≤1，則

Hδ(XjB)≤Hγ(XjB).

定義8集成定義7底層度量構(gòu)建了中層度量，其具有粒化單調(diào)性與參數(shù)單調(diào)性，這2條性質(zhì)(即性質(zhì)4與性質(zhì)5)自然來(lái)源于底層的相應(yīng)性質(zhì)(即性質(zhì)2與性質(zhì)3).類似地，下面將中層的度量及其性質(zhì)自然集成演化到高層.

定義9. 單調(diào)條件鄰域熵.在高層(B，D)上定義單調(diào)條件鄰域熵：

(8)

性質(zhì)6. 若A?B，則Hδ(DB)≥Hδ(DA).

性質(zhì)7. 若0≤γ≤δ≤1，則

Hδ(DB)≤Hγ(DB).

定義9最終建立了具有粒化單調(diào)性(性質(zhì)6)的條件鄰域熵，其“自底向上”的集成演化標(biāo)注于圖1的右列.利用圖1對(duì)條件鄰域熵(定義6)與單調(diào)條件鄰域熵(定義9)進(jìn)行比較總結(jié).

1) 圖1左列體現(xiàn)了條件鄰域熵的“高層→中層→底層”分解過(guò)程，即高層度量NHδ(DB)通過(guò)“Σ”分解到中層度量NHδ(XjB)，再通過(guò)“Σ”分解到底層度量NHδ(Xj

2) 圖1右列體現(xiàn)了單調(diào)條件鄰域熵的“底層→中層→高層”集成過(guò)程,即底層度量Hδ(Xj通過(guò)“Σ”集成到中層度量Hδ(XjB)，再通過(guò)“Σ”集成到高層度量Hδ(DB).

3) 定義6的條件鄰域熵的“自頂向下分解”與定義9的單調(diào)條件鄰域熵的“自底向上集成”具有相反性與對(duì)比性，但兩者在3種粒度層次上具有橫向改進(jìn)性.具體地，在底層上Hδ(Xj改進(jìn)NHδ(Xj在中層上Hδ(XjB)改進(jìn)NHδ(XjB)，在高層上Hδ(DB)改進(jìn)NHδ(DB).

綜上3點(diǎn)可見(jiàn)，現(xiàn)有工作已經(jīng)涉及3項(xiàng)內(nèi)容:1)對(duì)條件鄰域熵進(jìn)行3層分解，并揭示高層粒化非單調(diào)性及其底層誘因；2)自底向上構(gòu)建新型條件鄰域熵，從粒化機(jī)制上得到粒化單調(diào)性；3)從粒化單調(diào)性的角度，新型條件鄰域熵在3個(gè)層次上都具有改進(jìn)性.

3 基于粒化單調(diào)條件鄰域熵的屬性約簡(jiǎn)

目前，屬性約簡(jiǎn)主要集中在粒化高層，其中的粒化單調(diào)度量是構(gòu)建屬性約簡(jiǎn)的重要基礎(chǔ).第2節(jié)通過(guò)底層的單調(diào)構(gòu)造與0概率處理，在粒化高層建立了具有粒化單調(diào)性的條件鄰域熵，其具有特定的不確定性語(yǔ)義.進(jìn)而，本節(jié)采用新建單調(diào)條件鄰域熵來(lái)自然研究屬性約簡(jiǎn)，包括建立相關(guān)的定義、性質(zhì)及算法等.

定理2. 2個(gè)條件等價(jià)：

(N1)Hδ(DB)≠Hδ(D(B-{b})),?b∈B；

(N2)Hδ(DB′)≠Hδ(DB),?B′?B.

證明. 1) 若?B′?B，則?b∈B-B′?B，使得B′?B-{b}?B.由粒化單調(diào)性(性質(zhì)6)與N1，可知Hδ(DB′)≤Hδ(D(B-{b}))

2) ?b∈B，設(shè)B′=B-{b}?B.由N2知Hδ(DB)≠Hδ(D(B-{b}))，即N2?N1成立.

綜上2點(diǎn)得證.

證畢.

定義10. 約簡(jiǎn).引入新條件：

(S)Hδ(DB)=Hδ(DC)，

若子集B滿足條件S與N1或條件S與N2，則稱為C的一個(gè)相對(duì)D約簡(jiǎn)，所有相對(duì)約簡(jiǎn)組成的集合記為RedC(D).

基于單調(diào)條件鄰域熵，定理2提供2條等價(jià)的獨(dú)立必要性條件，即N1與N2.再加上聯(lián)合充分性條件S，定義10自然定義相關(guān)的屬性約簡(jiǎn).

定義11. 核.若Hδ(D(C-{c}))≠Hδ(DC)，則稱c在C中是必要的，否則是不必要的.C中所有必要屬性組成的集合稱為核，記為CoreC(D)，即：

CoreC(D)={c∈C|Hδ(D(C-{c}))≠Hδ(DC)}.

(9)

Hδ(DB)=Hδ(DC)，B?C-{c}?C，

由粒化單調(diào)性(性質(zhì)6)可得：

Hδ(D(C-{c}))=Hδ(DC).

由定義11知，c?CoreC(D).因此

2) 若c?CoreC(D)，由定義11知：

Hδ(D(C-{c}))=Hδ(DC).

?B∈RedC(D)，B?C-{c}，使得：

Hδ(D(C-{c}))=Hδ(DB).

由粒化單調(diào)性(性質(zhì)6)知，Hδ(DB)=Hδ(DC)，故B∈RedC(D).由B?C-{c}有c?B，從而因此：

綜上2點(diǎn)得證.

證畢.

類似于經(jīng)典情形，定義11提供核計(jì)算公式，并可生成相關(guān)算法(如算法1)；定理3表明核在所有約簡(jiǎn)中，因此可計(jì)算的核可以作為構(gòu)建約簡(jiǎn)的基礎(chǔ).定義12首先利用單調(diào)條件鄰域熵來(lái)建立屬性重要度，進(jìn)而設(shè)計(jì)基于核的啟發(fā)式屬性增加算法(如算法2).

定義12. 屬性重要度.設(shè)c∈C-B，則屬性c對(duì)條件屬性集B相對(duì)于D的重要度為

Sig(c,B,D)=Hδ(DB∪{c})-Hδ(DB).

(10)

其表征“B上增加屬性c”增加過(guò)程中單調(diào)條件鄰域熵的變化.

算法1. 求核算法.

輸入：決策表DS=(U,C∪D,V,f,δ);

輸出：CoreC(D).

Step1. 計(jì)算Hδ(DC)，設(shè)置CoreC(D)=?;

Step2. for ?ck∈C(k=1,2,…,n) do

Step3. 計(jì)算Hδ(D(C-{ck}));

Step4. ifHδ(D(C-{ck}))≠Hδ(DC)

then

Step5.CoreC(D)=CoreC(D)∪{ck};

Step6. end if

Step7. end for

Step8. returnCoreC(D).

算法2. 基于核的屬性增加啟發(fā)式約簡(jiǎn)算法.

輸入：決策表DS=(U,C∪D,V,f,δ);

輸出：B∈RedC(D).

Step1. 計(jì)算Hδ(DC);

Step2. 由算法1，計(jì)算CoreC(D)，取B=

CoreC(D)，計(jì)算Hδ(DB);

Step3. whileHδ(DB)≠Hδ(DC) do

Step4. ?ck∈C-B，計(jì)算Sig(ck,B,D)，取

c0=arg maxSig(ck,B,D);

Step5. 令B=B∪{c0}，計(jì)算Hδ(DB);

Step6. end while

Step7. returnB.

算法1通過(guò)逐個(gè)刪除條件屬性，并基于式(9)進(jìn)行求核計(jì)算.算法2在算法1求核的基礎(chǔ)上，采用屬性重要度進(jìn)行啟發(fā)式搜索，快速增加條件屬性來(lái)最終獲取一個(gè)屬性約簡(jiǎn).具體地，Step3～6循環(huán)增加屬性直至粒化單調(diào)條件鄰域熵值達(dá)到最初C所在的最高水平，其中主要加入具有最大Sig值的屬性(即Step4中的c0)，以提升整個(gè)算法的收斂速度.

最后指出，算法1基本地計(jì)算核而算法2啟發(fā)地搜索約簡(jiǎn)，兩者都依托了改進(jìn)條件鄰域熵及其粒化單調(diào)性.對(duì)比地，傳統(tǒng)條件鄰域熵具有粒化非單調(diào)性，不能進(jìn)行相關(guān)約簡(jiǎn)算法的有效構(gòu)建與具體實(shí)現(xiàn).

4 UCI數(shù)據(jù)實(shí)驗(yàn)

本節(jié)提供UCI(University of CaliforniaIrvine)數(shù)據(jù)實(shí)驗(yàn)，驗(yàn)證新建條件鄰域熵的改進(jìn)單調(diào)性與相關(guān)約簡(jiǎn)算法的有效性.

4.1 改進(jìn)條件鄰域熵的粒化單調(diào)性驗(yàn)證

這里驗(yàn)證改進(jìn)條件鄰域熵的粒化單調(diào)性.為此，選取3類UCI數(shù)據(jù)集：Wdbc,Pima,Sonar[21].其中，Wdbc數(shù)據(jù)集包含569個(gè)對(duì)象、30個(gè)條件屬性、1個(gè)決策屬性；Pima數(shù)據(jù)集包含768個(gè)對(duì)象、8個(gè)條件屬性、1個(gè)決策屬性；Sonar數(shù)據(jù)集包含208個(gè)對(duì)象、60個(gè)條件屬性、1個(gè)決策屬性.

對(duì)每一類數(shù)據(jù)集，主要在確定鄰域參數(shù)δ后選擇一條屬性擴(kuò)充增鏈，從而計(jì)算條件鄰域熵與改進(jìn)條件鄰域熵并分析它們的粒化單調(diào)性.

1) Wdbc數(shù)據(jù)集采用閾值δ=0.8，只關(guān)注前12個(gè)條件屬性并構(gòu)建一條具有自然序的屬性增鏈

{c1}→{c1,c2}→{c1,c2,c3}→…→
{c1,c2,c3,…,c12}；

2) Pima數(shù)據(jù)集采用δ=0.95，并關(guān)注自然增鏈

{c1}→{c1,c2}→{c1,c2,c3}→…→
{c1,c2,c3,…,c8}；

3) Sonar數(shù)據(jù)集采用δ=0.4，只關(guān)注前15個(gè)條件屬性及其構(gòu)成的自然增鏈

{c1}→{c1,c2}→{c1,c2,c3}→…→
{c1,c2,c3,…,c15}.

在這些實(shí)驗(yàn)設(shè)計(jì)下，3種數(shù)據(jù)集的2種條件鄰域熵值分別列入表2～4，它們對(duì)應(yīng)地描繪于圖3～5;其中，圖3～5中橫坐標(biāo)及屬性數(shù)目對(duì)應(yīng)著屬性增鏈，縱坐標(biāo)熵值記錄

NH=NHδ(D/B)與H=Hδ(D/B).

Table 2 Values of Two Types of Conditional Neighborhood Entropy in Wdbc Dataset (δ=0.8)

Table 3 Values of Two Types of Conditional Neighborhood Entropy in Pima Dataset (δ=0.95)

Table 4 Values of Two Types of Conditional Neighborhood Entropy in Sonar Dataset (δ=0.4)

Fig. 3 Changing curves of two types of conditional neighborhood entropy in Wdbc dataset (δ=0.8)圖3 Wdbc數(shù)據(jù)集的2種條件鄰域熵的變化曲線 (δ=0.8)

Fig. 4 Changing curves of two types of conditional neighborhood entropy in Pima dataset (δ=0.95)圖4 Pima數(shù)據(jù)集的2種條件鄰域熵的變化曲線 (δ=0.95)

Fig. 5 Changing curves of two types of conditional neighborhood entropy in Sonar dataset (δ=0.4)圖5 Sonar數(shù)據(jù)集的2種條件鄰域熵的變化曲線 (δ=0.4)

基于表2～4與圖3～5結(jié)果，容易驗(yàn)證2種條件鄰域熵的粒化單調(diào)性.

1) 在表2中，屬性增鏈

{c1,c2,c3}→{c1,c2,c3,c4}→{c1,c2,c3,c4,c5}

涉及NHδ(DB)非單調(diào)變化

2.097 547→2.101 147→2.101 050

與Hδ(DB)單增變化

2.112 881→2.140 857→2.141 813；

而屬性增鏈

{c1,c2,…,c10}→{c1,c2,…,c11}→{c1,c2,…,c12}

涉及NHδ(DB)非單調(diào)變化

2.109 760→2.118 238→2.117 672

與Hδ(DB)單增變化

2.256 689→2.283 208→2.298 845.

2) 在表3中，而屬性增鏈

{c1}→{c1,c2}→{c1,c2,c3}

涉及NHδ(DB)非單調(diào)變化

2.138 285→2.138 434→2.138 407

與Hδ(DB)單增變化

2.140 545→2.142 468→2.143 135.

3) 在表4中，而屬性增鏈

{c1,c2,…,c13}→{c1,c2,…,c14}→{c1,c2,…,c15}

涉及NHδ(DB)非單調(diào)變化

2.045 410→2.047 744→2.046 308

與Hδ(DB)單增變化

3.153 038→3.648 269→4.447 961.

由此可見(jiàn)，條件鄰域熵不具備粒化單調(diào)性，而新建條件鄰域熵具有改進(jìn)性.事實(shí)上，圖3～5比較清晰地展現(xiàn)了Hδ(DB)在所選屬性增鏈上的粒化單調(diào)性，這也說(shuō)明了Hδ(DB)的有效性；對(duì)比地，NHδ(DB)由于數(shù)值變化較小因而其粒化非單調(diào)性表現(xiàn)不是太明顯.總之，3個(gè)UCI實(shí)驗(yàn)較好地說(shuō)明了新建條件鄰域熵的粒化單調(diào)性及相關(guān)改進(jìn)性.

4.2 基于粒化單調(diào)條件鄰域熵的屬性約簡(jiǎn)實(shí)現(xiàn)

基于粒化單調(diào)的條件鄰域熵，下面說(shuō)明相關(guān)屬性約簡(jiǎn)的有效性.為此，主要在5類UCI數(shù)據(jù)集(Wdbc,Pima,Sonar,Wpbc,Wine)[21]上實(shí)施算法1與算法2，并得到核與約簡(jiǎn)的最終結(jié)果.

針對(duì)5類UCI數(shù)據(jù)集，實(shí)驗(yàn)中采用了3種鄰域參數(shù)，即δ分別取0.3,0.5,0.8.首先利用算法1求出核，再利用算法2求出一個(gè)約簡(jiǎn)(其中屬性重要度充當(dāng)了啟發(fā)式信息，用以加速整個(gè)搜索算法的收斂速度).表5給出了算法1與算法2的具體實(shí)驗(yàn)結(jié)果，即提供了相關(guān)的核與約簡(jiǎn)；進(jìn)而，表6給出了相關(guān)的數(shù)目統(tǒng)計(jì).

Table 5 Experimental Results of Core and Reduct Based on Five Types of UCI Data Sets表5 5類UCI數(shù)據(jù)集上的核與約簡(jiǎn)的實(shí)驗(yàn)結(jié)果

Table 6 Number Information of Five Types of UCI Data Sets and Their Experiment Results表6 5類UCI數(shù)據(jù)集及其實(shí)驗(yàn)結(jié)果的數(shù)目信息

基于表5與表6，這里的數(shù)據(jù)集已經(jīng)具有一定規(guī)模，但算法1與算法2都能夠有效地得到基本結(jié)果.下面，針對(duì)相同的數(shù)據(jù)集進(jìn)行相關(guān)分析.

核都在所得的相關(guān)約簡(jiǎn)中，表明算法1的核為約簡(jiǎn)構(gòu)建的基礎(chǔ).當(dāng)然，也有核為空的情況(如Wdbc數(shù)據(jù)集在δ=0.8時(shí))，此時(shí)算法2只能直接利用屬性重要度進(jìn)行啟發(fā)搜索.

基于粒化單調(diào)的條件鄰域熵，利用算法2可以有效地刪除部分冗余屬性，保留有效屬性.例如，Sonar具有60個(gè)條件屬性，核包括大約20多個(gè)，而約簡(jiǎn)包括大約30多個(gè)，相關(guān)屬性約簡(jiǎn)比較合理.

實(shí)驗(yàn)結(jié)果還依賴于參數(shù)δ的取值.隨著參數(shù)0.3→0.5→0.8的增大，核有擴(kuò)大或縮小的結(jié)果；屬性約簡(jiǎn)一般沒(méi)有擴(kuò)大或縮小的變化，但約簡(jiǎn)基數(shù)總體有變小的趨勢(shì).

基于大規(guī)模數(shù)據(jù)實(shí)驗(yàn)及其結(jié)果，本文所構(gòu)造的屬性約簡(jiǎn)算法是有效的，基于改進(jìn)條件鄰域熵的約簡(jiǎn)算法可以具體實(shí)現(xiàn)，這也充分說(shuō)明了改進(jìn)所得粒化單調(diào)性的應(yīng)用價(jià)值.

5 結(jié) 論

條件鄰域熵不具備粒化單調(diào)性，其中1個(gè)基本誘因是“0概率信息項(xiàng)”未處理導(dǎo)致的信息突變性；從而，粒化非單調(diào)性及其誘因阻礙了相關(guān)的屬性約簡(jiǎn)發(fā)展，例如沒(méi)法建立約簡(jiǎn)的核與啟發(fā)式算法.對(duì)此，本文主要進(jìn)行單調(diào)改進(jìn)與約簡(jiǎn)構(gòu)建.通過(guò)采用3層粒結(jié)構(gòu)[6],“自頂向下”分解剖析條件鄰域熵，“自底向上”集成構(gòu)建新型條件鄰域熵，并在每個(gè)層面獲取粒化單調(diào)性從而實(shí)現(xiàn)基本改進(jìn).進(jìn)而，基于高層所建的條件鄰域熵及其粒化單調(diào)性，深入研究屬性約簡(jiǎn)，并挖掘?qū)傩灾匾葋?lái)構(gòu)造基于核的啟發(fā)式約簡(jiǎn)算法(算法2).最后，通過(guò)大規(guī)模數(shù)據(jù)實(shí)驗(yàn)，有效驗(yàn)證了相關(guān)的粒化單調(diào)性與屬性約簡(jiǎn)算法.總之，本文所建的條件鄰域熵具有粒化單調(diào)性，改進(jìn)了傳統(tǒng)條件鄰域熵，其誘導(dǎo)的屬性約簡(jiǎn)具有應(yīng)用前景，但相關(guān)的理論探討與實(shí)際應(yīng)用還值得深入，比如相關(guān)的度量保持條件、度量近似應(yīng)用、與其他約簡(jiǎn)目標(biāo)的結(jié)合等，度量的分段性還值得實(shí)際處理.