目不相容決策表求核方法

1、遼寧對(duì)外經(jīng)貿(mào)學(xué)院第六屆學(xué)術(shù)研討會(huì)題 目：不相容決策表求核方法學(xué) 科：工學(xué)單 位：信息技術(shù)系作者姓名：陳鳳娟二一年十一月不相容決策表求核方法陳鳳娟（遼寧對(duì)外經(jīng)貿(mào)學(xué)院信息技術(shù)系,遼寧省 大連市 116052）摘 要 在不相容決策表中計(jì)算核屬性有很多方法，這些方法得到的結(jié)果并不完全一致。使用代數(shù)定義的方法求核可以忽略不相容決策表中不相容信息的影響，得到核屬性，很多改進(jìn)的差別矩陣都能得到與代數(shù)方法一致的核屬性。論文通過(guò)分析不相容決策表，提出相容核與不相容核的概念。然后分析了三個(gè)不相容決策表中的相容核與不相容核，比較了幾種現(xiàn)有的不相容決策表的求核方法，這些方法要么不能完全求出相容核與不相容核，要么不能把

2、得到的相容核與不相容核區(qū)分開(kāi)來(lái)。針對(duì)這一問(wèn)題，對(duì)HU差別矩陣進(jìn)行改進(jìn)，得到兩個(gè)新的差別矩陣，這兩個(gè)矩陣能分別計(jì)算出相容核與不相容核。關(guān)鍵詞 不相容決策表; 相容核; 不相容核; 差別矩陣Methods for Calculating Core Attributes of Inconsistent Decision TableChen Fengjuan(Department of information technology, Liaoning University of International Business and Economics, Dalian 116052)Abstract T

3、here are many calculation methods for core attributes of inconsistent decision table. But the results of these methods are not exactly the same. The algebraic definition method ignores the impact of inconsistent information of inconsistent decision table. Many improved discernibility matrix can get

4、the same results with algebraic definition method. Two concepts core for consistent information and core for inconsistent information have been proposed in this paper. Then analyzes the core of three inconsistent decision tables and compare several existing methods. These existing methods either can

5、not find the core for inconsistent information, or cannot distinguish core for consistent information and core for inconsistent information. Two new matrices have been proposed to solve this problem. One of the two new matrices can calculate core for consistent information, the other one can calcula

6、te core for inconsistent information.Key words Inconsistent Decision Table; Core for Consistent Information; Core for Inconsistent Information; Discernibility Matrix 中圖法分類號(hào)：TP18 1 引言屬性約簡(jiǎn)（知識(shí)約簡(jiǎn)）的計(jì)算是粗糙集理論中的一個(gè)主要研究方向。屬性核是決策表中最重要的特征集合，它包含在所有屬性約簡(jiǎn)之中，可以作為屬性約簡(jiǎn)的基礎(chǔ)，因此很多屬性約簡(jiǎn)算法是從屬性核出發(fā)，在屬性核之上通過(guò)一定的方法選取屬性增加到核中，從而得到約

7、簡(jiǎn)集合1。HU XIAOHUA等學(xué)者在文獻(xiàn)2中給出的利用改進(jìn)差別矩陣求核的方法是一個(gè)很有效的方法，但是有學(xué)者已經(jīng)證明該方法不適用于不相容決策表中求核34。目前，在不相容決策表的求核問(wèn)題上，主要的方法有使用代數(shù)定義、HU差別矩陣、使用信息熵定義5和改進(jìn)的HU差別矩陣346等方法，但這些方法并沒(méi)有完全解決不相容決策表的求核問(wèn)題。本文深入分析不相容決策表的性質(zhì)，把不相容決策表中的核屬性分為相容核與不相容核兩部分，以文3和文5中使用的三個(gè)不相容決策表為例，分析這三個(gè)不相容決策表的相容核與不相容核，然后比較現(xiàn)有的求核方法，發(fā)現(xiàn)這些方法不能夠得到正確的相容核與不相容核，通過(guò)改進(jìn)HU差別矩陣得到兩個(gè)新的差別

8、矩陣，利用這兩個(gè)新的矩陣計(jì)算出不相容決策表的相容核與不相容核。2 基本概念代數(shù)觀中的正域、屬性必要性及核屬性的相關(guān)概念如下1。定義1 設(shè)U為一個(gè)論域，P,Q為定義在U上的兩個(gè)等價(jià)關(guān)系族，Q的P正域記作POSP(Q)，定義為定義2 設(shè)U為一個(gè)論域，P,Q為定義在U上的兩個(gè)等價(jià)關(guān)系族，對(duì)于P中的關(guān)系r，若有 成立，則稱為P中Q不必要的；否則稱r為P中Q必要的。定義3 設(shè)U為一個(gè)論域，P,Q為定義在U上的兩個(gè)等價(jià)關(guān)系族，P中所有Q必要的原始關(guān)系族，稱為P的Q核，記為。核屬性是所有必要屬性的集合。從上面的定義可知，當(dāng)去掉某個(gè)屬性會(huì)導(dǎo)致正域發(fā)生變化時(shí)，則該屬性是核屬性。在不相容決策表中，論域中的元素可以

9、通過(guò)計(jì)算正域的方法，分成不包含沖突信息的相容元素和包含沖突信息的不相容元素兩部分。使用代數(shù)定義求核的方法通過(guò)比較正域的變化得到核屬性，由于不相容元素的劃分塊之間的合并對(duì)正域完全沒(méi)有影響，因此，這種方法能忽略掉不相容決策表中的不相容元素之間的變化規(guī)律，把導(dǎo)致正域發(fā)生變化的屬性稱為核屬性，本文稱這種核屬性為相容核屬性。有兩種情況會(huì)導(dǎo)致一個(gè)不相容決策表的正域發(fā)生變化一個(gè)相容元素的劃分塊和一個(gè)不相容元素的劃分塊發(fā)生合并；一個(gè)相容元素的劃分塊和另一個(gè)相容元素的劃分塊發(fā)生合并。（多于兩個(gè)的劃分塊的合并都可以分解成上面兩種情況）由于這兩種情況會(huì)影響正域，因此定義不相容決策表的相容核如下。定義4 在不相容決策

10、表中，若去掉某一個(gè)條件屬性，會(huì)使包含相容元素的劃分塊與其他劃分塊發(fā)生合并，導(dǎo)致正域發(fā)生變化，則該屬性屬于相容部分的核屬性，簡(jiǎn)稱相容核。從決策表的正域的變化中不能看到不相容信息是否發(fā)生了變化，由于負(fù)域與正域完全對(duì)應(yīng)，所以也不能用負(fù)域來(lái)衡量不相容部分是否變化。由于正域發(fā)生變化的本質(zhì)就是包含相容元素的劃分塊與別的劃分塊發(fā)生了合并，因此可以用不相容信息的劃分塊之間的合并作為衡量不相容部分是否發(fā)生變化的標(biāo)準(zhǔn)。也就是說(shuō)去掉某個(gè)屬性會(huì)導(dǎo)致不相容信息的劃分塊發(fā)生合并，那么這個(gè)屬性對(duì)不相容部分就是必要的屬性，是不相容部分的核屬性，為了區(qū)別于相容部分的核，稱這部分核屬性為不相容核。這種屬性的存在能保證不相容決策表

11、中不相容部分的劃分塊保持不變。根據(jù)這類屬性與決策表的不相容部分信息的變化之間存在的內(nèi)在聯(lián)系，給出如下的不相容決策表的不相容核的定義。定義5 在不相容決策表中，若去掉某一個(gè)條件屬性，會(huì)使包含不相容元素的劃分塊之間發(fā)生合并，則該屬性屬于不相容部分的核屬性，簡(jiǎn)稱不相容核。對(duì)于一個(gè)不相容決策表，完整的核屬性包含兩部分，即相容核與不相容核。相容核部分能考察相容部分的變化，而不相容核能考察不相容部分的變化。一個(gè)核屬性只能是相容核與不相容核中的一種，不可能二者兼為。3 已有不相容決策表求核方法存在的問(wèn)題在文3中，葉東毅教授分析了HU差別矩陣運(yùn)用于不相容決策表中求核時(shí)產(chǎn)生的錯(cuò)誤，并改進(jìn)HU差別矩陣，得到與代數(shù)

12、定義相同的結(jié)果。葉的方法就是通過(guò)改進(jìn)HU矩陣，把不相容決策表中的不相容信息對(duì)HU矩陣的影響去掉，只考慮影響相容部分信息的屬性。類似的改進(jìn)矩陣的方法還有很多，如楊明的改進(jìn)矩陣等46，這些方法雖然得到不同形式的差別矩陣，但是它們的思想是完全一致的，都是把不相容決策表中影響計(jì)算結(jié)果的沖突信息忽略掉。這類改進(jìn)HU矩陣的方法計(jì)算結(jié)果與代數(shù)定義方法完全相容，可以與代數(shù)定義方法歸為一類。在文5中，王國(guó)胤教授使用條件信息熵的方法計(jì)算不相容決策表的核，由于條件信息熵是由不相容信息產(chǎn)生的，因此計(jì)算條件信息熵的方法能考察到不相容部分的變化，但是由于條件信息熵是由比率得到的，因此當(dāng)某些不相容部分的劃分塊發(fā)生了合并，而

13、其比率不發(fā)生變化的情況，就會(huì)被條件信息熵方法忽略掉，導(dǎo)致該方法不能判斷所有的不相容劃分塊發(fā)生合并的情況。下面針對(duì)文3和文5中用到的三個(gè)不相容決策表，分別分析這些決策表中相容部分劃分塊和不相容部分劃分塊的變化，從而說(shuō)明現(xiàn)有的求核方法存在的問(wèn)題。 表1 決策表1U C1 C2 C3 D x1 1 0 1 1 x2 1 0 1 0 x3 0 0 1 1 x4 0 0 1 0 x5 1 1 1 1 決策表1的劃分如下：U/IND(C1,C2,C3)=x1,x2,x3,x4,x5，U/IND(D)=x1,x3,x5,x2,x4,正域POSC(D)=x5。去掉屬性C1,有U/IND(C2,C3)=x1,x

14、2,x3,x4,x5；去掉屬性C2,有U/IND(C1,C3)=x1,x2,x5,x3,x4；去掉屬性C3有U/IND(C1,C2)=x1,x2,x3,x4,x5；從上面的計(jì)算可知：決策表1中相容部分為x5，相容部分的劃分為x5，存在不相容信息的部分為x1,x2,x3,x4，不相容部分的劃分為x1,x2,x3,x4；去掉屬性C1，相容部分的劃分沒(méi)有發(fā)生變化，而不相容部分的劃分發(fā)生了變化，即不相容部分的劃分塊x1,x2和x3,x4合并成了一個(gè)劃分塊x1,x2,x3,x4。去掉屬性C1，導(dǎo)致不相容部分的劃分塊發(fā)生合并，由不相容核的定義，C1屬于不相容核。去掉屬性C2，使相容部分的劃分塊x5和不相容

15、部分的劃分塊x1,x2合并成了一個(gè)劃分塊x1,x2,x5，導(dǎo)致正域POSC(D)發(fā)生變化，根據(jù)相容核的定義，C2屬于相容核。去掉屬性C3，對(duì)相容部分的劃分沒(méi)有影響，對(duì)不相容部分的劃分也沒(méi)有影響，因此C3不屬于任何核。由以上分析可得，決策表1的核屬性集為C1, C2，其中，相容核為C2，不相容核為C1。代數(shù)方法求得的核為相容核C2；改進(jìn)的差別矩陣（如文3、4）中求得的也是相容核C2；信息熵的方法求得的核也是相容核C2；HU矩陣的方法求得的核是C1, C2，是所有的核。 表2 決策表2U C1 C2 C3 D x1 1 0 1 0 x2 0 0 1 1 x3 0 0 1 0 x4 1 1 1 1

16、決策表2的劃分如下：U/IND(C1,C2,C3)=x1,x2,x3,x4,U/IND(D)=x1,x3,x2,x4,正域POSC(D)= x1,x4。去掉屬性C1,有U/IND(C2,C3)=x1,x2,x3,x4；去掉屬性C2,有U/IND(C1,C3)=x1,x4,x2,x3；去掉屬性C3有U/IND(C1,C2)=x1,x2,x3,x4；從上面的計(jì)算可知：決策表2中相容部分為x1,x4，相容部分的劃分為x1,x4，存在不相容信息的部分為x2,x3，不相容部分的劃分為x2,x3；去掉屬性C1，使相容部分的劃分塊x1和不相容部分的劃分塊x2,x3合并成了一個(gè)劃分塊x1,x2,x3，導(dǎo)致正域

17、POSC(D)發(fā)生變化，根據(jù)相容核的定義，C1屬于相容核。去掉屬性C2，使相容部分的劃分塊x1和x4合并成了一個(gè)劃分塊x1,x4，導(dǎo)致正域POSC(D)發(fā)生變化，根據(jù)相容核的定義，C2屬于相容核。去掉屬性C3，相容部分的劃分和不相容部分的劃分都沒(méi)有發(fā)生變化，因此C3不屬于任何核。由以上分析可得，決策表2的核屬性集為C1, C2，其中，相容核為C1, C2，不相容核為空。代數(shù)方法、改進(jìn)的差別矩陣方法、信息熵的方法和HU矩陣的方法求得的核都是C1, C2。 表3 決策表3U C1 C2 C3 D x1 1 0 1 1 x2 1 0 1 0 x3 1 0 1 2x4 0 0 1 1 x5 0 0 1

18、 0 x6 1 1 1 1 決策表3的劃分如下：U/IND(C1,C2,C3)=x1,x2,x3,x4,x5,x6,U/IND(D)=x1,x4,x6,x2,x5,x3,正域POSC(D)= x6。去掉屬性C1,有U/IND(C2,C3)=x1,x2,x3,x4,x5,x6；去掉屬性C2,有U/IND(C1,C3)=x1,x2,x3,x6,x4,x5；去掉屬性C3有U/IND(C1,C2)=x1,x2,x3,x4,x5,x6；從上面的計(jì)算可知：決策表3中相容部分為x6，相容部分的劃分為x6，存在不相容信息的部分為x1,x2,x3,x4,x5，不相容部分的劃分為x1,x2,x3,x4,x5；去掉

19、屬性C1，使不相容部分的劃分塊x1,x2,x3和x4,x5合并成了一個(gè)劃分塊x1,x2,x3,x4,x5，根據(jù)不相容核的定義，C1屬于不相容核。去掉屬性C2，使相容部分的劃分塊x6和不相容部分的劃分塊x1,x2,x3合并成了一個(gè)劃分塊x1,x2,x3,x6，導(dǎo)致正域POSC(D)發(fā)生變化，根據(jù)相容核的定義，C2屬于相容核。去掉屬性C3，相容部分的劃分和不相容部分的劃分都沒(méi)有發(fā)生變化，因此C3不屬于任何核。由以上分析可得，決策表3的核屬性集為C1, C2，其中，相容核為C2，不相容核為C1。代數(shù)方法和改進(jìn)的差別矩陣的方法求得的核是相容核C2，信息熵的方法和HU矩陣的方法求得的核是所有核C1, C

20、2。對(duì)于上面的表1、表2和表3，代數(shù)方法和改進(jìn)的差別矩陣方法完全等價(jià)，它們只能求得不相容決策表的相容核；信息熵方法有時(shí)得到的是相容核，有時(shí)得到的是全部核屬性；HU矩陣方法能計(jì)算出不相容決策表的全部核屬性。HU矩陣方法雖然得到了全部的和屬性集合，但是該矩陣把這兩種核屬性混合在一起，使人很難分辨出哪個(gè)是相容核，哪個(gè)是不相容核，這種現(xiàn)象使得許多學(xué)者一致認(rèn)為HU矩陣不適用于不相容決策表。下面通過(guò)對(duì)HU差別矩陣進(jìn)行修改，使HU矩陣中的相容核與不相容核分開(kāi)，從而得到不相容決策表的所有的核屬性集合。4 改進(jìn)的差別矩陣HU差別矩陣定義如下：定義6 對(duì)于信息系統(tǒng)S=(U,A,V,f)，A=CD，CD= ，C和D

21、分別是條件屬性和決策屬性。S的可辨識(shí)矩陣M是一個(gè)n*n對(duì)稱矩陣，a(x)是記錄x在屬性a上的值，表示可辨識(shí)矩陣中第i行，第j列的元素，因此可辨識(shí)矩陣的定義為：= 文獻(xiàn)中給出如下結(jié)論：當(dāng)且僅當(dāng)某個(gè)mij為單個(gè)屬性時(shí),該屬性屬于核CORE(C)。根據(jù)前面給出的相容核與不相容核的計(jì)算過(guò)程及方法，修改HU矩陣為下面兩個(gè)新的矩陣分別計(jì)算不相容決策表的相容核與不相容核。定義7 對(duì)于信息系統(tǒng)S=(U,A,V,f)，A=CD，CD=，C和D分別是條件屬性和決策屬性。S的可辨識(shí)矩陣為CD(i,j)和CD(i,j)分別定義如下：， 其他情況CD(i,j)= 其中U1=POSC(D)，當(dāng)CD(i,j)為單個(gè)屬性時(shí)，

22、該屬性是相容部分的核屬性，與代數(shù)觀的核屬性定義方法計(jì)算的核屬性等價(jià)。， 其他情況CD(i,j)= 其中U2=U-POSC(D)，當(dāng)CD(i,j)為單個(gè)屬性時(shí)，該屬性是不相容部分的核屬性，刪除該屬性將導(dǎo)致不相容部分發(fā)生變化，即某些不相容塊發(fā)生合并。它的存在保證了不相容部分的分類與原始決策表的不相容部分分類一致。下面使用改進(jìn)的差別矩陣，計(jì)算以上三個(gè)不相容決策表的相容核與不相容核，由于矩陣的對(duì)稱性，只計(jì)算這些矩陣的下三角矩陣。對(duì)決策表1使用新的差別矩陣分別計(jì)算相容核與不相容核。 由矩陣CD(i,j)的定義計(jì)算得到如下矩陣。 表4 決策表1的差別矩陣CD(i,j) x1 x2 x3 x4 x5 x1

23、x2 x3 x4 x5 C2 C1,C2 由于C2是矩陣CD(i,j)中的單個(gè)屬性，因此，C2是相容核。由矩陣CD(i,j)的定義計(jì)算得到如下矩陣。 表5 決策表1的差別矩陣CD(i,j) x1 x2 x3 x4 x5 x1 x2 x3 C1 x4 C1 x5 由于C1是矩陣CD(i,j)中的單個(gè)屬性，因此，C1是不相容核。對(duì)決策表2使用新的差別矩陣分別計(jì)算相容核與不相容核。 由矩陣CD(i,j)的定義計(jì)算得到如下矩陣。 表6 決策表2的差別矩陣CD(i,j) x1 x2 x3 x4 x1 x2 C1 x3 x4 C1 C1,C2 由于C1，C2都是矩陣CD(i,j)中的單個(gè)屬性，因此，C1，

24、C2都是相容核。由矩陣CD(i,j)的定義計(jì)算得到如下矩陣。 表7 決策表2的差別矩陣CD(i,j) x1 x2 x3 x4 x1 x2 x3 x4 由于矩陣CD(i,j)中的沒(méi)有單個(gè)屬性，因此，該決策表的不相容核為。對(duì)決策表3使用新的差別矩陣分別計(jì)算相容核與不相容核。由矩陣CD(i,j)的定義計(jì)算得到如下矩陣。 表8 決策表3的差別矩陣CD(i,j) x1 x2 x3 x4 x5 x6 x1 x2 x3 x4 x5 x6 C2 C2 C1,C2 由于C2是矩陣CD(i,j)中的單個(gè)屬性，因此，C2是相容核。由矩陣CD(i,j)的定義計(jì)算得到如下矩陣。 表9 決策表3的差別矩陣CD(i,j) x1 x2 x3 x4 x5 x6 x1 x2 x3 x4 C1 C1 x5 C1 C1 x6 由于C1是矩陣CD(i,j)中的單個(gè)屬性，因此，C1是不