江效堯， 程玉勝， 胡林生

（1.南京審計(jì)學(xué)院 信息科學(xué)學(xué)院，江蘇 南京 210029；2.安慶師范學(xué)院 計(jì)算機(jī)與信息學(xué)院，安徽 安慶 246011）

基于極大相容塊的粗糙性度量及其屬性約簡

江效堯1， 程玉勝2， 胡林生1

（1.南京審計(jì)學(xué)院 信息科學(xué)學(xué)院，江蘇 南京 210029；2.安慶師范學(xué)院 計(jì)算機(jī)與信息學(xué)院，安徽 安慶 246011）

由于相似關(guān)系或相容關(guān)系不具有傳遞性或?qū)ΨQ性，從而相容類或相似類之間存在誤判，因此研究不完備信息系統(tǒng)中合適粒度下的粗糙性度量和屬性約簡算法很有必要。在不改變相關(guān)模型的基礎(chǔ)上，文章通過極大相容塊的思想，研究了非等價(jià)關(guān)系的基本知識粒度構(gòu)造，進(jìn)一步討論了合適粒度下的粗糙性度量方法，提出了基于極大相容塊的知識粗糙性更精確的定義和極大相容塊的條件信息熵及其屬性重要性定義，并證明了相關(guān)性質(zhì)；給出了合適粒度下屬性約簡的啟發(fā)式算法，結(jié)果表明，極大相容塊的重要性度量避免了通常意義下粒度過粗問題，知識粗糙性更為準(zhǔn)確。

粗糙集理論；極大相容塊；粗糙性度量；屬性約簡；條件信息熵

0 引 言

在粗糙集理論的研究中，不確定性問題及其度量一直是粗糙集理論研究的一個(gè)重要內(nèi)容［1］。在信息論中，熵是不確定性度量的一種重要方法［2］。文獻(xiàn)［3］從公理化角度提出粒度的定義，將Shannon熵［2］與不確定性度量［3－6］聯(lián)系起來；文獻(xiàn)［7］則進(jìn)一步討論了知識粗糙性與信息熵之間的關(guān)系，證明了知識粗糙熵的單調(diào)性，從信息論的角度刻畫了粗糙集理論的本質(zhì)。然而這些研究是在等價(jià)關(guān)系下進(jìn)行討論的。

對于不完備信息系統(tǒng)，文獻(xiàn)［8－9］討論了相容關(guān)系下的知識和粗集粗糙性度量問題，文獻(xiàn)［10］則進(jìn)一步給出了一般二元關(guān)系下的知識粗糙熵和粗集粗糙熵的定義，為不完備信息系統(tǒng)知識的獲取提供了一定的理論基礎(chǔ)；但不難發(fā)現(xiàn)，非等價(jià)關(guān)系（如相容關(guān)系［8－9］、一般二元關(guān)系［10］）求出的知識塊結(jié)構(gòu)不再形成對論域的劃分，而變成覆蓋；另外這些知識塊對象之間甚至同一知識塊內(nèi)的對象之間也存在一定程度的誤判。解決該問題的一種方法是改變非等價(jià)關(guān)系下的一些限制條件，如限制容差關(guān)系［11］、基于聯(lián)系度的容差關(guān)系［12］，在一定程度上克服了相容關(guān)系或相似關(guān)系存在的缺陷，這種方法稱為模型改變法；另一種方法是不改變模型，文獻(xiàn)［13］將離散數(shù)學(xué)中的極大相容塊思想引入到不完備信息系統(tǒng)中，討論了相容關(guān)系下知識基本粒度的構(gòu)造方法，為在不完備信息系統(tǒng)中度量粗糙性提供了可能。

然而，不確定性度量是以非等價(jià)關(guān)系下獲得的知識塊進(jìn)行討論的［8－10］，顯然有一定的缺陷。本文將最大相容聲（MCB）思想與信息熵聯(lián)系起來，通過MCB構(gòu)造非等價(jià)關(guān)系下的基本知識粒度，從而給出更加合理的知識粗糙熵度量的定義，并證明了該定義是等價(jià)關(guān)系下知識粗糙熵的推廣；定義了MCB條件下信息熵及其屬性重要性度量方法，由此給出了合適粒度下屬性約簡的啟發(fā)式算法。

1 相容類的知識粗糙熵與粗集粗糙度

對于不完備信息系統(tǒng)，文獻(xiàn)［14］定義的相容關(guān)系為：P?C確定了U上的二元關(guān)系TP：TP＝｛（x，y）∈U×U｜?a∈P，f（x，a）＝f（y，a）∨f（x，a）＝＊∨f（y，a）＝＊｝；令SP（x）表示在P下與x相容的所有對象的全體，即SP（x）＝｛y∈U｜（x，y）∈TP｝，SP（x）為x的P相容類。

基于相容類的定義，文獻(xiàn)［14］定義集合X關(guān)于屬性P的上近似（X））和下近似（（X））分別為：

定義2 集合X為論域U上的一個(gè)關(guān)于知識P的粗集，則其粗糙度定義［5］為：

定理1 對于不完備信息系統(tǒng)S＝（U，C∪D，V，f），若存在P?Q?C，則不等式P（X）?

定理1表明，在不完備信息系統(tǒng)中，當(dāng)Q比P劃分細(xì)時(shí)，粗集X關(guān)于Q的粗糙度小于其關(guān)于P的粗糙度。

2 基于MCB知識粗糙性度量

在完備信息系統(tǒng)中，知識的信息熵和粗糙熵是通過等價(jià)關(guān)系對論域的劃分來定義的［15］。當(dāng)?shù)葍r(jià)關(guān)系放寬為相容關(guān)系或相似關(guān)系后，相容類或相似類不再構(gòu)成對論域的劃分而變成覆蓋。盡管信息系統(tǒng)的知識和集合的粗糙性可以通過相容類或相似類來描述，但是，一個(gè)給定相容類中的對象也可能與其他相容類中的對象相似，甚至在同一個(gè)相容類中的對象也并不是不可區(qū)分的［16］。

例如相容類SC（5）＝｛4，5，6｝中｛4，6｝為可區(qū)分的，因此，如果仍然利用相容類或相似類作為信息系統(tǒng)的基本知識粒度來度量知識和粗集的粗糙性就不再恰當(dāng)。文獻(xiàn)［13，16］提出了在不完備信息系統(tǒng)中通過求解基本知識粒度，為準(zhǔn)確度量知識和粗集的不確定性提供了方法。

2.1 MCB 定義

定義3 設(shè)S＝ （U，C∪D，V，f）為不完備信息系統(tǒng)，P?C，X?U為對象集［13］。如果對任意x，y∈X，均有（x，y）∈TP，則稱X關(guān)于P是相容的。如果不存在對象子集Y，使得X?Y，且Y關(guān)于P也是相容的，則稱X為P的一個(gè)MCB。

如果X為 MCB，則［16］

（1）式給出了求解MCB的方法。MCB描述了一種極大的對象集合，在給定可利用信息下，該對象集合中的所有元素是不可區(qū)分的，因此它是相容類中極大不可區(qū)分集的形式描述，滿足了作為基本知識粒度的要求，所以可以用來度量知識和粗集的不確定性［17］。

由P?C確定的包含對象xi的所有MCB形成的集合記為（P），由P?C確定的所有MCB形成的集合記為C（P）。

定理2 設(shè)S＝ （U，C∪D，V，f） 不完備信息系統(tǒng)，P?C，則P的任意一個(gè)相容類可以被表示為包含于其中的P的MCB的并，即

例1 信息系統(tǒng)［17］見表1所列。設(shè)Q＝｛Price，Mileage，Size，Max－speed｝，則其Q相容類SQ（1）＝ ｛1｝，SQ（2）＝ ｛2，6｝，SQ（3）＝ ｛3｝，SQ（4）＝｛4，5｝，SQ（5）＝｛4，5，6｝，SQ（6）＝｛2，5，6｝，根 據(jù) 定 義 3 和 （1）式，得C1（Q）＝ ｛1｝，C2（Q）＝｛2，6｝，C3（Q）＝ ｛3｝，C4（Q）＝ ｛4，5｝，C5（Q）＝ ｛｛4，5｝，｛5，6｝｝，C6（Q）＝ ｛｛2，6｝，｛5，6｝｝，故Q的 MCB為C（Q）＝｛B1＝｛1｝，B2＝｛2，6｝，B3＝｛3｝，B4＝｛4，5｝，B5＝｛5，6｝｝，并有SQ（6）＝B2∪B5成立。

相容類中的對象并不都是相容的，而MCB中的所有對象是相容的。例1中相容類SQ（6）中對象2和對象5之間，由于（2，5）?TQ，所以SQ（6）＝｛2，5，6｝關(guān)于Q不是相容的，因此SQ（2）＝｛2，6｝是關(guān)于Q的 MCB。（雖然｛2，6｝?｛2，5，6｝，但｛2，5，6｝關(guān)于Q是不相容的）。相容類SQ（6）或SQ（5）中對象5和對象6之間，由于（5，6）∈TQ，根據(jù)（1）式得｛5，6｝是關(guān)于Q的 MCB。

2.2 基于MCB知識粗糙熵

定義4 對于不完備信息系統(tǒng)S＝（U，C∪D，V，f）和P?C的 MCB為C（P）＝｛B1，B2，…，Bn｝，P的 MCB信息熵定義［17］為：

其中，p（Bi）＝｜Bi｜／｜U｜。

同時(shí)，可以采用模糊信息熵的計(jì)算方法［15，18］，即Er（P）＝p（Bi）×（1－p（Bi）），避免了對數(shù)計(jì)算。

定義5 對于不完備信息系統(tǒng)S＝（U，C∪D，V，f） 和P?C的 MCB為C（P）＝｛B1，B2，…，Bn｝，P的 MCB粗糙熵定義為：

定理3 設(shè)S＝ （U，C∪D，V，f）是一個(gè)完備信息系統(tǒng)，P?C，U／TP＝｛SP（x1），SP（（x2），…，SP（x｜U｜）｝，U／IND（P）＝｛X1，X2，…，Xm｝，則基于MCB定義的知識P的粗糙熵退化為：

證明 在完備信息系統(tǒng)S中，不存在空值，因此相容關(guān)系TP就退化為TP＝｛（x，y）∈U×U｜?a∈P，f（x，a）＝f（y，a）｝，即TP退化為等價(jià)關(guān)系IND（P），因此任意一個(gè)相容類SP（xi）與包含xi的等價(jià)類［xi］P等價(jià)，所以有（P）＝［xi］P，故C（P）＝U／IND（P），得：

其中，［xi］P表示在知識P下包含xi的等價(jià)類。證畢。

定理3表明，完備信息系統(tǒng)中的知識粗糙熵是不完備信息系統(tǒng)中基于MCB定義的知識粗糙熵的特殊情形。

定理4 設(shè)S＝ （U，C∪D，V，f） 為不完備信息系統(tǒng)，如果P?Q?C，則Er′（Q）≤Er′（P）。

證明 設(shè)C（P）＝｛B1，B2，…，Bn｝，C（Q）＝｛Z1，Z2，…，Zm｝。當(dāng)P?Q時(shí)，顯然C（Q）?C（P）成立，故對?Zi，有Zi?Bj，且m≥n，令x＝｜Zi｜，y＝｜Bj｜，所以1≤x≤y。又因?yàn)椋?/p>

令fj（x）＝xlbx，因?yàn)閒j′（x）＝1／ln 2＋lbx＞0，所以fj（x）為增函數(shù)。

定理4說明，基于MCB定義的知識粗糙熵隨分辨能力的增強(qiáng)（通過更細(xì)的覆蓋）而單調(diào)下降。

例2 續(xù)例1，設(shè)P＝｛Price，Mileage，Size｝，顯然P?Q。因?yàn)镻的 MCB為C（P）＝｛｛1，4，5｝，｛2，5，6｝，｛3｝｝，所以Er′（P）＝lb 3＝1.58，而Er′（Q）＝1。

2.3 基于MCB的條件信息熵

定義6 對決策信息系統(tǒng)S＝（U，C∪D，V，f），U為論域，B?C，決策屬性D對論域U的劃分為U／D＝｛D1，D2，…，Dm｝，知識B的 MCB為C（B）＝｛B1，B2，…，Bn｝。定義B相對于D的MCB條件信息熵為：

其中，p（Dj｜Bi）＝｜Dj∩Bi｜／｜Bi｜。

根據(jù)定義4和定義6可以得出MCB粗糙熵和條件信息熵之間的關(guān)系。

證明

性質(zhì)1將MCB條件熵的計(jì)算轉(zhuǎn)換為求2個(gè)信息熵的和。

2.4 基于MCB的屬性重要性定義

定義7 對決策信息系統(tǒng)S＝（U，C∪D，V，f），B?C，b∈B在B中相對于決策屬性的屬性重要性定義為：

由于B的劃分比B＼｛b｝劃分細(xì)，因此SigB＼｛b｝（D｜｛b｝）≥0。該定義表明b在B中相對于決策屬性的重要性可以通過MCB條件熵的變化來度量，因此b在B中是必要的，等價(jià)于SigB＼｛b｝（D｜｛b｝）＞0。

定義8 對決策信息系統(tǒng)S＝（U，C，D），B?C，c∈C＼B，屬性c對于B的相對于決策屬性的相對重要性定義為：

3 基于MCB屬性約簡算法及其應(yīng)用

3.1 基于MCB屬性約簡算法

算法 MCBARUM （MCB for Attribute Reduction with Uncertainty Measure）的描述：

輸入：不完備信息系統(tǒng)S＝（U，C∪D，V，f）。

輸出：不完備信息系統(tǒng)S＝（U，C∪D，V，f）的一個(gè)屬性約簡Red。

（1）計(jì)算決策信息系統(tǒng) MCB條件信息熵EMCB（D｜C）。

（2）對每一個(gè)c∈C，計(jì)算c在C中相對于決策屬性的重要性SigC＼｛c｝（D｜｛c｝），求得 Red＝｛c｜SigC＼｛c｝（D｜｛c｝）＞0｝。

（3）重復(fù)做：① 計(jì)算EMCB（D｜Red），如果EMCB（D｜C）＝EMCB（D｜Red），輸出約簡集Red，算法停止；否則繼續(xù)②；② 對每個(gè)c∈C＼Red，計(jì)算SigRed（D｜｛c｝），選取使得SigRed（D｜｛a｝）最大的屬性c0，作Red＝Red∪｛c0｝，轉(zhuǎn)①。

3.2 應(yīng)用舉例

以表1為例，C＝｛Price，Mileage，Size，Maxspeed｝，則C（C）＝ ｛B1＝ ｛1｝，B2＝ ｛2，6｝，B3＝｛3｝，B4＝｛4，5｝，B5＝｛5，6｝｝；決策屬性D＝｛d｝的劃分U／D＝｛D1＝｛3｝，D2＝｛1，2，4，6｝，D3＝｛5｝｝。

為了計(jì)算方便，下文 Price、Mileage、Size、Max－speed分別用P、M、S、X代替；同時(shí)根據(jù)性質(zhì)1，采用模糊信息熵方法計(jì)算MCB條件信息熵，MCBARUM算法的執(zhí)行過程為：

（1）計(jì)算表1信息系統(tǒng)條件屬性C的MCB條件信息熵EMCB（D｜C）＝1.444。

（2）計(jì)算每個(gè)屬性重要性，SigC＼｛P｝（D｜｛P｝）＝－0.166 7，SigC＼｛M｝（D｜｛M｝）＝0；而 SigC＼｛S｝（D｜｛S｝）＝0.277 8，SigC＼｛X｝（D｜｛X｝）＝0.055 6，所以Red＝｛S，X｝。

（3）計(jì)算EMCB（D｜Red）＝1.389，但是EMCB（D｜Red）≠EMCB（D｜C），于是對C＼Red＝｛P，M｝中的每個(gè)屬性計(jì)算相對重要性，SigRed（｛P｝）＝0.111，SigRed（｛M｝）＝－0.055 6，于是Red＝｛P，S，X｝，計(jì)算EMCB（Red）＝1.444＝EMCB（C），故表1屬性約簡為｛P，S，X｝，比通常意義下獲得的約簡｛S，X｝［14，16］粒度要細(xì)，充分體現(xiàn)了MCB重要性度量，避免了通常意義下粒度過粗問題，知識粗糙性更為準(zhǔn)確。

4 結(jié)束語

在不完備信息系統(tǒng)中，當(dāng)相似關(guān)系或相容關(guān)系代替不可區(qū)分關(guān)系后，其相似類或相容類不再形成對原論域的劃分而覆蓋；另一方面，由于相似關(guān)系或相容關(guān)系不再具有傳遞性或?qū)ΨQ性，在相容類或相似類之間存在誤判問題，因此研究不完備信息系統(tǒng)下的粗糙性度量和相應(yīng)的屬性約簡算法很有必要。在不改變相關(guān)模型的基礎(chǔ)上，本文基于MCB思想求出不完備信息系統(tǒng)中的基本知識粒度，在現(xiàn)有條件下，克服了對象間的誤判問題，并由此定義知識粗糙熵，獲得等價(jià)關(guān)系下知識粗糙熵是該定義特殊情形的結(jié)果。提出的MCB條件信息熵和屬性重要性定義能有效地構(gòu)造屬性約簡的啟發(fā)式算法，其結(jié)果比通常意義下獲得的約簡粒度會更細(xì)，從而為研究不完備信息系統(tǒng)知識的獲取提供了一定的理論基礎(chǔ)。

［1］王國胤，何 曉.一種不確定條件下的自主式知識學(xué)習(xí)模型［J］.軟件學(xué)報(bào)，2003，14（6）：1096－1102.

［2］Shannon C E.The mathematical theory of communication［J］.The Bell System Technical Journal，1948，27（3／4）：373－423.

［3］Wierman M J.Measuring uncertainty in rough set theory［J］.International Journal of General Systems，1999，28（4）：283－297.

［4］Beaubouef T，Petry F E，Arora G.Information－Theoretic measures of uncertainty for rough relational databases［J］.Information Sciences，1998，109（1／2／3／4）：185－195.

［5］張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法［M］.北京：科學(xué)出版社，2001：134－156.

［6］郭 慶，戴習(xí)民，吳 磊.一種區(qū)間模糊粗糙集的定義及其性質(zhì)［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，34（6）：954－956.

［7］苗奪謙，王 玨.粗糙集理論中概念與運(yùn)算的信息表示［J］.軟件學(xué)報(bào)，1999，10（2）：113－116.

［8］Liang Jiye，Xu Zongben.Uncertainty measures of roughness of knowledge and rough sets in incomplete information systems［C］／／Proceedings of the 3rd world congress on intelligent control and automation，2000：2526－2529.

［9］Liang Jiye，Qu Kaishe.Information measures of roughness of knowledge and rough set for incomplete systems［J］.Journal of Systems Science and Systems Engineering，2001，10（4）：418－424.

［10］黃 兵，周獻(xiàn)中，史迎春.基于一般二元關(guān)系的知識粗糙熵與粗集粗糙熵［J］.系統(tǒng)工程理論與實(shí)踐，2004（1）：93－96.

［11］王國胤.Rough集理論在不完備信息系統(tǒng)中的擴(kuò)充［J］.計(jì)算機(jī)研究與發(fā)展，2002，39（10）：1238－1243.

［12］黃 兵，周獻(xiàn)中.不完備信息系統(tǒng)中基于聯(lián)系度的粗集模型拓展［J］.系統(tǒng)工程理論與實(shí)踐，2004（1）：88－93.

［13］Leung Yee，Li Deyu.Maximal consisitent block technique for rule acquisition in incomplete information systems［J］.Information Sciences，2003，153（1）：85－106.

［14］Krysckiewicz M.Rough set approach to incomplete information system ［J］.Information Sciences，1998，112（1／2／3／4）：39－49.

［15］程玉勝，張佑生，胡學(xué)鋼.基于邊界域的知識粗糙熵與粗集粗糙熵［J］.系統(tǒng)仿真學(xué)報(bào)，2007，19（9）：2008－2011.

［16］李德玉.粗糙集的代數(shù)結(jié)構(gòu)與信息系統(tǒng)知識約簡［D］.西安：西安交通大學(xué)，2002.

［17］Cheng Yusheng，Zhang Yousheng，Hu Xuegang，et al.Uncertainty measure of knowledge and rough set based on maximal consistent block technique［C］／／Proceedings of the sixth International Conference on Machine Learning and Cybernetics，2007：3069－3074.

［18］Liang J Y，Dang C Y，Chin K S，et al.A new method for measuring uncertainty and fuzziness in rough set theory［J］.Internactional Journal of General Systems，2002，31（4）：331－342.

Roughness measure and attribute reduction based on maximal consistent block

JIANG Xiao－yao1， CHENG Yu－sheng2， HU Lin－sheng1
（1.School of Information Science，Nanjing Audit University，Nanjing 210029，China；2.School of Computer and Information，Anqing Normal University，Anqing 246011，China）

Due to the lack of transference and symmetry，there exists misjudgment in tolerance or similarity classes.Therefore，it is necessary to study roughness measure and attribute reduction algorithm with suitable granularity in incomplete information system.Without changing the relevant model，this paper studies the basic knowledge granulation of non－equivalence relation such as the similarity or tolerance classes，and the roughness measure method of knowledge with suitable granularity according to maximal consistent black（MCB）.Based on it，the more accurate definition about the roughness of knowledge based on MCB，the conditional information entropy of MCB and its attribute significance are discussed.The relevant properties are proved and a heuristic algorithm of attribute reduction with suitable granularity is presented.The results show that the roughness measure based on MCB is more accurate，which can avoid the too rough granularity in the usual sense.

rough set theory；maximal consistent black（MCB）；roughness measure；attribute reduction；conditional information entropy

TP18

A

1003－5060（2012）04－0476－05

10.3969／j.issn.1003－5060.2012.04.010

2011－08－31

安徽省自然科學(xué)基金資助項(xiàng)目（070412061）；安徽省教育廳自然科學(xué)研究資助項(xiàng)目（2001kj161）

江效堯（1955－），女，安徽安慶人，南京審計(jì)學(xué)院副教授，碩士生導(dǎo)師；

程玉勝（1969－），男，安徽桐城人，博士，安慶師范學(xué)院教授，碩士生導(dǎo)師.

（責(zé)任編輯 閆杏麗）