基于粗糙集不確定度的特定類(lèi)屬性約簡(jiǎn)

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

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

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

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

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

圖1 特定類(lèi)不確定度約簡(jiǎn)的研究框架Fig.1 The research framework of class-specific attribute reducts based on uncertainty degrees

1 預(yù)備知識(shí)

首先復(fù)習(xí)粗糙集約簡(jiǎn)基本概念，主要涉及決策表的“特定類(lèi)正域約簡(jiǎn)”［3］與“決策分類(lèi)不確定度約簡(jiǎn)”［13］2種基本模式.

粗糙集屬性約簡(jiǎn)的基本形式背景是決策表

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

由此決策表具有3層粒度結(jié)構(gòu)［2］，高層（πA，πD）與中層（πA，Dj）分別對(duì)應(yīng)決策分類(lèi)約簡(jiǎn)與特定類(lèi)約簡(jiǎn).下面，?與‖分別表示補(bǔ)集與基數(shù).

定義1［3］關(guān)于條件屬性子集A?C，決策類(lèi)Dj的正域、負(fù)域、邊界域?yàn)椋?/p>

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

定義3［13］關(guān)于條件屬性子集A?C，決策分類(lèi)πD的不確定度為

定義4［13］條件屬性子集A?C為“決策分類(lèi)不確定度約簡(jiǎn)”，若：

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

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

2 特定類(lèi)不確定度屬性約簡(jiǎn)

在文獻(xiàn)［13］“決策分類(lèi)不確定度約簡(jiǎn)”基礎(chǔ)上，建立“特定類(lèi)不確定度約簡(jiǎn)”及其啟發(fā)式約簡(jiǎn)算法，并提供相關(guān)實(shí)例說(shuō)明.

2.1 約簡(jiǎn)構(gòu)建為了定義“特定類(lèi)不確定度約簡(jiǎn)”，需要首先確立特定類(lèi)不確定度及其粒化單調(diào)性等性質(zhì).下面將決策分類(lèi)不確定度進(jìn)行層次分解，定義特定類(lèi)不確定度.

定義5關(guān)于條件屬性子集A?C，決策類(lèi)Dj的不確度為

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

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

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

基于決策類(lèi)不確定度的度量語(yǔ)義與粒化單調(diào)性，下面提出相關(guān)的特定類(lèi)約簡(jiǎn)及其算法，所建約簡(jiǎn)與存在的決策分類(lèi)約簡(jiǎn)具有相似性.

定義6條件屬性子集A?C為特定類(lèi)Dj不確定度約簡(jiǎn)，若：

定義7設(shè)A?C且a∈C－A，屬性a相對(duì)于A的重要度為

定義6提出了“特定類(lèi)不確定度約簡(jiǎn)”，其中的決策類(lèi)不確定度具有粒化單調(diào)性，可以用于啟發(fā)式搜索.為此，定義7提出對(duì)應(yīng)的屬性重要度.

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

算法1 特定類(lèi)不確定度約簡(jiǎn)算法.

輸入：決策表T、關(guān)注的特定類(lèi)標(biāo)簽j；

輸出：特定類(lèi)Dj不確定度約簡(jiǎn)A.

步驟1 設(shè)置A＝?；

步驟2 計(jì)算UNC（Dj｜πC）；

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

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

2.2 實(shí)例說(shuō)明提供一個(gè)決策表實(shí)例，用于分析特定類(lèi)不確定度及“特定類(lèi)不確定度約簡(jiǎn)”.

例1設(shè)表1所述二分類(lèi)決策表T，其中

表1 實(shí)例決策1Tab.1 Example decision 1

此表是不協(xié)調(diào)的，其中的2個(gè)決策類(lèi)也是不協(xié)調(diào)的.

而C的非0不確定度剛好對(duì)應(yīng)決策類(lèi)不協(xié)調(diào)性.此外，粒化單調(diào)性可通過(guò)屬性層次鏈進(jìn)行檢驗(yàn)，例如：

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

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

進(jìn)入步驟4.向前遍歷刪除A中的每個(gè)屬性a，有

進(jìn)入步驟5，返回A，即D1類(lèi)具有約簡(jiǎn)A＝｛c1，c2｝.類(lèi)似可以得到D2類(lèi)不確定度約簡(jiǎn)｛c1，c2｝，其與定義6計(jì)算結(jié)果一致.

3 特定類(lèi)不確定度約簡(jiǎn)與2種存在約簡(jiǎn)的關(guān)系

如圖1所示，下面探究“特定類(lèi)不確定度約簡(jiǎn)”與“特定類(lèi)正域約簡(jiǎn)”“決策分類(lèi)不確定度約簡(jiǎn)”的關(guān)系，并提供相關(guān)實(shí)例分析.

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

定理1若A是C“特定類(lèi)Dj不確定度約簡(jiǎn)”，則

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

定理2若A是C的“特定類(lèi)不確定度約簡(jiǎn)”，則A必定包含C的一個(gè)“特定類(lèi)正域約簡(jiǎn)”.

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

A包含C的一個(gè)“特定類(lèi)正域約簡(jiǎn)”.證畢.

推論1若給定的決策類(lèi)是協(xié)調(diào)的，則A是C的“特定類(lèi)不確定度約簡(jiǎn)”等價(jià)于A是C的“特定類(lèi)正域約簡(jiǎn)”.

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

若A是C的“特定類(lèi)不確定度約簡(jiǎn)”，由定理1可知

因此，A是C的“特定類(lèi)正域約簡(jiǎn)”.

另一方面，若A是C的“特定類(lèi)正域約簡(jiǎn)”，則

因此，A是C的“特定類(lèi)不確定度約簡(jiǎn)”.證畢.

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

證明由后面例2的D1決策類(lèi)情況可證，證畢.

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

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

引理1約簡(jiǎn)條件具有如下等價(jià)表示：

3.2 實(shí)例分析下面提供一個(gè)實(shí)例來(lái)計(jì)算相關(guān)約簡(jiǎn)，從而驗(yàn)證“特定類(lèi)不確定度約簡(jiǎn)”與“特定類(lèi)正域約簡(jiǎn)”、“決策分類(lèi)不確定度約簡(jiǎn)”的關(guān)系.

例2設(shè)表3所述三分類(lèi)決策表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 實(shí)例決策2Tab.3 Example decision 2

此表是不協(xié)調(diào)決策表，其中的3個(gè)決策類(lèi)都是不協(xié)調(diào)的.

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

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

表4結(jié)果可以驗(yàn)證相關(guān)約簡(jiǎn)關(guān)系.針對(duì)D1類(lèi)，有：

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

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

針對(duì)不確定邊界域相關(guān)的特定類(lèi)屬性約簡(jiǎn)，分解建立決策類(lèi)的不確定度，進(jìn)而提出“特定類(lèi)不確定度屬性約簡(jiǎn)”及其啟發(fā)式算法，最終得到了“特定類(lèi)不確定度約簡(jiǎn)”與“特定類(lèi)正域約簡(jiǎn)”的橫向聯(lián)系以及與“決策分類(lèi)不確定度約簡(jiǎn)”的縱向聯(lián)系.由此，“特定類(lèi)不確定度約簡(jiǎn)”改進(jìn)了“特定類(lèi)正域約簡(jiǎn)”，主要是在不協(xié)調(diào)決策類(lèi)的情形下，同時(shí)其也為“決策分類(lèi)不確定度約簡(jiǎn)”奠定了集成基礎(chǔ).基于不確定度的粒化單調(diào)性，還可以建立約簡(jiǎn)核概念，充當(dāng)算法1的搜索起點(diǎn)從而提高算法搜索效率.