基于粗糙集不確定度的特定類屬性約簡

吳婉琳， 張賢勇*， 莫智文

（1.四川師范大學 數(shù)學科學學院，四川 成都610066； 2.四川師范大學 智能信息與量子信息研究所，四川 成都610066）

粗糙集理論是一種不確定性分析理論，能夠有效處理不精確、不完整、不一致數(shù)據(jù)，最終在決策表中提取決策規(guī)則或有用信息［1］.在粗糙集理論中，屬性約簡是核心內容與研究熱點，其主要在保持相同分類能力的前提下進行冗余屬性刪除，從而達到數(shù)據(jù)表的優(yōu)化處理.

決策表具有3層粒度結構［2］，在約簡方面涉及到系統(tǒng)決策分類與局部決策類2種主體.傳統(tǒng)的屬性約簡是決策分類約簡，主要考慮所有決策類的整體優(yōu)化.針對實際中存在的局部優(yōu)化需求，特定類約簡應運而生，并改進了決策分類約簡的盲點.文獻［3］基于正域首先建立特定類約簡，文獻［4-5］分別從信息度量與三支決策角度推進特定類約簡，文獻［6-8］分別從鄰域粗糙集、三支概率、決策分布的角度深化了特定類約簡.粗糙集的不確定性主要存在于邊界域，因而基于邊界域及其度量的屬性約簡具有基本的決策表不確定性處理功能.例如，文獻［9］得到信息熵約簡的邊界域條件信息熵表示，文獻［10］提出保持邊界域劃分的知識約簡算法，文獻［11］給出基于容差關系矩陣的決策表邊界域的計算方法，文獻［12］提出一種基于邊界區(qū)域的特征選擇算法，文獻［13］提出基于粗糙邊界域的約簡.歸納可見，基于邊界域的屬性約簡主要停留在決策分類約簡，而相關的特定類約簡罕見相關研究報道.

本文針對特定類屬性約簡，擬采用粗糙集邊界的角度進行初步探討.為此，主要針對已提出的“決策分類不確定度約簡”［13］，對應提出“特定類不確定度約簡”，并揭示兩者的層次關系與約簡關聯(lián).具體地，提取特定類的不確定度度量，依托?；瘑握{性來定義與研究特定類約簡及其啟發(fā)算法，并澄清“特定類不確定度約簡”與“特定類正域約簡”“決策分類不確定度約簡”的關系，最后用決策表實例有效驗證相關算法與約簡關聯(lián).新建的“特定類不確定度約簡”的研究框架如圖1.

圖1 特定類不確定度約簡的研究框架Fig.1 The research framework of class-specific attribute reducts based on uncertainty degrees

1 預備知識

首先復習粗糙集約簡基本概念，主要涉及決策表的“特定類正域約簡”［3］與“決策分類不確定度約簡”［13］2種基本模式.

粗糙集屬性約簡的基本形式背景是決策表

其中，U是非空有限論域，AT是屬性集合（其包括不交的條件屬性集C與決策屬性集D），Va是屬性a∈AT的值域，Ia：U→Va是相應信息函數(shù).關于粒化，條件屬性子集A?C與決策屬性集D分別誘導出知識剖分

由此決策表具有3層粒度結構［2］，高層（πA，πD）與中層（πA，Dj）分別對應決策分類約簡與特定類約簡.下面，?與‖分別表示補集與基數(shù).

定義1［3］關于條件屬性子集A?C，決策類Dj的正域、負域、邊界域為：

定義1提供了粗糙集模型的基本區(qū)域與概念不確定性度量.由此，定義2采用決策類正域自然定義了特定類約簡.類似地，可以采用決策分類正域定義決策分類約簡.下面，基于不確定度來聚焦決策分類約簡.

定義3［13］關于條件屬性子集A?C，決策分類πD的不確定度為

定義4［13］條件屬性子集A?C為“決策分類不確定度約簡”，若：

定義3提供了決策分類的不確定度，其來源于決策類粗糙度關于絕對基數(shù)比例的加權集成；該度量依托于邊界結構從而成為一種基本不確定性度量，關聯(lián)于知識對決策分類的解釋能力［13］.不確定度能夠刻畫決策表的協(xié)調性.蘊含相容規(guī)則的決策表稱為協(xié)調決策表，此時

此外，該度量具有粒化單調性［13］，從而定義4自然定義了“決策分類不確定度約簡”.文獻［13］還澄清了“決策分類不確定度約簡”與“決策分類正域約簡”（即代數(shù)約簡）的派生關系，并依據(jù)屬性重要度來開發(fā)了前向貪心約簡算法.

2 特定類不確定度屬性約簡

在文獻［13］“決策分類不確定度約簡”基礎上，建立“特定類不確定度約簡”及其啟發(fā)式約簡算法，并提供相關實例說明.

2.1 約簡構建為了定義“特定類不確定度約簡”，需要首先確立特定類不確定度及其粒化單調性等性質.下面將決策分類不確定度進行層次分解，定義特定類不確定度.

定義5關于條件屬性子集A?C，決策類Dj的不確度為

對比（3）和（4）式可見，決策類不確定度來源于決策分類不確定度的分解，而后者是關于所有決策類的層次集成（命題1）.從而，決策類不確定度具有關聯(lián)于決策分類不確定度的語義與性質，但主要落實于特定決策類.

具體地，決策類不確定度是決策類粗糙度與決策類基數(shù)比例的乘積，主要關聯(lián)于決策類邊界從而表征不確定性，能夠反向刻畫知識對于決策類的解釋能力，不確定度越小則解釋能力越高.

命題2提供了決策類不確定度的基本性質，其相似于決策分類不確定度性質，但為后者奠定了層次基礎與集成機制.其中，第1）條表明度量值域，相關的最值及其條件是顯然的；第2）條依托條件屬性集，揭示了決策類不確定度對于決策類協(xié)調性與不協(xié)調性的刻畫，后者提出于文獻［4］并用于分解決策表的協(xié)調性或不協(xié)調性；第3）條來源于粗糙度的粒化單調性，表明了決策類不確定度的粒化單調性.

基于決策類不確定度的度量語義與?；瘑握{性，下面提出相關的特定類約簡及其算法，所建約簡與存在的決策分類約簡具有相似性.

定義6條件屬性子集A?C為特定類Dj不確定度約簡，若：

定義7設A?C且a∈C－A，屬性a相對于A的重要度為

定義6提出了“特定類不確定度約簡”，其中的決策類不確定度具有?；瘑握{性，可以用于啟發(fā)式搜索.為此，定義7提出對應的屬性重要度.

SIG（a，A，Dj）描述屬性a加入到屬性子集A之后導致的決策類Dj不確定度減少量，該度量能夠體現(xiàn)a相對于A的重要性程度，其越大則屬性重要性越大.由此，下面利用該屬性重要度建立一個啟發(fā)式約簡算法，主要通過最大重要度尋找最優(yōu)屬性，以便最終快速獲取一個“特定類不確定度約簡”.

算法1 特定類不確定度約簡算法.

輸入：決策表T、關注的特定類標簽j；

輸出：特定類Dj不確定度約簡A.

步驟1 設置A＝?；

步驟2 計算UNC（Dj｜πC）；

步驟3 ?a∈（C－A），計算屬性重要度SIG（a，A，Dj），并靠前選擇屬性重要度最大的條件屬性a并入A的尾部，即進行更新A←A∪｛a｝.如果此時有

算法1是一個前向貪心約簡算法，其主要從空集開始增加屬性，步驟3通過順序選取最優(yōu)屬性讓A快速滿足定義6的約簡充分性條件（s），而步驟4是后項刪除過程，以確保A滿足定義6的約簡必要性條件（n），從而A是一個“特定類不確定度約簡”，最終被有效輸出.

2.2 實例說明提供一個決策表實例，用于分析特定類不確定度及“特定類不確定度約簡”.

例1設表1所述二分類決策表T，其中

表1 實例決策1Tab.1 Example decision 1

此表是不協(xié)調的，其中的2個決策類也是不協(xié)調的.

而C的非0不確定度剛好對應決策類不協(xié)調性.此外，?；瘑握{性可通過屬性層次鏈進行檢驗，例如：

根據(jù)定義6與表2，可以得到所有“特定類不確定度”約簡，即D1、D2類分別具有約簡｛c1，c2｝、｛c1，c2｝.從算法1的角度來看，針對D1類，靠前選擇不確定度最大的條件屬性c1，其沒有達到C的不確定度，此時｛c1｝的擴充有｛c1，c2｝和｛c1，c3｝2個選擇，選擇屬性重要度最大的屬性進行更新，得到A＝｛c1，c2｝，此時D1類不確定度達到C的不確定度0.34，即

表2 基于冪集空間的不確定度Tab.2 Uncertainty degrees based on power set space

進入步驟4.向前遍歷刪除A中的每個屬性a，有

進入步驟5，返回A，即D1類具有約簡A＝｛c1，c2｝.類似可以得到D2類不確定度約簡｛c1，c2｝，其與定義6計算結果一致.

3 特定類不確定度約簡與2種存在約簡的關系

如圖1所示，下面探究“特定類不確定度約簡”與“特定類正域約簡”“決策分類不確定度約簡”的關系，并提供相關實例分析.

3.1 約簡關系首先揭示“特定類不確定度約簡”與“特定類正域約簡”的橫向關聯(lián).

定理1若A是C“特定類Dj不確定度約簡”，則

證明若A是C“特定類Dj不確定度約簡”，根據(jù)定義6及（2）式，有

定理2若A是C的“特定類不確定度約簡”，則A必定包含C的一個“特定類正域約簡”.

證明若給定決策類是協(xié)調的，由定義6和命題2可知

A包含C的一個“特定類正域約簡”.證畢.

推論1若給定的決策類是協(xié)調的，則A是C的“特定類不確定度約簡”等價于A是C的“特定類正域約簡”.

證明基于單調性，約簡必要條件中的元素表述式?a∈A可以等價地修改為子集表達式?A′?A，由此下面證明采用后者來敘述.

若A是C的“特定類不確定度約簡”，由定理1可知

因此，A是C的“特定類正域約簡”.

另一方面，若A是C的“特定類正域約簡”，則

因此，A是C的“特定類不確定度約簡”.證畢.

推論2若給定的決策類是不協(xié)調的，則A是C的“特定類正域約簡”不一定等價于A是C的“特定類不確定度約簡”.

證明由后面例2的D1決策類情況可證，證畢.

“特定類正域約簡”保持正域，可能會造成邊界域的擴大.基于定理1，引入的“特定類不確定度約簡”能夠有效保持決策類的上近似和下近似，故具有差異性與價值性.進一步，定理2提供了2種約簡的關聯(lián)，其中“特定類不確定度約簡”更強一點.最后相關的推論1、2表明，在協(xié)調類時2種約簡是等價的，不協(xié)調類才可能引起“特定類不確定度約簡”強于且不同于“特定類正域約簡”.

下面揭示“特定類不確定度約簡”與“決策分類不確定度約簡”的縱向關聯(lián).為此，2種約簡集分別設為REDUNC（Dj）、REDUNC（πD）.利用文獻［3］的思路與結果，可以得到如下基本結論.針對這2種約簡，引理1表達約簡條件的相關性，定理3表現(xiàn)約簡的轉換條件，定理4表明決策分類約簡到特定類約簡的派生性，定理5提供相反的特定類約簡到?jīng)Q策分類約簡的派生性.

引理1約簡條件具有如下等價表示：

3.2 實例分析下面提供一個實例來計算相關約簡，從而驗證“特定類不確定度約簡”與“特定類正域約簡”、“決策分類不確定度約簡”的關系.

例2設表3所述三分類決策表T，其中U＝｛x1，x2，…x12｝，C＝｛c1，c2，c3｝，D1＝｛x1，x2，x3，x4｝，D2＝｛x5，x6，x7，x8｝，D3＝｛x9，x10，x11，x12｝.

表3 實例決策2Tab.3 Example decision 2

此表是不協(xié)調決策表，其中的3個決策類都是不協(xié)調的.

根據(jù)定義（如定義2、4、6），可得2種正域約簡與不確定度約簡，相關的4種約簡結果如表4.

表4 2種正域約簡與不確定度約簡Tab.4 Two types of positive region reducts and uncertainty degrees reducts

表4結果可以驗證相關約簡關系.針對D1類，有：

這表明“特定類不確定度約簡”導致上下近似相等，這驗證定理1；針對D1類，不確定度約簡｛c1，c2｝和｛c2，c3｝中分別包含正域約簡｛c1｝和｛c2，c3｝，這驗證定理2；｛c1，c2｝是D1類不確定度約簡，但不是正域約簡，｛c1｝是正域約簡，但不是不確定度約簡，這驗證了推論2的不等價性.同理可以驗證其他2類情形，其中D2、D3類正域約簡和不確定度約簡都為｛c1｝.針對2種不確定度約簡的縱向關系，主要驗證相互派生的定理4與5.針對唯一決策分類不確定度約簡A＝｛c1，c2｝，可以派生出分別適用于3個特定類約簡：

4 結束語

針對不確定邊界域相關的特定類屬性約簡，分解建立決策類的不確定度，進而提出“特定類不確定度屬性約簡”及其啟發(fā)式算法，最終得到了“特定類不確定度約簡”與“特定類正域約簡”的橫向聯(lián)系以及與“決策分類不確定度約簡”的縱向聯(lián)系.由此，“特定類不確定度約簡”改進了“特定類正域約簡”，主要是在不協(xié)調決策類的情形下，同時其也為“決策分類不確定度約簡”奠定了集成基礎.基于不確定度的?；瘑握{性，還可以建立約簡核概念，充當算法1的搜索起點從而提高算法搜索效率.