鄰域近似條件熵的特定類屬性約簡及啟發算法

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

1.西南醫科大學 醫學信息與工程學院，四川 瀘州646000

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

3.四川師范大學 數學科學學院，成都610066

1 引言

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

信息度量廣泛應用于不確定刻畫與屬性約簡。對于經典粗糙集，苗奪謙[8]建立信息熵、條件熵、互信息體系，而條件熵刻畫了屬性約簡[9-10]。對于鄰域粗糙集，Hu等[11]建立對數函數信息體系進行特征選擇，Chen等[12]提出鄰域精度、鄰域熵、信息粒度及相關粒化單調性，Chen等[13]利用聯合鄰域熵來設計基因選擇算法，Yuan等[14]采用鄰域熵變種度量來進行離群點檢測；進而針對屬性約簡，謝玲玲等[15]提出近似條件熵來進行屬性約簡，張寧和范年柏[16]提出鄰域（近似）條件熵來構建啟發式屬性約簡，趙小龍和楊燕[17]提出鄰域粒化條件熵來設計增量約簡算法，姚晟等[18]基于鄰域粗糙互信息來進行非單調屬性約簡。

本文擬從鄰域近似條件熵的信息角度，構建鄰域粗糙集的特定類約簡。從經典條件熵推廣后的鄰域近似條件熵出發，分解提取關于特定類的鄰域近似條件熵，證明信息粒化非單調性，建立特定類約簡及其啟發算法，并提供實例分析與實驗驗證。

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

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

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

基于文獻[8-9，15-16]，下面自然建立鄰域（近似）條件熵，其中鄰域及其粒數采用不重復規則，有利于覆蓋粒結構推理；當覆蓋退化到劃分時，它們將退化到經典粗糙集的（近似）條件熵。

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

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

3 中層鄰域近似條件熵

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

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

中層鄰域條件熵CE(Dj|B)對所有不重復鄰域粒實施信息集成，表征鄰域覆蓋結構對于特定決策類的不確定性程度。基于信息融合[15-16]，ACE(Dj|B)集成了信息度量CE(Dj|B)與結構度量ρB(Dj)的不確定性信息，有效用于鄰域粗糙集的特定類約簡構建。下面揭示CE(Dj|B)、ACE(Dj|B)的上下界與粒化非單調性。為此，提取定義3公式內層，記

定理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）對特定類Dj，若鄰域)滿足)?Dj=?則p(Dj|))=0、CE(Dj|))=0。下面考慮交Dj的鄰域并，設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；進而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)，根據公式（1）有CE(Dj|B)=(|Dj|/|U|)lb|U|=(1/|U|)lb|U|。進而ACE(Dj|B)=(1/|U|)lb|U|，其中ρB(Dj)=1。

定理2 設屬性子集A,B?C誘導的鄰域覆蓋U/NA、U/NB具有粒化關系U/NA-?U/NB（即?x∈U有nA(x)?nB(x)），則CE(Dj|A)與CE(Dj|B)、ACE(Dj|A)與ACE(Dj|B)無必然大小關系。

證明因為U/NA-?U/NB有nA(x)?nB(x) 。該嵌套鄰域結構與決策類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。由于上凸函數-plbp的非單調性，不能確定p(Dj|nA(x))×lbp(Dj|nA(x))與p(Dj|nB(x))×lbp(Dj|nB(x))的大小關系。從而，也不能確定CE(Dj|nA(x))與CE(Dj|nB(x))大小關系。

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

綜上，CE(Dj|nA(x))與CE(Dj|nB(x))無必然大小關系。后續粒化結構的重復計數消除過程也具有不確定性，故基于U/NA與U/NB結的CE(Dj|A)與CE(Dj|B)無必然大小關系。進而，ACE(Dj|A)與ACE(Dj|B)也無必然大小關系。

4 基于鄰域近似條件熵的特定類屬性約簡

基于中層鄰域（近似）條件熵及其不確定性語義、粒化非單調性，本章構建相應的特定類屬性約簡及其啟發算法，主要采用具有信息修正的鄰域近似條件熵。

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

這里的約簡目標追求更大的鄰域近似條件熵值，這種單向方案已經實際使用[18]。定義中的兩條分別對應“聯合充分性”與“個體必要性”。接下來，類似于文獻[18]，引入屬性重要度并構建啟發式約簡算法。

定義5a∈B關于B的內屬性重要度為：

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

算法1 基于鄰域近似條件熵的特定類屬性約簡啟發算法。

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

輸出 基于鄰域近似條件熵的特定類約簡R。

步驟1 設置R=。

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

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

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

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

步驟6 返回R。

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

5 決策表實例

本章提供一個實例，說明度量性質與屬性約簡。決策表NDT=＜U,C,D ＞如表1，其包括兩個決策類：D1={x1,x2}、D2={x3,x4}。

表1 實例決策表

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

該鏈誘導出鄰域覆蓋及其粒化關系：

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

上述所有值均隸屬理論雙界范圍[0,|Dj|lb |U|=4]（定理1）。4個不等式驗證了粒化非單調性（定理2）。

最后分析特定類約簡，主要采用決策類D2來說明算法1。步驟1 賦值R=?。步驟2 計算3 個條件屬性的內重要度：

由此沒有屬性滿足加入條件sigin＞0，故R=?。此時R達不到約簡第一條，在步驟3 中判斷后需要轉入步驟4，計算3個條件屬性的外重要度：

基于最大值隨機選取一個屬性如c1并入R，有R={c1}。此時，用更新的R={c1}進入步驟3，檢驗有：

即{c1} 滿足約簡第一條從而進入步驟5。基于步驟5，單屬性c1不能被刪除，即{c1} 滿足約簡條件第二條，并最終在步驟6中輸出作為約簡結果。

6 UCI數據實驗

本章實施數據實驗來驗證鄰域（近似）條件熵及其特定類約簡，主要是粒化非單調性（定理2）與啟發式約簡算法（算法1）。下面從UCI 機器學習知識庫（http：//archive.ics.uci.edu/ml）中選取5 組數據集，如表2。首先采用最大-最小標準化數據預處理，仍用Manhattan距離函數，鄰域半徑參見表2。

表2 5類UCI數據集的基本描述

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

圖1 5類UCI數據集關于屬性增鏈的三種度量變化

圖2 Wine數據集D1 類關于屬性增鏈與半徑增鏈的三種度量變化

最后分析鄰域半徑對度量與約簡的結果影響。作為代表，選取數據集Wine 的D1類，以δ=0.5 為初始值并以0.5 為步長構造半徑增鏈。圖2 提供了CE(Dj|B)、αB(Dj)、ACE(Dj|B)在半徑增鏈與屬性增鏈上的變化。基于圖2，對于鄰域近似條件熵，通常的半徑能夠較好表現粒化非單調性，而波峰或最大值隨著半徑增大而右移；可見，半徑取值決定著度量數值以及后續約簡。

進而，表3提供了特定類約簡結果，驗證了算法1的有效性。表4 則提供了Wine 數據集D1類相關半徑增鏈的約簡結果。基于表4，約簡具有隨半徑變大而屬性增多的大體趨勢；鄰域半徑過小（如0.5）會導致屬性約簡太單一，半徑過大（如4.0）則約簡太冗余，即這兩種極端情況下的約簡結果都不太理想；當δ取2.0、2.5、3.0時，約簡結果較好。此外，其他數據集實驗都表現出類似結果，即適中的鄰域半徑能夠有效表現粒化非單調性并獲取較好屬性約簡，而表2中的半徑取值正是經過實驗分析所得的較好參數設置。

表3 5類UCI數據集的特定類約簡

表4 Wine數據集D1 類關于半徑增鏈的約簡

7 結束語

本文粒化分解決策表高層的鄰域（近似）條件熵，提取出中層的鄰域（近似）條件熵，獲得信息上下界與粒化非單調性，進而構建特定類屬性約簡及其啟發式約簡算法。本文構建鄰域（近似）條件熵深化了文獻[15-16]的相關度量，后續特定類屬性約簡推廣了文獻[2]的經典特定類約簡，而相關啟發式約簡算法模擬并優化了文獻[18]的算法。所得結果有利于特定類模式識別的不確定性度量與優化應用，值得深入探討。