基于系統熵的粗糙集屬性約簡新方法

李偉濤，劉瓊蓀

(重慶大學 數學與統計學院，重慶 401331)

粗糙集(Rough Set)理論[1]是一種處理不確定、不完整知識的數學工具，最早是由Pawlak于1982年提出的。現在廣泛應用于數據挖掘、智能控制、模式識別等領域[2-3]。屬性約簡是粗糙集理論中的核心內容之一，有許多學者致力于粗糙集屬性約簡算法的研究。其中應用較多的是基于差別矩陣及在此基礎上的一些改進算法[4]，雖然該算法可以得到所有的約簡，但是只適合較小的數據集；基于代數觀點的相對約簡算法不能精確地度量粗糙集中的信息粒度劃分；苗奪謙[5]等人提出基于互信息的屬性約簡算法，是建立在條件屬性對決策屬性的信息量基礎上的。然而以上這些屬性約簡算法所依據的都是條件屬性的分類能力，它們的出發點都是一樣的，只是采用的標準有所不同。最近，有些學者提出新的屬性約簡定義，認為只關心條件屬性的分類能力是不夠的，決策屬性的分類能力也應該充分考慮，即基于系統熵的屬性約簡定義[6]，這種屬性約簡定義同時考慮到了條件屬性和決策屬性的分類能力，是一種較周全的屬性約簡模型。

本文從系統熵的角度出發，改進了原先的屬性重要度定義，給出了新的屬性重要性的度量方法，并構造了相應的啟發式算法，并通過實例驗證了算法的有效性。

1 粗糙集的基本概念

定義 1[7]：一個信息系統 S，表示為 S=(U，A，V，f)，其中 U={X1，…，Xn}是論域；A 是屬性集合；V=UVa，?∈aA，Va表示屬性的值域；f是一個信息函數，對 x∈U，a∈A有f(x，a)∈Va。若 A可以分為條件屬性集 C和決策屬性D，即 A=CUD，CID=φ，則稱該信息系統為決策表。

定義2[7]：在一個信息系統中，對于每個屬性子集B?A可以定義一個不可區分關系 IND(B)：IND(B)={(x，y)∈U×U：?b∈B，b(x)=b(y)}，稱為由 B 構造的不可分辨關系。

定義 3[7]：在信息系統 S中，對于屬性集 X?U，R為等價關系，定義2個子集為：

分別稱它們為X的R下近似和R上近似集。

定義 5[6]：設五元組 S=(U，C，D，V，f)是一個決策表。?P?C，U/P={P1，…，Pm}，U/D={D1，…，Dn}，決策表 S 的系統熵 H(U：P)定義為：

引理 1[6]：設五元組 S=(U，C，D，V，f)是一個決策表，對?B?C，有 H(U：C)≥H(U：B)。

定義 7[6]：設五元組 S=(U，C，D，V，f)是一個決策表，對?B?C，若 H(U：C)=H(U：B)，并且對?b∈B，均有 H(U：C)＞H(U：B-{b})，則稱 B 為條件屬性集 C 關于決策表屬性集D的一個基于系統熵的屬性約簡，簡稱B為決策表的基于系統熵的屬性約簡。

若所用的屬性約簡算法得到的約簡結果B同時滿足 H(U：C)≥H(U：B)和?b∈B，均有 H(U：C)＞H(U：B-{b})，則稱這個屬性約簡算法是一個完備的屬性約簡算法[8]。

2 基于改進系統熵的啟發式算法

2.1 改進的屬性重要性度量方法

設五元組 S=(U，C，D，V，f)是一個決策表，并且 R?C，則對于任意屬性a∈C-R的屬性重要度如定義8所示。

算法1：參考文獻[8]提出的基于系統熵的屬性約簡算法，以系統熵增益率的變化量作為屬性對決策的相對重要度為啟發式信息，基于系統熵增益率的屬性重要性度量方法為：

由式(1)定義的屬性重要度度量方法雖然考慮了屬性值域的大小，及屬性取值分布情況，但是由于數值的緣故，可能因為HA*(a)較小，進而導致sig(a)取值過大的情況出現。如果出現這種情況，依此屬性重要性選取的屬性對于決策屬性來說不一定是最重要的，這樣可能會導致約簡的個數增多，達不到所要求的約簡效果。

基于以上屬性重要性度量方法存在的一些問題，本文提出了一種新的屬性重要性度量方法：

這種新的度量方法同時兼顧了系統熵作為一種同時考慮了條件屬性和決策屬性的分類能力和數值大小對約簡結果的影響，并充分考慮到了在屬性子集R中添加屬性a∈C-R后系統熵的增量 (R自身的熵也被考慮在內)。這種新的屬性重要性的定義有如下特點：(1)當系統熵增量大小相等時，HA*(D/a)越小，相應的屬性重要度越大；(2)當 HA*(D/a)相等時，H(U：C)越大，則相應的屬性重要性越大。這兩個特性使得本文提出的屬性約簡算法在絕大多數的情況下都能夠做到使約簡的個數相對較少。

2.2 基于改進系統熵的啟發式算法

粗糙集的屬性約簡是指在不損失信息的情況下刪除信息系統中冗余的屬性，約簡結果的集合R={R：R?C，H(U：R)=H(U：C)}。所以說同樣的相關系數可以作為最終約簡的終止條件。本文根據式(2)定義的屬性重要度，提出一種改進的基于系統熵的粗糙集屬性約簡算法(算法2)。該算法采用backward約簡方式，依次剔除冗余的屬性，直到滿足終止條件 H(U：R)=H(U：C)，或者 H(U：C)-H(U：R)≤ω(ω 為指定的任意小的正整數)。

算法 2：

輸入：五元組 S=(U，C，D，V，f)，(其中 C 為條件屬性集合，D為決策屬性集合)，初始屬性集合R為空；

輸出：屬性約簡結果R。

此算法的時間復雜性為O(|A|3|U|log|U|)。

3 仿真實例和相關比較

為了驗證上述算法的有效性，從UIC數據庫中選取了三個具有離散屬性的數據庫實例進行驗證。分別采用文中所提到的兩種不同屬性重要性定義的約簡算法對其進行屬性約簡。約簡結果如表1所示。其中C為該屬性集合所包含的條件屬性的個數，算法1和算法2分別是以系統熵增益率和本文改進的系統熵增益率為屬性重要性度量方法的啟發式屬性約簡算法。從表中可以看到本文所提出的算法在大多數情況下獲得的相對約簡屬性個數較少。

表1 屬性約簡結果

為了進一步驗證文中所改進算法的特點，使用Zoo數據集如表 2所示。其中論域 U={1，…，101}，條件屬性C={hair，feathers，eggs，milk，airborne，aquatic，predator，toothed，backbone，breathes，venomous，fins，legs，tail，domestic，catsize}，D={type}為決策屬性。

表2 Zoo數據

如果按照式(1)所提出的屬性重要性來度量各個屬性的重要性，經計算得出屬性重要性最大的是{milk}。而依據本文所提出的屬性重要性得到的結果是 {eggs}，算法 1所得到的屬性約簡結果是：Ra={feathers，milk，airborne，aquatic，backbone，breathes，fins，legs}。

依照本文算法2所得到的屬性約簡結果是：Rb={milk，eggs，aquatic，legs}。這是因為利用式(1)計算屬性重要性的時候只考慮了屬性本身的值的分布而沒有考慮屬性的相對信息熵，如果某一屬性的相對信息熵較小會導致該屬性的屬性重要度較大，從而會使所選屬性并不是最重要的，或者造成錯選。

本文從系統熵的角度出發，定義了一種新的度量屬性重要性的方法，構造了相應的啟發式算法。相對于原算法，本文算法優勢明顯，通過實例證明，在大多數情況下本文的算法所得到的屬性約簡個數較少。

[1]PAWLAK Z.Rough sets[J].Int computer&science，1982；11(5)：341-356.

[2]常犁云，王國胤，吳渝.一種基于 Rough Set理論的屬性約簡及規則提取方法[J].軟件學報，1999，10(11)：1206-1211.

[3]Hu Xiaohua，CERCONE N.Learning in relational databases a rough set approach[J].International Journal of Computational Intelligence，1995，11(2)：320-340.

[4]RAUSZER S.The discernibility matrices and functions in information systems [M].Intelligent Decision Support-Handbook of Applications and Advances of the Rough Sets Theory.Dordrecht Kluwer，1992，31-362.

[5]苗奪謙，胡桂榮.知識約簡的一種啟發式算法[J].計算機研究與發展，1999，36(6)：681-684.

[6]Zhao Jun，Wu Zhongfu，Li Hua.System entropyand its application in feature selection[J].The Journal of China Universities of Posts and Telecommunications， 2004，11(1)：100-105.

[7]苗奪謙，李道國.粗糙集理論算法與應用[M].北京：清華大學出版社，2008.

[8]王雄彬，鄭雪峰，等，基于系統熵的屬性約簡的簡化差別矩陣方法 [J].計算機應用研究，2009，26(7)：2461-2464.