綜合屬性選擇和刪除的屬性約簡方法

楊成東，鄧廷權

(1.臨沂大學信息學院，山東臨沂 276005;2.哈爾濱工程大學理學院，黑龍江 哈爾濱 150001)

屬性約簡利用粗糙集［1-2］等理論，旨在保持信息系統決策能力不變的條件下，去除冗余屬性，從而減少數據的冗余度，是機器學習和人工智能最重要的研究方向之一.屬性約簡方法有很多，譬如基于依賴度的屬性約簡方法［3］、基于互信息的屬性約簡方法［4-5］、基于模糊粗糙集的屬性約簡方法［6-8］等.Skowron于1992年提出了辨識矩陣和辨識函數的概念［9］，利用辨識矩陣和辨識函數實現了屬性約簡，并得到了廣泛的研究［10］.然而，基于辨識矩陣的屬性約簡方法，存在不能得到約簡的可能性，仍具有冗余性.

1 基礎知識

給定決策系統 S=(U，C∩D，V，f)，其辨識矩陣定義為

式中:M(x，y)定義為

顯然，矩陣M中元素M(x，y)是由處于不同決策類中的對象x和y屬性值不同的屬性組成.

辨識函數f(M)定義為

式中:∨和∧是2個基本的二值邏輯運算:析取和合取.辨識函數是一個布爾表達式，通過等價的邏輯計算，將其化成若干個小合取式的析取式，那么每個小合取式就是一個約簡.一般地，約簡不是惟一的，決策系統的所有約簡用REDC(D)表示.

辨識矩陣和辨識函數有如下性質:

1)核是辨識矩陣中所有單個元素組成的集合;

2)辨識函數f(M)的極小析取范式中的所有合取式是屬性集C的所有約簡.

辨識矩陣和辨識函數方法能夠求出所有約簡，因此具有十分重要的理論意義.然而利用該方法求出的所有約簡仍是一個NP-hard問題，特別是在大規模數據集中幾乎無法求出約簡，其速度非常慢，而實際中通常只需要一個約簡.

2 辨識矩陣屬性約簡方法及其缺點

作為經典辨識矩陣算法，基于屬性頻率的辨識矩陣快速屬性約簡算法利用頻率作為衡量屬性重要程度的依據，具有重要的實用價值.在辨識矩陣中出現頻率最高的屬性是較為重要的，優先選擇該屬性.基于辨識矩陣屬性頻率的快速屬性約簡算法如下:

算法1 基于辨識矩陣屬性頻率的屬性約簡算法:

該算法中的時間復雜度分為關鍵2步:一是對屬性進行選擇有2個循環，時間復雜度為O(|C|2);另一個是計算單個屬性的頻率，時間復雜度為O(|U|).因此總的時間復雜度為:O(|U||C|2).

例1 給定關于大豆質量的決策系統S=(U，C∪D，V，f)如表1，其中 C={a，b，c，d，e}是條件屬性，D是決策屬性.

表1 決策系統Table 1 A decision system

通過計算，該信息系統有2個約簡，REDC(D)={{b，c}}.可以驗證該系統是協調決策系統，見表1.而利用算法1，求得的結果是{b，d，c}，顯然{b，d，c}?REDC(D)，仍包含了冗余屬性g0gggggg.該例說明經典算法不能有效計算約簡，仍具有一定的冗余性.本文提出一種新的屬性約簡方法來解決該問題.

3 結合屬性選擇和刪除的屬性約簡方法

首先證明算法1得到的屬性約簡沒有損失信息，即其依賴度相同.

定理1 給定決策系統S=(U，C∪D，V，f)，經過算法1后，得到red，那么

證明 反證法.假設γred(D)≠γC(D)，那么，γred(D)＜γC(D)，因此，存在 x∈PosC(D)，使得 x?Posred(D)，那么，存在 y∈［x］red，使得 M(x，y)≠?.然而這與算法1矛盾，因為經過算法1運算后，M是一個空矩陣，因此假設不成立.

例1說明了經典算法得到的red還具有一定冗余性，而定理1說明了經典算法得到的red與原始決策系統具有相同的分辨能力.因此，本文提出能有效避免冗余的辨識矩陣屬性約簡快速算法.

算法2 結合屬性選擇和刪除的屬性約簡快速算法:

算法2比算法1多了一個循環O(|U||C|)，由于這2個循環是并列的，那么總的時間復雜度為O(|U||C|2)+O(|U||C|)=O(|U||C|2)，因此算法2與算法1具有相同的時間復雜度，本文提出的算法的時間復雜度不會增加.

下面證明算法2選擇的屬性子集是約簡，既保持了信息，又有效地消除了冗余信息.

定理2 給定決策系統S=(U，C∪D，V，f)，經過算法2后，得到red，那么red是約簡.

證明 類似于定理1的證明，可以得到

另一方面，采用反證法證明red是獨立的.假設red不是獨立的，那么存在a∈red，滿足

那么這樣的屬性a在14)～19)的循環中被刪除了，即 a?red.

因此，假設不成立，red是獨立的.所以，red是約簡.

例2 繼續使用例1，利用算法2，可以得到約簡red={b，c}.因此，與基于辨識矩陣屬性約簡方法相比，該方法能夠有效地獲得約簡.

4 實驗與分析

用6個UCI標準數據集來驗證本文提出的方法的實用性和有效性，如表2所示.表3對經典方法選擇的屬性序列和本文提出的方法選擇的屬性序列進行了比較.利用經典方法得到的6個數據集中，Heart、Lymph、Soybean 有 3 個不是約簡.而本文方法得到的都是約簡，有效地解決了經典方法得不到約簡的問題.

表2 UCI標準數據集Table 2 UCI standard datasets

表3 與經典方法的比較Table 3 Comparison of UCI standard datasets and the classical approaches

從選擇屬性個數來看，與原始數據集對比，經典算法和本文提出的方法都大大減少平均屬性個數.進一步地，本文算法的平均屬性個數為8.5，比經典算法減少了1.3個.因此，本文提出的方法能夠獲得更為精簡的集約數據集，進一步降低了數據集的冗余性.

5 結束語

本文提出了結合屬性選擇和刪除的屬性約簡方法，該方法能夠徹底解決經典算法產生的冗余，得到有效的約簡，解決了經典算法不能得到約簡的問題.通過6個UCI標準數據集，實例分析表明，提出的方法選擇的平均屬性個數比經典算法減少了1.3個，顯示了其有效性和實用性.

［1］張文修，吳偉志，梁吉業，等.粗糙集理論與方法［M］.北京:科學出版社，2001:5-7.

［2］PAWLAK Z.Rough sets［J］.International Journal of Computer and Information Sciences，1982，11(5):341-356.

［3］蔣云良，楊章顯，劉勇.不協調信息系統快速屬性分布約簡方法［J］.自動化學報，2012，38(3):382-388.

JIANG Yunliang，YANG Zhangxian，LIU Yong.Quick distribution reduction algorithm in inconsistent information system［J］.Acta Automatica Sinica，2012，38(3):382-388.

［4］XU F，MIAO D，WEI L.Fuzzy-rough attribute via mutual information with an application to cancer classification［J］.Computers and Mathematics with Applications，2009，57(6):1010-1017.

［5］BHATT R，GOPAL M.On fuzzy-rough sets approach to feature selection［J］.Pattern Recognition Letters，2004，26(7):965-975.

［6］胡清華，于達仁，謝宗霞.基于鄰域粒化和粗糙逼近的數值屬性約簡［J］.軟件學報，2008，19(3):640-649.

HU Qinghua，YU Daren，XIE Zongxia.Numerical attribute reduction based on neighborhood granulation and rough approximation［J］.Journal of Software，2008，19(3):640-649.

［7］TSANG E C C，CHEN D G，YEUNG D S，et al.Attribute reduction using fuzzy rough sets［J］.IEEE Transactions on Fuzzy Systems，2008，16(5):1130-1141.

［8］張志飛，苗奪謙.基于粗糙集的文本分類特征選擇算法［J］.智能系統學報，2009，4(5):453-457.

ZHANG Zhifei，MIAO Duoqian.Feature selection for text categorization based on rough set［J］.CAAI Transactions on Intelligent Systems，2009，4(5):453-457.

［9］SKOWRON A，RAUSZER C.The discernibility matrices and functions in information systems［M］//Intelligent Decision Support，Handbook of Applications and Advances of the Rough Sets Theory.Dordrecht:Kluwer Academic Publishers，1992:331-362.

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

CHANG Liyun，WANG Guoyin，WU Yu.An approach for attribute reduction and rule generation based on rough set theory［J］.Journal of Software，1999，10(11):1206-1211.