逄玉俊　李　爽

摘 要：針對(duì)信息系統(tǒng)在屬性約簡(jiǎn)過(guò)程中存在屬性頻率值相同的問(wèn)題進(jìn)行改進(jìn)，改進(jìn)后的算法在基于可辨識(shí)矩陣屬性頻率約簡(jiǎn)算法的基礎(chǔ)上，引進(jìn)強(qiáng)等價(jià)集概念，以屬性在可辨識(shí)矩陣中出現(xiàn)的次數(shù)越多其重要性越大為啟發(fā)式信息，利用強(qiáng)等價(jià)集中的屬性是可以約簡(jiǎn)的特性，在屬性頻率約簡(jiǎn)過(guò)程中判斷具有相同屬性頻率屬性是否最終包含在核屬性集里，提出改進(jìn)的屬性頻率約簡(jiǎn)算法。通過(guò)理論和實(shí)例的分析證明，該算法在保持時(shí)間復(fù)雜度不變的情況下，處理具有相同屬性頻率信息系統(tǒng)的屬性約簡(jiǎn)，使其準(zhǔn)確性得到提高，與原算法相比，改進(jìn)后的算法可以得到一個(gè)更為精準(zhǔn)的約簡(jiǎn)結(jié)果。

關(guān)鍵詞：粗糙集;可辨識(shí)矩陣;強(qiáng)等價(jià)集;屬性頻率

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：1004－373X(2009)04－145－03

Attribute Frequency Reduction Arithmetic Based on Discernibile Matrix of Rough Set

PANG Yujun,LI Shuang

(Shenyang Institute of Chemical Technology College,Shenyang,110142,China)

Abstract：In the view of improving system exsists the same attribute frequency value in attribute reduction,the improved algorithm based on discernibile matrix affribute frequency reduction arithmentic,the concept of strong equivalent set is introduced to identify attributes in the matrix in the number of the more importance to the greater heuristics.Using strong focus on the strong equivalent set is the reduction of the frequency attribute reduction in judgements have the same attributes′frequency of property included in the final set of attributes,and the properties frequency reduction algorithm is improved.Through theoretical analysis and examples prove that the algorithm to maintain the same time complexity of the situation,to deal with the same attributes′ frequency of information systems attribute reduction,the accuracy is improved,compared with the original algorithm,improved algorithm can get a more precise reduction results.

Keywords：rough set;discernibility matrix;strong compressible set;attribute reduction

0 引言

粗糙集理論是由波蘭數(shù)學(xué)家Z.Pawlak在1982年提出的一種智能決策分析數(shù)學(xué)工具。它是研究不完整，不確定知識(shí)和數(shù)據(jù)的表達(dá)、學(xué)習(xí)、歸納的理論方法。粗糙集目前主要被廣泛地應(yīng)用與數(shù)據(jù)挖掘、人工智能、模式識(shí)別、網(wǎng)頁(yè)分類、故障診斷和專家系統(tǒng)等領(lǐng)域［1］。

屬性約簡(jiǎn)是粗糙集理論中重要的核心內(nèi)容之一。屬性約簡(jiǎn)主要目的是保持知識(shí)庫(kù)分類能力不變的條件下，刪除其中不相關(guān)或不重要的屬性，從而簡(jiǎn)化原有的系統(tǒng)。雖然Wond等已經(jīng)證明找出一個(gè)決策表的所有約簡(jiǎn)和最小約簡(jiǎn)是NP－h(huán)ard問(wèn)題，但是利用啟發(fā)式信息減小搜索空間，還是能得到一個(gè)相對(duì)最優(yōu)的約簡(jiǎn)［2］。

以基于可辨識(shí)矩陣的屬性頻率約簡(jiǎn)算法為基礎(chǔ)，引入強(qiáng)等價(jià)集概念，以屬性在可辨識(shí)矩陣中出現(xiàn)的次數(shù)越多，其重要性越大為啟發(fā)式信息。提出一種新的有效的屬性約簡(jiǎn)算法，該算法可以處理當(dāng)屬性頻率相同時(shí)，對(duì)決策表的屬性約簡(jiǎn)可以高效準(zhǔn)確的進(jìn)行。

1 相關(guān)概念和證明

1.1 決策表

形式上，四元組S=(U,A,V,f)是一個(gè)知識(shí)表達(dá)系統(tǒng)，其中U為對(duì)象的非空有限集合，稱為論域；A為屬性的非空有限集合；V=∪a∈AVa，Va是屬性a的值域;f為U×A→V是一個(gè)信息函數(shù)，它為每個(gè)對(duì)象的每個(gè)屬性賦予一個(gè)信息值，即對(duì)于所有的a∈A,x∈X,f(x,a)∈Va［3］。

知識(shí)表達(dá)系統(tǒng)也稱為智能系統(tǒng)。通常也用S=(U,A)來(lái)代替S=(U,A,V,f)。

1.2 約簡(jiǎn)和核

在信息系統(tǒng)S中，對(duì)于P罜，則P在S的不可分辨關(guān)系IND(P)定義為：

IND(P)={(x,y)∈U2|衋∈P,a(x)=a(y)}

IND(P)把對(duì)象集U劃為k個(gè)等價(jià)類，記為U/P={X1,X2,…,Xk}。

定義1［4］：設(shè)Q罰，如果Q是獨(dú)立的，并且IND(Q)=IND(P)，則稱Q是P的一個(gè)約簡(jiǎn)。P中所有必要關(guān)系的集合稱為P的核，用CORE(P)來(lái)表示。

定理1：簇集P的核等于P的所有約簡(jiǎn)的交集。即CORE(P)=∩RED(P)。

1.3 可辨識(shí)矩陣

令決策表系統(tǒng)S=＜U,R,V,f＞,R=C∪D是屬性集合；子集P={a i|i=1,2,…,m}和D=syggg00分別稱為條件屬性和決策屬性集；U={x1,x2,…,xn}是論域，ai(xj)是樣本xj在屬性ai上的取值。CD(i,j)表示可辨識(shí)矩陣中第i行和第j列的元素，則可辨識(shí)矩陣CDФㄒ澹5］為:

CD(i,j)={ak|ak∈P∧ak(xi)≠ak(xj)},d(xi)≠d(xj);

0,d(xi)=d(xj)

其中：i,j=1,2,…,n。

1.4 強(qiáng)等價(jià)集

設(shè)a∈A，如果存在某一集合B粒踑］，則稱集合B是屬于a的強(qiáng)等價(jià)集［6］。

定理2：A的子集B罙是強(qiáng)等價(jià)集的充分必要條件是：B被區(qū)分矩陣中2個(gè)或2個(gè)以上項(xiàng)同時(shí)包含，且B與區(qū)分矩陣中其它項(xiàng)的交為空。

定理3：如果C是一個(gè)約簡(jiǎn)，B是強(qiáng)等價(jià)集，且{a,b}∈B，則{a,b}不包含于C。

此定理可用反證法證明，證明過(guò)程［6］如下：

證明：假定C是一個(gè)約簡(jiǎn)，且有{a,b}罜因?yàn)閧a,b}∈B且B是強(qiáng)等價(jià)集，所以有Dis({a})=Dis()，于是有Dis(C－{a})=Dis(a)即IND(C－{a})=IND(C)，這與C是一個(gè)約簡(jiǎn)相矛盾，因此應(yīng)有{a,b}不包含于C。可見，任何一個(gè)約簡(jiǎn)最多只能包含強(qiáng)等價(jià)集中的一個(gè)屬性，簡(jiǎn)而言之，強(qiáng)等價(jià)集中的屬性是可以約簡(jiǎn)的。

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

2.1 算法思想

胡可云博士提出關(guān)于屬性頻率有兩種重要的啟發(fā)式思想［7］：

（1） 屬性在可辨識(shí)矩陣中出現(xiàn)的次數(shù)越多，該屬性的重要性越大；

（2） 在可辨識(shí)矩陣中屬性項(xiàng)越短，屬性的重要性越大。

由思想（2）可知：在可辨識(shí)矩陣中，可能會(huì)有一些只有1個(gè)屬性的屬性項(xiàng)，則這個(gè)惟一的屬性一定是核屬性，可直接把它加入到約簡(jiǎn)集中。提出一種新的計(jì)算屬性頻率的函數(shù)：

g(ai)=countai∑nj=2(counterai/j)

式中：countai體現(xiàn)出屬性在可辨識(shí)矩陣中出現(xiàn)的次數(shù)越多，這個(gè)屬性的重要性越大；counterai為屬性ai在可辨識(shí)矩陣中出現(xiàn)的總次數(shù)；j為含有屬性ai的屬性項(xiàng)中屬性的個(gè)數(shù)，n為含有屬性ai所有項(xiàng)中，屬性個(gè)數(shù)最多的項(xiàng)的屬性個(gè)數(shù)。基于此公式，可以計(jì)算出屬性頻率。

在文獻(xiàn)［3］中，算法的缺陷在于不能很好地解決出現(xiàn)2個(gè)屬性頻率相同時(shí)的情況。針對(duì)這個(gè)問(wèn)題，這里引入強(qiáng)等價(jià)集概念對(duì)屬性進(jìn)行區(qū)分。定理2表明強(qiáng)等價(jià)集中的屬性對(duì)分類具有相同的重要性。利用定理3判斷，當(dāng)屬性頻率相同時(shí)是否有屬性包含在強(qiáng)等價(jià)集中，可以保留出現(xiàn)在強(qiáng)等價(jià)集中的某個(gè)屬性去掉其他屬性。

2.2 算法描述

輸入：決策表S=(U,C∪D,V,f)，其中C={a1,a2,…,an}；

輸出：決策表的約簡(jiǎn)集Red。

（1） 把決策表S轉(zhuǎn)化成相應(yīng)的可辨識(shí)矩陣M，并初始化候選約簡(jiǎn)集合Red=h，令counterai=0；

（2） 將可辨識(shí)矩陣中屬性組合數(shù)為1的條件屬性（核屬性）直接加到約簡(jiǎn)集Red中，去掉含有核屬性的屬性項(xiàng)；

（3） 利用屬性頻率函數(shù)g(ai)對(duì)剩余屬性項(xiàng)中的各屬性計(jì)算屬性頻率。判斷是否有屬性頻率相同的屬性，有則轉(zhuǎn)（4），否轉(zhuǎn)（5）；

（4） 對(duì)有相同屬性頻率的屬性用定理2判斷是否為強(qiáng)等價(jià)集，若是則在可辨識(shí)矩陣M中保留強(qiáng)等價(jià)集中任一屬性去除其他屬性。否則轉(zhuǎn)（5）；

（5） 找出屬性頻率最高的屬性記作a1則Red=Red∪{a1}，去掉可辨識(shí)矩陣中含有屬性a1的屬性組合；

（6） 判斷可辨識(shí)矩陣是否為h，是結(jié)束，否則轉(zhuǎn)（3）。

顯然，該算法給處理具有相同屬性頻率的決策表屬性約簡(jiǎn)提供了較好的方法。大量數(shù)據(jù)表明遇到出現(xiàn)相同屬性頻率的情況非常多，所以該算法的實(shí)用性很廣泛。與文獻(xiàn)［3］的算法相比，改進(jìn)的基于屬性頻率的算法的實(shí)現(xiàn)對(duì)條件屬性的更優(yōu)的約簡(jiǎn)，其計(jì)算的主要時(shí)間花費(fèi)在計(jì)算g(ai)上，為O(|C||U|2)，而原算法的時(shí)間復(fù)雜度亦為O(|C||U|2)，可見新的算法在保持計(jì)算的時(shí)間復(fù)雜度不變的前提下，得到更精確的約簡(jiǎn)結(jié)果。

3 實(shí)例分析

表1［4］是一個(gè)信息系統(tǒng)。應(yīng)用這里改進(jìn)算法對(duì)該信息系統(tǒng)進(jìn)行屬性約簡(jiǎn)。

表1 信息系統(tǒng)

objectSizePanelBackMidClassification

1ShortDarkBluePale0

2TallDarkBrownMatt1

3TallRedBluePale0

4ShortBlondBlueMatt1

5TallBlondBluePale1

6TallDarkBluePale0

7TallBlondBrownMatt1

8ShortDarkBrownMatt1

式(2)為可辨識(shí)矩陣:

0

SBM0

hPBM0

PMhSPM0

SPhPh0

hBMhSPMP0

SPBMhPBMhhPBM0

BMhSPBMhhSBMh0〗(1)

式(3)為去掉核屬性后的可辨識(shí)矩陣:

0

SBM0

hh0

hhh0

hhhh0

hBMhhh0

hhhhhh0

BMhhhhSBMh0〗(2)

表1變換成對(duì)應(yīng)的可辨識(shí)矩陣，得式(1)所對(duì)應(yīng)的可辨識(shí)矩陣。式(2)是在式(1)的基礎(chǔ)上由算法第（2）步得到P為核屬性直接加入到約簡(jiǎn)Red中后，去掉含有P的屬性項(xiàng)得到化簡(jiǎn)后的新可辨識(shí)矩陣；在新的可辨識(shí)矩陣中可以得出屬性B,M頻率一樣，g(B)=g(M)=12.33，{B,M}有可能是強(qiáng)等價(jià)集，此時(shí)再利用定理1求出原可辨識(shí)矩陣的強(qiáng)等價(jià)集為{B,M}，根據(jù)強(qiáng)等價(jià)集的定理2，在可辨識(shí)矩陣中可以去掉M保留B，最后得到的約簡(jiǎn)集合{P,B}。再去掉含有B的屬性項(xiàng)，此時(shí)可辨識(shí)矩陣為h，則算法結(jié)束。而按照文獻(xiàn)［3］中的算法得到的約簡(jiǎn)集合為{P,B,M}，又由定理2中關(guān)于強(qiáng)等價(jià)集的性質(zhì)中可知，包含在強(qiáng)等價(jià)集中的屬性是可以約簡(jiǎn)的，所以{P,B,M}不是最后的約簡(jiǎn)結(jié)果。實(shí)例證明新算法可以實(shí)現(xiàn)更加有效精確的數(shù)據(jù)屬性約簡(jiǎn)。

4 結(jié) 語(yǔ)

由于現(xiàn)實(shí)信息系統(tǒng)的數(shù)據(jù)復(fù)雜度很高，出現(xiàn)相同頻率屬性的幾率很大，所以在基于粗糙集屬性頻率的約簡(jiǎn)算法的基礎(chǔ)上，引入強(qiáng)等價(jià)集概念，較好地解決了出現(xiàn)相同屬性頻率時(shí)屬性約簡(jiǎn)的問(wèn)題，具有一定的實(shí)際意義和應(yīng)用價(jià)值。與原算法相比，在保持計(jì)算速度保持不變的前提下實(shí)現(xiàn)了對(duì)信息系統(tǒng)更為精確的屬性約簡(jiǎn)。

參 考 文 獻(xiàn)

［1］Pawlak Z.Rough Set:Theoretical Aspects of Reasoning about Data.Dordrecht:Kluwer Academic Publisher,1991.

［2］Roman W Swiniarski,Andrzej Skowrin.Rough Set Methods in Feature Selection and Recognition.Pattern Recognition Letter,2003,24(6):833－849.

［3］任小康,吳尚智,馬如云.基于可辨識(shí)矩陣的屬性頻率約簡(jiǎn)算法［J］.蘭州大學(xué)學(xué)報(bào),2007,43(1):138－141.

［4］蘆曉紅,陳世權(quán),吳今培.基于可辨識(shí)矩陣的啟發(fā)式屬性約簡(jiǎn)方法及其應(yīng)用［J］.計(jì)算機(jī)工程,2003,29(1):56.

［5］薛安榮,韓紅霞,潘雨青.基于可辨識(shí)矩陣的快速粗糙集屬性約簡(jiǎn)算法［J］.計(jì)算機(jī)工程與設(shè)計(jì),2007,28(20):49－87.

［6］陶志,許寶棟,汪定偉.基于區(qū)分矩陣與強(qiáng)等價(jià)集的啟發(fā)式知識(shí)約簡(jiǎn)算法［J］.系統(tǒng)工程理論方法應(yīng)用,2004,13(6):513－514.

［7］胡可云.基于概念格和粗糙集的數(shù)據(jù)挖掘方法研究［D］.北京:清華大學(xué),2001.

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

［9］王國(guó)胤.Rough集理論與知識(shí)獲取［M］.西安:西安交通大學(xué)出版社,2001.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。