基于粗集可辨識矩陣的屬性頻率約簡算法

逄玉俊　李　爽

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

關(guān)鍵詞：粗糙集;可辨識矩陣;強等價集;屬性頻率

中圖分類號：TP391 文獻標識碼：B 文章編號：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ù)學家Z.Pawlak在1982年提出的一種智能決策分析數(shù)學工具。它是研究不完整，不確定知識和數(shù)據(jù)的表達、學習、歸納的理論方法。粗糙集目前主要被廣泛地應(yīng)用與數(shù)據(jù)挖掘、人工智能、模式識別、網(wǎng)頁分類、故障診斷和專家系統(tǒng)等領(lǐng)域［1］。

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

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

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

1.1 決策表

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

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

1.2 約簡和核

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

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

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

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

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

1.3 可辨識矩陣

令決策表系統(tǒng)S=＜U,R,V,f＞,R=C∪D是屬性集合；子集P={a i|i=1,2,…,m}和D=j5i0abt0b分別稱為條件屬性和決策屬性集；U={x1,x2,…,xn}是論域，ai(xj)是樣本xj在屬性ai上的取值。CD(i,j)表示可辨識矩陣中第i行和第j列的元素，則可辨識矩陣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 強等價集

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

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

定理3：如果C是一個約簡，B是強等價集，且{a,b}∈B，則{a,b}不包含于C。

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

證明：假定C是一個約簡，且有{a,b}罜因為{a,b}∈B且B是強等價集，所以有Dis({a})=Dis()，于是有Dis(C－{a})=Dis(a)即IND(C－{a})=IND(C)，這與C是一個約簡相矛盾，因此應(yīng)有{a,b}不包含于C?？梢姡魏我粋€約簡最多只能包含強等價集中的一個屬性，簡而言之，強等價集中的屬性是可以約簡的。

2 基于可辨識矩陣的屬性頻率約簡算法

2.1 算法思想

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

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

（2） 在可辨識矩陣中屬性項越短，屬性的重要性越大。

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

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

式中：countai體現(xiàn)出屬性在可辨識矩陣中出現(xiàn)的次數(shù)越多，這個屬性的重要性越大；counterai為屬性ai在可辨識矩陣中出現(xiàn)的總次數(shù)；j為含有屬性ai的屬性項中屬性的個數(shù)，n為含有屬性ai所有項中，屬性個數(shù)最多的項的屬性個數(shù)?；诖斯剑梢杂嬎愠鰧傩灶l率。

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

2.2 算法描述

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

輸出：決策表的約簡集Red。

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

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

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

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

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

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

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

3 實例分析

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

表1 信息系統(tǒng)

objectSizePanelBackMidClassification

1ShortDarkBluePale0

2TallDarkBrownMatt1

3TallRedBluePale0

4ShortBlondBlueMatt1

5TallBlondBluePale1

6TallDarkBluePale0

7TallBlondBrownMatt1

8ShortDarkBrownMatt1

式(2)為可辨識矩陣:

0

SBM0

hPBM0

PMhSPM0

SPhPh0

hBMhSPMP0

SPBMhPBMhhPBM0

BMhSPBMhhSBMh0〗(1)

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

0

SBM0

hh0

hhh0

hhhh0

hBMhhh0

hhhhhh0

BMhhhhSBMh0〗(2)

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

4 結(jié) 語

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

參 考 文 獻

［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］任小康,吳尚智,馬如云.基于可辨識矩陣的屬性頻率約簡算法［J］.蘭州大學學報,2007,43(1):138－141.

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

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

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

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

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

［9］王國胤.Rough集理論與知識獲取［M］.西安:西安交通大學出版社,2001.

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