楊成東，鄧廷權(quán)

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

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

1 基礎(chǔ)知識

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

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

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

辨識函數(shù)f(M)定義為

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

辨識矩陣和辨識函數(shù)有如下性質(zhì):

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

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

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

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

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

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

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

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

表1 決策系統(tǒng)Table 1 A decision system

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

3 結(jié)合屬性選擇和刪除的屬性約簡方法

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗與分析

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

表2 UCI標準數(shù)據(jù)集Table 2 UCI standard datasets

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

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

5 結(jié)束語

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

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

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

［3］蔣云良，楊章顯，劉勇.不協(xié)調(diào)信息系統(tǒng)快速屬性分布約簡方法［J］.自動化學(xué)報，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］胡清華，于達仁，謝宗霞.基于鄰域?；痛植诒平臄?shù)值屬性約簡［J］.軟件學(xué)報，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］.智能系統(tǒng)學(xué)報，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理論的屬性約簡及規(guī)則提取方法［J］.軟件學(xué)報，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.