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

唐鵬飛

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

0 引 言

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

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

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

1 集值決策表的相關知識

集值決策表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上相容關系：TB ＝｛（x，y） ∈U ×U ｜f（x，a） ∩f（y，a） ≠?，?a∈B｝，在TB下，對象x∈U關于B的相容類為TCB（x）＝｛y∈U ｜（x，y） ∈TB｝，所有相容類構成一個覆蓋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關于B的條件信息熵為：

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

決策類Dh關于B的近似精度為：

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

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

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

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

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

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

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

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

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

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

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

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

定義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 條分別對應“聯(lián)合充分性”和“個體必要性”。 特別地，近似條件熵的?；瘑握{(diào)性可以挖掘啟發(fā)式信息；由此，下面提出對應的屬性重要度，并建立啟發(fā)式約簡算法。

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

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

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

定理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設置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關于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），則重復該步驟選擇與更新過程，直到達到條件AHE（D ｜R）＝AHE（D ｜C），才執(zhí)行步驟5。

步驟5向前遍歷R中每個屬性a，若AHE（D ｜R -｛a｝）＝ AHE（D ｜R），則設置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é)通過一個實例，計算與分析近似條件熵性質及對應屬性約簡。

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

基于表1，構造自然屬性增鏈：

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

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

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

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

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

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

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

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

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

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

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

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

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

表3 本文算法的約簡結果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ù)相等。 說明本文算法的約簡結果更優(yōu)。

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

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

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

5 結束語

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