牟 恩，張賢勇，姚岳松，鄧 切

1.西南醫(yī)科大學(xué) 醫(yī)學(xué)信息與工程學(xué)院，四川 瀘州646000

2.四川師范大學(xué) 智能信息與量子信息研究所，成都610066

3.四川師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，成都610066

1 引言

粗糙集屬性約簡(jiǎn)能夠有效實(shí)施降維優(yōu)化與規(guī)則推理[1]。傳統(tǒng)“決策分類約簡(jiǎn)”追求所有決策類的全局優(yōu)化，而Yao和Zhang[2]提出的“特定類約簡(jiǎn)”涉及特定類的局部?jī)?yōu)化，兩類屬性約簡(jiǎn)分別位于決策表的宏觀高層與中觀中層[3]。當(dāng)前，特定類約簡(jiǎn)主要立足于經(jīng)典粗糙集[4-5]，故值得推廣。鄰域粗糙集推廣了經(jīng)典粗糙集，但相關(guān)屬性約簡(jiǎn)集中于決策分類約簡(jiǎn)（如文獻(xiàn)[6-7]），還未見(jiàn)特定類約簡(jiǎn)的報(bào)道。

信息度量廣泛應(yīng)用于不確定刻畫(huà)與屬性約簡(jiǎn)。對(duì)于經(jīng)典粗糙集，苗奪謙[8]建立信息熵、條件熵、互信息體系，而條件熵刻畫(huà)了屬性約簡(jiǎn)[9-10]。對(duì)于鄰域粗糙集，Hu等[11]建立對(duì)數(shù)函數(shù)信息體系進(jìn)行特征選擇，Chen等[12]提出鄰域精度、鄰域熵、信息粒度及相關(guān)?；瘑握{(diào)性，Chen等[13]利用聯(lián)合鄰域熵來(lái)設(shè)計(jì)基因選擇算法，Yuan等[14]采用鄰域熵變種度量來(lái)進(jìn)行離群點(diǎn)檢測(cè)；進(jìn)而針對(duì)屬性約簡(jiǎn)，謝玲玲等[15]提出近似條件熵來(lái)進(jìn)行屬性約簡(jiǎn)，張寧和范年柏[16]提出鄰域（近似）條件熵來(lái)構(gòu)建啟發(fā)式屬性約簡(jiǎn)，趙小龍和楊燕[17]提出鄰域?；瘲l件熵來(lái)設(shè)計(jì)增量約簡(jiǎn)算法，姚晟等[18]基于鄰域粗糙互信息來(lái)進(jìn)行非單調(diào)屬性約簡(jiǎn)。

本文擬從鄰域近似條件熵的信息角度，構(gòu)建鄰域粗糙集的特定類約簡(jiǎn)。從經(jīng)典條件熵推廣后的鄰域近似條件熵出發(fā)，分解提取關(guān)于特定類的鄰域近似條件熵，證明信息?；菃握{(diào)性，建立特定類約簡(jiǎn)及其啟發(fā)算法，并提供實(shí)例分析與實(shí)驗(yàn)驗(yàn)證。

2 鄰域粗糙集及高層鄰域近似條件熵

決策表NDT=＜U,C,D ＞包括有限論域U、條件屬性集C={c1,c2,…,cl}、決策屬性集D。鄰域體系涉及距離函數(shù)d與半徑參數(shù)δ。本文采用Manhattan 距離可得鄰域nC(x)={y∈U|dC(x,y)≤δ}、鄰域關(guān)系NC={(x,y)∈U×U|dC(x,y)≤δ}、鄰域覆蓋U/NC={nC(x)|x∈U} 。任意條件屬性子集B?C可以產(chǎn)生相關(guān)概念，如鄰域采用nB(x)或(x)并設(shè)鄰域粒數(shù)為n。設(shè)決策分類U/IND(D)={Dj|j=1,2,…,m}具有m個(gè)決策類。

定義1[7]決策類Dj關(guān)于B?C的鄰域上下近似為：

基于文獻(xiàn)[8-9，15-16]，下面自然建立鄰域（近似）條件熵，其中鄰域及其粒數(shù)采用不重復(fù)規(guī)則，有利于覆蓋粒結(jié)構(gòu)推理；當(dāng)覆蓋退化到劃分時(shí)，它們將退化到經(jīng)典粗糙集的（近似）條件熵。

定義2 決策屬性集D相對(duì)于B?C的鄰域條件熵為：

鄰域條件熵CE(D|B)采用經(jīng)典條件熵公式，將等價(jià)剖分結(jié)構(gòu)泛化推廣到鄰域覆蓋結(jié)構(gòu)，具有相應(yīng)不確定性語(yǔ)義。鄰域近似條件熵ACE(D|B)引入鄰域近似粗糙度ρB(Dj)作為權(quán)重系數(shù)，有效融合覆蓋結(jié)構(gòu)信息與近似逼近信息，變得更為強(qiáng)健。

3 中層鄰域近似條件熵

上述高層鄰域（近似）條件熵適用于整個(gè)決策分類。下面對(duì)它們施行“求和換序”與“分解提取”，得到中層相應(yīng)概念，以適用于特定決策類。

定義3 決策類Dj相對(duì)于B?C的鄰域條件熵為：

中層鄰域條件熵CE(Dj|B)對(duì)所有不重復(fù)鄰域粒實(shí)施信息集成，表征鄰域覆蓋結(jié)構(gòu)對(duì)于特定決策類的不確定性程度。基于信息融合[15-16]，ACE(Dj|B)集成了信息度量CE(Dj|B)與結(jié)構(gòu)度量ρB(Dj)的不確定性信息，有效用于鄰域粗糙集的特定類約簡(jiǎn)構(gòu)建。下面揭示CE(Dj|B)、ACE(Dj|B)的上下界與?；菃握{(diào)性。為此，提取定義3公式內(nèi)層，記

定理1（1）CE(Dj|B)∈[0,|Dj|lb|U|]、ACE(Dj|B)∈[0,|Dj|lb|U|] 。（2）若BndB(Dj)=?，則CE(Dj|B)=0 、ACE(Dj|B)=0 。（3）若U/NB={U} 且Dj={x}?U，則CE(Dj|B)=(1/|U|)lb|U|、ACE(Dj|B)=(1/|U|)lb|U|。

證明（1）對(duì)特定類Dj，若鄰域)滿足)?Dj=?則p(Dj|))=0、CE(Dj|))=0。下面考慮交Dj的鄰域并，設(shè)Sj={i∈{1,2,…,n}x)?Dj≠?}則|Sj|≤n≤N（這里N=|U|）。 ?i∈Sj有p(Dj|))∈[1/N,1]與lbp(Dj|))≥lb 1/N。因此：

（2）若BndB(Dj)=?，這意味著?nB(x)∈U/NB，nB(x)?Dj=?、p(Dj|nB(x))=0 或nB(x)?Dj=nB(x) 、p(Dj|nB(x))=1,即CE(Dj|nB(x))=0。從而CE(Dj|B)=0；進(jìn)而ACE(Dj|B)=0，其中ρB(Dj)=0。

（3）若U/NB={U} 且Dj={x}?U，即只存在唯一鄰域U,且其滿足p(Dj|U)∈(0,1)、lbp(Dj|U)=lb(1/N)，根據(jù)公式（1）有CE(Dj|B)=(|Dj|/|U|)lb|U|=(1/|U|)lb|U|。進(jìn)而ACE(Dj|B)=(1/|U|)lb|U|，其中ρB(Dj)=1。

定理2 設(shè)屬性子集A,B?C誘導(dǎo)的鄰域覆蓋U/NA、U/NB具有?；P(guān)系U/NA-?U/NB（即?x∈U有nA(x)?nB(x)），則CE(Dj|A)與CE(Dj|B)、ACE(Dj|A)與ACE(Dj|B)無(wú)必然大小關(guān)系。

證明因?yàn)閁/NA-?U/NB有nA(x)?nB(x) 。該嵌套鄰域結(jié)構(gòu)與決策類Dj具有三種相交情況。

（1）若nA(x)?Dj=nB(x)?Dj=即p(Dj|nA(x))=p(Dj|nB(x))=0，則可以得到：

（2）若?=nA(x)?Dj?nB(x)?Dj則0=p(Dj|nA(x))≤p(Dj|nB(x))≤1。由于上凸函數(shù)-plbp的非單調(diào)性，不能確定p(Dj|nA(x))×lbp(Dj|nA(x))與p(Dj|nB(x))×lbp(Dj|nB(x))的大小關(guān)系。從而，也不能確定CE(Dj|nA(x))與CE(Dj|nB(x))大小關(guān)系。

（3）若??nA(x)?Dj?nB(x)?Dj，但兩個(gè)非0 概率p(Dj|nA(x))與p(Dj|nB(x))之間的大小不確定[18]，故CE(Dj|nA(x))與CE(Dj|nB(x))大小關(guān)系也是不確定的。

綜上，CE(Dj|nA(x))與CE(Dj|nB(x))無(wú)必然大小關(guān)系。后續(xù)?；Y(jié)構(gòu)的重復(fù)計(jì)數(shù)消除過(guò)程也具有不確定性，故基于U/NA與U/NB結(jié)的CE(Dj|A)與CE(Dj|B)無(wú)必然大小關(guān)系。進(jìn)而，ACE(Dj|A)與ACE(Dj|B)也無(wú)必然大小關(guān)系。

4 基于鄰域近似條件熵的特定類屬性約簡(jiǎn)

基于中層鄰域（近似）條件熵及其不確定性語(yǔ)義、?；菃握{(diào)性，本章構(gòu)建相應(yīng)的特定類屬性約簡(jiǎn)及其啟發(fā)算法，主要采用具有信息修正的鄰域近似條件熵。

定義4 基于鄰域近似條件熵，B?C稱為C相對(duì)于決策類Dj的一個(gè)約簡(jiǎn)，若如下兩條成立：

這里的約簡(jiǎn)目標(biāo)追求更大的鄰域近似條件熵值，這種單向方案已經(jīng)實(shí)際使用[18]。定義中的兩條分別對(duì)應(yīng)“聯(lián)合充分性”與“個(gè)體必要性”。接下來(lái)，類似于文獻(xiàn)[18]，引入屬性重要度并構(gòu)建啟發(fā)式約簡(jiǎn)算法。

定義5a∈B關(guān)于B的內(nèi)屬性重要度為：

內(nèi)重要度sigin(a,B,Dj)表示在B中刪除屬性a產(chǎn)生的關(guān)于鄰域近似條件熵的信息減量，而外重要度sigout(a,B,Dj)表示在B上增加屬性a產(chǎn)生的信息增量，兩者提供了快速約簡(jiǎn)的屬性選擇機(jī)制。若a關(guān)于B是重要的，那么鄰域近似條件熵滿足關(guān)系A(chǔ)CE(Dj|B)＞ACE(Dj|B-{a}), 因此sigin(a,B,Dj)＞0, 反之sigin(a,B,Dj)＜0 ；對(duì)于a∈(C-B) ，若a關(guān)于B是重要的，則ACE(Dj|B?{a})＞ACE(Dj|B),因此有sigout(a,B,Dj)＞0，反之sigout(a,B,Dj)≤0。由此，下面采用這兩種重要度來(lái)設(shè)計(jì)一個(gè)啟發(fā)式搜索算法，以快速得到一個(gè)特定類約簡(jiǎn)。

算法1 基于鄰域近似條件熵的特定類屬性約簡(jiǎn)啟發(fā)算法。

輸入 決策表NDT=＜U,C,D ＞，鄰域半徑δ；

輸出 基于鄰域近似條件熵的特定類約簡(jiǎn)R。

步驟1 設(shè)置R=。

步驟2 計(jì)算?a∈C的內(nèi)屬性重要度sigin(a,C,Dj)，滿足sigin(a,C,Dj)＞0 的屬性a均加入R（即實(shí)施循環(huán)更新R←R?{a}）。

步驟3 計(jì)算子集R與全集C關(guān)于特定類Dj的鄰域近似條件熵ACE(Dj|R)與ACE(Dj|C)。若ACE(Dj|R)≥ACE(Dj|C)，則進(jìn)入步驟5，否則進(jìn)入步驟4。

步驟4 計(jì)算?a∈(C-R)的外屬性重要度sigout(a,R,Dj)，并選擇屬性重要度最大的屬性a*并入R（即施行一次更新R←R?{a*}），并進(jìn)入步驟3。

步驟5 ?a∈R，若屬性a滿足ACE(Dj|R-{a})≥ACE(Dj|R)，則從R中刪除a（即采用循環(huán)更新R←R-{a}）。

步驟6 返回R。

算法1 優(yōu)化了文獻(xiàn)[18]的非單調(diào)性算法結(jié)構(gòu)，并主要采用鄰域近似條件熵。步驟1是初始化。步驟2是啟發(fā)搜索過(guò)程，主要在條件屬性全集C中選取對(duì)類Dj具有相關(guān)模式識(shí)別功能的屬性。步驟3是一個(gè)評(píng)估過(guò)程，若步驟2 得到的子集R的鄰域近似條件熵小于全集C的（即ACE(Dj|R)＜ACE(Dj|C)），則需要利用步驟4 進(jìn)行剩余屬性的啟發(fā)式搜索，并加入最優(yōu)屬性以快速完成添加?？梢?jiàn)，鄰近步驟5 的R必然滿足約簡(jiǎn)“聯(lián)合充分性”，但不一定滿足約簡(jiǎn)“個(gè)體必要性”。由此，步驟5采用反向冗余刪除，最終獲得約簡(jiǎn)“個(gè)體必要性”?；谖墨I(xiàn)[18]的算法分析過(guò)程與結(jié)果，這里的算法1 計(jì)算量仍舊主要集中在步驟2，因此整個(gè)的時(shí)間復(fù)雜度為O(|C||U|lb |U|)。該算法是有效的，能夠得到一個(gè)基于鄰域近似條件熵的特定類屬性約簡(jiǎn)。

5 決策表實(shí)例

本章提供一個(gè)實(shí)例，說(shuō)明度量性質(zhì)與屬性約簡(jiǎn)。決策表NDT=＜U,C,D ＞如表1，其包括兩個(gè)決策類：D1={x1,x2}、D2={x3,x4}。

表1 實(shí)例決策表

基于Manhattan 距離與鄰域半徑δ=0.4，下面聚焦屬性增鏈

該鏈誘導(dǎo)出鄰域覆蓋及其粒化關(guān)系：

由此，可得兩個(gè)特定類的鄰域粗糙度：

上述所有值均隸屬理論雙界范圍[0,|Dj|lb |U|=4]（定理1）。4個(gè)不等式驗(yàn)證了?；菃握{(diào)性（定理2）。

最后分析特定類約簡(jiǎn)，主要采用決策類D2來(lái)說(shuō)明算法1。步驟1 賦值R=?。步驟2 計(jì)算3 個(gè)條件屬性的內(nèi)重要度：

由此沒(méi)有屬性滿足加入條件sigin＞0，故R=?。此時(shí)R達(dá)不到約簡(jiǎn)第一條，在步驟3 中判斷后需要轉(zhuǎn)入步驟4，計(jì)算3個(gè)條件屬性的外重要度：

基于最大值隨機(jī)選取一個(gè)屬性如c1并入R，有R={c1}。此時(shí)，用更新的R={c1}進(jìn)入步驟3，檢驗(yàn)有：

即{c1} 滿足約簡(jiǎn)第一條從而進(jìn)入步驟5?；诓襟E5，單屬性c1不能被刪除，即{c1} 滿足約簡(jiǎn)條件第二條，并最終在步驟6中輸出作為約簡(jiǎn)結(jié)果。

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

本章實(shí)施數(shù)據(jù)實(shí)驗(yàn)來(lái)驗(yàn)證鄰域（近似）條件熵及其特定類約簡(jiǎn)，主要是粒化非單調(diào)性（定理2）與啟發(fā)式約簡(jiǎn)算法（算法1）。下面從UCI 機(jī)器學(xué)習(xí)知識(shí)庫(kù)（http：//archive.ics.uci.edu/ml）中選取5 組數(shù)據(jù)集，如表2。首先采用最大-最小標(biāo)準(zhǔn)化數(shù)據(jù)預(yù)處理，仍用Manhattan距離函數(shù)，鄰域半徑參見(jiàn)表2。

表2 5類UCI數(shù)據(jù)集的基本描述

為表現(xiàn)度量變化，特選取自然屬性增鏈{c1}?{c1,c2}?…?C。針對(duì)所有的13 個(gè)決策類，進(jìn)行了完全實(shí)驗(yàn)計(jì)算；這里提供代表呈現(xiàn)，對(duì)此前3 個(gè)數(shù)據(jù)選取D2而后2 個(gè)數(shù)據(jù)集選取D1，相關(guān)度量結(jié)果參見(jiàn)圖1。在圖1 中，橫坐標(biāo)整數(shù)標(biāo)識(shí)屬性增鏈元B，縱坐標(biāo)實(shí)數(shù)標(biāo)識(shí)鄰域條件熵CE(Dj|B)、鄰域近似精度αB(Dj)（即1-ρB(Dj)）、鄰域近似條件熵ACE(Dj|B)。觀測(cè)可見(jiàn)，αB(Dj)很接近于0，CE(Dj|B)與ACE(Dj|B)具有細(xì)微調(diào)整差距，它們的?；菃握{(diào)性非常明顯?；谶@些非單調(diào)變化曲線，追求鄰域近似條件熵大值的特定類約簡(jiǎn)是合理的，其可以得到適當(dāng)長(zhǎng)度的約簡(jiǎn)結(jié)果。

圖1 5類UCI數(shù)據(jù)集關(guān)于屬性增鏈的三種度量變化

圖2 Wine數(shù)據(jù)集D1 類關(guān)于屬性增鏈與半徑增鏈的三種度量變化

最后分析鄰域半徑對(duì)度量與約簡(jiǎn)的結(jié)果影響。作為代表，選取數(shù)據(jù)集Wine 的D1類，以δ=0.5 為初始值并以0.5 為步長(zhǎng)構(gòu)造半徑增鏈。圖2 提供了CE(Dj|B)、αB(Dj)、ACE(Dj|B)在半徑增鏈與屬性增鏈上的變化。基于圖2，對(duì)于鄰域近似條件熵，通常的半徑能夠較好表現(xiàn)?；菃握{(diào)性，而波峰或最大值隨著半徑增大而右移；可見(jiàn)，半徑取值決定著度量數(shù)值以及后續(xù)約簡(jiǎn)。

進(jìn)而，表3提供了特定類約簡(jiǎn)結(jié)果，驗(yàn)證了算法1的有效性。表4 則提供了Wine 數(shù)據(jù)集D1類相關(guān)半徑增鏈的約簡(jiǎn)結(jié)果。基于表4，約簡(jiǎn)具有隨半徑變大而屬性增多的大體趨勢(shì)；鄰域半徑過(guò)?。ㄈ?.5）會(huì)導(dǎo)致屬性約簡(jiǎn)太單一，半徑過(guò)大（如4.0）則約簡(jiǎn)太冗余，即這兩種極端情況下的約簡(jiǎn)結(jié)果都不太理想；當(dāng)δ取2.0、2.5、3.0時(shí)，約簡(jiǎn)結(jié)果較好。此外，其他數(shù)據(jù)集實(shí)驗(yàn)都表現(xiàn)出類似結(jié)果，即適中的鄰域半徑能夠有效表現(xiàn)?；菃握{(diào)性并獲取較好屬性約簡(jiǎn)，而表2中的半徑取值正是經(jīng)過(guò)實(shí)驗(yàn)分析所得的較好參數(shù)設(shè)置。

表3 5類UCI數(shù)據(jù)集的特定類約簡(jiǎn)

表4 Wine數(shù)據(jù)集D1 類關(guān)于半徑增鏈的約簡(jiǎn)

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

本文?；纸鉀Q策表高層的鄰域（近似）條件熵，提取出中層的鄰域（近似）條件熵，獲得信息上下界與粒化非單調(diào)性，進(jìn)而構(gòu)建特定類屬性約簡(jiǎn)及其啟發(fā)式約簡(jiǎn)算法。本文構(gòu)建鄰域（近似）條件熵深化了文獻(xiàn)[15-16]的相關(guān)度量，后續(xù)特定類屬性約簡(jiǎn)推廣了文獻(xiàn)[2]的經(jīng)典特定類約簡(jiǎn)，而相關(guān)啟發(fā)式約簡(jiǎn)算法模擬并優(yōu)化了文獻(xiàn)[18]的算法。所得結(jié)果有利于特定類模式識(shí)別的不確定性度量與優(yōu)化應(yīng)用，值得深入探討。