基于近似條件熵的集值決策表屬性約簡算法

唐鵬飛

（1 四川師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 成都 610066； 2 四川師范大學(xué) 智能信息與量子信息研究所， 成都 610066）

0 引 言

屬性約簡是粗糙集理論的核心內(nèi)容之一，主要是在保持相同分類能力的前提下進行冗余屬性刪除，從而達到數(shù)據(jù)表的優(yōu)化處理［1］。 近似條件熵作為一種由近似精度與條件信息熵信息融合得到的強健度量模型，已廣泛應(yīng)用于不確定性測量、屬性約簡、機器學(xué)習(xí)。 對于經(jīng)典決策表，文獻［2］首先提出基于近似條件熵的屬性約簡；進一步，文獻［3-4］將近似條件熵推廣到鄰域粗糙集；文獻［5］利用近似條件熵進行電務(wù)設(shè)備故障預(yù)測；文獻［6］分解近似條件熵，提出鄰域粗糙集的特定類屬性約簡。 可見，近似條件熵是信息表進行屬性約簡的有效手段，具有重要的現(xiàn)實應(yīng)用意義。

集值決策表是經(jīng)典決策表的一種擴展，近年來已經(jīng)開展了一系列相關(guān)研究。 例如，文獻［7］采用條件信息熵構(gòu)建集值系統(tǒng)屬性約簡。 文獻［8］基于相容關(guān)系，提出信息熵、粗糙熵、知識粒度來刻畫集值信息系統(tǒng)的不確定性。 文獻［9］采用信息量構(gòu)建集值信息系統(tǒng)屬性約簡。 文獻［10］基于集值信息系統(tǒng)上的優(yōu)勢關(guān)系，提出多粒度優(yōu)勢關(guān)系粗糙集模型。 文獻［11］基于相容關(guān)系，研究了一致集值決策信息系統(tǒng)中的屬性約簡和判斷問題。 文獻［12］針對集值數(shù)據(jù)提出2 種模糊粗糙近似，并分別構(gòu)建其相對正域約簡。 文獻［13］從知識粒度視角，提出集值信息系統(tǒng)的動態(tài)屬性約簡算法。 文獻［14］基于巴氏距離提出λ 容差關(guān)系，研究了概率集值信息系統(tǒng)的動態(tài)變精度粗糙集模型。 文獻［15］針對集值決策信息系統(tǒng)中數(shù)據(jù)動態(tài)變化，構(gòu)建增量式屬性約簡算法。 文獻［16］采用正域構(gòu)建集值信息系統(tǒng)快速約簡算法。 文獻［17］基于模糊相容關(guān)系，引入依賴度構(gòu)建集值信息系統(tǒng)屬性約簡。 歸納可見，現(xiàn)有的集值決策信息系統(tǒng)屬性約簡僅從代數(shù)角度或信息角度單方面出發(fā)。 前者刻畫屬性對論域中確定分類子集的影響，后者刻畫屬性對論域中不確定分類子集的影響［18］，存在局限性。

針對上述問題，本文引入近似條件熵，構(gòu)建集值決策表的屬性約簡。 具體地，基于相容關(guān)系，將近似精度與條件信息熵信息融合建立強健的近似條件熵度量模型，挖掘度量的粒化單調(diào)性，從而自然構(gòu)建基于近似條件熵的屬性約簡及啟發(fā)算法，最后提供實例分析與實驗驗證。

1 集值決策表的相關(guān)知識

集值決策表SVDT ＝｛U，AT ＝C∪D，V，f｝。 其中，U ＝｛x1，x2，…，xn｝ 為非空有限論域；C為條件屬性集，D為決策屬性集，C∩D ＝?； 屬性值域V ＝∪a∈ATVa，這里Va為任意屬性a∈AT的值域；信息函數(shù)f：U × AT→Va， 并賦予x在屬性a上的值f（x，a）∈Va。 對任意條件屬性子集B?C，定義U上相容關(guān)系：TB ＝｛（x，y） ∈U ×U ｜f（x，a） ∩f（y，a） ≠?，?a∈B｝，在TB下，對象x∈U關(guān)于B的相容類為TCB（x）＝｛y∈U ｜（x，y） ∈TB｝，所有相容類構(gòu)成一個覆蓋U／TB ＝｛TCB（x）｜x∈U｝。 決策屬性集D在U上的劃分U／TD ＝｛D1，…，Dm｝，而且TD ＝｛（x，y） ∈U ×U ｜f（x，D）＝f（y，D）｝，Dh（1≤h≤m） 表示決策類。 本文用表示集合的基數(shù)。

定義1［7］決策劃分U／TD關(guān)于B的條件信息熵為：

定義2［16］決策類Dh關(guān)于B的下、上近似集分別為：

決策類Dh關(guān)于B的近似精度為：

定理1［7，16］決策分析原理可表示為：

（1）B?C?αB（Dh） ≤αC（Dh）；

（2）B?C?HE（D ｜C） ≤HE（D ｜B）

定義1 提供條件信息熵，其僅能刻畫粒化結(jié)構(gòu)的不確定性；定義2 提供近似精度，其僅能度量近似分類的不確定性［19］。 這2 種單一度量模型都存在一定的局限性。 因此，本文將兩者進行信息融合，構(gòu)建一種更為全面的度量模型，設(shè)計出一種更優(yōu)的約簡算法。

2 基于近似條件熵的啟發(fā)式屬性約簡算法

本節(jié)在條件信息熵與近似精度基礎(chǔ)上，構(gòu)建基于近似條件熵的屬性約簡及其啟發(fā)式約簡算法，并提供實例說明算法的有效性。 為此，首先通過信息融合提出近似條件熵。

定義3決策劃分U／TD關(guān)于B的近似條件熵為：

近似條件熵引入近似精度作為條件信息熵的權(quán)重系數(shù)，有效融合了兩者的優(yōu)點，變得更為強健。 既能度量近似分類的不確定性，又能表征粒化結(jié)構(gòu)的不確定性，是一種更加全面的度量模型。

定理2B?C?AHE（D ｜C） ≤AHE（D ｜B）

證明因為B?C， 由定理1 可得αB（Dh） ≤αC（Dh），HE（D ｜C） ≤HE（D ｜B）。 結(jié)合定義3 可得AHE（D ｜C） ≤AHE（D ｜B）。 證畢。

推論1AHE（D ｜B）∈［0，｜U ｜log2｜U ｜］。特別地，當(dāng)U／TB最細時（即?x∈U，TCB（x）＝｛x｝），AHE（D ｜B） 取得最小值為0。 當(dāng)U／TB最粗時（即?x∈U，TCB（x）＝U）， 且決策劃分最細時（即?Dh∈U／TD，｜Dh ｜＝1），AHE（D ｜B） 取得最大值為｜U ｜log2｜U ｜。

定理2 表明，通過信息融合得到的近似條件熵仍具有粒化單調(diào)性。 進而，推論1 給出相應(yīng)的值域與最值條件。 接下來，給出屬性的必要性和獨立性定義。

定義4?a∈C，AHE（D ｜C）≠AHE（D ｜C -｛a｝），則稱a為C中D必要的屬性，否則稱a為C中D不必要的屬性。

定義5若?a∈C為C中D必要的屬性，則稱C為D獨立的。 由C中所有D必要的屬性組成的集合，稱為C中D的核，記為CoreC（D）。

基于上述近似條件熵的度量語義與粒化單調(diào)性，給出以下近似條件熵約簡的定義。

定義6B?C為基于近似條件熵的屬性約簡，若能滿足2 個條件：

（1）AHE（D ｜B）＝AHE（D ｜C）；

（2）?a∈B，AHE（D ｜B -｛a｝） ≠AHE（D ｜B）

這里，屬性約簡模擬經(jīng)典情況，主要依托近似條件熵這一核心度量及其粒化單調(diào)性。 定義6 中的2 條分別對應(yīng)“聯(lián)合充分性”和“個體必要性”。 特別地，近似條件熵的粒化單調(diào)性可以挖掘啟發(fā)式信息；由此，下面提出對應(yīng)的屬性重要度，并建立啟發(fā)式約簡算法。

定義7B?C且a∈B，則a對于B關(guān)于決策劃分U／TD的內(nèi)屬性重要度為：

B?C，?a∈C -B，則a對于B關(guān)于決策劃分U／TD的外屬性重要度為：

內(nèi)屬性重要度SIGinner（a，B，D） 刻畫在B中刪除屬性a之后近似條件熵值的增加量，而外屬性重要度SIGouter（a，B，D） 刻畫在B上添加屬性a之后近似條件熵值的減少量。 相關(guān)度量值變化越大，則說明該屬性越重要，因此兩者提供了快速約簡的屬性選擇機制。 根據(jù)核屬性概念（定義5），下面利用內(nèi)屬性重要度構(gòu)造一個求核方法。

定理3?a∈C，則a為C中D必要的屬性?SIGinner（a，C，D）＞0，從而，CoreC（D）＝｛a∈C ｜SIGinner（a，C，D）＞0｝ （8）

證明若a為C中D必要的屬性，則AHE（D ｜C） ≠AHE（D ｜C -｛a｝），由近似條件熵的粒化單調(diào)性知，AHE（D ｜C）＜AHE（D ｜C -｛a｝）， 因此SIGinner（a，C，D）＞0。 反之，若SIGinner（a，C，D）＞0，則AHE（D ｜ C -｛a｝）＞ AHE（D ｜ C）， 從而AHE（D ｜C）≠AHE（D ｜C -｛a｝）。 由定義4 知，a為C中D必要的屬性，故式（8）成立。 證畢。

依據(jù)上述近似條件熵及約簡的定義，下面以定義7 的2 種屬性重要度為啟發(fā)式信息，開發(fā)一個以核為約簡起點的啟發(fā)式約簡算法，從而快速獲取一個屬性約簡。 算法步驟具體如下。

算法1 基于近似條件熵的啟發(fā)式約簡算法

輸入：集值決策表SVDT ＝｛U，AT ＝C∪D，V，f｝

輸出：該區(qū)間集決策信息表的一個約簡R

步驟1計算AHE（D ｜C）。

步驟2設(shè)置CoreC（D）＝?，?a∈C，計算內(nèi)屬性重要度SIGinner（a，C，D），若SIGinner（a，C，D）＞0，則CoreC（D）＝CoreC（D） ∪｛a｝，得到C中D的核CoreC（D），令R ＝CoreC（D）。

步驟3計算決策劃分U／D關(guān)于R的近似條件熵。 若AHE（D ｜R）＝AHE（D ｜C），則執(zhí)行步驟5，否則執(zhí)行步驟4。

步驟4?a∈（C - R）， 計算外屬性重要度SIGouter（a，R，D），靠前選擇外屬性重要度最大的條件屬性a*并入R中，即進行更新R←R∪｛a*｝。如果此時有AHE（D ｜R）＞AHE（D ｜C），則重復(fù)該步驟選擇與更新過程，直到達到條件AHE（D ｜R）＝AHE（D ｜C），才執(zhí)行步驟5。

步驟5向前遍歷R中每個屬性a，若AHE（D ｜R -｛a｝）＝ AHE（D ｜R），則設(shè)置R←R -｛a｝。

步驟6返回R。

算法1 是以核為約簡起點的啟發(fā)式約簡算法。步驟2 通過內(nèi)屬性重要度尋找到核屬性集，步驟3對其進行評估，若步驟2 得到的子集R的近似條件熵大于全集C的（即AHE（D ｜R）＞AHE（D ｜C）），則需進入步驟4 通過外屬性重要度對剩余屬性進行啟發(fā)式搜索，并通過順序選取最優(yōu)屬性以快速完成添加。 可見，臨近步驟5 的R必然滿足約簡“聯(lián)合充分性”，但不一定滿足約簡“個體必要性”。 由此，步驟5 采取后項刪除過程，以確保獲得“個體必要性”，從而R是一個基于近似條件熵的屬性約簡，最終被有效輸出。

3 實例分析

本節(jié)通過一個實例，計算與分析近似條件熵性質(zhì)及對應(yīng)屬性約簡。

例1集值決策表見表1。 其中，U／TD ＝｛D1，D2｝＝｛｛x1，x2，x3，x4｝，｛x5，x6，x7，x8｝｝。

基于表1，構(gòu)造自然屬性增鏈：

B1＝｛a1｝?B2＝｛a1，a2｝?B3＝｛a1，a2，a3｝?B4＝｛a1，a2，a3，a4｝ ?C ＝｛a1，a2，a3，a4，a5｝。

作為例子，選取屬性增鏈中的鏈元B2。 計算其誘導(dǎo)的相容類為：

由此，可得決策類D1、D2關(guān)于B2的近似精度分別為：

下面分別計算決策類D1、D2關(guān)于B2的條件信息熵為：

最后，計算決策劃分U／TD關(guān)于B2的近似條件熵為：

基于上述案例機制并經(jīng)過類似計算，下面直接給出關(guān)于屬性增鏈的近似條件熵及其大小關(guān)系，即：AHE（D ｜C）＝1.617 6。

上述關(guān)于屬性增鏈的不等式驗證了近似條件熵的粒化單調(diào)性（定理2）。 所有度量值均隸屬理論雙界范圍［0，｜U ｜log2｜U ｜］（推論1）。

最后根據(jù)算法1 求解該集值決策表的一個屬性約簡。 執(zhí)行步驟1，計算決策劃分U／TD關(guān)于C的近似條件熵為AHE（D ｜C）＝1.617 6。 執(zhí)行步驟2，設(shè)置CoreC（D）＝?，計算C中每個屬性關(guān)于決策劃分U／TD的內(nèi)屬性重要度為：

由計算可知，滿足條件的屬性為a1與a5， 則CoreC（D）＝｛a1，a5｝， 令R ＝CoreC（D）。 執(zhí)行步驟3，計算決策劃分U／TD關(guān)于R的近似條件熵為AHE（D ｜R）＝3.108 6 ≠AHE（D ｜C）。 執(zhí)行步驟4，?a∈（C-R），計算每個屬性對于R關(guān)于決策劃分U／TD的外屬性重要度為：

選擇外屬性重要度最大的屬性a4并入R中，即R更新為R ＝｛a1，a4，a5｝。 計算決策劃分U／TD關(guān)于R的近似條件熵為AHE（D ｜ R）＝1.617 6＝AHE（D ｜C）。 即R滿足約簡第一條，所以執(zhí)行步驟5，向前遍歷刪除R中的每個屬性a，有AHE（D ｜R -｛a｝） ≠AHE（D ｜R），進入步驟6，返回R，即約簡結(jié)果為R ＝｛a1，a4，a5｝。

4 UCI 數(shù)據(jù)實驗

本節(jié)實施數(shù)據(jù)實驗來驗證近似條件熵及其屬性約簡，主要是粒化單調(diào)性（定理2）與啟發(fā)式約簡算法（算法1）。 將算法1 與如下信息角度和代數(shù)角度具有代表性的集值決策表啟發(fā)式約簡算法從約簡個數(shù)與分類精度進行比較，即：基于條件信息熵約簡算法［7］、基于信息量約簡算法［9］和基于正域約簡算法［16］。 實驗環(huán)境為：操作系統(tǒng)Windows10 64b，Intel（R） Core（TM） i5-8200Y CPU ＠ 1.61 GHz，內(nèi)存4.00 GB，采用Matlab2018a 進行編程實現(xiàn)。 下面從UCI 數(shù)據(jù)集中挑選8 組數(shù)據(jù)集，見表2。 在實驗前均使用文獻［16］中的方法，將UCI 數(shù)據(jù)集轉(zhuǎn)化為集值決策表。

表2 數(shù)據(jù)集Tab.2 Data sets

為表現(xiàn)度量變化，選取自然屬性增｛a1｝ ?｛a1，a2｝ ?…?C。 針對8 個數(shù)據(jù)集，分別進行了實驗計算，相關(guān)度量結(jié)果見圖1。 在圖1 中，x軸標(biāo)識屬性個數(shù)，y軸標(biāo)識近似條件熵度量值。 觀測可見，近似條件熵值隨屬性個數(shù)的增加而減少，說明其具有屬性粒化單調(diào)性，與定理2 一致。 基于這些單調(diào)曲線，從核出發(fā)追求與全部條件屬性集近似條件熵相等的屬性約簡是合理的，則可以得到一個適當(dāng)長度的約簡結(jié)果。 下面給出8 個數(shù)據(jù)集在本文算法下的具體約簡結(jié)果，見表3。 表4 則給出8 個數(shù)據(jù)集在各約簡算法下的約簡個數(shù)。

圖1 8 類UCI 數(shù)據(jù)集關(guān)于屬性增鏈的度量變化Fig.1 The measure changes of the 8 types of UCI data sets on the attribute-addition chain

表3 本文算法的約簡結(jié)果Tab.3 The reduction results of the algorithm in this paper

表4 不同算法的約簡個數(shù)Tab.4 Number of reductions for different algorithms

由表4 可知，4 種算法約簡后的屬性個數(shù)都小于原始數(shù)據(jù)的屬性個數(shù)，說明對數(shù)據(jù)集進行優(yōu)化處理是有必要的。 比較4 種算法的約簡個數(shù)，本文算法在部分數(shù)據(jù)集上約簡個數(shù)更少，例如Glass、Iris、Zoo 與Vehicle 數(shù)據(jù)集；而在其余數(shù)據(jù)集上，與其它3種算法的約簡個數(shù)相等。 說明本文算法的約簡結(jié)果更優(yōu)。

最后比較不同算法的分類精度。 這里采用SVM 分類器，對表4 中8 個數(shù)據(jù)集的約簡結(jié)果進行十折交叉分類訓(xùn)練，得到各算法約簡結(jié)果的分類精度值，具體見表5。

表5 SVM 分類器下不同算法的分類精度比較Tab.5 Comparison of classification accuracy of different algorithms under SVM classifier %

在表5 中，“√”符號標(biāo)識4 種算法約簡集下分類精度的最大值，“-”符號標(biāo)識4 種算法約簡集下分類精度持平。 觀察表5 可知，本文算法在大部分數(shù)據(jù)集中，分類精度高于或等于其它3 種算法，僅在Heart、Diabetes 與Ecoli 數(shù)據(jù)集中與其它3 種算法持平。 這是因為其它3 種算法都是采用的單一度量方式，存在局限性；而本文算法采用的近似條件熵是由近似精度與條件信息熵信息融合所得，是一種更加全面的度量模型，從而具有更優(yōu)的分類性能。

5 結(jié)束語

本文基于近似精度與條件信息熵，提出近似條件熵，構(gòu)建基于近似條件熵的屬性約簡及其啟發(fā)式約簡算法。 通過具體實例與數(shù)據(jù)實驗，驗證了近似條件熵性質(zhì)的正確性與約簡算法的有效性，實驗結(jié)果表明，本文算法不僅能夠獲得更優(yōu)的約簡結(jié)果，而且分類精度更高。 所得結(jié)果深化了信息學(xué)習(xí)與特征選擇，對集值決策表的知識發(fā)現(xiàn)與規(guī)則推導(dǎo)具有意義。 下一步將對集值決策表的規(guī)則提取進行研究。此外，降低本文算法的時間復(fù)雜度，提高其運行效率，也是接下來的研究重點。