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

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

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

1 基礎(chǔ)知識(shí)

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

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

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

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

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

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

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

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

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

2 辨識(shí)矩陣屬性約簡(jiǎn)方法及其缺點(diǎn)

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

算法1 基于辨識(shí)矩陣屬性頻率的屬性約簡(jiǎn)算法:

該算法中的時(shí)間復(fù)雜度分為關(guān)鍵2步:一是對(duì)屬性進(jìn)行選擇有2個(gè)循環(huán)，時(shí)間復(fù)雜度為O(|C|2);另一個(gè)是計(jì)算單個(gè)屬性的頻率，時(shí)間復(fù)雜度為O(|U|).因此總的時(shí)間復(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

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

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

首先證明算法1得到的屬性約簡(jiǎn)沒(méi)有損失信息，即其依賴度相同.

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與分析

用6個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集來(lái)驗(yàn)證本文提出的方法的實(shí)用性和有效性，如表2所示.表3對(duì)經(jīng)典方法選擇的屬性序列和本文提出的方法選擇的屬性序列進(jìn)行了比較.利用經(jīng)典方法得到的6個(gè)數(shù)據(jù)集中，Heart、Lymph、Soybean 有 3 個(gè)不是約簡(jiǎn).而本文方法得到的都是約簡(jiǎn)，有效地解決了經(jīng)典方法得不到約簡(jiǎn)的問(wèn)題.

表2 UCI標(biāo)準(zhǔn)數(shù)據(jù)集Table 2 UCI standard datasets

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

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

5 結(jié)束語(yǔ)

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

［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)快速屬性分布約簡(jiǎn)方法［J］.自動(dòng)化學(xué)報(bào)，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］胡清華，于達(dá)仁，謝宗霞.基于鄰域?；痛植诒平臄?shù)值屬性約簡(jiǎn)［J］.軟件學(xué)報(bào)，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é)報(bào)，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］常犁云，王國(guó)胤，吳渝.一種基于Rough Set理論的屬性約簡(jiǎn)及規(guī)則提取方法［J］.軟件學(xué)報(bào)，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.